群智感知中基于時空關聯性的用戶激勵機制

周 強，李 鵬，聶 雷

（1.武漢科技大學計算機科學與技術學院，武漢 430065；2.智能信息處理與實時工業系統湖北省重點實驗室，武漢 430065）

0 概述

群智感知是結合眾包思想和移動設備感知能力的一種新的數據獲取模式［1］，其通過移動設備形成交互式和參與式的感知網絡，并將感知任務發布給網絡中的個體或群體來完成，從而幫助專業人員或公眾收集數據、分析信息和共享知識。相比傳統固定基站的數據收集方式，一方面群智感知模式由于GPS、羅盤、加速計等大量傳感器嵌入手機移動設備，用戶可方便快捷地參與任務，另一方面在收集大規模和大容量數據時其在質量、速度和效率方面更具優勢。本文以群智感知技術為研究背景，提出基于顯性時空關聯和隱性時空關聯的用戶激勵算法。

1 相關工作

在用戶激勵機制方面，文獻［2］主要從技術層面入手，分析激勵機制中的影響因素。文獻［3］研究跨空間領域中有關群智感知的用戶激勵機制、任務請求者以及最終執行任務的用戶三者之間的關系和多元互動來激勵效率高、質量好的用戶參與群智感知任務。文獻［4］在移動數據收集過程中設計一種基于時間敏感的用戶激勵機制，將用戶激勵問題轉化為用戶博弈問題，并證明了該博弈滿足納什均衡理論。

在用戶招募方面，文獻［5］從用戶社交性以及用戶和感知目標的距離角度進行群智感知用戶招募。文獻［6］對具有最低花費且用戶軌跡覆蓋相關興趣點的用戶進行招募，且將招募問題轉化為集合覆蓋問題。文獻［7］建立用戶質量模型、估算用戶信譽模型來選擇高質量用戶，且利用沙普利值計算用戶酬勞。

在用戶時空性方面，文獻［8］不僅考慮用戶當前位置，而且考慮用戶未來軌跡，將用戶選擇問題轉化為NP-Hard 問題并提出貪婪算法進行求解。文獻［9］結合感知任務的空間性和移動用戶的時間性提出LRBA 算法，從而將整個任務分配問題劃分成若干個子問題。文獻［10］研究基于感知任務截止時間的用戶選擇問題，并證明該問題是NP-Hard 問題。文獻［11］將感知任務分成時間敏感和延時容忍任務，對于時間敏感任務，招募用戶的準則是最小化用戶移動的總距離，而對于延時容忍任務，盡可能減少招募的用戶數量。文獻［12］提出一種依賴時間窗口和對數據完整性有較高要求的激勵機制，使用反向拍賣的框架來建立系統模型。

在預測用戶時空性方面，文獻［13］通過半馬爾科夫模型［14］預測興趣點軌跡，并充分考慮時間和空間的因素對用戶進行選擇。文獻［15］分析用戶完成任務的數量，根據用戶上傳數據的方式不同（蜂窩網絡和WiFi網絡），通過馬爾科夫模型對用戶軌跡進行預測，設計相應的貪婪算法進行滿足預算限制和最佳用戶的招募。文獻［16］針對確定軌跡和不確定軌跡分別提出基于線性規劃的遺傳算法和貪婪算法，并且保證了算法有效性。文獻［17］建立基于興趣點的軌跡預測模型得到所有任務的完成概率，并提出離線貪婪算法和在線用戶招募算法。文獻［18］基于群智感知提出實時軌跡追蹤系統，實現最大化實時追蹤軌跡和真實軌跡的覆蓋，并且最小化參與實時軌跡追蹤系統的用戶數量。

上述傳統激勵機制未同時考慮時空及時空關聯性因素，因此造成很多感知任務難以執行。基于時空因素，文獻［19］采用深度學習模型，提出基于時空相關性的短時交通流量預測法，但該方法更多關注顯性關聯性。文獻［20］研究時空因素下的用戶招募和激勵機制，但未考慮時空重疊和關聯性問題，而對比傳統激勵機制發現，很多任務和用戶具有時空重疊和關聯特性。為解決感知任務完成率低且花費高的問題，本文提出基于時空關聯性的用戶激勵機制STIM。

