吳黎兵 范 靜 王 婧 聶 雷 王 浩

1(軟件工程國家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué)) 武漢 430072) 2(武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072) 3(巖土力學(xué)與工程國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院武漢巖土力學(xué)研究所) 武漢 430072)

(wu@whu.edu.cn)

基于類哈夫曼編碼的緊急消息廣播方法

吳黎兵1,2范 靜2王 婧2聶 雷2王 浩3

1(軟件工程國家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué)) 武漢 430072)2(武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072)3(巖土力學(xué)與工程國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院武漢巖土力學(xué)研究所) 武漢 430072)

(wu@whu.edu.cn)

城市的發(fā)展為車載自組織網(wǎng)絡(luò)(vehicular ad hoc network, VANET)(也稱車聯(lián)網(wǎng))提供了廣闊的應(yīng)用空間，其中緊急消息廣播方法則是應(yīng)用的一個(gè)重點(diǎn)研究?jī)?nèi)容.緊急消息廣播需要滿足低延遲、高可靠和高可擴(kuò)展性等服務(wù)質(zhì)量方面的要求.現(xiàn)有的緊急消息廣播方法在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，假定每一個(gè)位置均有大致相等的概率被選為中繼區(qū)域，對(duì)所有位置的節(jié)點(diǎn)一視同仁，缺乏針對(duì)最優(yōu)節(jié)點(diǎn)位置分布規(guī)律的研究，不能較好地適應(yīng)最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)的分布情況.而降低緊急消息傳播延遲的關(guān)鍵是快速確定合適的中繼轉(zhuǎn)發(fā)節(jié)點(diǎn).因此，為了進(jìn)一步提高緊急消息廣播的及時(shí)性，降低傳播延遲，提出一種采用類哈夫曼編碼的緊急消息廣播方法.首先分析了城市道路中最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)的概率分布情況，然后在此基礎(chǔ)上利用哈夫曼編碼的原理，設(shè)計(jì)了一種能夠最小化最優(yōu)節(jié)點(diǎn)選取時(shí)間的快速分區(qū)方法，最終達(dá)到快速確定最優(yōu)中繼節(jié)點(diǎn)，降低緊急消息廣播延遲，提高緊急消息傳播速度的目的.仿真實(shí)驗(yàn)證明：該方法在不同場(chǎng)景中能夠降低5.3%～18.0%的緊急消息廣播時(shí)延，提高8.9%～24.5%的緊急消息傳播速度.

車聯(lián)網(wǎng)；多跳廣播協(xié)議；緊急消息分發(fā)；干擾幀；哈夫曼編碼

城市的快速發(fā)展在為人們帶來生活便利的同時(shí)也為城市交通帶來了新的挑戰(zhàn)，尤其是在交通安全保障方面.緊急消息廣播作為及時(shí)告警城市交通事故、降低突發(fā)事故危害的手段，成為了當(dāng)前城市交通問題的主要關(guān)注點(diǎn)之一[1].

城市道路中，車輛的快速移動(dòng)帶來了車載自組織網(wǎng)絡(luò)(vehicular ad hoc network, VANET)(也稱車聯(lián)網(wǎng))網(wǎng)絡(luò)拓?fù)涞目焖僮兓?，而緊急消息的廣播卻需要達(dá)成高可靠性和低時(shí)延等服務(wù)質(zhì)量要求.由于無線傳輸距離的限制，為了覆蓋足夠的范圍，緊急消息往往需要通過多跳廣播才能夠完全覆蓋目標(biāo)區(qū)域，因此快速選擇合適的中繼節(jié)點(diǎn)就成為了研究的焦點(diǎn).

研究者們提出了許多緊急消息的多跳廣播方法，這些方法通過隨機(jī)概率或者多次迭代等方式來確定一個(gè)或者多個(gè)中繼轉(zhuǎn)發(fā)節(jié)點(diǎn).其中，利用black-burst(BB)幀進(jìn)行緊急消息廣播中繼選擇的方法獲得了許多關(guān)注[2].BB幀是一種每一位編碼都為高位的干擾幀.通過發(fā)送BB幀，保證即使在與其他廣播信號(hào)發(fā)生沖突時(shí)BB幀仍然能夠被偵測(cè)到，因此更適用于緊急消息的廣播.在車聯(lián)網(wǎng)方向，現(xiàn)有的采用BB幀的廣播方法一般依靠相對(duì)固定的策略來使用BB幀，而對(duì)不同交通環(huán)境下的車輛密度缺乏針對(duì)性研究，難以最優(yōu)化其利用效率.

針對(duì)上述問題，本文在對(duì)最優(yōu)候選車輛出現(xiàn)位置進(jìn)行詳細(xì)歸納和推論后，分析了最優(yōu)候選車輛出現(xiàn)在不同位置的概率分布，并以此為依據(jù)，利用哈夫曼編碼的原理，提出了一種快速確定最優(yōu)轉(zhuǎn)發(fā)車輛所在分區(qū)的方法，并基于這種方法設(shè)計(jì)了一種采用類哈夫曼編碼的緊急消息廣播方法(Huffman-Like coding based broadcast method, HFMBB).實(shí)驗(yàn)結(jié)果顯示，相對(duì)于現(xiàn)有緊急消息廣播方法，本文方法能夠有效提高城市多車道道路的緊急消息傳播速度，降低消息傳播時(shí)延.本文的主要貢獻(xiàn)有2個(gè)方面：

1) 在合理量化車輛分布規(guī)律的基礎(chǔ)上，對(duì)最優(yōu)中繼車輛出現(xiàn)位置的概率分布進(jìn)行了理論推導(dǎo)，并給出了2種已知條件情況下對(duì)最優(yōu)中繼車輛分布的計(jì)算方法.

2) 利用哈夫曼編碼原理構(gòu)造了一種多跳廣播協(xié)議最優(yōu)中繼車輛選擇方法，設(shè)計(jì)了基于類哈夫曼編碼的緊急消息廣播方法HFMBB，并在仿真環(huán)境中對(duì)其進(jìn)行了詳細(xì)的驗(yàn)證和分析.

1 相關(guān)工作

現(xiàn)有的緊急消息廣播方法依照中繼選擇策略的不同主要可以分為三大類：1)基于概率的緊急消息廣播方法;2)基于距離退避的緊急消息廣播方法;3)基于BB分區(qū)的緊急消息廣播方法.

1.1基于概率的廣播方法

