(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210702389.9 (22)申请日 2022.06.21 (71)申请人 福州大学 地址 350108 福建省福州市闽侯县福州大 学城乌龙江北 大道2号福州大 学 (72)发明人 陈哲毅　宋日荣　胡晟熙　 (74)专利代理 机构 福州元创专利商标代理有限 公司 35100 专利代理师 丘鸿超　蔡学俊 (51)Int.Cl. G06F 9/445(2018.01) G06F 9/50(2006.01) G06N 20/00(2019.01) (54)发明名称 云边环境下基于强化学习的工作流调度方 法 (57)摘要 本发明提出一种云边环境下基于强化学习 的工作流调度方法， 基于云、 边、 端三层协同体系 结构， 考虑云、 边、 端不同的处理能力和不同层次 之间的不同的传输速率， 以最小化计算任务响应 时延为优化目标， 设计好Q学习算法状态、 动作和 奖励三要素， 让智能体不断地学习， 不断地调整， 使得智能体逐渐明白在什么样的状态下选择什 么样的动作能够得到最好的结果， 从而求解出最 优的卸载决策。 权利要求书2页 说明书11页 附图6页 CN 114942799 A 2022.08.26 CN 114942799 A 1.一种云边环境下基于强化学习的工作流调度方法， 其特 征在于： 基于由云端、 边缘设备和终端移动设备组成的三层体系结构， 给定云端、 边缘设备和终 端移动设备 的处理能力以及三者之间的传输速率， 给定一个用有向无环图来表示的含有n 个任务的工作流， 每 个节点对应一个任务的指令数量， 每条有向边对应处 理结果数据大小； 优化问题的目标是找 到一个工作流的卸载策略positionmin＝(p1， p2， p3，……， pn)， 使得 此工作流的总执 行延迟Tmin最小， 公式化 为： Tmin＝min{Ω}    (7) s.t.(1)‑(6) 定义了一个变量xik来表示任务分配情况， 若是任务i∈N被分配给节点k∈V， 则xik＝1， 否则xik＝0； 一个任务只能分配到一个节点上， 有以下约束： 定义一个变量yij来表示全局调度规则， 如果任务i∈N被安排在任务j∈N之前， yij＝1， 否则， yij＝0； 任务j在被处理前， 需要满足分配的节点上没有其他任务正在执行， 即被分配的设备是 可用的； 定了一个变量 来表示设备可用的时间， 当被分配到同一节点且全局调度上更优 先的所有任务完成后， 此节点对于当前任务是 可用的， 所以有以下约束： 其中 为任务i的完成时间； 定义一个变量 来表示任务j的就绪时间， 若任务j与前提任务被分配到同一个节点， 那么可以忽略前提任务的处理结果数据的传输时延， 若任务j与前提任务被分配到不同节 点上， 那么就必须考虑前提任务的处理结果数据从一个节点到另一个节点的传输时延， 有 以下约束： 任务j的开始处 理时间 由下面公式决定： 任务j的完成时间 由下面公式决定： 整个工作流的总完成时间Ω由下面公式决定： 采用Q学习算法求 解所述优化问题； 首先对Q表进行初始化， 接着在每一个回合中， 先将环境初始化为所有任务都未被处权　利　要　求　书 1/2 页 2 CN 114942799 A 2理， 将根任务在本地处理， 然后对剩下的每个任务选取动作， 或是随机， 或是Q值最大的动 作， 执行相应的动作并获得环境反馈的奖励， 根据奖励更新Q表， 若是全部任务处理完毕则 进入下一个回合， 不断地更新 Q表直至收敛。 2.根据权利要求1所述的云边环境下基于强化学习的工作流调度方法， 其特征在于： 在 所述Q学习算法中： 考虑事先确定好一个任务的优先级， 以确定任务的执行顺序， 按照顺序一个接一个地 确定任务卸载位置， 此时， t时刻的状态可由一个大小为n的列表来表示， 即statet＝[s1,s2, s3,……,sn]， si代表着按优先级排列第i个任务的处理情况， si＝‑1表示第i个任务未被处 理， si＝0表示第i个任务在终端设备上处理， si＝1表示第i个任务在边缘设备上处理， si＝2 表示第i个任务在云端上处 理， 状态空间为所有可能的statet所组成的集 合states； 卸载问题中的动作表示为选择一个要处理 的任务并决定其卸载位置； 而由于任务的执 行顺序已经事先确定好， 所以每次要处理的任务都是固定的， 按优先级排列第一个未被处 理的任务就是接下来将要被处理的任务， 即st ate中第一个值为 ‑1的任务。 选择好任务后， 决定其卸载位置， 也就是将其对应si修改： 置为0表示此任务将在终端设备上处理， 置为1表 示此任务将在边缘设备上处理， 置为2表示此任务将在云端上处理； 动作空间为actions＝ [0,1,2]； 对于状态空间states中的每个状态statet， 都有动作空间actions可供选择,智能体在 每个状态下选择指定的动作后进入下一个状态， 环境产生一个奖励reward， 用于表示从状 态statet到下一个状态statet+1的动作的好坏， 对Q表进行更新， 进而指导智能体的学习过 程： 定义一个变量 来表示当前状态已完成任务所花费的整体时间， 由以下公式得到： 将奖励reward定义为上一步状态的整体时间 减去这一步状态的整体时间 即： 其中， St是上一步的状态， St+1是St经过选定的某个动作所产生的新状态。 3.根据权利要求2所述的云边环境下基于强化学习的工作流调度方法， 其特征在于： 在 所述Q学习算法中： 学习率α 是指控制每次训练的经验被学习的程度， 将其设置为0.7； 奖励 衰减γ是指放弃眼前的收益， 换取长远收益的程度， 将其设置为0.95； 贪婪系数ε是指对状 态空间的探索程度， 一开始将贪婪系数ε设置为0， 而随着时间不断推进， 将贪婪系数ε逐渐 增大至1， 并保持到算法结束。权　利　要　求　书 2/2 页 3 CN 114942799 A 3