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

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

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

CLC Number: 

• TP393.07