车联网中基于概率的自适应多跳广播协议

程青青, 陈戈珩

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

0 引 言

0.1 VANET网络架构

VANET经典体系架构中包含车载单元(On Board Unit， OBU)节点和路边单元(Road Side Unit， RSU)节点两种设备类型。网络中的车与车之间、车与路侧单元节点通过无线技术通信，而车与基站之间通过蜂窝网技术通信。一般情况下，由于道路的约束，VANET中OBU节点会按照一定规则方式运动。而RSU等固定节点则负责在定点位置与车载节点通信，提供短距离范围内V2I和V2V通信服务或长距离范围的外部网络通信服务[1]。典型的VANET架构如图1所示。

0.2 问题分析

近年来，针对车载自组织网络中的紧急消息如何快速、可靠地传播到相关区域内所有车辆的特性，研究者提出了多种多跳广播方案。这种多跳广播方案解决了单跳广播覆盖区域不够大的问题，可以保证目标区域内每个车辆都能够成功地接收消息。

图1 VANET网络架构

最早提出的广播方式是简单泛洪[2]，要求网络中的每一个接收到广播包节点都要无条件转发，当网络密度达到一定程度时，网络中的消息副本将会迅速增加，造成广播风暴问题[3]。因此，如何根据VANET的特性设计出一种能够有效抑制广播风暴，并且具有高稳定性、低延迟的多跳广播方案，是目前VANET研究的重点和难点。

0.3 算法研究

现有的多跳广播方案主要可以分为两类：基于发送者的多跳广播协议和基于接收者的多跳广播协议。

基于发送者的多跳广播是指由发送者确定下一跳转发节点的一类多跳广播策略，这一类算法通常需要不断地交互一些本地信息，用于筛选下一跳转发节点。例如基于地理位置的多跳广播、基于优先级的多跳广播等。文献[4]提出了一种基于优先级的多跳广播策略AVED，转发节点先根据收集到的邻居节点的信息计算邻居节点的优先级，然后将优先级信息封装到广播数据包中一并广播出去，邻居节点接收到广播数据包之后判断是否应当进行转发。文献[5]提出的基于模糊逻辑的智能广播策略，以及文献[6-7]提出的基于距离的多跳广播策略，都属于基于发送者的多跳广播方案。

基于接收者的多跳广播是指由接收者自己判断是否应该转发数据包的一类多跳广播策略。例如基于概率的多跳广播、基于计数器的多跳广播。文献[8-9]提出的基于模糊逻辑的多跳广播策略FLB和BEFLAB，文献[10]提出的智能混合自适应广播策略IHAB，以及文献[11]中提出的基于计数的多跳广播方案CBBM都属于基于接收者的多跳广播策略。

文中提出的基于概率的自适应多跳广播协议PAMBP是一种基于接收者的多跳广播策略。文献 [12-16]分别提出了不同的基于概率的多跳广播方案。文献[12]针对不同的网络密度提出了一种基于计数和概率相结合的方法CAPP；文献[13]提出了一种分布式概率广播的方案DPB；文献[14]提出了一种基于车辆速度调节转发概率的多跳广播策略SAPB；文献[15]考虑了网络密度和距离的因素，提出了网络平均邻居数量Navg的概念，针对不同的网络密度，采用不同的转发概率计算公式，提出了AWPP方法；文献[16]提出了一种基于信号强度计算转发概率的跨层动态概率广播算法CDPBA，通过路由层和MAC层共享信号强度，完成路由层转发概率的计算。

1 算法模型

文中提出了一种能够根据网络环境自动调节转发概率的多跳广播协议。本协议在确定转发概率时，综合考虑网络密度、相对距离以及节点相对速度三方面的因素，另外，本协议通过动态调整不同因素在转发过程中所占的权重，以确保本协议在不同的网络环境中具有良好的适应性和稳定性。

1.1 网络建模

给出假定情景下的网络模型：

1)假设车辆的传输范围为R;

2)假设一跳范围内最大邻居节点数量为Nmax，两节点的最大相对移动速度为Vmax。

