[發(fā)明專利]一種面向自組織群智感知系統(tǒng)的在線任務分派方法

有效

• 申請?zhí)枺?/td>: 201710113588.5
• 申請日: 2017-02-28
• 公開（公告）號: CN107066322B
• 公開（公告）日: 2018-02-27
• 發(fā)明（設計）人: 魏曉輝;孫冰怡;來守芳
• 申請（專利權）人: 吉林大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京遠大卓悅知識產權代理事務所(普通合伙)11369
• 代理人: 周明飛

1.一種面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，包括如下步驟：

步驟一：根據(jù)移動社交網絡中的歷史信息，按照信譽度值對將遇到的所有參與者進行排序，并計算所有參與者的信譽度的平均值；

步驟二：通過比較參與者信譽度和所述平均值的關系，將大于信譽度平均值的參與者放入候選者集合；

步驟三：計算候選者集合中參與者個數(shù)；

若參與者個數(shù)小于任務副本數(shù)，則向候選者集合內補充信譽度高的參與者，達到候選者集合內參與者個數(shù)與任務副本數(shù)相同；

若參與者個數(shù)大于任務副本數(shù)，通過比較參與者與請求者的相遇間隔時間對候選者進行篩選，采用分層求解方法，以得到信譽度高和當前執(zhí)行時間小的參與者；

步驟四：按照貪心策略，為每個任務副本選擇合適的候選者，從而決定目前相遇的參與者上的任務副本集合，所述貪心策略，包括：

a.為候選者Can集合中每個候選者設置初始化值，并將它的初始執(zhí)行時間設置為它與請求者之間的相遇間隔時間，并且其上放置的任務集設置為空集，按照執(zhí)行時間，對參與者進行排序；

b.然后，將所有任務副本按照它們的處理時間從小到大排序，存放在集合J_s中，并將處理時間最短的任務放到當前執(zhí)行時間最短的參與者上；

c.計算參與者的當前執(zhí)行時間，即為初始執(zhí)行時間與任務處理時間之和，并重新按照當前執(zhí)行時間對參與者進行排序；

d.仍將處理時間最短的任務放到當前執(zhí)行時間最短的參與者上；最終只有被分配到當前相遇的候選者上的任務副本能夠真正被分派到移動設備上，其它任務仍然留在請求者任務隊列里；當遇到其他候選者時，重新執(zhí)行該在線分派方法，為遇到的候選者分派任務。

2.根據(jù)權利要求1所述的面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，所述步驟一中的參與者按照信譽值降序排列。

3.根據(jù)權利要求1或2所述的面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，所述步驟一任務分派的過程中，每個參與者的信譽度值保持不變。

4.根據(jù)權利要求3所述的面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，所述步驟三中包括：

a.將經過步驟一排序后的參與者存入集合Cr中，計算集合Cr中所有參與者的信譽度平均值，并將信譽度大于等于信譽度平均值的參與者存入集合G中；

b.比較參與者集合G中的元素個數(shù)|G|和所有副本個數(shù)SumC，其中，m為請求者提交的任務個數(shù)，c_q表示第q個任務的副本個數(shù)；

c.若|G|≥SumC，進一步設置篩選條件，采用分層求解方法，以得到信譽度高和當前執(zhí)行時間小的參與者；

若|G|＜SumC，增加參與者個數(shù)，將參與者集合Cr中前SumC-|G|個元素放入G中。

5.根據(jù)權利要求4所述的面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，所述分層求解方法，包括：

首先，計算G中前SumC個元素的相遇間隔時間的平均值MAve，并且設置一個集合PrCan，初始情況下所述集合PrCan為空集；

然后，從G中第SumC+1個元素開始尋找相遇間隔時間小于等于MAve的元素，將它們放入PrCan集合中，并按相遇間隔時間的升序排序；然后將它們從G中刪除；

接著，按照相遇間隔時間的降序排列G中的參與者,依次掃描G中的元素的相遇間隔時間，當掃描到某個參與者的相遇間隔時間大于MAve且PrCan集合不為空時，將這個參與者與PrCan中相遇間隔時間最小的參與者替換，同時刪去PrCan中的當前參與者；

最后，將G中所有的元素放入候選者集合Can中，候選者集合Can中存放的是經過挑選的信譽度高的參與者；

其中，相遇間隔時間均為參與者與請求者的相遇間隔時間。

6.根據(jù)權利要求1所述的面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，在步驟a中，如果相遇的參與者已被選為候選者，則將它的初始執(zhí)行時間設置為零，即將處理的任務副本集合設置為空集；對于還沒有相遇的候選者來說，初始執(zhí)行時間設置為這個候選者和請求者之間的相遇間隔時間，并且即將處理的任務副本集合初始設置為空集。

7.如權利要求6所述的面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，在步驟b中，任務的描述方式是其處理時間，無論該任務被放到哪個參與者上，所述處理時間都是相同的。

8.如權利要求6或7所述的面向自組織群智感知系統(tǒng)的在線任務分派方法，其特征在于，對所有任務副本按照處理時間從小到大排序，依照候選者當前的執(zhí)行時間，按升序排列候選者。