周 強(qiáng)，李 鵬，聶 雷

（1.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430065；2.智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430065）

0 概述

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

1 相關(guān)工作

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

在用戶招募方面，文獻(xiàn)［5］從用戶社交性以及用戶和感知目標(biāo)的距離角度進(jìn)行群智感知用戶招募。文獻(xiàn)［6］對(duì)具有最低花費(fèi)且用戶軌跡覆蓋相關(guān)興趣點(diǎn)的用戶進(jìn)行招募，且將招募問(wèn)題轉(zhuǎn)化為集合覆蓋問(wèn)題。文獻(xiàn)［7］建立用戶質(zhì)量模型、估算用戶信譽(yù)模型來(lái)選擇高質(zhì)量用戶，且利用沙普利值計(jì)算用戶酬勞。

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

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

上述傳統(tǒng)激勵(lì)機(jī)制未同時(shí)考慮時(shí)空及時(shí)空關(guān)聯(lián)性因素，因此造成很多感知任務(wù)難以執(zhí)行。基于時(shí)空因素，文獻(xiàn)［19］采用深度學(xué)習(xí)模型，提出基于時(shí)空相關(guān)性的短時(shí)交通流量預(yù)測(cè)法，但該方法更多關(guān)注顯性關(guān)聯(lián)性。文獻(xiàn)［20］研究時(shí)空因素下的用戶招募和激勵(lì)機(jī)制，但未考慮時(shí)空重疊和關(guān)聯(lián)性問(wèn)題，而對(duì)比傳統(tǒng)激勵(lì)機(jī)制發(fā)現(xiàn)，很多任務(wù)和用戶具有時(shí)空重疊和關(guān)聯(lián)特性。為解決感知任務(wù)完成率低且花費(fèi)高的問(wèn)題，本文提出基于時(shí)空關(guān)聯(lián)性的用戶激勵(lì)機(jī)制STIM。

2 時(shí)空關(guān)聯(lián)模型及問(wèn)題定義

2.1 系統(tǒng)模型

假設(shè)系統(tǒng)中發(fā)布一系列群智感知任務(wù)S={S1，S2，…，Sm}，對(duì)于任意任務(wù)Sj∈S均存在時(shí)間范圍和空間范圍Pj={l1，l2，…，lm}，其中表示感知任務(wù)的開(kāi)始時(shí)間表示感知任務(wù)的結(jié)束時(shí)間，lm表示感知任務(wù)需要感知的路段。結(jié)合時(shí)間和空間范圍，通過(guò)二元組，{l1，l2，…，lm} }來(lái)表示任務(wù)時(shí)空要求，即在時(shí)間范圍內(nèi)經(jīng)過(guò)的路段，例如θ1={[7：11]，{l1，l2}}表示任務(wù)1 需要用戶從07：00 到11：00 經(jīng)過(guò)l1、l2兩個(gè)路段。

假設(shè)系統(tǒng)有一系列用戶U={U1，U2，…，Un}，對(duì)于任意用戶Ui∈U均存在用戶三元組ωi=，{l1，l2，…，lm}，ci}，其中表示用戶能參與任務(wù)的開(kāi)始時(shí)間表示用戶能參與感知任務(wù)的結(jié)束時(shí)間，ci表示用戶花費(fèi)，例如ω1={[7：11]，{l1}，10}表示用戶1 從07：00 到10：00 經(jīng)過(guò)l1路段，花費(fèi)為10。

2.2 顯性時(shí)空關(guān)聯(lián)模型

顯性時(shí)空關(guān)聯(lián)表示感知任務(wù)與感知任務(wù)、用戶與用戶間存在相同時(shí)空特性，因此分別定義基于感知任務(wù)和用戶的顯性時(shí)空關(guān)聯(lián)。

定義1（基于感知任務(wù)的顯性時(shí)空關(guān)聯(lián)）對(duì)于任意兩個(gè)任務(wù)Sj1，Sj2∈S，滿足時(shí)空重疊（見(jiàn)式（1）），則稱該感知任務(wù)集合是基于感知任務(wù)的顯性時(shí)空關(guān)聯(lián)。

對(duì)于任意兩個(gè)任務(wù)Sj1，Sj2∈S，滿足時(shí)空重疊和時(shí)空覆蓋（見(jiàn)式（2）），則稱該感知任務(wù)集合是基于感知任務(wù)的覆蓋顯性時(shí)空關(guān)聯(lián)?？梢?jiàn)，時(shí)空覆蓋任務(wù)一定是時(shí)空重疊任務(wù)，但是時(shí)空重疊任務(wù)不一定是時(shí)空覆蓋任務(wù)，即時(shí)空重疊包含時(shí)空覆蓋。

將所有基于顯性時(shí)空關(guān)聯(lián)的感知任務(wù)集合視為一個(gè)感知任務(wù)，用戶的時(shí)空集合可以同時(shí)滿足多個(gè)任務(wù)的時(shí)空需求，大幅提高運(yùn)算效率。

定義2（基于用戶的顯性時(shí)空關(guān)聯(lián)）對(duì)于任意兩個(gè)招募用戶Ui1，Ui2∈U，可能存在部分相同的時(shí)空集合（滿足式（3）），則稱有相同時(shí)空的用戶集為基于用戶的顯性時(shí)空關(guān)聯(lián)。

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

圖1 表示顯性時(shí)空關(guān)聯(lián)狀態(tài)。已知感知任務(wù)1～感知任務(wù)4，感知任務(wù)1的感知時(shí)間間隔為08：00—10：00、感知任務(wù)2 的感知時(shí)間間隔為09：00—11：00、感知任務(wù)3的感知時(shí)間間隔為01：00—03：00、感知任務(wù)4的感知時(shí)間間隔為01：30—02：30；感知任務(wù)1和感知任務(wù)2的感知區(qū)域有重疊部分，感知任務(wù)3 的感知區(qū)域完全覆蓋感知任務(wù)4 的感知區(qū)域。用戶A 在時(shí)間間隔08：00—09：00 內(nèi)停留在感知任務(wù)1 的感知區(qū)域、在時(shí)間間隔09：00—11：00 內(nèi)停留在感知任務(wù)2 的感知區(qū)域。用戶B 在時(shí)間間隔08：00—10：00 內(nèi)停留在感知任務(wù)1 的感知區(qū)域、在時(shí)間間隔10：00—11：00 內(nèi)停留在感知任務(wù)2 的感知區(qū)域。

圖1 顯性時(shí)空關(guān)聯(lián)狀態(tài)Fig.1 Dominant spatial-temporal association status

感知任務(wù)1 和感知任務(wù)2 是基于感知任務(wù)的顯性時(shí)空關(guān)聯(lián)，因?yàn)楦兄蝿?wù)1 和感知任務(wù)2 有重疊時(shí)間，重疊時(shí)間間隔為09：00—10：00。另外，空間重疊為陰影部分，在任務(wù)發(fā)布后用戶只需滿足該部分的時(shí)空要求。感知任務(wù)3 和感知任務(wù)4 是基于感知任務(wù)的覆蓋顯性時(shí)空關(guān)聯(lián)，因?yàn)楦兄蝿?wù)3 覆蓋感知任務(wù)4，所以發(fā)布任務(wù)后只需滿足感知任務(wù)3 的時(shí)空要求。

用戶A 和用戶B 是基于用戶的顯性時(shí)空關(guān)聯(lián)，如果只招募用戶A，感知任務(wù)1 無(wú)法完成，如果只招募用戶B，感知任務(wù)2 無(wú)法完成，為保證感知任務(wù)1、感知任務(wù)2 都被完成，任務(wù)發(fā)布者和參與用戶所在的群智感知平臺(tái)會(huì)同時(shí)招募用戶A 和用戶B。此時(shí)，在用戶A 和用戶B 的時(shí)空狀態(tài)中存在重復(fù)的時(shí)空狀態(tài)，即在時(shí)間間隔08：00—09：00 內(nèi)用戶A 和用戶B 均停留在感知任務(wù)1 的感知區(qū)域、在時(shí)間間隔10：00—11：00 內(nèi)均停留在感知任務(wù)2 的感知區(qū)域。

2.3 隱性時(shí)空關(guān)聯(lián)模型

基于用戶當(dāng)前的時(shí)間和空間因素，用戶僅參與其中某些任務(wù)，但是隨著用戶移動(dòng)，用戶的時(shí)間和空間因素會(huì)發(fā)生改變，此時(shí)用戶可以參與一些額外任務(wù)。對(duì)于這種情況的用戶，可以稱為該用戶存在隱性時(shí)空關(guān)聯(lián)。在實(shí)際情況中無(wú)法知道用戶未來(lái)移動(dòng)方向，但是可基于用戶之前移動(dòng)情況進(jìn)行預(yù)測(cè)，因此考慮馬爾科夫模型得到用戶在某一時(shí)間間隔內(nèi)從一個(gè)路段l1移動(dòng)到另一個(gè)路段l2的概率。

本文假設(shè)用戶i的時(shí)空狀態(tài)為L(zhǎng)i={1，2，…，l}，其表示用戶當(dāng)前所在的路段位置；表示用戶i在第n個(gè)狀態(tài)時(shí)的路段位置表示用戶i在第n個(gè)時(shí)空狀態(tài)時(shí)的開(kāi)始時(shí)間，即用戶i進(jìn)入第n個(gè)路段的時(shí)間；表示用戶i在路段的停留時(shí)間。

用戶i在時(shí)間間隔t內(nèi)從路段l1到路段l2的概率為：

如圖2 所示，通過(guò)馬爾科夫模型預(yù)測(cè)用戶從路段l1移動(dòng)到路段l2的概率，顯示用戶1 的歷史時(shí)空狀態(tài)信息，用戶1在08：00到達(dá)路段，在10：00到達(dá)路段，……，在14：00 到達(dá)路段，在路段l1停留時(shí)間分別為{2，4，6，3，6}。因?yàn)閺膌1離開(kāi)的路段總數(shù)為，從l1移動(dòng)到l2的總數(shù)為，所以從空間上得到，時(shí)間間隔設(shè)置為4 h，10：00 和12：00 到達(dá)l2的時(shí)空狀態(tài)滿足該時(shí)間間隔，因此從時(shí)間上得到：

綜合時(shí)間和空間因素，用戶1 在4 h 內(nèi)從l1到l2的概率為

圖2 馬爾科夫模型的預(yù)測(cè)過(guò)程Fig.2 Prediction process of Markov model

式（9）表示兩個(gè)感知任務(wù)不存在任何顯性時(shí)空關(guān)聯(lián)，即兩個(gè)完全獨(dú)立的感知任務(wù)。式（10）表示用戶i的第1 個(gè)時(shí)空信息三元組ωi可以參與任務(wù)j1，即滿足第1 個(gè)感知任務(wù)的時(shí)空要求。式（11）表示ωi不滿足第2 個(gè)感知任務(wù)ω′i的時(shí)空要求。式（12）表示用戶i的第2 個(gè)信息三元組可以參與任務(wù)j2，即滿足第2 個(gè)感知任務(wù)的時(shí)空要求。式（13）表示用戶i在時(shí)間間隔內(nèi)（第2 個(gè)感知任務(wù)開(kāi)始時(shí)間與第1 個(gè)感知任務(wù)結(jié)束時(shí)間的差值），從路段Pj1移動(dòng)到路段Pj2的概率需要大于設(shè)定的閾值α，只有滿足該條件，馬爾科夫模型預(yù)測(cè)用戶i的時(shí)空狀態(tài)才能被認(rèn)為是相對(duì)準(zhǔn)確的。

隱性時(shí)空關(guān)聯(lián)狀態(tài)如圖3 所示。目前已知感知任務(wù)1 和感知任務(wù)2，感知任務(wù)1 的感知時(shí)間間隔為01：00—03：00、感知任務(wù)2 的感知時(shí)間間隔為04：00—06：00；用戶A 在感知時(shí)間間隔01：00—03：00 內(nèi)停留在感知任務(wù)1 的感知區(qū)域，通過(guò)預(yù)測(cè)1 h 后的時(shí)空狀態(tài)得到用戶A 在感知時(shí)間間隔04：00—06：00 內(nèi)停留在任務(wù)2 的感知區(qū)域。

圖3 隱性時(shí)空關(guān)聯(lián)狀態(tài)Fig.3 Recessive spatial-temporal association state

由于用戶A 為隱性時(shí)空關(guān)聯(lián)，因此用戶A 的時(shí)空狀態(tài)滿足感知任務(wù)1 的時(shí)空要求，通過(guò)預(yù)測(cè)1 h后用戶A 的時(shí)空狀態(tài)，用戶A 還可以完成感知任務(wù)2的時(shí)空要求，存在有效預(yù)測(cè)的時(shí)空狀態(tài)，即在感知時(shí)間間隔04：00—6：00 內(nèi)停留在感知任務(wù)2 的感知區(qū)域。

2.4 最大化社會(huì)收益問(wèn)題模型

定義4（用戶收益）群智感知平臺(tái)給用戶的報(bào)酬與用戶參與任務(wù)的花費(fèi)之間的差值即為用戶收益ui，即：

對(duì)于所有感知任務(wù)，如果用戶一個(gè)感知任務(wù)都沒(méi)有完成，則表示用戶沒(méi)有參與任何感知任務(wù)，收益為0，xij=0 表示用戶i沒(méi)有參加感知任務(wù)j，xij=1 表示用戶i參加感知任務(wù)j。如果用戶完成任務(wù)，則有相應(yīng)收益，pi表示平臺(tái)給用戶的報(bào)酬，cij表示用戶i參與任務(wù)j的總花費(fèi)。

定義5（社會(huì)收益）社會(huì)收益包含平臺(tái)收益和用戶收益，即：

其中，vj表示平臺(tái)收益?？梢园l(fā)現(xiàn)平臺(tái)給用戶的報(bào)酬被抵消，因此得出社會(huì)收益由平臺(tái)收益和用戶參與任務(wù)的花費(fèi)之間的差值所決定。社會(huì)收益越大，平臺(tái)和用戶會(huì)獲得更多的收益，雙方會(huì)更加有動(dòng)力去完成群智感知任務(wù)，有利于平臺(tái)對(duì)于優(yōu)質(zhì)用戶的激勵(lì)。

建立如式（16）所示的目標(biāo)函數(shù)，考慮時(shí)空關(guān)聯(lián)的情況下實(shí)現(xiàn)最大化社會(huì)收益并完成用戶激勵(lì)。

在所有感知任務(wù)發(fā)布確定的情況下，由于平臺(tái)收益固定，即vj為固定值，因此為最大化社會(huì)收益，則需要最小化用戶總花費(fèi)。目標(biāo)函數(shù)轉(zhuǎn)化為時(shí)空關(guān)聯(lián)情況下最小化用戶總花費(fèi)并完成用戶激勵(lì)：

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

3 用戶激勵(lì)機(jī)制設(shè)計(jì)

定理1基于時(shí)空關(guān)聯(lián)性的用戶激勵(lì)問(wèn)題為NP-Hard 問(wèn)題。

證明為證明STIM 問(wèn)題是NP-Hard 問(wèn)題，將該問(wèn)題轉(zhuǎn)化為傳統(tǒng)最小化集合覆蓋問(wèn)題。因?yàn)樽钚』细采w問(wèn)題是NP-Hard 問(wèn)題，所以STIM 問(wèn)題是NP-Hard 問(wèn)題。給定包含n個(gè)元素的總集合U和一系列集合U的子集S1，S2，…，Sk，并且每一個(gè)子集Sk都有花費(fèi)Ck，為保證總集合U被全部覆蓋，傳統(tǒng)最小化集合覆蓋算法最終選擇總花費(fèi)最小且集合覆蓋個(gè)數(shù)多的子集，即。STIM 問(wèn)題的給定情況為多個(gè)包含2 個(gè)元素（時(shí)間和空間）的感知任務(wù)總集合θ和一系列用戶的時(shí)空集合ω1，ω2，…，ωk，其中用戶集合包含3 個(gè)元素（時(shí)間、空間和花費(fèi)），需要確保感知任務(wù)總集合θ被完全覆蓋。為最小化用戶花費(fèi)，STIM 問(wèn)題可轉(zhuǎn)化為傳統(tǒng)最小化集合覆蓋問(wèn)題，因此STIM 問(wèn)題即為NP-Hard 問(wèn)題得以證明。

3.1 基于顯性時(shí)空關(guān)聯(lián)的用戶激勵(lì)算法

由于STIM 問(wèn)題是NP-Hard 問(wèn)題，因此利用貪婪算法求解該問(wèn)題。基于顯性時(shí)空關(guān)聯(lián)的用戶激勵(lì)算法DTS 如算法1 所示，貪婪策略的核心是最小化用戶總花費(fèi)和集合覆蓋個(gè)數(shù)的比值，即

算法1基于顯性時(shí)空關(guān)聯(lián)的用戶激勵(lì)算法

以DTS 算法為例，已知感知任務(wù)的時(shí)空要求θ={{[1：2 ]，{A} }，{[2：3 ]，{B}}，{[3：4 ]，{C}}}，用戶 1的時(shí)空集合為ω1={[1：2]，{B}，3}，用戶2 的時(shí)空集合為ω2={[2：3]，{B}，4}，用戶3 的時(shí)空集合為ω3={{[1：2]，[2：3]}，{A，B}，5}，用戶4 的時(shí)空集合為ω4={{[2：3]，[3：4]}，{B，C}，9}。DTS 算法得到結(jié)果為招募用戶3 和用戶4，最終總花費(fèi)為9+5-4=10。因?yàn)橛脩? 和用戶4 具有相同的時(shí)空狀態(tài)，即用戶2 的時(shí)空狀態(tài)為ω′={[2：3]，{B}，4}。

3.2 基于隱性時(shí)空關(guān)聯(lián)的用戶激勵(lì)算法

在解決隱性時(shí)空關(guān)聯(lián)的用戶激勵(lì)問(wèn)題時(shí)，考慮用戶的歷史時(shí)空狀態(tài)以及用戶當(dāng)前提交的時(shí)空狀態(tài)，利用馬爾科夫模型預(yù)測(cè)用戶的未來(lái)時(shí)空狀態(tài)，再結(jié)合顯性時(shí)空關(guān)聯(lián)的用戶激勵(lì)算法得到最終結(jié)果?；陔[性時(shí)空關(guān)聯(lián)的用戶激勵(lì)算法RTS 如算法2 所示。

算法2基于隱性時(shí)空關(guān)聯(lián)的用戶激勵(lì)算法

以RTS 算法為例，已知感知任務(wù)的時(shí)空要求：θ={{[1：2]，{A}}，{[2：3]，{B}}，{[3：4]，{C}}}，用戶1的時(shí)空集合為ω1={{[1：2 ]，[2：3]，[3：4]}，{A，B，C}，10}，用戶2 的時(shí)空集合為ω2={{[1：2 ]，[2：3]}，{A，B}，5}。經(jīng)過(guò)馬爾科夫模型預(yù)測(cè)后得到最終結(jié)果為ω2={{[1：2]，[2：3]，[3：4]}，{A，B，C}，7}。因?yàn)轭A(yù)測(cè)的時(shí)空狀態(tài)ω′={[3：4]，{C}，6}，花費(fèi)要比用戶本身直接提供的時(shí)空集合花費(fèi)低，所以RTS 算法得到的結(jié)果為招募用戶2，總花費(fèi)為7。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 仿真數(shù)據(jù)設(shè)置

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

本文提出的顯性時(shí)空關(guān)聯(lián)算法DTS 為執(zhí)行MCO 算法后去掉重復(fù)的時(shí)空集合并減去相應(yīng)的花費(fèi)，隱性時(shí)空關(guān)聯(lián)算法RTS 為經(jīng)過(guò)預(yù)測(cè)得到預(yù)測(cè)時(shí)空集合后執(zhí)行DTS 算法，其實(shí)驗(yàn)對(duì)比算法具體如下：1）最小化花費(fèi)（Minimum Cost，MC）算法，每次選擇花費(fèi)低的用戶；2）最大化覆蓋（Maximum Overlap，MO）算法，每次選擇時(shí)空集合覆蓋最多的用戶；3）最小化花費(fèi)覆蓋數(shù)比值（Minimum Cost Overlap，MCO）算法，每次選擇花費(fèi)和集合覆蓋個(gè)數(shù)比值小的用戶。本文實(shí)驗(yàn)對(duì)比參數(shù)為總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)，可變參數(shù)為感知任務(wù)數(shù)、用戶數(shù)、單一用戶提供的時(shí)空集合數(shù)和預(yù)測(cè)概率閾值。

4.2 仿真數(shù)據(jù)的實(shí)驗(yàn)結(jié)果分析

圖4 表示感知任務(wù)數(shù)對(duì)總花費(fèi)的影響。隨著感知任務(wù)數(shù)的增加，5 種算法的總花費(fèi)都增加，主要原因?yàn)槠脚_(tái)需要招募更多的用戶來(lái)完成更多的感知任務(wù)，所以總花費(fèi)增加。對(duì)于總花費(fèi)而言，算法順序依次為RTS

圖4 感知任務(wù)數(shù)對(duì)總花費(fèi)的影響Fig.4 Impact of the number of sensing tasks on the total cost

圖5 表示感知任務(wù)數(shù)對(duì)用戶選擇數(shù)的影響。隨著感知任務(wù)數(shù)的增加，5 種算法的用戶選擇數(shù)隨之增加，主要原因?yàn)槠脚_(tái)需要招募更多的用戶來(lái)完成更多的感知任務(wù)。對(duì)于用戶選擇數(shù)而言，算法順序依次為RTS

圖5 感知任務(wù)數(shù)對(duì)用戶選擇數(shù)的影響Fig.5 Impact of the number of sensing tasks on the number of user choices

圖6 表示感知任務(wù)數(shù)對(duì)迭代次數(shù)的影響。隨著感知任務(wù)數(shù)的增加，5 種算法的迭代次數(shù)隨之增加，主要原因是為完成所有感知任務(wù)，平臺(tái)需要招募更多的用戶來(lái)完成更多的感知任務(wù)，所以相應(yīng)算法的迭代次數(shù)會(huì)增加。對(duì)于迭代次數(shù)而言，算法順序依次為RTS

圖6 感知任務(wù)數(shù)對(duì)迭代次數(shù)的影響Fig.6 Impact of the number of sensing tasks on the number of iterations

圖7 表示用戶數(shù)對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響?？傮w而言，隨著用戶數(shù)的增加，5 種算法得到的總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)基本沒(méi)有太大變化，大致呈現(xiàn)小幅度減少趨勢(shì)，甚至有時(shí)出現(xiàn)總花費(fèi)高、用戶選擇數(shù)多和迭代次數(shù)多的情況。其主要原因?yàn)槠脚_(tái)發(fā)布的感知任務(wù)數(shù)已經(jīng)固定，雖然用戶數(shù)增加，但符合感知任務(wù)時(shí)空要求的用戶數(shù)不一定再增大，反而會(huì)出現(xiàn)更多時(shí)空集合覆蓋少、花費(fèi)高的用戶。因此，對(duì)于總花費(fèi)和迭代次數(shù)而言，算法順序依次為RTS

圖7 用戶數(shù)對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響Fig.7 Impact of the number of users on the total cost，the number of user choices and the number of iterations

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

圖8 用戶時(shí)空集合數(shù)對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響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 表示預(yù)測(cè)概率閾值增大對(duì)于總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響。預(yù)測(cè)概率閾值的增大主要影響RTS 算法，可以看出其他4 種算法的預(yù)測(cè)概率閾值增大對(duì)于總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響較小。隨著預(yù)測(cè)概率閾值的增大，預(yù)測(cè)得到的用戶時(shí)空狀態(tài)集合越來(lái)越少，RTS 得到的結(jié)果越來(lái)越趨近DTS。因此，對(duì)于算法的總花費(fèi)和迭代次數(shù)順序依次為RTS

圖9 預(yù)測(cè)概率閾值對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響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 真實(shí)數(shù)據(jù)集設(shè)置

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

4.4 真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

圖10 表示感知任務(wù)數(shù)對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響。對(duì)比仿真數(shù)據(jù)實(shí)驗(yàn)結(jié)果，對(duì)于總花費(fèi)而言，算法順序依次為RTS

圖10 感知任務(wù)數(shù)對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響Fig.10 Impact of the number of sensing tasks on the total cost，the number of user choices and the number of iterations

圖11 表示預(yù)測(cè)概率閾值對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響。對(duì)比仿真數(shù)據(jù)實(shí)驗(yàn)的結(jié)果，除了總花費(fèi)的影響外，其他沒(méi)有太大變化，規(guī)律和邏輯都與仿真數(shù)據(jù)實(shí)驗(yàn)一致，隨著預(yù)測(cè)概率閾值的增加，RTS 越來(lái)越趨近DTS。因此，對(duì)于總花費(fèi)而言，算法順序依次為RTS

圖11 預(yù)測(cè)概率閾值對(duì)總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)的影響2Fig.11 Impact of the predicted probability threshold on the total cost，the number of user choices and the number of iterations 2

5 結(jié)束語(yǔ)

本文將時(shí)空關(guān)聯(lián)的用戶激勵(lì)問(wèn)題分為顯性時(shí)空關(guān)聯(lián)和隱性時(shí)空關(guān)聯(lián)的用戶激勵(lì)問(wèn)題，并提出RTS 算法和DTS 算法對(duì)其進(jìn)行求解。通過(guò)仿真數(shù)據(jù)實(shí)驗(yàn)和真實(shí)數(shù)據(jù)集實(shí)驗(yàn)可以得出，RTS 算法和DTS 算法相比MC算法、MO 算法、MCO 算法具有更低的總花費(fèi)、用戶選擇數(shù)和迭代次數(shù)，從而驗(yàn)證基于時(shí)空關(guān)聯(lián)性的用戶激勵(lì)機(jī)制的有效性。然而本文在考慮隱性時(shí)空關(guān)聯(lián)性時(shí)對(duì)于用戶任務(wù)執(zhí)行情況的預(yù)測(cè)存在不確定性，后續(xù)將對(duì)此做進(jìn)一步研究，實(shí)現(xiàn)更高效的用戶激勵(lì)機(jī)制。