一种动态迭代分区紧急消息广播方法

聂 雷，张全玉，李 鹏，何 亨，吴黎兵(武汉科技大学计算机科学与技术学院，武汉430065)

2(智能信息处理与实时工业系统湖北省重点实验室，武汉430065)

3(武汉大学计算机学院，武汉430072)

E-mail:lnie@wust.edu.cn

1 引言

车联网(Vehicular Ad Hoc Network，VANET)作为物联网和移动互联网发展的代表性产物，成为现代智能交通的重要组成部分.目前，基于车联网技术的智能交通应用十分广泛，例如交通信号控制［1，2］、内容协助下载［3，4］和安全通信［5，6］等.其中，紧急消息广播作为车联网的安全类应用，能提供高效安全的驾驶环境，有效避免人员伤亡和减少经济损失，是车联网领域中的研究热点.

紧急消息广播在实时性和可靠性方面具有极高的需求.在车联网环境中，消息主要基于专用短程通信(Dedicated Short Range Communications，DSRC)技术或移动蜂窝网络，利用车与车/车与基础设施(Vehicle-to-Vehicle/Vehicle-to-Infrastructure，V2V/V2I)的通信方式进行多跳广播.紧急消息进行多跳广播的关键是快速选取下一跳的中继节点，现有的选取策略主要可以分为基于概率、基于距离-等待时间以及基于Black-burst迭代分区三种类型.其中，Black-burst［7］是一种可以多个目标同时传输且互不冲突的干扰信号，近年来一些研究学者利用这种特性支持紧急消息的广播.具体来讲，基于Black-burst的广播方法通过车辆之间的Black-burst交互对候选区域进行迭代分区，达到缩小候选中继节点竞争区域的目的，接着基于 RTB/CTB(Request To Broadcast/Clear To Broadcast)［8］握手机制从最远非空路段(即最佳路段)中选出唯一的中继节点.与其他类型的多跳广播方法相比较，基于Black-burst迭代分区的方法能够最大程度减少广播风暴和终端隐藏的影响，并且可以尽可能远地选择中继节点，有利于紧急消息的快速广播.

然而，现有的基于Black-burst方法的迭代分区机制较为固定，没有考虑车流密度对分区机制效果的影响.此外，由于采用竞争窗口机制选择唯一中继节点，导致CTB冲突容易在车流密度较大时发生.如何有效减少CTB冲突，并实现紧急消息的快速广播是现有这类方法亟需解决的问题.

本文第2节介绍了车联网环境下紧急消息广播的研究现状;第3节首先给出了系统模型，并详细介绍了基于动态迭代分区机制的紧急消息广播方法DIPS-MB(Dynamic and Iterative Partitioning Scheme based Multi-hop Broadcast);第4节从理论上分析了DIPS-MB方法的平均一跳时延和传播速度;第5节通过实验验证并分析了DIPS-MB方法的有效性;第6节是本文的总结和对下一步工作的展望.

2 相关工作

基于概率的广播方法允许部分候选车辆转发紧急消息，这类方法最重要的问题是确定消息转发概率.文献［9］提出了两种基于概率的广播方法，分别是权重p坚持方法WPP(Weighted p-Persistence)和时隙p坚持方法SPP(Weighted p-Persistence).与传统的固定 p坚持方法［10］不同，WPP为远端的候选车辆分配了更大的转发概率.尽管在SPP中车辆被赋予了固定大小的转发概率，但是远端的车辆会在紧急消息广播之前等待一个较短的时间.文献［11］考虑车流密度和位置信息提出了一种灵活的基于概率的方法，位于远端的候选车辆在车流稀疏情况下拥有更大的广播概率.基于概率的方法在一定程度上减轻了消息冗余和碰撞，但是在高度动态的车辆环境中难以确定一个合适的转发概率.此外，远端的车辆由于概率性因素无法总是被选为中继节点.

