Approximation algorithm for minimum weight fault-tolerant virtual backbone in homogeneous wireless sensor network
Zhao Zhang, Yishuo Shi · 2015
In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. Such a consideration leads to the problem of finding a minimum weight k-connected m-fold dominating set ((k, m)-MWCDS for short). In this paper, we give an (α + 2.5ρ)-approximation for (2, m)-MWCDS with m ≥ 2 in unit disk graph, where α is the performance ratio for the minimum weight m-fold dominating set problem, and ρ is the performance ratio for the {0,1,2}-Steiner Network Design problem. In view of currently best known ratios for α and ρ, (2, m)-MWCDS has a (9 + ε)-approximation for m ≥ 3 and a (8 + ε)-approximation for m =2, where ε is an arbitrary positive real number.