改进GA的边缘计算任务卸载与资源分配策略

贾 觐，暴占彪

(1.河南财经政法大学 网络信息服务中心，河南 郑州 450000；2.河南财经政法大学 现代教育技术中心，河南 郑州 450000)

0 引 言

随着智能应用的日益普及，增强型超可靠移动宽带、大规模数据通信以及超低通信延迟3大类业务对运营商的传输网络和核心网都提出了巨大的挑战[1,2]。虽然5G网络可以给用户带来更高的带宽速率、更多的网络连接和更低的延迟，但是这也将导致单位时间内核心网需要处理的数据量和业务请求数呈爆炸式增长[3,4]。

另一方面，由所有应用产生的数据都需要通过核心网进行交互，所以在业务接入高峰期会给通信网络负载造成很大压力。与云计算在网络方面的局限性相比，移动边缘计算集成网络通信、数据计算和处理等业务，形成一个开放平台，提供给用户更接近于实体或数据源的服务，使其应用能够在边缘端进行任务处理，从而实现更高效的网络服务响应，满足更多业务场景在实时处理、智能应用、安全和隐私保护等方面的需求[5,6]。换言之，移动边缘计算的核心思想是将计算资源和缓存资源边缘化和本地化，从而减少网络延迟，缓解带宽的压力。移动边缘计算不仅满足了移动设备扩展计算能力的需要，而且弥补了云计算中传输延迟长的缺点[7]。

由于不同应用场景下对任务处理具有不同的计算量和数据传输量要求，因此为了确保移动设备能够发挥其最佳性能，可以通过使用任务卸载策略来进行资源的优化分配，制定任务是在本地处理或是在远程服务器上执行的处理方案[8]。同时，由于移动边缘计算服务器在计算、存储、带宽等方面的资源均十分有限，而为了实现较低的网络延，且更好地利用边缘服务器集群有限的资源，任务卸载策略首先需要明确其目标服务器再进行任务卸载[9]。目前，任务卸载策略主要分为粗粒度任务卸载和细粒度任务卸载两种类型。粗粒度任务卸载通常以移动应用程序为卸载对象，且不会根据其功能划分为多个不同的子任务。该类方法往往没有充分考虑到整个应用的传输延迟和传输消耗。细粒度任务卸载一般首先会将一个移动应用划分为多个具有数据依赖关系的子任务[10,11]。由于划分后的子任务只需要较少的计算复杂度和数据传输量，因此细粒度任务卸载可以将部分或全部的子任务都卸载到多个远程服务器上进行处理，从而节省了计算时间和传输时间，实现了对边缘服务器集群资源更高效的利用。

因此，针对大规模异构移动边缘计算中具有多服务节点和多依赖移动子任务的场景，提出了一种移动边缘计算环境下基于改进遗传算法的计算任务卸载与资源分配算法，利用改进遗传算法来解决细粒度的任务决策问题，包括明确卸载内容、卸载数量以及卸载目标等问题,从而达到移动边缘计算平台在时延、成本、能耗和网络使用率多方面降低的目的。

1 相关工作

为了降低移动设备的能量消耗，提高现有设备计算能力，并有效地利用边缘服务器和云数据中心的计算资源，近年对移动边缘计算中的卸载问题已有了较深入的研究。一般来说，调度可以定义为在特定时间内将任务分配给有能力的资源[12]。并且，一个调度问题常常需要服从许多必须满足的约束条件和目标。调度问题可以映射成为一个最优化的问题，比如移动边缘计算中的计算卸载与资源分配决策的目标可以设定为延迟的最小化以及资源利用率的最大化。大多数的调度问题往往包含资源、任务、约束以及目标4个基本要素，其中资源是能够执行或处理任务的物理或逻辑设备；任务是需要由资源执行的物理或逻辑操作；约束是将任务调度到资源中时必须考虑的条件；而目标则是为了评估调度的表现而进行衡量的评估标准。

