移动边缘环境下面向工作流管理的计算迁移方法

伏舒存 付章杰 邢国稳 刘庆祥 许小龙

摘 要：针对移动边缘环境下移动设备大量的能源消耗问题，为了优化移动设备的能源消耗，提出一种能耗感知的工作流计算迁移（EOW）方法。首先，基于排队论分析边缘设备中计算任务的平均等待时间，建立了移动设备的时间模型和能耗模型;然后，基于非支配排序算法（NSGAⅢ）提出对应的计算迁移方法，对工作流的计算任务进行合理的分配，将一部分计算任务留在移动设备处理，或者迁移到边缘计算平台和远程云端，实现每个移动设备的节能目标;最后，通过CloudSim仿真平台对提出的计算迁移方法进行仿真和对比实验。实验结果表明，EOW方法能够明显地减少每个移动设备的能源消耗，同时满足每一个工作流的截止时间的要求。

關键词：能源消耗;计算迁移;边缘计算;工作流;截止时间

中图分类号：TP338.6

文献标志码：A

Abstract： The problem of high energy consumption for mobile devices in mobile edge computing is becoming increasingly prominent. In order to reduce the energy consumption of the mobile devices， an Energyaware computation Offloading for Workflows （EOW） was proposed. Technically， the average waiting time of computing tasks in edge devices was analyzed based on queuing theory， and the time consumption and energy consumption models for mobile devices were established. Then a corresponding computation offloading method， by leveraging NSGAⅢ （Nondominated Sorting Genetic Algorithm Ⅲ） was designed to offload the computing tasks reasonably. Part computing tasks were processed by the mobile devices， or offloaded to the edge computing platform and the remote cloud， achieving the goal of energysaving for all the mobile devices. Finally， comparison experiments were conducted on the CloudSim platform. The experimental results show that EOW can effectively reduce the energy consumption of all the mobile devices and satisfy the deadline of all the workflows.

英文关键词Key words： energy consumption; computation offloading; edge computing; workflow; deadline

0 引言

移动设备由于其便捷性和扩展性被人们广泛地使用，移动支付、定位导航、自然语言处理等移动应用已经完全融入到人们生活的各个方面[1]。在用户使用移动应用时，应用程序的执行通常需要一定的物理资源，但是，由于移动设备的物理资源有限，很难运行复杂且计算需求大的应用，结果导致移动应用很难满足用户的服务质量需求。

为了缓解移动设备物理资源受限的压力，为移动用户提供更高质量的服务，云计算技术被引入到了移动环境[2]。移动应用中的一部分计算任务可以借助计算迁移技术，把这些计算任务通过无线网络或者蜂窝网络从移动终端迁移到远程云数据中心执行[3-4]。

移动云计算技术扩展了移动设备的资源，并且很大程度上降低了移动设备在执行移动应用时产生的能源消耗[5];然而，由于云数据中心往往是集中式的，它们通常远离移动用户，因此通过广域网（Wide Area Network， WAN）在移动设备和云平台之间进行计算迁移而导致的传输延迟是不可忽视的。这种传输延迟导致设备产生额外的能量消耗[6]。

移动边缘计算是一种减少传输延迟和移动设备额外能源消耗的方法。边缘计算平台将移动用户附近分散的资源（包括计算资源、存储资源等）统一的管理，为移动用户提供高效的服务。边缘计算设备（例如朵云等）作为部署在用户附近的服务器集群，可以构建成一个移动边缘计算平台同时为周围的移动设备提供访问接口，为用户提供服务[7]。但是边缘设备的物理资源相对于云数据中心是有限的，当大量并发的应用被迁移到平台上，其中一部分计算任务必须在边缘设备中排队等待执行[8]。随着用户需求的不断增加，越来越多的计算密集型应用出现，这些应用可以被构建成由任务和数据依赖的工作流[9-10]。当大量并发的工作流任务被迁移到边缘设备时，边缘设备只能够提供相对有限的计算和数据存储资源，因此如何在移动设备端、边缘设备、远程云计算平台部署移动应用，设计合理的计算迁移方案，是当前面临的一个重要的技术挑战。

