基于图着色的无线自组网极小连通支配集算法

Graph coloring based minimal connected dominating set algorithm in wireless ad hoc networks

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的正确性和高效性,也通过仿真实验分析了该算法在多种情况下的实际性能,仿真结果表明新算法在簇头和主干节点数目方面具有较好的性能,特别在节点密集的网络环境中更加突出。

Connected dominating set based virtual backbone played a key role in a wireless ad hoc network for routing optimization, energy conservation and resource allocation. Using the concept of minimum dominating set, maximum independent set, new graph coloring theory based minimum connected dominating set algorithm was proposed to construct virtual backbone in wireless ad hoc networks. The accuracy and efficiently to generate minimum connected dominating set was analyzed and the computational complexity of the proposed algorithm was compared with that of conventional algorithm. Simulation result results show the proposed algorithm has less number of cluster heads and backbone nodes and the new algorithm can outperform in dense environment.