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

程青青 陳戈珩

摘要

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

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

1 VANET介紹

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

1.1 基于時(shí)間的多跳廣播

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

1.2 基于編碼的多跳廣播

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

1.3 基于概率的多跳廣播

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

p=（d/R）（1）

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

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

P：表示重播的概率;

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

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

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

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

2 算法模型

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

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

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

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

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

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

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

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

2.2 理論分析

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

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

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

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

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

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

2.2.2 平均時(shí)延

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

其中：

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

2.3 多跳廣播協(xié)議

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

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

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

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

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

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

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

3 仿真驗(yàn)證

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 仿真結(jié)果分析

計(jì)算轉(zhuǎn)發(fā)成功概率時(shí)，需要考慮每個(gè)節(jié)點(diǎn)在第一次嘗試轉(zhuǎn)發(fā)消息沒(méi)有任何退避的情況。由于轉(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ā)成功率。

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

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

4 結(jié)論

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

（通信作者：陳戈琦）

參考文獻(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.