MEC 系统中的资源分配算法研究综述

黄星，殷锋，袁平

（1.四川大学计算机学院，成都 610065；2.西南民族大学图书馆，成都 610041；3.重庆第二师范学院数学与信息工程学院，重庆 400067）

0 引言

近些年，物联网的快速发展使得需要处理的数据量大大增加，增强现实（Augmented Reality，AR）、虚拟现实（Virtual Reality，VR）等各种新兴应用的出现又对时延和带宽提出了更高的要求。边缘设备的计算和存储能力太弱，无法处理和存储庞大的数据。另外，执行计算集中型任务所消耗的能量对于能量有限的边缘设备来说也是一个很大的挑战。

为了解决边缘设备计算和存储能力不足的问题，移动云计算（Mobile Cloud Computing，MCC）应运而生。在移动云计算中，可以通过将边缘设备所产生的计算任务卸载到云服务器中进行计算来增强边缘设备的计算和存储能力，并且延长移动设备的运行时间。但是，这样做会导致三个问题：①边缘设备和云端的距离太过遥远，从而使得传输时延和总的通信时延都很高，这无法满足各种新兴应用的毫秒级时延要求。②整个物联网每年产生的数据量非常庞大，据思科全球云指数白皮书[1]中显示，2019 年，人和物产生的总数据量达到了500ZB，而全球云数据中心的网络流量仅能达到1ZB，也就是说网络容量是远远达不到物联网所产生的数据量的。假设将大部分数据传输到云端进行处理，势必会给主干网络带来极大的压力，极有可能导致网络阻塞甚至瘫痪。③原始数据包含着大量隐私，从边缘设备到云服务器的传输链路过长会使得隐私泄露的可能性增大。

欧洲电信标准化协会（European Telecommunications Standards Institute，ETSI）在 2014 年提出了移动边缘计算（Mobile Edge Computing，MEC）来主要解决长时延和网络容量不足问题。作为边缘计算概念的一种主要形式，移动边缘计算的主要定义为：在网络边缘向应用开发者和内容提供者提供云计算能力和IT 服务环境。相比于移动云计算，移动边缘计算可以将计算任务卸载至边缘服务器，并不经过广域网，从而达到既减少时延和能耗，又缓解网络带宽压力的目的。

1 理论基础

移动边缘计算和移动云计算中在计算卸载技术上唯一的不同就是卸载的目的地不同，前者是将计算任务卸载至边缘服务器中执行，后者是将计算任务卸载至云服务器中执行。计算卸载技术最重要的两步是卸载决策和卸载计算资源分配[2]。卸载决策所解决的是是否卸载、卸载多少计算量和卸载哪部分计算量的问题，卸载计算资源分配所解决的则是在有多个边缘服务器的情况下，选择将计算任务卸载到哪个边缘服务器的问题[3]。卸载决策的目的是计算所要卸载的任务大小以及具体的任务部分（如果不卸载，卸载的任务大小为0），而卸载计算资源分配的目的是决定卸载的目标服务器（一般在多边缘服务器场景下）。这两者都涉及计算资源分配，在比较复杂的边缘计算系统中，往往还需要考虑无线资源分配，因此，资源分配是计算卸载过程中所要解决的关键问题，主要包括计算资源分配和无线资源分配。

卸载决策可以分为完全卸载和部分卸载两类。完全卸载指的是将全部计算任务都卸载至边缘服务器或其它服务器中执行，而部分卸载则只是将部分计算任务卸载至服务器中执行，剩下的计算任务还在本地执行。

考虑到卸载任务的并行性，卸载计算资源分配可以分为单点计算资源分配和多点计算资源分配。当卸载任务不能被切分，即不能并行执行时，那么就只将卸载任务卸载至单个节点，等效于将单个节点的计算资源分配于该任务。如果卸载任务还可以被切分，可以并行执行，那么就可以将其切分，再把切分后的计算任务分配至多个节点处执行，这就是多点计算资源分配。

2 研究现状

按照边缘计算系统的规模来分，可以把资源分配问题分为三类：单用户边缘计算系统、多用户边缘计算系统和异构服务器边缘计算系统。下面介绍关于这三类资源分配问题的研究现状。

（1）单用户边缘计算系统

考虑到资源利用效率，一般不考虑单用户多服务器的边缘计算系统，因为它的资源利用率很低，所以单用户边缘计算系统一般是指由一个边缘设备和一个边缘服务器组成的系统。

