李昌群，陈国龙

1.安徽粮食工程职业学院信息技术系，安徽合肥，231131；2.蚌埠学院计算机与信息工程学院，安徽蚌埠，233000

随着网络通信技术和物联网的飞速发展，移动终端设备的数量呈指数式急剧增长。根据IOT ANALYTCS网站的报告，全球活跃的物联网设备的数量到2025年将达到220亿台[1]。随之而来的是各种各样的移动应用程序，例如虚拟现实(virtual reality)、人脸识别(face recognition)、自动驾驶(autonomous driving)，正在出现和改变着我们的生活[2]。这些移动应用程序需要大量的计算资源和消耗大量的能量，而移动终端设备的计算资源和电池容量都有限，这不利于移动应用程序的处理。传统的方法是把移动应用程序卸载到公有云，如Amazon EC2 和 Windows Azure的数据中心来处理，可以解决上述问题。但是由于公有云的数据中心离移动用户比较远，这会导致产生很长的传输延迟，这不利于需要实时处理的应用程序。移动边缘计算(Mobile Edge Computing，简称MEC)被认为是一种能够解决资源密集型应用和资源受限的移动设备之间矛盾的有前途的技术[3-4]。跟传统的云计算不同的是，移动运营商拥有移动边缘计算的数据中心，并且把云资源部署在蜂窝基站或者无线接入点，离终端用户比较近，这可以大大地降低终端设备用户和公有云数据中心之间由于长距离的传输所产生的延迟和核心网的处理压力[5]。移动云计算和移动边缘的比较如表1所示。

表1 移动云计算和移动边缘计算的比较

和传统的云计算相比，移动边缘计算有以下4个明显的优势[6]：

(1)移动终端设备的应用程序产生的数据，边缘端的服务器中预处理，这可以极大地减轻海量数据给核心网的网络带宽造成的压力。

(2)把部分数据处理放在移动终端设备上进行，而不是全部放在云计算中心，通过利用部署在靠近用户的服务器对采集到的数据进行处理，避免了与云数据中心的交互环节，降低了数据处理的响应时间，提高了系统的性能。

(3)用户的终端设备产生的数据是存储在边缘端的数据中心上，而不是存储在公有云的数据中心中，这降低了用户的敏感数据在上传公有云的数据中心过程中被非法窃取的风险，可以保护用户的隐私数据安全。

(4)在移动边缘计算系统中，数据不需要放到公有云的数据中心进行处理，这不但减少了数据从终端设备传输到云数据中心的能耗，而且也极大地降低了云数据中心的能耗。

近些年来，得益于移动边缘计算的以上这些优势，以自动驾驶(Autonomous Driving)、虚拟现实(virtual reality)等为代表的新型应用得到了飞速的发展。这些新型的应用对网络传输延时、数据隐私保护和安全方面都有较高的要求[7]，由于移动边缘计算能够满足它们的要求，因此基于移动边缘计算的应用和平台越来越多地涌现出来了。

1 移动边缘计算的相关研究

目前关于移动边缘计算的相关研究主要涉及任务卸载和资源分配的两个领域，研究工作的主要目标可以分为如下3种：

其一，降低设备处理任务的能耗。例如，Liu等[8]在具有时间截止和传输错误率的约束条件下，探讨一种在可接受的时延和通信质量下最小化移动设备能耗的卸载决策方法。吕昕晨等[9]研究了MEC系统中时延敏感应用的节能任务接纳，提出了约束条件下的总能耗最小化边缘服务器的计算资源和延迟。曾鸣等[10]研究了在传输资源和计算资源都稀缺的严格延迟限制的情况下，无线与无线联合分配的传输能耗问题。胡锦天等[11]提出了一种任务迁移策略来优化能耗，同时保持在任务迁移过程中的高性能。

其二，降低任务处理的时间。如王思华等[12]提出了一种多叠强化学习(RL)算法，避免相同资源分配方案和用户状态的重复学习，优化频谱分配和传输功率分配，最小化用户间的最大计算和传输延迟。Fan等[13]提出了一种非合作博弈方法 ,通过分布式迭代算法解决了MEC服务器间的多类型任务卸载，实现了所有任务总执行延迟的最小化。Liu等[14]比较混合多址传输场景中的三种卸载方式，并设计了一种有效算法，实现了用户灵活地在混合非正交多址与正交多址传输间选择最佳地卸载策略，以降低任务处理的时间。

