On Construction of Quality Fault-Tolerant Virtual Backbone in Wireless Networks
On Construction of Quality Fault-Tolerant Virtual Backbone in Wireless Networks
复制标题
DOI：
10.1109/tnet.2012.2227791
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Wei Wang;Donghyun Kim;Min Kyung An;Wei Gao;Xianyue Li;Zhao Zhang;Weili Wu
中科院分区：
文献类型：
--
作者：
Wei Wang;Donghyun Kim;Min Kyung An;Wei Gao;Xianyue Li;Zhao Zhang;Weili Wu
本文研究了同构无线网络中计算质量容错虚拟骨干网问题，将其定义为单位磁盘图中的k连通m支配集问题。这个问题是np困难的，因此已经做了很多努力来找到一个常因子近似算法，但迄今为止还没有成功的任意k≥3和m≥1对。对于任意m≥1的单元磁盘图，我们提出了一种计算较小尺寸3连通m支配集的新策略。结果表明，该算法的近似比为常数，运行时间为多项式。我们还进行了模拟，以检查我们的算法的平均性能。我们的结果表明，对于任意k≤3且m≥1对的k连通m控制集问题，虽然存在常因子逼近算法，但k连通m控制集问题在k > 3时仍然是开放的。
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 ≥ 3 and m ≥ 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 ≥ 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 ≤ 3 and m ≥ 1 pair, the k-connected m-dominating set problem is still open with k > 3.