基于次模优化的边云协同多用户计算任务迁移方法

梁冰，纪雯

（1.中国科学院计算技术研究所，北京 100190；2.中国科学院大学计算机科学与技术学院，北京 100190；3.移动计算与新型终端北京市重点实验室，北京 100190；4.鹏城实验室，广东 深圳 518055）

1 引言

随着人工智能和物联网移动应用的快速发展，自然语言处理、增强现实、人脸识别、行为分析等高计算能力和通信资源需求的服务被广泛地应用在各种移动终端设备中。由于移动终端设备受到电池电量、计算能力和存储空间等限制，通常难以满足上述应用的超低时延和低能耗的需求。因此，高资源需求的应用服务与资源受限的移动设备之间的鸿沟给当前及未来物联网移动应用的发展带来了极大挑战[1-3]。

针对上述挑战，移动云计算（MCC,mobile cloud computing）的提出为这些应用需求提供了新的解决思路[4-5]。MCC 利用无线网络将移动终端的应用任务卸载到计算能力更强的云端执行，可以解决终端计算能力不足的问题，并降低终端能耗。然而，云服务器往往位于远离用户终端位置的核心网，因此终端与云服务器之间的数据交换过程需要花费较多的传输时间和能耗。并且，针对许多特定的应用，例如语音识别、智能环境控制等，较长的时延会损害用户的使用体验并影响相关应用的性能表现。

为了解决上述移动云计算的缺点，欧洲电信标准化协会（ETSI,European Telecommunications Standards Institute）提出了一种新型的计算和存储服务技术——移动边缘计算（MEC,mobile edge computing）[6-7]。MEC 作为5G 的一项核心技术，通过将服务器部署在离用户更近的边缘位置，例如附近的网关和基站侧，能更有效地解决用户对特定应用服务的需求，例如高计算能力、存储服务、高可靠性、移动性支持和低时延等[8-10]。利用MEC 网络将地理分散的用户的计算任务从移动终端设备迁移到资源丰富的MEC 服务器，从而加快任务的执行[11-12]。然而，受限于移动边缘计算网络的通信能力以及MEC 服务器的计算资源和存储容量的限制，卸载过多的计算任务到边缘侧会给计算资源有限的MEC 服务器及网络传输带来沉重的负担，进而降低边缘计算服务的用户体验[13-14]。对于上述云计算和边缘计算所存在的缺点，结合各自优势的基于边云联合计算的方式为当前的应用需求提供了新的解决思路。然而，如何平衡云端和边缘端的计算任务的负载，提高边云联合计算的服务质量，成了边云联合计算待解决的关键问题之一[15-16]。

本文提出了一种基于边云联合计算下的多用户任务卸载方案，该方案联合考虑了用户任务卸载选择、边缘端和云端的通信及计算资源分配的问题，进而最大化系统的效用。本文的主要贡献如下。

1) 基于用户QoE（quality of experience）的效用函数，将用户任务卸载选择以及边缘端和云端的通信、计算资源分配的问题表示为一个混合整数非线性规划（MINLP,mixed integer nonlinear programming）问题。本文以最大化系统效用为目标，对用户的任务卸载决策、发射功率、边缘节点的计算资源分配以及回程链路的通信资源分配等问题进行了联合优化。

2) 本文将原始的系统效用最大化问题分解成2 个子问题，分别为固定用户的卸载决策后的资源分配问题以及优化资源分配问题后对应的最优值函数下的任务卸载决策问题。对于资源分配问题，本文进一步将该问题分解为用户上传发射功率分配问题、边缘端计算资源分配问题和核心网传输带宽分配问题，并利用拟凸和凸优化技术对上述3 个问题进行了求解。

3) 通过对用户系统效用函数的分析，本文从卸载决策的角度证明了系统效用函数是一个次模函数，进而基于次模理论设计了一种贪心的卸载策略算法用来求解用户任务的卸载决策问题。仿真实验结果表明，与其他卸载方案相比，本文提出的基于边云联合的计算方案下的用户卸载方法能够有效降低用户任务执行时延和能耗，并且在资源受限的条件下仍然能够保持稳定良好的系统效用值。

2 相关工作

