基于用户分类可靠性的群智感知任务分配机制研究

卜霄菲，吴文江，辛 煜，黄 河，吴晓灿，杨雪华

(1. 中国科学院 沈阳计算技术研究所有限公司，辽宁 沈阳110168；2. 沈阳师范大学 软件学院，辽宁 沈阳 110034；3. 北京遥感信息研究所，北京 100011；4. 苏州大学 计算机科学与技术学院，江苏 苏州 215006；5. 中国科学技术大学 苏州研究院, 江苏 苏州 215123)

群智感知技术作为物联网应用的重要外延，旨在通过智能手机、可穿戴设备等附着在人身上的各类移动终端设备在一个更加广泛的感知区域内实时获取用户感兴趣的信息[1].群智感知应用系统往往需要采集大量的数据以支撑系统的正常运行.与传统的无线传感网络采集数据方式不同，群智感知系统中的数据采集工作并非由固定员工完成，而是由系统将这些数据采集任务拆分成若干子任务[2-6]，然后分配给大量感兴趣的匿名智能终端用户完成.这种方式与传统的数据采集方式相比，可以在降低数据采集任务的执行时间和采集成本的基础上，大幅提高数据的采集规模，从而更容易通过分析得到可信的结果，进而为系统用户提供优质的服务[7].

在群智感知系统中，不同用户提交的数据质量可能是存在差异的.由于不同用户所持有的设备性能、对数据收集任务的理解程度以及对待任务的认真程度等方面存在差异，导致感知数据的质量也存在一定的差异.针对这一问题，部分研究选择多个用户来完成同一任务，然后再通过多数选举或加权多数选举的方式选出最终的可信数据[8-11].例如，文[8]中限定每个任务最多分配给l个用户来完成，并在此基础上设计出诚实的群智感知任务拍卖机制.然而，上述研究在仅仅是增加了完成任务的用户数量，然后通过冗余数据的方式来保证任务的完成质量，并未真正地考虑用户的可靠性对任务分配过程的影响.为了解决该问题，上海交通大学的吴帆研究团队提出在任务分配时首先预测用户的期望任务完成质量来选择高可靠性的用户，并根据用户实际提交的数据质量来决定用户的最终支付，从而促使用户提交高质量的数据[12].文[13]以任务完成质量最大化为优化目标，在任务分配时尽可能地选择了可靠性较高的一组用户来完成任务.然而，群智感知中的任务是异质的，用户完成不同类型任务的可靠性也应该是异质的，上述研究均假设用户完成不同任务的可靠性是相同的，没有考虑到群智感知中存在的用户分类可靠性问题.文[14]在考虑任务多样性的基础上，研究如何对用户在各类不同任务上的可靠性进行评估.然而，该研究是针对众包系统所设计的，无法直接应用到群智感知系统中.

为了解决上述问题，论文假设每个用户针对不同类型的任务具有不同的可靠性，旨在综合考虑用户分类可靠性的报价的基础上，选择一组最合适的用户完成感知任务.为了使所设计的机制更具通用性，论文还假设群智感知系统中存在着多个数据消费者.由于不同数据消费者之间还存在着竞争关系，所以论文以最大化收益最小的数据消费者的收益作为优化目标，采用贪心技术，设计了一种高效的群智感知任务分配机制，以保证数据消费者之间的公平性.除此之外，论文还设计了一种用户分类可靠性的更新技术，以保证任务分配机制选择最近一段时间提交数据质量较高的用户.最后，通过仿真实验对所设计机制的性能进行了验证.

1 问题模型

1.1 群智感知系统模型

平台在收到所有用户的任务请求后，会根据设定的用户与任务之间的匹配原则，将任务分配给用户完成.由于用户所提交的数据可能是不可靠的，所以所研究的模型允许一个任务同时分配给多个用户完成，以提高任务的期望完成质量.但是，在每个分配周期，每个用户最多只会分配到一个任务.最后，平台会发布任务分配结果，并在用户完成任务后根据其完成任务的质量更新用户的分类可靠性，作为下一次任务分配的依据.至此，一个群智感知任务分配周期结束.

1.2 问题描述

由于群智感知系统中存在多个数据消费者，且这些数据消费者之间的利益是冲突的.所以，论文在考虑用户分类可靠性的基础上，设计了一种群智感知系统的任务分配机制，以数据消费者的最大最小公平作为优化目标，实现用户与群智感知任务的最优匹配.

定义1满足最大最小公平的任务分配机制：如果一个群智感知任务分配机制最大化了收益最小的数据消费者的收益，那么该分配机制满足数据消费者的最大最小公平.

作者的优化目标是要实现数据消费者之间的最大最小公平，即在满足约束的条件下maxminui.

2 基于用户分类可靠性的群智感知系统任务分配机制

