基于閑時逆尋和路由學習機制的優化AODV路由協議

杜青松，朱江，張爾揚

（1. 國防科技大學 電子科學與工程學院，湖南 長沙 410073；

2. 湖南大學 計算機與通信學院，湖南 長沙 410082）

1 引言

按需距離矢量路由協議 AODV是移動自組織網絡（MANET）中一種經典的反應式路由協議，它專門針對MANET網絡自身特點而設計，具有算法簡單易實現、適度的控制開銷和帶寬開銷、具有良好的擴展性等優點，已經成為MANET網絡中一種標準化的路由協議[1]。

但在不同的網絡場景下，AODV路由協議在性能和效率方面存在著一定的局限和不足。

1) 在AODV協議中，一條已建立的路由在超過一段時間沒有進行數據傳輸的情況下會被刪除。在網絡拓撲變化相對較緩慢的MANET網絡中，節點間的路由相對較穩定，然而根據AODV協議，這些穩定的路由會由于超時而被刪除，導致額外的重路由開銷，增加了網絡負擔。

2) 在較大規模的MANET網絡中，處于網絡邊緣的節點之間跳數較多，當網絡一側的邊緣節點需要建立到網絡另一側的邊緣節點的路由時，最壞情況下路由的建立過程將貫穿整個網絡，這將導致較大的路由建立延時，對于實時性要求較高的業務數據傳輸是不利的。

3) AODV協議的路由發現過程只能建立一條源節點到目的節點的最短距離路由，沒有冗余路由信息，一旦由于網絡拓撲變化等原因導致路由故障，將不得不由上游節點進行本地修復或由源節點重新發起路由發現過程。如果網絡拓撲變化較快，則整個網絡中用于重路由和本地修復的開銷將大大增加，導致網絡性能的急劇下降。

不少研究文獻對AODV協議進行了改進，以提高它的性能。文獻[2～6]在 AODV協議的基礎上進行擴展，在一次路由發現的過程中建立多條到目的節點的路由，通信時使用其中一條路由，其余路由作為備份。這種多徑路由的方式提高了數據傳輸的可靠性，但路由建立的時延較大，路由發現和維護過程比較復雜。AODV-PA協議[7]利用DSR協議[8]的路徑收集思想，一次路由發現過程能夠建立很多路由，提高了路由發現的效率，但協議開銷大，路由請求響應延遲大。文獻[9]根據節點的速度和方向信息計算節點之間的可靠通信距離，通過選擇可靠距離大的節點建立路由的方式來提高 AODV協議對拓撲結構變化較快的網絡的適應能力，但要求每個節點配置GPS設備。ELRAODV[10]通過在節點間交互增強的Hello分組和NHello分組中，能夠快速感知路由中的故障點，并通過一種改進的本地修復機制提高故障路由的修復率。SARP[11]提出一種自學習機制，節點在轉發路由請求和響應分組時從分組頭中提取路由信息，從而使轉發節點能夠建立到源節點和目的節點的路由，但學習的節點僅限于最終建立的主路由上的節點。

本文在節點不增加硬件設備和不過多增加節點處理負擔的前提下，對基礎AODV路由協議進行擴展，利用網絡中很多節點經常處于空閑狀態的特點，提出一種節點在空閑時間進行反向路由搜索機制（本文簡稱閑時逆尋機制），該機制能夠在網絡中建立局部路由、刷新現成路由和更新故障路由；參照文獻[11]中節點學習路由的思想，利用無線信道廣播傳輸的特性，提出一種鄰居節點路由監聽學習機制（本文簡稱為路由學習機制），在不增加路由開銷的前提下為主路由建立冗余的路由信息，能夠加快新路由的發現和故障路由的快速修復。結合這2種機制而提出的O-AODV（optimized AODV）路由協議能夠在網絡規模擴大或網絡拓撲快速變化的情況下提升基礎 AODV路由協議的性能和路由效率，減少重路由的次數，降低網絡中無謂的路由開銷和控制開銷。

2 O-AODV的基本思想

2.1 閑時逆尋機制的基本思想

