Exploring Redundancy in Sensor Deployment to Improve Fault Tolerance

Fault tolerance is an important feature required for sustained and reliable operations of wireless sensor networks. This feature is typically provided by deploying redundant sensors, which is often treated as an NP-complete k-Coverage problem where every point in the region must be covered by at least k sensors. We extend the classical k-Coverage problem to a connected version in a two-dimensional continuous space. We derive a necessary and sufficient condition for checking the sensing coverage of a region based on rigorous geometric reasoning, and analytically derive the upper bound of k for any given network. We propose a heuristic approach to this problem and evaluate its performance through extensive simulations.