一种基于移动边缘计算的面向依赖型任务卸载方法及装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113741999A(43)申请公布日2021.12.03(21)申请号202110980231.3(22)申请日2021.08.25(71)申请人江南大学地址214122江苏省无锡市滨湖区蠡湖大道1800号(72)发明人卢先领王瑶(74)专利代理机构南京纵横知识产权代理有限公司32224代理人张欢欢(51)Int.Cl.G06F9/445(2018.01)G06F9/50(2006.01)H04W28/08(2009.01)权利要求书5页说明书12页附图4页(54)发明名称一种基于移动边缘计算的面向依赖型任务卸载方法及装置(57)摘要本发明公开了一种基于移动边缘计算的依赖型任务卸载方法及装置，方法包括：将应用形式化为多个任务组成的工作流，并用DAG图表示；遍历应用的DAG图，依据遍历的深度将工作流中所有任务划分为不同调度层；依据调度层的顺序依次处理调度层内的各任务；以应用的所有任务完成时延最小化为目标，考虑到跨服务器协作，将降低系统完成时延问题转化为面向各调度层的联合任务卸载和迁移问题；应用多领导者多跟随者的Stackelberg博弈，按照调度层顺序依次确定每个任务的卸载决策和迁移决策。本发明依据任务完成时延最小，将任务卸载到移动终端或边缘服务器执行，充分利用了计算资源，有效保证了服务质量，降低了系统的完成时延。CN113741999ACN113741999A权利要求书1/5页1.一种基于移动边缘计算的面向依赖型任务卸载方法，其特征在于，包括以下过程：将应用形式化为多个任务组成的工作流，并用DAG图表示工作流中任务以及任务之间的依赖关系；遍历应用的DAG图，依据遍历的深度将工作流中所有任务划分为不同调度层并确定各调度层的执行顺序；针对每个调度层，采用Stackelberg博弈模型描述任务卸载优化问题和边缘服务器迁移优化问题，其中任务卸载优化问题以任务的代价最小化为目标，边缘服务器迁移优化问题以边缘服务器的代价最小化为目标；依据各调度层的执行顺序，依次求解每个调度层的Stackelberg博弈模型，确定每个调度层上各任务的卸载决策和迁移决策。2.根据权利要求1所述的一种基于移动边缘计算的面向依赖型任务卸载方法，其特征在于，采用广度优先搜索算法遍历应用的DAG图。3.根据权利要求1所述的一种基于移动边缘计算的面向依赖型任务卸载方法，其特征在于，所述依据遍历的深度将工作流中所有任务划分为不同调度层，包括：寻找应用工作流的入口任务；从入口任务开始，采用广度优先算法遍历应用的DAG图，遍历的深度为每个任务分配调度编号，具有相同调度编号的任务划分为一个调度层。4.根据权利要求3所述的一种基于移动边缘计算的面向依赖型任务卸载方法，其特征在于，所述寻找应用工作流的入口任务时，当存在多个入口任务时，加入虚拟任务节点，将虚拟任务节点与原多个入口任务节点连接形成新的DAG图，以虚拟任务节点作为工作流的入口任务。5.根据权利要求1所述的一种基于移动边缘计算的面向依赖型任务卸载方法，其特征在于，所述任务卸载优化问题以任务的代价最小化为目标，包括：将调度层上任务的卸载决策的集合表示为Xl，边缘服务器ES的迁移决策表示为S，定义调度层sll上任务vm,i的代价函数为：其中，为任务vm,i本地执行的完成时延，为卸载任务vm,i至边缘服务器ESn的完成时延，为任务vm,i可以选择卸载的边缘服务器ES集合，I{*}为指示函数，当满足条件{*}时其值为1，否则为0，xm,i为任务vm,i的卸载决策；当xm,i＝0时，表示任务vm,i在本地执行；当xm,i＝n时，表示任务vm,i卸载到边缘服务器ESn执行；根据调度层sll上任务vm,i的代价函数的定义为最小化每个任务的完成时延，任务vm,i的卸载优化问题表述为博弈中的其中，X‑(m,i)为除任务vm,i外调度层sll上其他所有任务的卸载决策，卸载优化问题描述为固定其他任务的卸载决策X‑(m,i)和边缘服务器的迁移决策S不变，选择何种卸载决策xm,i2CN113741999A权利要求书2/5页能够使得其任务vm,i的代价Cm,i最小。6.根据权利要求5所述的一种基于移动边缘计算的面向依赖型任务卸载方法，其特征在于，所述任务的代价计算公式为：当任务vm,i决定在本地执行时，任务完成时延由其所需的周期数cm,i和移动终端用户m的计算能力决定，计算公式为：当任务vm,i决定卸载执行时，如果任务只在卸载到的边缘服务器ESn执行，而不迁移到别的边缘服务器，则完成时延由传输时延和计算时延组成；如果卸载到边缘服务器ESn上的任务vm,i需要进一步迁移至其他边缘服务器ESd，则完成时延还包含额外的迁移时延；得到任务vm,i从用户m到边缘服务器ESn传输时