近年来,随着无线网络技术的飞速发展,移动终端设备数量剧增.数百亿的移动终端设备导致数据爆炸性增长,催生出许多计算密集型和时延敏感型的新兴应用,如人脸识别、虚拟/增强现实等.这些新兴应用具有低时延、高带宽等服务需求.传统云计算将移动终端用户产生的数据传输到远端云服务器中进行集中处理,由于传输距离较长、回程链路受限等原因导致响应时延过高(数十至百毫秒级[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 面向多边缘设备协作的联合优化场景
edge n表示第n个边缘设备,其中n∈N,N＝{1,2,…,N},每个边缘设备配置一个服务器.edge n可提供的最大计算量表示为
,服务缓存容量表示为K n.UE m表示第m个终端用户,其中m∈M,M＝{1,2,…,M}.由于边缘设备密集部署,边缘设备的覆盖范围存在重叠区域,位于重叠区域内的终端用户选择信道条件最优的边缘设备进行关联.edge n关联的终端用户序号集合表示为M n,若UE m是edge n关联的终端用户,则m∈M n.所有边缘设备关联的终端用户并集为系统中所有的终端用户,即M＝∪n∈N M n.该场景可提供S种服务缓存,SC s表示第s种服务缓存,其中s∈S,S＝{1,2,…,S}.
将连续时间划分为T个分离的时隙,slot t表示第t个时隙.在每个时隙中,终端用户的位置固定.在不同时隙间,终端用户的位置动态变化[13].在每个时隙开始时更新边缘设备的服务缓存策略.假设每个时隙中UE m产生一个计算任务I m＝(λm,γm,d m,s m),其中λm表示任务I m的输入数据大小,γm表示任务I m的计算需求量,d m表示任务I m的执行时延限制,s m表示任务I m的服务缓存需求为SC s m,其中s m∈S.
2.2 通信模型
本节介绍通信模型,包括终端用户与边缘设备间的通信模型、多边缘设备间的通信模型以及边缘设备与远端云间的通信模型.
2.2.1 终端用户与边缘设备间的通信模型
本文中边缘设备采用正交频分多址(orthogonal frequency division multiple access,OFDMA)的方法与终端用户进行通信,即边缘设备为每个关联的终端用户分配一个正交信道用于数据传输,因此不同传输信道间不存在干扰问题[17].依据香农公式可以得到UE m与edge n间的上行链路传输速率r mn:
其中,B mn＝B n/|M n|表示edge n分配给UE m的传输带宽,B n表示edge n的信道带宽,|M n|表示edge n关联的终端用户个数,关联的终端用户平均分配信道带宽.h mn表示UE m与edge n间的信道增益.本文假设单个时隙内终端用户不发生移动,因此h mn是一个定值.P m表示UE m的传输功率,σ2表示噪声功率.由此可以得到UE m将任务I m卸载到edge n的上行传输时延:
由于任务结果比输入数据小很多[19,25],且从边缘设备到终端用户的下行链路传输速率远大于终端用户到边缘设备的上行链路传输速率,因此终端用户与边缘设备间的通信模型仅考虑上行链路,忽略边缘设备执行任务后将任务结果传回终端用户的时延开销.
2.2.2 多边缘设备间的通信模型
多边缘设备间通过本地局域网(local area network,LAN)连接[17].edge n和edge y间的传输速率是定值,表示为R ny.当edge n将自身关联的UE m产生的任务I m卸载到edge y处时,edge n与edge y间的传输时延表示为
2.2.3 边缘设备与远端云间的通信模型
当终端用户产生的任务选择在远端云处执行时,UE m产生的任务I m将从其关联的边缘设备传输到远端云.边缘设备通过回程链路访问远端云,假定边缘设备卸载任务I m到远端云的传输时延为恒定值,表示为
2.3 服务缓存模型
边缘设备为终端用户提供服务时需要本地缓存相应服务,但是由于边缘设备的缓存资源有限,不能同时在本地缓存所有服务.在每个时隙开始时,边缘设备根据待服务的终端用户决定需要缓存哪些服务
表示slot t时所有边缘设备的服务缓存策略,其中
表示edge n在slot t时的服务缓存策略
是一个二进制变量
表示edge n在slot t时缓存SC s;而
表示edge n在slot t时未缓存SC s.服务缓存不能违背边缘设备的缓存容量限制,因此每个edge n进行服务缓存时需满足的约束条件为
2.4 任务卸载模型
在每个时隙中每个终端用户产生的计算任务将卸载到自身能够关联的信道质量最好的边缘设备上.若终端用户关联的边缘设备资源不足或者未缓存所需服务,则该终端用户关联的边缘设备将计算任务卸载到其他协作的边缘设备或者远端云处执行.终端用户产生的计算任务可选的卸载位置包括自身关联的边缘设备、协作的边缘设备和远端云.
表示slot t时所有边缘设备的资源分配策略.其中
表示slot t时edge n分配给任务I m的计算量
表示edge n处执行的任务集合,包括edge n关联的终端用户产生的任务和协作边缘设备卸载的任务.为了方便表示,下文提到
时忽略表示时隙的变量t.由于edge n计算资源有限,因此为集合
中所有任务分配计算资源时必须满足边缘设备的计算资源约束,即
表示slot t时任务卸载位置选择策略.Device y表示任务卸载位置,包括边缘设备和远端云,远端云使用Device 0表示
是一个二进制变量.
表示在slot t时edge n关联的UE m产生的任务I m不在Device y处执行.而
表示在slot t时edge n关联的UE m产生的任务I m卸载到Device y处执行,其中y＝0时表示任务I m在远端云处执行;y＝n时表示任务I m在关联的edge n本地执行;y∈N\{n}表示任务I m在非关联的边缘设备处执行.若edge n和Device y间不可通信,即表示edge n与Device y不可协作,则
任务I m仅可在关联的边缘设备、协作的边缘设备和远端云中选择一个卸载位置,因此需要满足的约束条件为
下面将分别介绍终端用户产生的计算任务卸载到关联的边缘设备、协作的边缘设备和远端云处执行的任务卸载模型.
2.4.1 关联的边缘设备执行任务
若UE m产生的任务I m卸载到自身关联的edge n处执行,执行时延包括2部分:1)UE m上传数据到edge n所需的传输时延
执行任务所需的计算时延.edge n处执行任务I m所需的计算时延表示为γm/f nm,其中f nm表示edge n分配给任务I m的计算量.因此UE m产生的任务I m在其关联的edge n处执行所需的执行时延为
2.4.2 协作的边缘设备执行任务
由于边缘设备的计算和存储资源有限,且边缘设备间存在负载不均衡的现象,多边缘设备协作共同执行任务,可以充分利用边缘设备资源,提高系统的资源利用率.edge n接收自身关联的UE m的卸载任务I m后,若选择将任务I m卸载到协作的edge y处执行,执行时延包括3部分:1)UE m上传数据到edge n所需的传输时延
与edge y间传输数据所需的传输时延
执行任务所需的计算时延.f ym表示edge y分配给任务I m的计算量,任务I m在edge y处执行的计算时延表示为γm/f ym.将edge n关联的UE m产生的任务I m卸载到协作的edge y处执行所需的执行时延为
2.4.3 远端云执行任务
由于远端云具有强大的计算能力,可以忽略远端云的计算时延.那么edge n将自身关联的UE m产生的任务I m卸载到远端云处执行所需的执行时延包括2部分:1)UE m上传数据到edge n的传输时延
传输数据到远端云的传输时延
.因此任务I m在远端云处执行所需的执行时延为
2.5 问题描述
为了方便表示,在表示单个时隙的目标时将表示时隙的变量t省略.UE m产生的任务I m可选的卸载位置包括:关联的edge n、edge n协作的边缘设备和远端云.每个计算任务仅能选择一个卸载位置,并且选择的卸载位置提前缓存了执行该任务所需的服务.UE m产生的任务I m的执行时延为
本文研究面向多边缘设备协作的任务卸载和服务缓存联合优化问题,目标是在任务执行时延限制条件下,最小化任务整体执行时延,问题建模为
约束条件式(10.1)表示每个边缘设备缓存的服务个数不能超过自身的缓存容量限制.约束条件式(10.2)表示终端用户产生的计算任务仅可在关联的边缘设备、协作的边缘设备和远端云中选择一个卸载位置.约束条件式(10.3)表示边缘设备为本地执行的计算任务分配的计算量为正数.约束条件式(10.4)表示边缘设备为本地执行的计算任务分配的资源总量必须满足自身的计算资源总量限制.约束条件式(10.5)表示edge n是否缓存SC s.约束条件式(10.6)表示edge n关联的UE m产生的任务I m是否卸载到Device y处执行.
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 终端用户的情景信息
边缘设备在每个时隙开始时观察自身关联的终端用户的情景信息
表示在slot t时edge n关联的UE m的情景信息,其中X＝[0,1]D表示情景信息空间,D表示情景信息维度.在slot t时edge n关联的终端用户的情景信息集合表示为
若edge n为Sink node,则需要考虑候选协作的边缘设备所关联的终端用户的情景信息,Sink node n考虑的协作情景信息集合表示为
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中所有情景信息相应的数据值
表示slot t时edge n关联的UE m的情景信息
对应的分区情景信息,即
表示slot t时edge n关联的终端用户对应的分区情景信息集合
表示edge n记录的候选协作的edge y关联的UE w的情景信息对应的分区情景信息.
3.1.2 服务缓存问题建模
UE m产生的任务I m的执行时延限制表示为d m,执行任务所获收益值与d m相关.执行任务时延越低,与d m间的差值越大,则执行该任务的收益值越大.边缘设备只有缓存任务I m所需的SC s m时,才能执行该任务,产生收益值.因此,针对SC s执行任务I m产生的收益值
定义为
其中
表示slot t时情景信息为
、服务缓存需求为SC s m的任务I m的执行时延.
最小化系统中任务整体执行时延等价于最大化系统中任务整体收益值.任务整体收益值为执行系统中所有终端用户产生的任务所获收益值总和,因此最大化系统中任务整体收益值表示为3CMAB算法是一个探索与利用权衡的过程,为了获取情景信息对应的不同服务缓存的预估收益值,需要进行多次探索.探索阶段针对每种情景信息选择之前从未探索或者未探索完全的服务进行缓存,任务执行完成后得到缓存该服务相应的收益值,根据该收益值更新预估收益值,用于制定下一轮服务缓存策略.利用阶段则为每种情景信息选择预估收益值最高的服务进行缓存.为了得到每种情景信息对每种服务缓存的预估收益值,需要记录相关数据,因此会耗费一定的存储空间.当学习过程完成后,边缘设备即可根据学习获得的情景信息与服务缓存之间的模型,根据终端用户的情景信息选择预估收益值最高的服务进行缓存,快速制定服务缓存策略.
3CMAB算法需要优化系统长期收益,即最大化系统中长期任务整体收益值,具体表示为
3.1.3 3CMAB算法
本节详细介绍3CMAB算法,包括探索和利用2个阶段,算法流程如图3所示.首先,获取每个边缘设备本地关联的终端用户的情景信息集合,然后预判边缘设备类型,并依据类型设计不同的探索和利用过程.探索阶段中,每个边缘设备根据未探索完全的服务缓存个数和服务缓存容量限制之间的关系,选择不同的服务缓存策略进行探索.若探索完全,即针对每种情景信息学习到最优的服务缓存后,则进入利用阶段.利用阶段可依据终端用户的情景信息选择最优的服务进行缓存.
1)判断边缘设备运行阶段
表示到slot t为止,edge n为情景信息p选择SC s的次数.若在slot t中edge n为情景信息p选择SC s,则更新
,表示为
是一个确定性、单调递增的控制函数[23-24].若
,则表明edge n针对情景信息p,SC s未探索完全.
表示edge n针对待执行任务未探索完全的服务缓存集合
其中
表示edge n针对待执行任务未探索完全的服务缓存序号集合,具体表示为
其中,M n表示edge n关联的终端用户序号集合,
表示edge n针对情景信息p未探索完全的服务缓存序号集合.判断
是否为空,从而确定边缘设备运行阶段.若
则边缘设备进入探索阶段;若
,则边缘设备进入利用阶段.
Source node和Sink node两类边缘设备需要考虑不同的情景信息,缓存不同服务所获得的收益值存在差异,进而导致探索与利用策略有所不同.下面首先介绍如何判断边缘设备类型,然后分别介绍2类边缘设备的探索与利用过程.
2)判断边缘设备类型
当边缘设备进行服务缓存时,首先边缘设备需要根据自身关联的终端用户的情景信息推测任务计算需求量以及任务执行时延限制,进而对边缘设备类型进行预判断.
记录到slot t为止,edge n接收的情景信息为p、服务缓存需求为SC s的任务请求次数
在slot t时,若edge n接收到情景信息为p、服务缓存需求为SC s的任务请求,则更新
Fig.3 3CMAB algorithm flow chart
图3 3CMAB算法流程图
在当前时隙中,edge n关联的UE m产生的任务I m的计算需求量为γm,执行时延限制为d m.利用
与任务I m的计算需求量γm计算到slot t为止,edge n接收的情景信息为p、服务缓存需求为SC s的平均任务计算需求量
为
表示到slot t为止,edge n接收的情景信息为p的平均任务计算需求量.
利用
与任务I m的任务执行时延限制d m计算到slot t为止,edge n接收的情景信息为p、服务缓存需求为SC s的平均任务执行时延限制
为
表示到slot t为止,edge n接收的情景信息为p的平均任务执行时延限制.
在每个slot t开始时,edge n观察关联的终端用户的情景信息
根 据记录的平均任务计算需求量
和平均任务执行时延限制
计算关联的终端用户的总任务计算需求量即任务负载为
和总任务执行时延限制
edge n根据自身的总任务计算需求量和计算能力得到所有任务均在本地执行的平均执行时延:
edge n根据自身的总任务执行时延限制和任务数量,得到edge n执行所有任务的平均执行时延限制:
若
,表示edge n本地执行所有任务的平均执行时延超过所有任务的平均执行时延限制,意味着edge n负载较重,无法满足关联的终端用户的任务执行时延限制,则edge n预判为Source node.若
表示edge n本地执行所有任务的平均执行时延小于所有任务的平均执行时延限制,意味着edge n负载较轻,可以满足关联的终端用户的任务执行时延限制,则edge n预判为Sink node.
Source node负载较重,仅能为本地关联的终端用户提供服务,因此在制定服务缓存策略时仅需要考虑本地关联的终端用户的情景信息.而Sink node负载较轻,除了为本地关联的终端用户提供服务外,还需要执行候选协作的边缘设备卸载的任务,因此在制定服务缓存策略时除了考虑本地关联的终端用户的情景信息,还需要考虑候选协作的边缘设备关联的终端用户的情景信息.
3)Source node探索与利用过程
Source node n依据式(11)计算执行自身关联的UE m产生的任务I m的本地收益值r m.定义r m与后续Sink node执行候选协作的边缘设备卸载的任务所获得的协作收益值
进行区分,在4)中将对
进行详细介绍.
表示Source node n中情景信息为p、服务缓存需求为SC s的任务本地执行次数.Source node n每执行一次情景信息为p、服务缓存需求为SC s的任务,则更新
值:
表示Source node n针对自身关联的情景信息为p的终端用户选择SC s时的本地预估收益值.Source node n利用所获得的本地收益值r m和
更新本地预估收益值
,即到slot t为止,Source node n本地执行情景信息为p、服务缓存需求为SC s的任务所获得的平均本地收益值
计算为
表示Source node n为情景信息p缓存SC s的总预估收益值为
若Source node n未探索完全的服务缓存集合
不为空,则进入探索阶段.在探索阶段,Source node n根据未探索完全的服务缓存个数
和自身服务缓存容量限制K n之间的关系选择不同的服务缓存策略.若
则Source node n从
中随机选择K n个服务进行缓存;若
则Source node n首先选择
中所有服务进行缓存,然后选择
个总预估收益值最高的服务进行缓存:
其中
若Source node n未探索完全的服务缓存集合
为空,则进入利用阶段.在利用阶段,Source node n根据式(25)选择总预估收益值最高的K n个服务进行缓存:
4)Sink node探索与利用过程
Sink node的探索与利用过程和Source node相同,但由于Sink node除了执行本地关联的终端用户产生的任务外,还需要执行候选协作的边缘设备卸载的任务,因此Sink node在制定服务缓存策略时需要考虑候选协作的边缘设备的服务缓存需求.Sink node除了考虑本地关联的终端用户的情景信息外,还需要考虑候选协作的边缘设备关联的终端用户的情景信息,该部分情景信息与Sink node自身可接收的任务量和对候选协作的边缘设备的偏好值相关.
Sink node n自身关联的终端用户的总任务计算需求量为
表示Sink node n能够提供的总任务计算需求量.因此Sink node n可接收的候选协作的边缘设备卸载的总任务计算需求量
为两者的差值,表示为
计算Sink node n针对候选协作的edge y中每种情景信息p的偏好值
.该偏好值与edge y和Sink node n之间的历史协作次数
,以及候选协作的边缘设备edge y可选择的Sink node个数
相关
表示edge y候选协作的Sink node序号集合
表示到slot t为止,Sink node n执行edge y中情景信息为p的任务次数
表示到slot t为止,Sink node n执行edge y中情景信息为p、服务缓存需求为SC s的任务次数.每执行一次,则根据
更新
值.
Sink node n与edge y针对edge y中情景信息p的历史协作次数越多,edge y可选Sink node数量越少,则Sink node n针对edge y中情景信息p的偏好值
越高.
其中,N n表示Sink node n候选协作的边缘设备序号集合.
根据式(28)选择偏好值最高的情景信息,将选择的情景信息添加到Sink node n的协作情景信息集合
中.计算
中所有情景信息对应的终端用户的总任务计算需求量是否达到Sink node n当前可接收的总任务计算需求量,若达到则终止;若未达到则选择偏好值次高的情景信息,重复上述过程直到终止,得到Sink node n的协作情景信息集合
Sink node n执行任务产生的收益值包括r m和
两部分,r m表示Sink node n执行自身关联的UE m产生的任务I m所获得的本地收益值
表示Sink node n处执行候选协作edge y关联的UE w产生的任务I w所获得的协作收益值.根据式(11)计算r m和
表示Sink node n针对自身关联的情景信息为p的终端用户选择SC s时的本地预估收益值,更新过程与Source node相同,具体见式(21)(22).
表示Sink node n为候选协作的edge y中情景信息为p的终端用户选择SC s的协作预估收益值.利用所获得的协作收益值
和执行候选协作edge y产生的情景信息为p、服务缓存需求为SC s的任务次数
,表示为
表示Sink node n为情景信息p缓存SC s的总预估收益值,表示为
Sink node的探索与利用过程和Source node相同.若Sink node n未探索完全的服务缓存集合
不为空,则进入探索阶段.在探索阶段,Sink node n根据未探索完全的服务缓存个数
和自身服务缓存容量限制K n之间的关系,选择不同的服务缓存策略.若
,则Sink node n从未探索完全的服务缓存集合中随机选择K n个服务进行缓存;若
则Sink node n先缓存所有未探索完全的服务,然后选择总预估收益值最高的
个服务进行缓存:
若Sink node n未探索完全的服务缓存集合
为空,则进入利用阶段.在利用阶段,Sink node n选择总预估收益值最高的K n个服务进行缓存:
5)3CMAB算法流程
首先每个edge n获取自身关联的终端用户的情景信息集合
.然后分别依据式(19)和式(20)计算edge n中所有任务均在本地执行的平均执行时延
和平均执行时延限制
,根据
之间的大小关系预判断边缘设备类型.然后根据式(15)计算edge n针对待执行任务未探索完全的服务缓存集合
,则edge n进入探索阶段;若
,则edge n进入利用阶段.边缘设备类型不同时,总预估收益值的计算公式不同.Source node和Sink node分别根据式(23)和式(30)计算总预估收益值.探索阶段中,edge n根据未探索完全的服务缓存个数
与自身服务缓存容量限制K n之间的关系,选择不同的服务缓存策略.当
时,edge n从未探索完全的服务缓存集合中随机选择K n个服务进行缓存;当
K n时,edge n先将所有未探索完全的服务进行缓存,然后选择总预估收益值最高的
个服务进行缓存.根据边缘设备类型,Source node和Sink node分别根据式(24)和式(31)选择总预估收益值最高的len个服务进行缓存.利用阶段中,根据边缘设备类型,Source node和Sink node分别根据式(25)和式(32)选择K n个总预估收益值最高的服务进行缓存.3CMAB算法伪代码如算法1所示.
算法1.3CMAB算法.
输入:终端用户序号集合M n、终端用户情景信息
、边缘设备最大计算量
输出:服务缓存策略
初始化:服务缓存次数
任务请求次数
本地执行次数
协作执行次数
平均任务计算需求量
平均任务执行时延限制
本地预估收益值
;协作预估收益值
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)相关联的对偶量.拉格朗日函数表示为
定义拉格朗日对偶函数G P3(υ)为
G P3(υ)表示在原始F上求解最小值.将式(39)进一步转化为在υ上求解最大值的对偶函数,具体表示为
因为子问题P3是凸的,因此可以通过对拉格朗日函数L P3(F,υ)求解一阶导数,令其一阶导数为0来获得最优分配的计算量f∗nm,即:
将式(41)代入式(39)中.由于拉格朗日对偶函数G P3(υ)也是凸函数,求解G P3(υ)的一阶导数,令其等于0即可获得最优对偶量υ∗n,即:
将式(42)代入式(41)中,即可得到edge n为本地执行任务集合I exe n 中的每个待执行的任务I m分配的最优计算量:
3.2.2 任务卸载位置选择策略
根据3.2.1节所述方法可以获得边缘设备的资源分配策略F,在此基础上制定任务卸载位置选择策略A,确定所有任务的卸载位置.由于终端用户上传数据到自身关联的边缘设备所需的传输时延是确定的,因此可以将原始问题P1转化为子问题P4:
其中,
约束式(44.2)表示UE m产生的任务I m仅可在关联的边缘设备、协作的边缘设备和远端云中选择一个卸载位置.
edge n为自身关联的UE m产生的任务I m选择合适的卸载位置.若edge n缓存任务I m所需的SC s m,则该任务为本地缓存命中任务,添加到edge n的本地缓存命中任务集合
中.剩余任务即本地未缓存命中的任务添加到edge n的本地未缓存命中任务集合
中任务可以卸载到协作的Sink node或者远端云处执行.
边缘设备本地缓存命中任务集合
中的任务量决定了其负载状态,进而可以确定边缘设备类型:Source node或者Sink node.若边缘设备无法满足本地缓存命中任务集合
中的所有任务的执行时延限制,则该边缘设备为Source node;反之,若能够满足所有任务的执行时延限制,则该边缘设备为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 node n从本地缓存命中任务集合
中选择部分任务在本地执行
中剩余任务和
中的任务则需要进行卸载,将其添加到卸载任务集合
中.
中每个任务可选择的卸载位置除了本地边缘设备外,还可以选择候选协作的Sink node或者远端云.根据任务在候选协作的Sink node或者远端云处执行的卸载预估收益值来确定卸载的任务.卸载预估收益值与本地预估执行时延和卸载到其他位置执行的最低卸载预估执行时延之间的差值相关,下面对其进行详细介绍.
若任务I m卸载到候选协作的Sink node y处执行,假定Sink node y中的所有任务平分计算资源,则Sink node y中每个任务能够获得的计算量为
表示Sink node y待执行的任务个数.任务I m卸载到Sink node y处执行所需的卸载预估执行时延包括3部分:UE m将任务I m卸载到自身关联的Source node n所需的传输时延、任务I m从自身关联的Source node n卸载到Sink node y处的传输时延和任务I m在Sink node y处执行所需的计算时延,具体表示为
计算任务I m在所有候选协作的Sink node处执行所需的最低卸载预估执行时延表示为
其中
表示任务I m关联的边缘设备Source node n的候选协作Sink node序号集合.
由于远端云的计算能力较强,可以忽略远端云的计算时延.任务I m卸载到远端云处执行所需的卸载预估执行时延
包括2部分:UE m将任务I m卸载到自身关联的Source node n所需的传输时延、任务I m从自身关联的Source node n处卸载到远端云所需的传输时延,即
.任务I m在候选协作的Sink node和远端云处执行所需的最低卸载预估执行时延
表示为
若
表明任务I m卸载将无法满足任务执行时延限制,因此任务I m需要在关联的边缘设备本地执行,即a nn,Im＝1.
遍历本地缓存命中任务集合
中的每一个任务I m,将
的任务I m添加到
中,同时将其从
中删除.假设
中剩余的所有任务均在Source node本地执行,依据式(43)计算分配给
中每个任务的计算量,根据式(6)计算出中每个任务的本地预估执行时延.本地预估执行时延与最低卸载预估执行时延之间的差值表示卸载该任务可获得的卸载预估收益值.为
中的每个任务计算卸载预估收益值,依次选择
中卸载预估收益值最大的任务进行卸载,将其从
中删除,并添加到本地卸载任务集合
中,直到
中剩余的所有任务和
中的任务均满足任务执行时延限制,此时将
中剩余的所有任务全部添加到
中.
2)Sink node确定本地执行任务集合和本地卸载任务集合
由于Sink node计算资源充足,所有本地缓存命中任务集合
中的任务均在本地执行,本地未缓存命中的任务卸载到候选协作的Sink node或远端云处执行.本地卸载任务集合为
.此外Sink node还需要执行接收的其他候选协作边缘设备卸载的任务,因此Sink node n本地执行任务集合
包括本地缓存命中任务集合
和接收的卸载任务集合
3)基于偏好的双边匹配算法
采用基于偏好的双边匹配算法为所有边缘设备待卸载的任务(即
中的任务)选择合适的卸载位置.每个待卸载任务对不同卸载位置(候选协作的Sink node和远端云)存在偏好,偏好值与卸载位置的卸载预估执行时延相关,卸载预估执行时延越低,则偏好值越大.
UE m关联的边缘设备确定,此时UE m将任务I m卸载到自身关联的edge n所需的传输时延
即可确定,因此在计算偏好值考虑卸载预估执行时延时,不考虑
部分.
edge n中每个待卸载任务I m对每个候选协作的Sink node y的偏好值表示为
其中
表示edge n候选协作的Sink node序号集合.
edge n中每个待卸载任务I m卸载到远端云的偏好值表示为
每个edge n优先向偏好值最优的卸载位置发送卸载请求.若请求的卸载位置是远端云,则远端云直接接收该卸载请求,即a n 0,Im＝1.若请求的卸载位置为Sink node,则需要等待Sink node回复.若请求的Sink node接收该卸载请求,则可以确定该任务的卸载位置;若Sink node拒绝该卸载请求,则在下一轮迭代中向偏好值次优的卸载位置发送卸载请求.
接下来介绍Sink node y如何判断是否接收卸载请求
表示Sink node y接收到的卸载请求任务集合
表示Sink node y接收的卸载任务集合,
表示Sink node y的本地执行任务集合.在每轮迭代中,每个Sink node y可能接收到多个任务的卸载请求,假定接收所有卸载请求即
,同时根据
更新
值.根据式(43)得到Sink node y分配给
中的每个任务的计算量
中本地关联的终端用户产生的任务根据式(6)计算本地执行任务所需的本地预估执行时延
中接收的协作边缘设备的卸载任务根据式(7)计算卸载到Sink node y处执行所需的卸载预估执行时延.判断
中所有任务是否均可满足执行时延限制.若均可满足执行时延限制,则Sink node y接收所有卸载请求,否则将依据下面步骤拒绝部分卸载请求.
计算Sink node y接收
中每个卸载任务的接收预估收益值,即在Sink node y处执行该任务所需的卸载预估执行时延与该任务在次优执行位置所需的卸载预估执行时延之间的差值,拒绝
中接收预估收益值最低的卸载任务,将该任务从
中删除,同时更新
值.重复上述过程,直到能够满足
中所有任务的执行时延限制,得到最终接收的卸载任务集合
和本地执行任务集合
上述基于偏好的双边匹配算法能够依据边缘设备的任务需求、资源状态和负载情况合理卸载计算任务,实现边缘设备间负载均衡.由于仅Sink node可以接收卸载任务,待卸载任务可匹配的卸载位置无需考虑负载较重的Source node,因此有效降低了任务卸载的匹配空间,进而降低计算复杂度.上述算法流程如算法2所示.
算法2.多边缘设备间的任务卸载算法.
首先确定每个边缘设备的本地缓存命中任务集合
和本地未缓存命中任务集合
,然后依据
中的任务量判断边缘设备的类型,进一步分别为Source node和Sink node确定本地执行任务集合
和本地卸载任务集合
.若边缘设备为Source node,判断
中的每个任务是否需要卸载.计算每个可卸载任务的卸载预估收益值,依次选择卸载预估收益值最高的任务进行卸载,直到Source node剩余的所有任务均可满足执行时延限制,至此可以得到
.若边缘设备为Sink
中的所有任务均在本地执行,此外还可以接收候选协作的边缘设备卸载的任务
,因此
.本地未缓存命中的任务卸载到候选协作的Sink node或远端云处执行,即
.接下来,为每个边缘设备的本地卸载任务集合
中的每个任务计算对每个卸载位置的偏好值
,依次向偏好值最优的卸载位置发送卸载请求.若请求的卸载位置为远端云,则直接接收该卸载请求;若请求的卸载位置为Sink node,则需要决定是否接收该卸载请求.若请求的卸载位置Sink node接收该卸载请求,则可以确定该任务的卸载位置;若请求的卸载位置Sink node拒绝该卸载请求,则向偏好值次优的卸载位置发送卸载请求,重复上述过程,直到所有卸载任务均确定卸载位置则该算法终止.
3.3 JOC算法复杂度分析
3CMAB算法在线学习终端用户情景信息对边缘设备的服务缓存收益的影响,基于学习获得的模型,直接通过公式计算即可得出服务缓存策略.因此进行JOC算法复杂度分析时仅考虑多边缘设备间的任务卸载策略的复杂度.多边缘设备间的任务卸载策略是一种分布式策略,因此从单个边缘设备的角度进行算法复杂度分析.
令
表示edge n候选协作的Sink node个数,令M 1＝|M n|表示edge n关联的终端用户个数,因此edge n选择本地执行任务的时间复杂度为O(N 1×M 1).令
表示Sink node y接收的卸载请求任务个数,令
表示edge n待卸载的任务个数,因此edge n为卸载任务选择卸载位置的计算复杂度为O(M 2×(N 1 log N 1＋N 1×N 2)).所提算法的整体复杂度为O(N 1×M 1)＋
4 实验与结果
本节给出仿真结果用于评估所提任务卸载和服务缓存在线联合优化(JOC)算法的性能.
4.1 实验设置
移动边缘计算场景中部署3个边缘设备为终端用户提供服务.每个边缘设备的带宽为20 MHz.在每个边缘设备覆盖区域内随机部署终端用户,所有关联的终端用户平均分配带宽.每个edge n的最大计算量为
.每个UE m的传输功率为
,噪声功率为σ2＝－100 dBm,路径传输损耗模型为Los＝32.5＋20 lg Z＋20 lg X,其中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 实验结果
1)3CMAB算法的学习速率.首先探索函数
中参数β对实验性能的影响,探索不同β值时的学习速率.如图4所示,β值不同时,学习效果存在差异,同时收敛速率也各不相同.随着β值增大,需要探索的次数增加,收敛性能降低且收敛速率变慢.在β＝0.01和β＝1时,可以达到最好的学习效果,而β＝0.01的收敛速率稍微优于β＝1的收敛速率,因此在实验中,设置β＝0.01.
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算法可以获得更优的任务执行性能,同时实现边缘设备间负载均衡.
[1]Cuervo E,Balasubramanian A,Cho D,et al.MAUI:Making smartphones last longer with code offload[C]//Proc of the 8th Int Conf on Mobile Systems,Applications,and Services.New York:ACM,2010:4962
[2]Xu Jie,Chen Lixing,Zhou Pan.Joint service caching and task offloading for mobile edge computing in dense networks[C]//Proc of IEEE INFOCOM"18.Piscataway,NJ:IEEE,2018:207215
[3]Ma Xiao,Zhou Ao,Zhang Shan,et al.Cooperative service caching and workload scheduling in mobile edge computing[C]//Proc of IEEE INFOCOM"20.Piscataway,NJ:IEEE,2020:20762085
[4]LüHuazhang,Chen Dan,Fan Bin,et al.Standardization progress and case analysis of edge computing[J].Journal of Computer Research and Development,2018,55(3):4367(in Chinese)(吕华章,陈丹,范斌,等.边缘计算标准化进展与案例分析[J].计算机研究与发展,2018,55(3):4367)
[5]European Telecommunications Standards Institute(ETSI).Mobile-edge computing introductory technical white paper[OL].[2016-12-03].https://portal.etsi.org/Portals/0/TBpages/MEC/Docs/Mobile-edge_Comput ing_Introductory_Techical_White_Paper_V1%2018-09-14.pdf
[6]European Telecommunications Standards Institute(ETSI).Mobile edge computing(MEC):Framework and reference architecture[OL].[2016-03-17].http://www.etsi.org/deliver/etsi_gs/MEC/001_099/003/01.01.01_60/gs_MEC003 v010101p.pdf
[7]European Telecommunications Standards Institute(ETSI).Mobile edge computing(MEC):General principles for mobile edge service APIs[OL].[2017-07-11].https://www.etsi.org/deliver/etsi_gs/MEC/001_099/009/0 1.01.01_60/gs_MEC009v010101p.pdf
[8]3rd Generation Partnership Project(3GPP).3GPP TS,23.501,System architecture for the 5G system(Release 15)[OL].[2017-12-22].https://www.3gpp.org/DynaReport/23-series.htm
[9]China Communication Standards Association(CCAS).TC5-WG12-2017-002Q-Study on 5G MEC key technology[OL].[2017-08-15].http://www.ccsa.org.cn/(in Chinese)(中国通信标准化协会.TC5-WG12-2017-002Q-立项建议:5G MEC关键技术研究[OL].[2017-08-15].http://www.ccsa.org.cn/)
[10]Mach P,Becvar Z.Mobile edge computing:A survey on architecture and computation offloading[J].IEEE Communications Surveys＆Tutorials,2017,19(3):16281656
[11]Cardellini V,PersonéV D N,Valerio V D,et al.A gametheoretic approach to computation offloading in mobile cloud computing[J].Mathematical Programming,2016,157(2):421 449
[12]Chen Meng-Hsi,Dong Min,Liang Ben.Resource sharing of a computing access point for multi-user mobile cloud offloading with delay constraints[J].IEEE Transactions on Mobile Computing,2018,17(12):28682881
[13]Pham Q V,LeAnh T,Tran N H.Decentralized computation offloading and resource allocation in heterogeneous networks with mobile edge computing[J].ar Xiv preprint ar Xiv:1803.00683,2018
[14]Wu Hang,Chen Lixing,Shen Cong,et al.Online geographical load balancing for energy-harvesting mobile edge computing[C]//Proc of IEEE ICC"18.Piscataway,NJ:IEEE,2018:16.DOI:10.1109/ICC.2018.8422299
[15]Chen Lixing,Xu Jie.Socially trusted collaborative edge computing in ultra-dense networks[C]//Proc of the 2nd ACM/IEEE Symp on Edge Computing.New York:ACM,2017:111.DOI:10.1145/3132211.3134451
[16]Xiao Yong,Krunz M.QoE and power efficiency tradeoff for fog computing networks with fog node cooperation[C]//Proc of IEEE INFOCOM"17.Piscataway,NJ:IEEE,2017:19.DOI:10.1109/INFOCOM.2017.8057196
[17]Chen Lixing,Xu Jie,Zhou Sheng.Computation peer offloading in mobile edge computing with energy budgets[C]//Proc of IEEE GLOBECOM"17.Piscataway,NJ:IEEE,2017:16.DOI:10.1109/GLOCOM.2017.8255052
[18]Chen Lixing,Zhou Sheng,Xu Jie.Computation peer offloading for energy-constrained mobile edge computing in small-cell networks[J].IEEE/ACM Transactions on Networking,2018,26(4):16191632
[19]Chen Lixing,Shen Cong,Zhou Pan,et al.Collaborative service placement for edge computing in dense small cell networks[J].IEEE Transactions on Mobile Computing,2020,20(2):377390
[20]Poularakis K,Llorca J,Tulino A M,et al.Joint service placement and request routing in multi-cell mobile edge computing networks[C]//Proc of IEEE INFOCOM"19.Piscataway,NJ:IEEE,2019:1018
[21]He Ting,Khamfroush H,Wang Shiqiang,et al.It"s hard to share:Joint service placement and request scheduling in edge clouds with sharable and non-sharable resources[C]//Proc of ICDCS"18.Piscataway,NJ:IEEE,2018:365375
[22]Tran T X,Chan K,Pompili D.COSTA:Cost-aware service caching and task offloading assignment in mobile-edge computing[C]//Proc of IEEE SECON"19.Piscataway,NJ:IEEE,2019:19.DOI:10.1109/SAHCN.2019.8824854
[23]Chen Lixing,Xu Jie,Ren Shaolei,et al.Spatio-temporal edge service placement:A bandit learning approach[J].IEEE Transactions on Wireless Communications,2018,17(12):83888401
[24]Chen Lixing,Xu Jie.Budget-constrained edge service provisioning with demand estimation via bandit learning[J].IEEE Journal on Selected Areas in Communications,2019,37(10):23642376
[25]Chen Min,Hao Yixue.Task offloading for mobile edge computing in software defined ultra-dense network[J].IEEE Journal on Selected Areas in Communications,2018,36(3):587597
[26]Fleischer L,Goemans M X,MirrokniV S,et al.Tight approximation algorithms for maximum general assignment problems[C]//Proc of SODA"06.New York:ACM,2006:611620
[27]Müller S,Atan O,Schaar M,et al.Context-aware proactive content caching with service differentiation in wireless networks[J].IEEE Transactions on Wireless Communications,2017,16(2):10241036
[28]Chen Lixing,Xu Jie,Lu Zhuo.Contextual combinatorial multi-armed bandits with volatile arms and submodular reward[C]//Proc of NIPS"18.Cambridge,MA:MIT Press,2018:32513260
[29]Tran T X,Pompili D.Joint task offloading and resource allocation for multi-server mobile-edge computing networks[J].IEEE Transactions on Vehicular Technology,2019,68(1):856 868
