基于类哈夫曼编码的紧急消息广播方法

1 (软件工程国家重点实验室(武汉大学) 武汉 430072) 2 (武汉大学计算机学院武汉 430072) 3 (岩土力学与工程国家重点实验室(中国科学院武汉岩土力学研究所) 武汉 430072)

摘要 城市的发展为车载自组织网络(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的随机广播方法.由于节点会重复广播所有收到的信息，因此洪泛方法效率极低，且容易引起广播风暴 [3] .为提高信道利用率，降低广播风暴发生风险，文献[4]分别提出了权重 p 坚持(weighted p -persistence, WPP)和间隙 p 坚持(slotted p -persistence, SPP)两类基于概率的广播方法，收到广播的节点，根据距离相关的概率来决定是否在信道空闲时进行广播.WPP方法中，远处的车辆使用较高的转发概率，而源节点附近的车辆使用较低的转发概率；SPP方法中，车辆转发概率相同，但距离发送车辆远的车辆，需要等待的信道空闲时间短，因而能够更早进行消息转发.

虽然改进的基于概率的方案能够减少发生广播风暴的风险，但当道路车辆较为密集时，依然会产生大量的冗余广播.文献[5]进一步提出了基于交通密度的概率转发方案，通过在交通拥挤时降低车辆转发报文的概率，减少冗余报文，提高信道利用率，但依然无法完全克服报文大量冗余转发的问题.

区别于基于概率的广播方法，基于距离退避的方法旨在根据与发送节点的距离，适当选择退避时间，并选择一跳范围内最远节点作为消息传输的中继节点.文献[6]通过控制车辆转发紧急消息的退避时间来选择最远车辆作为中继节点.在收到需要广播的紧急消息后，离发送车辆越远的车辆将会更早进行紧急消息的广播，但是该方案主要适用于车流稀疏的高速道路.而在城市环境中，车辆更加密集，需要对等待时间进行更细致的划分，进而导致源节点远方没有车辆时近距离车辆需要等待很长时间才能对紧急消息进行转发.针对该问题，文献[7]提出了一种智能广播方法(smart broadcast, SB).在SB方法中，广播车辆通信范围内的道路被分为若干区域，道路中的车辆按照区域由远至近的不同，采用按一定尺寸递增的退避窗口，而同一个区域内的车辆则选择对应退避窗口范围内的随机退避时间进行退避.通过区域内车辆共享退避窗口，SB方法能够降低整个退避过程需要消耗的时间.但与此同时，当道路中车辆密集时，同一个退避窗口会有大量车辆参与竞争，退避过程中极易发生冲突.文献[8]提出了一种动态分区策略(dynamic partitioning scheme, DPS)来解决上述问题.DPS方法通过探测邻居车辆密度来动态地决定区域划分的数目，因而在一定程度上能够适应于不同的道路环境.文献[9]引入接收能量来判定距离，提高了基于距离算法的适用环境.

基于距离退避的广播方法中，离发送节点较近的车辆需要等待很长的退避时间.当道路较为空旷，且发送节点通信范围的远端没有车辆时，近端车辆需要等待较长时间才能进行转发，从而产生较大的转发延迟，无法满足紧急消息广播需求.

基于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分区方法基本原理进行了概括和定义.

城市道路一般由双向多车道道路构成.以图1所示双向4车道道路为例，道路由4条车道构成，其中 L 1 , L 0 车道上的车辆自右向左行驶， R 0 , R 1 车道上的车辆自左向右行驶.

城市环境中，车辆与车辆使用无线信道进行通信，其最远通信范围可以达到1 400 m [18] .但在紧急消息广播过程中，为了保证信息传播的可靠性会对单跳通信距离R加以限制.一般认为城市道路中自由移动的车辆服从泊松分布 [11-13] .将道路划分为长度为L连续的段落，每一个段落称为一个槽位，如图1中S 0 ～S 17 所示.每个槽位中可能存在车辆，也可能不存在车辆.若ρ为车辆密度，表示每个车道在单位长度的道路上车辆的平均数目，则每个槽位中存在车辆的概率满足p slot =1- e -ρ·L .一个槽位存在车辆时，车辆可能分布在该槽位范围内的任意位置.

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

广播发起车辆A在发起广播时需要发送 RTB 报文，其中包含了自身的位置信息.在成功接收到 RTB 报文的车辆中，只有距离广播发起车辆A小于R的车辆才能成为候选车辆，并参与紧急消息的转发 [13] .例如图1中位于槽位S 17 的车辆，由于超出了距离范围，因此即使成功接收到广播车辆发送的紧急消息也不能成为候选的中继车辆.最优转发车辆B为通信范围内距离广播车辆A距离最远的车辆，选择该车辆进行广播可以达到最大单跳广播距离.

现有基于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二分法中 S 3 , S 4 )首先发送BB帧.若第1轮广播车辆收到BB帧，则远端位置存在车辆，第2轮中远端车辆再进一步划分为2个部分，并进行第2轮划分，直到划分至需要的轮数后，被选中区域中的车辆开始进行退避，并发送CTB报文进行冲突避免.

而N分法则是将区域划分为N等分，每轮中又分为至多N-1个间隔，车辆按照所处分区的距离，由远到近在对应序号间隔内发送 BB 帧.当任一间隔内有车辆发送 BB 帧时，则可确认该间隔对应的分区存在最优候选中继车辆，进而开始下一轮划分过程.

如图2( b )三分法为例，若S 7 ～S 9 区域内存在车辆，则该区域内车辆在第1轮的第1个时间间隔内发送 BB 帧，并立即进入第2轮分区过程；反之，若S 7 ～S 9 区域内不存在车辆，则S 4 ～S 6 区域内的车辆在第1轮的第2个时间间隔内发送 BB 帧.此时若侦听到 BB 帧，则最优候选车辆位于S 4 ～S 6 区域内，分区过程进入第2轮.如果第1轮的第2个间隔仍然没有车辆发送 BB 帧，那么候选车辆必然位于S 1 ～S 3 区域内，分区过程进入第2轮.

3 基于类哈夫曼编码的广播方法

BB的分区目标是选择距离源节点最远的存在候选车辆的区域，但现有的方法均采用一定比值的分区方案，没有充分考虑最优候选车辆出现位置分布对分区过程的影响.本节首先对最优候选车辆出现位置的分布情况分析，再以此为基础设计一种能够充分考虑具体分布情况的分区方法，达到降低平均分区轮数，减低中继选择延迟的目的.

假定某道路包含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) 彼此独立且等于p s lot =1- e -ρ ·L .

而条件1和条件2互为独立事件，因此最优候选车辆位于槽位slot=(m,n)的概率P| n far =(m,n) 为

如果使用基于 Beacon 消息的邻居节点感知方法 [20] ，则能够获得通信半径内具体的车辆数目N car .受车辆长度vLen和安全距离minGap的限制 [21] ，车辆之间的最小间隔L min =vLen+minGap.将通信半径R划分为N个长度为L min 的槽位，则车辆在道路中的分布可以转换为槽位占用组合问题.

组合问题中，车道m∈[1,M]的第n个槽位slot=n中是否有车会影响其他槽位，条件1和条件2成为相关条件，须同时考虑.

当前条件下，存在的所有组合数目C all 等价于所有槽位slot=(m,n),m∈[1,M]，n∈[1,N]中选取N car 个槽位有车，计算为

条件1和条件2同时满足的组合情况为第n个槽位slot=n中至少有一辆车，而其他车辆分布于槽位slotlt;n中.其组合数目C n far =n 可以计算为

因此，已知通信范围内车辆数目情况下，最优候选车辆位于槽位slot=n的概率P b | n far =(m,n) 计算为

哈夫曼编码(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分区过程.

本节以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的节点(例如位于槽位 S 8 和 S 7 的节点)，则编码为0的节点退出竞争.分区第1轮完成后，没有退出竞争的节点按照所处槽位的第2位编码继续进行第2轮竞争，直至编码结束选出对应编码的槽位为止.

当分区过程执行完成后，该槽位内的车辆开始进行基于竞争窗口的冲突避免操作，直至选中唯一转发车辆.

广播过程中，受已知条件影响，槽位的编码可能并不相同，BB分区的具体分区过程也会有所不同.以双向2车道道路且通信半径划分为8个单位长度槽位为例，图5分别对已知道路车辆分布密度 ρ =3/16(即通信范围内期望车辆数目为3)和已知通信范围内车辆数目 N car =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表示).

实验环节中，本文使用Veins [22] 框架构建仿真环境.Veins能够提供十分接近真实情况的移动和网络仿真功能 [23] .本文实验中，网络仿真部分在Veins框架的802.11p协议基础上实现.实验过程中参数默认值如表1所示：

Table 1 Major Simulation Parameters

表1 主要仿真参数设置

实验中，移动模型使用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软件仿真过程所使用地图的截图.

实验过程中，本文方法分区精度 L slot =20 m，即将900 m通信距离分为45段.一般而言，城市道路每条车道的通过能力一般在每小时1 100辆以内 [26] ，即每秒每车道最大通过车辆数目 ρ ≈0.30辆.实验对 ρ ∈[0.02,0.30]时不同方法的广播过程进行了研究.当车辆行驶至道路末端100 m范围时，车辆发起紧急消息广播，并向后方道路传播.直至道路末端通信半径 R 内的任一车辆成为中继节点并完成紧急消息转发，该紧急消息广播过程停止.此时可以认为紧急消息已完成对当前道路的覆盖.

