基于四叉樹的路由技術(shù)研究.pdf

1、在網(wǎng)絡(luò)互連中，路由發(fā)揮了重要的作用。利用它一方面能夠找到最優(yōu)的路徑;另一方面能夠盡可能減小由路由引起的開銷，從而提高路由協(xié)議的性能。迄今為止，大量的路由方案已被廣泛研究。根據(jù)不同的需求，路由方案可以被分成多種類型。根據(jù)路由中利用信息的多少，現(xiàn)存的方案主要可以被分成兩類，即基于圖拓?fù)涞穆酚珊突诘乩砦恢玫穆酚伞?duì)于基于圖拓?fù)涞穆酚?，它總能保證找到最優(yōu)路徑，但路由表中包含了大量的表項(xiàng)。與基于圖拓?fù)渎酚芍新酚杀淼拇笮∠啾?，基于地理位置路由的?/p>

2、由表相當(dāng)?shù)男?。然而，后者一般找不到全局最?yōu)的路徑。本論文旨在現(xiàn)有的路由機(jī)制上改進(jìn)，結(jié)合了上述兩種路由機(jī)制的優(yōu)點(diǎn)，同時(shí)回避了二者的缺點(diǎn)。
　　本文提出了一種基于四叉樹的最優(yōu)路徑路由機(jī)制QOPR----利用圖拓?fù)渎酚傻乃枷?，它能夠保證最優(yōu)路徑。此外，通過(guò)使用地理位置信息和四叉樹結(jié)構(gòu)，路由表的大小可以被壓縮至其信息論的下界。為了保證最優(yōu)路徑且能將路由表盡可能的壓縮，文獻(xiàn)中已提出了大量的方案。通過(guò)利用地理位置信息，我們的理論結(jié)果比現(xiàn)存文獻(xiàn)

3、中的最好的結(jié)果（基于IP的方案）還要好。與其它方案相比，QOPR路由機(jī)制有兩大優(yōu)勢(shì)。一方面，它的編碼方案比IP地址更加直觀。路由表中的目的節(jié)點(diǎn)由四叉樹編碼，它可以直觀的劃分、編碼節(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í)引起的路由更新的不足，在QOP

4、R路由機(jī)制的基礎(chǔ)上，提出QOPR+路由機(jī)制。通過(guò)采用一種新型的proper四叉樹-位圖混合結(jié)構(gòu)(proper quadtree bitmap hybridstructure，簡(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)建、