移动边缘计算时延与能耗联合优化方法

张先超，任天时，赵 耀，樊 锐

(1. 东南大学移动通信国家重点实验室 南京 210096；2. 嘉兴学院浙江省医学电子与数字健康重点实验室 浙江 嘉兴 314001；3. 北京理工大学信息与电子学院 北京 海淀区 100081；4. 中国电子科学研究院 北京 石景山区 100041)

移动互联网的广泛应用，使得用户对数据速率和服务质量(quality of service, QoS)的需求呈指数增长。尽管移动终端设备的中央处理器性能不断提升，但仍无法应对处理任务的急剧增长，移动终端设备计算能力仍显不足。并且，移动终端设备的计算需要大量能耗，降低了设备的续航时间。这些问题推动了移动云计算概念的出现和发展[1]。

近年来物联网技术的发展与普及，导致移动云计算的缺点逐渐暴露。首先，云计算无法满足新兴应用场景对更低网络时延的需求[2]；其次，接入设备数量的急剧增加将导致网络数据传输量呈爆炸性增长趋势，采用云计算汇聚的网络流量会使核心网不堪重负[3]。为此，欧洲电信标准化协会(European telecommunications standards institute, ETSI)于2014 年提出了移动边缘计算(mobile edge computing,MEC)的概念，给出定义[4]：在无线接入网(radio access network, RAN)内和靠近移动用户的移动网络边缘，MEC 能够提供IT 服务环境和云计算的能力。2017 年，ETSI 将MEC 的概念延伸至Wi-Fi、车联网等接入网络，并将其更名为多接入边缘计算(multi-access edge computing)，简写仍为MEC[5]。

移动边缘计算由移动边缘服务器、基站、终端用户、核心网、云等构成，其中，移动边缘服务器部署在基站附近，为该基站小区内的用户提供计算资源。通过直接向移动边缘服务器寻求服务，用户可以享受低时延、高能效的体验。当移动边缘服务器的计算能力不足以支撑用户需求时，位于核心网的云计算(mobile cloud computing, MCC)才会进一步服务于用户的计算[6-7]。相比于MCC，MEC 有更低的时延、更低的移动设备能耗[8]，更好的上下文感知能力[9-11]和更强的隐私性与安全性[12]。MEC 技术能够有效应用的关键是计算任务在边缘服务器与终端之间有效分配[13]。计算任务分配就是将任务分配给合适的任务处理设备，包括本地处理器、临近的IoT 设备处理器、MEC 服务器、云服务器等，同时，明确应用中任务的依赖关系，给出任务处理的先后顺序。

5G 的商用投入和6G 高速发展增强了医疗急救、灾害救援等应急场景的处置能力。这些应急场景对现场信息处理有更高的要求。然而，用户端的计算能力通常难以满足，如移动急救车辆上的计算能力无法满足车辆上信息处理的需要，采用边缘计算是事宜的解决方案。

在应急情景下，单个小区中需要对多达数十个用户的计算任务进行合理有效的分配，以满足其低时延、低能耗的应用需求。文献[14]研究了带有能量收集设备的绿色MEC 系统，并给出了基于李亚普诺夫优化的动态计算任务分配策略，以最小化执行延迟和任务失败概率为目标，能够接近最优来解决任务分配问题。文献[15]将最优分配表征为在计算延迟约束下，最小化加权能耗和的凸优化问题，证明了对于分配优先级函数，最优策略具有阈值特征，优先级高于和低于给定阈值的用户将分别执行完整分配和最小值分配。文献[16]采用了博弈论的方法来实现有效的分布式计算任务分配，将移动设备用户之间的分布式计算卸载决策问题表述为一个多用户计算卸载博弈，设计了一种可以实现纳什均衡的分布式计算任务分配算法。文献[17]设计了一种移动边缘环境下对多用户时延与移动边缘计算服务器资源分配均衡性进行联合优化的计算卸载方法，构造了联合优化平均卸载时延与资源分配均衡度的目标函数，从而有效地减小多用户的平均卸载时延，同时平衡各移动边缘计算服务器的工作负荷。

本文针对5G 场景下超可靠低时延通信(ultrareliable and low-latency communications, uRLLC)典型应用场景中单小区多用户的移动边缘计算问题，研究在边缘服务器与移动用户终端之间进行计算任务分配，实现时延和能耗联合优化。

1 问题描述

设有一个包含gNB 节点和N个终端用户设备的无线接入网络，gNB 节点上部署着MEC 服务器和MEC 任务管理器，如图1 所示。gNB 节点可以控制通信流量，MEC 服务器负责对计算任务的处理，MEC 任务管理器模块与MEC 服务器在相同位置部署，负责MEC 系统中计算任务分配等。用Z={0,1,···n,···,N}表 示N个终端用户设备。每个终端用户设备都要完成大量计算任务，任务不能被分割，全部在终端CPU 处理，或全部通过无线信道将任务分配到MEC 服务器处理。MEC 任务管理器获取终端用户的状态、需要分配的任务以及MEC 服务器的可用资源，通过考虑能耗与时延等要求，确定所有终端用户的任务分配策略，并将任务分配策略反馈给终端用户设备和基站。

