Fault-Tolerant Virtual Backbone in Heterogeneous Wireless Sensor Network

• Published in: IEEE/ACM transactions on networking 2017-12, Vol.25 (6), p.3487-3499
• Main Authors: Zhou, Jiao, Zhang, Zhao, Tang, Shaojie, Huang, Xiaohui, Mo, Yuchang, Du, Ding-Zhu
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Approximation; approximation algorithm; Approximation algorithms; Backbone; Computer science; connected dominating set; Damage tolerance; Decision trees; Depletion; Energy conservation; Fault tolerance; Fault tolerant systems; Graph theory; Mathematical analysis; Nodes; Redundancy; Remote sensors; Sensors; Topology; virtual backbone; Virtual networks; Wireless sensor network; Wireless sensor networks
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2017.2740328

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 C ⊆ V (G) is a (k, m)-CDS of graph G if every node in V(G)\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 + 2 ln(2α - 6) for α ≥ 4 and γ = 3α +2 ln 2 for α