基于拓撲連通概率的車載自組織網(wǎng)絡路由算法

陶 軍 肖 鵬 劉 瑩 陳文強

(東南大學教育部計算機網(wǎng)絡和信息集成重點實驗室,南京210096)

近年來,各國學者提出了多種VANETs路由算法.其中,基于概率的路由算法從報文接收概率的角度進行分析,有效提升了路由算法報文的投遞率和下一跳選擇的正確性.文獻[1]按照節(jié)點的接收概率選擇下一跳路由,提出了REAR算法;文獻[2-3]基于節(jié)點移動參數(shù),建立了概率模型以預測連接持續(xù)時間,從而在全局情況下建立和維護路由;文獻[4-5]依據(jù)節(jié)點間的距離計算彼此的連通概率,提出連通感知路由算法CAR.REAR算法能夠有效傳輸數(shù)據(jù)包,其投遞率和使用包的數(shù)量也在接受范圍之內(nèi)[6-7].該算法的缺點在于:① 競爭延遲函數(shù)的選取不能反映網(wǎng)絡拓撲的變化;② 缺乏有效的廣播風暴抑制機制;③ 鄰居概率之和的計算方法過于繁瑣.

針對REAR算法存在的不足,本文在競爭延遲函數(shù)的參數(shù)、廣播報文的傳播時間、數(shù)據(jù)報文的廣播次數(shù)以及下一跳節(jié)點的判斷依據(jù)等方面進行了修改,提出了一種基于拓撲連通概率的車載自組織網(wǎng)絡路由算法——RPR算法.然后,從覆蓋率、輔助報文數(shù)量和結束時間等3個方面對REAR算法和RPR算法進行了比較.

1 網(wǎng)絡模型

REAR算法中,每個節(jié)點都會維護一張鄰居列表,列表中的內(nèi)容包括鄰居的位置、速度、方向、接收概率以及該節(jié)點的生存時間等.每個節(jié)點定期通過HelloBeacon數(shù)據(jù)包向自己的鄰居廣播上述信息.每個節(jié)點收到其他節(jié)點的數(shù)據(jù)包之后,如果此數(shù)據(jù)包是一個HelloBeacon數(shù)據(jù)包,則將其更新到鄰居列表中;否則根據(jù)自身情況進行廣播.節(jié)點的初始狀態(tài)是空閑狀態(tài),收到數(shù)據(jù)包之后便會進入競爭狀態(tài),隨后再進行數(shù)據(jù)包轉發(fā).如果一個節(jié)點收到新數(shù)據(jù)包時正處于競爭狀態(tài),則此節(jié)點取消自己的競爭狀態(tài),并且放棄自己將要轉發(fā)的數(shù)據(jù)包,重新進入競爭狀態(tài),等競爭狀態(tài)結束后再轉發(fā)新的數(shù)據(jù)包.具體的轉發(fā)流程見圖1.

圖1 REAR算法狀態(tài)轉換圖

節(jié)點處于競爭狀態(tài)的時間是根據(jù)節(jié)點鄰居的接收概率來確定的.如果一個節(jié)點鄰居的接收概率較高,則會較早地從該節(jié)點轉發(fā)數(shù)據(jù)包.因此,在REAR算法中，給出一個根據(jù)鄰居接收概率之和計算競爭狀態(tài)時間的函數(shù),即

fexp=aexp(-∑Pi)

式中,Pi表示節(jié)點的單個鄰居接收概率,即節(jié)點收到其他節(jié)點數(shù)據(jù)的可能性,具體的計算過程見文獻[1];a表示任意常量.為了證明算法的正確性,REAR算法的提出者進行了如下假設:

∑Pi=∑Pj+1

其具體物理意義為:一個節(jié)點鄰居的概率之和與另一個節(jié)點鄰居的概率之和的差的絕對值等于1.然而,VANETs是一個自組織的網(wǎng)絡,車輛之間的間距與鄰居都是隨機分布的,任意2個節(jié)點間不可能存在上述關聯(lián),故這個假設在物理上是沒有意義的.因此,本文對REAR算法進行了改進.

2 RPR算法

針對REAR算法存在的不足,本文提出了一種新的路由算法——RPR算法.

2.1 廣播風暴的抑制

對于廣播風暴的抑制可從以下2個方面考慮:① 廣播節(jié)點.若一個節(jié)點廣播了某個數(shù)據(jù)報文,則在一段時間內(nèi)它將不再對此廣播報文進行傳輸.② 數(shù)據(jù)報文.為了防止一個廣播報文在VANETs中被反復廣播,本文為報文添加了一個生存時間(TTL)[8].中間節(jié)點在轉發(fā)該數(shù)據(jù)包時,需要對TTL進行判定.如果TTL已經(jīng)為0,則不再轉發(fā)此數(shù)據(jù)包;否則,需要在轉發(fā)該數(shù)據(jù)包之前將TTL減少1.

