A robust relay node placement heuristic for structurally damaged wireless sensor networks

Wireless sensor networks (WSN) can increase the efficiency of many real-life applications through the collaboration of thousands of miniaturized sensors which can be deployed unattended in inhospitable environments. Due to the harsh surroundings and violent nature of the applications, the network sometimes suffers a large scale damage that involves many nodes and would thus create multiple disjoint partitions. This paper investigates a strategy for recovering from such damage through the placement of relay nodes and promotes a novel approach. The proposed approach opts to re-establish connectivity using the least number of relays while ensuring certain quality in the formed topology. Unlike contemporary schemes that form a minimum spanning tree among the isolated segments, the proposed approach establishes a topology that resembles a spider web, for which the segments are situated at the perimeter. Such a topology not only exhibits stronger connectivity than a minimum spanning tree but also achieves better sensor coverage and enables balanced distribution of traffic load among the employed relays. The simulation results demonstrate the effectiveness of the proposed recovery algorithm.