基于網絡拓撲變化的改進型按需路由協議

胡 博,陳侃松,顧豪爽,阮玉龍

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

1 引 言

移動自組網網絡(mobile ad-hoc network,MANET)[1,2]中,節點可以自由移動,具有很高的靈活性,網絡拓撲的動態變化影響著通信鏈路的穩定性,導致網絡的丟包率與端到端時延的增加.因此,移動自組網的路由協議研究一直是無線傳感網絡領域的熱點問題.針對MANET網絡,路由協議按照發現機制可主要分為表驅動型和按需路由型.其中按需路由協議拓撲結構和路由緩存是按需建立的,由于其路由開銷及路由控制簡單等特點使得在動態變化的移動網絡中應用比按需路由協議更具優勢[3].

目前MANET常用的按需路由協議有AODV[4,5](ad hoc on-demand distance vector routing)和DSR[6,7](dynamic source routing).這兩種路由協議都是主要由路由發現與路由維護兩部分組成,且不需要周期性維護路由表,減小了網絡資源消耗.為了進一步優化路由分組投遞率與時延,研究人員提出了許多對于路由協議的改進方法,這些方法在網絡拓撲變化速度穩定的環境對網絡性能均有一定的改善,但對于隨機性更強的動態拓撲網絡需要進一步的研究.為此,本文設計了一種基于網絡拓撲變化速度并引入源路由的按需距離矢量路由算法(AODV Routing based on dynamic source,DSODV),改進后的協議通過分析網絡拓撲變化并采取不同的路由發現機制,有效的降低了網絡的端到端時延并提高了網絡分組投遞率.

2 相關工作

按需路由協議是在沒有路由緩存或者路由失效時才啟動,主要分為路由發現和路由維護兩個過程.其中,路由發現過程中源節點廣播RREQ分組,中間節點接收經檢測后轉發,到達目的節點后建立反向路由,目的節點或有到目的節點的中間節點產生路由應答RREP.路由維護過程是源節點檢測到目的節當前路由可用情況,當網絡拓撲變化導致鏈路中斷時,切換到另一條路由或重新發起路由發現[8].AODV與DSR的是基于此路由發現和維護機制的兩種應用較為廣泛的兩種路由協議.

2.1 AODV路由協議

AODV路由協議路由發現過程是用廣播的方式實現,在傳輸的過程中包含3類型的消息:路由請求(RREQ)、路由回復(RREP)和路由錯誤(RERR).若由數組分組需要傳輸,當前節點會檢查自己路由表是否有存到目的節點的路由,若不存在就會啟動路由發現過程.首先向其鄰居節點廣播RREQ,接收到請求分組的節點會檢測自身是否是目的節點或其路由表中是否有到目的節點的路由,若其不是目的節點且路由表不存在到目的節點的路由時該節點會繼續轉發RREQ分組,直至源節點到目的節點建立一條可以通信的路由.AODV的路由維護方式有鄰居發現和鏈路層反饋兩種:鄰居節點發現是通過周期性廣播HELLO報文,維護與鄰居互連;鏈路層反饋是在轉發數據分組過程中,鏈路層檢測到下一跳節點路由信息無法到達目的節點時,進行本地恢復或廣播RERR操作.

2.2 DSR路由協議

動態源路由協議DSR是一種低開銷的快速響應按需路由協議.源節點在要發送數據之前會先檢測路由表中是否存在到目的節點的路由,如果有,他會將此信息附加到數據分組首部,經過的中間節點會按照順序轉發,最終到達目的節點;如果沒有,源節點啟動路由發現,以泛洪的方式廣播RREQ分組,轉發此分組的節點將自己的地址附在RREQ中并繼續向下轉發,直至到目的節點,則回復RREP分組.路由發現過程中會使得源節點存儲了到達目的節點的多條路由,當鏈路發生中斷或路由信息過期,可以選擇另外的路由進行數據發送,使得DSR協議降低了路由信息維護方面的開銷.但同時因此也會存在問題,由于網絡拓撲的頻繁變化,緩存的路徑會出現頻繁失效的現象,此時需要啟動路由發現過程進行新路徑搜尋,消耗額外的網絡資源.

2.3 改進按需路由協議

目前的一些關于AODV路由協議改進的文獻,對AODV路由協議的研究和改進主要集中在幾個方面:

1)降低路由控制開銷

AODV路由發現過程是采用洪泛路由請求包進行的,而Ad hoc網絡可用的網絡資源十分有限,降低路由控制開銷可以減少對網絡資源的利用,提高數據傳輸效率.其中基于概率的方法最為簡單.

2)提高鏈路的穩定性

