计算资源受限的移动边缘计算服务器收益优化策略

黄冬艳，付中卫，王 波*

（1. 深圳大学电子与信息工程学院，广东深圳518060；2. 认知无线电与信息处理省部共建教育部重点实验室（桂林电子科技大学），广西桂林541004）

（*通信作者电子邮箱glbluewind@126.com）

0 引言

随着物联网和5G 移动通信技术的发展，在智能手机、传感器和可穿戴计算设备等移动设备上运行计算密集型和延迟关键型应用已经成为趋势［1-2］。但由于受到自身计算能力和能量的限制，移动设备通常不具备运行这类应用的能力。

移动边缘计算（Mobile Edge Computing，MEC）［3］通过将计算任务从移动设备卸载到具有相对丰富计算资源的边缘服务器上执行，实现了在移动设备上运行计算密集型和延迟关键型应用的愿景。与移动云计算不同，MEC 服务器通常部署在网络边缘（例如，基站和无线局域网接入点），因此可以避免移动用户和远程云中心之间的长距离数据传输，从而显著降低延迟和移动用户的能量消耗。因此，MEC是5G网络的关键技术，获得了业界的广泛关注［4］。

通过优化任务卸载决策、资源分配或任务执行次序实现MEC 的吞吐量，端到端延迟或能量效率等性能的提升是MEC研究中的热点。

考虑到频谱资源受限，为了提高MEC 系统的吞吐量，文献［5-6］分别提出了相应的接入控制策略、频谱资源和计算资源联合优化算法。另一方面，为了降低移动设备的延迟和能耗，有文献提出通过多用户博弈［7］、联合优化子载波和功率的分配［8］等方式实现移动设备延迟最小化，以及结合数据压缩与频谱资源分配以降低移动用户的能耗［9］。

但在文献［5-9］的分析中均假设MEC 服务器具有无限的计算能力。事实上，受到部署场地和成本的制约，MEC 服务器的计算能力相比大型云计算中心是有限的。这导致任务在服务器的处理时间以及任务在MEC 服务器任务缓存区内的排队延迟不可忽略，特别是在负载密集的网络中。据研究表明，在5G 场景下，任务在MEC 服务器的处理时间远大于其上传时间［10］。以图像识别为例，对于569 KB 大小的图像，在4G网络下的传输时间为1.24 s，在5G 网络下的传输时间为0.001 s，而在MEC 服务器处理时间为1.12 s［10］。可见，在5G网络中，MEC 处理时间比上传时间高了3 个数量级。因此，MEC 面临的挑战从频谱资源和计算资源受限转变为计算资源受限，需要在计算资源受限的情况下，进一步研究MEC 的性能优化问题［11-14］。

文献［11］提出了一种延迟最小化的计算任务卸载方案，由移动用户根据MEC 服务器任务缓存区的状态、本地处理单元的执行状态和传输单元的状态做出卸载决策。文献［12-13］则研究了基于定价的分布式计算任务卸载决策，将MEC服务器和移动用户之间的交互建模为Stackelberg 博弈模型。在该博弈模型中，MEC 服务器依据收益最大化设定服务费。给定服务费后，每个用户依据延迟最小化［12］或是能耗最小化［13］自主做出卸载决定。此外，文献［14］通过优化任务执行次序，减小移动用户和MEC服务器的加权能耗。

在重业务负载的场景下，由于计算能力有限，为保证卸载任务的QoS（例如，在线游戏、增强现实（Augmented Reality，AR）、虚拟现实（Virtual Reality，VR）等延迟敏感型应用需要保证延迟需求），MEC 服务器只能进行接入控制，为部分用户提供计算服务。另一方面，为了收回设备部署和维护成本并实现盈利，MEC 服务器非常关注如何利用有限的资源最大化自身的收益。因此，为了确保卸载任务的QoS，同时最大化自身的收益，服务器必须合理地确定允许哪些任务卸载并确定卸载任务的执行次序。

本文关注于计算资源受限的MEC 服务器收益优化问题。与文献［12-13］不同，本文研究了存在不同QoS需求的多用户MEC 系统，提出通过优化任务执行次序提高MEC 服务器的收益。主要贡献如下:1）将MEC 服务器收益最大化问题建模为以任务执行次序为优化变量的优化问题；2）提出了一种基于分支定界法的排序算法，以获得收益优化的任务执行次序。

1 系统模型

考虑一个由基站和K个移动用户组成的多用户MEC 系统。该系统的每个用户都有一个计算密集型任务，并请求将任务卸载到MEC 服务器。每个任务都具有严格的截止期限。系统模型如图1所示。

此外，本文采用如下假设:

1）信道状态信息是已知的；

2）信道状态在任务卸载期间保持不变；

3）一旦决定将任务卸载到MEC 服务器，移动用户将不会停止卸载，直到卸载完成。

任务卸载过程如图2 所示。 首先，移动用户k(k∈{1，2，…，K})向MEC 服务器发送卸载请求消息。卸载请求消息包括客户端中间件收集的任务信息。收到一批卸载请求后，MEC 服务器做出卸载决定并将该决定反馈给用户。如果MEC服务器同意卸载，那么用户将任务上传并向MEC服务器支付相应的费用；否则，用户不需要支付费用。

