Constructing sensor barriers with minimum cost in wireless sensor networks

摘要

One major application category for wireless sensor networks is to detect intruders entering protected areas. Early research has studied the barrier coverage problem for intruder detection. However, an open problem is to build sensor barriers with minimum cost in wireless sensor networks. This is a critical problem (called minimum-cost barrier coverage), and its solution can be widely used in sensor barrier applications, such as border security and intruder detection. In this paper, we present a complete solution to the minimum-cost barrier coverage problem. The cost here can be any performance measurement and normally is defined as the resource consumed or occupied by the sensor barriers. Our algorithm, called the PUSH-PULL-IMPROVE algorithm, is the first one that provides a distributed solution to the minimum-cost barrier coverage problem in asynchronous wireless sensor networks. It can be used for protected areas of any size and shape with homogeneous or heterogeneous networks. In our algorithm, each node does not necessarily know its exact location and only needs to communicate with its neighbors. For a deployment of n sensors and a cost measurement with maximum value C_(max), our algorithm has O(n~2log(nC_(max))) message complexity and O(n~2log(nC_(max))) time complexity to find K barriers. Simulation results verify the performance of the algorithm. We observe that the actual number of messages sent in the simulations is much less than n~2.