對AdHoc 無線網絡路由協議的探討

匡紹東

（沈陽理工大學研究生學院，遼寧沈陽110159）

1 概述

無線Ad Hoc 網絡是一種新型的無線移動網絡。 目前Ad Hoc 網絡路由協議大致分為2 種：表驅動路由協議(如DSDV 等)和按需路由協議(DSR，AODV 等)。 其中動態源路由協議DSR 是按需路由協議中一種既簡單又行之有效的路由協議。研究發現，Ad Hoc 網絡節點頻繁快速的移動使得拓撲結構不斷變化，DSR 緩存路由表更新不及時，導致路由性能降低甚至失效。所以在這里我們有必要對它的路由協議進行解析和深入探討。

2 DSR 路由協議

DSR 協議是一種基于源路由的按需路由協議， 它是Carnegie-Mellon 大學“Monarch”項目的一部分，主要包括2 個過程：路由發現和路由維護。 當節點S 向節點D 發送數據時，首先檢查緩存里是否存在到目的節點D 的有效路由。 如果存在則直接使用，否則啟動路由發現過程。 在通信過程中，當中間節點檢測到通往目的節點的下一跳鏈路中斷時，它將從自己路由緩存中刪去包含該鏈路的路由并向節點S 返回一個路由出錯分組(RERR)。 S 收到RERR 后，觸發一次新的路由發現過程。

3 LS DSR 路由設計

3.1 協議總體思想

對路由協議的緩存提出過2 種機制：路徑緩存(path cache)和連接緩存(link cache)。局部自適應DSR 路由協議(LSDSR)的總體思想是：全局拓撲采用路徑緩存，局部拓撲采用連接緩存。

3.2 協議整體機制

每個節點維護一個局部連接表。讓路由所經過的中間節點掌握半徑為幾跳范圍的局部網絡拓撲結構， 局部范圍內的節點分為中心節點、轉發節點和邊界節點。對每條全局路由來說，只讓路由上的每個邊界節點維護整條路由。邊界節點到下一跳邊界節點間的局部路由采用自治的方法，對源、目的和不相鄰的邊界節點透明。

該路由協議有以下幾點好處：

（1）例如，C 是S 的邊界點，I 是C 的邊界點，按照DSR 協議從S 到D 緩存的路徑為SABCEIJKLD；而按照LSDSR 協議，緩存中的路徑變為SCILD， 這樣邊界節點的全局路徑緩存從逐跳記錄變成了邊界點記錄，有效縮短了路徑。

（2）由于局部范圍采用連接緩存，節點知道局部完整的拓撲，因此可以采用Dijkstra 算法自行發現最短路徑。 如果原先最短路徑斷路，它會自行查找新的最短路徑，從而使得局部路由中的轉發節點斷路和繞遠問題得到解決。 在圖1 中， 從C 到I 根據算法先選擇最短路徑CEI 而不會繞遠，當E 跑到E’造成EI 斷路后并不產生RRER 報文，而是自動選擇另一條路徑CFGHI， 這樣S 避免了重新啟動路由發現過程，也減少了每個上游節點對RRER 報文的處理和轉發。

（3）同樣，全局路由中的邊界節點如果出現繞遠現象也可以自動調整。 起先S 到T 的邊界點路由為SCILD，經過一段時間后L 移動到L’的位置，C 發現L 跑進了自己的局部范圍內，并且LD 并未斷路，這樣C 把路由自動改為SCLD 后并通知其他各節點，避免繞遠。

以上3 點使得優化后的協議明顯減少了路由發現次數和傳輸時延。

3 總結和展望

本文在DSR 的基礎上提出了LSDSR 路由協議，引進了節點局部自適應機制。 每個節點根據自己周圍的拓撲結構維護一個局部連接表，通過連接表，使路由發現和維護盡量使用節點已獲知的拓撲信息，從局部和全局兩方面對路由自動化恢復調整。 從而有效改進了DSR協議較大的路由維護開銷和時延以及對網絡拓撲結構變化適應能力差等不足，提高了DSR 的傳輸性能。

［1］丁楠,張力軍.移動AdHoc 網絡路由協議的分析與比較[J].計算機與數字工程，2007 年07 期.

［2］徐亦璐.移動AdHoc 多徑路由算法的研究與優化[D].南昌大學，2008.

［3］熊桂喜,王小虎,等,譯.計算機網絡[M].3 版.清華大學出版社，1998.

［4］J.Macker and S.Corson.Mobile ad hoc networks(MANET)[Z].

［5］http:www.ietf.og/html.charters/manet-charter,html,1977 [OL].IETF Working Group Charter.