Fault-Tolerant Virtual Backbone in Heterogeneous Wireless Sensor Network

To save energy and alleviate interference, connected dominating set CDS was proposed to serve as a virtual backbone of wireless sensor networks WSNs. Because sensor nodes may fail due to accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone with high redundancy in both coverage and connectivity. This can be modeled as a k-connected m-fold dominating set abbreviated as k,m-CDS problem. A node set CVG is a k,m-CDS of graph G if every node in VG\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. Constant approximation algorithm is known for 3,m-CDS in unit disk graph, which models homogeneous WSNs. In this paper, we present the first performance guaranteed approximation algorithm for 3,m-CDS in a heterogeneous WSN. In fact, our performance ratio is valid for any topology. The performance ratio is at mostγ, where γ=α +8+2ln 2α-6 forα≥4 andγ=3α+2ln2 forα.