On Fast Broadcasting of Emergency Messages in Urban VANET

为了研究车辆节点之间通信链路的质量，本文采用Nakagami提出的Nakagami-m模型^[4]来模拟无线信号在车联网环境下的衰落特点. Nakagami-m被学者们认为非常符合VANET的复杂环境，尤其符合车辆的高速运动场景^[5]. Nakagami信道的接收信号强度x的概率密度函数(Probability Density Function，PDF)如式(1)^[6]：

式(1)中，Γ(m)是伽马函数，m是衰减因子，Ω是平均信号接收功率，它们都与通信双方的距离d_ij有关.

多跳广播中中继转发节点的选择是关键，按照中继策略的不同，多跳广播算法主要分为基于发送端指定中继的策略(Sender-based)和基于接收端分布式竞争转发的策略(Receiver-based). Sender-based策略中下一跳的中继选择是由广播发起者指定，只有被指定的接收节点参与消息转发，而其他节点则不参与转发.在Sender-based策略中指定的中继可能由于信道衰减或干扰丢失分组暂停多跳广播进程，从而产生额外的时延或不必要的重发.为改进Sender-based策略的性能，学者们提出了不同的优化方案，如自适应的机会广播协议^[6]和基于树状结构的广播协议^[7].在自适应的机会广播协议中候选转发中继的优先级顺序被发送端以方向和距离为度量依据进行了预先分配，并且为保障可靠性该协议还引入了重传机制，但其忽略了网络拓扑的动态变化特性，因此在通信过程中引入了额外的等待时延.在基于树状结构的广播协议中发送端从事先维护的分布式树拓扑结构选择中继节点转发报文，该路由协议对网络拓扑的动态变化适应性好，但维护树形结构要付出代价.此类协议不适合VANET中快速变化的拓扑结构特点，因此，Sender-based策略在很大程度上受限于应用场景，在VANET中不适合广泛应用.

Receiver-based策略是由正确接收数据包的车辆节点根据特定规则进行分布式竞争转发.通常，接收节点根据与上一跳节点的距离设置具有不同等待延迟的定时器，以实现分布式转发.距离越大，等待延迟越小. Receiver-based策略能很好地适应拓扑的动态变化，使得广播连续性得到保障.然而，Receiver-based策略是否能成功通信取决于许多因素，例如发送端和接收端之间的相对距离^[8-9]、由历史接收分组估计的链路质量^[10]，是否位于连接区域内^[11]、节点在归属簇中的标识^[12]等.通常，协议中通过控制网络冗余来提高有效性，但这会引入额外的等待时延，不利于安全消息的快速传播.因此，Receiver-based策略在传输实时性方面需要进一步优化.

本文综合分析了Sender-based和Receiver-based两类中继策略的优缺点，提出了一种结合方案：在数据转发时，发送节点根据最小期望剩余时延中继选择模型指定最佳中继，被指定的最佳中继收到报文后立即转发，降低时延，确保了广播的时效性，而那些没有被指定的中继仍然按照分布式竞争方式协作转发以确保广播的连续性.

道路的属性是广播中继优化选择的基础，也是多跳广播实现的关键，直接影响广播性能的路由属性，分为全局静态路由属性和局部动态路由属性^[13].全局静态属性是指报文从生成到广播到目标区域的方向和覆盖范围.由于只有位于安全消息的发生位置后并驶向该位置的车辆才对此消息感兴趣，所以不在安全消息广播方向上的车辆节点在接收到广播消息之后不参与转发.全局静态属性用于过滤中继节点并在全局上起到引导作用.局部动态属性是指车辆在一跳范围内邻居节点的动态信息，包括邻居的数量、分布、移动状态和现有的网络负载，主要包括车辆拓扑结构的动态变化和相邻车辆间的通信链路质量.它决定了候选中继节点接收报文的准确率.本文通过研究通信方向上节点一跳范围的动态链路质量用于中继的选择，逐跳转发数据.

在分析道路属性的基础上，结合Sender-based和Receiver-based中继策略的优点，提出了一种考虑信号衰减、信道竞争、排队时延、广播干扰和车辆高移动性的最小期望剩余时延中继选择算法，设计了基于该算法的路由协议BP-MEDF.

图 1显示了BP-MEDF协议工作的详细流程.