目前提高鏈路穩定性的算法大致分為兩類,一是改進路由修復過程,二是通過添加鏈路預測模型,提前將不穩定的鏈路切換到穩定性較好的鏈路上.

3)節能路由、功率控制、跨層優化等其他方面

節點節能技術一直是Ad hoc網絡技術研究的重點.傳統的路由優化方法局限在網絡層單層協議上,跨層優化方法可以使各協議層信息共享,從而使路由算法和網絡性能得到提升.

按需路由協議只在無路由或路由失效時啟動路由發現與維護,當網絡拓撲發生變化,路由發現與維護頻繁發生,網絡資源的開銷增大且穩定性降低.為了提高在移動自組網絡路由協議的性能,研究者們提出了很多改進.例如,李向麗等人[9]提出的ARB-AODV是通過檢測節點接收功率是否到達閾值判斷斷裂可能性,并在即將斷裂的鏈路添加節點來避免鏈路斷裂.Yadav等人[10]針對AODV提出了一種基于信號強度的鏈路可用性預測改進方法,節點會預測鏈路斷開時間,并基于這一信息提前進行路由恢復或新的路由發現,減少了端到端延時和數據包的丟失.孫友偉等人[11]提出的根據節點和鏈路穩定性的ND_AODV協議,該協議根據節點間距離設置轉發等待時間,并根據鄰節點數設置轉發概率等方式選擇穩定路由.杜海韜等人[12]通過獲取MAC與物理層獲取鏈路質量和節點能量信息選取最優路由路徑建立的路由協議LE-AODV,該協議通過對路徑的能量狀態和跳數限制的路徑選取機制,避免網絡中熱點的產生.李楠等人[13]提出了一種基于緩沖器DSR協議改進方案,其中引入形成時間路由、生存時間路由和剩余生存時間路由三種參數,并對路由緩沖和路由縮短方式作了改進.

3 改進路由協議DSAODV

DSR協議中的路由緩存機制相比于AODV協議不需要周期性地維護路由表,在網絡拓撲結構簡單的情形建立路由開銷較小[14].并且其混雜監聽技術使得源節點的路由表中存儲了多條到目的節點的路徑,當路由出錯等情況出現,可以根據需要更快的選擇一條到達目的節點的路由,使網絡具有更好的魯棒性.但隨著網絡結構越來越復雜,源節點會存儲更多的路徑信息,此時需要花費更多的資源在路由表中搜索需要的路由信息,并且緩存信息中存在錯誤或者過期路由信息的數量會更大,最終導致分組投遞率下降,端到端延時增加[15].DSAODV協議根據網絡拓撲復雜性,采用高效的路由發現維護策略,使節點合理的使用網絡帶寬資源,降低了通信中平均通信時延,提高了分組投遞率.

3.1 網絡拓撲變化速度系數

網絡拓撲的穩定性是決定本路由算法的重要因素,不同動態拓撲環境下的網絡調節路由發現和路由維護機制,選擇鏈路更加穩定的路徑進行數據傳輸,減少了一些不必要的路由切換.下面給出本文路由協議采用的基于網絡拓撲穩定性的計算方法.假設網絡節點運動狀態隨機,規定節點最大移動速度vmax,并且獲得當前節點的瞬時運動速度vc(t),節點上一刻的預測速度為v(t-1),則節點的速度預測更新公式按照式(1)進行:

v(t)=ρ·v(t-1)+(1-ρ)·vc(t)

(1)

式中vc(t)=rand·vmax,rand為范圍為(0,1)的隨機數,ρ是速度更新系數,取值范圍為(0,1),ρ值越大節點速度矢量越穩定.

假設兩節點i,j以各自的速度vi和vj在同一二維平面中運動,節點i往目的位置的運動方向角是θi,節點j往目的位置的運動方向角是θj,位置分別為(xi,yi)和(xj,yj),并且都相互處于對方的通信范圍內,兩節點通信范圍均為r,如圖1,則鏈路持續時間通過以下公式計算[16]:

(2)

其中,

a=vicosθi-vjcosθj

b=xi-xj

c=visinθi-vjsinθj

(3)

d=yi-yj

當vi=vj并且θi=θj時,Ti,j為無窮大.通過獲取路徑中任意相鄰兩點鏈路的鏈路預測持續時間,并且取最小值可以得到完整路徑的預測持續時間.假設在某一運動狀態時,兩節點的運動方向剛好相反,也就是θi與θj之差為π時,則節點i,j之間的最短鏈路預測持續時間為:

(4)

圖1 節點相對運動模型Fig.1 Relative motion model of node

