面向多边缘设备协作的任务卸载和服务缓存在线联合优化机制

张秋平 孙 胜 刘 敏 李忠诚 张曾琪

(中国科学院计算技术研究所 北京 100190)

(中国科学院大学 北京100049)

(zhangqiuping＠ict.ac.cn)

近年来,随着无线网络技术的飞速发展,移动终端设备数量剧增.数百亿的移动终端设备导致数据爆炸性增长,催生出许多计算密集型和时延敏感型的新兴应用,如人脸识别、虚拟/增强现实等.这些新兴应用具有低时延、高带宽等服务需求.传统云计算将移动终端用户产生的数据传输到远端云服务器中进行集中处理,由于传输距离较长、回程链路受限等原因导致响应时延过高(数十至百毫秒级[1])、网络拥塞等问题,难以满足计算密集型和时延敏感型应用的服务需求.在此背景下,移动边缘计算(mobile edge computing,MEC)应运而生.

移动边缘计算通过在距离移动终端用户较近的无线网内部部署一定的通信、计算、存储等资源,提供类似云计算中心的能力,允许终端用户将自身产生的计算密集型和时延敏感型的计算任务卸载到边缘设备处执行,利用边缘设备靠近数据源的优势达到显著缩短传输距离、降低处理时延、改善用户体验、提升网络运行效率的目的.区别于云计算中的大规模数据处理中心,移动边缘计算中边缘设备的通信、计算、存储等资源相对有限.当终端用户的任务需求激增时,大量终端用户需要向边缘设备卸载任务,但是由于边缘设备资源相对有限,因此容易出现任务负载过重、处理时延增加等问题,导致任务处理的时效性缺失.另一方面,边缘设备间存在负载分布不均衡的情况,容易出现有些边缘设备任务过载而其他边缘设备资源闲置的问题.通过多边缘设备协作共同执行计算任务可以在保障终端用户服务需求的同时实现边缘设备间负载均衡,有效应对上述问题,因此多边缘设备协作成为一种必然趋势.

多边缘设备协作是指在具有通信、计算、存储能力的边缘设备间合理卸载计算任务,通过多边缘设备协作共同执行计算任务,以期满足多个终端用户的服务需求,并有效提高边缘设备的资源利用效率,实现边缘设备间负载均衡.边缘设备执行计算任务时需要进行服务缓存.服务缓存是指在边缘设备中缓存应用服务及相关数据库,使得相应的计算任务可以在边缘设备处执行[2].即使边缘设备具有充足的计算资源,但是若该边缘设备没有缓存相关服务则无法执行相应的计算任务,从而导致边缘设备的计算资源不能得到充分利用.由此可知,任务卸载和服务缓存之间相互耦合,服务缓存策略决定了能否进行任务卸载,而任务卸载结果反映了服务缓存策略的性能,因此对任务卸载和服务缓存进行联合优化是至关重要的.

本文研究移动边缘计算中面向多边缘设备协作的任务卸载和服务缓存联合优化问题,解决上述问题面临2方面挑战:1)任务卸载和服务缓存相互耦合,解决上述问题需要考虑2个子问题之间的相互作用,同时子问题耦合导致问题求解呈指数级增长,极大增加了问题求解的难度.2)不同边缘设备的任务负载及资源状态随时间、空间动态变化,需要考虑时空双维限制.时间维度上,边缘设备服务的终端用户随时间动态变化,且终端用户的服务缓存需求无法提前预知,边缘设备仅能获取终端用户的情景信息,终端用户情景信息相似时其服务缓存需求也是相似的,因此可以根据终端用户的情景信息在线学习其服务缓存需求,用于制定未来的服务缓存策略.在空间维度上,终端用户的位置分布动态变化且存在分布不均衡的现象,导致边缘设备间负载不均衡,进而影响边缘设备的任务执行性能,因此需要考虑边缘设备间协作.

本文提出一种面向多边缘设备协作的任务卸载和服务缓存在线联合优化机制,通过多边缘设备协作,实现边缘设备间负载均衡,目标是在满足任务执行时延限制的条件下,最小化任务整体执行时延.本文的主要贡献包括3个方面:

1)将面向多边缘设备协作的任务卸载和服务缓存联合优化问题建模为混合整数非线性规划问题,并设计一种任务卸载和服务缓存在线联合优化(online Joint optimization of task Offloading and service Caching,JOC)算法求解上述问题,实现服务缓存策略的在线动态更新,并通过多边缘设备协作,进行任务卸载,实现负载均衡.

2)将原始问题解耦为服务缓存和任务卸载2个子问题.针对服务缓存子问题,提出基于情景感知组合多臂赌博机的协作服务缓存(collaborative service caching based on contextual combinatorial multiarmed bandit,3CMAB)算法,基于用户情景信息在线学习多边缘设备的协同服务缓存策略,实现服务缓存策略的动态更新;针对任务卸载子问题,基于3CMAB算法获得的服务缓存策略,利用计算任务与卸载位置之间的卸载偏好,在计算任务与卸载位置之间进行匹配,并在多边缘设备间进行负载重分配,使得多边缘设备间的负载相对均衡,提高边缘设备执行任务的比例,有效降低任务整体执行时延.

3)利用大量仿真实验验证JOC算法的性能.将JOC算法与其他4种基准算法进行比较,实验结果表明JOC算法可以有效实现多边缘设备间的负载均衡,降低系统中任务整体执行时延.与非协作的算法相比,JOC算法的任务整体执行时延降低23.8%.与最新的多边缘设备协作的研究工作[3]相比,JOC算法的任务整体执行时延降低5.4%.此外本文所提服务缓存算法的执行时延可忽略不计,即可实现实时动态服务缓存.

1 相关工作

移动边缘计算已经引起了产业界和学术界的广泛关注.近年来涌现出大量与移动边缘计算相关的标准化工作[4].欧洲电信标准协会(European Telecommunications Standards Institute,ETSI)最早开始推进MEC标准化工作,于2014年12月成立了MEC ISG工业标准组,公布了20余份标准化文稿及白皮书[5-7],研究内容涵盖MEC平台架构、业务需求、管理编排等.在ETSI的推动下,第3代合作伙伴(The 3rd Generation Partnership Project,3GPP)、中国通信标准化协会(China Communications Standards Association,CCSA)等国际及国内标准化组织也相继启动了MEC标准化工作.3GPP SA2 23.501协议[8]中指出MEC能够让运营商和第三方服务部署在靠近终端设备接入点的地方,缩短端到端时延,同时降低传输负载.CCSA无线通信技术工作委员会(TC5)针对移动边缘计算中的平台架构、场景需求、关键技术等内容进行立项[9].互联网工程任务组(Internet Engineering Task Force,IETF)中的应用层流量优化(application layer traffic optimization,ALTO)工作组也积极开展MEC相关标准化的推进工作.