基于概率的中繼選擇方法中，節(jié)點(diǎn)在收到廣播消息后，依據(jù)某個(gè)隨機(jī)策略獨(dú)立選擇是否進(jìn)行轉(zhuǎn)發(fā).最早的洪泛廣播方法可以看作轉(zhuǎn)發(fā)概率為1的隨機(jī)廣播方法.由于節(jié)點(diǎn)會(huì)重復(fù)廣播所有收到的信息，因此洪泛方法效率極低，且容易引起廣播風(fēng)暴[3].為提高信道利用率，降低廣播風(fēng)暴發(fā)生風(fēng)險(xiǎn)，文獻(xiàn)[4]分別提出了權(quán)重p堅(jiān)持(weightedp-persistence, WPP)和間隙p堅(jiān)持(slottedp-persistence, SPP)兩類基于概率的廣播方法，收到廣播的節(jié)點(diǎn)，根據(jù)距離相關(guān)的概率來決定是否在信道空閑時(shí)進(jìn)行廣播.WPP方法中，遠(yuǎn)處的車輛使用較高的轉(zhuǎn)發(fā)概率，而源節(jié)點(diǎn)附近的車輛使用較低的轉(zhuǎn)發(fā)概率；SPP方法中，車輛轉(zhuǎn)發(fā)概率相同，但距離發(fā)送車輛遠(yuǎn)的車輛，需要等待的信道空閑時(shí)間短，因而能夠更早進(jìn)行消息轉(zhuǎn)發(fā).

雖然改進(jìn)的基于概率的方案能夠減少發(fā)生廣播風(fēng)暴的風(fēng)險(xiǎn)，但當(dāng)?shù)缆奋囕v較為密集時(shí)，依然會(huì)產(chǎn)生大量的冗余廣播.文獻(xiàn)[5]進(jìn)一步提出了基于交通密度的概率轉(zhuǎn)發(fā)方案，通過在交通擁擠時(shí)降低車輛轉(zhuǎn)發(fā)報(bào)文的概率，減少冗余報(bào)文，提高信道利用率，但依然無法完全克服報(bào)文大量冗余轉(zhuǎn)發(fā)的問題.

1.2基于距離退避的廣播方法

區(qū)別于基于概率的廣播方法，基于距離退避的方法旨在根據(jù)與發(fā)送節(jié)點(diǎn)的距離，適當(dāng)選擇退避時(shí)間，并選擇一跳范圍內(nèi)最遠(yuǎn)節(jié)點(diǎn)作為消息傳輸?shù)闹欣^節(jié)點(diǎn).文獻(xiàn)[6]通過控制車輛轉(zhuǎn)發(fā)緊急消息的退避時(shí)間來選擇最遠(yuǎn)車輛作為中繼節(jié)點(diǎn).在收到需要廣播的緊急消息后，離發(fā)送車輛越遠(yuǎn)的車輛將會(huì)更早進(jìn)行緊急消息的廣播，但是該方案主要適用于車流稀疏的高速道路.而在城市環(huán)境中，車輛更加密集，需要對(duì)等待時(shí)間進(jìn)行更細(xì)致的劃分，進(jìn)而導(dǎo)致源節(jié)點(diǎn)遠(yuǎn)方?jīng)]有車輛時(shí)近距離車輛需要等待很長(zhǎng)時(shí)間才能對(duì)緊急消息進(jìn)行轉(zhuǎn)發(fā).針對(duì)該問題，文獻(xiàn)[7]提出了一種智能廣播方法(smart broadcast, SB).在SB方法中，廣播車輛通信范圍內(nèi)的道路被分為若干區(qū)域，道路中的車輛按照區(qū)域由遠(yuǎn)至近的不同，采用按一定尺寸遞增的退避窗口，而同一個(gè)區(qū)域內(nèi)的車輛則選擇對(duì)應(yīng)退避窗口范圍內(nèi)的隨機(jī)退避時(shí)間進(jìn)行退避.通過區(qū)域內(nèi)車輛共享退避窗口，SB方法能夠降低整個(gè)退避過程需要消耗的時(shí)間.但與此同時(shí)，當(dāng)?shù)缆分熊囕v密集時(shí)，同一個(gè)退避窗口會(huì)有大量車輛參與競(jìng)爭(zhēng)，退避過程中極易發(fā)生沖突.文獻(xiàn)[8]提出了一種動(dòng)態(tài)分區(qū)策略(dynamic partitioning scheme, DPS)來解決上述問題.DPS方法通過探測(cè)鄰居車輛密度來動(dòng)態(tài)地決定區(qū)域劃分的數(shù)目，因而在一定程度上能夠適應(yīng)于不同的道路環(huán)境.文獻(xiàn)[9]引入接收能量來判定距離，提高了基于距離算法的適用環(huán)境.

基于距離退避的廣播方法中，離發(fā)送節(jié)點(diǎn)較近的車輛需要等待很長(zhǎng)的退避時(shí)間.當(dāng)?shù)缆份^為空曠，且發(fā)送節(jié)點(diǎn)通信范圍的遠(yuǎn)端沒有車輛時(shí)，近端車輛需要等待較長(zhǎng)時(shí)間才能進(jìn)行轉(zhuǎn)發(fā)，從而產(chǎn)生較大的轉(zhuǎn)發(fā)延遲，無法滿足緊急消息廣播需求.

1.3基于black-burst的廣播方法

基于BB的廣播方法是利用BB干擾幀進(jìn)行通信范圍內(nèi)區(qū)域快速劃分的廣播方法.BB幀能夠壓制其他信號(hào)，促使其他非緊急消息進(jìn)入退避時(shí)間，特別適用于最高優(yōu)先級(jí)的緊急消息廣播.文獻(xiàn)[10-11]利用BB幀的特性提出了適用于車聯(lián)網(wǎng)環(huán)境的城市多跳廣播方法(urban multi-hop broadcast, UMB)和點(diǎn)對(duì)點(diǎn)多跳廣播方法(ad hoc multi-hop broadcast, AMB).當(dāng)車輛收到源節(jié)點(diǎn)發(fā)送的廣播信息后，較遠(yuǎn)的候選車輛將會(huì)發(fā)送一個(gè)較長(zhǎng)的BB幀,最終發(fā)送BB時(shí)間最長(zhǎng)的那個(gè)節(jié)點(diǎn)成為中繼車輛.UMB和AMB雖然使用了BB幀，但依然采用基于距離長(zhǎng)度的等待方法，并沒有從根本上改變基于距離退避的廣播方法的原理.為了更好地利用BB幀抗干擾的特點(diǎn)，文獻(xiàn)[12]提出了一種基于BB幀的二分分區(qū)廣播方法(binary-partition assisted broadcast, BPAB).與SB方法類似，BPAB也將通信范圍劃分為多個(gè)分區(qū).但與基于距離退避的廣播方法不同，BPAB利用BB幀抗干擾的特點(diǎn)，不采用退避，而是通過半數(shù)分區(qū)內(nèi)的車輛同時(shí)發(fā)送BB幀來快速判定這些分區(qū)內(nèi)是否存在候選車輛，進(jìn)而在對(duì)數(shù)時(shí)間內(nèi)確定最優(yōu)候選車輛所處的具體分區(qū).在確定具體分區(qū)后，再通過隨機(jī)退避確定中繼車輛.在此基礎(chǔ)上，文獻(xiàn)[13]引入了最小分布式幀間間隙(min-DIFS)降低了BB幀的信道訪問等待時(shí)間，最終在二分分區(qū)方案的基礎(chǔ)上提出了基于BB的三分分區(qū)協(xié)議(trinary partitioned black burst based broadcast protocol, 3P3B).除此之外，文獻(xiàn)[14]還專門研究了道路交叉口區(qū)域的多跳廣播問題，提出了城市多跳廣播協(xié)議(urban multi-hop broadcast protocol, UMBP).

