【论文】一种面向移动云计算的多目标任务卸载算法

宋富洪,邢焕来,潘炜

西南交通大学信息科学与技术学院，四川 成都 611756

摘要

计算能力和资源受限的移动设备可将待处理的密集型任务卸载到云端执行，从而增强移动设备的计算能力并减少电池能源消耗（EC）。然而，现有研究在卸载任务时不能较好地均衡移动端的应用完成时间（FT）和EC。提出了基于分解的多目标进化算法（MOEA/D）来同时优化应用 FT 和 EC，并将动态电压频率调整技术引入MOEA/D中，在不增加应用FT的前提下，调节移动设备的CPU时钟频率以进一步降低移动设备的EC。仿真结果表明，与多个算法相比，所提出的算法在多目标性能上更优。

关键词：移动云计算;移动设备;多目标进化算法;任务卸载;完成时间;能源消耗

1 引言

当今，随着移动互联网技术的迅猛发展，诸如平板电脑、智能手机和便携式穿戴设备等智能移动设备已经成为用户的主要计算平台[1]。虽然智能终端和无线通信技术正在日益演进，使得移动设备的计算性能大幅度提升，但由于移动设备受电池容量、计算和存储能力等方面的限制，仍然无法满足计算密集型任务的需求。移动设备较低的计算能力可能会延迟应用的完成时间（FT， finish time），从而很难保证服务质量（QoS，quality of service）。同时，密集型任务会加速消耗移动设备有限的电池能量[2,3]。

无线网络和云计算的不断融合促使了移动云计算（MCC，mobile cloud computing）[4]的产生和发展，MCC 用户可将应用程序的部分任务卸载到具有丰富计算资源的远端云上执行，云端再将任务的执行结果返回到移动设备。一般来说，MCC 的大型云端服务器距离移动用户几十千米甚至更远，用户卸载任务时会产生大量的传输时延，因此，在MCC 环境下的任务卸载适用于时延容忍的大规模计算密集型应用，如在线社交网络、移动电子商务、移动医疗和移动在线学习等。相反地，移动边缘计算（MEC，mobile edge computing）[5]是将轻量级服务器部署在网络边缘，一般距离移动用户1 km以内，传输时延较短，因此，MEC适用于时延敏感的小规模计算密集型应用，如虚拟现实、自动驾驶和交互式在线游戏等。当前，随着信息技术的快速发展和移动用户应用的极大丰富，移动端应用程序越来越复杂，规模也相继增大。本文旨在研究时延容忍的计算密集型应用的任务卸载，即在 MCC环境下的任务卸载问题。

移动设备利用 MCC 技术获取云端服务器的丰富资源和强大的计算能力，从而扩展自身受限的资源以提升移动设备的计算能力。移动设备卸载任务到云端执行，能提高任务的执行效率并大幅度降低移动设备的能源消耗（EC，energy consumption）[6]。但是不合理的任务卸载策略会产生大量数据传输，不仅会增加执行应用的时延，还会大量消耗移动设备的能量。此外，随着移动设备应用任务数的增加，已有的卸载策略不能较好地权衡移动设备的任务FT和EC。因此，如何合理地在移动设备和云端之间卸载任务，在减少应用 FT 的同时，尽可能降低移动设备的EC，是当今MCC领域的重要问题，也称为任务卸载问题。

鉴于此，本文主要研究 MCC 环境下移动设备的应用 FT 和 EC 的多目标任务卸载优化问题，提出了基于分解的多目标进化算法（MOEA/D，multi-objective evolutionary algorithm based on de composition），该算法是分解一个多目标优化问题（MOP，multi-objective optimization problem）以同时优化多个标量的子问题。此外，将移动设备的动态电压频率调整（DVFS，dynamic voltage frequency scaling）技术引入MOEA/D中，采用遗传算子生成一个新解后，对该解实施动态电压调节机制，保证在不增加FT的情况下，进一步降低移动设备的EC。仿真结果表明，本文提出的算法具有可行性和优越性，在多目标性能上优于NSGA-Ⅱ算法、DVFS算法以及原始的MOEA/D算法。

2 研究现状

移动设备将资源密集型和计算密集型的应用程序卸载到云端执行，以弥补自身计算资源不足的问题。如何合理地卸载任务使 FT 降到最低，同时减小移动设备的EC，是MCC中的研究热点。目前，国内外学者对该问题进行了大量研究，可分为3类：1) 最小化应用的总FT；2) 最小化移动设备的EC；3) 同时优化移动设备的应用FT和EC。

