基于动态阈值的时空众包在线分配算法

doi:10.11772/j.issn.1001-9081.2019071282

计算机应用 ›› 2020, Vol. 40 ›› Issue (3): 658-664.DOI: 10.11772/j.issn.1001-9081.2019071282

基于动态阈值的时空众包在线分配算法

余敦辉^1,2, 袁旭¹, 张万山¹, 王晨旭¹

1. 湖北大学计算机与信息工程学院, 武汉 430062;
2. 湖北省教育信息化工程技术中心, 武汉 430062

收稿日期:2019-07-13 修回日期:2019-09-08 出版日期:2020-03-10 发布日期:2019-09-19
通讯作者: 袁旭
作者简介:余敦辉(1974-),男,湖北武汉人,教授,博士,CCF会员,主要研究方向:服务计算、大数据;袁旭(1994-),男,湖北荆州人,硕士研究生,主要研究方向:大数据;张万山(1973-),男,湖北武汉人,讲师,硕士,主要研究方向:Web信息挖掘;王晨旭(1997-),男,山西忻州人,主要研究方向:软件众包。
基金资助:
国家自然科学基金资助项目（61572371， 61832014）；湖北省技术创新重大专项（2018ACA13）。

Spatiotemporal crowdsourcing online task allocation algorithm based ondynamic threshold

YU Dunhui^1,2, YUAN Xu¹, ZHANG Wanshan¹, WANG Chenxu¹

1. College of Computer and Information Engineering, Hubei University, Wuhan Hubei 430062, China;
2. Hubei Provincial Education Informationization Engineering and Technology Center, Wuhan Hubei 430062, China

Received:2019-07-13 Revised:2019-09-08 Online:2020-03-10 Published:2019-09-19
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572371, 61832014), the Technology Innovation Special Program of Hubei Province (2018ACA13).

摘要/Abstract

摘要： 为提升时空众包动态现实场景中任务分配总效用，提出一种基于在线随机森林的动态阈值算法（DTRF）。首先，根据众包平台中工人和任务的历史匹配数据初始化在线随机森林；然后，通过在线随机森林预测每位工人期望的任务回报率作为阈值，按阈值为每个工人选取候选匹配集；最后，从候选匹配集中选取当前效用总和最高的匹配，同时用分配结果更新在线随机森林。实验结果表明，所提算法在提升总效用的同时有效地提高了工人的平均收益。与贪心算法相比，所提算法的任务分配率提升了4.1%，总效用提升了18.2%，工人平均收益提升了11.2%。与随机阈值算法相比，所提算法在任务分配率、总效用、工人平均收益等方面都有较好的提升，且稳定性更好。

关键词: 时空众包, 在线任务分配, 分配总效用, 在线随机森林, 动态阈值算法

Abstract: In order to improve the total utility of task allocation in spatiotemporal crowdsourcing dynamic reality, a Dynamic Threshold algorithm based on online Random Forest (DTRF) was proposed. Firstly, the online random forest was initialized based on the historical matching data of workers and tasks on the crowdsourcing platform. Then, the online random forest was used to predict the expected task return rate of each worker as the threshold, and the candidate matching set was selected for each worker according to the threshold. Finally, the matching with the highest sum of current utility was selected from the candidate match set, and the online random forest was updated based on the allocation result. The experiments show that the algorithm can improve the average income of workers while increasing the total utility. Compared with the greedy algorithm, the proposed algorithm has the task assignment rate increased by 4.1%, the total utility increased by 18.2%, and the average worker income increased by 11.2%. Compared with the random threshold algorithm, this algorithm has a better improvement in task allocation rate, total utility, average income of workers with better stability.

Key words: spatiotemporal crowdsourcing, online task allocation, total utility of task allocation, online random forest, dynamic threshold algorithm

中图分类号:

TP393

余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.

YU Dunhui, YUAN Xu, ZHANG Wanshan, WANG Chenxu. Spatiotemporal crowdsourcing online task allocation algorithm based ondynamic threshold[J]. Journal of Computer Applications, 2020, 40(3): 658-664.

参考文献

