自组织网络分布式最小连通支配集创建算法

• 作者: 刘爱民 张奇 王凌燕
• 来源期刊: 计算机应用研究
• 关键词: 分布式算法 最小连通支配集 自组织网络
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 网络与通信技术
• 页码范围: 2241-2243,2247
• 页数: 4页
• 分类号: TN915.04
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2009.06.073

摘要

针对无线自组织分组(Ad hoc)网络中最小连通支配集(MCDS)创建NP难问题,提出了一种分布式的最小连通集创建算法DMCA.DMCA基于最大独立集(MIS)的构建,只需要周围一跳邻居的信息,在不超过三跳距离的一对支配节点之间找出一条最短路径.对DMCA算法的性能分析表明,DMCA具有常数的近似比、线性的时间和消息复杂度.详细的仿真实验以及与其他创建最小连通支配集算法的比较表明,提出的DMCA算法在节点数量与节点传输范围变化时创建的最小连通集更小.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王凌燕	郴州职业技术学院计算机系	26	25	3.0	3.0
2	刘爱民	郴州职业技术学院计算机系	24	18	3.0	3.0
3	张奇	浙江大学计算机学院	3	8	1.0	2.0