此外，文獻(xiàn)[15]利用長(zhǎng)期演進(jìn)(long term evolu-tion, LTE)技術(shù)輔助進(jìn)行緊急消息廣播，文獻(xiàn)[16]利用多層協(xié)議進(jìn)行緊急消息廣播，文獻(xiàn)[17]利用RSU協(xié)助進(jìn)行緊急消息廣播.

相對(duì)于以上方案，基于BB的方案不需要額外的基礎(chǔ)設(shè)施，并且能夠在單個(gè)時(shí)隙內(nèi)確定一片區(qū)域是否存在候選車輛，進(jìn)而可以在極短時(shí)間內(nèi)以指數(shù)倍數(shù)縮小候選區(qū)域的范圍.基于BB的方案使用RTB/CTB(request to broadcast/clear to broadcast)機(jī)制確定唯一中繼轉(zhuǎn)發(fā)車輛，極大地減少消息冗余，提高無線信道資源利用率.

2 系統(tǒng)模型和基礎(chǔ)知識(shí)

研究城市環(huán)境中車輛廣播通信過程首先需要對(duì)應(yīng)用場(chǎng)景進(jìn)行定義和建模.本節(jié)針對(duì)城市場(chǎng)景進(jìn)行了建模分析，分別對(duì)道路模型、車輛通信模型和BB分區(qū)方法基本原理進(jìn)行了概括和定義.

2.1城市道路與通信模型

城市道路一般由雙向多車道道路構(gòu)成.以圖1所示雙向4車道道路為例，道路由4條車道構(gòu)成，其中L1,L0車道上的車輛自右向左行駛，R0,R1車道上的車輛自左向右行駛.

城市環(huán)境中，車輛與車輛使用無線信道進(jìn)行通信，其最遠(yuǎn)通信范圍可以達(dá)到1 400 m[18].但在緊急消息廣播過程中，為了保證信息傳播的可靠性會(huì)對(duì)單跳通信距離R加以限制.一般認(rèn)為城市道路中自由移動(dòng)的車輛服從泊松分布[11-13].將道路劃分為長(zhǎng)度為L(zhǎng)連續(xù)的段落，每一個(gè)段落稱為一個(gè)槽位，如圖1中S0～S17所示.每個(gè)槽位中可能存在車輛，也可能不存在車輛.若ρ為車輛密度，表示每個(gè)車道在單位長(zhǎng)度的道路上車輛的平均數(shù)目，則每個(gè)槽位中存在車輛的概率滿足pslot=1-e-ρ·L.一個(gè)槽位存在車輛時(shí)，車輛可能分布在該槽位范圍內(nèi)的任意位置.

Fig. 1 The example of the urban road module圖1 城市道路模型示意圖

廣播發(fā)起車輛A在發(fā)起廣播時(shí)需要發(fā)送RTB報(bào)文，其中包含了自身的位置信息.在成功接收到RTB報(bào)文的車輛中，只有距離廣播發(fā)起車輛A小于R的車輛才能成為候選車輛，并參與緊急消息的轉(zhuǎn)發(fā)[13].例如圖1中位于槽位S17的車輛，由于超出了距離范圍，因此即使成功接收到廣播車輛發(fā)送的緊急消息也不能成為候選的中繼車輛.最優(yōu)轉(zhuǎn)發(fā)車輛B為通信范圍內(nèi)距離廣播車輛A距離最遠(yuǎn)的車輛，選擇該車輛進(jìn)行廣播可以達(dá)到最大單跳廣播距離.

2.2black-burst分區(qū)原理

現(xiàn)有基于BB的廣播方法依靠對(duì)通信范圍內(nèi)的車輛以固定比例進(jìn)行多次劃分，達(dá)到快速縮小轉(zhuǎn)發(fā)車輛范圍的目的.按照區(qū)域劃分方式，BB分區(qū)方法可以分為二分法(binary partitioning)[12]和N分法(n-nary partitioning)[13]，如圖2所示.

Fig. 2 The example for existing black-burst partitioning圖2 現(xiàn)有black-burst分區(qū)方法示例

二分方法中，第1輪通信范圍內(nèi)車輛按距離分為2個(gè)部分，離廣播車輛較遠(yuǎn)的槽位(圖2二分法中S3,S4)首先發(fā)送BB幀.若第1輪廣播車輛收到BB幀，則遠(yuǎn)端位置存在車輛，第2輪中遠(yuǎn)端車輛再進(jìn)一步劃分為2個(gè)部分，并進(jìn)行第2輪劃分，直到劃分至需要的輪數(shù)后，被選中區(qū)域中的車輛開始進(jìn)行退避，并發(fā)送CTB報(bào)文進(jìn)行沖突避免.

而N分法則是將區(qū)域劃分為N等分，每輪中又分為至多N-1個(gè)間隔，車輛按照所處分區(qū)的距離，由遠(yuǎn)到近在對(duì)應(yīng)序號(hào)間隔內(nèi)發(fā)送BB幀.當(dāng)任一間隔內(nèi)有車輛發(fā)送BB幀時(shí)，則可確認(rèn)該間隔對(duì)應(yīng)的分區(qū)存在最優(yōu)候選中繼車輛，進(jìn)而開始下一輪劃分過程.

如圖2(b)三分法為例，若S7～S9區(qū)域內(nèi)存在車輛，則該區(qū)域內(nèi)車輛在第1輪的第1個(gè)時(shí)間間隔內(nèi)發(fā)送BB幀，并立即進(jìn)入第2輪分區(qū)過程；反之，若S7～S9區(qū)域內(nèi)不存在車輛，則S4～S6區(qū)域內(nèi)的車輛在第1輪的第2個(gè)時(shí)間間隔內(nèi)發(fā)送BB幀.此時(shí)若偵聽到BB幀，則最優(yōu)候選車輛位于S4～S6區(qū)域內(nèi)，分區(qū)過程進(jìn)入第2輪.如果第1輪的第2個(gè)間隔仍然沒有車輛發(fā)送BB幀，那么候選車輛必然位于S1～S3區(qū)域內(nèi)，分區(qū)過程進(jìn)入第2輪.

3 基于類哈夫曼編碼的廣播方法

BB的分區(qū)目標(biāo)是選擇距離源節(jié)點(diǎn)最遠(yuǎn)的存在候選車輛的區(qū)域，但現(xiàn)有的方法均采用一定比值的分區(qū)方案，沒有充分考慮最優(yōu)候選車輛出現(xiàn)位置分布對(duì)分區(qū)過程的影響.本節(jié)首先對(duì)最優(yōu)候選車輛出現(xiàn)位置的分布情況分析，再以此為基礎(chǔ)設(shè)計(jì)一種能夠充分考慮具體分布情況的分區(qū)方法，達(dá)到降低平均分區(qū)輪數(shù)，減低中繼選擇延遲的目的.

3.1最優(yōu)候選車輛分布概率分析

假定某道路包含M個(gè)車道，源節(jié)點(diǎn)通信半徑R能夠劃分出N個(gè)長(zhǎng)度為L(zhǎng)的槽位，則最優(yōu)候選車輛位于道路第n個(gè)槽位(即slot=n)需要同時(shí)滿足2個(gè)條件：

