基于分享度的最小连通支配集求解算法

doi:10.3969/j.issn.1000-3428.2013.06.028

计算机工程 ›› 2013, Vol. 39 ›› Issue (6): 134-137.doi: 10.3969/j.issn.1000-3428.2013.06.028

基于分享度的最小连通支配集求解算法

赵学锋^a，陈祥恩^b

(西北师范大学 a. 计算机科学与工程学院；b. 数学与统计学院，兰州 730070)

收稿日期:2012-07-05 出版日期:2013-06-15 发布日期:2013-06-14
作者简介:赵学锋(1965－)，男，副教授、硕士，主研方向：无线传感器网络；陈祥恩，教授
基金项目:
国家自然科学基金资助项目(61163037)

Minimum Connected Dominating Set Solution Algorithm Based on Share Degree

ZHAO Xue-feng ^a, CHEN Xiang-en ^b

(a. College of Computer Science and Engineering; b. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China)

Received:2012-07-05 Online:2013-06-15 Published:2013-06-14

摘要/Abstract

摘要： 以节点分享度作为选择分配点的优先级，提出一种最小连通支配集(CDS)求解算法。从根节点开始，将具有局部最大分享度的节点作为支配点，选择连接点与已确定的支配点连通，逐步构造网络的支配树，分析支配树的直径，计算支配树的平均跳数距离(AHD)，从而评价网络的通信成本。实验结果表明，与CDS-BD-C2算法相比，该算法得到的CDS规模较小，且支配树的AHD平均减少12%。

关键词: 最小连通支配集, 支配, 连接点, 分享度, 平均跳数距离, 单位圆盘图

Abstract: Making point Share Degree(SD) as the priority of selection control point, a new solution algorithm for computing the minimum Connected Dominating Set(CDS) in networks is proposed. Starting from root node, it iteratively selects nodes with maximum share degree in its neighborhood as dominators and some intermediate nodes as connector link to determined dominators previously, and a dominating tree is found gradually. The diameter of the dominating tree is analyzed, moreover its Average Hop Distances(AHD) is calculated in order to evaluate communication costs in networks. Experimental results show that this algorithm can construct smaller CDS than related works, and the AHD is reduced by 12% on average, compared with the CDS-BD-C2 algorithm.

Key words: Minimum Connected Dominating Set(MCDS), domination, connection point, Share Degree(SD), Average Hop Distance(AHD), Unit Disk Graph(UDG)

中图分类号:

TP301.6

赵学锋, 陈祥恩. 基于分享度的最小连通支配集求解算法[J]. 计算机工程, 2013, 39(6): 134-137.

DIAO Hua-Feng, CHEN Xiang-En. Minimum Connected Dominating Set Solution Algorithm Based on Share Degree[J]. Computer Engineering, 2013, 39(6): 134-137.

参考文献

