程青青, 陳戈珩

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

1 VANET介紹

車載自組織網(wǎng)絡(luò)(VANET)在智能交通系統(tǒng)(ITS)架構(gòu)中發(fā)揮著關(guān)鍵作用。VANET應(yīng)用程序可以分為兩大類：一類解決行車安全，稱之為安全應(yīng)用；另一類提供增值業(yè)務(wù)，如滿足乘客在車輛環(huán)境中的娛樂等功能，稱之為用戶應(yīng)用。據(jù)文獻(xiàn)[1]報(bào)道，如果汽車駕駛員在發(fā)生碰撞前0.5 s被予以示警，就可以避免60%的交通事故。因此，利用VANET向分散在稀疏區(qū)域的車輛傳播警告信息尤為重要,且具有挑戰(zhàn)性。

在過去十年中，專用短距離通信(DSRC)協(xié)議的發(fā)展?jié)M足了VANET安全和非安全應(yīng)用的需求[2]。VANET中車輛之間的通信主要取決于DSRC的機(jī)制，可以通過兩種方式完成：一種是車與車之間的通信(V2V)，道路上的每輛車都會(huì)向特定車輛發(fā)送消息；另一種是車輛與路邊單元的通信(V2R)[3-5]。廣播通信作為VANET應(yīng)用程序的基石，主要用于V2R或道路上的V2V廣播消息。假設(shè)路邊車輛可以周期性地廣播道路狀況消息，當(dāng)每個(gè)車輛第一次接收到該消息時(shí)都會(huì)以多跳的方式將接收到的消息廣播給鄰居車輛，鄰居車輛接收到消息后也會(huì)向其它車輛節(jié)點(diǎn)繼續(xù)有序地廣播已經(jīng)接收的消息，這樣就很好地避免了信息堵塞問題。傳統(tǒng)廣播方法“泛洪”在傳播消息時(shí)會(huì)將已經(jīng)接收到的消息充斥整個(gè)網(wǎng)絡(luò)，從而保證所有消息能夠廣播到每一輛車，在這一過程中會(huì)造成大量的冗余廣播消息，以及信道資源的浪費(fèi)。在VANET中這樣大型的可擴(kuò)展網(wǎng)絡(luò)使用泛洪的方式，會(huì)大大降低廣播消息的性能，因?yàn)榇罅康娜哂鄰V播消息會(huì)讓車輛在傳輸消息時(shí)無限制地競(jìng)爭(zhēng)信道資源。在移動(dòng)自組織網(wǎng)絡(luò)(MANET)中將這種現(xiàn)象稱之為“廣播風(fēng)暴”(BSP)，用于解決廣播風(fēng)暴的方法有4種[6]：1)基于概率的廣播協(xié)議；2)基于泛洪的廣播協(xié)議;3)基于區(qū)域的廣播協(xié)議;4)基于鄰居節(jié)點(diǎn)的廣播協(xié)議。這4種方案在MANET環(huán)境中得到了廣泛應(yīng)用，有效地抑制了“廣播風(fēng)暴”產(chǎn)生的不良影響[7-11]。但是在VANET中對(duì)于“廣播風(fēng)暴”的抑制研究還處于初級(jí)階段[12-13]，為了填補(bǔ)研究上的空白，文中給出一種新型的解決“廣播風(fēng)暴”問題的方案，并從消息的可達(dá)性和消息的存儲(chǔ)重播這兩個(gè)性能入手來驗(yàn)證方案的可實(shí)施性。

2 傳統(tǒng)的VANET廣播傳播方案

