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

吳黎兵 范 靜 王 婧 聶 雷 王 浩

1(軟件工程國家重點實驗室(武漢大學) 武漢 430072) 2(武漢大學計算機學院 武漢 430072) 3(巖土力學與工程國家重點實驗室(中國科學院武漢巖土力學研究所) 武漢 430072)

(wu@whu.edu.cn)

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

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

1(軟件工程國家重點實驗室(武漢大學) 武漢 430072)2(武漢大學計算機學院 武漢 430072)3(巖土力學與工程國家重點實驗室(中國科學院武漢巖土力學研究所) 武漢 430072)

(wu@whu.edu.cn)

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

車聯網；多跳廣播協議；緊急消息分發；干擾幀；哈夫曼編碼

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

城市道路中，車輛的快速移動帶來了車載自組織網絡(vehicular ad hoc network, VANET)(也稱車聯網)網絡拓撲的快速變化，而緊急消息的廣播卻需要達成高可靠性和低時延等服務質量要求.由于無線傳輸距離的限制，為了覆蓋足夠的范圍，緊急消息往往需要通過多跳廣播才能夠完全覆蓋目標區域，因此快速選擇合適的中繼節點就成為了研究的焦點.

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

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

1) 在合理量化車輛分布規律的基礎上，對最優中繼車輛出現位置的概率分布進行了理論推導，并給出了2種已知條件情況下對最優中繼車輛分布的計算方法.

2) 利用哈夫曼編碼原理構造了一種多跳廣播協議最優中繼車輛選擇方法，設計了基于類哈夫曼編碼的緊急消息廣播方法HFMBB，并在仿真環境中對其進行了詳細的驗證和分析.

1 相關工作

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

1.1基于概率的廣播方法

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

雖然改進的基于概率的方案能夠減少發生廣播風暴的風險，但當道路車輛較為密集時，依然會產生大量的冗余廣播.文獻[5]進一步提出了基于交通密度的概率轉發方案，通過在交通擁擠時降低車輛轉發報文的概率，減少冗余報文，提高信道利用率，但依然無法完全克服報文大量冗余轉發的問題.

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

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

基于距離退避的廣播方法中，離發送節點較近的車輛需要等待很長的退避時間.當道路較為空曠，且發送節點通信范圍的遠端沒有車輛時，近端車輛需要等待較長時間才能進行轉發，從而產生較大的轉發延遲，無法滿足緊急消息廣播需求.

1.3基于black-burst的廣播方法

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

此外，文獻[15]利用長期演進(long term evolu-tion, LTE)技術輔助進行緊急消息廣播，文獻[16]利用多層協議進行緊急消息廣播，文獻[17]利用RSU協助進行緊急消息廣播.

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

2 系統模型和基礎知識

研究城市環境中車輛廣播通信過程首先需要對應用場景進行定義和建模.本節針對城市場景進行了建模分析，分別對道路模型、車輛通信模型和BB分區方法基本原理進行了概括和定義.

2.1城市道路與通信模型

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

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

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

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

2.2black-burst分區原理

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

Fig. 2 The example for existing black-burst partitioning圖2 現有black-burst分區方法示例

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

而N分法則是將區域劃分為N等分，每輪中又分為至多N-1個間隔，車輛按照所處分區的距離，由遠到近在對應序號間隔內發送BB幀.當任一間隔內有車輛發送BB幀時，則可確認該間隔對應的分區存在最優候選中繼車輛，進而開始下一輪劃分過程.

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

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

BB的分區目標是選擇距離源節點最遠的存在候選車輛的區域，但現有的方法均采用一定比值的分區方案，沒有充分考慮最優候選車輛出現位置分布對分區過程的影響.本節首先對最優候選車輛出現位置的分布情況分析，再以此為基礎設計一種能夠充分考慮具體分布情況的分區方法，達到降低平均分區輪數，減低中繼選擇延遲的目的.

3.1最優候選車輛分布概率分析

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

組合問題中，車道m∈[1,M]的第n個槽位slot=n中是否有車會影響其他槽位，條件1和條件2成為相關條件，須同時考慮.

當前條件下，存在的所有組合數目Call等價于所有槽位slot=(m,n),m∈[1,M]，n∈[1,N]中選取Ncar個槽位有車，計算為

(4)

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

(5)

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

3.2類哈夫曼編碼算法

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

但是BB分區過程并不完全等價于字符編碼.BB分區編碼過程與標準哈夫曼編碼過程存在2點區別：

1) BB分區編碼過程中，發送BB幀的槽位會掩蓋不發送BB幀的槽位.

2) 槽位擁有優先級，即編碼結果中距離遠的槽位不能被距離近的槽位掩蓋.

由此可見，不同于標準哈夫曼編碼方法，進行BB分區編碼時，遠端部分的槽位必須優先編碼為1，且槽位不可交換順序，必須按優先級排序.在以上區別限制的情況下，本文構造類哈夫曼編碼算法流程如圖3所示.

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

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

廣播過程中收到RTB報文的候選車輛根據自身所處的槽位的編號，依據編碼結果依次監聽和發送BB幀，完成BB分區過程.

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

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

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

當需要進行廣播時，源節點等待mini-DIFS[12]的信道空閑時間后，發送攜帶自身位置和車輛密度信息的RTB報文，聲明緊急消息廣播開始.備選車輛收到RTB報文后，在下一個GPS同步時間同時發送BB幀，表明當前通信范圍內存在候選車輛，并開始執行BB分區過程.

