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

Abstract

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(n2log n) time algorithm. We obtain Θ(n3) 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.