定義 1 節點空閑狀態：當一個節點在某個時間段內除了與鄰居節點交換Hello信息分組外，不進行任何其他信息分組（包括數據分組、路由信息分組RREQ和RREP等）的發送、接收和轉發，則定義該節點在此時間段內處于空閑狀態。

定義 2 節點空閑時間：一個節點連續處于空閑狀態的時間長度稱為該節點的一段空閑時間，記作τIdle。在整個MANET網絡維持期間，同一節點可能會有很多段空閑時間，尤其是在通信量較少的網絡中。

在 O-AODV路由協議中定義一個節點空閑時間的閾值Tth，當某節點L檢測到自己的空閑時間τIdle＞Tth，就嘗試在網絡中廣播一個反向RREQ探測分組（R-RREQ），反向尋找以L為目的節點的源節點；如果R-RREQ在廣播過程中，正好碰到某個節點S要建立到節點L的路由，則節點S廣播的RREQ和節點L廣播的R-RREQ會在某個中間節點I相遇，由于此時節點I已經有I→S的反向路由和I→L的正向路由，I只要分別向S和L發送RREP報文就可以建立 S→L的路由，這樣就加快了路由發現的過程，這種在節點空閑時反向尋找源節點的過程就是本文提出的閑時逆尋機制。工作原理如圖1所示。

不過，上面描述的過程不是閑時逆尋機制的主要用途，因為并不是空閑節點L每次進行反向探測時都恰好能碰到有別的節點正在建立到L的路由。閑時逆尋機制的主要作用如下。

1) 空閑節點 L通過閑時逆尋操作，可以讓 L附近的其他節點建立到L的局部路由，一旦網絡中有節點要與L通信，這些局部路由就可以幫助源節點快速建立到L的路由，從而充分利用網絡資源。

圖1 閑時逆尋機制工作原理示例

2) 利用空閑時間刷新已經存在的路由，使這些已經存在的路由不會因為超時而被刪除。如圖2所示，節點f到節點q已經建立了路由f→g→m→q，該路由完成數據傳輸后就空閑下來，在該路由將要失效前，節點q在網絡上廣播一個R-RREQ分組，該路由上的節點m、g和f收到來自q的R-RREQ后就刷新自己路由表中到節點q的路由，使得路由繼續保持，以便下次使用。

3) 更新網絡中由于拓撲結構變化而斷裂的路由，加快路由的修復。如圖2所示，節點S建立了到節點d的路由S→c→e→h→d，但由于節點d在通信過程中移出了h的通信范圍使得h到d的鏈路斷開，因此斷開一段時間后d進入空閑狀態，于是d在網絡上廣播一個R-RREQ分組，此時節點e收到此R-RREQ，就可以重建S到d的路由。

圖2 閑時逆尋機制進行路由維護的原理示例

定義 3 信道空閑：如果一個節點的鄰居中有節點正在發送或轉發除Hello信息分組外的其他信息分組，則稱該節點的信道不空閑；反之則稱為信道空閑。

由于網絡可能會有很多節點同時處于空閑狀態，如果這些空閑節點同時進行反向探測，將會使網絡負載急劇上升，網絡中傳輸的數據分組發生碰撞的概率大大增加，反而使得網絡的性能下降，因此要采取措施限制同一時刻網絡進行反向探測的空閑節點數。本文采用信道偵聽+隨機退避機制來完成這種限制，具體做法是：源空閑節點在發送R-RREQ前先偵聽信道，如果信道不空閑，就隨機退避一段時間后再偵聽信道，直到信道空閑才開始廣播自己的R-RREQ；中間節點在轉發R-RREQ前先偵聽信道，如果信道不空閑，就停止轉發該R-RREQ，而只是向源空閑節點單播一個RREP分組，建立局部的雙向路由，從而限制R-RREQ在全網的洪泛。

2.2 路由學習的基本思想

由于無線信道具有廣播特性，因此MANET網絡中的任何一個節點向外發送任何消息時，它的鄰居節點都可監聽到此消息。如果將節點的工作模式設置為雜收模式，該節點就可以接收所有監聽到的消息并進行處理。

在AODV中，每一個數據分組和路由應答分組（RREP）中都包含有到源節點或目的節點的路由信息，如果所有節點都工作于雜收模式，則每個節點可以通過監聽鄰居節點發送或轉發的數據分組或RREP分組，從而可以獲取網絡中的路由信息，這一過程稱為路由學習。

