Improving the Lifetime of Non-penetrable Barrier Coverage in Sensor Networks

An area covered by a wireless sensor network is protected, or covered, by a sensor barrier if there exists a subset of sensors that divide the area into two regions, such that no intruder can move from one region into the other without being detected. To maximize the length of time the area is covered by a barrier, the sensors can be divided into multiple disjoint subsets, where each subset is a barrier. By having only one barrier active at any time, the duration of the coverage is maximized. Algorithms exist that divide the sensors into the maximum number of barriers, and thus, maximize network lifetime. Recently, a new security problem was discovered, known as a barrier-breach, that allows an intruder to cross the area while one barrier is being replaced by another. This is dependent not on the structure of an individual sensor barrier, but in the relative shape of two consecutive sensor barriers. Heuristics have been presented to choose the maximum number of sensor barriers without a barrier breach. In this paper, we redefine the barrier breach problem in such a way that it motivates a different heuristic for its solution. Through simulations, we show that our heuristic significantly outperforms the best known heuristic, and thus, it improves network lifetime and/or fault-tolerance.