On Enhancing Fault Tolerance of Virtual Backbone in a Wireless Sensor Network with Unidirectional Links

A wireless sensor network (WSN) is a collection of energy constrained sensor node forming a network which lacks infrastructure or any kind of centralized management. In such networks, virtual backbone has been proposed as the routing infrastructure which can alleviate the broadcasting storm problem occurring due to consistent flooding performed by the sensor node, to communicate their sensed information. As the virtual backbone nodes needs to carry other nodes’ traffic, they are more subject to failure. Hence, it is desirable to construct a fault tolerant virtual backbone. Most of recent research has studied this problem in homogeneous networks. In this chapter, we propose solutions for efficient construction of a fault tolerant virtual backbone in a WSN where the sensor nodes have different transmission ranges. Such a network can be modeled as a disk graph (DG), where link between the two nodes is either unidirectional or bidirectional. We formulate the fault tolerant virtual backbone problem as a k-Strongly Connected m-Dominating and Absorbing Set (k, m) SCDAS problem. As the problem is NP-hard, we propose an approximation algorithm along with the theoretical analysis and conjectured its approximation ratio.