1) 所有車道m(xù)∈[1,M]中比第n個(gè)槽位更遠(yuǎn)的槽位slot∈(n,N]均沒有車輛.

2) 車道m(xù)∈[1,M]中，至少有一個(gè)車道的第n個(gè)槽位slot=n存在車輛.

通過道路監(jiān)測(cè)手段可以獲取道路車輛的平均密度[19].在已知道路車輛平均密度ρ的情況下，車輛在道路中的分布服從泊松分布[13].車輛分布概率用P表示，則車道m(xù)的第n個(gè)槽位slot=(m,n)中存在車輛的概率P|s lot=(m,n)彼此獨(dú)立且等于ps lot=1-e-ρ ·L.

條件1和條件2發(fā)生的概率P|nfar≤n和P|s lot=(m,n)分別計(jì)算為

P|nfar≤n=(1-pslot)M(N-n),

(1)

P|s lot=(m,n)=pslot.

(2)

而條件1和條件2互為獨(dú)立事件，因此最優(yōu)候選車輛位于槽位slot=(m,n)的概率P|nfar=(m,n)為

P|nfar=(m,n)=pslot(1-pslot)M(N-n).

(3)

如果使用基于Beacon消息的鄰居節(jié)點(diǎn)感知方法[20]，則能夠獲得通信半徑內(nèi)具體的車輛數(shù)目Ncar.受車輛長(zhǎng)度vLen和安全距離minGap的限制[21]，車輛之間的最小間隔Lmin=vLen+minGap.將通信半徑R劃分為N個(gè)長(zhǎng)度為L(zhǎng)min的槽位，則車輛在道路中的分布可以轉(zhuǎn)換為槽位占用組合問題.

組合問題中，車道m(xù)∈[1,M]的第n個(gè)槽位slot=n中是否有車會(huì)影響其他槽位，條件1和條件2成為相關(guān)條件，須同時(shí)考慮.

當(dāng)前條件下，存在的所有組合數(shù)目Call等價(jià)于所有槽位slot=(m,n),m∈[1,M]，n∈[1,N]中選取Ncar個(gè)槽位有車，計(jì)算為

(4)

條件1和條件2同時(shí)滿足的組合情況為第n個(gè)槽位slot=n中至少有一輛車，而其他車輛分布于槽位slotlt;n中.其組合數(shù)目Cnfar=n可以計(jì)算為

(5)

因此，已知通信范圍內(nèi)車輛數(shù)目情況下，最優(yōu)候選車輛位于槽位slot=n的概率Pb|nfar=(m,n)計(jì)算為

3.2類哈夫曼編碼算法

哈夫曼編碼(Huffman coding)是一種依據(jù)字符出現(xiàn)概率，以最小平均碼長(zhǎng)為目的的編碼設(shè)計(jì)方法.在BB分區(qū)方法中，每一次BB幀的分區(qū)過程可以看做二進(jìn)制編碼的1位.BB分區(qū)方法的目的等價(jià)于按照指定二進(jìn)制編碼方式標(biāo)記出每一個(gè)分區(qū).例如圖2中二分法即每次按照1∶1的比例進(jìn)行二進(jìn)制編碼，圖2中三分法即依次按照1∶2和1∶1的比例交替進(jìn)行二進(jìn)制編碼.

但是BB分區(qū)過程并不完全等價(jià)于字符編碼.BB分區(qū)編碼過程與標(biāo)準(zhǔn)哈夫曼編碼過程存在2點(diǎn)區(qū)別：

1) BB分區(qū)編碼過程中，發(fā)送BB幀的槽位會(huì)掩蓋不發(fā)送BB幀的槽位.

2) 槽位擁有優(yōu)先級(jí)，即編碼結(jié)果中距離遠(yuǎn)的槽位不能被距離近的槽位掩蓋.

由此可見，不同于標(biāo)準(zhǔn)哈夫曼編碼方法，進(jìn)行BB分區(qū)編碼時(shí)，遠(yuǎn)端部分的槽位必須優(yōu)先編碼為1，且槽位不可交換順序，必須按優(yōu)先級(jí)排序.在以上區(qū)別限制的情況下，本文構(gòu)造類哈夫曼編碼算法流程如圖3所示.

Fig. 3 The flow chart of Huffman-Like coding algorithm圖3 類哈夫曼編碼算法流程

圖3中，首先按照槽位位置索引，使用各槽位最優(yōu)車輛出現(xiàn)概率構(gòu)造槽位節(jié)點(diǎn)列表slots；然后，由遠(yuǎn)至近依次遍歷所有相鄰槽位，找出概率和最小的2個(gè)相鄰槽位Slot[i]和Slot[j]；找到Slot[i]和Slot[j]之后，算法構(gòu)造新節(jié)點(diǎn)Slot[k]，并將其概率設(shè)置為Slot[i]與Slot[j]的和Slot[i]+Slot[j]，將Slot[i]和Slot[j]分別設(shè)置為Slot[k]節(jié)點(diǎn)的左右子節(jié)點(diǎn)；最后使用Slot[k]代替節(jié)點(diǎn)列表slots中的Slot[i]和Slot[j].循環(huán)進(jìn)行該過程直至槽位節(jié)點(diǎn)列表slots中只有一個(gè)節(jié)點(diǎn)(記作Root)為止；之后通過遍歷Root為根節(jié)點(diǎn)的二叉樹即可獲得每個(gè)槽位對(duì)應(yīng)的編碼結(jié)果.

廣播過程中收到RTB報(bào)文的候選車輛根據(jù)自身所處的槽位的編號(hào)，依據(jù)編碼結(jié)果依次監(jiān)聽和發(fā)送BB幀，完成BB分區(qū)過程.

3.3類哈夫曼廣播方法過程舉例

本節(jié)以BB分區(qū)精度為1/8為例，演示了本文提出的廣播方法.本廣播方法的總體過程如圖4所示:

Fig. 4 The general procedure of Huffman-Like broadcast圖4 類哈夫曼廣播方法整體步驟

當(dāng)需要進(jìn)行廣播時(shí)，源節(jié)點(diǎn)等待mini-DIFS[12]的信道空閑時(shí)間后，發(fā)送攜帶自身位置和車輛密度信息的RTB報(bào)文，聲明緊急消息廣播開始.備選車輛收到RTB報(bào)文后，在下一個(gè)GPS同步時(shí)間同時(shí)發(fā)送BB幀，表明當(dāng)前通信范圍內(nèi)存在候選車輛，并開始執(zhí)行BB分區(qū)過程.

BB分區(qū)過程開始的第1輪，第1位編碼為1的節(jié)點(diǎn)首先發(fā)送BB幀，而第1位編碼為0的節(jié)點(diǎn)則僅進(jìn)行監(jiān)聽.如果第1輪存在編碼為1的節(jié)點(diǎn)(例如位于槽位S8和S7的節(jié)點(diǎn))，則編碼為0的節(jié)點(diǎn)退出競(jìng)爭(zhēng).分區(qū)第1輪完成后，沒有退出競(jìng)爭(zhēng)的節(jié)點(diǎn)按照所處槽位的第2位編碼繼續(xù)進(jìn)行第2輪競(jìng)爭(zhēng)，直至編碼結(jié)束選出對(duì)應(yīng)編碼的槽位為止.

當(dāng)分區(qū)過程執(zhí)行完成后，該槽位內(nèi)的車輛開始進(jìn)行基于競(jìng)爭(zhēng)窗口的沖突避免操作，直至選中唯一轉(zhuǎn)發(fā)車輛.

廣播過程中，受已知條件影響，槽位的編碼可能并不相同，BB分區(qū)的具體分區(qū)過程也會(huì)有所不同.以雙向2車道道路且通信半徑劃分為8個(gè)單位長(zhǎng)度槽位為例，圖5分別對(duì)已知道路車輛分布密度ρ=3/16(即通信范圍內(nèi)期望車輛數(shù)目為3)和已知通信范圍內(nèi)車輛數(shù)目Ncar=3兩種情況進(jìn)行舉例說明.

Fig. 5 The example of black-burst partition process圖5 BB分區(qū)過程示例

如圖5所示，已知車輛密度時(shí)，BB分區(qū)過程期望輪數(shù)為2.56輪；已知車輛數(shù)目時(shí)，分區(qū)過程期望輪數(shù)為2.39.而現(xiàn)有的二分分區(qū)法劃分精度為1/8時(shí)的期望分區(qū)輪數(shù)為3輪，可見本文提出的方案相較于現(xiàn)有方案能夠降低分區(qū)過程的平均輪數(shù)，提高緊急消息廣播性能.

此外，類哈夫曼編碼分區(qū)方法不僅可以降低BB分區(qū)平均輪數(shù)，還可以對(duì)道路進(jìn)行任意數(shù)目的分區(qū)，進(jìn)而獲得更加精確的分區(qū)結(jié)果，減少分區(qū)完成后所選區(qū)域內(nèi)車輛的數(shù)目.因此，HFMBB方法在CTB消息退避階段的第1輪退避過程中使用激進(jìn)的競(jìng)爭(zhēng)方法，即設(shè)置最大競(jìng)爭(zhēng)窗口為1，在BB分區(qū)完成后立即發(fā)送CTB報(bào)文.當(dāng)?shù)?輪退避過程偵測(cè)到?jīng)_突，證明同一分區(qū)范圍內(nèi)存在其他車輛時(shí)，則在進(jìn)行下一輪競(jìng)爭(zhēng)時(shí)將競(jìng)爭(zhēng)窗口值增大一倍，繼續(xù)進(jìn)行退避過程，直到?jīng)]有沖突完成中繼節(jié)點(diǎn)選擇.

4 實(shí)驗(yàn)與仿真分析

本節(jié)通過仿真實(shí)驗(yàn)對(duì)本文提出的類哈夫曼廣播方法進(jìn)行可行性驗(yàn)證和性能分析.由于文獻(xiàn)[14]已經(jīng)對(duì)路口區(qū)域進(jìn)行了較為詳盡的研究，因此本文主要針對(duì)非路口區(qū)域進(jìn)行研究.實(shí)驗(yàn)過程中，HFMBB方法存在2種情況：已知道路平均車輛分布(實(shí)驗(yàn)中用HFMAVG表示)和已知通信范圍內(nèi)具體車輛數(shù)目(實(shí)驗(yàn)中用HFMFIX表示).對(duì)比方法選用文獻(xiàn)[14]中二分方法(實(shí)驗(yàn)中用BPAB表示)和三分方法(實(shí)驗(yàn)中用3P3B表示).

4.1仿真環(huán)境設(shè)置

實(shí)驗(yàn)環(huán)節(jié)中，本文使用Veins[22]框架構(gòu)建仿真環(huán)境.Veins能夠提供十分接近真實(shí)情況的移動(dòng)和網(wǎng)絡(luò)仿真功能[23].本文實(shí)驗(yàn)中，網(wǎng)絡(luò)仿真部分在Veins框架的802.11p協(xié)議基礎(chǔ)上實(shí)現(xiàn).實(shí)驗(yàn)過程中參數(shù)默認(rèn)值如表1所示：

Table 1 Major Simulation Parameters

實(shí)驗(yàn)中，移動(dòng)模型使用SUMO[24]進(jìn)行模擬，SUMO使用Krau?等人[25]開發(fā)的微觀模型作為基礎(chǔ)，在車輛引擎、駕駛員行為偏好等方面進(jìn)行了一定的拓展，能夠較為真實(shí)地模擬城市環(huán)境中車輛的運(yùn)動(dòng)情況.仿真所使用道路的為武漢大學(xué)周邊東湖南路(長(zhǎng)3 200 m，2車道,記作道路1)和八一路(長(zhǎng)2 000 m，6車道,記作道路2)部分路段.其具體的場(chǎng)景如圖6所示.

Fig. 6 The map used in simulation圖6 仿真環(huán)境地圖信息

圖6為武大周邊環(huán)境，圖6中上下2條白色線條分別為東湖南路和八一路，右上方為SUMO軟件仿真過程所使用地圖的截圖.

實(shí)驗(yàn)過程中，本文方法分區(qū)精度Lslot=20 m，即將900 m通信距離分為45段.一般而言，城市道路每條車道的通過能力一般在每小時(shí)1 100輛以內(nèi)[26]，即每秒每車道最大通過車輛數(shù)目ρ≈0.30輛.實(shí)驗(yàn)對(duì)ρ∈[0.02,0.30]時(shí)不同方法的廣播過程進(jìn)行了研究.當(dāng)車輛行駛至道路末端100 m范圍時(shí)，車輛發(fā)起緊急消息廣播，并向后方道路傳播.直至道路末端通信半徑R內(nèi)的任一車輛成為中繼節(jié)點(diǎn)并完成緊急消息轉(zhuǎn)發(fā)，該緊急消息廣播過程停止.此時(shí)可以認(rèn)為緊急消息已完成對(duì)當(dāng)前道路的覆蓋.

由于緊急事件發(fā)生率較低，本文暫不考慮同時(shí)發(fā)生多處緊急事故和多條緊急消息同時(shí)廣播的情況，實(shí)驗(yàn)中同一時(shí)刻至多僅進(jìn)行一個(gè)緊急消息廣播.

4.2緊急廣播消息傳播速度

Fig. 7 Dissemination speed on Road One圖7 道路1的傳播速度

對(duì)于緊急消息廣播方法，信息傳播的速度是關(guān)鍵性的衡量標(biāo)準(zhǔn)之一.對(duì)于緊急消息而言，廣播信息傳播速度越快，則其他車輛能夠越早收到道路緊急事件消息，進(jìn)而越早采取止損措施，降低由此導(dǎo)致的損失.道路1和道路2上緊急消息傳播速度實(shí)驗(yàn)結(jié)果分別如圖7和圖8所示:

Fig. 8 Dissemination speed on Road Two圖8 道路2的傳播速度

