V2V中基于竞争转发的路由协议改进

于淼淼，于璐巍

(1.许昌学院 信息化管理中心，河南 许昌 461000；2.北京理工大学 信息与电子学院，北京100000)

Ad hoc网络[1]以其无中心，自组织网络的特点应用于车联网(Internet of Vehicles，IoV)的V2V(Vehicle to Vehicle)中，自组织车联网的路由协议得到了广泛的研究，旨在提高数据传输的到达率，减少数据传输延时和路由开销.

改进了车载自组网通信的探测交通拥堵探测方法CoTEC[2](Coperative Traffic congestion detECtion)，Si-CoTEC采取的CBF(Contention-based Forwarding)竞争转发机制，提出DCBF基于双次竞争的转发路由机制.DCBF采取两次竞争转发，一次竞争中考虑的是车辆节点的移动方向和最小连接控制集[3]CDS成员，经过一次竞争成功的节点将参与二次竞争.二次竞争将根据车辆节点的行驶速度以及车辆节点的位置信息设置定时器.DCBF不仅在简单连接或低密度场景中可以有效构建CDS成员，也适用于复杂连接或高密度场景，且在端到端时延和传输成功率均有所提高.

1 信息转发机制

在消息转发中，一次竞争首先判断节点的方向，若与发送节点同向的节点，通过设置最小连接控制集CDS，最小化每个组中所有邻居的转播节点的覆盖数量，最小化递送到网络中的大多数节点的重传次数.消息转发竞争机制流程如图1所示.

中继车辆向所有邻居广播CTE消息，接收到该消息的车辆通过启动定时器进行转发，定时器的持续时间与它们到前一个转发节点的距离成和自身速度成反比(高速远距离的车辆在重新发送消息之前等待较短时间)来安排消息的重新传输.当定时器时间结束时就可以转发Data消息.

1.1 最小连接控制集

车辆行驶时是非均匀分布，密度动态分布.例如，在畅通的高速路上，密度非常稀疏，但在城市十字路口的中部，节点堆积密集.为了使算法适应不同的环境.本文通过选择具有最高数量的1跳邻居的节点来限制广播分组，因为它可以最小化接收到的节点数量，同时最小化重播节点，并且对于每个场景中的所有大小的分组都有效,因此，DCBF使用1跳邻居数作为算法的主要条件，具有1跳邻居节点最多的节点是CDS成员，如图2所示.

确定CDS成员重要的条件是具备网关条件[4].网关节点具有至少一个邻居，即不被一对网关节点的邻居覆盖，并且这两个邻居也是彼此的邻居.例如，判断节点A是否为网关节点，A需要具有至少一个邻居D，即不被一对连接的邻居B和C覆盖.如果A是网关节点，则邻居D不被B或C覆盖.因此，NA不是B或C的邻居.令NA是一组节点A的邻居，NB是一组节点B的邻居，和NC一组节点C的邻居.B和C是节点A的邻居.如果节点A同时满足以下公式，则将其从CDS中消除.

图1 消息转发竞争机制流程图

图2 最小连接控制集(CDS)

{B,C}∈NA，

(1)

{C}∈NB，

(2)

{B}∈NC，

(3)

NA⊆NB∪NC.

(4)

因此，CDS中的节点只是覆盖组中其他节点的必需节点.协议中的节点自己决定是否是CDS成员.如果是CDS成员，收到广播包后，随机设置非常短的退避延迟(<10 ms).延迟到期后，它立即重新播送数据包.不是CDS成员的节点将其等待的超时设置为比CDS成员更长的周期.当等待超时不会过期时，他们正在从其他节点接收转播.如果他们接收到在等待列表中重新播放相同的数据包，即从等待列表中删除该数据包，以避免冗余重传.

1.2 传输场景

传输场景主要包括正常广播场景和间歇性连接场景，如图3所示.图3(a)显示了正常的广播情况.S是源节点.令C为具有最高局部密度的节点，因此C将成为CDS成员.当S广播分组时，A、B和C接收广播分组.A和B计算他们的等待超时，并等待从CDS成员转播.C作为CDS成员，在重新播放数据包之前将设置转发定时器，参与二次竞争.在C正确重播数据包的情况下，A和B将取消其等待超时，以避免冗余重传.另一方面，如果C不转播该分组，则具有最短等待超时的A或B将重新广播分组.若B具有最短的等待超时，所以B重新广播数据包而不是C.A将取消其等待的超时，不会导致冗余重传.转发过程持续到组中的所有节点接收到数据包或直到数据包过期为止.

