张兴盛 余敦辉 张万山 王晨旭

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

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

中图分类号：TP311

文献标志码：A

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 AllocationGreedy （TGOAGreedy） 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

0 引言

众包[1-3]这一概念由美国人Jeff Howe在美国《连线》杂志上于2006年首次提出，通常指一种把工作任务通过公开的 Web 平台以自愿的形式外包给非特定的解决方案提供者群体来完成的分布式问题求解模式。……