针对移动应用计算迁移问题，国内外学术界以及工业界都展开了很多深入的研究。基于移动云的计算迁移的出现为移动设备提供了一种满足移动应用需求的方法。计算任务被迁移到远程云中执行，从而延长移动设备的电池寿命[11]。Elgazzar等[12]提出了一种云辅助移动服务框架，可以根据移动应用的资源需求和网络状况动态分配计算资源，提供强大的计算迁移能力; Shi等[13]设计了基于移动设备的计算迁移系统，为移动设备提供计算迁移服务，此系统能够有效地管理云资源来应对来自于移动设备的计算任务，提高移动设备卸载性能并降低向提供商发送每个请求的成本; Liu等[14]设计了一个针对于应用内容的计算迁移框架，按照应用程序的需求对计算任务进行迁移，同时又提出了一个估计模型用于自动选择云资源来进行计算迁移。

将计算任务迁移到移动边缘平台以优化通信和能量消耗同样得到了许多的研究：文献[15]中研究一个绿色的移动边缘计算（Mobile Edge Computing， MEC）系统，结合基于李雅普诺夫（Lyapunov）优化的复杂度低的动态计算迁移算法，开发一种有效的计算迁移策略，有效降低了设备的执行成本;Zhang等[16]结合5G异构网络的多址特性设计了5G异构网络中MEC的节能计算迁移方法，该方法联合优化卸载和无线资源分配，以在延迟约束下获得最小的能量消耗;文献[17]中根据移动用户的分布特征和计算任务，提出了软件定义的协同迁移模型，然后设计了一种在线任务调度算法，实现设备间均衡的能源消耗;Wang等[18]开发了一种最佳资源分配方法，该方法根据用户的计算延迟约束最小化无线访问节点的总能量消耗，利用优化技术以半闭合的形式推导出最优解，有效降低了无线访问节点能源消耗和服务延迟。

但是，现存的研究还存在一些问题尚未解决：首先在边缘计算环境下，如何针对能耗、延迟等多个目标进行优化;接着边缘平台的资源都是有限的，当计算任务迁移到平台上需要排队，如何分析任务到达的频率以及任务排队的时间也是一个问题;然后，针对密集型移动应用通常要用工作流来模拟，工作流中的计算任务相互都存在数据和控制约束，此时如何考虑这些任务的迁移问题，又是一个巨大的挑战。本文将针对移动边缘环境，对工作流应用的计算任务进行迁移来达到移动设备能耗和移动应用时间的优化。

1 系统模型

1.1 基本概念

在本文中，移动应用由工作流构建，并且使用加权有向无环图（Directed Acyclic Graph， DAG）来定义，表示为Af（T，R），式中T={t1f，t2f，…，tNff}表示计算任务的集合，R=（r（tif，tjf），di， j）表示计算任务之间的依赖关系，其中Nf表示第f个工作流中的任务数量，di， j表示计算任务之间传输的数据量。

边缘设备虚拟化出多个虚拟机，用于并行处理计算任务，表示为CL=（V，ccl，LAN），其中V是边缘设备中虚拟机的数量，ccl是边缘平台的计算能力，LAN是局域网（Local Area Network， LAN）的传输延迟。

计算任务表示为tif=（wif，xif），其中wif是任务tif的工作负载，xif是迁移策略。一个工作流中所有计算任务的迁移策略表示为Xf={xif|xif∈T}，其中xif=0表示计算任务tif在移动设备中执行，xif=1或2表示tif分别被迁移到边缘设备和远程云端。对所有工作流进行全局的计算迁移表示为Y= {X1， X2， …， XF}。

1.2 时间计算模型

本节给出三种时间的计算模型，分别是：计算任务在边缘设备中平均等待的时间、计算任务在不同服务终端执行消耗的时间，以及计算任务之间数据传输所花费的时间。

1.2.1 平均等待时间

假设边缘设备中的虚拟机数量为V。任务到达时间的间隔服从参数λ的负指数分布，并且边缘设备中的服务时间受到参数μ的负指数分布的影响。根据排队论建立M/M/V/∞模型。设βn是边缘设备在稳定状态下，运行时队列长度为l的概率。

