A Distributed Algorithm for Finding Maximum Barrier Coverage in Wireless Sensor Networks

Constructing sensor barriers to detect intruders crossing restricted regions, such as country borders, is one of the major application categories for wireless sensor networks. In this paper, we present a distributed algorithm to find the maximum number of disjoint sensor barriers in wireless sensor networks. Our solution works for any sensor deployment, for any size and shape of a covered region, and even for heterogeneous sensor nodes. In particular, our algorithm is distributed and works perfectly in an asynchronous communication environment. It utilizes the property of wireless channel and has lower complexity compared with other algorithms. For a deployment of n sensors, our algorithm spends O(n²) messages and O(n²) time.