摘  要： AODV路由協(xié)議每次在源節(jié)點只建立一條通向目的節(jié)點的路由,，未能充分利用從中間節(jié)點或者目的節(jié)點返回的路由應答信息,，針對這一問題,，提出了一個改進的方法。在源節(jié)點處建立一條主路由的基礎上,，利用路由應答信息,，建立一條備份路由，并且每次將最優(yōu)的設為主路由,，次優(yōu)的設為備份路由。仿真結(jié)果表明,，改進的協(xié)議和原協(xié)議相比,，降低了端到端的延時，提高了包投遞率

　　關鍵詞： Ad Hoc網(wǎng)絡,；路由協(xié)議,；AODV協(xié)議；備份路由

　　移動自組織網(wǎng)絡MANET（Mobile Ad Hoc Network）是一種移動,、自組織的系統(tǒng),。MANET是對等網(wǎng)絡，每個節(jié)點既可以作為主機,，也可以作為路由器,，數(shù)據(jù)包通過網(wǎng)絡進行逐跳轉(zhuǎn)發(fā),。由于它組網(wǎng)靈活、不依賴于現(xiàn)有的網(wǎng)絡基礎設施,，在軍事和緊急救援領域應用前景十分廣闊,。目前Ad Hoc網(wǎng)絡的路由協(xié)議可分為3大類，表驅(qū)動路由協(xié)議有OLSR,、WRP,、DSDV[1]，按需路由協(xié)議有AODV[2],、DSR,，基于約束的路由協(xié)議有ABR、LAR,。

　　AODV是一種按需路由協(xié)議,，并已經(jīng)成為IETF的標準化路由協(xié)議。它的主要特點是使用序列號來表示一條路由的新舊程度,，同時用來避免出現(xiàn)路由環(huán)路,，AODV主要有路由發(fā)現(xiàn)和路由維護兩個過程。

　　本文針對AODV路由協(xié)議出現(xiàn)鏈路斷開時只能通過本地修復機制來進行鏈路修復的不足,，利用從中間節(jié)點或者目的節(jié)點返回的路由應答信息,，在建立一條主路由的基礎上，再建立一條備份路由,，并且每次將最優(yōu)的設為主路由,，次優(yōu)的設為備份路由，使得出現(xiàn)鏈路斷開的上游節(jié)點能夠利用備份路由進行數(shù)據(jù)的傳輸,，有效地降低了時延和提高了分組投遞率,，通過仿真軟件NS2驗證了改進后的協(xié)議具有更好的性能。

1 AODV路由協(xié)議概述

　　1.1 路由發(fā)現(xiàn)過程

　　當源節(jié)點要向目的節(jié)點發(fā)送數(shù)據(jù)時,，創(chuàng)建一個路由請求包RREQ,，并向鄰居節(jié)點進行廣播，進行泛洪路由發(fā)現(xiàn)過程[3],。

　　中間節(jié)點收到路由請求之后,，首先根據(jù)RREQ中的廣播號判斷是否是已經(jīng)處理過的RREQ，如果是,，則丟棄,；如果是新收到的RREQ，就建立或者更新到源節(jié)點的反向路由,，使得反向路由表中到源節(jié)點的路由序列號大于RREQ中的序列號或者序列號相同并且有更少的跳數(shù),。然后查找路由表，如果沒有到目的節(jié)點的積極路由，就繼續(xù)廣播RREQ,，如果有到目的節(jié)點的積極路由,，并且路由中的目標節(jié)點序列號大于或者等于RREQ中的序列號，就沿著反向路由向源節(jié)點單播路由應答RREP,。

　　目的節(jié)點收到RREQ后,，不再廣播，建立反向路由,，產(chǎn)生一個含有最新序列號的路由應答RREP,，沿反向路由向源節(jié)點單播。中間節(jié)點收到RREP后,，建立到目的節(jié)點的正向路由,，并更新路由信息。源節(jié)點收到RREP后,，建立到目的節(jié)點的正向路由,，并開始向目的節(jié)點傳輸數(shù)據(jù)。

