AODV協議路由修復算法改進研究

蔡保國王耀國賈軍

（武漢船舶通信研究所武漢430205）

AODV協議路由修復算法改進研究

蔡保國王耀國賈軍

（武漢船舶通信研究所武漢430205）

論文對AODV協議的路由修復算法進行了改進研究。通過修改路由響應包（RREP）和數據包的監聽機制，節點不僅建立了到目的節點的前向路由，也建立了到源節點的反向路由，減少了尋路帶來的開銷。除此之外，論文還對中斷路由的修復策略進行了調整，以進一步提高路由修復的成功率。基于QualNet4.5的仿真結果表明，論文提出的路由修復改進算法在未明顯增加數據包的平均端到端延時和控制開銷的情況下，進一步提高了AODV協議的分組投遞率。

路由修復算法；監聽機制；中斷路由；平均端到端延時；控制開銷；分組投遞率

Class NumberTP393

1 引言

AODV協議［1］是一種典型的按需路由協議，具有效率高、開銷低的優點，能夠較好地適應無線自組織網絡［2］動態、自組織、多跳的特點。當某條活動路由發生鏈路中斷時，AODV協議采用本地修復（AODV-LR）算法［3～5］。但是，洪泛式的路由修復算法不僅增加了控制開銷和端到端延時，也加劇了網絡擁塞和碰撞，可能導致更多的鏈路中斷發生。為此，研究人員提出了各種改進的路由修復算法。PATCH［6］將路由修復的范圍限定在兩跳范圍內，通過搜索中斷節點的下一跳和下兩跳節點來修復中斷路由，以較低的開銷實現中斷路由的快速修復。PATCH認為鏈路中斷時下一跳節點位于當前節點兩跳范圍內的概率較大，但若不能成功修復路由將會導致更多的丟包。AODV-ABR和AODV-ABL［7］借鑒了AODV-BR［8］通過監聽建立替代路由的思想，只不過節點除了監聽附近的RREP包傳輸，還監聽附近的數據包傳輸，這提高了替代路由建立的概率。鏈路中斷時，中斷節點不是通過將數據包進行廣播而是通過詢問鄰居節點來修復中斷路由。二者的區別在于：當發生鏈路中斷時，AODV-ABR始終依賴鄰居節點的替代路由進行路由修復，而AODV-ABL則根據節點位置決定采取何種路由修復策略：AODV-LR或AODV-ABR。然而，與AODV-BR一樣，它們都只建立了到RREP包（或數據包）中目的地址的前向替代路由，而沒有建立到RREP包（或數據包）中源地址的反向替代路由。

為了提高AODV協議的路由修復效率，本文提出了一種不同的監聽機制和中斷路由修復策略，并通過仿真進行了驗證。

2 有關路由修復算法

評價路由修復算法優劣的指標包括路由修復效率和路由修復代價。前者是指路由修復的成功率，后者是指路由修復所需的額外開銷，它們與路由修復概率及路由搜索半徑有關。路由修復概率越高，則路由修復效率越高；路由搜索半徑越大，則路由修復代價越高，同時路由修復效率也越高。

在AODV-LR算法中，是否進行本地路由修復由中斷節點的位置決定。當中斷節點到目的節點的跳數不大于MAX_REPAIR_TTL時，其將發起洪泛式路由修復過程；否則，其將向源節點發送RERR消息報告路由中斷。假設活動路由上各節點發生鏈路中斷的概率是相等的，記源節點到目的節點的跳數為n，則AODV-LR算法進行路由修復的概率PAODV-LR滿足

AODV-LR算法進行路由搜索的半徑R可表示為

其中#hops表示中斷節點到源節點的路由跳數。

在PATCH算法中，中斷節點進行路由修復的概率為100%，其路由搜索半徑為2跳（鄰居節點及其下一跳）。

在AODV-ABR和AODV-ABL算法中，中斷節點進行路由修復的概率也為100%，但路由搜索范圍不盡相同。其中AODV-ABR算法的路由搜索半徑始終為1跳，而AODV-ABL算法的路由搜索半徑分為兩種情況：若中斷節點到目的節點的跳數不超過MAX_REPAIR_TTL，路由搜索半徑與AODV-LR算法相同，如式（2）所示；否則，路由搜索半徑與AODV-ABR算法相同，等于1跳（鄰居節點）。

表1 幾種路由修復算法比較

根據以上分析，可將上述幾種路由修復算法進行簡單比較，如表1所示。

3 改進的AODV路由修復算法

3.1 監聽機制

