无线ad hoc网络具有无中心、自组织、自适应、可快速展开、可移动等特点,旨在建立一个可即时展开、随意通信并对网络拓扑结构变化迅速作出反应的数据网络,可应用于军事战术通信系统、紧急服务和灾难恢复等诸多领域,它的出现引起了世界许多国家的军事部门、工业界和学术界的极大关注。Ad hoc网络没有类似蜂窝通信中基站的骨干基础,所以基于虚拟骨干网的分层路由机制日渐成为国内外研究的热点。已存在的分层路由机制鉴于主机的移动性,要求虚拟骨干网的高更新和高维护率,由此引起大量的控制开销和能耗。为了解决这个问题,本文利用网络图论中的一些理论,在不同的应用环境下给出几种虚拟骨干网的模型、构建及基于稳定性和节能的算法设计,并针对这些骨干网提出相应的分层路由机制,主要研究内容和贡献如下:考虑到主机的功率大小和在线时间长短对虚拟骨干中心的相对稳固性的影响,提出用基于极大权的最小连通支配集模拟虚拟骨干网;并给出其数学模型和相应的启发式算法,确保了性能强的主机担任骨干节点;通过优化规则确保骨干网的极小性,有效地减小了控制分组转发开销;最后进行了仿真验证。对规模较大、移动较频繁的ad hoc网络,用独立支配集构建虚拟骨干网,克服了骨干节点之间必须维护连通性的问题,使得拓扑变化较快时骨干网的重构能快速实现;采用动态按需路由机制,解决了骨干节点要维护路由表的问题;还利用极大独立集的求解得到极小独立支配集;并通过仿真测试了算法的正确性及自恢复能力。针对Ad hoc传感器网络只进行数据传输的特点,提出用极大权中继集的根树模拟虚拟骨干网,构成高效能的多级簇树;通过优先选择剩余能量高、与所有邻居交换信息耗能少的传感器节点为簇头的策略和定期更换簇头及移动基站的机制,减小和均衡每个传感器的耗能,从而延长全网的寿命。仿真结果表明了算法的有效性。提出基于有网关的多级簇树的路由机制,先通过求解具极大权的极大独立集得到合理的簇头,并在簇头之间引入一些网关节点做中继转发,解决了簇头距离过大耗能增加的问题,更进一步地延长了全网的寿命。仿真结果表明算法能更有效地提高网络的生存期。可扩展性好,具有自恢复能力。