本文關(guān)鍵詞：基于四叉樹(shù)的路由技術(shù)研究

  更多相關(guān)文章： 路由機(jī)制 信息論 四叉樹(shù) 最優(yōu)化 地理位置信息

【摘要】：在網(wǎng)絡(luò)互連中,路由發(fā)揮了重要的作用。利用它一方面能夠找到最優(yōu)的路徑；另一方面能夠盡可能減小由路由引起的開(kāi)銷,從而提高路由協(xié)議的性能。迄今為止,大量的路由方案已被廣泛研究。根據(jù)不同的需求,路由方案可以被分成多種類型。根據(jù)路由中利用信息的多少,現(xiàn)存的方案主要可以被分成兩類,即基于圖拓?fù)涞穆酚珊突诘乩砦恢玫穆酚伞?對(duì)于基于圖拓?fù)涞穆酚?它總能保證找到最優(yōu)路徑,但路由表中包含了大量的表項(xiàng)。與基于圖拓?fù)渎酚芍新酚杀淼拇笮∠啾?基于地理位置路由的路由表相當(dāng)?shù)男�。然�?后者一般找不到全局最優(yōu)的路徑。本論文旨在現(xiàn)有的路由機(jī)制上改進(jìn),結(jié)合了上述兩種路由機(jī)制的優(yōu)點(diǎn),同時(shí)回避了二者的缺點(diǎn)。論文主要貢獻(xiàn)如下： 提出了一種基于四叉樹(shù)的最優(yōu)路徑路由機(jī)制QOPR-一利用圖拓?fù)渎酚傻乃枷?它能夠保證最優(yōu)路徑。此外,通過(guò)使用地理位置信息和四叉樹(shù)結(jié)構(gòu),路由表的大小可以被壓縮至其信息論的下界。為了保證最優(yōu)路徑且能將路由表盡可能的壓縮,文獻(xiàn)中已提出了大量的方案。通過(guò)利用地理位置信息,我們的理論結(jié)果比現(xiàn)存文獻(xiàn)中的最好的結(jié)果(基于IP的方案)還要好。與其它方案相比,QOPR路由機(jī)制有兩大優(yōu)勢(shì)。一方面,它的編碼方案比IP地址更加直觀。路由表中的目的節(jié)點(diǎn)由四叉樹(shù)編碼,它可以直觀的劃分、編碼節(jié)點(diǎn)。另一方面,我們得到的路由表大小優(yōu)于現(xiàn)存文獻(xiàn)中的結(jié)果。仿真實(shí)驗(yàn)表明,一般情況下,本方案無(wú)論在路由表大小還是路由表的構(gòu)建、查找性能上均優(yōu)于基于IP的方案。 提出了一種QOPR+路由機(jī)制——針對(duì)QOPR路由機(jī)制中,當(dāng)插入新節(jié)點(diǎn)時(shí)引起的路由更新的不足,在QOPR路由機(jī)制的基礎(chǔ)上,提出QOPR+路由機(jī)制。通過(guò)采用一種新型的proper四叉樹(shù)-位圖混合結(jié)構(gòu)(proper quadtree bitmap hybrid structure,簡(jiǎn)稱pqbh(T))作為路由表,它能夠進(jìn)一步降低更新復(fù)雜度,兼顧查找速度和更新性能。此外,本文從理論上證明pqbh(T)也是一個(gè)很省空間的數(shù)據(jù)結(jié)構(gòu)。與QOPR路由機(jī)制中路由表的大小只相差了一個(gè)很小的常數(shù)因子。仿真實(shí)驗(yàn)表明,一般情況下,QOPR+路由機(jī)制的路由表構(gòu)建、查找、更新性能均優(yōu)于QOPR路由機(jī)制中的性能,但這是通過(guò)犧牲部分路由表大小實(shí)現(xiàn)的。
【關(guān)鍵詞】：路由機(jī)制 信息論 四叉樹(shù) 最優(yōu)化 地理位置信息
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP393.02;O157.5
【目錄】：

