Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance

Wireless sensor network (WSN) applications, especially those serving in inhospitable environments such as battlefield reconnaissance, are susceptible to large-scale damage which usually causes simultaneous failure of multiple collocated sensors and gets the network divided into disjoint partitions. In order to prevent the WSN from being inoperative, restoring the overall network connectivity is crucial. Furthermore, it may be desirable to make the repaired network topology resilient to future single node failures caused by aftermath. In this paper, we present an effective strategy for achieving such recovery goal by establishing a bi-connected inter-partition topology while minimizing the maximum path length between pairs for partitions and deploying the least count of relay nodes (RNs). Finding the optimal number and position of RNs is NP-hard and we thus pursue heuristics. The proposed Connectivity Restoration with Assured Fault Tolerance (CRAFT) algorithm strives to form the largest inner simple cycle or backbone polygon (BP) around the center of the damaged area where no partition lies inside. RNs are then deployed to connect each outer partition to the BP through two non-overlapping paths. We analyze the properties of CRAFT mathematically and validate its performance through extensive simulation experiments. The validation results show that CRAFT yields highly connected topologies with short inter-partition paths while employing fewer RNs than competing schemes.