车载网络自适应概率广播协议

程青青, 陈戈珩

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

1 VANET介绍

车载自组织网络(VANET)在智能交通系统(ITS)架构中发挥着关键作用。VANET应用程序可以分为两大类：一类解决行车安全，称之为安全应用；另一类提供增值业务，如满足乘客在车辆环境中的娱乐等功能，称之为用户应用。据文献[1]报道，如果汽车驾驶员在发生碰撞前0.5 s被予以示警，就可以避免60%的交通事故。因此，利用VANET向分散在稀疏区域的车辆传播警告信息尤为重要,且具有挑战性。

在过去十年中，专用短距离通信(DSRC)协议的发展满足了VANET安全和非安全应用的需求[2]。VANET中车辆之间的通信主要取决于DSRC的机制，可以通过两种方式完成：一种是车与车之间的通信(V2V)，道路上的每辆车都会向特定车辆发送消息；另一种是车辆与路边单元的通信(V2R)[3-5]。广播通信作为VANET应用程序的基石，主要用于V2R或道路上的V2V广播消息。假设路边车辆可以周期性地广播道路状况消息，当每个车辆第一次接收到该消息时都会以多跳的方式将接收到的消息广播给邻居车辆，邻居车辆接收到消息后也会向其它车辆节点继续有序地广播已经接收的消息，这样就很好地避免了信息堵塞问题。传统广播方法“泛洪”在传播消息时会将已经接收到的消息充斥整个网络，从而保证所有消息能够广播到每一辆车，在这一过程中会造成大量的冗余广播消息，以及信道资源的浪费。在VANET中这样大型的可扩展网络使用泛洪的方式，会大大降低广播消息的性能，因为大量的冗余广播消息会让车辆在传输消息时无限制地竞争信道资源。在移动自组织网络(MANET)中将这种现象称之为“广播风暴”(BSP)，用于解决广播风暴的方法有4种[6]：1)基于概率的广播协议；2)基于泛洪的广播协议;3)基于区域的广播协议;4)基于邻居节点的广播协议。这4种方案在MANET环境中得到了广泛应用，有效地抑制了“广播风暴”产生的不良影响[7-11]。但是在VANET中对于“广播风暴”的抑制研究还处于初级阶段[12-13]，为了填补研究上的空白，文中给出一种新型的解决“广播风暴”问题的方案，并从消息的可达性和消息的存储重播这两个性能入手来验证方案的可实施性。

2 传统的VANET广播传播方案

文献[14]通过对单车道和多车道的高速公路情景模拟探讨了BSP在VANET中的降级效应，提出了三种基于概率的计时器广播方案，通过对消息延迟率和丢包率来评估广播方案的性能。其中第一种方案将每一辆车的广播概率都设置为概率1进行广播。第二种方案是将每辆车的概率值设为固定概率P,通过实验验证，当概率P值取0.5时,网络性能达到最大化程度，但是这种方案在实施过程中仍然存在大量的冗余信息，为了解决这一问题就需要多方面考虑P的取值问题，选取最合适的P值使网络性能达到最佳状态。第三种方案将允许通过的每个车辆作为广播消息的发送器，在传输范围内依据车辆接收消息的机率分配概率值的大小，然后再根据概率的大小来广播消息。文献[15]提出了城市多跳广播协议(UMB)来解决“广播风暴”问题，主要是在确定邻居节点个数和多跳广播可靠性方面进行改进，通过实验验证该协议在高分组负载和不同网络密度的情况下依旧能够保证高效的广播传输效率，但需要安装中继器，这样就会造成额外的硬件消耗和功耗的损失。通过对UMB协议的扩展，文献[16]提出了基于点对点(Ad-hoc)的AMB多跳广播协议。这种广播协议在交叉路口进行广播消息时可以不依赖于中继器，采用定向广播的方法完成远距离车辆消息广播。传统方案是通过确定源节点车辆对于紧急消息的广播方向来抑制“广播风暴”的方案,由于没有对存储的广播消息进行量化，无法采用特定方法对这种广播方案进行合理的性能评估。文献[17]提出了一种基于车辆间通信的广播方案来接收和发送车辆的位置、方向和速度信息,这种方案不仅解决了端到端的传输延迟和传输时间的延迟,还通过忽略新增车辆节点的消息重传来最小化“广播风暴”问题。

3 自适应加权概率持久性方案(AWPP)

通过对传统方法的研究可知，VANET的有效广播协议必须在消息可达性和消息重播率之间达到一个平衡的状态，为了实现最佳的广播传输方案，文中给出了一种自适应加权概率持久性方案(AWPP)，这是基于传统的加权概率持久性方案(WPP)的基础上进行改进的。在传统的WPP中，每个车辆接收到的数据包概率为

