时空众包中基于质量感知的在线激励机制

doi:10.11772/j.issn.1001-9081.2022071095

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (7): 2091-2099.DOI: 10.11772/j.issn.1001-9081.2022071095

• 第39届CCF中国数据库学术会议(NDBC 2022) • 上一篇

时空众包中基于质量感知的在线激励机制

潘亚楠, 潘庆先(), 于兆一, 褚佳静, 于嵩

烟台大学计算机与控制工程学院，山东烟台 264005

收稿日期:2022-07-12 修回日期:2022-08-04 接受日期:2022-08-16 发布日期:2023-07-20 出版日期:2023-07-10
通讯作者: 潘庆先
作者简介:潘亚楠（1997—），女，山东济南人，硕士研究生，CCF会员，主要研究方向：机器学习、群智感知；
潘庆先（1979—），男，山东武城人，副教授，博士，CCF会员，主要研究方向：人工智能、机器学习；
于兆一（1995—），男，山东德州人，硕士，CCF会员，主要研究方向：移动众包；
褚佳静（1997—），女，山东威海人，硕士研究生，CCF会员，主要研究方向：群智感知；
于嵩（1998—），男，山东烟台人，硕士研究生，CCF会员，主要研究方向：移动众包。
基金资助:
国家自然科学基金资助项目(62072392)

Online incentive mechanism based on quality perception in spatio-temporal crowdsourcing

Yanan PAN, Qingxian PAN(), Zhaoyi YU, Jiajing CHU, Song YU

School of Computer and Control Engineering，Yantai University，Yantai Shandong 264005，China

Received:2022-07-12 Revised:2022-08-04 Accepted:2022-08-16 Online:2023-07-20 Published:2023-07-10
Contact: Qingxian PAN
About author:PAN Yanan， born in 1997， M. S. candidate. Her research interests include machine learning， crowd sensing.
PAN Qingxian， born in 1979， Ph. D.， associate professor. His research interests include artificial intelligence， machine learning.
YU Zhaoyi， born in 1995， M. S. His research interests include mobile crowdsourcing.
CHU Jiajing， born in 1997， M. S. candidate. Her research interests include crowd sensing
YU Song， born in 1998， M. S. candidate. His research interests include mobile crowdsourcing.
Supported by:
National Natural Science Foundation of China(62072392)

摘要/Abstract

摘要：

在实时、复杂的网络环境中，如何激励工人参与任务并得到高质量的感知数据是时空众包研究的重点。基于此，提出一种基于质量感知的时空众包在线激励机制。首先，为了适应时空众包实时性的特点，提出一种阶段性在线选择工人算法（POA），该算法在预算约束下将整个众包活动周期分为多个阶段，每个阶段在线选择工人；其次，为了提高质量预估的精度与效率，提出一种改进的最大期望（IEM）算法，该算法在算法迭代的过程中优先考虑可信度高的工人提交的任务结果；最后，通过真实数据集上的对比实验，验证了所提激励机制在提高平台效用方面的有效性。实验结果表明，POA相较于改进的两阶段拍卖（ITA）算法、多属性与两阶段相结合的拍卖（M-ITA）算法，以及L-VCG（Lyapunov-based Vickrey-Clarke-Groves）等拍卖算法，效率平均提高了11.11%，工人的额外奖励金额平均提升了12.12%，可以激励工人向冷门偏远地区移动；在质量预估方面，IEM算法相比其他质量预估算法，在精度和效率上分别平均提高了5.06%和14.2%。

关键词: 时空众包, 在线拍卖, 质量预估, 激励机制, 平台效用

Abstract:

In the real-time and complex network environment， how to motivate workers to participate in tasks and obtain high-quality perception data is the focus of spatio-temporal crowdsourcing research. Based on this， a spatio-temporal crowdsourcing’s online incentive mechanism based on quality perception was proposed. Firstly， in order to adapt to the real-time characteristics of spatio-temporal crowdsourcing， a Phased Online selection of workers Algorithm （POA） was proposed. In this algorithm， the entire crowdsourcing activity cycle was divided into multiple stages under budget constraints， and workers were selected online in each stage. Secondly， in order to improve the accuracy and efficiency of quality prediction， an Improved Expected Maximum （IEM） algorithm was proposed. In this algorithm， the task results submitted by workers with high reliability were given priority in the process of algorithm iteration. Finally， the effectiveness of the proposed incentive mechanism in improving platform utility was verified by comparison experiments on real datasets. Experimental results show that in terms of efficiency， compared with the Improved Two-stage Auction （ITA） algorithm， the Multi-attribute and ITA （M-ITA） algorithm， Lyapunov-based Vickrey-Clarke-Groves （L-VCG） and other auction algorithms， the efficiency of POA has increased by 11.11% on average， and the amount of additional rewards for workers has increased by 12.12% on average， which can encourage workers to move to remote and unpopular areas； In terms of quality estimation， the IEM algorithm has an average improvement of 5.06% in accuracy and 14.2% in efficiency compared to other quality estimation algorithms.

Key words: spatio-temporal crowdsourcing, online auction, quality prediction, incentive mechanism, platform utility

中图分类号:

TP18

潘亚楠, 潘庆先, 于兆一, 褚佳静, 于嵩. 时空众包中基于质量感知的在线激励机制[J]. 计算机应用, 2023, 43(7): 2091-2099.

Yanan PAN, Qingxian PAN, Zhaoyi YU, Jiajing CHU, Song YU. Online incentive mechanism based on quality perception in spatio-temporal crowdsourcing[J]. Journal of Computer Applications, 2023, 43(7): 2091-2099.

图/表 13

图1 基于质量感知的众包系统架构

Fig. 1 Architecture of crowdsourcing system based on quality perception

图2 基于质量感知的在线激励机制流程

Fig. 2 Flow of online incentive mechanism based on quality perception

图3 参数ρ对效率的影响

Fig. 3 Influence of parameter ρ on efficiency

图4 最大投标任务数β对效率的影响

Fig. 4 Influence of maximum number of bidding tasks β on efficiency

表1 实验参数设置

Tab. 1 Setting of experimental parameters

参数	设置
B	500，1 000，1 500，2 000
r_i	（0，1）
ρ	1
λ₁+λ₂+λ₃	1
β	8

图5 不同预算下效率对比结果

Fig. 5 Efficiency comparison results under different budgets

图6 中标工人数量以及额外奖励的差异

Fig. 6 Number of winning workers and difference in bonuses

图7 不同预算下工人的可信度

Fig. 7 Workers' reliability under different budgets

图8 正确答案的比例

Fig. 8 Proportion of correct answers

表2 数据集信息

Tab. 2 Datasets information

数据集	任务类别	任务选项	任务数
Adult2	标记网站	4	333
Duck	识别图像	2	39
LabelMe	注释图像	8	2 688

表3 工人历史信息

Tab. 3 Workers’ history information

工作者	历史信息
w₁	（0.87，0.82，0.92，0.87，0.92，0.9，0.95，0.87，0.9， 0.92，0.9，0.92）
w₂	（1，0.87，0.9）
w₃	（0.92，0.97，0.85，0.92，0.95，0.9，0.97）
w₄	（0.85，0.92，0.9，0.95，1）
w₅	（1，0.85，0.9，0.92，0.72，0.825）
w₆	（0.75，0.82，0.9）
w₇	（0.84，0.89）

图9 不同数据集上的精度对比结果

Fig. 9 Accuracy comparison results on different datasets

图10 不同数据集上的效率对比结果

Fig. 10 Efficiency comparison results on different datasets

参考文献 28

1	秦海燕，章永龙，李斌.社会网络下分配众包任务的真实机制［J］.计算机应用， 2020， 40（10）： 3019-3024. 10.11772/j.issn.1001-9081.2020020174
	QIN H Y， ZHANG Y L， LI B. Truthful mechanism for crowdsourcing task assignment in social network［J］. Journal of Computer Applications， 2020， 40（10）： 3019-3024. 10.11772/j.issn.1001-9081.2020020174
2	PAN Q X， PAN T W， DONG H B， et al. Research on task assignment to minimize travel cost for spatio-temporal crowdsourcing［J］. EURASIP Journal on Wireless Communications and Networking， 2021， 2021： No.59. 10.1186/s13638-021-01909-3
3	冉家敏，倪志伟，彭鹏，等.考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解［J］.计算机应用， 2021， 41（3）： 794-802. 10.11772/j.issn.1001-9081.2020060940
	RAN J M， NI Z W， PENG P， et al. Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution［J］. Journal of Computer Applications， 2021， 41（3）： 794-802. 10.11772/j.issn.1001-9081.2020060940