如圖3所示，網絡中存在2條路由，一條是正在進行數據傳輸的路由L→n→j→g，另一條是正在從目的節點l向源目的發送RREP分組的即將建立的路由S→c→e→h→l。節點f可以監聽到節點c轉發的RREP分組，因此能從RREP分組頭中提取到源節點S和目的節點l的路由信息，從而可以建立到 S的路由 f→c→S和到 l的路由 f→c→e→h→l。同理，節點I可以監聽到j轉發的數據分組，根據從數據分組頭中提取的路由信息，分別可以建立節點 I到節點 g和到節點 L的路由：I→j→g和 I→j→k→L。但這些學習到的路由信息有些是不完整的，在3.3節中進行了分析，并提出了解決方案，從而使網絡中增加了很多冗余的備份路由信息。

圖3 路由學習機制工作原理示例

通過路由學習機制獲得的路由并不一定是最短路由，但它用很少的節點處理開銷就為網絡中的主路由增加了很多有用的冗余路徑，給故障路由的快速修復和新路由的發現提供了可能。

3 O-AODV中的算法描述

3.1 路由發現與維護算法

O-AODV的路由發現過程與AODV相似，當源節點S需要到某個目的節點D的路由而其路由表中又沒有時，它就啟動路由發現過程[1]。

O-AODV對AODV的拓展在于，當中間節點I有到目的節點D的路由時，I要同時進行如下2項操作。

1) I向S單播RREP以建立S→I的正向路由（I→S的反向路由在I收到RREQ報文時已建立）。

2) I向D單播RREP以刷新或建立I→D的路由，以確保該路由是有效的（因為 I→D的路由可能已過時，或者有可能是單向路由）。如果I→D的路由發生故障，則由I到D中檢測到故障的上游節點啟動本地修復。

O-AODV的路由維護過程與AODV相同[1]，只不過 O-AODV在進行路由本地修復時可以使用閑時逆尋機制和路由學習機制得到的局部路由進行快速修復。

3.2 閑時逆尋規則

以下規則中假設廣播R-RREQ分組的源空閑節點為L。

規則 1 網絡中的所有節點都維護一個記錄本節點空閑時間的變量τIdle，該變量初始值為零。如果節點發送或轉發過除Hello信息分組外的任何其他分組，則將τIdle清零。

規則2 當節點檢測到自己的τIdle大于空閑時間的閾值，即有τIdle＞Tth，則先偵聽信道，如果信道空閑，則向網絡上廣播一個R-RREQ分組；否則隨機退避一段時間后再偵聽信道，尋機廣播R-RREQ。

R-RREQ分組的格式與RREQ的格式相同[1]，只不過其類型值為5，即Type=5。源空閑節點L在廣播R-RREQ分組前，R-RREQ分組中有關域的設置如圖4所示。

圖4 R-RREQ分組的域值設置

規則3 收到R-RREQ分組的節點I做如下處理。

1) 根據 RREQ ID判斷自己是否收到過該R-RREQ，如果收到過則簡單丟棄，結束處理；否則轉處理2)。

2) 根據R-RREQ分組中的Destination IP檢查自己的路由表中是否有到節點L的路由，如有，轉處理3)；否則轉處理4)。

3) 設節點I收到的R-RREQ中節點L的序列號為SLNew，跳數HopCount為 HLNew；節點I路由表中維護的節點L的序列號為SLOld，到節點L的跳數為 HLOld。如果 SLNew＞SLOld；或者 SLNew＝SLOld，但HLNew+1＜HLOld，則使用 SLNew和 HLNew+1更新到節點L的路由，然后轉處理5)；否則丟棄該R-RREQ，結束處理。

4) 在路由表中添加一個到節點L的路由表項，該表項中L的序列號為SLNew，跳數為HLNew+1，然后轉處理5)。

5) 將 R-RREQ分組中的 HopCount設為HLNew+1，然后按規則4進行處理（轉發或結束轉發）。

