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

Distributed Heuristic Approximation Algorithm for Minimum Connected Dominating Set

作　　者：陈勤[1] 范文涛[1] 张旻[1] 

机构地区：[1]杭州电子科技大学软件与智能技术研究所,杭州310018

出　　处：《计算机工程》2009年第10期92-94,共3页Computer Engineering

基　　金：现代通信国家重点实验室基金资助项目(9140c110206070c11);杭州电子科技大学校科学研究基金资助项目(KYF071506005)

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

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

分 类 号：TP393.07[自动化与计算机技术—计算机应用技术]