基于AODV的Ad Hoc網(wǎng)絡(luò)多路徑路由協(xié)議

周 杰

（安徽電子信息職業(yè)技術(shù)學(xué)院 軟件學(xué)院，安徽 蚌埠 233030）

0 引 言

Ad Hoc網(wǎng)絡(luò)[1]是一種無中心，并具有高效、自組織性的移動通信網(wǎng)絡(luò)，由于它具有多跳轉(zhuǎn)發(fā)技術(shù)、支持動態(tài)變換的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，以及抗毀性等特點，在事故突發(fā)現(xiàn)場、軍事戰(zhàn)術(shù)環(huán)境等領(lǐng)域被采用。然而，由于Ad Hoc網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)頻繁地變化，使得傳統(tǒng)的互聯(lián)網(wǎng)路由協(xié)議不能在該網(wǎng)絡(luò)使用，如ospf和rip。因而，Ad Hoc網(wǎng)絡(luò)所采用的路由協(xié)議一直是研究重點。

其中，按需路由協(xié)議AODV[2]是Ad Hoc網(wǎng)絡(luò)中一種極其重要的路由協(xié)議，它吸取了DSR[3]和DSDV[4]的優(yōu)點，技術(shù)成熟，是 DSR與 DSDV的完美結(jié)合。它不必維護去往所有節(jié)點的路由，僅在沒有去往目的節(jié)點路由的時候才按需進行路由發(fā)現(xiàn)，從而有效地節(jié)省了網(wǎng)絡(luò)資源。

但是，使用AODV路由協(xié)議的Ad Hoc網(wǎng)絡(luò)仍然有兩個問題亟待解決[5]。其一，源節(jié)點僅維護一條到指定目的節(jié)點的單路徑路由[6]，當(dāng)因某種因素（轉(zhuǎn)發(fā)節(jié)點位置移動）使得這條單路徑路由失效，從而使源節(jié)點需要重新進行到達(dá)目的節(jié)點的路由發(fā)現(xiàn)過程，因此，在網(wǎng)絡(luò)拓?fù)漕l繁變化的Ad Hoc網(wǎng)絡(luò)中，這將會影響整個網(wǎng)絡(luò)的傳輸性能。其二，源節(jié)點采用泛洪廣播的方式發(fā)送RREQ報文來建立路由的發(fā)現(xiàn)過程，但不論中間節(jié)點還是目的節(jié)點都只對收到的第一個RREQ報文進行處理，發(fā)送RREP報文或建立反向路由，然而大部分其它后到達(dá)的RREQ報文會被節(jié)點沒有利用地直接丟棄，從而浪費了Ad Hoc網(wǎng)絡(luò)帶寬。因此，針對AODV路由協(xié)議在這兩方面存在的不足，文中對AODV路由協(xié)議進行了改進，形成了新的AODV路由協(xié)議，即多路徑AODV 路由協(xié)議 （MultiPath AODV，MPAODV）。

1 MP－AODV路由協(xié)議的研究

通過對AODV路由協(xié)議兩方面的改進和擴展，形成了MP－AODV路由協(xié)議。這兩方面的改進分別為中間節(jié)點如何處理收到的RREQ報文和節(jié)點是如何選取不重復(fù)多路徑路由的，下面進行具體介紹。

1.1 MP－AODV路由協(xié)議對RREQ報文的處理

在使用AODV路由協(xié)議的Ad Hoc網(wǎng)絡(luò)中，當(dāng)源節(jié)點需要和目的節(jié)點通信但無有效路徑可用時，便啟動路由發(fā)現(xiàn)過程，產(chǎn)生RREQ報文路由請求消息，并以泛洪方式在全網(wǎng)范圍內(nèi)廣播，所以，多個相同RREQ報文（＜源節(jié)點序列號，RREQ ID＞相同）可能都會被中間節(jié)點收到。但是因為AODV路由協(xié)議是單路徑路由協(xié)議，所以，中間節(jié)點只會處理第一個到達(dá)的RREQ報文，其它隨后到達(dá)相同的RREQ報文直接就會被丟棄掉。這個中間節(jié)點處理RREQ報文的過程，使得有限的Ad Hoc網(wǎng)絡(luò)帶寬被浪費了。

然而，在 MP－AODV路由協(xié)議中，若中間節(jié)點在接收到多個相同的RREQ報文時，不會不做處理地丟棄掉這些相同的RREQ報文，而是讓后到達(dá)的RREQ報文和第一到達(dá)的RREQ報文進行比較，從而決定是否丟棄后到達(dá)的RREQ報文。其過程為中間節(jié)點收到第一個RREQ報文時，會將報文中的跳數(shù)值這個參數(shù)保存在緩存中，并建立反向路由，接著把該RREQ報文轉(zhuǎn)發(fā)給鄰居節(jié)點。然而，該中間節(jié)點再次收到相同RREQ報文（＜源節(jié)點序列號，RREQ ID＞相同）時，它會比較這個RREQ報文中的跳數(shù)值和自己緩存中的跳數(shù)值，若小于或者等于自己緩存中的跳數(shù)值，則該中間節(jié)點會建立另外一個反向路由，并將該RREQ報文繼續(xù)轉(zhuǎn)發(fā)給它的相鄰節(jié)點；若大于自己緩存中的跳數(shù)值，那么該節(jié)點會將該RREQ報文不做處理地丟棄掉。

一個包含5個節(jié)點的Ad Hoc網(wǎng)絡(luò)如圖1所示。

圖1 一個包含5個節(jié)點的Ad Hoc網(wǎng)絡(luò)

當(dāng)前源節(jié)點S需要向目的節(jié)點D傳輸數(shù)據(jù)，但是源節(jié)點S的路由表中沒有相關(guān)的路由，那么源節(jié)點S將啟動路由的發(fā)現(xiàn)過程，并產(chǎn)生和廣播RREQ報文。

在AODV路由協(xié)議中，節(jié)點處理RREQ報文的情況如圖2所示。

圖2 AODV路由協(xié)議，節(jié)點處理RREQ報文

中間節(jié)點c可以收到兩個相同的分別來自節(jié)點S和節(jié)點a的RREQ報文，但是中間節(jié)點c只處理先到達(dá)來自節(jié)點S的RREQ報文來建立反向路由，然而后到達(dá)來自節(jié)點a的RREQ報文，會不被處理地被節(jié)點c丟棄掉。節(jié)點b和節(jié)點D同樣也只處理最先到達(dá)的RREQ報文。

在MP－AODV路由協(xié)議中，節(jié)點處理RREQ報文的情況如圖3所示。

圖3 MP－AODV路由協(xié)議，節(jié)點處理RREQ報文

中間節(jié)點c可以收到兩個相同的分別來自節(jié)點S和節(jié)點a的RREQ報文，然而節(jié)點c會將首先接收到的來自節(jié)點S的RREQ報文進行處理，將報文中跳數(shù)為1的值記錄在自己的緩存中，中間節(jié)點c將會對后到達(dá)來自節(jié)點a的RREQ報文中的跳數(shù)值和自己緩存中的值進行比較后，決定該報文被丟棄，因為該報文中的跳數(shù)值為2大于中間節(jié)點c緩存中的值1。中間節(jié)點b可以收到兩個相同的分別來自節(jié)點a和節(jié)點c的RREQ報文，因為這兩個報文中跳數(shù)值都相同（都為2），所以，這兩個RREQ報文不論誰先到達(dá)還是后到達(dá)，都不會被中間節(jié)點b丟棄。

1.2 MP－AODV路由協(xié)議中不重復(fù)多路路由的選取

在MP－AODV路由協(xié)議中，目的節(jié)點最終可以收到多條來自不同路徑但相同的RREQ報文，若它根據(jù)這些報文形成多路徑的反向路由，并向源節(jié)點發(fā)送RREP報文的話，最終源節(jié)點就會學(xué)習(xí)到多條到達(dá)目的節(jié)點的路由。但是這些路由的中間節(jié)點有可能出現(xiàn)重復(fù)，只有中間節(jié)點不重復(fù)[3]，才能保證Ad Hoc網(wǎng)絡(luò)的穩(wěn)定性。

在圖3中，最終源節(jié)點S的路由表中存在3條去往目的節(jié)點D的路徑，其分別為S→c→D，S→a→b→D，S→c→b→D，可以發(fā)現(xiàn)，這3條路徑中，中間節(jié)點b和中間節(jié)點c重復(fù)屬于不同路徑，因而有可能因為其中某一節(jié)點的失效，造成該節(jié)點所連接的路徑都失效，所以，這3條路徑因為節(jié)點重復(fù)必將使Ad Hoc網(wǎng)絡(luò)的穩(wěn)定性受到影響。

為了使MP－AODV路由協(xié)議在路由發(fā)現(xiàn)的過程中，學(xué)習(xí)并形成節(jié)點不重復(fù)多路徑路由，在原來的RREQ協(xié)議幀中新添加“路由記錄列表”一項，形成新的RREQ協(xié)議幀。該幀中的“路由記錄列表”記錄RREQ報文從源節(jié)點到目的節(jié)點所經(jīng)過的中間節(jié)點地址。也就是當(dāng)RREQ報文傳送到中間節(jié)點時，中間節(jié)點會把自己的地址添加到該幀的“路由記錄列表”中，并轉(zhuǎn)發(fā)。

新RREQ協(xié)議幀中的“路由記錄列表”如圖4所示。

圖4 新RREQ協(xié)議幀中的“路由記錄列表”

在圖4中，當(dāng)源節(jié)點S廣播發(fā)送一個RREQ報文時，中間節(jié)點a和中間節(jié)點c接收到該報文后，若該報文有效，且該報文中的“路由記錄列表”中沒有自己節(jié)點地址，節(jié)點a和節(jié)點c會將自己的地址添加到“路由記錄列表”中，接著該RREQ報文再轉(zhuǎn)發(fā)給它的鄰居，當(dāng)中間節(jié)點b接收到該RREQ報文后，會采用相同的處理，在該RREQ報文的“路由記錄列表”中添加上自己的地址，因而當(dāng)該報文到達(dá)目的節(jié)點D時，目的節(jié)點D就可通過報文中“路由記錄列表”中的值，得知從源節(jié)點到目的節(jié)點存在幾條路徑。

MP－AODV路由協(xié)議通過新的RREQ報文，發(fā)現(xiàn)節(jié)點不重復(fù)多路徑路由非常容易，當(dāng)目的節(jié)點接收到一個新RREQ報文到達(dá)時，若是第一個，目的節(jié)點會將該報文中的“路由記錄列表”的值保存在自己的緩存中，同時，目的節(jié)點會按反向路由發(fā)送RREP報文。如果目的節(jié)點再次收到相同的新的RREQ報文時，會比較它的緩存中值和該報文中“路由記錄列表”的值，以判斷是否存在相同的節(jié)點 （源節(jié)點除外）。如果存在相同的節(jié)點，則丟棄掉該報文；如果不存在相同的節(jié)點，則將該報文中“路由記錄列表”的值也保存在緩存中，同時，目的節(jié)點也會按反向路由發(fā)送RREP報文。

由圖4可知，當(dāng)路徑為S→c→D的新RREQ報文最先到達(dá)目的節(jié)點D時，目的節(jié)點D將會把該報文中“路由記錄列表”中的值S，c保存在自己的緩存中，并發(fā)送反向RREP報文，當(dāng)目的節(jié)點D收到相同的RREQ報文，但路徑為S→c→b→D時，會比較該報文“路由記錄列表”和自己緩存中的值，比較后發(fā)現(xiàn)中間節(jié)點c重復(fù)了，所以目的節(jié)點會丟棄該RREQ報文。當(dāng)?shù)?個相同的RREQ報文到達(dá)目的節(jié)點D，但路徑為S→a→b→D時，再次比較自己緩存中的值和該報文中“路由記錄列表”中的值，比較后發(fā)現(xiàn)沒有節(jié)點重復(fù)，此時目的節(jié)點D也會將該報文“路由記錄列表”中的值S，a，b保存在自己的緩存中，并發(fā)送反向RREP報文。當(dāng)這兩條RREP報文到達(dá)源節(jié)點S后，源節(jié)點S就學(xué)習(xí)到，到達(dá)目的節(jié)點D存在兩條節(jié)點不重復(fù)路由，如圖5所示。

圖5 不重復(fù)節(jié)點的多路徑路由

2 仿真結(jié)果及分析

為了驗證MP－AODV路由協(xié)議比AODV路由協(xié)議有效，使用NS2[8]模擬軟件來仿真AODV和MP－AODV路由協(xié)議，仿真環(huán)境為一個包含50個移動節(jié)點的網(wǎng)絡(luò)模型，各節(jié)點隨機分布在1000m×1000m的矩形區(qū)域內(nèi)，并在100m的模擬時間內(nèi)，隨機以最小為0m／s的速度，最大從0m／s到60m／s的速度向任意目的地移動，到達(dá)目的地后，停留時間為0s，然后繼續(xù)隨機地選擇另一個節(jié)點移動。

2.1 數(shù)據(jù)報傳輸成功率的比較

通過模擬軟件NS2對AODV和MP－AODV的仿真實驗，將得到網(wǎng)絡(luò)節(jié)點在不同速度下數(shù)據(jù)報傳輸成功率的數(shù)據(jù)，并繪制出折線圖，如圖6所示。

1）當(dāng)節(jié)點移動速度小于35m／s時，網(wǎng)絡(luò)節(jié)點之間的鏈路比較穩(wěn)定，數(shù)據(jù)包很少丟失，所以，這兩個路由協(xié)議的數(shù)據(jù)報傳輸成功率較接近且較高。

圖6 兩種路由協(xié)議的數(shù)據(jù)報傳輸成功率