圖7和圖8中，橫線表示使用各廣播方法時(shí)緊急消息在不同條件下的平均傳播速度.圖7和圖8中豎線中部的“×”標(biāo)記表示對(duì)應(yīng)數(shù)據(jù)的中位數(shù)，豎線的兩端分別表示1/4和3/4分位線.道路1的實(shí)驗(yàn)結(jié)果中，總體平均傳播速度：3P3B為4.95×106m/s，BPAB為4.58×106m/s，HFMAVG為5.40×106m/s，HFMFIX為5.42×106m/s.在道路1中，HFMAVG方法緊急消息傳播速度相較于3P3B和BPAB分別提高了9.0%和17.9%，而HFMFIX方法分別提高了9.4%和18.4%.道路2的實(shí)驗(yàn)結(jié)果中，總體平均傳播速度：3P3B為4.51×106m/s，BPAB為4.26×106m/s，HFMAVG為5.34×106m/s，HFMFIX為5.32×106m/s.在道路2中，HFMAVG方法緊急消息傳播速度相較于3P3B和BPAB分別提高了18.3%和25.5%，而HFMFIX方法分別提高了18.0%和25.1%.

實(shí)驗(yàn)結(jié)果表明：在車道較少的道路1中，相較于現(xiàn)有的3P3B和BPAB廣播方法，隨著車流量的不斷增大，HFMBB方法中緊急消息能夠更快地進(jìn)行傳播.同時(shí)，當(dāng)實(shí)驗(yàn)場(chǎng)景變?yōu)檐嚨罃?shù)目較多的道路2時(shí)，現(xiàn)有的3P3B和BPAB方法會(huì)隨著車輛密度增加而導(dǎo)致傳播速度下降.而HFMBB方法則能夠更好地適應(yīng)道路環(huán)境，維持較高的傳播速度.

4.3消息廣播單跳時(shí)延

影響廣播消息傳播速度的因素主要包括單跳廣播傳輸距離和單跳廣播轉(zhuǎn)發(fā)時(shí)延，為進(jìn)一步確定本文方法的性能表現(xiàn)，本節(jié)對(duì)不同廣播方法單跳廣播時(shí)延進(jìn)行了統(tǒng)計(jì)，其結(jié)果如圖9和圖10所示.道路1的實(shí)驗(yàn)結(jié)果中，總體平均單跳時(shí)延：3P3B為1.70×10-4s，BPAB為1.83×10-4s，HFMAVG為1.61×10-4s，HFMFIX為1.61×10-4s.HFMBB在已知道路1平均路況的情況下，緊急消息單跳時(shí)延相較于3P3B和BPAB分別降低了5.3%和11.6%，而在已知通信范圍內(nèi)具體車輛數(shù)目情況下分別降低了5.8%和12.0%.道路2的實(shí)驗(yàn)結(jié)果中，總體平均單跳時(shí)延：3P3B為1.97×10-4s，BPAB為2.06×10-4s，HFMAVG為1.69×10-4s，HFMFIX為1.69×10-4s.HFMBB在已知道路2平均路況的情況下，緊急消息單跳時(shí)延相較于3P3B和BPAB分別降低了14.4%和18.0%，而在已知通信范圍內(nèi)具體車輛數(shù)目情況下分別降低了14.2%和17.8%.

Fig. 9 One hop delay on Road One圖9 道路1的單跳延遲

Fig. 10 One hop delay on Road Two圖10 道路2的單跳延遲

實(shí)驗(yàn)結(jié)果表明，相對(duì)于現(xiàn)有的BABP方法和3P3B方法，在道路1車道較少的情況下，HFMBB方法在車輛密度較高時(shí)能夠降低單跳廣播時(shí)延，并提高緊急廣播消息的響應(yīng)速度.而在道路2中車道較多的情況下，3P3B和BPAB方法的單跳時(shí)延會(huì)有較大幅度的增長(zhǎng)，而2種HFMBB方法能夠有效控制單跳時(shí)延，在車道較多且車輛密集的情況下仍然能夠保證較低的緊急消息廣播單跳時(shí)延，確保緊急消息能夠被及時(shí)響應(yīng).

為了進(jìn)一步研究各通信步驟對(duì)單跳延遲的具體影響，本文以ρ=0.1的情況為例，研究了道路1和道路2緊急消息廣播單跳時(shí)延的組成，其結(jié)果分別如圖11和圖12所示.圖11和圖12中RTB Cost，BP Cost和CW Cost分別代表RTB報(bào)文發(fā)送階段、BB幀分區(qū)階段和競(jìng)爭(zhēng)窗口退避階段的時(shí)間開銷.

Fig. 11 Constitution of one hop delay on Road One圖11 道路1單跳時(shí)延構(gòu)成

Fig. 12 Constitution of one hop delay on Road Two圖12 道路2單跳時(shí)延構(gòu)成

道路2的車道數(shù)目大于道路1，通信范圍內(nèi)車輛數(shù)目也較多，最優(yōu)中繼車輛位置相對(duì)道路1的情況也更遠(yuǎn).因此采用動(dòng)態(tài)分區(qū)方法的HFMBB方法能夠更快速地確定最優(yōu)轉(zhuǎn)發(fā)車輛所在分區(qū)，BB分區(qū)時(shí)間開銷明顯降低.而現(xiàn)有的3P3B方法和BPAB方法由于采用相對(duì)固定的分區(qū)策略，因此BB分區(qū)時(shí)間沒有明顯變化.隨著車道增加，通信范圍內(nèi)的車輛數(shù)目也相應(yīng)增加，因此HFMBB方法完成BB分區(qū)后的第1輪競(jìng)爭(zhēng)有較大概率出現(xiàn)沖突，退避過程時(shí)間開銷也會(huì)相應(yīng)增加.但由于HFMBB分區(qū)精度較高，分區(qū)內(nèi)參與競(jìng)爭(zhēng)的車輛數(shù)目較少，退避時(shí)間開銷依然明顯小于3P3B方法和BPAB方法.

4.4消息廣播單跳傳播距離

影響緊急消息傳播速度的另一個(gè)因素是單跳廣播距離. 圖13和圖14分別為道路1和道路2場(chǎng)景中單跳傳播距離隨車流密度ρ變化的情況.道路1的實(shí)驗(yàn)結(jié)果中，總體平均單跳傳播距離：3P3B為8.33×102m，BPAB為8.27×102m，HFMAVG為8.54×102m，HFMFIX為8.54×102m.由于HFMAVG和HFMFIX的分區(qū)精度一致，因此2種情況下緊急消息單跳廣播距離性能基本一致，相對(duì)于3P3B方法和BPAB方法分別提升了2.4%和3.2%的單跳廣播傳播距離.道路2的實(shí)驗(yàn)結(jié)果中，平均單跳傳播距離：3P3B為8.59×102m，BPAB為8.50×102m，HFMAVG為8.81×102m，HFMFIX為8.81×102m.HFMBB方法相對(duì)3P3B方法和BPAB方法分別提升了2.6%和3.6%的單跳廣播傳播距離.

Fig. 14 One hop distance on Road Two圖14 道路2單跳傳播距離