产业界对移动边缘计算也尤为关注.由华为、腾讯等牵头发起的业界首个5G移动边缘计算开源平台EdgeGallery于2020年正式上线.该平台聚焦5G场景,构建MEC资源、应用、安全、管理的基础框架.中国移动于2018年成立了边缘计算开放实验室,中国电信设立了边缘计算开放平台ECOP,中国联通在多个省市开展Edge-Cloud试点工作.

近年来学术界出现了很多关于移动边缘计算[10]的研究工作,任务卸载问题是其中研究的重点内容.早期研究工作仅考虑单个边缘设备的任务卸载问题[11-12].文献[11]中多个终端用户采用无中心、非协作的博弈方式独立决策自身计算任务的执行位置,将计算任务卸载到边缘设备或者远端云.文献[12]利用半定松弛法和随机映射方法联合优化所有终端用户的卸载策略,将多个终端用户的任务卸载到一个边缘设备处执行.

然而,当终端用户数量较多时,单个边缘设备由于自身资源限制难以满足所有终端用户的服务需求,容易导致处理时延较高或者任务执行失败.因此,最新研究工作考虑多边缘设备协作共同执行计算任务.文献[13]利用匹配策略制定多个终端用户和多个边缘设备间的任务卸载策略.文献[14]利用Lyapunov优化算法确定每个终端用户产生的计算任务的执行位置.文献[15]研究边缘设备密集部署场景下的任务卸载问题.多边缘设备间通过联盟博弈理论,形成协作联盟共同执行终端用户的计算任务.文献[16]研究在多个雾节点间进行任务卸载,提出分布式交替方向乘子方法(alternating direction method of multipliers,ADMM),在给定功率约束条件下制定任务卸载策略,提升用户的体验质量(quality of experience,QoE).文献[17-18]通过分布式博弈方法实现边缘设备间任务卸载,目标是最小化任务整体执行时延.然而,上述研究工作仅考虑任务卸载问题,假设边缘设备中已缓存所有任务所需的相关服务.当任务卸载到边缘设备时,边缘设备仅需考虑计算资源的限制,若边缘设备具有足够的计算资源即可为任务提供服务.但是在实际情况中,边缘设备的存储资源有限,难以缓存所有服务,需要根据实际任务需求制定动态服务缓存策略.由此可知,任务卸载和服务缓存相互耦合,需要进行任务卸载和服务缓存联合优化研究.

文献[2]首次在多基站MEC场景中研究任务卸载和服务缓存联合优化问题,利用ε-greedy方法制定服务缓存策略,并基于Gibbs采样制定任务卸载策略.文献[19]中不考虑边缘设备的计算资源限制,利用图着色方法制定边缘设备的服务缓存策略,目标是最小化每个边缘设备的能耗开销.文献[20]提出一种双准则算法联合优化路由请求和服务缓存,目标是最小化卸载到远端云的流量.文献[21]提出常因子近似算法和启发式算法分别用于求解缓存服务放置和任务请求调度问题,旨在最大化边缘云的用户请求数量.文献[22]考虑单个终端用户与多个可连接边缘设备间的关联策略,提出基于本地搜索的迭代算法,以最小化系统开销为目标.但是上述研究工作仅考虑终端用户和边缘设备间的任务卸载和服务缓存联合优化问题,当边缘设备未缓存所需服务或者计算资源不足时,需要将任务卸载到远端云处执行,而不是将任务卸载到具有执行能力的边缘设备上协作执行,从而导致边缘设备的资源利用率低下.

文献[3]考虑可通信的边缘设备协作共同执行任务,目标是最小化所有任务的服务响应时延,提出基于Gibbs采样的迭代缓存更新(iterative caching update,ICE)算法用于制定服务缓存策略,同时提出一种启发式负载调度算法用于制定负载调度策略,通过ICE算法和启发式负载调度算法迭代执行,求解任务卸载和服务缓存联合优化问题.然而该研究工作假设终端用户的服务缓存需求已知,在实际情况中服务缓存需求未知,仅能获取到终端用户的情景信息,需要根据情景信息学习终端用户的服务缓存需求.目前已有工作研究情景信息与服务缓存需求之间的关系.文献[23-24]基于情景感知组合多臂赌博机(contextual combinatorial multi-armed bandit,CC-MAB)算法在线学习终端用户的情景信息与服务需求之间的关系,制定服务放置策略.但是该方法无法适用于本文研究的多边缘设备协作进行服务缓存的场景,原因在于多边缘设备协作进行服务缓存时,不仅需要考虑自身关联的终端用户的情景信息,还需要考虑候选协作的边缘设备所关联的终端用户的情景信息.

综上所述,本文针对服务缓存需求未知的真实场景,研究移动边缘计算中面向多边缘设备协作的任务卸载和服务缓存联合优化问题,提出一种任务卸载和服务缓存在线联合优化算法,目标是在满足任务执行时延限制的条件下,最小化任务整体执行时延.

2 系统模型和问题描述

本节首先进行场景分析,然后介绍系统模型,包括通信模型、服务缓存模型和任务卸载模型,最后对本文要解决的问题进行形式化描述.本文涉及的主要变量及相关描述如表1所示:

Table 1 Variable Notation Table表1 变量符号表

续表1

2.1 场景分析

如图1所示,假定移动边缘计算网络包含N个边缘设备,为M个终端用户提供服务.远端云存储资源充足,因此缓存所有服务.边缘设备缓存资源有限,只能选择部分服务进行缓存.多边缘设备协作执行终端用户的计算任务,即相互连通的多边缘设备间可以进行计算任务卸载.首先终端用户产生计算任务,将计算任务上传到自身关联的边缘设备处;然后边缘设备根据任务的服务缓存需求、自身可用计算资源等因素为接收的计算任务选择合适的卸载位置,可选的卸载位置包括边缘设备本地、协作的边缘设备和远端云;确定计算任务的卸载位置后,将计算任务传输到相应的位置并执行该计算任务.

Fig.1 Scene for joint optimization for multi-edge device collaboration图1 面向多边缘设备协作的联合优化场景

edgen表示第n个边缘设备,其中n∈N,N＝{1,2,…,N},每个边缘设备配置一个服务器.edgen可提供的最大计算量表示为,服务缓存容量表示为K n.UEm表示第m个终端用户,其中m∈M,M＝{1,2,…,M}.由于边缘设备密集部署,边缘设备的覆盖范围存在重叠区域,位于重叠区域内的终端用户选择信道条件最优的边缘设备进行关联.edgen关联的终端用户序号集合表示为M n,若UEm是edgen关联的终端用户,则m∈M n.所有边缘设备关联的终端用户并集为系统中所有的终端用户,即M＝∪n∈N M n.该场景可提供S种服务缓存,SCs表示第s种服务缓存,其中s∈S,S＝{1,2,…,S}.

将连续时间划分为T个分离的时隙,slott表示第t个时隙.在每个时隙中,终端用户的位置固定.在不同时隙间,终端用户的位置动态变化[13].在每个时隙开始时更新边缘设备的服务缓存策略.假设每个时隙中UEm产生一个计算任务I m＝(λm,γm,d m,s m),其中λm表示任务I m的输入数据大小,γm表示任务I m的计算需求量,d m表示任务I m的执行时延限制,s m表示任务I m的服务缓存需求为SCs m,其中s m∈S.

2.2 通信模型

本节介绍通信模型,包括终端用户与边缘设备间的通信模型、多边缘设备间的通信模型以及边缘设备与远端云间的通信模型.

2.2.1 终端用户与边缘设备间的通信模型

本文中边缘设备采用正交频分多址(orthogonal frequency division multiple access,OFDMA)的方法与终端用户进行通信,即边缘设备为每个关联的终端用户分配一个正交信道用于数据传输,因此不同传输信道间不存在干扰问题[17].依据香农公式可以得到UEm与edgen间的上行链路传输速率r mn:

其中,B mn＝B n/|M n|表示edgen分配给UEm的传输带宽,B n表示edgen的信道带宽,|M n|表示edgen关联的终端用户个数,关联的终端用户平均分配信道带宽.h mn表示UEm与edgen间的信道增益.本文假设单个时隙内终端用户不发生移动,因此h mn是一个定值.P m表示UEm的传输功率,σ2表示噪声功率.由此可以得到UEm将任务I m卸载到edgen的上行传输时延:

由于任务结果比输入数据小很多[19,25],且从边缘设备到终端用户的下行链路传输速率远大于终端用户到边缘设备的上行链路传输速率,因此终端用户与边缘设备间的通信模型仅考虑上行链路,忽略边缘设备执行任务后将任务结果传回终端用户的时延开销.

2.2.2 多边缘设备间的通信模型

多边缘设备间通过本地局域网(local area network,LAN)连接[17].edgen和edgey间的传输速率是定值,表示为R ny.当edgen将自身关联的UEm产生的任务I m卸载到edgey处时,edgen与edgey间的传输时延表示为

2.2.3 边缘设备与远端云间的通信模型

当终端用户产生的任务选择在远端云处执行时,UEm产生的任务I m将从其关联的边缘设备传输到远端云.边缘设备通过回程链路访问远端云,假定边缘设备卸载任务I m到远端云的传输时延为恒定值,表示为

2.3 服务缓存模型

边缘设备为终端用户提供服务时需要本地缓存相应服务,但是由于边缘设备的缓存资源有限,不能同时在本地缓存所有服务.在每个时隙开始时,边缘设备根据待服务的终端用户决定需要缓存哪些服务表示slott时所有边缘设备的服务缓存策略,其中表示edgen在slott时的服务缓存策略是一个二进制变量表示edgen在slott时缓存SCs;而表示edgen在slott时未缓存SCs.服务缓存不能违背边缘设备的缓存容量限制,因此每个edgen进行服务缓存时需满足的约束条件为

2.4 任务卸载模型

在每个时隙中每个终端用户产生的计算任务将卸载到自身能够关联的信道质量最好的边缘设备上.若终端用户关联的边缘设备资源不足或者未缓存所需服务,则该终端用户关联的边缘设备将计算任务卸载到其他协作的边缘设备或者远端云处执行.终端用户产生的计算任务可选的卸载位置包括自身关联的边缘设备、协作的边缘设备和远端云.表示slott时所有边缘设备的资源分配策略.其中表示slott时edgen分配给任务I m的计算量表示edgen处执行的任务集合,包括edgen关联的终端用户产生的任务和协作边缘设备卸载的任务.为了方便表示,下文提到时忽略表示时隙的变量t.由于edgen计算资源有限,因此为集合中所有任务分配计算资源时必须满足边缘设备的计算资源约束,即

下面将分别介绍终端用户产生的计算任务卸载到关联的边缘设备、协作的边缘设备和远端云处执行的任务卸载模型.

2.4.1 关联的边缘设备执行任务

若UEm产生的任务I m卸载到自身关联的edgen处执行,执行时延包括2部分:1)UEm上传数据到edgen所需的传输时延执行任务所需的计算时延.edgen处执行任务I m所需的计算时延表示为γm/f nm,其中f nm表示edgen分配给任务I m的计算量.因此UEm产生的任务I m在其关联的edgen处执行所需的执行时延为

2.4.2 协作的边缘设备执行任务

由于边缘设备的计算和存储资源有限,且边缘设备间存在负载不均衡的现象,多边缘设备协作共同执行任务,可以充分利用边缘设备资源,提高系统的资源利用率.edgen接收自身关联的UEm的卸载任务I m后,若选择将任务I m卸载到协作的edgey处执行,执行时延包括3部分:1)UEm上传数据到edgen所需的传输时延与edgey间传输数据所需的传输时延执行任务所需的计算时延.f ym表示edgey分配给任务I m的计算量,任务I m在edgey处执行的计算时延表示为γm/f ym.将edgen关联的UEm产生的任务I m卸载到协作的edgey处执行所需的执行时延为

2.4.3 远端云执行任务

由于远端云具有强大的计算能力,可以忽略远端云的计算时延.那么edgen将自身关联的UEm产生的任务I m卸载到远端云处执行所需的执行时延包括2部分:1)UEm上传数据到edgen的传输时延传输数据到远端云的传输时延.因此任务I m在远端云处执行所需的执行时延为

2.5 问题描述

为了方便表示,在表示单个时隙的目标时将表示时隙的变量t省略.UEm产生的任务I m可选的卸载位置包括:关联的edgen、edgen协作的边缘设备和远端云.每个计算任务仅能选择一个卸载位置,并且选择的卸载位置提前缓存了执行该任务所需的服务.UEm产生的任务I m的执行时延为

本文研究面向多边缘设备协作的任务卸载和服务缓存联合优化问题,目标是在任务执行时延限制条件下,最小化任务整体执行时延,问题建模为

约束条件式(10.1)表示每个边缘设备缓存的服务个数不能超过自身的缓存容量限制.约束条件式(10.2)表示终端用户产生的计算任务仅可在关联的边缘设备、协作的边缘设备和远端云中选择一个卸载位置.约束条件式(10.3)表示边缘设备为本地执行的计算任务分配的计算量为正数.约束条件式(10.4)表示边缘设备为本地执行的计算任务分配的资源总量必须满足自身的计算资源总量限制.约束条件式(10.5)表示edgen是否缓存SCs.约束条件式(10.6)表示edgen关联的UEm产生的任务I m是否卸载到Devicey处执行.

3 任务卸载和服务缓存在线联合优化算法

