| 分布式最小连通支配集启发式算法 |
| |
| 引用本文： | 陈勤,FAN Wen-tao,范文涛,张旻. 分布式最小连通支配集启发式算法[J]. 计算机工程, 2009, 35(10): 92-94 |
| |
| 作者姓名： | 陈勤 FAN Wen-tao 范文涛 张旻 |
| |
| 作者单位： | 杭州电子科技大学软件与智能技术研究所,杭州,310018;杭州电子科技大学软件与智能技术研究所,杭州,310018;杭州电子科技大学软件与智能技术研究所,杭州,310018 |
| |
| 基金项目： | 现代通信国家重点实验室基金，杭州电子科技大学校科学研究基金 |
| |
| 摘 要： | 针对AdHoc网络中用洪泛法进行广播易引起广播风暴的问题，提出一个新的分布式最小连通支配集启发式算法HMCDS，其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法，实验结果证明，HMCDS算法生成的连通支配集大小为7．60pt＋1．4，时间复杂度为O（△^2），消息复杂度为O（n），比同类算法优秀。
|
| 关 键 词： | 有效度 支配节点 极大独立集 最小连通支配集 |
| 修稿时间： | |
Distributed Heuristic Approximation Algorithm for Minimum Connected Dominating Set |
| |
| CHEN Qin,FAN Wen-tao,ZHANG Min. Distributed Heuristic Approximation Algorithm for Minimum Connected Dominating Set[J]. Computer Engineering, 2009, 35(10): 92-94 |
| |
| Authors: | CHEN Qin FAN Wen-tao ZHANG Min |
| |
| Affiliation: | Institute of Software and Intelligent Technology;Hangzhou Dianzi University;Hangzhou 310018 |
| |
| 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... |
| |
| Keywords: | effective degree dominator node Maximum Independent Set(MIS) minimum connected dominating set |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载免费的PDF全文 |
