基于自适应信标交换的方向广播协议

吴学文，顾 欣

（河海大学 计算机与信息学院，江苏 南京211100）

0 引 言

VANET 通过车辆节点配备的传感器系统进行信息的采集、传输和交换，实现紧急情况预警、协同驾驶、分布式交通信息的收集与分发等交通安全类应用，以提高行车安全性和交通效率。其中，紧急情况预警对信息传输的实时性和可靠性要求极高。协同驾驶、分布式交通信息收集与分发则要求广泛性、高效性与安全性。舒适类应用中的信息传输往往对传输可靠性、带宽、延迟等要求较高。因此，VANET 的信息传输对服务质量QoS要求各异，如何针对VANET 的基本特征和不同应用设计高效的、可靠的广播协议成为目前VANET 的研究重点。本文旨在针对现有十字路口广播协议存在的不足，提出一种性能更优越的广播协议。

1 相关工作

现有的VANET 广播协议按照中继方式又可分为基于概率的广播协议、基于位置的广播协议、基于MAC 层的广播协议和基于邻居消息的广播协议。其中，多数协议是为高速公路等直线道路场景设计，只有少部分协议考虑十字路口处多路段的信息广播。

1.1 现有VANET广播协议分析

1.1.1 基于概率的广播协议

基于概率的广播协议中的节点接收到广播分组后，立即或等待一定时隙后以概率P 转发分组，P 为1时就退化为简单洪泛。文献 ［1］提出加权式p－坚持、时隙式1－坚持、时隙式p－坚持3种基于概率的广播协议。K.A.Hafeez等提出一种基于网络拓扑的p－坚持广播协议［2］（network topology p－persistence scheme，NTPP）：若接收节点为候选广播节点，则在延时等待后转发分组；否则在延时等待后以概率p转发分组。

1.1.2 基于位置的广播协议

基于位置的广播协议在传输范围内选择相对远的节点转发分组，可在较大程度上减少中继节点数目冗余。该类协议的中继节点选择策略主要有：距离阈值法、计数法、概率法、时间片法。前3种策略的共同特点是中继节点不唯一，因而不能最大程度减少中继节点的数目和分组冗余。基于位置的广播协议多为时间片法或其改进，完全采用分布式思想，选择的中继节点是确定且唯一的。目前，很多基于位置的广播协议被提出，时间片策略也被普遍采用，典型的基于位置的广播协议有EDB［3］、S1－PB、TRAB［4］、LDMB［5］等。

1.1.3 基于MAC层的广播协议

针对基于IEEE802.11的MAC 协议不支持可靠广播的问题，许多基于MAC 层的广播协议被提出，如Gokhan K等提出一种适用于城市道路场景的多跳广播［6］（urban multi－hop broadcast，UMB）协议，通过RTB／CTB 握手机制 （request to broadcast／clear to broadcast）选择最远节点作为广播中继节点，并通过ACK 分组确认提高可靠性。UMB的可靠性和资源利用率高，但基于握手机制的中继选择策略使得信道竞争与冲突问题较为突出，不适合高密度的VANET。文献 ［7］提出的基于跨层的多跳广播协议PMBP （position based multi－hop broadcast），基 于BRTS／BCTS握手机制选择中继节点，并采用IEEE 802.11e支持不同优先级分组的广播。

1.1.4 基于邻居消息的广播协议

基于邻居消息的广播协议中，节点根据来自邻居节点的周期性的Hello或Beacon消息维护和更新邻居列表，在得知网络拓扑的基础上选择最佳中继节点。这种协议的中继方式主要有：距离法、拓扑分层法、连通域集合法。其中连通域集合法是节点通过邻居列表信息计算自身是否处于连通区域集合 （connected dominating set，CDS）中，处于CDS内的节点相对处于CDS外的节点具有更短的延时等待时间，从而最先接入信道成为广播中继节点。典型的基于 邻 居 消 息 的 协 议 有 ERD［8］、StreetCAST［9］、DBAMAC［10］、DV－CAST［11］、AckPBSM［12］等。

