Barrier Resilience in Wireless Sensor Networks

by S. Bereg and D. G. Kirkpatrick

Abstract: Barrier coverage in a sensor network has the goal of ensuring that all paths through the surveillance domain joining points in some start region S to some target region T will intersect the coverage region associated with at least one sensor. In this paper, we revisit a notion of redundant barrier coverage known as k-barrier coverage.

We describe two different notions of width, or impermeability, of the barrier provided by the sensors in A to paths joining two arbitrary regions S to T. The first, what we refer to as the thickness of the barrier, counts the minimum number of sensor region intersections, over all paths from S to T. The second, what we refer to as the resilience of the barrier, counts the minimum number of sensors whose removal permits a path from S to T with no sensor region intersections. Of course, a configuration of sensors with resilience k has thickness at least k and constitutes a k-barrier for S and T.

Our result demonstrates that any (Euclidean) shortest path from S to T that intersects a fixed number of distinct sensors, never intersects any one sensor more than three times. It follows that the resilience of A (with respect to S and T) is at least one-third the thickness of A (with respect to S and T). (Furthermore, if points in S and T are moderately separated (relative to the radius of individual sensor coverage) then no shortest path intersects any one sensor more than two times, and hence the resilience of A is at least one-half the thickness of A.)

A second result, which we are only able to sketch here, shows that the approximation bounds can be tightened (to 1.666 in the case of moderately separated S and T) by exploiting topological properties of simple paths that make double visits to a collection of disks.
The resilience of the barrier between S and T is equal to 1 as there is a path crossong only one sensor.

pdf file


@inproceedings{bk-abrwsn-09
, author = {Sergey Bereg and David G. Kirkpatrick}
, title = {Approximating Barrier Resilience in Wireless Sensor Networks}
, booktitle = {Proc. of the 5th Internat. Workshop on Algorithmic Aspects of
    Wireless Sensor Networks}
, year = {2009}
, series = {LNCS 5804}
, pages = {29--40}
, url = {http://dx.doi.org/10.1007/978-3-642-05434-1_5}
}