利索能及
我要发布
收藏
专利号: 2022111840248
申请人: 重庆邮电大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-04-09
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种移动感知的微服务部署方法,其特征在于,该方法包括以下步骤:S1:确定系统的MEC网络结构以及边缘服务器的计算资源容量;

S2:构建微服务链模型、请求模型以及传输路径模型,根据Dijkstra算法找到最佳传输路径,具体包括以下步骤:S21:针对时延敏感型业务,定义 为微服务链, 为组成微服务链的微服务,微服务部署在边缘服务器上消耗的计算资源量为fl;

S22:定义用户发出的请求为一个三元组 包括所需的微服务链 最大容忍时延ζ和任务大小D0;假设在当前时间帧中,边缘服务器u的覆盖范围内用户服从速率为λu的泊松到达过程,且用户从边缘服务器i到边缘服务器j的移动概率为 表示边缘服务器集合;

S23:定义从边缘服务器i到边缘服务器j的数据传输路径为ψi,j=ψ0,ψ1,…,ψl,…,ψL1,ψ0=i,ψL1j,其中,ψl为处理任务的第l个微服务所在的边缘服务器;

S24:假设从边缘服务器i到边缘服务器j的最佳传输路径为 首先将原始网络拓扑图映射为按微服务分级的多级分裂边权图,然后通过计算对应的多级分裂边权图上源节点到目的节点之间的最短径来获得S3:构建请求时延模型:根据排队论进行排队时延分析,同时结合无线传输时延以及光纤链路传输时延建立传输时延模型,并加上处理时延得到请求时延Ti,j;具体包括以下步骤:S31:假设当前的服务部署方案为x=(x1,1,x1,2,…,xu,l,…,xV,L),其中xu,l表示边缘服务器u上部署了微服务l的个数,xu,l需要满足约束:S32:定义在部署方案x下能被成功服务的请求数为ω=(ω1,1,ω1,2,…,ωi,j,…,ωV,V),其中ωi,j表示当前时间帧内,从边缘服务器i移动到边缘服务器j的用户发出的所有请求中,能够被成功服务的数量,需要满足约束:其中,λi为边缘服务器i的覆盖范围内用户的到达率;

S33:请求时延包含微服务处的排队时延,数据传输时延以及微服务的处理时延,即从边缘服务器i移动到边缘服务器j的请求产生的时延模型构建如下:其中, 为传输时延, 为处理时延, 为排队时延;

时延需要满足约束:

Ti,J≤ζ

其中,ζ为请求的时延容忍阈值;

构建排队时延 具体包括:根据排队论,对于边缘服务器u内微服务l处的排队系统,平均排队队长为:其中, 表示无请求在排队系统中的概率,计算公式为:

其中,ρu,l表示节点的服务利用率,由请求到达率与任务处理速率的比值得到:其中,μl表示微服务l的数据处理速率,ηu,l表示请求到达率,定义为网络中所有请求的传输路径中经过边缘服务器u的请求量总和:为了使得队列能在有限时间范围内被服务完,需要保证服务利用率小于1,即需满足以下不等式约束:ρu,l<l

根据little定理,边缘服务器u内微服务l处请求的平均排队时间Wu,l计算如下:当不满足约束时,通过在ρu,l上叠加一个θ去除约束项,其中,θ是一个足够大的正整数;

当满足约束时,通过叠加请求的传输路径中经过的微服务上所需的所有平均排队时间Wu,l得到排队时延;最后,传输路径为 的请求的排队时延 计算如下:构建的传输时延 包括:用户到源节点的无线传输时延D0/ri、目的节点到用户的无线传输时延DL/rj以及从边缘服务器ψl到边缘服务器ψl+1的光纤链路传输时延 总传输时延计算如下:其中,ri、rj分别表示用户与边缘服务器i、j之间的无线传输速率,DL表示目的节点到用户的任务大小;在传输路径中,若当前节点ψl与下一个节点ψl+1不同,则传输时延为数据包通过节点ψl与ψl+1之间的传输链路产生的时延,表示为 相同时,表明数据包在同一个边缘服务器上进行了不同微服务的处理,则传输时延为0;链路传输时延 计算如下:其中, 为从边缘服务器ψl到边缘服务器ψl+1的链路传输带宽;