規則4 節點I在轉發處理完的R-RREQ分組前先偵聽信道，當信道空閑時廣播該R-RREQ分組，否則結束轉發該R-RREQ分組，往節點L單播一個RREP分組，從而建立I到L的局部路由。

收到過該R-RREQ分組的節點越多，網絡中到節點L的局部路由就越多，當網絡中有節點要建立到L的路由時，這些局部路由就能發揮作用，從而提高路由發現的效率，減少路由的時延。

另外，利用規則3和規則4，能夠刷新網絡中已經存在的路由，也可以更新網絡中由于故障斷裂的路由。

3.3 路由學習規則

將網絡中節點的工作模式設置為雜收模式，節點就具有了路由學習的功能。

規則 5 節點只對監聽到的有效監聽分組進行處理。有效監聽分組包括RREP分組、數據分組以及下面定義的HREP分組。

節點從監聽到的RREP分組中可以提取出源節點IP和目的節點IP、目的節點序列號及到目的節點的跳數，但不能提取源節點序列號及到源節點的跳數；從數據分組的頭信息中可以提取源節點IP、源節點序列號和目的節點IP、目的節點序列號，但不能提取到源節點的跳數和到目的節點的跳數。為了獲取這些跳數信息，特定義了規則6和規則7。

規則 6 節點在信道空閑時向有效監聽分組的來源節點單播一個查詢分組 HREQ（HopCount request），HREQ只在2個相鄰節點間傳輸，不會擴散到網絡中去，從而將網絡開銷限制在很小的范圍內。HREQ分組的格式如下：

Source IP：發送查詢分組的節點的IP地址；

Source SN：發送查詢分組的節點的序列號；

Dest IP：產生有效監聽分組的節點的IP地址；

Node 1 IP：第一個待查詢節點的IP地址；

Node N IP：第N個待查詢節點的IP地址。

規則7 產生有效監聽分組的節點收到HREQ分組后，根據HREQ分組中的待查詢節點信息，從自己的路由表獲取這些節點的序列號和跳數信息，填充到HREP分組中，然后將HREP分組單播給發送查詢分組的節點。HREP分組的格式如下：

Source IP：產生有效監聽分組的節點的IP地址；

Source SN：產生有效監聽分組的節點的序列號；

Dest IP：發送查詢分組的節點的IP地址；

Node 1 IP：第一個要查詢節點的IP地址；

Node 1 SN：第一個要查詢節點的序列號；

Node 1 HC：本節點到第一個要查詢節點的跳數；

…

進行路由學習的節點通過與有效監聽分組的來源節點之間交互HREQ和HREP，就可以獲取通過監聽得到的完整路由信息，從而增加了網絡中路由的冗余信息。

3.4 路由快速修復規則

通過閑時逆尋和路由學習，網絡中會存在很多冗余的局部路由，為故障路由的快速修復提供了可能。當某條正在使用的路由發生故障時，由發現故障的節點廣播一個RREQ分組進行本地修復，則發送或轉發該RREQ分組的節點J可能會有很多鄰居節點都有到目的節點的局部路由，都可能會對節點J回復RREP分組，因此會在節點J處產生碰撞。為此，特定義如下規則。

規則8 節點I在收到節點J發送或轉發的進行本地修復的RREQ分組后，如果自己的路由表中存在到目的節點的路由，則先偵聽信道，當發現信道空閑時，就向節點J發送自己的RREP分組。如果到節點J的信道不空閑，則重復“退避→偵聽→發送”的過程。

啟動本地修復的節點可能會收到多個RREP，分別包含不同的到達目的節點的路由，但只選擇其中跳數最少的路由，從而完成故障路由的快速修復。

4 仿真與性能分析

4.1 仿真環境設置

為了驗證O-AODV路由協議的有效性，本文采用網絡仿真軟件 OPNET 11.5對其性能進行仿真分析，并與標準的 AODV協議[1]進行性能比較。

基本的仿真參數為：MAC協議類型為 IEEE 802.11 DCF；節點無線傳輸半徑為 250m；節點移動模型為Random Waypoint；信號傳播模型為自由空間傳播；帶寬為 2Mbit/s；業務類型為 CBR；分組長度為512byte；分組發送速率為2packet/s。