2 時空關聯模型及問題定義

2.1 系統模型

假設系統中發布一系列群智感知任務S={S1，S2，…，Sm}，對于任意任務Sj∈S均存在時間范圍和空間范圍Pj={l1，l2，…，lm}，其中表示感知任務的開始時間表示感知任務的結束時間，lm表示感知任務需要感知的路段。結合時間和空間范圍，通過二元組，{l1，l2，…，lm} }來表示任務時空要求，即在時間范圍內經過的路段，例如θ1={[7：11]，{l1，l2}}表示任務1 需要用戶從07：00 到11：00 經過l1、l2兩個路段。

假設系統有一系列用戶U={U1，U2，…，Un}，對于任意用戶Ui∈U均存在用戶三元組ωi=，{l1，l2，…，lm}，ci}，其中表示用戶能參與任務的開始時間表示用戶能參與感知任務的結束時間，ci表示用戶花費，例如ω1={[7：11]，{l1}，10}表示用戶1 從07：00 到10：00 經過l1路段，花費為10。

2.2 顯性時空關聯模型

顯性時空關聯表示感知任務與感知任務、用戶與用戶間存在相同時空特性，因此分別定義基于感知任務和用戶的顯性時空關聯。

定義1（基于感知任務的顯性時空關聯）對于任意兩個任務Sj1，Sj2∈S，滿足時空重疊（見式（1）），則稱該感知任務集合是基于感知任務的顯性時空關聯。

對于任意兩個任務Sj1，Sj2∈S，滿足時空重疊和時空覆蓋（見式（2）），則稱該感知任務集合是基于感知任務的覆蓋顯性時空關聯。可見，時空覆蓋任務一定是時空重疊任務，但是時空重疊任務不一定是時空覆蓋任務，即時空重疊包含時空覆蓋。

將所有基于顯性時空關聯的感知任務集合視為一個感知任務，用戶的時空集合可以同時滿足多個任務的時空需求，大幅提高運算效率。

定義2（基于用戶的顯性時空關聯）對于任意兩個招募用戶Ui1，Ui2∈U，可能存在部分相同的時空集合（滿足式（3）），則稱有相同時空的用戶集為基于用戶的顯性時空關聯。

通過式（4）得到相同時空集合{[t′，p′]}，并將用戶集中有相同時空集合視為同一時空集合，這樣模型只要支付一次該時空集合的花費，就能節省總花費。

圖1 表示顯性時空關聯狀態。已知感知任務1～感知任務4，感知任務1的感知時間間隔為08：00—10：00、感知任務2 的感知時間間隔為09：00—11：00、感知任務3的感知時間間隔為01：00—03：00、感知任務4的感知時間間隔為01：30—02：30；感知任務1和感知任務2的感知區域有重疊部分，感知任務3 的感知區域完全覆蓋感知任務4 的感知區域。用戶A 在時間間隔08：00—09：00 內停留在感知任務1 的感知區域、在時間間隔09：00—11：00 內停留在感知任務2 的感知區域。用戶B 在時間間隔08：00—10：00 內停留在感知任務1 的感知區域、在時間間隔10：00—11：00 內停留在感知任務2 的感知區域。

圖1 顯性時空關聯狀態Fig.1 Dominant spatial-temporal association status

感知任務1 和感知任務2 是基于感知任務的顯性時空關聯，因為感知任務1 和感知任務2 有重疊時間，重疊時間間隔為09：00—10：00。另外，空間重疊為陰影部分，在任務發布后用戶只需滿足該部分的時空要求。感知任務3 和感知任務4 是基于感知任務的覆蓋顯性時空關聯，因為感知任務3 覆蓋感知任務4，所以發布任務后只需滿足感知任務3 的時空要求。