3)每辆车都会配备全球定位系统(GPS)，所以每辆车都可以随时随地知道自己的精准定位。

交通场景如图2所示。

图2 交通场景

图中，S表示源节点，R表示源节点S的通信半径。变量fi，i∈(1,2,3,…,N)表示源节点S的邻居节点，其中N表示源节点S通信范围内的邻居节点总数，节点fi与源节点S的距离用di表示。当遇到紧急情况时，源节点S将在第一时间内向传输范围内的所有邻居节点广播紧急数据包，邻居节点收到源节点发送的数据包后开始存储，但此时并不计算转发概率，邻居节点将在退避时间结束后开始计算转发概率的大小。在计算转发概率时，每个邻居节点首先要根据当前的网络状况确定网络密度ρi、距离di,以及相对速度Vi分别所占的权重，然后再计算转发概率的大小，当转发概率大于随机生成的概率时，该邻居节点获得转发权。

1.2 PAMBP系统模型

1.2.1 转发概率

文中在现有的基于概率的多跳转发方案的基础上进行改进，给出了新的转发概率计算公式，定义如下：

(1)

(2)

式中：α+β+γ=1；

N----本节点传输范围内的邻居节点数量；

d----本节点与上一跳转发节点相对距离；

V----本节点与上一跳转发节点的相对速度。

1.2.2 本地信息交互

网络中的每个节点通过周期性的广播Hello数据包进行本地信息的交互，Hello数据包携带的本地信息包括节点的MAC地址、经纬度坐标、速度和行驶方向。邻居节点接收到Hello数据包后，会更新自己的邻居列表。

邻居节点接收到Hello数据包后，根据数据包中携带的信息和下式分别计算两节点的相对距离d和相对速度V，更新自己的邻居列表信息。

(3)

式中：x1，x2，y1，y2----通过经纬度转换得到的两节点的位置坐标。

(4)

式中：V1，V2----分别为两节点的速度矢量；

c----真空下的光速。

1.2.3 权重调整

式(1)在计算转发概率时，不同的因素所占的权重是不同的，因此在计算转发概率之前，首先要确定不同因素所占的权重大小。权重的调整受当前邻居节点个数N,以及退避时间结束时节点收到的消息副本的数量C两方面的因素影响，并且，引入参数消息副本阈值Cthreshold作为确定权重调整大小的依据。具体权重调整算法如下。

首先判断条件Cthreshold

(5)

当节点接收到的消息副本的数量小于消息副本阈值时，说明网络中只有极少部分的节点完成了转发，此时，转发概率将会增大，反之，转发概率将会被抑制。

若条件不成立，说明当前网络密度较小，为了确保协议的稳定性，此时采用概率为“1”转发模式[17]，对报文进行无条件转发。

1.2.4 PAMBP协议

当车辆遭遇紧急情况时，需要以最快的速度向周围车辆广播紧急消息。为了提高广播的可靠性和稳定性，文中设计了一种基于概率的自适应多跳广播协议PAMBP，协议中涉及的变量及其初始值见表1。

表1 PAMBP协议变量

具体协议流程如下

(CWmax-CWmin)+CWmin。

(6)

1)源节点广播数据包，同时将数据包备份，并启动重播定时器(重播定时器的值设置为最大竞争窗口值CWmax)。

2)若重播定时器结束前，源节点仍没有接收到邻居节点转发的数据包，则判断最大重播次数RBmax是否为零，若RBmax≠0，源节点将重播数据包，重新设置重播定时器，并将RBmax减一，否则，源节点不再重播，并将备份数据包删除，算法结束；若重播定时器结束前，源节点收到了邻居节点转发的数据包，则不再重播，并将备份数据包删除。

3)邻居节点接收到广播数据包后，判断是否是首次接收到此数据包，若是，则执行下一步；若不是，则丢弃数据包。

4)计算退避时间，为了减少信道竞争和消息碰撞的概率，邻居节点采用式(6)计算自己的退避时间，并启动退避定时器。

5)执行权重调节算法，计算wadjust，退避时间结束后，根据式(5)计算wadjust，调整对应权重，并根据式(1)计算节点的转发概率p。