1.2 考虑十字路口的广播协议分析

上述广播协议多为高速公路等直线路段场景设计，未考虑十字路口处广播传输的方向性，因而将其用于城市道路是不可取的。现有的考虑十字路口的广播协议主要有UMB、EDB、DP－IB［13］、StreetCAST、RB－FI、AckPBSM、ERD 等。对于十字路口转发方式，UMB、EDB、DP－IB、StreetCAST 均在十字路口安装转发器，该集中式方法实现简单、可靠性和信道利用率比较高，缺点是给每个路口配备转发器增加了成本。RB－FI、AckPBSM、ERD 则采用完全分布式策略，分别在十字路口的各路段上，并从中选择合适的中继节点。本文主要讨论分布式策略。

RB－FI通过计算转播节点速度矢量与转播节点到接收节点的位移矢量间夹角的正弦值，分别将转播节点后方和前方节点分为三类 （sinα＞0、sinα＝0、sinα＜0），表示处于不同路段上，采用基于位置的时间片法分别选择中继节点。RB－FI默认相同道路上的车辆节点处于同一条直线上，但在实际场景中往往存在偏差 （尤其是多车道场景），容易造成分类错误，从而影响协议性能。AckPBSM 基于连通域集合法，无需根据车辆节点的位置、速度等信息了解车辆是否处于十字路口。ERD 在十字路口处根据 “line－ofsight”原则选择各路段上最合适中继节点，但由于缺乏重播机制，容易造成稀疏路段上的广播中断。UV－CAST 结合类似传染转发策略提高广播可靠性，核心思想是：处于十字路口的中继节点在完成分组转播后，选择其传输范围边界处 的 节 点 成 为SCF （store－carry－forward）节 点；SCF发现有未收到该分组的节点进入其传输范围时就转播分组，旨在保证所有方向上的不同路段的节点都能收到广播分组。相对于以上几种选择各路段上最远节点的广播协议，UVCAST 能保证广播覆盖率，但额外的SCF 节点转播分组，造成分组冗余和碰撞。

2 基于自适应信标交换的方向广播协议DB－IA

基于邻居消息的广播协议根据包含位置、速度等信息的信标掌握网络拓扑，在此基础上选择最合适的节点作为中继节点，实现简单且冗余抑制率高。因此，本文采用基于邻居消息的中继策略，针对现有考虑十字路口的广播协议存在的不足，提出一种同时适用于高速公路和城市道路场景的基于自适应信标交换的方向广播协议 （directional broadcast considering intersection via adaptive beaconing，DB－IA）。DB－IA 采用自适应信标交换机制动态调整信标分组广播周期，减小分组冲突和网络开销，提高资源利用率。在可靠性方面，DB－IA 通过中继节点间单播ACK 分组进行广播分组确认，并结合双向传输和存储－转发策略缓解广播中断问题。为避免十字路口多中继节点同时转播分组造成的冲突，DB－IA 通过优化退避方式控制转播队列，使分组转播快速、有序地完成，提高广播的实时性。

2.1 中继节点选择策略

DB－IA 中的节点根据周期性的包含ID、路段、位置、速率等信息的信标分组完成邻居列表的建立或更新。信标分组和邻居列表的格式如图1所示。

图1 信标分组和邻居列表格式

各字段含义如下：ID：节点标识符；R＿ID：路段标识符；Loc：节点位置；Vel：节点速率；Vel－R：邻居节点相对当前节点的运动趋势 （靠近／远离）；Loc－R：邻居节点与当前节点的位置关系 （前方／后方）；Dis：邻居节点与当前节点的距离。

对于紧急告警信息，同向车道上紧随EMSN 的车辆处境最危险，应当优先被警告；对于交通疏导信息，同向车道上的节点进入拥堵区域的概率比较大，应当快速被告知。因此，DB－IA 优先选择相距最远的同向车辆节点转发分组，旨在满足交通安全需求的同时减少中继节个数。当同向车道存在网络空洞时则采用反向中继策略，即暂时选择反向车道上的节点作为下一中继节点，而后在条件允许的情况下返回同向中继策略。因此，所有车辆节点可分为同向中继节点、反向中继节点和非中继节点三类。

