Fault tolerant connected sensor cover with variable sensing and transmission ranges

Sensor networks are often deployed in a redundant fashion. In order to prolong the network lifetime, it is desired to choose only a subset of sensors to keep active and put the rest to sleep. In order to provide fault tolerance, this small subset of active sensors should also provide some degree of redundancy. In this paper, we consider the problem of choosing a minimum subset of sensors such that they maintain a required degree of coverage and also form a connected network with a required degree of fault tolerance. In addition, we consider a more general, variable radii sensor model, wherein every sensor can adjust both its sensing and transmission ranges to minimize overall energy consumption in the network. We call this the variable radii k ₁ -Connected, k ₂-Cover problem. To address this problem, we propose a distributed and localized Voronoi-based algorithm. The approach extends the relative neighborhood graph (RNG) structure to preserve k-connectivity in a graph, and design a distributed technique to inactivate desirable nodes while preserving k-connectivity of the remaining active nodes. We show through extensive simulations that our proposed techniques result in overall energy savings in random sensor networks over a wide range of experimental parameters.