買專利賣專利找龍圖騰，真高效！ 查專利查商標用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或微信搜索“龍圖騰網”。