Online mobile Micro-Task Allocation in spatial crowdsourcing
Online mobile Micro-Task Allocation in spatial crowdsourcing
复制标题
DOI：
10.1109/icde.2016.7498228
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Yongxin Tong;Jieying She;Bolin Ding;Libin Wang;Lei Chen
中科院分区：
文献类型：
--
作者：
Yongxin Tong;Jieying She;Bolin Ding;Libin Wang;Lei Chen
随着智能手机的快速发展，空间众包平台越来越流行。空间众包的一个基础性研究是将微任务分配给合适的众包工作者。现有的研究大多集中在离线场景，其中所有的时空信息的微任务和人群工作者。然而，由于真实的应用中的微任务和人群工作者是动态出现的，并且它们的时空信息不能预先知道，因此它们是不切实际的。在本文中，为了解决现有的离线方法的缺点，我们首先确定了一个更实际的微任务分配问题，称为全球在线空间众包微任务分配（戈马）问题。我们首先扩展了最先进的在线最大加权二部匹配问题的戈马问题的算法作为基线算法。虽然基线算法为最坏情况提供了理论上的保证，但由于最坏情况在真实的世界中发生的概率很低，因此其在实践中的平均性能不够好。因此，我们考虑在线算法的平均性能，也就是在线随机顺序模型，我们提出了一个基于两阶段的框架，在此基础上，我们提出了TGOA算法的在线随机顺序模型下的竞争比为1比4。为了提高其效率，我们进一步设计了TGOA-Greedy算法，它运行速度比TGOA算法快，但竞争比较低，为1比8。最后，通过在真实的数据集和人工数据集上的实验，验证了所提方法的有效性。
With the rapid development of smartphones, spatial crowdsourcing platforms are getting popular. A foundational research of spatial crowdsourcing is to allocate micro-tasks to suitable crowd workers. Most existing studies focus on offline scenarios, where all the spatiotemporal information of micro-tasks and crowd workers is given. However, they are impractical since micro-tasks and crowd workers in real applications appear dynamically and their spatiotemporal information cannot be known in advance. In this paper, to address the shortcomings of existing offline approaches, we first identify a more practical micro-task allocation problem, called the Global Online Micro-task Allocation in spatial crowdsourcing (GOMA) problem. We first extend the state-of-art algorithm for the online maximum weighted bipartite matching problem to the GOMA problem as the baseline algorithm. Although the baseline algorithm provides theoretical guarantee for the worst case, its average performance in practice is not good enough since the worst case happens with a very low probability in real world. Thus, we consider the average performance of online algorithms, a.k.a online random order model.We propose a two-phase-based framework, based on which we present the TGOA algorithm with 1 over 4 -competitive ratio under the online random order model. To improve its efficiency, we further design the TGOA-Greedy algorithm following the framework, which runs faster than the TGOA algorithm but has lower competitive ratio of 1 over 8. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.