论文：Y. Tong, J. She, B. Ding, L. Wang and L. Chen, "Online mobile Micro-Task Allocation in spatial crowdsourcing," 2016 IEEE 32nd International Conference on Data Engineering (ICDE), Helsinki, 2016, pp. 49-60. doi: 10.1109/ICDE.2016.7498228

摘要

随着智能手机的快速发展，空间众包平台越来越受欢迎。空间众包的基础研究是将微任务分配给合适的群体工作者。大多数现有研究都侧重于离线情景，即给出了微任务和众包工作者的所有时空信息。然而，这种情况是不切实际的，因为实际应用中的微任务和众包工作者动态地出现并且他们的时空信息不能提前知道。在本文中，为了解决现有离线方法的缺点，本文首先确定了一个更实际的微任务分配问题，称为空间众包（GOMA）问题中的全局在线微任务分配。首先将在线最大加权二分匹配问题的最新算法扩展到GOMA问题作为基线算法。虽然基线算法提供了对于最坏情况的理论保证，它在实践中的平均表现不够好，因为最坏的情况在现实世界中以非常低的概率发生。因此，需要考虑在线算法的平均性能。本文提出了一个基于两阶段的框架，基于该框架，本嗯在在线随机顺序模型下提出了具有竞争比率4的TGOA算法。本文基于这个框架进一步设计了TGOA-贪婪算法，其速度相比TGOA更快，但是竞争比为8，最后本文在真实和合成的数据集上通过实验验证了上述方法的有效性。

简介：

近年来，随着Amazon Mechanical Turks（AMT），oDesk等成功众包平台的蓬勃发展，众包引起了业界和研究界的广泛关注。特别是随着智能手机和移动互联网的前所未有的发展，众包市场正在从传统的众包市场转向空间众包（又称移动众包）市场，在这些市场中，众包工作者通过手机执行微任务。例如，在Gigwalk1和Gmission2上，咨询公司招募人群工作人员检查超市中产品的价格，Waze3使用工作人员收集交通或剩余停车场的实时信息。

在离线场景下，空间众包中的任务分配问题可以通过简化为最大加权二分匹配问题来解决，其中任务和工人对应于两个不相交的顶点集合。 如果相应的任务位于相应工作者的受限范围内，则两个不相交的集合中的两个顶点之间存在边缘，其权重是该对任务和工作者的对应效用值。 此时离线解决方案变得不可行，因为在动态环境中任务和工作人员的到达顺序是未知的。

本文在动态环境中提出了一个新的任务分配问题，称为空间众包（GOMA）问题中的全局在线微任务分配。 由于任务和工作人员的到达顺序会显著影响算法的性能。现有的在线研究通常关注在最坏情况到达顺序的在线算法的性能，即在线对抗模型。 然而，这种算法在实践中可能表现不佳，因为最坏情况的顺序在现实世界中以非常低的概率发生。 因此，本文研究了GOMA中的在线算法的平均性能，a.k.a在线随机顺序模型。

问题定义：

1. 定义1（微任务）：微型任务（简称“任务”），由t = <lt，at，dt，pt>表示，位于2D空间中的lt位置，在时间点发布在平台上 要么分配给在响应截止日期之前到达平台的人群工作者，要么在之后不能分配。 此外，pt是任务t的回报。

2. 定义2（众包工作者）：众包工作者（简称“工人”），用w = <lw，aw，dw，rw，cw，δw>表示。

3. 定义3（效用值）：工人执行任务t的效用由U（t，w）= pt×δw计算。

4. 定义4（GOMA问题）：给定一组微任务T，一组工作人员W，以及空间众包平台上的效用函数U，该平台最初没有任务或工人，并允许每个任务和工人可以随时一个接一个地到达，GOMA问题是找到任务中的分配M和工人最大化总效用为：

提出的方法：

1.TGOA算法

