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

摘要:

权利要求书:

1.一种移动边缘环境下工作流卸载优化方法,其特征在于,包括以下步骤:步骤S1.构建移动边缘环境下的工作流调度模型;

步骤S2.根据拓扑结构寻找基于工作流本地计算量的关键路径,将关键路径上的节点和剩余节点分别存入关键节点队列和剩余节点队列中并等待调度;

步骤S3.将eNB节点抽象成拓扑结构后,根据用户历史移动路径并结合预测模型得到符合条件的eNB集,并根据预测概率、预测速度和预测方向筛选最优可卸载eNB并将其提供给用户执行任务卸载;

步骤S4.分别将任务按调度策略动态分为在本地执行或卸载至边缘侧执行,并在调度过程中动态更新关键路径;

步骤S5.根据调度结果分配任务至移动边缘环境下的设备,直至完成整个工作流的调度;

其中,所述步骤S1进一步包括以下步骤:步骤S11.UE将任务卸载至边缘侧以减少本地的计算负担,在传输过程中传输速率受信噪比的影响,UE与任务卸载节点的传输信噪比可表示为:其中 表示设备i进行传输时的电压频率, 表示设备i与当前eNB的距离导致的信号干扰,σ表示路径损耗因子,ξc表示卸载策略,即ξc=0时表示任务在本地执行,反之则将任务卸载至eNB;

由已知传输信噪比,移动边缘环境下瞬时传输率为:Rn=Blog2(1+fSNR(di,n)),其中,B为eNB的传输带宽;

步骤S12.当任务选择在本地执行时,本地计算即为本地执行工作流任务ti的时间,令local

f 表示UE的计算能力, 代表工作流任务ti的工作量;UE在本地执行任务ti的计算时间可表示为:

当用户在当前无可用eNB或任务不需要卸载至eNB时选择在本地执行任务,其产生的能耗为:

其中 表示设备选择在本地执行任务产生的能耗,Plocal表示设备在本地运行任务时的电压;

步骤S13.当UE选择将任务卸载至边缘侧运行时,首先将工作流任务ti传输到eNB(state=up),在成功卸载任务后,ti在eNB做计算处理(state=exec),最后将处理好的数据回传至UE端(state=down);从上传任务到eNB处理任务直至处理后的数据回传UE即为完成任务卸载,其时间开销如下所示:

其中, 代表ti的输入数据大小, 代表ti的输出数据大小;

考虑设备上传任务和任务下载到设备产生的能耗,因此任务卸载产生的能耗为:其中, 表示任务卸载处于state状态时产生的能耗,Ptrans表示设备UE处于传输数据时所需电压,当τ=0时表示UE能一次成功将任务卸载至边缘侧;

在步骤S2中,任务最早开始时间表示为EST,则任务的起始节点tsource最早开始时间为令tk表示工作流任务ti的前置任务,pre(tk)表示工作流任务ti的前置任务集合,对于DAG中其余任务节点,其最早任务开始时间从起始任务节点开始计算,表示为:任务最迟开始时间表示为LST,出口任务texit的最迟开始时间等于最早开始时间即令tk表示工作流任务ti的后继任务,succ(tk)表示工作流任务ti的后继任务集合,对于DAG中其余任务节点,根据逆拓扑排序从出口任务节点开始计算最迟任务开始时间,表示为:

首先初始化队列Q_cp并对工作流进行拓扑排序,然后依次对拓扑排序中的任务计算其EST和LST,当EST等于LST时,将任务加入到队列Q_cp中,反之则加入Q_noncp中;

所述步骤S3进一步包括:

S31.使用Baum‑Welch方法对隐性马尔科夫模型进行参数估计,用观测学习到的历史数据对数据集λ进行建模;然后针对已经建立好的隐性马尔科夫模型进行预测计算,通过HMM模型和已观测移动路径序列Oi<o1,o2,o3...oi>计算得到所有符合条件的下一个eNB端si+1,计算公式如下所示:

其中αt(i)=P(o1o2..ot,st=si|λ),βt(i)=P(ot+1ot+2..oT,st=si|λ),S32.基于高斯‑马尔科夫模型对当前区域的速度和偏移量进行预测,预测速度和偏移量的公式分别为:

其中vn和dn分别表示当前区域的移动速度和区域出口偏移量,vn‑1和dn‑1分别表示前一个区域的移动速度和区域出口偏移量,α表示记忆级别即当α=1时,当前区域的速度和出口偏移量为上一时间段的速度和出口偏移量,反之当α=0时,当前区域的速度和偏移量与前一个区域无任何关联,和dmid分别表示用户的平均速度和区域出口的中心位置,wn和mn分别表示服从标准正态分布的且独立与vn和dn的速度和出口偏移量;

S33.具体筛选过程为:根据当前位置并通过步骤S31获取当前所有可卸载的eNB,并对可卸载的eNB依照概率进行非增序排序,为进一步筛选可卸载的eNB,当被选概率与最高被选概率差值小于γ则添加到候选eNB集中,通过步骤S32获取当前位置在未来一段时间内的速度与方向筛选脱离距离最大的eNB,最后将该eNB标记为最适合任务卸载的eNB。

2.根据权利要求1所述的移动边缘环境下工作流卸载优化方法,其特征在于,在步骤S4中,在获取初始关键路径后,对于每个任务,若当前任务为关键路径上的任务则先判断任务能否在脱离当前eNB之前完成卸载,若在脱离前可以完成卸载,则将任务卸载至eNB,反之则判断该任务本地计算时间是否小于 若小于 则本地执行任务并在执行完成后重新获取新的关键路径,否则任务将等待调度直至存在可卸载的eNB;

当关键路径上的节点还存在前置任务没有完成时则重新通过关键路径算法获取新的关键路径节点,当任务为非关键路径上的任务时,则只需将任务调度在本地运行。

3.根据权利要求1或2所述的移动边缘环境下工作流卸载优化方法,其特征在于,在步骤S5中,针对移动边缘环境下的任务调度,依据调度方案对任务实时调度至设备上,并在调度过程中实时更新关键路径直至完成工作流的调度。

4.根据权利要求1或2所述的移动边缘环境下工作流卸载优化方法,其特征在于,当任务为关键节点或虽为关键节点但迁移至UE端调度的节点完成调度时,判断关键路径是否发生改变,若改变则动态生成新的关键路径并重复执行步骤4直至完成整个工作流的调度。