車聯(lián)網(wǎng)中基于概率和網(wǎng)絡(luò)密度的多跳廣播協(xié)議

程青青 陳戈珩

摘要

車載網(wǎng)絡(luò)最重要的應(yīng)用就是安全信息的傳播。不受控制的重播導(dǎo)致相同信息的冗余重傳、頻繁的信道沖突以及網(wǎng)絡(luò)資源耗盡。為了使網(wǎng)絡(luò)冗余和延遲最小化，同時確保整個網(wǎng)絡(luò)的高可靠性，本文采用了基于概率的多跳廣播方法來解決可靠性和延遲的問題在本文中，給出了一種新的基于概率的多跳廣播協(xié)議，與現(xiàn)有的概率分配方案不同，本協(xié)議不僅考慮了本地的信息，還考慮了轉(zhuǎn)發(fā)概率中一跳范圍內(nèi)的車輛數(shù)量，可以通過調(diào)整轉(zhuǎn)發(fā)概率的基本參數(shù)來獲得更高的轉(zhuǎn)發(fā)成功率。在參數(shù)設(shè)定的過程中，將更高的轉(zhuǎn)發(fā)概率分配給更靠近源節(jié)點的傳輸邊界的節(jié)點。我們比較了網(wǎng)絡(luò)轉(zhuǎn)發(fā)成功概率、平均次數(shù)和平均信道訪問延遲時間通過對仿真參數(shù)的記錄，證明了所給出的廣播協(xié)議具有高可靠性和有效性。

【關(guān)鍵詞】車載網(wǎng)絡(luò) 概率 網(wǎng)絡(luò)密度 多跳廣播

1 VANET介紹

依據(jù)車載自組織網(wǎng)絡(luò)對于緊急信息必須及時、可靠地傳播到相關(guān)區(qū)域內(nèi)的所有車輛的特性提出了多種多跳廣播方案來增強(qiáng)緊急消息傳播的性能。這種多跳廣播方案解決了單跳廣播的覆蓋區(qū)域不夠大的問題，可以保證目標(biāo)區(qū)域內(nèi)的每個車輛都能夠成功的接收消息?，F(xiàn)有的多跳廣播可以分為三類：基于時間、基于編碼和基于概率的方法，這三類多跳廣播方案都能增強(qiáng)緊急消息傳播協(xié)議的性能。在本文中，主要專注于研究基于概率的多跳廣播。

1.1 基于時間的多跳廣播

文獻(xiàn)[1]中給出一種適應(yīng)于高速公路的基于時間的快速轉(zhuǎn)發(fā)協(xié)議，稱為DEEP。假設(shè)在高速公路上運行的每一輛車的位置和所屬的區(qū)域都是已知的，當(dāng)車輛接收到緊急消息，會依據(jù)與源車輛之間的距離來計算延遲時間。通過實驗測試，DEEP多跳廣播協(xié)議有效的解決了廣播風(fēng)暴問題，大大縮短了廣播延遲時間，具有較高的可靠性，唯一不足之處是這種多跳廣播機(jī)制需要依賴于高精度GPS定位和本地地理信息。為了解決這種不足，文獻(xiàn)[2]z中提出了一種健壯性較好的快速轉(zhuǎn)發(fā)協(xié)議（ROFF）。它通過計算等待時間來避免潛在的轉(zhuǎn)發(fā)器候選（PFC）之間的傳輸沖突。ROFF令每個PFC的等待時間與其轉(zhuǎn)發(fā)優(yōu)先級成反比，該轉(zhuǎn)發(fā)優(yōu)先級是基于空白空間分布（ESD）的位圖計算的。ESD位圖存儲了前一個轉(zhuǎn)發(fā)器和轉(zhuǎn)發(fā)器候選者之間距離的信息。

1.2 基于編碼的多跳廣播

文獻(xiàn)[3]中提出了一種關(guān)于V2V通信的網(wǎng)絡(luò)編碼方法，這種網(wǎng)絡(luò)編碼為每個中間節(jié)點提供轉(zhuǎn)發(fā)前不同接收分組的能力。在文獻(xiàn)[4]中將XOR和RS編碼技術(shù)應(yīng)用于確定性廣播方法（CODEB），有效的降低了整個網(wǎng)絡(luò)的傳輸次數(shù)。文獻(xiàn)[5]中提出了一種新的協(xié)議（EBNC），它將網(wǎng)絡(luò)編碼技術(shù)與概率轉(zhuǎn)發(fā)算法相結(jié)合，這種結(jié)合方式可以運用網(wǎng)絡(luò)編碼來減少協(xié)議開銷，提高分組接收概率。研究表明，CODEB和EBNC多跳廣播協(xié)議在節(jié)點移動速度較快的情況下具有脆弱性，在高速變化的車載網(wǎng)絡(luò)中，這兩種方法顯現(xiàn)出很大的劣勢。

1.3 基于概率的多跳廣播

基于概率的多跳廣播協(xié)議在重新廣播消息之前不需要額外的等待時間，允許每個節(jié)點以預(yù)定的概率立即重新廣播。最簡單的基于概率的多跳廣播稱為泛洪，在泛洪中，每個節(jié)點在源節(jié)點接收到緊急消息之后會立即以概率1重新廣播該分組，這種廣播方法會導(dǎo)致廣播風(fēng)暴和過多的數(shù)據(jù)冗余，在密集的無線車載網(wǎng)絡(luò)中這一缺陷也表現(xiàn)的更加明顯。文獻(xiàn)[6]中提出了一種加權(quán)p的持續(xù)廣播（WPB）方案來避免重復(fù)廣播的問題，可以表示為：

p=（d/R）（1）

d：表示從當(dāng)前位置到源車輛的距離;

R：表示每輛車的傳輸半徑;

P：表示重播的概率;

這種轉(zhuǎn)發(fā)方案實現(xiàn)了從傳播范圍一半到范圍邊界之間的所有節(jié)點的轉(zhuǎn)發(fā)概率超過了50%，因此，在密集的VANET中會導(dǎo)致嚴(yán)重的沖突和端到端的延遲。在文獻(xiàn)[7]中，L.Zhou改進(jìn)了WPB方案并提出了NPPB協(xié)議，此時的轉(zhuǎn)發(fā)概率為：

K：表示NPPB協(xié)議中的轉(zhuǎn)發(fā)概率系數(shù)。

其中K的值越大，分配給源節(jié)點附近的轉(zhuǎn)發(fā)概率越小，NPPB在密集的VANET環(huán)境中，協(xié)議的性能要優(yōu)于WPB，但是當(dāng)傳輸范圍附近的區(qū)域內(nèi)沒有足夠的車輛時，能夠傳輸成功的概率將明顯降低。文獻(xiàn)[8]中提出了基于概率的不確定轉(zhuǎn)發(fā)方案（IF），此時的轉(zhuǎn)發(fā)概率變?yōu)椋海罕硎疽话丬囕v間距下分布的均值指數(shù)假設(shè)值。

研究表明，此時的轉(zhuǎn)發(fā)概率分布可以適應(yīng)車輛密度[9]。在對IF方案進(jìn)行真實車輛間距分布的評估中發(fā)現(xiàn)IF方案的節(jié)點難以察覺間距分布[10]，該方案仍然無法解決當(dāng)傳輸范圍的邊界區(qū)域車輛較少時導(dǎo)致的傳輸成功概率低的問題。

2 算法模型

本文提出了一種新的多跳廣播算法來解決密集VANET中的網(wǎng)絡(luò)沖突問題。為了更好地應(yīng)用于不同的車輛密度發(fā)揮網(wǎng)絡(luò)性能的優(yōu)越性，轉(zhuǎn)發(fā)概率會依據(jù)實時車輛密度的變化而變化。不僅可以在第一時間成功轉(zhuǎn)發(fā)緊急消息還減少了數(shù)據(jù)包的延遲，在轉(zhuǎn)發(fā)的過程中減少了重復(fù)消息的傳播，還引入了參數(shù)k來提高消息轉(zhuǎn)發(fā)成功的概率。

2.1 網(wǎng)絡(luò)建模

給出假定情景下的網(wǎng)絡(luò)模型：

（1）假設(shè)車輛的傳輸范圍R;

（2）假設(shè)車輛均勻地分布，車輛間空間為V_S=N/R，其中N指的是一跳范圍內(nèi)的節(jié)點總數(shù);

（3）每輛車都會配備全球定位系統(tǒng)（GPS），所以每輛車都可以隨時隨地知道的自己的精準(zhǔn)定位。

如圖1所示，假設(shè)筆直的公路為一維模型。定義f_i，i∈{1，2，…，N）函數(shù)，其中N表示在一跳范圍內(nèi)的最大車輛數(shù)，節(jié)點i到源節(jié)點的距離用d_i表示，源節(jié)點用s表示，源節(jié)點的傳輸范圍用R表示。當(dāng)源節(jié)點S遇到緊急情況，它會廣播一個緊急包給傳輸范圍內(nèi)的所有鄰居節(jié)點，當(dāng)所有鄰居節(jié)點接收到源節(jié)點發(fā)送的數(shù)據(jù)包會開始存儲并計算轉(zhuǎn)發(fā)概率。這里將源節(jié)點傳播的最遠(yuǎn)范圍記為一跳的傳播距離，在分配轉(zhuǎn)發(fā)概率時，給最遠(yuǎn)的節(jié)點分配最高的轉(zhuǎn)發(fā)概率。在設(shè)計多跳廣播協(xié)議時，要最大化提高轉(zhuǎn)發(fā)成功概率、減少單跳廣播中的廣播延遲和增強(qiáng)單跳轉(zhuǎn)發(fā)的可靠性。定義RE來表示單跳轉(zhuǎn)發(fā)的可靠性，p_i，i∈（1，2，…，N）表示節(jié)點的轉(zhuǎn)發(fā)概率，P_S表示一跳的轉(zhuǎn)發(fā)成功概率，系數(shù)用λ，λ∈（0，1）。在傳播的過程中，要保證至少有一個節(jié)點能夠把緊急消息傳播至源節(jié)點的傳播邊界。因此，可以得到：

其中λ_opt表示λ的最優(yōu)值。

2.2 理論分析

給出新的轉(zhuǎn)發(fā)概率公式，定義為：將距離源節(jié)點最遠(yuǎn)的距離定義為d₁，N表示一跳范圍內(nèi)的節(jié)點總數(shù)，λ用于調(diào)整轉(zhuǎn)發(fā)成功概率的系數(shù)。

2.2.1 轉(zhuǎn)發(fā)成功的概率

由于傳輸距離足夠短，假設(shè)每個節(jié)點接收到數(shù)據(jù)包的時段是相同的。當(dāng)數(shù)據(jù)包傳來之后，所有的節(jié)點就會共同競爭信道，此時信道的狀態(tài)有三種可能的情況：空閑、成功傳輸或者沖突。信道處于空閑、成功傳輸或者沖突對應(yīng)的三種情況分別是沒有節(jié)點、只有一個節(jié)點或者超過一個節(jié)點在一個空時隙開始的時候請求信道發(fā)送。我們將只有一個節(jié)點在一個空時隙開始時請求信道發(fā)送，并獲得信道成功發(fā)送緊急消息的概率記為P_S。當(dāng)每個節(jié)點都以相同的轉(zhuǎn)發(fā)概率p轉(zhuǎn)發(fā)數(shù)據(jù)包時，得到公式：

定義成功轉(zhuǎn)發(fā)概率的公式為：

另外，平均副本數(shù)量的定義如下：

其中P_cn表示n個節(jié)點在沒有任何退避情況下轉(zhuǎn)發(fā)接收到的數(shù)據(jù)包概率，當(dāng)節(jié)點計算的轉(zhuǎn)發(fā)概率大于隨機(jī)生成的概率時，該節(jié)點就獲得了轉(zhuǎn)發(fā)權(quán)。

2.2.2 平均時延

在IEEE802.11（WIFI）的標(biāo)準(zhǔn)修訂版本，DSRC在PHY和MAC層中將IEEE802.11p無線協(xié)議用于車載自組織網(wǎng)絡(luò)（VANET）中，IEEE802.11p是基于分布式協(xié)調(diào)函數(shù)（DCF）的廣播協(xié)議，在DCF中使用載波感知多址機(jī)制（CSMA/CA）來爭奪信道。為了減少碰撞的發(fā)生，DCF采用信道感知檢測信道活動和截斷二進(jìn)制指數(shù)退避隨機(jī)化分組傳輸?shù)拈_始時間[11].其中信道的訪問延遲可以表示為：

其中：

P_bi表示信道忙時數(shù)據(jù)包占用第i個信道時的概率，Q表示最大回放級的數(shù)目，T⁰是一個隨機(jī)變量，表示成功發(fā)送數(shù)據(jù)包占用的信道時間。Ts表示一個時隙，CW₀表示競爭窗口值，那么一跳的延遲時間就可以表示為：

2.3 多跳廣播協(xié)議

源節(jié)點車輛遇到緊急情況時，需要盡快向車流量的相反方向節(jié)點廣播緊急消息，假設(shè)整個車輛網(wǎng)絡(luò)有效連接，傳輸范圍內(nèi)的所有車輛都可以有效地接收廣播包。

（1）源節(jié)點會將數(shù)據(jù)包廣播到傳輸范圍內(nèi)的所有節(jié)點，包括事件ID、GPS坐標(biāo)和行駛方向，還會把緊急數(shù)據(jù)包存儲到緩沖區(qū)。

（2）在廣播緊急消息包后，源節(jié)點會啟動倒計時（這個計數(shù)器的初始值是在網(wǎng)絡(luò)中預(yù)先確定的），在計數(shù)器時間減為零后，如果還沒有任何節(jié)點接收到原始廣播數(shù)據(jù)包，源節(jié)點會重新發(fā)送存儲在緩沖區(qū)的數(shù)據(jù)包，否則將刪除緩沖區(qū)存儲的數(shù)據(jù)包。

（3）鄰居節(jié)點接收到緊急包之后，每一個節(jié)點都會通過公式（6）來計算自己的轉(zhuǎn)發(fā)概率，另外，節(jié)點還會生成一個0到1之間的隨機(jī)概率。如果計算出來的轉(zhuǎn)發(fā)概率值大于生成的隨機(jī)概率，則該節(jié)點轉(zhuǎn)向轉(zhuǎn)發(fā)過程。

（4）當(dāng)有多個節(jié)點進(jìn)入轉(zhuǎn)發(fā)過程時，會發(fā)生網(wǎng)絡(luò)沖突進(jìn)入二進(jìn)制指數(shù)退避，最大退避指數(shù)的數(shù)目為3。

（5）如果有且僅有一個節(jié)點成功競爭該信道，它將轉(zhuǎn)發(fā)緊急消息，成為源節(jié)點的下一跳。

（6）如果在最大數(shù)量的退避指數(shù)和源節(jié)點的延遲計數(shù)器計時結(jié)束之后轉(zhuǎn)發(fā)過程失敗，源節(jié)點會重新發(fā)送原始緊急消息。

3 仿真驗證

3.1 實驗環(huán)境

本實驗使用MATLAB仿真模擬器來驗證基于概率的多跳廣播算法的性能[12]，跟其它不同的基于概率的多跳廣播方案的轉(zhuǎn)發(fā)成功率作比較。實驗時，車輛處在源節(jié)點傳輸范圍均勻分布的車聯(lián)網(wǎng)中，在單跳范圍內(nèi)車輛數(shù)N為10-100之間，傳輸范圍為300米。將WPB協(xié)議和NPPB協(xié)議作為比照對象，當(dāng)NPPB協(xié)議作為比較對象時選取了具有代表性的兩個參數(shù)k=3和k=5.本文中給出的算法，也設(shè)定了兩種情況：λ=1和λ=0.6。首先，依據(jù)公式R/（N+1）來計算車輛之間的距離，從而得到每個車輛之間的距離，再計算出每個節(jié)點的轉(zhuǎn)發(fā)概率。表1中給出了部分仿真參數(shù)的設(shè)置[13]。

3.2 仿真結(jié)果分析

計算轉(zhuǎn)發(fā)成功概率時，需要考慮每個節(jié)點在第一次嘗試轉(zhuǎn)發(fā)消息沒有任何退避的情況。由于轉(zhuǎn)發(fā)概率考慮了車輛密度因子，從圖2可以看出，隨著車輛數(shù)量的增加，轉(zhuǎn)發(fā)成功的概率始終很高，而WPB、NPPB（k=3）和NPPB（k=5）的轉(zhuǎn)發(fā)成功率則顯著下降。λ=1的網(wǎng)絡(luò)轉(zhuǎn)發(fā)成功率高于λ=0.6的網(wǎng)絡(luò)轉(zhuǎn)發(fā)成功率。

