基于四叉树编码实现路由表压缩的复合路由方案研究

发布时间：2017-12-31 16:38

本文关键词：基于四叉树编码实现路由表压缩的复合路由方案研究　出处：《中国科学技术大学》2017年硕士论文　论文类型：学位论文

【摘要】：无线网络中已有的路由协议主要分为两类:基于拓扑结构的路由和基于地理位置的路由。使用基于拓扑结构的路由协议,网络中的节点可以使用最短路径算法选择到不同目的节点相对最优的路径,但是节点存储的路由表比较庞大,需要较大的存储开销,影响路由的效率。使用基于地理位置的路由协议,节点根据地理位置信息路由,只需维护很小的路由状态。然而,贪婪地理位置路由不能实现数据包保证交付,可能出现路由空洞的问题。后来也有一些方案来解决路由空洞的问题,但是它们增加了路由算法的复杂性。此外,采用地理位置路由,网络中节点传输数据包的路径较长。本文我们结合两类路由协议的优势,提出了一个基于四叉树编址的复合路由机制 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路由机制能实现更好的压缩效果并且路径延伸比更低。
[Abstract]:The existing routing protocols in wireless networks can be divided into two categories: topology based routing and geographical location based routing, and topology based routing protocols are used. Nodes in the network can use the shortest path algorithm to select the optimal path to different destination nodes, but the routing table stored by nodes is relatively large, which requires large storage overhead. It affects the efficiency of routing. Using geo-location based routing protocol, nodes need to maintain a very small routing state according to geographical location information. However, greedy geographical location routing can not guarantee the delivery of packets. Then there are some solutions to solve the problem of routing holes, but they increase the complexity of routing algorithms. In addition, geographical routing is adopted. In this paper, we combine the advantages of two kinds of routing protocols. A hybrid routing mechanism based on quadtree addressing (HQLSRs) is proposed. Hierarchical Quadtree-Based Link State routing). The HQLSR mechanism can significantly compress the routing table while implementing packet delivery guarantee. And the average path extension is relatively small. Firstly, we use quadtree data structure to assign addresses to nodes in different geographical locations, then converge according to the real topology of nodes according to connectivity rules. Finally, the network can be divided into different Zone. we adopt different routing algorithms in zone and zone. In zone, we use neighbor subtree routing algorithm to reduce the size of the routing table in the domain. According to the number of zone hops, we use the shortest path algorithm to choose the path between zone. In the case of uneven distribution of nodes and narrow distribution region. The maximum addressing length of nodes using quadtree is very long and the convergence effect is not ideal. We propose rectangular addressing to improve quadtree addressing to reduce maximum addressing length, which on the one hand can reduce the size of routing tables in zone. On the other hand, it can reduce the length of packet header and node address field in routing table. In addition, we can use flexible aggregation to improve convergence effect by using rectangular addressing. In order to achieve better compression effect, we also apply the rectangular addressing technology to the routing mechanism. An improved compound routing mechanism, HRAR(Hierarchical Rectangle-based Addressing routing, is proposed. Experimental results show that the HRAR routing mechanism can achieve better compression performance and lower path extension ratio than the HQLSR routing mechanism.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN92

【相似文献】