用戶A 和用戶B 是基于用戶的顯性時空關聯，如果只招募用戶A，感知任務1 無法完成，如果只招募用戶B，感知任務2 無法完成，為保證感知任務1、感知任務2 都被完成，任務發布者和參與用戶所在的群智感知平臺會同時招募用戶A 和用戶B。此時，在用戶A 和用戶B 的時空狀態中存在重復的時空狀態，即在時間間隔08：00—09：00 內用戶A 和用戶B 均停留在感知任務1 的感知區域、在時間間隔10：00—11：00 內均停留在感知任務2 的感知區域。

2.3 隱性時空關聯模型

基于用戶當前的時間和空間因素，用戶僅參與其中某些任務，但是隨著用戶移動，用戶的時間和空間因素會發生改變，此時用戶可以參與一些額外任務。對于這種情況的用戶，可以稱為該用戶存在隱性時空關聯。在實際情況中無法知道用戶未來移動方向，但是可基于用戶之前移動情況進行預測，因此考慮馬爾科夫模型得到用戶在某一時間間隔內從一個路段l1移動到另一個路段l2的概率。

本文假設用戶i的時空狀態為Li={1，2，…，l}，其表示用戶當前所在的路段位置；表示用戶i在第n個狀態時的路段位置表示用戶i在第n個時空狀態時的開始時間，即用戶i進入第n個路段的時間；表示用戶i在路段的停留時間。

用戶i在時間間隔t內從路段l1到路段l2的概率為：

如圖2 所示，通過馬爾科夫模型預測用戶從路段l1移動到路段l2的概率，顯示用戶1 的歷史時空狀態信息，用戶1在08：00到達路段，在10：00到達路段，……，在14：00 到達路段，在路段l1停留時間分別為{2，4，6，3，6}。因為從l1離開的路段總數為，從l1移動到l2的總數為，所以從空間上得到，時間間隔設置為4 h，10：00 和12：00 到達l2的時空狀態滿足該時間間隔，因此從時間上得到：

綜合時間和空間因素，用戶1 在4 h 內從l1到l2的概率為

圖2 馬爾科夫模型的預測過程Fig.2 Prediction process of Markov model

式（9）表示兩個感知任務不存在任何顯性時空關聯，即兩個完全獨立的感知任務。式（10）表示用戶i的第1 個時空信息三元組ωi可以參與任務j1，即滿足第1 個感知任務的時空要求。式（11）表示ωi不滿足第2 個感知任務ω′i的時空要求。式（12）表示用戶i的第2 個信息三元組可以參與任務j2，即滿足第2 個感知任務的時空要求。式（13）表示用戶i在時間間隔內（第2 個感知任務開始時間與第1 個感知任務結束時間的差值），從路段Pj1移動到路段Pj2的概率需要大于設定的閾值α，只有滿足該條件，馬爾科夫模型預測用戶i的時空狀態才能被認為是相對準確的。

隱性時空關聯狀態如圖3 所示。目前已知感知任務1 和感知任務2，感知任務1 的感知時間間隔為01：00—03：00、感知任務2 的感知時間間隔為04：00—06：00；用戶A 在感知時間間隔01：00—03：00 內停留在感知任務1 的感知區域，通過預測1 h 后的時空狀態得到用戶A 在感知時間間隔04：00—06：00 內停留在任務2 的感知區域。

圖3 隱性時空關聯狀態Fig.3 Recessive spatial-temporal association state

由于用戶A 為隱性時空關聯，因此用戶A 的時空狀態滿足感知任務1 的時空要求，通過預測1 h后用戶A 的時空狀態，用戶A 還可以完成感知任務2的時空要求，存在有效預測的時空狀態，即在感知時間間隔04：00—6：00 內停留在感知任務2 的感知區域。

2.4 最大化社會收益問題模型

定義4（用戶收益）群智感知平臺給用戶的報酬與用戶參與任務的花費之間的差值即為用戶收益ui，即：

對于所有感知任務，如果用戶一個感知任務都沒有完成，則表示用戶沒有參與任何感知任務，收益為0，xij=0 表示用戶i沒有參加感知任務j，xij=1 表示用戶i參加感知任務j。如果用戶完成任務，則有相應收益，pi表示平臺給用戶的報酬，cij表示用戶i參與任務j的總花費。