图1 多用户移动边缘计算系统构成

通过求解Z，使得该MEC 系统的Call最小。

2 联合优化模型

若任务An选择在用户终端处理，终端设备的计算时延与能耗为：

若任务An分配至MEC 服务器进行处理，需要将任务An从用户终端传输到MEC 服务器进行处理，处理结果由MEC 服务器传输回本地。

由于处理结果传回用户设备的数据量通常较小，且MEC 服务器的传输功率很大，因此可以忽略处理结果由MEC 服务器传输回本地的时延，则任务An由用户终端传输至MEC服务器与在MEC 服务器处理的时延以及移动设备能耗分别为：

式中，Rul是数据从用户终端传输至MEC 服务器的速率；fs表示为该用户分配的虚拟CPU 频率(以CPU 周期/s 为单位)；Pul指移动设备传输数据的功率；Pi指移动设备空闲时的功率。

考虑只有一个移动基站的系统，忽略其他小区的通信干扰，那么，用户设备的上传数据速率为：

式中，W是无线信道的带宽；Pn是无线信道中第n个 用户设备的传输功率；hn是 无线信道中第n个用户设备的信道增益；N0为噪声功率。

同样，用时延和能耗的加权和，表征任务分配至MEC 服务器处理所需代价：

式(9a)是优化的目标，使得终端用户的时延和能耗的代价和最小；式(9b)是终端用户时延约束；式(9c)是终端用户的功率约束；式(9d)中αn是求解变量，表示任务An在终端用户或在MEC 服务器处理。

3 分支定界算法

分支定界算法是求解整数规划问题的常用算法，分支把区域逐次分割成越来越多的小区域，定界在这些小区域内，确定目标函数的上界和下界[20]。

针对模型式(9)，设计如下分支定界算法。

算法1：时延与能耗联合优化分支定界算法

1) 初始化全局参数，全局上界U=∞，全局下界L=−∞， 全局最优值C∗←∅, 问题最优解Z∗←∅，初始化松弛线性规划问题队列Q

2) 初始化N个用户的参数，计算用户本地计算时延Tnl， 本地计算能耗Enl，MEC 服务器计算时延Tno，MEC 服务器计算能耗Eno

3) 计算初始整数规划问题求解所需参数

4) 取第一个用户的任务分配决策α1=0和 α1=1，分作两个问题

5) 将两个问题分别松弛求解，得到解Z1、Z2和目标函数值C=min(Z1,Z2)

6) 全局下界更新L←C

7) 若两问题均无解，则算法失败，停机

8) 若解 αn∈{0, 1},n=1,···,N，则Z∗←Z，算法结束，停机

9) 否则，将解、目标函数值与约束参数放入队列Q

10) whileQ不为空 do

11) 以广度搜索取出当前问题

12) ifC>Udo

13) continue

14) if 解αn∈{0, 1},n=1,···,Ndo

15) ifU>Cdo

16)U←C

17) end if

18) ifC∗>Cdo

19)C∗←C,Z∗←Z

20) end if

21) else

22) 寻找解中第一个不为0 或1 的分量，取其下标idx，带入其已确定的节点值，构建两个新的线性规划问题r1和r2

23) ifr1计 算成功 andr2计算失败

24) 将r2的 解与约束参数放入队列Q

25) elifr2计 算成功 andr1计算失败

26) 将r1的 解与约束参数放入队列Q

27) elifr2计 算成功 andr1计算成功

28) 首先将目标函数值C小的问题加入队列Q

29) end if

30) end if

31) end while

区别于随机算法，该算法按照广度优先的方式对状态空间树进行搜索，通过不断地剪枝操作寻找最优解的子节点，最终获得模型式(9)的确定性解。具体来说，该算法在获取所有用户参数之后，将0-1 整数规划问题的解松弛为[0,1]之间的连续变量，根据松弛线性规划问题的解是否为整数，来判断下一步继续分支还是停止计算。该算法通过不断地松弛求解，得到原问题的最优解，且其在数十个用户的小规模问题下可以适用。

本文算法的复杂度主要取决于对松弛线性规划问题的求解。在使用分支定界法的过程中，每进行一次分支，就会产生两个松弛线性规划问题，即最多会产生 2N个松弛线性规划问题，因此在最差的情况下，本文算法的复杂度为O(2N)。在进行分支定界法的剪枝操作后，当用户数为150 个时，计算时间可以控制在0.1 s，因此在几十个用户规模的问题下该算法可以适用。

