陳侃松,李豪科,阮玉龍,王時繪

(湖北大學 計算機與信息工程學院 物聯(lián)網(wǎng)工程研究所,湖北 武漢 430062)

Ad Hoc 網(wǎng)絡(luò)是一種無需基礎(chǔ)設(shè)施的多跳無線自組織移動網(wǎng)絡(luò),廣泛應用于軍事和緊急救災等領(lǐng)域.在Ad Hoc 網(wǎng)絡(luò)中,當節(jié)點高速移動時,網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化很快,導致網(wǎng)絡(luò)鏈路狀態(tài)不穩(wěn)定[1].此時,路由需要盡快重新找到能耗較低且狀態(tài)穩(wěn)定的鏈路.同時,在路由失效時避免網(wǎng)絡(luò)中斷.

本文主要研究的是Ad Hoc 網(wǎng)絡(luò)中一種按需距離矢量路由協(xié)議AODV 及其改進協(xié)議,AODV 協(xié)議在路由查找階段采用泛洪機制廣播RREQ 分組,可能會導致廣播風暴[2].在通信過程中,如果發(fā)生路由中斷,則其需由源節(jié)點重新建立到目的節(jié)點的路由.同時,當節(jié)點移動速度較快時,由于網(wǎng)絡(luò)拓撲頻繁變化,鏈路極易中斷,導致網(wǎng)絡(luò)性能迅速下降.因此,本文將跨層設(shè)計[3-6]和動態(tài)概率相結(jié)合,針對上述問題,對AODV 協(xié)議做出修改:首先,在AODV 路由發(fā)現(xiàn)階段采取動態(tài)概率轉(zhuǎn)發(fā)機制,根據(jù)局部鄰居節(jié)點數(shù)量,選擇計算轉(zhuǎn)發(fā)概率抑制路由風暴,提高了網(wǎng)絡(luò)性能;并在路由路徑選擇階段,利用跨層設(shè)計思想,提高了路由鏈路在網(wǎng)絡(luò)拓撲變化頻繁時的穩(wěn)定性.

本文主要貢獻如下:

(1) 針對AODV 路由查找階段容易導致廣播風暴的問題,提出一種動態(tài)轉(zhuǎn)發(fā)概率公式.基于網(wǎng)絡(luò)局部鄰居節(jié)點數(shù)量,使節(jié)點獲取當前所在區(qū)域、上級節(jié)點所在區(qū)域和整個網(wǎng)絡(luò)的節(jié)點密度,并根據(jù)不同的節(jié)點密度計算轉(zhuǎn)發(fā)概率,更好地抑制廣播風暴;

(2) 在快速變化的Ad Hoc 網(wǎng)絡(luò)中,針對AODV 協(xié)議建立的路由鏈路不穩(wěn)定、從而影響網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膯栴},提出鏈路權(quán)值的概念.利用跨層設(shè)計思想,結(jié)合網(wǎng)絡(luò)層節(jié)點運動速度計算鏈路權(quán)值,并在路由選擇依據(jù)中,將鏈路權(quán)值作為標準,以提高路由鏈路的時效性;

(3) 通過NS2 仿真平臺,對改進協(xié)議進行仿真以驗證其性能.分別對節(jié)點在40、60、80、100 節(jié)點數(shù)量不同移動速度的場景以及在30m/s、40m/s、50m/s 移動速度的不同節(jié)點數(shù)量的場景下進行仿真實驗,對改進協(xié)議的分組投遞率、端到端時延、歸一化路由開銷這3 項指標進行仿真性能評估,分析兩種改進協(xié)議(參見文獻[7,8]),同時驗證分析了本文改進協(xié)議與原始協(xié)議和文獻[7,8]的改進協(xié)議相比的優(yōu)勢.

1 相關(guān)工作

AODV 路由協(xié)議在路由查找階段采用泛洪機制發(fā)送RREQ 分組,如圖1 所示.圖1(a)中,當節(jié)點發(fā)起路由請求時,A節(jié)點開始廣播RREQ,B、C、D收到分組后繼續(xù)廣播該分組,E和F收到后仍然繼續(xù)廣播直到找到目的節(jié)點.這種方式容易導致廣播風暴,即網(wǎng)絡(luò)內(nèi)很多節(jié)點均在廣播發(fā)送消息,從而導致網(wǎng)絡(luò)擁堵甚至癱瘓,使得網(wǎng)絡(luò)性能下降,出現(xiàn)網(wǎng)絡(luò)可用帶寬減小、丟包率增加、傳輸延時增加等問題.因此,為了改善網(wǎng)絡(luò)性能,希望RREQ分組能夠以圖1(b)所示的方式轉(zhuǎn)發(fā),節(jié)點根據(jù)通信范圍內(nèi)的節(jié)點密度智能地選擇是否轉(zhuǎn)發(fā)分組,從而提高網(wǎng)絡(luò)的可用帶寬[5].

Fig.1 Broadcast storm diagram圖1 廣播風暴示意圖

AODV 路由路徑選擇建立階段如圖2(a)所示,其中,從節(jié)點S到節(jié)點D的最短跳數(shù)路徑選擇為S→B→D.在靜態(tài)網(wǎng)絡(luò)中,該路徑選擇策略可降低數(shù)據(jù)傳輸時延,節(jié)省網(wǎng)絡(luò)能量;但在拓撲變化較快的網(wǎng)絡(luò)中,采用該策略將會降低路由的時效性.如圖2(b)所示:當節(jié)點B運動較快且超出S的通信范圍時,S到D的鏈路就會斷裂,此時,S→B→D的路徑已失效,需再次重新發(fā)起路由查找;而另一路徑S→A→E→D仍然可用.因此,在網(wǎng)絡(luò)拓撲快速變化時,不應依據(jù)最短跳數(shù)來建立路由路徑,而應選擇更穩(wěn)定的路徑.

