AODV協議局部修復機制改進

韓林呈，陳喜春

?

AODV協議局部修復機制改進

韓林呈，陳喜春

AODV協議是Ad Hoc網絡中典型的按需路由協議在詳細分析AODV局部修復機制的基礎上，提出了一種針對局部修復引發競爭問題的改進方法，即當多個斷路發生時，分配每個修復進程優先級以避免競爭問題。仿真表明，該機制能夠有效避免競爭并提升網絡性能。

AODV；Ad Hoc；局部修復；競爭問題；優先級

0 引言

Ad Hoc[1]網絡節點的快速移動及電量限制等原因可能會導致通訊鏈路中斷。因此，在Ad Hoc網中如何進行有效地路由維護是國內外學者爭相研究的重點。DSR[2]和AODV[3]是典型的按需路由協議，可以建立從源節點到目標節點的最短路由。當網絡拓撲結構快速變化需頻繁重建路由時，局部修復相對于全局修復能夠以更短的時間和更小的代價達到修復損壞路由的目的。因此很多路由協議例如AODV和ABR[4]等都采用了局部修復[3,4,5]機制。但是，通常局部修復對于源節點是不可知的，自發和分散的局部修復很可能會導致競爭問題并降低網絡性能。因此，本文在詳細分析原協議的運行機制的基礎上，深入闡述其斷路的局部修復所引發的問題，并提出一種新的改進算法。文中最后通過仿真數據，直觀說明改進后協議在路由修復開銷、數據包投遞率和端到端平均時延上的優越性。

1 AODV的局部修復機制

AODV路由協議采用Hello消息機制進行鏈路連通性管理，對有效路由進行維護。具有有效路由的節點每隔固定時間T便廣播一個特殊的RREP包，即Hello消息。鄰節點收到Hello消息，可對各自的相應路由進行建立或更新。若節點在連續的幾個T的時間內未收到有效路由中相鄰節點的Hello消息便認為該鏈路中斷，并發送RERR至相關路由的節點。當發現鏈路斷開時，可以由源節點重新發出RREQ查找路由。但是，目前多用局部修復，即斷開處的節點試圖修復斷開的活躍路由，如果一次修復嘗試失敗則由源節點重新發出RREQ查找路由。當發現鏈路斷開后，如果斷鏈處的上游節點與目的節點之間的距離大于MAX-REPAIR-TTL跳[6,7]，則上游節點發送一個RERR(Route Error)到源節點以啟動全局修復；否則該節點啟用生存時間比較小的RREQ廣播來局部修復路由。如表1所示：

表1 RREQ格式

局部修復與全局修復的RREQ格式相同。Originator代表泛洪發送RREQ消息的節點。

J, R: reserved for multicast

G: Gratuitous RREP flag

D: Destination only flag (indicates only the destination may respond to this RREQ)

U: Unknown sequence number

2 局部修復引發的競爭問題

由于局部修復通常是自發的并且是分散的，這就很難把握修復時其他鏈路的狀況。如果路由協議既有全局修復機制又有局部修復機制(例如AODV)，則在全局修復和局部修復之間也可能會產生沖突。這種競爭會對路由修復產生負面影響。產生這種競爭的時間條件如圖1所示：

圖1 局部修復引發競爭的時間條件

當某些節點移動較快時，產生的斷路故障可能會觸發多個修復進程。若這時有兩個局部修復發生在同一條路由線路，臨近目標節點的某些節點可能會收到兩個RREQ消息，競爭沖突也就產生了。這種沖突通常會導致局部修復失敗并產生冗余的無效路由。如圖2所示：

圖2 RREQ（M1）被丟棄過程

S為源節點D為目的節點，S到D之間有一條線路S-M1-M2-M3-M4-D，數據由此路由線路傳送。當M1-M2和M3-M4中斷時，M1節點發起一個局部修復，泛洪廣播RREQ(記為RREQ(M1))，幾乎在同一時刻，M3節點同樣發起局部修復，泛洪廣播RREQ(記為RREQ(M3))。RREQ(M3)首先到達節點N3，N3在路由表中增加一條以源節點S為目標的反向路由字段，其中M3為此條路由的下一條節點。然后，N3繼續泛洪廣播RREQ(M3)。很快，RREQ(M1)消息也到達N3節點。然而，由于此時N3存有的以S為目標的路由字段的SrcSeqNo和RREQ(M1)的相等，并且RREQ(M1)的Hop Count(由M1到S的跳數)不小于此條路由字段的Hop Count，因此RREQ(M1)被忽視并且丟棄。

