An approach for bounding breach path detection reliability in wireless sensor networks

This paper considers wireless sensor networks (WSNs) deployed to provide surveillance against intruders that wish to cross a given area. Due to limited resources, low manufacturing cost, and operation in harsh environments, nodes in such networks are subject to random failure in the field. Hence, there is a need to develop suitable reliability assessment mechanisms to quantify a WSN´s ability to perform successfully. Here, we consider one such measure, called the breach path detection reliability (BPDREL), that applies to networks where any intruder crossing a line segment between some adjacent operating pairs of sensor nodes can be detected, and the network perimeter is made of a polygon of such line segments. Each breach path across the network is associated with a pair of entry-exit sides on the perimeter. Our measure takes into account intrusion events associated with any user-specified set of such entry-exit sides. Computing the exact BPDREL can be shown to be #P-hard. We extend existing results on the BPDREL by developing an approach for deriving lower bounds on the problem for arbitrary WSNs where the sink node is located on the network´s perimeter. The resulting algorithm is used to analyze the impact of varying various network parameters on the overall network reliability.