基于局部鄰居節點和鏈路權值的改進AODV 路由協議*

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

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

Ad Hoc 網絡是一種無需基礎設施的多跳無線自組織移動網絡,廣泛應用于軍事和緊急救災等領域.在Ad Hoc 網絡中,當節點高速移動時,網絡拓撲結構變化很快,導致網絡鏈路狀態不穩定[1].此時,路由需要盡快重新找到能耗較低且狀態穩定的鏈路.同時,在路由失效時避免網絡中斷.

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

本文主要貢獻如下:

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

(2) 在快速變化的Ad Hoc 網絡中,針對AODV 協議建立的路由鏈路不穩定、從而影響網絡數據傳輸的問題,提出鏈路權值的概念.利用跨層設計思想,結合網絡層節點運動速度計算鏈路權值,并在路由選擇依據中,將鏈路權值作為標準,以提高路由鏈路的時效性;

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

1 相關工作

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

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

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

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

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

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

2 協議改進

2.1 基于局部鄰居的動態概率轉發

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

Fig.3 Forwarding model diagram圖3 轉發模型圖

每個節點所能覆蓋的有效傳播范圍是INCR(d),當節點B也轉發該數據時,增加的陰影部分區域為

其中,A、B兩節點均能傳輸到的區域:

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

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

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

1.網絡平均鄰居數量avgCnt:網絡中所有節點的鄰居節點數量之和與網絡節點數量的比值:

N為網絡節點數量,nbCnti為第i個節點的鄰居節點數量;

2.本地鄰居數量nbCnt:當前節點的鄰居節點數量;

3.上級節點:本地鄰居節點中,將RREQ 轉發給當前節點的節點;

4.上級節點鄰居數量pnbCnt:上級節點的鄰居節點數量;

5.轉發概率P:節點收到RREQ 分組后,轉發該分組的概率:

當節點收到RREQ 分組后,將自身鄰居數量和上級節點鄰居數量以及網絡平均鄰居數量進行比較,以選擇不同的轉發概率計算公式,其中,P1>P3>P2>P4.

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

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

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

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

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

2.2 基于鏈路權值的路由選擇

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

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

其中,k表示節點的鄰居節點數量,vn表示第n個鄰居節點的速度.

2.鏈路信號系數lk:通信范圍內兩節點間LQI 的比例系數:

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

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

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

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

4.鏈路權值LP:路由路徑選擇的依據,權值最小的鏈路為當前最優路由:

其中,spdWgti表示節點i的速度權值,lki表示節點i與上級節點的鏈路信號系數.

鏈路LP 值決定最終路由路徑的選取,LP 值最小,表明當前路徑速度權值和鏈接強度之和最小,且速度權值為所有路徑中的較小值,說明所選路徑中的節點在該節點的鄰居網絡鏈路中信號強度較高,穩定性較好.

2.3 改進算法流程

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

由于改進方法中需由節點獲取鄰居節點數量、速度等信息,為方便數據結構的設計,直接利用協議的HELLO 消息機制,由每個節點獲取鄰居節點的相關信息,因此,需重新設計HELLO 消息格式,具體設計見表1.

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

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

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

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

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

(1) 如果數據類型為RREQ 分組,則主要解析處理RREQ 分組并判斷是否繼續轉發;

(2) 通過調用路由請求函數來處理接收RREP 分組,函數輸出有效值是對路由請求的響應.表明已經找到數據傳輸的目的節點,并且已經創建了反向的路由鏈路;

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

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

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

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

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

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

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

3 仿真結果及分析

3.1 仿真環境

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

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

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

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

Table 3 Protocol parameter type settings表3 協議仿真參數類型設置

3.2 性能評價指標

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

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

(2) 數據分組投遞率:節點接收到的總分組個數與發送出去的總分組個數的比值,反映了網絡傳輸的可靠性.分組投遞率越大,可靠性越高.數據分組投遞率是衡量網絡丟包率的重要指標,反映了網絡性能的好壞;

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

3.3 仿真結果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結

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