一种基于路侧装置修正的遗传VANET算法

朱 正 国

(安徽城市管理职业学院 信息技术学院, 合肥 230011)

0 前 言

车载自组网(vehicular ad-hoc network，VANET)是移动自组织网络(mobile ad-hoc network，MANET)的一个分支，车辆可以在车 — 车、车 — 基础设施模式下相互连接，或者在混合模式下进行连接[1-3]。 VANET中的路由协议分为基于拓扑的路由协议和基于地理位置的路由协议等两大类[4-5]。

基于地理位置的路由协议适用于MANET[6]。其中，GPSR是典型的基于地理位置的路由协议[7]，使用车载全球定位系统接收器获取车辆移动信息，选择距离目的地最近的车辆转发数据。首先，源车辆选择距离目的地最近的相邻车辆作为第一邻居(first neighbor，FN)；然后，FN以相同方法选取下一个FN，直到数据包到达目标节点。但由于节点运动速度较快，一旦转发失败(即无法找到适合目标节点的FN或者通过GPSR协议发现的FN由于各种原因已失效)，则会重新寻找转发邻居，从而导致吞吐量下降[8]。

Wang等人提出了一种基于预测的贪婪周边无状态路由协议，通过车辆的速度和方向来预测相邻车辆位置，直到接收到新信息[9]。袁学松提出了一种基于高速公路应用场景的邻居发现方法NDK，通过卡尔曼滤波(kalman filter，KF)理论预测节点邻居表[10]。路径感知GPSR(path aware greedy perimeter stateless routing，PA-GPSR)在邻居表中设计扩展表，选择最佳路径并绕过恢复模式下传递数据包的节点，但节点位置信息过于完美，不适合较复杂的场景[11]。Cao等人提出了一种基于模糊多因素决策(IRFMFD)的交叉口路由协议，适用于城市场景下的VANET传输[12]。为了解决VANET中高速公路场景下拓扑频繁改变而导致的车辆节点丢失等问题，提出了一种基于遗传算法(genetic algorithm,GA)的高效邻居发现方法(neighbor discovery method by genetic algorithm，NDG)。

1 预测节点下一时刻位置与邻居节点更新方案

1.1 路由节点丢失问题

使用GPSR协议时会出现中继遗失的情况[13]，双向路况通信模型如图1所示。当车辆C要和车辆E通信时，根据GPSR协议，车辆C的数据将被发送至距其最远且在通信范围内的车辆D。但在下一时刻，由于车辆E的通信范围与车辆D无交集，因此车辆C不能将数据包传输给车辆E，从而导致中继遗失。此时，车辆C需要重新寻找中继并传输数据包，网络吞吐量下降。

图1 双向路况通信模型

当车辆C进入路侧单元(RSU)的通信范围后，RSU请求与其构建拓扑。车辆C按照规定的时间间隔进行信号和拓扑检测，在接收到RSU的请求后同意构建拓扑。车辆C进入拓扑后既可以与其他车辆通信，也可以与RSU通信。当车辆C超出RSU的通信范围时，车辆C和卡车建立拓扑，卡车作为FN传输数据。

下一时刻，车辆D超出RSU的通信范围，RSU请求和车辆D断开拓扑。车辆D按照规定的时间间隔进行信号和拓扑检测，在接收到RSU的请求后同意断开拓扑。此时车辆D重新按照规定的时间间隔进行拓扑检测，发现其不在卡车的通信范围内，故向卡车发送断开拓扑的请求，卡车接受请求后，车辆D完全断开模型拓扑。

初始状态下，车辆E不在拓扑内，下一时刻车辆E通过伪基站进入拓扑，车辆节点数据传输不超过3跳。为了防范重新发现节点的不良影响，对节点通信范围内所有节点下一时刻的位置、速度、加速度和运动方位等基本信息进行实时预测。本次研究使用GA[14]对节点基本信息进行预测。

