Restoring connectivity in wireless sensor-actor networks with minimal topology changes

In Wireless Sensor-Actor Networks (WSANs), actors collect sensor readings and respond collaboratively to achieve an application mission. Since actors coordinate their operation, a strongly connected network topology would be required at all time. In addition, the path between actors may have to be capped in order to meet latency constraints. However, a failure of an actor may cause the network to partition into disjoint blocks and would thus violate such connectivity goal. One of the effective recovery methodologies is to autonomously reposition a subset of the actor nodes to restore connectivity. Contemporary schemes rely on maintaining 1 or 2-hop neighbor lists and predetermine criteria for node's involvement in the recovery. However, 1-hop based schemes often impose high node relocation overhead. In addition, the repaired inter-actor topology using 2-hop schemes often differs significantly from its pre-failure status and some inter-actor data paths may get extended. This paper presents a Least-Disruptive topology Repair (LeDiR) algorithm. LeDiR relies on the local view of a node about the network in order 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 path discovery activities and imposes no additional pre-failure communication overhead. LeDiR is validated through simulation and is shown to outperform existing schemes.