車聯網中基于概率和網絡密度的多跳廣播協議

程青青 陳戈珩

摘要

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

【關鍵詞】車載網絡 概率 網絡密度 多跳廣播

1 VANET介紹

依據車載自組織網絡對于緊急信息必須及時、可靠地傳播到相關區域內的所有車輛的特性提出了多種多跳廣播方案來增強緊急消息傳播的性能。這種多跳廣播方案解決了單跳廣播的覆蓋區域不夠大的問題，可以保證目標區域內的每個車輛都能夠成功的接收消息。現有的多跳廣播可以分為三類：基于時間、基于編碼和基于概率的方法，這三類多跳廣播方案都能增強緊急消息傳播協議的性能。在本文中，主要專注于研究基于概率的多跳廣播。

1.1 基于時間的多跳廣播

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

1.2 基于編碼的多跳廣播

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

1.3 基于概率的多跳廣播

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

p=（d/R）（1）

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

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

P：表示重播的概率;

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

K：表示NPPB協議中的轉發概率系數。

其中K的值越大，分配給源節點附近的轉發概率越小，NPPB在密集的VANET環境中，協議的性能要優于WPB，但是當傳輸范圍附近的區域內沒有足夠的車輛時，能夠傳輸成功的概率將明顯降低。文獻[8]中提出了基于概率的不確定轉發方案（IF），此時的轉發概率變為：：表示一般車輛間距下分布的均值指數假設值。

研究表明，此時的轉發概率分布可以適應車輛密度[9]。在對IF方案進行真實車輛間距分布的評估中發現IF方案的節點難以察覺間距分布[10]，該方案仍然無法解決當傳輸范圍的邊界區域車輛較少時導致的傳輸成功概率低的問題。

2 算法模型

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

2.1 網絡建模

給出假定情景下的網絡模型：

（1）假設車輛的傳輸范圍R;

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

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

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

其中λ_opt表示λ的最優值。

2.2 理論分析

給出新的轉發概率公式，定義為：將距離源節點最遠的距離定義為d₁，N表示一跳范圍內的節點總數，λ用于調整轉發成功概率的系數。

2.2.1 轉發成功的概率

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

定義成功轉發概率的公式為：

另外，平均副本數量的定義如下：

其中P_cn表示n個節點在沒有任何退避情況下轉發接收到的數據包概率，當節點計算的轉發概率大于隨機生成的概率時，該節點就獲得了轉發權。

2.2.2 平均時延

在IEEE802.11（WIFI）的標準修訂版本，DSRC在PHY和MAC層中將IEEE802.11p無線協議用于車載自組織網絡（VANET）中，IEEE802.11p是基于分布式協調函數（DCF）的廣播協議，在DCF中使用載波感知多址機制（CSMA/CA）來爭奪信道。為了減少碰撞的發生，DCF采用信道感知檢測信道活動和截斷二進制指數退避隨機化分組傳輸的開始時間[11].其中信道的訪問延遲可以表示為：

其中：

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

2.3 多跳廣播協議

源節點車輛遇到緊急情況時，需要盡快向車流量的相反方向節點廣播緊急消息，假設整個車輛網絡有效連接，傳輸范圍內的所有車輛都可以有效地接收廣播包。

（1）源節點會將數據包廣播到傳輸范圍內的所有節點，包括事件ID、GPS坐標和行駛方向，還會把緊急數據包存儲到緩沖區。

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

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

（4）當有多個節點進入轉發過程時，會發生網絡沖突進入二進制指數退避，最大退避指數的數目為3。

（5）如果有且僅有一個節點成功競爭該信道，它將轉發緊急消息，成為源節點的下一跳。

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

3 仿真驗證

3.1 實驗環境

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

3.2 仿真結果分析

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

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

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

4 結論

通過仿真實驗的模擬，給出的基于概率的多跳廣播協議在不需要網絡拓撲的先驗知識情況下，每個節點以一定的概率轉發緊急消息，不僅提高了數據包轉發成功的概率、減少了平均副本數也降低了信道訪問延遲。與此同時，所給出的轉發概率也可以根據車輛密度自適應地進行調整，能夠保證網絡性能不會因為車輛密度的增加而面臨急劇下降的問題，顯著的改善了車載網絡轉發的可靠性也減少了時間延遲。

（通信作者：陳戈琦）

參考文獻

[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.