節(jié)點廣播轉(zhuǎn)發(fā)鄰居節(jié)點的數(shù)據(jù)之后,可增加的平均有效廣播區(qū)域為41%[6].同時,當節(jié)點擁有多鄰居節(jié)點時,增加的有效廣播區(qū)域則會減少.文獻[9]中提出一種利用節(jié)點的平均鄰居節(jié)點數(shù)量來衡量網(wǎng)絡(luò)的稠密程度的策略,以動態(tài)概率轉(zhuǎn)發(fā)路由查找分組,從而抑制路由查找階段的廣播泛洪.該方法以動態(tài)形式表示網(wǎng)絡(luò)的疏密程度,并給出轉(zhuǎn)發(fā)概率,但是,由于網(wǎng)絡(luò)拓撲的變化和節(jié)點的快速移動,導致每個節(jié)點不能實時獲取網(wǎng)絡(luò)的疏密程度.同時,網(wǎng)絡(luò)中存在網(wǎng)絡(luò)節(jié)點分布不均勻的情況,導致轉(zhuǎn)發(fā)概率的計算不準確[10],因此,在一定程度上會影響到路由網(wǎng)絡(luò)的時效性和穩(wěn)定性.

Fig.2 Comparison of routing path selection圖2 路由路徑選擇對比圖

在文獻[11]中提出了一種基于計數(shù)的轉(zhuǎn)發(fā)方案來抑制路由風暴,它在每次要轉(zhuǎn)發(fā)RREQ 分組前開始等待時間來避免所有節(jié)點均廣播轉(zhuǎn)發(fā),但是該方案明顯提高了數(shù)據(jù)傳輸?shù)臅r延.Kim 等人在文獻[12]中提出一種基于鏈路質(zhì)量LQI(link quality indicator)的改進協(xié)議,通過設(shè)定鏈路質(zhì)量的閾值來界定一條鏈路的好壞.因為鏈路的選擇是基于優(yōu)秀鏈路質(zhì)量最優(yōu)的一條,因此改進的協(xié)議能夠提高數(shù)據(jù)傳輸?shù)姆€(wěn)定性[13].由于L-AODV 沒有考慮網(wǎng)絡(luò)節(jié)點運動的情況,從而選擇不穩(wěn)定的路由路徑導致數(shù)據(jù)傳輸時延增大.Mohammed 等人在文獻[14]中提出一種基于能量的改進協(xié)議,結(jié)合路徑的能量消耗以及節(jié)點的最低能耗來設(shè)定能量閾值,避免了節(jié)點成為熱點而死亡,從而導致鏈路中斷.但是因為在路徑選擇中過度考慮能量導致鏈路的質(zhì)量不高,數(shù)據(jù)傳輸穩(wěn)定性較低.文獻[15]提出基于跨層機制以及能量約束來選擇路由路徑,結(jié)合MAC 層的信號鏈路強度和節(jié)點能量因素來平衡網(wǎng)絡(luò)中的能量消耗,選擇一條最優(yōu)路徑以避免網(wǎng)絡(luò)節(jié)點出現(xiàn)熱點現(xiàn)象,但是并未考慮到網(wǎng)絡(luò)拓撲變化的情況會影響路由的時效性.

2 協(xié)議改進

2.1 基于局部鄰居的動態(tài)概率轉(zhuǎn)發(fā)

如圖3 所示,A、B兩節(jié)點間相距d,節(jié)點通信半徑為R(R>d),當B接收到A轉(zhuǎn)發(fā)的數(shù)據(jù)后,如果繼續(xù)轉(zhuǎn)發(fā)該數(shù)據(jù),則可增加的有效覆蓋區(qū)域為圖中陰影部分面積.

Fig.3 Forwarding model diagram圖3 轉(zhuǎn)發(fā)模型圖

每個節(jié)點所能覆蓋的有效傳播范圍是INCR(d),當節(jié)點B也轉(zhuǎn)發(fā)該數(shù)據(jù)時,增加的陰影部分區(qū)域為

其中,A、B兩節(jié)點均能傳輸?shù)降膮^(qū)域:

在實際傳輸過程中,當兩節(jié)點間距離剛好為節(jié)點傳輸半徑R時,兩節(jié)點間重復的傳播區(qū)域最小,轉(zhuǎn)發(fā)增加的有效傳播區(qū)域最大,此時,R=d,INCR(d)最大為

由公式(2)可知,節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)之后能夠增加的有效傳播區(qū)域最大為原區(qū)域的61%.該區(qū)域隨著節(jié)點間距離的減小而降低,而增加的平均區(qū)域計算公式如下:

由上述分析可得,數(shù)據(jù)在轉(zhuǎn)發(fā)之后能夠增加的有效傳播區(qū)域平均值為41%.這是在節(jié)點只有一個鄰居的情況下所得,而在實際應用中,一個節(jié)點擁有多個鄰居節(jié)點,因此,在轉(zhuǎn)發(fā)過程中增加的有效傳播區(qū)域?qū)⒏賉16].本文在AODV 路由查找階段提出一種基于動態(tài)概率的路由轉(zhuǎn)發(fā)模型,該概率公式通過本節(jié)點的鄰居數(shù)量與上級節(jié)點的鄰居數(shù)量、網(wǎng)絡(luò)平均鄰居數(shù)量之間的比較,計算選擇不同的轉(zhuǎn)發(fā)概率,使RREQ 分組可依據(jù)網(wǎng)絡(luò)的疏密程度以動態(tài)概率轉(zhuǎn)發(fā),極大地改善了廣播風暴問題,也提高了網(wǎng)絡(luò)可用帶寬.現(xiàn)將本文中參數(shù)定義說明如下.