(1)

式中:Dij----节点i和j之间的相对距离;

R----平均传输范围。

根据WPP协议，如果车辆从多个广播源接收消息，车辆会在广播消息之前等待一段时间来确保以低概率重播，相同距离车辆的重播概率相同。采用这种形式的广播方式在高密度VANET中会导致“广播风暴”，在稀疏密度VANET中会导致重播概率非常低，消息可达性差。因此,针对传统方案中存在的问题，对转发概率方案进行了改进。WPP方案的缺点如图1所示 。

图1 WPP方案的缺点

图1说明了上述的两种情况。假设车辆S在250 m的传输范围内广播消息，距车辆C,E,F,G,H之间的距离D分别为5、100、100、125、125 m。那么通过式(1)计算出每辆车的广播概率分别为0.02、0.4、0.4、0.5和0.5。通过观察可以知道,车辆C发出的广播消息不会到达车辆A和车辆B，而车辆在广播的过程中将会收到重复的广播消息。这种传播方式就会造成车辆之间在接收和发送消息的过程中发生紊乱，尤其是在车辆分布密集的VANET中，这种现象会更加突出。为了解决这一问题，给出了一种通用的概率方法，可以根据每辆车的实时局部密度情况来动态地调整每一辆车的转发概率。可以通过使用“HELLO”分组来收集邻居节点的信息，在每辆车的位置构建一跳的邻居,从而估计出本地网络的密集程度。

AWPP协议的算法步骤:

Begin

{

Step1:记录车辆Vr在第一次接收到广播消息msg

Step2:获取发送消息车辆Vs和接收消息车辆Vr之间的距离d

Step3:获取接收消息车辆Vr的邻居节点数量Nn

Step4:得到平均网络邻居节点数目Navg

Step5:IF dNavgTHEN

Vr位于密集区域

Vr和Vs在相距较近的广播覆盖范围内

当Vr的最小传播概率P=Plow时跳转到step 7

Step6:IF d>r/2 and Nn

Vr位于稀疏区域

Vr和Vs在相距较远的广播覆盖范围内

当Vr的最大传播概率P=Phigh时跳转到step 7

Step7:IF (Random::uniform(0,0,0,1)≤P)

Forward(msg)

Else

Free(msg)

}

End

对于给定的区域拓扑场景，则可以给出定义式

(2)

式中：N----网络中的车辆总数;

Xi----特定时刻车辆Vi处的邻居节点数量;

Navg----车联网中的网络平均邻居节点数量。

每个车辆节点会在1 s时间内定期广播“HELLO”数据包，在一跳的广播距离范围内收集Xi值。Vi值则需要根据此时的网络环境是密集区域还是稀疏区域来确定。在特定时刻围绕在Vi周围的车辆数量高于Navg时，此时意味着Vi处于密集区域，否则处于稀疏区域。在确定完Vi值后，每一个车辆节点都会依据当时自己所处节点的实时状态来决定是否将自己收到的消息广播给其他的车辆节点。由于资源和时间有限,在实验过程中只能广泛地进行模拟实验，找出Navg的近似值。

不同路况下Navg的取值见表1。

表1 不同车辆和道路数量的预期平均邻居节点数量汇总

AWWP协议在逻辑上将道路状况分为稀疏型和密集型，将Navg值作为判断道路是稀疏还是密集的阈值，车辆在每个位置都具有不同的概率值P,在密集区域的转发概率公式

(3)

在稀疏区域的转发概率公式

(4)

某些特殊情况下，概率值P可能小于零或者大于1。在小于零的情况下，意味着车辆距离源发送节点的距离非常近，并且处在车辆非常密集的区域中，这时就需要通过编码来将概率值P调整为零。如果概率值超过1，就意味着车辆距离源发送节点非常远并且车辆处在非常稀疏的区域中，此时需要将概率值P调整为1。不同距离和邻居节点数对应的概率值见表2。

表2 不同距离和邻居节点对应的概率值

每一辆车在接收消息之前都会存在等待延迟时间，也就是不同概率值在接收广播消息时对应的初始计数器等待时间TWAIT_TIME。如果车辆在Tmax时段内接收到重复的消息就需要运用式(3)来计算此时的转发概率，否则用式(4)来计算。文中将给出计算广播延迟时间：

TWAIT_TIME=Tmax*T0,

(5)

(6)

式中：T0----车辆密度与其距离发送者距离之间的关系。

