基于信譽模型的群智感知網(wǎng)絡(luò)用戶參與激勵機(jī)制

張 寧 蘇 華 孫學(xué)梅 趙帥飛

(天津工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院 天津 300387)

基于信譽模型的群智感知網(wǎng)絡(luò)用戶參與激勵機(jī)制

張 寧 蘇 華 孫學(xué)梅*趙帥飛

(天津工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院 天津 300387)

隨著集成了越來越多傳感器的移動設(shè)備的普及和發(fā)展，移動群智感知網(wǎng)絡(luò)正成為一個新的研究領(lǐng)域，而充足的用戶(尤其是信譽好的用戶)參與，是移動群智感知網(wǎng)絡(luò)的基礎(chǔ)。在對用戶參與激勵機(jī)制策略進(jìn)行研究和分析的基礎(chǔ)上，針對現(xiàn)有激勵機(jī)制在用戶選擇的隨機(jī)性、任務(wù)處理效率和預(yù)算控制方面的不足，提出一種基于信譽模型的用戶參與激勵機(jī)制。初始時設(shè)置用戶的信譽值，在任務(wù)分配過程中選擇信譽度高的用戶來參與任務(wù)處理，并通過設(shè)置因子減小用戶的花費代價，這樣在提高任務(wù)處理效率的基礎(chǔ)上有效地控制了預(yù)算開支。最后通過實驗驗證，與現(xiàn)有普遍應(yīng)用的用戶參與激勵機(jī)制策略相比，基于信譽模型的用戶參與激勵機(jī)制在提高任務(wù)處理效率和控制預(yù)算方面有更好的效果。

移動群智感知 激勵機(jī)制 信譽模型 用戶參與

0 引 言

隨著移動技術(shù)的不斷發(fā)展，現(xiàn)有的移動終端集成了越來越多的傳感器，每個移動終端都可以成為一個計算和信息資源交互設(shè)備，而大量的終端設(shè)備構(gòu)建起的網(wǎng)絡(luò)能夠使用戶快速、動態(tài)地獲取和分享數(shù)據(jù)。這種感知方式的出現(xiàn)和普及，一方面擴(kuò)展了傳統(tǒng)的計算機(jī)網(wǎng)絡(luò)和系統(tǒng)的功能；另一方面，也促進(jìn)了移動群智感知網(wǎng)絡(luò)[1]MCS(Mobile Crowd Sensing System)的發(fā)展。移動群智感知網(wǎng)絡(luò)通常由移動感知用戶和群智感知平臺兩部分構(gòu)成[2]，其中，移動群智感知平臺是由服務(wù)器組成的數(shù)據(jù)中心；移動感知用戶則是攜帶移動設(shè)備的普通用戶。大部分群智感知是利用用戶參與來提供服務(wù)[3-5]，通過用戶攜帶的移動設(shè)備與移動互聯(lián)網(wǎng)絡(luò)之間進(jìn)行交互，實現(xiàn)感知任務(wù)的分配、協(xié)調(diào)和處理。

在移動群智感知網(wǎng)絡(luò)中，普通用戶需要主動參與感知任務(wù)的處理。然而，用戶參與需要付出一定的代價(例如網(wǎng)絡(luò)帶寬消耗、費用消耗等)，因此應(yīng)當(dāng)設(shè)計一種合理的補(bǔ)償激勵機(jī)制來對用戶的消耗代價進(jìn)行補(bǔ)償[6]，以此來吸引更多用戶主動參與到感知過程中來。當(dāng)前對于移動群智感知網(wǎng)絡(luò)激勵機(jī)制開始了一部分研究工作。文獻(xiàn)[7]考慮了兩種系統(tǒng)模型：以平臺為中心和以用戶為中心。首先應(yīng)用博弈論理論分析，然后應(yīng)用拍賣理論設(shè)計出兩種不同模型的激勵機(jī)制。文獻(xiàn)[8]考慮了以平臺為中心的用戶激勵機(jī)制模式，并將這種模式建模為斯塔克伯格博弈來研究，進(jìn)一步考慮了平臺和用戶均僅知道所有用戶的感知成本的累積分布函數(shù)的情況。文獻(xiàn)[9]研究了移動群智感知網(wǎng)絡(luò)激勵機(jī)制問題，首先平臺發(fā)布一些感知任務(wù)，然后用戶根據(jù)他們的感知成本和時間來競爭這些任務(wù)，最后平臺在預(yù)算限制下支付給用戶感知報酬。文獻(xiàn)[10]釆用基于逆向拍賣的動態(tài)價格激勵機(jī)制，進(jìn)一步考慮了用戶基于位置進(jìn)行感知，而平臺需要滿足覆蓋約束和預(yù)算約束的情況。文獻(xiàn)[11]基于手機(jī)用戶動態(tài)到達(dá)平臺并且任務(wù)隨機(jī)提交到平臺這一真實場景，設(shè)計了一種真實可靠地在線激勵機(jī)制。

以上是對激勵機(jī)制的早期研究，而近期研究者針對原來激勵機(jī)制的不足提出一些新的方法。在文獻(xiàn)[12]中作者把任務(wù)分成三種不同的類型(即效用值隨任務(wù)大小成正比例變化，效用值隨任務(wù)處理過程成正比例變化，效用值隨任務(wù)處理過程成反比例變化)，對于每一種任務(wù)類型用四種不同的激勵機(jī)制(Proportion incentive policy、Participation-aware incentive policy、Quality-aware incentive policy、Thrifty incentive policy)計算報酬。其中用戶參與激勵機(jī)制策略PAIP(participation aware incentive policy)在選擇用戶時采用隨機(jī)的方式，沒有考慮用戶自身的特點，這樣用戶在處理任務(wù)時目的性不強(qiáng)，在感知任務(wù)分配階段用戶的參與率不高，降低了整個任務(wù)的完成率，增加了代價花費，而使總預(yù)算減少。

本文在研究和分析了PAIP在用戶選擇、用戶花費代價、任務(wù)處理效率這三方面的不足后，提出了基于信譽模型的用戶激勵機(jī)制CPAIP(credit participation-aware incentive policy)。該機(jī)制初始時為用戶設(shè)置不同的信譽值，當(dāng)平臺發(fā)布感知任務(wù)并且用戶競爭這些感知任務(wù)時，平臺會根據(jù)用戶的信譽值進(jìn)行選擇，優(yōu)先選擇信譽值高的用戶進(jìn)行任務(wù)處理，并且通過因子調(diào)節(jié)用戶的代價花費。最后對用戶的信譽值進(jìn)行更新之后用戶可以進(jìn)入到下一次的任務(wù)競爭中。通過CPAIP在提高用戶參與率和任務(wù)完成率的同時，減少用戶的花費，從而節(jié)省了總預(yù)算。

1 CPAIP模型

移動群智感知網(wǎng)絡(luò)(MCS)主要包括三個部分：用戶集U、任務(wù)集T和平臺S。任務(wù)集T包括若干子任務(wù)，每個子任務(wù)的處理過程是輪流進(jìn)行的(即在每個子任務(wù)被執(zhí)行之前，平臺S都會向用戶發(fā)布這個子任務(wù)處理請求)，每個用戶會決定是否接受請求，來處理子任務(wù)并獲得報酬。這個過程會重復(fù)進(jìn)行，直到所有的任務(wù)都被處理或者全部預(yù)算B都被用完。其符號如表1所示。

表1 主要用到的符號

CPAIP模型具體工作流程如下：

(1) 當(dāng)有任務(wù)要處理時，平臺S首先把任務(wù)集T劃分為若干子任務(wù)k：k?{1,2,…,K}。并在任務(wù)發(fā)布區(qū)域選取一用戶集U，對其進(jìn)行劃分Ui：i?{1,2,…,N}。對每一個用戶i設(shè)置一個獨立的閾值Thresi，該值對其他用戶和平臺是保密的，并根據(jù)全部用戶的閾值和單個用戶的閾值設(shè)置一個信譽值Qi，所用公式如下所示：

(1)

同時，針對劃分的子任務(wù)的不同，為每一個子任務(wù)設(shè)置一個效用值，用uk=f(ξ,ξk)來表示，所用公式如下所示：

(2)

(2) 當(dāng)處理子任務(wù)時，平臺每次會選取信譽值大的用戶(即Qi最大者)參與子任務(wù)的處理過程。用戶Ui在處理子任務(wù)k時，會產(chǎn)生一個花費代價。本文針對一個子任務(wù)k，用ci=f(ξk,uk,Qi)來表示代價函數(shù)，也就是說，用戶的代價受分配的子任務(wù)大小和用戶信譽值影響，與子任務(wù)大小成正比關(guān)系，與用戶信譽值成反比關(guān)系。所用公式如下所示：

(3)

其中α和β是兩個因子，且α+β=10。

(3) 平臺為鼓勵更多用戶參與任務(wù)的處理過程，會在每個子任務(wù)處理后為對應(yīng)用戶提供報酬。本文中用Pk=f(uk,N(t),B(t))來表示報酬函數(shù)，所用公式如下所示：

(4)

其中c為正常數(shù)。通過這種方式，平臺S初始時會提供很高的報酬來鼓勵用戶參與任務(wù)處理，隨著用戶參與的比例越來越高(即N(t)值越來越大，最終趨于穩(wěn)定)，報酬會慢慢趨于平穩(wěn)。

(4) 根據(jù)處理子任務(wù)k時所需的代價ci和平臺S對于k所支付的報酬P(guān)k，用戶i可以決定是否最后接受這個子任務(wù)的處理請求。本文中用函數(shù)Ji=f(ci,Pk,Thresi)來表示，所用公式如下所示：

(5)

平臺S對于處理子任務(wù)k所支付的報酬P(guān)k和處理k所需的代價ci的比例與用戶閾值進(jìn)行比較，如果比例大于用戶閾值，則用戶選擇接受這個子任務(wù)處理請求，否則用戶拒絕這個請求。

(5) 最后利用用戶所處理子任務(wù)的效用值來更新用戶信譽值，并參與競爭下一個子任務(wù)處理請求，直到所有的子任務(wù)全部處理完成。

CPAIP模型算法偽代碼如下：

算法1CPAIP模型

Input：Tasks numberK，setofusersN，budgetB，thresholdThres

Output：remainingbudgetB(t)，taskpercentagecompletedT(t)

1：initialthetasksandusers,setcreditvaluesQ

2：while!k‖B

3：fork=1:1:K

4：MaxQi←findtheuserofthemaxcreditvalue

5：Uk←calculatetheutilityofsegmentk

6：Ci←calculatethecostofsegmentk

7：Pk←calculateincentivesforuser

8：AccordingtoCi,Pk,Threstodeterminewhetheracceptsegmentornot

9：ifacceptsegment

10：N(t) ←calculateproportionofuserparticipation

11：B(t) ←B-Pk

12：else

13：constantvalues

14：endif

15：Qi←updatecreditvalueofuseri

16：endfor

17：calculateT(t)

18：Nextloop

19：endwhile

20：returnB(t)，T(t)

第5行應(yīng)用式(2)來計算子任務(wù)的效用值，第6～8行應(yīng)用式(3)、式(4)計算用戶的代價花費和處理子任務(wù)后會獲得的報酬，并且用戶根據(jù)代價、報酬、閾值的關(guān)系接受子任務(wù)請求。這樣在提高用戶的參與率和減少代價花費的同時，也加快了子任務(wù)處理速度，減少了總的預(yù)算，如第9～12行所示。當(dāng)用戶接受子任務(wù)之后，會對此用戶的信譽值進(jìn)行更新并參與到下一次子任務(wù)的競爭中，如第15～18行所示。

2 實驗及結(jié)果分析

2.1 仿真實驗環(huán)境

本文按照用戶的閾值將用戶分為三組，分別為高閾值用戶、低閾值用戶和中間閾值用戶，為每個用戶設(shè)置信譽值Qi。同時進(jìn)行多組實驗，將用戶總數(shù)N=100、子任務(wù)數(shù)量K=1 000、初始預(yù)算B=1 000設(shè)置為對比組。具體實驗分組及參數(shù)設(shè)置如表2所示。本文實驗是在MATLABR2014a環(huán)境下進(jìn)行的，下面從任務(wù)完成比例和預(yù)算剩余比例兩個方面進(jìn)行說明。

表2 實驗分組及參數(shù)

2.2 任務(wù)完成比例

平臺將任務(wù)集劃分為若干子任務(wù)，并保證子任務(wù)能依次順利處理。本文目標(biāo)就是能使子任務(wù)盡快地被處理完成，也就是說能在更短的時間內(nèi)獲得更高的任務(wù)完成比例。因此，選擇合適的用戶對于子任務(wù)集的處理尤為重要。圖1為對比組的實驗對比圖。而實驗一通過提高總預(yù)算時PAIP的處理速度加快，但與CPAIP相比，PAIP的速度還是明顯落后于CPAIP。實驗二通過增加用戶數(shù)量時PAIP與CPAIP的處理速度變化不大。實驗三增加子任務(wù)的數(shù)量時PAIP的處理速度會有所降低，而CPAIP的速度變化不大。實驗四中同時增加用戶數(shù)量、總預(yù)算和子任務(wù)數(shù)量時PAIP與CPAIP的處理速度都有所增加，但CPAIP的速度還是明顯快于PAIP。綜合對比各組實驗中的曲線可以很明顯地看出在一段時間內(nèi)CPAIP能夠更快地處理完子任務(wù)集，同時各參數(shù)變化時，CPAIP在處理任務(wù)速度方面具有更好的穩(wěn)定性。通過設(shè)置用戶的信譽值，區(qū)別劃分用戶，每次選擇信譽度高的用戶來依次處理子任務(wù)，這樣通過影響平臺支付報酬函數(shù)Pk和用戶的代價函數(shù)ci，使這兩者的比例大于用戶閾值Thresi，從而使得用戶參與比例不斷增大(即N(t)值增大)，并最終趨于平穩(wěn)。

圖1 任務(wù)完成比例對比圖

2.3 預(yù)算剩余比例

預(yù)算剩余比例也就是總預(yù)算減去用戶集處理完整個子任務(wù)集所花費的總代價之后的剩余預(yù)算與總預(yù)算的比例關(guān)系。平臺根據(jù)用戶處理的子任務(wù)向用戶支付報酬，本文目標(biāo)之一就是保證子任務(wù)在順利處理完的基礎(chǔ)上減少用戶的花費代價和平臺支付給用戶的報酬，從而使得預(yù)算剩余比例增大。圖2為對比組的實驗對比圖。實驗一通過提高總預(yù)算時PAIP與CPAIP在剩余預(yù)算比例方面變化不大。實驗二通過提高用戶總數(shù)時CPAIP的預(yù)算剩余比例會有所降低，但還是明顯高于PAIP。實驗三通過提高子任務(wù)數(shù)量時PAIP與CPAIP的預(yù)算剩余比例會有所增加，但CPAIP的增加幅度大于PAIP且最終剩余比例也要高于PAIP。實驗四中同時增加用戶數(shù)量、總預(yù)算和子任務(wù)數(shù)量時CPAIP的預(yù)算剩余比例會增加，而PAIP保持不變。綜合對比各組實驗中的曲線可以很明顯地看出在一段時間內(nèi)CPAIP能在保證子任務(wù)順利處理的基礎(chǔ)上，減少了用戶花費代價和平臺支付給用戶的報酬，從而使剩余的預(yù)算比例更高，即花費的預(yù)算更少。圖3顯示了任務(wù)進(jìn)度比例和預(yù)算比例的對比圖。實驗一通過提高總預(yù)算時PAIP與CPAIP的任務(wù)進(jìn)度比例和預(yù)算比例變化不大。實驗二通過增加用戶數(shù)量時CPAIP的任務(wù)進(jìn)度比例和預(yù)算比例有所降低，但還是要高于PAIP。實驗三通過增加子任務(wù)數(shù)量時CPAIP的任務(wù)進(jìn)度比例和預(yù)算比例會增大，而PAIP的變化不大。實驗四中同時增加用戶數(shù)量、總預(yù)算和子任務(wù)數(shù)量時CPAIP的任務(wù)進(jìn)度比例和預(yù)算比例會增大，而PAIP的變化不大。綜合對比各組的任務(wù)進(jìn)度比例和預(yù)算比例可以看到和PAIP相比，CPAIP能更快地完成整個子任務(wù)集，在提高了任務(wù)完成率的同時，也使得預(yù)算剩余比例增大。本文中選擇了信譽高的用戶處理子任務(wù)，使得用戶參與比例不斷增大(即N(t)值增大)，從而降低了平臺支付給用戶的報酬(即Pk值不斷減小)。同時平臺通過因子調(diào)節(jié)用戶在處理子任務(wù)時的代價ci。這樣使得CPAIP在提高任務(wù)處理效率的同時也減少了預(yù)算的花費。

圖2 預(yù)算剩余比例對比圖

圖3 預(yù)算——任務(wù)比例對比圖

3 結(jié) 語

本文針對現(xiàn)有用戶參與激勵機(jī)制策略的不足提出了基于信譽模型的用戶參與激勵機(jī)制。通過設(shè)置用戶的信譽值，每次選擇信譽高的用戶來依次處理子任務(wù)集，并設(shè)置因子來減少用戶的花費代價，影響平臺對于用戶的支付機(jī)制，并通過代價、報酬和閾值這三者的關(guān)系來決定用戶最終是否接受子任務(wù)的處理請求。該機(jī)制模型與現(xiàn)有用戶參與激勵機(jī)制策略相比，在提高任務(wù)完成效率和減少預(yù)算方面具有明顯的優(yōu)勢。

在未來的工作中，我們在進(jìn)一步完善該模型的基礎(chǔ)上，考慮記錄用戶的成功與失敗的比例，并以此來優(yōu)化用戶選擇。同時也可以在子任務(wù)效用和報酬支付方面進(jìn)一步優(yōu)化該模型性能。

[1] Ganti R K,Ye F,Lei H.Mobile crowdsensing:current state and future challenges[J].IEEE Communications Magazine,2011,49(11):32-39.

[2] 趙東.移動群智感知網(wǎng)絡(luò)中數(shù)據(jù)收集與激勵機(jī)制研究[D].北京:北京郵電大學(xué),2014.

[3] Koukoumidis E,Peh L S,Martonosi M R.SignalGuru:leveraging mobile phones for collaborative traffic signal schedule advisory[C]//Proceedings of the 9thInternational Conference on Mobile Systems,Applications,and Services.ACM,2011:127-140.

[4] D’Hondt E,Stevens M,Jacobs A.Participatory noise mapping works! An evaluation of participatory sensing as an alternative to standard techniques for environmental monitoring[J].Pervasive and Mobile Computing,2013,9(5):681-694.

[5] Rana R K,Chou C T,Kanhere S S,et al.Ear-phone:an end-to-end participatory urban noise mapping system[C]//Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks,2010:105-116.

[6] Zhao D,Li X Y,Ma H.Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully[J].IEEE/ACM Transactions on Networking,2016,24(2):647-661.

[7] Yang D,Xue G,Fang X,et al.Crowdsourcing to smartphones:incentive mechanism design for mobile phone sensing[C]//Proceedings of the 18thAnnual International Conference on Mobile Computing and Networking.ACM,2012:173-184.

[8] Duan L,Kubo T,Sugiyama K,et al.Incentive mechanisms for smartphone collaboration in data acquisition and distributed computing[C]//Proceedings of the 2012 IEEE International Conference on Computer Communications,2012:1701-1709.

[9] Han K,Zhang C,Luo J,et al.Truthful scheduling mechanisms for powering mobile crowdsensing[J].IEEE Transactions on Computers,2016,65(1):294-307.

[10] Jaimes L G,Vergara-Laurens I,Labrador M A.A location-based incentive mechanism for participatory sensing systems with budget constraints[C]//Proceedings of the 2012 IEEE International Conference on Pervasive Computing and Communications,2012:103-108.

[11] Zhu Y,Zhang Q,Zhu H,et al.Towards truthful mechanisms for mobile crowdsourcing with dynamic smartphones[C]//Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems,2014:11-20.

[12] Angelopoulos C M,Nikoletseas S,Raptis T P,et al.Design and evaluation of characteristic incentive mechanisms in mobile crowdsensing systems[J].Simulation Modelling Practice and Theory,2015,55:95-106.

CROWD SENSING NETWORK USER PARTICIPATION INCENTIVE MECHANISM BASED ON CREDIBILITY MODEL

Zhang Ning Su Hua Sun Xuemei*Zhao Shuaifei

(CollegeofComputerScienceandSoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387,China)

With the popularization and development of mobile devices which integrated more and more sensors, the mobile crowd sensing network is becoming a new research field. Adequate user participation (especially users with good credibility) is the basis for mobile crowd sensing network. Based on the research and analysis of user participation incentive mechanism, aiming at the shortcomings of the existing incentive mechanism, such as randomness of user selection, task processing efficiency and budget control, a user participation incentive mechanism based on credibility model is proposed. The initial value of the user’s credibility set in the task allocation process to select high credibility of the user to participate in task processing, and set the factor to reduce the cost of the user’s cost, so that improve the efficiency of task processing on the basis of effective control of the budget. Finally, it is verified by experiments that compared with the existing popular user participation incentive mechanism, the user participation incentive mechanism based on credibility model has better effect in improving the efficiency of task processing and budget control.

Mobile crowd sensing Incentive mechanism Credibility model User participation

2016-04-01。張寧，碩士生，主研領(lǐng)域：計算機(jī)網(wǎng)絡(luò)，群智感知網(wǎng)絡(luò)。蘇華，副教授。孫學(xué)梅，副教授。趙帥飛，本科生。

TP3

A

10.3969/j.issn.1000-386x.2017.05.021