匡紹東

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

1 概述

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

2 DSR 路由協(xié)議

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

3 LS DSR 路由設計

3.1 協(xié)議總體思想

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

3.2 協(xié)議整體機制

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

該路由協(xié)議有以下幾點好處：

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

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

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

以上3 點使得優(yōu)化后的協(xié)議明顯減少了路由發(fā)現(xiàn)次數(shù)和傳輸時延。

3 總結和展望

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

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

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

［3］熊桂喜,王小虎,等,譯.計算機網(wǎng)絡[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.