一种基于移动边缘计算的多用户多任务卸载方法转让专利
申请号 : CN201911318653.3
文献号 : CN111148134B
文献日 : 2021-06-01
发明人 : 季荣华 , 申富饶 , 赵健
申请人 : 南京大学
摘要 :
权利要求 :
1.一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,包括:步骤1,构建基于移动边缘计算的多用户多任务场景模型,所述多用户多任务场景模型包括系统模型和模块模型;所述系统模块在多用户和多任务场景将任务在基站和移动设备中进行传输和处理;
所述模块模型包括:任务模型、信道模型、任务卸载模型和移动设备本地及边缘服务器的计算模型,所述任务模型通过三元组表征每个任务后,根据所述信道模型对多用户进行信道分配,并根据任务卸载模型确定是否将任务卸载到基站通过边缘服务器进行处理,所述移动设备本地及边缘服务器的计算模型用于分别计算任务在本地及边缘服务器的处理时延,根据时延大小决策将任务在移动设备本地处理还是在边缘服务器进行处理;
步骤2,根据任务类别和任务卸载策略对任务进行卸载,所述任务类别包括个人任务和共享任务,所述任务卸载策略以最优的任务处理时延为目标求解获得;
在所述步骤2之前,以最优的任务处理时延为目标求解获得所述任务卸载策略,包括:步骤2.1,将每个不可分任务变为可分任务,包括:基于所述步骤1提出原始问题P1,所述原始问题P1是一个混合整数非线性规划问题,且是一个最小化最大的问题,将所述原始问题P1中的0‑1整数变量松弛成[0,1]的连续变量,并将最小化最大问题转化成求最小的问题,所述原始问题P1便成为非线性规划问题P2;
步骤2.2,所述非线性规划问题P2是一个非凸问题,采用渐进凸逼近的方法,将所述非线性规划问题P2转化为一个凸优化问题P3;
步骤2.3,采用凸优化的方法求解所述凸优化问题P3,获得所述原始问题P1的次优解,即获得最优的任务处理时延的任务卸载策略。
2.根据权利要求1所述的一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,所述步骤2包括:
步骤2.4,获取所述任务的任务类别;
步骤2.5,若所述任务的任务类别为共享任务,根据所述任务卸载策略判断共享任务是否需要卸载;
步骤2.6,若所述共享任务需要卸载,每个移动设备根据所述任务卸载策略将部分共享任务上传至基站,所述每个移动设备上传的部分共享任务在基站合成一组完整的共享任务,通过边缘服务器处理所述完整的共享任务,获得卸载到基站处理的共享任务处理结果并下传至所述每个移动设备后,执行步骤2.11的操作;
步骤2.7,若所述共享任务不需要卸载,则不作处理;
步骤2.8,若所述任务的任务类别为个人任务,根据所述任务卸载策略判断个人任务是否需要卸载;
步骤2.9,若所述个人任务需要卸载,每个移动设备根据所述任务卸载策略将个人任务上传至基站,通过所述边缘处理器处理个人任务,获得卸载到基站处理的个人任务处理结果并下传至所述每个移动设备后,执行步骤2.11的操作;
步骤2.10,若所述个人任务不需要卸载,通过移动设备本地处理所述个人任务,获得本地处理的个人任务处理结果,执行步骤2.11的操作;
步骤2.11,将本地处理的任务结果和卸载到基站处理的任务结果合并,所述本地处理的任务结果包括本地处理的个人任务处理结果,所述卸载到基站处理的任务结果包括卸载到基站处理的共享任务处理结果和卸载到基站处理的个人任务处理结果。
3.根据权利要求1所述的一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,所述步骤1包括构建所述系统模型:所述系统模型包括边缘服务器、一个基站以及所述基站服务的Q个移动设备,每个所述移动设备有N个任务, N=N1+N2,其中,N是移动设备中所有计算任务的数量,N1是移动设备中个人任务的数量,N2是移动设备中共享任务的数量;
所述移动设备将部分任务通过上行链路上传至基站,所述基站处理移动设备上传的任务,将任务处理结果通过下行链路传至移动设备;同时,所述移动设备在本地处理未上传的任务;所述边缘服务器具有计算和处理能力。
4.根据权利要求3所述的一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,所述步骤1包括构建所述任务模型:通过三元组表征每个所述任务:{Lu,q,n,Ld,q,n,xn},其中,Lu,q,n是移动设备q中的任务n处理前的大小,单位为比特,n∈N,q∈Q,Ld,q,n是移动设备q中的任务n处理后的大小,xn是处理计算任务n所需要的工作量,单位为圈/比特;
所述移动设备q中的任务n处理后的大小等于α倍的移动设备q中的任务n处理前的大小:
Ld,q,n=αLu,q,n,α∈[0,1]edge
所述移动设备q的计算能力为 单位为圈/秒,边缘服务器的计算能力为F ,单位为圈/秒。
5.根据权利要求4所述的一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,所述步骤1包括构建所述信道模型:信道以动态分配的方式分配给每个移动设备;用B表示整个无线系统的带宽,所述移动设备q的上行链路的频谱效率eu,q表示为:其中,pu,q表示移动设备q的传输功率,hu,q表示移动设备q上行链路的信道增益,N0表示加性高斯白噪声;
所述移动设备q的下行链路的频谱效率ed,q表示为:其中,pd,q表示基站传输到移动设备q的功率,hd,q表示移动设备q下行链路的信道增益;
用λu,q表示上行链路分配给移动设备q的带宽比例,用λd,q表示下行链路分配给移动设备q的带宽比例,λu,q∈[0,1],λd,q∈[0,1],所述上行链路的传输速率Ru,q表示为:Ru,q=λu,qBeu,q(3),所述下行链路的传输速率Rd,q表示为:Rd,q=λd,qBed,q(4)。
6.根据权利要求5所述的一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,所述步骤1包括构建所述任务卸载模型:采用部分卸载策略,即将部分任务卸载到基站通过边缘服务器进行处理,剩下的任务由本地移动设备进行本地同步处理;
对于卸载到边缘服务器进行处理的任务,任务处理包括:移动设备将部分任务上传到基站;基站的边缘服务器进行任务处理;基站将任务处理结果下传给移动设备,所述任务处理结果即卸载到基站处理的任务结果,包括卸载到基站处理的共享任务处理结果和卸载到基站处理的个人任务处理结果;
对于个人任务,定义 为移动设备q对其任务n1的卸载决策,表示移动设备q的任务n1由本地处理, 表示移动设备q的任务n1上传到基站由边缘服务器处理;
对于共享任务,定义 为移动设备q对其任务n2的卸载决策,表示移动设备q的任务n2由本地处理, 表示移动设备q的任务n2上传到基站由边缘服务器处理;
ind
定义S 为Q行N1列的变量矩阵, 为其第q行第n1个变量;
shared
定义S 为Q行N2列的变量矩阵, 为其第q行第n2个变量;
由于每个所述移动设备的共享任务是一样的,所以每个移动设备只需部分卸载其共享任务到边缘服务器;在所述边缘服务器中将收到的所有移动设备上传的共享任务加起来等于一组完整的N2个共享任务,公式表述如下:其中, 是移动设备q中上传的共享任务n2。
7.根据权利要求6所述的一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,所述步骤1包括构建所述移动设备本地及边缘服务器的时延计算模型:整个系统的时延包括:本地处理时延、上传时延、边缘处理时延以及下传时延;
对于个人任务,所述移动设备q的本地处理时延表示为:其中, 是移动设备q上传的个人任务n1的大小;
所述移动设备q的上行传输时延表示为:其中, 是移动设备q上传的共享任务n2的大小;
对于个人任务,边缘处理的时延表示为:其中,βq是边缘服务器分配给处理移动设备q上传的任务的计算资源的比例,βq∈[0,
1];
对于共享任务,所述边缘服务器需等所有移动设备上传完共享任务后才可以进行处理,所以边缘服务器处理共享任务的时延表示为:基站下传至移动设备q的传输时延表示为:其中, 是移动设备q中下行传输的个人任务n1, 是移动设备q中下行传输的共享任务n2;
结合(8)(9)(10)(11)式可得,所述移动设备q的任务在边缘服务器处理的总时延表示为:
基于上述分析,对于移动设备q,从任务开始上传到基站处理完下传至移动设备的整个端到端时延是本地处理时延和边缘服务器处理的总时延的最大值,表示为:
8.根据权利要求7所述的一种基于移动边缘计算的多用户多任务卸载方法,其特征在于,所述步骤2包括:
将最优的任务处理时延为目标以如下公式化表述为原始问题P1:
0≤λu,q≤1,0≤λd,q≤1,
0≤βq≤1,
其中, 和 是二进制卸载决策变量,λu,q、λd,q和βq是无线资源和计算资源分配变量, 是移动设备q任务处理的时延限制;
第一个约束表明了每个移动设备能处理任务的最大时延限制;第二个和第三个约束表明了频谱资源的分配限制;第四个和第五个约束表明了边缘服务器的计算资源的分配限制;第六个约束确保所有移动设备上传的共享任务的尺寸大小等于所有共享任务的尺寸大小;第七个约束确保了所有移动设备上传的共享任务的数量是N2;
所述原始问题P1是一个混合整数非线性规划问题,同时是一个最小化最大问题,是一个NP‑hard问题;
通过如下步骤求解所述原始问题P1:将最小化最大问题转化成求最小问题并将整数变量近似成连续变量;
考虑一种情景,假设一个问题如下:引入辅助变量η,则问题(14)转化为如下形式:s.t.f1(x)≤η,f2(x)≤η.(15),根据式(14)(15),引入辅助变量集合 将所述原始问题P1转化为求最小值问题;
将变量 和 转化为连续变量:所述原始问题P1转化为如下形式:
0≤λu,q≤1,0≤λd,q≤1,
0≤βq≤1,
所述非线性规划问题P2是一个非凸问题,其中约束 是非凸约束,通过采用连续凸逼近方法,将非凸约束进行转化;
引入辅助变量 将约束 分解为以下六个约束:约束(16)‑(20)都可以看成是 的形式;
假定有三个变量:a,b,c,有一个约束是 的形式,可以转成a≤bc的形式,进一步转化成
在每个点(bi,ci)的线性下界可以表示为:通过将 不等式右边替换成式(22),所述非线性规划问题P2可转化成一个凸优化问题P3:
0≤λu,q≤1,0≤λd,q≤1
0≤βq≤1,
定义 为每个参数在第i次迭代的值,通过不断迭代处理所述凸优化问题P3,可以渐近逼近所述非线性规划问题P2的解;获得所述凸优化问题P3最优的无线资源分配的解、最优的计算资源分配的解和最优的任务卸载策略;通过多次迭代之后,把获取的最优的任务卸载策略解投影到整数域获得整数解。
说明书 :
一种基于移动边缘计算的多用户多任务卸载方法
技术领域
背景技术
一些特定场景下,如:增强现实(Augmented Reality,AR)、云游戏等场景下,对任务处理的
时延要求非常高,这对网络处理任务的策略提出了新的挑战。移动边缘计算作为一种新的
通信及计算架构,将服务器设定在用户周围,使得用户与服务器之间的通信链路大大缩短,
并通过将移动设备中的任务卸载上传到邻近的边缘服务器进行处理,使其具备低延时,高
带宽的传输能力,有效缓解网络对于传输带宽和时延的要求。
基于能耗优化的资源分配方法,侧重点在于降低整个网络的功耗。然而文中只考虑一个移
动设备只有一个任务,且该任务是可分的,这意味着一个任务可以被无限划分,且在不同的
计算设备上进行处理。与文章【1】不同的是,文章【2】中移动设备上的计算任务是不可分的,
一个任务只能被移动设备自身处理或者迁移到边缘服务器进行处理,但作者没有将信道模
型考虑进系统中,缺少通信模块。除了通过移动边缘计算方法处理个人任务外,在多人AR场
景体验中,各个AR设备在处理个人任务的同时,还需要和其他AR设备处理一些共同的任务,
比如各个设备在同一个虚拟场景下,各个设备需要共同进行该虚拟场景的渲染处理等任
务,即各个设备还需处理共享任务。庞大的计算量加上现有网络通信容量的限制,使任务处
理时延较高,给用户的体验较差。
有效解决。
in in Proc.ICC,Shanghai,China,Jul.2019.
Chengdu,China,Dec.2018.
发明内容
题。
移动设备本地及边缘服务器的计算模型;
原始问题P1中的0‑1整数变量松弛成[0,1]的连续变量,并将最小化最大问题转化成求最小
的问题,所述原始问题P1便成为非线性规划问题P2;
任务,通过边缘服务器处理所述完整的共享任务,获得卸载到基站处理的共享任务处理结
果并下传至所述每个移动设备后,执行步骤2.11的操作;
理结果并下传至所述每个移动设备后,执行步骤2.11的操作;
卸载到基站处理的共享任务处理结果和卸载到基站处理的个人任务处理结果。
传的任务。
特;
基站处理的共享任务处理结果和卸载到基站处理的个人任务处理结果;
来等于一组完整的N2个共享任务,公式表述如下:
限制;第六个约束确保所有移动设备上传的共享任务的尺寸大小等于所有共享任务的尺寸
大小;第七个约束确保了所有移动设备上传的共享任务的数量是N2;
所示:
凸优化问题P3最优的计算资源分配的解,S 和S 是凸优化问题P3最优的任务卸载
策略;
用户多任务场景模型包括系统模型和模块模型;所述模块模型包括:任务模型、信道模型、
任务卸载模型和移动设备本地及边缘服务器的计算模型;步骤2,根据任务类别和任务卸载
策略对任务进行卸载,所述任务类别包括个人任务和共享任务,所述任务卸载策略以最优
的任务处理时延为目标求解获得。
解决。而采用前述方法,通过采用联合移动设备本地和边缘服务器进行同时处理的机制,相
对于将计算任务只放在本地处理和只卸载到边缘服务器进行处理,大大提高了处理效率,
减少了整个系统的任务处理时延,达到了提升系统处理速度的效果,进一步提升了用户体
验。
场景比现有技术相对复杂且更贴合实际情况。
调度问题提供新的思路,促进移动边缘计算领域的发展。
附图说明
可以根据这些附图获得其他的附图。
具体实施方式
每个AR设备运行时会产生大量的任务,而有限容量的通信网络使得任务处理时延较大,影
响用户体验。本发明的提出的策略和算法可以在现有网络条件下,有效减少任务处理时延,
提升用户体验。
方法,包括:
移动设备本地及边缘服务器的计算模型;
原始问题P1中的0‑1整数变量松弛成[0,1]的连续变量,并将最小化最大问题转化成求最小
的问题,所述原始问题P1便成为非线性规划问题P2;
任务,通过边缘服务器处理所述完整的共享任务,获得卸载到基站处理的共享任务处理结
果并下传至所述每个移动设备后,执行步骤2.11的操作;
理结果并下传至所述每个移动设备后,执行步骤2.11的操作;
卸载到基站处理的共享任务处理结果和卸载到基站处理的个人任务处理结果。本实施例
中,合并是指将本地处理的任务得到的计算结果和卸载到基站处理的任务得到的计算结果
放在一起,组成完整的移动设备初始需要处理任务的任务结果。
Server,MEC Server)、一个基站(Base Station,BS)以及所述基站服务的Q个移动设备
(Mobile Device,MD), 所述边缘服务器有计算和处理的功能。
传的任务。
特;
系统的带宽,所述移动设备q的上行链路的频谱效率eu,q表示为:
基站处理的共享任务处理结果和卸载到基站处理的个人任务处理结果;
站由边缘服务器处理;
ind
来等于一组完整的N2个共享任务,公式表述如下:
务的最大时延限制;第二个和第三个约束表明了频谱资源的分配限制;
了所有移动设备上传的共享任务的数量是N2。
间复杂度内归约到结果;
凸优化问题P3最优的计算资源分配的解,S 和S 是凸优化问题P3最优的任务卸载
策略;
任务不可分的情况下,用户和边缘服务器联合处理的时延优化问题。
用户多任务场景模型包括系统模型和模块模型;所述模块模型包括:任务模型、信道模型、
任务卸载模型和移动设备本地及边缘服务器的计算模型;步骤2,根据任务类别和任务卸载
策略对任务进行卸载,所述任务类别包括个人任务和共享任务,所述任务卸载策略以最优
的任务处理时延为目标求解获得。
解决。而采用前述方法,通过采用联合移动设备本地和边缘服务器进行同时处理的机制,相
对于将计算任务只放在本地处理和只卸载到边缘服务器进行处理,大大提高了处理效率,
减少了整个系统的任务处理时延,达到了提升系统处理速度的效果,进一步提升了用户体
验。
场景比现有技术相对复杂且更贴合实际情况。
调度问题提供新的思路,促进移动边缘计算领域的发展。
数的增加,曲线趋于收敛到一个固定值,证明SCA方法有效。
加,系统整体时延也随之增加的情况。可以看出,本地处理的方法需要消耗最多的时间,因
为本地移动设备的计算能力有限。受益于边缘服务器强大的计算能力,全部卸载方法的效
果要比本地处理方法好一点。因将本地计算资源和边缘服务器的计算资源联合协同,本发
明任务处理时延是最小的,也是最佳的。如图5所示,是本发明实施例部分提供的一种基于
移动边缘计算的多用户多任务卸载方法中不同数量的移动设备下系统平均时延对比图。展
示了随着移动设备数量的增加,移动设备的平均时延随之增加的情况。同样的,本发明的效
果是最好的。如图6所示,是本发明实施例部分提供的一种基于移动边缘计算的多用户多任
务卸载方法中不同边缘服务器的计算能力下系统整体时延对比图。展示了随着边缘服务器
的计算能力的增加,整个系统的处理时延随之减小的情况,可以看出,本发明的效果远远胜
于本地处理和全部卸载的方法。
动设备本地及边缘服务器的计算模型构成。本发明采用优化的方法解决多用户多任务卸载
策略问题,以整个系统总时延为优化目标,将问题表述成一个混合整数非线性规划问题。为
便于求解,本发明提出的方法将原始整数规划问题松弛成非整数规划问题,并通过连续凸
逼近方法将问题转化成凸优化问题进行求解。最终将求解获得的卸载决策映射到整数域,
获得本问题的最终解。通过验证,本发明提出的方法降低了整个系统的总时延,提升了移动
设备体验。且相较于其他卸载方案,本发明在模拟仿真中展现了更好的效果。
法的各实施例中的部分或全部步骤。所述的存储介质可为磁碟、光盘、只读存储记忆体(英
文:read‑only memory,简称:ROM)或随机存储记忆体(英文:random access memory,简称:
RAM)等。
说对现有技术做出贡献的部分可以以软件产品的形式体现出来,该计算机软件产品可以存
储在存储介质中,如ROM/RAM、磁碟、光盘等,包括若干指令用以使得一台计算机设备(可以
是个人计算机,服务器,或者网络设备等)执行本发明各个实施例或者实施例的某些部分所
述的方法。