[0056] 以下将结合附图对本发明提供的技术方案作进一步说明。
[0057] 本发明提供一种移动边缘环境下工作流卸载优化方法,参见图1和2,显示了本发明提供的一种结构示意图,具体如下:
[0058] 步骤S1在移动边缘环境下工作流的任务可选择在本地进行计算,也可以选择将任务卸载至边缘侧进行计算。无论是本地计算还是卸载至边缘侧都会产生时间和能耗上的开销,因此工作流调度需要对网络传输速率和任务卸载、本地执行进行建模:
[0059] 图3所示为本发明提供的一种移动边缘环境下工作流卸载优化方法中上述步骤的详细流程图,其进一步包括以下步骤:
[0060] S11.UE可将任务卸载至边缘侧减少本地的计算负担,因此在任务卸载的过程中需要考虑移动边缘环境下的网络传输问题。在传输过程中传输速率受信噪比的影响,移动设备与任务卸载节点的传输信噪比fSNR(di,n)如下所示:
[0061]
[0062] 其中 表示设备i进行传输时的电压频率, 表示设备i与当前eNB的距离导致的信号干扰,σ表示路径损耗因子,ξc表示卸载策略即ξc=0时表示任务在本地执行,反之则将任务卸载至eNB。已知传输信噪比,假设B为eNB的传输带宽则移动边缘环境下瞬时传输率Rn可定义为:
[0063] Rn=Blog2(1+fSNR(di,n))
[0064] 其中在上述对通信模型的描述中,令UE与eNB通信的传输速率为L bps,数据传输率不能超过eNB n的最大传输能力即Rn≤Ln,且对 都成立,在任务上传/下载过程中假定信噪比函数中距离为移动用户开始发送输入/接受输出数据的位置与连接eNB的距离。
[0065] S12.当任务选择在本地执行时,本地计算即为本地执行工作流任务ti的时间,令localf 表示UE的计算能力(每秒钟的CPU周期), 代表工作流任务ti的工作量,因此UE在本地执行任务ti的计算时间 可表示为:
[0066]
[0067] 当用户在当前无可用eNB或任务不需要卸载至eNB时可以选择在本地执行任务,其产生的能耗为:
[0068]
[0069] 其中 表示设备选择在本地执行任务产生的能耗,Plocal表示设备在本地运行任务时的电压。
[0070] S13.当UE选择将任务卸载至边缘侧运行时,首先需要将工作流任务ti传输到eNB(state=up),在成功卸载任务后,ti在eNB做计算处理(state=exec),最后将处理好的数据回传至UE端(state=down)。从上传任务到eNB处理任务直至处理后的数据回传UE即为完成任务卸载,令 代表ti的输入数据大小, 代表ti的输出数据大小,则其时间开销如下所示:
[0071]
[0072] 因此考虑任务卸载时产生的能耗,需要分别考虑设备上传任务和任务下载到设备产生的能耗,因此任务卸载产生的能耗如下所示:
[0073]
[0074] 其中 表示任务卸载处于state状态时产生的能耗,Ptrans表示设备UE处于传输数据时所需电压,当τ=0时表示UE能一次成功将任务卸载至边缘侧。
[0075] 步骤S2任务最早开始时间表示为EST,则任务的起始节点tsource最早开始时间为令tk表示工作流任务ti的前置任务,pre(tk)表示工作流任务ti的前置任务集合,对于DAG中其余任务节点,其最早任务开始时间从起始任务节点开始计算,表示为:
[0076]
[0077] 任务最迟开始时间表示为LST,出口任务texit的最迟开始时间等于最早开始时间即 令tk表示工作流任务ti的后继任务,succ(tk)表示工作流任务ti的后继任务集合,对于DAG中其余任务节点,根据逆拓扑排序从出口任务节点开始计算最迟任务开始时间,表示为:
[0078]
[0079] 首先初始化队列Q_cp并对工作流进行拓扑排序,然后依次对拓扑排序中的任务计算其EST和LST,当EST等于LST时,将任务加入到队列Q_cp中,反之则加入Q_noncp中。
[0080] 步骤S3基于隐形马尔科夫模型,移动边缘环境下预测可卸载eNB问题就可以转化为从一个节点到另一个节点的概率计算问题。
[0081] 图4所示为本发明提供的一种移动边缘环境下工作流卸载优化方法中上述步骤的详细流程图,其进一步包括以下步骤:
[0082] S31.根据用户历史移动路径和eNB历史迁移数据,对eNB迁移的预测可以通过以下两步进行:首先需要参数学习,本发现使用Baum‑Welch方法对隐性马尔科夫模型进行参数估计,用观测学习到的历史数据对数据集λ进行建模。然后针对已经建立好的隐性马尔科夫模型进行预测计算,由此移动用户eNB卸载预测可以转化为其常规求解问题,即通过HMM模型和已观测移动路径序列Oi<o1,o2,o3...oi>计算得到所有符合条件的下一个eNB端si+1,计算公式如下所示:
[0083]
[0084] 其中αt(i)=P(o1o2..ot,st=si|λ),βt(i)=P(ot+1ot+2..oT,st=si|λ),[0085] S32基于高斯‑马尔科夫模型对当前区域的速度和偏移量进行预测,预测速度和偏移量的公式分别为:
[0086]
[0087]
[0088] 其中vn和dn分别表示当前区域的移动速度和区域出口偏移量,vn‑1和dn‑1分别表示前一个区域的移动速度和区域出口偏移量,α表示记忆级别即当α=1时,当前区域的速度和出口偏移量为上一时间段的速度和出口偏移量,反之当α=0时,当前区域的速度和偏移量与前一个区域无任何关联, 和dmid分别表示用户的平均速度和区域出口的中心位置,wn和mn分别表示服从标准正态分布的且独立与vn和dn的速度和出口偏移量。
[0089] S33具体筛选过程为:根据当前位置并通过步骤3‑1获取当前所有可卸载的eNB,并对可卸载的eNB依照概率进行非增序排序,为进一步筛选可卸载的eNB,当被选概率与最高被选概率差值小于γ则添加到候选eNB集中,通过步骤3‑2获取当前位置在未来一段时间内的速度与方向(当前位置与预测出口位置连接的方向)筛选脱离距离最大的eNB,最后将该eNB标记为最适合任务卸载的eNB。
[0090] 步骤S4在任务调度的过程中,由于网络等因素导致任务卸载失败或是调度完成时间的改变都会导致关键路径发生变化,因此需要动态的更新关键路径,其调度过程如图5所示,在获取初始关键路径后,对于每个任务,若当前任务为关键路径上的任务则先判断任务能否在脱离当前eNB之前完成卸载,若在脱离前可以完成卸载,则将任务卸载至eNB,反之则判断该任务本地计算时间是否小于 若小于 则本地执行任务并在执行完成后重新通过算法2获取新的关键路径,否则任务将等待调度直至存在可卸载的eNB,当关键路径上的节点还存在前置任务没有完成时则重新通过关键路径算法获取新的关键路径节点,当任务为非关键路径上的任务时,则只需将任务调度在本地运行。
[0091] 步骤S5针对移动边缘环境下的任务调度,依据调度方案对任务实时调度至设备上,并在调度过程中实时更新关键路径直至完成工作流的调度。
[0092] 通过上述过程,本发明实现了移动边缘环境下工作流的优化,即通过高精度的预测模型筛选出最优可卸载eNB,并将需要卸载的任务迁移至该节点,以达到降低任务卸载失败率的目的。
[0093] 下面以模拟移动边缘环境下工作流调度为例对上述发明进行详细说明:
[0094] 在本发明中模拟工作流任务为随机生成,工作流的任务量服从[1GHz‑5GHz]的均匀分布,每个任务的输入输出服从[1Mb‑15Mb]的均匀分布。UE的计算能力为1GHz、计算功率为0.5W,上传和下载功率分别为0.1W和0.05W,eNB的计算能力为3GHz。设定传输电压为2 ‑10
0.1W,路径损耗因子σ=10 W/Hz。
[0095] 工作流任务根据是否LSTtexit=ESTtexit可划分为关键路径队列{a,c,d,e,..}和剩余节点{b,f,g,..},在完成对任务节点进行分类后,当任务为关键路径的节点时,首先通过当前位置及公式 获得当前可连接eNB节点,然后通过公式 和
进一步筛选最优可卸载边缘侧,通过预测的速度
和方向判断选择的边缘侧节点能否在脱离前完成卸载,若能完成卸载则卸载至边缘侧,反之则判断该任务本地计算时间是否小于 若小于 则本地执行任务
并在执行完成后重新通过关键路径算法获取新的关键路径,若不小于 则将任务置于eNB端执行。当任务为剩余节点时,则直接将任务置于UE端执行
[0096] 为了验证本发明技术方案的技术效果,通过算法对比验证本发明的有效性:
[0097] 设定预测精度为80%的情况下,对本发明的卸载模型和任务调度模型的优化效果进行考量,其中分别以时间和能耗为观测目标,本发明与PSwH、RANDOM算法和HEFT算法进行比较,其中PSwH(Path Selection with Handover)算法在保证通信质量的基础上,进一步考虑数据回传和eNB卸载的收益来选择边缘侧节点。RANDOM为任务采用随机排序的方式进行调度,是较为经典的调度方法。HEFT算法第二阶段策略为计算任务基于时间和能耗的优先值,并依据优先值对任务依次调度,同样是具有代表性的调度算法。但本说明不会构成对本发明的限制,其实验对比如图6、图7所示。
[0098] 图6和图7分别显示了本发明的算法在预测精度为80%的情况下和PSwH算法、RANDOM算法和HEFT算法在时间和能耗上的优化对比。本发明通过隐性马尔科夫模型选择可卸载eNB集并结合速度与偏移量预测筛选最优可调度eNB,极大程度上减少了卸载失败率;由图可知,相比另外三种算法,本发明通过降低卸载失败率,从而降低由卸载失败导致的能耗损失率和时耗损失率,并且基于关键路径的任务调度算法能将计算负担较为合理的分配至边缘侧,并且通过在调度过程中动态更新关键路径而从有效减少网络环境变化对任务调度的影响,当任务量为100时本算法相比PSwH分别减少了近20%、30%的时间和能耗,相比RANDOM算法分别减少了约35%、40%的时间和能耗,相比HEFT算法分别减少近15%和25%时间和能耗。
[0099] 以上实施例的说明只是用于帮助理解本发明的方法及其核心思想。应当指出,对于本技术领域的普通技术人员来说,在不脱离本发明原理的前提下,还可以对本发明进行若干改进和修饰,这些改进和修饰也落入本发明权利要求的保护范围内。
[0100] 对所公开的实施例的上述说明,使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的,本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下,在其它实施例中实现。因此,本发明将不会被限制于本文所示的这些实施例,而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。