丛玉良，孙闻晞，薛科，钱志鸿，陈绵书

（1.吉林大学通信工程学院，吉林 长春 130012；2.中国科学院长春光学精密机械与物理研究所，吉林 长春 130012）

0 引言

随着智能汽车和无线通信的快速发展，车联网中出现了许多先进应用，如自动驾驶和视频辅助实时导航等。这些应用程序的实现需要强大的计算能力来管理各种计算密集且对时延敏感的任务[1-2]。为了解决车辆终端计算能力等问题，移动边缘计算（MEC,mobile edge computing）被认为是一种很有前途的范例[3]。有了MEC，车辆的计算任务通过无线链路上传到MEC 服务器上计算[4]，可以减少本地计算时延。然而，随着越来越多的任务被转发到MEC 服务器，由于无线和计算资源有限，MEC 服务器将承受巨大压力，这将导致车辆的高时延和低可靠性。面对多车多服务器的场景，合理的任务卸载决策和计算资源分配值得研究。

车联网任务卸载决策主要解决的是终端是否将任务卸载至服务器，以及卸载多少的问题，是一个典型的0-1 整数规划问题。近年来，遗传算法因其具有全局优化性、简单性及稳健性等特点，得到了许多学者的青睐。余翔等[5]面对移动边缘计算的车联网场景，考虑并发多个优先级不同的计算任务，提出了一种基于遗传算法的任务卸载策略。邓添等[6]提出了一种在多信道环绕下的任务卸载模型，并采用遗传算法来求解。高基旭等[7]考虑了本地、边缘服务器和云端协同计算的任务卸载模型，提出了一种基于遗传算法的求解方案，从而得到同时考虑时延和能耗的最小系统代价。但是上述文献均没有对基本的遗传算法进行改进，传统的遗传算法后期易出现早熟现象且寻优能力无法达到理想效果。并且上述文献只考虑了任务卸载决策这一个问题，未对MEC 的计算资源进行优化。

Zhao 等[8]在云辅助的情况下，通过联合优化任务卸载决策和计算资源分配，建立了以系统效用最大化的优化问题，提出了一种分布式计算卸载和资源分配算法。Yang 等[9]研究了车载边缘计算网络中高效的任务卸载策略。车辆以最佳方式执行卸载时间选择、通信和计算资源分配，并考虑车辆的移动性和任务的最大时延。梁颖杰等[10]提出了一种基于MEC 和任务优先级的智能卸载策略以降低由时延所组成的系统总成本，并根据任务优先级对任务卸载位置进行选择。

文献[8-10]虽同时考虑了任务卸载决策和资源分配2 个因素，但均只考虑了时延这一个指标。近几年来，能源短缺正成为限制车联网发展的一个关键障碍。根据统计数据[11]，在不断增长的能源需求中，电力占16.5%，传统可再生能源占11.9%，煤炭占6.4%，而化石燃料占49.4%，主要包括现有车辆消耗。因此，考虑车辆应用的能耗意义重大。特别是，电动汽车或混合动力电动汽车将在不久的将来主导市场，这促使人们考虑车联网中的能源消耗。

在现实生活中，每辆车由于计算任务大小的不同通常会需要不同计算资源。在计算任务卸载过程中，有限的计算资源在车辆之间共享，每辆车需要确定是否进行卸载，每台MEC 服务器也应在多车之间进行合理的资源分配。考虑到上述问题，本文的主要研究工作如下。

1) 构建了基于MEC 的车联网任务卸载模型，在任务卸载决策和资源分配的约束下，通过联合优化任务卸载决策和边缘服务器的资源分配来最小化系统内的平均成本。成本是基于任务时延、能耗和权重因子这3 个指标定义的。

2) 将任务卸载决策和资源分配建模为一个混合整数非线性规划问题，针对这个问题，提出了一种基于改进的混合遗传算法的两阶段启发式方案。通过将优化问题分成2 个子问题，利用改进的混合遗传算法（IGHA,improved hybrid genetic algorithm）求解任务卸载决策问题，利用改进的人工鱼群算法（AFSA,artificial fish-swarm algorithm）求解资源分配问题，再将二者不断迭代求解，直至达到终止条件。

3) 对基本的遗传算法进行了改进。充分考虑了MEC 服务器出现过载或者对计算资源利用不足的2 种情况，具体为通过对经过交叉、变异后得到的不满足约束条件的染色体和满足约束条件但对MEC 的计算资源并未充分利用的染色体使用了贪婪修正法进行修正，使其转换为对MEC 的计算资源充分利用的染色体，从而提高算法的收敛速度和寻优能力。