节点接收到广播分组后，判断自己是否为上层中继节点 （pre－relay node，PRN）选择的中继节点，若是则进行下一中继节点的选择。首先，根据邻居列表中感兴趣区域的邻居节点的路段标识符R＿ID判断场景：若R＿ID相同，说明为直路场景；若R＿ID不同，说明为十字路口场景，每个路段分别选择一个中继节点。同向中继节点的感兴趣区域为其后方，而反向中继节点的感兴趣区域为其前方。

直路或每个路段的中继选择策略基本相同，描述如下：若当前节点为同向中继节点，则选择后方邻居节点中距离最远且靠近的节点为同向中继节点，如无靠近的节点则选择距离最远且远离的节点为反向中继节点；若当前节点为反向中继节点，则选择前方邻居节点中最远且靠近的节点为同向中继节点，若无靠近的节点则选择距离最远且远离的节点为反向中继节点。

如图2 所示，假设节点A 为紧急消息源节点 （emergency message source node，EMSN），A 根 据 邻 居 节 点 的R－ID判断后方为直线道路场景，则选择后方最远且靠近的节点B为同向中继节点；B 判断其后方为十字路口场景，在路段2、3根据最远且靠近原则分别选择D 和G 为同向中继节点。对于路段1，因为无靠近的节点则根据双向中继原则选择最远且远离的节点C为反向中继节点。对于节点D，在判断后方为直线道路场景后发现后方传输范围内无靠近的节点，即发生同向传输空洞，所以选择节点E为反向中继节点。E选择其前方且靠近的节点为同向中继节点。告警信息分组按照以上规则被传输到远处路段上，直到分组过期。

2.2 自适应信标交换机制

信标交换主要实现邻居节点发现和位置等信息交互，是DB－IA进行中继节点选择的重要基础和依据，其广播方式和周期对DB－IA协议性能存在较大的影响。在节点密度相对低的场景下，较小频率的信标交换延长邻居发现时间，某一时刻使用的邻居节点信息并不是最实时的，影响协议的可靠性。在节点密度相对高的场景下，若保持较大频率的信标交

图2 DB－IA 中继节点选择

换，虽能获得较为实时的邻居信息，但过多占用了告警信息广播带宽，产生冲突的概率较大，降低协议的实时性。因此，为使DB－IA能适应不同节点密度场景，本文提出一种自适应信标交换机制来取代传统的固定周期的信标交换策略。

自适应信标交换机制主要依据车辆节点密度、距离、移动性等因素，动态调整信标交换周期I，涉及的主要参数包括：密度度量D，距离度量d、移动性度量M 等。I 的计算方法如下所示

其中，Di＝n，n表示邻居节点的总个数，Dmax是一个预设值，表示节点能够承受的最大邻居节点数，dij为节点i到邻居节点j的距离 （m），R 为车辆节点传输范围，vi和vj分别为节点i及其邻居节点的移动速率 （m／s）；w 为权重因子，可根据场景或应用的不同，调节各参数对I 计算的影响程度，此处w1＝w2＝0.25，w3＝0.5，I 的值始终处于区间 ［Imin，Imax］内，Imin和Imax分别为I 的下限和上限，其值由网络负载承受能力和可靠性要求来决定。考虑以下几种情形：①D 较大，表明局部节点密度较大；②d 较大，表明节点距离较远，节点靠近其邻居节点的传输范围边界，因而离开其传输范围的概率较大；③M 较大，即节点i的相对移动速度较快，可能快速从一邻居节点的传输范围移动到另一邻居节点的传输范围。根据式 （1）可知：情形①下，应在保证邻居发现精度的基础上适量减小I值，避免频繁的信标交换造成信息碰撞；情形②③，应增大I，来缓减稀疏网络或移动性的影响，保证邻居发现的实时性和精度。

2.3 可靠性保障

