(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210886097.5 (22)申请日 2022.07.26 (71)申请人 福州大学 地址 350108 福建省福州市闽侯县福州大 学城乌龙江北 大道2号福州大 学 (72)发明人 陈星　林潮伟　姚泽玮　胡晟熙　 (74)专利代理 机构 福州元创专利商标代理有限 公司 35100 专利代理师 张灯灿　蔡学俊 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) (54)发明名称 模糊边云协同环境下的多工作流应用调度 方法 (57)摘要 本发明涉及一种模糊边云协同环境下的多 工作流应用调度方法， 包括： 构建多工作流应用 调度模型， 包括带截止时间约束的多工作流应用 模型、 边云协同环境以及代价驱动调度器； 针对 建立的多工作流应用调度模型， 采用基于遗传算 子的粒子群优化调度策略来最小化多工作流应 用在模糊边 云协同环境中的模糊执行代价， 并在 其中引入二次惩罚方法， 以使调度策略更快地搜 索到可行解。 该方法有利于降低截止时间约束下 多工作流应用的模糊执 行代价。 权利要求书8页 说明书23页 附图3页 CN 115168011 A 2022.10.11 CN 115168011 A 1.一种模糊边云协同环境下的多工作流应用调度方法， 其特 征在于， 包括： 构建多工作流应用调度模型， 包括带截止时间约束的多工作流应用模型、 边云协同环 境以及代价驱动调度器； 针对建立的多工作流应用调度模型， 采用基于遗传算子的粒子群优化调度策略来最小 化多工作流应用在模糊边云协同环境中的模糊执行代价， 并在其中引入二次惩罚方法， 以 使调度策略更 快地搜索到可 行解。 2.根据权利要求1所述的模糊边云协同环境下的多工作流应用调度方法， 其特征在于， 所述多工作流应用模型的实现方法为： 在边云协同环境中， 用户在不同时间向边云协同系统提交工作流应用， 假设工作流应 用的到达满足一个强度为λ 的泊松过程， 则工作流应用到达的时间间隔服从参数为λ 的指数 分布， 其中， λ表示工作流的到达率； 多工作流应用W由多个工作流应用{w1,w2,…,wn}组成， 每个工作流应用wi可以表示为一个三元组wi＝( αi,di,Gi)， αi表示第i个工作流应用到达边 云协同系统的时间； di表示第i个工作流应用的截止时间， 在一个调度方案中， 若所有工作 流应用都能在相应的截止时间前被执行完成， 则称 该调度方案是可行的； Gi表示第i个工作 流应用的数据依赖结构； 每个工作流应用的数据依赖结构用有向无环图来表示， 即Gi＝(Vi,Ei)； 其中， Vi表示包 含m个任务的集合{vi,1,vi,2,…,vi,m}， vi,j表示第i个工作流中的第j个任务， τi,j表示任务 vi,j的计算量； 表示任务之间的数据边集合， 对于一条有向边 表示任务vi,p 和任务vi,q之间存在数据依赖关系， 由任 务vi,p向任务vi,q传输的数据量大小为 同时， 任 务vi,p是任务vi,q的前驱任务， 任务vi,q是任务vi,p的后继任务； 在工作流应用调度中， 一个任 务当且仅当其所有前驱任务都被执行完成， 且得到所有前驱任务传输的数据， 该任务才能 被执行； 对于一个工作流应用， 若一个任务没有前驱任务， 则将其标记为入任务vin， 同理， 若没 有后继任务， 则将其标记为出任务vout； 若一个工作流包含两个及以上入任务或出任务， 则 通过为其添加 虚拟入任务vin或虚拟出任务vout， 将其转化为仅含有一个入任务和出任务的 工作流， 具体操作如下： 设置虚拟入任务vin或虚拟出任务vout的计算量为0， 并将原有的入任务和出任务分别与 vin和vout通过虚拟数据边连接， 同时将上述虚拟数据边的权值设置为0， 即其传输数据量为 0。 3.根据权利要求1所述的模糊边云协同环境下的多工作流应用调度方法， 其特征在于， 所述边云协同环境的实现方法为： 在多工作流应用调度过程中， 边云协同环境向用户提供计算服务和带宽服务； 边云协 同环境S＝{Scloud,Sedge}由云和边缘组成， 云Scloud＝{s1,s2,...,su}包含的u个服务器， 边缘 Sedge＝{su+1,su+2,...,su+v}包含v个服务器； 服务器sk可以表示 为： 其中， pk表示服务器sk的计算性能； uk表示服务器sk提供服务而设定的特定要价单元时 间； 表示服务器sk在单元时间uk内的计算代价， 单元计算代价近似与其计算性能成正比； fk∈{0,1}表示服务器sk所属平台的类型， 当fk＝0时， sk属于云， 具有较强的计算性能； 当fk权　利　要　求　书 1/8 页 2 CN 115168011 A 2＝1时， sk属于边缘， 具有一般的计算 性能， 假定每 个服务器的处 理能力是已知的； 根据服务器所属平台的类型， 边云协同环境中的服 务器sr和st之间的带宽βr,t表示为： 其中， br,t表示带宽βr,t的值， 表示从服务器sr传输1GB数据到服务器st产生的数据传 输代价。 4.根据权利要求1所述的模糊边云协同环境下的多工作流应用调度方法， 其特征在于， 所述代价驱动调度器的实现方法为： 在边云协同环境中， 代价驱动调度器的目标是给定一个调度方案， 在每个工作流应用 都满足截止时间约束的条件下， 多工作流应用的执行代价最低； 其根据调度方案中工作流 应用任务和服 务器之间的映射关系， 为工作流应用任务分配相应的服 务器； 多工作流应用的调度方案 定义如下： Γ＝(W,S,M,ce,Tf),      (3) 其中， 表示多工作流应用W对应于边 云协同环境S的映射， ce表示多工作流应用W在边云协同环境S中的执行代价， 表示多工作流应用的完成时间； 对于映射M中的两类元素， (vi,j,sk)表示任务vi,j在服务器sk上执行， 表示数据 边 从服务器 sr传输到服务器st上； 当映射M的子映射 被确定 时， 子映射 也随之确定； 因此， 映射M等 价为： 对于确定性边云协同环境下的调度， 考虑任务计算时间ttc和数据传输时间tdt， 其计算 方式具体如下： 其中， 式表示任务vi,j在服务器sk上的计算时间， 式表示数据边 从服务器sr传输到服 务器st产生的传输时间； 由于单个服务器的带宽为无穷大， 当数据传输发生在同一台服务 器上时， 其数据传输时间为0； 对于一个调度方案Γ， 一旦映射M被确定， 每个服务器sk的使用情况也随之确定， 从而确 定其启动时间tboot(sk)； 根据多工作 流应用W对应于边云协同环境S的映射M， 对相关变量定 义如下： (1)tstart(vi,j,sk)： 任务vi,j在服务器sk上的开始时间， 由服务器sk的当前可用时间和任 务vi,j所有前驱任务的完成时间所决定， 如所示； (2)tend(vi,j,sk)： 任务vi,j在服务器sk上的完成时间， 等于任务vi,j的开始时间与其在服权　利　要　求　书 2/8 页 3 CN 115168011 A 3