2.2 鄰居概率之和的計算

由文獻[1]可知,利用REAR算法計算鄰居概率之和的算法過于繁瑣,并且?guī)砹艘恍┴撁嫘?如計算量過大、部分數(shù)據(jù)不能夠反映路由的真正走向等.此外,REAR算法需要同時考慮上一跳節(jié)點和下一跳節(jié)點的接收概率,導致不能夠正確選擇下一跳節(jié)點.在本文算法中,節(jié)點只計算下一跳節(jié)點的接收概率,減少了不必要的運算,從而提高了算法的效率.

2.3 延遲函數(shù)的假象條件

REAR算法提出了延遲函數(shù)的定義,但該函數(shù)的證明存在問題.本文只需要修改函數(shù)的參數(shù),使得函數(shù)中任意2個參數(shù)值之差的絕對值大于等于1即可.令Ri,j為節(jié)點j在節(jié)點i的鄰居中的排名信息,并將Ri,j作為延遲函數(shù)的參數(shù).排名的依據(jù)是節(jié)點的接收概率之和:節(jié)點的接收概率之和越大,節(jié)點的排名越小.

對于任意一個節(jié)點vi,當其收到鄰居發(fā)出的HelloBeacon數(shù)據(jù)包時,便可獲得所有鄰居的接收概率.將這些接收概率排序后廣播出去,則vi的所有鄰居便能獲取自身的排名信息.任意2個節(jié)點的排名信息是不相同的,且排名信息是一個整數(shù),故其滿足延遲函數(shù)參數(shù)的要求.此外,排名信息的另一個優(yōu)勢在于:一個節(jié)點的鄰居數(shù)量是有限的,故任意2個鄰居的排名信息的差值也是有限的,從而導致任意2個節(jié)點的競爭延遲時間的差值較小,即可有效減少節(jié)點等待的時間.

3 仿真實驗

對本文算法進行了覆蓋率、輔助報文數(shù)量和結束時間等方面的性能分析,并將其與REAR子集算法、REAR全集算法進行了對比.此處,覆蓋率是指模擬結束后收到廣播報文的節(jié)點與總節(jié)點的比值;輔助報文數(shù)量是指整個廣播過程中使用的報文數(shù)量[9];結束時間是指達到指定覆蓋率所需的時間.

3.1 場景設置與描述

本文采用了一段直線道路場景(見圖2),道路長度為6 km.為了使實驗中的車輛不局限于兩側,減少邊界效應的發(fā)生,本文主要研究了2～4 km范圍內(nèi)車輛承載算法的運行狀況.因此,在運行算法的初始階段,0～2 km和4～6 km段道路上沒有車輛;隨著算法的運行,車輛向兩邊擴散并趨于穩(wěn)定.假設場景中的車輛總數(shù)為n,車輛速度在20～30 m/s內(nèi)隨機分布,平均速度為25 m/s.通過計算可以得到,當車輛到達2～4 km時,其分布滿足泊松分布,車輛密度λ=n/80.車輛的無線信號覆蓋范圍為250 m.為了消除隨機性,選擇2 000組數(shù)據(jù)的平均值作為最終結果.節(jié)點個數(shù)分別為40,50,60,70,80,90,100,110,120,130,140,150,160.算法運行時間為50 s.

圖2 模擬場景(單位：km)

3.2 結束時間與節(jié)點密度

由于實驗中覆蓋率很難達到100%,且當節(jié)點數(shù)量較少時,算法的覆蓋率很難達到90%以上,因此下面統(tǒng)計數(shù)據(jù)中的輔助報文數(shù)量[9]和結束時間是覆蓋率達到80%的數(shù)據(jù).

圖3為結束時間與節(jié)點數(shù)的關系曲線.由圖可知,RPR算法和REAR算法的收斂速度都較快.在不到1 s的時間內(nèi),2種算法均達到了80%的覆蓋率.此外,RPR算法在結束時間方面的優(yōu)勢是十分明顯的,其原因在于:RPR算法使用的是排名信息,節(jié)點之間的競爭延遲相差不明顯;而REAR算法則將鄰居的概率之和作為參數(shù),該變量的最大值和最小值之間的差距較大,在對比數(shù)據(jù)中,最大甚至達到500∶1,這一時間差距對于最終的時間延遲會產(chǎn)生較大的影響.通過計算可得,RPR算法的傳輸時間縮短至REAR算法的72%.

圖3 結束時間與節(jié)點數(shù)的關系

3.3 節(jié)點覆蓋率與節(jié)點密度

圖4為覆蓋率與節(jié)點數(shù)的關系曲線.從圖中可以看出,RPR算法的覆蓋率較REAR算法稍有提升,從原來的93%提升至99%.這是由于在計算鄰居概率之和時,REAR算法同時計算了下一跳節(jié)點和上一跳節(jié)點的累積概率[10],故而無法準確地選擇下一跳節(jié)點.此外，節(jié)點的覆蓋率隨著節(jié)點密度的增大而增加,這是因為節(jié)點密度的增大會使每個節(jié)點的鄰居增多,從而增加了節(jié)點被覆蓋到的概率.