其三，如何在任务处理时间和设备能耗间做出平衡和选择。尽管移动边缘计算应用程序的任务卸载功能能够提高移动终端设备端的处理能力和降低这些设备的能耗，但在一个需要大量密集型计算任务的系统中，由于无线信道的带宽有限，设备间会竞争网络资源，并形成相互干扰，导致数据传输速率降低，延长数据传输时间。同时，在边缘云数据中心计算资源有限的情况下，把所有的应用程序卸载到边缘云端并不是明智的选择[9]。随着移动终端设备的性能的提高，把一部分移动应用程序放在终端处理，另一部分卸载到边缘云的数据中心，可以降低移动设备间由于网络资源竞争导致的数据传输时间延长以及对边缘云数据中心计算资源的需求。如Yang等[15]开发了一种混合遗传爬坡算法，在非正交多址(NOMA)支持的小单元MEC网络中分别建立通信模型和计算模型，通过快速找到最优解以实现在不同需求下任务卸载总成本以及计算能力的能量与传输时延问题最小化的目标。

综上，目前多数研究停留在考虑全任务卸载的问题上，即任务要么在本地设备处理，要么在边缘云处理[9，16-17]。而在进一步的研究中，也仅考虑了采用DVS技术进行偏分任务卸载[18]，没有考虑到计算资源的分配。关于该方向的研究尚未被充分挖掘，这对大数据应用程序尤为重要。因此，文章就移动边缘计算的边缘云计算资源分配和偏分任务卸载的问题开展研究，以期为该领域的相关研究提供参考。

2 MEC系统模型的设置

MEC系统模型由多个服务器组成的数据中心和N个物联网设备组成，如图1所示。参考文献[16，18]，建立MEC系统模型。设物联网设备i∈{1,2,…,N}的任务记作i。每个物联网设备有一个延迟敏感(delay-sensitive)和需要大量计算资源的任务要处理。这些任务要么放在本地的设备处理，要么卸载到边缘云数据中心处理。物联网设备可以通过基站(Base Station,简称BS)来访问数据中心中的计算资源。F表示边缘云数据中心服务器的CPU频率；fi,l表示物联网设备i的CPU频率；Di表示任务i的大小；Ci表示完成任务i所需要的CPU周期数；λ∈(0，1)，表示任务i在本地处理所占的比例。

图1 一个典型的MEC系统

2.1 本地计算模型

在本地计算模型中，移动应用程序将在物联网的终端设备处理。fi,l表示设备i的计算能力，用每秒的CPU周期数来衡量。因此，物联网设备i处理任务所需要的时间Ti,l和消耗的能耗Ei,l可以分别表示为 ：

(1)

Ei,l=PiλiCi

(2)

在公式(2)中，Pi表示每一个CPU周期所消耗的能量，可以用如下公式来表示：

(3)

ki是固定的参数，它的值取决于芯片的结构[19]。

2.2 通信模型

当应用程序通过无线信道卸载到边缘云时，上行链路传输会产生额外的时间和能量。对于物联网设备i来说，上行传输的数据率可用如下公式表示:

(4)

在公式(4)中，Bi表示分配给物联网设备i的带宽，qi表示传输功率，hi表示路径损耗，N0表示噪声功率。

基于公式(4)，上行传输时间可以表示为：

(5)

相应的上行消耗的能量为：

(6)

2.3 边缘云计算模型

当任务到达边缘云数据中心之后，服务器将分配计算资源来处理这些任务。对于物联网设备i来说，假设分配它的计算资源用Fi,e来表示，那么在边缘云中的处理时间可以表示为：

(7)

根据公式(5)和(7)，当任务在边缘云处理时，总的任务卸载所需要的时间可以表示为

Ti,0=Ti,t+Ti,e

(8)

基于以上模型，在本地处理的计算开销Zi,l和卸载到边缘云的计算开销Zi,0可以分别表示为：

(9)

(10)

相应的系统计算开销Zi可以表示为：

(11)