文獻(xiàn)[14]通過對(duì)單車道和多車道的高速公路情景模擬探討了BSP在VANET中的降級(jí)效應(yīng)，提出了三種基于概率的計(jì)時(shí)器廣播方案，通過對(duì)消息延遲率和丟包率來評(píng)估廣播方案的性能。其中第一種方案將每一輛車的廣播概率都設(shè)置為概率1進(jìn)行廣播。第二種方案是將每輛車的概率值設(shè)為固定概率P,通過實(shí)驗(yàn)驗(yàn)證，當(dāng)概率P值取0.5時(shí),網(wǎng)絡(luò)性能達(dá)到最大化程度，但是這種方案在實(shí)施過程中仍然存在大量的冗余信息，為了解決這一問題就需要多方面考慮P的取值問題，選取最合適的P值使網(wǎng)絡(luò)性能達(dá)到最佳狀態(tài)。第三種方案將允許通過的每個(gè)車輛作為廣播消息的發(fā)送器，在傳輸范圍內(nèi)依據(jù)車輛接收消息的機(jī)率分配概率值的大小，然后再根據(jù)概率的大小來廣播消息。文獻(xiàn)[15]提出了城市多跳廣播協(xié)議(UMB)來解決“廣播風(fēng)暴”問題，主要是在確定鄰居節(jié)點(diǎn)個(gè)數(shù)和多跳廣播可靠性方面進(jìn)行改進(jìn)，通過實(shí)驗(yàn)驗(yàn)證該協(xié)議在高分組負(fù)載和不同網(wǎng)絡(luò)密度的情況下依舊能夠保證高效的廣播傳輸效率，但需要安裝中繼器，這樣就會(huì)造成額外的硬件消耗和功耗的損失。通過對(duì)UMB協(xié)議的擴(kuò)展，文獻(xiàn)[16]提出了基于點(diǎn)對(duì)點(diǎn)(Ad-hoc)的AMB多跳廣播協(xié)議。這種廣播協(xié)議在交叉路口進(jìn)行廣播消息時(shí)可以不依賴于中繼器，采用定向廣播的方法完成遠(yuǎn)距離車輛消息廣播。傳統(tǒng)方案是通過確定源節(jié)點(diǎn)車輛對(duì)于緊急消息的廣播方向來抑制“廣播風(fēng)暴”的方案,由于沒有對(duì)存儲(chǔ)的廣播消息進(jìn)行量化，無法采用特定方法對(duì)這種廣播方案進(jìn)行合理的性能評(píng)估。文獻(xiàn)[17]提出了一種基于車輛間通信的廣播方案來接收和發(fā)送車輛的位置、方向和速度信息,這種方案不僅解決了端到端的傳輸延遲和傳輸時(shí)間的延遲,還通過忽略新增車輛節(jié)點(diǎn)的消息重傳來最小化“廣播風(fēng)暴”問題。

3 自適應(yīng)加權(quán)概率持久性方案(AWPP)

通過對(duì)傳統(tǒng)方法的研究可知，VANET的有效廣播協(xié)議必須在消息可達(dá)性和消息重播率之間達(dá)到一個(gè)平衡的狀態(tài)，為了實(shí)現(xiàn)最佳的廣播傳輸方案，文中給出了一種自適應(yīng)加權(quán)概率持久性方案(AWPP)，這是基于傳統(tǒng)的加權(quán)概率持久性方案(WPP)的基礎(chǔ)上進(jìn)行改進(jìn)的。在傳統(tǒng)的WPP中，每個(gè)車輛接收到的數(shù)據(jù)包概率為

(1)

式中:Dij----節(jié)點(diǎn)i和j之間的相對(duì)距離;

R----平均傳輸范圍。

根據(jù)WPP協(xié)議，如果車輛從多個(gè)廣播源接收消息，車輛會(huì)在廣播消息之前等待一段時(shí)間來確保以低概率重播，相同距離車輛的重播概率相同。采用這種形式的廣播方式在高密度VANET中會(huì)導(dǎo)致“廣播風(fēng)暴”，在稀疏密度VANET中會(huì)導(dǎo)致重播概率非常低，消息可達(dá)性差。因此,針對(duì)傳統(tǒng)方案中存在的問題，對(duì)轉(zhuǎn)發(fā)概率方案進(jìn)行了改進(jìn)。WPP方案的缺點(diǎn)如圖1所示 。

圖1 WPP方案的缺點(diǎn)

圖1說明了上述的兩種情況。假設(shè)車輛S在250 m的傳輸范圍內(nèi)廣播消息，距車輛C,E,F,G,H之間的距離D分別為5、100、100、125、125 m。那么通過式(1)計(jì)算出每輛車的廣播概率分別為0.02、0.4、0.4、0.5和0.5。通過觀察可以知道,車輛C發(fā)出的廣播消息不會(huì)到達(dá)車輛A和車輛B，而車輛在廣播的過程中將會(huì)收到重復(fù)的廣播消息。這種傳播方式就會(huì)造成車輛之間在接收和發(fā)送消息的過程中發(fā)生紊亂，尤其是在車輛分布密集的VANET中，這種現(xiàn)象會(huì)更加突出。為了解決這一問題，給出了一種通用的概率方法，可以根據(jù)每輛車的實(shí)時(shí)局部密度情況來動(dòng)態(tài)地調(diào)整每一輛車的轉(zhuǎn)發(fā)概率?？梢酝ㄟ^使用“HELLO”分組來收集鄰居節(jié)點(diǎn)的信息，在每輛車的位置構(gòu)建一跳的鄰居,從而估計(jì)出本地網(wǎng)絡(luò)的密集程度。