如今，国内外学者开展了大量针对移动云计算和移动边缘计算的任务卸载问题的研究。文献[17]研究了动态环境下的多用户计算卸载问题。考虑到多个物联网设备同时通过无线信道卸载计算任务时的信道干扰问题，该研究将用户的计算卸载决策问题表述为一种进化博弈的模型，并设计了一种基于强化学习的进化博弈算法用来求解用户的卸载决策。文献[18]研究了基于车辆边缘计算网络中的计算卸载问题。考虑到车辆需要在动态网络环境下实时确定其任务卸载策略，该研究提出了一种多用户非合作计算卸载博弈，以调整车辆边缘计算网络中每辆车的任务卸载概率，并同时考虑了车辆与边缘计算接入点之间的距离。进一步地，该研究基于计算卸载博弈模型构造了分布式最佳响应算法，以最大化每种车辆的效用。文献[19]构建了适用于移动和普适计算场景的三层架构下的用户卸载问题，提出了一种分布式的均衡计算算法用来确定用户的计算任务卸载的决策。文献[20]研究了动态环境下移动云计算的多用户计算卸载问题，考虑到移动用户在将计算任务卸载到移动云上的自利性和自私性，将动态环境下移动用户的卸载决策过程描述为随机博弈问题，最后求解用户的卸载决策。文献[21]提出了移动边缘计算和云计算的联合卸载优化问题，并设计了一种基于博弈论的卸载调度和负载均衡方案，但该研究仅对分层框架下的用户卸载决策进行了建模与优化，并未优化边、云的计算以及通信资源的分配问题。上述相关研究对用户任务卸载的决策问题给出了一些求解的方法，但是这些研究主要集中在用户的卸载决策问题上，忽略了卸载过程中系统有限的通信与计算资源分配的问题。针对上述研究存在的问题，文献[4]研究了基于移动边缘云计算的无线信道干扰环境下的多信道多用户的计算卸载问题，提出了一种分布式的用户计算卸载算法并联合考虑了边缘云的计算资源分配问题。文献[22]以移动边缘计算系统下的用户移动设备能耗最小化为目标，提出了一种计算卸载、子载波分配和计算资源分配的联合优化策略，并设计了一个有界改进分支定界算法来寻找全局最优解。文献[23]提出了一种联合用户计算任务部分卸载和资源分配的方案，联合考虑所需能耗、部分卸载和资源分配约束条件，最大程度地减少所有设备任务执行产生的时延之和。文献[24]提出了一种由半定松弛、交替优化和连续调节组成的三步算法，联合优化了用户任务的卸载决策以及计算和通信资源的分配，以最大限度地降低所有用户执行任务产生的能耗和时延。文献[25]考虑了移动边缘计算用户计算卸载的花费和时延问题，该研究以最小化移动设备系统花费和时延为目标，提出了一种多目标的计算卸载与资源分配的算法，以联合优化用户的卸载决策以及边缘端的资源分配。文献[26]面向工业物联网场景下的雾节点计算任务，以雾节点能耗最小化为目标，提出了一种节能的计算卸载方案，并综合考虑了雾节点能耗、本地计算、传输状态和等待状态的能耗。针对该能耗最小化问题，该研究提出了一种加速梯度算法，可以快速找到最优的任务卸载比，从而提高了传统方法的收敛速度。文献[27]考虑了基于移动边缘计算的节能卸载框架并联合优化无线通信资源和计算资源，以最小化用户设备的能耗为目标，设计了基于基尼系数的贪婪启发式算法以降低用户的能耗。文献[28]研究了5G 异构网络的MEC 节能计算卸载机制，以最小化系统能耗为目标，联合优化任务卸载和无线资源分配问题，并结合5G 异构网络的多址特性，提出了一种节能计算卸载（EECO,energy-efficient computation offloading）算法，有效提升了系统能耗的效率。文献[29-30]研究了边缘端或近端云的联合用户卸载决策与资源优化的问题，并分别提出了一种启发式的卸载决策算法提升系统的效用。但上述研究仅考虑用户任务只向边缘端或云端进行任务卸载，并未考虑在边云联合计算的环境下用户如何进行卸载的策略以及资源的优化问题。

综上所述，已有的相关研究主要包含以下2 个方面：1) 在不考虑通信及计算资源分配的情况下，优化云或边缘计算的用户卸载决策；2) 针对云或边缘计算的用户任务卸载，联合优化用户的卸载决策以及资源分配的问题。然而，在实际应用场景中，当选择任务卸载的用户数量增多时，考虑到边缘节点的计算能力以及远端云传输带宽的受限性，仅面向云端或边缘端的任务卸载将带来任务卸载的高时延性问题[1]。当多用户选择将任务卸载到云端时，由于远端的云需要支撑大量用户的接入需求，因此还需要考虑传输过程中核心网有限的带宽资源分配问题。针对上述问题，本文研究了基于边云联合计算下的任务卸载方法，联合优化了该方法下的用户计算任务卸载决策、边缘端计算和通信资源及远端传输过程中核心网有限的带宽资源分配。并且，本文提出的方法还能够解决仅考虑边缘计算或云计算情况下的用户计算卸载问题，因此具有更广泛的适用性。

