车载通信中增强型多跳广播算法研究*

赵海涛 ，朱洪波 ，2，刘南杰 ，蔡耿雄

（1.南京邮电大学通信与信息工程学院 南京 210003；2.南京邮电大学物联网技术与应用协同创新中心 南京210003）

1 引言

根据世界卫生组织(World Health Organization,WHO)2013年的全球道路安全现状报告，全球每天有将近3 400人死于交通事故，每年因交通事故受伤或残疾的人数近千万[1]。数据表明大多数交通事故是由于司机错误判断而引起的，因为他们不能预料到前方道路的危险状况。除此之外，天气以及视线遮挡都有可能进一步降低司机对前方道路的了解。

幸运的是，随着世界各国专家和研究人员对车辆通信不断的研究和探讨[2～7]，这个问题有望得到解决。除此之外，VANET(vehicular Ad Hoc network)已成为近10年来智能交通的研究热点之一。因为VANET在解决车辆与道路安全、交通效率以及司机与乘客的便利性和舒适性上有极大的潜力。目前对VANET的研究主要集中在架构的设计和实施上，研究工作包括路由、广播、服务质量、安全性等[8]。而本文的研究工作主要集中在VANET的多跳广播协议。

由于VANET固有的特性，如车辆快速移动、节点分布不均匀、网络拓扑频繁变化等因素，多跳广播存在许多挑战和亟待解决的问题。在车辆密集的情况下，存在多辆车同时广播数据分组，从而导致竞争和冲突。而当车辆稀疏时，又容易造成网络分割问题，即广播车辆一跳范围内没有车辆可以作为中继节点向更远的区域转发数据分组。同时，大量隐藏/暴露节点的存在也会影响广播信息分发的可靠性。

2 相关研究

在Ad Hoc网络中，当消息目的地在车辆一跳范围之外时，多跳是唯一的可行方法。最简单的多跳协议是洪泛广播，接收到广播消息的车辆需要立即向其邻居车辆转发该消息。在车辆稀疏的环境中，洪泛广播是一种有效的消息分发方式。然而，随着车辆数的增加，由于竞争和冲突，消息的交付率会大幅下降，即所谓的“广播风暴”问题[9]。

广播抑制技术是一种常用的解决广播风暴问题的手段。Wisitpongphan等提出3种轻量级的广播抑制技术：加权p-持续、时隙1-持续以及时隙p-持续[10]。其中时隙p-持续广播结合了加权p-持续广播和时隙1-持续广播的优点。车辆接收到数据分组之后，根据广播节点和自身的距离计算出分配的等待时间。若在等待时间结束之前还没有收到数据分组的副本，则以概率p转发数据分组，否则丢弃数据分组。

然而，时隙p-持续广播存在两个主要的问题。在稀疏网络中，分配的时隙可能不存在任何车辆，从而增加了不必要的等待时间（空白等待时间）。而对于密集网络，同一时隙存在大量车辆，因此也会引起频繁的竞争和冲突。Bae等提出一种基于邻居信息的广播机制（NIBS）解决上述的问题[11]。广播节点根据邻居表计算出在自己之后的车辆数目，并将其包含在广播信息分组中。接收节点根据自己的邻居表算出与广播节点之间的车辆数目，用接收到的数据分组中的车辆数目减去计算出的车辆数目，即可得出自己是距离广播节点第n远的车辆。经过（n-1）×τ（其中τ为等待时隙）的等待时间后，若车辆还没有收到广播数据分组的副本，则广播该数据分组；否则丢弃该数据分组。NIBS解决了空白等待时间的问题，降低了端到端时延。然而，NIBS没有解决稀疏网络中的网络分割问题，并且在密集网络中竞争与冲突问题依然存在。

Li等提出一种基于距离的广播协议——高效方向广播(EDB)[12]。EDB使用定向天线，规定与行驶方向相反的最远接收节点负责转发数据分组，并且在十字路口中安装定向中继器，用于协助向各个路段转发数据分组。节点接收到数据分组后等待一段时间，此等待时间与发送者和接收者之间的距离成反比。若接收节点在等待时间后还没有接收到广播数据分组的副本，则转发此数据分组；否则丢弃数据分组。Chou等在EDB的基础上，提出了基于位置的定向广播(LDB)协议[13]。LDB对节点等待时间进行改进，考虑了车辆位置、行驶方向和速度等因素。虽然LDB比EDB有更好的端到端时延，且考虑了双向的高速公路场景，但与EDB一样，依然没有解决网络分割问题。

