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

来源:用户上传      作者:

　　摘 要：针对时空众包任务分配研究中单一考虑任务分配总效用或任务等待时间，导致总体分配效果不佳的问题，提出一种基于分配时间因子的动态阈值算法。首先，基于预估等待分配时间和已等待分配时间计算任务的分配时间因子;其次，综合考虑任务的回报值和分配时间因子进行任务分配排序;然后，在初始值的基础上增加动态调整项为每一项任务设置阈值;最后，根据阈值条件为每一项任务设置候选匹配集，并从候选匹配集中选择匹配系数最大的候选匹配对加入结果集，完成任务分配。通过实验证明，该算法在任务分配率达到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 平台以自愿的形式外包给非特定的解决方案提供者群体来完成的分布式问题求解模式。随着互联网技术的发展，这种通过群体智慧求解问题的新模式也受到了工业界和学术界的广泛关注，像AMT （Amazon Mechanical Turks）这类众包平台得到了迅速发展。近年来，伴随移动互联网技术和共享经济的兴起，以及移动智能设备的普及和应用，为众包模式带来更多的外延需求，不再满足于传统众包模式下单一的任务类型，扩展了更多包含时空属性，从而发展为时空众包[4]，例如，滴滴出行、百度外卖等。 　　在时空众包环境下，任务分配[5]依然是其核心问题之一。针对这一问题学术界展开了积极研究，文献[6-8]重点考虑任务分配总效用： 文献[6]提出一种基于两阶段框架模型的全球在线微任务分配改进算法（Two phase based Global Online AllocationGreedy， TGOAGreedy），确保分配速度的同时优化分配总效用，但算法以贪心算法作为基线算法，任务的分配总效用可进一步提升;文献[7]基于当前的阈值机制，提出了一种根据任务分配情况自动调整阈值的自适应阈值算法，对比随机阈值算法提升了分配总效用，但算法阈值是从确定集合中选择，分配效用仍存在很大的提升空间;文献[8]提出一种基于统计预测的自适应阈值算法，进一步优化了分配总效用，不足是任务分配率偏低。文献[9-10]从缩短匹配距离，同时减小众包工人差旅成本入手展开研究：文献[9]提出了一种面向距离的阈值算法，旨在最小化最大的匹配距离，但实际应用中更多考虑的是平均匹配距离，因此算法缺乏实用性;文献[10]针对最小化分配总距离问题进行了综合性实验，证明了贪心算法解决这类问题时的高效性，但缺乏稳定可靠性。文献[11-12]综合考虑了分配效用和差旅成本，进行双目标优化：文献[11]提出了一种将双目标优化和多臂赌博机相结合的动态分配方法，旨在尽量减少差旅成本的前提下最大限度地提高任务的可靠性，同时提升分配效用，但没有考虑任务和工人活跃范围的限制;文献[12]提出基于二分法框架模型来最大化任务分配的数量，同时最小化差旅成本，但与文献[11]一样，均没有从任务发布者的角度出发，考虑任务等待分配这一过程的时间成本。
　　从上不难看出，现有的研究更多是聚焦于单一考虑任务分配总效用或任务等待时间，从而导致效用高的算法任务等待时间可能过长，等待时间短的算法分配总效用有时又太低。综合这两方面要素的算法考虑又不够完善，存在很大的提升空间。
　　为此，本文从众包平台和众包任务发布者双方的角度出发，综合考虑了任务分配的總效用和任务等待时间，提出一种基于分配时间因子的动态阈值（Allocationtime Factor based Dynamic Threshold， AFDT）算法，旨在保证任务分配总效用的同时缩短任务平均等待时间。对比文献[6-7]中的算法，AFDT算法进一步提高了分配总效用;对比文献[8]中的算法，AFDT算法不仅提高了分配总效用，同时也确保了任务分配率;对比文献[9-10]中的算法，AFDT算法更具实用性，算法性能也更加稳定可靠;对比文献[11-12]中的算法，AFDT算法既考虑了任务和工人活跃范围的限制，也增加了从任务等待分配角度的考虑。
　　本文的主要贡献如下：1）提出一种用于衡量任务等待分配程度的计量因子——分配时间因子（Allocation Time Factor of mission，ATFm），作为任务等待程度的衡量指标。2）设计一种基于分配时间因子的动态阈值算法（AFDT算法），AFDT算法基于任务的分配时间因子ATFm动态调整阈值，实现任务等待时间与分配效用之间的均衡。
　　5 结语
　　本文研究了时空众包环境下时效均衡的在线任务分配问题，利用分配时间因子衡量任务的等待分配程度，并采用面向工人任务成功率的动态阈值机制，设计了一种基于分配时间因子的动态阈值算法。本文通过基于真实数据的仿真实验证明了所提算法在任务分配率、分配总效用、任务平均等待时间方面均具有较好的性能表现，能够有效解决时效均衡的在线任务分配问题。未来的时空众包研究可从以下两个方面展开：1）引入机器学习的方法进一步提升任务分配总效用或缩短任务的等待时间。2）研究从众包工人方面考虑工人成本的问题，进一步优化在线任务分配算法。
　　参考文献 （References）
　　[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. Reputationbased 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] LI Y， YIU M L， 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.
　　[5] 童咏听， 袁野， 成雨蓉，等. 时空众包数据管理技术研究综述[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.） 　　[6] TONG Y X， SHE J， DING B， et al. Online mobile microtask allocation in spatial crowdsourcing[C]// Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering， Piscataway， NJ： IEEE， 2016： 49-60.
　　[7] 宋天舒， 童詠昕， 王立斌， 等. 空间众包环境下的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.）
　　[8] 刘辉， 李盛恩. 时空众包环境下基于统计预测的自适应阈值算法[J]. 计算机应用， 2018， 38（2）： 415-420. （LIU H， LI S E. Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment[J]. Journal of Computer Applications， 2018， 38（2）： 415-420.）
　　[9] LONG C， WONG R CW， YU P S， et al. On optimal worstcase matching[C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2013： 845-856.
　　[10] TONG Y， SHE J， DING B， et al. Online minimum matching in realtime spatial data： experiments and analysis [J]. Proceedings of the VLDB Endowment， 2016， 9（12）： 1053-1064.
　　[11] HASSAN U U， CURRY E. Efficient task assignment for spatial crowdsourcing： a combinatorial fractional optimization approach with semibandit learning[J]. Expert Systems with Applications， 2016， 58（C）： 36-56.
　　[12] DENG D， SHAHABI C， ZHU L. Task matching and scheduling for multiple workers in spatial crowdsourcing[C]// Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2015： Article No. 21.
　　[13] CHEN Z， FU R， ZHAO Z， et al. gMission： a general spatial crowdsourcing platform[J]. Proceedings of the Very Large Data Base Endowment， 2014， 7（13）： 1629-1632.
转载注明来源:https://www.xzbu.com/8/view-14941556.htm