基于路由長度的多徑路由協(xié)議

王 頂,王珊珊,席效禹

(西北工業(yè)大學電子信息學院,西安710129)

基于路由長度的多徑路由協(xié)議

王 頂,王珊珊,席效禹

(西北工業(yè)大學電子信息學院,西安710129)

針對單徑路由協(xié)議在高速Ad hoc網(wǎng)絡中平均端到端時延和丟包率高的問題,在動態(tài)源路由協(xié)議的基礎上,提出基于鄰居節(jié)點變化率與路由長度的多徑路由協(xié)議DSR_HD。利用HELLO消息獲得一跳范圍內(nèi)可用鄰居數(shù),根據(jù)鄰居數(shù)求得節(jié)點的鄰居節(jié)點變化率。在路由發(fā)現(xiàn)過程中,采用路由距離與路由跳數(shù)相結合的方法計算路由長度,并選擇鄰居節(jié)點變化率和路由長度低的節(jié)點加入路由,從而提高路由的穩(wěn)定性。仿真實驗結果顯示, DSR_HD協(xié)議可以有效減少數(shù)據(jù)分組傳輸?shù)亩说蕉藭r延及路由開銷,提高分組成功投遞率。

無線自組織網(wǎng)絡;多徑路由;路由長度;鄰居變化率;DSR_HD路由協(xié)議

1 概述

在自組織網(wǎng)絡開發(fā)應用過程中,與傳統(tǒng)網(wǎng)絡有很多不同之處。自組網(wǎng)中的設備大多處于高速移動狀態(tài),由于節(jié)點數(shù)量較多,相對速度較快,直接造成網(wǎng)絡結構的快速變化,傳統(tǒng)路由協(xié)議不能很好地適應網(wǎng)絡拓撲結構的變化,因此路由算法成為Ad hoc網(wǎng)絡中的研究重點。

在Ad hoc網(wǎng)絡中,DSR,AODV都是采用一次路由發(fā)現(xiàn),僅選擇一條路由策略。但是隨著Ad hoc網(wǎng)絡研究的不斷深入,單徑路由協(xié)議已經(jīng)不能滿足更高層次的路由要求。單徑不能充分利用網(wǎng)絡資源,易于產(chǎn)生擁塞,使端到端的時延以及丟包率增加,并且會使某些節(jié)點承擔的轉(zhuǎn)發(fā)任務過重,使能源耗盡,最終導致網(wǎng)絡斷開,而多徑路由算法可以很好地解決這些問題。

本文在動態(tài)源路由(Dynamic Source Routing, DSR)協(xié)議的基礎上提出基于路由長度的路由協(xié)議(DynamicSourceRouting Based on Hop and Distance,DSR_HD),采用路由距離與路由跳數(shù)相結合的方法,同時利用鄰居節(jié)點變化率與多徑傳輸數(shù)據(jù),實現(xiàn)Ad hoc網(wǎng)絡資源的充分利用。

2 DSR協(xié)議

DSR協(xié)議是最早采用按需路由協(xié)議思想的路由協(xié)議,主要由 2個機制組成:路由發(fā)現(xiàn)和路由維護[1]。

在DSR協(xié)議中,采用源路由的方式[2]避免了數(shù)據(jù)包經(jīng)過的中間節(jié)點不停更新路由,而且允許節(jié)點在轉(zhuǎn)發(fā)或無意中接收到數(shù)據(jù)包時,將最新的路由信息存于它的路由緩存器中以備不時之需,減少了路由發(fā)現(xiàn)的開銷。源主機知道到達目標主機的路徑,而且可以自由地從中選擇合適的路徑來發(fā)送數(shù)據(jù)包。這就使得DSR上的多徑路由比基于逐跳的路由協(xié)議上的多徑路由簡單。基于DSR協(xié)議的性能表現(xiàn)以及源路由的特征,因此,選擇DSR協(xié)議進行擴展。

