一种基于马尔可夫决策过程的工作流任务卸载方法

dependencyandservicecachinginmobileedgecomputing，”inieeetransactionsonparallelanddistributedsystems，vol.32，no.11，pp.2777-2792，1nov.2021，doi：10.1109/tpds.2021.3076687.9.[4]l.liu，h.tan，s.h.-c.jiang，z.han，x.-y.li，andh.huang，“dependenttaskplacementandschedulingwithfunctionconfigurationinedgecomputing，”inproc.acmint.symp.qual.serv.，2019，pp.1-10.[0010][5]g.yang，l.hou，x.he，d.he，s.chanandm.guizani，″offloadingtimeoptimizationviamarkovdecisionprocessinmobile-edgecomputing，″inieeeinternetofthingsjournal，vol.8，no.4，pp.2483-2493，15feb.15，2021，doi：10.1109/jiot.2020.3033285。技术实现要素：[0011]本发明考虑在资源受限的异构边缘网络中针对工作流任务进行任务的卸载，目标是获得一组具有最小完成时间的卸载策略。工作流到达各个边缘服务器的速率λ遵循泊松分布。其中，每一个工作流wfl＝{al，gl}，al表示工作流wfl的到达时间，gl表示工作流wfl的拓扑结构。对于gl进一步将其建模为dag图，即gl＝(tl，el)，其中tl＝{task1，task2，...，taskm}表示工作流中的任务，即dag图的顶点，m为任务数量，el＝{ei，j|taski，taskj∈tl}表示任务之间的依赖关系，即dag图的边，如ei，j表示从任务taski指向任务taskj的箭头，这代表着在taski执行完之前不能执行taskj。每一个任务taski＝{inst1，inst2，...，instn}表示为一组函数实例的集合，代表该任务需要执行的函数实例集，其中每一个instx＝(typex，cpux，memx，execx)被表示为一个四元组，typex表示该函数的类型，cpux表示该函数的一个实例占用的计算资源，memx表示该函数的一个实例占用的存储资源，execx表示该函数的一个实例在服务器上的执行时间。[0012]发明目的：为克服现有技术中存在的不足，本发明针对具有偏序关系的工作流，考虑资源有限且异构的云边环境，运用马尔可夫决策过程，提供一种最小化执行时间的边缘卸载方法。目标函数：[0013]技术方案：为实现上述目的，本发明采用的技术方案为：[0014]一种基于马尔可夫决策过程的工作流任务卸载方法，包括以下阶段：[0015]a.预处理阶段：记录每一个边缘服务器的计算资源、存储资源、函数镜像，构造服务器集合；根据边缘服务器的网络拓扑结构构建邻接矩阵表，表内元素代表边缘服务器之间的距离。[0016]b.解决方案阶段：对于每一个待卸载的工作流，首先根据工作流的拓扑结构，构造工作流的直接前驱表、已卸载任务集、待卸载任务集和候选集，再对工作流进行马尔可夫决策过程建模，即定义状态空间、动作集合、奖励函数，最后根据价值函数评估出当前状态下的最佳决策，形成决策集；[0017]c.更新阶段：根据不同原因产生的状态更新，分别更新待卸载任务集、已卸载任务集、候选集、服务器集等参数。[0018]所述预处理阶段具体步骤如下：[0019]a1.记录每一个边缘服务器的计算资源、存储资源、函数镜像，定义服务器集m＝es，cs，其中边缘服务器集es＝{esi，cpui，memi，insti}，其中esi表示边缘服务器的编号为i，cpui表示边缘服务器i的剩余cpu核数，memi表示边缘服务器i的剩余内存，insti表示边缘服务器i存放的函数镜像，0≤i≤n，n为边缘服务器总数；云服务器集合cs＝{cs，∞，∞，install}，install表示云服务器拥有所有类型的函数镜像。[0020]a2.根据网络拓扑结构构建邻接矩阵表adj[n+1][n+1]，表示服务器之间的距离。其中前n行n列代表n个边缘服务器，第n+1行和第n+1列代表云服务器。云服务器到所有边缘服务器的距离都非常大；[0021]所述解决方案阶段中包括以下步骤：[0022]b1.构造工作流的直接前驱表pretable＝{taski，prei}，prei表示taski的直接前驱集合，为直接指向taski的任务；[0023]b2.构造工作流的已卸载任务集comp、待卸载任务集wait；[0024]b3.构造候选集cand，表示下一个状态可以转移的任务集。在初始时刻，候选集中有唯一一个任务，即工作流任务拓扑排序的第一个节点，该节点没有直接前驱；[0025]b4.定义状态空间s＝{tasks×m}，其中×表示笛卡尔积，tasks表示任务集，即工作流中的所有任务节点；m表示服务器集。例如，si＝taski,{esi,cpui,memi,insti}表示当前状态为任务taski在拥有计算资源cpui、存储资源memi和函数镜像insti的服务器esi上运行；[0026]b5.定义动作集合a＝{a1,a2,...,an,...,an}∩ac，表示从当前状态转移到下一个状态所采取的动作，即决定选择哪一台服务器卸载任务。am＝1表示选择第m台服务器卸载，am＝0表示不选择第m台服务器卸载；ac表示是否卸载到云服务器的行为，ac＝1表示卸载到云服务器，ac＝0表示不卸载到云服务器；[0027]b6.定义奖励函数r(s,a)，代表处于某状态能获得的奖励值。r(s,a)＝-(ttrans+texec)，其中ttrans表示传输时间，例如表示taski从当前服务器esi卸载到服务器的传输时间，texec表示执行时间，例如表示taski在服务器上的执行时间。其中di表示taski的数据量，adji,j表示taski所在服务器esi与之间的距离，b表示taski所在服务器esi与之间的带宽。由任务taski需要执行的所有函数实例的执行时间累加得出。[0028]b7.定义预期奖励，以基于此选出最优策略，最小化卸载时间。定义动作价值函数表示在当前状态为s时遵循策略π得到的期望回报。价值函数表示选择策略为π且当前状态为s时的期望回报。其中，表示策略为π且当前状态为s时计算期望奖励的期望函数；rt(s,a)表示执行任务taskt卸载决策的即时奖励，γ为折现因子，γ∈(0,1]。具体地，目标是通过选择δ中的最优策略最小化卸载时间，δ是π的集合。最大期望奖励从而，最优策略从而，最优策略至此，选出当前状态下的最优策略π*；[0029]b8.状态转移。具体包括以下步骤：[0030]b8.1在候选集cand中选择一个任务taski作为当前状态的待卸载任务，优先选择本任务需要的函数镜像与上一个状态所在服务器拥有的函数镜像相同的任务，若没有这样的任务，则在候选集中随机选择一个；[0031]b8.2遍历边缘服务器函数镜像库，(1)对于不拥有taski需要的函数镜像的边缘服务器eswithout中的每一个边缘服务器中的每一个边缘服务器(2)对于拥有taski需要的函数镜像的边缘服务器eshold中的每一个边缘服务器计算选择服务器卸载的策略的预期奖励，从中选择一个具有最大预期奖励的策略π*(s)；[0032]b8.3根据策略π*(s)，转移至下一个状态。[0033]所述更新阶段包括以下步骤：[0034]系统状态更新在以下两种情况下产生：(1)某任务节点到达某台服务器，即将占用该服务器资源，开始执行；(2)某任务在某台服务器上执行完毕，即将释放该服务器资源。[0035]c1.若状态更新由任务开始执行引起，系统将更新待卸载任务集wait、已卸载任务集comp、候选集cand、服务器集m等参数；[0036]c2.若状态更新由任务执行完毕引起，系统将更新参数服务器集m。[0037]c3.转至步骤b8。[0038]有益效果：本发明提供的一种基于马尔可夫决策过程的工作流任务卸载方法，与现有技术相比，具有以下有益效果：[0039](1)本发明考虑了具有偏序关系的工作流任务，目标是获得具有最小完成时间的卸载策略。具有依赖关系的工作流在卸载时执行顺序具有不确定性，本发明所提出的方法能够选择具有最小完成时间的子任务执行顺序。[0040](2)边缘服务器的资源有限，且每个边缘服务器的资源分布各不相同，动态变化。采用马尔可夫决策过程能够根据当下资源情况快速选择当前状态下的最佳决策，与传统的启发式规则相比，该方法对于资源变化的感知力和适应力更强。[0041](3)马尔可夫决策过程结合强化学习的方法具有学习特性，这使得卸载策略将随着迭代的次数增加而变得越来越优。附图说明[0042]图1是本发明实例中工作流拓扑、网络拓扑示意图。[0043]图2是本发明方法的场景和基本原理示意图。[0044]图3是本发明方法的马尔可夫决策过程状态转移示意图。[0045]图4是本发明方法的具体实现算法的流程示意图。具体实施方式[0046]下面结合附图和具体实施用例，进一步阐明本发明，应理解这些实例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本技术所附权利要求所限定的范围。[0047]实施例：[0048]如图2所示为一种基于马尔可夫决策过程的工作流任务卸载方法，综合考虑服务器资源异构且有限、工作流动态到达、完成时间最小化等约束，在做卸载决策的过程中，利用马尔可夫决策过程结合强化学习方法，动态分析任务调度顺序和系统资源的影响，最小化每个工作流的完成时间。[0049]假设此时在服务器es1到达如图1左侧所示的工作流，a、b分别表示每一个任务需要的函数实例类型。系统中资源情况如图1右侧所示。包括以下阶段：[0050]a.预处理阶段：记录每一个边缘服务器的计算资源、存储资源、函数镜像，构造服务器集合；根据边缘服务器的网络拓扑结构构建邻接矩阵表，表内元素代表边缘服务器之间的距离。[0051]b.解决方案阶段：对于每一个待卸载的工作流，首先构造工作流的直接前驱表、已卸载任务集、待卸载任务集和候选集，再对工作流进行马尔可夫决策过程建模，即定义状态空间、动作集合、奖励函数、预期奖励，最后根据奖励选出当前状态下的最佳策略，加入决策集。[0052]c.更新阶段：系统状态更新在以下两种情况下产生：(1)某任务节点到达某台服务器，即将占用该服务器资源，开始执行；(2)某任务在某台服务器上执行完毕，即将释放该服务器资源。在系统产生状态更新后，分别更新待卸载任务集、已卸载任务集、候选集、服务器资源集等参数。[0053]所述预处理阶段具体步骤如下：[0054]a1.记录每一个边缘服务器的计算资源、存储资源、函数镜像，定义服务器集m＝es，cs，其中边缘服务器集es＝{{es1，6，3，a}，{es2，3，2，b}，{es3，2，1，a}}，该实施例中没有云服务器，则云服务器集合因此m＝{{es1，6，3，a}，{es2，3，2，b}，{es3，2，1，a}}。[0055]a2.根据网络拓扑结构构建邻接矩阵表adj[3][3]＝[[0，1，1.2]，[1，0，0.2]，[1.2，0.2，0]]，adj[i，j]表示服务器i到服务器j之间的距离。[0056]所述解决方案阶段具体步骤如下：[0057]b1.根据工作流的拓扑结构g＝(v，e)，其中v＝{{1，a}，{2，b}，{3，a}，{4，b}，{5，a}，{6，b}}，e＝{(1，2)，(1，3)，(2，4)，(2，5)，(3，5)，(4，6)，(5，6)}，构造工作流的直接前驱表pretable＝{taski，prei}，prei表示taski的直接前驱集合，的直接前驱集合，为直接指向taski的任务，pretable＝{1：{}；2：{1}；3：{1}；4：{2}；5：{2，3}；6：{4，5}}[0058]b2.构造工作流的已卸载任务集comp＝{}、待卸载任务集wait＝{1,2,3,4,5,6}；[0059]b3.构造候选集cand，表示下一个状态可以转移的任务集。在初始时刻，候选集中有唯一一个任务，即工作流任务拓扑排序的第一个节点，该节点没有直接前驱，即cand＝{1}；[0060]b4.定义状态空间si＝taski,{esi,cpui,memi,insti}表示当前状态为任务taski在拥有计算资源cpui、存储资源memi和函数镜像insti的服务器esi上运行；[0061]b5.定义动作集合a＝{a1,a2,a3}，表示从当前状态转移到下一个状态所采取的动作，即决定选择哪一台服务器卸载任务。am＝1表示选择第m台服务器卸载，am＝0表示不选择第m台服务器卸载；ac表示是否卸载到云服务器的行为，ac＝1表示卸载到云服务器，ac＝0表示不卸载到云服务器。当前实施例下没有云服务器，则动作集合中未包含ac；[0062]b6.定义奖励函数r(s,a)，代表处于某状态能获得的奖励值。r(s,a)＝-(ttrans+texec)，其中ttrans表示传输时间，例如表示taski从当前服务器esi卸载到服务器的传输时间，texec表示执行时间，例如表示taski在服务器上的执行时间。上的执行时间。其中di表示taski的数据量，adji,j表示taski所在服务器esi与之间的距离，b表示taski所在服务器esi与之间的带宽。由任务taski需要执行的所有函数实例的执行时间累加得出。[0063]b7.定义预期奖励，以基于此选出最优策略，最小化卸载时间。定义动作价值函数表示在当前状态为s时遵循策略π得到的期望回报。价值函数表示选择策略为π且当前状态为s时的期望回报。其中，表示策略为π且当前状态为s时计算期望奖励的期望函数；rt(s,a)表示执行任务taskt卸载决策的即时奖励，γ为折现因子，在本实施例中，γ＝0.5。具体地，目标是通过选择δ中的最优策略最小化卸载时间，δ是π的集合。最大期望奖励从而，最优策略[0064]b8.状态转移，具体包括以下步骤：[0065]b8.1在候选集cand中选择一个任务taski＝1作为当前状态的待卸载任务，优先选择本任务需要的函数镜像与上一个状态所在服务器拥有的函数镜像相同的任务，若没有这样的任务，则在候选集中随机选择一个；[0066]b8.2遍历边缘服务器函数镜像库，(1)对于不拥有taski需要的函数镜像的边缘服务器eswithout中的每一个边缘服务器中的每一个边缘服务器(2)对于拥有taski需要的函数镜像的边缘服务器eshold中的每一个边缘服务器计算选择服务器卸载的策略的预期奖励，从中选择一个具有最大预期奖励的策略π*(s)。在本实施例中，由于task＝1所需函数类型a正好是服务器es1所拥有的函数镜像，则选择卸载策略es1即a1＝1，直接在es1上卸载，π*(s)＝a1＝1；[0067]b8.3根据策略π*(s)，转移至下一个状态s′。[0068]所述更新阶段包括以下步骤：[0069]系统状态更新在以下两种情况下产生：(1)某任务节点到达某台服务器，即将占用该服务器资源，开始执行；(2)某任务在某台服务器上执行完毕，即将释放该服务器资源。[0070]c1.若状态更新由任务开始执行引起，系统将更新待卸载任务集wait、已卸载任务集comp、候选集cand、服务器集m等参数。当前状态是由任务task＝1卸载至服务器es1引起，此时状态来到了s＝{1,{es1,4,2,a}}，更新候选集cand＝{2,3}，待卸载任务集wait＝{2,3,4,5,6}，已卸载任务集comp＝{1}，服务器m＝{{es1,4,2,a},{es2,3,2,b},{es3,2,1,a}}；[0071]c2.若状态更新由任务执行完毕引起，系统将更新参数服务器集m。[0072]c3.转至步骤b8：由于本状态处于服务器es1，而候选集中task＝3所需函数类型为es1所拥有，因此从候选集中选择task＝3作为待卸载节点，则es1所拥有，因此从候选集中选择task＝3作为待卸载节点，则评估动作集合a中各行为的价值，选择最优策略，即π*(s′)＝a1＝1。依此类推，循环往复更新状态参数、选择待卸载节点、评估各策略价值、选择最优策略的过程，直到待卸载候选集为空，算法结束。最终形成的调度结果为：res＝{(1,es1),(3,es1),(2,es2),(4,es2),(5,es3),(6,es2)},最终完成时间为：2.8s。[0073]需要说明的是上述实施例，并非用来限定本发明的保护范围，在上述技术方案的基础上所作出的等同变换或替代均落入本发明权利要求所保护的范围。当前第1页12当前第1页12
技术特征：
1.一种基于马尔可夫决策过程的工作流任务卸载方法，其特征在于：包括以下阶段：a.预处理阶段：记录每一个边缘服务器的计算资源、存储资源、函数镜像，构造服务器集合；根据边缘服务器的网络拓扑结构构建邻接矩阵表，表内元素代表边缘服务器之间的距离；b.解决方案阶段：对于每一个待卸载的工作流，首先构造工作流的直接前驱表、已卸载任务集、待卸载任务集和候选集，再对工作流进行马尔可夫决策过程建模，即定义状态空间、动作集合、奖励函数、预期奖励，最后根据奖励选出当前状态下的最佳策略，加入决策集；c.更新阶段：系统状态更新在以下两种情况下产生：(1)某任务节点到达某台服务器，即将占用该服务器资源，开始执行；(2)某任务在某台服务器上执行完毕，即将释放该服务器资源，在系统产生状态更新后，分别更新待卸载任务集、已卸载任务集、候选集、服务器资源集等参数。2.根据权利要求1所述的基于马尔可夫决策过程的工作流任务卸载方法，其特征在于：a.预处理阶段：具体步骤如下：a1.记录每一个边缘服务器的计算资源、存储资源、函数镜像库，定义服务器集，集合的每一个元素都包含服务器编号、服务器剩余cpu核数、服务器剩余内存；a2.根据网络拓扑结构构建邻接矩阵表，表示服务器之间的距离。3.根据权利要求2所述的基于马尔可夫决策过程的工作流任务卸载方法，其特征在于：b.解决方案阶段：包括以下步骤：b1.根据工作流的拓扑结构，构造工作流的直接前驱表，表示每一个任务节点的直接前驱集合；b2.构造工作流的已卸载任务集、待卸载任务集；b3.构造候选集，表示下一个状态可以转移的任务集；b4.定义状态空间，表示某一任务在某一拥有若干资源的服务器上运行；b5.定义动作集合，表示当前状态转移到下一个状态所采取的动作；b6.定义奖励函数，代表处于某状态能获得的奖励值；b7.定义预期奖励，包括下一步状态的即时奖励和长远状态的预期奖励；b8.状态转移。4.根据权利要求3所述的基于马尔可夫决策过程的工作流任务卸载方法，其特征在于：c.更新阶段：包括以下步骤：c1.若状态更新由任务开始执行引起，系统将更新待卸载任务集、已卸载任务集、候选集、服务器集参数；c2.若状态更新由任务执行完毕引起，系统将更新服务器集参数；c3.参数更新后，转至步骤b8。5.根据权利要求4所述的基于马尔可夫决策过程的工作流任务卸载方法，其特征在于：所有工作流的拓扑结构都相同，每个工作流中的子任务每次需要的函数类型及调用次数各不相同，云边服务器资源异构且有限，云端计算、存储资源无限，运算速度远快于边缘服务器。6.根据权利要求3所述的基于马尔可夫决策过程的工作流任务卸载方法，其特征在于：
b8状态转移,具体包括以下步骤：b8.1在候选集cand中选择一个任务task
i
作为当前状态的待卸载任务，优先选择本任务需要的函数镜像与上一个状态所在服务器拥有的函数镜像相同的任务，若没有这样的任务，则在候选集中随机选择一个；b8.2遍历边缘服务器函数镜像库，(1)对于不拥有task
i
需要的函数镜像的边缘服务器es
without
中的每一个边缘服务器(2)对于拥有task
i
需要的函数镜像的边缘服务器es
hold
中的每一个边缘服务器计算选择服务器卸载的策略的预期奖励，从中选择一个具有最大预期奖励的策略π
*
(s)；b8.3根据策略π
*
(s)，转移至下一个状态。

技术总结
本发明公开了一种基于马尔可夫决策过程的工作流任务卸载方法，包括预处理阶段：对整个云边端系统进行资源监测与记录，定义服务器集合和网络拓扑的邻接矩阵表；解决方案阶段：对于每一个待卸载的工作流，构造直接前驱表、已卸载任务集、待卸载任务集等，基于工作流构建马尔可夫决策过程模型，根据价值函数选出当前状态下的最佳决策；更新阶段：根据不同原因产生的状态更新，更新系统各参数。本发明使用马尔可夫决策过程，在异构云边端场景下解决工作流卸载问题，优化了任务的最快完成时间，在移动物联网领域有广泛的应用价值和使用前景。移动物联网领域有广泛的应用价值和使用前景。移动物联网领域有广泛的应用价值和使用前景。


技术研发人员：王爽 张易新 李小平 陈龙 朱夏
受保护的技术使用者：东南大学
技术研发日：2023.05.23
技术公布日：2023/8/21