這里取所有節點在t=0的最短鏈路預測持續時間與鏈路持續時間的比值作為定量選取不同路由發現機制的速度系數來間接反映整個網絡的拓撲變化程度,設定一個鏈路拓撲變化速度閾值:

vTH=γvmax

(5)

當節點速度小于vTH時,節點的路由構建過程加入源路由發現機制,并將路由發現過程中產生的多條路徑記錄在路由表;當節點速度大于vTH時,節點進行路由維護階段將采用周期更新機制.其中網絡拓撲變化速度系數γ為:

(6)

3.2 路由發現過程

提出的DSAODV中,當源節點要發送數據時,首先會檢測路由表中有無到達目的節點路由,若沒有或已經過期失效,此時需要發起新一輪的路由發現過程:

a)源節點生成一個路由請求數據分組RREQ廣播給它所有的鄰居節點,數據分組包括源節點IP、廣播ID、目的節點、跳數計數器的信息并附加當前運動狀態轉b).

b)鄰居節點接收到RREQ后會判斷是否接受過此信息,避免路徑重傳,轉c).

c)取當前節點的移動速度vk并與vTH比較,當移動速度大于速度閾值時,轉d),當移動速度小于速度閾值時,轉e).

d)中間節點根據RREQ記錄下到源節點的逆向路徑,并檢查自己ID是否與RREQ中目的節點一致,檢測路由表存儲有到達目的節點ID,若不符合條件繼續進行d)轉發給鄰居節點若符合條件轉e),轉發過程中節點會將自身ID附在RREQ中,接收到消息節點以此為上跳節點.

e)目的或存在到目的節點的中間節點生成一個路由應答數據分組RREP,通過反向路由轉發給源節點,轉f.

f)源節點根據跳數和時間戳選取一條最佳路由路徑,添加源路由標識O,路由發現過程完成.

g)中間節點檢查自己ID是否與RREQ中目的節點一致,檢測路由表存儲有到達目的節點ID,若不符合條件繼續進行g)轉發給鄰居節點若符合條件轉h).

h)目的或存在到目的節點的中間節點生成一個路由應答數據分組RREP,源節點將接收并記錄從不同路徑傳來的RREP,并在此路徑信息添加源路由標識S.

根據以上路由發現策略,根據不同的網絡拓撲環境在目的節點及中間節點記錄此過程中轉發的路由路徑,節點在發送數據過程中會根據不同標識的路由路徑分別采取AODV最優路徑傳輸機制或將路由信息附加到數組分組的源路由機制,并且當路由標識為S時,在路由維護的過程中會關閉在AODV中周期廣播HELLO分組的路由維護過程.

4 仿真與分析

為了驗證本文路由協議的綜合網絡性能得到了提高,采用NS2軟件對網絡進行仿真.采用802.11作為MAC層協議,設置節點通信范圍為250 m,仿真時間為300秒,每秒鐘發送2個CBR數據流,每個數據分組長度為512 byte,建立10對通信連接,節點運動停留時間1s.仿真實驗主要是從不同節點最大移動速度下平均分組投遞率和平均端到端延時兩個方面來評價改進路由協議和原有的兩種協議的性能.平均分組投遞率是所有節點接收到的總分組數量與CBR流發送出的總分組數量的比值,這個參數反映了改進協議的效率以及網絡傳輸的可靠性.平均端到端時延數據分組從源節點到目的節點之間消耗的平均時間,反映了路由發現過程中的尋徑效率.文章中的數據來源于NS2仿真,運動速度和方向均來源于NS2的setdest工具生成的隨機移動場景.

圖2和圖3對比了3種路由協議在節點最大速度變化的情況下的性能.仿真模擬了一定數量的節點在固定的通信區域內最大速度分別為5 m/s到40 m/s的場景.每種場景仿真30次,并綜合30次實驗結果為平均性能指標,比較分析了AODV、DSR和DSAODV三種協議平均時延和平均分組投遞率,具體仿真參數見表1.

表1 節點最大速度變化仿真參數
Table 1 Simulation parameters of maximum velocity variation of nodes

參數取值仿真區域面積1000×1000m2節點數量50節點速度5 m/s ～ 40 m/s仿真時間300s傳輸范圍250m數據包尺寸512byte

從圖2可以看出,在節點移動速度較低時,所有節點組成的網絡拓撲變化不大,此時AODV協議的平均端到端時延由于其只緩存了一條最優路由鏈路,當鏈路失效時要重新建立,所以端到端時延要明顯高于其他協議.隨著移動速度的增加,節點更容易相對移動到自身的傳輸范圍之外,網絡拓撲變化較大,鏈路的穩定性下降,三種路由協議的平均端到端時延都會隨之降低.但是本文改進的方法在不同的網絡環境下分別采用了原兩種協議的路由發現與路由維護機制,故在仿真節點速度不斷變化的情況下,綜合平均端到端延時優于原有的兩種協議.

