改进多种群进化算法求解移动边缘计算中任务调度问题

朱清华，鹿安邦，周俭铁，侯 艳

（广东工业大学 计算机学院， 广东 广州 510006）

随着移动互联网的发展，出现了越来越多的计算密集型任务，例如增强现实、人脸识别和导航应用等[1]。与此同时，移动设备的综合能力也在显著提升。移动设备体积小、重量轻，相对于服务器来说，移动设备的计算能力和续航能力相对有限。当移动设备的处理能力不能有效地执行一个应用时，会降低用户的体验质量(Quality of Experience, QoE)。

移动云计算是解决上述问题的一种有效方式。通过将计算密集型的任务卸载到计算能力更强的远程服务器中进行处理，移动设备的能耗和任务的完成时间将会大大减少[2]。然而，云计算中心往往分布在离用户比较远、电价较低的地方，这样不可避免地带来了较长的通信时延。虽然移动云计算能够在很大程度上提升移动设备的综合性能，但它仍然不是最有效的一种解决方案。为此，Satyanarayanan等[3]提出了微云的概念：“微云是靠近用户侧的，可信的，与互联网有很好连接的一台计算资源丰富的计算机或者计算机集群”。移动设备可以通过无线网络接入微云，获取对应的计算、网络通信等服务。移动边缘计算的概念类似微云；此外，它能够支持多种无线网络(Wi-Fi，4G等)。移动边缘计算技术部署边缘服务器在靠近用户的网络边缘，为移动设备提供超低延迟的网络通信服务和云一样的计算能力。因此，相比移动云计算而言，移动边缘计算是一种更加有效的解决方案[4]。

目前，已有很多关于移动边缘计算环境下任务的调度问题的研究[5-9]。这些研究普遍关注移动边缘计算环境下的任务卸载和资源分配问题。问题的优化目标往往是移动设备的任务的完成时间、移动设备的能耗，或者是两者之间权衡。文献[10]针对只包含一个边缘服务器和一个移动设备的边缘计算环境，提出了一种基于李雅普诺夫优化的调度策略。该策略能够有效地减少任务完成时间，同时降低任务错误率。文献[11]针对包含一个边缘计算节点和多个物联网设备的移动边缘计算环境，考虑了信道的随机波动，提出了一种随机优化算法，降低了多个设备的平均能耗。Chen等[12]提出了一种基于博弈论的分布式算法，同时优化了移动设备的任务能耗和任务的完成时间两个目标。Mazouzi等[13]构建了一个包含多个微云的移动边缘计算环境模型，并针对该模型下的任务卸载问题，提出了一种微云选择策略用来减少移动设备的能耗。文献[14]针对包含多个边缘服务器和单个用户的移动边缘计算环境，提出了一种基于半定松弛算法的任务调度算法。文献[15]针对包含一种边缘计算节点和一个中心云的移动边缘计算环境，考虑单用户具有多个任务的情况，提出了一种基于粒子群算法的任务卸载策略。文献[16]针对包含多个边缘服务器和多个用户的移动边缘计算场景，考虑每个用户具有多个任务的情况，提出了一种基于深度学习的方法优化了任务的完成时间和移动设备的能耗的权衡值。

综上所述，这些工作并没有针对包含多个用户和多个边缘服务器的移动边缘计算环境，同时优化移动设备任务的完成时间、能耗以及通信成本3个目标。此外，本文考虑每个用户具有多个任务的场景。为了更好地解决上述问题，本文首先对该问题的优化目标进行了归一化，然后通过加权将多目标优化问题转化为一种单目标优化问题。最后，提出了一种基于多种群进化算法的任务调度算法。

1 移动边缘计算模型与问题描述

1.1 场景描述

令Nq={1, 2, 3 , ···,q}表示自然数集合，q为一个正整数。|Z|表示集合Z的基数。令 Ω表示云和微云的服务器的集合，则Ω={Ωk|k∈|Ω|}。当k=|Ω |时，Ωk代表中心云服务器。每个微云都由一个网络接入点AP(Access Point)和一个边缘服务器组成。本文考虑的移动边缘计算环境，包含多台移动设备、多个微云和一个中心云。图1是移动边缘计算环境示意图。

图1 包含3个微云和一个中心云的移动边缘计算环境Fig.1 An MEC environment with three cloudlets and a central cloud

