PINC: Pickup Non-Critical Node Based <i>k</i>-Connectivity Restoration in Wireless Sensor Networks

Abstract

A Wireless Sensor Network (WSN) is connected if a communication path exists among each pair of sensor nodes (motes). Maintaining reliable connectivity in WSNs is a complicated task, since any failure in the nodes can cause the data transmission paths to break. In a k-connected WSN, the connectivity survives after failure in any k-1 nodes; hence, preserving the k-connectivity ensures that the WSN can permit k-1 node failures without wasting the connectivity. Higher k values will increase the reliability of a WSN against node failures. We propose a simple and efficient algorithm (PINC) to accomplish movement-based k-connectivity restoration that divides the nodes into the critical, which are the nodes whose failure reduces k, and non-critical groups. The PINC algorithm pickups and moves the non-critical nodes when a critical node stops working. This algorithm moves a non-critical node with minimum movement cost to the position of the failed mote. The measurements obtained from the testbed of real IRIS motes and Kobuki robots, along with extensive simulations, revealed that the PINC restores the k-connectivity by generating optimum movements faster than its competitors.

Keywords

• Wireless Sensor Networks
• connectivity restoration
• <i>k</i>-connectivity
• mobility
• reliability
• minimum vertex cut