根据文献[20]给出的经验，Tmax的值要在[0,2 ms]之间均匀生成，这就意味着拥有多邻居节点的车辆会用很长一段时间重复广播，而拥有少邻居节点的车辆则会用较短的时间重复广播。

4 仿真验证

为了验证文中给出方案的可行性，运用NS-2.34软件和曼哈顿模型进行仿真实验，在以往的研究中也运用过相似的方法，将车辆放置在一个2 km×2 km的区域，放置时间为15 min。实验过程中,将模拟区域划分为2个水平街道和2个垂直街道，这样一来会形成4个交叉点。在每一个交叉路口车辆在向左转还是向右转的概率为0.5,是确定值。每一条街都有两条车道，车辆可以在车道两侧移动，在250 m的可靠传输范围内满足DSRC近似标准范围数据传输准则。通过改变车道上车辆的数量来改变交通流密度从低到高的变化，用来模拟高峰时段和非高峰时段的情形，车辆数量分别为25、100 辆/km。由于城市环境中车辆速度多变，为了使实验更加接近真实城市道路，使用不同的速度来进行试验。在交通状况拥挤时车辆的最大移动速度为60 km/h，最低速度为30 km/h。将AWWP协议和传统的WPP[18]协议、简单泛洪(SF)协议进行对比仿真实验，模拟实验参数见表3。

表3 对比参数值

实验结果表明，对于多个冗余信息和传输覆盖区域，重复广播概率P的取值不同，产生的结果也不相同。实验中，通过改变车辆数量(车辆数量从10 辆/km变为100 辆/km)来验证不同交通状况下的情景。文献[19-20]通过对两个重要指标参数减少重复消息广播概率Saved Rebroadcast(SR)和消息可达率Reachability(RE)对概率方案进行了验证。

SR可定义为

(6)

RE可定义为

(7)

式中:N----车联网中的车辆数;

r----车辆接收的消息数量。

通过仿真实验验证了不同车联网密度状态下AWWP协议、WPP协议和SF协议在减少重复消息广播概率和消息可达率的性能指标。仿真实验时，车辆数的变化区间为[25 辆/km,100 辆/km]，车速的变化区间为[20 km/h,60 km/h]。通过实验数据图可以发现，AWWP协议不管是在密集区域还是在稀疏区域的网络广播性能都优于SF协议和WPP协议。三种协议在不同车辆密度下的减少重复消息广播概率比较如图2所示。

图2 三种协议在不同车辆密度下的减少重复消息广播概率比较

通过仿真实验数据可以看出：车辆数量为100 辆/km时，AWWP协议的SR值为73%,远高于WPP协议的39%和SF协议的0%;车辆数量为10 辆/km时，AWWP协议的SR值为31%,远高于WPP协议的15%和SF协议的0%。由此可见，AWWP协议可以广泛应用于不同车流量密度的场景，不仅在密集区域的性能远优于其它两种协议在稀疏区域的性能,也远优于其它两种协议性能。

在可达率(RE)方面，随着车流量密度的增加，RE值也随之增加。三种协议在不同车辆密度下的消息可达率比较如图3所示。

图3 三种协议在不同车辆密度下的消息可达率比较

车辆数量增加到70 辆/km时，三种协议的可达率(RE)都近似接近100%，这就意味着AWWP协议实现了密集车联网级别的泛洪可达率。在稀疏区域的车联网中，SF协议的性能要略优于AWWP协议，而WPP协议的性能则是最差的。

仿真数据验证了AWWP协议、SF协议和WPP协议的网络性能。三种协议在不同车辆速度下的减少重复消息广播概率能力及消息可达率分别如图4和图5所示。

图4 三种协议在不同车辆速度下的减少重复消息广播概率能力比较

若将网络密度设定为70 辆/km，取30 km/h到80 km/h之间的不同速度值来进行仿真实验，结果表明,AWWP协议相比于SF协议和WPP协议在车辆速度多变的情况下有更好的适应性，显著地降低了重复消息广播概率，有效避免了广播风暴。在消息可达率方面，AWWP协议在车速高于60 km/h时，消息可达率几乎达到100%，虽然车速低于60 km/h 时，消息可达率略低于SF协议，但是综合减少重复消息广播概率参数SR的性能指标，AWWP协议的优势是显而易见的。

5 结 语

给出了一种用于解决广播风暴问题的AWWP协议，通过仿真模拟实验验证了AWWP协议的性能优势。AWWP协议相比于传统的WPP协议和SF协议，在减少重复消息广播概率和消息可达率上的不足进行了弥补，解决了“广播风暴”问题。在实际的应用中，广播消息的传播覆盖率和车辆节点之间消息的可达性较传统多跳广播协议更具有优越性。