熊 鹏

(上海电机学院 电子信息学院，上海 201306)

车载自组网(Vehicular Ad-hoc Networks, VANET )的发展不仅对众多商业发展和娱乐推广起着巨大的推动作用，也是现代智能交通系统(Intelligent Transportation System, ITS) 的重要组成部分，对提高交通安全状况更是不可或缺的。据文献[1]报道,若司机能多出额外0.5 s的报警时间，高速上车辆追尾事故将能降低近60%。因此，通过为VANET设计和构建新协议来向那些行驶在车辆稀疏或视线受限区域的车辆发布告警信息具有非常重要的积极意义。

专用短距通行(Dedicated Short Range Communication, DSRC)技术作为近年新出现的技来术，完全能够满足了VANET对安全或非安全领域的需求；它同时也被认为是车辆间实现无线访问(Wireless Access in Vehicular Environment, WAVE)[2]或IEEE802.11p协议[3]的最好技术和方案。借助于DSRC技术，VANET中车辆间通信可以通过两种方式来实现：车辆与车辆间的通信 (V2V) 和车辆与路边设施间的通信(V2R)[2,4-5]。前者借助车载本身搭载的通信单元(OBU)，车辆向行驶在路上的某特定车辆发送信息；后者车辆则只与安装在路边的固定设施(RSU)进行信息交互。不管是V2V还是V2R，广播通信都已成为多数VANET实际应用中车辆间信息发布的基础性方案。例如，某个特定RSU可以针对路上的特定区域广播交通事故信息。对应区域车辆一旦收到相关信息，则可以进一步向与其相邻的车辆广播该信息，同样的行为在该区域所有车辆间不断重复进行,直至该区域所有车辆都收到该信息，进而能做出规避事故区域的选择，从而能够避免事故区域的交通拥堵状况，提高整个道路车辆通行效率。原始意义上的广播通信通常由泛洪算法实现。泛洪是一种节点全网广播信息，以保证网络中所有节点都能收到相应信息的算法。这种算法在节点有限的中小网络中运行效果不错，通行效率也较高。但同样的算法照搬到大型可扩展网络中，节点的广播、重播通信将会造成大量冗余广播信息，以及因共享无线信道而导致的节点相互传送信息时的信道争用带来的数据冲突，都将使得泛洪算法的性能急剧降低。这就是著名的广播风暴问题(Broadcast-Storm Problem, BSP)[6]。近年来，针对BSP涌现出了不少解决方案，它们可归纳为4类[7]：① 基于概率的；② 基于泛洪的；③ 基于区域的(又可进一步划分为基于位置和基于距离的)；④ 基于邻居关系的。这些方案同时也在移动自组网中出现并得到广泛研究[8-12]。BSP同样也困扰着VANET中节点进行的信息广播通信。针对VANET中的BSP，在综合分析和参考已有技术方案的情况下，从信息的可达性和降低信息重播数量两方面着手，提出了新的基于概率的自适应加权广播协议(Adaptive and Weighted Broadcast Protocol，AWBP)。模拟试验显示方案在没有显著增加额外开销的情况下，能够解决或较大程度地缓解大型网络中广播通信引起的BSP。

1 相关工作