　　路由發(fā)現(xiàn)過程如圖1所示,。如果節(jié)點S需要對節(jié)點D進行通信,，節(jié)點S沒有到節(jié)點D的積極路由，節(jié)點S廣播一個路由請求RREQ,。節(jié)點1收到RREQ,，假設其沒有到節(jié)點D的積極路由，節(jié)點1會繼續(xù)廣播此RREQ,。假設節(jié)點2中有一條到達目的節(jié)點D的積極路由,，節(jié)點3和節(jié)點4中沒有到節(jié)點D的積極路由。最終節(jié)點S將會先后收到由節(jié)點2和節(jié)點D分別發(fā)送的包含S-1-2-D和S-3-4-D的路由應答RREP,，由于節(jié)點D發(fā)送的RREP具有更高的序列號,，所以路由S-1-2-D將被丟棄，即使這條路由也是有效的,。這樣當節(jié)點S與節(jié)點3鏈路斷開,，節(jié)點S進行鏈路失效處理時就無法使用路由S-1-2-D，而可能進行局部修復,，從而造成了延時,。設想如果能將S-1-2-D路由作為備份加以保留，那么在S-3-4-D路由斷裂時,，就可以轉(zhuǎn)換到使用備份路由上來。

　　1.2 路由維護

　　路由維護[4]可以及時發(fā)現(xiàn)節(jié)點因移動或其他原因而引起的鏈路斷開,，每個包含路由的節(jié)點,，周期地廣播HELLO消息，并且TTL值為1，因此只能與其相鄰節(jié)點傳播,。一個節(jié)點收到HELLO消息便知道自己與鄰節(jié)點保持連接,，如果在一定時間內(nèi)收不到HELLO消息，則進行鏈路失效的處理,。如果鏈路斷開處離目的節(jié)點較近,，將進行鏈路的局部修復，即由鏈路斷開處的上游節(jié)點發(fā)起到目的節(jié)點的路由發(fā)現(xiàn)過程,。如果在給定的時間內(nèi)重新建立起有效的路由,，就繼續(xù)發(fā)送數(shù)據(jù)；如果未能成功建立,，則向上游發(fā)送RERR,。如果鏈路斷開處離目的節(jié)點較遠，則不進行局部修復,，直接將路由設為失效狀態(tài),，并向上游發(fā)送RERR。設想如果有一條備份路由存在于鏈路斷開處離目的節(jié)點較遠的地方,，就可以直接使用備份路由而不必進行泛洪路由發(fā)現(xiàn)過程,。

2 基于備份路由的改進方法

　　對AODV路由協(xié)議的分析表明，源節(jié)點接收到路由應答RREP后,，將序列號最大或者序列號相同且有較少的跳數(shù)作為判據(jù),，因此只保留了一條到目的節(jié)點的路由，如果這條路由失效,，就會重新發(fā)起路由發(fā)現(xiàn)過程,，從而增大了網(wǎng)絡的開銷。為了充分利用源節(jié)點接收到的路由應答信息,，同時又能避免路由環(huán)路的出現(xiàn)[5],，對AODV協(xié)議作了改進。

　　在路由表項中添加標記主路由或備份路由的主/備份標志位,，并且初始化為0,，表示主路由（1表示備份路由），在鏈路未出現(xiàn)斷開的情況下,，均默認使用主路由,。

　　為了能夠?qū)崿F(xiàn)添加備份路由的功能，對源節(jié)點接收到RREP的處理過程作了修改,，如圖2所示,。在路由發(fā)現(xiàn)過程中，源節(jié)點接收到RREP后建立主路由,。如果接收到的RREP的序列號比存在的到該目的節(jié)點的主路由序列號大,，或者序列號相同但是有更少的跳數(shù)，并且是第一次接收到RREP的話，更新主路由,。如果不是第一次接收到RREP并且沒有備份路由,，則更改原來主路由的標志位，設為備份路由,，添加新的主路由并更新,；如果有備份路由，更改原來主路由中的標志位,，設為備份路由,，更改原來備份路由中的標志位，設為主路由并更新,。

　　如果源節(jié)點接收到的RREP的序列號沒有比存在的到目的節(jié)點的主路由序列號大,，或者序列號相同但是沒有更少的跳數(shù)，而且沒有備份路由,，則添加此RREP序列號對應的路由為備份路由,；如果存在備份路由，并且現(xiàn)接收序列號比備份路由序列號大,，或者序列號相同但是有更少的跳數(shù),，則更新備份路由，否則丟棄RREP,。

　　這樣通過以上過程,，就能使得每次在路由發(fā)現(xiàn)過程以及可能的修復過程中建立兩條路由，而且主路由和備份路由是最優(yōu)的兩條路由,，同時主路由優(yōu)于備份路由,。如圖1所示，通過改進的方法,，在與之前相同的情況下,，節(jié)點S與節(jié)點D之間便建立了一條主路由S-3-4-D和一條備份路由S-1-2-D。在整個網(wǎng)絡的路由發(fā)現(xiàn)過程中,，除了前述改進方法中源節(jié)點通過接收到的RREP建立備份路由時要查找本地路由表中是否有到目的節(jié)點的備份路由外,，其他的節(jié)點均只查找本地路由表中是否有到目的節(jié)點的主路由，從而保證了優(yōu)先使用主路由,。