分析相关研究可以发现，对于任务卸载和资源分配的调度类技术通常包含两大类方法：精确方法和启发式方法[13]。精确方法可以找到调度问题的绝对最优解。文献[14]采用了混合整数非线性规划方法来解决任务卸载问题，并最终实现了用户成本的降低。但该方案在传输延迟性方面还有进一步提升的空间[15]。文献[16]提出了一种面向边缘计算的用户请求数量预测模型，并在此基础上设计了一种任务卸载方案。通过比较该算法与贪婪算法、线性规划算法和遗传算法在任务卸载方面的性能，验证了该算法的有效性。文献[17]建立了一种基于移动边缘计算体系结构的数学模型。该数学模型通过测量用户设备与处于网络边缘的移动边缘计算服务器之间的往返时间实现了移动边缘计算卸载策略的最优化，并确定了何时将用户的计算任务卸载到移动边缘计算服务器进行处理。文献[18]研究了移动边缘计算卸载场景下的多用户服务延迟问题，并提出了一种部分计算卸载模型。采用最优化策略来优化通信和计算资源的分配。与任务在只本地执行或边缘执行的方案相比，该文所提出的部分卸载策略可以实现所有用户设备的延迟的最小化，从而提高了用户的服务质量。

而启发式方法虽然并不能保证找到最优解，但是与采用精确方法所需的时间相比，启发式方法能够在合理的计算时间内找到具有某种程度的最优解。文献[19]在提出的启发式算法的基础上，引入了多拓扑路由，来确保所分配的出口路由器具有近似最优解的性能。实验结果表明，与其它方法相比，该算法具有更低的执行时间和更好的服务质量，满足了云计算和边缘计算中网络流量问题的灵活性和效率要求。考虑到环境的性质，安全性是移动边缘计算中所面临的一个主要挑战，文献[20]提出了一个网络安全框架，可识别出在移动边缘计算环境中的恶意边缘设备。该框架采用两阶段马尔可夫模型对恶意或合法边缘设备进行早期预测。并且实验结果表明了提出的框架的有效性。

但是启发式算法容易陷入只能获取到局部最小值的困境，从而难以得到整体的最优解，并且不适用于移动边缘计算环境中海量的数据处理，为此，提出了一种移动边缘计算中基于改进遗传算法的计算卸载与资源分配算法。其创新点总结如下：

(1)为了高效处理网络中海量的数据，构建了移动边缘计算网络模型，其中包括能耗、平均服务延迟、执行时间以及负载均衡模型，以合理卸载设备服务请求且优化计算资源的分配。

(2)由于现有算法存在延迟较大且负载不均衡的问题，所提算法以能耗、延迟、负载均衡最小化为优化目标，利用改进的遗传算法进行求解，并且从染色体一维表现形式、交叉和变异算子等方面进行改进以提高算法的性能。

2 系统建模

移动边缘计算网络通常包括3个部分，分别为云数据中心层、边缘计算层和移动请求设备层，其架构如图1所示。移动请求设备层包含了传感器、笔记本电脑、手机等处理性能较低的设备；边缘计算层将所有的边缘服务器按其相对距离划分成为多个区域，且每个区域均中包含了一些性能中等的异构边缘计算服务器；云数据中心层包含了可形成一个群集的大量高性能物理服务器。

图1 移动边缘计算的架构

当移动请求设备需要通过计算卸载和资源分配来提高性能时，那么整个移动请求任务会通过分割算法被划分为若干个子任务。其中一些子任务必须在本地执行，例如用户交互任务、设备输入/输出任务和外围接口任务，而另一些任务可以卸载到服务器上执行，通常是计算量比较大的数据处理任务。

2.1 能耗模型

对于包括了智能手机、传感器和远程服务器在内的所有请求设备，在一定执行时间内的总能耗主要由两个部分组成，即所有设备的计算能耗Ecom和移动设备的卸载能耗Eoff。 其中第m个计算资源的能耗模型为

(1)

(2)

式中：taskm表示第m个计算资源中所有任务的数量，Mn表示部署第n个子任务所需的CPU资源，CMm表示第m个计算资源内的CPU总资源。同时将第n个请求设备在某一信道中的数据传输速率rn定义为

(3)

(4)

(5)

系统中，计算资源的总数量为 (1+M+N)， 以及请求设备的总数量是N， 则在单位时间t内产生的计算能耗与卸载能耗为