1.網(wǎng)絡(luò)平均鄰居數(shù)量avgCnt:網(wǎng)絡(luò)中所有節(jié)點的鄰居節(jié)點數(shù)量之和與網(wǎng)絡(luò)節(jié)點數(shù)量的比值:

N為網(wǎng)絡(luò)節(jié)點數(shù)量,nbCnti為第i個節(jié)點的鄰居節(jié)點數(shù)量;

2.本地鄰居數(shù)量nbCnt:當前節(jié)點的鄰居節(jié)點數(shù)量;

3.上級節(jié)點:本地鄰居節(jié)點中,將RREQ 轉(zhuǎn)發(fā)給當前節(jié)點的節(jié)點;

4.上級節(jié)點鄰居數(shù)量pnbCnt:上級節(jié)點的鄰居節(jié)點數(shù)量;

5.轉(zhuǎn)發(fā)概率P:節(jié)點收到RREQ 分組后,轉(zhuǎn)發(fā)該分組的概率:

當節(jié)點收到RREQ 分組后,將自身鄰居數(shù)量和上級節(jié)點鄰居數(shù)量以及網(wǎng)絡(luò)平均鄰居數(shù)量進行比較,以選擇不同的轉(zhuǎn)發(fā)概率計算公式,其中,P1>P3>P2>P4.

(1) 當本地鄰居數(shù)量<上級節(jié)點鄰居數(shù)量,并且本地鄰居數(shù)量<網(wǎng)絡(luò)平均鄰居數(shù)量時,表明當前節(jié)點通信范圍相對于上級節(jié)點以及整個網(wǎng)絡(luò)來說處于一個較稀疏的路由網(wǎng)絡(luò)中,因此需要以較大概率P1 來轉(zhuǎn)發(fā)RREQ,避免該分組在當前的小網(wǎng)絡(luò)被吸收(此時,分組數(shù)據(jù)傳遞不出去);

(2) 當本地鄰居數(shù)量<上級節(jié)點鄰居數(shù)量,并且本地鄰居數(shù)量≥網(wǎng)絡(luò)平均鄰居數(shù)量時,表明當前節(jié)點通信范圍只是相對于上級節(jié)點而言所處的網(wǎng)絡(luò)較稀疏,此時只需以一般隨機概率P2 轉(zhuǎn)發(fā)RREQ.上級節(jié)點也是相對于整個網(wǎng)絡(luò)而言處在稠密網(wǎng)絡(luò)中,其周圍將會有很多節(jié)點已接收到RREQ 分組并已經(jīng)轉(zhuǎn)發(fā);

(3) 當本地鄰居數(shù)量≥上級節(jié)點鄰居數(shù)量,并且本地鄰居數(shù)量<網(wǎng)絡(luò)平均鄰居數(shù)量時,表明當前節(jié)點通信范圍相對于整個網(wǎng)絡(luò)而言處于稀疏狀態(tài),相對于上級節(jié)點而言處于稠密狀態(tài),因此需要以概率P3 轉(zhuǎn)發(fā)RREQ.此時,上級節(jié)點相對于全網(wǎng)處于稀疏狀態(tài),所以,當前節(jié)點的分組會被吸收,可以適當降低轉(zhuǎn)發(fā)概率;

(4) 當本地鄰居數(shù)量≥上級節(jié)點鄰居數(shù)量,并且本地鄰居數(shù)量≥網(wǎng)絡(luò)平均鄰居數(shù)量時,表明當前節(jié)點通信范圍相對于上級節(jié)點以及整個網(wǎng)絡(luò)處于一個較稠密的小網(wǎng)絡(luò)中,因此以小概率P4 來轉(zhuǎn)發(fā)RREQ.因為當前節(jié)點所處的網(wǎng)絡(luò)較為稠密,其鄰居節(jié)點已有很大幾率接收到RREQ 分組并已經(jīng)轉(zhuǎn)發(fā),當前節(jié)點的分組被吸收.

概率轉(zhuǎn)發(fā)公式中的ifc為影響因子,經(jīng)過多次實驗,最終選定該值為0.5.該值用來平衡部分節(jié)點周圍分布不均勻的情況,當節(jié)點鄰居節(jié)點較少時,影響因子可使得函數(shù)y=e-x的指數(shù)部分變小從而增大轉(zhuǎn)發(fā)概率.在概率轉(zhuǎn)發(fā)公式中,結(jié)合網(wǎng)絡(luò)平均鄰居節(jié)點和上級節(jié)點鄰居節(jié)點數(shù)量,能夠充分反映整個網(wǎng)絡(luò)以及單個節(jié)點通信范圍內(nèi)的節(jié)點密度[17],使每個節(jié)點能夠更加智能地依據(jù)自身和周圍的節(jié)點密度調(diào)節(jié)轉(zhuǎn)發(fā)概率.

2.2 基于鏈路權(quán)值的路由選擇

在Ad Hoc 網(wǎng)絡(luò)中,節(jié)點的移動會導致網(wǎng)絡(luò)拓撲的變化.為了適應移動自組織網(wǎng)絡(luò)的網(wǎng)絡(luò)性能,在保證數(shù)據(jù)分組投遞率的同時,盡量降低數(shù)據(jù)傳輸?shù)臅r延.本文利用跨層設(shè)計思想,將物理層和MAC 層的LQI 信息傳遞給網(wǎng)絡(luò)層,并結(jié)合節(jié)點移動速度提出鏈路權(quán)值,利用鏈路權(quán)值來衡量路由路徑的動態(tài)穩(wěn)定性,依據(jù)最小權(quán)值選擇最佳路由,以提高路由的時效性,避免了頻繁的路由斷裂和查找,降低了數(shù)據(jù)傳輸時延和丟包率.現(xiàn)將相關(guān)定義說明如下.

1.鄰居平均速度avgSpd:當前節(jié)點所有鄰居節(jié)點的平均速度:

其中,k表示節(jié)點的鄰居節(jié)點數(shù)量,vn表示第n個鄰居節(jié)點的速度.

2.鏈路信號系數(shù)lk:通信范圍內(nèi)兩節(jié)點間LQI 的比例系數(shù):

其中,LQI(i,j)為i,j兩節(jié)點間的LQI 值.兩節(jié)點間鏈路信號強度越高,lk值越小.

3.速度權(quán)值spdWgt:當前節(jié)點速度與鄰居平均速度比值(取小于等于1 的比):

其中,ispeed表示當前節(jié)點i的速度,avg_nb_speedi表示i節(jié)點的鄰居平均速度.

本文中,速度權(quán)值取值為小于等于1.當權(quán)值大于1 時,將權(quán)值置為2,表明當前節(jié)點相對于周圍鄰居節(jié)點運動過快.權(quán)值越小,表明當前節(jié)點相對于周圍鄰居節(jié)點運動緩慢,以此節(jié)點作為路由,可以增加路由鏈路的時效性;權(quán)值越大,表明當前節(jié)點相對于周圍鄰居節(jié)點運動過快,此時,可能由于節(jié)點運動過快而導致路由鏈路過早失效.

4.鏈路權(quán)值LP:路由路徑選擇的依據(jù),權(quán)值最小的鏈路為當前最優(yōu)路由:

其中,spdWgti表示節(jié)點i的速度權(quán)值,lki表示節(jié)點i與上級節(jié)點的鏈路信號系數(shù).

鏈路LP 值決定最終路由路徑的選取,LP 值最小,表明當前路徑速度權(quán)值和鏈接強度之和最小,且速度權(quán)值為所有路徑中的較小值,說明所選路徑中的節(jié)點在該節(jié)點的鄰居網(wǎng)絡(luò)鏈路中信號強度較高,穩(wěn)定性較好.

2.3 改進算法流程

節(jié)點在上電工作后,開始周期性地發(fā)送HELLO 消息,通過HELLO 消息獲取鄰居節(jié)點數(shù)量的相關(guān)信息;當節(jié)點開始路由發(fā)現(xiàn)或者接收到RREQ 分組時,首先判斷是否丟棄該分組,若不丟棄,則判斷是否建立到源節(jié)點的反向路由;在節(jié)點再次轉(zhuǎn)發(fā)此RREQ 之前,通過計算轉(zhuǎn)發(fā)概率來決定是否轉(zhuǎn)發(fā)該RREQ,若需要轉(zhuǎn)發(fā),則再次計算本節(jié)點與上級節(jié)點間的LP 值,根據(jù)每個不同路徑的RREQ 分組中的LP 值選擇最優(yōu)路徑,LP 最小的路徑則為當前路由發(fā)現(xiàn)的最優(yōu)路徑并返回RREP 消息分組.

由于改進方法中需由節(jié)點獲取鄰居節(jié)點數(shù)量、速度等信息,為方便數(shù)據(jù)結(jié)構(gòu)的設(shè)計,直接利用協(xié)議的HELLO 消息機制,由每個節(jié)點獲取鄰居節(jié)點的相關(guān)信息,因此,需重新設(shè)計HELLO 消息格式,具體設(shè)計見表1.

在路由查找階段,每個節(jié)點接收到RREQ 分組后,均要計算源到當前節(jié)點的總LP,以及上級節(jié)點和當前節(jié)點的LP 值并加以存儲,以便RREP 消息傳輸時獲得此值.因此,需要在RREQ 消息格式中添加相應字段,修改后的RREQ 消息格式見表2.

Table 1 Modified HELLO message format表1 修改后HELLO 消息格式

Table 2 Modified RREQ message format表2 修改后RREQ 消息格式

因為路由路徑的選擇依據(jù)是LP 值,因此在路由表條目中需要增加字段路由鏈路,當有新的路徑需要更新時,比較路由表條目中的LP 值與新路徑的LP 值來更新路徑.當源節(jié)點接收到RREP 分組后,通過比較每條路徑中的LP 值,選擇LP 值最小的路徑作為源節(jié)點到目的節(jié)點的最優(yōu)路徑,存入路由表條目中.

因為路由路徑的選擇依據(jù)是LP 值,在路由表條目中需要增加字段和路由鏈路,當有新的路徑需要更新時,比較路由表條目中的LP 值與新路徑的LP 值來更新路徑.若接收到的數(shù)據(jù)類型是RREQ、RREP、RRER、HELLO分組類型,則表明接收的是AODV 協(xié)議類型分組.此時將分組中的TTL 字段減1,然后對分組進行響應.根據(jù)不同的數(shù)據(jù)包類型調(diào)用不同的處理函數(shù),主要分為以下幾種情況.

(1) 如果數(shù)據(jù)類型為RREQ 分組,則主要解析處理RREQ 分組并判斷是否繼續(xù)轉(zhuǎn)發(fā);

(2) 通過調(diào)用路由請求函數(shù)來處理接收RREP 分組,函數(shù)輸出有效值是對路由請求的響應.表明已經(jīng)找到數(shù)據(jù)傳輸?shù)哪康墓?jié)點,并且已經(jīng)創(chuàng)建了反向的路由鏈路;

(3) 處理接收到的RRER 分組,通過相關(guān)函數(shù)對當前使用路由做出錯誤響應,并對路由路徑進行檢測維護.

改進協(xié)議路由請求工作流程如圖4 所示.

