Barrier resilience

Barrier resilience. This instance has resilience = 1 (it is possible to connect the green regions by a path that crosses only one barrier, the blue one) but the barrier must be crossed twice by the path.

Barrier resilience is an algorithmic optimization problem in computational geometry motivated by the design of wireless sensor networks, in which one seeks a path through a collection of barriers (often modeled as unit disks) that passes through as few barriers as possible.

Definitions

The barrier resilience problem was introduced by Kumar, Lai & Arora (2005) (using different terminology) to model the ability of wireless sensor networks to detect intruders robustly when some sensors may become faulty. In this problem, the region under surveillance from each sensor is modeled as a unit disk in the Euclidean plane. An intruder can reach a target region of the plane without detection, if there exists a path in the plane connecting a given start region to the target region without crossing any of the sensor disks. The barrier resilience of a sensor network is defined to be the minimum, over all paths from the start region to the target region, of the number of sensor disks intersected by the path. The barrier resilience problem is the problem of computing this number by finding an optimal path through the barriers.

A simplification of the problem, which encapsulates most of its essential features, makes the target region be the origin of the plane, and the start region be the set of points outside the convex hull of the sensor disks. In this version of the problem, the goal is to connect the origin to points arbitrarily far from the origin by a path through as few sensor disks as possible.

Another variation of the problem counts the number of times a path crosses the boundary of a sensor disk. If a path crosses the same disk multiple times, each crossing counts towards the total. The barrier thickness of a sensor network is the minimum number of crossings of a path from the start region to the target region.

Computational complexity

Barrier thickness may be computed in polynomial time by constructing the arrangement of the barriers (the subdivision of the plane formed by overlaying all barrier boundaries) and computing a shortest path in the dual graph of this subdivision.

The complexity of barrier resilience for unit disk barriers is an open problem. It may be solved by a fixed-parameter tractable algorithm whose time is cubic in the total number of barriers and exponential in the square of the resilience, but it is not known whether it has a fully polynomial time solution. The corresponding problem for barriers of some other shapes, including unit-length line segments or axis-aligned rectangles of aspect ratio close to 1, is known to be NP-hard.

A variation of the barrier resilience problem, studied by Kumar, Lai & Arora (2005), restricts both the sensors and the escape path to a rectangle in the plane. In this variation, the goal is to find a path from the top side of the rectangle to the bottom side that passes through as few of the sensor disks as possible. By applying Menger's theorem to the unit disk graph defined from the barriers, this minimal number of disks can be shown to equal the maximum number of subsets into which all of the disks can be partitioned, such that each subset contains a chain of disks passing all the way from the left to the right side of the rectangle. As Kumar, Lai & Arora (2005) showed, this characterization allows the optimal resilience to be computed in polynomial time by transforming the problem into an instance of the maximum flow problem.

For unit disks with bounded ply (the maximum number of disks that have a common intersection) there exists a polynomial-time approximation scheme for the resilience, that can be generalized to barrier shapes of the same size as each other with bounded aspect ratios. For unit disks without assuming bounded ply, the problem of computing the resilience may be approximated to within a constant factor, using the fact that for this shape of barrier the optimal path can only cross each barrier a constant number of times, so the barrier thickness and barrier resilience are within a constant factor of each other. Similar methods can be generalized to non-uniform sensors of approximately equal size.

References

• Alt, Helmut; Cabello, Sergio; Giannopoulos, Panos; Knauer, Christian (2011), Minimum cell connection and separation in line segment arrangements, arXiv:1104.4618, Bibcode:2011arXiv1104.4618A.
• Bereg, Sergey; Kirkpatrick, David (2009), "Approximating barrier resilience in wireless sensor networks", Algorithmic Aspects of Wireless Sensor Networks: 5th International Workshop, ALGOSENSORS 2009, Rhodes, Greece, July 10-11, 2009, Revised Selected Papers, Lecture Notes in Computer Science, vol. 5804, Springer, pp. 29–40, Bibcode:2009LNCS.5304...29B, CiteSeerX 10.1.1.174.7950, doi:10.1007/978-3-642-05434-1_5, ISBN 978-3-642-05433-4.
• Chan, David Yu Cheng; Kirkpatrick, David (2013), "Approximating barrier resilience for arrangements of non-identical disk sensors", Algorithms for Sensor Systems: 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7718, Springer, pp. 42–53, doi:10.1007/978-3-642-36092-3_6, ISBN 978-3-642-36091-6.
• Korman, Matias; Löffler, Maarten; Silveira, Rodrigo I.; Strash, Darren (2014), "On the complexity of barrier resilience for fat regions", Algorithms for Sensor Systems: 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8243, Springer, pp. 201–216, arXiv:1302.4707, doi:10.1007/978-3-642-45346-5_15, ISBN 978-3-642-45345-8, S2CID 6550993.
• Kumar, Santosh; Lai, Ten H.; Arora, Anish (2005), "Barrier coverage with wireless sensors", Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom '05, Cologne, Germany), New York, NY, USA: ACM, pp. 284–298, doi:10.1145/1080829.1080859, ISBN 1-59593-020-5, S2CID 565989.
• Tseng, Kuan-Chieh Robert; Kirkpatrick, David (2012), "On barrier resilience of sensor networks", Algorithms for Sensor Systems: 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7111, Springer, pp. 130–144, doi:10.1007/978-3-642-28209-6_11, ISBN 978-3-642-28208-9.