图1 多用户MEC 系统Fig. 1 Multi-user MEC system

图2 MEC系统的任务卸载流程Fig. 2 Task offloading process in MEC system

2 问题建模及优化算法

考虑一个有多个计算密集型任务同时请求卸载的重业务负载场景。首先，将MEC 服务器收益最大化问题建模成以任务执行次序为优化变量的最优化问题；然后，提出了一种基于分支定界法的排序算法来寻找该问题的最优解。

2.1 问题建模

定义 MEC 服务器中一个执行次序为s=(s(1)，s(2)，…，s(k))。 其 中s是1，2，…，K的 一 种 排 列，s(k)∈{1，2，…，K}。举例说明，当K= 3，s=(2，1，3)，则s(1)=2，表示第2号任务排在次序s的第1个位置。

若将任务s(k)卸载到MEC 服务器执行，则完成该任务的所需时间包括任务上传时间，在MEC 服务器的队列等待时间，服务器处理时间和计算结果下载时间。由于计算结果的大小通常远小于计算任务本身，因此可以合理地认为计算结果的下载时间远小于任务上传时间。为简化分析，在接下的分析中主要关注总时间的3 个主要部分:上传时间、队列等待时间和执行时间。

令ls(k)（单位:bit）表示任务s(k)的大小，Gs(k)（单位:cycle/bit）表示计算强度，ds(k)（单位:s）表示任务的截止期限，MEC服务器的CPU时钟频率为fc（单位:Hz）。

1）任务上传时间tu，s(k)为:

其中rs(k)是传输速率。根据香农定理，可知:

其中:Bs(k)为分配给移动用户s(k)的传输带宽，N0为噪声功率谱密度，hs(k)是介于移动用户s(k)和基站之间的信道增益，ps(k)为传输功率。

3 仿真结果

本章通过仿真验证所提算法的性能。仿真设定参照5G环境设定［10，12］。仿真设定每个任务的大小均匀分布在100～500 Kbit，计算强度均匀分布在1 000～2 000 cycle/bit，截止期限均匀分布在30～150 ms。此外，可用带宽B= 20 MHz，信道增益在［-50，-30］dBm 范围内均匀分布，用户的传输功率设置为200 mW，噪声功率谱密度为-174 dBm/Hz，MEC 服务器单位收益为每CPU周期1×10-8元。

首先比较了本文算法（Proposed algorithm）、低延迟任务优先（Low-Latency Task First，LLTF）算法、大任务优先（Large Task First，LTF）算法和先到先服务（First Come First Served，FCFS）算法的平均收益。具体而言，LLTF 算法和LTF 算法分别优先考虑具有更高延迟要求和更高计算资源要求的任务，FCFS 算法则优先考虑上传时间最小的任务。在相同的仿真参数下，独立运行所提算法与对比算法各10 000 次并记录每种算法的平均收益。然后，将所提算法的平均收益与对比算法的平均收益进行比较。

如图3 所示:1）所提算法的平均收益高于其他算法的平均收益。随着移动用户数量的增加，所提算法优势变得更加明显。给定MEC 服务器的CPU 频率fc= 10 GHz，当移动用户数K= 24 时，所提算法的平均收益分别比LTF、LLTF 和FCFS高11%、14%和21%。2）随着移动用户数K的增加，每种算法的平均收益均趋于稳定。这是因为在工作负载重的网络中，fc成为收益增加的瓶颈。

图3 不同算法的MEC服务器平均收益Fig. 3 Average revenue of MEC server in different algorithms

本文还比较了不同算法的任务完成率，即MEC 服务器能够接受的任务数占任务总数的百分比。任务完成率体现了MEC 服务器容纳用户的能力。任务完成率越高意味着可以满足更多用户的需求。如图4 所示，当用户数较少时，所提算法的平均任务完成率高于LTF 和FCFS，并且该算法的平均任务完成率接近LLTF。随着用户数量的增加，当fc= 20 GHz，K= 24 时，所提算法的平均完成率低于LLTF 约4%，比FCFS低约3%，高于LTF。采用所提算法可以完成近32%的任务，但采用LTF仅完成18%的任务。

从图3 和图4 中，还可观察到:1）随着用户数量的增加，LLTF 和FCFS 具有较高的完成率但是这两种算法的平均收益均低于所提算法。这意味着收益并不完全等价于已完成任务的数量。2）所提算法的平均收益高于其他对比算法；同时，该算法的任务平均完成率略低于LLTF 与FCFS。因此，所提算法在优化收益同时也很好地兼顾容纳用户的能力。

图4 不同算法的平均任务完成率Fig. 4 Average task completion rate of different algorithms

4 结语

本文研究了计算资源受限的MEC 服务器收益优化问题。以最大化MEC 服务器收益为优化目标，提出了一种基于分支定界法的算法，以获得最优的接入策略和任务执行次序。仿真结果表明，在重负载网络中，该算法能够有效提高MEC 服务器的平均收益。本文仅讨论了每单位CPU 周期的价格固定的情况，未来拟在价格可更改的场景下进一步研究MEC 服务器收益优化问题。