作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2009, Vol. 35 ›› Issue (10): 92-94. doi: 10.3969/j.issn.1000-3428.2009.10.030

• 网络与通信 • 上一篇    下一篇

分布式最小连通支配集启发式算法

陈 勤,范文涛,张 旻   

  1. (杭州电子科技大学软件与智能技术研究所,杭州 310018)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-05-20 发布日期:2009-05-20

Distributed Heuristic Approximation Algorithm for Minimum Connected Dominating Set

CHEN Qin, FAN Wen-tao, ZHANG Min   

  1. (Institute of Software and Intelligent Technology, Hangzhou Dianzi University, Hangzhou 310018)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-05-20 Published:2009-05-20

摘要: 针对Ad Hoc 网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.6opt+1.4,时间复杂度为O(△2),消息复杂度为O(n),比同类算法优秀。

关键词: 有效度, 支配节点, 极大独立集, 最小连通支配集

Abstract: In Ad Hoc network, broadcasting by flooding results in broadcast storm problem. This paper proposes a new distributed Heuristic approximation algorithm for Minimum Connected Dominating Set(HMCDS), which includes constructing Maximum Independent Set(MIS), introducing the concept of effective degree, and using of the greedy strategy of choosing dominator node through nodes’ information of effective degree. Experimental results show that the size of Connected Dominating Set(CDS) achieved by using HMCDS is 7.6opt+1.4, time complexity is O(△2) and message complexity is O(n), which are better than similar algorithms.

Key words: effective degree, dominator node, Maximum Independent Set(MIS), minimum connected dominating set

中图分类号: