一种基于遗传算法的多站点协同计算卸载算法*

季子豪，江凌云

(南京邮电大学通信与信息工程学院，江苏 南京 210003)

1 引言

随着物联网IoT(Internet of Things)、5G技术的发展，终端设备的数量迅速增加，其产生的数据量呈指数级增长，当前核心网的带宽无法承受日益庞大的数据量传输。此外，增强现实、虚拟现实和无人驾驶等，尤其是基于人工智能的新型应用程序的出现对时延和功耗提出了更高的要求[1]。IoT终端的计算、存储和电池能力有限，无法独立完成这些计算密集型应用任务。边缘计算(Edge Computing)为解决这些问题提供了有效途径。边缘计算的思想是在靠近终端侧部署计算资源和存储资源，对终端的计算任务和存储任务就近处理，以此优化计算密集型应用的响应延迟[2]。

计算卸载是边缘计算领域的一项关键技术[3]。计算卸载技术通过将资源受限的IoT终端的计算任务卸载到计算资源更强的边缘节点或中心云执行，可以优化物联网应用的响应延迟，同时有效降低终端设备的能耗。关于单一设备的计算卸载已经有很多研究人员进行了研究，即将应用程序完整地部署在一台设备上，在进行卸载决策时，对应用程序的各任务进行代价分析，判断哪些任务卸载到边缘节点执行，哪些任务在本地执行，可以使得应用程序的总执行代价最小。

但是，在未来的IoT环境中，大部分应用服务都将以分布式架构的形式进行部署，一个完整的IoT应用被拆分为多个具有依赖关系的子任务，这些子任务初始部署在多个站点中，例如IoT终端、边缘节点或中心云，这些站点协作完成整个应用任务。但是，受计算资源、存储容量和电池电量的影响，在终端进行数据处理可能会耗费过长时间，需要将自身的计算任务卸载到边缘节点或中心云处理[4]；同样，受网络带宽的影响，终端和边缘节点之间的数据传输代价可能大于本地执行代价[5]，不适合卸载任务。在这样的场景下，站点间的通信代价无法被简单忽略，进行计算卸载决策、寻找最优任务分配策略十分具有挑战性。

本文的其余部分组织如下：第2节介绍计算卸载的相关工作；第3节建立多站点协同计算卸载问题的数学模型；第4节描述遗传算法，并利用遗传算法寻找最优卸载决策，提出基于遗传算法的多站点协同计算卸载算法GAMCCO(Genetic Algorithm-based Multi-site Collaborative Computation Offloading);第5节进行仿真实验，并对结果进行讨论；最后对本文进行了总结和展望。

2 相关工作

作为边缘计算领域的一项关键技术，计算卸载已经得到了广泛的研究。文献[6]提出了MAUI计算卸载框架，该框架将计算卸载问题转化为整数线性规划问题，将一些繁重的计算任务卸载到邻近的边缘云服务器上，以降低移动设备的能耗。文献[7]提出了基于遗传算法的任务调度方案，该方案将应用程序划分为多个子任务，分别计算每一个子任务的本地执行代价和远程执行代价，构建具有时延约束的能耗模型，最后利用遗传算法分析该能耗模型，得出最佳卸载方案。文献[8]将应用程序建模为由细粒度任务组成的通用拓扑结构，这些细粒度任务可以在本地或边缘节点上执行，然后将计算卸载问题规约为具有时延约束的工作流调度问题，提出了基于拉格朗日松弛的聚合代价算法计算工作流调度问题的最优解。文献[9]针对单一云服务器计算资源有限的情形，考虑将计算任务卸载到多个云服务器上，提出了基于遗传算法的多站点计算卸载决策GAMCO(Genetic-based decision Algorithm for Multi-site Computation Offloading)，实现应用程序的性能提升。文献[10]实现了一个多站点自适应卸载框架，该框架把设备的硬件信息变化和实时网络条件纳入考量，将移动设备的计算任务卸载到自组织云、边缘云和中心云中，以加快应用程序的执行。文献[11]针对动态环境中的计算卸载，采用随机博弈方法建立了动态模型，并提出多代理随机学习的方法寻找最优决策。文献[12]提出了一种能量高效的动态上传策略，利用动态电压和频率分配技术优化移动设备的性能。文献[13]则是采用马尔可夫决策过程，将多站点卸载问题转化为具有时延约束、最小卸载代价的最短路径问题，并提出基于能耗的多点卸载策略算法，寻找多站点任务卸载的解决方案。

但是，以上关于计算卸载的研究工作都是假设应用程序初始完整地部署在一台设备上，并将计算任务从该设备上卸载到其余站点执行，并未考虑到应用程序分布式部署在多个设备上的情形。因此，本文基于应用程序分布式部署的情形，将多站点协同计算卸载问题建模为一个通用的代价模型，利用遗传算法寻找最优的卸载方案，以最小化总执行代价。

3 计算卸载模型

本节首先基于应用程序分布式部署的假设，对多站点协同计算卸载的场景进行描述，并以此构建任务依赖关系图。然后根据站点间通信代价、任务执行的时延代价和能耗代价进行模型构建，最终得出模型的数学表达式。

3.1 系统场景

传统的计算卸载场景如图1所示。终端设备上有一个完整的应用程序待执行，应用程序由多个子任务组成，根据相应的计算卸载算法判断哪些子任务在本地执行，哪些子任务需要卸载到边缘节点或中心云执行。针对这种场景的计算卸载算法无法用于应用程序在多站点分布式部署的情形。

Figure 1 Edge computing scenario for single device computation offloading

本文考虑这样一个需要多站点协同计算的边缘计算场景，如图2所示。该场景包含多个IoT终端、1个边缘节点和1个中心云，一共涉及K个节点。物联网应用程序在开发时已经被划分为K个子任务V={v1,v2,…,vK}，并以分布式的形式部署在IoT终端、边缘节点和中心云上，应用程序执行时需要这些站点协同计算。应用程序的子任务之间具有依赖关系，初始部署在各个IoT终端上的计算任务既可以在该终端本地执行，也可以根据上下文信息卸载到边缘节点或中心云执行。

Figure 2 Edge computing scenario for multi-site collaborative computation offloading

Figure 3 Dependency relationship graph among application components

3.2 系统代价模型

3.2.1 参数描述

下面对计算卸载模型涉及的参数进行简要描述：

(1)计算卸载方案为X={x1,x2,…,xK}，其中xk∈{-1,0,1}，xk=-1表示将任务vk卸载到云端执行，xk=0表示将任务vk卸载到边缘节点执行，xk=1表示在站点k处执行即本地执行。

(3)本文构造的计算卸载代价模型由时延代价和能耗代价组成，用于寻找应用程序组件的最佳卸载决策，以最小化应用程序的总执行代价。计算卸载决策X所对应的应用程序代价如式(1)所示：

(1)

其中，T(X)和E(X)分别表示应用程序使用卸载方案X的时延代价和能耗代价；Torigin和Eorigin分别表示应用程序组件不经过计算卸载，直接按照初始部署执行的总时延和能耗代价，可以认为是一个常数；α和β分别表示时延和能耗在整个代价模型中所占的比重。

3.2.2 时延代价模型

时延代价包括任务计算时延和数据通信时延。对于每一个站点k，fk表示该站点的计算能力，任务vk在各站点本地的计算时延可以表示为式(2)：

(2)

在边缘节点的计算时延由式(3)表示：

(3)

在云端的计算时延由式(4)表示：

(4)

其中，fe和fc分别表示边缘节点和云端的计算能力。

(5)

当计算任务vi和任务vj的卸载目的地一致时，它们之间的数据通信时延为0。

时延模型的优化目标是找到应用程序的最佳计算卸载决策Xbest，满足应用程序各组件的时延代价加权最小。

根据候选卸载决策X给出的应用程序时延模型如式(6)所示：