1.2 预测节点下一时刻位置

GA具有高鲁棒性和强通用性的特点，可以通过模拟自然进化过程找到最优解[15]。轨迹数据是一种多变量、多特征的数据，需要在多个变量之间找到最优解。本次研究根据车辆一段时间内的历史轨迹，使用GA建立车辆历史行为模式，以预测节点下一时刻位置。使用GA预测节点下一时刻位置的步骤如下：

(1) 基因编码：在种群初始化之前，对历史信息进行编码。每隔1 s记录1次车辆位置，车辆轨迹是染色体，车辆位置是基因。为了识别轨迹中的车辆身份，将染色体按时间顺序排列，包括车辆ID和车辆位置。T={IDi，Ai，Bi，Ci，Di，Ei，Fi}，其中IDi是车辆i的身份，Ai、Bi、Ci、Di、Ei、Fi是车辆i的历史轨迹，根据历史轨迹可以解析出车辆的速度、加速度、位置、方向等基本信息。记录t时刻的前6个轨迹，并动态清除t时刻前7个及更早的轨迹。对轨迹点使用实数编码方法，即每个轨迹点由1个基因编码，如1、2、3、4、5、6。对车辆身份使用二进制编码，如00、01、10、11等。

(2) 初始化种群：随机选择部分个体作为初始种群。

(3) 适应度函数：用于衡量个体轨迹的相似度。

(4) 个体选择：根据相似度大小，在种群中优选部分个体作为下一轮种群进化的初始成员。

(5) 基因交换：选择2个个体，按照规定的方式交换它们的一些基因，产生1个新的个体。

(6) 基因变异：基因交换完成后，存在很多个体。由于遗传的多样性，以95%的概率选择正常情况下第i个个体第j个基因(即第i条轨迹上的第j个位置)的个体，以5%的概率选择第i个个体的第j个基因突变。

(7) 确定位置：根据获得的轨迹确定最终位置。

1.3 邻居节点更新方案

本次研究仅考虑最多2跳的情况，即如果源节点直接传输或者通过1个FN将数据传输至目标节点失败，则命令源节点不传输数据至目标节点。因为当网络中存在3跳及以上时，路由寿命的陡降可能导致路由失效。

为了解决车辆计算和存储能力过载[16]等问题，采用基于GA的高效邻居发现方法(NDG，neighbor discovery method based on genetic algorithm)，在NDG中引入RSU，如图2所示。RSU放置在隔离带中间某个位置，由于 RSU的覆盖范围较广且计算能力强，因此使用RSU计算数据。RSU在NDG中起到转发数据和计算参数的作用。

图2 系统模型

车辆C发送数据给车辆E的过程包括以下3个步骤：

(1) 车辆C查询邻居表中是否存在车辆E。邻居表中包含C的邻居节点、C与邻居节点的权重。

(2) 采用NDG计算邻居节点下一时刻的基本数据。

(3) 当发现车辆D并非车辆C的邻居节点时，将数据传输给车辆C邻居表中下一时刻方向相同的邻居节点中权重最大的车辆B。

源节点2跳范围内的邻居车辆数、源节点t时刻的速度和最高时速等因素影响着通信质量。车辆在选择FN的权重如式(1)所示：

(1)

式中：Wi—— 车辆i的权重；

Ni—— 车辆i在2跳范围内的邻居车辆数，Ni=min(Ni,10)；

vm—— 高速公路的最高限速，vm=120 km/h；

vi—— 车辆i的速度；

a—— 邻居影响比例；

b—— 车速影响比例。

其中：

(2)

FN的选择过程如图3所示，主要包括以下3个步骤：

图3 FN的选择过程

(1) 车辆向RSU发送传输数据的请求，RSU命令车辆反馈ID号、位置、车速、方向、通信范围和半径等基本信息。

(2) RSU判断源车辆是否在其通信范围内，如果不在则计算其通信范围内的车辆权重，并建立邻居表。