這種情況導致的后果如圖3所示：

圖3 RREP無法傳送到源節點

節點D收到RREQ（M3）后返回RREP消息，當RREP依次由N5、N4、N3、M3傳送到M2時，因為由源節點S到M2的路由線路很可能尚未修復，因此使得此次局部修復失敗。在稍后的時間，M1將會注意到它的局部修復失敗并通知源節點S。最終，S會以較大的TTL值泛洪發送RREQ消息啟動全局修復。這樣不僅增加了延時，而且，在全局修復完成之前，數據傳輸停止，一條冗余的路由線路M3-N3-N4-N5-D會一直被維護。

3 優化策略

競爭問題會使得離源節點最近的損壞鏈路無法修復。因此，當競爭沖突發生時，賦予離源節點最近的（即離目標節點最遠）損壞鏈路最高局部修復優先級，其他局部修復賦予較低優先級，或者直接丟棄。

每一個節點要有以下功能：

有一個Repair Control Table(RC Table)，記錄修復進程的歷史管理信息。

競爭偵測功能

競爭解決功能

在局部修復消息中增加以下信息：

指定源節點和目標節點

指定新路由線路

指定路由中損壞鏈路位置

RREQ消息格式如表2所示：

表2 改進AODV RREQ消息格式

陰影部分是與AODV不相同的部分。OD hop count是由偵測到鏈路損壞的節點(即Originator)到目的節點的跳數。在全局修復的情況下，OD hop count賦值INFINITY以區分局部修復。

RC Table消息格式如表3所示：

表3 RC Table格式

用來確定某一條路由線路及其新舊程度，OD Hop Count說明正在修復的路由線路的斷鏈位置。

當節點收到局部修復消息后，將損壞鏈路的位置信息存儲在RC Table中。根據RC Table，節點判斷同一條路由是否執行了多個局部修復進程。對于正在修復的路由線路，節點收到一個RREQ消息，若此消息中的Destination IP與該節點RC Table存有的Destination IP相同，且具有相等的Destination Sequence Number，則認為沖突發生。那么必須對這些有沖突的修復進程分配優先級。如果此修復進程是全局修復，則賦予其較高優先級。如果是局部修復且其OD hop count比RC Table存有的OD hop count大(即在之前某一時刻進行的局部修復的OD hop count)，則同樣賦予其較高優先級。否則賦予此修復進程較低優先級。有較高優先級的RREQ隨之將更新相應的路由表項及RC Table。修復策略的算法框圖如圖4所示：

圖4 修復策略的算法框圖

4 仿真實驗分析

選擇OPNET modeler 10.5[8]作為仿真工具，對AODV和改進后的AODV進行仿真測試。為表述方便，現做如下定義：

GR AODV：僅具備全局修復機制的AODV協議。

Proposed Method 1：具備全局修復和局部修復機制的AODV協議，即RFC 3561中的AODV協議。

Proposed Method 2：具備全局修復和局部修復機制，且能夠避免競爭沖突的AODV協議，即本文提出的改進后的AODV協議。

仿真的基本參數設置如表4所示：

表4 仿真的基本參數設置

對以上描述的幾個協議分別收集以下性能評價參數來比較分析：路由修復開銷、數據包投遞率和端到端平均時延，分別定義如下：

數據包投遞率：數據包到達目的節點次數/數據包發送次數

端到端平均時延：到達目的節點時間-發送時間

隨著網絡吞吐量的增大，3種路由算法的修復開銷逐漸增大，如圖5所示：

圖5 路由修復開銷仿真結果

