期刊信息
- 刊名： 河北师范大学学报（自然科学版）Journal of Hebei Normal University (Natural Science)
- 主办： 河北师范大学
- ISSN： 1000-5854
- CN： 13-1061/N
- 中国科技核心期刊
- 中国期刊方阵入选期刊
- 中国高校优秀科技期刊
- 华北优秀期刊
- 河北省优秀科技期刊
无线Ad Hoc网络MCDS的贪心分布式近似算法
-
1. 河北师范大学数学与信息科学学院, 河北石家庄 050016;
2. 石家庄经济学院数理学院, 河北石家庄 050031;
3. 石家庄经济学院信息工程学院, 河北石家庄 050031 -
DOI：
A Greedy Distributed Approximation Algorithm for MCDS in Wireless Ad Hoc Networks
摘要/Abstract
摘要：
在无线Ad Hoc网络中基于最小连通支配集(MCDS)构建虚拟主干网可以有效缓解广播风暴,提高网络性能,延长网络生存时间.利用单位圆盘图中极大独立集的性质,使用2阶段贪心分布式近似算法构造了MCDS.从理论上分析了算法的时间复杂度、信息复杂度和近似比.
Abstract：
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 22 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.