Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (5): 1357-1363.DOI: 10.11772/j.issn.1001-9081.2018092027

• Data science and technology • Previous Articles     Next Articles

Time utility balanced online task assignment algorithm under spatial crowdsourcing environment

ZHANG Xingsheng1, YU Dunhui1,2, ZHANG Wanshan1,2, WANG Chenxu1   

  1. 1. School of Computer Science and Information Engineering, Hubei University, Wuhan Hubei 430062, China;
    2. Education Informationization Engineering Research Center of Hubei Province(Hubei University), Wuhan Hubei 430062, China
  • Received:2018-10-09 Revised:2018-12-07 Online:2019-05-10 Published:2019-05-14
  • Supported by:
    This work is partially supported by the National Key R&D Program of China (2017YFB1400602), the National Natural Science Foundation of China (61572371, 61832014).

时空众包环境下时效均衡的在线任务分配算法

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

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

Abstract: Focusing on the poor overall allocation effect due to the total utility of task allocation or task waiting time being considered respectively in the study of task allocation under spatial crowdsourcing environment, a dynamic threshold algorithm based on allocation time factor was proposed. Firstly, the allocation time factor of task was calculated based on the estimated waiting time and the already waiting time. Secondly, the task allocation order was obtained by comprehensively considering the return value of task and the allocation time factor. Thirdly, the dynamic adjustment item was added based on the initial value to set the threshold for each task. Finally, candidate matching set was set for each task according to the threshold condition, and the candidate matching pair with the largest matching coefficient was selected from the candidate matching set to join the result set, and the task allocation was completed. When the task allocation rate was 95.8%, compared with greedy algorithm, the proposed algorithm increased total allocation utility by 20.4%; compared with random threshold algorithm, it increased total allocation utility by 17.8% and decreased task average waiting time by 13.2%; compared with Two phase based Global Online Allocation-Greedy (TGOA-Greedy) algorithm, it increased total allocation utility by 13.9%. The experimental results show that proposed algorithm can shorten the average waiting time of task while improving the total utility of task allocation, to achieve the balance between the total allocation utility and the task waiting time.

Key words: spatial crowdsourcing, online task assignment, total utility of task allocation, waiting time of task, allocation time factor, dynamic threshold algorithm

摘要: 针对时空众包任务分配研究中单一考虑任务分配总效用或任务等待时间,导致总体分配效果不佳的问题,提出一种基于分配时间因子的动态阈值算法。首先,基于预估等待分配时间和已等待分配时间计算任务的分配时间因子;其次,综合考虑任务的回报值和分配时间因子进行任务分配排序;然后,在初始值的基础上增加动态调整项为每一项任务设置阈值;最后,根据阈值条件为每一项任务设置候选匹配集,并从候选匹配集中选择匹配系数最大的候选匹配对加入结果集,完成任务分配。通过实验证明,该算法在任务分配率达到95.8%的情况下,与贪心算法相比,在分配总效用方面提升20.4%;与随机阈值算法相比,在分配总效用方面提升17.8%,在任务平均等待时间方面缩短13.2%;与基于两阶段框架模型的在线微任务分配改进(TGOA-Greedy)算法相比,在分配总效用方面提升13.9%。实验结果表明,该算法能够在提升任务分配总效用的同时缩短任务的平均等待时间,实现分配总效用与任务等待时间两者间的均衡。

关键词: 时空众包, 在线任务分配, 任务分配总效用, 任务等待时间, 分配时间因子, 动态阈值算法

CLC Number: