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 nn sensors and a cost measurement with maximum value Cmax, our algorithm has O(n2log(nCmax)) message complexity and O(n2log(nCmax)) time complexity to find KK 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 n2n2.

► A distributed algorithm to build wireless sensor barriers with minimum cost.
► Finds barriers with the best message complexity and time complexity.
► Scalable to any size and shape of homogeneous or heterogeneous networks.
► Nodes set up wireless barriers without knowing their exact locations.