如前所述，AODV-ABR和AODV-ABL算法沒有建立到RREP包（或數據包）源節點的反向替代路由。除此之外，與AODV-BR類似，AODV-ABR和AODV-ABL將路由分為兩類：主路由與替代路由，因此每個節點都需要維護兩張路由表：主路由表與替代路由表，兩種路由的處理策略可能不盡相同。在我們提出的算法中，節點通過監聽不僅可以建立到RREP包（或數據包）源節點的反向路由（如果有必要的話），而且所有節點都只需維護一張路由表，這與AODV協議一致。

節點監聽到RREP包時處理如下：

1）節點首先查詢是否有到該RREP包中目的地址的路由（RREP包中的目的地址是產生RREP包的源地址），若無路由或路由已過期，或路由的目的序列號小于RREP包中的目的序列號，或目的序列號相等但路由跳數大于RREP包中跳數加1，則建立或更新路由，否則轉2）；

2）路由保持不變

具體過程如圖1所示。節點B通過監聽節點F轉發的RREP，建立了到RREP中目的節點D的新路由。

圖1 RREP的監聽處理

節點通過監聽數據包，不僅可以建立或更新到數據包目的節點的路由，還可以建立或更新到數據包源節點的路由，路由建立或更新的規則與處理RREP完全相同。不過，要想通過監聽鄰近的數據包來建立或更新路由需要在數據包的頭部記錄到源節點和目的節點的跳數信息。節點監聽數據包的具體過程如圖2所示。節點C通過監聽節點F上的數據包傳輸，建立了到數據包源節點S和目的節點D的路由。另外，圖2還示意了通過監聽建立的路由被刪除的情形。節點B之前通過監聽節點F轉發的RREP建立了到節點D的路由（見圖1），隨著節點的移動和網絡拓撲的變化，節點B逐漸移出了節點F的傳輸覆蓋范圍。若在一定時間內該路由未得到更新（例如節點B在該時間內始終未能從節點F接收或監聽到任何消息），該路由將被認為已過期并予以刪除。

圖2 數據包的監聽處理

3.2 中斷路由修復策略

當數據傳輸過程中發生鏈路中斷時，中斷節點將發起路由修復過程。與文獻［7］類似，路由修復也采用握手方式進行，但具體方法與AODV-LR、AODV-ABR以及AODV-ABL算法有所不同。具體操作過程如下：

1）不論中斷節點位置如何，其都將廣播一個一跳的RREQ；

2）若其某鄰居正確收到該RREQ且有到該中斷路由目的地址的有效路由，則用RREP進行回復；

3）若中斷節點在一定時間內成功接收到一個或多個RREP，則路由修復成功，接下來的處理與AODV-LR相同；否則，按照AODV-LR算法進行修復；

4）若中斷節點在一段時間內成功收到一個或多個RREP，則路由修復成功，接下來的處理與AODV-LR相同；否則，路由修復失敗，中斷節點沿反向路由方向發送RERR。

4 仿真與評估

為了檢驗路由修復算法性能，采用QualNet4.5［9］進行仿真。仿真場景大小設為1500m×1500m，50個節點隨機分布于其中，仿真結果取20幅不同拓撲圖運行結果的平均值。仿真時間為300s，信道帶寬為2Mbps，路徑損耗模型為Two-Ray Ground Model，節點移動模型為Random Waypoint Model，節點最大移動速率為20m/s，節點最大暫停時間為300s，物理層采用802.11b模型，MAC層采用802.11 DCF協議，隨機選擇若干對節點建立512字節的CBR/UDP業務，CBR包生成速率為4包/秒，節點運行AODV協議，路由修復算法分別采用AODV-LR、AODV-ABR、AODV-ABL以及本文提出的路由修復算法（記為AODV-IRR）。

4.1 分組投遞率

分組投遞率是指所有目的節點總共接收到的數據包數目與所有源節點總共發送的數據包數目之比。我們分別仿真了在四種不同路由修復算法下分組投遞率隨節點暫停時間變化的性能曲線，如圖3所示。我們發現，當暫停時間增加時，分組投遞率呈下降趨勢，這一結果與文獻［8］中的仿真結果相異。這是由于在我們設定仿真場景中，較少的暫停時間或者說更多的移動性反而提高了Ad Hoc網絡的吞吐量，這正好與文獻［10］的結論一致。

圖3 分組投遞率

4.2 端到端延時

端到端延時反映了數據包從源節點到目的節點所經歷的平均時間（只考慮成功到達目的節點的數據包），它包含了數據包在各跳節點中的排隊時延、傳輸時延、傳播時延以及可能的路由重建時間（例如路由修復時間）。平均端到端延時隨暫停時間變化的曲線如圖4所示。

圖4 端到端延時