受到解决经典秘书问题的方法的启发，本文提出了TGOA算法。 TGOA的主要思想是首先根据到达顺序将所有顶点（每个顶点可以是任务或工人）划分为两个相等的组，并对它们采用不同的策略。也就是说，顶点的前半部分首先到达，而后半部分顶点到达。注意在一个时间间隔内平台上的任务和工作者的总数，例如， 24小时，可以根据平台的历史记录估算。然后，对于上半部分任务和工作人员，TGOA执行贪婪策略，将每个新到达任务（工作人员）分配给具有最高效用并满足所有约束的相应工作人员（任务）。对于后半部分的任务和工作人员，当新任务或工作人员到达时，TGOA会尝试执行全局最佳匹配已经到达的后半个顶点，以减少被困在上半部任务和工人的贪婪策略的局部最优的可能性。与Extended Greedy-RT算法类似，对于每个具有容量cw的工人，本文将其视为同时到达并逐个处理它们的cw重复工作者。

2.TGOA-Greedy算法

请注意，尽管TGOA算法在后半部分顶点采用了更优化的策略以确保更高的分配结果质量，但由于需要立方时间复杂度来找到每个第二个的当前全局最优匹配，因此效率不高。因此，本文通过用贪婪策略取代最优匈牙利算法来提高TGOA的效率，但这也导致竞争比率略低。

实验

通用空间众包平台。在gMission数据集中，每个任务都有任务描述，位置，发布时间，截止日期和支付。每个工作人员还根据他/她完成任务的历史记录与位置，可用时间，截止日期，最大活动范围和成功率相关联。 EverySender是校园内的空间众包快递平台，校园内的每个人都可以发布微任务，例如：购买一些饮料或收集包裹，或作为众包工作者执行任务。与gMission数据集类似，EverySender数据集中的每个任务和工作程序也包含其相应的信息。由于数据集中没有给出工人的能力，本文产生了均匀分布的工人的能力。还使用合成数据集进行评估。分别按照均匀分布和正态分布生成效用值。此外，所有任务和工人的到达顺序遵循在线随机订单模型之后的均匀分布。

根据总效用评分，运行时间和内存成本评估Greedy-RT，TGOA和TGOA-Greedy算法，并研究不同参数对算法性能的影响。在每个实验中，本文反复测试50个不同的任务和工人的在线到达顺序，并报告平均结果。

实验结果

与Extended Greedy-RT（基线）算法相比，使用基于两阶段的框架的算法总能实现更大的总效用值。 TGOA-Greedy算法虽然在理论上具有比TGOA算法更低的竞争比，但在运行时间和内存成本方面明显优于TGOA算法，并且在总效用方面几乎与TGOA算法一样好。 最后，TGOA-Greedy在实践中在时间和空间方面都是有效且可扩展的。

结论：

本文确定了一个新的在线微任务分配问题，称为空间众包（GOMA）中的全球在线微任务分配。本文首先分析与现有空间众包问题的差异，这些问题假设离线情景和传统的在线最大加权二分匹配（OMWBM）问题。然后，将OMWBM问题的在线对手模型下的最新算法扩展为基线算法。尽管基线算法保证了最坏的情况，但在实践中它的表现并不好。为了找到更好的解决方案，本文首先澄清基线算法的较差性能是因为最坏的情况在现实世界中以非常低的概率发生，然后提出基于两阶段的框架。在此框架的基础上，提出了TGOA算法，该算法在4在线随机顺序模型下具有1竞争比率，该模型描述了在线算法的平均性能，但由于其立方时间复杂度而无法扩展到大数据集。为了提高可扩展性，本文进一步设计了基于两阶段框架的TGOA-Greedy算法，该算法运行速度比TGOA算法快，但返回的竞争比率较低。

本文工作的主要贡献是：

1. 本文提出了一个新的在线微任务分配问题，即空间众包（GOMA）问题中的全局在线微任务分配，该问题具有广泛的空间众包应用。 本文将在线对抗模型下的OMWBM问题的最新算法扩展到GOMA问题作为基线算法，并表明它具有2eln（1 + Umax）的竞争比率，其中Umax是任务的最大效用。
2. 本文发现基线算法在实践中表现不佳，因为对抗模型的最坏情况在现实世界中以非常低的概率发生，提出具有1/4竞争比的两阶段在线随机序列模型。
3. 通过对真实和合成数据集的广泛实验来验证所提方法的有效性和效率。

致谢

本转述工作部分得到国家重点研发计划“信息产品及科技服务集成化众测服务平台研发与应用 (2018YFB1403400)”资助