4) 仿真结果表明，相比于基准方案，IHGA-AFSA方案降低了系统内的平均开销、时延及能耗。

1 系统模型

1.1 网络模型

如图1 所示，本文所研究的基于MEC 的车联网包括N辆单向行驶在道路上的汽车，道路沿线有M个路边单元（RSU,road side unit），每个RSU 都配备一个MEC 服务器，二者通过光纤有线链路连接。RSU 的集合定义为 M=｛1,2,…,M｝。车辆的集合定义为 N=｛1,2,…,N｝，每辆车有且仅有一个计算任务。其中，Dn是输入数据的大小，Cn是完成任务Qn所需的CPU 周期数，是任务完成可容忍的最大时延。任务可以在本地处理，或者卸载到MEC 服务器处理，定义an表示任务卸载决策变量，an=1表示车辆将任务卸载至边缘服务器计算，an=0表示任务在车辆本地计算。

图1 车联网场景

车辆与RSU 之间的通信是通过直连的无线链路进行的，车辆到RSU 的上传链路设定为频率平坦型快衰落瑞利信道。根据香农公式，可以计算出上传链路的传输速率为

其中，Bn表示MEC 服务器与车辆之间的带宽大小，Pn表示车载设备的发射功率，Gn表示车辆与RSU之间的信道增益，σ2表示无线信道的传输噪声。

1.2 计算模型

1) 本地计算

当车辆在本地处理其计算任务时，计算时延取决于其自身的计算能力，设是车辆n的计算能力，由放置在车辆上的车载单元（OBU,on-board unit）确定[12]。故本地计算时延为

同时可以获得车辆用户进行任务卸载的能耗为

2) 边缘服务器计算

与其他研究[12-13]一样，在语音识别等许多应用中，其计算结果的大小远小于输入数据的大小，接收计算结果的时延可以忽略不计。在这种情况下，总时延具体包括上行链路传输时延及计算任务执行时延。车辆n的总时延为

其中，fn表示MEC 服务器分配给车辆n的计算资源，定义为服务器m的总计算资源，有表示计算任务所属车辆与服务器之间的无线传输速率。

车辆任务卸载时的能耗主要来自卸载数据到边缘服务器的过程中的能耗，即

1.3 问题表述

由于每个任务可以在本地或者MEC 服务器上执行，因此车辆n的总时延为

车辆n的能耗包括本地能耗和上传能耗，表示为

将时延能耗开销（LEC,latency-energy cost）即车辆开销，定义为任务执行的时延和能耗的加权和。因此，车辆n的LEC 表达式为

本节将联合任务卸载决策和资源分配作为优化问题，目标是最小化系统内平均开销。定义a=｛a1,a2,…,an｝为MEC 服务器任务卸载决策变量，f=｛f1,f2,…,fn｝为计算资源变量，将优化问题表示为

其中，C1和C2 表示一个计算任务只能卸载至某一个MEC 服务器，不能同时卸载至2 个服务器；C3表示MEC 服务器分配给车辆n的计算资源不能为负数；C4 表示MEC 服务器总计算资源的约束。

2 算法设计

解决P1的关键挑战是求解整数变量an∈ ｛0,1｝，an使P1是一个混合整数非线性规划问题，这类问题通常都是非凸的NP-hard[14]，求解起来具有一定的难度，对此本文提出了一种基于改进的混合遗传算法的求解方案，具体将P1划分为2 个子问题。

1) 任务卸载决策问题。假设资源分配已给定，即f=f(0)，那么原优化问题就变成了只关于变量a的0-1 整数规划问题，本文采用IHGA 求解。

2) 资源分配问题。在该子问题的基础上，确定a=a*后，问题P1转化为关于f的连续问题，本文采用改进的AFSA 求解。

2.1 任务卸载决策

当f=f(0)给定时，P1转化为P2

此时，P1转化为关于a的优化问题P2，a为0-1 整数变量，采用遗传算法进行求解。遗传算法不要求求解的问题是连续的或可微的，也不需要控制算法的执行方向，具体步骤如下。

步骤1染色体。遗传算法借鉴了自然选择的思想[15]，引入了染色体的概念，即可能的解。本文中的任务卸载决策构成了个体的染色体信息，对于第n条染色体，其染色体信息可表示为

编码及种群初始化。根据任务的卸载模型，共有N个任务要经过卸载决策之后决定是否卸载。因此在遗传算法中，每个染色体都应该由N个基因组成，每个任务都可以选择在本地计算还是卸载至MEC 服务器计算，故每个基因都有2 个可能的值（本地计算则基因为0，MEC 服务器计算则基因为1），并得到初始的染色体种群I(0)。