其中GR AODV的開銷最大，這是因為GR AODV并不具備局部修復能力，每次斷鏈都會從源節點發起全局修復；Proposed Method 1的修復代價也很大，在達到69kb/s時甚至和GR AODV一樣；而Proposed Method 2的代價最小。3種路由算法在網絡負載加大的情況下，數據包投遞率呈下降趨勢，而端到端平均時延逐漸增加，如圖6圖7所示：

圖6 數據包投遞率仿真結果

圖7 數端到端平均時延仿真結果

其中Proposed Method 1的性能較差，在超過40kb/s時甚至不如GR AODV，這是因為Proposed Method 1雖然具備局部修復機制，但由于不能避免競爭沖突，使得當多處斷鏈頻繁發生時，離源節點較遠的節點發出大量無用的數據包，影響投遞率，并且延后能夠成功修復路由的其他局部修復或全局修復，增大端到端平均時延。由于Proposed Method 2能夠有效避免由于競爭問題導致的局部修復失敗，并減少無效的數據包，因此其無論在數據包投遞率還是端到端平均時延都有較好表現。

5 總結

局部修復相對于全局修復能夠以較小的開銷達到修復損壞路由的目的。但是，另一方面，全局修復卻可以得到跳數最少的路由線路。因此，AODV采取了全局修復和局部修復相結合的方式。但是，由于AODV沒有解決競爭沖突機制，因此，使得其在處理多處斷鏈時性能較低。本文在原有的AODV路由算法基礎上，提出了一種新的改進的局部修復算法，它采用分配每個修復進程優先級的方法來避免競爭問題。從仿真的結果看，新的修復機制降低了路由修復開銷和端到端平均時延，提高了數據包投遞率，使路由協議的性能有所提高，對于深入了解Ad hoc網絡的路由機制具有一定的意義。

參考文獻：

[1] 鄭少仁,王海濤,趙志峰等.Ad Hoc網絡技術[M].北京,人民郵電出版社,2005:1-13,64-79

[2] Johnson, D.B.. Maltz D.A, “Dynamic Source Routing in Ad Hoc Wireless Networks”[M], in Mobile Computing, ed. By T.imielinski and H.korth, Kluwer Academic Publishers, 1996.

[3] RFC3561，Ad hoe On—Demand Distance Vector(AODV) Routing[S]．

[4] .Toh, C.-K “Associativity-based routing for ad-hoc mob-ile networks”[J], Wireless Pers.Commun.J., vol.4, no.2, pp.103-139, March 1997.

[5] Srinath Perur, Abhilash P. and Sridhar Iyer, “Router handoff: a preemptive route repair strategy for AODV”[M], IEEE Intel. Conference on Personal Wireless Computing, New Delhi,Dec, 2002.

[6] 袁培燕,李靜,史向陽.AODV路由協議局部修復機制的改進[J]. 河南師范大學學報(自然科學版),2008,36(5):29-31

[7] 葛文英,李臘元.AODV路由協議局部修復機制的優化與仿真研究[J]. 武漢理工大學學報.2007,31(6):464-467

[8] Anipakala Suresh .Performance Analysis of Ad hoc On-demand Distance Vector routing (AODV) using OPNET Simulator[M], Bremen, 11th April 2005

Improvement of Local Repair Mechanism in AODV Protocol

Han Lincheng, Chen Xichun

(Combat Training Experiment Center, Mechanized Infantry Academy, Shijiazhuang 050083, China)

AODV protocol is a typical on-demand routing protocol in Ad Hoc networks. Based on the detailed analysis of the mechanism of local repair in AODV, this paper proposes an improved method to solve the race problem caused by local repair, that when multiple open circuit occurs, priority will be distributed to every repair process to avoid the problem of competition. Simulations show that the proposed mechanism can effectively avoid the competition and improve the network performance.

AODV; Ad Hoc; Local Repair; Race Problem; Priority

1007-757X(2016)04-0065-03

TP183

A

（2015.09.07）

韓林呈（1984-），男，河北石家莊人，機械化步兵學院教研部作戰訓練實驗中心，助教，碩士，研究方向：計算機仿真及人工智能，石家莊，050083。

陳喜春（1971-），男，河南新鄉人，機械化步兵學院教研部作戰訓練實驗中心，講師，碩士，研究方向：計算機仿真，石家莊，050083。