首先证明上述多边缘设备协作的任务卸载和服务缓存联合优化问题是NP难的,利用已知的NP难问题——广义分配问题(general assignment problem,GAP)[26]进行证明.GAP中假设有N个容器,M个物品,将物品m放入容器n中,获得相应收益.该优化问题的目标是为每个物品选择一个合适的容器放置,在容器成本的约束条件下最大化物品放置的整体收益.针对本文的问题进行参数映射和转换,GAP中的N个容器对应本文中的N个边缘设备和远端云,GAP中的M个物品对应本文中的M个终端用户产生的任务,本文的优化目标是为每个任务选择一个合适的卸载位置,在边缘设备的资源约束条件下最大化任务的整体执行收益,即最小化任务整体执行时延,因此原始问题P1为NP难问题,难以在多项式时间内获得最优的任务卸载和服务缓存策略.

上述面向多边缘设备协作的任务卸载和服务缓存联合优化问题是一个混合整数非线性优化问题.该问题中服务缓存策略C和任务卸载位置选择策略A为二进制变量,边缘设备上的资源分配策略F为连续变量.原始问题P1中服务缓存策略的约束条件式(10.1)(10.5)和任务卸载策略的约束条件式(10.2)(10.3)(10.4)(10.6)是彼此分开的.因此,为了降低该问题求解的计算复杂度,将原始问题P1解耦为2个子问题——服务缓存子问题和任务卸载子问题,通过求解2个子问题解决原始问题P1.针对这2个子问题,设计任务卸载和服务缓存在线联合优化(JOC)算法.针对服务缓存子问题,提出基于情景感知组合多臂赌博机的协作服务缓存(3CMAB)算法,在线学习边缘设备的服务缓存收益,进而制定服务缓存策略;针对任务卸载子问题,基于3CMAB算法获得的服务缓存策略确定任务卸载的可选空间,提出基于偏好的双边匹配算法,在边缘设备间进行负载重分配,实现多边缘设备间负载均衡,进一步依据任务卸载结果更新服务缓存收益,进而影响下一轮的服务缓存策略.下面将对提出的JOC算法进行详细介绍.

3.1 边缘设备的服务缓存策略

本节提出基于情景感知组合多臂赌博机的协作服务缓存(3CMAB)算法求解服务缓存子问题.每个边缘设备需要利用终端用户的情景信息判断其服务缓存需求,因此该子问题是一个“contextual”问题;边缘设备需要缓存多个服务,因此该子问题也是一个“combinatorial”问题.与此同时,不同边缘设备的负载各不相同,多个边缘设备需要协同提供服务,因此边缘设备在制定服务缓存策略时需要考虑候选协作的边缘设备所关联的终端用户的情景信息,因此该子问题还是一个“collaborative”问题.

根据负载情况将边缘设备分为2类:Source node和Sink node.Source node负载较重,仅能为本地关联的终端用户提供服务,不能处理的任务卸载到协作的边缘设备或者远端云处执行.Sink node负载较轻,除了为本地关联的终端用户提供服务外,同时可以接收候选协作的边缘设备卸载的任务.由此可知,Source node在制定服务缓存策略时,仅需考虑本地关联的终端用户的情景信息;而Sink node不仅需要考虑本地关联的终端用户的情景信息,同时还需要考虑候选协作的边缘设备所关联的终端用户的情景信息.

文献[23-24]均采用终端用户情景信息相似时其服务缓存需求也相似的[27-28]假设.本文基于这种假设提出3CMAB算法,在线学习每种情景信息下终端用户的服务缓存需求,在每个时隙开始时边缘设备根据终端用户的情景信息制定服务缓存策略,有效提高服务缓存命中率.

3.1.1 终端用户的情景信息

边缘设备在每个时隙开始时观察自身关联的终端用户的情景信息表示在slott时edgen关联的UEm的情景信息,其中X＝[0,1]D表示情景信息空间,D表示情景信息维度.在slott时edgen关联的终端用户的情景信息集合表示为若edgen为Sink node,则需要考虑候选协作的边缘设备所关联的终端用户的情景信息,Sink noden考虑的协作情景信息集合表示为

Fig.2 Illustration of context space and partitions图2 情景信息空间和分区示意图

在初始化阶段,将情景信息空间X＝[0,1]D划分为(h T)D个集合,每个集合是具有相同大小(1/h T)×…×(1/h T)的D维立方体空间.h T是一个输入数据,决定情景信息空间可划分的集合个数.每个集合作为一个整体,其情景信息为p,p∈P T.P T表示划分后的整体情景信息空间.情景信息空间及分区如图2所示.每个边缘设备均需要记录P T中所有情景信息相应的数据值表示slott时edgen关联的UEm的情景信息对应的分区情景信息,即表示slott时edgen关联的终端用户对应的分区情景信息集合表示edgen记录的候选协作的edgey关联的UEw的情景信息对应的分区情景信息.

3.1.2 服务缓存问题建模

UEm产生的任务I m的执行时延限制表示为d m,执行任务所获收益值与d m相关.执行任务时延越低,与d m间的差值越大,则执行该任务的收益值越大.边缘设备只有缓存任务I m所需的SCs m时,才能执行该任务,产生收益值.因此,针对SCs执行任务I m产生的收益值定义为

最小化系统中任务整体执行时延等价于最大化系统中任务整体收益值.任务整体收益值为执行系统中所有终端用户产生的任务所获收益值总和,因此最大化系统中任务整体收益值表示为3CMAB算法是一个探索与利用权衡的过程,为了获取情景信息对应的不同服务缓存的预估收益值,需要进行多次探索.探索阶段针对每种情景信息选择之前从未探索或者未探索完全的服务进行缓存,任务执行完成后得到缓存该服务相应的收益值,根据该收益值更新预估收益值,用于制定下一轮服务缓存策略.利用阶段则为每种情景信息选择预估收益值最高的服务进行缓存.为了得到每种情景信息对每种服务缓存的预估收益值,需要记录相关数据,因此会耗费一定的存储空间.当学习过程完成后,边缘设备即可根据学习获得的情景信息与服务缓存之间的模型,根据终端用户的情景信息选择预估收益值最高的服务进行缓存,快速制定服务缓存策略.

3CMAB算法需要优化系统长期收益,即最大化系统中长期任务整体收益值,具体表示为

3.1.3 3CMAB算法

本节详细介绍3CMAB算法,包括探索和利用2个阶段,算法流程如图3所示.首先,获取每个边缘设备本地关联的终端用户的情景信息集合,然后预判边缘设备类型,并依据类型设计不同的探索和利用过程.探索阶段中,每个边缘设备根据未探索完全的服务缓存个数和服务缓存容量限制之间的关系,选择不同的服务缓存策略进行探索.若探索完全,即针对每种情景信息学习到最优的服务缓存后,则进入利用阶段.利用阶段可依据终端用户的情景信息选择最优的服务进行缓存.

