A fault-tolerant relay placement algorithm for ensuring k vertex-disjoint shortest paths in wireless sensor networks

Wireless sensor networks (WSNs) are prone to failures. To be robust to failures, the network topology should provide alternative routes to the sinks so when failures occur the routing protocol can still offer reliable delivery. Our contribution is a solution that enables fault-tolerant WSN deployment planning by judicious use of a minimum number of additional relays. A WSN is robust if at least one route with an acceptable length to a sink is available for each sensor node after the failure of any k-1 nodes. In this paper, we define the problem for increasing WSN reliability by deploying a number of additional relays to ensure that each sensor node in the initial design has k length-bounded vertex-disjoint shortest paths to the sinks. To identify the maximum k such that each node has k vertex-disjoint shortest paths, we propose Counting-Paths and its dynamic programming variant. Then, we introduce GRASP-ARP, a centralised offline algorithm that uses Counting-Paths to minimise the number of deployed relays. Empirically, it deploys 35% fewer relays with reasonable runtime compared to the closest approach. Using network simulation, we show that GRASP-ARP's designs offer a substantial improvement over the original topologies, maintaining connectivity for twice as many surviving nodes after 10% of the original nodes have failed.