(6)

(7)

3.2.3 能耗代价模型

与终端相比，边缘节点和云端的电量近乎是无限的，因此本文只考虑终端产生的能耗。终端产生的能耗包括计算能耗和数据传输的通信能耗。与以往关于计算卸载的研究类似，在数据传输的通信能耗这一方面，本文只考虑终端发送数据的能耗，因为与发送功率相比，接收功率往往很小，可以忽略不计。

任务vk在各站点的计算能耗如式(8)所示：

(8)

(9)

能耗模型的优化目标是找到应用程序的最佳计算卸载决策Xbest，使得应用程序各组件的能耗代价加权最小。

根据候选卸载决策X给出的应用程序能耗模型如式(10)所示：

(10)

4 GAMCCO算法

由于考虑了多站点之间的任务依赖关系，求解最佳计算卸载策略的难度大大提高，很难在多项式时间内计算出最优解。因此，本文引入遗传算法，提出GAMCCO算法来寻找计算卸载策略的最优解。

遗传算法借鉴了自然界的遗传选择和自然淘汰的生物进化过程，其核心思想是模拟一个人工种群的进化过程，通过选择、交叉和变异机制，经过若干代进化后，产生最优个体，是一种高效的全局搜索算法，适合处理传统寻优算法难以解决的非线性问题。

遗传算法的个体对应到计算卸载问题中即为计算卸载方案，染色体表示经过编码后的卸载方案，基因表示每个任务的卸载目的地。

4.1 编码和初始种群

实现遗传算法的第1步是对求解问题的解空间进行编码。在本文提出的多站点协同计算卸载模型中，应用程序被划分为K个需要卸载的子任务，因此在遗传算法中每条染色体由K个基因组成，部署在各站点的任务可以在本地执行，也可以迁移到边缘节点或迁移到云端执行，因此每个基因有3个可能值(云：-1，边缘：0，本地：1)。一条染色体就是一个可能的计算卸载方案，如图4所示，是一个由K个基因构成的染色体。

Figure 4 A chromosome with K genes

初始种群使用随机构造的方法产生，初始种群规模为M。

4.2 适应度函数

遗传算法对一个个体(解)的好坏用适应度函数值来评价[14]。在本文中，适应度函数定义为应用程序计算卸载总代价的倒数，如式(11)所示，以此评判每个计算卸载方案的优劣，适应度函数值越大，对应的总代价越小，那么计算卸载方案越好。

(11)

在每一次的迭代进化过程中，采取精英选择的策略保留每一代的精英解。进行第i次迭代时，首先计算第i代种群中每个个体的适应度函数值，并将种群中的个体按照适应度函数值大小降序排列，然后丢弃适应度较低的后一半个体，选择种群中适应度较高的前一半个体延续到下一步的交叉过程。

4.3 交叉过程

交叉过程中，2个父亲染色体按照某种规则交换其部分基因，产生子代染色体。本文选取了单点交叉的方式进行交叉操作。所谓单点交叉，就是在父亲染色体中随机选择1个交叉点，然后以交叉点为界，交换2个父亲染色体交叉点位置的左右基因，产生2个新的染色体。一个单点交叉的例子如图5所示。

Figure 5 An example of a single point crossing

4.4 变异过程

变异操作是根据设定的变异概率选取染色体的若干位基因改变其值，其目的是产生新的个体，保持种群的多样性，防止过早陷入局部最优。本文对交叉过程产生的染色体种群进行基因变异。另一方面，变异操作完成后，为了将尽可能多的卸载方案纳入考量，防止适应度函数过早收敛，本文构造与当前的精英染色体数目相等的随机染色体，两者共同组成新一代的染色体种群。在这一步中使用随机染色体和精英染色体共同组成新种群的方法则是对经典遗传方法的改进，经典遗传方法只会保留精英个体，容易过早收敛。

4.5 终止条件