在通信時選擇路由開銷小、節(jié)點間鏈路失效時間長的路由,可以提高鏈路的穩(wěn)定性,延長網(wǎng)絡(luò)的壽命.鄰居節(jié)點數(shù)量在一定程度上反映了網(wǎng)絡(luò)的狀況.路由協(xié)議能夠選擇較為穩(wěn)定的鏈路進行數(shù)據(jù)傳輸,提高了分組投遞率,降低了端到端平均時延與歸一化路由開銷,進而提高了路由協(xié)議的性能,將最優(yōu)路由選擇問題轉(zhuǎn)化為路由開銷C、節(jié)點平均鄰居節(jié)點數(shù)N和鏈路失效時間T最優(yōu)的問題,上述3 個條件轉(zhuǎn)化為權(quán)值計算,表示為

網(wǎng)絡(luò)中,鏈路上節(jié)點能量的大小及能量消耗的快慢對鏈路質(zhì)量起著決定性作用.鏈路越短,新增協(xié)議字段的長度和緩沖數(shù)據(jù)包越少,節(jié)點能量消耗越小,數(shù)據(jù)傳輸時延越小.所以,路由開銷可用公式表示為

其中,h表示跳數(shù),q表示鏈路中節(jié)點緩存數(shù)據(jù)包的最大數(shù)目,e表示鏈路中節(jié)點剩余的最小能量值.由公式(11)可知:路由開銷越小,鏈路的生存時間越長[18].

本文對協(xié)議的改進主要表現(xiàn)在如下兩個方面:第1,在路由請求階段,當節(jié)點收到其他節(jié)點轉(zhuǎn)發(fā)的RREQ 分組時,依據(jù)上級節(jié)點鄰居數(shù)量和本地鄰居數(shù)量的大小,選擇不同的轉(zhuǎn)發(fā)概率公式,以避免路由廣播風暴影響網(wǎng)絡(luò)性能,同時能夠降低傳輸時延;第2,在路由路徑選擇時,利用鏈路權(quán)值來決定當前網(wǎng)絡(luò)拓撲下的最優(yōu)路徑,使得在網(wǎng)絡(luò)拓撲變化的情況下路徑相對穩(wěn)定,減少路由斷裂情況以避免多次路由查找,降低了傳輸時延,提高了分組投遞率.

Fig.4 Routing request workflow diagram圖4 路由請求工作流程圖

3 仿真結(jié)果及分析

3.1 仿真環(huán)境

本文利用網(wǎng)絡(luò)仿真軟件NS2 分別對AODV 路由協(xié)議、本文改進路由協(xié)議(MOD-AODV)以及文獻[7,8]中提出的改進協(xié)議I-AODV-SE 和ND-AODV 進行了仿真模擬,實驗仿真場景主要分為兩種.

場景1.節(jié)點數(shù)量不變,節(jié)點平均移動速度在改變.最大連接數(shù)為10,模擬時間為100s,停留時間為0s,數(shù)據(jù)類型為cbr,發(fā)包速度為4 包/秒,仿真場景為1000m×1000m,節(jié)點最小移動速度為1m/s,最大移動速度分別為10、20、30、40、50(m/s).節(jié)點最大移動速度在改變(即網(wǎng)絡(luò)平均速度發(fā)生改變),根據(jù)節(jié)點數(shù)量分別為40、60、80、100,比較不同平均移動速度下的時延、分組投遞率、歸一化路由開銷;

場景2.節(jié)點平均移動速度不變,節(jié)點數(shù)量在改變.最大連接數(shù)為10,模擬時間為100s,停留時間為0s,數(shù)據(jù)類型為cbr,發(fā)包速度為4 包/秒,仿真場景大小為1000m×1000m.節(jié)點個數(shù)為20、40、60、80、100,最大移動速度分別為30m/s、40m/s、50m/s,比較不同節(jié)點數(shù)目下時延、分組投遞率、歸一化路由開銷;

本文對每個場景進行30 次模擬仿真實驗,將收集到的數(shù)據(jù)進行統(tǒng)計平均,然后繪圖.為了繪圖方便,在節(jié)點平均速度變化的圖示中,橫坐標為節(jié)點的最大移動速度,節(jié)點最大移動速度的改變即是網(wǎng)絡(luò)平均移動速度的改變.其中,I-AODV-SE 和ND-AODV 分別是文獻[7,8]中的算法,MOD-AODV 是本文改進的算法,AODV 為原始協(xié)議.協(xié)議仿真參數(shù)設(shè)置見表3.

Table 3 Protocol parameter type settings表3 協(xié)議仿真參數(shù)類型設(shè)置

3.2 性能評價指標

為了能夠全面分析改進前后AODV 協(xié)議的性能,本文從以下3 個性能指標的角度進行了分析.

(1) 端到端傳輸時延:所有數(shù)據(jù)分組從源節(jié)點發(fā)出到目的節(jié)點正確接收所用時間的平均值,亦即數(shù)據(jù)包從源節(jié)點發(fā)出到目的節(jié)點接收之間的平均時間差,反映了路由的有效性;

(2) 數(shù)據(jù)分組投遞率:節(jié)點接收到的總分組個數(shù)與發(fā)送出去的總分組個數(shù)的比值,反映了網(wǎng)絡(luò)傳輸?shù)目煽啃?分組投遞率越大,可靠性越高.數(shù)據(jù)分組投遞率是衡量網(wǎng)絡(luò)丟包率的重要指標,反映了網(wǎng)絡(luò)性能的好壞;

(3) 歸一化路由開銷:每發(fā)送一個數(shù)據(jù)分組所需要的路由分組數(shù),其中,路由分組每一跳的傳輸均認為是一個新的路由分組,反映了網(wǎng)絡(luò)的擁塞程度和路由效率[19].對于Ad hoc 網(wǎng)絡(luò)中的路由協(xié)議,路由開銷越低越好.

3.3 仿真結(jié)果分析

圖5(a)～圖5(d)所示為節(jié)點數(shù)量分別為40、60、80、100 時,不同節(jié)點速度下的端到端時延.

