0 引言

    随着自组织无线通信和车辆技术的快速发展，在不久的将来，交通信息方向将发生重大转变。未来，将采用分布式的移动探测点(Probes)收集和分布实时的交通信息，不再引用嵌入基于基础系统中的固定传感节点。车辆的分布式网络，即车联网VANETs(Vehicular ad hoc networks)^[1-2]成为无基础设施、自组织的交通信息系统。在VANET中，每个车辆就是一个移动传感节点，承担收集、分发交通信息的角色。

    分发交通信息是VANETs中最根本的问题。相比于Internet内的单播数据，交通信息通常具有定向广播(Broadcast-oriented)特性。换而言之，交通信息是公共利益(Public interest)，受益的是一群车辆，而不是某个体车辆。因此，与单播协议相比，广播方案更适合于VANETs。广播方案的主要优势在于车辆不需要目的地址，而单播协议需要准确的目的地址，这就避免了路由发现、地址解析以及拓扑管理等复杂环节^[3-4]。 为此，本文着重分析VANETs的广播方案。目前，研究人员已提出许多广播方案，这些方案可分为单跳广播和多跳广播。

    在多路广播方案中，通过网络泛洪方式传输数据包。通常，当源车辆广播了信息数据包后，位于源车辆邻近区域的车辆就变成下一跳转发车辆(节点)，并扮演着通过重播转发数据包的任务。类似地，后续的车辆继续转发数据包。通过这种方式，能够将源节点的数据包传输至远距离的车辆。

    目前，研究人员已提出众多的基于多跳的广播协议，如图1所示。本文针对这些多跳广播协议进行分析，解析它们的特点。

1 多跳广播协议

    多跳广播协议是通过泛洪方式传递数据包。然而，在VANETs使用纯(Pure)泛洪方案是不足够的，原因有两点：可扩展性和数据包碰撞。随着网络密度的增加，导致相同的数据包在网络内反复重传，这将引起信道带宽的浪费，这就说明纯泛洪方案不适应于密集网络，不具有可扩展性。此外，在密集网络，由于在同一个区域大量数据包同时广播，不可避免会引起数据包碰撞，即广播风暴问题^[5]。为此，一个优质的多跳广播协议必须要解决这两个问题。

    目前，解决扩展性和碰撞两个问题的常用方法就是降低冗余重传数据包的数量。换而言之，只选择部分车辆重传数据包。依据现在多跳广播协议特性，可分为基于时延、基于概率和基于网络编码的多跳广播方案。

1.1 基于时延多跳广播

    所谓基于时延多跳广播就是每个接收了数据包的车辆在转发数据包之前，设定不同的延时等待，只有延时完毕，再转发数据包，具有最短延时等待的车辆具有重播数据包的最高优先权，此外，为了避免冗余，一旦监听到其他车辆已重播了数据包，车辆放弃等待。通常，延时时间是关于车辆与传输数据包的源车辆间的距离函数，一般距离越远，延时时间越短，成为下一跳重播节点的几率越大。接下来，分析几种典型的基于时延多跳广播方案的特性。

1.1.1 城市多跳广播UMB方案^[6]

    UMB(Urban Multi-Broadcast)方案目的在于解决广播风暴、节点隐藏以及多跳广播中的可靠性问题。UMB方案首先将源节点传输范围内的道路划分几个区域(Segments)，位于最远Segments内的车辆具有优先转发数据包的权力。此外，UMB方案引用定向-广播(directional broadcast)和十字路口广播(Intersection broadcast)两种模式。

    在定向-广播(directional broadcast)模式中，当车辆i需要发送数据包时，i首先传输请求广播控制包RTB(Request -to-Broadcast)，其包含了自己的位置和数据包传输方向。位于车辆i传输范围内的车辆一旦收到RTB，它们就开始传输被称为Black-burst的干扰信号(Jamming Signal)。Black-burst的时长L是关于车辆i与接收RTB的车辆间的距离d的函数，如式(1)所示。

    其中R表示车辆的传输范围、S表示时隙的时长。从式(1)可知 ，距离d越远，时长L越长。

    车辆(假定车辆j)传输了Black-burst后，车辆j继续监听信道。如果发现信道忙，则表明有其他车辆正在传输Black-burst。在这种情况下，车辆j将放弃转发数据包的权力。转发数据包的任务由其他车辆完成。反之，若信道是空闲的，车辆j向车辆i回复被称为消除广播的数据包CTB(Clear-to-Broadcast)。成功传输了CTB的车辆被选为转发数据包的下一跳车辆。

    一旦车辆i接收到CTB，车辆i就开始传输DATA数据包。当车辆j收到DATA数据包后，车辆j向车辆i回复确认数据包ACK。如果在规定时间内，车辆i未能收到ACK控制包，那么整个过程重新开始。

    然而，UMB方案并非是免碰撞的协议。当一个segment内有多个车辆时，它们可能会同时传输CTB，这就会引用碰撞。

