Ad Hoc网络路由协议是过去几年来广泛研究的主题,近来在实际应用上的研究更加侧重网络的可扩展性。随着网络规模的扩大,现有路由算法都存在路由开销大、可扩性低的问题。为了保证大规模网络的良好通信,需要对开销进行缩减以优化网络的性能。其中一个重要的问题就是:什么样的路由协议在网络扩展性和路由开销方面表现更佳?在链路状态路由算法中,通常采用两种方法减少路由开销,即覆盖控制法和高效广播法。HSLS路由算法采用覆盖控制技术,通过减小链路状态更新消息的初始TTL来控制LSU报文可达的范围。然而,覆盖控制法将带来次优路由问题,这将导致协议无法进一步降低开销。为了解决这个问题,文献[15]重新定义了路由算法总开销,引入次优路由开销。本文结合覆盖控制法和高效广播法的优势,提出了一种基于虚拟骨干网的分级分布式HSLS路由算法。该算法无缝集成了基于最小连通支配集的虚拟骨干网构建算法和采用扩展环搜索算法的链路状态路由算法,相比于原有的HSLS路由协议VB-HSLS利用虚拟骨干网进一步减少广播开销,将链路状态更新消息的转发限制在骨干网中。VB的引入能够容忍更多的次由路由开销,即使增加控制消息的发送,但该技术在广播消息控制方面对开销减小的效果更为突出最终使路由总开销得到了进一步降低。考虑虚拟骨干网的影响我们对VB-HSLS总开销进行了推算,并求出HSLS和VB-HSLS协议的最小广播间隔。在MATLAB仿真工具中进行数值计算证明了相同条件下VB-HSLS相比于HSLS能显著的降低算法总开销。在网络直径2?D?500时理论最小总开销和整数解条件下最小总开销相关差始终小于0.744%。同时我们计算了总开销同网络直径和网络密度的关系,结果表明网络密度越大VB-HSLS协议的性能越佳。最后在对VB-HSLS协议理论研究的基础上提出了VB-HSLS协议的实现方案,并在Linux操作系统下对分级分布式HSLS路由协议的实现方案进行可行性验证。搭建实验平台对该实现方案进行功能性测试,包含静态网络场景和动态网络场景。实验证明所提出的VB-HSLS具有现实可行性,且该算法静态和动态网络场景中都有较好的表现。