圖4 節(jié)點覆蓋率與節(jié)點數(shù)的關系

3.4 輔助報文數(shù)量與節(jié)點密度

圖5為是輔助報文數(shù)量與節(jié)點數(shù)的關系曲線.由于REAR全集算法和REAR子集算法都沒有對廣播風暴進行控制,故其使用的報文數(shù)量較RPR算法明顯要多.由圖可知,RPR算法使用的廣播報文數(shù)量減至REAR算法的78%.此外,REAR子集算法和REAR全集算法使用的報文數(shù)量相似,因為這兩者在輔助報文控制方面進行的約束是一致的.RPR算法中,輔助報文數(shù)量減少的原因主要是:① 引入了TTL和廣播報文的限制;② 使用排名信息,使得延遲函數(shù)的前提條件得到滿足,一些不必要的數(shù)據(jù)報文在轉發(fā)之前就被取消了.

圖5 輔助報文數(shù)量與節(jié)點數(shù)的關系

3.5 覆蓋率與時間

節(jié)點數(shù)為100時,覆蓋率隨時間的變化情況見圖6.由圖可知,從1 s開始到模擬結束,覆蓋率基本沒有改變.其原因在于:車輛之間的數(shù)據(jù)傳輸較車輛本身的速度快很多,故在1 s內(nèi)所有數(shù)據(jù)已經(jīng)基本傳輸完畢.此外,覆蓋率增加的主要原因可歸結于VANETs的移動性,部分節(jié)點在模擬的初始階段未能與其余節(jié)點進行通信,隨著車輛的移動以及VANETs拓撲的變化,這些節(jié)點進入其余節(jié)點的通信范圍之內(nèi),故而覆蓋率得到提高.

圖6 覆蓋率與時間的關系

4 結語

本文提出了一種基于拓撲連通概率的車載自組織網(wǎng)絡路由算法——RPR算法.從覆蓋率、輔助報文數(shù)量和結束時間等3個方面對REAR算法和RPR算法進行了比較.結果表明,RPR算法可將廣播報文數(shù)量減少至REAR算法的78%,數(shù)據(jù)通信時間縮短至原算法的72%,覆蓋率則由原來的93%提升至99%.

)

[1]Hao J, Hao G, Li J C. Reliable and efficient alarm message routing in VANETs [C]//Proceedingsofthe28thInternationalConferenceonDistributedComputingSystemsWorkshops. Beijing, China, 2008:186-191.

[2]Yan G Y, Rawat D B, El-Tawab S.Ticket-based reliable routing in VANETs[C]//ProceedingsofIEEE6thInternationalConferenceonMobileAdHocandSensorSystems. Macao, China, 2009: 609-614.

[3]Naumov V, Naumov V, Gross T. Connectivity-aware routing (CAR) in vehicular ad hoc networks[C]//Proceedingsof2007IEEEInternationalConferenceonComputerCommunications. Anchorage, Alaska, USA, 2007: 1919-1927.

[4]Yan G Y, Olariu S, Salleh S. A probabilistic routing protocol in VANETs[C]//Proceedingsofthe7thInternationalConferenceonAdvancesinMobileComputingandMultimedia. Kuala Lumpur, Malaysia, 2009: 179-186.

[5]Karnadi F K, Mo Z H. Rapid generation of realistic mobility models for VANETs[C]//Proceedingsof2007WirelessCommunicationsandNetworkingConference. Washington DC, USA, 2007: 2506-2511.

[6]Abedi O, Fathy M, Taghiloo J. Enhancing AODV routing protocol using mobility parameters in VANETs[C]//Proceedingsofthe2008IEEE/ACSInternationalConferenceonComputerSystemsandApplications. Washington DC, USA, 2008: 229-235.

[7]Namboodiri V, Gao L. Prediction-based routing for vehicular ad hoc networks [J].IEEETransactionsonVehicularTechnology, 2007,56(4): 2332-2345.

[8]Lee Y, Lee H, Choi N, et al. Macro-level and micro-level routing (MMR) for urban vehicular ad hoc networks [C]//Proceedingsof2007IEEEGlobalTelecommunicationsConference. Washington DC, USA, 2007: 715-719.

[9]Korkmaz G, Ekici E, Ozguner F. Black-burst-based multihop broadcast protocols for vehicular,networks [J].IEEETransactionsonVehicularTechnology, 2007,56(5): 3159-3167.

[10]Xu Q, Mak T, Ko J, et al. Medium access control protocol design for vehicle-vehicle safety messages [J].IEEETransactionsonVehicularTechnology, 2007,56(2): 499-518.