-
移动互联网的广泛应用,使得用户对数据速率和服务质量(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场景下超可靠低时延通信(ultra-reliable and low-latency communications, uRLLC)典型应用场景中单小区多用户的移动边缘计算问题,研究在边缘服务器与移动用户终端之间进行计算任务分配,实现时延和能耗联合优化。
-
设有一个包含gNB节点和
$N$ 个终端用户设备的无线接入网络,gNB节点上部署着MEC服务器和MEC任务管理器,如图1所示。gNB节点可以控制通信流量,MEC服务器负责对计算任务的处理,MEC任务管理器模块与MEC服务器在相同位置部署,负责MEC系统中计算任务分配等。用${ Z} = \left\{ {0,1, \cdots {{n}}, \cdots, {{N}}} \right\}$ 表示$N$ 个终端用户设备。每个终端用户设备都要完成大量计算任务,任务不能被分割,全部在终端CPU处理,或全部通过无线信道将任务分配到MEC服务器处理。MEC任务管理器获取终端用户的状态、需要分配的任务以及MEC服务器的可用资源,通过考虑能耗与时延等要求,确定所有终端用户的任务分配策略,并将任务分配策略反馈给终端用户设备和基站。第
$n$ ($1 \leqslant n \leqslant N$ )个终端用户的计算任务,表征为$ {A}_{n} \sim ({L}_{n},{\tau }_{n}^{d},{X}_{n}) $ ,其中,${L_n}$ 表示任务数据大小(单位:bit),$\tau _n^d$ 表示第$n$ 个终端用户的最大要求时延(单位:s),$F$ 是终端用户的总功率上限,${X_n}$ 表示单位数据计算量(以CPU周期/bit为单位),${X_n}$ 的与${L_n}$ 呈正相关[18-19]。设任务${A_n}$ 在终端用户上处理,需要的时间和能耗分别是$t_n^l$ 和$E_n^l$ ,综合代价为$C_n^l{\text{ = g}}_n^l( {t_n^l,E_n^l} )$ ,在MEC服务器上处理,需要的时间和能耗分别是$t_n^{{o}}$ 和$E_n^{{o}}$ ,综合代价为$C_n^{{o}}{{ = g}}_n^{{o}}\left( {t_n^{{o}},E_n^{{o}}} \right)$ 。用$ {\alpha }_{n}\in \left\{0,1\right\} $ 表征${A_n}$ 在终端用户或MEC服务器上处理,当${\alpha _n}{\text{ = }}1$ 时,${A_n}$ 在MEC服务器上处理,当${\alpha _n}{\text{ = }}1$ 时,${A_n}$ 在用户终端上处理。${\alpha _1}, {\alpha _2}, \cdots ,{\alpha _n}{\text{,}} \cdots {\text{,}}{\alpha _N}$ 构成的向量表征为${\boldsymbol{Z}}{\text{ = }}\left\{ {{\alpha _1},{\alpha _2}, \cdots ,{\alpha _n}{\text{,}} \cdots {\text{,}}{\alpha _N}} \right\}$ 。那么,$ N $ 个终端用户的计算总代价为:$$ {C_{{\rm{all}}}} = \sum\limits_{n - 1}^N {\left[ {\left( {1 - {\alpha _n}} \right)C_n^l + {\alpha _n}C_n^o} \right]} $$ (1) 通过求解
${\boldsymbol{Z}}$ ,使得该MEC系统的${C_{{\rm{all}}}}$ 最小。 -
若任务
${A_n}$ 选择在用户终端处理,终端设备的计算时延与能耗为:$$ t_n^l = \frac{{{L_n}{X_n}}}{{{f_n}}} $$ (2) $$ E_n^l = \kappa {L_n}{X_n}f_n^2 $$ (3) 式中,
${f_n}$ 表示用户设备$n$ 的CPU频率(以CPU周期s为单位);$\kappa f_n^2$ 表示CPU一个周期的能耗。用时延和能耗的加权和,表征任务
${A_n}$ 在用户终端处理所需的代价:$$ C_n^l = g_n^l(t_n^l,{\kern 1pt} {\kern 1pt} E_n^l) = I_n^tt_n^l + I_n^eE_n^l $$ (4) 式中,
$I_n^t$ 是任务${A_n}$ 的时延成本的权重;$I_n^e$ 是能耗成本的权重,$ 0 \leqslant I_n^t \leqslant 1 $ ,$ 0 \leqslant I_n^e \leqslant 1 $ 且$ I_n^t + I_n^e = 1 $ 。$I_n^t$ 与$I_n^e$ 对于不同类型的任务可能是不同的,为简单起见,认为每个任务的权重在整个计算过程中保持不变。若任务
${A_n}$ 分配至MEC服务器进行处理,需要将任务${A_n}$ 从用户终端传输到MEC服务器进行处理,处理结果由MEC服务器传输回本地。由于处理结果传回用户设备的数据量通常较小,且MEC服务器的传输功率很大,因此可以忽略处理结果由MEC服务器传输回本地的时延,则任务
${A_n}$ 由用户终端传输至MEC服务器与在MEC服务器处理的时延以及移动设备能耗分别为:$$ t_n^o = t_n^{{\rm{ul}}} + t_n^s = \frac{{{L_n}}}{{{R^{{\rm{ul}}}}}} + \frac{{{L_n}{X_n}}}{{{f_s}}} $$ (5) $$ E_n^o = {P^{{\rm{ul}}}}{t^{{\rm{ul}}}} + {P^i}{t^s} $$ (6) 式中,
$ {R^{{\rm{ul}}}} $ 是数据从用户终端传输至MEC服务器的速率;$ {f_s} $ 表示为该用户分配的虚拟CPU频率(以CPU周期/s为单位);$ {P^{{\rm{ul}}}} $ 指移动设备传输数据的功率;$ {P^i} $ 指移动设备空闲时的功率。考虑只有一个移动基站的系统,忽略其他小区的通信干扰,那么,用户设备的上传数据速率为:
$$ {R^{{\rm{ul}}}} = W\lg \left( {1 + \frac{{{P_n}{h_n}}}{{W{N_0}}}} \right) $$ (7) 式中,
$ W $ 是无线信道的带宽;$ {P_n} $ 是无线信道中第$ n $ 个用户设备的传输功率;$ {h_n} $ 是无线信道中第$ n $ 个用户设备的信道增益;$ {N_0} $ 为噪声功率。同样,用时延和能耗的加权和,表征任务分配至MEC服务器处理所需代价:
$$ C_n^o = g_n^o(t_n^o,\,E_n^o) = I_n^tt_n^o + I_n^eE_n^o $$ (8) 式中,
$ I_n^t $ 指任务${A_n}$ 的时延成本的权重;$ I_n^e $ 是能耗成本的权重,$ 0 \leqslant I_n^t \leqslant 1 $ ,$ 0 \leqslant I_n^e \leqslant 1 $ ,$ I_n^t + I_n^e = 1 $ 。同样,权重在任务处理过程中保持不变。因此,综合本地计算模型和MEC服务器的计算模型,
$ N $ 个任务分配所需代价的和可由式(1)得到。根据上述分析,建立问题的0-1整数规划模型:
$$ {C_{{\rm{all}}}} = \min \sum\limits_{n - 1}^N {\left[ {\left( {1 - {\alpha _n}} \right)C_n^l + {\alpha _n}C_n^o} \right]} \tag{9a}$$ $${\rm{s}}.{\rm{t}}.\quad\;\; \left( {1 - {\alpha _n}} \right)T_n^l + {\alpha _n}T_n^o \leqslant \tau _n^d\qquad \forall n \in N \tag{9b}$$ $$\sum\limits_{n = 1}^N {{\alpha _n}{f_n}} \leqslant F\qquad \forall n \in N \tag{9c}$$ $${\alpha _n} \in \left\{ {0,1} \right\}\qquad \forall n \in N \tag{9d}$$ 式(9a)是优化的目标,使得终端用户的时延和能耗的代价和最小;式(9b)是终端用户时延约束;式(9c)是终端用户的功率约束;式(9d)中
$ {\alpha _n} $ 是求解变量,表示任务${A_n}$ 在终端用户或在MEC服务器处理。 -
设一个带宽为
$ W = 50\;{\rm{MHz}} $ 的gNB小区,gNB基站部署有MEC服务器,用户终端设备随机分布在距离gNB基站200 m的范围内。MEC服务器的计算容量为$ F = 10\;{\rm{GHz}} $ ,每个用户设备的CPU频率为$ f_n^l = 2\;{\rm{GHz}} $ ,用户设备的传输功率和空闲功率设置为$ {P_n} = 500\;{\rm{mW}} $ 和$ P_n^i = 100\;{\rm{mW}} $ 。需要计算分配的数据$ {B_n} $ (单位:Bytes)满足(300, 500)之间的均匀分布,CPU周期$ {D_n} $ (单位:Megacycles)满足(900, 1 000)之间的均匀分布,时延要求为2 s。每个用户设备对时延和能耗分配的权重被设置为$ I_n^t = I_n^e = 0.5 $ 。平均信道增益$ {h_n} $ 遵循自由空间路径损耗模型:$$ {h_i} = {A_d}{\left( {\frac{{3 \times {{10}^8}}}{{4{\text{π}}{f_c}{d_i}}}} \right)^{{d_e}}} $$ (10) 式中,
$ {A_d} = 4.11 $ 表示天线增益;$ {f_c} = 915\;{\rm{MHz}} $ 表示载波频率;$ {d_e} = 2.8 $ 表示路径损耗指数。根据式(7),可以计算得到用户设备的数据上传速率
$ {R^{{\rm{ul}}}} $ 。设置用户设备数分别为4、6、8、10、12、14、16个,根据分支定界法计算该模型的最优解$ {\boldsymbol{Z}} = \{ {\alpha _1},{\alpha _2}, \cdots ,{\alpha _n}, \cdots ,{\alpha _N}\} $ ,如表1所示。表 1 不同用户设备数下的最优解
用户数 最优解 4 [1 1 1 1] 6 [1 1 0 1 1 1] 8 [0 1 1 1 0 1 1 0] 10 [0 1 0 0 1 1 1 0 1 0] 12 [0 0 1 1 1 0 0 0 1 0 1 0] 14 [0 0 1 0 0 1 0 0 0 0 1 1 0 1] 16 [0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1] 图2是不同用户数的代价曲线。从图中可以看出,本文优化方法的代价小于全部在用户终端处理或全部在MEC服务器处理,且随着用户数的增加,本文的优化方法优势更加明显。同时,本文将实验结果与能有效地帮助移动设备实现MEC系统的节能运行的最大节能优先算法[21](select maximum saved energy first, SMSEF)进行对比,本文算法利用贪婪选择解决优化问题,为MEC计算资源分配等问题提供解决方案,相较于传统方法节能效果更好,在用户数量增大时,本文方法的优势也逐渐增大。
固定用户设备数目为8个,改变MEC服务器的计算容量为6、8、10、12、14 GHz,代价曲线如图3所示。由于用户终端处理不需要MEC服务器,所以随着MEC服务器计算容量地增加,用户终端所需代价几乎不变。当MEC服务器计算容量足够大时,全部在MEC服务器处理和本文的优化方法得到的结果相接近。同时,相比于最大节能优先算法,本文方法在MEC服务器计算容量较小时所需的代价更小。
不失一般性,改变用户设备的CPU频率
$ f_n^l $ 为(1,3)之间的均匀分布,使得用户设备的CPU频率各不相同,设置用户设备数目分别为4、6、8、10、12、14、16个,其代价曲线如图4所示。可以看出,随着用户数目的增大,本文的优化方法相较于全部在用户终端处理、全部在MEC服务器处理和SMSEF算法,能取得较低的代价,且趋势与固定用户设备CPU频率时相同。提升MEC服务器的计算容量为100 GHz,并增加用户数量为50、100、150、200、250、300个,如图5所示。将本文的优化方法的代价,与全部在用户终端处理、全部迁移到MEC服务器处理、随机调度和循环调度进行比较(随机调度指随机决定任务的分配方式,循环调度指采用循环的方式将任务依次分配到用户设备或MEC服务器进行处理)。可以看出,随着用户数量的增加,本文方法相较于其他方法的优势更加显著。
随着用户规模的增大,本文方法进行任务分配决策的时间也在增加,如图6所示。当用户数小于150时,计算时间可以控制在0.1 s;当用户数为300时,计算时间在0.4 s以内。在不超过300个用户数的情况下,决策时间可接受。随着用户数的大规模增加,需要能够快速决策的智能优化方法来满足要求。
Joint Optimization Method of Energy Consumption and Time Delay for Mobile Edge Computing
-
摘要: 针对移动边缘计算中时延与能耗是关键性能指标,且相互制约的问题,研究了通过在边缘与终端之间进行任务分配,对时延与能耗进行联合优化。首先,建立了能耗与时延联合优化的0-1整数规划模型;其次,设计了对任务进行分配的分支定界算法。仿真结果表明,该方法能够有效降低移动边缘计算能耗与时延。Abstract: In mobile edge computing, time delay and power consumption are key performance indicators, and they are mutually restricted. This paper studies the joint optimization of time delay and power consumption by distributing tasks between edge and terminal. Firstly, the 0-1 integer programming model for joint optimization of energy consumption and time delay is established on the basis of describing the research problem. Secondly, a branch and bound algorithm for task assignment is designed. Finally, the simulation show that the proposed method can effectively reduce the energy consumption and time delay of mobile edge computing.
-
Key words:
- branch-and-bound method /
- energy consumption /
- joint optimization /
- mobile edge computing /
- time delay
-
表 1 不同用户设备数下的最优解
用户数 最优解 4 [1 1 1 1] 6 [1 1 0 1 1 1] 8 [0 1 1 1 0 1 1 0] 10 [0 1 0 0 1 1 1 0 1 0] 12 [0 0 1 1 1 0 0 0 1 0 1 0] 14 [0 0 1 0 0 1 0 0 0 0 1 1 0 1] 16 [0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1] -
[1] ZHANG Q, CHENG L, BOUTABA R. Cloud computing: State-of-the art and research challenges[J]. Internet Services Application, 2010, 1(1): 7-18. doi: 10.1007/s13174-010-0007-6 [2] LI A, YANG X, KANDULA S. Cloud Computing: Comparing public cloud providers[C]//The 10th ACMSIGCOMM Internet Measurement Conference (IMC) Melbourne: [s.n.], 2010: 1-14. [3] SHAFI M, MOLISCH A. F, SMITH P. J. 5G: A tutorial overview of standards, trials, challenges, deployment, and practice[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(6): 1201-1221. doi: 10.1109/JSAC.2017.2692307 [4] PATEL M, NAUGHTON B, CHAN C. Mobile-Edge computing—introductory technical white paper[R]. Sophia Antipolis: Mobile-Edge Computing Industry Initiative, 2014. [5] REZNIK A, ARORA R, CANNON M. Developing software for multi-access edge computing[R]. Sophia Antipolis: ETSI White Paper, 2017. [6] LEI L, ZHONG Z, ZHENG K, et al. Challenges on wireless heterogeneous networks for mobile cloud computing[J]. IEEE Wireless Communication, 2013, 20(3): 34-44. doi: 10.1109/MWC.2013.6549281 [7] BONOMI F, MILITO R, ZHU J, et al. Fog computing and its role in the Internet of Things[C]//Proceeding of MCC Workshop Mobile Cloud Computing. Helsinki: [s.n.], 2012: 13-16. [8] HRISHIKESH J, KANGWOO L, WOO S, et al. Powering the internet of things[C]//2014 IEEE/ACM International Symposium on Low Power Electronics and Design (ISLPED). La Jolla, CA: IEEE, 2014: 375-380. [9] SCHILIT W N. A system architecture for context-aware mobile computing[D]. New York: Columbia University, 1995. [10] PERERA C, ZASLAVSKY A, CHRISTEN P. Context aware computing for the internet of things: A survey[J]. IEEE Communications Surveys & Tutorials, 2014, 16(1): 414-454. [11] NUNNA S, KOUSARIDAS A, IBRAHIM M. Enabling real-time context-aware collaboration through 5G and mobile edge computing[C]//IEEE International Conference Information Technology New Generation. (ITNG). Las Vegas: IEEE, 2015: 601-605. [12] SUO H, LIU Z, WAN J, et al. Security and privacy in mobile cloud computing[C]//Proceeding of IEEE International Wireless Communications and Mobile Computing Conference(IWCMC). Cagliari: IEEE, 2013: 655-659. [13] 黄永明, 郑冲, 张征明, 等. 大规模无线通信网络移动边缘计算和缓存研究[J]. 通信学报, 2021, 42(4): 44-61. doi: 10.11959/j.issn.1000-436x.2021096 HUANG Y M, ZHENG C, ZHANG Z M, et al. Research on mobile edge computing and caching in massive wireless communication network[J]. Journal on Communications, 2021, 42(4): 44-61. doi: 10.11959/j.issn.1000-436x.2021096 [14] MAO Y, ZHANG J. Dynamic computation offloading for mobile-edge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3590-3605. doi: 10.1109/JSAC.2016.2611964 [15] YOU C, HUANG K, CHAE H. Energy-Efficient resource allocation for mobile-edge computation offloading[J]. IEEE Transactions on Wireless Communications, 2017, 16(3): 1397-1411. [16] CHEN X, JIAO L, LI W Z, et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE-ACM Transactions on Networking, 2016, 24(5): 2827-2840. [17] 张文柱, 曹琲琲, 余静华. 移动边缘计算中一种多用户计算卸载方法[J]. 西安电子科技大学学报, 2020, 47(6): 131-138. doi: 10.19665/j.issn1001-2400.2020.06.019 ZHANG W Z, CAO B B, YU J H. Multi-User computation offloading approach for mobile edge computing[J]. Journal of Xidian University, 2020, 47(6): 131-138. doi: 10.19665/j.issn1001-2400.2020.06.019 [18] MAO Y, YOU C, ZHANG J, et al. A Survey on mobile edge computing: The communication perspective[J]. IEEE communications surveys & tutorials, 2017, 19(4): 2322-2358. [19] LI J, GAO H, LV T, et al. Deep reinforcement learning based computation offloading and resource allocation for MEC[C]//IEEE Wireless Communications and Networking Conference. Barcelona: IEEE, 2018: 1-6. [20] 杨永健. 求全局最优化的几种确定性算法[D]. 上海: 上海大学, 2005. YANG Y J. Some deterministic algorithms for global optimization[D]. Shanghai: Shanghai University, 2005. [21] WEI F, CHEN S, ZOU W. A greedy algorithm for task offloading in mobile edge computing system[C]//2018 IEEE 18th International Conference on Communication Technology (ICCT). [S.l.]: IEEE, 2018: 149-157.