欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2018116210614
申请人: 杭州电子科技大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种边缘计算环境下针对可靠性的工作流容错调度方法,其特征在于,包括以下步骤:步骤S1:定义移动边缘环境下的工作流和基站,W=(T,E)表示用户提交到移动边缘环境的服务工作流,W代表工作流,T={t1,t2...tR},R代表任务节点数目,任务节点间拥有以下依赖关系:E={(ti,tj,Dij)|(ti,tj)∈T×T,i≠j}其中,Dij表示任务ti和任务tj的数据传输成本,移动边缘计算系统M由一组给定的基站组成,M={eNB1,eNB2...eNBn},eNB代表基站,每个基站对外提供一定程度的工作流执行可靠性,用γ={γ1,γ2...γn}表示,各个基站间利用网络互连,基站eNBi和eNBj间的带宽为BWij;

步骤S2:建立可靠性模型;用户在提交工作流W时,通常采用可靠性需求(Reliability Demand,RD)描述不同计算密集型的任务,RD={RD1,RD2...RDR},RDi表示任务ti的可靠性需求系数;移动设备的失败计算服从暂态故障变量,故障变量服从泊松分布,在基站站点l下执行任务的可靠性如下:其中γl表示任务调度基站l的对外可靠性服务系数,λ表示移动边缘环境的故障系数;

步骤S3:建立延迟执行模型;当移动边缘计算资源的某个计算资源节点出现失效时,分配在此资源节点上的所有任务都无法执行;移动边缘计算资源下任务节点ti在基站站点l的延迟执行时间概率模型如下所示:其中参数μ表示由临时资源故障导致的延迟时间系数;

步骤S4:建立执行时间模型;其执行时间模型定义如下:

其中TFT(ti)代表任务ti的结束时间;

步骤S5:建立容错机制,以优化任务的流程执行;

步骤S6:初始化各参数;生成初始的生物种群POPULATION,最优调度方案向量Δ,最大迭代次数GENERATION_MAXIMUM;

步骤S7:计算调度方案的适应度值;在移动边缘环境下,假设有n个基站站点,针对某一指定的站点l,在站点l的执行结束时间ftl之后任务继续执行的概率如下:基站站点l的执行时间El(ti)如下所示:

其中,将计算得到的工作流执行时间作为适应度函数的值,评价工作流调度方案的优劣程度;

步骤S8:更新调度方案;在遗传算法的基础上进行迭代,不断更新现有的调度方案;具体步骤如下:步骤S81:调度方案双亲选择;根据遗传算法的定义,新的调度方案会遗传父母双方各一部分的基因;

步骤S82:双亲染色体切除;通过步骤S81中获得的双亲调度方案,随机选取其染色体编码向量的切除点;

步骤S83:双亲染色体拼接;通过步骤S82中获得的双亲染色体的切除点,将双亲染色体的编码向量进行拼接;

步骤S84:染色体变异;通过步骤S83中获得的染色体,在该染色体编码中随机选取变异点进行变异操作,最终生成新的调度方案;

步骤S9:判断是否符合结束条件;不符合则ITERATOR=ITERATOR+1,ITERATOR代表当前迭代次数,返回步骤S7继续迭代更新操作,符合或者达到迭代次数则停止更新,输出最优调度方案。