一种边缘网络动态业务卸载和调度方法及装置与流程

专利2022-05-09  7



1.本发明涉及通信技术领域,尤其涉及一种边缘网络动态业务卸载和调度方法及装置。


背景技术:

2.移动边缘计算(mobile edge computing,mec)作为5g的关键技术之一,已成为推动智能化产品和应用的重要核心技术。mec通过在网络边缘部署边缘云或雾服务器,就近为终端设备提供便捷的云计算服务,可有效弥补终端设备计算能力的不足,并大大降低远程的移动云计算服务所带来的长传延时和回程链路流量负担。随着边缘网络的快速发展和部署,越来越多的新型智能化产品和应用将受益于mec。然而,由于边缘网络资源有限性,现有的边缘网络业务卸载和资源调度机制难以有效满足未来智能化产品和应用的海量连接和性能需求。
3.目前,针对边缘网络的业务卸载和资源调度问题研究中的实际网络环境和用户设备的动态性,包括无线网络环境的随机扰动、用户移动性和用户业务到达的随机性等,一些动态业务卸载和资源调度的研究,利用李雅普诺夫优化或马尔可夫理论,对动态网络环境下网络和用户的长期性能进行优化。但是,上述研究提出的动态业务卸载和资源调度方案应对动态网络环境和用户业务变化的鲁棒性和实用性不高。
4.因此,如何更好地实现动态业务卸载和资源调度,已成为业界关注的研究重点。


技术实现要素:

