基于信譽模型的群智感知網絡用戶參與激勵機制

張 寧 蘇 華 孫學梅 趙帥飛

(天津工業大學計算機科學與軟件學院 天津 300387)

基于信譽模型的群智感知網絡用戶參與激勵機制

張 寧 蘇 華 孫學梅*趙帥飛

(天津工業大學計算機科學與軟件學院 天津 300387)

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

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

0 引 言

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

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

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

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

1 CPAIP模型

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

表1 主要用到的符號

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

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

(1)

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

(2)

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

(3)

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

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

(4)

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

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

(5)

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

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

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

2 實驗及結果分析

2.1 仿真實驗環境

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

表2 實驗分組及參數

2.2 任務完成比例

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

圖1 任務完成比例對比圖

2.3 預算剩余比例

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

圖2 預算剩余比例對比圖

圖3 預算——任務比例對比圖

3 結 語

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

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

[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] 趙東.移動群智感知網絡中數據收集與激勵機制研究[D].北京:北京郵電大學,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。張寧，碩士生，主研領域：計算機網絡，群智感知網絡。蘇華，副教授。孫學梅，副教授。趙帥飛，本科生。

TP3

A

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