(6)

2.2 平均服务延迟

(7)

(8)

则在单位时间t内，第m个子任务的数据传输延迟Dtr为

(9)

另外，在单位时间t内，第m个子任务由于处理数据而产生的计算延迟Dcom为

(10)

式中：vserver(t) 表示远程服务器部署第m个子任务的处理速率，vlocal(t) 表示本地设备部署第个子任务的处理速率，xoff用来表示当前子任务是否卸载到远程服务器执行。

根据以上分析，单位时间t内所有请求设备的平均时延为

2.2两组患者治疗前后PANSS评分比较 治疗前,观察组PANSS评分为(90.11±5.82)分,对照组PANSS评分为(89.82±5.79)分,两组比较差异无统计学意义(t=0.215,P=0.830>0.05)。治疗后,观察组PANSS评分为(42.08±3.11)分,对照组PANSS评分为(50.82±3.28)分,两组比较差异有统计学意义(t=11.762,P=0.000<0.05)。

(11)

式中：Dtotal(t0) 表示所有请求设备的总延迟，表示请求设备的数量， Ωn表示在第n个请求设备被划分后的子任务数。

2.3 平均执行时间

执行时间指的是子任务处理数据所需的时间。当子任务可以使用的资源越多时，那么子任务所需的处理时间越短，同时在单位时间内子任务可以处理的请求越多。因此，卸载决策需要尽可能减少所有请求设备的平均执行时间。平均执行时间的计算如下

(12)

式中：T(t0) 表示在单位时间内所有请求设备的平均执行时间。

2.4 负载平衡目标

负载平衡是一种可在网络中实现各种资源有效利用的重要方法，其主要目的是资源最优化利用、最大化吞吐量、最小化响应时间，避免过载，增强网络数据处理能力，以及提高网络的灵活性和可用性[22]。网络中所有设备的负载平衡优化目标为

(13)

(14)

(15)

3 提出的遗传算法

由于移动边缘计算中计算卸载和资源分配问题在本质上存在着复杂性，精确的最优解不充分，因此，采用改进的遗传算法对问题进行求解[23]。遗传算法是一种由自然选择过程产生的元启发式算法，其属于一类进化算法。在此进化算法中，优化问题的候选解(染色体)群体可进化为更好或更适合的解。

在计算卸载和资源分配问题中，种群染色体可以用来表示问题的候选解，如果一个解满足问题的约束条件，那么其就是可行的；否则是不可行的[24]。提出的遗传算法中根据问题需要采用染色体表现形式、交叉和变异算子，用于惩罚不可行的解决方案，使这些不可行的解决方案具有较小的选择(或生存)概率。所提算法的流程如图2所示。

图2 所提改进遗传算法的处理流程

首先定义问题的规模，即请求设备的数量和可用的计算资源，并且生成种群数量的候选解(染色体或个体)，以初始化群体。然后评估每个染色体的适应度F，F为总潜伏期的倒数，并且选择即将进行交叉和突变的配偶或亲本个体(染色体)，从当前种群中创建新的后代种群。在完成交叉和变异后，该算法根据适应度函数F来评价每个产生的子代染色体的适应度值。最后，使用一个程序确定不可行的染色体，以及使用另一个程序惩罚其中的一些染色体。此外，该算法保留了所有产生的种群中的最好染色体，即适应值最小的染色体。遗传算法会不断重复上述步骤，直到满足一些终止的条件。当迭代终止时，遗传算法会返回代表优化问题解决方案的最佳染色体。

在改进的遗传算法中，算子的实现如下：

(1)染色体表示：在提出的遗传算法中，问题的候选解决方案(染色体)是一个0或1个整数值Xmn元素(或基因)的二维数组，其表示考虑到在m个计算资源分配给n个请求设备的情况下向资源分配请求的可能。如果请求rn被分配给资源sm， 则基因Xmn的值为1；否则为0。为了获得表示染色体的一维解数组，二维数组被垂直拉伸，如图3所示。

图3 染色体的二维排列