3 系统模型

如图1 所示，本文给出了基于边云联合计算的任务卸载框架的系统模型。系统模型由一个宏eNode B（MeNB）和其所覆盖小区内的多个终端设备用户组成。该宏eNode B 配备了边缘计算服务器并通过核心网与远端的云服务器相连。

图1 边云联合计算的多用户任务卸载框架

本文定义MeNB 覆盖下的用户数量的集合为U={1,2,…,U}，u∈U 表示该用户集合中的某一个用户。设用户u需要执行的计算任务为Tu={du,cu}，且该任务不可再分割。其中du为该任务执行需要传输的数据量（例如系统的设置、参数的设置以及程序代码等），cu为该任务执行所需要的计算资源（例如完成该任务所需要的CPU cycle 总数）。每个用户可以选择的任务执行模式如下：1) 本地计算，即用本地的终端设备处理任务；2) 边缘计算，即通过蜂窝网络将任务卸载到MeNB 后，在边缘计算服务器处理任务；3) 云端计算，首先通过蜂窝网络将任务卸载到MeNB 后，再通过核心网传至远端的云服务器处理。此外，本文定义了任务卸载决策变量xu,j={0,1}。其中xu,j=1表示用户u选择模式j进行计算，xu,j=0表示用户u选择其他模式进行计算。j=0,1,2 表示所选择的任务执行模式，其中j=0 表示本地计算，j=1 表示边缘端计算，j=2 表示云端计算。接下来，本文将分别给出本地计算、边缘端计算及云端计算。

3.1 本地计算

根据文献[20,28]，用户执行任务Tu的能耗可表示为

3.2 边缘端计算

当用户选择通过将任务卸载到边缘端及云端时，完成任务的总时间包括：1) 用户将计算任务上传至MeNB 所需的时间；2) 用户任务在MEC的执行时间；3) 将任务完成的结果从MEC 传输到用户设备的时间。如果该任务卸载到云端执行，则完成该任务的总时间除了包含将任务上传至MeNB 所需的时间外，还包含：1) 用户将计算任务从MeNB 上传至云端所需的时间；2) 用户任务在云端的执行时间；3) 将任务完成的结果从云端传输到MeNB 的时间。由于通常情况下，任务完成的输出结果的大小远远小于任务的输入大小，并且考虑到传输的下行速度远大于上行速度，因此本文忽略任务从云端传输到MEC 的时间以及MEC 传输到用户设备的时间[29,33-34]。

本文考虑上传时用户网络为多用户正交频分多址接入（OFDMA,orthogonal frequency division multiple access）系统，该系统中的每个信道都是正交的，因此可以忽略小区内的干扰。定义B为系统的无线链路的上行带宽，则每个用户可用的上行带宽，其中N为小区内的用户数量。由此，得到用户u的任务Tu的上行传输速率为

其中，pu表示用户u上传任务的输入为du时的发射功率，pu为正数且不超过允许的最大值Pu，即0

接下来，给出用户u的任务Tu在MEC 的执行时间。本文设MEC 服务器的计算资源上限为fe，其表示边缘服务器可用的CPU cycle 总数。所有请求将任务卸载到MEC 服务器进行计算的用户共同分享MEC 服务器的计算资源。定义MEC 服务器分配给卸载到边缘的用户u的计算资源大小为，且。由于MEC 服务器计算资源有限，分配给所有将任务卸载到边缘端的用户的计算资源总和不能超过MEC 服务器的计算资源的上限，因此满足约束条件，即

根据式(4)和式(6)，可以得出当给定用户发射功率pu时，用户选择边缘计算模式执行任务卸载的总时延为

3.3 云端计算

当用户选择云端计算模式执行任务卸载时，假设云端给卸载任务Tu分配的计算资源大小为。尽管云端具有非常丰富的计算资源，但由于需求远程云端计算的任务请求数量非常庞大，因此云端会为每个用户分配固定且受限的计算资源。本文设为固定大小，且等于云端能为用户分配的计算资源的最大值。因此，类似于式(6)，可以得出用户任务在云端的计算时间为

考虑到在云端执行用户任务需要通过核心网传至远端的云服务器，因此可以得出选择云端执行模式时任务卸载的总上传时延为