基于距离-等待时间的方法倾向选择最远的一跳邻居车辆作为中继节点.文献［12］将距离消息发送者越远的候选车辆设定一个更短的等待时间后开始广播紧急消息，然而该方法只能适用于车辆稀疏且互联的高速场景中.文献［13］提出了一种基于位置感知的智能广播方法SB(Smart Broadcast)，消息发送者的通信范围被迭代分区成若干个路段，这些路段由远及近被依次分配一个递增且不重合的竞争窗口，因此位于远端路段的车辆会在一个较小的竞争窗口中选择一个随机退避值，有利于优先被选为中继节点.然而，SB没有提供消息碰撞的解决机制，同时被划分的路段数量是一个常量.文献［14］提出了一种动态分区方案 DPS(Dynamic Partitioning Scheme)，路段的数量取决于邻居车辆的密度，因此该方法能够有效作用在多种交通情况下.然而，现有基于距离-等待时间方法的性能极大地受到中继车辆位置的影响，例如在车流稀疏情况下，中继车辆可能非常靠近消息发送者，因此其会等待一段较长的时间才开始转发紧急消息.

基于Black-burst的方法通过迭代分区有效缩小最佳候选车辆的竞争范围，从而实现减少竞争冲突和提高紧急消息传播速度的目的.文献［15］提出了一种基于Black-burst的二进制分区协助多跳广播方法BPAB(Binary Partition Assisted Broadcast).消息发送者的通信距离被迭代分区成多个路段，并利用消息发送者和邻居车辆之间的Black-burst交互寻找出最远非空路段，同时利用竞争窗口机制从最佳路段中选出唯一的中继节点.文献［16］和文献［17］分别基于BPAB提出了基于Black-burst的三进制分区协助多跳广播方法3P3B(Trinary Partitioned Black-burst-based Broadcast)和城市多跳广播方法UMBP(Urban Multi-hop Broadcast Protocol).其中，3P3B首次引入了mini-DIFS(mini Distributed Inter Frame Space)机制，用于减少紧急消息的信道访问时延;而UMBP则解决了城市交叉路口处多方向广播的消息碰撞问题.为了解决CTB(Clear To Broadcast)冲突引起的传输时延问题，文献［18］提出了一种基于Black-burst和多信道技术的多跳广播方法BMMB(Black-burst and Multi-channel based Multi-hop Broadcast).与现有的多跳广播方法对比，BMMB利用Blackburst和多信道技术缩短了寻找最优路段的迭代过程，同时在避免CTB冲突的前提下，能够在最优路段中选出唯一的中继节点.

与基于概率和基于距离-等待时间的方法相比，基于Black-burst的广播方法能在尽可能小地减少候选节点之间的冲突的前提下，找到唯一最佳中继车辆，方法的性能更为高效.然而，当前基于Black-burst的广播方法普遍存在迭代分区机制较为固定的问题，并没有考虑车流密度对分区效果的影响.针对上述问题，本文提出了一种更为高效的多跳广播方法DIPS-MB，其关键在于能够在不同车流密度下动态选择最佳迭代分区机制，从而进一步缩小寻找最佳候选车辆的时间.与同类方法对比，基于DIPS-MB的紧急消息在动态车流环境中具有更小的单跳时延和更快的传播速度.

3 基于动态迭代机制的广播方法

3.1 系统模型与假设

本节描述了系统模型，并列出了支撑本文所提方法的必要假设条件.如图1所示，考虑一个典型城市场景下的紧急消息多跳广播.最左侧车辆作为源节点向周围广播紧急消息，并选取了同向的一个邻居车辆作为紧急消息的转发节点，该转发节点随后继续寻找下一跳来协助完成多跳广播.当转发节点靠近交叉路口时，将紧急消息广播给位于路口中心的中继器，并由中继器完成紧急消息的多向广播.因此本文主要解决的是直路上的单向多跳广播.

本文的系统模型满足以下假设条件:

