基于GAPSO-ANFIS的VANET路由性能推理系统

师亚莉，黄 楠，杨军华，杨 志

(西安邮电大学 电子工程学院，陕西 西安 710121)

车辆自组织网络(Vehicular Ad-Hoc Network，VANET)是智能交通体系中车间通信的一种移动性自组织网络，具有无中心、自组织及多跳等特点[1]。作为VANET网络关键技术之一的路由技术，主要负责信息传输通道的优化，而VANET通信的拓扑结构变化频繁、节点移动性高和链路生存时间短等特点，使得车辆节点在市区和郊区来回切换时对VANET路由性能的质量影响较大[2]，VANET应用的多样性和场景的多变性使得单一路由机制不再适用。因此，良好的路由协议可以保障网络互通性和通信的稳健性[3]。

VANET中有很多路由协议用来稳定和高效地传递消息。文献[4]对VANET路由协议在不同网络场景中的性能表现进行了研究，结果显示，主动式路由协议和被动式路由协议在不同场景下性能差异较大，表明了选取最优路由机制的必要性，但文献中并没有对选取最优路由协议进一步研究。为了使不同机制的VANET路由协议能在适用的场景中发挥最大性能，路由机制选择中引入了自适应策略，试图通过推理为当前网络环境匹配最适合的路由机制，从而增强网络通信质量。

文献[5]提出了一种自适应的路由算法。该算法可以根据网络的移动性推理当前适配的路由机制，然后根据推理的结果在主动式路由机制和被动式路由机制中进行切换，这种方式有利于同时结合两种路由机制的优点，提高网络效率。在文献[6]中提出的一种自适应路由机制中，由基站基于网络能量和负载对当前的路由机制进行管理，实现了自适应路由机制的切换。吕双玥[7]提出了自适应组播路由协议选择算法，该算法在自适应模糊神经推理算法(Adaptive Neuro-Fuzzy Inference System，ANFIS)的基础上提出了一种改进型算法，并将其用于路由协议选择策略库中，实现了不同场景中最优组播路由协议的选取。文献[8]将ANFIS应用于VANET网络中交叉路口场景下的路由选择，利用网络特征对最优路由进行推导，进一步提高了网络的整体性能，但仅考虑了车辆在交叉路口时的路由选择情况，无法满足车辆在实际场景中面临的多种场景。

在以上车联网场景自适应路由的研究中，通过自适应模糊神经推理算法进行最优路由协议选择的方法，由于其参数学习的复杂性与易陷入局部最优等缺点并不能满足客观需要[9]。因此，基于遗传粒子群算法的自适应模糊推理系统(Genetic Algorithm Particle Swarm Optimization Adaptive Neuro-Fuzzy Inference System，GAPSO-ANFIS)，拟提出一种VANET路由性能推理系统。该系统通过研究ANFIS的参数优化问题，结合遗传算法(Genetic Algorithm，GA)进行粒子群全局寻优，从而搭建最优路由机制推理系统。同时，对该系统在节点密度和节点速度变化时几种典型路由协议的性能建模进行分析。最后，为了进一步验证所提的改进型VANET路由性能推理系统的有效性，在按需距离矢量路由协议(Ad hoc On-Demand Distance Vector Routing，AODV)、目的序列距离矢量路由协议(Destination Sequenced Distance-Vector，DSDV)及动态源路由协议(Dynamic Source Routing，DSR)等3种典型VANET路由协议仿真数据集下，利用所提系统进行最优路由协议推理验证。

1 基于ANFIS的路由策略推理

VANET网络的场景因素对路由协议的性能具有重要影响。在不同的网络场景中，路由协议往往会表现出截然不同的性能[10]。因此，根据路由协议在不同网络场景中的性能表现，可以推理得到不同用户需求下的最优路由协议。在VANET网络中，影响路由协议性能的主要参数有网络节点的移动性和网络节点规模[11]，通过对这两个参数进行设计可以得到最优的路由选择。考虑ANFIS中的参数结构太过复杂，同时其参数调整过程中采用的最小二乘法和梯度下降法很容易得到局部最优解[12-14]。因此，针对ANFIS中的参数复杂、运算量大等问题，提出了改进后的ANFIS算法。该算法在改进过程中通过粒子群算法对ANFIS参数进行了寻优，同时还结合遗传算法中的交叉、变异等操作，进一步避免了粒子群算法早熟的问题。以该算法为基础提出的路由策略推理系统如图1所示。

