Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree

In some applications, wireless sensor networks (WSNs) operate in very harsh environments and nodes become subject to increased risk of damage. Sometimes a WSN suffers from the simultaneous failure of multiple sensors and gets partitioned into disjoint segments. Restoring network connectivity in such a case is crucial in order to avoid negative effects on the application. Given that WSNs often operate unattended in remote areas, the recovery should be autonomous. This paper promotes an effective strategy for restoring the connectivity among these segments by populating the least number of relay nodes. Finding the optimal count and position of relay nodes is NP-hard and heuristics are thus pursued. We propose a Distributed algorithm for Optimized Relay node placement using Minimum Steiner tree (DORMS). Since in autonomously operating WSNs it is infeasible to perform a network-wide analysis to diagnose where segments are located, DORMS moves relay nodes from each segment toward the center of the deployment area. As soon as those relays become in range of each other, the partitioned segments resume operation. DORMS further model such initial inter-segment topology as Steiner tree in order to minimize the count of required relays. Disengaged relays can return to their respective segments to resume their pre-failure duties. We analyze DORMS mathematically and explain the beneficial aspects of the resulting topology with respect to connectivity, and traffic balance. The performance of DORMS is validated through extensive simulation experiments. (C) 2010 Elsevier Inc. All rights reserved.