1.1.2 智能广播SB^[7]

    由上述分析可知，UMB方案中下一跳的转发车辆需要等待很长的时间才能转发数据包。为此，文献[18]提出智能广播SB(Smart Broadcast)方案，通过为下一跳转发车辆设定短的等待时间解决这个问题。

    SB方案的数据包转发过程如下所示。当车辆(仍假定车辆i)需要发送数据包，首先车辆i传输RTB，其包含位置、传输方向和竞争窗口尺寸(Contention window size)等信息。位于车辆i传输范围内的车辆将接收到RTB，它们从RTB提取车辆i的位置信息，并决定自己的“sector”。最后，它们再依据自己所属的sector，选择竞争时延。

    依据文献[7]，UMB方案设定了N_S个sector。位于第r个sector内的车辆可从式(2)所示的时延集内随机地选择自己的竞争时延W_r：

其中r=1，2，…，N_S，并且r=1表示最远的sector。c_ω是竞争时延的时长。如式(2)所示，位于最远sector内的车辆(r=1)等待的时延最短。

    当等待时延计时完毕，车辆(仍假定车辆j)就向车辆i传输CTB包。若成功接收了CTB包，车辆i就传输数据包DATA。

    文献[7]对SB和UMB方案的性能进行了对比分析。结果表明SB方案在数据包传输率方面优于UMB方案，主要原因在于：UMB方案的数据包碰撞率随着车辆密度的增加而提升。而SB方案的数据包传输率趋于一常数，不随车辆密度变化而波动。

1.1.3 有效定向广播EDB^[8]

    文献[8]提出了基于时延的多跳广播协议，其工作流程与UMB和SB方案类似。然而，EDB(Efficient Directional Broadcast)方案未引用RTB和CTB控制数据包。此外，EDB方案引用了定向天线，每个车辆装有两个定向天线，波束宽度为30度。

    与UMB方案类似，EDM方案依据车辆所处的位置不同，定义两类数据包：道路上数据包和十字路口数据包。位于道路上的车辆，若它(假定车辆i)需要传输数据包，车辆i直接传输数据包，其后面的车辆跟着转发。为了减少冗余重传数据包，车辆在转发数据包之前设定不同的延时等待。延时的时长是关于离源车辆(车辆i)的距离函数，如式(3)所示。

其中R表示传输范围、d表示车辆离源车辆i的距离。max_WT表示最长的等待时间。

    如式(3)可知，离源车辆i越远的车辆具有越高的转发权。一旦延时等待完毕，车辆就立即传输ACK确定包。其他车辆监听到ACK包，表明有车辆具有比自己更高的转发权，自己就放弃这次竞争转发权任务。当源车辆i收到ACK，车辆i就传输数据包DATA。此外，为了提高可靠性，如果在max_WT内没有车辆转发数据包，车辆将周期地广播数据包。

1.1.4 Slotted 1-Persistence Broadcasting^[9]

    文献[9]提出Slotted 1-Persistence广播方案，其类似于其他的基于时延多跳广播方案。离源车辆i越远的车辆，具有越高的数据包转发权。当接收到数据包，车辆就依据给定的时隙(Time slot)转发数据包。时隙是关于车辆离源车辆的距离函数。假定车辆给定的时隙：

其中D_ij表示车辆j离源车辆i的距离、R为传输范围、N_S表示预定的时隙数。

    与Slotted 1-Persistence广播方案类似，文献[13]提出基于车辆密度的紧急广播VDEB(Vehicle-density-based Emergency Broadcasting)方案。VDEB方案也采用等待时隙，其是关于距离的函数。与Slotted 1-Persistence不同的是，VDEB方案考虑了车辆密度信息，并依据该信息决定合适的时隙数。

