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

  更多相關(guān)文章： 四叉樹編址 路由表壓縮 基于地理位置的路由 基于拓?fù)浣Y(jié)構(gòu)的路由 RGA編址 復(fù)合路由方案

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張慶紅;程國建;;淺析路由表原理在網(wǎng)絡(luò)中的應(yīng)用[J];網(wǎng)絡(luò)安全技術(shù)與應(yīng)用;2010年04期

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

3 司麗娟;;基于路由表權(quán)重調(diào)整提高任意播負(fù)載均衡性能的算法[J];計(jì)算機(jī)應(yīng)用;2011年S2期

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

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

6 崔欣波;;策略性路由應(yīng)用[J];內(nèi)蒙古電大學(xué)刊;2006年12期

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

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

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

10 王利媛,馬躍,徐塞虹;對(duì)路由表結(jié)構(gòu)和查找算法的研究[J];計(jì)算機(jī)應(yīng)用;2004年11期

相關(guān)會(huì)議論文 前3條

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

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

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

相關(guān)重要報(bào)紙文章 前10條

1 江蘇 白洋;看路由表就是這么簡(jiǎn)單[N];電腦報(bào);2005年

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

3 ;測(cè)試方法解析[N];網(wǎng)絡(luò)世界;2002年

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

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

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

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

8 張志剛 屈永華;路由器撐不住了咋辦[N];中國計(jì)算機(jī)報(bào);2001年

9 廣州 梁俊清;ADSL Modem的遠(yuǎn)程控制[N];電腦報(bào);2001年

10 華為公司供稿;華為MPLS VPN技術(shù)特色[N];計(jì)算機(jī)世界;2002年

相關(guān)博士學(xué)位論文 前8條

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

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

3 楊仝;骨干網(wǎng)路由表壓縮、查找及增量更新技術(shù)研究[D];清華大學(xué);2013年

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

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

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

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

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

相關(guān)碩士學(xué)位論文 前10條

1 趙曼;基于路由表的無線傳感器網(wǎng)絡(luò)路由算法的研究[D];華北電力大學(xué);2016年

2 王志坤;一種基于實(shí)際交通數(shù)據(jù)的RSU網(wǎng)絡(luò)構(gòu)建策略[D];重慶大學(xué);2016年

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

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

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

6 鄒香玲;基于路由表的無線傳感器網(wǎng)絡(luò)路由算法研究[D];華中師范大學(xué);2013年

7 任勇軍;一個(gè)P2P資源查找的改進(jìn)方法[D];河海大學(xué);2004年

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

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

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

本文編號(hào)：1360605