2.3.1 ACK 机制

由于DB－IA 在每个路段只选择一个中继节点，这些中继节点能否可靠地接收到告警分组至关重要，DB－IA 通过在相邻中继节点间的ACK 分组来保证广播的可靠性。每个中继节点在转播分组后开启重播定时器 （ReBroadcast timer，RBT），生成ACK 分组并准备发送至PRN；检查其邻居列表，若PRN 在其中，则单播ACK 分组给PRN；否则，广播该ACK 分组。接收ACK 广播分组的邻居节点，若发现目标节点在其邻居列表中，则竞争ACK 信使节点。竞争胜出的节点单播该ACK 分组给目标节点；否则，丢弃该ACK 分组，不作处理。若该中继节点在其RBT 溢出之前未收到所有来自下层中继节点的ACK 分组，则进行告警分组重播。

ACK 信使节点竞争过程如下：发送ACK 报文的最大等待时间TAck－max被分为NAck个等长时间片，每个时间片的长度LAck为

每个竞争ACK 信使节点的中间节点首先从 ［0，NAck－1－1］中随机选择一个时间片idx，再从 ［0.0，LAck］中随机选择一个片内偏移offset，则最终的延时等待时间TAck如下所示

经过两次随机选择，各中间节点的等待时间被较大程度地离散化，有效降低了多个中间节点同时转发ACK 报文的概率。

2.3.2 网络空洞修复机制

当因网络空洞造成广播中断时，中继节点重复启动重播定时器，不断周期性的重播分组，直到有车辆进入其信号覆盖范围内或者消息过期。图3展现了网络空洞的修复过程：时刻1，中继节点A需要转播分组，而其传输范围内无车辆节点，即产生网络空洞；时刻2，节点B进入A 的信号覆盖范围内，成为反向中继节点，而其传输范围内也无其它节点，因此继续周期性重播过程；时刻3，节点C进入B的信号覆盖范围，成为同向广播节点，网络空洞修复成功；若分组未过期，则继续进行分组的定向广播。网络空洞修复时间相对较长，对信息传输时延的影响较大，却又不可避免。

图3 网络空洞修复过程

2.4 十字路口多中继节点快速转播机制

在十字路口场景中，各路段的中继节点接收到广播分组的时刻比较靠近，并可能同时尝试转播分组竞争信道。为减少随机退避策略带来的冲突和碰撞，DB－IA 通过合理设置退避时间来控制分组转播队列，使得十字路口的广播中继快速、有序完成，减少时延。

如图4所示，节点B和C侦听到节点A 的转播，而后节点B开始延时退避和转播，后续节点C 重复这个过程。DB－IA 加入网络分配矢量NAV，其值设置足够大，以保证列表上的中继节点能不受干扰地完成各路段上的分组转播。

图4 十字路口多中继节点转播机制

3 协议仿真与性能评估

本文以NS－2作为网络仿真平台，利用VanetMobiSim交通流仿真器限制车辆运动的区域及轨迹，以广播覆盖率（REachability，RE）、广 播 冗 余 抑 制 率 （saved ReBroadcast，SRB）、分组碰撞次数 （number of collision，NoC）、端到端时延 （latency）为网络性能评估指标，分别对RBFI、ERD、UV－CAST 和本文提出的DB－IA 进行仿真实验和性能比较。

以上评估指标定义如式 （8）～式 （10）所示，其中NRNt和NRNr分别是源节点后方车辆节点数和源节点后方接收到广播分组的车辆节点数，NBNf是信道竞争后成为中继节点的车辆节点数，TSr是源节点后方某节点首次接收到广播分组的时间戳，TSs是源节点产生告警信息的时间戳

3.1 实验环境与场景

本文利用VanetMobiSim 为车辆自组网设计了车辆移动的场景，设置的参数包括仿真区域，仿真区域被划分块数，其中运动的车辆数，车辆移动的速度范围，以及包含红绿灯的岔路口个数。具体参数设置见表1。

表1 VanetMobiSim 的仿真参数设置

