高效的分布式最小连通支配集近似算法  

Efficient Distributed Approximation Algorithm for Minimum Connected Dominating Set

作　　者：张旻[1] 张颖[1] 陈勤[1] 

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

出　　处：《计算机工程》2008年第23期139-141,163,共4页Computer Engineering

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

摘　　要：在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.

关 键 词：AD HOC网络 分布式 极大独立集 最小连通支配集 

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