ＡＯＤＶ的本地修復算法

摘要：提出了一種新的路由本地修復算法，將修復盡量限制在斷鏈的局部范圍內，減少了修復時間和降低路由維護的開銷， 且不用考慮失效鏈路在整個路由上的相對位置，均可對其進行修復，提高了處理失效鏈路的能力，有利于提高網絡的可擴展性。仿真表明，這種新的路由本地修復算法明顯地提高了網絡多方面的性能。

關鍵詞：自組織分組無線網絡; 路由協議; 自組織分組無線網絡按需距離矢量路由; 本地修復; 下兩跳

中圖分類號：TP311文獻標志碼：A

文章編號：1001—3695(2007)03—0231—03

移動自組織網（Mobile Ad hoc Networks，MANET）是由一組帶有無線收發裝置的移動節點組成的無需基站支持的多跳的臨時性自治系統。MANET主要用于滿足應急通信和軍用移動通信需求，如戰場上部隊快速部署和推進、地震或水災后的營救等。由于節點的無線通信覆蓋范圍有限，兩個無法直接通信的移動節點需要借助于其他節點進行分組轉發，即經過多跳，這是MANET與其他移動網絡的最根本區別。

由于節點的隨機移動，MANET的拓撲隨時都在發生變化，無中心的動態變化的拓撲給設計自適應的分布式路由協議帶來了很大的困難。路由技術是實現Ad hoc網絡的一項關鍵技術，MANET的路由協議可分為表驅動和按需兩大類。表驅動路由協議[1]又被稱為主動式路由協議，網絡中的節點通過周期性的交互路由信息更新到其他所有節點的路由，而不管是否需要該路由進行通信。典型的表驅動路由協議有OLSR(Optimized Link State Routing Protocol)[1]、WRP(Wireless Routing Protocol)[2］和TBRPF(Topology Dissemination Based on Reverse-Path Forwarding)[3]。按需路由協議 [4]又稱為反應式路由協議，在節點需要進行通信時才建立路由，且僅在通信過程中才維護路由。典型的反應式路由協議有AODV(Ad hoc On-demand Distance Vector Routing)[5]、DSR(Dynamic Source Routing)[6]和TORA(Temporally-Ordered Routing Algorithms)[7]。反應式路由協議更能適應Ad hoc網絡的動態拓撲、帶寬受限和能源約束等特點，通常分為路由發現和路由維護兩個階段。目前，對于Ad hoc網絡路由協議的研究正逐步深入，但主要集中于路由發現階段，而關于路由維護的研究卻較少。C.Gui等人[8]提出了一種自修復和優化路由算法(SHORT)，在SHORT算法中，路由的所有相鄰節點均在監視這條路由，當有更好的子路由時就優化它。然而，路由優化會影響網絡的性能和能量消耗，當負荷較重時影響更加嚴重。Genping Liu等人[9]提出了一種路由本地修復算法（PATCH），用較少的開銷實現了對鏈路的快速修復，但是這種算法只能用于源路由協議。本文將基于AODV提出一種改進的路由本地修復算法，將修復盡量限制在失效鏈路的附近，從而縮短了修復的時間，減少了控制的開銷，而且其控制開銷與時延均與網絡的規模無關。

1AODV協議及其本地修復算法

AODV是最有代表性的按需路由協議之一，它有三種類型的控制分組：路由請求（RREQ）、路由應答（RREP）和路由錯誤（RERR）。當源節點需要發送數據而又沒有到達目的節點的有效路由時，啟動路由發現過程，在收到路由應答后則開始向對應目的節點發送數據。在數據傳輸過程中，如果有效路由發生鏈路中斷，斷鏈的上游節點可能會選擇在本地修復鏈路。為了修復鏈路，節點增加關于目的節點的序列號，然后廣播關于目的節點的RREQ。發起修復的節點等待路由發現周期來獲得響應的RREP，在本地修復過程中數據分組應該進行緩存。如果路由發現周期結束仍然沒有收到關于目的節點的RREP，則發送關于該目的的RERR；另一方面，如果節點在路由發現期間收到一個或多個RREP，它就更新關于該目的的路由表項。

在AODV中，序列號的管理對于避免路由環路是非常關鍵的。在修復鏈路時，發起修復的節點增加關于目的節點的序列號，然后廣播關于目的的RREQ。多跳路由的失效通常是由于節點的相對運動或故障導致的單條和相鄰的兩條鏈路斷裂而引起的，可以假設兩條不相鄰的鏈路是相互獨立的，也就是說，當單條和相鄰的兩條鏈路斷裂時，路徑上的其余部分仍然是有效的。路徑上靠近目的的節點可能仍有到達目的的有效路由，但是這些節點的路由表項中保存的目的序列號卻過時了，從而不能對收到的RREQ進行應答。通常只有目的節點才能作出應答，所以RREQ的廣播范圍必須覆蓋目的節點。這種路由本地修復算法仍需要大范圍的泛洪，這會導致大的控制開銷和長的時延。在現有算法中，只有當節點比較靠近目的時才發起路由修復。

2AODV本地修復的改進

2.1改進的本地修復算法

在原始的AODV算法中，RREQ和RREP只保存下一跳和前一跳節點的IP地址，節點中的路由表項也只有下一跳節點地址。如圖1所示，當節點A發送數據分組（當節點A是源節點時）或者轉發數據分組（當節點A是中間節點時）到達目的節點D時，節點A檢查路由表。如果沒有找到目的為節點D的路由表項或者路由表項已經過期，則發送目的為節點D的RREQ消息。如果到節點D的路由表項的下一跳節點B失效或者節點B移出節點A的通信范圍時，節點A到節點D的路徑失效。若節點A到節點D的距離比較近，則發起本地修復，廣播目的為節點D的RREQ消息，RREQ消息途經節點E，F最后到達節點D，然后由節點D發送RREP消息，沿反向路由傳送到節點A。這樣，就重新建立了從節點A途經節點E，F到節點D的路由。

在改進的修復算法中，用斷鏈附近的節點替換失效的節點，而路徑上的其他節點可以保留。RREQ和RREP分組還保存下兩跳和前兩跳節點的IP地址，節點的路由表項中也增加了下兩跳節點地址。下兩跳節點是指在該路徑上的下一跳節點的下一跳；前兩跳節點則是在該路徑上的前一跳節點的前一跳。如圖1中的節點C是節點A的下兩跳節點，而節點A是節點C的前兩跳節點。

如圖2所示，節點A發送數據分組或者轉發數據分組到節點D時，節點A檢查路由表，如果沒有找到目的為節點D的路由表項或者路由表項已經過期，則發送目的為節點D的RREQ消息。當到節點D的路由表項的下一跳節點B失效或者節點B運動出節點A的通信范圍時，節點A到節點D的路徑失效，由節點A進行本地修復。節點A并不直接發送目的為D的RREQ消息，而是查找節點A的目的為D的路由表項中的下兩跳節點C，如果路由表項中下兩跳節點C地址存在，則節點A發送目的為節點C的路由修復請求分組Repair_RREQ。當Repair_RREQ經過節點E到達節點C，并且節點C到節點D的路由有效，則從節點C發送路由修復應答分組Repair_RREP，經反向路由通過節點D將Repair_RREP消息發送回節點A。這樣，就重新建立了一條從節點A途經節點E，C到節點D的路由。

如果路由表項中節點A的下一跳節點B和下兩跳節點C同時失效，則節點A發送目的為節點D的RREQ消息，下面的步驟就與原始的AODV本地修復相同了。

從上面的論述可以看出，由于節點C通常比節點D距離節點A更近，所以當節點A只有下一跳節點失效時，修復的范圍將限制在A與C之間，所以網絡上傳播的控制分組數量要少一些，尋路時間也短一些。

圖1原始的AODV算法圖2改進的AODV算法

2.2路由表的改動

路由表中目的節點的IP地址域保存所要到達的目的節點的IP地址，每個表項都具有不同的目的節點地址，以此作為區別和查找網絡路由的關鍵字。目的節點的序列號保存該表項的當前目的序列號，只有在整個移動自組織網中沒有對應的比其更大的目的序列號時才表示這條路由信息是最新的。下一跳節點IP地址域保存到達目的節點路徑上的下一跳節點的地址，作為轉發數據時生成IP分組的報頭信息。改進算法中的路由表項增加了下兩跳節點IP地址域，保存到達目的節點路徑上的下兩跳節點的地址。當下一跳鏈路無效時，若下兩跳節點有效，則發送本地修復的路由請求分組，目的地址就是下兩跳節點的IP地址。

2.3RREQ、RREP、RERR分組的改動以及新增分組

為了使路由本地修復時能在路由表中獲得下兩跳節點的地址，RREQ、RREP、RERR分組中分別添加了前兩跳節點的IP地址字段，其他字段均無變動。另外，為了進行路由的本地修復，新增加了本地修復的路由請求分組Repair_RREQ、路由應答分組Repair_RREP、NOTICE分組。節點進行本地修復時，路由請求是以下兩跳節點（圖2中的節點C）為目的節點，但還應該攜帶修復的路由的真實目的（圖2中的節點D）的信息。于是，Repair_RREQ分組在RREQ分組基礎上添加了以下字段：真實目的節點的IP地址和序列號；Repair_RREP分組在RREP分組基礎上添加了以下字段：真實目的節點的IP地址和序列號，下兩跳節點到達真實目的節點的跳數。

本地修復時，發起修復的節點（圖2中的節點A）先將到節點D的路由設為無效，并且將D的目的序列號加一，再廣播Repair_RREQ分組。但是由于Repair_RREQ不能到達節點D，從而使得A到C之間的節點的真實目的節點的序列號更新了，但C與D之間的節點卻沒有得到更新，在以后的路由中，將可能形成環路，或者D發出的路由分組將由于序列號低而無法更新其他節點。為此，協議增加了NOTICE分組。當節點C收到Repair_RREQ分組時，產生一個NOTICE分組并存入D的新序列號，并且將這個分組沿著C到D的路徑發送，路徑上的節點收到此分組后則更新自己到D的新序列號，最后到達D，使得D也能更新自己的序列號，從而避免了以上問題。由于NOTICE分組很小，故增加的協議開銷很少。NOTICE分組格式如表1所示。

表1NOTICE分組格式

type(8 bits)dest(32 bits)destSeq(8 bits)nextHop(32 bits)

其中， type為分組類型；dest為需要通知的目的節點；destSeq為需要通知的目的節點的新序列號；nextHop為下一跳，接收方用于判斷該分組是否正確發送。

2.4改進的本地修復算法的工作流程

由于在RREQ、RREP中添加了前兩跳節點字段，每個RREQ、RREP發送之前都要將前一跳地址放入分組的前兩跳節點字段中。這樣下一個節點將知道它的前兩跳節點，由此更新自己到源（或者到目的）的反向路由（或正向路由）。在RREQ的廣播過程中，節點在收到有效的RREQ之后，要將RREQ中的前兩跳節點字段的值更新到該節點到源節點的反向路由的下兩跳字段；同樣地，當節點收到RREP之后，要將RREP中的前兩跳節點字段更新到該節點到達目的節點的正向路由的下兩跳字段。由此則在路由表中增加了下兩跳。

增加下兩跳的作用主要是為了進行路由的本地修復。在改進的AODV協議中，如圖2所示，當B失效時，A先將到D的路由設為無效，檢查目的為D的路由表項，若下兩跳C存在且有效，則將其目的序列號加一，以C為目的節點廣播Repair_RREQ分組，其TTL值可以設為2（或3）。除C之外的節點都不對Repair_RREQ進行應答。當節點C收到Repair_RREQ分組時，產生一個Repair_RREP分組，同時還產生一個NOTICE分組并存入D的新序列號，并且將這個分組沿著C到D的路徑傳送。此路徑上的節點收到NOTICE分組時，則更新其路由表項中D的新序列號，最后到達D，D也更新自己的序列號。當節點A收到Repair_RREP時，則更新其到D的路由。若下兩跳不存在，或者存在但無效，則節點A向D發送RREQ，從而回到原始AODV協議的本地修復過程。

3仿真及分析

3.1仿真環境和性能評估參數

本仿真實驗是為了比較改進的AODV路由協議和原始的AODV路由協議的性能，采用網絡仿真軟件OPNET 8.1。120個節點在1 500 m×2 000 m的區域內隨機移動，采用Random Way-Point 移動模型[10]。節點在所規定的網絡范圍內，隨機選擇一個目的位置，然后以速度V向目的位置運動，到達該點后，暫停一個等待時間（T_pause， 設為30 s），再向下一個目的位置移動，如此反復。為了考查網絡在不同的拓撲變化情形下協議的性能，仿真取了四個場景，速度V分別設為5、10、15、20 m/s。選擇30個節點產生數據流，流持續、空閑的時間分別服從均值為30 s，5 s的指數分布，每秒產生八個數據分組，每個數據分組為128 Bytes，向隨機選擇的一個目的發送。節點傳輸距離為300 m，MAC層使用802.11協議，仿真時間為600 s。收集的仿真參數[11]包括數據成功接收率、平均端到端時延以及協議開銷，其中協議開銷分別按字節數和分組數計算。協議開銷是指網絡中傳輸的控制分組的字節（分組）數與所有分組的字節（分組）數的比值。

3.2仿真結果及性能分析

圖3給出了在不同節點運動速度下的數據成功接收率。很明顯，在所有的移動場景下，改進后的AODV協議性能均優于原始的協議。另外，隨著速度的增加，改進的協議性能比原始協議下降得慢一些，這顯示它能更好地適應拓撲快速多變的環境。因為改進的修復算法將操作限制在斷鏈的局部范圍內，從而不用考慮斷鏈在整條路徑上的相對位置，均可進行修復，提高了處理失效鏈路的能力，故因沒有找到路由而丟棄的數據分組和緩存內的數據分組更少，從而明顯地提高了數據成功接收率。

圖4給出了協議改進前后的平均端到端時延，可以看出，協議改進之后，平均端到端時延也下降了。由分析可知，由于改進的路由修復算法限制了修復的范圍，修復所需的時間更短，緩存的數據就能更快地發送出去，從而降低了時延；另外，正常接收到的分組時延很小（毫秒級），而由于改進后的協議成功接收的數據分組更多，這些多接收到的分組是在路由修復之后收到的，時延比較大，對平均值的影響大，從而實際的性能改善其實更好一些。

圖3數據成功接收率圖4平均端到端時延

圖5，圖6顯示了改進前后協議的控制開銷。由于改進的協議增加了控制分組的長度和新的分組，但通過限制修復的范圍卻可以減少控制分組的數量，這兩個因素都會影響控制開銷。當節點移動較慢時（5 m/s）， 斷鏈較少發生，路由很少需要修復，但因為控制分組字段的增加使得改進后的協議字節開銷增加了，不過此時的分組開銷卻降低了，即減少了控制分組的數量。隨著節點運動速度的增加，鏈路更加頻繁地斷開，修復的次數相應增加了，改進的修復算法就更能發揮其優越性。

圖5協議比特開銷圖6協議分組開銷

4結束語

本文對AODV路由協議的本地修復算法做了很大的改動，提出了新的路由本地修復算法。在原始路由協議中，本地修復的意義就在于將修復限定在出錯的節點和目的節點之間，而盡量不涉及源節點，且只有當失效鏈路離目的節點較近時才對路由進行修復，否則通知源節點重新路由。

而改進之后的算法則完全詮釋了局部的意義，發起修復的節點向其下兩跳節點發起修復過程，把修復限定在了失效鏈路的附近，范圍更小，處理時間更短，從而也無需考慮失效鏈路在整個路由上的相對位置，均可進行修復，提高了處理失效鏈路的能力。此外，改進的本地修復算法的控制開銷和時延都與網絡的規模無關。當網絡規模越大，路由的跳數越多，改進的路由本地修復算法就越有其優越性，從而有利于提高移動Ad hoc網的可擴展性[12]。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。