4	ZHAO D， MA H D， JI X N. Generalized lottery trees： budget-balanced incentive tree mechanisms for crowdsourcing［J］. IEEE Transactions on Mobile Computing， 2021， 20（7）： 2379-2394. 10.1109/tmc.2020.2979459
5	SHI Z G， YANG G， GONG X W， et al. Quality-aware incentive mechanisms under social influences in data crowdsourcing［J］. IEEE/ACM Transactions on Networking， 2022， 30（1）： 176-189. 10.1109/tnet.2021.3105427
6	SUN Z C， WANG Y J， CAI Z P， et al. A two-stage privacy protection mechanism based on blockchain in mobile crowdsourcing［J］. International Journal of Intelligent Systems， 2021， 36（5）： 2058-2080. 10.1002/int.22371
7	霍峥，张坤，贺萍，等.满足本地化差分隐私的众包位置数据采集［J］.计算机应用， 2019， 39（3）： 763-768. 10.11772/j.issn.1001-9081.2018071541
	HUO Z， ZHANG K， HE P， et al. Crowdsourcing location data collection for local differential privacy［J］. Journal of Computer Applications， 2019， 39（3）： 763-768. 10.11772/j.issn.1001-9081.2018071541
8	WANG Y J， GAO Y， LI Y S， et al. A worker-selection incentive mechanism for optimizing platform-centric mobile crowdsourcing systems［J］. Computer Networks， 2020， 107： No.107144. 10.1016/j.comnet.2020.107144
9	GAO L P， JIN T， LU C. A long-term quality perception incentive strategy for crowdsourcing environments with budget constraints［J］. International Journal of Cooperative Information Systems， 2020， 29（1/2）： No.2040005. 10.1142/s0218843020400055
10	WANG Y J， CAI Z P， ZHAN Z H， et al. An optimization and auction based incentive mechanism to maximize social welfare for mobile crowdsourcing［J］. IEEE Transactions on Computational Social Systems， 2019， 6（3）： 414-429. 10.1109/tcss.2019.2907059
11	WANG Y J， CAI Z P， YIN G S， et al. An incentive mechanism with privacy protection in mobile crowdsourcing systems［J］. Computer Networks， 2016， 102： 157-171. 10.1016/j.comnet.2016.03.016
12	ZHAO D， LI X Y， MA H D. Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully［J］. IEEE/ACM Transactions on Networking， 2016， 24（2）： 647-661. 10.1109/tnet.2014.2379281
13	胡颖.群智感知网络中移动众包的激励机制研究［D］.烟台：烟台大学， 2020： 19-41.
	HU Y. Research on incentive mechanism of mobile crowd sourcing in crowd sensing networks［D］. Yantai： Yantai University， 2020： 19-41
14	LUO T， TAN H P， XIA L R. Profit-maximizing incentive for participatory sensing ［C］// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway： IEEE， 2014： 127-135. 10.1109/infocom.2014.6847932
15	GAO L， HOU F， HUANG J W. Providing long-term participation incentive in participatory sensing ［C］// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway： IEEE， 2015： 2803-2811. 10.1109/infocom.2015.7218673
16	WANG Y J， CAI Z P， ZHAN Z H， et al. Walrasian equilibrium-based multiobjective optimization for task allocation in mobile crowdsourcing［J］. IEEE Transactions on Computational Social Systems， 2020， 7（4）： 1033-1046. 10.1109/tcss.2020.2995760
17	QUOC VIET HUNG N， TAM N T， TRAN L N， et al. An evaluation of aggregation techniques in crowdsourcing ［C］// Proceedings of the 2013 International Conference on Web Information Systems Engineering， LNCS 8181. Berlin： Springer， 2013： 1-15.
18	高丽萍，孙明达，高丽，等.移动众包环境下一种多阶段质量感知的在线激励机制［J］.小型微型计算机系统， 2022， 43（5）： 1102-1108.
	GAO L P， SUN M D， GAO L， et al. Online incentive mechanism of multi-stage quality perception in mobile crowdsourcing environment［J］. Journal of Chinese Computer Systems， 2022， 43（5）： 1102-1108.
19	仲秋雁，刘志娟.考虑工作者信誉的众包质量EM评估方法［J］.科技管理研究， 2018， 38（21）： 70-76. 10.3969/j.issn.1000-7695.2018.21.010
	ZHONG Q Y， LIU Z J. EM evaluation method of crowdsourcing quality considering the reputation of workers［J］. Science and Technology Management Research， 2018， 38（21）： 70-76. 10.3969/j.issn.1000-7695.2018.21.010
