一种新型的Ad Hoc网络虚拟主干网构造技术

A Novel Construction Technology in Virtual Backbone of Ad Hoc Network

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。本文对现存基于连通支配集算法的提出背景和应用环境作了简单介绍,由于在无线自组网中搜索主干节点和群首类似于图论中的最小连通支配集和最小支配集问题的求解,在此基础上提出了一种性能较好的虚拟主干网的构造技术--基于图着色思想提出的一种极小连通支配集的构造算法,并从理论上证明了该算法的正确性和高效性,通过分析,算法的时间和消息复杂度明显优于其他已知算法。

Connected dominating set based virtual backbone played a key role in a wireless ad hoc network for routing optimization, energy conservation and resource allocation.In this paper, discussed based on the Connected Dominating Set clustering algorithms and their background,their proposed application environment.Because in the wireless ad hoc network to search the trunk node and the first group is similar to graph theory of Minimum Connected Dominating Set and Minimum Dominating Set Problem, and on this basis, a better virtual backbone construct technology-based on graph coloring is brought up, a new thinking Minimal Connected Dominating Set Algorithm.The accuracy and efficiently to generate minimum connected dominating set was analyzed.Through the analysis, the algorithm complexity of time and news is better than the other known algorithms.