由图 1可知，BP-MEDF协议有两种工作模式：源端指定中继模式(Sender Specifying Forwarder，SSF)和接收端协助转发模式(Receiver Cooperating Forwarding，RCF). SSF模式下发送节点基于最小期望剩余时延中继选择模型指定最优中继，RCF模式下接收节点基于指定的优先级和距离进行分布式协作转发.如果发送节点在最大等待时延结束后仍然没有收到确认帧(ACK)或转发副本，这就表明所有候选节点都转发失败，那么协议开启重传机制，确保安全消息连续传输.对应两种模式，相应地，接收节点也有两类：一类是由发送端指定的最佳中继V_EFN，另一类是协助转发中继V_HFN.发送端指定最佳中继的等待时延用式(2)表示，其他车辆收到转发确认帧或副本后，结束等待进程.

协助转发中继的时延用式(3)表示：

式(3)中d_k为协助转发节点V_HFN^k与上一跳转发节点间的距离.由公式(3)可知，在等待V_EFN节点转发时间结束后，如果V_HFN仍然没有收到广播副本或ACK，那么它们就按照配置的等待时延先后转发.需要特别强调的是协议中将通信距离大于R的协助转发节点的等待时延也设置为零.

如何选择期望转发节点(Expected Forwarding Node，EFN)是广播协议设计的关键.如果较远的节点被选做EFN，到达潜在危险区域(Potential Dangerous Area，PDA)的广播跳数和传输时间将变小.然而由于较远端的链路质量差，容易受到干扰丢包导致传输中断，使得主动选择转发节点失去意义.相反，如果选择较近的节点，消息转发可靠，但向前跳数增加，从而浪费了有限的带宽.因此，广播协议的设计要平衡可靠性和有效性.综合考虑道路局部的动态特性和全局的静态特性，我们为EFN的选择提出了一种新的参数——期望剩余时延(Excepted Remain Delay，ERD).

用D_F^j表示邻居车辆V_j被发送端V_i选作其EFN时，在广播进程中到达PDA终点的期望剩余时延.在表示D_F^j时本文考虑了网络中信道竞争、传输时延、信号衰减、广播干扰、链路可用性等因素.

1) 信道竞争

在链路L_ij上的竞争信道的成功率P_ij^c和报文在无线信道上的平均服务时延D_ij^c用式(4)表示^[11]：

式(4)中，p_b是车辆V_i信道忙的概率，Q_i是报文服务时间稳态概率的概率生成函数.

2) 传输时延

网络中已有的数据可以通过车辆内部传输时延D_q来估计，如式(5)所示：

式(5)中l_p是数据报文p的长度，而u_i是通过Q_i计算获得的服务速率.

因此发送端V_i和邻居V_j的链路平均传输时延D_ij^o是D^q和D^c的和，表示为D_ij^o=D^q(i)+D_ij^c.

3) 信号衰减

在Nakagami模型中，与发送节点V_i相距d_ij的邻居V_j能成功接收并解析出报文的概率P_ij^f是车辆相对距离的函数，用式(6)表示：

式(6)中F_dij是按公式(1)计算的接收信号的累积分布函数.

4) 广播干扰

在接受报文的过程中，与发送节点V_i距离是d_ij的邻居V_j不受隐藏终端影响的P_fh并且不被其他广播干扰的概率P_ij^if用式(7)表示：

式(7)中λ是报文到达率，ρ是道路中的车辆密度，n_s(p)是发送报文p需要的时隙总和，其值是报文大小除以传输速率和单位时隙，$\overline {{N_t}} $是在消息传输时间内开始传输数据的节点的平均数.

5) 链路可用性

车辆V_i和V_j间链路保持连通的概率P_ij^a可以通过假设相对速度V_ij服从正态分布的车辆运动模型表示^[14]，用式(8)描述：

式(8)中概率P由V_ij的PDF计算出来，d_ij是车辆V_i和V_j间的相对距离，R是在Nakagami模型中的通信范围，本文中将其设置为接受概率超过80%的值.

综上所述，车辆V_i的邻居节点V_j能成功接收到其广播报文的概率可用式(9)预估：

式(9)的物理意义是：只有发送端V_i成功地通过竞争获得信道使用权，V_i和邻居V_j之间的链路是稳定的，它们之间的信号足够强，不受其他广播干扰，在传输过程中信号强度也没有衰减到正确解析门限以下，这样接受端V_j才可以正确接收该广播报文.

我们设定如果发送端V_i选择了邻居V_j作为EFN，那么V_j会在收到数据报文后立即转发.由于无线信道的不稳定性，V_j可能没有收到报文，那么其他非期望中继利用Slotted-1协议进行分布式方式等待转发^[6]，其转发时延用式(10)表示：

式(10)中τ是一跳的平均时延，N_s是一跳广播范围内车辆的数目.

对于V_i的任意邻居V_k(V_k∈N_i)成功接收报文的概率P_ik和时延D_ik可分别由式(11)和式(12)表示：

