A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks: Research Articles
A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks: Research Articles
复制标题
一种新的分布式近似算法，用于在无线自组织网络中构造最小连通支配集：研究文章
DOI：
10.1002/dac.v18:8
复制
发表时间：
2005
影响因子：
2.1
通讯作者：
Huiye Ma
中科院分区：
文献类型：
--
作者：
Bo Gao;Yuhang Yang;Huiye Ma
近年来，由连通支配集（CDS）中的节点构建虚拟骨干网被提出来改善adhoc无线网络的性能。一般来说，控制集满足图中的每个顶点要么在集合中，要么与集合中的一个顶点相邻。一个CDS是一个支配集，它也导出一个连通子图。然而，寻找最小连通支配集（MCDS）是图论中一个著名的NP-难问题。文献中已经提出了MCDS的近似算法。这些算法大多存在近似率低、时间复杂度和消息复杂度高的问题，本文提出了一种新的基于极大独立集（MIS）的分布式近似算法。我们的算法，这是完全本地化的，有一个常数的近似比，和O（n）的时间和O（n）的消息复杂度。在该算法中，每个节点只需要知道它的一跳邻居，并且只有一条最短路径连接两个最多三跳的支配者。我们不仅对算法进行了理论性能分析，而且进行了大量的仿真，将我们的算法与文献中的其他算法进行了比较。仿真结果和理论分析表明，该算法具有较好的效率和性能.版权所有© 2005年约翰威利父子有限公司。
In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub-graph. However, finding the minimum connected dominating set (MCDS) is a well-known NP-hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity.In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one-hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd.