面向用戶協(xié)作對的移動群智感知激勵機制

楊桂松，李漢卿，何杏宇

1(上海理工大學 光電信息與計算機工程學院，上海200093) 2(上海理工大學 出版印刷與藝術(shù)設(shè)計學院，上海200093)

1 引 言

移動群智感知[1]是一種利用大量用戶所攜帶的智能終端設(shè)備隨時隨地感知和獲取周圍環(huán)境信息的方法[2].目前，移動群智感知已經(jīng)催生了眾多應用，如交通監(jiān)控[3，4]，環(huán)境監(jiān)測[5-7]，移動社交推薦[8，9]等.這些應用的成功運行離不開無數(shù)用戶的感知行為.然而，在執(zhí)行感知任務的過程中，用戶消耗的是自己的資源，如電池電量、計算能力、時間等.為了合理補償用戶在感知過程中的消耗，以及提高用戶參與感知任務的積極性，需要設(shè)計相應的激勵機制[10]，使盡可能多的用戶參與到感知活動中，保證感知任務按時按需按量[11]完成.

激勵機制的目標是激勵盡可能多的用戶參與感知活動.然而，由于平臺的理想化以及用戶的不確定性，使得傳統(tǒng)的激勵機制在用戶招募方面遭遇瓶頸(更多具備一定感知能力的用戶等待被發(fā)現(xiàn))，在報酬支付設(shè)計方面面臨一定的挑戰(zhàn)(如何同時兼顧平臺與用戶的利益).平臺的理想化在于，平臺默認能夠參與感知任務的用戶是能獨自完成任務的用戶，對于具備一定感知能力卻又不足以獨自完成任務的用戶，直接排除他們參與感知任務的可能性.用戶的不確定性在于，用戶的感知能力取決于感知設(shè)備的能力，自身的感知時間以及對任務感興趣的程度等因素.考慮到以上兩點，移動群智感知中的任務的有效覆蓋比例無法得到提升，進一步地，造成用戶效用和平臺工作效率低下.當前，大多數(shù)關(guān)于激勵機制的研究工作假設(shè)平臺將用戶狀態(tài)理想化[12-14]，缺乏考慮具備感知資源但無法獨自完成任務的用戶類型，而非理想化的情況更符合實際場景.

為了解決上述問題，本文從感知時間的角度考慮，提出了一種面向用戶協(xié)作對的激勵機制.主要貢獻如下：

1)研究并提出了移動群智感知的一個新問題，即如何充分利用資源較少的用戶來提高移動群智感知系統(tǒng)的工作效率(用戶參與比例，任務覆蓋比例及用戶平均效用).

2)提出協(xié)作對的概念，設(shè)計時間協(xié)作模型，旨在解決用戶無法獨自執(zhí)行任務的難題.

3)提出基于斯塔克爾伯格博弈的激勵方式解決了用戶最佳報酬的問題，同時提高了協(xié)作用戶的效用值.

2 相關(guān)工作

一些工作研究了不同類型的協(xié)作式感知問題.Lee等人在文獻[15]中提出CoMon平臺來解決最小化設(shè)備能量消耗的協(xié)作式感知問題.文獻[16，17]從用戶專業(yè)技能方面研究協(xié)作式感知問題，考慮招募具有不同專業(yè)技能的用戶組成協(xié)作小組，共同完成復雜任務.文獻[18]提出一種基于效用的節(jié)點協(xié)作感知方法以解決移動設(shè)備異構(gòu)型與感知信息質(zhì)量相矛盾的問題.與這些研究工作不同，本文考慮用戶感知時間跨度受限的問題來進行協(xié)作感知設(shè)計.

在移動群智感知中，用戶的報酬問題是激勵用戶參與感知任務的關(guān)鍵所在.Xiong等人設(shè)計的CrowdTasker[19]采用靜態(tài)報酬與動態(tài)報酬相結(jié)合的方式.其中靜態(tài)報酬是固定支付給感知用戶的獎勵；動態(tài)報酬則與分配給感知用戶的感知周期數(shù)成正比.拍賣機制的利用也是基于報酬的激勵機制設(shè)計的一大特點.Yang等人[20，21]分別采用Stackelberg博弈與拍賣機制設(shè)計了兩種激勵模型，以促使足夠多的用戶參與感知任務.前一種激勵模型采用Stackelberg博弈理論，系統(tǒng)預先設(shè)定獎勵金額，經(jīng)過博弈確定任務執(zhí)行者以最大化平臺與感知用戶的效益.后一種激勵模型基于拍賣機制，在滿足任務要求的前提下，用戶提出可以接受的報酬底價，經(jīng)過競拍決定感知任務的執(zhí)行者.文獻[22]基于動態(tài)定價設(shè)計了新型的反向拍賣激勵機制，利用用戶聲明的投標價格，將感知數(shù)據(jù)出售給合適的服務提供商.該機制能夠降低極力擁護持續(xù)參與感知任務的成本，提高社會福利，并公平地給與用戶報酬獎勵.文獻[23]設(shè)計了一個精確的激勵機制，該機制讓參與者在信息不完全的情況下進行貝葉斯博弈，以避免參與者出現(xiàn)虛假效用的局面，從而提高感知數(shù)據(jù)質(zhì)量.文獻[24]為了激勵參與者，考慮了社會網(wǎng)絡(luò)效應，并構(gòu)建了不完全信息下的貝葉斯Stackelberg博弈模型來分析服務提供商和參與者之間的交互作用.文獻[25]考慮了具有時間敏感性的數(shù)據(jù)收集場景，設(shè)計了基于討價還價博弈的激勵機制，并通過納什均衡得到最大化收集者效用的解.

上述研究大都假設(shè)參與感知任務的用戶能獨自完成任務，沒有考慮處于能力不足狀態(tài)的用戶也能參與感知任務的情況.激勵機制的目標是促使更多用戶參與感知任務，從用戶角度來說，在預算一定的前提下，以最大程度發(fā)掘不同能力的用戶為目標設(shè)計激勵機制，會起到更好的激勵作用.

3 時間協(xié)作模型

考慮到用戶感知時間的高效利用，協(xié)作對的感知時間跨度在滿足任務需求的基礎(chǔ)上應該盡可能的小.為此，本文提出時間重疊率的概念，時間重疊率ORx，y由3部分組成：

2)后延：若用戶Ux的感知時間跨度包含對應任務τj的結(jié)束時間，則該任務的結(jié)束時間到該用戶的結(jié)束時間這段時間稱之為“后延”，用afxj表示.

3)時間重疊：任意兩個用戶Ux、Uy的感知時間的重疊部分，用OLx，y表示.

本文將時間重疊率定義為3個部分之和與任務時間跨度的比值.該模型的目標是最小化協(xié)作對的時間重疊率：

(1)

約束條件為：

(2)

(3)

(4)

(5)

(6)

(7)

其中公式(2)表明，協(xié)作對的時間跨度不能小于任務的時間跨度；公式(3)表明，構(gòu)成協(xié)作對的兩位用戶在感知時間上不能存在包含關(guān)系，且兩者感知時間存在連接關(guān)系(第2位用戶的開始時間小于或等于第1位用戶的結(jié)束時間)；公式(4)、公式(5)表明，協(xié)作對中的第1位用戶的感知時間跨度要包含任務的開始時間；公式(6)、公式(7)表明，協(xié)作對中的第2位用戶的感知時間跨度要包含任務的結(jié)束時間.

4 激勵機制

4.1 協(xié)作對形成

協(xié)作對形成算法的過程如算法1所示，其具體描述如下：

1)用戶主觀協(xié)作意愿評估(算法1第1-3行)

用戶的主觀協(xié)作意愿是通過分析他們的實際興趣得來的[26]，而實際興趣又與瀏覽行為密切相關(guān)，包括瀏覽內(nèi)容、瀏覽停留時長、瀏覽頻率.為了評估用戶的興趣，采用瀏覽歷史分析方法，其主要通過語義、標簽等關(guān)鍵詞來分析用戶針對特定內(nèi)容的瀏覽歷史.本文利用瀏覽歷史分析方法來分析用戶在最近TB內(nèi)的瀏覽行為，從而獲得用戶對感知任務的瀏覽次數(shù)和瀏覽停留時長，該感知任務與最后執(zhí)行的感知任務趨于一致.在統(tǒng)計時間[0，TB]內(nèi)，用戶Ui對任務τj共H次瀏覽后的興趣強度，即主觀協(xié)作意愿為：

(8)

2)時間重疊率計算并擇優(yōu)(算法1第4-16行)

在遍歷全部用戶的過程中，滿足任務類型相同、主觀協(xié)作意愿達到閾值和用戶感知時間跨度大于任務所需感知時間跨度這3點要求的協(xié)作對，對其進行時間重疊率計算.然后根據(jù)時間重疊率的計算值將選擇合適的協(xié)作對作為相應任務候選執(zhí)行者.

算法1說明協(xié)作對形成的過程.

算法1.協(xié)作對形成算法

1.輸入：用戶集合R1，任務τj

2.輸出：協(xié)作對P

3.forifrom1ton

5.endfor

6.forifrom1ton

7.fori′fromi+1ton

10. 將ORi，i′放入集合C中

11.endif

12.endfor

13.endfor

14.forORinsetC

15.ifORk，k′=min{C}

16.P=(k，k′)

17.endif

18.endfor

19.returnP

4.2 平臺-協(xié)作對博弈

雖然通過4.1節(jié)得到的協(xié)作對是具有主觀協(xié)作意愿的，但用戶受到自身資源的限制，其會權(quán)衡收益與成本(進行感知活動的成本)，從而導致用戶可能不會主動參與協(xié)作感知.因此，為了進一步激勵用戶參與協(xié)作感知，本文從博弈論角度制定激勵機制策略，提高用戶的客觀協(xié)作意愿.

協(xié)作對和平臺之間的博弈是通過他們的報價來定義的.理論上，有序報價比隨機報價能更快達到均衡價格.因此，引入斯塔克爾伯格博弈[27]，并通過領(lǐng)導者和追隨者序列的動態(tài)博弈改進隨機報價方法.

給予協(xié)作對合理的獎勵可以有效地激勵用戶的客觀協(xié)作意愿，因此在博弈之前，應該定量分析協(xié)作對的感知成本.

(9)

(10)

(11)

2)博弈激勵：由上文可知，用戶在執(zhí)行感知任務時會產(chǎn)生一定的資源消耗.根據(jù)用戶的自私性，需要一定的報酬來對此消耗進行補償.然而，用戶一般是理性的，希望得到更多的報酬.同樣，平臺也是理性的，希望用盡可能少的報酬來獲得用戶的感知數(shù)據(jù)，因此，雙方之間存在矛盾.為了解決這個矛盾，本文引入了基于有序報價的斯塔克爾伯格博弈，博弈后可以得到一個合理的支付方案，從而有效地激勵用戶的客觀協(xié)作意愿.

斯塔克爾伯格博弈是一種完全信息動態(tài)博弈，在模型中存在“領(lǐng)導者”和“追隨者”兩種角色.在博弈的第1階段中，平臺作為領(lǐng)導者率先行動，根據(jù)任務的評估價值來決定報酬報價Φ，如式(12)所示：

(12)

式中，ε為感知平臺統(tǒng)計的其他用戶執(zhí)行類似感知任務時，每單位時間內(nèi)的最高成本.在第2階段中，協(xié)作對作為追隨者根據(jù)領(lǐng)導者的報價隨后做出決策.

協(xié)作對P以最大化其收益為目標.因此，協(xié)作對P的效用函數(shù)可以被定義為獲得的報酬減去成本，如式(13)所示：

(13)

其中，δ和δ′分別為協(xié)作對P中用戶Ui和Ui′的單位時間成本.

分析斯塔克爾伯格博弈的方法是逆向歸納法.首先分析第2階段，在這個階段中，協(xié)作對根據(jù)報酬Φ進行博弈.如果平臺和協(xié)作對都不能夠通過單方面地改變策略來提高收益，那么在此階段將達到納什均衡(Nash Equilibrium，NE)，從而使得協(xié)作對成功執(zhí)行相應任務.隨后，在第1階段，平臺選擇合適的報酬Φ來最大化其收益.斯塔克爾伯格博弈具有如下均衡：

1)如果UP≤ 0，將不會有協(xié)作對成功執(zhí)行相應任務.

2)如果UP>0，平臺將會在第1階段提供報價Φ.在第2階段，協(xié)作對成功執(zhí)行相應任務.

5 仿 真

為了評估面向用戶協(xié)作對的激勵機制(incentive mechanism based on user collaboration pair，簡稱IMUCP)的有效性，針對用戶參與比例、任務覆蓋比例、用戶平均效用和協(xié)作率4個性能指標進行了仿真，仿真飾演的主要參數(shù)在表1中給出.

表1 仿真參數(shù)表Table 1 Simulation parameters

將IMUCP的性能與最小感知時間算法(The Minimum Sensing Time Algorithm，MSTA)和反向維克里拍賣算法(Reverse Vickrey Auction Incentive Mechanism，RVA-IM)[28]的性能進行比較.在MSTA算法中，根據(jù)適合指定任務類型且具備最小感知時間跨度的條件來選擇單個用戶.在RVA-IM算法中，在滿足任務類型和感知時間跨度的條件下，出價第2低的用戶將成為任務執(zhí)行者，以此避免用戶間的惡性高價競爭.以上3種算法均進行1000次仿真，并取其平均值用于仿真結(jié)果展示.

5.1 用戶參與比例

圖1顯示了IMUCP和RVA-IM、MSTA的用戶參與比例對比.從圖1(a)可知，用戶參與比例隨任務數(shù)量的增加而升高.這是因為當任務數(shù)量相對于用戶數(shù)量較少時，能夠參與感知任務的用戶也相對較少，因此3種算法下的用戶參與比例均處于較低的水平.隨著任務數(shù)的增加，能夠參與到感知任務當中的用戶數(shù)量也隨之增加，因此用戶參與比例隨之上升.從圖1(b)可以看出，用戶參與比例隨用戶數(shù)量的增加而下降.

圖1 用戶參與比例對比Fig.1 Comparison of user participation ratio

這是因為在任務數(shù)量一定的情況下，用戶數(shù)量的增加使得能夠被用戶執(zhí)行的任務迅速飽和，導致大量的用戶因剩余任務數(shù)量不夠而處于無法參與感知任務的狀態(tài)，從而使得用戶參與比例下降.相較于RVA-IM和MSTA而言，IMUCP因為在單人覆蓋任務的基礎(chǔ)上實現(xiàn)了協(xié)作對協(xié)作覆蓋任務，使得能夠參與到感知任務當中的用戶更多，因此用戶參與比例始終處于高于RVA-IM和MSTA的水平.

5.2 任務覆蓋比例

圖2顯示了IMUCP和RVA-IM、MSTA的任務覆蓋比例對比.由于協(xié)同機制的存在，IMUCP在不同任務數(shù)量和用戶數(shù)量條件下的任務覆蓋比例都優(yōu)于RVA-IM和MSTA.如圖2(a)所示，隨著任務數(shù)量的增加，3種算法下的任務覆蓋比例都逐漸下降.這是因為在用戶數(shù)量一定的情況下，能夠執(zhí)行任務的用戶數(shù)量會達到飽和，后續(xù)增加的任務由于剩余用戶不足而無法被執(zhí)行，從而導致任務覆蓋比例降低.從圖2(b)中可以看出，在3種算法下的任務覆蓋比例都隨著用戶數(shù)量的增加而升高.這是因為用戶數(shù)量的增加可以直接提升任務被覆蓋的概率，從而提升任務覆蓋比例，直到被覆蓋的任務達到飽和.

圖2 任務覆蓋比例對比Fig.2 Comparison of task coverage ratio

5.3 用戶平均效用

圖3顯示了IMUCP和RVA-IM、MSTA的用戶平均效用對比.總體來說，IMUCP的用戶平均效用均高于RVA-IM和MSTA.這是因為相對于RVA-IM和MSTA的單人感知模式來說，IMUCP采用的基于斯塔克爾伯格博弈的協(xié)作對協(xié)作感知模式使得協(xié)作中的用戶能夠得到相對較高的報酬，因此提高了其用戶平均效用.在圖3(a)中，3種算法下的用戶平均效用均隨著任務數(shù)量的增加而減少.從用戶參與比例和任務覆蓋比例的仿真分析中可以知道，當任務數(shù)量增加時，用戶參與比例逐漸升高，而任務覆蓋比例逐漸下降，導致用戶的人均報酬下降，從而減少了用戶平均效用.在圖3(b)中，3種算法下的用戶平均效用均隨著用戶數(shù)量的增加而增加.同樣，從用戶參與比例和任務覆蓋比例的仿真分析中可以知道，當用戶數(shù)量增加時，用戶參與比例逐漸下降，而任務覆蓋比例逐漸上升，導致用戶的人均報酬上升，從而增加了用戶平均效用.

圖3 用戶平均效用對比Fig.3 Comparison of user average utility

5.4 協(xié)作率

圖4顯示了不同的任務數(shù)(用戶數(shù))和任務單位時間預算對IMUCP協(xié)作率的影響.由圖可知協(xié)作率隨著任務單位時間預算ε的增加而上升，在ε=2時達到最大值，之后趨于穩(wěn)定.這是因為ε的增大可以直接增加斯塔克爾伯格博弈的成功率，促使協(xié)作用戶的效用值為正，進而提升了IMUCP的協(xié)作率.

圖4 任務數(shù)(用戶數(shù))和任務單位時間預算對IMUCP協(xié)作率的影響Fig.4 Effects of the number of tasks (users) and task unit time budget on collaboration rate

6 結(jié)束語

本文研究了移動群智感知中的激勵機制問題，提出了一種面向用戶協(xié)作對的移動群智感知激勵機制.本文基于兩個用戶之間的時間狀態(tài)和主觀協(xié)作意愿來獲得這兩個用戶組成的協(xié)作對的協(xié)作狀態(tài)，并篩選出協(xié)作狀態(tài)最佳的協(xié)作對作為相應任務的執(zhí)行者.設(shè)計了一種基于斯塔克爾伯格博弈的激勵方式以充分激勵協(xié)作用戶的客觀協(xié)作意愿，進一步激勵協(xié)作用戶參與協(xié)作感知.大量仿真結(jié)果表明，相比于RVA-IM、MSTA兩個算法，本文所提機制是有效的并且在性能上表現(xiàn)良好.在未來的工作中，可以將從空間的角度來考慮用戶的協(xié)作場景.同時，還將探索更多的博弈激勵機制方法.