Ad Hoc网络是一组带有无线收发设备的移动节点组成的多跳的临时性无中心网络,可以在任何时刻、任何地点快速构建起一个移动通信网络,并且不需要现有网络基础设施的支持。在Ad Hoc网络中移动节点不仅要负责通信任务,同时还要担当路由功能。而基于全网的洪泛机制会引起广播风暴问题,这将消耗大量的网络资源。由于网络拓扑结构动态变化性、多跳通信特性和资源的有限性,合理的路由设计成了一个挑战性的问题。对此,许多学者提出通过构造虚拟骨干网,将网络分级来实现网络的稳定性和高效性。通过在Ad Hoc网络构建虚拟骨干网即可将网络中节点进行分级,而这一过程正是图论中连通支配集理论的一个应用。可以将路由简化到由最小连通支配集构造成的虚拟骨干网中去。消息从源节点沿着CDS中的节点传递到离目的节点最近的支配节点,最终到达目的节点。本文以支配集做为研究问题的理论基础,对传统的构造连通支配集方法进行深入研究,针对以上所列举的技术的不足,提出了改进的算法。在构造连通支配集的算法时,有以下四个方面的因素度量算法的性能:算法的近似比、局部性、时间复杂度和消息复杂度、以及稳定性。因此,考虑到主机的剩余能量的大小、节点度大小、以及移动速度等因素对于所构建的连通支配集稳固性起着重要的作用,提出了一种改进的基于权值的最小连通支配集构造虚拟骨干网的改进算法。并给出了权值的计算公式,确保了性能强的主机优先担当支配节点。另外,还针对节点移动的情况下,如何维护连通支配集提出了维护策略。证明了该算法具有较低的时间复杂度和算法复杂度。