基于路由長度的多徑路由協議

王 頂,王珊珊,席效禹

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

基于路由長度的多徑路由協議

王 頂,王珊珊,席效禹

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

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

無線自組織網絡;多徑路由;路由長度;鄰居變化率;DSR_HD路由協議

1 概述

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

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

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

2 DSR協議

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

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

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

3 多徑路由

3.1 多徑路由的定義

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

圖1 多徑路由的分類

3.2 多徑路由的選擇

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

3.2.1 路由條數的確定

在被動路由協議中,路由開銷主要由路由發現、路由維護以及數據傳輸造成[5]。

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

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

圖2 路徑條數對網絡路由開銷的影響

3.2.2 多徑使用模式

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

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

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

4.1 鄰居變化率

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

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

圖3 鄰居表建立流程

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

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

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

通過鄰居變化率選擇局部拓撲結構變化較小的節點參與數據的轉發,減少了路徑中發生斷裂的概率。

根據NVR的大小節點自動調整發送HELLO消息的周期,當NVR較大時,增大HELLO消息發送的周期,當NVR較小時,減少HELLO消息發送的周期,這樣可以適當減少路由開銷。

4.2 路由長度

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

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

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

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

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

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

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

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

4.3 協議描述

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

圖4 RREQ分組包結構

4.3.1 路由發現過程

路由發現過程具體如下:

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

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

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

圖5 中間節點對RREQ的處理轉發過程

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

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

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

4.3.2 路由維護

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

5 仿真實驗與結果分析

5.1 仿真系統介紹

本文采用NS2網絡仿真軟件對DSR路由協議與DSR_HD路由協議進行性能比較。

5.2 仿真參數

網絡拓撲結構是一個包括20個移動節點的網絡模型,節點隨機分布在1 000 m×1 000 m的平面區域中,按照設定的速度隨機向任意方向移動[11]。節點采用全向天線,默認傳輸范圍為250 m。因為本文討論的是高速移動的自組網中設備的運動模型,所以將此停留時間設置為0。源節點每隔0.5 s發送一個數據,每隔數據分組為512 Byte,仿真時間為500 s。為了盡可能地保證模擬的一致性,本文采用Setdest Version2中將節點移動速度的最大與最小值設為相同。這樣在每個生成的場景中,節點均以固定速度移動。以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 性能參數

性能參數具體如下:

(1)投遞率:目的節點正確接收到的數據包占產生數據包的比例。

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

(3)端到端平均時延:從源節點產生的數據包到目的節點收到該數據包的平均時間[12]。

5.4 結果分析

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

圖6 分組成功投遞率比較

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

圖7 路由開銷比較

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

圖8 平均端到端時延比較

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

6 結束語

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

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

[2] 邵 琳,阮穎平,彭 宏.Ad hoc網絡中一種新的基于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] 郭曉峰,陳躍泉,陳貴海.一種累計多路徑移動自組網絡路由策略[J].軟件學報:自然科學版,2004,15(4): 594-603.

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

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

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

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

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

[12] 張現芳.基于SMR的多路徑協議的分析和優化[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

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

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

2013-08-12

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