On Breach Path Detection Reliability of Wireless Sensor Grids

We consider wireless sensor networks (WSNs) deployed in the plane for area surveillance against intrusion attacks. Sensor nodes often employ low-cost sensing and wireless communication modules that are prone to random failure especially when operated in harsh environments. To quantify the network´s ability to monitor the area, we formalize the breach path detection reliability (BPDREL) problem that takes as input a specified set of entry-exit pairs of network sides, and calls for computing the likelihood that the network can detect intrusion paths between any of the specified pairs of sides. We devise an exact algorithm for solving the problem on networks that can be embedded in grid networks utilizing diagonal links. Using the devised algorithm, we analyze the least and most detectable classes of intrusion paths, as well as the impact of varying various network parameters on the overall network reliability.