5.本发明提供一种边缘网络动态业务卸载和调度方法及装置,用以更好地实现动态业务卸载和资源调度。
6.本发明提供一种边缘网络动态业务卸载和调度方法,包括:
7.在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;
8.在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;
9.对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。
10.根据本发明提供的一种边缘网络动态业务卸载和调度方法,所述在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息的步骤,具体包括:
11.在所述当前滚动窗口的调度窗口内,采集网络状态变化信息和新增任务集信息;
12.根据所述网络状态变化信息,在所述当前滚动窗口的优化窗口内,对所述初始系统信息的网络状态信息进行更新,得到更新后的网络状态信息;
13.根据所述新增任务集信息,在所述当前滚动窗口的优化窗口内,对初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息。
14.根据本发明提供的一种边缘网络动态业务卸载和调度方法,对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案的步骤,具体包括:
15.根据所述更新后的系统信息,基于二层编码方法,生成多条染色体,作为初始种群;
16.其中,每条所述染色体的第一层序列为用户业务的子任务执行序列,第二层序列为卸载计算服务器指示序列;
17.基于所述初始种群进行遗传操作,在满足预设终止条件的情况下,获得最优染色体;
18.根据所述二层编码方法,对所述最优染色体进行解码,得到所述下一个滚动窗口的最优业务卸载和调度方案。
19.根据本发明提供的一种边缘网络动态业务卸载和调度方法,根据所述新增任务集信息,在所述当前滚动窗口的优化窗口内,对初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息的步骤,具体包括:
20.根据所述新增任务集信息,基于贪心算法,得到自适应调度方案信息;
21.根据所述自适应调度方案信息,对所述初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息。
22.根据本发明提供的一种边缘网络动态业务卸载和调度方法,所述当前滚动窗口的优化窗口,对当前滚动窗口的调度窗口所获取的系统信息进行更新的步骤之前,所述方法还包括:
23.根据预设时间间隔划分全局时间轴,得到多个滚动窗口;
24.其中,所述全局时间轴为按时间先后顺序执行用户业务的时间轴,每个所述滚动窗口均包括一个调度窗口和一个优化窗口。
25.根据本发明提供的一种边缘网络动态业务卸载和调度方法,所述得到当前滚动窗口更新后的系统信息的步骤之后,所述方法还包括:
26.根据所述当前滚动窗口的网络状态信息和下一个滚动窗口的网络状态信息,确定所述当前滚动窗口的平均用户信道增益和所述下一个滚动窗口的平均用户信道增益之间的差值;
27.根据所述差值与预设阈值,确定所述下一个滚动窗口的时间间隔调整信息。
28.根据本发明提供的一种边缘网络动态业务卸载和调度方法,所述方法还包括:
29.在所述当前滚动窗口的调度窗口内,监控到网络拓扑和用户集合大规模变化的情况下,重新获取系统信息,以建立新的业务卸载和调度模型;
30.对所述新的业务卸载和调度模型进行分析,得到当前所述调度窗口的最优业务卸载和调度方案。
31.本发明还提供一种边缘网络动态业务卸载和调度装置,包括:
32.模型建立模块,用于在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;
33.在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;
34.方案生成模块,用于对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。
35.本发明还提供一种电子设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,所述处理器执行所述程序时实现如上述任一种所述边缘网络动态业务卸载和调度方法的步骤。
36.本发明还提供一种非暂态计算机可读存储介质,其上存储有计算机程序,该计算机程序被处理器执行时实现如上述任一种所述边缘网络动态业务卸载和调度方法的步骤。
37.本发明提供的边缘网络动态业务卸载和调度方法及装置,通过对当前滚动窗口内的系统信息进行采集和更新,建立多目标计算卸载和任务调度问题优化模型,通过模型分析得到下一个滚动窗口的最优业务卸载和资源调度方案,以此逐步对各个滚动窗口区间进行业务卸载和资源调度优化,实现了将一个大规模或无限时段的全局优化复杂问题分解为一系列彼此相关的小规模局部优化子问题,从而大大降低了计算复杂度,并提高了动态业务卸载和资源调度方案应对动态网络环境和用户业务变化的鲁棒性和实用性。
附图说明
38.为了更清楚地说明本发明或现有技术中的技术方案,下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍,显而易见地,下面描述中的附图是本发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。
39.图1是本发明提供的边缘网络动态业务卸载和调度方法的流程示意图;
40.图2是本发明提供的实施例中基于遗传算法计算的双亲染色体编码示意图;
41.图3是本发明的实施例中基于贪心算法得到当前调度窗口的自适应调度方案的示意图;
42.图4是本发明提供的边缘网络动态业务卸载和调度方法的调度机制框架图;
43.图5是本发明提供的边缘网络动态业务卸载和调度装置的结构示意图;
44.图6是本发明提供的电子设备的结构示意图。
具体实施方式
45.为使本发明的目的、技术方案和优点更加清楚,下面将结合本发明中的附图,对本发明中的技术方案进行清楚、完整地描述,显然,所描述的实施例是本发明一部分实施例,而不是全部的实施例。基于本发明中的实施例,本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例,都属于本发明保护的范围。
46.图1是本发明提供的边缘网络动态业务卸载和调度方法的流程示意图,如图1所示,包括:
47.步骤s1,在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息。
48.具体地,本发明所描述的滚动窗口具有时间属性,具有时间间隔大小。滚动窗口内包含调度窗口和优化窗口。
49.随着时间推移,滚动窗口将不断滚动推进,在其时间间隔内,通过采集和更新系统信息,进行业务卸载和资源调度优化。
50.在本发明的实施例中,当前滚动窗口指的是在当前时刻,进行业务卸载和调度所
处的滚动窗口。
51.需要说明的是,本发明的方法适用于边缘网络中具有时序依赖业务特征的多业务多用户多基站网络场景;其中,本发明所描述的时序依赖业务指的是沿着时间线存在时间顺序依赖关系的用户业务。
52.在本发明的实施例中,网络中有多个基站m={1,2,

,m,

,m},每个基站配置有计算能力为的移动边缘服务器,可以为用户卸载的计算业务提供卸载后的计算服务。网络中存在随机移动且业务动态到达的用户u={1,2,

,鸪

,u},在第t个时间段内,每个用户的业务为随机到达,每个业务可包括多个需要按顺序执行的子业务。用户设备可支持多连接技术,同一个用户的多个业务可以通过多连接技术,通过不同基站卸载到不同的移动边缘服务器处进行处理。因此,将网络中的多个用户的所有业务进行统一编号,并将网络中多用户业务集合表示为service={1,2,

,k,

k},每个业务的子业务集合表示为
53.本发明的实施例利用三元组来表示每个子业务的服务需求{r
kl
,z
kl
,d
kl
,ta
kl
},其中,r
kl
表示子业务源数据大小,z
kl
表示子业务计算需求,d
kl
表示子业务最大容忍时延,指允许的完成子业务的最大时长,ta
kl
表示子业务到达时间。每个用户的每个子业务又可通过多连接技术卸载至不同的移动边缘服务器上执行,令a
kl
表示业务子业务卸载指示,其中a
kl
=0表示在本地执行,a
kl
=m表示通过子业务通过第m个基站卸载至其mec服务器上执行计算服务。
54.通过上述描述的网络信息和用户业务信息,不难理解的是,本发明的方法中的系统信息具体包括网络状态信息,如信道状态、网络拓扑、用户设备和服务器计算能力等信息,及用户业务信息,如新到达业务集、取消的业务集等信息。
55.进一步地,滚动窗口的调度窗口负责监控和采集上述系统信息;当前调度窗口的系统信息指的是在当前调度窗口内,调度窗口通过监控和采集获得的系统信息;初始系统信息指的是在当前调度窗口监控和采集系统信息之前,当前调度窗口从上个滚动窗口获得的系统信息;
56.滚动窗口的优化窗口负责通过用户和网络信息交互,对调度窗口内监控和采集的系统信息进行更新,具体为:
57.当调度窗口滚动至优化窗口区间时,优化窗口根据调度窗口采集的系统信息,对初始系统信息进行更新,得到更新后的系统信息;
58.本发明所描述的更新后的系统信息指的是在当前滚动窗口的初始系统信息基础上,根据采集的系统信息得到的当前滚动窗口最终系统信息。
59.步骤s2,在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型。
60.具体地,本发明所描述的业务卸载和调度模型是在滚动窗口内将计算卸载与业务调度在线优化子问题转换为一个多目标优化问题的模型。
61.综合考虑网络效率、资源成本和用户体验等多种衡量准则,本发明的方法利用加权法将多目标计算卸载和业务调度问题建模一个多目标优化问题。令c
k
表示用户u
k
应用完成总时间,e
k
表示用户u
k
应用完成能耗总开销,d
k
表示用户u
k
应用超过最低服务需求的拖期服务时延。
62.其中,用户u
k
应用各任务完成的总时间c
k
=maxk∈u,l∈tsk
k
{ckl},用户u
k
应用各任务超过最低服务需求的拖期服务时延d
k
=max{0,c
kl

d
kl
},c
kl
表示业务k的第l个业务完成时间。
63.相比静态调度,本发明的方法引入偏离度性能指标来尽量减少由于前后调度方案的改变所导致的资源偏差和调度开销,其中为第(i

1)调度窗口调度方案,为本次调度方案。因此,调度窗口计算卸载与业务调度在线优化子问题可以建模为一个多目标优化问题,该模型的目标函数为:
[0064][0065]
其中,α表示用户u
k
应用的延迟需求系数;β表示用户u
k
应用的能耗需求系数。α和β可以根据边缘网络的实际情况预先设定,其具体取值本发明实施例不作限制。执行任务对延迟和能耗的敏感程度,可以通过调节α和β的值来决定,γ为惩罚系数,γ的值由各个用户u
k
应用确定。
[0066]
在本发明的实施例中,对于每个调度窗口的业务卸载与资源调度在线优化子问题,一方面要考虑调度在用户体验和网络性能方面的有效性,另一方面还要衡量前后两次调度方案的稳定性,以避免用户的频繁切换和资源配置的大幅变动。同时,对于具有时序依赖的业务中子业务的卸载还需遵循业务间时序约束。
[0067]
进一步地,令需要在某业务之前执行的业务为此业务的紧前业务。令s
kl1
表示业务k的第l个业务数据传输开始时间,c
kl1
表示业务k的第l个业务数据传输完成时间,s
kl2
表示业务k的第l个业务计算服务开始时间,c
ki2
表示业务k的第l个业务计算服务完成时间,p
kl
表示业务k的第l个业务的紧前业务集合,则用户业务之间和业务卸载数据传输阶段和计算服务阶段之间存在的逻辑约束,即业务卸载和调度模型的约束条件可表示为:
[0068][0069][0070]
由此,根据更新后的系统信息,可以在当前优化窗口内建立业务卸载和调度模型。
[0071]
步骤s3,对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。
[0072]
具体地,本发明针对建立的多目标计算卸载与业务调度优化问题模型进行分析,可以采用遗传算法或深度强化学习算法对上述模型进行求解,以获得下一个滚动窗口的最优业务卸载和调度方案。
[0073]
本发明所描述的下一个滚动窗口是在当前滚动窗口调度区间时段结束后的下一个滚动窗口调度区间时段,二者在时间上是连续的;
[0074]
在本发明的实施例中,最优业务卸载和调度方案指的是用户业务各子任务的最优调度次序和各子任务对应的卸载计算服务器指示位置。
[0075]
通过本发明实施例提供的方法,对当前滚动窗口内的系统信息进行采集和更新,建立多目标计算卸载和业务调度问题优化模型,通过模型分析得到下一个滚动窗口的最优业务卸载和资源调度方案,以此逐步对各个滚动窗口区间进行业务卸载和资源调度优化,
实现了将一个大规模或无限时段的全局优化复杂问题分解为一系列彼此相关的小规模局部优化子问题,从而大大降低了计算复杂度,并提高了动态业务卸载和资源调度方案应对动态网络环境和用户业务变化的鲁棒性和实用性。
[0076]
基于上述任一实施例,所述在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息的步骤,具体包括:
[0077]
在所述当前滚动窗口的调度窗口内,采集网络状态变化信息和新增业务集信息;
[0078]
根据所述网络状态变化信息,在所述当前滚动窗口的优化窗口内,对所述初始系统信息的网络状态信息进行更新,得到更新后的网络状态信息;
[0079]
根据所述新增业务集信息,在所述当前滚动窗口的优化窗口内,对初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息。
[0080]
具体地,本发明所描述的网络状态变化信息,包括信道状态、网络拓扑、用户设备和服务器计算能力等的变化;新增业务集信息包括上述描述的新到达用户业务集和取消的用户业务集。其中,新到达用户业务集指的是用户新增需要进行卸载和调度处理的业务子任务的集合;取消的用户业务集指的是用户需要取消卸载和调度处理的业务子任务的集合。
[0081]
进一步,在当前滚动窗口的优化窗口内,根据信道状态、网络拓扑、用户设备和服务器计算能力等的变化信息,对初始系统信息的网络状态信息进行更新,得到更新后的网络状态信息;根据新到达用户业务集和取消的用户业务集,对初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息。
[0082]
针对上述描述的信息,为了便于后续算法的执行,本发明的实施例在系统中在每个滚动窗口间隔内主要收集、更新和维护以下几种数据:
[0083]
网络环境数据,包括用户到各个基站的无线信道增益矩阵g,用户设备可用计算资源矩阵f
local
,mec服务器可用计算资源矩阵f
mec
,用户设备可用计算资源时间矩阵t
local
,基站可用无线资源时间矩阵t
bs
,mec服务器可用计算资源时间矩阵t
mec

[0084]
网络拓扑数据,包括可用基站/服务器集合m,用户集合u;
[0085]
用户业务信息数据,包括业务状态表serive_list(包括用户编码,业务编码,子业务编码,子业务状态,子业务需求)和调度方案执行状况。
[0086]
通过本发明的实施例,通过用户和网络信息交互,将调度窗口时段监控和采集的网络环境数据、网络拓扑数据和用户业务信息数据,在优化窗口时段进行更新,得到当前滚动窗口时段最终的系统信息数据,便于后续模型的计算和分析。
[0087]
基于上述任一实施例,对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案的步骤,具体包括:
[0088]
根据所述更新后的系统信息,基于二层编码方法,生成多条染色体,作为初始种群;
[0089]
其中,每条所述染色体的第一层序列为用户业务的子业务执行序列,第二层序列为卸载计算服务器指示序列;
[0090]
基于所述初始种群进行遗传操作,在满足终止条件的情况下,获得最优染色体;
[0091]
根据所述二层编码方法,对所述最优染色体进行解码,得到所述下一个滚动窗口的最优业务卸载和调度方案。
[0092]
具体地,在本发明的实施例中,可以利用遗传算法来求解业务卸载和调度模型。
[0093]
在遗传算法中,每个解决方案可以由染色体定义,本实施例采用分段编码方法来定义染色体。
[0094]
编码方法是遗传算法的关键,变异概率和交叉概率都受到编码方法的影响,因此编码问题极大的影响了遗传计算的效率。
[0095]
因此,本发明的实施例采取基于业务执行顺序的表达方法,对染色体采用二层编码方法,第一层表示用户业务的子业务执行序列o,第二层表示卸载计算服务器指示a。染色体可以表示为:
[0096]
i
i
=[o
i
;a
i
];
ꢀꢀꢀꢀꢀꢀ
(4)
[0097]
进一步地,根据更新后的系统信息,基于二层编码方法,可以生成多条染色体,作为初始种群。在本发明的实施例中,设定多条染色体的数量为n,则可产生n个初始解,每个解都是一种业务卸载和资源调度的方式,上述n种方式都可以视为初始种群。其中,n为预设值,可以根据遗传算法的控制参数进行设定,可以设为50,100,150等。
[0098]
图2是本发明提供的实施例中基于遗传算法计算的双亲染色体编码示意图,如图2所示,本发明实施例采取基于业务执行顺序的表达方法,对染色体采用二层编码方法。
[0099]
如图2所示,双亲染色体if1,2,1,3,2,3;0,2,1,0,1,2}由两部分组成,即业务处理序列向量o
i
={1,2,1,3,2,3}和业务卸载决策向量a
i
={0,2,1,0,1,2}。在o
i
中,用第一个1来表示业务1的第一个业务tsk
11
,用第二个1来表示业务1的第二个业务t
12
。因此,描述的o
i
的业务处理序列为{tsk
11
,tsk
21
,tsk
12
,tsk
31
,tsk
22
,tsk
32
}。在a
i
中,业务卸载决策向量按照移动设备的业务号依次进行编码,可以解释为{a
11
=0,a
12
=2,a
21
=1,a
22
=0,a
31
=1,a
32
=2}。基于o
i
和a
i
,可以识别出每个业务的紧前业务集,并计算出问题优化目标值。
[0100]
基于初始种群进行遗传操作,在满足预设终止条件的情况下,获得最优染色体。
[0101]
本发明所描述的预设终止条件包括预设的收敛条件,或者预设的迭代最大次数。
[0102]
在本发明的实施例中,为了评价每个解的质量,使用目标函数(1)来计算每个染色体的适应度值。适应度函数定义如下:
[0103][0104]
其中,g是一个常值,它足够大,保证适应度是非负的。
[0105]
具体地,遗传算法寻找最优解的过程就是遗传操作的过程,主要包括三个遗传操作分别是选择操作、交叉操作和变异操作。
[0106]
对于选择操作,可以采用轮盘赌的选择方法来选择较优的解,在选择操作中,从初始种群的n个染色体中选择适合度最佳的染色体。
[0107]
轮盘赌的一般步骤为:
[0108]
步骤1、计算种群p中所有个体的适应度,求出总适应度:
[0109][0110]
其中,f(x
m
)为第m位个体适应度值;
[0111]
步骤2、计算染色体的选择概率:
[0112][0113]
步骤3、计算个体的累计概率q
n
,相当于转盘上的“跨度”,“跨度”越大越容易被选
到:
[0114][0115]
步骤4、随机产生一个[0,1]之间的数θ;
[0116]
步骤5、如果θ≤q1,则选择第一条染色体x1,否则,如果q
m
‑1<θ≤q
m
,则选择第m条染色体(2≤m≤n)。
[0117]
适应度可以根据上述预先设计的适应度函数计算获得。
[0118]
对于交叉操作,交叉的目的是利用双亲个体经过一定操作组合后产生新个体,特征的有效继承性保证了双亲个体的信息传到子代。
[0119]
在本发明实施例中,对双亲染色体进行交叉操作,在o和a的相应位置交换随机选择的基因片段。但是,由于染色体中o的数据特征,交叉操作可能会造成数据冗余,丢失部分业务处理序列信息。在这种情况下,为了保证子代染色体中业务处理序列的可行性和有效性,可检查冗余的基因位置,并用缺失的基因数据进行补充。
[0120]
如图2所示,随机交换染色体i和染色体(i 1)中o
i
的第二列到第四列,a
i
的第三列到第五列的基因片段。在本发明的实施例中,经过检查,发现o的最后一个基因数据在子代染色体i和(i 1)中都是冗余的。同时,tsk
13
基因数据在子代i染色体中缺失,tsk
33
基因数据在子代(i 1)染色体中缺失。因此,可以将1、3分别填充到子代染色体i和(i 1)的冗余基因位置。
[0121]
对于变异操作,变异的目的是通过随机改变染色体的某些基因,对染色体进行较小扰动来生成新的个体,增加种群多样性。
[0122]
在本发明的实施例中,对于变异,可以包括两种方式。
[0123]
第一种方式是对于第一层编码o,随机选择染色体中的两个基因位,采用互换变异,然后根据第一层编码的交换基因位进行第二层编码的变化,改变卸载计算服务器指示位置。
[0124]
第二种方式是直接对第二层编码a进行变异,改变卸载计算服务器指示位置。
[0125]
进一步地,通过交叉和变异操作,生成子代群体。将双亲群体和子代群体合并到新的群体中,并根据计算出的适合度按降序对所有染色体进行排序。根据自然进化原理,将适应度差的染色体剔除,只在新种群中保留一定数量的适应度好的染色体。基于上述种群进化算法,重复进行适应度计算、选择操作、交叉操作和变异操作,直到达到预设终止条件,获得最优染色体。
[0126]
利用二层编码方法,对最优染色体进行相应调度方案解码,得到下一个滚动窗口的最优业务卸载和调度方案。
[0127]
通过本发明的实施例,根据遗传算法,求解业务卸载和调度模型,获取下一个滚动窗口的最优业务卸载和调度方案的步骤具体可以表示为:
[0128]
步骤1、产生规模为n的初始种群p0;
[0129]
步骤2、对种群p0进行解码,得到业务卸载和资源调度方案s;
[0130]
步骤3、根据业务卸载和调度方案计算目标函数;
[0131]
步骤4、计算种群p0的适应度;
[0132]
步骤5、采用轮盘赌的选择方法从种群中选择较优的个体组成配对种群p1;
[0133]
步骤6、对种群p1实施遗传操作,包括选择操作、交叉操作和变异操作,生成子代种
群p2;
[0134]
步骤7、对子代种群p2根据业务卸载和调度方案计算目标函数;
[0135]
步骤8、在种群p0中重新插入子种群以替代双亲,输出插入后的当前种群的个体以及插入后当代的个体的目标值;
[0136]
步骤9、若满足收敛条件,或者达到迭代次数则终止运算,否则返回步骤4。
[0137]
通过本发明实施例的方法,基于遗传算法,对多目标业务计算卸载和业务调度优化问题模型进行计算和分析,得到下一个滚动窗口的最优业务卸载和调度方案。
[0138]
基于上述任一实施例,根据所述新增业务集信息,在所述当前滚动窗口的优化窗口内,对初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息的步骤,具体包括:
[0139]
根据所述新增业务集信息,基于贪心算法,得到自适应调度方案信息;
[0140]
根据所述自适应调度方案信息,对所述初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息。
[0141]
具体地,在本发明实施例中,新增业务集信息包括新到达用户业务集和取消的用户业务集;本发明所描述的自适应调度方案信息表示自适应调度方案对应的用户业务信息。
[0142]
进一步地,对于调度窗口期间新到达的业务,为了能够在调度窗口期自适应地提供调度服务,对新到达的业务进行业务编码,利用贪心算法,生成其对应的初始调度方案信息。
[0143]
本发明实施例中,本发明所描述的新到达的业务即为新增业务集信息。
[0144]
通过本发明的实施例,生成自适应调度方案信息的具体步骤如下:
[0145]
对新到达的业务进行业务编码,并按照业务达到先后顺序将新到达业务的所有子业务加入到当前调度窗口的原调度方案的用户子业务执行序列o之后。
[0146]
按照此子业务执行时序,分别计算不同卸载决策下目标函数(1)的函数值大小,基于贪心算法,选取最小目标函数值所对应的初始调度方案信息中的卸载决策加入到当前调度窗口的原调度方案的卸载计算服务器指示序列a之后。
[0147]
由此,将新到达业务的初始调度方案信息加入到当前窗口的原调度方案信息之后,得到自适应调度方案信息。
[0148]
本发明的实施例中,对生成的自适应方案进行解码,得到自适应方案对应的用户业务信息,进而对初始系统信息的用户业务信息进行更新,即可得到更新后的用户业务信息。
[0149]
通过本发明实施例的方法,对于调度窗口期间新到达的业务,基于贪心算法,能够在调度窗口期自适应地提供调度服务。
[0150]
图3是本发明的实施例中基于贪心算法得到当前调度窗口的自适应调度方案的示意图,如图3所示,当前调度窗口的原调度方案,即上一个滚动窗口的优化窗口生成的最优调度方案schedule为{1,2,3,1,3,2;0,1,2,2,1,2};新到达业务编码为4,有2个相关子业务,基于贪心算法,计算不同决策下目标函数(1)函数值大小,选取最小目标函数值所对应的初始调度决策分别为{a
41
=0,a
42
=2},故将新到达业务的初始调度决策加入到原调度方案之后生成自适应调度方案schedule*为{1,2,3,1,3,2,4,4;0,1,2,2,1,2,0,2}。
[0151]
基于上述任一实施例,所述当前滚动窗口的优化窗口,对当前滚动窗口的调度窗口所获取的系统信息进行更新的步骤之前,所述方法还包括:
[0152]
根据预设时间间隔划分全局时间轴,得到多个滚动窗口;
[0153]
其中,所述全局时间轴为按时间先后顺序执行用户业务的时间轴,每个所述滚动窗口均包括一个调度窗口和一个优化窗口。
[0154]
具体地,为了将一个大规模或无限时段的全局优化复杂问题分解为一系列彼此相关的小规模局部优化子问题,在本发明的实施例中,将整个动态调度过程划分为多个连续的静态调度区间。
[0155]
进一步地,以δt为单位时间间隔,将按时间先后顺序执行用户业务的全局时间轴划分为多个滚动窗口。每个滚动窗口根据功能分为两个基本子窗口:优化窗口和调度窗口。
[0156]
通过本发明的实施例,该滚动窗口重调度方法可以在线优化每个调度区间,使得系统在各调度区间内能够达到局部最优,从而使得业务卸载和资源调度方案能够适应复杂多变的动态用户和网络环境变化。
[0157]
基于上述任一实施例,所述得到当前滚动窗口更新后的系统信息的步骤之后,所述方法还包括:
[0158]
根据所述当前滚动窗口的网络状态信息和下一个滚动窗口的网络状态信息,确定所述当前滚动窗口的平均用户信道增益和所述下一个滚动窗口的平均用户信道增益之间的差值;
[0159]
根据所述差值与预设阈值,确定所述下一个滚动窗口的时间间隔调整信息。
[0160]
具体地,本发明所描述的下一个滚动窗口的时间间隔调整信息指的是经过优化调整,所得的下一个滚动窗口的时间间隔具体数值。
[0161]
进一步地,通过实时监控当前滚动窗口和下一个滚动窗口的网络状态信息,可以获取当前滚动窗口的平均用户信道增益值和下一个滚动窗口的平均用户信道增益值,从而确定二者的差值,来判断网络环境的动态性。
[0162]
在本发明的实施例中,下一个滚动窗口的时间间隔调整优化的步骤,具体如下:
[0163]
设定m为常量整数;g_threshold为预设阈值,即为信道增益差值阈值门限;time_down为时间间隔下调步长,time_up为时间间隔上调步长。
[0164]
若当前滚动窗口和下一个滚动窗口区间的平均用户信道增益差值连续m次大于设定阈值g_threshold时,可判断此网络环境具有较高动态性,则将下一个滚动窗口时间间隔δt调减一个time_down的长度,以此缩短下一个滚动窗口时间间隔;
[0165]
若当前滚动窗口和下一个滚动窗口区间的平均用户信道增益差值连续m次小于设定阈值g_threshold时,可判断此网络环境具有较低动态性,则将下一个滚动窗口时间间隔δt调增一个time_up的长度,以此延长下一个滚动窗口时间间隔。
[0166]
本发明实施例的方法,通过监控前后两个滚动窗口的平均用户信道增益差值来判断网络环境的动态性,从而自适应调整滚动窗口区间的时间间隔。
[0167]
基于上述任一实施例,所述方法还包括:
[0168]
在所述当前滚动窗口的调度窗口内,监控到网络拓扑和用户集合大规模变化的情况下,重新获取系统信息,以建立新的业务卸载和调度模型;
[0169]
对所述新的业务卸载和调度模型进行分析,得到当前所述调度窗口的业务卸载和
调度方案。
[0170]
具体地,本发明所描述的网络拓扑和用户集合大规模变化,也称为重调度触发事件,进而在当前滚动窗口的调度窗口内,监控到重调度触发事件的情况下,重新获取系统信息。
[0171]
本发明所描述的重新获取系统信息是当前调度窗口通过重新监控和采集得来的系统信息。
[0172]
由调度窗口进入优化窗口后,当前优化窗口将根据重新获取的系统信息,建立新的业务卸载和调度模型,进而通过遗传算法或深度强化学习等优化算法,对新的业务卸载和调度模型进行优化分析,得到当前调度窗口的最优业务卸载和调度方案。
[0173]
通过本发明实施例的方法,在监控到网络拓扑和用户集合大规模变化,需要紧急重调度的事件,如基站或设备故障,则启动调度窗口内调度方案优化决策,实现调度窗口期间自适应提供服务的目的。
[0174]
图4是本发明提供的边缘网络动态业务卸载和调度方法的调度机制框架图,如图4所示,全局时间轴以时间间隔δt划分为多个滚动窗口,当前滚动窗口为第(i

1)个滚动窗口,下一个滚动窗口为第i个滚动窗口,第(i

1)个滚动窗口包括第(i

1)个调度窗口和第(i

1)个优化窗口,第(i)个滚动窗口包括第(i)个调度窗口和第(i)个优化窗口。
[0175]
如图4所示,在第(i

1)个调度窗口内,进行信息收集与监控,其中所述信息包括网络拓扑信息、网络环境信息和业务信息。另外,还负责业务编码与预决策,即通过业务编码和贪心预决策算法,针对新到达业务得到其对应的初始调度方案信息,进而生成自适应调度方案;
[0176]
随着时间推移,调度窗口时段结束,进入到优化窗口时段的预测时刻,在第(i

1)个优化窗口内,根据调度窗口内收集和监控的信息对网络信息进行更新,包括用户/基站集合更新、信道增益和节点资源状态更新和业务信息更新;可选的,优化窗口内可以进行窗口间隔调整,得到第(i)个滚动窗口的时间间隔。在获得更新后的网络信息后,优化窗口内开始进行调度窗口任务卸载和资源调度子问题优化,通过建立多目标计算卸载和任务调度优化问题模型,可利用遗传算法等优化算法,对调度窗口资源受限多目标优化问题求解,得到下一个滚动窗口即第(i)个调度窗口的最优业务卸载和调度方案,以在优化窗口时段的重调度时刻之后,第(i)个调度窗口执行该最优业务卸载和调度方案。
[0177]
在第(i

1)个调度窗口内,若监控到重调度若监控到重调度触发事件,如网络拓扑和用户集合的大规模变化,则立即重启计算卸载和任务调度的优化程序,即根据重新收集和监控的系统信息,建立多目标计算卸载和任务调度优化问题模型,利用遗传算法等优化算法,对调度窗口资源受限多目标优化问题求解,得到第(i)个调度窗口的最优业务卸载和调度方案。
[0178]
图5是本发明提供的边缘网络动态业务卸载和调度装置的结构示意图,如图5所示,本发明提供的边缘网络动态业务卸载和调度装置,包括:
[0179]
模型建立模块510,用于在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;
[0180]
在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;
[0181]
方案生成模块520,用于对所述业务卸载和调度模型进行分析,得到下一个滚动窗
口的最优业务卸载和调度方案。
[0182]
本发明提供的边缘网络动态业务卸载和调度装置,通过对当前滚动窗口内的系统信息进行采集和更新,建立多目标计算卸载和任务调度问题优化模型,通过模型分析得到下一个滚动窗口的最优业务卸载和资源调度方案,以此逐步对各个滚动窗口区间进行业务卸载和资源调度优化,实现了将一个大规模或无限时段的全局优化复杂问题分解为一系列彼此相关的小规模局部优化子问题,从而大大降低了计算复杂度,并提高了动态业务卸载和资源调度方案应对动态网络环境和用户业务变化的鲁棒性和实用性。
[0183]
本发明描述的边缘网络动态业务卸载和调度装置与上文描述的边缘网络动态业务卸载和调度方法可相互对应参照,故此处不再赘述。
[0184]
图6是本发明提供的电子设备的结构示意图,如图6所示,该电子设备可以包括:处理器(processor)610、通信接口(communications interface)620、存储器(memory)630和通信总线640,其中,处理器610,通信接口620,存储器630通过通信总线640完成相互间的通信。处理器610可以调用存储器630中的逻辑指令,以执行所述边缘网络动态业务卸载和调度方法,该方法包括:在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。
[0185]
此外,上述的存储器630中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时,可以存储在一个计算机可读取存储介质中。基于这样的理解,本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来,该计算机软件产品存储在一个存储介质中,包括若干指令用以使得一台计算机设备(可以是个人计算机,服务器,或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括:u盘、移动硬盘、只读存储器(rom,read

only memory)、随机存取存储器(ram,random access memory)、磁碟或者光盘等各种可以存储程序代码的介质。
[0186]
另一方面,本发明还提供一种计算机程序产品,所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序,所述计算机程序包括程序指令,当所述程序指令被计算机执行时,计算机能够执行上述各方法所提供的所述边缘网络动态业务卸载和调度方法,该方法包括:在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。
[0187]
又一方面,本发明还提供一种非暂态计算机可读存储介质,其上存储有计算机程序,该计算机程序被处理器执行时实现以执行上述各方法提供的所述边缘网络动态业务卸载和调度方法,该方法包括:在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。
[0188]
以上所描述的装置实施例仅仅是示意性的,其中所述作为分离部件说明的单元可
以是或者也可以不是物理上分开的,作为单元显示的部件可以是或者也可以不是物理单元,即可以位于一个地方,或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下,即可以理解并实施。
[0189]
通过以上的实施方式的描述,本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现,当然也可以通过硬件。基于这样的理解,上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来,该计算机软件产品可以存储在计算机可读存储介质中,如rom/ram、磁碟、光盘等,包括若干指令用以使得一台计算机设备(可以是个人计算机,服务器,或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。
[0190]
最后应说明的是:以上实施例仅用以说明本发明的技术方案,而非对其限制;尽管参照前述实施例对本发明进行了详细的说明,本领域的普通技术人员应当理解:其依然可以对前述各实施例所记载的技术方案进行修改,或者对其中部分技术特征进行等同替换;而这些修改或者替换,并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征:
1.一种边缘网络动态业务卸载和调度方法,其特征在于,包括:在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。2.根据权利要求1所述的边缘网络动态业务卸载和调度方法,其特征在于,所述在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息的步骤,具体包括:在所述当前滚动窗口的调度窗口内,采集网络状态变化信息和新增任务集信息;根据所述网络状态变化信息,在所述当前滚动窗口的优化窗口内,对所述初始系统信息的网络状态信息进行更新,得到更新后的网络状态信息;根据所述新增任务集信息,在所述当前滚动窗口的优化窗口内,对初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息。3.根据权利要求1所述的边缘网络动态业务卸载和调度方法,其特征在于,对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案的步骤,具体包括:根据所述更新后的系统信息,基于二层编码方法,生成多条染色体,作为初始种群;其中,每条所述染色体的第一层序列为用户业务的子任务执行序列,第二层序列为卸载计算服务器指示序列;基于所述初始种群进行遗传操作,在满足预设终止条件的情况下,获得最优染色体;根据所述二层编码方法,对所述最优染色体进行解码,得到所述下一个滚动窗口的最优业务卸载和调度方案。4.根据权利要求2所述的边缘网络动态业务卸载和调度方法,其特征在于,根据所述新增任务集信息,在所述当前滚动窗口的优化窗口内,对初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息的步骤,具体包括:根据所述新增任务集信息,基于贪心算法,得到自适应调度方案信息;根据所述自适应调度方案信息,对所述初始系统信息的用户业务信息进行更新,得到更新后的用户业务信息。5.根据权利要求1所述的边缘网络动态业务卸载和调度方法,其特征在于,所述当前滚动窗口的优化窗口,对当前滚动窗口的调度窗口所获取的系统信息进行更新的步骤之前,所述方法还包括:根据预设时间间隔划分全局时间轴,得到多个滚动窗口;其中,所述全局时间轴为按时间先后顺序执行用户业务的时间轴,每个所述滚动窗口均包括一个调度窗口和一个优化窗口。6.根据权利要求1所述的边缘网络动态业务卸载和调度方法,其特征在于,所述得到当前滚动窗口更新后的系统信息的步骤之后,所述方法还包括:根据所述当前滚动窗口的网络状态信息和下一个滚动窗口的网络状态信息,确定所述当前滚动窗口的平均用户信道增益和所述下一个滚动窗口的平均用户信道增益之间的差
值;根据所述差值与预设阈值,确定所述下一个滚动窗口的时间间隔调整信息。7.根据权利要求1所述的边缘网络动态业务卸载和调度方法,其特征在于,所述方法还包括:在所述当前滚动窗口的调度窗口内,监控到网络拓扑和用户集合大规模变化的情况下,重新获取系统信息,以建立新的业务卸载和调度模型;对所述新的业务卸载和调度模型进行分析,得到当前所述调度窗口的最优业务卸载和调度方案。8.一种边缘网络动态业务卸载和调度装置,其特征在于,包括:模型建立模块,用于在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;在当前所述优化窗口内,根据所述更新后的系统信息,建立业务卸载和调度模型;方案生成模块,用于对所述业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。9.一种电子设备,包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序,其特征在于,所述处理器执行所述程序时实现如权利要求1至7任一项所述边缘网络动态业务卸载和调度方法的步骤。10.一种非暂态计算机可读存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器执行时实现如权利要求1至7任一项所述边缘网络动态业务卸载和调度方法的步骤。
技术总结
本发明提供一种边缘网络动态业务卸载和调度方法及装置,包括:在当前滚动窗口的优化窗口内,根据当前调度窗口的系统信息对初始系统信息进行更新,得到更新后的系统信息;在当前优化窗口内,根据更新后的系统信息,建立业务卸载和调度模型;对业务卸载和调度模型进行分析,得到下一个滚动窗口的最优业务卸载和调度方案。本发明的方法通过对当前滚动窗口内的系统信息进行采集和更新,建立多目标计算卸载和任务调度问题优化模型,通过模型分析得到下一个滚动窗口的最优调度方案,以此逐步对各个滚动窗口进行业务卸载和资源调度优化,大大降低了计算复杂度,并提高了动态业务卸载和资源调度方案应对动态网络环境和用户业务变化的鲁棒性和实用性。鲁棒性和实用性。鲁棒性和实用性。


技术研发人员:孙阳 李慧欣 王朱伟 吴文君 方超 李萌 司鹏搏 张延华
受保护的技术使用者:北京工业大学
技术研发日:2021.03.23
技术公布日:2021/7/15

转载请注明原文地址:https://doc.8miu.com/read-650201.html

最新回复(0)