Construction of node- and link-fault-tolerant virtual backbones in wireless networks

In wireless sensor networks (WSNs), the virtual backbone (VB) consists of a subset of nodes, which are responsible for routing tasks. Fault-tolerant VBs are desirable for overcoming the effects of node or link failure in WSNs. Usually, a homogeneous WSN (VB) is abstracted as a unit disk graph (UDG) (connected dominating set(CDS)). This paper introduces the concept of a fault-tolerant CDS in a UDG called a ((2, 2), m)-CDS, which is different from a traditional fault-tolerant CDS ((k, m)-CDS). A ((2, 2), m)-CDS can still function even if one edge or one node fails, which implies that it possesses fault-tolerant properties for both nodes and edges, in contrast to traditional (k, m)-CDSs, which possess fault tolerance only for nodes. Then, we propose a 5 α-approximation algorithm for computing a ((2, 2), m)-CDS, where α is the performance ratio for computing a (2, m) -CDS, and analyze its time complexity. In simulations, we compare our algorithm with an existing algorithm for fault-tolerant CDS construction based on CDS size. From the simulations, we find that our algorithm outperforms its competitor in constructing a quality VB.