[發明專利]一種基于移動機會網絡的群智計算在線任務分配方法

有效

• 申請號: 201810083243.4
• 申請日: 2018-01-29
• 公開（公告）號: CN108415760B
• 公開（公告）日: 2021-11-30
• 發明（設計）人: 徐琴珍;李卓青;楊堤;楊綠溪
• 申請（專利權）人: 東南大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 姜慧勤

本發明公開了一種基于移動機會網絡的群智計算在線任務分配方法，分別針對最小化獨立式任務的平均反饋時間和最小化協作式任務的最長反饋時間兩類問題，結合用戶相遇規律和計算能力差異，將待分配的任務按平均執行時間排序，任務請求者每與一個用戶相遇，執行一次虛擬離線全局分配方法，重復計算并實時更新每個用戶對每個任務的預估反饋時間，將任務依次分配給反饋時間最小的用戶，但只有結果中屬于當前相遇用戶的任務真實分配。與下個用戶相遇時，重復上述過程，直到所有任務分配完成。理論分析和仿真結果證明，本發明提出的方法能在相同的任務和用戶規模下最小化任務完成時間，提高效率，在基于移動機會網絡的群智計算場景中具有很強的實用價值。

技術領域

本發明涉及一種基于移動機會網絡的群智計算在線任務分配方法，屬于移動網絡和群智計算技術領域。

背景技術

群智計算的思想來源于眾包和群智感知，是一種利用移動用戶及其智能設備進行的分布式問題解決模式。移動設備的普及和快速發展拓寬了群智計算的應用場景和實現規模，網絡中的用戶可以通過手持設備中內置的豐富傳感器(GPS、相機、加速計、指南針等)和強大的存儲計算能力隨時隨地參與任務的感知、計算和數據分發，通過合理的協作和共享完成機器或個人難以完成的大規模復雜問題。

目前關于群智計算的研究多考慮基于分散位置的模型，即用戶需要移動到某些固定位置完成感知任務，例如環境、交通路況監控等，任務信息的收發和結果反饋通過3G/4G網絡傳輸，通過設計合理的激勵機制和任務分配算法保證任務有序進行。隨著無線通信技術的發展，搭載在移動社交網絡中的群智計算系統允許用戶通過WiFi、藍牙、D2D實現近距離通信，方便大規模數據傳輸，節省通信花費，基于機會式相遇的用戶協作也具有更高的安全性和可靠性，可更好的應用于大規模群智計算場景中。移動用戶作為網絡中的節點進行協作分布式計算具有部署方便、靈活、成本低等優點，用戶攜帶的信息也具有豐富的挖掘價值，將成為未來移動互聯網中值得探索的新模式。在多任務、多用戶隨機游走的復雜群智計算系統中如何結合用戶移動規律和計算差異進行合理的任務分配和資源調度，保證任務有序高效的完成，則是本發明關注解決的問題和創新性貢獻。

發明內容

本發明所要解決的技術問題是：提供一種基于移動機會網絡的群智計算在線任務分配方法，任務請求者每相遇一個用戶，根據當前的情況尋找最適合該用戶的任務子集并立即分配，保證任務高效完成。

本發明為解決上述技術問題采用以下技術方案：

一種基于移動機會網絡的群智計算在線任務分配方法，包括以下步驟：

步驟1，初始化任務請求者發布的待分配任務J＝{j₁,j₂,...,j_m,...,j_M}，其中，m＝1,…,M，j_m代表第m個待分配任務，M為待分配任務的總數；根據待分配任務類型和優化目標，將待分配任務按平均執行時間進行排序，得到有序任務列表；

步驟2，初始化候選用戶U＝{u₁,u₂,...,u_n,...,u_N}，其中，n＝1,…,N，u_n代表第n個愿意參與群智計算任務的候選用戶，N為候選用戶的總數；根據歷史交易記錄，計算每個候選用戶與任務請求者的相遇參數{λ₁,λ₂,...,λ_n,...,λ_N}和各個候選用戶的歷史任務執行時間比{p₁,p₂,...,p_n,...,p_N}，其中，λ_n和p_n分別代表第n個候選用戶與任務請求者的相遇參數和歷史任務執行時間比；

步驟3，當任務請求者與移動機會網絡中某個候選用戶u_n相遇時，對該用戶進行在線任務分配，具體為：