图1 路由策略推理系统

由图1可以看出，路由策略推理方案主要包含网络情景感知、模糊神经网络推理算法和最优路由协议选择等3部分。首先，由网络情景感知模块对当前VANET网络中的节点移动速度和网络规模进行感知，并将感知结果以及备选路由协议的性能数据集作为改进后的模糊神经网络推理算法的输入。其次，由改进后的GAPSO-ANFIS分别对不同路由协议下的性能指标进行推理,得到吞吐量、时延和丢包率等性能指标，再通过效用值函数得到各性能指标的效用值，将效用值和不同用户需求下的目标函数相结合，可以得到各备选路由协议的总效用值。最后，选择效用值最大的备选路由协议，就可以实现最优路由协议的选择。

2 自适应模糊神经推理算法的优化

2.1 粒子群遗传算法

综合两种算法的优势，将GA中的遗传、交叉和变异等操作引入到PSO算法中，提出了GAPSO-ANFIS，粒子群算法和遗传算法的结合原理如图2所示。在PSO算法每一次迭代生成粒子群后，GAPSO-ANFIS都会按照粒子的适应度值对粒子群中每个粒子进行优劣性排序，将排序属于前半部分的粒子作为优质粒子，直接用于下一代。然后对剩下的一半粒子进行遗传算法中的选择、交叉和变异操作。将操作后的粒子与操作前的粒子进行排序，再次选出较优粒子与优质粒子结合起来形成新一代种群，并继续下一步运算。

图2 粒子群遗传算法结合原理

2.2 ANFIS优化

智能算法适合用于解决那些无法建立有效模型的问题[18]。为了改善ANFIS算法参数学习复杂、运算量大等问题，提出了GAPSO-ANFIS，首先，在PSO算法中，各粒子都具有记忆存储能力，能对个体和种群的最优粒子位置信息进行保留，局部的寻优能力更强，收敛速度更快，利用PSO调整ANFIS参数，可以获得最优参数值。GA拥有全局搜索能力，其交叉和变异操作既能进行信息交换又能增加粒子种群的多样性，避免迭代过程中出现局部最优解。GAPSO-ANFIS流程如图3所示。

图3 GAPSO-ANFIS流程

GAPSO-ANFIS具体的步骤如下。

步骤1首先，对种群的规模m、粒子运动的最大速度vmax和最大迭代次数参数T等参数进行初始化。

步骤3按照该优化问题对应的目标函数计算每个粒子的适应度值，采用均方根误差(Root-Mean-Square Error，RMSE)作为目标函数，表达式为[19]

大家都知道一讲到底的授课方式效果不好，却难以改变。我们曾做过调查，课堂讲授的方式，教师教得太辛苦，学生也不愿意听，想让学生参与到课堂中来，学生碍于情面和习惯，参与意愿不强。学生对这样一种教学方式也不满意，认为这样的教学方式剥夺了自己的学习自主权，而且长时间听讲做到一直集中精力几乎不可能，再生动的讲解听久了也会让人疲劳。学生希望教师能够设计一些让他们参与其中的教学环节。既然教师与学生都有交流互动的需要，那为什么交流互动难以实施呢？

(1)

式中：yi和ydi分别表示网络的输出值和输出期望值；N为数据总量。

步骤4判断当前适应度值是否小于之前的个体最优解Pbest，若小于之前的Pbest，则表示该粒子更优，可以使用该粒子对之前的个体最优值进行替换。同时，对将该粒子的Pbest与其他粒子的Pbest进行对比，选出全局最优解Gbest。

步骤5对粒子当前的位置以及速度进行修正，并对每个粒子的最大移动范围pmax和最大移动速度vmax进行限制。

步骤6计算当前粒子所对应的适应度值，并根据所得到的数值对粒子种群进行排序。