仿真实验在Otcl仿真配置脚本中设置相关实验参数，见表2。其中，RB－FI处于 ［0，RAD＿TMAX］区间上，RAD＿TMAX 设置为100ms。Street－CAST 和ERD 的信标交换周期设置为0.25 ms，而DB－IA 则根据密度、速度等参 数 计 算 信 标 交 换 周 期。Street－CAST、RB－FI、ERD、UV－CAST 的MAC 协 议 均 采 用IEEE802.11DCF，而DBIA 则采用提出的改进思想。

3.2 结果与分析

本文在不同告警信息产生时刻，对6种交通场景进行仿真，最后统计获得其平均值作为实验结果，如图5～图8所示。

（1）4种协议的RE随车辆节点密度呈递增趋势，且在高密度场景下都能达到100%。ERD 因缺乏分组确认机制来修复稀疏路段的广播中断，RE 性能较差，原因在于：UV－CAST 协议指定SCF 节点缓存分组，并转发给进入其传输范围内且未收到该分组的邻居节点，以确保所有路段的车辆节点都能接收到广播分组；DB－IA 通过在中继节点间单播ACK 分组进行广播分组确认；RB－FI虽采用存储－转发策略，但节点分类错误使得实际情况中某些路段上不存中继节点，从而影响RE性能。

表2 NS－2仿真实验参数设置

图5 不同车辆节点密度场景下的RE

图6 不同车辆密度场景下的SRB

图7 不同车辆密度场景下的NoC

图8 不同车辆密度场景下的平均Latency

（2）DB－IA 和ERD 的冗余抑制效果接近且相对较好，RB－FI次 之，UV－CAST 相 对 最 差。ERD 和DB－IA 都 是 在得知网络拓扑的基础上，直接在每个路段上选择最远且唯一的中继节点，从而较大程度上减少了中继节点的数目和广播跳数。RB－FI由于分类错误问题，某一路段可能存在两个或以上节点转播分组，广播冗余抑制的效果不佳。在稀疏场景中，UV－CAST 中每个十字路口选择的SCF 节点增加了转播节点的个数，所以SRB性能相对RB－FI低。随着节点密度的增加，UV－CAST 的SCF 节点转播分组需求降低，而RB－FI的分类错误程度加剧，两中协议的SRB性能的差距逐渐减小。

（3）4种协议的NoC都是车辆节点密度的递增函数。当节点密度增大时，ERD的中继节点数目不受影响，但信标分组数量激增；ERD的分组碰撞比较严重。RB－FI中，节点分类错误增加了中继节点的个数，而节点密度的增加使得距离相近的邻居节点竞争信道，导致分组碰撞加剧。DB－IA 的NoC最小，原因在于：与ERD 相似，中继节点数目基本不受节点密度变化的影响；自适应信标交换机制在节点密度增大时适度减少分组交换频率，从而减少信标分组的数量；针对十字路口各路段上的中继节点同时转播分组可能造成的碰撞，DB－IA通过设置递增的退避时间来控制转播顺序，使得转播快速、有序完成，很大程度上减少分组碰撞的概率。

（4）平均Latency曲线呈现两边高、中间低的形态，表明节点密度过低或过高都会降低广播的实时性。无论在稀疏场景或稠密场景中，DB－IA 的实时性最好。

当ρ＞10时，DB－IA 的中继节点个数几乎不受密度增加的影响；改进的退避方式避免十字路口多中继节点的分组碰撞，有效减少信道接入时延；自适应信标交换机制减小信标的广播周期，减少信标分组与广播分组的碰撞。ERD 中激增的信标分组，UV－CAST 中多中继节点的信道竞争，RB－FI中节点路段分类错误，使得它们的平均Latency比DB－IA 大。

当ρ≤10时，ERD 由于没有确认和重播机制修复网络空洞，广播中断带来的时延较大。DB－IA 结合存储－转发和双向传输策解决网络空洞问题，修复时间相对短。RB－FI和UV－CAST 分别采用存储－转发和SCF节点转发策略修复网络空洞，但耗时相对DB－IA 长，平均Latency稍大。