式(12)中D_ik^w是由公式(10)确定的V_k的等待时延.

若V_i是EFN，但V_k是实际的转发者，则V_j沿着广播的方向到达PDA终点的ERD可预估为式(13)：

如果L_ik被选中作为到达PDA终点的传输链路，则式(13)中E(Hop_F(L_ik))表示平均跳数，可以通过节点V_i到PDA终点的距离D_iEnd除以距离d_ik获得，即E(Hop_F(L_ik))=D_iEnd/d_ik.

在式(13)中，前两项的乘积是表示单跳平均传输时延，它是基于源节点局部动态信息的估计，第3项是基于全局静态信息的估计，至此，协议在选择最佳时综合考虑了道路的全局静态和局部动态路由属性.

由于链路不稳定，发送端V_i的所有邻居都有可能成为实际的中继节点，因此，在其选择邻居V_j作为EFN时的预估ERD是所有可能转发数据报文的邻居ERD的累加，可用式(14)表示：

综上所述，最小期望剩余时延链路模型通过发送端与中继端的ERD来建立.

基于ERD度量，发送端计算所有邻居的ERD，并选择一辆具有最小ERD的车辆作为EFN，设置城市VANET场景(图 2).

在一个广播进程中，发送端V_i计算所有邻居的ERD，如图 2中的V_j，V_k和V_m，其中V_j的ERD可用式(15)表示：

同样地，计算出E(D_F^k)和E(D_F^m)，选择具有最小ERD的节点并在广播前标记在数据报文的头部，在图 2中V_k是EFN.

开启分布式协作转发进程的原因有两个：一是被指定的EFN因为不稳定的无线链路丢失报文；另一个是其他等待的邻居没有收到来自转发节点的ACK.在拥挤的城市交通中，一个数据报文由许多相邻的节点多次转发，从而导致广播风暴^[8].为减少广播冗余，本文提出了一种重复检测机制(Duplicate Detecting Process，DDP).一旦检测到重复次数超过给定的阈值，转发过程将被取消，该阈值是在邻居表中根据车辆密度动态估算出来的.

为验证BP-MEDF协议的性能，我们使用网络模拟软件NS 2.35.经典的基于接收端的Slotted-1协议用来与之进行比较分析.此外，为比较分析BP-MEDF转发优化的性能，我们设计了两个方案：①算法A命名最近优化(NEAREST)，该算法选择通信范围内最近的邻居作为EFN，是一种基于发送端的协议，没有协作转发；②算法B命名为最远优化(FARTHEST)，该算法选择最远的邻居作为EFN，与BP-MEDF类似，是一种具有混合机制的协议.

在模拟场景中我们设置1条长度为2 km的道路.源节点和目的节点各自位于道路两端.在道路上有20~100辆车，组成道路连接拓扑.车辆的初始位置是随机分布的，速度范围为30~60 km/h.我们用含有表示车辆移动性能的智能驾驶员模型的软件SUMO生成具有不同初始化值的场景，每个场景模拟10次，并用95%的置信区间测量平均值. 表 1列出了其他关键参数.

在仿真中，我们评估比较分析以下指标：

1) 报文投递率(Packet delivery ratio，PDR)，该参数表示广播路由的可靠性，其值是目标节点接收到的报文数与源节点发送的报文数的比值；

2) 报文覆盖率(Packet coverage，Coverage)，是网络中消息所覆盖的车辆与总车辆数的比值；

3) 广播跳数(Broadcast hops，BH)，它是广播从头到尾所经历的跳数，是广播算法对资源使用情况的反映；

4) 端到端时延(End-to-end delay，E2ED)，该参数是报文从产生到被目标节点接收所经历的时延，其值反映了广播算法的时效性；

5) 网络冗余(Redundancy)，该参数反映了广播算法产生的网络开销，用转发报文数除以目标节点接收的报文数来度量；

6) 传输效率(Dissemination efficiency，DE)，是平均一次广播所获得的地理覆盖前进度，是广播资源利用率的反映.

仿真结果如图 3至图 8.

