欢迎来到利索能及~ 联系电话:18621327849
利索能及
我要发布
收藏
专利号: 2021110128374
申请人: 重庆理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-10-29
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种融合神经网络求解和启发式算法的任务调度方法,其特征在于,应用于分层边缘计算环境中,包括以下:S1、建立一个基于Seq2Seq的神经网络模型,通过该神经网络模型完成卸载任务对边缘云节点的映射;

S2、采用基于蒙特卡洛策略梯度的深度强化学习方法训练基于Seq2Seq的所述神经网络模型,使得基于Seq2Seq的所述神经网络模型作为强化学习中的智能体并获得自学习以优化任务调度决策的能力;其中基于蒙特卡洛策略梯度的深度强化学习方法的训练过程为:

1)状态集合:所有系统状态的集合,将边缘云向任务提供服务所产生的延迟作为状态,通过调度会使任务映射至不同的服务节点从而形成不同的处理延迟和传输延迟,即产生状态间的转化;将此状态集合表示为:t

S={h1(t),h2(t),…,hn(t)} (10)

其中,hi(t),i∈[1,n]表示在时间t第i个任务调度至服务节点hi(t)上;

2)动作空间:把边缘计算中心化协调器可能产生的潜在调度策略定义为动作空间,即一种调度策略是动作集合中的一个元素;此动作集合为:式中, 表示在时间t边缘云中心化协调器对第j个任务的调度动作;

3)回报模型:定义了系统的奖励和惩罚,将整个系统建模为带约束的优化问题,对违反约束条件的情况进行计算,并得到惩罚,其惩罚函数为:其中

式中 为每次执行动作后违反约束的惩罚期望, 求得

了系统中违反服务率,网络带宽,存储资源以及链路带宽约束条件的惩罚值总和,其中λx为惩罚因子,并定义了边缘云向任务提供服务的总延迟L,系统的动作奖励表示为:所以,卸载任务调度模型的效益函数可表示为:

t t t+1 t t

式中I(s ,a ,s )表示系统在状态为s 选择行动a后,系统所获得的总收益,式中为系统的总支出,系统目标为将收益最大化,即得到如下优化问题:t t t

其中,η为折扣因子(0<η<1),并且η随着时间增加其值减少,得到最优策略π为系统中对于卸载任务的调度决策;

S3、在系统中部署首次适应启发式算法;当边缘云接收到任务后,会同时生成以通过步骤S2训练后的神经网络模型输出的调度解与启发式算法的调度解,边缘计算中心化协调器根据两者的调度解的惩罚值以及预期延迟对其进行进一步评估,并在惩罚值小于零的基础上选择预期延迟最低的解为最优解;当出现调度解的惩罚值均大于零,或存在算法无法完成调度任务的情况,所述边缘计算中心化协调器将以通过步骤S2训练后的模型输出的调度最优解为主要策略,以启发式调度算法为辅助调度算法获得在边缘云中总延迟最小,服务质量最高的调度方案。

2.根据权利要求1所述的一种融合神经网络求解和启发式算法的任务调度方法,其特征在于,在步骤S3中融合神经网络求解和启发式算法混合的方法包括以下:移动应用将自己的资源密集型任务通过就近连接的基站卸载至边缘云,当边缘云接收到任务后,同时生成以Seq2Seq神经网络训练后输出的调度解和启发式算法的调度解,边缘计算中心化协调器根据两者的调度解的惩罚值以及预期延迟对其进行进一步评估,并在惩罚值小于零的基础上选择预期延迟最低的解为最优解;当出现调度解的惩罚值均大于零,或存在算法无法完成调度任务的情况,边缘计算中心化协调器将以Seq2Seq神经网络训练后输出的调度最优解为主要策略,以启发式调度算法为辅助调度算法;按照神经网络输出的主要策略依次完成对请求的调度,并在依次对请求任务执行调度时,检查完成本次操作是否会违反系统的服务率,网络带宽,存储资源以及链路带宽的四项约束,若违反则使用辅助调度算法,在可用服务节点中为该请求任务重新选择适合的服务节点。

3.根据权利要求1所述的一种融合神经网络求解和启发式算法的任务调度方法,其特征在于,在步骤S2中基于蒙特卡洛策略梯度的深度强化学习下式(15)的方法包括以下:t

得到的最优策略函数πθ(a|h(t))的具体参数,其中hi(t)∈S为输入的任务请求,策略函数πθ(a|h(t))中概率高的将会分配给惩罚低的动作a,概率低的则会分配给惩罚高的动作a,任务请求序列中未被调度的任务请求将根据已调度的的任务ah*和环境状态向量共同决定,即:基于历史调度以决定剩余任务的调度操作一旦智能体在学习过程中达到收敛状态,向系统输入任务时,智能体将会返回合理的调度策略;为评估模型参数,策略梯度法定义了表示权重θ的每个向量的期望回报的目标式;该式为评估调度策略质量的优化目标式,且被每一种不同的调度策略定义,具体由当前环境状态和神经网络模型而设定,因而不直接依赖于模型,只取决于每一次智能体生成的调度策略;为此,定义了与输入请求调度策略相关的预期延迟La:智能体通过每次输入的任务推断调度策略;因此根据任务分布的期望定义了预期延迟:如式(19),问题转化为在满足约束条件的前提下,找到最小化预期延迟期望的策略,其中 为在式(14)定义的系统中违反服务率,网络带宽,存储资源以及链路带宽四项约束条件的惩罚值总和:利用拉格朗日松弛算法,将公式(19)转化为无约束问题等式(20),等式(20)中,为拉格朗日目标式:采用随机梯度下降法和蒙特卡罗策略梯度法计算优化该目标函数的权值θ:

使用对数似然法获得拉格朗日函数的梯度;其中,L(a|h(t))为转化为无约束问题的拉格朗日对偶函数:where.L(a|h(t))=La(a|h(t))+∑xλx·Cx(a|h(t)) (22)通过蒙特卡罗法对输入采样K个,分为h1(t),h2(t),…,hK(t),同时通过引入Baseline辅助网络bθ,减小了梯度的方差且没有引入偏差,加快了收敛速度,从而获得更加优质稳定的输出策略,因此将 作近似处理为:使用Baseline辅助网络,预测了当前调度策略的惩罚,并采用随机梯度下降法对预测值bθ(hj(t))与环境实际惩罚值L(a|hj(t))的均方误差进行训练;