[1] HOWE J. The rise of crowdsourcing[J]. Wired Magazine,2016, 14(6):1-4.
[2] 芮兰兰,张攀,黄豪球,等. 一种面向众包的基于信誉值的激励机制[J]. 电子与信息学报,2016,38(7):1808-1815.(RUI L L, ZHANG P,HUANG H Q,et al. Reputation-based incentive mechanisms in crowdsourcing[J]. Journal of Electronics & Information Technology,2016,38(7):1808-1815.)
[3] 施战,辛煜,孙玉娥,等. 基于用户可靠性的众包系统任务分配机制研究[J]. 计算机应用,2017,37(9):2449-2453.(SHI Z, XIN Y,SUN Y E,et al. Task allocation mechanism for crowdsourcing system based on reliability of users[J]. Journal of Computer Applications,2017,37(9):2449-2453.)
[4] TANG F,ZHANG H. Spatial task assignment based on information gain in crowdsourcing[EB/OL].[2019-05-12]. https://sci-hub.tw/10.1109/tnse.2019.2891635.
[5] LI Y,YIU M L,and XU W J. Oriented online route recommendation for spatial crowdsourcing task workers[C]//Proceedings of the 14th International Conference on Advances in Spatial and Temporal Database. New York:ACM,2015:137-156.
[6] KAZEMI L,SHAHABI C. GeoCrowd:enabling query answering with spatial crowdsourcing[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York:ACM,2012:189-198.
[7] KAZEMI L,SHAHABI C,CHEN L. GeoTruCrowd:trustworthy query answering with spatial crowdsourcing[C]//Proceedings of the 21st ACM Sigspatial International Conference on Advances in Geographic Information Systems. New York:ACM,2013:314-323.
[8] 范泽军,沈立炜,彭鑫,等. 基于约束的空间众包多阶段任务分配[J]. 计算机学报,2019,42(12):2722-2741.(FAN Z J, SHEN L W,PENG X,et al. Multi stage task allocation on constrained spatial crowdsourcing[J]. Chinese Journal of Computers, 2019,42(12):2722-2741.)
[9] 童咏昕,袁野,成雨蓉,等. 时空众包数据管理技术研究综述[J]. 软件学报,2017,28(1):35-58.(TONG Y X,YUAN Y,CHENG Y R,et al. Survey on spatiotemporal crowdsourced data management techniques[J]. Journal of Software, 2017, 28(1):35-58.)
[10] HASSAN U U,CURRY E. Efficient task assignment for spatial crowdsourcing:a combinatorial fractional optimization approach with semi-bandit learning[J]. Expert Systems with Applications, 2016,58(C):36-56.
[11] WU P,NGAI E W T,WU Y. Toward a real-time and budgetaware task package allocation in spatial crowdsourcing[J]. Decision Support Systems,2018,110:107-117.
[12] 宋天舒,童咏昕,王立斌,等. 空间众包环境下的3类对象在线任务分配[J]. 软件学报,2017,28(3):611-630.(SONG T S, TONG Y X,WANG L B,et al. Online task assignment for three types of objects under spatial crowdsourcing environment[J]. Journal of Software,2017,28(3):611-630.)
[13] 余敦辉, 张灵莉, 付聪. 基于动态效用的时空众包在线任务分配[J]. 电子与信息学报, 2018, 40(7):180-187.(YU D H, ZHANG L L,FU C. Spatial crowdsourcing online task allocation based on dynamic utility[J]. Journal of Electronics & Information Technology,2018,40(7):180-187.)
[14] 张兴盛,余敦辉,张万山,等. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用,2019,39(5):1357-1363. (ZHANG X S,YU D H,ZHANG W S,et al. Online task assignment algorithm for time-efficient balance in spatial crowdsourcing environment[J]. Journal of Computer applications,2019,39(5):1357-1363.)
[15] 方匡南,吴见彬,朱建平, 等. 随机森林方法研究综述[J]. 统计与信息论坛,2011,26(3):32-38.(FANG K N,WU J B, ZHU J P,et al. Review of random forest methods[J]. Statistics and Information BBS,2011,26(3):32-38.)

基于动态阈值的时空众包在线分配算法

Spatiotemporal crowdsourcing online task allocation algorithm based ondynamic threshold

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	聂茜婵, 张阳, 余敦辉, 张兴盛. 面向全局优化的时空众包任务分配算法[J]. 计算机应用, 2020, 40(7): 1950-1958.
[2]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[3]	刘辉, 李盛恩. 时空众包环境下基于统计预测的自适应阈值算法[J]. 计算机应用, 2018, 38(2): 415-420.