• 摘要5-6
• ABSTRACT6-8
• 目錄8-11
• 插圖索引11-13
• 表格索引13-14
• 第1章 緒論14-20
• 1.1 研究背景與意義14-15
• 1.2 研究現(xiàn)狀15-17
• 1.2.1 現(xiàn)有路由機(jī)制的研究現(xiàn)狀15-16
• 1.2.2 路由表的壓縮16-17
• 1.2.3 現(xiàn)有研究的不足17
• 1.3 研究?jī)?nèi)容與創(chuàng)新點(diǎn)17-18
• 1.4 結(jié)構(gòu)安排18-20
• 第2章 相關(guān)路由技術(shù)及其應(yīng)用20-30
• 2.1 基于圖拓?fù)涞穆酚煞桨?/span>20-23
• 2.1.1 先驗(yàn)式路由20-21
• 2.1.2 反應(yīng)式路由21-22
• 2.1.3 混合式路由22-23
• 2.2 基于地理位置路由方案23-28
• 2.2.1 貪婪轉(zhuǎn)發(fā)路由23-26
• 2.2.2 有限制的方向性洪泛路由26-27
• 2.2.3 分層路由27-28
• 2.3 利用四叉樹(shù)解決路由問(wèn)題28
• 2.4 本章小結(jié)28-30
• 第3章 基于四叉樹(shù)的路由機(jī)制30-60
• 3.1 基于四叉樹(shù)的路由機(jī)制30-37
• 3.1.1 四叉樹(shù)對(duì)二維平面的編碼方案30-31
• 3.1.2 網(wǎng)絡(luò)拓?fù)?/span>31
• 3.1.3 QOPR 算法31-33
• 3.1.4 路由表的形式33-35
• 3.1.5 路由表的構(gòu)建和查找35-37
• 3.2 性能分析37-42
• 3.2.1 路由表大小37-41
• 3.2.2 QCCT的性能41
• 3.2.3 路由表查找操作的性能41-42
• 3.3 仿真實(shí)驗(yàn)42-59
• 3.3.1 數(shù)據(jù)預(yù)處理42-43
• 3.3.2 性能驗(yàn)證43-59
• 3.4 本章小結(jié)59-60
• 第4章 QOPR+路由機(jī)制60-86
• 4.1 qcct(T)的更新60-62
• 4.2 QOPR+機(jī)制62-67
• 4.2.1 路由表的形式62-64
• 4.2.2 路由表的構(gòu)建及查找64-66
• 4.2.3 路由表的更新66-67
• 4.3 性能分析67-71
• 4.3.1 路由表的構(gòu)建性能67
• 4.3.2 路由表查找操作的性能67-68
• 4.3.3 路由表的更新68-69
• 4.3.4 路由表的大小69-71
• 4.4 仿真實(shí)驗(yàn)71-84
• 4.4.1 路由表的構(gòu)建性能71-73
• 4.4.2 路由表查找操作的性能73-77
• 4.4.3 路由表的更新77-79
• 4.4.4 路由表的大小79-84
• 4.5 本章小結(jié)84-86
• 第5章 總結(jié)與展望86-88
• 5.1 論文總結(jié)86
• 5.2 未來(lái)工作展望86-88
• 參考文獻(xiàn)88-94
• 致謝94-96
• 在讀期間發(fā)表的學(xué)術(shù)論文與取得的其他研究成果96

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前3條

1 魏子卿;;2000中國(guó)大地坐標(biāo)系[J];大地測(cè)量與地球動(dòng)力學(xué);2008年06期

2 黃謨濤,翟國(guó)君,管錚,歐陽(yáng)永忠;空間直角坐標(biāo)和大地坐標(biāo)的轉(zhuǎn)換[J];解放軍測(cè)繪學(xué)院學(xué)報(bào);1998年03期

3 楊望;;CAIDA提供互聯(lián)網(wǎng)數(shù)據(jù)共享服務(wù)[J];中國(guó)教育網(wǎng)絡(luò);2008年05期

，

本文編號(hào)：749812