在基本仿真參數的基礎上，本文設置了如下 2種場景來驗證O-AODV路由協議的性能。

1) 節點最大運動速度變化的場景：仿真區域大小為1 500m×1 500m，節點數量為100個，節點間的最大連接數為30，節點的最大運動速度分別設置為 0m/s、5m/s、10m/s、15m/s、20m/s、25m/s、30m/s、35m/s、40m/s時進行仿真實驗。

2) 網絡規模變化的場景：節點的最大運動速度設置為 10m/s，同時在保證節點平均分布密度基本不變的前提下，擴大仿真區域，使得網絡規模逐漸加大。仿真區域大小和網絡中節點數量設置如表 1所示，節點間的最大連接數為30，并且將進行通信的節點選擇為網絡邊緣的節點。

表1 網絡規模變化場景下的參數設置

仿真時間均為600s，所有實驗結果均為3次模擬的平均值。

4.2 性能評估指標

本文采用端到端分組投遞率、數據分組端到端時延、平均路由修復時間和歸一化路由開銷 4個指標對AODV和O-AODV進行比較，前3個指標反映路由協議的可靠性和有效性，歸一化路由開銷則反映路由協議的效率。其中端到端分組投遞率指的是目的節點接收到的數據分組的個數與源節點發送的數據分組的個數之比值；端到端時延指的是目的節點的分組接收時間與源節點的相應分組發送時間的平均差值；歸一化路由開銷反映的是為傳輸數據分組而發送的路由控制分組的開銷；平均路由修復時間則指的是網絡中節點從發現路由斷裂并啟動本地路由修復過程開始，到路由修復成功時所花費的時間的平均值（如果網絡拓撲變化非常快，或者網絡由于通信業務量大而發生擁塞，則斷裂路由修復過程可能會由于超時而失敗。本文忽略了所有修復不成功的斷裂路由所花費的時間，只對成功修復的斷裂路由所花費時間進行平均計算）。

4.3 仿真結果分析

4.3.1 節點最大移動速度變化場景下的仿真結果分析

圖5(a)～圖5(d)分別給出了AODV和O-AODV 2種路由協議在不同的節點最大運動速度條件下分組投遞率、端到端時延、平均路由修復時間和歸一化路由開銷的仿真結果。

圖5 最大移動速度變化場景下的仿真結果

由圖5(a)可以看出，隨著節點運動速度的提高，網絡拓撲結構變化加劇，路由失效率增多，因此導致 2種路由協議的分組投遞率都在下降。由于O-AODV采用的路由學習和閑時逆尋機制加快了故障路由修復的速度，提高了路由修復的成功率，因此 O-AODV的分組投遞率在節點移動條件下高于AODV。

由圖 5(b)可知，2種路由協議的端到端時延都隨著節點運動速度的提高而增加，運動越快，時延越大。由于 O-AODV的閑時逆尋機制加快了路由發現的速度，路由學習機制則提高了斷裂路由修復的成功率和速度，因此 O-AODV的源節點路由發現時延和路徑中斷修復時延均小于 AODV，使得O-AODV的端到端時延小于AODV。網絡拓撲結構變化越快，O-AODV與AODV的端到端時延差別越大。

圖 5(c)對比了 2種協議對斷裂路由的修復速度。在節點處于靜止狀態時，網絡中的路由發生斷裂的可能性非常小，因此在最大速度為0時2種協議的平均路由修復時間接近于 0；隨著節點移動速度的增加，2種協議的平均路由修復時間也隨著增加。由于 O-AODV在網絡中產生很多冗余的局部路由，加快了斷裂路由的修復速度，因此O-AODV的平均路由修復時間大大低于AODV。

圖5(d)則說明，隨著節點運動速度的提高，用于成功傳輸數據分組的路由開銷越來越大。由于O-AODV在路由學習和閑時逆尋時都需要少量的路由開銷，因此在節點靜止或慢速運動時，O-AODV的歸一化路由開銷略大于AODV。當節點最大移動速度大于20m/s時，網絡拓撲結構變化加快，AODV路由修復次數和重路由次數逐漸增多，路由開銷越來越大；而O-AODV通過路由學習和閑時逆尋減少了重路由，路由開銷漸漸小于AODV。

