Packing of cutsets for a breach path detection problem
Mohammed Elmorsy, Ehab S. Elmallah · 2016
The breach path detection reliability (BPDREL) problem is a core Wireless Sensor Networks (WSNs) surveillance problem discussed in the literature. The problem concerns WSNs deployed to guard an area with multiple entry-exit sides where intruders can cross the area through any specified subset of sides. Nodes in the network can fail randomly, and we ask what is the likelihood that the network can successfully detect intrusion events. Our work here develops methods for deriving upper bounds on the solutions by means of packing network nodes into cutsets having certain properties. The developed methods are efficient and can be used either as standalone tools, or as subroutines to improve the time-accuracy of other iterative methods that can achieve higher accuracy with increased number of iterations. The obtained numerical results are used to analyze the merits of the devised methods. In addition, we discuss and evaluate the applicability of our methods to tackle an optimum sink location design problem.