　　在路由維護階段,，如圖3所示，如果節(jié)點S要向節(jié)點D傳輸數(shù)據(jù),，在建立的主路由S-1-4-5-D中,，節(jié)點1和節(jié)點4之間發(fā)生鏈路中斷，這時,，節(jié)點1要對鏈路斷開進行處理,。如果之前節(jié)點1向節(jié)點D傳輸過數(shù)據(jù),，并且通過本文前述改進的方法在路由發(fā)現(xiàn)過程中建立了備份路由1-2-3-D（節(jié)點1曾經(jīng)擔任過源節(jié)點），且該備份路由有效,，則節(jié)點1使用備份路由發(fā)送數(shù)據(jù)，從而減少了延時,，提高了分組的投遞率,；如果該備份路由已經(jīng)失效，則進行與原AODV協(xié)議相同的操作,。

3 仿真環(huán)境和結(jié)果

　　用仿真軟件NS2進行了模擬實驗[6],，網(wǎng)絡拓撲結(jié)構(gòu)是一個包含50個移動節(jié)點的網(wǎng)絡模型，各節(jié)點隨機分布在1 000 m×300 m的平面矩形區(qū)域內(nèi),，并隨機地以均勻分布在0~20 m/s之間的速度向區(qū)域內(nèi)任意目的地移動,，到達目的地后停留一段時間，然后再隨機地選擇一個目的地移動,，如此反復,，直到模擬結(jié)束?？偰M時間為300 s,，若停留時間為0，則節(jié)點到達目的地后不停留,，若停留時間為300 s,，則節(jié)點靜止。每個節(jié)點的數(shù)據(jù)速率為1 Mb/s,，MAC層協(xié)議采用IEEE 802.11,，采用CBR業(yè)務類型，CBR流的個數(shù)為10,。

　　端到端的延時是指一個數(shù)據(jù)分組從源節(jié)點的IP層到目的節(jié)點的IP層所需要的平均時間,，從圖4中可以看到兩種協(xié)議的平均端到端延時隨著節(jié)點暫停時間的增加都在減小，但是,，新協(xié)議的端到端延時比原協(xié)議更小,。

　　分組投遞率是目的節(jié)點應用層接收到的分組數(shù)與源節(jié)點發(fā)送的分組數(shù)之比，從圖5中可以看到兩種協(xié)議的分組投遞率隨著節(jié)點暫停時間的增加都在增加,，但是新協(xié)議有更高的分組投遞率,。

　　本文對AODV路由協(xié)議進行了分析，針對AODV路由發(fā)現(xiàn)過程中源節(jié)點未能充分利用路由應答的問題進行了改進,，建立備份路由,，并通過改進主路由和備份路由的選擇機制，使得當鏈路斷開時,，鏈路斷開處的上游節(jié)點可以使用備份路由發(fā)送數(shù)據(jù),，盡管在建立備份路由的過程中占用一定的時間和資源,，但仿真結(jié)果明顯表明，其減少了端到端的時延和提高了分組投遞率,。

　　參考文獻

　　[1] PERKINS C,， BHAGWAT P. Highly dynamic destination sequenced distance vector(DSDV）routing for mobile compu-ters[C]. Proceedings of ACMSIGCOMM′94， 1994：234-244.

　　[2] PERKINS C,， ROYER E. RFC 3561 Ad-hoc on-demand distance vector（AODV） routing[S]. 2003-07.

　　[3] 高興國,，王漢星，胡細.一個優(yōu)化的AODV路由協(xié)議[J].計算機工程與應用,，2007,，43（3）：128-130.

　　[4] 肖百龍，郭偉,，劉軍,，等.AODV的本地修復算法[J].計算機應用研究，2007,，24（3）：231-237.

　　[5] 李世寶,，洪利.基于鄰居緩存的AODV路由協(xié)議[J].計算機應用，2011,，31（7）：1931-1943.

　　[6] 馬崇霄,，吳長奇.基于網(wǎng)絡仿真器NS2的Ad hoc網(wǎng)絡路由協(xié)議仿真[J].電子測量技術，2008,，31（5）：75-79.