步骤2染色体修正。对初始化染色体进行修正，修正主要分为以下两步。

1) 对不符合约束条件的染色体进行修正。对于该部分染色体，基于文献[16]中混合遗传算法的思想使其转换为符合约束条件的染色体，如果转换后的染色体充分利用了资源，则修正结束；否则转至2)。具体为，当时，将an=1的车辆按照从大到小的顺序进行排序，然后根据排序将选择卸载的车辆进行任务卸载，直至接近但不超过服务器的计算总资源，将剩余选择卸载的车辆由状态an=1改变为an=0。

2) 对满足约束条件但对MEC 的计算资源利用不足的染色体，运用贪婪修正法进行修正。设是一个对MEC 的计算资源利用不足的染色体，该染色体有r个车辆an=0，MEC的剩余计算资源为Fm0，通过贪婪修正法将其修正为充分利用计算资源的染色体将染色体Xi中an=0的车辆按照从大到小的顺序进行排序，形成长度为r的序列｛b1,b2,…,br｝（其中，b1为最大的序号，br为最小的序号），然后按排序将an=0的车辆转变为an=1，直至接近服务器的计算总资源，但不能超过其计算资源。

步骤3遗传算法中个体（解决方案）的质量由适应度值来评估。由于本文研究了最小化问题，因此将适应度函数设置为

适应度值越高，目标函数的成本就会越小，表明该卸载策略越优。

步骤4选择。采用轮盘赌算法筛选个体，即随机旋转轮盘进行选择，每个个体都可能被反复挑选。其基本思想是每个个体被选中的概率与其适应度成正比。设P(di)为下一代选择染色体di被选中的概率，即

步骤5交叉。如图2 所示，采用单点交叉的方式，在染色体串中随机设置一个交叉点，然后进行基因交换，生成2 个新个体。其意义在于通过为下一代群体保留具有更好亲本的基因来改善新群体的适应性。

图2 交叉

步骤6变异。防止种群中的所有解落入局部最优解。对于二进制编码，随机选择几个位置从1变成0 或从0 变成1，如图3 所示。

图3 变异

2.2 资源分配

当求出较优的任务卸载决策a*后，代入P1，得到问题P3

特别是，AFSA 有一种机制，可以使搜索行为跳出局部极值点并获得全局优化解。因此，采用AFSA 求解资源分配问题[17]。通常，AFSA 有4 个关键行为，具体如下。

1) 觅食行为：人工鱼趋向于食物的一种行为。人工鱼通过视觉或味觉来感知水中食物量或食物浓度来选择行动的方向。觅食行为是算法收敛的基础。假设第i条人工鱼的当前位置和适应度值分别为Xi和Yi，人工鱼视野内的另一个位置为Xj和适应度值为Yj，若Yj＞Yi，则按式(15)向新选择的位置靠近一步；否则，重新获取新位置，判断是否满足条件，若还不满足条件，则按式(16)随机移动一步，人工鱼Xi在其视野内随机选择一个位置Xj，其表达式为

2) 聚群行为：促使人工鱼自发地聚集在一起以避免伤害。如果鱼群中心有许多“营养食物”，并且它们不是太拥挤，即人工鱼Xi搜索当前视野内(dij＜ Visual)的伙伴数目nf和中心位置Xc，若，则Xi朝伙伴的中心位置移动一步

3) 追尾行为：当一个人工鱼找到一个食物充足且不太拥挤的最佳区域时，附近的人工鱼将跟随它并快速到达其附近的位置。人工鱼Xi搜索当前视野内(dij＜ Visual)的伙伴中函数Yj最优伙伴Xj，若，则Xi朝此伙伴移动一步

4) 随机行为：为了使人工鱼在更大范围内寻找食物或同伴，会按式(19)在水中随机地游来游去。当发现食物时，会向食物逐渐增多的方向快速移动。

基本的AFSA 步长和视野一般是固定值，这样前期的搜索易陷入盲目搜索，故本文引入自适应因子使视野和步长能根据外界环境信息的变化而动态地调整，这样算法在前期具有更好的全局搜索能力，还可以避免算法在后期容易发生振荡现象。二者的变化满足

其中，k为迭代次数，a∈（0,1）为自适应因子。

基于改进的AFSA 求解资源分配的具体步骤如下。

步骤1初始化设置，包括种群规模N，每条人工鱼的初始位置、视野Visual、步长Step、拥挤度因子δ、重复次数k；

