1.一种强化学习与启发式驱动的边缘计算依赖任务调度方法,其特征在于,包括以下步骤:S1、对多用户的任务进行合并,为所有没有前驱任务的任务添加一个开始节点;
S2、将边缘计算与依赖性任务调度问题转化成双层优化问题:在上层优化中,使用基于强化学习的人工智能算法对任务的依赖关系进行修改,即增加新的边,从而增加新的约束条件;
在下层优化中,采用传统的启发式算法对任务进行卸载求解,得到任务的调度顺序和调度地点;
S3、迭代优化上下两层,以最小化目标函数;
S2中,上层优化过程如下:
Sa1、构建马尔科夫链MDP:
将问题表述成强化学习的马尔科夫链MDP,状态是当前有向无环图DAG Gk,动作被定义为向Gk添加一条边,得到一个新的DAG Gk+1;
添加的边强制执行额外的约束,缩减决策空间,其中,xk表示第k步调度的执行顺序和地点,在Gk+1上采用传统启发式算法计算xk+1;
根据xk计算问题的目标函数值f (xk| Gk),定义奖励为前一个目标函数值f (xk| Gk)减去新的目标函数值f (xk+1| Gk+1):Reward = f (xk| Gk)−f (xk+1| Gk+1);
对于状态转换,每轮迭代设置一个最大动作数K作为结束条件,避免算法无法终止;
Sa2、状态编码:
采用图卷积网络GCN对DAG表示的状态进行编码,以提取数据特征,考虑DAG结构,使用两个GCN,第一个GCN处理原始DAG,第二个GCN处理所有边都翻转的DAG;
连接两个GCN模块得到节点特征n,并采用注意力池化层提取图的整体特征g:n=[GCN1(Gk)||GCN2(reverse(Gk))];
g=Att(n);
其中,reverse(Gk)表示Gk对应边全翻转的DAG,为拼接函数;
Sa3、使用由策略网络Actor Net和价值网络Critic Net组成的近端策略优化算法,策略网络Actor Net负责生成动作的概率分布,价值网络Critic Net负责评估当前状态长期价值;
S2中,下层优化使用基于贪婪算法的传统启发式算法对任务卸载问题进行求解,具体过程如下:Sb1、将所有用户中无前驱节点的任务放入就绪队列ready list,并根据应用的截止时间进行非降序排序,得到第一轮调度的任务及其调度顺序;
Sb2、将队列中的任务按顺序调度到时延、能耗和成本三个目标值加权和最小的地点执行,执行完后将任务从队列中移除,同时标记该任务已完成;
Sb3、检查被调度任务的后继任务是否符合条件,即后继任务的所有直接前驱任务是否已完成,如果符合条件,将该后继任务放入就绪队列;
Sb4、当一轮就绪队列中的任务全部完成,对新添加进队列的任务进行应用的截止时间的非降序排序,开始新一轮的任务调度;当所有任务都执行完成时,得到最终解。
2.根据权利要求1所述的一种强化学习与启发式驱动的边缘计算依赖任务调度方法,其特征在于:S1中,假定每个终端设备产生一个由一系列依赖性任务组成的应用程序,任务之间存在依赖关系,先对多用户的任务进行合并,为所有没有前驱任务的任务添加一个开始节点,该节点无数据和类型。
3.根据权利要求1所述的一种强化学习与启发式驱动的边缘计算依赖任务调度方法,其特征在于,在依赖任务卸载问题中,Sa3中的策略网络Actor Net为每条边生成相应的选择概率,为了减少动作空间,将选择边操作action分为选择起始节点和选择目的节点两步执行,选择起始节点和选择目的节点分别由两个独立的3层残差网络ResNet模块预测,其中,第二个ResNet的输入还包含所选起始节点的特征向量:P(a1) = softmax(ResNet1([n || g]));
P(a2 | a1) = softmax(ResNet2([n || n[a1] || g]));
其中,n[a1]的下标表示节点a1的节点特征。
4.根据权利要求3所述的一种强化学习与启发式驱动的边缘计算依赖任务调度方法,其特征在于,在选择边的过程中,检查添加边的动作是否合法,合法判定条件如下:在有向无环图DAG中,检查当前DAG中是否已包含待添加的边,若已包含待添加的边,则添加边的动作不合法;
判断待添加的边的起始节点和目的节点之间是否已经存在通路,若存在通路,则添加边的动作不合法;
通过拓扑排序或深度优先搜索DFS检测添加边后是否会形成环路,若形成环路,则添加边的动作不合法;
采用增加动作掩码的操作,将非法动作的概率设为零或负无穷,动作掩码通过屏蔽非法动作,确保智能体仅选择合法动作。
5.根据权利要求1所述的一种强化学习与启发式驱动的边缘计算依赖任务调度方法,其特征在于,Sa3中,价值网络Critic Net预测从当前状态开始,遵循当前策略的预期累积回报;
对所有节点特征进行最大池化maxpool处理,将池化后的特征与来自状态编码器的图特征进行拼接,由另一个ResNet进行值预测处理,即:V(Gk) = ResNet3([maxpool(n) || g]);
得到对当前状态长期价值的预测结果。