[發(fā)明專利]一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法

在審

• 申請?zhí)枺?/td>: 201910319148.4
• 申請日: 2019-04-19
• 公開（公告）號: CN110070287A
• 公開（公告）日: 2019-07-30
• 發(fā)明（設(shè)計）人: 於志文;楊聰穎;劉一萌;王亮;郭斌
• 申請（專利權(quán)）人: 西北工業(yè)大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06K9/62
• 代理公司: 西安利澤明知識產(chǎn)權(quán)代理有限公司 61222
• 代理人: 劉偉

本發(fā)明提供一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法，將復(fù)雜任務(wù)分解為原子任務(wù),并通過其任務(wù)關(guān)系矩陣,建立相應(yīng)的任務(wù)圖；遍歷現(xiàn)有數(shù)據(jù)庫中所匹配的任務(wù)對，讀取其相似任務(wù)所對應(yīng)參與者以及參與者未完成任務(wù)個數(shù)，然后調(diào)用平均分配思想的任務(wù)分配算法來對待分配任務(wù)進行動態(tài)任務(wù)分配。本發(fā)明具有以下有益效果為：可以對復(fù)雜任務(wù)得執(zhí)行情況進行全局把控，將未按時執(zhí)行得任務(wù)，按照原有得最優(yōu)匹配以及任務(wù)內(nèi)在得關(guān)系，還有參與者負載等多個約束，將未按時執(zhí)行得任務(wù)進行動態(tài)任務(wù)分配，保證任務(wù)的順利完成。

技術(shù)領(lǐng)域

本發(fā)明涉及通信技術(shù)領(lǐng)域，具體涉及一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法。

背景技術(shù)

復(fù)雜移動眾包任務(wù)的執(zhí)行過程中，任務(wù)與任務(wù)之間信息交互復(fù)雜，導(dǎo)致復(fù)雜任務(wù)在執(zhí)行過程中存在大量不可避免的返工與迭代。同時復(fù)雜任務(wù)執(zhí)行中，存在大量的不確定性，無法準確把控分配得任務(wù)被合適、合理的執(zhí)行，去除不確定性帶了的負面影響對應(yīng)其著復(fù)雜移動眾包任務(wù)的動態(tài)分配，該動態(tài)任務(wù)分配是一個極為復(fù)雜的NP難題。由于在復(fù)雜移動眾包任務(wù)的執(zhí)行過程中，任務(wù)與任務(wù)之間信息交互復(fù)雜，導(dǎo)致復(fù)雜任務(wù)在執(zhí)行過程中存在大量不可避免的返工與迭代。如果復(fù)雜任務(wù)的某些原子任務(wù)不能及時完成，則會導(dǎo)致整個復(fù)雜任務(wù)的延遲，甚至停滯。

發(fā)明內(nèi)容

針對以上缺陷，本發(fā)明根據(jù)任務(wù)執(zhí)行的實時反饋，對未能正常執(zhí)行的任務(wù)進行動態(tài)任務(wù)分配，保證復(fù)雜移動眾包任務(wù)的整體完成率。本發(fā)明的技術(shù)方案為：

一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法，所述方法包括以下步驟：

S1、建立任務(wù)圖：將復(fù)雜任務(wù)分解為原子任務(wù),并通過其任務(wù)關(guān)系矩陣,建立相應(yīng)的任務(wù)圖；

S2、進行任務(wù)相似度的刻畫，將任務(wù)圖Graph轉(zhuǎn)換為DiGraph，對相似度較高的任務(wù)添加雙向虛邊，來表示兩者除了依賴關(guān)系之外，還具有相似度關(guān)系；

S3、得到任務(wù)DiGraph之后，調(diào)用Tarjan算法，找到Graph的強連通分量，最終將相似并且依賴關(guān)系較強的強連通任務(wù)存儲到一個序列中，用于給動態(tài)分配提供分配依據(jù)；

S4、根據(jù)Tarjan算法所產(chǎn)生的任務(wù)序列，遍歷現(xiàn)有數(shù)據(jù)庫中所匹配的任務(wù)對，讀取其相似任務(wù)所對應(yīng)參與者以及參與者未完成任務(wù)個數(shù)，然后調(diào)用平均分配思想的任務(wù)分配算法來對待分配任務(wù)進行動態(tài)任務(wù)分配。

進一步的，一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法，所述相似度包括位置相似度、需求相似度和時間相似度。

進一步的，一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法，所述S4中平均思想的任務(wù)分配方法，是根據(jù)參與者負載以及參與者未完成的任務(wù)個數(shù)，將待分配任務(wù)平均分配給參與者。

進一步的，一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法，首先找出所有參與者中手頭未完成任務(wù)數(shù)最大的參與者，然后找出每個參與者的對應(yīng)負載，最后計算所有參與者可以再執(zhí)行的任務(wù)之和，任務(wù)和即為所有參與者的負載.

進一步的，一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法，在總參與者負載任務(wù)數(shù)量小于等于待分配任務(wù)個數(shù)的情況下，直接進行除法式的平均分配，未能整除的任務(wù)采用隨機分配。

進一步的，一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法，如果參與者負載總數(shù)大于待分配任務(wù)個數(shù)，則選擇降低標桿max_task來實現(xiàn)任務(wù)均勻分配。

本發(fā)明具有以下有益效果為：可以對復(fù)雜任務(wù)得執(zhí)行情況進行全局把控，將未按時執(zhí)行得任務(wù)，按照原有得最優(yōu)匹配以及任務(wù)內(nèi)在得關(guān)系，還有參與者負載等多個約束，將未按時執(zhí)行得任務(wù)進行動態(tài)任務(wù)分配，保證任務(wù)的順利完成。

附圖說明

圖1為本發(fā)明一種基于相似聚類及平均思想的動態(tài)任務(wù)分配方法的DAG轉(zhuǎn)換為DiGraph示意圖；