On the Devolution of Large-Scale Sensor Networks in the Presence of Random Failures

In battery-constrained large-scale sensor networks, nodes are prone to random failures due to various reasons, such as energy depletion and hostile environment. Random failures can substantially impact the communication connectivity, which in turn impairs the sensing coverage. Redeploying additional sensors is one effective way to maintain the connectivity; however, it may be infeasible and costly to replace failed sensors one by one. When should a redeployment be conducted is an interesting and important question in designing resilient sensor networks. In this paper, we tackle this problem by investigating the devolution process of large-scale sensor networks. We first define a new metric called the first partition time, which is the first time that a network starts to discomposes to multiple isolated small components. Then we analyze the devolution process in a geometric random graph from a percolation-based connectivity perspective and obtain the condition under which the graph is not percolated. Finally, we find out that the lower bound of the first partition time depends on the node lifetime distribution and should be of the order between log (log n) and (log n)^1/rho for rho > 1. This result provides a theoretical upper bound of the latest time that a redeployment has to be carried out.