由于紧急事件发生率较低，本文暂不考虑同时发生多处紧急事故和多条紧急消息同时广播的情况，实验中同一时刻至多仅进行一个紧急消息广播.

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×10 6 m/s，BPAB为4.58×10 6 m/s，HFMAVG为5.40×10 6 m/s，HFMFIX为5.42×10 6 m/s.在道路1中，HFMAVG方法紧急消息传播速度相较于3P3B和BPAB分别提高了9.0%和17.9%，而HFMFIX方法分别提高了9.4%和18.4%.道路2的实验结果中，总体平均传播速度：3P3B为4.51×10 6 m/s，BPAB为4.26×10 6 m/s，HFMAVG为5.34×10 6 m/s，HFMFIX为5.32×10 6 m/s.在道路2中，HFMAVG方法紧急消息传播速度相较于3P3B和BPAB分别提高了18.3%和25.5%，而HFMFIX方法分别提高了18.0%和25.1%.

实验结果表明：在车道较少的道路1中，相较于现有的3P3B和BPAB广播方法，随着车流量的不断增大，HFMBB方法中紧急消息能够更快地进行传播.同时，当实验场景变为车道数目较多的道路2时，现有的3P3B和BPAB方法会随着车辆密度增加而导致传播速度下降.而HFMBB方法则能够更好地适应道路环境，维持较高的传播速度.

影响广播消息传播速度的因素主要包括单跳广播传输距离和单跳广播转发时延，为进一步确定本文方法的性能表现，本节对不同广播方法单跳广播时延进行了统计，其结果如图9和图10所示.道路1的实验结果中，总体平均单跳时延：3P3B为1.70×10 -4 s，BPAB为1.83×10 -4 s，HFMAVG为1.61×10 -4 s，HFMFIX为1.61×10 -4 s.HFMBB在已知道路1平均路况的情况下，紧急消息单跳时延相较于3P3B和BPAB分别降低了5.3%和11.6%，而在已知通信范围内具体车辆数目情况下分别降低了5.8%和12.0%.道路2的实验结果中，总体平均单跳时延：3P3B为1.97×10 -4 s，BPAB为2.06×10 -4 s，HFMAVG为1.69×10 -4 s，HFMFIX为1.69×10 -4 s.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方法.

影响紧急消息传播速度的另一个因素是单跳广播距离. 图13和图14分别为道路1和道路2场景中单跳传播距离随车流密度 ρ 变化的情况.道路1的实验结果中，总体平均单跳传播距离：3P3B为8.33×10 2 m，BPAB为8.27×10 2 m，HFMAVG为8.54×10 2 m，HFMFIX为8.54×10 2 m.由于HFMAVG和HFMFIX的分区精度一致，因此2种情况下紧急消息单跳广播距离性能基本一致，相对于3P3B方法和BPAB方法分别提升了2.4%和3.2%的单跳广播传播距离.道路2的实验结果中，平均单跳传播距离：3P3B为8.59×10 2 m，BPAB为8.50×10 2 m，HFMAVG为8.81×10 2 m，HFMFIX为8.81×10 2 m.HFMBB方法相对3P3B方法和BPAB方法分别提升了2.6%和3.6%的单跳广播传播距离.

Fig. 13 One hop distance on Road One
图13 道路1单跳传播距离

Fig. 14 One hop distance on Road Two
图14 道路2单跳传播距离

结果表明，车道较多或者车辆密度较高时更多的备选车辆能够增加最优中继车辆相对源节点的距离，可以提高单跳广播距离.同时，由于3P3B方法2轮BB分区精度为1/9，而BPAB方法3轮BB分区精度为1/8，低于本文分段精度1/45，因此本文的单跳广播距离高于现有方法，能够提高紧急消息广播过程单跳广播信息传播距离，进而提高广播消息传播速度.

城市道路复杂多变，车道数目多种多样.以长度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%的紧急消息广播传播速度.

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]. IEEE

ACM 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[C

OL]

Proc of Integration Platform for Management and Optimisation Systems in Traffic(ViMOS). Köln, Germany: DLR, 2012 [2017-05-31]. http:

elib.dlr.de

79428

[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(3

4): 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)

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

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

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

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

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

Emergency Message Broadcast Method Based on Huffman - Like Coding

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)

Abstract 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%.

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

基金项目： 国家自然科学基金项目(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).