Recovering from a node failure in wireless sensor-actor networks with minimal topology changes

In wireless sensor-actor networks, sensors probe their surroundings and forward their data to actor nodes. Actors collaboratively respond to achieve predefined application mission. Since actors have to coordinate their operation, it is necessary to maintain a strongly connected network topology at all times. Moreover, the length of the inter-actor communication paths may be constrained to meet latency requirements. However, a failure of an actor may cause the network to partition into disjoint blocks and would, thus, violate such a connectivity goal. One of the effective recovery methodologies is to autonomously reposition a subset of the actor nodes to restore connectivity. Contemporary recovery schemes either impose high node relocation overhead or extend some of the inter-actor data paths. This paper overcomes these shortcomings and presents a Least-Disruptive topology Repair (LeDiR) algorithm. LeDiR relies on the local view of a node about the network to devise a recovery plan that relocates the least number of nodes and ensures that no path between any pair of nodes is extended. LeDiR is a localized and distributed algorithm that leverages existing route discovery activities in the network and imposes no additional prefailure communication overhead. The performance of LeDiR is analyzed mathematically and validated via extensive simulation experiments.