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

陶 軍 肖 鵬 劉 瑩 陳文強

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

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

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

1 網絡模型

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

圖1 REAR算法狀態轉換圖

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

fexp=aexp(-∑Pi)

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

∑Pi=∑Pj+1

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

2 RPR算法

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

2.1 廣播風暴的抑制

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

2.2 鄰居概率之和的計算

由文獻[1]可知,利用REAR算法計算鄰居概率之和的算法過于繁瑣,并且帶來了一些負面效應,如計算量過大、部分數據不能夠反映路由的真正走向等.此外,REAR算法需要同時考慮上一跳節點和下一跳節點的接收概率,導致不能夠正確選擇下一跳節點.在本文算法中,節點只計算下一跳節點的接收概率,減少了不必要的運算,從而提高了算法的效率.

2.3 延遲函數的假象條件

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

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

3 仿真實驗

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

3.1 場景設置與描述

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

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

3.2 結束時間與節點密度

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

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

圖3 結束時間與節點數的關系

3.3 節點覆蓋率與節點密度

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

圖4 節點覆蓋率與節點數的關系

3.4 輔助報文數量與節點密度

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

圖5 輔助報文數量與節點數的關系

3.5 覆蓋率與時間

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

圖6 覆蓋率與時間的關系

4 結語

本文提出了一種基于拓撲連通概率的車載自組織網絡路由算法——RPR算法.從覆蓋率、輔助報文數量和結束時間等3個方面對REAR算法和RPR算法進行了比較.結果表明,RPR算法可將廣播報文數量減少至REAR算法的78%,數據通信時間縮短至原算法的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.