韓林呈，陳喜春

?

AODV協(xié)議局部修復(fù)機制改進(jìn)

韓林呈，陳喜春

AODV協(xié)議是Ad Hoc網(wǎng)絡(luò)中典型的按需路由協(xié)議在詳細(xì)分析AODV局部修復(fù)機制的基礎(chǔ)上，提出了一種針對局部修復(fù)引發(fā)競爭問題的改進(jìn)方法，即當(dāng)多個斷路發(fā)生時，分配每個修復(fù)進(jìn)程優(yōu)先級以避免競爭問題。仿真表明，該機制能夠有效避免競爭并提升網(wǎng)絡(luò)性能。

AODV；Ad Hoc；局部修復(fù)；競爭問題；優(yōu)先級

0 引言

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

1 AODV的局部修復(fù)機制

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

表1 RREQ格式

局部修復(fù)與全局修復(fù)的RREQ格式相同。Originator代表泛洪發(fā)送RREQ消息的節(jié)點。

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 局部修復(fù)引發(fā)的競爭問題

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

圖1 局部修復(fù)引發(fā)競爭的時間條件

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

圖2 RREQ（M1）被丟棄過程

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

這種情況導(dǎo)致的后果如圖3所示：

圖3 RREP無法傳送到源節(jié)點

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

3 優(yōu)化策略

競爭問題會使得離源節(jié)點最近的損壞鏈路無法修復(fù)。因此，當(dāng)競爭沖突發(fā)生時，賦予離源節(jié)點最近的（即離目標(biāo)節(jié)點最遠(yuǎn)）損壞鏈路最高局部修復(fù)優(yōu)先級，其他局部修復(fù)賦予較低優(yōu)先級，或者直接丟棄。

每一個節(jié)點要有以下功能：

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

競爭偵測功能

競爭解決功能

在局部修復(fù)消息中增加以下信息：

指定源節(jié)點和目標(biāo)節(jié)點

指定新路由線路

指定路由中損壞鏈路位置

RREQ消息格式如表2所示：

表2 改進(jìn)AODV RREQ消息格式

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

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

表3 RC Table格式

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

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

圖4 修復(fù)策略的算法框圖

4 仿真實驗分析

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

GR AODV：僅具備全局修復(fù)機制的AODV協(xié)議。

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

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

仿真的基本參數(shù)設(shè)置如表4所示：

表4 仿真的基本參數(shù)設(shè)置

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

數(shù)據(jù)包投遞率：數(shù)據(jù)包到達(dá)目的節(jié)點次數(shù)/數(shù)據(jù)包發(fā)送次數(shù)

端到端平均時延：到達(dá)目的節(jié)點時間-發(fā)送時間

隨著網(wǎng)絡(luò)吞吐量的增大，3種路由算法的修復(fù)開銷逐漸增大，如圖5所示：

圖5 路由修復(fù)開銷仿真結(jié)果

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

圖6 數(shù)據(jù)包投遞率仿真結(jié)果

圖7 數(shù)端到端平均時延仿真結(jié)果

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

5 總結(jié)

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

參考文獻(xiàn)：

[1] 鄭少仁,王海濤,趙志峰等.Ad Hoc網(wǎng)絡(luò)技術(shù)[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路由協(xié)議局部修復(fù)機制的改進(jìn)[J]. 河南師范大學(xué)學(xué)報(自然科學(xué)版),2008,36(5):29-31

[7] 葛文英,李臘元.AODV路由協(xié)議局部修復(fù)機制的優(yōu)化與仿真研究[J]. 武漢理工大學(xué)學(xué)報.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-），男，河北石家莊人，機械化步兵學(xué)院教研部作戰(zhàn)訓(xùn)練實驗中心，助教，碩士，研究方向：計算機仿真及人工智能，石家莊，050083。

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