本文首发于《计算机科学》，边缘计算社区经过作者授权转发分享。
刘通1，2 方璐1 高洪皓1,3
1 上海大学计算机工程与科学学院上海市200444
2 上海智能计算系统工程技术研究中心上海市200444
3 嘉泉大学京畿道461-701 韩国
（tong_liu@shu.edu.cn）
基金项目：国家自然科学基金青年项目（61802245）；上海市“科技创新行动计划”青年科技英才扬帆计划（18YF1408200）
通信作者：高洪皓（gaohonghao@shu.edu.cn）
全文8888字，内容非常详实，以下为正文，欢迎收藏转发学习。
摘要
近年来，随着移动智能设备的普及以及5G等无线通信技术的发展，边缘计算作为一种新兴的计算模式被提出，是对传统的云计算模式的扩展与补充。边缘计算的基本思想是将移动设备上产生的计算任务从原来的卸载到云端转移到卸载到网络边缘端，从而满足诸如实时在线游戏、增强现实等的计算密集型应 用对低延迟的要求。边缘计算中的计算任务卸载是一个关键的研究问题，即计算任务应该在本地执行还是卸载到边缘节点或云端。不同的任务卸载方案对任务完成时延和移动设备能耗都有着较大的影响。
本文首先对边缘计算的基本概念进行了介绍，并归纳了边缘计算的几种系统架构。随后，本分详细阐述了边缘计算中的计算任务卸载问题。基于对任务卸载方案研究必要性与挑战的分析，本文对现有的相关研究工作进行了全面的综述和总结，并对未来的研究方向进行了展望。
关键词：边缘计算；任务卸载；资源分配；任务延迟；能量消耗
01
引 言
随着移动智能设备的普及以及5G等无线通信技术的发展，涌现出了许多具有低延迟要求的计算密集型应用，如在线沉浸式游戏，增强现实和视频流分析等。由于传统的云计算无法满足这些应用的对低延迟的需求，最近提出了一种新型的计算模式，称为边缘计算[1]。该计算模式将计算任务负载从远程的云转移到里用户更近的核心网络的边缘节点（例如无线接入点或基站）上。
图1显示了一个典型的边缘计算系统，该系统由许多具有计算需求的移动智能设备、充当边缘节点的基站和远程的云共同组成。多种多样的计算任务是由移动智能设备上的各种应用程序实时生成的。将这些计算任务卸载到边缘节点可以显著降低设备与云之间的数据传输时间。
然而，边缘节点的计算资源和网络资源是有限的。因此，计算任务是在本地执行还是卸载到边缘节点或云端，移动设备应进行仔细的规划，已达到任务完成时延最短的目标，这在边缘计算系统中称为计算任务卸载问题。设计高效的、节能的计算任务卸载方案是边缘计算领域中的一个重要的研究方向，需要考虑到边缘节点资源分配的合理性，不同的任务执行方案所带来的时延和移动设备能耗差异等因素。由于智能设备的移动性、计算任务的异构性（即不同的任务所需计算资源和网络资源不同）、边缘节点资源的有限性以及异构性，对计算任务卸载问题的解决形成了不小的挑战。
本文从边缘计算的基本定义和系统架构出发进行了阐述，并详细介绍了边缘计算中的一个重要的研究问题——计算任务卸载，即计算任务在设备端执行还是卸载到边缘端或云端。本文围绕现有的计算任务卸载的相关工作，对它们的优化目标、决策变量和算法设计等方面进行了总结。第2节给出了边缘计算的概念定义，并分类整理了边缘计算的典型系统架构，分析了不同系统架构的特点；第3节阐述了边缘计算中的计算任务卸载问题，论述了该问题在边缘计算中的重要地位，以及存在的研究难点；第4节综述了边缘计算中计算任务卸载问题的相关研究工作；最后总结全文并展望未来的研究方向。
02
边缘计算的定义和系统架构
2.1 边缘计算的定义
无线通信技术的飞速发展迎来了低时延网络时代，这是一个以万物互联为基础，实现海量数据实时高速传输的时代，而如何为用户提供高可靠、低时延的数据传输服务是一个难点。随着低时延、高可靠计算服务需求的日益增长，越来越多的研究人员对这一问题进行了深入的研究与实践，边缘计算这一概念也应运而生。
边缘计算的定义在不同组织中各有不同。
定义1 边缘计算[2]是指在网络边缘执行计算的一种新型计算模式，边缘计算中边缘的下行数据表示云服务，上行数据表示万物互联服务，而边缘计算的边缘是指从数据源到云计算中心路径之间的任意计算和网络资源。
定义2 边缘计算[3]是在靠近物或数据源头的网络边缘侧，融合网络、计算、存储、应用核心能力的开发平台，就近提供边缘智能服务，满足行业数字在敏捷联接、实时业务、数据优化、应用智能、安全与隐私保护等方面的关键需求。
以上两个边缘计算定义分别是美国韦恩州立大学计算机科学系施巍松等人和边缘计算产业联盟分别提出的。定义1指出边缘计算的边缘是指从数据源到云计算中心路径之间的任意计算和网络资源，强调了云计算与边缘计算是相辅相成的关系，云计算掌握大局，边缘计算关注局部。定义2阐述了边缘计算较为具体的实现形式以及其优势。通过以上定义分析，可以得知云计算与边缘计算不是针尖对麦芒的关系，边缘计算是为了解决云计算现存的亟待解决的痛点而生的，一旦脱离了云计算，边缘计算也难以独活。相比于云计算，边缘计算有如下的优势：
(1)分布式低延时
设备端到云端的距离较长，离边缘段更近。因此边缘计算专注于满足时间敏感的计算需求。
(2)减小数据流量
数据在离设备端更近的边缘端处理，传输更高效，且能减少传输能耗。边缘端可以进行数据的预先过滤与分析，减少了设备与云端之间的数据流量，使的计算任务的响应时间更短。
(3)安全性高
云计算模式容易受到断电的影响，而边缘计算将数据处理分布式化，更能适应异常情况。当一个边缘节点受到攻击或者发生异常时，其他边缘节点仍旧可以照常工作。
2.2 边缘计算的系统架构
边缘计算将边缘设备（基站、无线接入点、路由器等）作为云端和终端设备间的桥梁，将云服务拓展到的网络边缘侧，因此边缘计算系统架构主要包括云端、边缘端和设备端。接下来对架构的每一层进行详细介绍并将现有研究中的系统架构进行总结和归类。
云端：云端是由若干高性能服务器以及相匹配的存储设备组成的。其计算能力与存储能力都十分强大，能够处理复杂性高的计算需求。云端以云中心的角色合理控制边缘端与云端的协调合作，提升用户体验感。
边缘端：边缘端是距离终端用户较近的具有一定计算存储能力的设备，包括但不限于特定边缘服务器、无线接入点、基站、各级网关和路由器以及交换机等。边缘端的设备可以满足用户的实时需求，还可以帮助云端设备进行数据的过滤与分析。
设备端：用户持有的移动设备，例如智能手机、可穿戴设备、智能家居设备等。为了保证终端设备有较长的续航时间，需要将复杂性高的计算任务放到边缘端或者云端执行。
按不同的研究侧重点，边缘计算的系统架构可归类为以下三种：
(1)云-边-端三层架构模型：考虑云边端三者之间的协同工作。云端的中心控制策略会对边缘端的计算与存储进行有效的管理，使得边缘端的分布式计算处理模式发挥最好的效果，提升计算处理的效率，满足用户的需求。设备终端的计算任务可以在本地、边缘端、云端三种模式下完成。计算任务的异构性以及边缘端设备的异构性给三层架构下的任务协调带来了巨大挑战。
(2)云-边双层架构模型：云-边双层架构只考虑云端与边缘端的协调，对此架构下任务调度的研究，有助于处理一些在设备终端难以执行的计算任务。
(3)边-端双层架构模型：边-端双层架构可以看作是一个小型的云计算架构，只是把云计算中的高性能服务器换成了计算和存储能力有限的边缘端设备，但是又拉近了用户与云端的传输距离。
03
边缘计算中的计算任务卸载问题
在现实环境中，计算卸载会被外界环境、软硬件环境或者用户个性等多种因素影响，比如无线信道内部以及外部的干扰、终端边缘端以及云端的性能、用户个性化使用等，这些前提使得制定合理且适应环境动态变化的任务卸载策略变的困难而又至关重要。
首先，用户的体验感是网络服务最重要的指标，而且用户的计算任务之间存在关联性，某个任务的响应时间过长可能造成有承接关系的计算任务响应失败，因此计算任务的执行时延是判定任务卸载决策好坏的重要指标。其次，终端设备 的能耗也是用户关心的一个指标，能耗过大会大大减弱设备续航能力，并且长期的能耗高压可能会影响设备的使用寿命。因此计算任务的卸载决策需要同时考虑时延和能耗两个方面，从而找到较好的时延和能耗的平衡点。由以上分析可以将关注任务卸载决策制定的研究分为以最小化时延为目标、以最小化能耗为目标以及以权衡时延与能耗为目标三大类。
由于不同的边缘端设备的计算和存储能力不同，计算卸载决策的制定与边缘端的资源分配息息相关。分配的资源主要包括移动端的计算资源（调节CPU频率）和能量资源（调节数据传输功率），以及边缘端的无线网络资源（信道竞争）、计算资源（CPU和GPU等）和存储资源（服务缓存）。多用户场景中，存在多个用户将计算任务卸载到同一边缘端的情况，这些用户需要竞争无线带宽资源。此外，卸载到同一边缘端的计算任务需要竞争计算和存储资源。因此，如何分配网络、计算和存储资源，对计算任务卸载策略的制定有着非常大的影响。同样地，边缘计算中资源分配类的研究主要可以分为通信资源分 配、计算资源分配、联合计算与通信资源分配三大类。
04
相关研究工作
在本节中，我们总结了现有的边缘计算中解决计算任务卸载问题的相关研究工作。
现有的一些工作主要研究如何离线或在线地做出任务分配决策，且大都以任务完成时间和移动设备能耗最小为优化目标。文献[4]中的边缘计算系统由边缘节点接入点(AP)和带有计算任务 的移动设备(MD)组成，且这些任务以离线的方式卸载。该论文考虑了AP的CPU频率可以和不可以调节两种不同的情况，并针对这两种情况分别提出了基于线性松弛的方法和基于穷举搜索的方法来得到卸载决策。
为了权衡能耗和计算延迟两个指标，文献[5]提出了一种基于李雅普诺夫的算法，用于计算移动边缘计算系统中的任务卸载决策。该算法在满足时延约束条件下大大降低了设备的能耗。文献[7]为多服务器的边缘计算场景设计了在线计算任务调度方法。除了响应时间外，还考虑任务之间的公平程度。在文献[9]中，作者研究了计算卸载与调度问题，力求将每个移动设备的成本降至最低，其中成本被定义为任务完成时间和能耗的线性组合。此外，该文献还考虑了设备间的通信和计算资源竞争，并利用博弈模型对问题进行了形式化定义，设计了去中心化算法达到纯策略的纳什均衡。
文献[6]和文献[8]同时考虑了边缘计算系统中的服务缓存和任务卸载问题，考虑到每个边缘服务器由于其存储资源有限而无法缓存所有服务。文献[6]考虑了服务的异构性，并设计了一种基于李雅普诺夫优化和Gibbs采样的算法。文献[8]提出了一种提出了一种基于primal-dual的短期任务负荷预测算法。与上述工作不同的是，文献[10]中考虑了一个任务可以分为多个子任务，并分别卸载到不同的边缘服务器。该文献的作者将子任务之间的时序关系建模成有向图，并针对单一用户和多用户的情景分别提出了任务卸载算法。
考虑到边缘节点通信和计算资源的有限性，还有一些其他工作提出了同时解决任务卸载和资源分配问题的方案，旨在进一步减少任务完成时延和设备能量消耗。具体地，文献[11]研究了多接入5G异构网络中移动边缘计算的节能卸载和无线资源分配问题。考虑到每个任务的截止期限，该文献以最大程度地减少总能耗为目标提出了离线的次优解决方案。文献[12]仅考虑在多用户的边缘计算场景中的无线资源分配问题。为了满足时延约束下最小化能量消耗，分别针对TDMA 和FDMA信道提出了基于阈值的最优策略和次优算法。在文献[13]中，作者考虑了边缘计算系统中的移动设备具有充电的功能。为了最小化执行时延和任务失败率，设计了一种基于李雅普诺夫优化的算法，动态地调度移动设备的CPU频率和发射功率。文献[19]共同优化任务卸载决策、计算资源调度和无线资源分配。利用李雅普诺夫优化理论将问题分解为若干个子问题，然后通过凸优化和匹配博弈来解决。
文献[14]综合考虑了协同优化任务卸载、无线资源分配和计算资源分配。为了最大程度降低能耗，作者将问题建模成混合整数非线性规划，并提出了基于分支定界方法的线性化重构技术和基于多项式复杂度基尼系数的贪婪启发式方法。文献[15]联合调度移动设备的数据传输功率和边缘服务器上的计算资源，提出了一种启发式的任务卸载算法，该算法具有次优的性能和多项式时间复杂度。文献[16]的作者考虑到任务执行要求在任务到来之前是不确定的，提出了联合优化卸载决策以及计算和通信资源分配，以最大程度地减少用户能耗和任务时延。
文献[17]是第一个研究基于NOMA网络的移动边缘计算中资源分配问题的工作。作者考虑该网络中存在多个组且每个组中的多个用户共享无线资源。为了最大程度地减少所有任务总时间和总能耗，提出了一种迭代算法。类似地，文献[18]中也考虑了基于NOMA网络的边缘计算场景。联合优化了移动设备本地CPU频率调度、传输功率分配和计算卸载，以实现任务时延和能耗之间的权衡。
05
总结与展望
近年来，随着日益增长的低延迟、计算密集型应用的涌现，越来越多的研究人员加入到对边缘计算的研究中，边缘计算的浪潮将卷起一个新的网络时代。计算卸载是边缘计算中的核心技术，其不单指表面上的“卸载”二字，还囊括了计算任务调度、计算和网络资源分配、服务缓存与管理、云边端协同等多方面的技术研究。本文阐述了边缘计算的概念与优势，介绍了边缘计算系统的各类架构设计，并重点梳理了边缘计算系统中计算卸载问题的研究现状。希望本文能帮助不了解边缘计算的人们理解边缘计算的概念并为相关领域的专家学者的研究工作提供一定的参考与帮助。
参考文献
[1]SatyanarayananM.The Emergence of Edge Computing[J].Computer,2017,50(1):30-39.
[2]Weisong S,Hui S,Jie C,etal.Edge Computing:An Emerging Computing Model for the Internet of Everything Era[J]. Journal of Computer Research and Development,2017(5).(inChinese)
施巍松, 孙辉, 曹杰,etal.边缘计算:万物互联时代新型计算模型[J].计算机研究与发展,2017(5).
[3]Teng H.Talking About a Brief Aanalysis of the Current Situation and Challenges of Edge Computing Technology[C]//Proceedings of the 34th China(Tianjin)2020'IT,Network,Information Technology,Electronics, Instrumentation Innovation Academic Conference,2020.
何腾.浅析边缘计算技术应用的现状及挑战[C]//第三十四届中国(天津)2020'IT,网络,信息技术,电子,仪器仪表创新学术会议论文集.2020.
[4]DinhTQ,TangJ,La QD,etal.Offloading in Mobile EdgeComputing: Task Allocation and Computational Frequency Scaling[J].IEEE Transactions on Communications,2017,65(8):3571-3584.
[5]WuH,SunY,WolterK.EnergyEfficient Decision Making for Mobile Cloud Offloading[J].IEEE Transactions on Cloud Computing,2017:1-1.
[6]XuJ,ChenL,ZhouP.Joint Service Caching and Task Offloading for Mobile Edge Computing in Dense Networks[J].2018.
[7]HanZ,TanH,LiXY,etal.OnDisc:Online Latency-Sensitive Job Dispatching and Scheduling in Heterogeneous Edge-Clouds[J].IEEE/ACM Transactions on Networking, 2019, PP(99):1-14.
[8]ZengY,HuangY,LiuZ,etal.Joint Online Edge Caching and Load Balancing for Mobile Data Offloading in 5G Networks[C]// 2019 IEEE39thInternational Conferenceon Distributed Computing Systems(ICDCS).IEEE,2019.
[9]JoiloSlaana, DánGyrgy. Computation Offloading Scheduling for PeriodicTasksinMobileEdgeComputing[J].IEEE/ACMTransactionsonNetworking,2020.
[10]ShuC,ZhaoZ,HanY,etal.Multi-User Offloading for Edge Computing Networks:ADependency-Aware and Latency-OptimalApproach[J].IEEE Internet of Things Journal,2019,PP(99):1-1.
[11]ZhangK,MaoY,LengS,etal.Energy-Efficient Offloading for MobileEdge Computing in 5GHeterogeneous Networks[J].IEEEAccess,2017.
[12]YouC,HuangK,ChaeH,etal.Energy-Efficient Resource Allocation for Mobile-EdgeComputationOffloading[J].IEEE Transactionson Wireless Communications,2017,16(3):1397-1411.
[13]MaoY,ZhangJ,LetaiefKB.Dynamic Computation Offloading for Mobile-Edge Computing with Energy Harvesting Devices[J].IEEE Journal on Selected Areas in Communications,2016,34(12):35903605.
[14]ZhaoP,TianH,QinC,etal.Energy-SavingOffloading by Jointly Allocating Radio and Computational Resources for Mobile Edge Computing[J].IEEEAccess,2017:1-1.
[15]TranTX,PompiliD.JointTask Offloading and Resource Allocation for Multi-ServerMobile-Edge Computing Networks[J]. IEEE TransactionsonVehicularTechnology, 2017.
[16]EshraghiN,LiangB.Joint Offloading Decision and Resource Allocation with UncertainTask Computing Requirement[C]// IEEE INFOCOM2019-IEEE Conference on Computer Communications.IEEE,2019.
[17]YangZ,PanC,HouJ,etal.EfficientResourceAllocationforMobile-Edge Computing Networks with NOMA:CompletionTime and Energy Minimization[J].IEEE Transactions on Communications,2019,67(11):7771-7784.
[18]NouriN,AboueiJ,JaseemuddinM,etal.Joint Access and Resource Allocation in Ultradense mm Wave NOMA Networks With Mobile Edge Computing[J].IEEE Internet of Things Journal,2020,7(2):1531-1547.
[19]ZhangQ,GuiL,HouF,etal.DynamicTaskOffloading and Resource Allocation for Mobile Edge Computing in DenseCloudRAN[J].IEEEInternet ofThings Journal,2020,7(4):3282-3299.