基于以上的相关研究，本文提出一种基于邻居信息的增强型多跳广播协议（enhanced neighbor information-based broadcast protocol,ENIMBP），ENIMBP解决了高速公路场景下的网络分割问题，在稀疏网络中能显著地降低端到端时延，并且能够适应不同的车辆密度场景。

3 基于邻居信息的增强型多跳广播协议

3.1 系统模型

目前大多数高速公路都是双向的，选择反向行驶的车辆作为转发节点除了可以解决稀疏网络中的网络分割问题之外，还可以适应不同的场景[14]。假设每辆车都能通过定位系统获取自己的精确位置、速度和行驶方向。每辆车都有相同的处理器和计算能力，且无线信号的传输速度接近光速。除此之外，ENIMBP要求车辆维护自己的邻居表，因此需要周期性地发送Hello分组进行信息交互。

定义1 中继区域和忽略区域

ENIMBP采用全向天线，并将车辆i的广播范围分成两个区域：位于广播车辆后面的区域，定义为中继区域Ri；位于广播车辆前面的区域，定义为忽略区域Ii,如图1所示。ENIMBP规定，车辆i的邻居表中只有位于中继区域Ri的车辆才负责转发数据分组，而位于忽略区域Ii的车辆则丢弃数据分组。

图1 广播范围划分

定义2 转发等待时间WTi

ENIMBP采用基于接收者的广播抑制技术，即由接收者根据自己的信息决定何时进行广播。定义车辆i的转发等待时间为WTi，在等待WTi时间后，若还没有收到任何数据分组，则进行广播。WTi的计算会在第3.2节进行阐述。

3.2 中继节点选择

3.2.1 数据分组格式

当车辆探测到紧急情况时，会生成并广播数据分组。车辆根据邻居表可以计算出位于中继区域内的节点数目N。数据分组格式如图2所示。

图2 数据分组格式

其中，VID表示广播车辆ID；Position表示广播车辆的位置；Velocity表示车辆的速度矢量，包括大小和方向；N为位于广播节点中继区域内的车辆数目；MID表示消息ID；Message描述详细的道路事件。

3.2.2 计算WTi

广播车辆的邻居节点收到广播数据分组后，根据广播数据分组和各自的位置、速度信息计算相应的转发等待时间。假设广播车辆i的速度大小为vi，归一化的单位向量为；接收车辆j的速度大小为vj，归一化的单位向量为。广播车辆i的中继区域内的车辆数目为Ni，接收车辆j根据自己的邻居表计算出自身与广播车辆i之间的车辆数nj,i（不包含广播车辆）。在没有并行车辆的情况下，根据式（1）就可以区分出不同车辆的转发等待时间。式（1）可以计算出接收车辆j是距离广播车辆i第Ni-nj,i远的车辆，其中，C1为单位等待时间，即最远接收车辆等待C1，次远接收车辆等待2C1，以此类推。

然而，在许多实际场景中，往往会出现多辆车并行的情况，也就是说最远接收车辆有可能有多辆。因此，ENIMBP对式（1）进行改进，考虑了节点速度和方向等因素，得出接收车辆j的转发等待时间为：

从式（2）可以看出，在距离相同的情况下，与广播车辆反向的接收车辆转发等待时间会比与广播车辆同向的接收车辆的小，因此会优先转发数据分组。在距离相同且广播车辆与接收车辆同向的情况下，则速度小的车辆优先转发数据分组，因为速度小的接收车辆与广播车辆的相对距离较大；而在距离相同且广播车辆与接收车辆反向的情况下，则速度大的车辆优先转发数据分组，因为速度大的接收车辆与广播车辆的相对距离较大。适当选择C1与 C2，可以有效地区分接收车辆的转发优先级。

3.3 广播流程

NIBS只考虑了单向的公路场景，因此当存在稀疏网络中的网络分割问题时，会导致广播中断。然而，现实中的高速公路大多数都是双向的，因此，这里针对双向的高速公路，提出一种切实可行的转发算法。

为了解决隐藏/暴露节点问题，在广播车辆中继区域内没有任何车辆时，广播车辆会广播一个仅包含事件ID的取消数据分组，通知忽略区域内的车辆放弃广播。

如图3（a）所示，在车辆A处发生了意外，由车辆A产生广播数据分组，并按以下流程完成信息的传播。

步骤1 广播车辆根据邻居表计算出位于自己中继区域内的车辆数目N，若N=0，则进入步骤2，否则，进入步骤3。