步骤2根据P3 计算初始个体的适应值；

步骤3对每个个体进行评价，从觅食、聚群、追尾和随机中选择一个行为；

步骤4执行行为，更新自己，生成新鱼群；

步骤5评价所有个体；

步骤6达到迭代次数上限时算法结束，否则转到步骤3。

2.3 全局算法

综上，本文将任务卸载决策和资源分配建模为混合整数非线性规划问题，对此提出了一个基于改进的混合遗传算法的两阶段启发式算法的方案。将问题分成2 个子问题，通过将初始化资源分配代入P1，得到只关于任务卸载决策的P2，通过IHGA 进行求解。将得到的任务卸载决策解代入P1，得到只关于资源分配问题的P3。利用改进的AFSA 进行求解，基于二者的耦合关系，不断迭代求解，具体步骤如下。

步骤1初始化资源分配为f(0)，代入P1，设置当前迭代次数为r=0；

步骤2将资源分配f(r)代入P2，通过IHGA得到较优的任务卸载决策a(r+1)；

步骤3通过IHGA 得到的任务卸载决策a(r+1)代入P1，得到P3，通过改进的AFSA 求解得到资源分配方案f（r+1）；

步骤4判别相邻两次目标函数的增长值是否小于阈值τ，若大于或等于则r=r+1，并同时继续步骤2；否则输出当前最优的任务卸载决策和资源分配方案f*。

全局算法流程如图4 所示。

图4 全局算法流程

3 仿真实验及数据分析

为了验证本文针对任务卸载决策和资源分配所提的算法，在MATLAB 平台进行仿真实验。参考文献[7-9,12]，以及本文的实际仿真环境，有如下参数设置。考虑一条长为2 000 m 的单向道路，放置5 个RSU，每个RSU 的通信覆盖范围的半径为500 m，RSU 分配给每辆车的子信道带宽为2 MHz，每辆车的发射功率为46 dBm，高斯白噪声为σ2=-1 47dBm，车辆用户的信道衰减模型为u=127+30logd，其中d是每辆车与RSU 中心的距离，RSU 与车辆i之间的信道增益为。IHGA 中的交叉概率为0.4，变异概率为0.02，种群数量为50，迭代次数为50。改进的AFSA 中[18]的人工鱼数量为50 只，感知距离为1，步长为1，拥挤度因子为0.618，最多迭代次数为50，最多试探次数为100，自适应因子为0.6。设置时延因子，能耗因子。IHGAAFSA 方案的阈值τ=0.1。

为了验证本文提出的IHGA-AFSA 方案的性能，对比了以下3 种基准方案。

1) 本地计算方案：计算任务不卸载到MEC 服务器上计算，而是全部留在车辆本地计算。

2) 随机卸载策略：车辆随机选择是否进行卸载，若卸载则利用改进的AFSA 求解资源分配问题。

3) IHGA-平均方案：IHGA 求解任务卸载决策，将MEC 的计算资源平均分配给车辆。

3.1 任务所需CPU 周期数性能分析

本节实验中一共有100 辆车，每辆车均有一个计算任务，故共有100 个计算任务。每个RSU 配备一台MEC 服务器，每台MEC 服务器的最大计算资源为400 GHz，每辆车的计算频率在1.8～2.0 GHz随机分布。计算任务的输入数据量大小为1.5 MB，图5～图7 分别展示了完成任务所需计算量（用CPU周期数表示）为1 300～2 000 Megacycles 时系统内开销、时延及能耗的变化。为了消除随机性，一共进行100 次实验，最后结果取平均。

图5 分析了任务所需计算量与系统内开销的关系。从图5 可以看出，当任务所需计算量增加时，系统内开销不断增加。其中，本地计算方案的开销最大，IHGA-AFSA 方案与随机卸载策略相比，资源分配均采用改进的AFSA，而IHGA-AFSA 方案所产生的开销更小，说明本文提出的IHGA对任务卸载决策起到了优化作用。IHGA-AFSA 方案与IHGA-平均方案相比，卸载决策均采用IHGA，而IHGA-AFSA 方案所产生的开销也是更小，说明本文提出的改进的AFSA 对资源分配起到了优化效果。因此本文提出的IHGA-AFSA 方案在优化系统开销方面性能优于本地计算、随机卸载和IGHA-平均方案。

图5 任务所需计算量与系统内开销的关系