1)双向多车道的城市场景中，车辆密度为ρ且服从泊松分布;

2)交叉路口处安置有消息中继器，能够实现紧急消息在交叉路口处的多方向广播;

3)车辆装配GPS和电子地图获取位置信息，同时借助车载单元OBU(On-Board Unit)基于DSRC技术进行V2V/V2I通信;

4)车辆具备自适应调节天线发射功率的能力，默认功率和通信距离分别为P和R，且R为有效通信距离;

图1 系统模型Fig.1 System model

5)通信过程中不考虑无线信道错误.即在有效的通信距离R内，紧急消息都能被正确接收;

6)紧急消息的最大有效传输距离为Dmax，最大跳数为Hmax.

3.2 多跳广播方法DIPS-MB

在城市场景中，紧急消息的广播主要存在直路上的单向广播以及交叉路口处的多向广播.本文采用基于地理位置的广播策略.具体来讲，当转发车辆与交叉路口安置的中继器之间的距离大于有效通信距离R时，转发车辆采用基于V2V通信的方式多跳传递紧急消息;否则转发车辆广播紧急消息，并由中继器完成交叉路口处的多方向广播.下面着重介绍基于V2V通信方式的多跳广播，即基于动态迭代机制的多跳广播DIPS-MB，其主要步骤的流程如图2所示.

基于动态迭代机制的多跳广播DIPS-MB的主要步骤如下所示:

步骤1.转发节点广播RTB包，并设置重传定时器RT1;

步骤2.当候选节点收到RTB包后，根据自身与转发节点的距离来调节功率，并发送一个时隙的Black-burst;

步骤3.转发节点根据接收的Black-burst信号强度估算车流密度，并基于车流密度动态回复Black-burst;

步骤4.候选节点根据接收的Black-burst具体情况来确定并执行相对应的迭代分区方法;

步骤5.候选节点通过迭代分区判断自身是否位于最优路段，是则基于随机竞争窗口机制回复CTB包，否则退出竞争;

步骤6.转发节点接收CTB包，开始广播紧急消息，并设置重传定时器RT2;

步骤7.候选节点接收紧急消息，并成为下一跳广播的转发节点.

在以上过程中，动态迭代分区方法DIPS是影响紧急消息广播性能的关键因素，其主要包括步骤3中基于自适应功率的车流密度估计，以及步骤4中基于车流密度的动态迭代分区方法.

图2 DIPS-MB方法流程Fig.2 Procedure of DIPS-MB

3.3 动态迭代分区方法DIPS

3.3.1 车流密度估计

动态迭代分区方法DIPS的关键是根据车流密度选择迭代分区机制，因此首先估算出当前的车流密度.本节利用文献［19］的方法估算车流密度.其基本思想是根据接收功率的叠加强度计算通信范围内的车辆数量，从而估算车流密度.由于无线信号强度随着传播距离增大而逐渐衰减，邻居车辆可以根据自身与转发车辆的距离来调节发射功率，从而使得无线信号以Pth的强度到达转发车辆.如公式(1)所示，根据双径地面反射模型计算接收功率大小.

式中，Pr和Pt分别是消息接收和发射功率，Gt和Gr分别是发射端和接收端的天线增益，ht和hr分别是发射端和接收端的天线高度，d是接收端和发射端之间的距离.

为了使得转发节点处的接收功率为固定阈值Pth，发射功率的计算公式如公式(2)所示:

式中，Pth、Gt、Gr、ht和 hr均为常数，因此距离转发节点越远的车辆需要使用更大的发射功率.车流密度ρ的计算公式如公式(3)所示，其表示有效通信范围R内单位距离长度包含的车辆数量.

3.3.2 基于车流密度的DIPS