步骤7通过对粒子种群进行筛选，从中选出较优的前一半粒子作为优质粒子进入下一代，然后再对后一半粒子执行GA中的选择、交叉及变异等操作。

步骤8在GA操作之后，得到较优的粒子，将其与上一步选出的优质粒子进行合并，产生新的粒子群。

步骤9分别重新计算当前粒子群中的Pbest和Gbest。

步骤10判断当前得到的最优解是否达到目标，或是否达到最大迭代次数：若达到，则转到步骤11；否则，对其迭代次数加1并转至步骤5。

步骤11通过步骤10得到全局最优值Gbest，将其作为ANFIS最优参数值，并使用测试数据集进行测试。

在对算法进行对比时，常用的评价指标分别是RMSE、平均绝对误差(Mean Absolute Error，MAE)和判定系数R2等指标。通常可以根据R2的值判断模型的好坏：如果其结果为0，则说明该模型的拟合效果很差；如果其结果接近于1，则说明模型几乎没有错误。MAE[20]和R2[21]的表达式分别为

(2)

(3)

3 数值分析

3.1 最优路由策略库构建

采用交通仿真软件(Simulation of Urban Mobility，SUMO)和网络仿真软件(Network Simulator version 2，NS 2)进行联合仿真，所使用的实际道路场景移动模型如图4所示。

图4 实际道路场景移动模型

由图4可以看出，改变图4中的车辆数量以及车辆移动速度，可以构建出VANET网络中的多个网络场景，记录不同场景下的按需距离矢量路由协议(Ad-hoc On-Demand Distance Vector Routing，AODV)、目的序列距离矢量路由协议(Destination Sequenced Distance-Vector，DSDV)及动态源路由协议(Dynamic Source Routing，DSR)等3种备用路由协议的性能表现，构成策略知识库。网络中的数据业务特性通常可以使用吞吐量、时延和丢包率刻画，在不同网络场景下得到的数据集属性如表1所示。

表1 数据集属性

以数据集中的吞吐量为例，VANET网络中各协议的吞吐量在AODV、DSDV及DSR等不同场景下的变化情况如图5(a)到图5(c)所示。

图5 吞吐量变化情况

由图5可以看出，图5(a)展示了 AODV在不同场景下的吞吐量变化情况。该协议在节点速度较低、节点数目中等的情况下吞吐量性能值约为510 Kb·s-1，表现较好，这是由于AODV是被动式路由协议，维护的路由信息较少，并且会周期性地进行路由发现以确保当前路由信息的更新。图5(b)展示了DSDV的吞吐量变化情况，该协议在节点数目较多、节点速度较低时表现最好，吞吐量性能值约为 550 Kb·s-1，原因在于DSDV是主动式路由协议，在连接数变化时路由开销几乎不会增加，而另外两种被动式路由协议在通信密度增加时，频繁进行路由发现，导致吞吐量降低。图5(c)是DSR的吞吐量变化情况，该协议在节点数目较少、节点速度较低时，性能表现最好，约为530 Kb·s-1，主要原因在于DSR对路由信息进行缓存，使得源节点保存了多条通往目的节点的路由路径，减少了路由发现的次数，从而减少了路由发现的开销。

由以上分析可以看出，不同的路由协议在不同网络场景下的性能表现差别明显，每种路由协议都有其适用的场景。因此，通过所提的自适应最优路由协议选择方法，选出与目前的网络场景最适配的路由协议，就可以进一步保障该场景下的路由性能。

3.2 实验参数设置

将均方根误差RMSE设为适应度函数，使用得到的数据集进行仿真，对所提出的模糊推理模型的准确性进行验证。对数据集采用随机划分的方式，选出80%的数据作为GAPSO-ANFIS网络的训练数据，其余数据用于网络测试。GAPSO-ANFIS网络建模过程中所用到的一些参数初始值如表2所示。仿真过程中为了测试误差是否满足精度要求，分别对每个数据集进行了100次实验，进而计算出对应评价指标的均值。

表2 GAPSO-ANFIS参数