所设计的机制主要包含两部分：任务与用户的最优匹配机制和用户分类可靠性的实时更新机制.其中，任务与用户的匹配机制是要结合用户的分类可靠性和报价，以满足数据消费者的最大最小公平为优化目标，将任务分配给最合适的一组用户完成.而用户分类可靠性的实时更新机制则要根据用户每轮实际提交的数据质量，更新分类用户的可靠性，促使用户更好地完成任务.

2.1 任务与用户的匹配机制

任务与用户之间的匹配机制迭代进行.每次迭代，群智感知平台会选择一个任务和用户完成匹配.由于所设计的机制以实现数据消费者的最大最小公平为优化目标，所以平台在每次迭代开始会首先寻找当前收益最低的数据消费者，并期望完成该数据消费者的一个任务与用户之间的匹配，以提高该数据消费者的收益.具体的实现细节如算法1所示.

算法1任务与用户的匹配机制

1) 设置D′=D,S′=S；

2) While (数据消费者集合D′≠φ)

3) {

4) 找到D′中具有最小收益的数据消费者i；

6) for (每个sj∈S′)

7) {

9) {

10) 计算将任务ti,k分配给用户sj所能带来的收益增量Δui；

12) {

14) 设置maxs=sj；

15) 设置maxt=ti,k；

16) }

17) }

18) }

20) {

21) 将任务ti,k分配给用户sj；

22) 将用户sj从集合S′中删除；

23) }

24) else

25) 将数据消费者i从集合D′中删除；

26) }

Δui=ui(Si,k∪{sj})-ui(Si,k).

在求Δui(Si,k)或Δui(Si,k∪{sj})的值时，首先Si,k或Si,k∪{sj}中的用户按照可靠性从高到低排序.若sj是排序后Si,k或Si,k∪{sj}中的第l个用户，那么sj所能为消费者i带来的收益为

αl-1rj,h*vi,k-pj,i,k，

其中:pj,i,k等于sj对任务ti,k的实际报价.

在求得Si,k或Si,k∪{sj}中所有用户的收益后，Δui(Si,k)或Δui(Si,k∪{sj})的值即为这些收益的总和.

2.2 用户分类可靠性的更新机制

隐马尔可夫模型作为一种统计模型，被用于描述一个包含隐含未知参数的马尔可夫过程.隐马尔可夫模型着重解决了如下问题:在了解模型存在若干种隐含状态后，可以根据可见状态连链的具体情况，反推出隐含状态间的转换概率;在了解模型存在若干种隐含状态和隐含状态间的转换概率后，也可以根据见状态连链的具体情况，知道隐含状态链的情况以及每一个隐含状态产生的概率.这正与所需要解决的问题相吻合.

在基于用户可靠性的众包系统分配机制中，需要用到用户的可靠性信息来计算任务分配所能带来的收益以及最终给用户的报酬.为了能使用户的可靠性信息能真实地反映用户近期完成任务的质量，每次任务分配结束后还应该根据该轮用户的任务完成质量更新该用户的可靠性信息.

由于用户的工作状态不可能始终保持一致，任务完成的质量会受到或好或坏影响，因此对于用户可靠性的评价，主要是依照用户最近一次完成任务的质量来完成的.再者，用户在完成任务时往往会受到诸多外在因素的影响，同类型的任务完成质量并不可能相同，而用户完成多个同类任务的质量序列反映了诸多未知的外在因素对用户的影响程度.因此可以以用户过去的任务质量序列为输入，建立一个隐马尔可夫模型，来反映用户在完成某一类型任务时，诸多未知的外在因素对用户的影响程度，然后以所得对用户下次完成此类任务时的表现进行预测.

在每次任务分配结束后，根据用户的任务完成质量以及此前该用户完成同类型任务的完成质量，建立隐马尔可夫模型，通过Baum-Welch算法对模型进行学习，反推出隐含状态间的转换概率.再根据所得的模型和任务完成质量序列，得出用户下次完成此类任务时最可能出现的表现.

3 仿真实验分析

3.1 仿真模拟建立

在仿真模拟部分，假设在每一轮任务分配中有m个数据消费者和n个用户.设m=15，用户的报价均匀分布于[0.7,1)，每个用户任意从平台发布的任务中选取1或2个任务作为自己感兴趣的任务.假定每一个任务实际价值与对应的数据消费者的预算相同,分别在两个环境下进行仿真实验.在第一个环境中，假定数据消费者i所要完成的任务数目|Ti|均匀分布于[5,8]范围中，每一个任务预算均匀分布于[1.75,2)内.在第二个环境中，假定数据消费者i所要完成的任务数目|Ti|为5，每一个任务预算为1.75.通过变换用户数目n的大小来检验在不同情形下机制的表性能.

对于每一个实验，重复进行500次，再取其平均值作为实验结果.

3.2 性能分析

