优化遗传算法的车联网计算卸载*

顾佳赛，江凌云

（南京邮电大学，江苏 南京 210003）

0 引言

在智能驾驶快速发展的推动下，引入车载环境的应用数量不断增加，要为这些应用提供计算支持，车辆本身必须具备更高的计算能力。由于传统的云计算在车辆终端的计算能力有限，因此无法满足低时延、低能耗的需求，而边缘计算的出现解决了这一问题，满足了低时延、低能耗的需求。用户终端的计算任务如何做出最合理的计算卸载决策，使边缘网络发挥最佳的作用，是当今边缘计算的一个主要的研究方向。

在车联网边缘计算中，计算卸载[1]是一项关键的技术，合理地计算卸载决策有益于降低计算时延，节约能耗。对于移动边缘计算中的任务卸载，当计算任务卸载到边缘设备上时，需要为计算任务分配计算资源。计算卸载主要分为计算卸载策略[2]、多接入边缘计算（Multi-Access Edge Computing，MEC）内的计算资源分配[3]以及移动性管理[4]3 个关键领域。在未来的车联网环境中，一个完整的车联网计算任务可以被拆分成K个子任务，这些子任务可以分别选择不同的计算卸载策略进行计算卸载，由多种卸载策略协同完成车联网计算任务。本文提出了本地卸载策略、MEC 多跳卸载策略、车与车通信（Vehicle-to-Vehicle，V2V）辅助回传卸载策略这3 种卸载策略，并在此基础上提出了优化的遗传算法以解决子任务的计算卸载策略分配问题。

1 相关工作

在移动边缘计算中，车联网计算卸载作为一项重要的技术，已有许多国内外专家对其进行了深入研究。Huang 等人[5]提出了一种将蜂窝网络中的车辆通信流量卸载到车辆自组网络中可能存在的V2V路径的思路和控制方案，以解决车用移动通信网络（Vehicular Ad-hoc Network，VANET）卸载的复杂问题；但是，该方案仅适用于车辆密度适中的情况。Debnath 等人[6]提出了一个动态协作的计算卸载框架CASINO，CASINO 可以显著改善计算延迟；但是，该框架无法发挥多节点并行能力，对时延的改善有限。Zhang 等人[7]提出了带预测性的V2V 卸载算法，预测任务完成时车辆的位置，即将计算任务输入数据通过V2V 方式前向传播至前方MEC 服务器进行执行，但是V2V 预测性计算卸载不能承载数量较多的任务，局限性太大，无法满足车联网业务的稳定性的需求。

本文结合车辆本身的计算能力以及V2V 通信[8]，基于车辆计算任务可拆分[9]的前提，考虑多策略协同处理车辆应用的各个子任务，合理利用了车辆的计算资源以及传输能力，以本地卸载策略、直接卸载策略、V2V 辅助回传策略协同完成计算任务，旨在降低任务卸载的时间延迟与能耗，得到时延和能耗最低的任务卸载策略。

2 系统模型

车联网计算卸载场景建模如图1 所示，所有路边单元等距离分布，并且与MEC 服务器通过有线的电缆连接，因此认为MEC 服务器与路边单元之间的通信带宽是无限大的，所以路边单元与MEC服务器的传输时间可忽略不计。并且由于MEC 服务器一直保持接电状态，故忽略MEC 服务器计算和传输任务时所产生的能耗。每辆车只能在MEC服务器覆盖范围内才能与其进行数据传输。

图1 车联网网络拓扑

Z为车辆应用发起计算卸载时，路边单元所覆盖的范围与车辆后方之间的距离。从车辆开始进行计算任务卸载起在当前路边单元范围内的停留时间t为：

定义为一个Pi=(χi,μi,ηi)计算任务，其中，χi表示任务计算量大小，该参数影响业务计算的时间；μi表示任务数据量，该参数影响任务传输的时间；ηi表示任务计算结果的数据量大小。定义车辆发起的计算任务为Pi，车速为v。定义Ec为车辆的计算能力，Emec为MEC 服务器的计算能力，Rv2i为车辆向MEC 服务器数据上传的速率，Ri2v为MEC 服务器向车辆计算结果回传的速率，Rv2v为车辆通信时的信息传输速率，t0为跳数。

定义车辆的计算任务卸载执行一共有3 种策略：

（1）本地计算策略；

（2）直接卸载策略；

（3）V2V 辅助回传卸载策略。

定义卸载决策矩阵J=(-1,0,1)，-1 表示车辆选择本地卸载策略，0 表示车辆选择直接卸载策略，1表示车辆选择V2V 辅助回传卸载策略。

定义时延矩阵Yn·3，yij表示车辆的任务i采用决策方式j计算卸载的执行时延。

定义能耗矩阵en·3，eij表示任务i采用决策方式j计算卸载的执行能耗。

2.1 车辆本地计算策略

对于这一类任务，计算卸载时延只与车辆的计算能力Ec有关，故时延可以表示为：