實驗也進(jìn)行了平均副本數(shù)的對比。為了簡化計算的復(fù)雜性，將在傳輸范圍內(nèi)的車輛數(shù)N設(shè)為10-28。如圖3所示，網(wǎng)絡(luò)的平均副本數(shù)不會隨著車輛密度的增加而增加，甚至看起來會略有減少。

平均信道接入延遲的仿真結(jié)果如圖4所示。由于WPB和NPPB分配的接近節(jié)點的轉(zhuǎn)發(fā)概率不夠小，使得節(jié)點在信道競爭過程中具有較高的繁忙概率，因此平均信道接入延遲隨車輛密度的增加呈指數(shù)增長。

4 結(jié)論

通過仿真實驗的模擬，給出的基于概率的多跳廣播協(xié)議在不需要網(wǎng)絡(luò)拓?fù)涞南闰炛R情況下，每個節(jié)點以一定的概率轉(zhuǎn)發(fā)緊急消息，不僅提高了數(shù)據(jù)包轉(zhuǎn)發(fā)成功的概率、減少了平均副本數(shù)也降低了信道訪問延遲。與此同時，所給出的轉(zhuǎn)發(fā)概率也可以根據(jù)車輛密度自適應(yīng)地進(jìn)行調(diào)整，能夠保證網(wǎng)絡(luò)性能不會因為車輛密度的增加而面臨急劇下降的問題，顯著的改善了車載網(wǎng)絡(luò)轉(zhuǎn)發(fā)的可靠性也減少了時間延遲。

（通信作者：陳戈琦）

參考文獻(xiàn)

[1]M.-C.Chuang，and M.C.Chen，”DEEP：Density-awareemergencymessageextens ion protocolfor VANETs，”IEEE Transactionson WirelessCommunications，12.10（2013）：4983-4993.

[2]H. Yoo and D. Kim，”ROFF：RObustand Fast Forwarding in vehicularad-hoc networks，”IEEE Transactions onMobile Computing，14.7 （2015）：1490-1502.

[3]I.Achour，T.Bejaoui，andS.Tabbane.”Network codingapproachforvehicle-to-vehiclecommunication：Principles，protocols and benefits.”Software，Telecommunications and ComputerNetworks（SoftC0M），2014 22ndInternational Conference on. IEEE，2014.

[4]L.Li，R.Ramjee，M.Buddhikot，andS.Miller，”Network codingbasedbroadcast in mobile ad-hocnetworks.”INFOCOM 2007-26thIEEE International Conference onComputer Communications.IEEE，2007，pp.1739-1747.

[5]C.Fragouli，J.Widmer，and J.-Y.L.Boudec.”Efficient broadcastingusingnetwork coding.”IEEE/ACMTransactions on Networking（TON）16.2（2008）：450-463.

[6]N.Wisitpongphan，et al，”Broadcaststorm mitigation techniquesinvehicular ad hoe networks，”IEEE Wireless Communications，14.6 （2007）：84-94.

[7]L.Zhou，et al，”NPPB：A broadcastscheme in dense VANETs，”InformationTechnology Journal，9.2（2010）：247-256.

[8]S.Panichpapiboon and G.Ferrari，”Irresponsible forwarding，”ITSTelecommunications，2008.ITST2008.8th International Conferenceon.IEEE，2008.

[9]S.Panichpapiboon”Irresponsibleforwarding under general intervehiclespacing distributions，”ElectricalEngineering/Electronics，Computer，Telecommunications and InformationTechnology（ECTI-CON），2011 8thInternational Conference on. IEEE，2011.

[10]S.Panichpapiboon and L.Cheng，”Irresponsible forwardingunderreal intervehicle spacingdistributions，”IEEE Transactionson VehicularTechnology，62.5 （2013）：2264-2272.

[11]X.Li，et al.”Multi-hop delayreduction for safety-related messagebroad-casting in vehicle-to-vehiclecommunications.”IET Communications9.3（2015）：404-411.

[12]The Network Simulator-ns-2.[Onlinel，Available：http：//www.isi.edu/nsnam/ns/.

[13]Y.Bi，ff.Shan，X.S.Shen，N.Wangand H.Zhao，"A Multi-Hop BroadcastProtocol for Emergency MessageDissemination in Urban Vehicular AdHoe Networks，"in IEEE Transactionson Intelligent TransportationSystems，Vol.17，no.3，pp.736-750，March 2016.