当资源受限的移动设备利用 MCC技术卸载密集型应用程序到云端执行时，任务的 FT 是衡量MCC环境下QoS的一个重要指标。Cai等[7]提出了一种需求驱动的任务调度模型，并引入估计方法来预测任务的FT。该文献从移动用户和服务供应商两个方面来研究任务卸载问题，通过一种基于 2D 染色体遗传算法（GA，genetic algorithm）的目标权重方法来最小化移动用户的 FT 并均衡服务供应商的负载。Yang等[8]研究了多用户的计算分区和云资源计算卸载的调度问题，与优化单用户的应用 FT不同，该文献旨在最小化多个用户的平均 FT。Balamurugan 等[9]提出了一种处理器选择算法来有效地卸载应用任务到异构处理器上，该算法通过任务的优先级对移动设备上的应用程序实现高效、快速调度。

另一个衡量MCC环境QoS的重要指标是移动设备的 EC。Kumar 等[10]根据待卸载的任务量和网络性能分析了任务的卸载，认为卸载任务到云端并不总会节省移动设备的 EC，进一步分析可知，卸载任务是否能节省EC取决于卸载的任务量是否超过无线通信的开销。Tong等[11]旨在权衡移动设备的EC 和应用 QoS，并提出了基于应用感知的无线传输调度算法，在满足应用截止时间的前提下，最小化移动设备无线传输的EC。Mahmoodi等[12]建模任务卸载为一个线性优化问题，从而得到更具适应性和可扩展性的模型。与其他只考虑任务先后次序的方法相比，该方法能得到更优的方案。Lin 等[13]研究了在满足应用截止时间的基础上，尽可能最小化移动设备的 EC。首先计算任务优先级以确定任务的执行顺序，再根据此顺序得到具有最小 FT 的初始调度，最后通过启发式算法和DVFS技术来进一步降低移动设备的 EC。但该方法只考虑在满足应用截止时间的基础上降低EC，而未对应用FT进行优化。

一般来说，应用 FT 和移动设备的 EC 之间是相互关联的，减少 FT 势必会导致移动设备的 EC过多，反之亦然，因此，一些研究致力于联合优化这两者。Deng 等[14]提出了基于 GA 的任务卸载策略来同时优化工作流的FT和移动设备的EC，该策略还设计了设备的移动性管理和卸载系统的容错管理。Guo等[15]提出了一种能效动态卸载和资源调度算法，在任务截止时间的硬性条件下，降低卸载过程的EC。Zhou等[16]研究了MCC环境下基于时延传输的多目标工作流调度，并提出了基于GA的算法，在GA的编码中同时考虑了任务的执行位置和执行顺序。通过延长非关键任务的执行时间，以进一步降低移动设备的 EC，该算法虽然能获得大量非支配解以供决策者按需选择，但随着应用任务数的增加，所得解的质量越来越低。

3 模型及问题描述

本节首先介绍 MCC 环境下移动设备的应用表示，包括本地计算模型和云计算模型，然后详细阐述本文的多目标任务卸载问题[13]。

移动设备执行的应用可表示为一个有向无环图（DAG，directed acyclic graph），记为

，节点 vi∈V 表示一个任务；边 e(vi,vj)∈E 表示任务vi和任务 vj之间的先序限制关系，即任务 vi必须在任务 vj开始执行之前完成执行。用 pre(vi)表示节点 vi的前驱节点集，suc(vi)表示节点 vi的后继节点集。N=|V|表示应用的总任务数，一般不超过100个。无任何前驱节点的任务节点为开始任务，记为 vstart，无任何后继节点的任务节点为结束任务，记为vend。

3.1 本地执行模型

用Tc(vi)、Ttxd(vi)和Trxd(vi)分别表示任务vi在云端的执行时间、移动设备发送任务vi所需时间和移动设备从云端接收任务vi的输出数据的所用时间。

如果任务 vi在移动设备的第 k 个处理器上执行，则移动设备执行任务vi的EC为

其中，γk∈[2,3]，

是任务vi在第k个处理器上以最大运行频率执行时的EC。

任务的执行必须满足任务之间的先序限制关系，任务开始执行前，其所有前驱任务已被卸载完成。若任务vi在本地处理器上执行，则执行的准备时间为

3.2 云计算模型

若将任务vi卸载到云端执行，则在无线发送信道上的准备发送时间为

进一步可得移动设备发送数据的EC为

任务vi在云端服务器上执行完成后，需将执行结果返回移动设备，则传输返回结果的准备时间为

式(8)表明，任务vi在云端执行完毕后，可立即将vi的输出数据发送给移动设备。