1.1.1 移动设备

移动设备具有一定计算能力和通信能力，例如手机、平板、笔记本电脑等。Mn代表移动边缘计算环境中的第n台移动设备。Bup,Bdl分别为移动设备的上传和下载速率。rn为第n台移动设备的处理速率，单位为GHz。Pidle、Pup、Pdl、Pcm分别为移动设备的空闲功率、上传功率、下载功率、计算功率。计算功率与移动设备的处理器速率相关。Pcm(n)代表第n台移动设备的计算功率，计算式为

式中： β为能效因子。参考文献[13]，将 β设定为10-9。

1.1.2 计算能力

fk为 Ωk的计算能力，其中k为云或者微云的编号，当k＜ |Ω|时，fk为第k个微云的计算能力；当k= |Ω|时，fk为云的计算能力。

1.1.3 网络连接

移动设备通过无线通信网络与AP进行通信，AP通过高速有线网络与边缘服务器进行连接。相比于AP与移动设备之间的通信时延，AP与边缘服务器之间的时延很小。因此，本文忽略了AP与边缘服务器之间的通信时延。矩阵B=[Bk1,k2]|Ω|×|Ω|表示不同微云或者云之间的通信速率，Bk1,k2表示Ωk1与Ωk2之间的通信速率。

1.1.4 任务

式中：A是一个常量，表示任务负载与输入数据量之间的比例常数，单位为Cycle/byte。参考文献[17]，将A设定为1 900 Cycle/byte。

1.2 时间计算模型

Tup(n,i)为任务tni的输入数据从移动设备上传到微云L(n)的时间，计算式为

Tdl(n,i)为Mn从AP下载任务tni的输出数据的时间，计算式为

T为每个移动设备完成全部任务的平均时间，计算式为

式中：u为移动设备的数量。

1.3 能耗计算模型

Eup(n)为Mn上传所有任务的输入数据总的通信能耗，计算式为

Edl(n)为Mn下载所有任务的输出数据总的通信能耗，计算式为

E为每个移动设备完成全部任务的平均能耗，计算式为

1.4 通信成本计算模型

C(n)为Mn完成所有任务时的总通信成本，计算式为

1.5 问题描述

为了避免各个优化目标量纲不一致的问题，本文对当前的多个优化目标进行了归一化处理。此外，用户对于任务的完成时间、能耗、通信成本关注程度不同。线性加权是权衡多个目标的一种常用处理方式[18]。一个目标的权重因子越大，表示用户对这个目标的关注程度越高。例如，当用户想要花费更少的通信成本时，就会将通信成本的权重因子设置为较大的值。本文采用线性加权的方式该多目标优化问题转化成单目标优化问题。建立模型表示该问题，如式(21)所示。

2 改进多种群进化算法

2.1 算法相关设置

2.1.1 初始化种群

2.1.2 编码方式

编码方式主要2种: 实数编码和二进制编码。二进制编码方式一般适用于问题的解精度较小的问题。对于精度较高和维度较大的问题，二进制编码会占用大量存储空间。为了更好地求解提出的问题，采用实数编码的方式。

2.1.3 种群更新

进化种群通过一定更新方式迭代寻优，从而得到问题的解。例如，遗传算法通过交叉、变异和选择更新种群，从而得到问题的最优解或者次优解。

2.1.4 移民操作

简单来说，移民操作就是使用当前子种群中的最优个体替换掉目标子种群中的适应度最差的个体。移民操作能够实现子种群之间的信息交流，增强算法的全局寻优能力，从而避免算法过早收敛。

2.2 不同算法的更新流程

2.2.1 基于精英保留的遗传算法

遗传算法(Genetic Algorithm, GA)是一种通过模拟自然进化过程探索最优解的方法。基于精英保留的遗传算法(Elitism Genetic Algorithm, EGA)在GA的基础上增加了精英保留机制[18]。EGA算法种群更新操作如下。

(1) 交叉：交叉是为了将两个个体人工结合生成新的个体。模拟二进制交叉算子对连续优化问题具有很好的性能[19]。因此，采用模拟二进制交叉算子。

(2) 变异：变异是对现有种群中的个体进行随机调整，这可以改变原始的个体特性，从而引入新的特征。本算法采用多项式变异算子作为变异算子[20]。

