On Practical Construction of Quality Fault-Tolerant Virtual Backbone in Homogeneous Wireless Networks
On Practical Construction of Quality Fault-Tolerant Virtual Backbone in Homogeneous Wireless Networks
复制标题
DOI：
10.1109/tnet.2017.2780262
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Bei Liu;Wei Wang;Donghyun Kim;Yingshu Li;Sung-Sik Kwon;Yaolin Jiang
中科院分区：
文献类型：
--
作者：
Bei Liu;Wei Wang;Donghyun Kim;Yingshu Li;Sung-Sik Kwon;Yaolin Jiang
多年来，人们对无线网络中高质量容错虚拟骨干网的构建问题进行了大量的研究。当无线网络由物理上相等的节点组成，例如具有相同的通信范围时，广泛使用单元磁盘图（unit disk graph， UDG）来抽象无线网络，并将问题表述为UDG上的最小$k$ -连通$m$ -支配集问题。到目前为止，大多数研究成果都集中在设计一个常因子近似算法来解决这个np困难问题，该问题满足$m \geq k \geq 1$和$k \leq 3$两个正整数$k$和$m$。本文介绍了一种求解$m \geq k \geq 1$问题的近似算法。该算法实现简单；它通过添加有限数量的路径连接组件，首先计算1连接$m$主导集$D$，并重复以下步骤：(a)使用$i = 2, 3, \cdots, k$在$(i-1,m)$ -CDS中任意搜索分隔符，(b)在$(i-1,m)$ -CDS中添加有限数量的连接分隔符分隔的组件的路径，以提高$(i-1,m)$ -CDS的连通性，直到它成为$k$连接，(c)如果每次迭代都存在冗余路径，则删除冗余路径。我们提供了一个严格的理论分析来证明所提出的算法是正确的，它的近似比是一个常数，对于任何固定$k$。
Over years, many efforts are made for the problem of constructing quality fault-tolerant virtual backbones in wireless network. In case that a wireless network consists of physically equivalent nodes, e.g., with the same communication range, unit disk graph (UDG) is widely used to abstract the wireless network and the problem is formulated as the minimum $k$ -connected $m$ -dominating set problem on the UDG. So far, most results are focused on designing a constant factor approximation algorithm for this NP-hard problem under two positive integers $k$ and $m$ satisfying $m \geq k \geq 1$ and $k \leq 3$ . This paper introduces an approximation algorithm for the problem with $m \geq k \geq 1$ . This algorithm is simple to implement; it connects the components by adding a bounded number of paths, which first computes a 1-connected $m$ -dominating set $D$ and repeats the following steps: (a) search the separators arbitrarily in $(i-1,m)$ -CDS with $i = 2, 3, \cdots, k$ , (b) add a bounded number of paths connecting the components separated by separators in $(i-1,m)$ -CDS to improve the connectivity of $(i-1,m)$ -CDS, until it becomes $k$ -connected, and (c) remove redundant paths if there exist at every iteration. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant, for any fixed $k$ .