文献[13]基于概率和计时器在单、双车道高速路的设定场景下，提出了3个广播通信方案: 时隙1-坚持、时隙p-坚持和加权时隙p-坚持；并分别从分组传送延迟、丢包率和系统开销3个方面分析了它们的性能。时隙1-坚持中，网络中的节点一旦收到相关广播信息，则以概率1向其他节点广播接收到的信息(即一定重播)。时隙-坚持，其要求所有节点以预先选定的概率p重新广播接收到的信息。这里，概率p通常为0.5，该值通常能实现网络的最大效能。虽然，时隙p-坚持能通过使用多个不同的p值来提升网络性能[8,10]，但其仍然存在着大量广播被重传的现象。对于加权p-坚持(WPP)[13]，其节点重播接收到信息的概率必须等于发送节点和接收节点信号范围间的比值。WPP在网络节点(车辆)数量不足的区域效率非常低；而对高密度节点(车辆)区域，节点也必须选择一个适当的广播概率才行。此外，上述3个方案在广播收到(或新)的信息前，节点都必须缓存信息一段时间。文献[14]针对BSP和隐藏节点问题及可靠的多跳广播需求提出了一个专用于车载网的城区多跳广播协议(Urban Multi-hop Broadcast,UMB)。该协议虽然实现了高密度节点区域高流量负荷环境下的网络信息交付的高成功率，但该协议需要中继器、支持黑场信号等的硬件成本和额外能量消耗。作为UMB协议的扩展，文献[15]给出了一个完全自组织网络多跳广播协议(Adhoc Multihop Broadcast,AMB)。该协议使用了一个定向广播方案来向距离自己最远的节点指派重播功能，专门设计的十字路口广播方案被用来处理十字路口的信息重播，从而避免了UMB中交叉路口广播信息时对中继器的需求。

文献[12]中的广播方案，试图通过限定紧急信息的广播方向在源节点周边减缓BSP。然而该方案没有对由广播造成的影响进行量化性分析，也没有提供具体的方式、方法或手段来评估该方案的具体性能和效果。文献[12]中的方案基于源节点和目的节点的位置、方向和移动速度提出了一个新的广播方案。通过忽略源、目的节点信号没有覆盖到的节点进行的重播，使得该方案能把BSP的影响降到最低。 事实上，前面提到的绝大多数基于概率的广播方案都会造成网络中大量冗余广播信息的出现，而这些信息正是导致BSP产生的根源。在充分吸纳现有广播协议优点的情况下，本文基于WPP协议提出了一个新的基于概率的AWBP。模拟试验表明：新协议能够避免WPP协议性能严重依赖网络环境的不足，在数据可达率和降低节点广播数量等多个指标数据上均有良好的性能。

2 基于概率AWBP

新协议以WPP协议为基础 ，以低重传概率实现网络信息高可达性为目标，尝试着提出了一个新的基于概率的AWBP，并对它的性能做了全面分析， 试验结果显示AWBP完全能够以较低的额外开销实现预先设定的各项目标。

2.1 相关概念

通过对现有研究的分析和总结，能够发现，车载网的广播协议的性能可集中体现于2个参数：信息可达率RE(Reachability)和重播保存率SR(Saved Rebroadcast)。一个好的车载网广播协议应该具备在信息可达性和重播保存率间达成平衡的能力。

定义1信息可达率RE。假设网络中的节点总数为N，节点Vr收到的信息数量为r，则信息可达率为

RE=r/N

(1)

该参数反映了收到信息的车辆与网络中车辆总数之间的比值。

定义2重播保存率SR。假设节点Vs发送了s个信息，如果节点Vr收到的信息数量为r，则重播保存率为

SR=1-s/r

(2)

该参数主要反映协议降低广播重播信息的能力。

2.2 基于概率的AWPB

WPP协议中，车辆一旦收到一个数据分组，就按概率Pij进行重播并定义

Pij=Dij/R

(3)

式中:Dij为节点i和j间的距离；R为网络中信息平均传输的范围。

WPP规定：如果节点收到来自多个不同节点的相同信息，则该节点在重播该信息前必须等待一段随机时间，从而能够以尽量低的概率来重播信息。显然，那些与源节点有相同距离的节点将具有相同的重播概率。这也是WPP协议在高密度节点网络中更容易出现BSP的原因。对于一个拥有少量节点的稀疏网络，当接收到信息的节点恰好为源节点的近距离节点时，该节点的重播概率将非常低，从而又将导致信息在全网节点间的低可达性。显然，应该对WPP中的转发概率进行重新设计。

图1显示的两种场景。假设S以250 m的半径广播信息。其中，S与C,E,F,G和H间的距离D分别为5 m、100 m、100 m、125 m和125 m。根据式(1)，相应节点的转发概率分别为0.02，0.4，0.4，0.5和0.5。通过试验可观察到，来自C的重播将会消亡，无法到达节点A和B。而来自E，F，G和H的重播又将产生过多的重播冗余数据出现。

