On path exposure in probabilistic wireless sensor networks

We consider wireless sensor networks for surveillance applications where a node´s ability to detect and report intrusion is described probabilistically. In addition, intruders traversing an area may probabilistically disrupt sensors by spreading jamming devices. Thus, at any instant a network can be either in an operating state that enables detection, or a failed state. To analyze the likelihood that a network is in an operating state, we formalize a problem called the path exposure (EXPO) problem. We show that EXPO is #P-hard and then devise an algorithm that works by processing most probable network states first. Our algorithm computes exact solutions for small networks efficiently. For large networks, the algorithm computes lower and upper bounds on a solution. The obtained simulation results analyze the gap between the obtained lower and upper bounds. We also demonstrate the use of our algorithm as a tool in analyzing two related intrusion problems.