在间歇连接情况中，节点需要在组间重传数据包,情景如图3(b)所示.节点A，B和C已经从S接收到广播分组.当B超过其他车辆时，它离开旧的组并加入新组.新组中的节点是D，E和F他们从未接收到来自S的广播分组.B可以通过来自D，E和F的数据确认检测丢失的分组.B将设置其等待超时，并将其转发到其他节点.当D，E和F接收到数据包时，它们将作为正常的广播情况.CDS的成员立即重新播送数据包，而其他成员设置的时间比CDS成员长，直到所有节点接收到数据包或数据包过期.

图3 传输场景

1.3 消息转发定时器

中继车辆向所有邻居广播CTE消息.接收到该消息的车辆，在一次竞争成功后，通过启动定时器进行二次竞争转发.定时器的持续时间与它们到前一个转发节点的距离、速度最大值、当前速度等有关.通过定时器来安排消息的下一步传输.当定时器时间结束时就可以转发Data消息.按公式(5)计算自身的定时器的等待值.

(5)

Tmax是最大的转发延时，rradio是广播直径.Tmax和rradio均为定值.v为节点的移动速度大小，vmax为所有车辆节点的最大移动速度，T为定时器的等待时间.T越小越容易在竞争中胜出.dis是拥堵位置与本车的距离，因此越大越好，即距离拥堵位置越远且速度越大的节点越容易二次竞争成功，优先转发.

2 等待超时机制

等待超时[5]是分布式系统中广播冲突的解决方案.节点将随机设置等待超时作为转播延迟.在两种情况下启动等待超时机制.一种情况是非CDS的成员节点接收到广播数据包时.他们将数据包添加到广播列表并设置等待超时.这些节点必须接收其邻居中CDS成员的转播.如果等待超时结束，并且没有CDS成员转播该分组，则具有最短等待超时的节点将重新广播分组.另一种是当节点从邻居节点中检测到丢失的数据包时.他们将数据包添加到广播列表，并将等待超时设置与第一种情况相同，然后，具有最短等待超时的节点将丢失的分组重新广播到其邻居.

等待超时的缺点是它会延迟整个系统.现有的研究多为计算他们的等待超时与1跳邻居数成反比关系.目的是通过使用具有1跳邻居最多的节点，使每次重传中传递的节点数量最大，不过这也会触发竞争问题.由于当节点处于密集区域时，用反比关系函数计算出很短的延迟范围，所以它在高密度场景中会使冗余重传增加.因此，同一区域中的大多数节点将具有相同的等待超时.然后他们同时转播造成冲突.为了防止这种情况，协议使用1跳邻居的数量来调整等待超时功能的变化.通过设置定向函数防止在极高密度情况下的碰撞.等待超时由公式(6)计算.

W(n)=Random[nτ，(2τ+nβτ)].

(6)

τ表示网络延迟，即数据包被传送到接收器为止.n是多个1跳邻居.β是用于扩展最小等待超时和最大等待超时之间的范围的常数值.最优状态下β值可以显著减少密集区域的碰撞事件，同时只增加较小的延迟.等待超时的最小项表示从MAC层中的数据排队的延迟可能性.所以最小项将等于所有邻居的数据发送时间的总延迟.等待超时的最大期限由两个部分组成.第一项2τ，即网络延迟的两倍.这是因为在节点具有一个邻居的情况下，它们有可能等待来自邻居的一个数据和来自转播的另一个网络延迟.第二项，nβτ是从MAC层中的数据排队的可能性延迟，即乘以扩展值β.β用于扩展最小项和最大项之间的范围.

3 拥堵信息数据结构

V2V中车辆之间拥堵消息传递采用的是广播泛洪的方式，拥堵信息的结构[6]在一定程度上影响信息的冗余度，信息传递的丢包率，传输安全和成功率.故需设计拥堵信息的结构，使接收方在收到信息快速的辨别出有效信息，并且降低信息冗余度，提高信息传递成功率.

在DCBF中合作拥堵识别是依靠车辆间信息的传递完成的，其中传递的消息类型有三种，分别是Beacon、Data、CTE消息.其中Beacon消息用于自身拥堵判别，传输车辆的位置、速度等信息，Data消息用于检测到拥堵后开启合作检测，CTE消息用于合作检测结束后向后车传递检测的拥堵级别.