其中,M n表示edgen关联的终端用户序号集合,表示edgen针对情景信息p未探索完全的服务缓存序号集合.判断是否为空,从而确定边缘设备运行阶段.若则边缘设备进入探索阶段;若,则边缘设备进入利用阶段.

Source node和Sink node两类边缘设备需要考虑不同的情景信息,缓存不同服务所获得的收益值存在差异,进而导致探索与利用策略有所不同.下面首先介绍如何判断边缘设备类型,然后分别介绍2类边缘设备的探索与利用过程.

2)判断边缘设备类型

当边缘设备进行服务缓存时,首先边缘设备需要根据自身关联的终端用户的情景信息推测任务计算需求量以及任务执行时延限制,进而对边缘设备类型进行预判断.

记录到slott为止,edgen接收的情景信息为p、服务缓存需求为SCs的任务请求次数在slott时,若edgen接收到情景信息为p、服务缓存需求为SCs的任务请求,则更新

Fig.3 3CMAB algorithm flow chart图3 3CMAB算法流程图

在当前时隙中,edgen关联的UEm产生的任务I m的计算需求量为γm,执行时延限制为d m.利用与任务I m的计算需求量γm计算到slott为止,edgen接收的情景信息为p、服务缓存需求为SCs的平均任务计算需求量为

在每个slott开始时,edgen观察关联的终端用户的情景信息根 据记录的平均任务计算需求量和平均任务执行时延限制计算关联的终端用户的总任务计算需求量即任务负载为和总任务执行时延限制

edgen根据自身的总任务计算需求量和计算能力得到所有任务均在本地执行的平均执行时延:

edgen根据自身的总任务执行时延限制和任务数量,得到edgen执行所有任务的平均执行时延限制:

Source node负载较重,仅能为本地关联的终端用户提供服务,因此在制定服务缓存策略时仅需要考虑本地关联的终端用户的情景信息.而Sink node负载较轻,除了为本地关联的终端用户提供服务外,还需要执行候选协作的边缘设备卸载的任务,因此在制定服务缓存策略时除了考虑本地关联的终端用户的情景信息,还需要考虑候选协作的边缘设备关联的终端用户的情景信息.

3)Source node探索与利用过程

Source noden依据式(11)计算执行自身关联的UEm产生的任务I m的本地收益值r m.定义r m与后续Sink node执行候选协作的边缘设备卸载的任务所获得的协作收益值进行区分,在4)中将对进行详细介绍.

若Source noden未探索完全的服务缓存集合不为空,则进入探索阶段.在探索阶段,Source noden根据未探索完全的服务缓存个数和自身服务缓存容量限制K n之间的关系选择不同的服务缓存策略.若则Source noden从中随机选择K n个服务进行缓存;若则Source noden首先选择中所有服务进行缓存,然后选择个总预估收益值最高的服务进行缓存:

若Source noden未探索完全的服务缓存集合为空,则进入利用阶段.在利用阶段,Source noden根据式(25)选择总预估收益值最高的K n个服务进行缓存:

4)Sink node探索与利用过程

Sink node的探索与利用过程和Source node相同,但由于Sink node除了执行本地关联的终端用户产生的任务外,还需要执行候选协作的边缘设备卸载的任务,因此Sink node在制定服务缓存策略时需要考虑候选协作的边缘设备的服务缓存需求.Sink node除了考虑本地关联的终端用户的情景信息外,还需要考虑候选协作的边缘设备关联的终端用户的情景信息,该部分情景信息与Sink node自身可接收的任务量和对候选协作的边缘设备的偏好值相关.

Sink noden自身关联的终端用户的总任务计算需求量为表示Sink noden能够提供的总任务计算需求量.因此Sink noden可接收的候选协作的边缘设备卸载的总任务计算需求量为两者的差值,表示为

计算Sink noden针对候选协作的edgey中每种情景信息p的偏好值.该偏好值与edgey和Sink noden之间的历史协作次数,以及候选协作的边缘设备edgey可选择的Sink node个数相关表示edgey候选协作的Sink node序号集合表示到slott为止,Sink noden执行edgey中情景信息为p的任务次数表示到slott为止,Sink noden执行edgey中情景信息为p、服务缓存需求为SCs的任务次数.每执行一次,则根据

Sink noden与edgey针对edgey中情景信息p的历史协作次数越多,edgey可选Sink node数量越少,则Sink noden针对edgey中情景信息p的偏好值越高.

其中,Nn表示Sink noden候选协作的边缘设备序号集合.

根据式(28)选择偏好值最高的情景信息,将选择的情景信息添加到Sink noden的协作情景信息集合中.计算中所有情景信息对应的终端用户的总任务计算需求量是否达到Sink noden当前可接收的总任务计算需求量,若达到则终止;若未达到则选择偏好值次高的情景信息,重复上述过程直到终止,得到Sink noden的协作情景信息集合

Sink noden执行任务产生的收益值包括r m和两部分,r m表示Sink noden执行自身关联的UEm产生的任务I m所获得的本地收益值表示Sink noden处执行候选协作edgey关联的UEw产生的任务I w所获得的协作收益值.根据式(11)计算r m和

Sink node的探索与利用过程和Source node相同.若Sink noden未探索完全的服务缓存集合不为空,则进入探索阶段.在探索阶段,Sink noden根据未探索完全的服务缓存个数和自身服务缓存容量限制K n之间的关系,选择不同的服务缓存策略.若,则Sink noden从未探索完全的服务缓存集合中随机选择K n个服务进行缓存;若则Sink noden先缓存所有未探索完全的服务,然后选择总预估收益值最高的个服务进行缓存:

若Sink noden未探索完全的服务缓存集合为空,则进入利用阶段.在利用阶段,Sink noden选择总预估收益值最高的K n个服务进行缓存:

5)3CMAB算法流程

首先每个edgen获取自身关联的终端用户的情景信息集合.然后分别依据式(19)和式(20)计算edgen中所有任务均在本地执行的平均执行时延和平均执行时延限制,根据之间的大小关系预判断边缘设备类型.然后根据式(15)计算edgen针对待执行任务未探索完全的服务缓存集合,则edgen进入探索阶段;若,则edgen进入利用阶段.边缘设备类型不同时,总预估收益值的计算公式不同.Source node和Sink node分别根据式(23)和式(30)计算总预估收益值.探索阶段中,edgen根据未探索完全的服务缓存个数与自身服务缓存容量限制K n之间的关系,选择不同的服务缓存策略.当时,edgen从未探索完全的服务缓存集合中随机选择K n个服务进行缓存;当K n时,edgen先将所有未探索完全的服务进行缓存,然后选择总预估收益值最高的个服务进行缓存.根据边缘设备类型,Source node和Sink node分别根据式(24)和式(31)选择总预估收益值最高的len个服务进行缓存.利用阶段中,根据边缘设备类型,Source node和Sink node分别根据式(25)和式(32)选择K n个总预估收益值最高的服务进行缓存.3CMAB算法伪代码如算法1所示.