能量消耗为任务执行时本地车载单元CPU 的能量消耗，其计算方式为：

式中：Pc为车载单元的计算功率。

2.2 直接卸载策略

车辆在MEC 服务器的执行主要由计算数据上传、MEC 服务器执行计算、数据回传[10]3 部分组成，因此卸载时延主要由车辆经过多个RSU 覆盖范围引起的多跳传输时间组成。

对于车辆i，直接卸载任务时延可以表示为：

直接卸载任务能耗可以表示为：

式中：Pco为车辆终端的发射功率；Pci为车辆的接收功率。当任务量大，所需的计算时间比较长，或者当车速比较快时，车辆已经脱离了其进行计算卸载的MEC 服务器的多跳范围，需要MEC 服务器之间进行多跳传输将结果回传到车辆，则有：

2.3 V2V 辅助回传策略

在C-V2X 中，V2V 的作用极为关键。顾名思义，V2V 表示车辆与车辆之间的信息传输。由于现代车联网技术的飞速发展，车辆自身携带的OBU 的计算能力越来越强。虽然远不能和MEC 服务器相比，但是对于一些计算量较小的车联网计算任务，或者计算量较大的计算任务中的一小部分，完全能够将V2V 通信利用起来，缓解RSU 面临的计算压力。因此，本节提出V2V 辅助回传策略，如图2 所示，旨在充分利用车联网计算卸载中车辆的计算能力，以V2V 辅助回传的方式代替MEC 服务器回程链路之间的多跳传输，缓解MEC 服务器的压力，降低整个计算卸载过程的时延与能耗。

图2 V2V 辅助回传策略

当车辆生成任务时，它通过车道基础设施（Vehicle to Infrastructure，V2I）将任务数据上传到其范围内的MEC 服务器。当MEC 服务器收到来自车辆的计算任务后，首先对计算资源进行分配，其次对计算任务进行计算。如果上述过程完成后任务车辆仍在其进行计算卸载的边缘计算服务器的覆盖范围内，则结果数据通过MEC 服务器直接传回该车辆。如果任务车辆已经驶出了其进行计算卸载的MEC 服务器的覆盖范围，则首先将数据传输到其覆盖范围内的车辆，其次通过多跳V2V 将数据多跳传输回传至任务车辆。

计算卸载的时延可以表示为：

计算卸载的能耗可以表示为：

2.4 总代价

定义决策矩阵Mn·3，mij表示任务i选择第j种决策方式[11]，则有：

对于决策矩阵Mn·3中的任意一行，有即任一子任务只能选择一种计算卸载策略。目标是寻找最佳的子任务卸载策略，使时延与能耗的总代价最低。

时延代价模型为：

能耗代价模型为：

定义总代价为：

式中：α和β为时延代价与能耗代价的权重系数。

3 GAC 算法

3.1 编码与初始种群选择

遗传算法[12]将解的概念表示为一个染色体个体，确定编码方式和个体长度后，从初代种群开始，通过精英选择策略[13]和染色体交叉变异等一系列过程得到新一代的种群。所提的多卸载策略协同的模型中，单个车联网计算任务由K个子任务所组成，所以设置在遗传算法中每条染色体由K个基因组成。每个子任务可以选择本地卸载、直接卸载或者V2V 辅助回传卸载策略。因此每个基因均有-1，0，1 这3 种可能。如图3 所示，这是一个由K个基因构成的染色体集合。

图3由K 个基因组成的染色体

考虑到子任务卸载的前后关系，对卸载策略加以部分限制，第一个子任务与最后一个子任务默认执行车辆本地卸载策略，生成初始种群，初始种群规模为M。

3.2 适应度函数

适应度函数[14]是评估算法性能的函数，本文的优化目标是任务卸载中的时延和能耗，时延和能耗的总开销定义为W(X)，适应度函数的值随着总开销减小而变大。将适应度函数表示为：

式（14）中对分母加1 是为了避免分母为0 的情况发生。

在每一次的迭代进化中，采用了精英选择策略，精英选择策略是将每一代最优解直接复制到下一代，目的是防止进化中产生的最优解被交叉和变异破坏。针对精英选择策略做了一些改进，具体操作如下：

（1）对于第K代种群Ck，求出其所有染色体矩阵对应的适应度函数最大值，记为fitness。

（2）根据轮盘赌策略[15]生成第K代种群Ck+1,求出所有个体对应的适应函数的最大值，记为fk+1。

（3）针对遗传算法的精英选择策略容易陷入局部最优的缺点，对遗传算法的精英选择策略做了一些改进。比较第K代种群和第K+1 代种群的适应度函数最大值，如果fk≥fk+1，即第K代种群中所有适应度大于或等于fk+1的染色体复制，将所复制的染色体数记为N,同时随机生成相同数量的N个随机染色体，将其作为父母染色体，通过交叉变异流程生成子代，然后将生成的子代染色体复制并且替换第K+1 代种群中相同个数的染色体。传统精英选择策略则是将第K代种群中所有适应度大于等于fk+1的染色体复制，并替换第K+1 代种群中相同个数的染色体，容易使局部最优个体不断被保留，因此无法淘汰并快速扩散，进而陷入局部最优解。改进后的方法可以对比更多的卸载方案，在防止过早陷入局部最优的基础上，最大限度地保持最优解的继承性。