20	WHITEHILL J， RUVOLO P， WU T F， et al. Whose vote should count more： optimal integration of labels from labelers of unknown expertise ［C］// Proceedings of the 22nd International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2009： 2035-2043.
21	LI H W， YU B. Error rate bounds and iterative weighted majority voting for crowdsourcing［EB/OL］. （2014-11-15）［2022-05-33］. . 10.1016/j.ins.2022.05.066
22	CELEUX G， GOVAERT G. A classification EM algorithm for clustering and two stochastic versions［J］. Computational Statistics and Data Analysis， 1992， 14（3）： 315-332. 10.1016/0167-9473(92)90042-e
23	DAWID A P， SKENE A M. Maximum likelihood estimation of observer error-rates using the EM algorithm［J］. Journal of the Royal Statistical Society Series C： Applied Statistics， 1979， 28（1）： 20-28. 10.2307/2346806
24	ZHENG C Z. High bids and broke winners［J］. Journal of Economic Theory， 2001， 100（1）： 129-171. 10.1006/jeth.2000.2715
25	BATENI M， HAJIAGHAYI M， ZADIMOGHADDAM M. Submodular secretary problem and extensions［J］. ACM Transactions on Algorithms， 2013， 9（4）： No.32. 10.1145/2500121
26	IPEIROTIS P G， PROVOST F， WANG J. Quality management on Amazon Mechanical Turk ［C］// Proceedings of the 2010 ACM SIGKDD Workshop on Human Computation. New York： ACM， 2010： 64-67. 10.1145/1837885.1837906
27	WELINDER P， BRANSON S， BELONGIE S， et al. The multidimensional wisdom of crowds ［C］// Proceedings of the 23rd International Conference on Neural Information Processing Systems — Volume 2. Red Hook， NY： Curran Associates Inc.， 2010： 2424-2432.
28	RODRIGUES F， LOURENÇO M， RIBEIRO B， et al. Learning supervised topic models for classification and regression from crowds［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， 39（12）： 2409-2422. 10.1109/tpami.2017.2648786

[1]	李从东, 黄浩, 张帆顺. 基于演化博弈的领先用户知识共享行为激励机制[J]. 计算机应用, 2021, 41(6): 1785-1791.
[2]	巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892.
[3]	聂茜婵, 张阳, 余敦辉, 张兴盛. 面向全局优化的时空众包任务分配算法[J]. 计算机应用, 2020, 40(7): 1950-1958.
[4]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[5]	陈秀华, 刘慧, 熊金波, 马蓉. 移动群智感知中面向任务需求的用户选择激励机制[J]. 计算机应用, 2019, 39(8): 2310-2317.
[6]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[7]	刘辉, 李盛恩. 时空众包环境下基于统计预测的自适应阈值算法[J]. 计算机应用, 2018, 38(2): 415-420.
[8]	王莹洁, 蔡志鹏, 童向荣, 潘庆先, 高洋, 印桂生. 基于声誉的移动众包系统的在线激励机制[J]. 计算机应用, 2016, 36(8): 2121-2127.
[9]	朱旋, 杨麦顺, 安健, 向乐乐, 杨蔷薇. 群智感知中基于反拍卖模型的众包激励方法[J]. 计算机应用, 2016, 36(7): 2038-2045.
[10]	刘大福, 苏旸, 谢洪安, 杨凯. 电子商务中客户评价策略选择的演化博弈分析[J]. 计算机应用, 2016, 36(12): 3269-3273.
[11]	宋伟余强彭军孙庆中. 基于歧视性的第二价格拍卖算法的激励机制[J]. 计算机应用, 2014, 34(11): 3147-3151.
[12]	张涵张建标林莉. 面向半分布式P2P系统的可靠节点交换机制[J]. 计算机应用, 2013, 33(01): 4-7.
[13]	李绍静. 基于动态拓扑构造的信誉激励机制[J]. 计算机应用, 2012, 32(10): 2752-2756.
[14]	许力陈心瑜陈志德. 基于贝叶斯博弈模型的无线多跳网络激励机制[J]. 计算机应用, 2011, 31(12): 3169-3173.
[15]	程普楚艳萍杜莹. 博弈论框架下P2P实时流的合作模型研究[J]. 计算机应用, 2011, 31(05): 1159-1161.

时空众包中基于质量感知的在线激励机制

Online incentive mechanism based on quality perception in spatio-temporal crowdsourcing

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 28

相关文章 15

编辑推荐

Metrics