雖然DSR協(xié)議有其自身的優(yōu)點,但是它也有自身的缺點,如:(1)一次路由發(fā)現(xiàn)過程可能會產(chǎn)生多條到目的節(jié)點的路由,但是只采用一條路徑進行傳輸,造成資源浪費;(2)由于Ad hoc網(wǎng)絡拓撲結構變化較快,路由緩存中的過期路由會影響路由選擇的準確性。

3 多徑路由

3.1 多徑路由的定義

多徑路由算法[3]是指可以為源節(jié)點與目的節(jié)點同時提供多條可用路徑,并且允許節(jié)點選擇如何使用這些路徑的算法。多徑路由可以分為3類[4]:節(jié)點不相關多徑路由,鏈路不相關多徑路由以及相關多徑路由,如圖1所示。

圖1 多徑路由的分類

3.2 多徑路由的選擇

節(jié)點不相關多徑路由之間沒有公用的節(jié)點或鏈路,其容錯能力最強,具有更好的穩(wěn)定性。鏈路不相關多徑路由的容錯能力次之,相關多徑路由的容錯能力最差。所以本文采用節(jié)點不相關多徑路由。

3.2.1 路由條數(shù)的確定

在被動路由協(xié)議中,路由開銷主要由路由發(fā)現(xiàn)、路由維護以及數(shù)據(jù)傳輸造成[5]。

假設移動節(jié)點均勻分布在半徑為R的網(wǎng)絡中,節(jié)點的密度為δ,設網(wǎng)絡中有N個節(jié)點,則N=πR2δ。每個鏈路發(fā)生斷裂的概率為μ。假定hs與hm分別為單徑與多徑路由協(xié)議的平均路由跳數(shù)。因為單徑路由協(xié)議采用最短的路徑,所以hm＞hs。發(fā)生路徑斷裂處的節(jié)點距離源節(jié)點的平均跳數(shù)為he。設Ac為每個節(jié)點活躍鏈接數(shù)。設Nu為多徑協(xié)議的路由條數(shù),λs,λm分別為單徑與多徑路由協(xié)議的路由發(fā)現(xiàn)頻率,P為數(shù)據(jù)包的開銷,ε為發(fā)送數(shù)據(jù)包的頻率。路由請求分組(Routing Request,RREQ)、路由答應(Routing Reply,RREP)、路由錯誤(Routing Error, RRER)分組大小分別為Mrq,Mrp,Me。一次路由發(fā)現(xiàn)需要時間T完成。設Osl,Oml分別為單徑路由協(xié)議與多徑路由協(xié)議的開銷。

單徑與多徑路由協(xié)議的開銷隨路由跳數(shù)變化,如圖2所示。當路由條數(shù)為2或3時,多徑路由協(xié)議的開銷增加不明顯。當路由條數(shù)超過3時,多徑路由協(xié)議的開銷急劇增大。所以,一般選2條～3條路徑,本文選取2條路徑。

圖2 路徑條數(shù)對網(wǎng)絡路由開銷的影響

3.2.2 多徑使用模式

多徑的使用有2種基本使用模式,同時使用多條路徑或先使用主路徑,主路徑失效后在使用其他路徑。

本文采用輪流發(fā)送的方式發(fā)送數(shù)據(jù)包[6]。通過采用這種方式,可以簡單地模擬n個數(shù)據(jù)包同時使用2條節(jié)點不相關路徑進行傳輸。

4 基于鄰居變化率和路由長度的多徑路由

4.1 鄰居變化率

在DSR_HD協(xié)議中每隔HELLO_INTERVAL廣播HELLO消息。節(jié)點可以通過接收相鄰節(jié)點發(fā)送來的HELLO消息來與確定其與鄰居節(jié)點的連通性。

