基于拓?fù)溥B通概率的車(chē)載自組織網(wǎng)絡(luò)路由算法

陶 軍 肖 鵬 劉 瑩 陳文強(qiáng)

(東南大學(xué)教育部計(jì)算機(jī)網(wǎng)絡(luò)和信息集成重點(diǎn)實(shí)驗(yàn)室,南京210096)

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

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

1 網(wǎng)絡(luò)模型

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

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

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

fexp=aexp(-∑Pi)

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

∑Pi=∑Pj+1

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

2 RPR算法

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

2.1 廣播風(fēng)暴的抑制

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

2.2 鄰居概率之和的計(jì)算

由文獻(xiàn)[1]可知,利用REAR算法計(jì)算鄰居概率之和的算法過(guò)于繁瑣,并且?guī)?lái)了一些負(fù)面效應(yīng),如計(jì)算量過(guò)大、部分?jǐn)?shù)據(jù)不能夠反映路由的真正走向等.此外,REAR算法需要同時(shí)考慮上一跳節(jié)點(diǎn)和下一跳節(jié)點(diǎn)的接收概率,導(dǎo)致不能夠正確選擇下一跳節(jié)點(diǎn).在本文算法中,節(jié)點(diǎn)只計(jì)算下一跳節(jié)點(diǎn)的接收概率,減少了不必要的運(yùn)算,從而提高了算法的效率.

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

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

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

3 仿真實(shí)驗(yàn)

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

3.1 場(chǎng)景設(shè)置與描述

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

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

3.2 結(jié)束時(shí)間與節(jié)點(diǎn)密度

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

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

圖3 結(jié)束時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系

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

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

圖4 節(jié)點(diǎn)覆蓋率與節(jié)點(diǎn)數(shù)的關(guān)系

3.4 輔助報(bào)文數(shù)量與節(jié)點(diǎn)密度

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

圖5 輔助報(bào)文數(shù)量與節(jié)點(diǎn)數(shù)的關(guān)系

3.5 覆蓋率與時(shí)間

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

圖6 覆蓋率與時(shí)間的關(guān)系

4 結(jié)語(yǔ)

本文提出了一種基于拓?fù)溥B通概率的車(chē)載自組織網(wǎng)絡(luò)路由算法——RPR算法.從覆蓋率、輔助報(bào)文數(shù)量和結(jié)束時(shí)間等3個(gè)方面對(duì)REAR算法和RPR算法進(jìn)行了比較.結(jié)果表明,RPR算法可將廣播報(bào)文數(shù)量減少至REAR算法的78%,數(shù)據(jù)通信時(shí)間縮短至原算法的72%,覆蓋率則由原來(lái)的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.