BB分區過程開始的第1輪，第1位編碼為1的節點首先發送BB幀，而第1位編碼為0的節點則僅進行監聽.如果第1輪存在編碼為1的節點(例如位于槽位S8和S7的節點)，則編碼為0的節點退出競爭.分區第1輪完成后，沒有退出競爭的節點按照所處槽位的第2位編碼繼續進行第2輪競爭，直至編碼結束選出對應編碼的槽位為止.

當分區過程執行完成后，該槽位內的車輛開始進行基于競爭窗口的沖突避免操作，直至選中唯一轉發車輛.

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

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

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

此外，類哈夫曼編碼分區方法不僅可以降低BB分區平均輪數，還可以對道路進行任意數目的分區，進而獲得更加精確的分區結果，減少分區完成后所選區域內車輛的數目.因此，HFMBB方法在CTB消息退避階段的第1輪退避過程中使用激進的競爭方法，即設置最大競爭窗口為1，在BB分區完成后立即發送CTB報文.當第1輪退避過程偵測到沖突，證明同一分區范圍內存在其他車輛時，則在進行下一輪競爭時將競爭窗口值增大一倍，繼續進行退避過程，直到沒有沖突完成中繼節點選擇.

4 實驗與仿真分析

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

4.1仿真環境設置

實驗環節中，本文使用Veins[22]框架構建仿真環境.Veins能夠提供十分接近真實情況的移動和網絡仿真功能[23].本文實驗中，網絡仿真部分在Veins框架的802.11p協議基礎上實現.實驗過程中參數默認值如表1所示：

Table 1 Major Simulation Parameters

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

Fig. 6 The map used in simulation圖6 仿真環境地圖信息

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

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

由于緊急事件發生率較低，本文暫不考慮同時發生多處緊急事故和多條緊急消息同時廣播的情況，實驗中同一時刻至多僅進行一個緊急消息廣播.

4.2緊急廣播消息傳播速度

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

對于緊急消息廣播方法，信息傳播的速度是關鍵性的衡量標準之一.對于緊急消息而言，廣播信息傳播速度越快，則其他車輛能夠越早收到道路緊急事件消息，進而越早采取止損措施，降低由此導致的損失.道路1和道路2上緊急消息傳播速度實驗結果分別如圖7和圖8所示:

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

圖7和圖8中，橫線表示使用各廣播方法時緊急消息在不同條件下的平均傳播速度.圖7和圖8中豎線中部的“×”標記表示對應數據的中位數，豎線的兩端分別表示1/4和3/4分位線.道路1的實驗結果中，總體平均傳播速度：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的實驗結果中，總體平均傳播速度：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%.

實驗結果表明：在車道較少的道路1中，相較于現有的3P3B和BPAB廣播方法，隨著車流量的不斷增大，HFMBB方法中緊急消息能夠更快地進行傳播.同時，當實驗場景變為車道數目較多的道路2時，現有的3P3B和BPAB方法會隨著車輛密度增加而導致傳播速度下降.而HFMBB方法則能夠更好地適應道路環境，維持較高的傳播速度.

4.3消息廣播單跳時延

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

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

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

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

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

Fig. 11 Constitution of one hop delay on Road One圖11 道路1單跳時延構成

Fig. 12 Constitution of one hop delay on Road Two圖12 道路2單跳時延構成

道路2的車道數目大于道路1，通信范圍內車輛數目也較多，最優中繼車輛位置相對道路1的情況也更遠.因此采用動態分區方法的HFMBB方法能夠更快速地確定最優轉發車輛所在分區，BB分區時間開銷明顯降低.而現有的3P3B方法和BPAB方法由于采用相對固定的分區策略，因此BB分區時間沒有明顯變化.隨著車道增加，通信范圍內的車輛數目也相應增加，因此HFMBB方法完成BB分區后的第1輪競爭有較大概率出現沖突，退避過程時間開銷也會相應增加.但由于HFMBB分區精度較高，分區內參與競爭的車輛數目較少，退避時間開銷依然明顯小于3P3B方法和BPAB方法.

4.4消息廣播單跳傳播距離

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

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

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

4.5車道數與分區精度影響

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

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

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

本文提出的方案中，HFMAVG方法可以實現任意尺度的分區過程.本文以ρ=0.1的情況為例，進一步研究了道路1場景中HFMAVG方法使用不同分區數目時的性能表現，其結果如圖16所示：

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

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

5 總結與展望

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

綜合全文，本文主要有3點貢獻：

1) 對現有的基于BB的分區方案進行了分析，歸納出統一的BB分區模式.

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

3) 設計了基于類哈夫曼編碼的緊急消息廣播方法HFMBB，并在仿真環境中對其進行了詳細的驗證和分析.

在未來的研究中，我們將針對通信范圍內車輛數目和密度偵測、車輛阻塞等方面進行進一步的研究，以爭取減小緊急消息廣播中繼選擇時間.

[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)(文孟飛, 彭軍, 朱正發, 等. 交通網絡車流量的分布式協同優化方法研究[J]. 小型微型計算機系統, 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

國家自然科學基金項目(61472287,61572370,61772377);湖北省自然科學基金重點項目(2015CFA068);武漢市科技計劃項目(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