由于用户仅在将任务上传至MeNB 时有能源消耗，因此用户通过云端计算模式产生的能耗为

3.4 基于边缘端−云端联合计算的系统效用最大化问题

在边缘端−云端联合计算框架下，用户的QoE 主要由完成任务所产生的时延和能耗体现。基于3.1～3.3节各模式下计算卸载模型及用户偏好，本文定义用户u的卸载效用函数为[29-30]

在上述系统效用最大化问题中，卸载决策x与通信资源和计算资源的优化相结合。由于卸载决策x是0-1 整型向量且f、p、R是连续型向量，因此式(15)优化问题是一个MINLP 问题[35]。考虑到优化问题的表达结构，当给定卸载决策x的取值时，可以将复杂度较高的原始优化问题分解为具有较低复杂度的主问题和一系列的子问题[36]。因此，式(15)所示问题可以转化为

由于卸载决策的限制条件C1 与资源分配策略的限制条件C2～C6 是可分离的，因此式(16)所示的优化问题可以分解为主问题和子问题，分别如式(17)和式(18)所示。

将式(15)的优化问题分解为式(17)和式(18)的优化问题并不会改变其最优解[36]，接下来，本文将分别给出式(17)和式(18)优化问题的求解方法，并最终求解出式(15)问题。

3.5 联合优化边云资源方法

根据式(14)的形式，当给定卸载决策x时，式(18)优化问题可以转化为

根据式(22)的形式可以发现，当给定卸载策略x时，式(22)等号右边的第三项为常数。对于式(22)的上传发射功率pu、边缘计算资源以及核心网传输带宽的分配，其目标函数和约束条件可以彼此解耦。因此，可以将式(21)的优化问题转化为求解以下3 个独立的优化问题：1) 上传发射功率分配问题；2) 边缘端计算资源分配问题；3) 核心网传输带宽分配问题。

3.5.1 上传发射功率分配问题

上传发射功率分配优化问题的表达形式为

3.5.2 边缘端计算资源分配问题

边缘端计算资源分配优化问题的表达形式为

证明详见附录2。

3.5.3 核心网传输带宽分配问题

核心网传输带宽分配优化问题的表达形式为

证明证明过程与引理2 的思路相同。

3.6 联合资源分配的任务卸载策略算法

定理1系统效用函数V为次模函数

证明详见附录3。

根据定理1，上述系统效用最大化问题式(34)能够被证明是NP-hard 问题[39-40]。针对该问题，本文提出了一种基于次模理论的贪心卸载策略算法，求解出问题式(34)的近似解[41-42]。

算法2基于次模理论的贪心卸载策略算法

3.7 算法时间复杂度分析

4 仿真结果

本节通过仿真实验评估所提出的边云联合计算方案下的优化资源分配和多用户任务卸载决策算法的系统效用。具体仿真环境如下：假设U个用户随机均匀地分布在200 m×200 m 的小区中，基站部署在小区的中心位置，N 为小区内覆盖用户的数量。用户计算任务输入数据大小du在100～1 000 KB随机均匀分布，所对应的完成任务需要的计算资源cu（CPU cycle 总数）在[0.2,1]Gcycle 随机均匀分布。考虑到用户本地设备计算能力的异构性，在{0.5 GHz,0.8 GHz,1.0 GHz}集合内等概率取值[20]。参考之前研究的用户设备功率参数值选择[4,30]，并结合当前最新相关的实测设备功率情况，本文选择的用户设备计算能力所对应的={0.5 W,0.75 W,0.9 W}[32]。设用户最大传输发射功率Pu=100 mW，MeNB 到云端的上行总传输速率Rc=100 Mbit/s[43]。其余相关仿真参数设置如表1 所示。

表1 仿真参数设置

在同等的参数设置下，本节选择将本文提出的基于边云联合计算方案下的用户卸载策略的系统效用表现分别与以下方案进行对比。

1) 本地计算：所有的用户全部采用本地计算的方式来完成任务。

2) 基于边缘计算的联合资源优化的全卸载策略：所有的用户全部将任务卸载到边缘端执行，如文献[44-45]，并采用3.4 节的优化资源分配方案。

3) 基于云端计算的联合资源优化的全卸载策略：所有的用户全部将任务卸载到云端执行，如文献[44-45]，并采用3.4 节的优化资源分配方案。

不失一般性地，仿真结果均为各仿真实验重复1 000 次并取平均的结果。

