Minimum Movement Relocation Strategies for Barrier Coverage on a Line Segment

Mobile sensor network is a cost effective and powerful tool for numerous applications including border protection and combat field surveillance. Barrier coverage is a critical issue that can provide protection with minimal number of planted sensors by enclosing only the border. Initially sensors are planted randomly along a line. There exists gaps if every point of the line segment is not within the sensing range of at least one sensor. It is important to exploit sensor mobility to improve barrier coverage. However it is challenging to compute the desired location that offers coverage improvement while conserving energy due to sensor movement. Given a set of sensors in random initial positions, we study the problem of computing final positions to maximize the barrier coverage of a line segment with minimal movement of sensors. We formulate the problem as linear programming framework with two variants of the objective functions: 'MinSum' that minimizes the sum of sensor movements, and 'MinMax' that minimizes the maximum distance traversed among all sensors. If the total sensing ranges of all sensors is greater than the length of the line segment, then complete coverage is possible. If the total sensing ranges of all sensors is less than the length of the line, then two different types of maximal coverage is possible: noncontiguous and contiguous. We study the same problem for variable sensing range. We also present a computationally efficient heuristic algorithm for variable range 'MinSum' problem. We demonstrate the effectiveness of these formulations on a variety of examples and provide comparisons with alternative strategies through extensive simulations.