论文研究自组织网络分布式最小连通支配集创建算法.pdf

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