每個節(jié)點維護2個鄰居表,一個鄰居表用來記錄鄰居節(jié)點id和t0時刻與t1時刻該節(jié)點與鄰居節(jié)點的距離,另一個鄰居表用來記錄與該節(jié)點建立過連接的節(jié)點id。鄰居表建立流程如圖3所示。

圖3 鄰居表建立流程

假設節(jié)點n在t0時刻的鄰居表集為sn(t0),時刻的t1鄰居表集為sn(t1),則節(jié)點n的鄰居變化率[7]為:

由式(3)可知,鄰居變化率是t1-t0時間間隔內(nèi)和節(jié)點保持連接的節(jié)點個數(shù)與t0時刻和該節(jié)點建立過接連的節(jié)點個數(shù)之比。

NVR越大,說明節(jié)點n的局部拓撲結構越穩(wěn)定,NVR越小,說明節(jié)點n的局部拓撲結構變化越劇烈。

通過鄰居變化率選擇局部拓撲結構變化較小的節(jié)點參與數(shù)據(jù)的轉(zhuǎn)發(fā),減少了路徑中發(fā)生斷裂的概率。

根據(jù)NVR的大小節(jié)點自動調(diào)整發(fā)送HELLO消息的周期,當NVR較大時,增大HELLO消息發(fā)送的周期,當NVR較小時,減少HELLO消息發(fā)送的周期,這樣可以適當減少路由開銷。

4.2 路由長度

DSR路由協(xié)議以路由跳數(shù)作為判據(jù)標準,雖然非常簡單,但是網(wǎng)絡中可能存在很多相同跳數(shù)的最短路徑,這就可能沒有選擇到最優(yōu)鏈路,并且路由跳數(shù)少時,源節(jié)點與目的節(jié)點之間的距離也可能很大,反之,源節(jié)點與目的節(jié)點之間的距離也可能很小。路由跳數(shù)多,路由中使用的節(jié)點就增多,造成浪費,源節(jié)點到目的節(jié)點的距離大,路由鏈路斷裂的概率就大。本文采用路由跳數(shù)與路由距離的均衡值路由長度L作為路由判據(jù)。

其中,h為路由跳數(shù);s為源節(jié)點到目的節(jié)點最小跳數(shù);di為第i跳t1時刻兩節(jié)點間的距離;r為兩節(jié)點間最大的通信距離;f為糾正因子,它與t0時刻與t1時刻兩節(jié)點間距離的關系如下:

(1)當前時刻與鄰居節(jié)點的距離大于上一刻與鄰居節(jié)點的距離,則說明2個節(jié)點在遠離,則f=1;

(2)當前時刻與鄰居節(jié)點的距離小于上一刻與鄰居節(jié)點的距離,則說明2個節(jié)點在靠近,則f= -1;

(3)當前時刻與鄰居節(jié)點的距離等于上一刻與鄰居節(jié)點的距離,則說明2個節(jié)點保持相對位置不變,則f=0。

經(jīng)過多次實驗,當ω=0.3時,性能較好。為計算路由判據(jù)L,必須求得節(jié)點間的距離,本文利用在接收分組或消息時通過探測接收信號強度來計算出節(jié)點間的距離[8]。

在自由空間中,根據(jù)自由空間傳播模型,接收信號的強度與節(jié)點間距離的平方成反比。按Frri自由空間方程式[9],接收信號的強度與節(jié)點間距有如下關系:

其中,pr(d)是接收功率;λ是波長;Gr是接收方天線增益;pt是發(fā)送功率;Gr是發(fā)送方天線增益;l是系統(tǒng)損耗率;d為發(fā)送方到接收方的距離。由式(6)可以得到式(7),從而可以求出路由長度L。

4.3 協(xié)議描述

當源節(jié)點S需要向目的節(jié)點發(fā)送數(shù)據(jù)而緩存中沒有到目的節(jié)點D的路由時,就會啟動路由發(fā)現(xiàn)的過程。DSR_HD路由協(xié)議的RREQ分組包結構相比于DSR路由協(xié)議來說,做了一定的改進,其格式如圖4所示。