1.1.5 分发安全消息的可靠RMDSI方案

    文献[10]针对网络不连接问题，提出RMDSI(Reliable Method for Disseminating safety information)方案，从而提高通信的可靠性。RMDSI方案利用延时给每个车辆配置不同的转发数据包的优先权。与EDB类似，当接收到了数据包，车辆就依据式(3)计算等待时延，当时延计时完毕，就转发数据包。在等待过程中，车辆一直监听信道，一旦发现其他车辆已转发了数据包，就取消自己转发数据包的任务。

    RMDSI方案的另一个特性就是引用了解决网络断裂的机制。每个转发车辆都保存它已转发数据包的副本，直到它监听到来自下一跳转发节点发送的副本(Duplicate)或者数据包的有效期已过。如果没有监听到来自下一跳转发节点发送的副本，则表明网络可能断裂。在这种情况下，转发车辆就继续重播，直到它监听到来自下一跳转发节点发送的副本。通过这种机制应对网络断裂，提高数据包传输成功率。

1.1.6 多跳车辆广播MHVB

    文献[11]提出多跳车辆广播MHVB(Multi-Hop Vehicular Broadcast)方案。与其他基于时延广播方案一样，MHVB方案引用了转发数据包进行时延等待机制，时延的时长是关于距离函数。然而，不足的是：文献[11]中并没有给出计算时延时长的具体函数。

    与其他基于时延广播方案不同，MHVB方案采用了交通拥挤检测机制。交通拥挤，意味着车辆密度高，在这种环境下，每个车辆广播自己消息的间隔应增大。基于这个原理，MHVB方案利用邻居数和行驶速度信息对交通拥挤进行检测。当车辆发现自己的邻居数大于门限值X，并且自己的行驶速度低于门限值V_max，表明交通拥挤，在这种情况下，车辆将增加广播间隔。

1.1.7 RBLSM

    文献[12]提出RBLSM(Reliable Broadcasting of life safety messages)方案。RBLSM方案也采用时延等待机制：车辆在转发数据包之前，进行时延等待，直到时延计时完毕，才转发数据包。与其他时延等待方案不同的在于：RBLSM方案不再将离源车辆远的车辆给予最高的转发数据包权，反而，就离源车辆最近的车辆，给予最高的转发权。此外，RBLSM方案也采用了RTB、CTB控制包。

    与RBLSM方案类似，文献[14]提出基于链路的分布式多跳广播LDMB(Link-based Distributed Multi-hop Broadcast)方案。与RBLSM方案不同，LDMB方案中车辆在计算等待时延时，不仅考虑离源车辆的距离，还融入了交通密度、传输范围以及数据包传输率。

1.2 基于概率的多跳广播

    所谓基于概率的多跳广播就是指每个车辆设定转发数据包的概率，如文献[15-17]。由于不是所有的车辆都能够转发数据包，冗余数据包的数量和数据包碰撞率得到有效的下降。基于概率的多跳广播方案最关键的因素在于如何设置数据包转发概率。接下来，分析一些典型的基于概率的多跳广播方案。

1.2.1 Weighted p-Persistence

    文献[9]采用Weighted p-Persistence策略计算数据包转发概率。车辆在转发数据包之前，先依据离源车辆的距离计算转发概率：

其中D_ij表示车辆j离源车辆i的距离、R为传输范围。依据式(6)可知，离源车辆越远，具有转发数据包优先权的概率越大。然而，这个概率函数并没有考虑车辆密度信息，因此，如果网络密集，转发的数据包数量仍然很大。此外，文献[32]提出与Weighted p-Persistence类似的方案，转发概率正比于离源车辆的距离。

1.2.2 优化的自适应概率广播OAPB

    文献[15]提出了优化的自适应概率广播OAPB(Optimized Adaptive Probabilistic Broadcast)方案。OAPB方案依据局部的车辆密度计算数据包转发概率。每个车辆通过交互HELLO数据包，计算自己的局部车辆密度信息。假定车辆j收到数据包，其转发数据包的概率φ_j：

