基于信誉模型的群智感知网络用户参与激励机制

张 宁 苏 华 孙学梅 赵帅飞

(天津工业大学计算机科学与软件学院 天津 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