(2)适应度评价：对于群体的每个染色体，可以通过F=1/LA计算给定染色体的适应度，其中LA由式(15)中的目标函数给出。

(3)交叉和变异：改进的遗传算法使用传统的轮盘赌方法，从当前种群中将两个分为一组进行选择，将其交配(交叉)以繁殖新后代种群的双亲。然后，对于每两个被选择的染色体，会选择一个交叉点ϑ， ϑ是介于2和请求总数n之间的整数值，因此，可以在不混淆请求分配的位置上直接选取交叉点ϑ， 如图4所示。最后，与请求ϑ到n对应的所有基因被交换，从而产生两个新的染色体。这个过程将一直重复，直到新一代产生的子代染色体数目等于当前一代的染色体数目。其中对于每个随机选择的基因Xmn进行突变，即将数值翻转到相反的值(如从1翻转到0)。

图4 染色体内交叉点的选取

(4)可行性检测和不可行性惩罚：提出的遗传算法会检测杂交和突变后的新后代染色体的可行性。准确地说，明确哪些新染色体是可行的，即它们是否满足约束条件。换言之，对于每个染色体，如果染色体满足约束条件，将确定其每个请求设备都会被分配到一个计算资源。而50%不满足约束条件的不可行染色体通过增加其适应值而受到惩罚，从而降低它们下一代存活的概率。

(5)精英主义和终止准则：提出的遗传算法保存了到目前为止所有生成种群中的最优染色体(可行且适应值最小的染色体)。当满足终止条件时，算法会停止。根据实验结果，当4次连续迭代后，最佳适应度没有改变，或者最大迭代次数达到30时，算法满足终止条件。

4 仿真实验

4.1 仿真环境

利用iFogSim对所提算法进行模拟仿真实验，通过在移动边缘计算环境对比各个算法在能耗、负载均衡、服务延迟、平均执行时间和网络使用情况等方面的性能表现。在模拟实验中，移动边缘计算网络主要由1个云数据中心、80个边缘计算服务器和许多个请求设备组成。其中，所有的边缘计算服务器都被平均分为10个不同的区域，且每个请求设备在单位时间内只能发送一个卸载请求。

为了模拟移动应用被划分为不同子任务后进行卸载的过程，构造了一个虚拟现实游戏，以体现子任务的相互依赖关系，如图5所示。

图5 虚拟现实游戏中子任务的依赖性

该应用程序主要由5个子任务组成，分别为脑电图、客户端、集中计算器、协调器和显示。脑电图和显示必须在本地设备上执行，剩余的子任务可以根据策略进行卸载和分配。对延迟敏感的应用程序对卸载决策有着非常高的要求。一方面，将需要高计算量的模块卸载到云服务器上执行是十分必要的，这样可以最大限度地降低移动设备的能耗；另一方面，边缘计算模块需要尽可能靠近数据源，从而减少模块间数据传输造成的延迟。

4.2 实验结果分析

实验中从Google数据集中选取1000个应用程序对改进的遗传算法进行训练，然后选取部分剩余数据对训练后的网络模型进行测试，从而论证所提算法的通用性和有效性。执行时间作为评价算法性能的关键指标，分析其与改进遗传算法的种群规模与最大迭代次数的关系，有助于所提算法中参数的合理设置。其中考虑了不同规模的计算卸载与资源分配问题N， 且N中的每个值是包含j请求和i资源的一个元组 (j/i)， 实验中将多个元组的值分别设为(30/10)，(60/20)，(100/40)和(140/70)。针对N中的每个值，进行5次不同的实验。算法执行时间与种群规模与最大迭代次数的关系如图6、图7所示。

图6 执行时间与种群规模的关系

图7 执行时间与最大迭代次数的关系

从图6中可以看出，执行时间随着种群规模和问题规模N的增加而继续急剧增加。由于种群规模增加，算法需要更长的时间完成算法的运算，并且问题规模增加，意味着有更多的请求设备需要分配计算资源，算法更加复杂，因此执行时间增长。综合各方面因素考虑，将种群规模设为60最为合理，只需花费中等运行时间而能获得高质量的解决方案。