6)转发数据包，节点会生成一个随机概率P，若p≥P，则节点立即转发数据包，否则放弃转发。

2 仿真验证

2.1 实验环境

使用NS-3网络仿真模拟器来验证PAMBP的性能[18]，与SPAB和AWPP两种同样基于概率的算法作了比较。实验时，车辆节点随机分布在覆盖范围为2 km×2 km的车联网环境中，单跳范围内的节点数量在0～300之间，车辆速度在0～100 km/h之间。其他一些仿真参数设置见表2[19-20]。

表2 仿真参数设置

2.2 性能指标

2.2.1 平均副本数量

平均副本数量可以在很大程度上反应网络中的数据包冗余度，其定义如下

(7)

式中：PCi----i个节点接收到数据包的概率。

2.2.2 平均时延

标准IEEE802.11的修订版本中指出，VANET网络在PHY和MAC层采用IEEE802.11p无线协议，IEEE802.11p是基于分布式协调函数(DCF)的广播协议，DCF采用带有冲突避免的载波监听多路访问(CSMA/CA)机制来争夺信道。为了减少冲突，DCF采用信道感知来检测信道活动，并且利用截断二进制指数退避方法随机化分组传输的开始时间[20-21]。一跳平均时延可以表示为

(8)

其中

(9)

T0=Theader+Tdata+AIFSN,

(10)

式中：PC----每个时隙时间内冲突发生的概率;

T0----成功发送数据包占用的信道时间;

Ts----一个时隙;

q----最大退避指数。

3)平均消息可达率。消息可达率体现了协议的信息传播效率和可靠性，其定义如下

(11)

式中：Nr----成功接收的数据包数量；

Ns----发送的数据包总数。

2.3 仿真结果分析

为了确定系统参数的初始值，我们进行了多次实际测试，最终确定以下组合，能够确保本协议在不同的VANET环境中都具有良好的性能,见表3。

表3 系统参数

另外，前面提到本协议中转发概率的计算受到网络密度、相对距离以及相对速度三个因素的影响，但是由式(1)可知，这三种因素在对转发概率的影响方面是平行关系，不同的仅仅是影响程度。因此，在接下来的仿真结果分析中，只分析网络密度对协议性能的影响，车辆速度设置为60km/h。

网络密度对消息副本数量的影响如图3所示。

图3 平均副本数量

从图中可以看出，本协议的平均副本数量不会随着网络密度的增加而显著增大，平均副本数量维持在3个左右。这是因为文中提出的权重调节算法考虑到了消息副本的影响，当节点接收到的消息副本增加时，其转发概率就会降低，从而抑制消息副本的数量。相比CDPAB算法，本算法具有较大优势，平均副本数量低2个左右，而DPB、SPAB和AWPP算法随着网络密度的增加，平均副本数量增长较大，其中AWPP算法由于没有考虑网络密度的因素，其平均副本数量的增长趋势最为明显。

平均一跳延迟时间的仿真结果如图4所示。

图4 平均延迟时间

本协议的平均一跳延迟时间相对较低，并且随着网络密度的增大，逐渐趋于稳定。这是因为本协议提出了相应的退避等待规则，邻居节点根据自己与转发节点的相对距离和相对速度确定自己的等待时间，从而降低了信道冲突的概率。

网络密度对平均消息可达率的影响如图5所示。

图5 平均消息可达率

从图中可以看出，本协议的PDR始终保持在95%以上，并且不会随着网络密度的变化而显著改变。这是因为在本协议中，当节点接收到的消息副本数量低于消息副本阈值Cthreshold时，节点的转发概率会显著增大，从而在一定程度上确保了消息的有效传播。

3 结 语

通过仿真实验，比较了本协议与DPB、SPAB、AWPP和CDPAB四种算法在平均副本数量、平均时延以及平均消息可达率三个方面的性能，可以看出，本协议在消息副本数量、时延以及消息可达率方面都有良好的表现，并且消息副本的数量不会随着车辆密度的增大而显著增加。另外，平均消息可达率始终保持着较高的水平，说明本协议在不同网络环境中都具有良好的稳定性。