AWPP協(xié)議的算法步驟:

Begin

{

Step1:記錄車輛Vr在第一次接收到廣播消息msg

Step2:獲取發(fā)送消息車輛Vs和接收消息車輛Vr之間的距離d

Step3:獲取接收消息車輛Vr的鄰居節(jié)點(diǎn)數(shù)量Nn

Step4:得到平均網(wǎng)絡(luò)鄰居節(jié)點(diǎn)數(shù)目Navg

Step5:IF dNavgTHEN

Vr位于密集區(qū)域

Vr和Vs在相距較近的廣播覆蓋范圍內(nèi)

當(dāng)Vr的最小傳播概率P=Plow時(shí)跳轉(zhuǎn)到step 7

Step6:IF d>r/2 and Nn

Vr位于稀疏區(qū)域

Vr和Vs在相距較遠(yuǎn)的廣播覆蓋范圍內(nèi)

當(dāng)Vr的最大傳播概率P=Phigh時(shí)跳轉(zhuǎn)到step 7

Step7:IF (Random::uniform(0,0,0,1)≤P)

Forward(msg)

Else

Free(msg)

}

End

對(duì)于給定的區(qū)域拓?fù)鋱?chǎng)景，則可以給出定義式

(2)

式中：N----網(wǎng)絡(luò)中的車輛總數(shù);

Xi----特定時(shí)刻車輛Vi處的鄰居節(jié)點(diǎn)數(shù)量;

Navg----車聯(lián)網(wǎng)中的網(wǎng)絡(luò)平均鄰居節(jié)點(diǎn)數(shù)量。

每個(gè)車輛節(jié)點(diǎn)會(huì)在1 s時(shí)間內(nèi)定期廣播“HELLO”數(shù)據(jù)包，在一跳的廣播距離范圍內(nèi)收集Xi值。Vi值則需要根據(jù)此時(shí)的網(wǎng)絡(luò)環(huán)境是密集區(qū)域還是稀疏區(qū)域來確定。在特定時(shí)刻圍繞在Vi周圍的車輛數(shù)量高于Navg時(shí)，此時(shí)意味著Vi處于密集區(qū)域，否則處于稀疏區(qū)域。在確定完Vi值后，每一個(gè)車輛節(jié)點(diǎn)都會(huì)依據(jù)當(dāng)時(shí)自己所處節(jié)點(diǎn)的實(shí)時(shí)狀態(tài)來決定是否將自己收到的消息廣播給其他的車輛節(jié)點(diǎn)。由于資源和時(shí)間有限,在實(shí)驗(yàn)過程中只能廣泛地進(jìn)行模擬實(shí)驗(yàn)，找出Navg的近似值。

不同路況下Navg的取值見表1。

表1 不同車輛和道路數(shù)量的預(yù)期平均鄰居節(jié)點(diǎn)數(shù)量匯總

AWWP協(xié)議在邏輯上將道路狀況分為稀疏型和密集型，將Navg值作為判斷道路是稀疏還是密集的閾值，車輛在每個(gè)位置都具有不同的概率值P,在密集區(qū)域的轉(zhuǎn)發(fā)概率公式

(3)

在稀疏區(qū)域的轉(zhuǎn)發(fā)概率公式

(4)

某些特殊情況下，概率值P可能小于零或者大于1。在小于零的情況下，意味著車輛距離源發(fā)送節(jié)點(diǎn)的距離非常近，并且處在車輛非常密集的區(qū)域中，這時(shí)就需要通過編碼來將概率值P調(diào)整為零。如果概率值超過1，就意味著車輛距離源發(fā)送節(jié)點(diǎn)非常遠(yuǎn)并且車輛處在非常稀疏的區(qū)域中，此時(shí)需要將概率值P調(diào)整為1。不同距離和鄰居節(jié)點(diǎn)數(shù)對(duì)應(yīng)的概率值見表2。

表2 不同距離和鄰居節(jié)點(diǎn)對(duì)應(yīng)的概率值

每一輛車在接收消息之前都會(huì)存在等待延遲時(shí)間，也就是不同概率值在接收廣播消息時(shí)對(duì)應(yīng)的初始計(jì)數(shù)器等待時(shí)間TWAIT_TIME。如果車輛在Tmax時(shí)段內(nèi)接收到重復(fù)的消息就需要運(yùn)用式(3)來計(jì)算此時(shí)的轉(zhuǎn)發(fā)概率，否則用式(4)來計(jì)算。文中將給出計(jì)算廣播延遲時(shí)間：

TWAIT_TIME=Tmax*T0,

(5)

(6)

式中：T0----車輛密度與其距離發(fā)送者距離之間的關(guān)系。

根據(jù)文獻(xiàn)[20]給出的經(jīng)驗(yàn)，Tmax的值要在[0,2 ms]之間均勻生成，這就意味著擁有多鄰居節(jié)點(diǎn)的車輛會(huì)用很長一段時(shí)間重復(fù)廣播，而擁有少鄰居節(jié)點(diǎn)的車輛則會(huì)用較短的時(shí)間重復(fù)廣播。

4 仿真驗(yàn)證

為了驗(yàn)證文中給出方案的可行性，運(yùn)用NS-2.34軟件和曼哈頓模型進(jìn)行仿真實(shí)驗(yàn)，在以往的研究中也運(yùn)用過相似的方法，將車輛放置在一個(gè)2 km×2 km的區(qū)域，放置時(shí)間為15 min。實(shí)驗(yàn)過程中,將模擬區(qū)域劃分為2個(gè)水平街道和2個(gè)垂直街道，這樣一來會(huì)形成4個(gè)交叉點(diǎn)。在每一個(gè)交叉路口車輛在向左轉(zhuǎn)還是向右轉(zhuǎn)的概率為0.5,是確定值。每一條街都有兩條車道，車輛可以在車道兩側(cè)移動(dòng)，在250 m的可靠傳輸范圍內(nèi)滿足DSRC近似標(biāo)準(zhǔn)范圍數(shù)據(jù)傳輸準(zhǔn)則。通過改變車道上車輛的數(shù)量來改變交通流密度從低到高的變化，用來模擬高峰時(shí)段和非高峰時(shí)段的情形，車輛數(shù)量分別為25、100 輛/km。由于城市環(huán)境中車輛速度多變，為了使實(shí)驗(yàn)更加接近真實(shí)城市道路，使用不同的速度來進(jìn)行試驗(yàn)。在交通狀況擁擠時(shí)車輛的最大移動(dòng)速度為60 km/h，最低速度為30 km/h。將AWWP協(xié)議和傳統(tǒng)的WPP[18]協(xié)議、簡(jiǎn)單泛洪(SF)協(xié)議進(jìn)行對(duì)比仿真實(shí)驗(yàn)，模擬實(shí)驗(yàn)參數(shù)見表3。

表3 對(duì)比參數(shù)值

實(shí)驗(yàn)結(jié)果表明，對(duì)于多個(gè)冗余信息和傳輸覆蓋區(qū)域，重復(fù)廣播概率P的取值不同，產(chǎn)生的結(jié)果也不相同。實(shí)驗(yàn)中，通過改變車輛數(shù)量(車輛數(shù)量從10 輛/km變?yōu)?00 輛/km)來驗(yàn)證不同交通狀況下的情景。文獻(xiàn)[19-20]通過對(duì)兩個(gè)重要指標(biāo)參數(shù)減少重復(fù)消息廣播概率Saved Rebroadcast(SR)和消息可達(dá)率Reachability(RE)對(duì)概率方案進(jìn)行了驗(yàn)證。

SR可定義為

(6)

RE可定義為

(7)

式中:N----車聯(lián)網(wǎng)中的車輛數(shù);

r----車輛接收的消息數(shù)量。

