匡紹東

（沈陽(yáng)理工大學(xué)研究生學(xué)院，遼寧沈陽(yáng)110159）

1 概述

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

2 DSR 路由協(xié)議

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

3 LS DSR 路由設(shè)計(jì)

3.1 協(xié)議總體思想

對(duì)路由協(xié)議的緩存提出過(guò)2 種機(jī)制：路徑緩存(path cache)和連接緩存(link cache)。局部自適應(yīng)DSR 路由協(xié)議(LSDSR)的總體思想是：全局拓?fù)洳捎寐窂骄彺妫植客負(fù)洳捎眠B接緩存。

3.2 協(xié)議整體機(jī)制

每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)局部連接表。讓路由所經(jīng)過(guò)的中間節(jié)點(diǎn)掌握半徑為幾跳范圍的局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)， 局部范圍內(nèi)的節(jié)點(diǎn)分為中心節(jié)點(diǎn)、轉(zhuǎn)發(fā)節(jié)點(diǎn)和邊界節(jié)點(diǎn)。對(duì)每條全局路由來(lái)說(shuō)，只讓路由上的每個(gè)邊界節(jié)點(diǎn)維護(hù)整條路由。邊界節(jié)點(diǎn)到下一跳邊界節(jié)點(diǎn)間的局部路由采用自治的方法，對(duì)源、目的和不相鄰的邊界節(jié)點(diǎn)透明。

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

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

（2）由于局部范圍采用連接緩存，節(jié)點(diǎn)知道局部完整的拓?fù)洌虼丝梢圆捎肈ijkstra 算法自行發(fā)現(xiàn)最短路徑。 如果原先最短路徑斷路，它會(huì)自行查找新的最短路徑，從而使得局部路由中的轉(zhuǎn)發(fā)節(jié)點(diǎn)斷路和繞遠(yuǎn)問(wèn)題得到解決。 在圖1 中， 從C 到I 根據(jù)算法先選擇最短路徑CEI 而不會(huì)繞遠(yuǎn)，當(dāng)E 跑到E’造成EI 斷路后并不產(chǎn)生RRER 報(bào)文，而是自動(dòng)選擇另一條路徑CFGHI， 這樣S 避免了重新啟動(dòng)路由發(fā)現(xiàn)過(guò)程，也減少了每個(gè)上游節(jié)點(diǎn)對(duì)RRER 報(bào)文的處理和轉(zhuǎn)發(fā)。

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

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

3 總結(jié)和展望

本文在DSR 的基礎(chǔ)上提出了LSDSR 路由協(xié)議，引進(jìn)了節(jié)點(diǎn)局部自適應(yīng)機(jī)制。 每個(gè)節(jié)點(diǎn)根據(jù)自己周圍的拓?fù)浣Y(jié)構(gòu)維護(hù)一個(gè)局部連接表，通過(guò)連接表，使路由發(fā)現(xiàn)和維護(hù)盡量使用節(jié)點(diǎn)已獲知的拓?fù)湫畔?，從局部和全局兩方面?duì)路由自動(dòng)化恢復(fù)調(diào)整。 從而有效改進(jìn)了DSR協(xié)議較大的路由維護(hù)開(kāi)銷和時(shí)延以及對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化適應(yīng)能力差等不足，提高了DSR 的傳輸性能。

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

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

［3］熊桂喜,王小虎,等,譯.計(jì)算機(jī)網(wǎng)絡(luò)[M].3 版.清華大學(xué)出版社，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.