无线Ad Hoc网络MCDS的贪心分布式近似算法  

A Greedy Distributed Approximation Algorithm for MCDS in Wireless Ad Hoc Networks

作　　者：田海燕[1] 高英[2] 贺毅朝[3] 

机构地区：[1]河北师范大学数学与信息科学学院,河北石家庄050016 [2]石家庄经济学院数理学院,河北石家庄050031 [3]石家庄经济学院信息工程学院,河北石家庄050031

出　　处：《河北师范大学学报（自然科学版）》2010年第3期280-283,共4页Journal of Hebei Normal University：Natural Science

基　　金：河北省自然科学基金(A2008000128)

摘　　要：在无线Ad Hoc网络中基于最小连通支配集(MCDS)构建虚拟主干网可以有效缓解广播风暴,提高网络性能,延长网络生存时间.利用单位圆盘图中极大独立集的性质,使用2阶段贪心分布式近似算法构造了MCDS.从理论上分析了算法的时间复杂度、信息复杂度和近似比.In wireless Ad Hoc networks,a minimum connect dominating sets （MCDS） has been used as virtual backbone to alleviate the broadcasting storm,improve the performance and prolong the system lifetime.A 2-phase distributed approximation algorithm for constructing MCDS based on the properties of maximal independent set is proposed.The time complexity,message complexity and the performance ratio of algorithms are analyzed respectively.

关 键 词：无线AD Hoc网络 虚拟主干网 最小连通支配集 极大独立集 

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