通過仿真實(shí)驗(yàn)驗(yàn)證了不同車聯(lián)網(wǎng)密度狀態(tài)下AWWP協(xié)議、WPP協(xié)議和SF協(xié)議在減少重復(fù)消息廣播概率和消息可達(dá)率的性能指標(biāo)。仿真實(shí)驗(yàn)時(shí)，車輛數(shù)的變化區(qū)間為[25 輛/km,100 輛/km]，車速的變化區(qū)間為[20 km/h,60 km/h]。通過實(shí)驗(yàn)數(shù)據(jù)圖可以發(fā)現(xiàn)，AWWP協(xié)議不管是在密集區(qū)域還是在稀疏區(qū)域的網(wǎng)絡(luò)廣播性能都優(yōu)于SF協(xié)議和WPP協(xié)議。三種協(xié)議在不同車輛密度下的減少重復(fù)消息廣播概率比較如圖2所示。

圖2 三種協(xié)議在不同車輛密度下的減少重復(fù)消息廣播概率比較

通過仿真實(shí)驗(yàn)數(shù)據(jù)可以看出：車輛數(shù)量為100 輛/km時(shí)，AWWP協(xié)議的SR值為73%,遠(yuǎn)高于WPP協(xié)議的39%和SF協(xié)議的0%;車輛數(shù)量為10 輛/km時(shí)，AWWP協(xié)議的SR值為31%,遠(yuǎn)高于WPP協(xié)議的15%和SF協(xié)議的0%。由此可見，AWWP協(xié)議可以廣泛應(yīng)用于不同車流量密度的場(chǎng)景，不僅在密集區(qū)域的性能遠(yuǎn)優(yōu)于其它兩種協(xié)議在稀疏區(qū)域的性能,也遠(yuǎn)優(yōu)于其它兩種協(xié)議性能。

在可達(dá)率(RE)方面，隨著車流量密度的增加，RE值也隨之增加。三種協(xié)議在不同車輛密度下的消息可達(dá)率比較如圖3所示。

圖3 三種協(xié)議在不同車輛密度下的消息可達(dá)率比較

車輛數(shù)量增加到70 輛/km時(shí)，三種協(xié)議的可達(dá)率(RE)都近似接近100%，這就意味著AWWP協(xié)議實(shí)現(xiàn)了密集車聯(lián)網(wǎng)級(jí)別的泛洪可達(dá)率。在稀疏區(qū)域的車聯(lián)網(wǎng)中，SF協(xié)議的性能要略優(yōu)于AWWP協(xié)議，而WPP協(xié)議的性能則是最差的。

仿真數(shù)據(jù)驗(yàn)證了AWWP協(xié)議、SF協(xié)議和WPP協(xié)議的網(wǎng)絡(luò)性能。三種協(xié)議在不同車輛速度下的減少重復(fù)消息廣播概率能力及消息可達(dá)率分別如圖4和圖5所示。

圖4 三種協(xié)議在不同車輛速度下的減少重復(fù)消息廣播概率能力比較

若將網(wǎng)絡(luò)密度設(shè)定為70 輛/km，取30 km/h到80 km/h之間的不同速度值來進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明,AWWP協(xié)議相比于SF協(xié)議和WPP協(xié)議在車輛速度多變的情況下有更好的適應(yīng)性，顯著地降低了重復(fù)消息廣播概率，有效避免了廣播風(fēng)暴。在消息可達(dá)率方面，AWWP協(xié)議在車速高于60 km/h時(shí)，消息可達(dá)率幾乎達(dá)到100%，雖然車速低于60 km/h 時(shí)，消息可達(dá)率略低于SF協(xié)議，但是綜合減少重復(fù)消息廣播概率參數(shù)SR的性能指標(biāo)，AWWP協(xié)議的優(yōu)勢(shì)是顯而易見的。

5 結(jié) 語

給出了一種用于解決廣播風(fēng)暴問題的AWWP協(xié)議，通過仿真模擬實(shí)驗(yàn)驗(yàn)證了AWWP協(xié)議的性能優(yōu)勢(shì)。AWWP協(xié)議相比于傳統(tǒng)的WPP協(xié)議和SF協(xié)議，在減少重復(fù)消息廣播概率和消息可達(dá)率上的不足進(jìn)行了彌補(bǔ)，解決了“廣播風(fēng)暴”問題。在實(shí)際的應(yīng)用中，廣播消息的傳播覆蓋率和車輛節(jié)點(diǎn)之間消息的可達(dá)性較傳統(tǒng)多跳廣播協(xié)議更具有優(yōu)越性。