圖2 不同最大移動速度平均時延Fig.2 Average time delay of different maximum moving speed

圖3體現了最大移動速度對分組投遞率的影響.分組投遞率是目的節點接收到數組分組的綜述和CBR產生數據分組總數之比.節點移動速度較慢時,鏈路相對穩定,路由發現與路由重建較少,故分組投遞率高,隨著速度的增加,網絡拓撲變化頻繁,進行新的路由發現過程的報文增多,帶寬占用率也會增大,分組投遞率呈現出下降的趨勢.其中DSR路由協議因為采用了多路徑路由方式,一旦當前路由斷開,會立即使用緩存在路由表中的備用路由重新發送數據分組,而當前路由上的路由分組丟失,而節點最大移動速度直接影響著網絡拓撲變化速度,導致DSR協議在最大移動速度增大到20 m/s時性能下降速率高于其他兩種協議.綜合比較DSR、AODV和DSAODV三種方法的平均分組投遞率分別為94.35%、94.77和96.04%,其中在節點最大移動速度為40m/s時DSAODV比DSR投遞率高出3.9%;在節點最大移動速度為10m/s DSAODV比AODV投遞率高出2.5%.說明了DSAODV所采取基于拓撲變化的路由發現機制是有效的,網絡在節點速度變化的條件下適應性得到了明顯提升.

圖3 不同最大移動速度平均分組投遞率Fig.3 Average packet delivery rate of different maximum moving speed

圖4和圖5對比了路由協議在不同網絡規模下的性能.仿真模擬了一定數量的節點在固定的通信區域內最大節點數為10到90的場景.同樣綜合30次實驗結果為平均性能指標,具體仿真參數見表2.

圖4說明了網絡中節點數的大小對傳輸時延的影響.當節點數小于40時,在仿真區域為1000m×1000m范圍內網絡節點密度較小,端到端的鏈路較少,最優路徑的平均跳數增加,而且路由發現較慢,所以平均端到端時延較大,隨著節點的數目增加,網絡節點密度逐漸增加時延逐漸減少.當節點數目繼續增加,路由發現過程中RREQ重傳加劇了網絡風暴,數據分組競爭激烈,占用了有效帶寬資源,傳輸時延又會上升,但是DSAODV在路由維護的過程中,會根據節點的拓撲變化速率選取路由路徑,抑制了網絡中RREQ的報文,網絡使用帶寬更小,在保證可靠數據傳輸的情況下,平均時延優于原協議.

表2 節點數目變化仿真參數
Table 2 Simulation parameters of number of nodes

參數取值 仿真區域面積1000×1000m2節點數量10 ～ 90節點速度25m/s仿真時間300s傳輸范圍250m數據包尺寸512byte

圖4 不同節點數平均時延Fig.4 Average time delay of different node numbers

圖5提現了節點數與分組投遞率之間的關系.節點數目較小,此時網絡的吞吐量在單位時間內少,鏈路在建立的過程中選擇也相應少,路由發現緩慢.隨著節點數目的增大,路由發現過程中有更多較優路徑選擇,分組投遞率也隨之上升.在節點數增大到一個閾值時,隨著節點的鄰居節點數密度的增大,路由發現的RREQ分組使用更為頻繁,網絡重傳分組次數增加,導致分組投遞率呈下降的趨勢.隨著節點數進一步的增加到70以上,DSR協議由于其路由發現多鏈路支持機制,網絡帶寬資源占用上升,并且隨著網絡密度的增加,附在DSR協議分組首部的路徑信息也會隨路徑增加,使得DSR在復雜網絡中分組投遞率更小.

圖5 不同節點數平均分組投遞率Fig.5 Average packet delivery rate of different node numbers

5 結束語

本文針對MANET網絡中按需路由中存在的不同路由拓撲變化條件下網絡適用性低的缺陷提出了有效的改進方案,該方案通過建立網絡拓撲變化模型,提出了網絡拓撲變化速度系數并利用此系數選取合適的路由選取機制,使得源節點在路由發現的過程中選取更加高效的報文轉發方式,最終建立了一條穩定性高的鏈路作為通信路由.通過建立NS2仿真環境在兩種不同的變化環境,比較了路由協議對于節點最大移動速度以及網絡節點總數的端到端時延與分組投遞率.仿真實驗驗證了改進后的協議在鏈路穩定性不同環境下表現出更好的性能,更好的適應于在不同網絡拓撲變化條件下的動態網絡.