2.2 基于NSGAⅢ的计算迁移方法

与传统遗传算法相比，NSGAⅢ不仅可以快速准确地找到可行解中的全局最优解，同时在多目标的情况下优化效果要明显优于其他基因算法，因此，本文采用NSGAⅢ来解决多目标的计算迁移问题。基于遗传算法，本文考虑如下的编码方法：每一个染色体代表F个工作流的计算迁移策略，本文考虑对每一个工作流，最小化其对应的每一个移动设备的能源消耗，因此，每一条染色体均有F个适应度函数，由式（12）给出。

对于每一个工作流，使用算法1根据计算迁移策略求出实际的完成时间，如果不满足式（13）和（14）中的时间约束和策略约束，则该迁移策略所表示的染色体在选择的过程中不予考虑，满足约束的被称作有效染色体，种群中有效染色体的个数为S，每一代的染色体数为G。对S个染色体进行交叉变异操作，生成2G-S个染色体，当前的染色体数为2G。不同于普通的遗传算法，本文使用NSGAⅢ来进行下一代的选择。

1）非支配划分。基于有效染色体中包含的工作流计算迁移策略，计算相应的移动设备能源消耗。根据这F个适应值进行非支配性选择，将2G个染色体划分成若干非支配性层。

2）初始选择。从最高非支配层开始，每次随机选择一个染色体进入下一代，直至选出G个迁移策略。记最后一个染色体所在的非支配层为第l层：如果l层的所有染色体均被选择进入下一代，则选择操作结束;否则进行优化选择。

3）优化选择。记l层共有m个染色体被选择。首先除去这m个染色体。对于每一个工作流，一共有S个计算迁移策略，在这2G个迁移策略对应的适应值中选择最小值，其余的适应值均减去该最小值，然后根据相应的权值计算每个移动应用适应值的极值。将每个适应值作为一个坐标轴，基于极值计算出每个坐标轴的截距。对所有的适应值进行归一化操作。每一个染色体对应F个坐标轴组成的超平面的一个点，其各坐标轴的坐标即为对应的归一化后的适应值。基于参考点选择：在截距均为1的F个坐标轴进行等值划分，在超平面上生成若干参考点，将归一化后的染色体与参考点关联。根据关联的参考点的个数将第l非支配层的染色体进行划分。从关联的参考点的个数的最高层开始，随机选择一个个染色体，直至选出所有的m个染色体。

3 實验评估

本文将EOW和三种不同的计算迁移方法进行比较，包括：将所有计算任务留在移动设备处理的方法，记作Benchmark;将所有计算任务迁移到边缘设备的方法，记作为CLO;以及将所有任务都迁移到云端的方法，记作为CO[19-20]。

3.1 實验环境

本文采用CloudSim仿真工具进行了边缘设备中的计算迁移模拟实验，来评估提出的计算迁移方法。实验所需的工作流实例和数据部分来源于文献[10]，本文使用移动设备能源消耗计算迁移结果、工作流的完成时间和移动设备各部分能耗的对比来评估提出的迁移方法。实验所需的参数的设置如表1所示。

4 结语

为了优化边缘环境下的计算迁移中移动设备的能源消耗，本文提出了一种能耗感知的工作流计算迁移方法。基于排队论在边缘计算平台中建立了移动设备的能量消耗模型。在方法上本文提出了基于NSGAⅢ的节能计算迁移方法，不再是集中处理计算任务，而是合理将任务分配，以优化所有移动设备的能源消耗。最后，实验结果验证了本文方法的有效性。将用户的移动性和边缘网络变化考虑到计算迁移中是笔者未来的工作目标。

参考文献 （References）

[1] 张文丽，郭兵，沈艳，等.智能移动终端计算迁移研究[J].计算机学报，2016，39（5）：1021-1038. （ZHANG W L， GUO B， SHEN Y， et al. Computation offloading on intelligent mobile terminal [J]. Chinese Journal of Computers， 2016， 39（5）： 1021-1038.）

