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

有效

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

技術領域

本發明涉及群智感知領域，尤其涉及一種面向自組織群智感知系統的在線任務分派方法。

背景技術

近些年，隨著電子技術和通訊技術的發展，智能手機已經完全地融入了人們的生活。由于智能手機通常集成多種傳感器，例如：加速度傳感器、陀螺儀、亮度傳感器、全球定位系統(GPS)等。這些傳感器在大多數時間都處于空閑狀態，因此可以將它們在群智感知系統中加以利用，一方面，參與者能通過執行任務獲得收益，另一方面，不需要安裝額外的專用傳感器即可以采集到數據，降低了設備開銷。群智感知的概念是由Raghu K.Ganti在2011年提出的，由請求者向云端提出請求，云通過招募大量智能移動設備在請求者要求的區域和時間段內采集數據和計算，從而完成任務，這種收集模式能被廣泛地應用于路況監控，環境監控以及室內定位導航等方面。全球市場研究機構TrendForce的研究報告指出，2016年全球智能手機的出貨量將達到13.4億支，這意味著有大量的手機用戶能夠參與到群智感知系統中，因此群智感知成為了新興起的研究方向和應用模式。

現在廣泛研究的群智感知系統主要由三部分組成：請求者，云管理控制平臺和參與者。請求者將希望通過群智感知完成的任務傳輸到云端；云管理控制平臺查看現有的已登錄的參與者的性能，應用調度算法選擇合適的參與者，然后利用無線機會網絡通知被選擇的參與者并且將任務發送給他們；參與者完成任務后同樣利用無線機會網絡向云端返回結果，云管理控制平臺再將結果返回給請求者；請求者向云管理控制平臺支付酬勞，由其向參與者發放他們應該獲得的報酬。雖然，云管理控制平臺擁有大量的處理能力，能夠快速完成復雜度高的調度算法，但是這種群智感知系統同樣會帶來不可避免的缺陷，主要有如下三點：一、參與者與云管理控制平臺之間的通訊都是經過機會網絡，如果附近沒有無線WiFi接入點或者參與者沒有打電話(無法攜帶式傳輸數據)就會帶來實時性差的缺點。二、云管理控制平臺沒有廣告機制，不能針對任務的特殊性招募合適的參與者，只能被動地在已經登錄的參與者中進行挑選，因此可能帶來采集結果低效的缺點。三、現在的群智感知系統是中央化的并且有平臺特殊性，因此靈活性和魯棒性都受到限制。

考慮到現在主流的群智感知系統的以上三個缺點，2015年一種面向自組織網絡的群智感知系統應運而生，這種系統只包含兩個組成部分：請求者R和參與者P。R和P在無線局域網中的交互過程如圖1所示，在R向P發送任務描述(1)并且P確認有足夠的處理能力且同意R所提供的酬勞(2)后，R執行調度算法確定是否選擇P為自己完成任務，如果P被R所選擇，則R向P發送需要完成的任務(3)，待P完成后返回結果(4)，R向P支付酬金(5)。在這種只由請求者和參與者組成的系統中，請求者所持有的計算資源遠沒有云管理控制平臺那么多，因此如何選擇合適的調度算法即為系統實現的關鍵。

然而，面向自組織網絡的群智感知系統的調度算法并沒有得到應有的關注。Mingjun Xiao等人的文獻中提出了在此種群智感知架構中的多任務放置算法，包括離線放置算法和在線放置算法，該算法采用貪心的策略并證明這種策略能實現任務平均執行時間最少。但是，在這篇文獻中，每個任務并沒有副本也沒有考慮參與者是否可信，當執行某個任務的參與者只想獲得酬金而不愿真正執行任務，并且為了蒙蔽請求者而給出錯誤的結果時，請求者并沒有機制能保證結果的正確性。

因此，需要找出一種適合于自組織網絡的群智感知系統的任務分派方法，該方法能夠兼顧選擇信譽度高的參與者和在多副本情況下盡可能地減少任務的平均執行時間兩個目標，以達到避免上述調度算法的缺陷的目的。

發明內容

本發明的目的在于提供一種面向自組織網絡的群智感知系統的在線任務分派方法，結合移動社交網絡中人群移動軌跡的特性，實現兼顧選擇信譽度高的參與者和在多副本情況下盡量減少任務的平均處理時間。

本發明提供的技術方案為：

一種面向自組織群智感知系統的在線任務分派方法，包括如下步驟：

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

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

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

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