Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (3): 658-664.DOI: 10.11772/j.issn.1001-9081.2019071282

• Artificial intelligence • Previous Articles     Next Articles

Spatiotemporal crowdsourcing online task allocation algorithm based ondynamic threshold

YU Dunhui1,2, YUAN Xu1, ZHANG Wanshan1, WANG Chenxu1   

  1. 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).

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

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

  1. 1. 湖北大学 计算机与信息工程学院, 武汉 430062;
    2. 湖北省教育信息化工程技术中心, 武汉 430062
  • 通讯作者: 袁旭
  • 作者简介:余敦辉(1974-),男,湖北武汉人,教授,博士,CCF会员,主要研究方向:服务计算、大数据;袁旭(1994-),男,湖北荆州人,硕士研究生,主要研究方向:大数据;张万山(1973-),男,湖北武汉人,讲师,硕士,主要研究方向:Web信息挖掘;王晨旭(1997-),男,山西忻州人,主要研究方向:软件众包。
  • 基金资助:
    国家自然科学基金资助项目(61572371, 61832014);湖北省技术创新重大专项(2018ACA13)。

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

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

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

CLC Number: