摘 要： AODV路由協議每次在源節點只建立一條通向目的節點的路由，未能充分利用從中間節點或者目的節點返回的路由應答信息，針對這一問題，提出了一個改進的方法。在源節點處建立一條主路由的基礎上，利用路由應答信息，建立一條備份路由，并且每次將最優的設為主路由，次優的設為備份路由。仿真結果表明，改進的協議和原協議相比，降低了端到端的延時，提高了包投遞率
關鍵詞： Ad Hoc網絡；路由協議；AODV協議；備份路由
移動自組織網絡MANET（Mobile Ad Hoc Network）是一種移動、自組織的系統。MANET是對等網絡，每個節點既可以作為主機，也可以作為路由器，數據包通過網絡進行逐跳轉發。由于它組網靈活、不依賴于現有的網絡基礎設施，在軍事和緊急救援領域應用前景十分廣闊。目前Ad Hoc網絡的路由協議可分為3大類，表驅動路由協議有OLSR、WRP、DSDV[1]，按需路由協議有AODV[2]、DSR，基于約束的路由協議有ABR、LAR。
AODV是一種按需路由協議，并已經成為IETF的標準化路由協議。它的主要特點是使用序列號來表示一條路由的新舊程度，同時用來避免出現路由環路，AODV主要有路由發現和路由維護兩個過程。
本文針對AODV路由協議出現鏈路斷開時只能通過本地修復機制來進行鏈路修復的不足，利用從中間節點或者目的節點返回的路由應答信息，在建立一條主路由的基礎上，再建立一條備份路由，并且每次將最優的設為主路由，次優的設為備份路由，使得出現鏈路斷開的上游節點能夠利用備份路由進行數據的傳輸，有效地降低了時延和提高了分組投遞率，通過仿真軟件NS2驗證了改進后的協議具有更好的性能。
1 AODV路由協議概述
1.1 路由發現過程
當源節點要向目的節點發送數據時，創建一個路由請求包RREQ，并向鄰居節點進行廣播，進行泛洪路由發現過程[3]。
中間節點收到路由請求之后，首先根據RREQ中的廣播號判斷是否是已經處理過的RREQ，如果是，則丟棄；如果是新收到的RREQ，就建立或者更新到源節點的反向路由，使得反向路由表中到源節點的路由序列號大于RREQ中的序列號或者序列號相同并且有更少的跳數。然后查找路由表，如果沒有到目的節點的積極路由，就繼續廣播RREQ，如果有到目的節點的積極路由，并且路由中的目標節點序列號大于或者等于RREQ中的序列號，就沿著反向路由向源節點單播路由應答RREP。
目的節點收到RREQ后，不再廣播，建立反向路由，產生一個含有最新序列號的路由應答RREP，沿反向路由向源節點單播。中間節點收到RREP后，建立到目的節點的正向路由，并更新路由信息。源節點收到RREP后，建立到目的節點的正向路由，并開始向目的節點傳輸數據。
路由發現過程如圖1所示。如果節點S需要對節點D進行通信，節點S沒有到節點D的積極路由，節點S廣播一個路由請求RREQ。節點1收到RREQ，假設其沒有到節點D的積極路由，節點1會繼續廣播此RREQ。假設節點2中有一條到達目的節點D的積極路由，節點3和節點4中沒有到節點D的積極路由。最終節點S將會先后收到由節點2和節點D分別發送的包含S-1-2-D和S-3-4-D的路由應答RREP，由于節點D發送的RREP具有更高的序列號，所以路由S-1-2-D將被丟棄，即使這條路由也是有效的。這樣當節點S與節點3鏈路斷開，節點S進行鏈路失效處理時就無法使用路由S-1-2-D，而可能進行局部修復，從而造成了延時。設想如果能將S-1-2-D路由作為備份加以保留，那么在S-3-4-D路由斷裂時，就可以轉換到使用備份路由上來。
1.2 路由維護
路由維護[4]可以及時發現節點因移動或其他原因而引起的鏈路斷開，每個包含路由的節點，周期地廣播HELLO消息，并且TTL值為1，因此只能與其相鄰節點傳播。一個節點收到HELLO消息便知道自己與鄰節點保持連接，如果在一定時間內收不到HELLO消息，則進行鏈路失效的處理。如果鏈路斷開處離目的節點較近，將進行鏈路的局部修復，即由鏈路斷開處的上游節點發起到目的節點的路由發現過程。如果在給定的時間內重新建立起有效的路由，就繼續發送數據；如果未能成功建立，則向上游發送RERR。如果鏈路斷開處離目的節點較遠，則不進行局部修復，直接將路由設為失效狀態，并向上游發送RERR。設想如果有一條備份路由存在于鏈路斷開處離目的節點較遠的地方，就可以直接使用備份路由而不必進行泛洪路由發現過程。
2 基于備份路由的改進方法
對AODV路由協議的分析表明，源節點接收到路由應答RREP后，將序列號最大或者序列號相同且有較少的跳數作為判據，因此只保留了一條到目的節點的路由，如果這條路由失效，就會重新發起路由發現過程，從而增大了網絡的開銷。為了充分利用源節點接收到的路由應答信息，同時又能避免路由環路的出現[5]，對AODV協議作了改進。
在路由表項中添加標記主路由或備份路由的主/備份標志位，并且初始化為0，表示主路由（1表示備份路由），在鏈路未出現斷開的情況下，均默認使用主路由。
為了能夠實現添加備份路由的功能，對源節點接收到RREP的處理過程作了修改，如圖2所示。在路由發現過程中，源節點接收到RREP后建立主路由。如果接收到的RREP的序列號比存在的到該目的節點的主路由序列號大，或者序列號相同但是有更少的跳數，并且是第一次接收到RREP的話，更新主路由。如果不是第一次接收到RREP并且沒有備份路由，則更改原來主路由的標志位，設為備份路由，添加新的主路由并更新；如果有備份路由，更改原來主路由中的標志位，設為備份路由，更改原來備份路由中的標志位，設為主路由并更新。
如果源節點接收到的RREP的序列號沒有比存在的到目的節點的主路由序列號大，或者序列號相同但是沒有更少的跳數，而且沒有備份路由，則添加此RREP序列號對應的路由為備份路由；如果存在備份路由，并且現接收序列號比備份路由序列號大，或者序列號相同但是有更少的跳數，則更新備份路由，否則丟棄RREP。
這樣通過以上過程，就能使得每次在路由發現過程以及可能的修復過程中建立兩條路由，而且主路由和備份路由是最優的兩條路由，同時主路由優于備份路由。如圖1所示，通過改進的方法，在與之前相同的情況下，節點S與節點D之間便建立了一條主路由S-3-4-D和一條備份路由S-1-2-D。在整個網絡的路由發現過程中，除了前述改進方法中源節點通過接收到的RREP建立備份路由時要查找本地路由表中是否有到目的節點的備份路由外，其他的節點均只查找本地路由表中是否有到目的節點的主路由，從而保證了優先使用主路由。
在路由維護階段，如圖3所示，如果節點S要向節點D傳輸數據，在建立的主路由S-1-4-5-D中，節點1和節點4之間發生鏈路中斷，這時，節點1要對鏈路斷開進行處理。如果之前節點1向節點D傳輸過數據，并且通過本文前述改進的方法在路由發現過程中建立了備份路由1-2-3-D（節點1曾經擔任過源節點），且該備份路由有效，則節點1使用備份路由發送數據，從而減少了延時，提高了分組的投遞率；如果該備份路由已經失效，則進行與原AODV協議相同的操作。
3 仿真環境和結果
用仿真軟件NS2進行了模擬實驗[6]，網絡拓撲結構是一個包含50個移動節點的網絡模型，各節點隨機分布在1 000 m×300 m的平面矩形區域內，并隨機地以均勻分布在0~20 m/s之間的速度向區域內任意目的地移動，到達目的地后停留一段時間，然后再隨機地選擇一個目的地移動，如此反復，直到模擬結束。總模擬時間為300 s，若停留時間為0，則節點到達目的地后不停留，若停留時間為300 s，則節點靜止。每個節點的數據速率為1 Mb/s，MAC層協議采用IEEE 802.11，采用CBR業務類型，CBR流的個數為10。
端到端的延時是指一個數據分組從源節點的IP層到目的節點的IP層所需要的平均時間，從圖4中可以看到兩種協議的平均端到端延時隨著節點暫停時間的增加都在減小，但是，新協議的端到端延時比原協議更小。
分組投遞率是目的節點應用層接收到的分組數與源節點發送的分組數之比，從圖5中可以看到兩種協議的分組投遞率隨著節點暫停時間的增加都在增加，但是新協議有更高的分組投遞率。
本文對AODV路由協議進行了分析，針對AODV路由發現過程中源節點未能充分利用路由應答的問題進行了改進，建立備份路由，并通過改進主路由和備份路由的選擇機制，使得當鏈路斷開時，鏈路斷開處的上游節點可以使用備份路由發送數據，盡管在建立備份路由的過程中占用一定的時間和資源，但仿真結果明顯表明，其減少了端到端的時延和提高了分組投遞率。
參考文獻
[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] 高興國，王漢星，胡細.一個優化的AODV路由協議[J].計算機工程與應用，2007，43（3）：128-130.
[4] 肖百龍，郭偉，劉軍，等.AODV的本地修復算法[J].計算機應用研究，2007，24（3）：231-237.
[5] 李世寶，洪利.基于鄰居緩存的AODV路由協議[J].計算機應用，2011，31（7）：1931-1943.
[6] 馬崇霄，吳長奇.基于網絡仿真器NS2的Ad hoc網絡路由協議仿真[J].電子測量技術，2008，31（5）：75-79.