Restoring Virtual Backbone of Wireless Sensor Network Using Position Restricted Relay Nodes

In Wireless Sensor Network (WSN), sensor nodes send sensed data through multi-hops involving intermediate relay nodes. Construction of virtual backbone (VB) of sensor network is preferred to reduce the energy depletion of the WSN. The VB brings substantial benefits by simplifying routing and topology control. In WSN, sensors are prone to failure, due to power depletion or some other reasons. Therefore, the existing VB may be partitioned into segments after failure. Hence, re-construction of VB is an important issue in sensor network. This can be achieved either by discovering alternate backbone or by redeployment additional new relay nodes to restore the VB. This paper proposes an efficient strategy for restoring VB by connecting disconnected VBs using minimum relay nodes. Finding the optimal number of relay nodes and their positions is NP-hard, heuristic algorithms are proposed to minimize the repairing cost.