跟很多研究一样，忽略了把计算结果从边缘云传输到物联网设备的时间，这是由于对于很多应用程序来说，如人脸识别应用程序，计算结果的大小通常来说相对于输入数据来说小很多。

3 问题的构造和提出的解决算法

3.1 问题的构造

我们的目标是最小化系统计算开销，所构造的优化问题可以表示为：

3.2 提出的解决算法

在提出算法之前，先给出定理1，该定理在文献[19]中已经得到了证明。基于这个定理，提出解决问题1的算法。

在定理1的公式中，supf～(x,y)=supyf(x,y)。

定理1表明，当最小化一个函数时，可先优化其中一些变量，再优化剩下的变量。基于定理1，对于给定的λi，可以把问题1分为以下两个子问题：

子问题1：边缘云计算开销的最小化问题；

子问题2：本地计算开销的最小化问题。

在问题1的基础上，子问题1可以表达为：

(12)

其中，μ≥0是拉格朗日乘子。

根据凸优化中的KKT条件[19]，得到下面的结果：

(13)

(14)

μ≥0

通过公式(13)，可以知道μ>0，并且可以得到

(15)

因此，把公式(15)代入到公式(14)，可以得到

(16)

通过公式(16)，可以得到

(17)

公式(15)代公式(17)，可以得到公式(18)

(18)

因此，通过把公式(18)分别代入到公式(8)和(11)，就可以得到在任务卸载的情况下的计算时间和卸载开销。

令Ti,l=Ti,0，有

(19)

从而得到:

(20)

基于以上的结果，提出如下的资源分配和任务卸载的算法(表2)。

表2 计算资源和任务卸载的算法

4 仿真实验

4.1 参数的设置

假设一个MEC系统中有N=5个设备，对于物联网设备i的参数设置(见表3)主要参考文献[9，16-17]，但这些文献中，作者只考虑了二分任务卸载。故本研究侧重于探索部分任务卸载的情景，这大数据应用程序更实际。

表3 参数值的设置

4.2 实验结果

为了验证所提出算法的有效性，研究将针对本地任务处理(Local)(在这种情况下，所有的任务都放在本地的设备端处理)和边缘云任务处理(Edge Cloud)(在这种情况下，所有的任务都放在边缘云处理)两种基准算法进行比较：

如图2，物联网设备的任务由不同带宽值情况下的选择决定。1表示物联网设备把任务卸载到边缘云，0表示任务在本地的设备处理。从图中可以看出编号为需要计算资源比少的物联网设备，像设备1和2，在带宽比较小的情况下会在本地设备处理任务。随着网络带宽的增大，需要大量计算资源的物联网设备会选择把任务卸载到边缘云处理。

图2 物联网设备的任务选择决定

图3、图4、图5分别反映在不同网络带宽值情况下物联网设备的任务处理时间、能耗和系统代价的变化。其中，系统代价以能耗和任务处理时间作为衡量标准。如图3，当网络带宽值很小时，就所提出的算法和边缘处理算法来说，任务处理时间、能耗和系统代价都比较大。

图3 任务处理时间随着宽带的变化

图4显示在本地处理所需要时间最小情境下，所提出算法能达到最低的能耗，并且边缘云所消耗的能量逐渐比本地处理所消耗的能耗低。

图4 任务处理时间随着宽带的变化

随着网络带宽值的增大，如图5所示，很明显地发现，本地处理的系统代价超过边缘云处理的系统代价，边缘云的系统代价越来越小。跟两个基准算法相比，所提出的算法能取得比较小的系统代价，从而验证了所提出的算法的有效性。

图5 系统代价随着宽带的变化

5 结论和未来的研究工作

在本文中我们研究了移动边缘计算中的计算资源分配和任务卸载的问题。由于所建立的问题是MINP，是典型的NP难的问题。针对这种情况，我们提出了一种有效的任务卸载和计算资源分配的算法。仿真实验表明，所提出的算法能有效地降低系统的任务处理延迟和能耗。

在未来的研究工作中，针对所构造的问题，我们将研究其他的经典算法如，ADMM和Dinkelbach等算法的复杂性。同时，我们也将采用机器学习的算法，如深度强化学习来解决MINP的问题。