(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210840069.X (22)申请日 2022.07.18 (71)申请人 黑龙江八一农垦大 学 地址 163319 黑龙江省大庆市高新区新 风 路 ５号 (72)发明人 富爽　丁晨阳　王晓亮　蒋鹏　 姜岱林　 (74)专利代理 机构 黑龙江省百盾知识产权代理 事务所(普通 合伙) 23218 专利代理师 门雨晴 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/445(2018.01) G06F 9/455(2006.01) G06F 9/50(2006.01)G06N 3/12(2006.01) (54)发明名称 基于遗传算法的多用户工作流任务卸载决 策与调度方法 (57)摘要 本发明针对移动边缘环境下多用户多虚拟 服务器的工作流调度问题， 提出一种基于遗传算 法的多用户工作流任务卸载决策与调度方法。 首 先对多用户多虚拟服务器工作流任务的卸载调 度问题进行建模， 在此基础上获得系统总时延和 总能耗的计算表达式； 然后， 采用遗传算法， 通过 编码、 个体修正、 精英选择、 自适应交叉、 变异概 率等操作， 确定最优的工作流任务的执行顺序和 卸载位置。 该方法考虑多用户多虚拟服务器的工 作流任务卸载场景， 能够通过遗传算法， 对工作 流任务的执行顺序和卸载位置进行最优决策， 使 其在满足时延约束的条件下， 系统总能耗最小。 仿真结果表明， 相比其他几种比较方法， 能够有 效降低系统能耗。 权利要求书3页 说明书11页 附图2页 CN 115408121 A 2022.11.29 CN 115408121 A 1.一种基于遗传算法的多用户工作流任务卸载 决策与调度方法， 该方法包括下列系统 模型： (1)、 移动边缘计算系统由K个移动设备和一个配有MEC服务器的基站组成， MEC服务器 包含M个虚拟服务器用于并发处理多个计算任务， K个移动设备可以通过无线信道访问MEC 服务器， 每个移动设备有一个工作流任务需要进 行计算和卸载， 每个工作流任务由I个子任 务组成， 工作流任务可以通过一个加权有向无环图来描述子任务执 行的先后依赖关系； (2)、 定义移动设备k(1≤k≤K)的工作流任务为Wk， Wk由一个二元组(Vk,Ek)表示， 其中， Vk是工作流任务中I个子任务的集合， Ek是子任务之间边的集合， 每条边连接两个子任务， 表 示它们之间的存在数据依赖关系， 移动设备k的第i个子任务vi,k， 定义一个二元组vi,k＝ (ωi,k,ci,k)来表示， ωi,k表示第k个用户的第i个子任务的输入数据大小(以bit为单位)； ci,k表示单位比特任务执 行所需要的CPU周期数； (3)、 每个用户采用正交频分多址(OFDM,Orthogonal  Frequency  Division  Multiple   Access)的方式将任务卸载到基站上， 设 为移动设备k上行链路的传输速率， 其中， k＝1, 2,...,K， 假设下行信道具有相同的衰落环境和噪声， 为移动设备k下行链路的传输速率， 其中， k＝1,2,...,K； (4)、 子任务vi,k在本地执行时， 执行的时间和能耗由本地设备的计算能力决定， 其执行 时间为所需的CPU周期数除以CPU频率， 因此， 子任务的执 行时延 和能耗 为： 其中： κ 为与CPU芯片结构相关的能量消耗因子， 为移动设备k的本地计算频率， 则每 个CPU周期内的能耗 为 (5)、 子任务vi,k卸载到MEC虚拟服务器m计算时， 时延可以分为两部分， 一是子任务向 MEC服务器的卸载时延； 二是子任务在虚拟服务器上的计算时延， 因此， 子任务被卸载到MEC 虚拟服务器m上的传输时延 和能耗 为： 其中， 为用户k上传时的传输功率； (6)、 子任务vi,k被卸载到MEC虚拟服务器m上执行 时， 假设子任务持续占用CPU直到任务 执行完为止， 子任务在MEC虚拟服务器m上的执行时延取决于MEC虚拟服务器的计算能力及 其CPU频率， 则子任务在M EC虚拟服务器m上的执 行时延为： 其中， 为MEC虚拟服务器m的CPU频率；权　利　要　求　书 1/3 页 2 CN 115408121 A 2(7)、 定义集合L＝S∪{ 0}＝{0， 1， 2， ...， M}表示工作流中子任务的执行位置， 由于一个 子任务只能在一个虚拟服务器上执行， 因此定义变量xi,k,m∈{0,1}表示移动设备k的第i个 子任务vi,k的卸载决策， 如果任务vi,k卸载到边缘服务器m(m∈S)上执行， 则xi,k,m＝1， 否则 xi,k,m＝0， 设子任务vi,k的总的时延为Ti,k， 能耗为Ei,k； (8)、 在工作流任 务中， 工作流任 务Wk的两个关联的子任 务vi,k和vj,k， 如果在同一位置执 行， 则它们之 间的传输数据和传输时延为零； 如果在不同位置执行， 则他们之间需要传输数 据， 任务vi,k在本地执行， 后继任务vj,k在MEC虚拟服务器 m上执行时， 设两个子任务之间传输 数据的时延为 能耗为 同理， 任务vj,k在本地执行， 后继任务vi,k在MEC虚拟服务 器m上执行时， 设两个子任务之间传输数据的时延为 能耗为 (9)、 工作流任务Wk的总计算时间是相互关联的子任务 之间传输 数据的时延和子任务计 算之和， 工作流任务的总能耗是本地计算能耗、 卸载能耗和相互关联 的子任务之间传输数 据的能耗之和， 如上 所述， 总计算时间和总能耗可以分别计算 为： 综上， 移动边缘计算系统下， 在满足用户时延约束条件下通过对工作流任务卸载策略、 卸载位置的优化， 降低系统的总能耗， 系统能耗 最小化问题可以表示 为： 2.根据权利要求书1所述的基于遗传算法的工作流任务的任务卸载决策与调度方法， 其特征是： 其工作流任务的任务卸载决策与调度方案是按照如下步骤得到的： 步骤1初始化种群， 设系统中有K个移动设备和一个包含M个虚拟服务器的MEC边缘服务 器， 每个移动设备的工作流任务可以分成I个子任务， 将 工作流任务的执行顺序与执行位置 联合表示为一个个体， 则个体长度为I ×K， 每个个体对应一种执行顺序和执行位置， 随机产 生一个包含N个个体的初始种群； 步骤2个体初始化， 包括子任务的执 行位置和执 行顺序初始化； 步骤3适应度评估， 根据式(7)计算 适应度值， 即系统总能耗； 步骤4个体修正， 对于每个移动设备的工作流任务， 计算任务的完成时间， 如果不满足 时间约束， 则在选择操作中将不考虑由染色体表示的卸 载策略， 满足时间约束的染色体成 为有效染色体； 步骤5选择操作， 采用精英 选择策略从种群中选取适应度最高的个 体； 步骤6生存竞争， 每一代种群中， 随机选取两个个体进行生存竞争， 选择出适应度高的 个体， 得到N/2种群 个体进入下一代；权　利　要　求　书 2/3 页 3 CN 115408121 A 3