经过上述遗传算法的操作，可以得到新一代的染色体种群，根据本文提出的适应度函数，对新一代种群进行适应度评估。如果当前迭代次数已经达到了预先设定的最大值，或者在连续的若干代染色体种群中，最低适应度函数值没有改进，那么遗传寻优过程的终止条件得到满足，算法终止；否则，继续重复遗传迭代进化过程，直至满足算法的终止条件。

4.6 算法流程

本文提出的卸载架构如图6所示，其中设备D1、D2和D3是终端节点，具备计算和本地组网功能，边缘节点作为控制调度器进行参数收集和卸载决策。云、边缘节点和终端共同构成了一项服务。UE是用户设备，由它来调用该服务。当边缘节点接收到用户的调用请求后，分析各站点的硬件信息和网络条件，进行分析决策，并将决策结果告知各站点进行计算，最终将计算结果返回给用户。

Figure 6 Offloading framework

基于遗传算法的多站点协同计算卸载算法(GAMCCO)的流程图如图7所示。

Figure 7 Flow chart of GAMCCO

5 仿真和评估

本节将使用Matlab对提出的GAMCCO算法进行仿真并加以分析。

5.1 参数设置

仿真场景包括1个中心云、1个边缘节点和多个终端节点，总计为K个。对于终端节点，假设除了部署在各节点的任务不同外，它们的硬件完全相同，即拥有完全一样的计算能力和功耗。仿真实验的部分参数如表1所示。

以图像拼接应用为例，图像拼接技术的原理是根据图像重叠部分将多幅衔接的图像拼合成一幅高分辨率全景图。目前图像拼接过程主要包括以下几个主要步骤：图像预处理、图像配准、图像融合与边界平滑。其中，图像预处理主要是对各摄像终端采集的图像进行几何畸变校准和噪声点抑制，使

Table 1 Parameters of simulation experiment

参考图像不存在明显的几何畸变。该步骤可以在各摄像终端直接运行，当终端资源受限时可以选择卸载到边缘节点或云端运行。本文分析了此应用程序内部的方法调用关系，将其细分为由10个任务组成的应用，并构造相应的任务依赖关系图，然后利用模拟的数据集进行仿真实验。以下Cttotal是根据一组模拟的数据集计算出的时延代价矩阵，Cttotal中的行代表应用程序的子任务，列代表云端、边缘节点或本地，Cttotal[i][j]表示应用程序子任务vi在站点j处执行的总代价(包括通信时延代价和计算时延代价)。当给定卸载方案X={x1,x2,…,xK}时，根据Cttotal和X即可计算出式(1)中T(X)所表示的应用程序总时延代价。同理，总能耗代价E(X)也可根据能耗代价矩阵和卸载方案X计算得到。设置了时延因子α和能耗因子β后，式(1)的总代价W(X)也可计算得出。

X′表示初始种群中的卸载方案样本的集合，它的每一列都表示一个卸载方案。由于本文将初始种群设置为100个，所以X′的列数为100，行数为子任务数。实际实验时，本文使用多组模拟的数据集计算平均结果，尽可能确保实验结果不具备偶然性。

5.2 结果分析

遗传算法的参数对GAMCCO算法的性能有着很大的影响，例如初始种群规模、突变概率和遗传迭代次数等。为了使GAMCCO算法获得最佳性能，本文利用控制变量的方法研究了突变概率和遗传迭代次数对总代价的影响。图8展示了突变概率对算法总代价的影响。具体设置为初始种群规模100，迭代次数100，突变概率在[0,0.2]变化，同时适应度函数中的时延因子α和能耗因子β都设置为0.5。从图8可以看出，在[0,0.04]内，总代价呈下降趋势，然后随着突变概率的增加，总代价上升，突变概率增加到0.15以后，总代价上下起伏。这是因为随着突变概率的增加，种群中的较优解可能会变异为较差解，导致性能下降。

Figure 8 Impact of mutation probability on the performance of the algorithm