具体来说，算法的1)～3)行为初始化全局参数，将上界和下界均设为极值，将最优解与最优目标函数值设为空，再使用环境模型计算出分支定界算法所需要的参数；算法的4)～8)行进行初次的分支，将第一个用户的决策分为两支后对分支后的两个问题松弛计算。判断该线性规划问题的解，若解均为0 或1，则算法结束，找到最优目标函数值；若无解，则算法失败；否则开始分支。算法的8)～29)行通过不断将不能求解的子问题和目标函数值已经大于问题上界的节点剪枝，同时对该问题下没有剪枝的叶子节点分支，直到得到解均为整数0 或1，算法结束。

4 仿真分析

设一个带宽为W=50 MHz 的gNB 小区，gNB基站部署有MEC 服务器，用户终端设备随机分布在距离gNB 基站200 m 的范围内。MEC 服务器的计算容量为F=10 GHz，每个用户设备的CPU 频率为fnl=2 GHz，用户设备的传输功率和空闲功率设置为Pn=500 mW和Pin=100 mW。需要计算分配的数据Bn(单位：Bytes)满足(300, 500)之间的均匀分布，CPU 周期Dn(单位：Megacycles)满足(900,1 000)之间的均匀分布，时延要求为2 s。每个用户设备对时延和能耗分配的权重被设置为Int=Ine=0.5。平均信道增益hn遵循自由空间路径损耗模型：

式中，Ad=4.11表 示天线增益；fc=915 MHz表示载波频率；de=2.8表示路径损耗指数。

根据式(7)，可以计算得到用户设备的数据上传速率Rul。设置用户设备数分别为4、6、8、10、12、14、16 个，根据分支定界法计算该模型的最优解Z={α1,α2,···,αn,···,αN}，如表1 所示。

表1 不同用户设备数下的最优解

图2 是不同用户数的代价曲线。从图中可以看出，本文优化方法的代价小于全部在用户终端处理或全部在MEC 服务器处理，且随着用户数的增加，本文的优化方法优势更加明显。同时，本文将实验结果与能有效地帮助移动设备实现MEC 系统的节能运行的最大节能优先算法[21](select maximum saved energy first, SMSEF)进行对比，本文算法利用贪婪选择解决优化问题，为MEC 计算资源分配等问题提供解决方案，相较于传统方法节能效果更好，在用户数量增大时，本文方法的优势也逐渐增大。

图2 代价与用户设备数的关系

固定用户设备数目为8 个，改变MEC 服务器的计算容量为6、8、10、12、14 GHz，代价曲线如图3 所示。由于用户终端处理不需要MEC服务器，所以随着MEC 服务器计算容量地增加，用户终端所需代价几乎不变。当MEC 服务器计算容量足够大时，全部在MEC 服务器处理和本文的优化方法得到的结果相接近。同时，相比于最大节能优先算法，本文方法在MEC 服务器计算容量较小时所需的代价更小。

图3 用户设备数为8 时代价与MEC 服务器计算容量关系

不失一般性，改变用户设备的CPU 频率fnl为(1,3)之间的均匀分布，使得用户设备的CPU 频率各不相同，设置用户设备数目分别为4、6、8、10、12、14、16 个，其代价曲线如图4 所示。可以看出，随着用户数目的增大，本文的优化方法相较于全部在用户终端处理、全部在MEC 服务器处理和SMSEF 算法，能取得较低的代价，且趋势与固定用户设备CPU 频率时相同。

图4 不同CPU 频率下代价与用户设备数的关系

提升MEC 服务器的计算容量为100 GHz，并增加用户数量为50、100、150、200、250、300个，如图5 所示。将本文的优化方法的代价，与全部在用户终端处理、全部迁移到MEC 服务器处理、随机调度和循环调度进行比较(随机调度指随机决定任务的分配方式，循环调度指采用循环的方式将任务依次分配到用户设备或MEC 服务器进行处理)。可以看出，随着用户数量的增加，本文方法相较于其他方法的优势更加显著。

图5 扩大MEC 服务器容量时代价与用户设备数关系

随着用户规模的增大，本文方法进行任务分配决策的时间也在增加，如图6 所示。当用户数小于150 时，计算时间可以控制在0.1 s；当用户数为300 时，计算时间在0.4 s 以内。在不超过300 个用户数的情况下，决策时间可接受。随着用户数的大规模增加，需要能够快速决策的智能优化方法来满足要求。

图6 分支定界法计算时间与用户数的关系

5 结 束 语

本文针对移动边缘计算中低时延与低能耗两大要求，研究了时延与能耗联合优化方法。通过对优化问题的研究，建立了0-1 整数规划模型，采用分支定界算法对模型予以求解，通过仿真，验证了本文的优化方法的优越性和适用性。本文方法不仅能够和5G 技术协同解决VR/AR 应用的不足，还能够应用于联合作战、生命健康、智能制造等多个领域。为了适用超大规模用户终端的需求，未来还将研究智能优化方法，进一步提升移动边缘计算任务分配的效率与效果。