文獻(xiàn)標(biāo)識(shí)碼: A
移動(dòng)自組網(wǎng)(MANET)是由一系列移動(dòng)終端組成的無固定基礎(chǔ)設(shè)施的多跳自組織網(wǎng)絡(luò)系統(tǒng)[1],,其拓?fù)浣Y(jié)構(gòu)因?yàn)楣?jié)點(diǎn)電量不足或是移動(dòng)而變化,,所以MANET的路由協(xié)議與傳統(tǒng)網(wǎng)絡(luò)的路由協(xié)議有著很大的區(qū)別。
目前,移動(dòng)網(wǎng)絡(luò)中較成熟,、較典型的路由協(xié)議有DSDV,、DSR、AODV,、ZRP等[2],。其中,AODV路由協(xié)議[3]是一種經(jīng)典的按需路由協(xié)議,,它在一定程度上比其他協(xié)議有較小的路由開銷和更好的擴(kuò)展性能,,但是這種路由協(xié)議在網(wǎng)絡(luò)拓?fù)漕l繁變化的情況下,路由斷鏈的幾率很大,其網(wǎng)絡(luò)性能下降很快,,無法保證較高要求的服務(wù)質(zhì)量,。
針對(duì)高速移動(dòng)自組網(wǎng)的特性,本文提出一種基于AODV的改進(jìn)路由協(xié)議,,即IMAODV,,它在路由度量值、斷鏈修復(fù)策略以及HELLO消息機(jī)制上做了修改,,使之能有效地降低網(wǎng)絡(luò)延遲,,提高網(wǎng)絡(luò)的吞吐量。通過NS2仿真可以看到,,本文提出的IMAODV路由協(xié)議與傳統(tǒng)的AODV路由協(xié)議相比具有一定的優(yōu)勢:它既能降低中高速移動(dòng)自組網(wǎng)的網(wǎng)絡(luò)延時(shí),,又能在一定程度上提高網(wǎng)絡(luò)吞吐量;同時(shí),,IMAODV路由協(xié)議能夠較好地適應(yīng)無線網(wǎng)絡(luò)環(huán)境,,有效提高網(wǎng)絡(luò)性能。
1 IMAODV路由算法
1.1 AODV
傳統(tǒng)自組網(wǎng)路由協(xié)議可分為主動(dòng)路由協(xié)議和按需路由協(xié)議[4],,由于移動(dòng)自組網(wǎng)存在著動(dòng)態(tài)多變特性,,主動(dòng)路由協(xié)議應(yīng)用在移動(dòng)網(wǎng)絡(luò)中有著明顯的缺陷,所以實(shí)際中經(jīng)常使用的都是按需路由協(xié)議[5],。
AODV是Ad-hoc網(wǎng)絡(luò)的經(jīng)典路由協(xié)議,,它是由路由發(fā)現(xiàn)和路由維護(hù)組成。路由發(fā)現(xiàn)過程如圖1所示,。而在路由維護(hù)中,節(jié)點(diǎn)通過周期性地發(fā)送HELLO包維持與鄰居節(jié)點(diǎn)的連接,,若一段時(shí)間后還未收到鄰居節(jié)點(diǎn)的HELLO包,則開始鏈路修復(fù)過程,。若本節(jié)點(diǎn)離目的節(jié)點(diǎn)較近,,則進(jìn)行本地修復(fù),發(fā)送RREQ進(jìn)行路由重建,當(dāng)中間節(jié)點(diǎn)有到不可達(dá)節(jié)點(diǎn)的有效路由或者不可達(dá)節(jié)點(diǎn)收到此RREQ后就發(fā)送一個(gè)路由回復(fù)RREP給源節(jié)點(diǎn),,這樣路由就得到了重建,。若鏈路修復(fù)失敗,則節(jié)點(diǎn)向所有的鄰居節(jié)點(diǎn)廣播RERR包,,RERR包中的不可達(dá)節(jié)點(diǎn)列表不僅包括了鏈路斷開的鄰居節(jié)點(diǎn),,還包括了以此鄰居節(jié)點(diǎn)作為下一跳的所有目的節(jié)點(diǎn)。通過RERR的廣播,,其他節(jié)點(diǎn)便知道鏈路斷開了,,當(dāng)此包傳到源節(jié)點(diǎn)時(shí),將進(jìn)行新一輪的路由發(fā)現(xiàn),。
1.2 IMAODV路由算法
AODV雖然也能適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò),,但是它的機(jī)制并不靈活,不能根據(jù)網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)調(diào)節(jié)發(fā)送頻率,再者路由度量值僅僅考慮了跳數(shù)信息,,且路由單一,,所以不能滿足移動(dòng)環(huán)境較為復(fù)雜或移動(dòng)速度較高的網(wǎng)絡(luò)環(huán)境。為了更好地滿足移動(dòng)自組網(wǎng)的服務(wù)要求,,本文將針對(duì)高速移動(dòng)環(huán)境提出的IMAODV,,在AODV協(xié)議的基礎(chǔ)上做出以下改進(jìn),以改善網(wǎng)絡(luò)的吞吐量和平均端到端延遲,。
1.2.1節(jié)點(diǎn)度量值的選取
以跳數(shù)為度量的AODV,容易造成大量數(shù)據(jù)通過少量節(jié)點(diǎn)傳輸引起網(wǎng)絡(luò)的阻塞,,而導(dǎo)致分組延時(shí)過大,吞吐量下降[6],。為了緩解這種情況,,本文在路由度量值的選取中將考慮以下因素:
節(jié)點(diǎn)移動(dòng)速度:節(jié)點(diǎn)的移動(dòng)速度越大,鏈路越不穩(wěn)定,,所以在選擇路由時(shí)要選移動(dòng)速度較低的中間節(jié)點(diǎn),,避免因節(jié)點(diǎn)移動(dòng)造成斷鏈的路由重啟過程,以降低網(wǎng)絡(luò)開銷,。
延遲:路由過程中,,延遲越小,數(shù)據(jù)傳輸才能顯示其時(shí)效性,。
跳數(shù):跳數(shù)越少,,在某種程度上,所消耗的網(wǎng)絡(luò)資源越少,。
考慮到節(jié)點(diǎn)的計(jì)算復(fù)雜度,路由度量值:
其中hop代表跳數(shù),,nodenum表示網(wǎng)絡(luò)總的節(jié)點(diǎn)數(shù),,delay代表上一跳節(jié)點(diǎn)到本節(jié)點(diǎn)的延遲,speed代表本節(jié)點(diǎn)的移動(dòng)速度,max speed代表網(wǎng)絡(luò)中節(jié)點(diǎn)的最大移動(dòng)速度,,w1,、w2和w3分別代表權(quán)值,其中,w1+w2+w3=1,,本協(xié)議中w1,、w2和w3的值分別取為0.7、0.2和0.1,。當(dāng)metric的值越小,,路由鏈路的穩(wěn)定度越高,網(wǎng)絡(luò)延遲越小,。
1.2.2 節(jié)點(diǎn)功能的改進(jìn)
傳統(tǒng)AODV中源節(jié)點(diǎn)只保留一條到目的節(jié)點(diǎn)的路由,,當(dāng)主路由上的鏈路斷開時(shí),源節(jié)點(diǎn)重新開始進(jìn)行路由發(fā)現(xiàn)幾率較大,,容易造成過大的路由開銷和較大時(shí)延,。為改善這種情況,本文提出的IMAODV,,利用無線通信中廣播信道偵聽到的相鄰節(jié)點(diǎn)發(fā)給其他節(jié)點(diǎn)的RREP信息建立備用路由[7-8],通過增加節(jié)點(diǎn)的功能,使之具有監(jiān)聽路由控制信息的能力,。
1.2.3 Hello機(jī)制的改進(jìn)
IMAODV中對(duì)HELLO消息做兩方面改進(jìn): (1)是為HELLO消息設(shè)置了一個(gè)標(biāo)志。初始化為TURE,,節(jié)點(diǎn)發(fā)送HELLO消息,,當(dāng)節(jié)點(diǎn)有路由或數(shù)據(jù)信息需要廣播時(shí),標(biāo)志設(shè)為FALSE,。如果HELLO發(fā)送周期再次到來,,先檢查標(biāo)志,如果為FALSE,,則改變狀態(tài)為TURE后不作任何處理,,直至下一個(gè)周期的到來,再繼續(xù)檢查標(biāo)志,;當(dāng)標(biāo)志為TURE時(shí),,則發(fā)送HELLO消息,同時(shí)每個(gè)節(jié)點(diǎn)在接收路由包或是數(shù)據(jù)包的時(shí)候,,要更新鄰居的生存時(shí)間,,這樣可以降低發(fā)送HELLO消息的開銷。(2)由于節(jié)點(diǎn)的移動(dòng),,會(huì)造成網(wǎng)絡(luò)拓?fù)涞淖兓?,HELLO消息的固定發(fā)送肯定不能有效地捕捉到網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑸榱吮WC鏈路的有效性,,本文將根據(jù)節(jié)點(diǎn)自身的速度來調(diào)節(jié)HELLO包的發(fā)送頻率,發(fā)送頻率與節(jié)點(diǎn)的移動(dòng)速度成正比,,流程如圖2所示,。
1.2.4 鏈路修復(fù)的改進(jìn)
由于IMAODV路由中每個(gè)節(jié)點(diǎn)對(duì)路由應(yīng)答包具有偵聽功能,所以主路徑上節(jié)點(diǎn)的一跳鄰居都能夠偵聽到此包,,所以都能通過主路徑上的節(jié)點(diǎn)建立到目的節(jié)點(diǎn)的路由,,這樣就形成了多個(gè)到目的節(jié)點(diǎn)的備份路由。當(dāng)主路由上的某條鏈路斷開時(shí),,便可以通過路由請求RREQ進(jìn)行局部修復(fù),。為了減小路由請求的開銷,本文設(shè)置了路由請求的生存期為2跳,,中間節(jié)點(diǎn)收到路由請求時(shí),,若路由生存期不為0,則查找自己是否有到目的節(jié)點(diǎn)的路由,。若有,,則按原AODV的方式進(jìn)行應(yīng)答,若沒有則繼續(xù)廣播路由請求消息,,直到生存期變?yōu)?時(shí)丟棄包,。當(dāng)局部修復(fù)失敗時(shí),節(jié)點(diǎn)再廣播路由錯(cuò)誤包,。
1.2.5 IMAODV路由協(xié)議
IMAODV在路由請求,、路由應(yīng)答以及路由表中添加metric字段,以記錄路徑上每個(gè)節(jié)點(diǎn)的累計(jì)路由度量值,。當(dāng)源節(jié)點(diǎn)需要通信路由時(shí),,先初始化metric為0,再廣播這個(gè)RREQ包啟動(dòng)路由發(fā)現(xiàn)過程,。中間節(jié)點(diǎn)的路由表段中添加一個(gè)rt_metric,,記錄從源節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的路徑度量最小值,中間節(jié)點(diǎn)收到非重復(fù)的RREQ包時(shí),,將自身的metric值累加到路由RREQ中的rq_metric上,,再繼續(xù)轉(zhuǎn)發(fā)。如果節(jié)點(diǎn)已經(jīng)收到了同一源節(jié)點(diǎn)相同的廣播ID的RREQ,,且包的目的序列號(hào)大于路由表中序列號(hào),,則直接更新路由,若相等就通過比較rq_metric與rt_metric,,選較小者作為本路由表項(xiàng)中的rt_metric,,即更新路由表項(xiàng)再轉(zhuǎn)發(fā)包。當(dāng)路由請求包到達(dá)目的節(jié)點(diǎn)時(shí),,目的節(jié)點(diǎn)將選擇一個(gè)擁有較小metric的路由,,發(fā)送路由回復(fù)RREP。路由應(yīng)答是以單播的方式傳送,,接收到此包的節(jié)點(diǎn)時(shí),首先根據(jù)接收包中下一跳信息判斷本節(jié)點(diǎn)是監(jiān)聽節(jié)點(diǎn)還是正常的路由應(yīng)答節(jié)點(diǎn),如下一跳ID不等于本節(jié)點(diǎn)ID,,則本節(jié)點(diǎn)是監(jiān)聽節(jié)點(diǎn),,此時(shí)記錄到目的節(jié)點(diǎn)的路由后不再轉(zhuǎn)發(fā),否則是主路徑上的節(jié)點(diǎn),則按照傳統(tǒng)AODV路由應(yīng)答的方式進(jìn)行處理,。圖3為IMAODV路由建立的流程。
在圖3中,,路由建立或更新是根據(jù)路由序列號(hào)和路由度量值來決定的,。如果是第一次收到路由請求包,則建立路由,;若收到請求包中的目的節(jié)點(diǎn)序列號(hào)大于路由表中存儲(chǔ)的目的節(jié)點(diǎn)序列號(hào)或是等于路由表中存儲(chǔ)的目的序列號(hào),,但路由表中的路由度量值大于請求包中的路由度量值,則更新路由,。“是否忽略”檢查是否收到重復(fù)的包,,若是,則丟棄,;否則更新路由表和請求包信息再轉(zhuǎn)發(fā),。
2 仿真分析
2.1仿真環(huán)境
仿真工具采用NS-2.30[7]版本,網(wǎng)絡(luò)的拓?fù)洵h(huán)境是一個(gè)包含50個(gè)移動(dòng)節(jié)點(diǎn)的網(wǎng)絡(luò)模型,,節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m的正方形區(qū)域內(nèi),,并設(shè)置節(jié)點(diǎn)的移動(dòng)速度在0 m/s~40 m/s之間,每個(gè)節(jié)點(diǎn)的無線接口帶寬為2 Mb/s,有效無線發(fā)射范圍為250 m,鏈路層采用無線802.11 MAC協(xié)議,在50個(gè)節(jié)點(diǎn)中隨機(jī)產(chǎn)生4對(duì)恒定比特率的CBR連接,每個(gè)分組的長度為512 B,每秒發(fā)送4個(gè)包,為了考察改進(jìn)的協(xié)議在網(wǎng)絡(luò)仿真環(huán)境中的性能,,本文將模擬節(jié)點(diǎn)速度在0~20 m/s時(shí)由于停留時(shí)間(pause time),、網(wǎng)絡(luò)中節(jié)點(diǎn)間最大連接數(shù)以及節(jié)點(diǎn)的速度的變化對(duì)網(wǎng)絡(luò)吞吐量的影響,還有節(jié)點(diǎn)移動(dòng)速度變化對(duì)網(wǎng)絡(luò)平均端到端延遲的影響,設(shè)置了在相同環(huán)境下與AODV作比較,,給出了仿真結(jié)果,。
2.2 仿真結(jié)果及性能分析
圖4顯示了端到端延遲與節(jié)點(diǎn)移動(dòng)速度的關(guān)系,由此可知IMAODV協(xié)議的平均端到端延遲隨節(jié)點(diǎn)移動(dòng)速度的增大優(yōu)于AODV協(xié)議,,其原因是在路由度量中考慮了每一跳的延遲,,且改進(jìn)的HELLO機(jī)制的發(fā)送頻率與節(jié)點(diǎn)移動(dòng)速度有關(guān),能較快地發(fā)現(xiàn)路由斷鏈情況并做出相應(yīng)處理,。圖中節(jié)點(diǎn)最大速度為5 m/s時(shí),,由于處于低速狀態(tài),IMAODV優(yōu)勢并不突出,,較AODV的延遲大,,但是隨著節(jié)點(diǎn)的移動(dòng)速度的增加,IMAODV的平均端到端延遲低于AODV,;當(dāng)節(jié)點(diǎn)最大移動(dòng)速度達(dá)到40 m/s時(shí),,IMAODV的延遲約為AODV延遲的1/2。從總體來看,隨著節(jié)點(diǎn)移動(dòng)速度的增加,,IMAODV延遲有所下降,。
圖5中IMAODV在路由度量值和HELLO消息機(jī)制中考慮到節(jié)點(diǎn)移動(dòng)速度的影響,,并且節(jié)點(diǎn)具有偵聽路由應(yīng)答的功能,使其具有多條到目的節(jié)點(diǎn)的路由,。這樣在斷鏈的時(shí)候能夠及時(shí)地恢復(fù)路由,,進(jìn)行數(shù)據(jù)傳輸,隨著節(jié)點(diǎn)速度的提高,,IMAODV的吞吐量明顯優(yōu)于AODV,,如圖5所示,在節(jié)點(diǎn)最大移動(dòng)速度為10 m/s和15 m/s時(shí),IMAODV能提供比AODV高29.4%和34.3%的網(wǎng)絡(luò)吞吐量,。
圖6中反映了節(jié)點(diǎn)停留時(shí)間與吞吐量的關(guān)系,,此時(shí)場景中節(jié)點(diǎn)的最大移動(dòng)速度為20 m/s,停留時(shí)間在40 s、50 s以及150 s時(shí),,IMAODV的吞吐量較AODV略有下降,,原因是這些場景中中間節(jié)點(diǎn)的移動(dòng)速度較小,由于新協(xié)議中路由度量是多個(gè)方面的折中考慮,,所以在移動(dòng)速度不明顯的時(shí)候,,IMAODV的優(yōu)越性就不太明顯,但總體性能較AODV好,。
圖7是最大節(jié)點(diǎn)移動(dòng)速度為20 m/s時(shí),,網(wǎng)絡(luò)中節(jié)點(diǎn)連接增加對(duì)網(wǎng)絡(luò)吞吐量的影響。圖中兩個(gè)協(xié)議的吞吐量都隨著網(wǎng)絡(luò)中節(jié)點(diǎn)連接數(shù)的增加而增大,。明顯地,,由于考慮了節(jié)點(diǎn)的移動(dòng)速度,改進(jìn)后的協(xié)議能夠較快地捕捉節(jié)點(diǎn)間的斷鏈情況,,并做出較快的路由重建處理,,使得圖中IMAODV比AODV能產(chǎn)生較高的吞吐量。
本文針對(duì)移動(dòng)自組織網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)速度對(duì)路由協(xié)議的影響對(duì)AODV協(xié)議做了改進(jìn),,提出了一種新的改進(jìn)路由協(xié)議IMAODV(Improved AODV),。該協(xié)議在對(duì)HELLO消息機(jī)制及路由修復(fù)機(jī)制做出優(yōu)化的同時(shí),在MAC層做了優(yōu)化以使節(jié)點(diǎn)具有偵聽功能,,使之能夠在節(jié)點(diǎn)以中高速運(yùn)動(dòng)的條件下建立較穩(wěn)定的路由,,降低了分組傳輸端到端的平均延遲,并提高了網(wǎng)絡(luò)的吞吐量,。仿真結(jié)果表明,,該協(xié)議能較好地適應(yīng)移動(dòng)自組織網(wǎng)絡(luò)的通信環(huán)境。
下一步工作將對(duì)路由協(xié)議做多接口擴(kuò)展和跨層的優(yōu)化處理,,以進(jìn)一步提高路由算法的性能,。
參考文獻(xiàn)
[1] RFC2501. Mobile Ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations[s]
[2] 王金龍,王呈貴. Ad Hoc移動(dòng)無線網(wǎng)絡(luò)[M]. 北京:國防工業(yè)出版社,,2004:81-83
[3] RFC3561. Ad hoc on-demand distance vector (AODV)Routing [S].
[4] PERKINS C E. Ad hoc on demand distance vector Routing [J]. Mobile Computing Systems and Applications, 1991.
[5] 王力超,林綠洲,陸起涌. 基于AODV的改進(jìn)型ad hoc路由協(xié)議,儀器儀表學(xué)報(bào),, 2006,27(6).
[6] PERKINS D D, HUGHES H D, OWEN C B. Factors affecting the performance of Ad hoc networks[C]. IEEE International Conference on Communications,2002.Michigan State University, 2002:2048-2052.
[7] LWW S J, MARIO G AODV-BR: Backup routing in Ad hoc networks[C]. IEEE Wireless Communications and Networking Conference,2000(WCNC 2000),2000,3:1311-1316.
[8] 鄭相全,,郭偉,李帆. 自組網(wǎng)AODV路由協(xié)議中鍛煉修復(fù)的改進(jìn)[J].電子科技大學(xué)學(xué)報(bào),,2003,32(5).
[9] NS2[OL]. http://nsnam.isi.edu/nsnam/index.php.