摘要
在Alzoubi and Wan’s算法的基础上,利用2跳局部网络拓扑信息选择连通点,提出一个高效的分布式最小连通支配集算法EDMCDS。理论分析表明,EDMCDS算法生成的连通支配集大小为(5.8+ln4)opt+1.2,时间复杂度为O(△|MIS|),信息复杂度为O(4|E|)。与TFA和Alzoubi and Wan’s算法相比,该算法生成的连通支配集更小,时间复杂度和信息复杂度也有所降低。
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 O(△|MIS|) and message complexity is O(4|E|) , which are all better than TFA algorithm and Alzoubi and Wan's algorithm.
出处
《计算机工程》
CAS
CSCD
北大核心
2008年第23期139-141,163,共4页
Computer Engineering
基金
现代通信国家重点实验室基金资助项目(9140C110206070C11)
杭州电子科技大学校科学研究基金资助项目(KYF071506005)
关键词
AD
HOC网络
分布式
极大独立集
最小连通支配集
Ad Hoc networks
distributed
maximal independent set
minimum connected dominating set