欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2022116230807
申请人: 长沙理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2025-12-26
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种动态融合遗传算法的边缘容器多目标蚁群优化调度方法,其特征在于,包括如下步骤:S1、获取系统模型和网络模型,所述系统模型包括多个边缘服务器、若干无线基站组、一个云服务中心;边缘计算的所述网络模型由用户与边缘服务器云服务器的连接方式确定;用户通过WLAN连接到最近的边缘服务器,边缘服务器间通过城域网MAN互相连接,边缘服务器与云端通过广域网WAN进行连接,所有边缘服务器都使用具有千兆以太网容量的共享城域网,如果将任务卸载到远程边缘服务器,则使用MAN,在这种情况下通过至少两跳访问,通过WLAN和MAN调度到合适的节点;

S2、用户具有t种不同请求需求的任务,将t种任务封装到t种不同的Container中,待调度的Pod有i个,P={P0,P1,...,Pi-1}则为待调度的pod队列,每个Pod由n个容器构成,Pi={C1,C2,...,Cn},待部署的Node节点有j个,N={N0,N1,...,Nj-1}表示待部署节点的队列,每个Node上有k种资源Nj={1,2,...,k},一个Pod只能对应在一个Node节点运行,对于任意一种资源k,边缘服务器上所有的Node节点资源分配小于该边缘服务器的相应资源容量;

S3、根据网络模型信息和待调度的pod属性,得到pod调度到边缘服务器的网络传输开销、计算时延和负载均衡度,建立多目标优化函数;

S4、使用遗传算法群体性的快速随机全局搜索能力,产生目标函数的初始解,在遗传算法阶段,采用间接编码方式,对每个pod被分配到的Node节点进行编码,根据kubernetes默认调度中判断资源优先级的思想定义遗传算法中的适应度函数,预先设置遗传算法的最小迭代次数gmin、最大迭代次数gmax以及最小进化率gratio,然后统计迭代过程中子代群体的进化率,若在给定的迭代次数范围内有连续gs代的进化率均低于gratio,则终止遗传算法搜索,开始进入蚁群算法求解;

S5、信息素规则决定Pod调度到相应Node节点的概率,将遗传算法得到的初始解转化为蚁群算法的初始化信息素浓度,基于遗传算法中变异操作保持种群的多样性防止算法陷入早熟加入蚁群算法局部信息素更新思想,并将蚂蚁为节点的打分值作为更新启发信息值,进行最优解求解;

所述步骤S4根据kubernetes默认调度中判断资源优先级的思想定义遗传算法中的适应度函数,具体包括:步骤一:根据在Kubernetes的默认调度方法中由Node空闲资源与Node资源总量的比值来决定Node评分,空闲资源越多,评分越高,得到计算公式如下:其中,Ncpu、Nmem和Nst分别表示Node节点的CPU、内存和磁盘总资源量,Nusedu、Nusedm和Nusedst分别表示Node节点通过遗传算法求解后得到的已用的CPU、内存和磁盘资源量,Prequ、Preqm和Preqst分别表示Pod请求的CPU、内存和磁盘资源量;

步骤二:建立遗传算法的适应度函数:

Fit(i)=aRcpu+bRst+cRmem

根据求得的Rcpu、Rst和Rmem比较三个值的大小得出a,b,c的权值系数大小依次为0.5,0.3,0.2;

所述步骤S5信息素规则具体包括:

步骤一:基于遗传算法变异操作防止算法陷入早熟加入蚁群算法局部信息素更新,局部信息素浓度公式为:τij(t+1)=(1-ρ)τij(t)+rFit(i)

Fit(i)为遗传算法中的适应度函数,将其作为影响因子加入局部信息素浓度更新公式,该值越大,则部署到节点的可能性越大,r为适应度的权重系数;

步骤二:当所有蚂蚁为全部待调度pod分配到相应的Node节点之后,可以计算出此次循环迭代的全局最优解,并对Pareto解集中所有最优解构建的放置方案中每个Pod所分配节点的映射进行信息素全局更新,更新公式如下所示:为该最优解放置方案的信息素增量,其值为

f为pareto解集中的解对应的放置方案,为f方案对应得网络开销归一化函数,其值为是物理机j上的最高能源消耗。

2.如权利要求1所述的一种动态融合遗传算法的边缘容器多目标蚁群优化调度方法,其特征在于,所述步骤S3中建立多目标优化函数,具体包括:步骤一:建立网络传输开销目标函数:

P(i)st为Podi的传输数据大小,hopi代表Pod调度到边缘服务器所经过的跳数,dlMAN和dlWLAN分别代表城域网延迟和无线网络延迟,BWMAN和BWWLAN分别表示城域网带宽和无线网带宽,所有Pod网络传输开销为:Nwcost越小,表示所有Pod单位时间网络传输开销越小,即该调度方法所得分配方案越优;

步骤二:建立计算时延的目标函数:

P(i)l表示Podi请求的任务长度,Nips和Nstc表示Node节点的计算速度和存储能力大小;

步骤三:建立负载均衡度的目标函数:

AvgN表示边缘环境下Pod调度完成后占用服务运行在各边缘服务器上Node节点的平均数,N表示当前边缘服务器上的Node节点数,m表示当前边缘环境下的边缘服务器,Nload其值越大,分布越不均衡,反之,分布越均衡。

3.如权利要求1所述的一种动态融合遗传算法的边缘容器多目标蚁群优化调度方法,其特征在于,所述步骤S5初始化信息素浓度值,将其根据遗传算法求得的最优解的后50%个体转化为蚁群算法的初始化信息素浓度值:其中,Nallc Nallm和Nallst分别表示集群所有节点的CPU、内存和磁盘总资源量,将τij(0)作为遗传算法获得最优解转换的信息素值,反映的是Node节点的能耗状态。

4.如权利要求1所述的一种动态融合遗传算法的边缘容器多目标蚁群优化调度方法,其特征在于,所述步骤S5将蚂蚁为节点的打分值作为更新启发信息值,第t次迭代i到j的信息启发值可以表示为:其中,ρ为信息素挥发因子。

5.如权利要求1所述的一种动态融合遗传算法的边缘容器多目标蚁群优化调度方法,其特征在于,如果每只蚂蚁都将Pod部署在信息素浓度最高的节点,会降低错过寻找最优解的可能,即蚂蚁认为已找到最好的部署方案,其实只是一个局部最优方案,因此需要一部分蚂蚁遵循目标函数最优的分配策略,还需要一部分蚂蚁遵循随机分配的策略,以发现新的最优解,将第x*80%只蚂蚁到第x只蚂蚁寻优方法设为随机分配策略,从而随机为Pod选择部署的节点,如果信息素浓度大于3,就通过变异的方式在[0,3]范围内处理。