移動群智感知時間窗口相關任務的激勵機制

研究背景：

近幾年來，智能手機市場增長迅速而不斷擴大。隨著5G網路和嵌入式感測器的技術進步，手機已被開發為強大的可編程移動數據介面，因為它由一組感測器集成，例如相機、光感測器、GPS、加速度計、數字羅盤、陀螺儀、麥克風和接近度感測器等等。另外，其他類型的感測器，如睡眠感測器、EEG耳機、氣壓計、心率監測感測器、化學感測器預計將在不久的將來應用到智能手機中。這些感測器可以感知到各種人類活動和周圍環境，如果我們利用普及的智能手機來收集數據，這將成為滿足大規模感知應用的有效途徑。

與傳統感測器網路相比，移動群智感知因其突出的優勢而擁有很大的潛力，比如廣泛時空覆蓋、成本低、可擴展性、應用場景廣等。作為新型的感知模式，移動群智感知能夠在不同領域中實現有吸引力的感測應用，例如健康監測、社交網路、環境監測和運輸。

我們著重探索滿足移動人群中時間窗相關任務所需屬性的真實激勵機制。我們提出一個普遍的新型群智感知場景的系統模型。為了激勵智能手機用戶，平台和智能手機用戶之間的互動被建模為反向拍賣機制。我們制定社會優化用戶選擇（SOUS）問題，並提出兩種激勵機制MST和MMT，分別在單時窗口案例和多時間窗口案例中解決SOUS問題。在MST中，我們設計一個動態規劃演算法來選擇用戶並確定Vickrey-Clarke-Groves（VCG）拍賣的付款。由於一般的SOUS問題是NP-hard，我們基於近似演算法設計的MMT遵循貪心的方法並證明了這兩種激勵機制滿足期望的性能。

研究方法和成果

我們考慮一個由平台和許多智能手機用戶組成的移動群智感知系統，平台駐留在雲端。

圖1 基於反向拍賣的移動群智感知系統

與大多數群智感知系統不同，我們考慮一個時間窗口相關任務感知的場景，即平台希望以特定時間間隔收集連續的數據。這種情況非常實用和普遍。如圖2所示，對於數據完整性要求很高的群智感知，諸如連續測量跟蹤，交通狀況，雜訊，空氣污染和垃圾分類的連續觀察等眾多時間窗相關應用，這些任務可以被看作是一個很大的任務，持續到整個時間窗口，不可能通過單個人類完成，例如對整個公交線路上的單元塔序列進行採樣，測量長期等效雜訊水平以及隨時收集空氣污染讀數等。這些項目都屬於時間窗口相關的任務疏散場景。

圖2 時間窗口相關任務範例

研究貢獻與影響

據我們所知，這是第一個對數據完整性要求較高的移動群智感知應用的工作激勵機制。在本文中，我們專註於處理一個類別的時間窗口相關任務的移動群智感知，這是一個新穎的實用的場景。我們提出了這種情景的通用系統模型，並制定了社會優化用戶選擇（SOUS）問題。

在單時間窗口的情況下，我們設計了基於動態規劃的最優演算法來解決SOUS問題。我們設計一個基於VCG拍賣的激勵機制，其計算效率高、個性理性以及可信性高。

在多個時間窗口的情況下，我們顯示一般SOUS問題是NP-hard，我們開發一種近似演算法，它遵循一種貪心演算法來選擇用戶並確定付款。此外，我們展示了在這種情況下提出的激勵機制在計算上有效率，具有低近似比的個人理性和真實性。

論文信息

Jia Xu, Jinxin Xiang, Dejun Yang. Incentive Mechanisms for Time Window Dependent Tasks in Mobile Crowdsensing. IEEE Transactions on Wireless Communications (TWC), 2015,14(11):6353-6364.

作者介紹

徐佳，博士，現任南京郵電大學計算機學院教授，博士生導師，江蘇省大數據安全與智能處理重點實驗室大數據通信與網路方向學術帶頭人。擔任國際會議IEEE ISKE 2017，IEEE MASS 2017，IEEE CyberC 2017的組織委員會主席或分組主席，及國際會議ICNC、ICSC、ICC的程序委員。目前主要研究領域為群智感知、區塊鏈、邊緣計算、演算法博弈論。在IEEE TMC、IEEE TWC、Computer Communications、IEEE SECON、IEEE MASS、ACM CIKM、JCST、Wireless Networks、PPNA等期刊及會議上發表論文70餘篇。曾獲2014年度中國通信學會科技進步二等獎，2016年度江蘇省教育科學研究成果獎二等獎。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！