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

Distributed MCDS constructing algorithm in Ad hoc networks

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

For the NP-hard problem of constructing minimum connected dominating set （MCDS） in Ad hoc networks, this paper proposed a novel distributed MCDS constructing algorithm called DMCA. DMCA constructed a MCDS for Ad hoc networks based on a maximal independent set （MIS）. In DMCA, each node only required the knowledge of its one-hop neighbors and there existed only one shortest path connecting two dominators these were at most three hops away. The theoretical analysis shows that DMCA was fully localized, had a constant approximation ratio, and O（n） time complexity and O（n） message complexity. Detailed simulation results and comparisons with existed algorithms show that the proposed DMCA algorithm has less size of MCDS with varying node number and transmission range.