步骤2 若中继区域内的车辆数目N=0，则广播车辆不会广播数据分组。与此同时，该车辆不断地更新邻居表，每次更新邻居表都会检测是否有车辆位于自己的中继区域。当中继区域出现车辆时，则进入步骤3；否则，继续存储携带。

步骤3 若中继区域内的车辆数目N>0，广播车辆以自己的ID、位置以及中继区域车辆数目更新广播数据分组中相应的信息，并广播数据分组，进入步骤4。值得注意的是，为了避免因链路中断而导致的分组丢失，广播节点会一直周期性地进行广播，直到收到广播数据分组副本或者取消数据分组为止。

步骤4 接收车辆首先根据数据分组中的广播节点位置和自己的位置判断自己处于广播节点的哪个区域。若处于忽略区域，则不做任何处理，直接丢弃数据分组；若处于中继区域，则根据数据分组的事件信息对驾驶员做出相应的提醒，并进入步骤5。

步骤5 接收车辆根据接收的数据和式（2）计算自己的等待时间，并根据自己的邻居表判断中继区域中是否有车辆。若有，则转到步骤3，若没有，则进入步骤6。

步骤6 当接收车辆中继区域没有车辆时，接收节点广播取消数据分组，即让位于忽略区域的车辆放弃不必要的广播（因为此时没有车辆比本接收车辆距离广播车辆更远）。接收到此取消数据分组的车辆将放弃广播。

图3 ENIMBP广播过程

对于图3所示的车辆分布，车辆A为源点，它产生数据分组。由于中继区域中有车辆B、C、D，所以车辆A广播该数据分组。车辆E位于A的忽略区域中，故直接丢弃数据分组。根据式（2），车辆B为第一个广播节点，但由于B的中继区域不存在任何车辆，故广播取消数据分组，车辆A、C、D接收到取消数据分组请求后放弃后续的广播。经过一段时间后，车辆C将进入B的中继区域 （车辆A与车辆B相向而行），此时B更新数据分组中的相应数据，并广播该数据分组。

根据上述的步骤，基于邻居信息的增强型多跳广播协议的流程如图4所示。

图4 ENIMBP广播流程

4 仿真与性能评估

为了对改进算法进行性能评估，本文使用网络仿真软件NS2对算法进行仿真，并与已提出的NIBS和时隙p-持续(p=0.5)方案进行比较。

4.1 仿真环境

仿真场景为双向的高速公路场景，每个方向3个车道，车道宽4 m，道路总长5 km。利用车载网络移动模拟器VanetMobiSim[15]模拟车辆的移动，假设车辆随机分布，并产生车辆移动跟踪文件。网络仿真软件选用NS-2.34[16]，该版本集成了IEEE 802.11p/WAVE[17～19]模块，因此很适合用于VANET的仿真。仿真参数见表1。

表1 仿真参数

4.2 仿真结果与分析

4.2.1 端到端时延

图5 端到端时延

图5是 NIBS、时隙 p-持续（p=0.5）和 ENIMBP 3种方案的端到端时延随着车辆密度的变化情况。从图5中可以看出，在任何车辆密度场景下，ENIMBP的端到端时延都优于NIBS和时隙p-持续方案。在车辆密度极低的情况下，网络分割问题的存在导致NIBS和时隙p-持续方案的端到端时延剧增；而随着车辆密度的不断增大，相同距离的车辆也随之增多，从而NIBS和时隙p-持续方案都有所增加。然而，ENIMBP利用反向车辆很好地解决了车辆密度低时的网络分割问题；同时转发等待时间引入了车辆速度和方向等因素，在相同距离的车辆不断增多的情况下，依然能够很好地区分车辆间的转发等待时间。

4.2.2 分组到达率

图6是 NIBS、时隙 p-持续(p=0.5)和 ENIMBP 3种方案的分组到达率随着车辆密度变化的情况。从图6中可以看出，在车辆密度极低的情况下，由于网络分割问题的存在，NIBS和时隙p-持续方案的分组到达率都很低；随着车辆密度的增大，NIBS和时隙p-持续方案的分组到达率显著提高，但当车辆密度增大到一定程度时，相同距离的车辆增多，分组到达率又有所下降。而ENIMBP解决了网络分割问题，并引入车辆速度和方向，在何种车辆密度场景下，都能保证高的分组到达率。

图6 分组到达率

5 结束语

