Partition Connectivity Recovery based on Relay Node Deployment for Wireless Sensor Networks

Partition Connectivity Recovery based on Relay Node Deployment for Wireless Sensor Networks

In this paper, we address the problem of partition connectivity recovery based on relay node deployment for wireless sensor networks. We firstly propose a graph theory based method to accurately detect partitions in the network which consists of vast low-energy sensor nodes. To restore the communication links between these partitions, we present a heuristic Steiner tree based partition recovery algorithm by deploying high-energy relay nodes. The suitable quadrilaterals or triangles are chosen to connect the disjoint partitions and their Steiner nodes are found. The minimum number of relay nodes are placed on the edges of Steiner tree. Experimental results show that our algorithm can achieve partition connectivity recovery for wireless sensor networks with a smaller number of relay nodes and less energy consumption of network communication compared to MST algorithm.