定義5（社會收益）社會收益包含平臺收益和用戶收益，即：

其中，vj表示平臺收益。可以發現平臺給用戶的報酬被抵消，因此得出社會收益由平臺收益和用戶參與任務的花費之間的差值所決定。社會收益越大，平臺和用戶會獲得更多的收益，雙方會更加有動力去完成群智感知任務，有利于平臺對于優質用戶的激勵。

建立如式（16）所示的目標函數，考慮時空關聯的情況下實現最大化社會收益并完成用戶激勵。

在所有感知任務發布確定的情況下，由于平臺收益固定，即vj為固定值，因此為最大化社會收益，則需要最小化用戶總花費。目標函數轉化為時空關聯情況下最小化用戶總花費并完成用戶激勵：

式（18）表示所有感知任務由用戶完成；式（19）表示所有任務只能分配給一個用戶完成；式（20）表示xij為0 或1，1 表示用戶i完成任務j，反之用戶無法完成該任務。如果是顯性時空關聯問題，則需滿足式（1）～式（4）；如果是隱性時空關聯問題，則需滿足式（9）～式（13）。

3 用戶激勵機制設計

定理1基于時空關聯性的用戶激勵問題為NP-Hard 問題。

證明為證明STIM 問題是NP-Hard 問題，將該問題轉化為傳統最小化集合覆蓋問題。因為最小化集合覆蓋問題是NP-Hard 問題，所以STIM 問題是NP-Hard 問題。給定包含n個元素的總集合U和一系列集合U的子集S1，S2，…，Sk，并且每一個子集Sk都有花費Ck，為保證總集合U被全部覆蓋，傳統最小化集合覆蓋算法最終選擇總花費最小且集合覆蓋個數多的子集，即。STIM 問題的給定情況為多個包含2 個元素（時間和空間）的感知任務總集合θ和一系列用戶的時空集合ω1，ω2，…，ωk，其中用戶集合包含3 個元素（時間、空間和花費），需要確保感知任務總集合θ被完全覆蓋。為最小化用戶花費，STIM 問題可轉化為傳統最小化集合覆蓋問題，因此STIM 問題即為NP-Hard 問題得以證明。

3.1 基于顯性時空關聯的用戶激勵算法

由于STIM 問題是NP-Hard 問題，因此利用貪婪算法求解該問題。基于顯性時空關聯的用戶激勵算法DTS 如算法1 所示，貪婪策略的核心是最小化用戶總花費和集合覆蓋個數的比值，即

算法1基于顯性時空關聯的用戶激勵算法

以DTS 算法為例，已知感知任務的時空要求θ={{[1：2 ]，{A} }，{[2：3 ]，{B}}，{[3：4 ]，{C}}}，用戶 1的時空集合為ω1={[1：2]，{B}，3}，用戶2 的時空集合為ω2={[2：3]，{B}，4}，用戶3 的時空集合為ω3={{[1：2]，[2：3]}，{A，B}，5}，用戶4 的時空集合為ω4={{[2：3]，[3：4]}，{B，C}，9}。DTS 算法得到結果為招募用戶3 和用戶4，最終總花費為9+5-4=10。因為用戶3 和用戶4 具有相同的時空狀態，即用戶2 的時空狀態為ω′={[2：3]，{B}，4}。

3.2 基于隱性時空關聯的用戶激勵算法

在解決隱性時空關聯的用戶激勵問題時，考慮用戶的歷史時空狀態以及用戶當前提交的時空狀態，利用馬爾科夫模型預測用戶的未來時空狀態，再結合顯性時空關聯的用戶激勵算法得到最終結果。基于隱性時空關聯的用戶激勵算法RTS 如算法2 所示。

算法2基于隱性時空關聯的用戶激勵算法

