基于四叉樹編碼實(shí)現(xiàn)路由表壓縮的復(fù)合路由方案研究.pdf

1、無線網(wǎng)絡(luò)中已有的路由協(xié)議主要分為兩類:基于拓?fù)浣Y(jié)構(gòu)的路由和基于地理位置的路由。使用基于拓?fù)浣Y(jié)構(gòu)的路由協(xié)議，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以使用最短路徑算法選擇到不同目的節(jié)點(diǎn)相對最優(yōu)的路徑，但是節(jié)點(diǎn)存儲的路由表比較龐大，需要較大的存儲開銷，影響路由的效率。使用基于地理位置的路由協(xié)議，節(jié)點(diǎn)根據(jù)地理位置信息路由，只需維護(hù)很小的路由狀態(tài)。然而，貪婪地理位置路由不能實(shí)現(xiàn)數(shù)據(jù)包保證交付，可能出現(xiàn)路由空洞的問題。后來也有一些方案來解決路由空洞的問題，但是它們增加了路

2、由算法的復(fù)雜性。此外，采用地理位置路由，網(wǎng)絡(luò)中節(jié)點(diǎn)傳輸數(shù)據(jù)包的路徑較長。
　　本文我們結(jié)合兩類路由協(xié)議的優(yōu)勢，提出了一個基于四叉樹編址的復(fù)合路由機(jī)制HQLSR(Hierarchical Quadtree-Based Link State Routing)。HQLSR機(jī)制能夠在實(shí)現(xiàn)數(shù)據(jù)包保證交付的前提下顯著壓縮路由表，并且平均路徑延伸比較小。我們首先利用四叉樹數(shù)據(jù)結(jié)構(gòu)對不同地理位置的節(jié)點(diǎn)分配地址，然后根據(jù)節(jié)點(diǎn)的真實(shí)拓?fù)浒凑者B通性規(guī)則

3、進(jìn)行匯聚，將滿足連通性的節(jié)點(diǎn)匯聚成一個區(qū)域zone，最終網(wǎng)絡(luò)能夠分成不同的zone。我們在zone內(nèi)和zone間分別采用不同的路由算法，構(gòu)建一個層次化路由架構(gòu)。在zone內(nèi)，我們利用鄰居子樹路由算法來降低域內(nèi)路由表規(guī)模。在zone間，我們根據(jù)zone跳數(shù)采用最短路徑算法來選擇zone間的路徑。
　　在節(jié)點(diǎn)分布不均勻、分布區(qū)域比較狹長的情況下，節(jié)點(diǎn)采用四叉樹編址時最大編址長度會很長，匯聚效果不理想。因此，我們提出矩形編址來改進(jìn)四叉樹

4、編址減少最大編址長度。減少編址長度一方面能夠減少zone內(nèi)路由表的大小，另一方面能夠減少數(shù)據(jù)包包頭和路由表中節(jié)點(diǎn)地址域的長度。此外，利用矩形編址我們可以采用靈活地匯聚來提高匯聚效果，從而實(shí)現(xiàn)更好的壓縮效果。同樣我們將矩形編址技術(shù)應(yīng)用到路由機(jī)制中，提出了一個改進(jìn)的復(fù)合路由機(jī)制HRAR(Hierarchical Rectangle-based Addressing Routing)。實(shí)驗(yàn)結(jié)果表明HRAR路由機(jī)制相比HQLSR路由機(jī)制能實(shí)現(xiàn)更