随着用户数量的变化，各方案的系统效用值的变化如图2 所示。从图2 可以看出，随着用户数量的增加，对比其他方案，本文提出的方案（以下简称本文方案）的系统效用值有很大的提升。当用户数量较少时，除本地计算方案外，其他各方案的系统效用值随用户数量的增加而增加，且本文方案系统效用值要高于其他2 种方案。当用户总数超过某一阈值时，伴随着用户数量的增加，选择全卸载的边缘计算和云计算方案的系统效用值会逐渐下降，且当用户的数量超过一定阈值时，系统效用值低于本地计算方案。这是因为当卸载用户数量过多时，受限的上行通信资源和边缘计算资源不能为每个需求用户提供更丰富的资源需求，进而导致更高的计算时间和传输时延。用户通过全卸载的方式发送和执行任务将导致所有的用户对有限的资源进行竞争。当卸载用户过多时，边缘计算方案下的边缘节点分配给用户的计算资源会低于本地的计算资源，而云计算方案下用户较低的上行通信资源会导致任务卸载的传输时延过高，进而导致以上2 种方案的系统效用降低甚至低于本地计算的效用。而随着用户增加，应用本文方案下的用户卸载策略选择算法仍能维持较高且稳定的系统效用值。这是因为该方案能够合理地为用户规划任务卸载的模式选择，从而保证有限的计算和通信资源的最大化利用。

为了评估本文方案针对应用任务时的系统效用性能，本文选择人脸识别这一特定的应用任务：该计算任务输入数据大小du=420 KB，完成该任务需要的计算资源cu=1 000 Mcycle[30]，相关实验结果如图3 所示。

图2 不同用户总数条件下各方案的系统效用

图3 特定任务下的不同用户总数条件下各方案的系统效用

从图3 可以看出，当针对人脸识别这一特定的任务时，本文方案的系统效用值始终高于全卸载的边缘计算方案和全卸载云计算方案。并且随着用户总数逐渐增多，全卸载边缘计算方案和全卸载云计算方案的系统效用值会逐渐下降，而本文方案依旧能够保持稳定较高的系统效用。本文方案通过联合边缘端、云端以及本地端的所有可用的计算和通信资源，在用户数量增加时依然保持系统效用平稳占优。

基于人脸识别这一特定的应用任务，在不同用户总数的条件下，本文方案中用户对边缘端、云端以及本地计算模式的任务卸载的决策选择的总数如图4 所示。从图4 可以看出，当用户数量较少时，用户更倾向于将任务卸载到边缘端和云端执行。随着用户数量的增加，选择将任务卸载到边缘端和云端的用户数量逐渐趋于平稳，用户主要由边缘端和云端计算模式向本地计算模式迁移。这是因为，随着用户数量的增加，受到上行通信资源和边缘计算资源的限制，边缘节点的计算资源和上行的通信资源逐渐不能满足用户的计算和通信需求，进而更多用户愿意选择计算资源稳定且没有传输时延的本地计算模式。

图4 特定任务下的不同用户总数条件下各模式参与用户数

接下来，本文分析了在人脸识别这一特定的应用任务情况下，随着用户对时间偏好权重的变化，即从0.1 变化到0.9 的过程中，所有用户的平均时间消耗情况，结果如图5 所示。从图5 可以看出，随着用户对时间偏好权重的增加，任务卸载的平均时间消耗逐渐降低。从不同用户数量下的任务平均时间消耗曲线能够看出，当系统中有更多的用户时，任务的平均时间消耗更多。这是由于当系统中用户数量增加时，将有更多的用户争夺有限的通信和计算资源，因此每个用户所获得的计算和通信资源会降低，进而导致通过任务卸载方式完成任务的平均时耗增加。

图5 不同用户对时间偏好权重下的任务卸载平均时耗对比

5 结束语

本文提出了一种基于边云联合计算的多用户任务卸载方案。本文提出的方案通过联合考虑边缘计算以及云计算的相关优势特性，解决了多用户异构任务的卸载选择问题并实现了边缘端和云端资源的合理分配和充分利用。通过证明系统效用函数是次模函数，本文利用次模理论设计了一种基于边云联合计算的贪心的用户卸载策略选择算法，并联合优化了边云联合计算框架下计算和通信资源的分配。仿真结果表明，在面对受限的通信资源和计算资源的条件下，且当卸载计算的用户数量增加时，本文提出的方案仍能保持稳定良好的系统效用。

附录1 Λ(pu)严格拟凸性证明

附录2 引理2 证明

附录3 效用函数为次模函数证明