On Construction of Quality Fault-Tolerant Virtual Backbone in Wireless Networks
Wei Wang, Donghyun Kim, Min Kyung An, Wei Gao, Xianyue Li, Zhao Zhang, Weili Wu · IEEE/ACM Transactions on Networking · 2012
In this paper, we study the problem of computing quality fault-tolerant virtual backbone in homogeneous wireless network, which is defined as the$k$-connected$m$-dominating set problem in a unit disk graph. This problem is NP-hard, and thus many efforts have been made to find a constant factor approximation algorithm for it, but never succeeded so far with arbitrary$k\geq 3$and$m\geq 1$pair. We propose a new strategy for computing a smaller-size 3-connected$m$-dominating set in a unit disk graph with any$m\geq 1$. We show the approximation ratio of our algorithm is constant and its running time is polynomial. We also conduct a simulation to examine the average performance of our algorithm. Our result implies that while there exists a constant factor approximation algorithm for the$k$-connected$m$-dominating set problem with arbitrary$k\leq 3$and$m\geq 1$pair, the$k$-connected$m$-dominating set problem is still open with$k>3$.