当ρ处于 （5，10］区间时，DB－IA 和ERD 的平均Latency小于RB－FI和UV－CAST，原因在于：DB－IA 和ERD在每个路段上选择唯一的中继节点，平均Latency随着中继节点数目较少而减少；RB－FI和UV－CAST 的广播冗余效果不如前两种协议，平均Latency有所增加。

4 结束语

本文在研究现有VANET 广播协议的基础上，针对十字路口广播协议存在的不足，提出了一种同时适用于高速公路和城市道路两种场景的方向广播协议DB－IA。根据周期性的信标交换获得网络拓扑信息，在各路段上选择最远的节点作为中继节点，减少了广播跳数。采用自适应信标交换机制取代传统的固定周期的信标交换，减少了分组冲突和网络开销。通过ACK 分组确认机制，提高广播可靠性。通过给每个中继节点设置递增的退避时间，提高广播实时性和可靠性。仿真结果表明，DB－IA 具有相对优越的性能，适合交通安全类信息传输。

［1］Wistipongphan N，Tonguz OK，Parikh JS，et al.Broadcast storm mitigation techniques in vehicular ad hoc networks［J］.Wireless Communications.IEEE，2007，14 （6）：84－94.

［2］Hafeez KA，Zhao Lian，Liao Zaiyi，et al.A new broadcast protocol for vehicular ad hoc networks safety applications［C］／／Global Telecommunications Conference.IEEE，2010：1－5.

［3］Li Da，Huang Hongyu，Li Xu，et al.A distance－based directional broadcast protocol for urban vehicular ad hoc network ［C］／／Proc of the International Conference on Wireless Communications，Networking and Mobile Computing，2007：1520－1523.

［4］Wu Xuewen，Yan Wei，Song Shiming，et al.A transmission range adaptive broadcast algorithm for vehicular ad hoc networks［C］／／Proc of the Second International Conference on Networks Security Wireless Communication and Trusted Computing，2010：28－32.

［5］Yang Qiong，Shen Lianfeng.A multi－hop broadcast scheme for propagation of emergency messages in VANET ［C］／／Proc of 12th IEEE International Conference on Communication Technology，2010：1072－1075.

［6］Korkmaz G，Ekici E，Ozguner F.Black－burst－based multihop broadcast protocols for vehicular networks［J］.IEEE Transactions on Vehicular Technology，2007，56 （5）：3159－3167.

［7］BI Yuanguo，ZHAO Hai，SHEN Xuemin.A directional broadcast protocol for emergency message exchange in inter－vehicle communications［C］／／IEEE International Conference on Communications，2009：1－5.

［8］Tung Lung－Chih，Gerla M.An efficient road－based directional broadcast protocol for urban VANETs ［C］／／Proc of IEEE Vehicular Networking Conference，2010：9－16.

［9］Yi Chih－Wei，Chuang Yi－Ta，Yeh Hou－Heng，et al.Streetcast：An urban broadcast protocol for vehicular ad hoc networks［C］／／Proc of the IEEE 71st Vehicular Technology Conference，2010：1－5.

［10］Bononi L，Di Felice M.A cross layered MAC and clustering scheme for efficient broadcast in VANETs［C］／／Proc of the IEEE International Conference of Mobile Ad Hoc and Sensor Systems，2007：7－12.

［11］Tonguz O，Wisitpongphan N，Bai F，et al.Broadcasting in VANET ［J］.Mobile Networking for Vehicular Environments.IEEE，2007：7－12.

［12］Ros FJ，Ruiz PM，Stojemnovic I.Reliable and efficient broadcasting in vehicular ad hoc networks［C］／／Proc of Vehicular Technology Conference.IEEE，2009：1－5.

［13］Zhao Jing，Zhang Yang，Cao Guohong.Data pouring and buffering on the road：A new data dissemination paradigm for vehicular ad hoc networks［J］.IEEE Transactions of Vehicular Technology，2007，56 （6）：3266－3277.