(3) 选择：选择操作用来模拟生物界“物竞天择，适者生存”的自然选择机制。从每次迭代产生的个体中，选择适应度函数值比较好的个体作为下一代迭代的父代种群。本文使用轮盘赌选择算子。

(4) 精英保留：种群中迄今适应度最好的个体不参与种群的更新迭代过程，直接保留进入下一代父代种群。

2.2.2 粒子群算法

粒子群(Particle Swarm Optimization, PSO)算法是一种具有个体改进、种群合作和竞争机制的启发式算法，它受启发于自然界中成群鸟类或成群鱼类的捕食行为[21]。PSO算法更新操作主要包括速度更新和位置更新。

Ql(h)表示第h个种群中的第l个个体，Vl(h+1)为第l个体的更新速度，hmax为最大迭代次数。个体在决策空间中的速度和位置的更新公式为

式中：G1，G2为区间[0,1]之间的随机变量。c1，c2为学习因子。w为动态惯性因子，wmax为最大的惯性因子，wmin为最小的惯性因子。pl,best(h)为第h代种群的第l个个体的最优位置，pgbest(h)为第h代种群的全局最优位置。

2.2.3 布谷鸟算法

布谷鸟 (Cuckoo Search, CS) 算法是一种用来解决优化问题的元启发式算法。该算法模拟了布谷鸟独特的寻窝产卵的行为，并引入了自然界一些鸟类和果蝇的Levy飞行机制[22]。布谷鸟算法更新操作主要包括更新鸟巢和丢弃鸟蛋。

(1) 更新鸟巢。种群中个体的位置更新如式(25)所示。

式中：α 表示步长因子。Y(λ)代表Levy飞行步长更新函数，计算公式参考文献[22]。

(2) 丢弃鸟蛋。表示鸟蛋被丢弃的概率。遍历当前种群中的个体，以概率pa丢弃种群中的个体，并重新生成个体替换掉当前个体。

2.3 约束处理

本文对不同约束采用了不同处理方式：对于约束(a), 在算法流程中如果有元素超出了边界，使用边界值进行替代。对于约束(b), 如果xin等于0，令r(n,i,xin)=rn。对于约束(c), 采用了非固定多阶段映射罚函数法[23]处理约束。该方法通过在约束条件上添加一个惩罚项，使得不满足约束条件的个体具有很差的适应度值。这样，不满足约束条件的个体在算法迭代的过程更容易淘汰掉，满足约束和适应度更好的解会得到保留。令Λ表示X中出现过的计算节点编号的集合。其计算式为

式(26)中，g(X,R)为约束的违反函数；式(27)中，H(X,R)为最终的惩罚项；式(28)中，q(X,R)为对约束的违背程度；式(29)中， ψ(q(X,R))为惩罚函数的程度；式(30)中，θ(q(X,R))为多阶段映射函数；式(31)中，δ(h)为当前迭代次数的惩罚力度。F(X,R)为添加惩罚项后的适应度函数，其计算式为

2.4 GA-PSO-CS算法流程描述

步骤1 初始化算法参数。按照算法参数初始化3个子种群。按照式(27)～(31)初始化约束，并设置h=1。

步骤2 对种群1进行模拟二进制交叉和多项式变异。

步骤3 按照式(32)对种群1进行适应度计算，将最优个体保存为种群1的第一个个体。

步骤4 按照式(22)对种群2的每个个体进行更新。

步骤5 按照式(25)，对种群3中的每一个个体进行更新得到新种群,如果新种群的个体的适应度函数值小于种群3对应个体的适应度函数值，使用新种群的个体替换掉种群3中的对应个体。

步骤6 遍历种群3，以一定的概率pa丢弃种群3的个体，并重新生成个体，替换掉被丢弃的个体。

步骤7 在种群1～3之间进行移民操作。

步骤8 按照式(32)计算整个种群的适应度，获得整个种群中的最优个体，将种群1的第一个个体替换为整个种群的最优个体。

步骤9 按照式(27)～(31)更新约束。

步骤10h=h+1;如果h＜hmax，返回步骤2，否则停止迭代。

3 实验

3.1 实验环境参数设置