3.3 染色体交叉

染色体交叉是对除了精英选择的百分之二十的个体以外的较差的染色体进行交叉，交叉的过程中，在父辈染色体之间随机设置一个交叉点，以交叉点交换两个父辈染色体的基因，生成新的染色体。

3.4 染色体变异

染色体变异从遗传的角度来说就是基因突变。设置基因突变的概率，根据突变概率随机改变染色体的某些基因的值，生成新的染色体。染色体变异概率由3.5 节的控制变量法得到。

3.5 终止条件

通过上述流程得到新一代染色体种群，根据适应度函数计算新一代染色体种群的适应度值。如果在连续5 次迭代中，适应度函数的值都没有得到改进，则达到终止条件，GAC 算法结束；若未达到终止条件，则重复上述迭代进化过程，直至满足算法的终止条件。

4 结果仿真

在本节中，将在Windows10 系统下使用MATLAB R2021b 工具对所提出的算法进行仿真实验并加以分析。

4.1 参数设置

仿真的场景包括1 辆车、多个MEC 服务器和1 个车辆计算任务（10 个子任务），假设所有MEC服务器的性能完全一致，仿真实验的部分参数如表1 所示。

表1 仿真实验部分参数

4.2 结果分析

遗传算法中染色体变异概率对算法的性能影响较大，为了使算法性能得到最佳体现，需要得到最佳的染色体变异概率参数以及迭代次数。故使用控制变量法研究染色体变异概率对于计算卸载总代价的影响，结果如图4 所示。将初始的种群规模设置为100，同时将迭代次数设置为100，染色体变异概率为[0,0.2]。从图4 中可以分析得出，染色体变异概率在0.038 时，总代价为最小值，因此在下面的仿真实验中将染色体变异的概率设置为0.038。

图4 染色体变异概率对总代价的影响

图5 展示了遗传算法迭代次数对于算法总代价的影响。将初始种群的规模设置为100，染色体变异概率设置为0.038，时延权重系数与能耗权重系数均设置为0.5，将迭代次数设置为[1,100]。从图5可以看出，当迭代次数不断增加时，总代价不断降低，当迭代次数超过80 次后，总代价趋于平稳。

图5 迭代次数对总代价的影响

根据上述两个实验的结果，将染色体变异概率与迭代次数分别设置为0.038 与80，将初始种群数量设置为100 进行下面的实验。为了更准确地评估算法的性能，将GAC 方案与以下几种方案进行对比。

（1）车辆本地卸载方案（Local）：所有子任务均在车辆本地卸载。

（2）直接卸载方案（Edge）：所有子任务均卸载到MEC 服务器上执行。

（3）普通遗传方案（Genetic Algorithm，GA）：使用经典遗传算法的方案进行子任务卸载策略的分配。

对比结果如图6、图7、图8 所示。图6 将权重系数α，β设置为0，1，图7 将权重系数α，β设置为1，0，图8 将权重系数α，β设置为0.5，0.5。分别代表了迭代次数在[0,100]变化时对能耗代价的影响、对时延代价的影响和对时延能耗代价的影响。

图6 迭代次数对能耗代价的影响

图7 迭代次数对时延代价的影响

图8 迭代次数对时延能耗代价的影响

随着迭代次数的增加，GA 方案与GAC 方案均优于Local 与Edge 方案，同时与GAC 方案相比，GA 方案收敛更快，原因是传统精英选择策略容易使得某个局部最优个体不易被淘汰而快速扩散，从而陷入局部最优解。而GAC 方案通过改进精英选择策略，使遗传算法不会过快收敛而陷入局部最优解，在防止了过早陷入局部最优的基础上，最大限度地保持最优解的继承性，从而降低了时延与能耗的代价。

综上，GAC 算法可以有效降低车联网计算卸载过程中时延与能耗的代价，算法的性能更优。

5 结语

为了满足5G 时代车联网车载终端资源短缺问题，考虑了未来车联网场景中的应用普遍采用分布式卸载的方式，提出了V2V 辅助回传策略。

以本地卸载策略、直接卸载策略、V2V 辅助回传策略3 种策略协同完成车联网的计算任务。为了得到时延能耗最低的子任务卸载策略，本文基于遗传算法提出了GAC 算法，通过改进经典遗传算法中的编码方式以及精英选择策略，使得遗传算法不易过快收敛而陷入局部最优解，在最大限度保持最优解的继承性的基础上，对比更多的卸载策略，从而得到时延和能耗均最低的子任务卸载策略的分配方式。基于车联网应用，各子任务间可能存在一些相互依赖的关系，下一步工作将考虑在车辆行驶过程中，车辆应用子任务之间的依赖关系，从而得到更加准确的卸载策略。