车辆之间通过周期性地发送Beacon消息来判断彼此是否能建立通信连接.Beacon消息一般需要包含如下信息：车辆的ID、位置、速度、消息类型、消息有效时间、拥堵程度、排队长度、安全优先等级等.格式为如图4所示，其中，Node ID为车辆节点的ID号，Grade安全优先等级，Posi为位置信息，Vel表示车速，Type为消息类型，Length表示拥堵长度，Direction为行车方向，TTL为消息的有效时间.Beacon消息被存储在车辆节点的历史消息列表中.消息发布节点或订阅节点以固定时间间隔τ广播发送Beacon消息，获知k跳邻居节点，通过建立局部网络拓扑视图，节点与周围车辆建立k跳中继连接.消息发布节点以一定的时间间隔τ广播发送Beacon消息，获知k跳邻居节点.

图4 Beacon数据结构

DCBF中的节点使用Data消息发现1跳邻居并交换其本地信息.Data消息报头包括：源标识符，1跳邻居数，1跳邻居标识符列表和仍未过期的接收报文列表，拥堵判别信息.接收到的分组的列表包含发送源的标识符和分组的标识符.此列表用于检测丢失的信息.在没有1跳邻居和接收到的数据包的情况下，数据大小将至少为5个字节.数据大小将为每个1跳邻居增加4个字节，并为每个接收到的数据包增加5个字节.为了减少数据的数量，如图5所示.当它们具有重播分组时，节点用广播分组背对数据头，然后下一个数据将被推迟到下一个数据间隔.

图5 Data、CTE数据结构

4 仿真结果和分析

为了评估DCBF算法在监控交通拥堵的应用性，进行仿真验证，重点分析了端到端时延数据包投递率和路由开销.使用交通模拟器SUMO产生逼真的车辆运动轨迹.在NS3中进行模拟仿真.表1为参数配置.

表1 交通仿真参数设置

4.1 数据包投递率

Si-CoTEC可以实时的评估车辆四周的密度信息，并且利用估算的密度信息和行驶速度对当前的路况进行评级.图6显示了DCBF和Si-CoTEC在不同的车辆节点场景中，数据包投递率变化情况.从图中能够看出：随着车辆节点数目的增多，DCBF、Si-CoTEC的数据包的投递率也随之提高，投递率均在0.5以上，并且当节点数目增多时，在车辆数达到100以上时，DCBF投递率高达90%，Si-CoTEC为80%.此外，DCBF比Si-CoTEC协议数据包的投递率提高得更快.由于车辆节点数目较少的车联网的连通性不好，很容易造成网络分割最终导致路由的失败，所以车辆节点数目较少的时候DCBF和Si-CoTEC的数据包投递率均不是很高.而随着车辆节点数目的增多，车联网的连通性有所改善，因而数据包的投递率也会随之提高.同时也可以看出在车辆节点数目相同的情况下，所提出的DCBF数据包的投递率比Si-CoTEC要高，说明本文提出的DCBF的丢包率更小.

4.2 路由开销

图7显示了DCBF和Si-CoTEC在100个车辆节点的城市场景中，不同车速下的路由开销.从图中能够看出：DCBF数据包的路由开销大于Si-CoTEC，这是由于DCBF在采用了两次竞争，在选择最小控制集成员时会产生开销，但随着车辆节点速度的增大，DCBF的开销并未受到太大的影响，均在2*104左右，Si-CoTEC则会因为速度的变化路由开销逐渐增大，在速度为30 m/s的时候，Si-CoTEC的路由开销跟DCBF相近.

图6 数据包投递率

图7 路由开销

5 结语

主要介绍了V2V中拥堵信息的转发过程.在车载Ad-hoc无中心，自组织的多跳背景下，消息转发的泛洪问题也是影响V2V在智能交通系统中发展的原因.介绍了DCBF为了平衡有限的带宽和通信资源及庞大的节点发送需求之间的冲突，提高消息的传递率，改进了CoTEC，Si-CoTEC采取的CBF竞争转发机制，将原本的位置转发竞争机制改进为两次竞争.一次竞争中在方向同向的竞争后添加了最小连接控制集成员的竞争条件，介绍了最小连接控制集为竞争条件的优势以及方法.二次竞争中将Si-CoTEC采取的距离发送节点最远等待时间最短的条件改进为考虑速度和距离双重因素来设置定时器，更能适应与车辆的动态环境，使DCBF无论是在节点密集的城市和节点稀疏的高速路，均能更好的传递信息，降低广播风暴.