图1 WPP协议的缺陷

因此，提出的AWBP协议中，设计了一个通用的概率方法，其动态地调整每辆车的重新转发概率，并且考虑每个车辆的局部密度，具体算法逻辑步骤如下。

Begin

{

Step1节点Vr收到新信息msg

Step2计算源节点Vs与Vr间的距离d

Step3计算Vs邻居节点的数量Nn

Step4计算网络中平均邻居结点数量Navg

Step5Ifd≤r/2 THEN //r为传输范围

IfNn≥NavgTHEN

Vr位于一个密集结点的网络区域中

Vr靠近源节点Vs,并且广播半径小

Vr以低概率P=Plow对接收到的信息进行

Go to Step7

Else

Vr位于一个稀疏结点的网络区域中

Vr靠近源节点Vs,但广播半径小

Vr以低概率P=Plow对接收到的信息进行

重播: Go to Step7

Step6Ifd>r/2 THEN

IfNn

Vr位于一个稀疏结点的网络区域中

Vr无离源节点Vs,度且广播半径大

Vr以低概率P=Plow对接收到的信息进行

重播: Go to Step7

Else

Vr位于一个密集结点的网络区域中

Vr靠近源节点Vs,并且广播半径小

Vr以低概率P=Plow对接收到的信息进行

重播: Go to Step7

Step7If (Random::uniform(0.0, 1.0)<=P)

Forward(msg)

Else

Free(msg)

}

End

上述算法中,步骤7是利用区域(0.0,1.0)中的均匀随机数来进一步降低网络中可能出现的重播冗余。

为了评估网络的局部密度，AWBP通过使用“HELLO”分组来获取节点的邻域信息，以便为网络中的每个节点构造其1跳邻居列表。

对一给定拓扑场景的网络，假设网络中节点总数为N，任意节点Vi在某一特定时刻的邻居节点数量为Xi，则该网络的邻居节点平均数为

(4)

根据文献[6]中的方法，网络中每个节点每秒周期性地向四周广播“HELLO”分组以获取该节点的邻居数量(Xi)，该值与网络平均邻居节点数(Navg)间的比值作为判断节点所处网络区域的疏密标准。每个节点就能对接收到的信息独立作出重播与否决策。限于资源和时间，本协议的最佳网络节点平均邻居数量Navg通过大量的模拟试验来获取。表1显示了在不同路况和节点总数的情况下，相对应的最佳平均网络邻居节点的数量。

表1 不同路况和节点数量下对应的平均邻居节点数

AWPB依据网络平均节点数把道路划分为节点密集区和节点稀疏区2个逻辑区域。不同的逻辑区域中的不同节点都将有自己特定的信息重播概率。

对于高密度区，节点的信息转发概率可由式(3)调整为

(5)

相应的低密度区节点转发概率可调整为

(6)

在某些情况下，P值可能小于零或大于1。 小于零则意味着高密度区中,节点非常靠近发送节点。 这种情况下,通过编码可以将P值调整为零。大于1则意味着稀疏区域中的节点距离发送节点非常远。 同理,这时P的值将被调整为1。

表2显示了不同P值的可能情况。每个接收到信息的节点首先应该缓存该信息，同时初始化自己的计时器以等延时TWAIT_TIME的到来。若在最大延时Tmax期间，节点不止一次的收到相同信息，则依据式(5)来计算信息重播概率。否则，信息重播概率由式(6)决定。信息重播延迟则可通过下式(7)来确定：

式中：T0为节点密度与信息发送、接收节点间距离的关系。

表2 不同距离邻居节点对应的转发

这里需要特别指出的是：AWBP采用文献[16]的方案，Tmax的值均匀的分布于[0，2] ms之间。这就意味着：邻居越多的节点，其延迟重播信息的时间越长；反之，邻居越少的节点则能更快的重播信息。

3 性能分析