3.3 问题描述

本文在 MCC 环境下多目标任务卸载算法的主要目标是最小化移动设备的应用FT和EC。对于给定的一个应用（有向无环图G），算法的目标是产生多个可行解

表示应用的任务执行位置向量，其中，

则表示任务vi在移动设备的某个处理器上执行，loci=K+1表示任务vi在云端执行；

表示应用的任务执行顺序向量，其中，ord1=vstart， ordN=vend，ordi∈{v2,...,vN-1}。任务的执行必须满足任务间的先序限制关系，即任务的执行必须在所有前驱任务完成执行后才能开始执行。已知L和O后，就可以确定任务在本地核执行还是在云端执行以及执行顺序，因此，一个可行解?就是应用的一个卸载策略。

为了计算应用FT，需计算每个任务的开始时间和结束时间，因此，移动设备的应用 FT 为结束任务vend的FT，即

其中，locend为结束任务vend的执行位置。

若任务在本地执行，则移动设备的EC为在本地核上执行的 EC；若任务在云端执行，则移动设备的EC为发送数据的EC。因此，在整个应用的执行过程中，移动设备的EC为

基于以上两个方面的计算，本文在MCC 环境下的多目标任务卸载问题可描述为：找到一种或多种卸载策略，在该策略下，能够最小化移动设备的应用FT和EC，即

4 算法设计

MOP可通过式(12)来定义[19

式(12)表明，MOP有m个优化目标，且目标之间一般是相互冲突的，其中，

是n维决策向量,

表示该优化问题的两个约束条件。

定义1 Pareto占优

设 x1,x2∈X，当且仅当满足式(13)时，称x1Pareto占优x2。

也可称为解x1支配解x2，记为x1?x2。

定义2 Pareto最优解

对于式(12)描述的MOP，若x*∈X满足式(14)，则称x*为Pareto最优解。

定义3 Pareto最优解集

对于 MOP，所有 Pareto 最优解组成的集合为Pareto最优解集，记为PS

定义4 Pareto前沿

将定义3中的PS对应的目标函数在空间上形成的曲线称为Pareto前沿。

在 MCC 环境下，移动设备可将密集型的任务卸载到云端执行，以降低设备 EC，但需将任务执行的相关数据传输到云端，这势必会增加传输时延，延迟了应用FT。因此，本文优化的移动设备应用FT(G)" role="presentation">

是两个相互冲突的优化目标，不存在同时使两个目标都达到最优的解，取而代之的是找到优化问题的Pareto最优解集。

目前，对于 MOP 的求解主要采用多目标进化算法（MOEA，multi-objective evolutionary algorithm）[20]，MOEA可得到近似最优的Pareto解集，其中，每个解表示 MOP 中多个目标之间的权衡。MOEA/D[17]是求解 MOP 的一个全新框架，该框架将MOP分解为多个标量形式的单目标优化子问题，再对多个子问题同时进行优化。此外，MOEA/D与单目标GA相融合，利用遗传操作产生新个体，通过多次迭代进化，获得MOP最优前沿。理论表明， MOEA/D 比 NSGA-Ⅱ[18]具有更低的计算复杂度，且收敛速度更快，所以一提出就受到了学术界的广泛关注，已成功应用于一系列复杂 MOP 中[21,22,23,24]。因此，本文采用MOEA/D求解MCC环境下的多目标任务卸载问题，同时优化

。

4.1 分解方法

MOEA/D将MOP分解成多个标量形式的单目标优化子问题，再同时优化这些子问题，分解方式有多种，本文采用Tchebycheff方法进行MOP的分解[17]，其计算如式(16)所示。

4.2 初始化

如 3.3 节所述，解

的编码由两部分组成，分别是任务的执行位置和执行顺序。对于执行位置来说，任务可在移动设备的任一处理器上执行或卸载到云端执行。本文随机生成每个任务的执行位置，具体产生方式即任务执行位置初始化伪代码，如算法1所示，其中，randInt(1,K+1)表示随机生成[1,K+1]之间的整数。

算法1 任务执行位置初始化伪代码

1) for i=1 to N do //N为应用任务数

2) loci=randInt(1,K+1) //随机生成vi的执行位置

3) end for

在任务执行顺序初始化方面，必须满足任务之间的先序限制关系，即任意边 e(vi,vj)∈E，任务 vi必须在任务 vj开始执行之前完成其执行，文献[16]给出了任务执行顺序伪代码如算法2所示。

算法2 任务执行顺序初始化伪代码

1) S=? // 待排序任务集

2)O={vstart}" role="presentation">

//已排序任务集