算法1.3CMAB算法.

输入:终端用户序号集合Mn、终端用户情景信息、边缘设备最大计算量

3.2 多边缘设备间的任务卸载策略

在给定服务缓存策略的基础上制定多边缘设备间的任务卸载策略,目标是实现边缘设备间负载均衡.本节仅考虑单个时隙内的任务卸载,因此将表示时隙的变量t省略.原始问题P1中的资源分配策略F和任务卸载位置选择策略A的约束条件是彼此分开的,因此可以将任务卸载问题分解为资源分配和任务卸载位置选择2个子问题,分别进行求解.

3.2.1 边缘设备的资源分配策略

边缘设备进行资源分配时,假定边缘设备上的服务缓存策略C和任务卸载位置选择策略A确定.此时终端用户上传数据到关联的边缘设备的传输时延、边缘设备间的传输时延、边缘设备到远端云的传输时延均可确定,因此可以将原始优化问题P1转化为

此外,由于边缘设备的服务缓存策略c y,sm和任务卸载位置选择策略a ny,Im均为定值,可以确定每个边缘设备本地执行任务集合.因此,可以将上述优化问题进一步转化为子问题P3进行求解[13,29]:

值得注意的是约束条件式(34.2)是凸的.定义优化目标函数为

求解优化目标函数D(F)′对f nm的二阶导数,得到:

由式(36)(37)可以得出,子问题P3的Hessian矩阵是对角矩阵,具有严格的正值,即该Hession矩阵为一个正定矩阵,因此子问题P3是一个凸优化问题,可以通过对偶方法进行求解.令υ＝{υn}n∈N表示与约束条件式(34.2)相关联的对偶量.拉格朗日函数表示为

定义拉格朗日对偶函数GP3(υ)为

GP3(υ)表示在原始F上求解最小值.将式(39)进一步转化为在υ上求解最大值的对偶函数,具体表示为

因为子问题P3是凸的,因此可以通过对拉格朗日函数LP3(F,υ)求解一阶导数,令其一阶导数为0来获得最优分配的计算量f∗nm,即:

将式(41)代入式(39)中.由于拉格朗日对偶函数GP3(υ)也是凸函数,求解GP3(υ)的一阶导数,令其等于0即可获得最优对偶量υ∗n,即:

将式(42)代入式(41)中,即可得到edgen为本地执行任务集合Iexen中的每个待执行的任务I m分配的最优计算量:

3.2.2 任务卸载位置选择策略

根据3.2.1节所述方法可以获得边缘设备的资源分配策略F,在此基础上制定任务卸载位置选择策略A,确定所有任务的卸载位置.由于终端用户上传数据到自身关联的边缘设备所需的传输时延是确定的,因此可以将原始问题P1转化为子问题P4:

其中,

约束式(44.2)表示UEm产生的任务I m仅可在关联的边缘设备、协作的边缘设备和远端云中选择一个卸载位置.

edgen为自身关联的UEm产生的任务I m选择合适的卸载位置.若edgen缓存任务I m所需的SCs m,则该任务为本地缓存命中任务,添加到edgen的本地缓存命中任务集合中.剩余任务即本地未缓存命中的任务添加到edgen的本地未缓存命中任务集合中任务可以卸载到协作的Sink node或者远端云处执行.

Source node负载较重,仅能执行本地关联的终端用户卸载的计算任务,当计算资源不足时需要将中的部分任务进行卸载.Sink node负载较轻,除了执行中的所有本地缓存命中的任务,还具有多余的计算资源可以接收候选协作的边缘设备卸载的任务.Source node和Sink node均可将本地未缓存命中任务集合中的任务卸载到缓存有相应服务的Sink node或者远端云处.

由此论述可以看出,无论是Source node还是Sink node均需要进行任务卸载,而只有Sink node可以接收候选协作的边缘设备卸载的任务.

下面针对Source node和Sink node两种类型的边缘设备,分别介绍如何根据本地服务缓存策略、计算能力以及负载情况确定各自的本地执行任务集合和本地卸载任务集合;然后介绍基于偏好的双边匹配算法,目的是建立待卸载任务与Sink node之间的匹配关系,为本地卸载任务集合中的每个待卸载任务选择合适的卸载位置,实现边缘设备间负载均衡.

1)Source node确定本地执行任务集合和本地卸载任务集合

Source noden从本地缓存命中任务集合中选择部分任务在本地执行中剩余任务和中的任务则需要进行卸载,将其添加到卸载任务集合中.

若任务I m卸载到候选协作的Sink nodey处执行,假定Sink nodey中的所有任务平分计算资源,则Sink nodey中每个任务能够获得的计算量为表示Sink nodey待执行的任务个数.任务I m卸载到Sink nodey处执行所需的卸载预估执行时延包括3部分:UEm将任务I m卸载到自身关联的Source noden所需的传输时延、任务I m从自身关联的Source noden卸载到Sink nodey处的传输时延和任务I m在Sink nodey处执行所需的计算时延,具体表示为

计算任务I m在所有候选协作的Sink node处执行所需的最低卸载预估执行时延表示为

由于远端云的计算能力较强,可以忽略远端云的计算时延.任务I m卸载到远端云处执行所需的卸载预估执行时延包括2部分:UEm将任务I m卸载到自身关联的Source noden所需的传输时延、任务I m从自身关联的Source noden处卸载到远端云所需的传输时延,即.任务I m在候选协作的Sink node和远端云处执行所需的最低卸载预估执行时延表示为

2)Sink node确定本地执行任务集合和本地卸载任务集合

由于Sink node计算资源充足,所有本地缓存命中任务集合中的任务均在本地执行,本地未缓存命中的任务卸载到候选协作的Sink node或远端云处执行.本地卸载任务集合为.此外Sink node还需要执行接收的其他候选协作边缘设备卸载的任务,因此Sink noden本地执行任务集合包括本地缓存命中任务集合和接收的卸载任务集合

3)基于偏好的双边匹配算法

采用基于偏好的双边匹配算法为所有边缘设备待卸载的任务(即中的任务)选择合适的卸载位置.每个待卸载任务对不同卸载位置(候选协作的Sink node和远端云)存在偏好,偏好值与卸载位置的卸载预估执行时延相关,卸载预估执行时延越低,则偏好值越大.

UEm关联的边缘设备确定,此时UEm将任务I m卸载到自身关联的edgen所需的传输时延即可确定,因此在计算偏好值考虑卸载预估执行时延时,不考虑部分.

edgen中每个待卸载任务I m对每个候选协作的Sink nodey的偏好值表示为

edgen中每个待卸载任务I m卸载到远端云的偏好值表示为