实验采用和曼哈顿城市模型(Manhattan Grid Model)在NS-2 2.34相同的模拟实验平台[17]执行。通过不同场景和关键参数的多个模拟实验来获取包括信息可达率和重播保存率在内的AWPB的多项性能指标。实验区域大小设为2 km×2 km，每次实验时间定为15 min，具体参数如表3。

整个区域被划分为两横两纵，拥有4个十字路口的车辆通行环境。在每个十字路口，车辆可以某个确定的概率选择向左或右转。这时车辆转弯的概率设定为0.5。每条道路拥有两个车道，车辆在两边均可移动。车辆发送信号的有效距离为250 m，这也是DSRC[18]的推荐距离。网络密度通过改变公路上的车辆数量来实现网络中节点密度从低到高变化。为了更真实地模仿城市道路通行状况，则以不同车速的实验来模拟现实道路交通环境。例如，车速可分别设定为60 km/h的城市道路最高限速或30 km/h拥挤时的车速。为了更好地反映AWPB的性能，实验对AWPB，WPP和简单泛洪协议(SF)三者同时展开模拟，并对它们的实验数据进行比较。结果显示,重播的概率对网络中冗余信息的数量存在着重要的影响。

表3 模拟实验的参数设置

实验分别从车辆密度和车速两方面考察对信息的可达性和重播保存率2个重要指标[19-20]的影响。

3.1 车辆密度对广播协议性能的影响

为了摸拟现实交通中车辆密度随时间变化的场景，第1个试验，每公里的车辆数从10辆逐渐增加到100辆。车速则从最低的20 km/h提高到60 km/h。结果如图2和图3所示。

图2 3个协议的SR与车辆密度的关系

图2和图3显示了车辆密度不同时，对三者的重播保存率和信息可达率带来的影响。图2反映了车辆密度与AWBP,WPP和SF 3个广播协议的重播保存率的关系。当车辆密度为100辆/km时，AWBP,WPP和SF分别对应着73%，39%和0保存率；而当车辆密度降到10辆/km时，它们相应的保存率也降低到31%，15%和0。显然，AWPB性能明显优于WPP和SF两者。此外，相对WPP和SF，AWPB的车辆密度应用范围也更大。

图3 3个协议的RE与车辆密度的关系

3.2 车速对广播协议性能的影响

第2个实验的车辆密度定为70辆/km，车速介于30～80 km/h，以便观察车速对RE和SR的影响。

图4反映的是车速与AWBP,WPP和SF 3个广播协议SR的关系。从图4可看出，随着车速从30 km/h增加到80 km/h，WPP的SR从20%提升到40%，而AWPB却把自己的SR从40%提升到了78%左右。这里，SF的SR近似于零，这是因为每辆车都重播它们的信息而导致的。显然，AWBP相较于WPP和SF,SR提高了50%～100%，有着明显的性能优势。

图4 3个协议的SR与车速的关系

图5反映的是车速与AWBP,WPP和SF 3个广播协议的信息可达率RE的关系。从图5可以看出，随着车速的提升，三者都有较好的表现，尤其SF表现最好，其信息可达率RE几乎近于100%。但与WPP比,AWBP的表现又要更好些，当车速达到或超过某个值时，其RE有着和SF同样的优异表现。

图5 3个协议的RE与车速的关系

4 结 语

提出一个新的基于概率的AWPB，目的是为了缓解车载网广播信息时所引起的BSP。模拟实验结果显示，AWBP能极大地减少网络中的泛洪数据量(比SF减少了60%以上，比WPP也减少了25%以上)。显然，AWPB的性能比很多已有的类似工作在缓解BSP上有着更好地表现。希望对VANET设计者在开发具有指定的覆盖和连接度的基于应用的车载网络时具有实际意义。

参考文献

[1] AMBAK K, ATIQ R, ISMAIL R, Intelligent transport system for motorcycle safety and issues[J].European Journal of Scientific Research, 2009,28(4): 600-611.

[2] MORGAN Y L.Managing DSRC and WAVE standards operations in a V2V Scenario[J]. International Journal of Vehicular Technology, 2010(2):1-18.