4.3.2 網絡規模變化場景下的仿真結果分析

此場景下的仿真結果如圖6所示。

根據仿真結果可知，隨著網絡規模增大，從網絡一側的邊緣節點到另一側的邊緣節點之間的路由跳數在增加，使得一條路由由于節點運動而斷裂的可能性也加大了，因此AODV的分組投遞率在明顯下降；但網絡規模的擴大增加了網絡中的空閑節點，使得O-AODV產生的局部冗余路由也增多了，有利于加快路由發現和故障路由修復，因此網絡規模的擴大對O-AODV協議的分組投遞率影響不大。

圖6 網絡規模變化場景下的仿真結果

由于規模的擴大使得路由跳數增加了，使得數據傳輸時延和路由斷裂的可能性都加大了，因此 2種協議的端到端時延以及平均路由修復時間就相應地增加了。但 O-AODV協議產生的大量局部路由加快了路由發現和斷裂路由修復的速度，因此O-AODV的端到端時延和平均路由修復時間都小于AODV。

另外，網絡規模的擴大使得2種協議的路由開銷都明顯增加了，由于 O-AODV的大量局部路由有利于減少了重路由的次數，因此可以有效地減少路由開銷。

5 結束語

針對AODV路由協議在大規模和拓撲變化快的 MANET網絡中性能較差和效率低的特點，本文提出了節點閑時逆尋機制和鄰居節點路由監聽學習機制，結合這 2種機制進一步提出了優化的AODV路由協議——O-AODV。O-AODV協議改進了原AODV協議的路由發現和故障路由修復過程，增加了對穩定路由的刷新，從而減少了節點重路由的次數，加快了故障路由的修復速度，節省了網絡帶寬。仿真結果表明，在規模大和拓撲結構變化快的MANET網絡中，O-AODV協議中具有比AODV協議更好的性能和更高的路由發現與修復效率。

[1] PERKINS C, BELDING R E, DAS S. Ad-hoc On-demand Distance Vector ( AODV ) Routing[S]. IETF RFC 3561, 2003.

[2] MARINA M K, DAS S R. On-demand multipath distance vector routing for ad hoc networks[A]. Proceedings of IEEE International Conference on Network Protocols[C]. 2001. 14-23.

[3] AMMAAR Z, ALADDIN A. Analytical study to detect threshold number of efficient routes in multipath AODV extensions[A]. IEEE Cairo Conference(ICEEC07)[C]. 2007.95-100.

[4] HIGAKI H, UMESHIMA S. Multiple-route ad hoc on-demand distance vector (MRAODV) routing protocol[A]. Proceedings of the 18th International Parallel and Distributed Processing Symposium, IEEE[C].2004. 237.

[5] ZAHARY A, AYESH A. On-demand multiple route maintenance in AODV extensions (ORMAD)[A]. International Conference on Computer Engineering & Systems[C]. 2008. 225-230.

[6] SUJATA V. M, SUJATA T. Enhanced ad-hoc on demand multipath distance vector routing protocol (EAOMDV)[J]. International Journal of Computer Science and Information Security, 2010, 7(3):166-170.

[7] GWALANI S, ELIZABETH M, ROYER B. AODV-PA: AODV with path accumulation[A]. Proceedings of IEEE International Conference on Communication[C]. 2003.527-531.

[8] JOHNSON D B, MALTZ D A. Dynamic Source Routing in Ad Hoc Wireless Networks[M]. Kluwer Academic Publishers, 1996.

[9] ZHAO Q, ZHU H B. An optimized AODV protocol in mobile ad hoc network[A]. The 4th International Conference on Wireless Communications, Networking and Mobile Computing[C]. 2008. 1-4.

[10] JAGPREET S, PARAMJEET S, SHAVETA R. Enhanced local repair AODV (ELRAODV)[A]. International Conference on Advances in Computing, Control, and Telecommunication Technologies[C]. 2009.787-791.

[11] BEST P, GUNDETI S, PENDSE R. Self-learning ad-hoc routing protocol[A]. Vehicular Technology Conference, VTC 2003-Fall 2003 IEEE 58th[C]. 2003. 2824-2828.