圖5 中,為了繪圖美觀,將圖中橫坐標改為節(jié)點最大移動速度.由圖5 可以看出:隨著網(wǎng)絡(luò)平均速度的增加,3種協(xié)議的傳輸時延總體上呈上升趨勢.AODV 協(xié)議傳輸時延較高.兩種對比協(xié)議I-AODV-SE 和ND-AODV 在節(jié)點密集與稀疏、移動速度不同時各有優(yōu)劣:在節(jié)點運動速度低且數(shù)目較少時,I-AODV-SE 算法表現(xiàn)出較好的時延特性;而在節(jié)點運動速度高且數(shù)目較多時,ND-AODV 算法有較好的時延特性.MOD-AODV 變化趨勢比另外兩種協(xié)議平緩.這是因為,隨著節(jié)點移動速度的增加,網(wǎng)絡(luò)拓撲變化逐漸加快,MOD-AODV 可通過節(jié)點的運動快速獲取網(wǎng)絡(luò)疏密情況以及上級節(jié)點通信范圍內(nèi)網(wǎng)絡(luò)的疏密度以動態(tài)計算轉(zhuǎn)發(fā)概率,極大地減少了RREQ 的轉(zhuǎn)發(fā),提高了網(wǎng)絡(luò)可利用帶寬,減少了傳輸時延.同時,在路由建立的初始通過鏈路權(quán)值來選擇路由,使得路由路徑在快速變化的拓撲環(huán)境下相對穩(wěn)定,減少了路由查找的次數(shù),降低了數(shù)據(jù)傳輸時延.

I-AODV-SE 協(xié)議在節(jié)點運動中獲取鄰居節(jié)點情況,在轉(zhuǎn)發(fā)RREQ 分組時,根據(jù)節(jié)點計算得出的概率進行轉(zhuǎn)發(fā).該協(xié)議在延時上相對經(jīng)典AODV 有所降低,但是隨著節(jié)點速度的不斷增加,它所獲取的網(wǎng)絡(luò)情況是不連續(xù)的,致使網(wǎng)絡(luò)可用帶寬沒有較大的提升.對于ND-AODV 路由協(xié)議,建立路由關(guān)系依據(jù)定位信息確定鏈路權(quán)值,因此在低速節(jié)點情況下建立的鏈路選擇范圍較大,增加了網(wǎng)絡(luò)風暴的可能性.本文算法MOD-AODV 由路徑選擇時利用鏈路權(quán)值來決定當前網(wǎng)絡(luò)拓撲下的最優(yōu)路徑,使得在網(wǎng)絡(luò)拓撲變化的情況下路徑相對穩(wěn)定,在節(jié)點密集和節(jié)點相對運動速度較大時,MOD-AODV 改進協(xié)議呈現(xiàn)于端到端時延的優(yōu)勢更加明顯.由圖5(a)～圖5(d)可以看出:即使網(wǎng)絡(luò)節(jié)點的數(shù)量有所增加,改進協(xié)議在傳輸時延上仍然能夠表現(xiàn)出一定的優(yōu)勢,表明改進協(xié)議不僅能夠適應網(wǎng)絡(luò)拓撲的快速變化,在網(wǎng)絡(luò)節(jié)點數(shù)量發(fā)生變化的情況下也有良好的表現(xiàn).

圖6(a)～圖6(d)所示為節(jié)點數(shù)量分別為40、60、80、100 時,不同節(jié)點平均速度下的數(shù)據(jù)分組投遞率.為了繪圖美觀,將圖中橫坐標改為節(jié)點最大移動速度.

Fig.5 End-to-end delays at different average speeds圖5 不同平均速度下的端到端時延

Fig.6 Packet delivery rate at different average speeds圖6 不同平均速度下的分組投遞率

由圖6 可以看出:隨著節(jié)點速度的增加,3 種協(xié)議的分組投遞率總體呈下降趨勢.分組投遞率中,MOD-AODV最高,AODV 最低,I-AODV-SE 和ND-AODV 兩種改進協(xié)議在不同場景下的投遞率各有不同.

隨著節(jié)點運動速度的增加,分組投遞率呈下降趨勢.因為節(jié)點速度增大,網(wǎng)絡(luò)拓撲變化頻繁,鏈路斷裂的幾率變大,網(wǎng)絡(luò)中RREQ 報文增多,帶寬占用率加大,導致ND-AODV 分組投遞率下降.I-AODV-SE 協(xié)議在網(wǎng)絡(luò)內(nèi)傳輸?shù)臄?shù)據(jù)包數(shù)也在增多,它們均在占用網(wǎng)絡(luò)資源,導致資源出現(xiàn)競爭.由于MOD-AODV 利用上級鄰居和本級鄰居來計算轉(zhuǎn)發(fā)概率,因此在節(jié)點相對速度較快的情況下對網(wǎng)絡(luò)稠密的判斷影響不大,更有效地抑制了廣播風暴,提高了網(wǎng)絡(luò)帶寬以增大分組投遞率.AODV 依據(jù)最短跳數(shù)選擇路由,致使在節(jié)點運動速度增加的過程中鏈路中斷的概率增大,而使路由失效,因此數(shù)據(jù)傳輸不夠穩(wěn)定,分組投遞率降低.同樣地,由圖6(a)～圖6(d)的對比可以看出,改進協(xié)議在分組投遞率上也能適應網(wǎng)絡(luò)節(jié)點數(shù)量的變化.

圖7(a)～圖7(d)所示為節(jié)點數(shù)量分別為40、60、80、100 時,不同節(jié)點平均速度下的歸一化路由開銷.為了繪圖美觀,將圖中橫坐標改為節(jié)點最大移動速度.由圖7 可以看出:隨著節(jié)點移動速度的增加,3 種協(xié)議的路由開銷呈上升趨勢,其中,MOD-AODV 在路由開銷上只是略低于AODV;總體來看,兩種協(xié)議的路由開銷基本相近.這是因為,MOD-AODV 在節(jié)點運動過程中能夠建立相對穩(wěn)定的路由,避免了頻繁的路由查找,降低了路由查找數(shù)據(jù)傳遞所需的開銷.協(xié)議在路由發(fā)起部分根據(jù)節(jié)點穩(wěn)定度判決結(jié)果決定是否轉(zhuǎn)發(fā),限制了RREQ 消息在網(wǎng)絡(luò)中的洪泛,因此,MOD-AODV 路由協(xié)議的歸一化路由開銷低于AODV.

Fig.7 Normalized route overhead at different average speeds圖7 不同平均速度下的歸一化路由開銷

但是,在路由建立的過程中,因為涉及到節(jié)點相關(guān)信息的傳遞,所以相對于AODV 來說,額外增加了在路由查找階段所需的分組數(shù)量,節(jié)省的路由查找次數(shù)的分組用在路由查找階段額外增加的分組上,因此整體路由開銷并沒有降低很多.而I-AODV-S 在路由查找階段也涉及到要獲取信息,只需要額外增加路由分組數(shù)量而沒有在其他地方來平衡這種額外的增加.同時,I-AODV-SE 協(xié)議通過優(yōu)化路徑,在估計路徑權(quán)重時也加大了能量消耗,即增加了路由成本,因此路由開銷較另外3 種協(xié)議要高,尤其是在節(jié)點相對速度較大時,開銷對比更明顯.結(jié)合圖6 所示MOD-AODV 在不增加額外路由開銷的前提下,有效地提高了數(shù)據(jù)的分組投遞率,降低了端到端時延,間接表明MOD-AODV 協(xié)議在性能上的優(yōu)勢.

圖8(a)～圖8(c)給出了節(jié)點最大移動速度分別為30m/s、40m/s、50m/s 時,不同節(jié)點數(shù)目下的端到端時延.由圖8 可以看出:當節(jié)點數(shù)量為20 時,4 種協(xié)議的延時都相對較高;之后,隨著節(jié)點數(shù)量的增加,端到端延時整體呈上升趨勢.其中,AODV 延時最高,MOD-AODV 延時相對較低.這是因為,當節(jié)點數(shù)量較少(數(shù)量為20)時,網(wǎng)絡(luò)處于較稀疏(相對于1000m×1000m 的場景)狀態(tài),4 種協(xié)議均會因為網(wǎng)絡(luò)中節(jié)點彼此距離太遠導致數(shù)據(jù)傳輸不穩(wěn)定,此時,傳輸時延較大.在網(wǎng)絡(luò)節(jié)點數(shù)量增加的過程中,AODV 因為采用了廣播機制,致使路由請求時間過長而增大了數(shù)據(jù)傳輸時延.

Fig.8 End-to-end delay with different number of nodes圖8 不同節(jié)點數(shù)量下的端到端延時

ND-AODV 通過計算鄰居節(jié)點的數(shù)量來選擇概率轉(zhuǎn)發(fā),能夠縮短路由請求的時間,降低了數(shù)據(jù)傳輸?shù)臅r延;但沒有考慮到當前節(jié)點與上級節(jié)點的密度關(guān)系,使得計算的轉(zhuǎn)發(fā)概率過大,在轉(zhuǎn)發(fā)過程中仍存在很多不必要的重傳數(shù)據(jù).兩種協(xié)議依據(jù)跳數(shù)選擇路由,降低了該路由的時效性,需要再次查找路由而增大傳輸時延.I-AODV-SE協(xié)議考慮了網(wǎng)絡(luò)拓撲的穩(wěn)定性以及節(jié)點能量信息,并計算了基于路徑穩(wěn)定和路徑能量的路徑權(quán)重值,選擇權(quán)重小的路徑傳輸數(shù)據(jù)包,因此,節(jié)點數(shù)目對端到端時延影響相對較小.MOD-AODV 在計算轉(zhuǎn)發(fā)概率中,能夠結(jié)合當前節(jié)點和目前所在區(qū)域的節(jié)點密度以及上級節(jié)點所在區(qū)域的節(jié)點密度,能夠更全面地表示局部網(wǎng)絡(luò)的稠密,相比ND-AODV,可更大程度地降低不必要的重傳,縮短了路由查找的時間,且建立的路由鏈路較為穩(wěn)定,因此,端到端延時比另外兩種改進協(xié)議要低.圖8(a)～圖8(c)的對比也表明,MOD-AODV 在不同移動速度場景下的傳輸時延也優(yōu)于其他3 種協(xié)議.

圖9(a)～圖9(c)給出了節(jié)點最大移動速度分別為30m/s、40m/s、50m/s 時,不同節(jié)點數(shù)目下的分組投遞率.由圖9 可以看出,3 種協(xié)議的分組投遞率隨著節(jié)點數(shù)量的增加呈上升趨勢.AODV 協(xié)議分組投遞率最低,這是因為,隨著節(jié)點的數(shù)量的增加,路由網(wǎng)絡(luò)變得稠密,節(jié)點間鏈路之間的信號質(zhì)量增加,傳輸路徑更加穩(wěn)定,使得網(wǎng)絡(luò)分組投遞率有所增長.而ND-AODV 雖然利用網(wǎng)絡(luò)鄰居計算了轉(zhuǎn)發(fā)概率,一定程度上減少了RREQ 分組的轉(zhuǎn)發(fā),釋放了部分可利用帶寬,但是隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增加,網(wǎng)絡(luò)稠密度更高且節(jié)點處于運動狀態(tài),導致節(jié)點獲取的網(wǎng)絡(luò)鄰居頻繁地發(fā)生變化,使得轉(zhuǎn)發(fā)概率的計算不夠準確以及在節(jié)點運動相對速度大時導致計算失敗,從而降低了數(shù)據(jù)分組投遞率.

