發(fā)布時間：2017-12-31 16:38

  本文關鍵詞：基于四叉樹編碼實現(xiàn)路由表壓縮的復合路由方案研究　出處：《中國科學技術大學》2017年碩士論文　論文類型：學位論文

  更多相關文章： 四叉樹編址 路由表壓縮 基于地理位置的路由 基于拓撲結構的路由 RGA編址 復合路由方案

【摘要】：無線網絡中已有的路由協(xié)議主要分為兩類:基于拓撲結構的路由和基于地理位置的路由。使用基于拓撲結構的路由協(xié)議,網絡中的節(jié)點可以使用最短路徑算法選擇到不同目的節(jié)點相對最優(yōu)的路徑,但是節(jié)點存儲的路由表比較龐大,需要較大的存儲開銷,影響路由的效率。使用基于地理位置的路由協(xié)議,節(jié)點根據(jù)地理位置信息路由,只需維護很小的路由狀態(tài)。然而,貪婪地理位置路由不能實現(xiàn)數(shù)據(jù)包保證交付,可能出現(xiàn)路由空洞的問題。后來也有一些方案來解決路由空洞的問題,但是它們增加了路由算法的復雜性。此外,采用地理位置路由,網絡中節(jié)點傳輸數(shù)據(jù)包的路徑較長。本文我們結合兩類路由協(xié)議的優(yōu)勢,提出了一個基于四叉樹編址的復合路由機制 HQLSR(Hierarchical Quadtree-Based Link State Routing)。HQLSR 機制能夠在實現(xiàn)數(shù)據(jù)包保證交付的前提下顯著壓縮路由表,并且平均路徑延伸比較小。我們首先利用四叉樹數(shù)據(jù)結構對不同地理位置的節(jié)點分配地址,然后根據(jù)節(jié)點的真實拓撲按照連通性規(guī)則進行匯聚,將滿足連通性的節(jié)點匯聚成一個區(qū)域zone,最終網絡能夠分成不同的zone。我們在zone內和zone間分別采用不同的路由算法,構建一個層次化路由架構。在zone內,我們利用鄰居子樹路由算法來降低域內路由表規(guī)模。在zone間,我們根據(jù)zone跳數(shù)采用最短路徑算法來選擇zone間的路徑。在節(jié)點分布不均勻、分布區(qū)域比較狹長的情況下,節(jié)點采用四叉樹編址時最大編址長度會很長,匯聚效果不理想。因此,我們提出矩形編址來改進四叉樹編址減少最大編址長度。減少編址長度一方面能夠減少zone內路由表的大小,另一方面能夠減少數(shù)據(jù)包包頭和路由表中節(jié)點地址域的長度。此外,利用矩形編址我們可以采用靈活地匯聚來提高匯聚效果,從而實現(xiàn)更好的壓縮效果。同樣我們將矩形編址技術應用到路由機制中,提出了一個改進的復合路由機制HRAR(Hierarchical Rectangle-based Addressing Routing)。實驗結果表明 HRAR 路由機制相比HQLSR路由機制能實現(xiàn)更好的壓縮效果并且路徑延伸比更低。
[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

【相似文獻】

相關期刊論文 前10條

1 張慶紅;程國建;;淺析路由表原理在網絡中的應用[J];網絡安全技術與應用;2010年04期

2 王姝;陳常嘉;;基于地址分配算法壓縮路由表[J];北京交通大學學報;2010年02期

3 司麗娟;;基于路由表權重調整提高任意播負載均衡性能的算法[J];計算機應用;2011年S2期

4 劉倉明;基于流量分布的高速路由表查找算法[J];山西電子技術;2004年01期

5 趙光富,姜建國,楊曉強,王曉峰;一種路由表三層下發(fā)算法[J];電子科技;2005年03期

6 崔欣波;;策略性路由應用[J];內蒙古電大學刊;2006年12期

7 張龍;;MPLS VPN互訪的幾種方式[J];電力信息化;2008年09期

8 張昊;;基于信任概率的雙向路由表研究[J];硅谷;2012年03期

9 李臘元;一種路由表維護協(xié)議的分析[J];微電子學與計算機;1992年09期

10 王利媛,馬躍,徐塞虹;對路由表結構和查找算法的研究[J];計算機應用;2004年11期

相關會議論文 前3條

1 趙永勝;谷利澤;;基于路由表的主機非法外聯(lián)監(jiān)控技術研究與分析[A];2009通信理論與技術新發(fā)展——第十四屆全國青年通信學術會議論文集[C];2009年

2 程青松;王文鼐;唐寶民;;考慮業(yè)務流量分布的路由表查找算法[A];開創(chuàng)新世紀的通信技術——第七屆全國青年通信學術會議論文集[C];2001年

3 譚振華;程維;常桂然;高曉興;王賀;;一種基于分布式選舉算法的結構化P2P覆蓋網絡路由協(xié)議[A];2008'中國信息技術與應用學術論壇論文集（二）[C];2008年

相關重要報紙文章 前10條

1 江蘇 白洋;看路由表就是這么簡單[N];電腦報;2005年

2 Mark Gibbs;IT從業(yè)十誡[N];網絡世界;2006年

3 ;測試方法解析[N];網絡世界;2002年

4 浙江 林美榮;修改ADSL Modem路由表，，限制用戶訪問[N];電腦報;2003年

5 ;MPLS不利于Internet發(fā)展[N];計算機世界;2001年

6 工信部電信研究院規(guī)劃所 蘇嘉;IPv6地址資源規(guī)劃需趁早[N];人民郵電;2011年

7 何茂平;中興SmartNetwork智能IP城域網[N];人民郵電;2001年

8 張志剛 屈永華;路由器撐不住了咋辦[N];中國計算機報;2001年

9 廣州 梁俊清;ADSL Modem的遠程控制[N];電腦報;2001年

10 華為公司供稿;華為MPLS VPN技術特色[N];計算機世界;2002年

相關博士學位論文 前8條

1 陸璇;互聯(lián)網域間路由可擴展性的相關研究[D];北京郵電大學;2015年

2 潘恬;支持快速啟動和協(xié)議識別的路由器線卡的研究[D];清華大學;2015年

3 楊仝;骨干網路由表壓縮、查找及增量更新技術研究[D];清華大學;2013年

4 葉麟;基于行為測量的P2P系統(tǒng)優(yōu)化研究[D];哈爾濱工業(yè)大學;2011年

5 王洪君;Internet域間路由穩(wěn)定性研究[D];東北大學;2006年

6 孫慶南;面向IPv6分組轉發(fā)的路由技術研究[D];中國科學院研究生院（計算技術研究所）;2005年

7 高蕾;面向多核多線程的BGP協(xié)議并行技術研究[D];國防科學技術大學;2009年

8 張曉哲;路由協(xié)議并行處理技術研究[D];國防科學技術大學;2005年

相關碩士學位論文 前10條

1 趙曼;基于路由表的無線傳感器網絡路由算法的研究[D];華北電力大學;2016年

2 王志坤;一種基于實際交通數(shù)據(jù)的RSU網絡構建策略[D];重慶大學;2016年

3 吳晶晶;基于四叉樹編碼實現(xiàn)路由表壓縮的復合路由方案研究[D];中國科學技術大學;2017年

4 朱凱;FCoE路由管理模塊的設計與實現(xiàn)[D];北京郵電大學;2010年

5 陶中平;基于鄰近度的P2P路由算法的設計與實現(xiàn)[D];電子科技大學;2007年

6 鄒香玲;基于路由表的無線傳感器網絡路由算法研究[D];華中師范大學;2013年

7 任勇軍;一個P2P資源查找的改進方法[D];河海大學;2004年

8 馬常霞;基于移動Agent的分布式路由算法研究[D];南京理工大學;2003年

9 劉昊東;基于DHT的P2P路由算法研究[D];武漢理工大學;2010年

10 吳婷婷;基于四叉樹的路由技術研究[D];中國科學技術大學;2015年

本文編號：1360605