韓林呈，陳喜春

?

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

韓林呈，陳喜春

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

AODV；Ad Hoc；局部修復(fù)；競(jìng)爭(zhēng)問(wèn)題；優(yōu)先級(jí)

0 引言

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

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

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

表1 RREQ格式

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

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ā)的競(jìng)爭(zhēng)問(wèn)題

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

圖1 局部修復(fù)引發(fā)競(jìng)爭(zhēng)的時(shí)間條件

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

圖2 RREQ（M1）被丟棄過(guò)程

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

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

圖3 RREP無(wú)法傳送到源節(jié)點(diǎn)

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

3 優(yōu)化策略

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

每一個(gè)節(jié)點(diǎn)要有以下功能：

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

競(jìng)爭(zhēng)偵測(cè)功能

競(jìng)爭(zhēng)解決功能

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

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

指定新路由線(xiàn)路

指定路由中損壞鏈路位置

RREQ消息格式如表2所示：

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

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

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

表3 RC Table格式

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

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

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

4 仿真實(shí)驗(yàn)分析

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

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

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

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

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

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

對(duì)以上描述的幾個(gè)協(xié)議分別收集以下性能評(píng)價(jià)參數(shù)來(lái)比較分析：路由修復(fù)開(kāi)銷(xiāo)、數(shù)據(jù)包投遞率和端到端平均時(shí)延，分別定義如下：

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

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

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

圖5 路由修復(fù)開(kāi)銷(xiāo)仿真結(jié)果

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

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

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

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

5 總結(jié)

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

參考文獻(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] 袁培燕,李靜,史向陽(yáng).AODV路由協(xié)議局部修復(fù)機(jī)制的改進(jìn)[J]. 河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,36(5):29-31

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

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