I-AODV-SE 擇優(yōu)選擇權(quán)重小的路徑傳輸數(shù)據(jù)包,提高了網(wǎng)絡(luò)生存時間,能夠有效地提高數(shù)據(jù)包傳輸率,避免了因節(jié)點能量問題而降低了數(shù)據(jù)包的丟包率,相對于AODV 協(xié)議,投遞率提高了不少.而MOD-AODV 利用上級的鄰居節(jié)點和本級節(jié)點動態(tài)地計算轉(zhuǎn)發(fā)概率,能夠連續(xù)、動態(tài)地獲取網(wǎng)絡(luò)的實際情況以調(diào)整轉(zhuǎn)發(fā)概率,盡管節(jié)點的運動導致網(wǎng)絡(luò)鄰居頻繁發(fā)生變化,但是考慮到MOD-AODV 利用局部連續(xù)的思想,獲得的鄰居信息不是孤立的,因此不會出現(xiàn)突變的情況,路由的時效性也較高,使得網(wǎng)絡(luò)的稠密度變化對節(jié)點的數(shù)據(jù)傳輸和路由查找不會帶來明顯的影響,因此分組投遞率較另外兩種協(xié)議要高.同樣地,圖9(a)～圖9(c)也表明,MOD-AODV 在不同運動場景下對數(shù)據(jù)分組投遞率有一定的改善.

Fig.9 Packet delivery rate at different number of nodes圖9 不同節(jié)點數(shù)量下的分組投遞率

圖10(a)～圖10(c)給出了節(jié)點最大移動速度分別為30m/s、40m/s、50m/s 時,不同節(jié)點數(shù)目下的歸一化路由開銷.由圖10 可以看出:4 種協(xié)議的路由開銷隨著節(jié)點數(shù)量的增加而增加.這是因為,隨著節(jié)點數(shù)量的增加,網(wǎng)絡(luò)建立的從源節(jié)點到目的節(jié)點的路由會增多,傳輸?shù)穆酚煞纸M也就更多,因此增大了網(wǎng)絡(luò)的路由開銷.由圖10 還可以看出:ND-AODV 和AODV 在整體上路由開銷很相近,MOD-AODV 則低于這兩種協(xié)議.這是因為,隨著節(jié)點數(shù)量的增加,ND-AODV 利用概率轉(zhuǎn)發(fā)減少的RREQ 分組相對就會增加,雖然額外增加了每次查找中的分組數(shù)量,但兩者隨著網(wǎng)絡(luò)節(jié)點數(shù)量的不斷增大而趨于平衡,因此兩者路由開銷接近.從文獻[8]可以看出,I-AODV-SE協(xié)議生存時間提高得并不多:一方面,I-AODV-SE 協(xié)議通過優(yōu)化路徑,避免了能量空洞問題,降低了能量消耗率;另一方面,I-AODV-SE 在估計路徑權(quán)重時也加大了能量消耗,即增加了路由成本,并且在節(jié)點稠密和節(jié)點運動速度大時更加明顯.

MOD-AODV 在轉(zhuǎn)發(fā)RREQ 分組過程中因為利用局部鄰居節(jié)點,使得計算的轉(zhuǎn)發(fā)概率連續(xù)且相對NDAODV 更準確,更大程度地降低了RREQ 的重復轉(zhuǎn)發(fā),降低了路由開銷.同時,相比于AODV 協(xié)議,建立的路由更穩(wěn)定,也減少了路由查找的次數(shù),降低了路由開銷.對比圖8、圖9 可以看出:MOD-AODV 在網(wǎng)絡(luò)節(jié)點平均移動速度基本不變的情況下,可在提高分組投遞率、降低傳輸時延的同時,有效地降低路由的開銷,也間接表明了MOD-AODV 在性能上優(yōu)于AODV 和另外兩種改進算法.

Fig.10 Normalized routing overhead for different number of nodes圖10 不同節(jié)點數(shù)量下的歸一化路由開銷

4 總結(jié)

在網(wǎng)絡(luò)節(jié)點密度較大的情況下,AODV 協(xié)議在路由發(fā)現(xiàn)階段易導致廣播風暴,影響網(wǎng)絡(luò)性能,增大數(shù)據(jù)傳輸時延.另一方面,在網(wǎng)絡(luò)拓撲處于動態(tài)變化、節(jié)點運動速度不一致的網(wǎng)絡(luò)中,AODV 協(xié)議的路由選擇方法導致鏈路的時效性較低,使得節(jié)點需要頻繁地進行路由的重新查找與建立,極大地增加了數(shù)據(jù)傳輸時延和丟包率.針對上述問題,本文提出了上級鄰居節(jié)點和本節(jié)點鄰居節(jié)點的概念,基于局部鄰居節(jié)點數(shù)量來計算轉(zhuǎn)發(fā)概率;并且,在路由建立階段利用跨層設(shè)計思想,結(jié)合物理層和MAC 層的LQI 值與網(wǎng)絡(luò)層節(jié)點速度提出了鏈路權(quán)值概念,依據(jù)鏈路權(quán)值選擇最佳路由,從而提高路由鏈路的時效性.仿真實驗結(jié)果表明:改進協(xié)議能夠更好地適應動態(tài)網(wǎng)絡(luò),并且提高了網(wǎng)絡(luò)性能,增大了路由鏈路的時效性,降低了數(shù)據(jù)傳輸時延和丟包率.雖然仿真結(jié)果表明:改進后的協(xié)議在平均端到端時延和丟包率的指標上均優(yōu)于AODV 路由協(xié)議,但在路由開銷上還未見明顯改善.后續(xù)工作將在保證網(wǎng)絡(luò)路由鏈路穩(wěn)定性的同時,針對降低路由開銷等問題繼續(xù)展開深入的研究.