3) T=T-{vstart}

4) while T≠? do

5) for i=1 to N do

6)

7)S=S+{vi}

8) end if

9) end for

10) 从S中随机选择一个任务vs

11)S=S-{vs}

12)T=T-{vs}

13)

//在O的末尾添加vs

14) end while

设种群规模为P，则需要循环执行P次算法1和算法2的伪代码，实现任务执行位置和执行顺序的初始化，下面给出基于 MOEA/D 的多目标任务卸载算法的初始化过程。

4.3 基于MOEA/D的多目标任务卸载算法

DVFS 能降低移动设备的高性能处理器的执行频率，使得高性能处理器与低性能处理器具有相同的执行性能，那么在低性能处理器上执行任务可降低移动设备的 EC，因此，本文将 DVFS 技术融入MOEA/D中，以进一步降低移动设备的EC。首先给出 DVFS 算法的伪代码[13]，随后描述基于MOEA/D的多目标任务卸载算法过程。

算法3中第9行和第14行表示执行DVFS算法后不增加整个应用的FT，因此，在不增加FT的基础上，达到降低移动设备EC的目的。

下面描述在MCC环境下，基于MOEA/D的多目标任务卸载算法过程，记为MOEA/D-DVFS。在Step1中，采用4.2节中的初始化过程对算法进行初始化，包括P个权重向量和P个个体的种群。Step3中对xi的两个邻居个体xk和xl进行遗传操作，产生新的个体，本文采用文献[16]中的遗传算子（交叉、变异）来进行遗传操作。在 Step4 中，对新个体 y实施DVFS算法，产生新的策略y以进一步降低移动设备的EC。

5 仿真实验

本节首先描述4种算法的性能评价指标，然后给出实验场景及参数设置，最后MOEA/D-DVFS与NSGA-Ⅱ、DVFS以及原始的MOEA/D进行完整的算法性能比较。

5.1 性能评价指标

为了综合评估MOEA/D-DVFS的算法性能，使用4种算法性能度量指标。设PFref为较好接近于真实Pareto前沿的参考集，PFknow为算法获得的最优解集。一般情况下，对于高复杂性的 MOP[24]（如本文的多目标任务卸载问题）并不知道真实的Pareto 前沿，因此，将所有算法运行后得到的最优解组合起来，求出非支配解作为参考集PFref。

1) 反向世代距离指标

反向世代距离（IGD，inverted generational distance）可衡量算法非支配解集的收敛性和多样性， IGD值越小则表明算法整体性能越好，定义如下

其中，d(sr,PFknow)是sr与PFknow中每个解的最小欧式距离。

2) 世代距离指标

世代距离（GD，generational distance）可判断算法获得的最优解集与真实 Pareto 前沿的收敛程度，定义如下

3) 平均计算时间指标

将每种算法运行 50 次所消耗的平均计算时间（ACT，average computation time）作为衡量算法计算复杂度的指标。

4) Pareto前沿曲线

由于多目标任务卸载问题的优化目标为应用FT和移动设备EC，为典型的双目标优化问题。因此，可将算法得到的Pareto解集绘制在二维坐标系中显示出来，Pareto曲线可以直观展示算法的Pareto解集的分布性和收敛性。

5.2 实验结果

采用随机生成应用（即DAG）的方式来产生实验场景[13]，模拟10种具有不同任务数的DAG，任务数N分别为10,20,…,100。

假定移动设备具有K=3个异构处理核，核1为低功率处理器，核3为高功率处理器。3个处理器在最大运行频率下的功率消耗 Pk分别为 P1=1、P2=2、P3=4。移动设备卸载任务时的传输功率

。每个处理器具有H=4种可调节的频率，频率调节因子分别为 αk,1=0.2、αk,2=0.5、αk,3=0.8、αk,4=1；且γk=2，k=1,2,3。

为了验证本文提出的MOEA/D-DVFS在4种性能评价指标上的优越性，比较以下4种算法，每种算法独立运行 50 次，统计每次运行的IGD、GD和 ACT值，并且计算这 50次的均值和标准差。

1) NSGA-Ⅱ（A1）：Zhou等[16]针对基于时延传输的多目标工作流调度问题，提出用NSGA-Ⅱ来解决，通过延长非关键任务的执行时间来降低移动设备的EC。种群规模和最大迭代次数都设为100，交叉概率和变异概率为1。

2) DVFS（A2）：Lin等[13]提出了DVFS技术来进一步降低移动设备的EC。

