Barrier Resilience in Wireless Sensor Networksby S. Bereg and D. G. KirkpatrickAbstract: 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.
@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} } |