图6分析了任务所需计算量与系统内时延的关系。从图6 可以看出，当任务所需计算量增加时，系统内时延不断增加。其中，本地计算方案的时延最大，其余3 种方案均小于本地时延，说明车联网与MEC 技术的结合更加符合时延敏感型任务对时延的苛刻要求。当任务所需计算量为 1 700 Megacycles 时，IHGA-AFSA 方案与本地计算方案相比时延减少了约17.4%。在4 种方案中，本文所提方案时延最低，因此本文提出的IHGA-AFSA 方案在优化系统时延方面性能强于本地计算、随机卸载和IHGA-平均方案。

图6 任务所需计算量与系统内时延的关系

图7 分析了任务所需计算量与系统内能耗的关系。当任务所需计算量增加时，系统内能耗不断增加。其中，本地计算方案的能耗最大，其次是随机卸载策略，再次是IHGA-平均方案，本文提出的方案在优化能耗方面性能是最优的，产生的能耗是最低的。IHGA-AFSA 方案与随机卸载策略相比，资源分配均采用改进的AFSA，而IHGA-AFSA 方案所产生的能耗更小，说明本文提出的IHGA 不仅对任务卸载决策起到了优化作用，对能耗也有效果，在任务所需计算量为1 700 Megacycles 时，能耗减少约16.6%。

图7 任务所需计算量与系统内能耗的关系

3.2 任务数据量大小性能分析

本节实验中一共有70辆车，每辆车均有一个计算任务，故共有70 个计算任务。每个RSU 配备一台MEC 服务器，每台MEC 服务器的最大计算资源为400 GHz，每辆车的计算频率在1.8～2.0 GHz 随机分布。计算任务所需的CPU 周期数为2 000 Megacycles，图8～图10 分别展示了任务数据量大小为0.5～1.5 MB 时系统内开销、时延及能耗的变化。为了消除随机性，一共进行100 次实验，最后结果取平均。

图8 分析了任务数据量大小与系统内开销的关系。当任务数据量大小增加时，本地计算方案所产生的开销波动较小，这是因为开销是时延和能耗的加权，时延和能耗波动均比较小，故开销波动也小。但本地计算方案产生的开销是最大的，其次是随机卸载策略，本文提出的IHGA-AFSA 方案与IHGA-平均方案相比产生的开销更小。这说明IHGA-AFSA 方案在优化开销方面强于本地计算、随机卸载、IHGA-平均方案。当任务数据量大小为1 MB 时，本文方案相比于本地计算、随机卸载、IHGA-平均方案所产生的开销降低了约29.1%、23.3%、14.4%。

图8 任务数据量大小与系统内开销的关系

图9 分析了任务数据量大小与系统内的时延的关系。随着任务数据量大小的增加，本地计算方案的时延波动最小，这是因为任务数据量大小与本地时延没有直接的关系。其余3 种方案的时延随着任务数据量大小的增加并没有明显的递增性，这是因为任务数据的大小只会对任务上传的时延造成影响，而上传链路的传输速率较快，故总体的时延不会有很明显的递增表现。但是在3 种方案中，本文提出的IGHA-AFSA 方案产生的时延最小，证实了其在优化时延方面的优越性。当任务数据量大小为1 MB 时，本文方案相比于本地计算、随机卸载、IHGA-平均方案所产生的时延降低了约23.4%、16.5%、15.5%。

图9 任务数据量大小与系统内时延的关系

图10 分析了任务数据量大小与系统内能耗的关系。随着任务数据量大小的增加，本地计算方案的能耗波动最小，这是因为任务数据量大小与本地能耗没有直接的关系。其余3 种方案的能耗随着任务数据量大小的增加而增加，这是因为任务数据量大小会对任务上传的能耗造成影响，在这种情况下本文提出的IHGA-AFSA 方案在能耗优化方面效果是最好的。随机卸载策略中，卸载决策是随机选择的，并且本文时延因子设置的较大，更倾向于对时延的优化，在图10 中也证实了该方案对能耗优化的有效性。当任务数据量大小为1 MB 时，IGHA-AFSA 方案相比于本地计算、随机卸载、IHGA-平均方案所产生的能耗降低了约32.1%、27.2%、13.6%。

图10 任务数据量大小与系统内能耗的关系

4 结束语

本文对基于MEC 车联网中的任务卸载决策和资源分配进行了研究。考虑决策和资源的约束，建立了以最小化系统内平均开销为目标的计算模型。针对优化问题的NP-hard，将优化问题划分成2 个子问题，提出了一个基于改进的混合遗传算法的两阶段启发式方案。利用IHGA求解任务卸载决策，AFSA求解资源分配，再将二者不断迭代优化求解，直至达到阈值条件。仿真结果表明，所提方案与基准方案相比降低了系统内的平均开销、时延及能耗。