买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜云南师范大学申请的专利一种基于时空感知的流式计算作业调度方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN119201405B 。

龙图腾网通过国家知识产权局官网在2025-03-25发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202411593871.9，技术领域涉及：G06F9/48；该发明授权一种基于时空感知的流式计算作业调度方法是由熊文;段飒飒;王晓璇设计研发完成，并于2024-11-08向国家知识产权局提交的专利申请。

本一种基于时空感知的流式计算作业调度方法在说明书摘要公布了：本发明涉及一种基于时空感知的流式计算作业调度方法，属于大数据处理技术任务调度领域。首先，对当前时刻的移动物体进行两阶段聚类，保持局部性的同时达到数据均匀；其次，在当前时刻两阶段聚类的基础上，对最新时刻的移动物体进行动态增量聚类，降低切换成本；随后，使用数据偏移、数据局部性、切换成本与综合指标来评价动态增量聚类算法的聚类质量；最后，将动态增量聚类后的每个簇映射到流式计算引擎的不同分区，再将每个分区调度到不同的计算任务，执行各种实时计算。本发明解决了大规模交通场景下任务实时调度的问题，通过保持局部性，降低数据偏移，减少切换成本，显著节省了计算资源。

本发明授权一种基于时空感知的流式计算作业调度方法在权利要求书中公布了：1.一种基于时空感知的流式计算作业调度方法，其特征在于：Step1：获取移动物体集合当前时刻在路网上的空间分布；Step2：对给定空间分布的移动物体集合，按照数据密度将纬度区间分割为多个纬度长度不等的子区间，保证不同子区间内的移动物体数量一致，每个子区间视为第一阶段聚类后的大簇；Step3：在得到的第一阶段聚类后的大簇内，按照数据密度切割经度区间为多个经度子区间，保证不同子区间内的移动物体数量一致，每个子区间视为第二阶段聚类后的小簇；Step4：获取移动物体集合最新时刻在路网上的空间分布；Step5：设定参数组合的集合，每个参数组合包括三个参数，分别是时间间隔，位移阈值，半径阈值；Step6：在当前时刻得到的第二阶段聚类后的小簇的基础上，使用当前参数组合结合最新时刻移动物体的空间分布进行动态增量聚类，计算每个移动物体两个不同时刻间产生的位移，若位移超过位移阈值，则对所述移动物体重新聚类；若位移没有超过位移阈值，则所述移动物体保留当前时刻的簇标记作为最新时刻的簇标记，得到最新时刻的小簇集合；Step7：为最新时刻的每个小簇生成簇心，将同一个簇内每个移动物体的经度相加后除以簇内移动物体的数量，纬度相加后除以簇内移动物体数量，获得簇心的经纬度；Step8：对于需要重新聚类的移动物体，以移动物体为圆心，半径阈值为半径，生成圆形搜索区域，对于出现在搜索区域的簇心，作为移动物体在重新聚类中的备选簇；Step9：在备选簇中，选择移动物体数量最少的簇作为移动物体重新聚类后的新簇；Step10：迭代Step8与Step9，直到所有需要重新聚类的移动物体处理完毕，完成动态增量聚类；Step11：使用数据偏移、数据局部性和切换成本三个度量指标评价使用当前参数组合进行动态增量聚类后的聚类质量，获得一个综合指标；Step12：迭代Step7至Step11，直到遍历完所有参数组合，获得不同参数组合下的所有综合指标；Step13：选择综合指标最小的参数组合，作为动态增量聚类算法的最优参数组合，并在每次切换调度时选用最优参数组合；Step14：将最优参数组合中的时间间隔作为切换调度的时间间隔，每次切换调度时，将动态增量聚类后的每个簇映射到流式计算引擎的不同分区，再将每个分区调度到不同的计算任务，执行各种实时计算；所述Step2中第一阶段聚类具体构建过程为：Step2.1：第一次聚类前的数据预处理与相关变量的定义、计算，如公式（1）所描述： （1）；在公式（1）中，表示按照经度由小到大对原始数据集排序后的列表，表示大簇的数量，1表示第一次聚类中大簇的理想数据量；Step2.2：获取每个大簇的数据，如公式（2）所描述: （2）；在公式（2）中，表示大簇的编号，表示第个大簇，表示在中对应的子集；Step2.3：为添加对应的簇标记；Step2.4：迭代Step2.2与Step2.3，直到所有移动物体完成第一阶段的聚类；所述Step3中第二阶段聚类具体构建过程为：Step3.1：第二次聚类前的数据预处理与相关变量的定义、计算，如公式（3）所描述： （3）；在公式（3）中，表示每个大簇中的小簇数量，表示的数据量，ideal表示每个小簇内的理想数据量；Step3.2：令表示第个小簇，寻找的簇心，按纬度从大到小对中的数据排序得到，选取其中纬度最大点作为簇心；Step3.3：寻找的同簇点，如公式（4）与公式（5）所描述： （4）；在公式（4）中，distance函数输入与，输出两者之间的垂直欧式距离，表示距离列表； （5）；在公式（5）中，表示的同簇点；Step3.4：令表示存储第j个小簇的数据列表，将与加入，并添加簇标记；Step3.5：令表示存储所有小簇的数据列表，将加入；Step3.6：迭代Step3.2到Step3.5，直到所有数据都被划分到簇中；所述Step11中综合指标具体为：综合指标是数据偏移，数据局部性和切换成本三个指标的加权平均；数据偏移是对移动物体聚类后不同簇之间数据量的不均衡程度，数据偏移的计算方法如公式（6）所描述： （6）；在公式（6）中，表示数据偏移，表示簇的编号，表示簇的数量，表示第个簇内的移动物的数量，表示聚类后每个簇内移动物体的理想数量，表示移动物体的总数量，数据偏移越小，不同簇之间数据量越均衡，按照调度方案将这些簇映射到分区，分区调度到任务，执行计算后，任务间的时间延迟越低；数据局部性是从空间分布的视角，判断不同簇边界分明的程度，数据局部性的计算方法如公式（7）到（9）所描述： （7）； （8）； （9）；在公式（7）到（9）中，表示第个移动物体，表示所在簇以外的其它簇的外接多边形集合，函数输入与输出对应的数据局部性，表示移动物体的总数量，表示所有移动物体的平均数据局部性，局部性越大，不同簇之间越边界分明；切换成本是切换调度时，进行重聚类的移动物体的比例，切换成本的计算方法如公式（10）与（11）所描述： （10）； （11）；在公式（10）与（11）中，表示的切换成本，，分别表示在上下两个时刻的位置，表示位移阈值，表示所有移动物体的切换成本，切换成本越小，进行重新聚类的移动物体比例越低，节省的计算资源越多；对应聚类质量的综合指标的计算方法如公式（12）与（13）描述： （12）； （13）；在公式（12）与（13）中，表示综合指标，、分别表示数据偏移、数据局部性、切换成本的权重，综合指标越小，说明数据局部性高、数据偏移低的同时切换成本低。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人云南师范大学，其通讯地址为：650500 云南省昆明市呈贡区聚贤街768号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。