图9展示了遗传迭代次数对算法总代价的影响。具体参数设置为初始种群规模100，突变概率0.04，迭代次数从1增加至100，时延因子α和能耗因子β都为0.5。从图9可以发现，随着迭代次数的增加，总代价虽有起伏，但仍呈下降趋势，当迭代次数达到80后，代价曲线基本平稳。

Figure 9 Impact of the number of genetic iterations on the performance of the algorithm

根据以上实验，本文将遗传算法参数设置为种群数100，突变概率0.04，遗传迭代次数100。为了评估所提算法的可行性和性能，将GAMCCO算法的结果和以下几种卸载方案对比：

(1)本地卸载方案(Local)：所有站点的计算任务都在各站点本地执行。

(2)边缘卸载方案(Edge)：所有站点的计算任务都迁移到边缘节点执行。

(3)遗传方案(GA)：使用遗传算法的经典实现对本文所建立的代价模型进行遗传寻优。

(4)多站点卸载方案(GAMCO)：对该算法的代价模型和卸载方案进行了扩展，使其能适用于本文的多站点协同计算卸载的场景，并进行了仿真。

图10～图12展示了GAMCCO算法和以上4种卸载方案的对比。图10中时延因子α和能耗因子β都设置为0.5，横坐标为遗传迭代次数，纵坐标为总代价，由于本文所建立的代价函数模型是卸载方案代价与本地代价的比值，因此纵坐标的总代价没有单位。

Figure 10 Comparison of 4 offloading schemes when α=0.5 and β=0.5

图11中时延因子α设置为1，能耗因子β设置为0，这时只考虑时延代价。

Figure 11 Comparison of 4 offloading schemes when α=1 and β=0

图12中时延因子α设置为0，能耗因子β设置为1，此时考虑的是能耗代价。

Figure 12 Comparison of 4 offloading schemes when α=0 and β=1

从图10～图12中可以发现，GAMCCO算法求出的方案均优于其余4种卸载方案。和GAMCCO算法相比，GA算法的曲线收敛较快，这是由于本文在实现GA经典方法时，在遗传选择的步骤中仅仅使用精英选择的策略筛选出了精英解，并没有对种群的其余个体进行替换，导致大部分的卸载方案都没有被考虑进去，从而过早陷入了局部最优，最差的情况在到达第30次迭代左右就收敛。而GAMCCO算法在遗传迭代步骤中，使用精英选择策略+随机解替换的方式，筛选出当前种群的较优解，同时将较差解替换为随机解，考量到了更多的卸载方案，因此收敛性能较好。但是，无论是GAMCCO还是GA算法求出的方案，都优于本地执行和边缘执行。而GAMCO算法则是采用了2个初始种群进行遗传迭代，即采用固定种群+随机种群的方式，也能避免过早收敛的情况，如图12所示，迭代到达80次才收敛，但其性能仍然劣于本文提出的GAMCCO算法的。GAMCCO算法可以有效降低多站点协同计算卸载时的总代价。

6 结束语

随着物联网和分布式服务的发展，未来物联网应用程序将普遍采用分布式部署的方式。然而分布式部署引入了站点间任务依赖的问题，使得这种场景下的计算卸载更为复杂。为了优化应用程序的执行代价(时延和能耗)，本文提出了基于遗传算法的多站点协同计算卸载算法GAMCCO。该算法分析了应用程序各站点、各任务之间的依赖关系，将计算任务卸载到边缘节点或云端，以缩短应用程序的执行时间，降低终端的能耗。实验结果表明，GAMCCO算法可以有效减少应用的执行时间，降低能耗代价。本文还将GAMCCO算法和GA算法、GAMCO算法进行了比较，GAMCCO算法比GA算法收敛更慢，不会过早收敛，性能也优于GA和GAMCO算法的。但是，本文提出的算法并不总是能得到最优解，在实验中存在着收敛较快，陷入局部最优的情况。未来将继续对代价模型进行完善，同时考虑将遗传算法和其他的启发式算法相结合，尽可能减少陷入局部最优的情况。