圖4 RREQ分組包結構

4.3.1 路由發(fā)現(xiàn)過程

路由發(fā)現(xiàn)過程具體如下:

(1)中間節(jié)點對RREQ分組的處理

中間節(jié)點接收到RREQ分組時,不管緩存中有沒有到達目的節(jié)點的路由,都不回復RREP分組[10],并且當節(jié)點通信范圍內(nèi)包含目的節(jié)點時,置RREQ的標志位為1。對RREQ分組的處理和轉(zhuǎn)發(fā)過程如圖5所示,具體步驟如下:

中間節(jié)點接收到RREQ分組后,首先判斷該節(jié)點的鄰居變化率是否超過門限值,如果鄰居變化率超過門限值,則說明當前節(jié)點的路由不可靠,則直接丟棄該RREQ分組;反之,繼續(xù)判斷該RREQ分組的標志位,如果標志位為1,說明上一節(jié)點通信范圍內(nèi)包括目的節(jié)點,為減少路由開銷,直接丟棄該RREQ分組,如果標志位為0,說明節(jié)點通信范圍內(nèi)沒有該RREQ分組,該節(jié)點在緩存中尋找該RREQ分組的記錄,如果沒有,則計算路由判據(jù)L,并將L與上一跳的地址記錄到存儲器中,轉(zhuǎn)發(fā)數(shù)據(jù)包。如果中間節(jié)點的緩存中有該RREQ分組,計算其路由判據(jù)S,并將S與之前存儲器的路由長度L進行比較。如果S≥L,則丟棄該RREQ分組。如果S＜L,則判斷RREQ分組中攜帶的上一跳地址與第一次記錄的前一節(jié)點地址是否相同,如果相同,則丟棄該RREQ分組。反之則轉(zhuǎn)發(fā)該RREQ分組。

圖5 中間節(jié)點對RREQ的處理轉(zhuǎn)發(fā)過程

(2)目的節(jié)點對RREQ分組的處理

一般的多徑路由協(xié)議(如SMR)由目的節(jié)點控制,源節(jié)點只能被動地接受目的節(jié)點選擇的路由,這樣的方式使源節(jié)點在有限的幾條路徑失效時,只能重新啟動路由請求,特別是當多條路徑同時發(fā)送數(shù)據(jù)時,源節(jié)點多條路徑中的其中一部分如果斷開,只能舍棄這樣的路徑,退化成單徑的方式發(fā)送數(shù)據(jù)。如果能在源節(jié)點,而不是目的節(jié)點保留充分的網(wǎng)絡狀態(tài)信息,將可以較好地解決該問題。

本文目的節(jié)點收到第一個RREQ包后,立刻發(fā)送RREP給源節(jié)點,通知源節(jié)點這條路由為延遲最短的路徑,目的節(jié)點繼續(xù)等待接收更多的RREQ,每收到一個這樣的 RREQ包,延遲一定時間,再將RREP發(fā)送給源節(jié)點。這樣源節(jié)點就可以獲得多條路徑,然后選擇L小的路由,發(fā)送數(shù)據(jù)。

4.3.2 路由維護

本文采用2條路由輪流發(fā)送的方式來發(fā)送數(shù)據(jù)包,源節(jié)點保留充分的網(wǎng)絡狀態(tài)信息,當發(fā)現(xiàn)一條中斷時,首先查找緩存,尋找另一條到達目的節(jié)點的路由,從而保持2條路由輪流進行數(shù)據(jù)包的發(fā)送,如果找不到到達目的節(jié)點的路由,源節(jié)點就保持單條路徑發(fā)送數(shù)據(jù)包,直到所有路徑全部不可用,才重新進行路由發(fā)現(xiàn)過程尋找新的路由。所以,本文利用多徑路由協(xié)議沒有增加路由發(fā)現(xiàn)的次數(shù),從而減少了路由開銷。