以RTS 算法為例，已知感知任務的時空要求：θ={{[1：2]，{A}}，{[2：3]，{B}}，{[3：4]，{C}}}，用戶1的時空集合為ω1={{[1：2 ]，[2：3]，[3：4]}，{A，B，C}，10}，用戶2 的時空集合為ω2={{[1：2 ]，[2：3]}，{A，B}，5}。經過馬爾科夫模型預測后得到最終結果為ω2={{[1：2]，[2：3]，[3：4]}，{A，B，C}，7}。因為預測的時空狀態ω′={[3：4]，{C}，6}，花費要比用戶本身直接提供的時空集合花費低，所以RTS 算法得到的結果為招募用戶2，總花費為7。

4 實驗與結果分析

4.1 仿真數據設置

仿真數據實驗時間序列列舉24 h，即24 個點，空間序列列舉26 個點。單一感知任務的時空要求分別從時間序列和空間序列中隨機各取一個點構成，需要注意多個感知任務的時空要求不能重復，在此實驗環境下最多產生24×26=624 個感知任務，因此選擇400 個感知任務作為基數。單一用戶的時空集合分別從時間序列和空間序列中各取一個點構成，時間序列先隨機選中一個開始時間點，然后按照順序選取1→2 →…→24 →1→2 →…→24；空間序列隨機選取，為完成所有感知任務，最終選擇10 000 個用戶作為基數。設置一天工作時間為8 h，因此默認單一用戶提供的時空集合數為8。預測概率閾值默認設置為0.80。本文實驗采用單一變量法控制思想，在改變某一參數值的情況下，其他參數值皆為默認參數值。

本文提出的顯性時空關聯算法DTS 為執行MCO 算法后去掉重復的時空集合并減去相應的花費，隱性時空關聯算法RTS 為經過預測得到預測時空集合后執行DTS 算法，其實驗對比算法具體如下：1）最小化花費（Minimum Cost，MC）算法，每次選擇花費低的用戶；2）最大化覆蓋（Maximum Overlap，MO）算法，每次選擇時空集合覆蓋最多的用戶；3）最小化花費覆蓋數比值（Minimum Cost Overlap，MCO）算法，每次選擇花費和集合覆蓋個數比值小的用戶。本文實驗對比參數為總花費、用戶選擇數和迭代次數，可變參數為感知任務數、用戶數、單一用戶提供的時空集合數和預測概率閾值。

4.2 仿真數據的實驗結果分析

圖4 表示感知任務數對總花費的影響。隨著感知任務數的增加，5 種算法的總花費都增加，主要原因為平臺需要招募更多的用戶來完成更多的感知任務，所以總花費增加。對于總花費而言，算法順序依次為RTS

圖4 感知任務數對總花費的影響Fig.4 Impact of the number of sensing tasks on the total cost

圖5 表示感知任務數對用戶選擇數的影響。隨著感知任務數的增加，5 種算法的用戶選擇數隨之增加，主要原因為平臺需要招募更多的用戶來完成更多的感知任務。對于用戶選擇數而言，算法順序依次為RTS

圖5 感知任務數對用戶選擇數的影響Fig.5 Impact of the number of sensing tasks on the number of user choices

圖6 表示感知任務數對迭代次數的影響。隨著感知任務數的增加，5 種算法的迭代次數隨之增加，主要原因是為完成所有感知任務，平臺需要招募更多的用戶來完成更多的感知任務，所以相應算法的迭代次數會增加。對于迭代次數而言，算法順序依次為RTS

圖6 感知任務數對迭代次數的影響Fig.6 Impact of the number of sensing tasks on the number of iterations

圖7 表示用戶數對總花費、用戶選擇數和迭代次數的影響。總體而言，隨著用戶數的增加，5 種算法得到的總花費、用戶選擇數和迭代次數基本沒有太大變化，大致呈現小幅度減少趨勢，甚至有時出現總花費高、用戶選擇數多和迭代次數多的情況。其主要原因為平臺發布的感知任務數已經固定，雖然用戶數增加，但符合感知任務時空要求的用戶數不一定再增大，反而會出現更多時空集合覆蓋少、花費高的用戶。因此，對于總花費和迭代次數而言，算法順序依次為RTS