每个edgen优先向偏好值最优的卸载位置发送卸载请求.若请求的卸载位置是远端云,则远端云直接接收该卸载请求,即a n0,Im＝1.若请求的卸载位置为Sink node,则需要等待Sink node回复.若请求的Sink node接收该卸载请求,则可以确定该任务的卸载位置;若Sink node拒绝该卸载请求,则在下一轮迭代中向偏好值次优的卸载位置发送卸载请求.

接下来介绍Sink nodey如何判断是否接收卸载请求表示Sink nodey接收到的卸载请求任务集合表示Sink nodey接收的卸载任务集合,表示Sink nodey的本地执行任务集合.在每轮迭代中,每个Sink nodey可能接收到多个任务的卸载请求,假定接收所有卸载请求即,同时根据更新值.根据式(43)得到Sink nodey分配给中的每个任务的计算量中本地关联的终端用户产生的任务根据式(6)计算本地执行任务所需的本地预估执行时延中接收的协作边缘设备的卸载任务根据式(7)计算卸载到Sink nodey处执行所需的卸载预估执行时延.判断中所有任务是否均可满足执行时延限制.若均可满足执行时延限制,则Sink nodey接收所有卸载请求,否则将依据下面步骤拒绝部分卸载请求.

计算Sink nodey接收中每个卸载任务的接收预估收益值,即在Sink nodey处执行该任务所需的卸载预估执行时延与该任务在次优执行位置所需的卸载预估执行时延之间的差值,拒绝中接收预估收益值最低的卸载任务,将该任务从中删除,同时更新值.重复上述过程,直到能够满足中所有任务的执行时延限制,得到最终接收的卸载任务集合和本地执行任务集合

上述基于偏好的双边匹配算法能够依据边缘设备的任务需求、资源状态和负载情况合理卸载计算任务,实现边缘设备间负载均衡.由于仅Sink node可以接收卸载任务,待卸载任务可匹配的卸载位置无需考虑负载较重的Source node,因此有效降低了任务卸载的匹配空间,进而降低计算复杂度.上述算法流程如算法2所示.

算法2.多边缘设备间的任务卸载算法.

3.3 JOC算法复杂度分析

3CMAB算法在线学习终端用户情景信息对边缘设备的服务缓存收益的影响,基于学习获得的模型,直接通过公式计算即可得出服务缓存策略.因此进行JOC算法复杂度分析时仅考虑多边缘设备间的任务卸载策略的复杂度.多边缘设备间的任务卸载策略是一种分布式策略,因此从单个边缘设备的角度进行算法复杂度分析.

4 实验与结果

本节给出仿真结果用于评估所提任务卸载和服务缓存在线联合优化(JOC)算法的性能.

4.1 实验设置

移动边缘计算场景中部署3个边缘设备为终端用户提供服务.每个边缘设备的带宽为20 MHz.在每个边缘设备覆盖区域内随机部署终端用户,所有关联的终端用户平均分配带宽.每个edgen的最大计算量为.每个UEm的传输功率为,噪声功率为σ2＝－100 dBm,路径传输损耗模型为Los＝32.5＋20 lgZ＋20 lgX,其中Z表示载波频率,X表示终端用户与边缘设备之间的距离.终端用户产生的任务的输入数据大小λm区间为[0.3,0.45]Mb/task,任务的计算需求量γm区间为[0.2,0.5]GHz/task.实验的主要参数如表2所示:

Table 2 The Main Parameters Setting表2 主要参数设置

4.2 对比算法及性能指标

1)Cloud.假设边缘设备不缓存任何服务,所有任务均卸载到远端云处执行.

2)Service Caching Randomly(Random).每个边缘设备随机选择服务进行缓存,边缘设备间不进行任务卸载.

3)Non-Cooperative(Non_Co).每个边缘设备根据本地关联的终端用户的情景信息学习服务缓存策略,边缘设备间不进行任务卸载.

4)ICE.利用文献[3]中所提的服务缓存策略,每次迭代时依据收益值以一定概率更新服务缓存策略,直到达到迭代终止条件.利用本文所提任务卸载策略实现边缘设备间协作.

5)JOC.本文提出的算法,利用3CMAB算法制定服务缓存策略,利用基于偏好的双边匹配算法确定边缘设备间的任务卸载策略,实现边缘设备间协作.

性能指标有:任务整体执行时延、任务平均执行时延、边缘设备的负载分配情况以及边缘设备的服务缓存命中率.边缘设备的服务缓存命中率是指对于边缘设备能够执行的任务,自身缓存的服务命中的概率.每个实验重复100次,计算100组实验结果的平均值使得实验结果更加准确.

4.3 实验结果

Fig.4 The effect ofβon learning rate图4 β对学习速率的影响

2)拓扑结构.任务卸载和服务缓存均与网络拓扑结构高度相关,下面通过实验验证网络拓扑结构对算法性能的影响.分别针对3个边缘设备的2种拓扑结构、4个边缘设备的3种拓扑结构以及5个边缘设备的3种拓扑结构进行实验,网络拓扑结构如图5所示,其中每个边缘设备旁的数字表示可连接的边缘设备数量.

实验结果如图6所示.随着边缘设备数量增加,可以服务的终端用户数量也随之增加,任务整体执行时延也进一步增加.当边缘设备数量固定时,网络拓扑结构对算法性能有明显影响.不同网络拓扑结构下每个边缘设备可连接的边缘设备数量是不同的.当可连接的边缘设备数量增加时,任务整体执行时延降低.相比于最简单的链式拓扑结构,环形和全连接拓扑结构下的任务整体执行时延分别降低了5.39%到12.38%.原因在于随着可连接的边缘设备数量增加,负载较重的边缘设备可以选择的任务卸载位置变多,使得边缘设备间负载更加均衡,从而有效降低了任务整体执行时延.

Fig.5 Topological structures for different numbers of edge devices图5 不同边缘设备数量的拓扑结构

Fig.6 Effect of topological structure on JOC algorithm performance图6 拓扑结构对JOC算法性能的影响

3)任务整体执行时延.下面对5种算法的整体执行时延性能进行比较.结果如图7所示,算法性能JOC＞ICE＞Non_Co＞Random＞Cloud.

Fig.7 Comparison of different algorithms on overall execution delay of tasks图7 不同算法的任务整体执行时延对比图

Cloud算法将所有任务部署到远端云处执行,由于传输时延较长,导致实验性能最差.Random算法和Non_Co算法不考虑边缘设备间协作,即边缘设备间不能进行任务卸载,边缘设备只能将本地无法完成的任务卸载到远端云处执行,因此性能相对较差.与Random算法相比,Non_Co算法能够根据本地情景信息进行服务缓存,有效提高了服务缓存命中率,因此Non_Co算法性能优于Random算法.