5 仿真實驗與結果分析

5.1 仿真系統(tǒng)介紹

本文采用NS2網(wǎng)絡仿真軟件對DSR路由協(xié)議與DSR_HD路由協(xié)議進行性能比較。

5.2 仿真參數(shù)

網(wǎng)絡拓撲結構是一個包括20個移動節(jié)點的網(wǎng)絡模型,節(jié)點隨機分布在1 000 m×1 000 m的平面區(qū)域中,按照設定的速度隨機向任意方向移動[11]。節(jié)點采用全向天線,默認傳輸范圍為250 m。因為本文討論的是高速移動的自組網(wǎng)中設備的運動模型,所以將此停留時間設置為0。源節(jié)點每隔0.5 s發(fā)送一個數(shù)據(jù),每隔數(shù)據(jù)分組為512 Byte,仿真時間為500 s。為了盡可能地保證模擬的一致性,本文采用Setdest Version2中將節(jié)點移動速度的最大與最小值設為相同。這樣在每個生成的場景中,節(jié)點均以固定速度移動。以10 m/s,20 m/s,30 m/s,40 m/s, 50 m/s,60 m/s,70 m/s,80 m/s,90 m/s,100 m/s進行仿真。

5.3 性能參數(shù)

性能參數(shù)具體如下:

(1)投遞率:目的節(jié)點正確接收到的數(shù)據(jù)包占產(chǎn)生數(shù)據(jù)包的比例。

(2)路由開銷比例:路由包(包括RREQ,RREP, RRER等)占全部數(shù)據(jù)包(正確接收的數(shù)據(jù)包與路由協(xié)議控制包)的比例。

(3)端到端平均時延:從源節(jié)點產(chǎn)生的數(shù)據(jù)包到目的節(jié)點收到該數(shù)據(jù)包的平均時間[12]。

5.4 結果分析

由圖6可以看出,DSR路由協(xié)議隨著節(jié)點運動速度的增大,其分組成功投遞率呈現(xiàn)下降趨勢,而DSR_HD協(xié)議則基本沒受到速度因素的影響。這是因為DSR_HD路由協(xié)議考慮了路由的穩(wěn)定性,保證了鏈路的穩(wěn)定。

圖6 分組成功投遞率比較

圖7顯示了路由開銷的比較,在低速環(huán)境下, DSR_HD的開銷要大于DSR。這是因為DSR_HD是多徑路由,它在整個通信開始的時要出現(xiàn)2條路由,所以開始的開銷要高于DSR。但是在高速環(huán)境下,DSR的路由重建率要遠大于DSR_HD,DSR_HD可以較好地降低路由重建所帶來的時延。

圖7 路由開銷比較

圖8顯示了平均端到端延時的比較,在低速環(huán)境下,網(wǎng)絡拓撲結構變化緩慢,DSR路由協(xié)議中由于某個節(jié)點移動而引起多條路徑斷裂的優(yōu)勢就不是很明顯,從而DSR在時延方面表現(xiàn)略優(yōu)于DSR_HD。但是在高速環(huán)境下,DSR_HD優(yōu)于DSR路由協(xié)議。

圖8 平均端到端時延比較

綜上所述,在拓撲結構變化較快的網(wǎng)絡中,DSR_ HD路由協(xié)議在提高分組成功投遞率、降低端到端延時和控制路由開銷方面都有顯著提高,DSR_HD路由協(xié)議比DSR路由協(xié)議能更好地適應拓撲結構變化快速的網(wǎng)絡,所以,DSR_HD路由協(xié)議更加適合高速移動的自組網(wǎng)。

6 結束語

本文在DSR協(xié)議和多徑路由思想的基礎上,提出了 DSR_HD路由協(xié)議。該協(xié)議通過定期發(fā)送HELLO消息,排除路由長度過長并且鄰居變化率較大的路由,減少路由開銷,而且源節(jié)點建立了相對完備的網(wǎng)絡拓撲結構。仿真實驗證明了該協(xié)議的可行性與可靠性,在平均端到端的延時、分組投遞率、路由開銷等方面均具有較好的性能。

[1] 王金龍.Ad Hoc移動無線網(wǎng)絡[M].北京:國防工業(yè)出版社,2004.

[2] 邵 琳,阮穎平,彭 宏.Ad hoc網(wǎng)絡中一種新的基于DSR的多路由算法[C]//中國電子學會第十七屆信息論學術年會論文集.西安:[出版者不詳],2010: 339-345.

[3] Nasipuri A,Castaneda R,Das S R.Performance of Multi-path Routing for On-demand Protocols in Mobile Ad Hoc Network[J].Mobile Networks and Application, 2001,6(4):339-349.

[4] Mueller S,Tsang R P,Ghosal D.Multipath Routing in Mobile Ad Hoc Networks:Issues and Challenges[M]// Calzarossa M C,Gelenbe E.Performance Tools and Applications to Networked Systems.Berlin,Germany: Springer,2004:209-234.

[5] Pham P P,Perreau S.Performance Analysis of Reactive Short-est Path and Multipath Routing Mechanism with Load Balance[C]//Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]:IEEE Press,2003:251-259.

[6] 郭曉峰,陳躍泉,陳貴海.一種累計多路徑移動自組網(wǎng)絡路由策略[J].軟件學報:自然科學版,2004,15(4): 594-603.

[7] 劉 兵,高 強,曾長安.一種改進型的Ad hoc網(wǎng)絡值分簇算法[J].華北電力大學學報,2007,34(5): 99-102.

[8] 蔣世林.基于節(jié)點相對移動性的自適應按需組播路由協(xié)議的研究與實現(xiàn)[D].沈陽:東北大學,2011.

[9] 安輝耀,王新安,李 揮,等.移動自組網(wǎng)中的先進路由算法與路由協(xié)議[M].北京:科學出版社,2009.

[10] 朱 偉.Ad hoc網(wǎng)絡獨立多路徑路由的研究與改進[D].濟南:山東大學,2006.

[11] 柯志亨,程榮祥,鄧德雋.NS2仿真實驗-多媒體和無線網(wǎng)絡通信[M].北京:電子工業(yè)出版社,2009.

[12] 張現(xiàn)芳.基于SMR的多路徑協(xié)議的分析和優(yōu)化[J].移動通信,2012,36(6):45-48.

編輯 陸燕菲

Multipath Routing Protocol Based on Routing Length

WANG Ding,WANG Shan-shan,XI Xiao-yu
(College of Electronic and Information,Northwestern Polytechnical University,Xi'an 710129,China)

Aiming at the shortcomings that signal path protocol has high end-to-end delay and packet loss rate in highspeed environments,this paper modifies the Dynamic Source Routing(DSR)protocol,and by using the HELLO message,the number of neighbors can be obtained.According to the number of neighbors,it can calculate the neighbor change ratio.During the routing discovery,it can calculate the length of the routing by using the method of routing distance and routing hops combination,and choose the neighbor node whose neighbor change ratio and route length are lower join the routing.So it can choose the high degree of stability of routing.Simulation results show that under the high-speed environment the algorithm can control the end to end delay of data packet transmission,dramatically increase the successful package delivery ratio and reduce routing overhead.

Ad hoc network;multipath routing;routing length;neighbor change ratio;DSR_HD routing protocol

1000-3428(2014)09-0082-05

A

TN915.04

10.3969/j.issn.1000-3428.2014.09.017

西北工業(yè)大學基礎研究基金資助項目(GBKY1011)。

王 頂(1973-),男,副教授、博士,主研方向:寬帶無線通信;王珊珊、席效禹,碩士研究生。

2013-08-12

2013-10-11E-mail:wangshanshan42587@163.com