求解圆盘图中最小连通支配集的近似算法

doi:10.3724/SP.J.1087.2011.01962

计算机应用 ›› 2011, Vol. 31 ›› Issue (07): 1962-1965.DOI: 10.3724/SP.J.1087.2011.01962

求解圆盘图中最小连通支配集的近似算法

赵学锋

西北师范大学数学与信息科学学院，兰州 730070

收稿日期:2010-12-17 修回日期:2011-01-31 发布日期:2011-07-01 出版日期:2011-07-01
通讯作者: 赵学锋
作者简介:赵学锋(1965-),男,甘肃渭源人, 副教授,硕士,主要研究方向：图与网络算法。
基金资助:
甘肃省科技攻关项目

Approximation algorithm for minimum connected dominating set in unit disk graphs

Xue-feng ZHAO

College of Mathematics and Information Science, Northwest Normal University, Lanzhou Gansu 730070, China

Received:2010-12-17 Revised:2011-01-31 Online:2011-07-01 Published:2011-07-01
Contact: Xue-feng ZHAO

摘要/Abstract

摘要： 针对无线传感器网络常用的拓扑模型单位圆盘图，提出了基于分布式贪心策略的近似算法DDT，在算法执行的每一轮中，根据一跳邻域范围内的权值和邻居的状态信息，选举出节点并和已确定的节点连接，逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析，得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明，和相关的分布式算法相比，DDT产生的连通支配集在规模上更优。

关键词: 最小连通支配集, 极大独立集, 近似算法, 支配树, 单位圆盘图

Abstract: Minimum Connected Dominating Set (MCDS) problem is a classical optimization issue in the design of wireless networks. For the construction of MCDS in the Unit Disk Graph (UDG) to model wireless sensor networks, an efficient approximation algorithm, DDT, was proposed based on distributed greedy strategy. In each round, it repeatedly selected a node to link a determined node according to weights and state information among one-hop neighborhood, and finally, found a dominating tree for the graph. The maximum node degree in the dominating tree was studied using probabilistic method. By analyzing the relationship between the size of the maximal independent set and the minimum connected dominating set, the algorithm produced a new approximation ratio. The experimental results show the superiority of the DDT algorithm over other existing distributed algorithms in terms of the CDS size.

Key words: minimum connected dominating set, minimal independent set, approximately algorithms, dominating tree, Unit Disk Graph (UDG)

中图分类号:

TP393

赵学锋. 求解圆盘图中最小连通支配集的近似算法[J]. 计算机应用, 2011, 31(07): 1962-1965.

Xue-feng ZHAO. Approximation algorithm for minimum connected dominating set in unit disk graphs[J]. Journal of Computer Applications, 2011, 31(07): 1962-1965.

参考文献

[1]CLARK B N, COLBOURN C J, JOHNSON D S. Unit disk graphs [J]. Discrete Mathematics, 1990,86(1/2/3): 165-177.

[2]BUTENKO S, CHENG X, OLIVEIRA C, et al. A new heuristics for the minimum connected dominating set problem on Ad Hoc wireless networks[C]// Recent Developments in Cooperative Control and Optimization. New York: Kluwer Academic Publisher, 2004: 61-73.

[3]DAI F, WU J. An extended localized algorithm for connected dominating set formation in Ad Hoc wireless networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(10): 908-920.

[4]ALZOUBI K M, WAN P J, FRIEDER O. Maximal independent set, weakly connected dominating set, and induced spanners for mobile Ad Hoc networks [J]. International Journal of Foundations of Computer Science, 2003,14(2): 287-303.

[5]FUNKE S, KESSELMAN A, MEYER U, et al. A simple improved distributed algorithm for minimum CDS in unit disk graphs [J]. ACM Transactions on Sensor Networks, 2006,2(3): 444-453.

[6]谢嵘，齐德昱，李拥军,等. 传感器网络中高效的最小连通支配集求解算法[J]. 计算机应用， 2008, 28(2): 342-344.

[7]唐勇, 周明天. 基于极大独立集的最小连通支配集的分布式算法[J]. 电子学报, 2007, 35(5): 868-874.

[8]HAN B. Zone-based virtual backbone formation in wireless Ad Hoc networks [J].Ad Hoc Networks, 2009, 7(1): 183-200.

[9]YANG H Y, LIN C H, TSAI M J. Distributed algorithm for efficient construction and maintenance of connected k-hop dominating sets in mobile Ad Hoc networks [J]. IEEE Transactions on Mobile Computing, 2008,7(4):444-457.

[10]WU W, DU H, JIA X, et al. Minimum connected dominating sets and maximal independent sets in unit disk graphs [J]. Theoretical Computer Science, 2006, 352(1/2/3): 1-7.

[11]YOUSSEF M A,YOUSSEF A, YOUNIS M F. Overlapping multihop clustering for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(12): 1844-1856.

求解圆盘图中最小连通支配集的近似算法

Approximation algorithm for minimum connected dominating set in unit disk graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	唐海波, 林煜明, 李优, 蔡国永. 基于模拟退火与贪心策略的平衡聚类算法[J]. 计算机应用, 2018, 38(11): 3132-3138.
[2]	高文宇, 李华. 团图点删除问题的近似算法[J]. 计算机应用, 2015, 35(8): 2137-2139.
[3]	刘彩苹蔡玉武毛建旭蔡玉文. 无线传感器网络不重复记录求和近似算法[J]. 计算机应用, 2014, 34(2): 313-317.
[4]	杨慧孟凡星. 改进的SAX符号化算法在QAR数据中的应用[J]. 计算机应用, 2012, 32(05): 1484-1487.
[5]	高文宇张力. 贝叶斯网最优消元顺序的近似构造算法[J]. 计算机应用, 2011, 31(08): 2072-2074.
[6]	方飞毛玉明冷甦鹏毛建兵. 自适应p坚持时隙ALOHA近似算法性能分析[J]. 计算机应用, 2011, 31(04): 897-900.
[7]	高文宇. 有向图最多叶子生成树问题研究[J]. 计算机应用, 2010, 30(06): 1431-1433.
[8]	张娟陆林生. 应用层并行I/O效率研究[J]. 计算机应用, 2009, 29(1): 9-11,1.
[9]	刘新刘任任侯经川. 求解旅行商问题的整体优先算法[J]. 计算机应用, 2007, 27(5): 1204-1207.
[10]	汪学清杨永田 . 一种基于虚拟菱形网格的传感器节点布置算法[J]. 计算机应用, 2006, 26(7): 1554-1556.