4.3 控制開銷

控制開銷是指每成功發送一個數據包平均需要發送的控制包數目。如圖5所示，控制開銷隨暫停時間的增加而增加，這是由于在節點移動狀態下路由修復方案能夠自適應地優化路由，減少路由中斷的發生。在相同的暫停時間下，由于AODVABR將路由修復的范圍限定在一跳范圍，因而其控制開銷最低。當中斷節點和目的節點之間的距離大于MAX_REPAIR_TTL跳時，AODV-ABL和AODV-IRR仍將修復中斷路由，因此其控制開銷比AODV-LR高。與AODV-ABL相比，AODV-IRR可能有更多的修復嘗試，因此其控制開銷在四種修復方案中最高。

圖5 控制開銷

5 結語

本文提出了一種改進的AODV路由修復算法（AODV-IRR），其能更有效地適應網絡拓撲的變化。通過監聽鄰近的RREP和數據包傳輸，AODV-IRR不僅能夠創建或更新到目的節點的前向路由，也能創建或更新到源節點的反向路由。而且，AODV-IRR并不需要維持備用路由表，這也在一定程度上減少了協議的開銷和復雜度。最后的仿真結果表明，與AODV-LR、AODV-ABR以及AODV-ABL相比，AODV-IRR以稍高的平均端到端延時和控制開銷為代價，獲得了更高的數據包投遞率性能。

［1］Perkins C，Royer E，Das S.Ad hoc On-demand Distance Vector（AODV）Routing［S］.IETF RFC 3561，2003.

［2］Gupta P，Saxena P，Ramani A K，et al.Optimized use of battery power in wireless Ad hoc networks［C］//Proceedings of IEEE International Conference on Advanced Communication Technology，2010：1093-1097.

［3］Yu C W，Wu T-K，Cheng R H.A low overhead dynamic route repairing mechanism for mobile ad hoc networks［J］. Computer Communications，2007，30（5）：1152-1163.

［4］薛強，呂光宏.AODV的本地修復改進機制［J］.計算機工程，2008，34（19）：121-126.

XUE Qiang，LV Guanghong.Improved local recovery mechanism in AODV［J］.Computer Engineering，2008，34（19）：121-126.

［5］丁緒星，吳青，謝方方.AODV路由協議的本地修復算法［J］.計算機工程，2010，36（6）：126-130.

DING Xuxing，WU Qing，XIE Fangfang.Local repair algorithm for AODV routing protocol［J］.Computer Engineering，2010，36（6）：126-130.

［6］Liu G P，Wong K J，Lee B S，et al.PATCH：A novel local recovery mechanism for mobile ad-hoc networks［C］//Proceedings of IEEE Vehicular Technology Conference，2003：2995-2999.

［7］Lee S J，Gerla M.AODV-BR：Backup routing in ad hoc networks［C］//Proceedings of IEEE WCNC 2000，2000：1311-1316.

［8］Lai W K，Hsiao S Y，Lin Y C.Adaptive backup routing for ad-hoc networks［J］.Computer Communications，2007，30（2）：453-464.

［9］Scalable Network Technologies，Inc.QualNet 4.5 Programmer's Guide［EB/OL］.http：//www.qualnet.com，2008.

［10］Grossglauser M，Tse D.Mobility increase the capacity of Ad hoc wireless networks［J］.IEEE/ACM Transactions on Networking，2002，10（4）：477-486.

Research on Improved Route Repair Algorithm of AODV Protocol

CAI BaoguoWANG YaoguoJIA Jun
（Wuhan Maritime Communication Research Institute，Wuhan430205）

An improved route repair algorithm of AODV protocol is researched in this paper.By means of the modifications to overhearing mechanism of Route Reply（RREP）packets and data packets，a node can create forward routes to destination nodes and backward routes to source nodes，which decreases the costs caused by routing.Besides，the repair measures of broken routes are adjusted to improve the success rate of route repair in this paper.The simulation results based on QualNet 4.5 show that the improved route repair algorithm proposed in this paper can efficiently improve packet delivery ratio of AODV protocol and clearly decrease its control overheads in case of not obviously increasing average end-to-end delay of data packets.

route repair algorithm，overhearing mechanisms，broken routes，average end-to-end delay，control overheads，packet delivery ratio

TP393

10.3969/j.issn.1672-9722.2017.06.032

2016年12月8日，

2017年1月22日

蔡保國，男，博士，工程師，研究方向：無線通信網絡總體設計。王耀國，男，博士，工程師，研究方向：無線通信網絡協議及大數據應用。賈軍，男，碩士，工程師，研究方向：無線通信設備硬件設計。