一种新的自组网极小连通支配集生成算法

A Novel Distributed Minimum Connected Dominating Set Algorithm in Ad Hoc Network

自组网通过节点的自组织,构造成一种不需要任何基础设施的新型无线网络,基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足,基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS(Coloring Based-Minimum Connected Dominating Set)。CB-MCDS算法仅需要一跳邻居节点的拓扑信息,就能快速地构造出虚拟主干网,理论分析表明整个算法的时间和消息复杂度分别为O(△)和O(n△),该性能明显优于已有的算法。

A wireless ad hoe network consists of many mobile and organized hosts communicating with each other without any infrastructure. Connected dominating set-based virtual backbone plays a key role in a wireless ad hoc network for routing optimization, energy conservation and resource allocation. To construct virtual backbone efficiently, a new distributed coloring - based method, called CB - MCDS for short, is introduced. Because the CB- MCDS algorithm uses only 1 - hop neighbors information, it is proven that this coloring - based method runs with O（△ ） time complexity and O（ n△） message complexity, which are better than the previous works.