[3] Network Working Group. Ad hoc on demand distance vector (AODV) routing protocol. RFC 3561. [EB/OL]. (2003-07-01) [2018-03-23]. https://tools.ietf.org/html/rfc3561

[4] ARMSTRONG L. Dedicated short range communications (DSRC) Home. [EB/OL][2018-03-23].http://www.leearmstrong.com/DSRC/DSRCHomeset.htm.

[5] IEEE standards association. IEEE Std 802.11eTM. [EB/OL]. (2005-05-03)[2018-03-23]. http:// http://standards.ieee.org/findstds/standard/802.11e-2005.html

[6] NI S Y, TSENG Y C, CHEN Y S,et al. The broadcast storm problem in a mobile ad hoc network [J]. The 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1999,8(2-3): 151-162.

[7] WILLIAMS B, CAMP T.Comparison of broadcasting techniques for mobile ad-hoc networks[C]//The 3th Acm International Symposium on Mobile Ad Hoc Networking and Computing. Lausanne: ACM SIGMOBILE, 2002: 194-205.

[8] SASSON Y, CAVIN D,SCHIPER A. Probabilistic broadcast for flooding in wireless mobile ad hoc networks[J]. Wireless Communications and Networking, 2002(2): 1124-1130.

[9] FUKUHARA T, WARABINO T, OHSEKI T,et al. Broadcast methods for inter-vehicle communications system[J]. Wireless Communications and Networking Conference, 2005(4): 2252-2257.

[10] YASSEIN M M B,KHAOUA M O,MACKENZIE L M,et al. Performance evaluation of adjusted probabilistic broadcasting in MANETs[EB/OL]. [2018-03-23].https://www.computer.org/csdl/proceedings/dasc/2006/2539/00/25390245-abs.html.

[11] YASSEIN M B, AL-DUBAI A, KHAOUA M O, et al. New adaptive counter based broadcast using neighborhood information in MANETS.[C]//The 23rd IEEE International Symposium on Parallel and Distributed Processing. Rome: IEEE, 2009:1-7.

[12] YANG Y, CHOU L. Position-based adaptive broadcast for inter-vehicle communications[EB/OL].[2018-03-23].https://www.mendeley.com/research-papers/positionbased-adaptive-broadcast-intervehicle-communications/.

[13] SLAVIK M, MAHGOUB I. Stochastic broadcast for VANET[C]// The 7th IEEE Conference on Consumer Communications and Networking Conference. Las Vegas:IEEE,2010: 205-209.

[14] KORKMAZ G, EKICI E, ÖZGÜNER F,et ai.Urban multihop broadcast protocol for inter-vehicle communication systems[J]. ACM International Workshop on Vehicular Ad-hoc Networks. 2004:76-85.

[15] KORKMAZ G, EKICI E, OZGUNE F.An Efficient fully ad-hoc multi-hop broadcast protocol for inter-vehicular communication systems[J]. IEEE International Conference on Communications, 2006(1):423-428.

[16] BACHIR A,BENSLIMANTE A. A multicast protocol in ad hoc networks inter-vehicle geocast.[C]//The 57thIEEE Semiannual Vehicular Technology Conference. Jeju Island: IEEE, 2003:2456-2460.

[17] Information Sciences Institute. NS-2 simulation experiment platform. [EB/OL]. (2016-10-18)[2018-03-23]. http://ftp.isi.edu/nsnam/dist/.

[18] OMAR H A, ZHUANG W, LI L.VeMAC: A TDMA-based MAC protocol for reliable broadcast in VANETs[J]. IEEE Educational Activities Department , 2013,12(9): 1724-1736.

[19] AL-KUBATI G, AL-DUBAI A, MACKENZIE L，et al. Efficient road topology based broadcast protocol for VANETs.[C]//The IEEE Wireless Communications and Networking Conference. Istanbul: IEEE,2014:2710-2715.

[20] ELBATT T, YEUNG G, HABERMASS.Performance evaluation of safety applications over DSRC vehicular ad hoc networks.[C]//Proceedings of the First International Worshop on Vehicular Ad Hoc Networks. Philadelphia: ACM SIGMOBILE,2004:1-9.