[1] Wu Jie, Lou Wei, Dai Fei. Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs[J]. IEEE Transactions on Computers, 2006, 55(3): 334-347.
[2] Cooper C, Klasing R, Zito M. Lower Bounds and Algorithms for Dominating Sets in Web Graphs[J]. Internet Mathematics, 2005, 2(2): 275-300.
[3] Wan Pengjun, Alzoubi K M, Frieder O. Distributed Construc- tion of Connected Dominating Set in Wireless Ad Hoc Net- works[J]. Mobile Networks and Applications, 2004, 9(2): 141-149.
[4] Wu Weili, Du Hongwei, Jia Xiaohua, et al. Minimum Con- nected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs[J]. Theoretical Computer Science, 2006, 352(1-3): 1-7.
[5] Funke S, Kesselman A, Meyer U. A Simple Improved Dis- tributed Algorithm for Minimum CDS in Unit Disk Graphs[J]. ACM Transactions on Sensor Networks, 2006, 2(3): 444-453.
[6] Kim D, Wu Yiwei, Li Yingshu, et al. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks[J]. IEEE Transactions on Parallel and Distributed System, 2009, 20(2): 147-157.
[7] 解文斌, 李佳, 鲜明, 等. 基于拓扑特性的分布式虚拟骨干网算法[J]. 软件学报, 2010, 21(6): 1416-1425.
[8] Butenko S, Cheng Xiuzhen, Oliveira C, et al. A New Heuris- tics for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks[C]//Proc. of Recent Developments in Cooperative Control and Optimization. New York, USA: Kluwer Academic Publisher, 2004.
[9] Borgs C, Brautbar M, Chayes J, et al. The Power of Local Information in Social Networks[C]//Proc. of the 8th International Conference on Internet and Network Economics. Berlin, Germany: Springer, 2012.
[10] Wang Feng, Du Hongwei, Camacho E, et al. On Positive Influence Dominating Sets in Social Networks[J]. Theoretical Computer Science, 2011, 412(3): 265-269.
[11] Li Shaohua, Wang Jianxin, Chen Jianer, et al. An Algorithm for Minimum Vertex Cover Based on Max-I Share Degree[J]. Journal of Computers, 2011, 6(8): 1781-1788.
[12] Mitzenmacher M, Upfal E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis[M]. Cambridge, UK: Cambridge University Press, 2005.
编辑刘冰

[1]	郑楚红, 彭勇, 徐一鸣, 廖毅. 云制造环境下基于改进NSBBO的任务调度算法[J]. 计算机工程, 2019, 45(10): 26-32.
[2]	董雷刚,刘国华. 组合Skyline的求解与更新算法[J]. 计算机工程, 2017, 43(6): 195-201,206.
[3]	李志,焦琴琴,周愉峰. 震后应急物资供应点的多目标动态定位-分配模型 [J]. 计算机工程, 2017, 43(6): 281-288.
[4]	吉福生,吴晨,刘乔寿. WSN中能量有效的连通支配集构建算法[J]. 计算机工程, 2017, 43(1): 138-143.
[5]	周愉峰,李志,郑斌. 考虑失灵风险的随机多目标定位-库存问题及其优化算法[J]. 计算机工程, 2015, 41(6): 247-253.
[6]	孔凡凤,欧红玉,龙林德,陈曦. 基于连通支配集的WSN自适应数据调度算法[J]. 计算机工程, 2015, 41(10): 94-98,104.
[7]	祝青,何建新. CRN 中基于单位圆盘图模型的广播调度算法[J]. 计算机工程, 2014, 40(11): 101-105.
[8]	周愉峰,李志. 有容量约束的随机多目标LIP 模型及其求解算法[J]. 计算机工程, 2014, 40(11): 183-188.
[9]	陈浩, 张书奎, 杨凯. 基于支配集的多传感器集成复合事件检测[J]. 计算机工程, 2013, 39(3): 118-122.
[10]	赵学锋. 基于GSO算法的最小连通支配集问题求解[J]. 计算机工程, 2013, 39(2): 99-102.
[11]	李志强，蔺想红. 基于聚类的NSGA-II算法[J]. 计算机工程, 2013, 39(12): 186-190.
[12]	赵学锋. 求解最小连通r-跳k-支配集的启发式算法[J]. 计算机工程, 2012, 38(21): 67-69,73.
[13]	范会联, 仲元昌. 基于多目标进化的属性约简算法[J]. 计算机工程, 2012, 38(08): 153-155.
[14]	赵学锋, 杨海斌, 张贵仓. 基于堆的最小连通支配集高效近似算法[J]. 计算机工程, 2011, 37(2): 54-56.
[15]	刘鹃梅, 王小玲. Ad Hoc网络均匀区域广播算法[J]. 计算机工程, 2011, 37(2): 78-80.

基于分享度的最小连通支配集求解算法

Minimum Connected Dominating Set Solution Algorithm Based on Share Degree

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10