結(jié)果表明，車道較多或者車輛密度較高時(shí)更多的備選車輛能夠增加最優(yōu)中繼車輛相對(duì)源節(jié)點(diǎn)的距離，可以提高單跳廣播距離.同時(shí)，由于3P3B方法2輪BB分區(qū)精度為1/9，而BPAB方法3輪BB分區(qū)精度為1/8，低于本文分段精度1/45，因此本文的單跳廣播距離高于現(xiàn)有方法，能夠提高緊急消息廣播過程單跳廣播信息傳播距離，進(jìn)而提高廣播消息傳播速度.

4.5車道數(shù)與分區(qū)精度影響

城市道路復(fù)雜多變，車道數(shù)目多種多樣.以長(zhǎng)度3 200 m的道路1為基礎(chǔ)，通過修改道路1的車道數(shù)目，本文以ρ=0.1的情況為例，進(jìn)一步研究了單車道道路到雙向6車道等不同車道數(shù)目對(duì)各廣播算法性能的影響.圖15展示了這些情況下各算法緊急消息傳播速度.

Fig. 15 Dissemination speed of different lane number圖15 不同車道情況下緊急消息傳播速度

圖15的實(shí)驗(yàn)結(jié)果表明，HFMBB方法在各種車道數(shù)目情況下均優(yōu)于現(xiàn)有的BPAB方法和3P3B方法.當(dāng)車道數(shù)目較少時(shí)可選的中繼車輛數(shù)目較少，最優(yōu)候選車輛分布在距離較近區(qū)域的可能性較高，因此各廣播算法傳播速度較慢.隨著車道數(shù)目增多，道路中可選車輛增多，因此傳播速度逐漸上升.但隨著車道數(shù)目進(jìn)一步增加，在完成BP分區(qū)過程后，會(huì)有更多的候選車輛參與分區(qū)后的退避過程，消息傳播速度開始逐漸下降.

本文提出的方案中，HFMAVG方法可以實(shí)現(xiàn)任意尺度的分區(qū)過程.本文以ρ=0.1的情況為例，進(jìn)一步研究了道路1場(chǎng)景中HFMAVG方法使用不同分區(qū)數(shù)目時(shí)的性能表現(xiàn)，其結(jié)果如圖16所示：

Fig. 16 Dissemination speed of different slot number圖16 不同分區(qū)數(shù)目時(shí)HFMAVG方法緊急消息傳播速度

實(shí)驗(yàn)結(jié)果顯示，分區(qū)數(shù)目較小時(shí)，BP分區(qū)完成后依然有大量候選節(jié)點(diǎn)需要進(jìn)行退避競(jìng)爭(zhēng)，因此消息傳播速度較低.隨著分區(qū)數(shù)目提高，BP分區(qū)之后剩余參與競(jìng)爭(zhēng)的候選車輛數(shù)目減少，因此能夠更快選出唯一候選車輛，消息傳播速度逐步提高.當(dāng)分區(qū)數(shù)目增加到一定程度后，由于車輛存在最小間隔，進(jìn)一步增加分區(qū)精度不能進(jìn)一步明顯降低BP分區(qū)后參與退避競(jìng)爭(zhēng)的車輛數(shù)目，因此更多的分區(qū)反而會(huì)增加BP分區(qū)過程的輪數(shù)，降低緊急消息傳播速度.

5 總結(jié)與展望

通過對(duì)BB方法中最優(yōu)車輛出現(xiàn)位置分布規(guī)律的研究，本文提出了一種基于BB幀的類哈夫曼編碼廣播方法——HFMBB.該方法依據(jù)當(dāng)前道路的車輛密度，動(dòng)態(tài)決定每一輪BB分區(qū)過程的分區(qū)比例，達(dá)到最優(yōu)化分區(qū)性能的目的.仿真實(shí)驗(yàn)證明，相較于現(xiàn)有方法，本文提出的HFMBB廣播方法能夠在不同場(chǎng)景分別降低5.3%～18.0%的廣播單跳時(shí)延，提高緊急消息廣播響應(yīng)及時(shí)性.同時(shí)HFMBB方法能夠提高2.6%～3.6%的單跳平均傳播距離，最終提高8.9%～24.5%的緊急消息廣播傳播速度.

綜合全文，本文主要有3點(diǎn)貢獻(xiàn)：

1) 對(duì)現(xiàn)有的基于BB的分區(qū)方案進(jìn)行了分析，歸納出統(tǒng)一的BB分區(qū)模式.

2) 從概率角度分析了最優(yōu)中繼車輛的分布規(guī)律，利用類哈夫曼編碼原理給出了不同交通密度情況下求解近似最優(yōu)分區(qū)方法的可行算法.

3) 設(shè)計(jì)了基于類哈夫曼編碼的緊急消息廣播方法HFMBB，并在仿真環(huán)境中對(duì)其進(jìn)行了詳細(xì)的驗(yàn)證和分析.

在未來的研究中，我們將針對(duì)通信范圍內(nèi)車輛數(shù)目和密度偵測(cè)、車輛阻塞等方面進(jìn)行進(jìn)一步的研究，以爭(zhēng)取減小緊急消息廣播中繼選擇時(shí)間.

[1]Bi Yuanguo, Zhou Haibo, Zhuang Weihua, et al. Overview of safety message broadcast in vehicular networks[G]Safety Message Broadcast in Vehicular Networks. Berlin: Springer, 2017: 11-24

[2]Al-Mefleh H, Al-Kofahi O. Taking advantage of jamming in wireless networks: A survey[J]. Computer Networks, 2016, 99(Supp.C): 99-124

[3]Haas Z J, Halpern J Y, Li Li. Gossip-based ad hoc routing[J]. IEEEACM Trans on Networking, 2006, 14(3): 479-491

[4]Wisitpongphan N, Tonguz O K, Parikh J S, et al. Broadcast storm mitigation techniques in vehicular ad hoc networks[J]. IEEE Wireless Communications, 2007, 14(6): 84-94

[5]Hafeez K A, Zhao Lian, Liao Zaiyi, et al. A new broadcast protocol for vehicular ad hoc networks safety applications[C]Proc of Global Telecommunications Conf. Piscataway, NJ: IEEE, 2010: 1-5

[6]Briesemeister L, Hommel G. Role-based multicast in highly mobile but sparsely connected ad hoc networks[C]Proc of the 1st Annual Workshop on Mobile and Ad Hoc Networking and Computing. Piscataway, NJ: IEEE, 2000: 45-50

[7]Fasolo E, Zanella A, Zorzi M. An effective broadcast scheme for alert message propagation in vehicular ad hoc networks[C]Proc of the 9th Int Conf on Communications. Piscataway, NJ: IEEE, 2006: 3960-3965

[8]Rayeni M S, Hafid A, Sahu P K. Dynamic spatial partition density-based emergency message dissemination in VANETs[J]. Vehicular Communications, 2015, 2(4): 208-222

[9]Lee T, Chung J M. Reception power quantization-based emergency message vehicle-to-vehicle multihop broadcast transmission scheme for vehicle accident prevention[J]. International Journal of Distributed Sensor Networks, 2017, 13(4): DOI: 10.1177/1550147717706619