构建的处理时延 是请求所需微服务上的处理时延之和,表达式如下:其中,μl表示微服务l的数据处理速率;

S4:建立服务质量最大化和部署成本最小化的目标函数,将成本和服务质量双目标要求下的微服务部署方案构建为一个约束多目标优化问题模型,具体包括以下步骤:S41:定义服务质量R为能实现的请求成功数与请求总数的比值:S42:定义边缘服务器每单位计算资源成本为c,则总部署成本C计算如下:S43:构建多目标优化问题:将成本和服务质量双目标要求下的微服务部署方案问题描述如下的约束多目标优化问题:其中, 表示自然数集合;

S5:采用罚函数将原始约束多目标优化问题转化为多目标优化问题,具体包括以下步骤:S51:采用MOEA‑PM算法求解步骤S43的问题P:首先采用罚函数将P转化为MOPP′,然后采用MOEA求解P′;

S52:偏差计算公式:由于问题P的约束(1)、(2)、(4)通过设置变量的上下界来实现,因此需要去除的是约束(3)和约束(5);对应的偏差计算公式如下:ξ1=||fl×x‑fu||∞,ξ2=||T‑ξ||∞

其中,fl=f1,…,fl,…,fL]为微服务消耗的计算资源组成的向量,fu=f1,…,fu,…,fV]为边缘服务器的计算资源容量组成的向量, 是请求响应时延矩阵,ζ是维度为V×V元素全为ζ的方阵;

S53:构造惩罚函数:对于目标1,由于是最大化请求成功率,那么构造的关于约束项的惩罚函数应为关于偏差的单减函数,且惩罚函数的最大值必须小于原函数的最小值;对于目标2,由于是最小化成本,那么构造的关于约束项的惩罚函数应为关于偏差的单增函数,且函数的最小值必须大于原函数的最大值;

S54:适应度函数:对于目标1,由于其原函数R的变化范围为[0,1],设置ζ1对应的惩罚函数的变化范围为(1,2],2对应的惩罚函数的变化范围为(0,1];对于目标2,由于其原函数C的变化范围为[0,cmax],其中cmax表示最大成本,设置ζ1对应的惩罚函数的变化范围为2·cmax,4·cmax],ζ2对应的惩罚函数的变化范围为cmax,2·cmax];得到的分段罚函数如下所示:其中,tmax表示请求响应时延超过时延阈值的最大可能值;改进的无约束问题如下:S6:采用带惩罚机制的进化算法MOEA‑PM求解多目标优化问题,通过繁殖和迭代找到原始问题的Pareto最优解集,直到算法收敛,则整个算法结束。

2.根据权利要求1所述的微服务部署方法,其特征在于,步骤S6具体包括以下步骤:S61:初始化:假设种群大小为K,对每个基因在其取值范围内随机取值进行种群初始化;

S62:非支配排序:采用快速非支配排序算法对种群进行非支配排序和拥挤度排序;首先计算种群的适应度F=[F1,F2,…,Fk,…,FK],其中, 然后计算每个适应度值的非支配等级lk,其中非支配等级越小,则解距离帕累托前沿越近,解越优;

S63:繁殖:从种群p中随机选择两个个体作为父代,并随机选择基因执行交叉操作产生c c两个子代,重复以上操作,直到产生r·K个子代作为子代种群 其中,r为交叉率;然后从种群p中随机选择一个个体作为父代,并随机选择父代的一个基因执行变异操作产生一v v个子代,重复以上操作,直到产生r·K个子代作为子代种群 其中,r为变异率;将亲代种群p和两个子代种群 和 合并为新种群。