摘要： 在Alzoubi and Wan’s算法的基础上，利用2跳局部网络拓扑信息选择连通点，提出一个高效的分布式最小连通支配集算法EDMCDS。理论分析表明，EDMCDS算法生成的连通支配集大小为(5.8+ln4)opt+1.2，时间复杂度为 ，信息复杂度为 。与TFA和Alzoubi and Wan’s算法相比，该算法生成的连通支配集更小，时间复杂度和信息复杂度也有所降低。

关键词: Ad Hoc网络, 分布式, 极大独立集, 最小连通支配集

Abstract: Based on Alzoubi and Wan’s algorithm, this paper proposes Effective Distributed Minimum Connected Dominating Set Algorithm (EDMCDS) by choosing connector node with two hop local network topology information. Analysis shows that the size of connected dominating set with EDMCDS is (5.8+ln4)opt+1.2, time complexity is and message complexity is , which are all better than TFA algorithm and Alzoubi and Wan’s algorithm.

Key words: Ad Hoc networks, distributed, maximal independent set, minimum connected dominating set

中图分类号: 

• TP393.07