[2] 崔勇，宋健，缪葱葱， 等.移动云计算研究进展与趋势[J].计算机学报，2017，40（2）：273-295. （CUI Y， SONG J， MIAO C C， et al. Mobile cloud computing research progress and trends [J]. Chinese Journal of Computers， 2017， 40（2）： 273-295.）

[3]     BARBERA M V， KOSTA S， MEI A， et al. To offload or not to offload？ The bandwidth and energy costs of mobile cloud computing [C]// Proceedings of the 2013 IEEE International Conference on Computer Communications. Piscataway， NJ： IEEE， 2013： 1285-1293.

[4]     SHI W， CAO J， ZHANG Q， et al. Edge computing： vision and challenges [J]. IEEE Internet of Things Journal， 2016， 3（5）： 637-646.

[5]     DENG S， HUANG L， TAHERI J， et al. Computation offloading for service workflow in mobile cloud computing [J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（12）： 3317-3329.

[6]     XU X， DOU W， ZHANG X， et al. EnReal： An energyaware resource allocation method for scientific workflow executions in cloud environment [J]. IEEE Transactions on Cloud Computing， 2016， 4（2）： 166-179.

[7]     赵梓铭，刘芳，蔡志平，等.边缘计算：平台、应用与挑战[J].计算机研究与发展，2018，55（2）：327-337. （ZHAN Z M， LIU F， CAI Z P， et al. Edge computing： platforms， applications and challenges [J]. Journal of Computer Research and Development， 2018， 55（2）： 327-337.）

[8]     JIA M， LIANG W， XU Z， et al. Cloudlet load balancing in wireless metropolitan area networks[C]// Proceedings of the 35th Annual IEEE International Conference on Computer Communications. Piscataway， NJ： IEEE， 2016： 1-9.

[9]     曾广周，党妍.基于移动计算范型的迁移工作流研究[J].计算机学报，2003， 26（10）：1343-1349.（ZENG G Z， DANG Y. The study of migrating workflow based on the mobile computing paradigm[J]. Chinese Journal of Computers， 2003， 26（10）： 1343-1349.）

[10]    ZHU Z， ZHANG G， LI M， et al. Evolutionary multiobjective workflow scheduling in cloud [J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（5）： 1344-1357.

[11]    RIMAL B P， van PHAM D， MAIER M. Cloudlet enhanced fiberwireless access networks for mobileedge computing[J]. IEEE Transactions on Wireless Communications， 2017， 16（6）： 3601-3618.

[12]    ELGAZZAR K， MARTIN P， HASSANEIN H. Cloudassisted computation offloading to support mobile services[J]. IEEE Transactions on Cloud Computing， 2016， 4（3）： 279-292.

[13]    SHI C， HABAK K， PANDURANGAN P， et al. COSMOS： computation offloading as a service for mobile devices[C]// Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM， 2014： 287-296.

[14]    LIU Z， ZENG X， HUANG W， et al. Framework for contextaware computation offloading in mobile cloud computing[C]// Proceedings of the 15th IEEE International Symposium on Parallel and Distributed Computing. Piscataway， NJ： IEEE， 2016： 172-177.

[15]    MAO Y， ZHANG J， LETAIEF K B. Dynamic computation offloading for mobileedge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications， 2016， 34（12）： 3590-3605.

[16]    ZHANG K， MAO Y， LENG S， et al. Energyefficient offloading for mobile edge computing in 5G heterogeneous networks[J]. IEEE Access， 2016， 4：5896-5907.

[17]    CUI Y， SONG J， REN K， et al. Software defined cooperative offloading for mobile cloudlets[J]. IEEE/ACM Transactions on Networking， 2017， 25（3）： 1746-1760.

[18]    WANG F， XU J， WANG X， et al. Joint offloading and computing optimization in wireless powered mobileedge computing systems [J]. IEEE Transactions on Wireless Communications， 2018， 17（3）： 1784-1797.

[19]    KUMAR K， LU Y H. Cloud computing for mobile users： can offloading computation save energy？ [J]. Computer， 2010， 43（4）： 51-56.

[20]    YANG Z， NIYATO D， PING W. Offloading in mobile cloudlet systems with intermittent connectivity [J]. IEEE Transactions on Mobile Computing， 2015， 14（12）： 2516-2529.