首先，需要对种群规模进行设定，该数值的大小直接影响到粒子的全局搜索能力。该数值越大，种群中各个体的搜索能力就越强。但是，搜索能力强的同时，也存在着一定问题，种群规模大就会导致整体搜索的时间更长，无法快速得到最优解。因此，种群规模M一般取值范围为[20,40]。其次，还需要对学习因子的大小进行设定。该数值的大小与种群进行局部搜索的能力相关，该值越大，种群进行局部搜索的能力就会越强，c1，c2的取值范围一般为[0,4]。另外，还需要对惯性权重进行设置，该值的大小决定了种群对解的探索能力，该值越大，种群对于全局的搜索能力就越强，ω的取值范围一般为[0.9,1.2]。交叉概率Pc的取值范围一般为0.40～0.99，变异概率Pm的取值范围一般为0.000 1～0.1。文献[19]通过对比验证给出了Pc和Pm更准确的取值范围，据此将交叉概率Pc和变异概率Pm分别设为0.90和0.01，在保证个体种群多样性的同时，也避免了搜索过程过于缓慢。

3.3 性能对比

为验证所提的GAPSO-ANFIS的可靠性，对表1给出的数据集进行分析，参照其中的节点数目和节点移动性，将其作为初始参数值并输入算法程序，基于初始化函数视角对网络进行初始化操作。同时，GAPSO算法使用遗传运算符选择初始群体，使用适度函数确定遗传过程的质量，获得全局优化位置。进而完成ANFIS算法的参数寻优，并由此模型进行吞吐量预测。基于以上两种算法的VANET路由性能推理系统得到的预测数据与实际数据对比情况如图6所示。由图6可以看出，通过与实际输出比较，实际输出结果与基于改进型ANFIS的推理系统结果更加贴合，推理误差更小，直观地说明了所提系统的合理性和有效性。

图6 预测数据与实际数据对比情况

为进一步验证所提系统的准确性，还将其与基于ANFIS、PSO-ANFIS的推理系统就相对误差指标进行了对比，结果如图7所示。

图7 相对误差对比

由图7可以看出，从误差对比情况看，所提系统的相对误差明显较ANFIS和PSO-ANFIS更接近于0，其预测性能能够满足路由性能参数推理的准确性要求。

采用式(1)至式(3)对基于ANFIS、PSO-ANFIS和GAPSO-ANFIS的VANET推理系统性能进行了对比，对比结果如表3所示。

表3 算法性能对比

由表3可以看出，GAPSO-ANFIS经过改进后能够自适应得到最优参数，整体性能稳定。与基于ANFIS(RMSE为12.751 4，MAE为10.377 9，R2为0.826 4)的推理系统相比，基于GAPSO-ANFIS(RMSE为6.061 8，MAE为4.847 2，R2为0.909 7)的推理系统性能更优。同时，基于GAPSO-ANFIS的推理系统性能还优于仅使用粒子群算法优化的PSO-ANFIS(RMSE为8.542 7，MAE为6.942 9，R2为0.886 2)。

4 结语

以车联网城市场景为背景，针对VANET网络不同场景中路由机制的适配问题，提出了在参数寻优过程中采用粒子群遗传融合算法的VANET路由性能推理系统。该系统通过引进粒子群算法和遗传算法，在改进型ANFIS的基础上，设计了VANET最优路由机制推理系统，可以改善ANFIS所面临的参数复杂、运算量大等问题。

通过效用函数对网络最优路由机制进行推理，在AODV、DSDV和DSR等3种典型的VANET路由协议仿真数据集下，对基于改进型ANFIS的VANET路由性能推理系统进行了最优路由协议推理验证。验证结果显示，基于改进型ANFIS的系统R2值为0.909 7，基于ANFIS的系统R2值为0.826 4，证明改进后的VANET路由性能推理系统拟合效果更优。同时，基于改进型ANFIS的VANET路由性能推理系统的RMSE为6.061 8，MAE为6.942 9，均低于基于ANFIS算法的推理系统，也说明该改进算法在准确性方面表现更优。以上分析结果表明，改进型ANFIS的VANET最优路由推理系统具有可靠性高、误差小等特点，在VANET网络最优路由协议选择方面具有更高的准确性。