其中，N₁、N₂和N₃分别表示车辆j的一跳邻居数、二跳邻居数和三跳邻居数。

    此外，为了进一步减少被转发的数据包数量，具有相同转发概率φ的车辆设定不同的时延：

    仿真结果表明OAPB方案在广播开销和数据包传输率方面优于DB(Deterministic Broadcast)。原因在于OAPB能够依据网络特性自适应地调整转发概率。

1.2.3 AutoCast

    文献[16]采用了AutoCast广播方案，依据车辆一跳邻居数计算转发概率p：

其中N_h表示一跳邻居数。从式(9)可知，转发概率随着一跳邻居数的增加而下降。然而，显然，AutoCast广播方案能够正常工作是以N_h大于或等于5为前提的。但是，文献[16]并没有描述在N_h小于5时，AutoCast广播如何计算转发概率。

    此外，为了提高覆盖率和可靠性，AutoCast广播方案采用了周期性重播机制。重播间隔t：

    与MILE和按需MILE相比，AutoCast广播方案的性能有显著提高。MILE方案只是一个简单的周期广播协议，节点周期性转发接收到的数据包。而按需MILE方案是基于MILE的优化版，降低转发的数据包数量。仿真结果证实了AutoCast广播方案在数据包传输率和传输速度方面均优于MILE和按需MILE方案。原因在于AutoCast方案考虑了车辆密度信息计算转发概率，这有助于降低数据包碰撞概率和增加数据包传输率。

1.2.4 不可靠转发IF

    文献[17]提出了不可靠转发IF(Irresponsible Forwarding)方案。IF方案依据离源车辆距离和车辆密度信息计算转发概率p，如式(11)所示。

其中ρ_s表示车辆密度、z表示传输范围、d为车辆离源车辆的距离。c为形状参数shaping parameter，且c≥1。注意到式(11)，其不同于传统的转发概率函数。传统的转发概率函数是关于距离的线性函数。从式(11)可知，转发概率p随着距离d的增加而提高，随着网络密度ρ_s的增加而下降。

    文献[17]进一步分析证实：可通过形状参数c控制转发的数据包的数量。此外，IF方案维持转发数据包的数量趋于常数，即使是在车辆密集区域，这点说明，IF方案具有可扩展性。

1.3 基于网络编码的多跳广播

    网络编码是一种新颖消息分发方式，其能够有效地提高网络吞吐量^[18]。如图2所示。考虑一个简单的场景(如图2(a))，节点C位于节点A、B之间，并且节点A、B不能直接相连接。假定A需要向节点B传输一个数据包，同样，节点B也需要向节点A传输一个数据包。由于节点A、B不能直接相连接，它们只能借助于节点C转发。具体而言，节点A先将数据包转发给C，然后C再转发给B。类似地，节点B将数据包转发C，然后由C转发给A。显然，这种简单的方式，发生四次数据包转发。

    若采用网络编码，如图2(b)所示，首先，节点A向C发送数据包，然后，节点B也向C发送数据包。接下来，节点C利用异或XOR操作，对接收到的两个数据进行编码，编码后，再广播。最后，节点A、B接收到编码后的数据包，再进行XOR操作就能够得到自己所需的数据包，这个过程只需要三次数据包转发。

    上述分析可知，通过网络编码分发消息能够有效地降低数据包转发的次数，提高了宽带利用率。接下来，分析典型的基于网络编码的广播方案。

1.3.1 COPE

    文献[19]采用了基于网络编码的协议COPE。在实施过程中，COPE主要分为三步：(1)机会监听(Opportunistic listening)；(2)机会编码(Opportunistic listening)；(3)邻居学习(Neighbor state learning)。机会监听充分利用无线广播媒介探听的优势，每个节点将自己监听到的数据包存于自己缓冲区，但仅存一段时间。当机会来临时，将这些数据包进行编码。机会编码就是指节点利用一些规则对数据进行编码，然后再向外传输，但是，需要保证接收节点能够正确地对已编码的数据包进行解码。邻居学习就是接收哪个邻居节点所发送的数据包。为此，每个节点周期地向邻居节点广播自己缓存区域内的数据包。

