面向移动边缘计算网络的高能效计算卸载算法*张祥俊1,2, 伍卫国1,2, 张 弛1, 柴玉香1, 杨诗园1, 王 雄11(西安交通大学 计算机科学与技术学院, 陕西 西安 710049)2(西安交通大学 国家高性能计算中心(西安), 陕西 西安 710049)通信作者: 伍卫国, E-mail: wgwu@mail.xjtu.edu.cn摘　要: 移动边缘计算(mobile edge computing, MEC) 是一种高效的技术, 通过将计算密集型任务从移动设备卸载到边缘服务器, 使终端用户实现高带宽、低时延的目标. 移动边缘计算环境下的计算卸载在减轻用户负载和增强终端计算能力等方面发挥着重要作用. 考虑了服务缓存, 提出一种云-边-端协同的计算卸载框架, 在该框架中引入D2D (device-to-device, D2D) 通信和机会网络. 基于建立的模型, 将计算卸载决策问题转化为一个混合整数非线性规划问题, 并对无线特性和移动用户之间的非合作博弈交互制定了一个迭代机制来共同确定计算卸载方案. 对提出的计算卸载算法从理论上证明了多用户计算卸载博弈模型为严格势力场博弈(exact potential game, EPG), 卸载决策可获得全网范围内的最优效益. 考虑到服务器的计算资源、卸载任务数据量和任务延迟需求, 提出对用户和MEC 服务器之间最佳用户关联匹配算法. 最后, 模拟结果表明, 卸载决策算法具有较快的收敛速度, 并在能效方面优于其它基准算法.关键词: 移动边缘计算; 计算卸载; 用户关联匹配; 服务质量; 严格势力场博弈中图法分类号: TP393中文引用格式: 张祥俊, 伍卫国, 张弛, 柴玉香, 杨诗园, 王雄. 面向移动边缘计算网络的高能效计算卸载算法. 软件学报.http://www.jos.org.cn/1000-9825/6417.htm英文引用格式: Zhang XJ, Wu WG, Zhang C, Chai YX, Yang SY, Wang X. Energy-efficient Computing Offloading Algorithm forMobile Edge Computing Network. Ruan Jian Xue Bao/Journal of Software (in Chinese). http://www.jos.org.cn/1000-9825/6417.htmEnergy-efficient Computing Offloading Algorithm for Mobile Edge Computing NetworkZHANG Xiang-Jun1,2, WU Wei-Guo1,2, ZHANG Chi1, CHAI Yu-Xiang1, YANG Shi-Yuan1, WANG Xiong11(School of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, China)2(National High Performance Computing Center (Xi’an), Xi’an Jiaotong University, Xi’an 710049, China)Abstract: Mobile edge computing (MEC) is an efficient technology that enables end users to achieve the goal of high bandwidth and lowlatency by offloading computationally intensive tasks from mobile devices to edge servers. Computing offloading in the mobile edgecomputing environment plays an important role in reducing user load and enhancing terminal computing capabilities. This study considersservice caching, and proposes a cloud-side-end collaborative computing offloading framework, in which D2D communication andopportunistic networks are introduced. Based on the established model, the offloading decision problem is transformed into a mixed integernonlinear programming problem, and an iterative mechanism is formulated for the non-cooperative game interaction between wirelesscharacteristics and mobile users to jointly determine the computational offloading plan. The proposed computational offloading algorithmtheoretically proves that the multi-user computational offloading game under this framework is an exact potential game (EPG), and theoffloading decision is to uninstall under the optimal benefit strategy in the entire network. Taking into account the computing resources ofthe server, the amount of data for offloading tasks, and the delay requirements of tasks, based on the Gale-Shapley matching theory, thebest user association matching algorithm is improved and proposed. Finally, the simulation results show that the proposed unloading* 基金项目: 国家重点研发计划(2016YFB0201800, 2017YFB0203003)收稿时间: 2021-05-06; 修改时间: 2021-05-23, 2021-06-20; 采用时间: 2021-07-05软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cnJournal of Software [doi: 10.13328/j.cnki.jos.006417] http://www.jos.org.cn©中国科学院软件研究所版权所有. Tel: +86-10-62562563网络首发时间：2022-11-15 09:31:07网络首发地址：https://kns.cnki.net/kcms/detail/11.2560.TP.20221113.1329.023.htmldecision algorithm has a faster convergence rate and is superior to other benchmark algorithms in terms of energy efficiency.Key words: mobile edge computing; computation offloading; user association matching; quality of service; exact potential game1 引　言在先进的5G 蜂窝系统高速发展驱动下, 各种新兴的资源需求型、时延敏感型移动应用不断涌现. 例如数据流、实时视频、3D 游戏等, 这些新兴的应用为人们的生活带来了极大的便利. 然而, 随着业务逐渐复杂和多样化,移动网络的流量呈指数级增长. 传统的集中式网络架构由于回程链路负载过重、时延较长, 无法满足移动用户的需求[1,2]. 据IDC 预测, 到2025 年底将有超过416 亿终端设备联网, 其中超过50% 的数据需要在网络边缘分析、处理与存储[3]. 而传统的“云-端二体协同计算”模式已无法满足低时延、高带宽的需求. 移动边缘计算(mobile edgecomputing, MEC) 是将网络能力从核心网下放至边缘网络的新型体系结构, 使移动终端能够将计算负载转移到边缘服务器, 为这一问题提供了一种有效的解决方案[4] . 由于接近终端设备, MEC 不仅减轻了云中心的处理压力, 而且节省了端到云的高带宽成本, 降低了端到边缘节点的网络响应时延[5,6].计算卸载作为移动边缘计算中一种增强移动设备计算能力的技术已经崛起. 它能够打破移动设备资源限制,拓展移动设备计算能力、电池容量和存储能力等[7]. 通过将移动设备的计算任务卸载到边缘服务器中执行, 达到增强移动设备的计算能力、缩短服务时延、节省移动设备能耗的目的. 然而, 在动态变化的网络环境中, 移动用户很难实时的做出细粒度的计算卸载决策, 从而无法最大化降低系统卸载开销[8,9]. 一方面, 由于移动用户与边缘服务器之间的无线链路具有实施不确定性; 另一方面, 相比于云服务器, 边缘服务器在计算、存储等方面的资源仍相对有限[10]. 近年来, 基于MEC 的计算卸载问题得到了越来越多的关注, 学界提出了各种计算卸载策略. 现有的工作大多集中在小型同步MEC 系统的卸载设计[11−15], 卸载策略问题通常被表述为一个静态的凸或非凸优化问题,并将能源消耗和时延做为主要的性能指标. 例如, Tan 等人[16]研究了边缘计算系统中的可持续计算卸载. 他们提出在线奖励-最优拍卖的策略来优化卸载任务的长期奖励总和, 同时适应高度动态的能量收集过程和计算任务到达.针对大规模异步MEC 系统场景, Liu 等人[17]设计了一种基于索引的实时任务卸载策略, 该方法可捕获随机临界性的任务. 文献[18] 提出基于混合非正交倍数接入(non-orthogonal multiple access, NOMA)-正交多址(orthogonalmultiple access, OMA) 传输策略, 采用逐次凸逼近技术设计了一种求解复杂非凸问题的有效算法.然而, 上述工作大多在卸载决策前认定信道状态信息是已知和静态的, 这意味着无线信道的相干时间远远大于应用程序的执行时间[19,20]. 另外, 为了提高频谱效率和增强边缘用户的覆盖, 网络部署趋向于密集化, 这大大增加了不同接入单元(计算接入点或微基站) 的密度和规模, 导致传统卸载方法计算复杂度增大, 在信道相干时间内难以求解, 并且大多数方法仅考虑用户和运营商单方面的效益. 与此同时, 为实现用户邻近性并提高服务质量, 访问单元集成移动边缘服务器(MEC servers, MESs) 也趋向于密集, 所以合理的用户关联也十分重要. 为此, 需要设计快速、多用户的计算卸载机制, 同时考虑符合实际计算资源和任务延迟场景下的用户关联决策.本文考虑了多用户的MEC 场景(如图1 所示), 我们设计了高能效的计算卸载算法进行卸载决策, 同时寻求最佳的用户关联匹配. 特别是在卸载决策问题中, 引入机会网络做服务缓存, 并使用博弈方法分析建立了一个全网最优效益的计算卸载算法. 最后, 模拟结果表明, 提出的计算卸载算法与基准算法相比始终保持了最小化能耗和延迟, 且具有良好的性能和时间复杂度特性. 综上所述, 本文的贡献如下:(1) 本文提出了一个具有MEC 密集部署的计算卸载系统模型, 其中小基站(small base stations, SBSs) 和边缘计算节点都配备了MESs. 在边缘网络计算卸载过程结合了服务缓存, 显著地降低了延迟和能耗, 提升了系统的整体效率.(2) 提出了云-边-端协同的计算卸载框架, 引入D2D 通信和机会网络的计算卸载场景, 并结合服务缓存, 更好适配了5G 蜂窝系统下的MEC 应用场景. 从而使云计算中心强大计算能力和边缘云距离终端设备的邻近性优势互补. 另外, 对不同卸载模式建立了能耗和时延模型, 将效益最优化问题转化成混合整数非线性规划问题, 该问题属于NP-hard.(3) 对多用户计算卸载问题, 每个用户是理性的(为收益最大化而调整卸载策略), 采用博弈方法可保证全网每个用户的收益最大化, 并通过数学推导证明了多用户计算卸载问题为严格势力场博弈. 最后设计了基于博弈理论2 软件学报 ****年第**卷第*期的计算卸载算法, 并分析算法收敛性和时间复杂度. 此外, 在卸载决策基础上, 改进基于Gale-Shapley 的匹配算法,设计了最佳用户关联匹配算法.(4) 在模拟实验中, 我们考虑了一个实际的场景, 其中部署多个用户和SBSs, 并与其它基准算法进行比较, 验证了该算法的高能效.本文第2 节总结了相关工作. 在第3 节中, 我们详细描述系统模型和问题形式化. 第4 节给出多用户联合计算卸载和用户关联匹配算法. 第5 节讨论计算卸载和关联匹配算法的实验结果和性能评价. 最后, 第6 节对本文进行总结.Cloud serverMEC serverMEC serverMEC serverMECserverONsONs ONsCNCNCNCNCNCNCAPCAPCAPMUMUMUMUMUMUD2D linkCellular linkONs linkFiber link图 1　联合计算卸载模型2 相关工作移动边缘计算(MEC) 作为物联网和5G 的一项关键使能技术, 可显著减少核心网络拥塞导致的延迟. 计算卸载是近年来MEC 中的一个关键问题和研究热点[21,22], 例如, 文献[23] 提出了一个分时和计算时限约束下的总能耗最小化优化方法, 制定了对具有异构输入数据到达时间和计算截止时间的资源管理策略. 在文献[24] 中, 设计了一种混合光纤-无线网络, 为集中云和多接入边缘计算的共存提供支持, 并提出了采用光纤-无线接入网络的架构和卸载方案. 为了提高效率, 文献[25−30] 集中于二进制全卸载策略的研究, 以最小化延迟或能耗. Guo 等人[31]综合考虑了卸载决策、信道分配以及计算资源分配方案的优化. 通过结合遗传算法和粒子群算法的优点改进卸载算法性能和收敛速度, 提出了一种基于遗传算法和粒子群算法的次优算法. 然而, 这些工作只关注无线接入网的计算卸载过程, 忽略了无线接入网信道信息的动态变化和干扰. 针对多用户计算卸载问题, 文献[32] 提出了一个综合效益最优的D2D 资源共享方案, 该方案可显著改善卸载网络的性能. 文献[33] 利用D2D 卸载计算、并结合用户行为和特定网络运行条件, 开发了大规模D2D 支持的蜂窝网络ESE 评估框架. 为分析信噪比分布和平均速率,文献[34] 提出了一种D2D 通信框架. 此外, 文献[35] 中, 作者采用了频谱共享, 并提供了两种不同共享模式的覆张祥俊 等: 面向移动边缘计算网络的高能效计算卸载算法3盖性能比较分析.最近的一些工作致力于采用分散式的计算卸载方案. 例如, 文献[36] 提出一个以共同确定计算卸载方案、传输调度规则和定价规则的博弈算法. 该算法可使全网范围内的效益最大化, 同时实现移动用户之间的博弈均衡.Quang 等人[37]针对边缘节点对通信和计算资源争用问题提出了一种非合作的具体潜在博弈(noncooperative exactpotential game), 旨在最大化计算卸载的长期效益. Zhang 等人[38]采用进化博弈论(evolutionary game) 优化子载波分配方案, 为信道状态较好的子载波分配更多的子载波, 使能量效率最优. 在文献[39] 中研究了一种MEC 网络中新的计算卸载问题, 移动设备可以通过D2D 通信或MEC 服务器将任务卸载到分布式计算节点上, 并将移动设备的卸载决策问题推导为一个序列博弈. 然而, 文献[39] 没有到考虑服务缓存, 即在分布式计算节点和边缘服务器[40]上没有缓存与计算任务运行所依赖的二进制文件. 由于边缘服务器的计算和存储资源有限, 会导致不可避免的影响服务质量.鉴于此, 我们对多接入MEC 的计算卸载进行了新的研究. 与已有工作关注点不同的是, 本文研究了异构网络环境下多用户计算卸载和传输调度的能耗和时延最小化问题, 引入D2D 通信和机会网络到MEC 网络, 并结合服务缓存. 为克服边缘节点资源不足的缺陷, 我们设计了云-边-端协同的计算卸载框架, 既保证了边缘服务器与终端设备的邻近性, 又利用了云端的强大计算和存储资源. 本文集中于研究在云-边-端协同的计算卸载问题上使用博弈方法, 相比其他传统方法, 所设计的基于多用户卸载问题的博弈卸载算法和用户关联匹配算法, 可在信道相干时间内快速求解组合优化问题, 并综合考虑了全网效益最优的卸载策略. 数值计算结果表明, 与现有的优化方法相比, 该算法在计算时间上显著减少, 且性能接近最优.3 系统模型及问题形式化3.1 网络模型如图1 所示, 我们提出了一个云-边-端协同的计算卸载框架, 与已有卸载框架不同, 所提出的框架是结合了D2D 通信和机会网络, 并考虑计算任务服务缓存的联合计算卸载模型. 该框架3 层如下.(1) 云服务器层: 该层是由各类资源充足的云节点组成, 可提供集中式的云服务和缓存终端用户任务依赖的二进制文件功能.(2) 边缘服务层: 在本层中, 接受计算的服务器包括多接入MEC 服务器和具备一定计算能力的计算节点(computing node, CN). MEC 服务器被附加到蜂窝通信基站中, 移动设备连接到MEC 服务器和计算节点分别通过蜂窝链路和D2D 链路, 这两条链路之间由于频率不同, 相互隔离, 互不干扰.(3) 移动设备层: 该层由各类移动终端组成, 任意移动设备的计算密集型任务都可以在本地运行或卸载到边缘服务层进行计算. 边缘服务层缓存了计算任务所依赖的二进制文件以确保卸载任务正确执行. 注意, 当MEC 服务器和计算节点存储空间不够, 未能缓存所需的二进制文件时, 可通过核心网向云服务器层或机会网络缓存所需的文件.��� = fl1; l2; : : : ; l j; : : : ; lJ gLji = fBj;ini ;Bj;outi ;Cji ;Dji ;T ji;MAXg; i 2 N; j 2 J Bj;iniBj;outi Cji Dji T ji;MAXLji Lji考虑移动边缘计算环境是由N 个移动用户MUs (mobile user, MU) 和K 个计算接入点CAPs (computationalaccess points, CAPs) 构成的多用户移动边缘计算系统, 我们分别用N={1, 2, …, i, …, N}和K={1, 2, …, k, …, K}表示, 这里的接入点可以是具有计算能力的基站和移动边缘计算服务器等. 定义 表示所有的任务集, j 表示计算任务的类型, 每个移动设备运行着不同类型的计算任务, 如计算密集型和延迟敏感的应用程序. 每个移动设备i 上的j 类型的计算任务 . 其中, 是计算任务的输入数据,是返回的计算结果, 是计算任务所需的CPU 周期数, 是计算任务所需依赖的二进制文件大小, 是任务 的最大可接受时延. 每个MU i 要么在本地执行计算任务 , 要么完全卸载任务到MEC 服务器执行.3.2 通信模型Vn在MEC 系统中, 移动设备可以通过计算无线接入点将计算任务卸载到边缘服务器[41]. 我们定义每个移动用户MU n 的设备传输速率为 , 表示为:4 软件学报 ****年第**卷第*期Vn = Wklog20BBBBBBBBBBBBBB@1+pnhn;kw0 +Σm2Nnfngpmhm;k1CCCCCCCCCCCCCCA(1)pn Wk w0hn;k本文考虑了通信的链路之间的相互干扰. 在上式中, 是MU n 的传输功率, 是信道带宽, 是信道的背景噪音功率, 是MU n 和计算接入点k 间的信道增益, 是一个独立同分布的随机变量[42], 可由公式(2) 得出.hn;k = g0(d0d)(2)其中,  是路径损耗指数, d0 是参考距离, d 是移动设备与 MEC 服务器的距离, g0 是路径损耗常数.3.3 计算模型aji = f0;1;2;3;4g、Toff II考虑到服务缓存, 我们在卸载模型中引入了D2D 通信和机会网络(opportunistic networks, ONs). 机会网络是一种自组织网络, 它引入节点移动带来的相遇机会从而实现通信, 使通信不再依赖于源节点与目标节点之间的完整链路. 其次, 当通信双方距离较近时, 移动终端可以直接利用D2D 技术进行通信, 节省了大量信令带宽资源, 并减少了传输延迟. 由于路径损耗远低于基站到MU 之间的通信损耗, D2D 技术可以提高网络信道的频谱效率[42−44].每个MU 决定是否将其计算任务卸载到K 个计算接入点中任意一个, 我们定义MU i 的j 类计算任务的卸载类型和链路传输数据时延分别为 , 使用指示函数 表示不同卸载模式, 具体如下.aji = 0 LjifMU tlocalLji(1) 本地计算: 当 , , 计算任务 通过MU i 的本地计算资源执行任务. 定义MU 的设备CPU 周期频率为. 令 表示本地执行任务的时间. 可由公式(3) 给出:tlocalLji=CLifMU(3)Tofflocal = 0 (4)aji = 1 LjitMECLji; tTranLji; tCompLji; tResLji;ToffMECfMEC;