摘 要: AODV路由協(xié)議每次在源節(jié)點(diǎn)只建立一條通向目的節(jié)點(diǎn)的路由,,未能充分利用從中間節(jié)點(diǎn)或者目的節(jié)點(diǎn)返回的路由應(yīng)答信息,,針對(duì)這一問(wèn)題,,提出了一個(gè)改進(jìn)的方法,。在源節(jié)點(diǎn)處建立一條主路由的基礎(chǔ)上,,利用路由應(yīng)答信息,,建立一條備份路由,,并且每次將最優(yōu)的設(shè)為主路由,,次優(yōu)的設(shè)為備份路由。仿真結(jié)果表明,,改進(jìn)的協(xié)議和原協(xié)議相比,,降低了端到端的延時(shí),提高了包投遞率
關(guān)鍵詞: Ad Hoc網(wǎng)絡(luò),;路由協(xié)議,;AODV協(xié)議;備份路由
移動(dòng)自組織網(wǎng)絡(luò)MANET(Mobile Ad Hoc Network)是一種移動(dòng),、自組織的系統(tǒng),。MANET是對(duì)等網(wǎng)絡(luò),每個(gè)節(jié)點(diǎn)既可以作為主機(jī),,也可以作為路由器,,數(shù)據(jù)包通過(guò)網(wǎng)絡(luò)進(jìn)行逐跳轉(zhuǎn)發(fā)。由于它組網(wǎng)靈活,、不依賴(lài)于現(xiàn)有的網(wǎng)絡(luò)基礎(chǔ)設(shè)施,,在軍事和緊急救援領(lǐng)域應(yīng)用前景十分廣闊。目前Ad Hoc網(wǎng)絡(luò)的路由協(xié)議可分為3大類(lèi),,表驅(qū)動(dòng)路由協(xié)議有OLSR,、WRP,、DSDV[1],按需路由協(xié)議有AODV[2],、DSR,,基于約束的路由協(xié)議有ABR、LAR,。
AODV是一種按需路由協(xié)議,,并已經(jīng)成為IETF的標(biāo)準(zhǔn)化路由協(xié)議。它的主要特點(diǎn)是使用序列號(hào)來(lái)表示一條路由的新舊程度,,同時(shí)用來(lái)避免出現(xiàn)路由環(huán)路,,AODV主要有路由發(fā)現(xiàn)和路由維護(hù)兩個(gè)過(guò)程。
本文針對(duì)AODV路由協(xié)議出現(xiàn)鏈路斷開(kāi)時(shí)只能通過(guò)本地修復(fù)機(jī)制來(lái)進(jìn)行鏈路修復(fù)的不足,,利用從中間節(jié)點(diǎn)或者目的節(jié)點(diǎn)返回的路由應(yīng)答信息,,在建立一條主路由的基礎(chǔ)上,再建立一條備份路由,,并且每次將最優(yōu)的設(shè)為主路由,,次優(yōu)的設(shè)為備份路由,使得出現(xiàn)鏈路斷開(kāi)的上游節(jié)點(diǎn)能夠利用備份路由進(jìn)行數(shù)據(jù)的傳輸,,有效地降低了時(shí)延和提高了分組投遞率,,通過(guò)仿真軟件NS2驗(yàn)證了改進(jìn)后的協(xié)議具有更好的性能。
1 AODV路由協(xié)議概述
1.1 路由發(fā)現(xiàn)過(guò)程
當(dāng)源節(jié)點(diǎn)要向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí),,創(chuàng)建一個(gè)路由請(qǐng)求包RREQ,,并向鄰居節(jié)點(diǎn)進(jìn)行廣播,,進(jìn)行泛洪路由發(fā)現(xiàn)過(guò)程[3],。
中間節(jié)點(diǎn)收到路由請(qǐng)求之后,首先根據(jù)RREQ中的廣播號(hào)判斷是否是已經(jīng)處理過(guò)的RREQ,,如果是,,則丟棄;如果是新收到的RREQ,,就建立或者更新到源節(jié)點(diǎn)的反向路由,,使得反向路由表中到源節(jié)點(diǎn)的路由序列號(hào)大于RREQ中的序列號(hào)或者序列號(hào)相同并且有更少的跳數(shù)。然后查找路由表,,如果沒(méi)有到目的節(jié)點(diǎn)的積極路由,,就繼續(xù)廣播RREQ,如果有到目的節(jié)點(diǎn)的積極路由,,并且路由中的目標(biāo)節(jié)點(diǎn)序列號(hào)大于或者等于RREQ中的序列號(hào),,就沿著反向路由向源節(jié)點(diǎn)單播路由應(yīng)答RREP。
目的節(jié)點(diǎn)收到RREQ后,,不再?gòu)V播,,建立反向路由,,產(chǎn)生一個(gè)含有最新序列號(hào)的路由應(yīng)答RREP,沿反向路由向源節(jié)點(diǎn)單播,。中間節(jié)點(diǎn)收到RREP后,,建立到目的節(jié)點(diǎn)的正向路由,并更新路由信息,。源節(jié)點(diǎn)收到RREP后,,建立到目的節(jié)點(diǎn)的正向路由,并開(kāi)始向目的節(jié)點(diǎn)傳輸數(shù)據(jù),。
路由發(fā)現(xiàn)過(guò)程如圖1所示,。如果節(jié)點(diǎn)S需要對(duì)節(jié)點(diǎn)D進(jìn)行通信,節(jié)點(diǎn)S沒(méi)有到節(jié)點(diǎn)D的積極路由,,節(jié)點(diǎn)S廣播一個(gè)路由請(qǐng)求RREQ,。節(jié)點(diǎn)1收到RREQ,假設(shè)其沒(méi)有到節(jié)點(diǎn)D的積極路由,,節(jié)點(diǎn)1會(huì)繼續(xù)廣播此RREQ,。假設(shè)節(jié)點(diǎn)2中有一條到達(dá)目的節(jié)點(diǎn)D的積極路由,節(jié)點(diǎn)3和節(jié)點(diǎn)4中沒(méi)有到節(jié)點(diǎn)D的積極路由,。最終節(jié)點(diǎn)S將會(huì)先后收到由節(jié)點(diǎn)2和節(jié)點(diǎn)D分別發(fā)送的包含S-1-2-D和S-3-4-D的路由應(yīng)答RREP,,由于節(jié)點(diǎn)D發(fā)送的RREP具有更高的序列號(hào),所以路由S-1-2-D將被丟棄,,即使這條路由也是有效的,。這樣當(dāng)節(jié)點(diǎn)S與節(jié)點(diǎn)3鏈路斷開(kāi),節(jié)點(diǎn)S進(jìn)行鏈路失效處理時(shí)就無(wú)法使用路由S-1-2-D,,而可能進(jìn)行局部修復(fù),,從而造成了延時(shí)。設(shè)想如果能將S-1-2-D路由作為備份加以保留,,那么在S-3-4-D路由斷裂時(shí),,就可以轉(zhuǎn)換到使用備份路由上來(lái)。
1.2 路由維護(hù)
路由維護(hù)[4]可以及時(shí)發(fā)現(xiàn)節(jié)點(diǎn)因移動(dòng)或其他原因而引起的鏈路斷開(kāi),,每個(gè)包含路由的節(jié)點(diǎn),,周期地廣播HELLO消息,并且TTL值為1,,因此只能與其相鄰節(jié)點(diǎn)傳播,。一個(gè)節(jié)點(diǎn)收到HELLO消息便知道自己與鄰節(jié)點(diǎn)保持連接,如果在一定時(shí)間內(nèi)收不到HELLO消息,,則進(jìn)行鏈路失效的處理,。如果鏈路斷開(kāi)處離目的節(jié)點(diǎn)較近,將進(jìn)行鏈路的局部修復(fù),,即由鏈路斷開(kāi)處的上游節(jié)點(diǎn)發(fā)起到目的節(jié)點(diǎn)的路由發(fā)現(xiàn)過(guò)程,。如果在給定的時(shí)間內(nèi)重新建立起有效的路由,,就繼續(xù)發(fā)送數(shù)據(jù);如果未能成功建立,,則向上游發(fā)送RERR,。如果鏈路斷開(kāi)處離目的節(jié)點(diǎn)較遠(yuǎn),則不進(jìn)行局部修復(fù),,直接將路由設(shè)為失效狀態(tài),,并向上游發(fā)送RERR。設(shè)想如果有一條備份路由存在于鏈路斷開(kāi)處離目的節(jié)點(diǎn)較遠(yuǎn)的地方,,就可以直接使用備份路由而不必進(jìn)行泛洪路由發(fā)現(xiàn)過(guò)程,。
2 基于備份路由的改進(jìn)方法
對(duì)AODV路由協(xié)議的分析表明,源節(jié)點(diǎn)接收到路由應(yīng)答RREP后,,將序列號(hào)最大或者序列號(hào)相同且有較少的跳數(shù)作為判據(jù),,因此只保留了一條到目的節(jié)點(diǎn)的路由,如果這條路由失效,,就會(huì)重新發(fā)起路由發(fā)現(xiàn)過(guò)程,,從而增大了網(wǎng)絡(luò)的開(kāi)銷(xiāo)。為了充分利用源節(jié)點(diǎn)接收到的路由應(yīng)答信息,,同時(shí)又能避免路由環(huán)路的出現(xiàn)[5],,對(duì)AODV協(xié)議作了改進(jìn)。
在路由表項(xiàng)中添加標(biāo)記主路由或備份路由的主/備份標(biāo)志位,,并且初始化為0,,表示主路由(1表示備份路由),在鏈路未出現(xiàn)斷開(kāi)的情況下,,均默認(rèn)使用主路由,。
為了能夠?qū)崿F(xiàn)添加備份路由的功能,對(duì)源節(jié)點(diǎn)接收到RREP的處理過(guò)程作了修改,,如圖2所示,。在路由發(fā)現(xiàn)過(guò)程中,,源節(jié)點(diǎn)接收到RREP后建立主路由,。如果接收到的RREP的序列號(hào)比存在的到該目的節(jié)點(diǎn)的主路由序列號(hào)大,或者序列號(hào)相同但是有更少的跳數(shù),,并且是第一次接收到RREP的話(huà),,更新主路由。如果不是第一次接收到RREP并且沒(méi)有備份路由,,則更改原來(lái)主路由的標(biāo)志位,,設(shè)為備份路由,添加新的主路由并更新,;如果有備份路由,,更改原來(lái)主路由中的標(biāo)志位,,設(shè)為備份路由,更改原來(lái)備份路由中的標(biāo)志位,,設(shè)為主路由并更新,。
如果源節(jié)點(diǎn)接收到的RREP的序列號(hào)沒(méi)有比存在的到目的節(jié)點(diǎn)的主路由序列號(hào)大,或者序列號(hào)相同但是沒(méi)有更少的跳數(shù),,而且沒(méi)有備份路由,,則添加此RREP序列號(hào)對(duì)應(yīng)的路由為備份路由;如果存在備份路由,,并且現(xiàn)接收序列號(hào)比備份路由序列號(hào)大,,或者序列號(hào)相同但是有更少的跳數(shù),則更新備份路由,,否則丟棄RREP,。
這樣通過(guò)以上過(guò)程,就能使得每次在路由發(fā)現(xiàn)過(guò)程以及可能的修復(fù)過(guò)程中建立兩條路由,,而且主路由和備份路由是最優(yōu)的兩條路由,,同時(shí)主路由優(yōu)于備份路由。如圖1所示,,通過(guò)改進(jìn)的方法,,在與之前相同的情況下,節(jié)點(diǎn)S與節(jié)點(diǎn)D之間便建立了一條主路由S-3-4-D和一條備份路由S-1-2-D,。在整個(gè)網(wǎng)絡(luò)的路由發(fā)現(xiàn)過(guò)程中,,除了前述改進(jìn)方法中源節(jié)點(diǎn)通過(guò)接收到的RREP建立備份路由時(shí)要查找本地路由表中是否有到目的節(jié)點(diǎn)的備份路由外,其他的節(jié)點(diǎn)均只查找本地路由表中是否有到目的節(jié)點(diǎn)的主路由,,從而保證了優(yōu)先使用主路由,。
在路由維護(hù)階段,如圖3所示,,如果節(jié)點(diǎn)S要向節(jié)點(diǎn)D傳輸數(shù)據(jù),,在建立的主路由S-1-4-5-D中,節(jié)點(diǎn)1和節(jié)點(diǎn)4之間發(fā)生鏈路中斷,,這時(shí),,節(jié)點(diǎn)1要對(duì)鏈路斷開(kāi)進(jìn)行處理。如果之前節(jié)點(diǎn)1向節(jié)點(diǎn)D傳輸過(guò)數(shù)據(jù),,并且通過(guò)本文前述改進(jìn)的方法在路由發(fā)現(xiàn)過(guò)程中建立了備份路由1-2-3-D(節(jié)點(diǎn)1曾經(jīng)擔(dān)任過(guò)源節(jié)點(diǎn)),,且該備份路由有效,則節(jié)點(diǎn)1使用備份路由發(fā)送數(shù)據(jù),,從而減少了延時(shí),,提高了分組的投遞率;如果該備份路由已經(jīng)失效,則進(jìn)行與原AODV協(xié)議相同的操作,。
3 仿真環(huán)境和結(jié)果
用仿真軟件NS2進(jìn)行了模擬實(shí)驗(yàn)[6],,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一個(gè)包含50個(gè)移動(dòng)節(jié)點(diǎn)的網(wǎng)絡(luò)模型,各節(jié)點(diǎn)隨機(jī)分布在1 000 m×300 m的平面矩形區(qū)域內(nèi),,并隨機(jī)地以均勻分布在0~20 m/s之間的速度向區(qū)域內(nèi)任意目的地移動(dòng),,到達(dá)目的地后停留一段時(shí)間,然后再隨機(jī)地選擇一個(gè)目的地移動(dòng),,如此反復(fù),,直到模擬結(jié)束??偰M時(shí)間為300 s,,若停留時(shí)間為0,則節(jié)點(diǎn)到達(dá)目的地后不停留,,若停留時(shí)間為300 s,,則節(jié)點(diǎn)靜止。每個(gè)節(jié)點(diǎn)的數(shù)據(jù)速率為1 Mb/s,,MAC層協(xié)議采用IEEE 802.11,,采用CBR業(yè)務(wù)類(lèi)型,CBR流的個(gè)數(shù)為10,。
端到端的延時(shí)是指一個(gè)數(shù)據(jù)分組從源節(jié)點(diǎn)的IP層到目的節(jié)點(diǎn)的IP層所需要的平均時(shí)間,,從圖4中可以看到兩種協(xié)議的平均端到端延時(shí)隨著節(jié)點(diǎn)暫停時(shí)間的增加都在減小,但是,,新協(xié)議的端到端延時(shí)比原協(xié)議更小,。
分組投遞率是目的節(jié)點(diǎn)應(yīng)用層接收到的分組數(shù)與源節(jié)點(diǎn)發(fā)送的分組數(shù)之比,從圖5中可以看到兩種協(xié)議的分組投遞率隨著節(jié)點(diǎn)暫停時(shí)間的增加都在增加,,但是新協(xié)議有更高的分組投遞率,。
本文對(duì)AODV路由協(xié)議進(jìn)行了分析,針對(duì)AODV路由發(fā)現(xiàn)過(guò)程中源節(jié)點(diǎn)未能充分利用路由應(yīng)答的問(wèn)題進(jìn)行了改進(jìn),,建立備份路由,,并通過(guò)改進(jìn)主路由和備份路由的選擇機(jī)制,使得當(dāng)鏈路斷開(kāi)時(shí),,鏈路斷開(kāi)處的上游節(jié)點(diǎn)可以使用備份路由發(fā)送數(shù)據(jù),,盡管在建立備份路由的過(guò)程中占用一定的時(shí)間和資源,但仿真結(jié)果明顯表明,,其減少了端到端的時(shí)延和提高了分組投遞率,。
參考文獻(xiàn)
[1] PERKINS C, BHAGWAT P. Highly dynamic destination sequenced distance vector(DSDV)routing for mobile compu-ters[C]. Proceedings of ACMSIGCOMM′94,, 1994:234-244.
[2] PERKINS C, ROYER E. RFC 3561 Ad-hoc on-demand distance vector(AODV) routing[S]. 2003-07.
[3] 高興國(guó),王漢星,,胡細(xì).一個(gè)優(yōu)化的AODV路由協(xié)議[J].計(jì)算機(jī)工程與應(yīng)用,,2007,43(3):128-130.
[4] 肖百龍,,郭偉,,劉軍,等.AODV的本地修復(fù)算法[J].計(jì)算機(jī)應(yīng)用研究,,2007,,24(3):231-237.
[5] 李世寶,洪利.基于鄰居緩存的AODV路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,,2011,,31(7):1931-1943.
[6] 馬崇霄,吳長(zhǎng)奇.基于網(wǎng)絡(luò)仿真器NS2的Ad hoc網(wǎng)絡(luò)路由協(xié)議仿真[J].電子測(cè)量技術(shù),,2008,,31(5):75-79.