在图1、2中，设α=0.5,并通过变化用户数目n的大小来检验机制的表性能.图中的最大收益和最小收益依次是算法结果下收益最大和最小的数据消费者所获的收益.图1是在第二个环境下机制产生的结果.由于每一个任务的预算、每一个数据消费者所要完成的任务数目是相同的，如果机制满足最大最小公平性，理论上来说，最大效益的曲线应该与最小效益的曲线十分接近.而从图1上看，实验结果与上述分析是一致的.此外，也发现图1的两条曲线开始时斜率都较大，而随着用户数目的增加，曲线斜率趋于平稳.这是因为当用户数目足够大时，任务的预算不足或其收益已经无法继续增长，平台无法将任务分配给更多用户了.

图2是平台在第一个环境下进行任务分配得到的结果.由于任务的预算、数据消费者所要完成的任务数目不完全相同，但用户足够多时，那些要完成的任务数目较多、任务预算较大的数据消费者会获得更大的收益.而对于要完成的任务数目较少的数据消费者，分配给他们的用户数目达到一定的值时，他们的收益便会固定不再增长.正如图2所示，最大收益与最小收益的差是随着用户数目的增加而增大的.

在图3、4中,设α=0.5,并通过变化用户数目n的大小来检验机制的表性能.可以发现，图3、4的实验结果依次与图1、2相似.因此，尽管α值越大，数据消费者能获得更多的收益，但所提机制的性能是不受α值的大小影响的.

图1 α=0.5，环境2下数据消费者的收益 图2 α=0.5，环境1下数据消费者的收益

图3 α=0.67，环境2下数据消费者的收益 图4 α=0.67，环境1下数据消费者的收益

4 结束语

针对群智感知系统中的任务分配问题，研究了多数据消费者模型下如何实现数据消费者之间的最大最小公平，并在综合考虑用户的分类可靠性以及报价的基础上，实现任务与用户之间的最佳匹配;研究首先采用贪心技术，以实现数据消费者的最大最小公平为优化目标，提出一种基于用户分类可靠性的任务与用户的匹配机制;提出一种用户分类可靠性的更新机制，为下一轮任务分配提供依据，并激励用户高质量地完成任务;最后，通过仿真实验证明，所设计任务分配机制较好地实现了数据消费者之间的最大最小公平，并保证了较高的任务完成质量.

参考文献：

[1] 刘云浩. 群智感知计算[J]. 中国计算机学会通讯, 2012, 8 (10): 38-41.

[2] BOUTSIS I, KALOGERAKI V. On task assignment for real-time reliable crowdsourcing[C]// IEEE 34th ICDCS, 2014: 1-10.

[3] GOEL G, NIKZAD A, SINGLA A. Mechanism design for crowdsourcing markets with heterogeneous tasks[C]// Second AAAI Conference on Human Computation and Crowdsourcing, 2014： 1-12.

[4] HE S, SHIN D H, ZHANG J, et al. Toward optimal allocation of location dependent tasks in crowdsensing[C]// IEEE INFOCOM , 2014, 5 (11): 745-753.

[5] JIN H, SU L, CHEN D, et al. Quality of information aware incentive mechanisms for mobile crowd sensing systems[C]// ACM MobiHoc, 2015: 167-176.

[6] XU W, HUANG H, SUN Y E, et al. DATA: a double auction based task assignment mechanism in crowdsourcing systems[C]// 8th International ICST Conference on Communications and Networking in China, 2014: 172-177.

[7] BI R, ZHENG X, TAN G. Optimal assignment for deadline aware tasks in the crowdsourcing[C]// IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom) (BDCloud-Social Com-SustainCom), 2016: 178-184.

[8] ZHAO D, MA H, LIU L. Frugal online incentive mechanisms for crowdsourcing tasks truthfully[J]. Computer Science, 2014, 37 (3): 103-122.

[9] ZHAO D, LI X Y, MA H. How to crowdsource tasks truthfully without sacrificing utility: online incentive mechanisms with budget constraint[C]// Proceedings of IEEE INFOCOM, 2014: 1213-1221.

[10] SONG Z, NGAI E, MA J, et al. A novel incentive negotiation mechanism for participatory sensing under budget constraints[C]// Proceedings of IEEE/ACM IWQoS, 2014: 326-331.

[11] DUAN L, KUBO T, SUGIYAMA K, et al. Incentive mechanisms for smartphone collaboration in data acquisition and distributed computing[C]// Proceedings of IEEE INFOCOM, 2012: 1701-1709.

[12] PENG D, WU F, CHEN G H. Pay as how well you do: A quality based incentive mechanism for crowdsensing[C]// Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2015), 2015: 177-186.

[13] 杜扬, 黄河, 孙玉娥, 等. 地理位置相关移动感知系统任务分配问题研究[J]. 计算机研究与发展, 2014, 51 (11): 2374-2381.

[14] MA F, LI Y, LI Q, et al. Faitcrowd: fine grained truth discovery for crowdsourced data aggregation[C]// Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2015), 2015: 745-754.