基于四叉樹的路由技術研究.pdf

1、在網絡互連中，路由發(fā)揮了重要的作用。利用它一方面能夠找到最優(yōu)的路徑;另一方面能夠盡可能減小由路由引起的開銷，從而提高路由協(xié)議的性能。迄今為止，大量的路由方案已被廣泛研究。根據(jù)不同的需求，路由方案可以被分成多種類型。根據(jù)路由中利用信息的多少，現(xiàn)存的方案主要可以被分成兩類，即基于圖拓撲的路由和基于地理位置的路由。對于基于圖拓撲的路由，它總能保證找到最優(yōu)路徑，但路由表中包含了大量的表項。與基于圖拓撲路由中路由表的大小相比，基于地理位置路由的路

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

3、中的最好的結果（基于IP的方案）還要好。與其它方案相比，QOPR路由機制有兩大優(yōu)勢。一方面，它的編碼方案比IP地址更加直觀。路由表中的目的節(jié)點由四叉樹編碼，它可以直觀的劃分、編碼節(jié)點。另一方面，我們得到的路由表大小優(yōu)于現(xiàn)存文獻中的結果。仿真實驗表明，一般情況下，本方案無論在路由表大小還是路由表的構建、查找性能上均優(yōu)于基于IP的方案。-提出了一種QOPR+路由機制----針對QOPR路由機制中，當插入新節(jié)點時引起的路由更新的不足，在QOP

4、R路由機制的基礎上，提出QOPR+路由機制。通過采用一種新型的proper四叉樹-位圖混合結構(proper quadtree bitmap hybridstructure，簡稱pqbh(T)）作為路由表，它能夠進一步降低更新復雜度，兼顧查找速度和更新性能。此外，本文從理論上證明pqbh（T）也是一個很省空間的數(shù)據(jù)結構。與QOPR路由機制中路由表的大小只相差了一個很小的常數(shù)因子。仿真實驗表明，一般情況下，QOPR+路由機制的路由表構建、