Minimizing maximum movement of sensors for line barrier coverage in the plane

Border surveillance for intrusion detection is an important application of wireless sensor networks (WSNs). Given a set of mobile sensors and their initial positions, how to move these sensors to a region border to achieve barrier coverage energy-efficiently is challenging. This paper studies the 2-D MinMax barrier coverage problem of moving n sensors in a two-dimensional plane to form a barrier coverage of a specified line segment in the plane while minimizing the maximum sensor movement for the sake of balancing battery power consumption. Previously, this problem was shown to be NP-hard for the general case when the sensing ranges are arbitrary. It was an open problem whether the problem is polynomial-time solvable for the case when sensors have a fixed number of sensing ranges. We first study the barrier coverage problem for the general case and propose a two-phase algorithm and a greedy algorithm. The approximation factor of the two-phase algorithm is proved to be 2 for the case when the sensors can exactly cover the barrier. We then study a special case of great practical significance that the sensors have the same sensing range and present an O(n²log n) time algorithm. We obtain Θ(n³) candidate values for the minimum maximum sensor movement by deriving a necessary condition of the optimal sensor deployment and find the optimal sensor movement among them by using an efficient search procedure and a decision algorithm. To the best of our knowledge, this is the first result for solving the 2-D MinMax barrier coverage problem both for the general case and the uniform case.