(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210535602.1 (22)申请日 2022.05.17 (65)同一申请的已公布的文献号 申请公布号 CN 114780247 A (43)申请公布日 2022.07.22 (73)专利权人 中国地质大 学 （北京） 地址 100083 北京市海淀区学院路2 9号 (72)发明人 孙大为　崔鑫垚　 (74)专利代理 机构 北京市广友专利事务所有限 责任公司 1 1237 专利代理师 张仲波 (51)Int.Cl. G06F 9/50(2006.01) G06F 9/48(2006.01) G06N 3/00(2006.01) (56)对比文件 CN 110086855 A,2019.08.02 CN 111614754 A,2020.09.01 CN 103049322 A,2013.04.17 CN 111860754 A,2020.10.3 0CN 110888728 A,2020.0 3.17 CN 110764912 A,2020.02.07 CN 114077475 A,202 2.02.22 CN 102932422 A,2013.02.13 CN 10732 9815 A,2017.1 1.07 CN 112434779 A,2021.0 3.02 CN 110413389 A,2019.1 1.05 安思华.基 于Hadoop平台的作业调度算法研 究与改进. 《中国优秀硕士学位 论文全文数据库 信息科技 辑》 .2016,(第3期), 王志刚等.基 于遗传蚁群算法的雾 计算任务 调度研究. 《计算机 应用与软件》 .2021,第38卷 (第8期), 王雅琴.基 于多核系统的混合关键任务调度 策略研究. 《中国优秀硕士学位 论文全文数据库 信息科技 辑》 .2021,(第8 期), (续) 审查员 高小霞 (54)发明名称 一种流速和资源感知的流应用调度方法及 系统 (57)摘要 本发明提供一种流速和资源感知的流应用 调度方法及系统， 方法包括： 根据流应用的拓扑 结构构建数据流划分模型； 根据执行器间的元组 传输速率构建任务分配模型； 根据计算节点资源 的占用情况构建负载均衡模型； 根据数据流划分 模型， 提出基于FFD算法的流速感知方法进行调 度， 将执行器和计算节点分别按照元组传输速率 和负载均衡指数进行排序， 在不超 过计算节点阈 值的情况下， 将高度通信的执行器聚集到同一计 算节点中； 根据任务分配模型与负载均衡模型， 基于蚁群优化的资源感知方法进行调度， 以最小 化任务完成时间和优化资源分配方案为目标， 将任务的资源需求与计算节点剩余资源情况加入 到信息素和启发式函数中， 在分配过程中使任务 根据资源需求类型找到相匹配的计算节点。 [转续页] 权利要求书3页 说明书14页 附图6页 CN 114780247 B 2022.12.13 CN 114780247 B (56)对比文件 Yangyang Dai 等.A Task Sc heduling Algorithm Based o n Genetic Algorithm and Ant Colony Optimizati on Algorithm w ith Multi-QoS Constraints in Cloud Computi ng. 《IEEE》 .2015,2/2 页 2[接上页] CN 114780247 B1.一种流速和资源感知的流应用调度方法， 其特 征在于， 所述方法包括： 根据流应用的拓扑 结构构建数据流划分模型； 根据执行器间的元组传输 速率构建任务分配模型； 根据计算节点资源的占用情况构建负载均衡模型； 根据所述数据流划分模型， 提出基于FFD算法的流速感知方法进行调度， 将执行器和计 算节点分别按照元组传输速率和负载均衡指数进行排序， 在不超过计算节点阈值的情况 下， 将高度通信的执 行器聚集到同一计算节点中； 根据所述任务分配模型与负载均衡模型， 提出基于蚁群优化的资源感知方法进行调 度， 以最小化任务完成时间和优化资源分配方案为 目标， 将任务的资源需求与计算节点剩 余资源情况加入到信息素和启发式函数中， 在分配过程中使任务根据资源需求类型找到相 匹配的计算节点， 采用精英蚂蚁搜索减少蚁群算法在调度过程中的收敛时间； 构建数据流划分模型包括： 获取拓扑 结构中单位时间内相邻两个执 行器之间传输的元组数量； 获取统计时间内所述拓扑 结构的执 行器之间元组传输 速率的平均值； 获取数据流传输 速率的偏移量； 获取数据流传输 速率的平均偏移量； 根据所述元组数量、 元组传输速率的平均值、 数据流传输速率的偏移量以及数据流传 输速率的平均偏移量得到所述数据流划分模型； 构建任务分配模型包括： 根据如下矩阵得到任务和计算节点的分配关系： 其中， 在矩阵X中， n为待执行的任务， m为计算节点， 其中n>m， n个任务集表示为T＝t1, t2…,tn， n表示第n个任务， m个计算节点集合表示为VM＝{VMl,VM2,…,VMm}， 其中m表示第m 个计算节点； X为一个0/ 1矩阵， 其中xnm为任务n和计算节点m的映射关系， 将第n个待执行任务分配到 第m个计算节 点上执行， 如果任务n被 分配到计算节 点m上， 在矩阵X中(n,m)的位置上的值为 1， 否则为0； 所述构建负载均衡模型包括： 获取集群中计算节点的负载均衡指数， 根据 所述负载均衡指数确定所述计算节点的负 载情况； 所述获取集群中计算节点的负载均衡指数， 包括： 按照如下公式获取集群中所有计算节点的平均负载均衡值： 权　利　要　求　书 1/3 页 2 CN 114780247 B 3