On The Reliability of Wireless Sensor Networks

In wireless sensor networks (WSN), reliable monitoring of a phenomenon (or event detection) depends on the collective data provided by the target cluster of sensors and not on any individual node. In this paper we define a WSN reliability measure that considers the aggregate flow of sensor data into a sink node (gateway or cluster head). Given an estimation of the data generation rate and the failure probability of each sensor, we formulate the reliability measure and show that computing this measure for an arbitrary WSN is #P-hard. We present an exponential algorithm for arbitrary WSN. We then consider some special cases where we can either compute or approximate (bound) the reliability using an efficient algorithm. Finally, we present some numerical results that demonstrate some of the applications of our algorithms. Reliability evaluation tools are important in the context of design and analysis of sensitive information gathering sensor networks.