Fault-tolerant relay deployment for k node-disjoint paths in wireless sensor networks

Ensuring that wireless sensor networks (WSNs) are robust to failures requires that the physical network topology will offer alternative routes to the sinks. This requires sensor network deployments to be planned with an objective of ensuring some measure of robustness in the topology, so that when failures occur that routing protocols can continue to offer reliable delivery. Our contribution is a solution that enables fault-tolerant WSN deployment planning by judicious use of a minimum number of additional relay nodes. A WSN is robust if at least one route to a sink is available for each remaining sensor node after the failure of up to k-1 nodes. In this paper, we define the problem for increasing WSN reliability by deploying a number of additional relay nodes to ensure that each sensor node in the initial design has k node-disjoint paths to the sinks. We present GRASP-ARP, a centralised offline algorithm to be run during the initial topology design to solve this problem. We have implemented this algorithm and demonstrated in simulation that it improves the efficiency of relay node placement for k node-disjoint paths compared to the most closely related published algorithms.