1.3.2 CODEB

    文献[20]提出CODEB方案，其将COPE扩展到自组织网络。与COPE类似，CODEB方案引用机会监听。此外，每个节点周期地广播自己的一跳邻居清单。这样，每个节点能够构成两跳的邻居清单，从而形成广播主线。

    基于概率广播方案中，利用概率选择下一跳转发节点。与基于概率广播方案不同，CODEB方案从邻居节点中选择一些节点构成子集，该子集内的节点转发数据包。每个节点利用PDP(Partial Dominant Pruning)算法构建自己的子集。

    仿真结果表明CODEB方案在数据包传输率、数据包传输次数方面的性能优于仅采用PDP算法未利用网络编码的方案。原因在于网络编码能够减少数据包传输的次数。

1.3.3 EBCD方案

    文献[21]提出基于EBCD(Efficient Broadcasting Using Network Coding and Directional Antennas)方案。EBCD方案结合了网络编码和定向天线的优势。与CODEB方案类似，EBCD方案利用DDCDS(Dynamic Directional Connected Dominating Set)算法构建转发节点集。与CODEB不同之处在于：EBCD方案中网络编码应用到定向天线的每个sector区域。仿真结果证实EBCD方案能够有效地降低数据包传输次数。

1.3.4 DifCODE

    文献[22]提出DifCODE方案。与CODEB方案类似，DifCODE方案利用多点转发MPR(Multi-point relay)算法计算数据包转发节点集。与CODEB方案不同之处在于机会编码策略。在CODEB方案中，源车辆的所有邻居车辆都需要能够立即解码所接收到的数据包。这限制了编码机会。而DifCODE方案释放了这个限制性，允许节点缓存那些不能立即解码的数据包。仿真结果表明，与基于概率方案相比，DifCODE方案具有低的冗余率。

2 性能指标

    目前，研究人员采用众多的方法评估多跳广播方案的性能指标。为此，依据每个性能指标的特性，所有性能指标分为三类：频率、空间、时间，如表1所示。频率类的性能指标主要涉及到计数，如数据包的数量和车辆数量。空间类的性能指标主要涉及到距离的测量，而时间类的性能指标是关于时间的测量。

    表1的第2列给每个性能指标进行编号。表1的第3列列举每个性能指标，从表1可知，有些性能指标是非常类似的。第4列描述了计算每个性能指标公式，第5列描述了性能指标的单位，第6列表示该性能指标的使用频率。

3 多跳广播方案的性能比较

    第1节已分析了各类典型的多跳广播方案的特性，为了更充分地分析各方案的特点，表2还从评估模型、仿真平台以及使用的性能进行总结。

4 总结与展望

    针对VANET网络内的消息分发方案进行了分析和总结。依据特性的不同，将现有方案分为三类：基于时延、基于概率和基于网络编码的多跳广播方案。随后，总结了评估多跳广播方案的性能指标。

    尽管研究人员提出众多的多跳广播方案，但仍存在需要亟待解决问题。

    (1)理论性能分析的缺失

    从表2可知，目前仅少数多跳广播方案进行理论性能分析，多数方案仅采用仿真。因此，通用于分析多跳广播方案的基础理论模型值得研究。理论模型首先应该包含车辆移动模型，这直接影响到网络拓扑和网络连接。其次，应该能够包含数据包转发模型。

    (2)真实场景测试的缺失

    现有多数广播方案均是采用简单直线道路场景进行测试。然而，分发交通信息的多数场景是发生于城市交通，而城市交通的道路结构是非常复杂，不再是简单的直线道路场景。因此，广播方案应该需要在一个复杂的，逼近真实城市交通场景中进行测试。

参考文献

[1] 于海宁，张宏莉.VANETs路由协议的研究进展[J].电子学报，2011，39(12)：2868-2880.

[2] ABBOUD K，ZHUANG W.Analysis of communication link lifetime using stochastic microscopic vehicular mobility model[C]//IEEE Globecom，Atlanta，GA，USA，Dec.2013：405-410.

[3] CHENG H T，SHAN H，ZHUANG W.Infotainment and road safety service support in vehicular networking: From a communication perspective[J].Mech.Syst.Signal Process.，2011，25(6)：2020-2038.

[4] ALASMARY W，ZHUANG W.Mobility impact in IEEE802.11p infrastructureless vehicular networks[J].Ad Hoc Netw.，2012，10(2)：222-230.

[5] 李元振，廖建新，李彤红，等．城市场景车载Ad Hoc网络竞争转发关键参数分析[J]．电子学报，2011，38(5)：1154-l158．

6-22略