与现有基于Black-burst的方法相同，最优路段(即最远非空路段)是通过多次迭代分区获得的.如图3所示K进制分区的第一次分区结束后，通信范围R被划分为K等份，距离转发节点由远及近分别为路段 S1，1，S1，2，…，S1，K.其中 Sp，q表示第p次分区后由远及近的第q个路段.

图3 K进制第一次分区情况Fig.3 First partition by K-way mechanism

每一次竞争过程中，位于Sp，i(1≤i≤K－1)路段的车辆将在第i个时隙发送Black-burst，而位于Sp，K路段的车辆则一直保持监听状态.因此对于每一辆车而言，其在迭代分区过程中能根据自身的地理位置确定一个发送或者监听Black-burst的时间开销序列，记为 T1，T2，…，TIk.其中Tp表示第 p次分区的时间开销，IK表示K进制分区的迭代次数.

本文假设在迭代分区后，最佳路段中每条车道至多容纳一辆车.因此，迭代次数IK满足公式(4):

式中，Lv为车辆长度，Lg为车间安全间距.因此K进制分区的迭代次数IK取值如公式(5)所示:

此外为避免路段被划分过短，本文规定每辆车不得占用超过两个路段，因此迭代次数IK的取值还需满足公式(6):

若第i(1≤i≤KIK)个路段Si进行IK次迭代分区后成为最佳路段，则处于该路段的候选车辆在第j(1≤j≤IK)次分区的时间开销Ti，j计算公式如公式(7)所示:

其中，W={K，K2，…，KIK}.因此候选车辆在整个分区过程中的总时间开销如公式(8)所示:

根据文献［16］可知，路段Si成为最佳路段的概率P(Si)的计算公式如公式(9)所示:

其中μ表示单个路段中车辆的数量，因此K进制策略的理论分区时间开销如公式(10)所示:

根据公式(10)可知，K进制分区的时间开销与车流密度ρ有关，其关系如图4所示.

图4 K进制分区时间开销Fig.4 Time cost of K-way partition

根据图4可知，当车流密度小于ρ1(约等于60辆/千米)时，执行四进制分区效果最优;当车流密度大于ρ1时，执行八进制分区效果最优.本文采用基于Black-burst交互的方式为候选车辆统一分区策略.具体来讲，令车辆在某个tmini-slot时隙发送Black-burst的事件记为1，不发送记为0.当转发车辆估算完车辆密度后，利用1个tmini-slot时隙进行Black-burst交互，邻居车辆则根据监听到的Black-burst发送情况确定分区策略.即候选车辆监听到Black-burst，则采取四进制分区，否则采取八进制分区策略.因此，DIPS-MB方法能够在动态车流环境中采取最佳分区策略.

4 数学分析

本节理论分析DIPS-MB方法在V2V通信情况下广播紧急消息的平均一跳时延和平均传播速度.

4.1 平均一跳时延

根据图2可知，DIPS-MB方法的一跳时延主要包含RTB广播(步骤1)、分区机制决策(步骤2和3)、迭代分区(步骤4)、中继节点选择(步骤5)和数据传输(步骤6)五个部分.

当监听到信道空闲时，转发节点在等待mini-DIFS时间后向周围一跳邻居广播RTB包，该阶段的时间开销如公式(11)所示:

分区机制决策阶段包含一个mini-slot的密度估计和一个mini-slot的分区机制决策，该阶段时间开销如公式(12)所示:

在迭代分区阶段，转发车辆与候选车辆通过Black-burst交互选出最佳路段，该阶段时间开销如公式(13)所示:

在中继选择阶段，位于最佳路段的候选车辆利用大小为cw的竞争窗口随机选出唯一中继车辆，并回复CTB消息.由于在此阶段可能会产生CTB冲突，该阶段的时间开销如公式(14)所示:

在数据传输阶段，转发车辆在等待SIFS时隙后广播紧急消息，该阶段的时间开销如公式(15)所示:

结合公式(11)到(15)，可得DIPS-MB方法的平均一跳时延如公式(16)所示:

4.2 平均传播速度

