论文部分内容阅读
无线网络中已有的路由协议主要分为两类:基于拓扑结构的路由和基于地理位置的路由。使用基于拓扑结构的路由协议,网络中的节点可以使用最短路径算法选择到不同目的节点相对最优的路径,但是节点存储的路由表比较庞大,需要较大的存储开销,影响路由的效率。使用基于地理位置的路由协议,节点根据地理位置信息路由,只需维护很小的路由状态。然而,贪婪地理位置路由不能实现数据包保证交付,可能出现路由空洞的问题。后来也有一些方案来解决路由空洞的问题,但是它们增加了路由算法的复杂性。此外,采用地理位置路由,网络中节点传输数据包的路径较长。本文我们结合两类路由协议的优势,提出了一个基于四叉树编址的复合路由机制 HQLSR(Hierarchical Quadtree-Based Link State Routing)。HQLSR 机制能够在实现数据包保证交付的前提下显著压缩路由表,并且平均路径延伸比较小。我们首先利用四叉树数据结构对不同地理位置的节点分配地址,然后根据节点的真实拓扑按照连通性规则进行汇聚,将满足连通性的节点汇聚成一个区域zone,最终网络能够分成不同的zone。我们在zone内和zone间分别采用不同的路由算法,构建一个层次化路由架构。在zone内,我们利用邻居子树路由算法来降低域内路由表规模。在zone间,我们根据zone跳数采用最短路径算法来选择zone间的路径。在节点分布不均匀、分布区域比较狭长的情况下,节点采用四叉树编址时最大编址长度会很长,汇聚效果不理想。因此,我们提出矩形编址来改进四叉树编址减少最大编址长度。减少编址长度一方面能够减少zone内路由表的大小,另一方面能够减少数据包包头和路由表中节点地址域的长度。此外,利用矩形编址我们可以采用灵活地汇聚来提高汇聚效果,从而实现更好的压缩效果。同样我们将矩形编址技术应用到路由机制中,提出了一个改进的复合路由机制HRAR(Hierarchical Rectangle-based Addressing Routing)。实验结果表明 HRAR 路由机制相比HQLSR路由机制能实现更好的压缩效果并且路径延伸比更低。