从图7中可以看出，最大迭代次数的增加会急剧增加算法的运行时间。通常来说，迭代次数越多，获得的最优解越理想，算法的性能更佳，但是付出的执行时间成本过高，为此，综合考虑，将最大迭代次数设置为25，此时，算法可以只花费中等运行时间而得到高质量的解。

4.3 不同算法的对比分析

为了论证所提算法在能耗、负载平衡、延迟、网络使用率等方面的性能，将其与文献[14]、文献[16]、文献[18]、文献[21]进行对比分析，结果如图8所示。其中文献[14]采用了混合整数非线性规划方法解决任务卸载问题；文献[16]设计了一种面向边缘计算的用户请求数量预测模型，并基于此提出任务卸载方案；文献[18]提出一种分布计算卸载模型；文献[21]基于计算卸载和任务分配的联合凸优化目标，采用拉格朗日乘子法进行迭代更新得到最优解。

图8 任务卸载中每种算法产生的资源消耗

从图8中可以看出，随着请求设备数量的增加，各种算法生成的计算卸载和资源分配策略在能耗、负载平衡、延迟、网络使用率等方面基本上都是递增的。所提算法在延迟、网络利用率和负载均衡方面都能取得较好的效果，但在能耗方面表现一般。主要是因为移动边缘计算更倾向于将子任务卸载到本地设备上执行，当本地设备处的资源不足时，子任务被逐层地卸载到上层设备当中。由于一些子任务可以在本地执行而无需网络传输，所以所提算法的延迟较低。并且所提算法更倾向于将子任务卸载到边缘计算服务器中，这使得所有边缘计算服务器的资源利用效率都保持在平均水平，并实现了负载均衡值的最小化。与此同时，边缘计算服务器的性能可以满足更多子任务的处理请求，从而减少了子任务之间的网络传输，进一步降低了整个系统的网络利用率。但由于移动边缘计算设备的处理能力和计算能力远远小于云服务器，因此，在本地设备上处理子任务将导致更高的能耗。

此外，从图8中可以看出，随着应请求设备数量的增加，由文献[18]算法生成的计算卸载和资源分配策略在负载平衡方面表现得很差，且在其它方面也表现得一般。文献[21]算法在除了延迟之外的所有方面的表现都比文献[18]算法要好一些。文献[21]算法综合考虑了两种方法在各个方面的优势，在能耗、负载均衡等方面的性能较为理想。当设备数量较多时，由文献[14]算法生成的策略在延迟方面都有很好的效果，但在能耗方面的效果是最差的。同时，因为文献[21]算法和文献[18]算法更倾向于将子任务卸载到本地设备，而当任务被卸载到具有更高计算能力的边缘计算服务器时，文献[21]算法的性能优于文献[18]算法。当应用数量较多时，文献[16]算法和文献[14]算法的时延呈下降趋势，其性能优于其它两种对比算法。另外，文献[21]算法和文献[14]算法在网络利用率方面具有相似的性能，其结果仅次于所提算法。

5 结束语

由于智能终端设备和物理环境之间会通过传感和驱动的方式进行交互，有着严苛的延迟要求，而设备本身的计算能力有限，因此需要根据需求进行计算卸载，将任务卸载至云和边缘计算服务器中，以合理分配计算资源。所提出的移动边缘计算中基于改进遗传算法的计算卸载与资源分配算法在完成移动边缘计算网络架构设计的基础上，构建包括能耗、平均服务延迟、执行时间以及负载均衡的系统模型，并以能耗、延迟、负载均衡最小化为优化目标，利用改进的遗传算法进行求解，以实现计算的高效卸载与资源的最优分配。此外，利用iFogSim和Google集群对所提算法进行仿真测试，结果表明，算法种群数量和最大迭代次数的合理值分别是60和25，且所提算法得到的计算卸载和资源分配策略在能耗、负载均衡、延迟和网络使用率方面的表现均优于其它算法。

接下来的研究工作是将所提算法应用于更大规模的网络，其中考虑关键请求调度和允许抢占、优先处理等方面。并且还可将多个目标函数扩展至该算法，从而进一步提高计算资源的利用率以及减少延迟和能耗等。