假设最佳中继车辆位于Si路段，也就意味着其他的Sj(j＞i)路段内没有车辆，则最佳中继车辆与转发车辆的平均距离如公式(17)所示:

可得DIPS-MB方法的平均一跳距离如公式(18)所示:

其中，P(Si)表示第i个路段Si成为最佳路段的概率，取值见公式(9).因此，DIPS-MB方法的平均传播速度如公式(19)所示:

5 实验与分析

5.1 实验环境与参数

Veins(Vehicles in Network Simulation)［20］是一种开源的车辆网络仿真框架，提供了车辆移动和网络部分的双向交互功能.其在网络通信层面使用OMNeT++(Objective Modular Network Tested in C++)［21］进行仿真和控制，在移动层面使用 SUMO(Simulation of Urban MObility)［22］进行模拟.本文使用 OMNeT++4.6 和 SUMO 0.21.0，基于 Veins 3.0 构建城市交通环境下的仿真环境如图5所示，本文首先基于百度地图得到武汉科技大学黄家湖校区附近的真实道路网络拓扑.接着，利用SUMO构造了该拓扑的主干道，与仿真相关的主要参数如表1所示.

表1 主要仿真参数Table 1 Major simulation parameters

5.2 结果对比与分析

在本文中只考虑所涉及的场景中某一地方发生紧急消息广播事件.如图5所示，源节点A处发生交通事故，并开始向周围广播紧急消息.紧急消息通过多跳广播，在到达目的节点B 处后停止.本文所提方法 DIPS-MB 与 BPAB［15］、3P3B［16］和UMBP［17］三种基于Black-burst的方法进行比较.

首先比较几种方法在不同车流密度条件下的平均一跳距离，结果如图6所示.从图中可以看出，DIPS-MB在车流密度较大时具有更远的一跳距离.具体来讲，与其他方法相比较，平均一跳距离提高了大约2.5%.其主要原因是DIPS-MB方法通过多进制迭代分区机制充分划分并缩小了最佳候选节点的竞争区域，使得位于最远处的车辆在车流密度较大时能够在随机窗口竞争阶段有更大的概率胜出成为唯一的中继节点，从而提高了紧急消息广播的一跳距离.

图5 道路拓扑Fig.5 Road topology

图6 平均一跳距离Fig.6 Average one-hop distance

图7 平均一跳时延Fig.7 Average one-hop delay

接着比较几种方法在不同车流密度条件下的平均一跳时延和传播速度.影响这两种性能指标的主要因素在于位于最佳路段中的车辆在竞争唯一中继节点时容易产生CTB冲突，且在车流密度较大时产生冲突的概率性越高，从而导致过高的转发时延.缩小竞争区域是减少CTB冲突的一种有效途径，DIPS-MB在不同的车流密度下，采用了最恰当的多进制迭代分区机制，得以获得比其他方法更小的竞争区域，从而有效地减少了CTB冲突，为紧急消息的及时广播提供了保障.

从图7和图8中可以看出，DIPS-MB在车流密度较大时与性能较优的UMBP相比，其平均一跳时延大约比减少了18.5%，平均传播速度大约提高了25.8%.因此，DIPS-MB方法在动态车流环境下具有更小的一跳时延和更快的传播速度.

图8 平均传播速度Fig.8 Average propagation speed

6 结论

本文提出了一种基于Black-burst的动态迭代分区多跳广播方法DIPS-MB.与现有基于 Black-burst的方法相比，DIPS-MB能够在不同车流密度下动态选择最佳的迭代分区机制，充分地缩小了候选车辆的竞争区域，从而缩小寻找最佳候选车辆的时间，在动态车流环境下更好地满足了紧急消息广播的实时性和可靠性.

融合多种通信协议的异构车联网架构是未来发展的必然趋势，因此在下一步工作中，将研究城市环境下多通信协议协作的异构车联网紧急消息广播方法.