为了得到计算卸载发生的条件，Salvador 等人同时对计算时间和通信时间进行建模，得到了任务在本地计算和卸载到服务器计算两种情况的完成时间[4]。之前的研究表明，只考虑时延的话，当任务在本地计算的时延比卸载到服务器执行的时延还要高时，就可考虑卸载[5]。Salvador 等人为了得到边缘计算系统参数和卸载任务参数之间的关系，引入了CCR（Computation-to-Communication Ratio）和 RLR（Remote-to-Local Ratio）两个参数对计算卸载发生的条件进行分析，得出了CCR 和RLR 的不等式。作者假设通信系统处于非阻塞情况下，去掉排队时延和转发时延，最后得到了边缘计算系统参数和计算任务参数的不等式。该不等式可以作为卸载决策的参考公式，满足这个不等式的计算任务才可以被卸载到边缘服务器中执行。

和文献[4]研究的问题不同，文献[6]研究的是怎样在给定完成时间的约束下，最小化移动设备的能耗的问题。边缘设备所产生的计算任务要么在本地执行，要么卸载到服务器处执行。作者假设任务不可分割，只能全部卸载，于是当计算任务在边缘设备执行时，只需要考虑边缘设备的计算能耗，当计算任务在服务器处执行时，只需要考虑无线通信的能耗。本文作者提出随机无线信道下最小化边缘设备能耗的框架。当计算任务在边缘设备执行时，通过动态调整时钟频率来最小化CPU 能耗；当计算任务在服务器处执行时，通过调整边缘设备的无线传输功率来最小化无线通信能耗。通过对这两个调度问题的求解，得到了最佳卸载决策，从而最小化边缘设备的能耗。

虽然文献[6]给出了在给定时间约束下，如何调度和分配计算资源和存储资源以最小化能耗的问题的解，但是它忽略了任务间的依赖。文献[7]则考虑了任务间的依赖，并且由于现有移动设备大多具备多核CPU，所以该文把边缘设备逻辑表示为多个CPU 核的集合。在该文献中，作者研究在满足给定时间的约束的条件下，如何利用big.LITTLE 架构来最小化能耗。首先对计算和存储资源的分配问题进行建模，再结合模型把物理问题形式化为混合整数非线性规划问题，然后提出启发式算法来解决该卸载决策和任务调度问题。该启发式算法分成三个阶段：第一个阶段是初始化阶段，目的是在满足任务依赖约束的条件下，最小化时间；第二个阶段是任务重分配阶段，基于关键路径，重新分配任务以最小化能耗，当然前提是不超过完成时间约束；最后一个阶段是对第二阶段的补充，如果这时还有剩余完成时间，那么可以应用动态电压频率调整技术（Dynamic Voltage Frequency Scaling，DVFS）来进一步降低能耗。实验表明，和其他方法相比，能耗最少可以降低24.1%。

（2）多用户边缘计算系统

多用户边缘计算系统一般是指多个用户和一个边缘服务器组成的系统。

在文献[8]中，计算资源和无线通信资源都是边缘服务器来集中分配的。为了解决集中式资源分配问题，作者先是通过建立无线通信模型和计算模型将联合无线和计算资源优化问题抽象化为凸优化问题，然后用拉格朗日乘子法求出凸优化问题的解。除此之外，作者还得出分配给每个信道的传输能量和分配给相关用户的CPU 周期数之间存在着一一映射的关系，并且提出一种许可控制策略，其核心思想是允许的任务传输到边缘处理，不允许的任务就在本地处理，这样不仅可以保证边缘服务器不过载，也保证了边缘设备任务队列的稳定性。

与文献[8]不同，文献[9]解决的是分布式资源分配问题。分布式资源分配问题的定义是边缘设备执行资源分配过程，而集中式资源分配问题的定义是服务器执行该过程。作者先对计算资源和无线资源分配问题进行建模，再把它形式化为多用户卸载博弈问题并证明该卸载博弈问题存在纳什均衡。基于此，作者提出分布式计算卸载算法，得出了聚合时间的上限和系统总代价。实验结果证明，和其他算法相比，该算法的系统总代价，也就是时延和能耗的加权最少降低51%。

（3）异构服务器边缘计算系统

异构服务器边缘计算系统一般是指多个服务器和多个边缘服务器组成的系统，有的研究把云服务器加入这个系统组成端-边-云三层架构。

文献[10]考虑由边缘设备、边缘云和远端云所组成的三层系统架构，其中边缘云由多个边缘服务器组成。由于边缘云的计算能力和存储能力有限，因此要考虑多用户之间资源竞争的问题。作者利用排队论来建立多用户资源竞争模型来获取用户交互信息和计算卸载对用户感知性能的影响。作者随后根据该模型将多用户资源竞争问题形式化为广义纳什均衡问题，也称非合作博弈问题。在深入分析均衡问题的基础上，提出了适合问题结构的分布式均衡算法。实验结果表明，响应时延比其他方法降低了20%以上的时延。

3 结语

本文详细介绍了资源分配问题的分类和研究现状。从上述文献中可看出，资源分配算法在本质上是等同于计算卸载的。虽然目前对资源分配算法的研究文章较多，但仍有不少问题等着学者去研究解决，例如在线任务切分，大规模的系统优化。