ICE算法和JOC算法均考虑边缘设备间协作,通过边缘设备间任务卸载实现负载均衡.与ICE算法相比,JOC算法的任务整体执行时延降低了5.4%.由于终端用户的服务需求与其情景信息相关联,具有相似情景信息的用户会请求相似的服务,因此相对于未考虑用户情景信息的ICE算法,JOC算法中基于用户情景信息的服务缓存策略可以提高缓存命中率,从而能够将更多的计算任务部署在边缘设备上执行,有效降低了任务整体执行时延.此外,ICE算法制定服务缓存策略时,需要根据当前轮次的服务缓存收益值与之前轮次的服务缓存收益值之间的差值,得到后续的缓存更新概率,需要进行多轮迭代后才可以获得最终的服务缓存策略,运行该算法需要1.958 s.而JOC算法在学习完成后,利用学习到的模型可直接计算出服务缓存策略,运行该算法仅需0.001 95 s.由此可知,JOC算法可以显著降低计算开销并且实现实时动态缓存,而ICE算法的计算复杂度较高且缓存相对滞后.

4)服务缓存容量.下面实验验证边缘设备的服务缓存容量对实验性能的影响.如图8所示,Cloud算法中所有任务均在远端云处执行,因此边缘设备服务缓存容量变化对该算法的任务整体执行时延没有影响.其他4种算法均存在部分任务在边缘设备处执行的情况,因此服务缓存容量对这些算法的任务整体执行时延产生明显影响.当边缘设备的服务缓存容量增加时,终端用户所需的服务将更有可能缓存在边缘设备中,因此边缘设备可以为更多的终端用户提供服务,使得卸载到远端云的任务数量减少,从而使得任务整体执行时延呈现下降的趋势.Random算法随机选择服务进行缓存,随着缓存容量增加,服务缓存命中增多,因此其任务整体执行时延呈现单调下降趋势,但由于随机缓存命中率不高,Random算法性能低于其他3种算法.与Random算法相比,虽然Non_Co,ICE和JOC这3种算法的服务缓存命中率有所提高,但是当服务缓存容量达到一个临界值之后,边缘设备受自身计算资源限制,无法执行更多任务,因此服务缓存容量继续增加并不会使得任务整体执行时延持续下降,最终任务整体执行时延保持不变.

Fig.8 Impact of edge devices service caching capacity on overall execution delay of tasks图8 边缘设备的服务缓存容量对任务整体执行时延的影响

ICE算法和JOC算法中边缘设备间可以进行任务卸载实现负载均衡,因此任务整体执行时延较低.当服务缓存容量较低时,由于JOC算法的服务缓存策略优于ICE算法中的服务缓存策略,因此JOC算法的整体性能优于ICE算法.当服务缓存容量增加到5时,2种算法的服务缓存效果接近相同,此时2种算法的性能趋于一致.

5)终端用户数量.下面通过实验验证终端用户数量对实验性能的影响.终端用户数量增加,任务整体执行时延随之增加.为了验证终端用户数量对实验性能的影响,本次实验采用任务平均执行时延这一指标,任务平均执行时延为任务整体执行时延除以执行的任务个数.如图9所示,Cloud算法中所有任务均在远端云处执行,终端用户数量增加会使得终端用户间传输带宽竞争加剧,进而导致任务平均执行时延增加.对于其他4种算法,随着终端用户数量增加,任务平均执行时延增加.这是因为边缘设备资源有限,随着任务数量增加,每个任务可以获得的资源量逐渐减少,因此导致任务平均执行时延增加.当终端用户数量超过边缘设备的服务容量时,边缘设备卸载到远端云处执行的任务增加,进而导致任务平均执行时延进一步增加.JOC算法与ICE算法可在边缘设备间进行任务卸载,有效提高边缘设备的资源利用率,使得任务平均执行时延相对较低,因此这2种算法的性能优于Non_Co算法.

当终端用户数量在5～25时,与ICE算法相比,JOC算法能够获得更高的服务缓存命中率,边缘设备能够执行更多的任务,因此性能优于ICE算法.然而当终端用户数量超过25后,边缘设备受到其自身计算资源的限制,JOC算法和ICE算法能够执行的任务数量趋于一致,因此2种算法的性能基本持平.

Fig.9 Impact of the number of end users on average execution delay of tasks图9 终端用户数量对任务平均执行时延的影响

6)服务缓存命中率.下面通过实验展示不同算法的服务缓存命中率.Cloud算法中所有任务均在远端云处执行,因此本次对比实验不考虑Cloud算法,仅对其他4种算法进行对比.如图10所示,JOC算法的服务缓存命中率最高.Non_Co算法根据本地的情景信息学习服务缓存策略,其服务缓存命中率仅次于JOC算法.ICE算法的服务缓存命中率仅优于Random算法.

Fig.10 Comparison of different algorithms on service caching hitting ratio图10 不同算法的服务缓存命中率对比图

7)负载均衡性能.下面通过实验验证JOC算法可以在边缘设备间实现负载均衡.在边缘设备负载不均衡的情况下进行实验,观察每个边缘设备的执行任务数量.如图11所示,Cloud算法所有任务均在远端云处执行,因此所有边缘设备的执行任务数量均为0.Random算法和Non_Co算法未考虑边缘设备间协作,因此这2种算法的边缘设备负载相对不均衡,边缘设备执行的任务数量与自身服务缓存命中的任务数量相关.而ICE算法与JOC算法允许边缘设备间进行任务卸载,因此边缘设备间负载相对均衡.由于JOC算法的服务缓存策略优于ICE算法的服务缓存策略,因此相比于ICE算法,JOC算法在边缘设备处执行的任务数量更多.

根据图11中边缘设备执行的任务数量计算不同算法将任务卸载到远端云处执行的比例,如图12所示.Random算法和Non_Co算法将任务卸载到远端云处执行的比例相对较高.与Random算法相比,Non_Co算法的服务缓存命中率更高,因此任务卸载到远端云处执行的比例低于Random算法.ICE算法和JOC算法允许边缘设备间进行任务卸载,因此边缘设备能够执行更多的任务,任务卸载到远端云处执行的比例相对较低.相比于ICE算法,JOC算法的服务缓存命中率更高,因此JOC算法将任务卸载到远端云处执行的比例更低.

Fig.11 Load balancing between edge devices图11 边缘设备间的负载均衡情况

Fig.12 The percentage of offloading task to cloud for execution图12 任务卸载到远端云处的执行率

5 总 结

本文研究面向多边缘设备协作的任务卸载和服务缓存联合优化问题,将该问题形式化描述为混合整数非线性优化问题.为了解决该问题,本文提出一种任务卸载和服务缓存在线联合优化(JOC)算法,将原始问题解耦为服务缓存和任务卸载2个子问题.针对服务缓存子问题,提出基于情景感知组合多臂赌博机的协作服务缓存算法,用于制定边缘设备的服务缓存策略;针对任务卸载子问题,设计基于偏好的双边匹配算法,确定边缘设备间的任务卸载策略.仿真实验表明:与现有算法相比,JOC算法可以获得更优的任务执行性能,同时实现边缘设备间负载均衡.