从图 3和图 4中可以看出，随着车流密度(以每2 km计)增加，所有广播路由的报文投递率和覆盖率都呈现递增态势，这是由于车辆增多后道路的连通性会随之变好，在广播过程中有更多的节点参与到转发报文过程中. NEAREST协议的报文投递率和覆盖率最低，这是协议本身选择通信范围内最近的节点作为中继的必然结果. BP-MEDF投递率和覆盖率高于FARTHEST，这是因为发送端指定中继时，FARTHEST仅仅选择最远的邻居，但BP-MEDF综合考虑了信道的衰落、车辆的移动以及干扰等因素，通过度量节点RED选择的中继节点比最远邻居具有更优的链路质量，从而保证了更高的广播可靠性. Slotted-1的报文投递率和覆盖率比BP-MEDF高，这是因为Slotted-1是完全基于接收端的竞争转发策略，因此在广播方向上至少有1个节点会收到广播信息进行转发，而且静态等待时延的设置使得接收节点避免了转发误判；另外在分布式竞争转发时通过划分时隙数来区分优先级，减少了节点间的碰撞和竞争，保证了多跳转发的连续性.因此，Slotted-1的可靠性在几类路由算法中更优.

从图 5中可以看出，NEAREST因跳数增加导致其端到端时延随着车流密度(以每2 km计)增加而增加，而其他3类算法的端到端时延随着车流密度的增加呈递减态势，其原因是更多的候选节点参与转发过程使得道路拓扑连通编号，从而减少了额外的等待时延.由于发送端指定的中继策略没有额外的等待时延，当指定中继收到报文后立即转发，而接收端分布式竞争的中继策略在等待时延超时后才能转发，因此NEAREST，FARTHEST和BP-MEDF等Sender-based策略的端到端时延要明显优于基于Receiver-based策略的Slotted-1的端到端时延.另外，在NEAREST，FARTHEST和BP-MEDF中的BP-MEDF选择预估端到端时延最低的节点为中继节点，因此其端到端时延在几类广播算法中更优.

从图 6中可以看出，随着车流密度的增加，车间平均距离减小，因NEAREST总是选择最近的邻居转发报文，因此广播跳数增加了；而FARTHEST，BP-MEDF和Slotted-1的广播跳数呈递减态势，这是因为车间平均距离减小导致平均单跳可覆盖更远的车辆节点.而BP-MEDP广播跳数要高于Slotted-1，这是由于BP-MEDP考虑了链路质量因素，在实际转发过程中每跳选择的最佳中继并不是距离上一跳发送节点最远的车辆节点，而Slotted-1总是选择最远的车辆节点作为其转发中继.虽然FARTHEST也是选择最远节点转发，但是由于车辆的运动和发包间隔导致其邻居列表并非准确且实时，因此发送端选择的最远邻居并非距离上一跳节点最远的，因此其广播跳数略高于Slotted-1.

从图 7中可以看出，随着车流密度(以每2 km计)的增加，由于NEAREST每次都是选择最近邻居转发，这样便增加了转发跳数从而导致冗余量呈持续递增态势；而FARTHEST，BP-MEDF和Slotted-1的冗余量呈先减后增态势，这是因为随着车流密度的增加，网络的连通性逐渐变好，更多的车辆节点参与转发增加了报文的投递，网络冗余数逐渐变少；而车流密度每2 km大于40车时，车辆间的广播碰撞也随之加剧，PDR增长变缓，网络冗余则呈现递增趋势，车流越密集越容易出现局部广播风暴问题.车流密度较低时，基于动态预测的BP-MEDF由于车辆高速运动会存在一定的误差，导致发送端指定中继节点的转发失败而转为协作转发模式，如此会使得参与转发的节点数相应增加，且其PDR比具有静态等待机制的Slotted-1还低，所以网络冗余量更高.由此可见BP-MEDF在拓扑变化快的低密度场景下依赖于精确的邻居信息.

从图 8中可以看出，随着车流密度(以每2 km计)的增加，车间平均距离减小，由于NEAREST每次都是选择最近邻居转发，导致其转发效率呈递减态势；而FARTHEST，BP-MEDF和Slotted-1则随着车里密度的增加其转发效率呈递增态势，其中BP-MEDF相比于其他几类典型的广播协议，具有更高的广播效率.这是因为BP-MEDF结合了基于发送端指定中继策略快速分发报文和基于接收端分布式转发策略可靠投递的优点，以更低的端到端时延和相对较高的广播跳数即可覆盖整个PDA区域，从而使广播效率明显增加，因此该协议对有限的信道资源利用率更高.

安全消息多跳广播的研究，中继转发节点的选择是关键，既要能保证安全消息广播的可靠性，还要尽可能地降低广播时延，满足安全消息广播的要求.本文在前人研究的基础上，通过分析城市车联网的拓扑结构变化的特点，在保证广播可靠性的前提下，研究了基于全局广播时延优化的中继选择算法，设计了基于该算法的路由协议，通过软件仿真表明，设计的广播协议相比于传统的协议，在满足广播可靠性的条件下，优化了广播时延.下一步研究的方向是跨物理层、MAC层和应用层优化协议，从而进一步提高协议对车流密度和拓扑变化的适应性.