本文提出了一种高速公路场景下基于邻居信息的增强型多跳广播协议——ENIMBP，通过利用车辆的邻居信息同时结合车辆的位置、行驶速度和方向来确定转发等待时间，以选择最优的转发车辆。根据车辆的位置，ENIMBP可以初步确定与广播车辆距离不同的车辆的转发等待时间。而在与广播车辆距离相同的情况下，ENIMBP则利用车辆速度和方向来区分转发等待时间。仿真结果表明，与NIBS和时隙p-持续方案相比，在车辆密度较小的情况下，ENIMBP利用邻居信息和反向车辆的存储—转发机制，可以保证较低的端到端时延和较高的分组到达率；而在车辆密度较大的情况下，由于额外引进了车辆速度和位置来计算转发等待时间，ENIMBP能更好地区分相同距离车辆的等待转发时间，从而降低了冲突和竞争，提高了分组到达率。

然而，ENIMBP依然存在很多不足的地方。邻居信息需要及时地更新和维护，在车辆密度低的情况下，广播算法需要频繁地广播取消数据分组，从而增加了网络负载。ENIMBP只考虑了高速公路场景，而并不适用于城市道路环境。下一步的工作将围绕这些问题进一步深入研究，不断完善本文提出的广播算法。

1 World Health Organization.Global Status Report on Road Safety 2013,2013

2 Tsugawa S,Kato S,Tokuda K,et al.A cooperative driving system with automated vehicles and inter-vehicle communications in Demo 2000.IEEE Intelligent Transportation Systems,2001(3)

3 Car 2 car.http://www.car-to-car.org,2012

4 Festag A,Fubler H,Hartenstein H,et al.FleetNet:bringing car-to-car communication into real world.Proceedings of 11th World Congress on Intelligent Transportation Systems(ITS’04),Maceiò,Alagoas,Brazil,2004

5 Reichardt D,Miglietta M,Morsink P.CarTALK 2000:safe and comfortable driving based upon inter-vehicle-communication.IEEE Intelligent Vehicle Symposium,2002(12)

6 CVIS.http://www.cvisproject.org,2012

7 Jiang D,Delgrossi L.IEEE 802.11p:towards an international standard for wireless access in vehicular environments.Proceedings of IEEEVehicularTechnologyConference,Baltimore,MD,USA,2008

8 Zeadally S,Hunt R,Chen Y.S,et al.Vehicular Ad Hoc networks(VANETS):status,results,and challenges.Telecommunication Systems,2012(4)

9 Tseng Y C,Ni S Y,Chen Y S,et al.The broadcast storm problem in a mobile Ad Hoc network.Wireless Networks,2002,8(2～3)

10 Wisitpongphan N,Tonguz O K,Parikh J S,et al.Broadcast storm mitigation techniques in vehicular Ad Hoc networks.IEEE Wireless Communications,2007(6)

11 Bea J S,Kum D.W,Nam J.C,et al.Neighbor informationbased broadcast scheme for VANET.Proceedings of 18th Asia-Pacific Conference on Communications,Penang,Malaysia,2012

12 Li D,Huang H,Li X,et al.A distance-based directional broadcast protocol for urban vehicular Ad Hoc network.Proceedings of the 3rd IEEE International Conference on Wireless Communications,Networking and Mobile Computing(WiCOM 2007),Shanghai,China,2007

13 Chou L D,Yang Y T.Location-based directional broadcast for inter-vehicle communications.Proceedings of IEEE Vehicular Technology Conference,Ottawa,Canada,2010

14 Nadeem T,Shankar P,Iftode L.A comparative study of data dissemination models for vanes.Proceedings of 3rd Annual International Conference on Mobile and Ubiquitous Systems(MOBIQUITOUS),San Jose,CA,USA,2006

15 VanetMobiSim.http://vanet.eurecom.fr/

16 Network Simulator 2(NS2).http://nsnam.isi.edu/nsnam/index.php/Main_Page

17 Eichler S.Performance evaluation of the IEEE 802.11p WAVE communication standard. Proceedings of IEEE Vehicular Technology Conference(VTC-2007),Baltimore,USA,2007

18 Stanica R,Chaput E,Beylot A L.Properties of the MAC layer in safety vehicular Ad Hoc networks.IEEE Communications Magazine,2012(5)

19 Ghandour A J,Difelice M,Artail H,et al.Dissemination of safety messages in IEEE 802.11p/WAVE vehicular network:analytical study and protocol enhancements.Pervasive and Mobile Computing,2013(3)