圖7 用戶數對總花費、用戶選擇數和迭代次數的影響Fig.7 Impact of the number of users on the total cost，the number of user choices and the number of iterations

圖8 表示用戶時空集合數對于總花費、用戶選擇數和迭代次數的影響。隨著單用戶時空集合數增加，用戶選擇數以及迭代次數持續減少，但是總花費持續增加，對于MC 而言，增大幅度最大，其主要原因為相對于單用戶時空集合個數少的情況，MC 每次選擇的用戶是花費較高的用戶（時空集合多且花費高），而且這些用戶的時空集合中只有少部分符合感知任務的時空要求，因此MC 漲幅最大；DTS 和RTS基本保持不變，用戶的時空集合多，總花費高。因此，對于總花費和迭代次數而言，算法順序依次為RTS

圖8 用戶時空集合數對總花費、用戶選擇數和迭代次數的影響Fig.8 Impact of the number of user spatial-temporal sets on the total cost，the number of user choices and the number of iterations

圖9 表示預測概率閾值增大對于總花費、用戶選擇數和迭代次數的影響。預測概率閾值的增大主要影響RTS 算法，可以看出其他4 種算法的預測概率閾值增大對于總花費、用戶選擇數和迭代次數的影響較小。隨著預測概率閾值的增大，預測得到的用戶時空狀態集合越來越少，RTS 得到的結果越來越趨近DTS。因此，對于算法的總花費和迭代次數順序依次為RTS

圖9 預測概率閾值對總花費、用戶選擇數和迭代次數的影響1Fig.9 Impact of the predicted probability threshold on the total cost，the number of user choices and the number of iterations 1

4.3 真實數據集設置

真實數據集實驗采用意大利羅馬30 天內320 輛出租車的軌跡數據集［21］，采集時間為2014 年2 月1 日至2014 年3 月2 日，約7 s 更新一次經緯度，數據格式為出租車ID、日期時間、經緯度。為更加契合仿真實驗的參數設置，將羅馬地區分為大小為100×100的網格，每輛出租車的軌跡經緯度轉化為網格序號，表示出租車所在的空間范圍；將每輛出租車進入和離開網格的時間表示出租車的時間范圍。實驗中用戶數及單一用戶提供的時空集合數為固定，因此改變感知任務數和預測概率閾值來驗證算法的有效性，其他參數設置和仿真數據實驗參數設置保持一致。

4.4 真實數據集的實驗結果分析

圖10 表示感知任務數對總花費、用戶選擇數和迭代次數的影響。對比仿真數據實驗結果，對于總花費而言，算法順序依次為RTS

圖10 感知任務數對總花費、用戶選擇數和迭代次數的影響Fig.10 Impact of the number of sensing tasks on the total cost，the number of user choices and the number of iterations

圖11 表示預測概率閾值對總花費、用戶選擇數和迭代次數的影響。對比仿真數據實驗的結果，除了總花費的影響外，其他沒有太大變化，規律和邏輯都與仿真數據實驗一致，隨著預測概率閾值的增加，RTS 越來越趨近DTS。因此，對于總花費而言，算法順序依次為RTS

圖11 預測概率閾值對總花費、用戶選擇數和迭代次數的影響2Fig.11 Impact of the predicted probability threshold on the total cost，the number of user choices and the number of iterations 2

5 結束語

本文將時空關聯的用戶激勵問題分為顯性時空關聯和隱性時空關聯的用戶激勵問題，并提出RTS 算法和DTS 算法對其進行求解。通過仿真數據實驗和真實數據集實驗可以得出，RTS 算法和DTS 算法相比MC算法、MO 算法、MCO 算法具有更低的總花費、用戶選擇數和迭代次數，從而驗證基于時空關聯性的用戶激勵機制的有效性。然而本文在考慮隱性時空關聯性時對于用戶任務執行情況的預測存在不確定性，后續將對此做進一步研究，實現更高效的用戶激勵機制。