(3) 选取源车辆通信范围内权重最小的车辆作为FN，如果权重相同，则选取ID号较小的车辆作为FN。

1.4 NDG流程介绍

NDG流程如图4所示，主要包括以下8个步骤：

图4 NDG流程

(1) 源车辆向RSU发送传输数据的请求；

(2) RSU收集车辆基本信息；

(3) RSU使用GA预测下一时刻车辆轨迹；

(4) 计算RSU和车辆的距离d1；

(5) 如果d1≥RRSU+RV(RRSU为RSU的通信半径，RV为车辆的通信半径)，则RSU选择FN，调取FN的通信半径RFN，计算车辆和FN的距离d2；

(6) 如果d2

(7) 如果d2≥RBN+RV，则不构建拓扑；

(8) 如果d1

2 仿真结果分析

假设全部车辆均安装了定位装置(如GPS、BDNSS等)，且车辆和RSU的通信范围均是标准的圆。同时，车辆可以通过车载装置获得基本数据，如车辆的准确位置、速度、ID号、加速度和运动方向等[17]。为了确保仿真实验的真实性，对FL-QN[14]和GPSR-2P进行仿真实验，在Matlab2020仿真平台上生成一段10 km×30 m的车道模型，车道为高速公路场景下双向8车道，每隔2 km设置一个通信范围为500 m的RSU。仿真参数说明如表1所示。选取数据包传递率(PDR)、端到端延迟(EED)、吞吐量等指标进行仿真实验[18]。

表1 仿真参数说明

(1) PDR。源车辆传输的数据包数量与正确传输给目标车辆的数据包数量的比率。PDR的计算如式(3)所示：

(3)

式中：RPD—— PDR；

PR—— 接收到的数据包数量；

PS—— 发送的数据包数量。

(2) EED。相同数据流的所有数据包到达目的地的平均时间。EED的计算如式(4)所示：

(4)

式中：n—— 数据包数量；

TR,i—— 数据包i的接收时间；

TS,i—— 数据包i的发送时间。

(3) 吞吐量。单位时间内路由协议在网络中传输的信息量。吞吐量的计算如式(5)所示：

(5)

式中：PT—— 吞吐量。

由PDR仿真实验结果(见图5)可知，相较于FL-QN和GPSR-2P，NDG的PDR最大，且稳定在90%以上。这是因为NDG使用了GA预测节点下一时刻位置，并利用中继、RSU来辅助数据传输。

图5 PDR仿真实验结果

由EED仿真实验结果(见图6)可知，相较于FL-QN和GPSR-2P，NDG的EED最小。这是因为GPSR-2P选择2条路径来发送相同的数据包，增加了延迟时间和重复数据包的数量；FL-QN未对FN进行修正，会在稀疏场景中重新发现邻居，导致路由数据包不断重发，进而增加了EED。

图6 EED仿真实验结果

由吞吐量仿真实验结果(见图7)可知，3种算法的吞吐量都随着车辆密度的增加而增加，但相较于FL-QN和GPSR-2P，NDG的吞吐量最大。这是因为GPSR-2P选择2条路径来发送相同的数据包，增加了接收时间与发送时间差；而FL-QN未对FN进行修正，会在稀疏场景中重新发现邻居，导致路由数据包不断重发，进而降低了吞吐量。

图7 吞吐量仿真实验结果

3 结 语

VANET是MANET的一个分支，已被广泛应用于各个领域中。本次研究针对高速公路场景下数据传输的问题，提出了基于GA的高效邻居发现方法。当车辆进入RSU通信范围内时，利用RSU估算车辆下一时刻位置。RSU根据权重大小选择最佳邻居、计算最优路由方式，将最佳邻居和路由信息发送给车辆。仿真实验结果表明，本算法在不同的节点密度下均优于FL-QN和GPSR-2P。