3) MOEA/D（A3）：Zhang 等[17]提出了MOEA/D，将 MOP 分解为多个标量的子问题。设分解方式为Tchebycheff，种群规模P=100终止条件为达到最大迭代次数100，邻居大小T=10，遗传算子的交叉概率和变异概率均为1。

4) MOEA/D-DVFS（Prop.）：本文提出的基于MOEA/D的多目标任务卸载算法，该算法将DVFS技术引入原始的 MOEA/D 中来进一步降低移动设备的EC，算法参数设置与MOEA/D相同。

4种算法在所有测试场景下的IGD和GD统计结果如表1 所示，显然本文提出的MOEA/D-DVFS的IGD和GD值均小于其他3种算法，表明在 MCC 环境下的多目标任务卸载问题上，本文提出的算法性能最优。如4.1节所述， IGD 反映算法的整体性能，可同时评估算法的收敛性和多样性，IGD 值越小，表明算法整体性能越好。同样，提出的算法也得到了最小的 GD，该值反映出值越小则算法的近似Pareto解集越接近于真实的 Pareto 前沿。此外，DVFS 在所有实验场景下具有0值标准差，由于DVFS是一种启发式算法，与其他3种随机搜索的进化算法相比，不具有随机性，因此，DVFS 算法运行多次得到的Pareto解集一样，且通过比较IGD和GD值证明解质量较差。

ACT 可评价算法计算复杂度，ACT 统计结果如表2所示，统计了所有算法运行50次的ACT，其中，最优值加粗。由表2可看出，当N=10、20、30、40 时，A2 的 ACT 值最小；当 N 大于或等于50时，A3的ACT值最小。所以，当应用任务数较大时，A3的时间复杂度较低，算法更具有实用性。此外，本文所提算法的 ACT 值大于 A3，由于所提算法在 A3的基础上增加了 DVFS技术，需消耗一定时间，但两者 ACT 值非常接近，因此，所提算法在解决多目标任务卸载问题上同样具有实用性。

注：表中x(y)的x和y分别表示均值和标准差，最优值加粗。

图14种算法在4种场景下的近似Pareto曲线

注：表中最优值加粗。

为了直观地展示算法的Pareto解集的分布性和收敛性，4种算法在4种场景下的近似Pareto曲线如图1所示，绘制了4个实验场景（即N=10、40、70、100）中 4 种算法独立运行 50 次得到的近似Pareto解集。横坐标为应用FT，纵坐标为移动设备EC，且两者均是最小化目标，由图1可知，本文所提算法更接近于真实的Pareto前沿。

综上所述，本文提出的算法在4种算法性能评估指标上更优，能较好地解决多目标任务卸载问题。

6 结束语

任务卸载问题是MCC环境中的重要研究内容，设计卸载策略时的一个关键问题是怎样均衡移动设备的应用FT和EC。以往的研究工作主要关注降低移动设备EC或者减少应用FT，较少同时优化两者，即使联合优化两个目标，也不能在FT和EC之间取得较好的平衡。而且，当应用任务数量较大时，传统方法也不能较好地解决本文问题。

鉴于此，针对MCC环境下的多目标任务卸载问题，本文提出了基于 MOEA/D 的多目标进化算法，该算法将 DVFS 技术引入 MOEA/D 中，来进一步降低移动设备的 EC。仿真结果表明，在多个实验场景下，与NSGA-Ⅱ、DVFS、原始MOEA/D算法相比，本文所提算法在IGD、GD、Pareto前沿曲线以及ACT指标上更优，从而能较好地均衡移动设备的应用FT和EC。

作者简介 About authors

宋富洪（1992-），男，贵州遵义人，西南交通大学博士生，主要研究方向为移动边缘计算和多目标进化算法 。

邢焕来（1983-），男，河北唐山人，西南交通大学副教授，主要研究方向为计算机网络、进化计算和边缘计算 。

潘炜（1959-），男，湖南岳阳人移动应用 云计算，西南交通大学教授、博士生导师，主要研究方向为通信与信息系统、微波光子学等 。

END

声明：文本来源若标注错误或侵犯到您的权利，烦请发公众号消息告知，我们将立即删除！

投稿邮箱：wlwxb@bjxintong.com.cn

『物联网学报』办刊方针和业务范围为：刊载物联网及相关交叉学科研究领域具有创新性的基础理论、关键技术、研究热点及基础与应用研究成果的学术论文，充分展示我国研究成果，反映我国的前沿研究水平，为我国正在迅速发展的物联网科技创新与产业服务提供学术支持，促进我国物联网技术与应用领域的发展。

扫码关注物联网学报官方微信获取更多！

（编辑：拼字网 - 核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!