[10]Korkmaz G, Ekici E, Ozguner F, et al. Urban multi-hop broadcast protocol for inter-vehicle communication systems[C]Proc of the 1st ACM Int Workshop on Vehicular Ad Hoc Networks. New York: ACM, 2004: 76-85

[11]Korkmaz G, Ekici E, Ozguner F. An efficient fully ad-hoc multi-hop broadcast protocol for inter-vehicular communication systems[C]Proc of 2006 IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2006: 423-428

[12]Sahoo J, Wu E H K, Sahu P K, et al. Binary-partition-assisted mac-layer broadcast for emergency message dissemination in vanets[J]. IEEE Trans on Intelligent Transportation Systems, 2011, 12(3): 757-770

[13]Suthaputchakun C, Dianati M, Sun Z. Trinary partitioned black-burst-based broadcast protocol for time-critical emergency message dissemination in vanets[J]. IEEE Trans on Vehicular Technology, 2014, 63(6): 2926-2940

[14]Bi Yuanguo, Shan Hangguan, Shen X S, et al. A multi-hop broadcast protocol for emergency message dissemination in urban vehicular ad hoc networks[J]. IEEE Trans on Intelligent Transportation Systems, 2016, 17(3): 736-750

[15]Ucar S, Ergen S C, Ozkasap O. Multihop-cluster-based IEEE 802.11p and LTE Hybrid architecture for vanet safety message dissemination[J]. IEEE Trans on Vehicular Technology, 2016, 65(4): 2621-2636

[16]Bi Yuanguo, Zhou Haibo, Zhuang Weihua, et al. Cross-layer broadcast in V2V communication networks[G]Safety Message Broadcast in Vehicular Networks. Berlin: Springer, 2017: 25-52

[17]Bi Yuanguo, Zhou Haibo, Zhuang Weihua, et al. Safety message dissemination in V2I Communication networks[G]Safety Message Broadcast in Vehicular Networks. Berlin: Springer, 2017: 83-101

[18]Eckhoff D, Sommer C, Dressler F. On the necessity of accurate IEEE 802.11p models for IVC protocol simulation[C]Proc of the 75th IEEE Vehicular Technology Conf. Piscataway, NJ: IEEE, 2012: DOI: 10.1109/VETECS.2012.6240064

[19]Darwish T, Bakar K A. Traffic density estimation in vehicular ad hoc networks: A review[J]. Ad Hoc Networks, 2015, 24(PA): 337-351

[20]Wu Weilong, Ping Wang, Chao Wang, et al. A beacon rate control scheme based on embms in cellular-vanets heterogeneous networks[C]Proc of Internet of Vehicles-Safe and Intelligent Mobility. Berlin: Springer, 2015: 324-335

[21]Erdmann J. Online-kalibrierung einer mikroskopischen verkehrssimulation[COL]Proc of Integration Platform for Management and Optimisation Systems in Traffic(ViMOS). K?ln, Germany: DLR, 2012 [2017-05-31]. http:elib.dlr.de79428

[22]Sommer C, Dressler F. Progressing toward realistic mobility models in VANET simulations[J]. IEEE Communications Magazine, 2008, 46(11): 132-137

[23]Sommer C, German R, Dressler F. Bidirectionally coupled network and road traffic simulation for improved IVC analysis[J]. IEEE Trans on Mobile Computing, 2011, 10(1): 3-15

[24]Krajzewicz D, Erdmann J, Behrisch M, et al. Recent development and applications of SUMO-simulation of urban mobility[J]. International Journal on Advances in Systems and Measurements, 2012, 5(34): 128-138

[25]Krau? S, Wagner P, Gawron C. Metastable states in a microscopic model of traffic flow[J]. Physical Review E, 1997, 5(1997): 5597-5602

[26]Wen Mengfei, Peng Jun, Zhu Zhengfa, et al. Distributed cooperative methods for traffic flow optimization in intelligent transportation network[J]. Journal of Chinese Computer Systems, 2012, 33(4): 852-855 (in Chinese)(文孟飛, 彭軍, 朱正發(fā), 等. 交通網(wǎng)絡(luò)車流量的分布式協(xié)同優(yōu)化方法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012, 33(4): 852-855)

WuLibing, born in 1972. PhD, professor. His main research interests include wireless sensor networks, network management and distributed computing.

FanJing, born in 1989. PhD candidate. His main research interests include Internet of vehicles and distributed computing.

WangJing, born in 1994. MSc candidate. Her main research interests include digital signatures and secure cloud storage.

NieLei, born in 1989. PhD candidate. His main research interests include wireless sensor networks and vehicular ad-hoc network.

WangHao, born in 1972. PhD. His main research interests include wireless sensor networks and vehicular ad-hoc network.

EmergencyMessageBroadcastMethodBasedonHuffman-LikeCoding

Wu Libing1,2, Fan Jing2, Wang Jing2, Nie Lei2, and Wang Hao3

1(State Key Laboratory of Software Engineering (Wuhan University), Wuhan 430072)2(Computer School, Wuhan University, Wuhan 430072)3(State Key Laboratory of Geomechanics and Geotechnical Engineering (Institute of Rock and Soil Mechanics, Chinese Academy of Sciences), Wuhan 430072)

The development of urban city greatly promotes the application of vehicular ad-hoc network, among which the safety-related emergency message broadcast is one of the key research points. The emergency message broadcast needs to meet the requirements for the quality of service such as low latency, high reliability, high scalability and so on. Most existing emergency message broadcasting methods, when selecting the next hop forwarding node, assume that there is an approximately equal probability of being selected as the relay area for each location, and the nodes of all positions are treated equally, which lacks the study of the distribution of the optimal node position so that it cannot adapt well to the distribution of the optimal forwarding node. However, the key to reducing the delay in emergency messaging is to quickly determine the appropriate relay forwarding node. Therefore, in order to further improve the timeliness of emergency message broadcasting and reduce the propagation delay, in this paper, we propose a Huffman coding-based emergency message broadcasting method. Generally, we first analyze the probability distribution of the optimal forwarding nodes in urban roads. And based on it, we then use the principle of Huffman coding to design a fast partition method, which can achieve the goals of quickly selecting optimal relay node, reducing the delay of emergency message broadcast, and improving the speed of emergency message transmission by minimizing the optimal node selection time. Our simulation results show that the proposed method can reduce the delay of emergency message broadcasts in different scenarios by 5.3%～18.0%, and improve the speed of emergency message transmission by 8.9%～24.5%.

vehicular ad hoc network; multi-hop broadcast protocols; emergency message dissemination; black-burst; Huffman coding

2017-05-31；

2017-08-08

國家自然科學(xué)基金項(xiàng)目(61472287,61572370,61772377);湖北省自然科學(xué)基金重點(diǎn)項(xiàng)目(2015CFA068);武漢市科技計(jì)劃項(xiàng)目(2016060101010047)

This work was supported by the National Natural Science Foundation of China (61472287, 61572370, 61772377), the Science and Technology Support Program of Hubei Province (2015CFA068), and the Science and Technology Plan of Wuhan City (2016060101010047).

TP391