计算机配置：CPU为Core(TM) i9-9900K CPU@3.60 GHz型号, 内存容量32 GB。表1为移动边缘计算环境参数表。实验考虑包含3个异构微云和一个中心云的移动边缘计算环境。参考文献[16]，将3个微云的处理频率分别设置为3.5，5，6.5 GHz。将中心云的处理速率设置为10 GHz。参考文献[24]，将移动设备的通信成本Pc设定为1.5 unit/MB。Din(tni)在10～30 MB之间随机生成，Dout(tni)在1～3 MB之间随机生成。

表1 MEC环境参数Table 1 MEC environment parameters

3.2 各算法参数设置

EGA算法参数设置为：种群规模为60，交叉概率为0.8，变异概率为0.02。

CS算法参数设置为：种群规模为60，丢弃概率pa=0.25，步长因子α=0.1, λ=1。

GA-PSO-CS算法参数设置为：对于种群1，种群规模为15，交叉概率为0.8, 变异概率0.005。对于种群2，种群规模15，c1和c2都设置为2，wmax=1，wmin=0.1。对于种群3，种群规模为30，pa=0.25，α =0.1, λ=1。

3.3 收敛性分析

为了更好地对比提出的GA-PSO-CS算法的性能，选择CS算法和EGA算法作为对比算法。为了保证实验结果的公平性，每次运行算法时设置迭代次数为200，独立运行每个算法20次，取结果的平均值。为了更好地说明算法的有效性，针对三组不同优化目标权重因子设置进行了实验。权重因子设置如下：

3.3.1 收敛结果分析

图2～4分别对应3组不同参数的运行结果的收敛曲线示意图。

图2 设置(I)下的不同算法的收敛结果Fig.2 Convergence of different algorithms under setting (I)

表2是设置(I)下不同算法收敛时的平均任务完成时间、平均能耗、平均通信成本以及对应的综合成本。由表2可以看出，GA-PSO-CS能够得到最小的综合成本、平均任务完成时间和平均能耗。设置(II)和(III)下的结果不再展示。

表2 设置(I)下的不同算法的目标对比Table 2 Comparison of objectives of different algorithms under setting (I)

图3 设置(II)下的不同算法的收敛结果Fig.3 Convergence of different algorithms under setting (II)

图4 设置(III)下的不同算法的收敛结果Fig.4 Convergence of different algorithms under setting (III)

从图2～4可以看出，GA-PSO-CS算法能够得到更优的适应度值，这表明该算法具有更好的全局寻优结果。在设置(I)下，GA-PSO-CS最先收敛且收敛结果优于CS和EGA。在设置(II)下，CS最先收敛，但很快陷入局部最优。GA-PSO-CS收敛速度适中，但收敛结果优于CS和EGA。在设置(III)下，GA-PSO-CS收敛速度最慢，但能够得到最好的收敛结果。综上所述，GA-PSO-CS相比于EGA和CS，具有更好的收敛性能。

3.3.2 综合指标分析

为了评估算法的性能，选取20次收敛结果的平均值、最优值、最差值以及标准差作为算法的评估指标。表3对应设置(I)～(III)下不同算法的综合指标结果。

表3 不同设置下的不同算法的收敛结果指标对比Table 3 Comparison of convergence result indicators of different algorithms under different settings

从表3可以看出，在设置(I)和(II)下，GA-PSOCS算法得到的收敛结果的最优值、平均值、最差值均优于EGA和CS。在设置(III)下，GA-PSO-CS算法的收敛结果具有最好的最优值、平均值、最差值以及标准差。综上所述， GA-PSO-CS算法具有最强的收敛性，且具有较强的稳定性。

4 总结与展望

本文针对包含多个异构微云和一个中心云的移动边缘计算环境下任务卸载与资源分配问题，考虑了多用户、多任务的场景。提出了在满足资源约束情况，同时优化包含任务的完成时间、移动设备的能耗以及移动设备的平均通信成本多个目标的任务调度问题。针对该问题，提出了一种基于多种群进化算法的任务调度算法。该算法通过合理地对任务卸载位置和计算资源分配进行决策，提升了移动设备的综合性能。仿真实验结果表明，相比于CS和EGA，提出的改进多种群进化算法GA-PSO-CS具有更好的综合性能。在未来工作中，笔者将针对有数据依赖的应用任务进行研究，同时使用深度强化学习或者基于单解的启发式算法求解问题。