2）當(dāng)節(jié)點移動速度大于35m／s時，AODV的數(shù)據(jù)報傳輸成功率下降非?？?，但MP－AODV的數(shù)據(jù)報傳輸成功率仍然維持較高水平（80%左右）。因而節(jié)點以比較快的速度移動時，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)會發(fā)生較大變化，從而容易造成源節(jié)點到目的節(jié)點失效的路由路徑，傳輸過程中易出現(xiàn)數(shù)據(jù)包丟失。這個時候AODV中的源節(jié)點只能重新廣播RREQ報文來學(xué)習(xí)新的路由路徑。然而，此時在MP－AODV中源節(jié)點會啟動備份路由來發(fā)送數(shù)據(jù)，無需學(xué)習(xí)新的路由路徑。

2.2 平均延遲時間的比較

用同樣的方法，最終將得到節(jié)點在不同速度下平均延遲時間的數(shù)據(jù)，并繪制出折線圖，如圖7所示。

圖7 兩種路由協(xié)議的平均延遲時間

1）當(dāng)節(jié)點移動速度小于35m／s時，網(wǎng)絡(luò)節(jié)點之間的鏈路比較穩(wěn)定，所以兩種路由協(xié)議的平均延遲時間都比較接近且值小。但AODV的平均的延遲時間有時會低于MP－AODV，出現(xiàn)這樣的情況原因是MP－AODV的目的節(jié)點需要通過比較多個RREQ報文來決定是否發(fā)送RREP報文，而且源節(jié)點還通過接受到多條RREP報文來建立多條節(jié)點不重復(fù)路由，因此，花費時間要比AODV路由協(xié)議多。

2）當(dāng)節(jié)點移動速度大于35m／s時，AODV的平均延遲時間會迅速增加，而MP－AODV的平均延遲時間增加緩慢。這是因為當(dāng)網(wǎng)絡(luò)節(jié)點以較快速度移動時，Ad Hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)會較大變化，容易造成源節(jié)點到目的節(jié)點的路由失效，傳輸?shù)臄?shù)據(jù)包也容易丟失。此時AODV中的源節(jié)點只能重新廣播RREQ請求報文，以便學(xué)習(xí)到新的路由。但是，在MP－AODV協(xié)議中源節(jié)點會啟動備份路由來發(fā)送數(shù)據(jù)，無需學(xué)習(xí)新的路由路徑。

3 結(jié) 語

Ad Hoc網(wǎng)絡(luò)因組網(wǎng)靈活簡便、生存能力強，所以具有極其廣泛的應(yīng)用前景，同時其路由協(xié)議一直是研究的重點。文中針對Ad Hoc網(wǎng)絡(luò)中典型路由協(xié)議AODV存在的問題，對其進行改進，提出了MP－AODV路由協(xié)議。通過NS－2軟件的仿真結(jié)果表明，在網(wǎng)絡(luò)節(jié)點以較大速度移動時，MP－AODV路由協(xié)議的數(shù)據(jù)報傳輸成功率和平均延遲都比AODV路由協(xié)議有所提高，從而使Ad Hoc網(wǎng)絡(luò)數(shù)據(jù)傳輸效率得到提高。

[1]陳林星.移動Ad Hoc網(wǎng)絡(luò)[M].北京：電子工業(yè)出版社，2006.

[2]Perkins C，Belding－Royer，Das S.Ad hoc On－demand Distance Vector（AODV）Routing[EB／OL].RFC 3561.[2003－05－10]http：／／www.ietf.org／rfc／rfc3561.txt：July.

[3]王申濤，楊浩，周熙，等.Ad Hoc網(wǎng)絡(luò)DSR路由協(xié)議仿真性能分析[J].無線電通信技術(shù)，2006（5）：54－65.

[4]Perkins C E，Bhagwat P.Highly dynamic Ddestination－Sequenced Ddistance－Vector Routing （DSDV）for mobile computers[C]／／ Processing of SIGCOMM’94，ACM SIGCOMM’94Communications Architectures.New York：ACM Press.，1994.

[5]毛靖添，馬光勝，李洪升.基于AODV動態(tài)自適應(yīng)多路徑路由[J].長春工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2006，27（2）：75－79.

[6]朱彥松，萬潤澤，羅飛，等.Ad hoc網(wǎng)絡(luò)單路徑路由算法的比較研究[J].計算機與數(shù)字工程，2007，（8）：101－110.

[7]Gou Yiao－Feng，Chen Yue－Quan.An aggregated multipath routing scheme for Ad Hoc networks[J].Jounral of Software，2004，15（4）：594－603.

[8]徐雷鳴，龐博，趙耀.NS與網(wǎng)絡(luò)模擬[M].北京：人民郵電出版社，2003.