时空众包技术综述

2022-08-02程维杰李洪贵范勇强彭钰寒

无线电工程 2022年8期

程维杰，李洪贵，范勇强，彭钰寒，甘戈

(1.四川省金科成地理信息技术有限公司，四川成都 610095；2.成都市生态环境数智治理中心，四川成都 610015；3.成都信息工程大学，四川成都 610225；4.成都市公安局，四川成都 610017)

0 引言

众包是一种让人们主动或被动参与任务的新技术，自提出以来引起了广泛关注，国内已经有很多类似美团、滴滴和顺丰快递等成功的众包平台。随着全球经济和科技发展，移动设备的先进和普及以及5G技术的突破，学者们提出了一种新的众包类型，叫作时空众包，也称为空间众包。时空众包是调度人群去现实生活中的指定地点执行指定的任务，任务具有强烈的时空性质，是传统众包不能比拟的。

时空众包包含任务、工作人员和平台3个部分，传统众包虽然包含上述3部分任务，但是不同之处在于[1]：时空众包具有时空约束，而传统众包没有。时空约束是指时空属性的约束，也就是时空众包中的任务、工作人员和平台包含自己的时间和空间属性。本文主要从任务分配、众包评估和激励机制3个方面进行综述。

众包平台每天要管理大量的任务和工作人员，工作人员每天向平台提出任务分配申请，产生大量数据。因此，时空众包面临的首要问题就是如何把任务高效地分配给员工，即任务分配[2]。任务分配是众包工作中最重要的一步，因为众包工作首先要解决的问题就是任务分配，如果任务分配解决不好，众包平台就不能长久运作。众包评估是指分辨工作人员完成众包平台分配任务质量的好坏，可以量化工作人员完成任务的质量，并记录这部分结果，这样可以在一定程度上让工作人员高质量完成任务，让众包平台高质量、高效运转。在进行众包评估时，需要保护工作人员的个人隐私，平台不能泄露这部分信息。也可以在工作人员同意的情况下，对工作人员的评估情况进行排名。激励机制是指对工作情况优良的员工进行激励，从而增加工作人员的粘性，并吸引更多的员工来参与众包。时空众包的激励机制是动态的，针对不同的区域设立特定的激励机制。例如：如果一个区域的工作人员数量很少，那么完成这个区域内的任务应该适当提高奖励，来让工作人员更有动力到这个区域来完成任务。

在对时空众包的算法进行详细介绍之前，需要给出以下几个基本概念。

任务请求者：负责在众包平台上发布任务，当工作人员接收并完成任务后，任务请求者根据任务的完成情况通过众包平台给予工作人员对应的奖励。

工作人员：是众包平台上接收任务领取奖励的人。

任务：是由任务请求者发出的需要工作人员完成的事。

奖励：是任务请求者通过众包平台给予工作人员的东西。

众包平台：是任务请求者和工作人员互动的地方，众包平台的运行成本的主要来源是工作人员，即在工作人员的激励中抽取一笔费用当作众包的运行成本。

本文的贡献如下：① 按时间顺序介绍任务分配、众包评估和激励机制的具体方法；② 详细概述了现有的众包技术；③ 讨论了众包技术未来面临的挑战。

本文首先介绍众包技术相关的背景并详细综述众包技术相关算法的研究现状，涉及任务分配、众包评估和激励机制；然后描述时空众包的工作流程；最后展望众包技术的发展方向。

1 时空众包工作流程

时空众包的工作流程涉及任务申请者、工作人员、任务和众包服务器4个部分。任务申请者是一个人或者一个组织，负责请求任务并为任务设立奖励；工作人员负责执行平台分配或自己选择的任务，有自己的时间属性和空间属性；任务由任务请求者发布在众包平台上，也有自己的时间属性和空间属性；众包服务器监控整个众包工作流程，在工作人员和任务请求者信息交互时，众包服务器作为媒介，保管重要数据。时空众包工作流程如图1所示。

图1 时空众包工作流程Fig.1 Workflow of spatial crowdsourcing

时空众包工作流程有以下步骤：① 任务请求者设立任务和奖励，将任务信息上传到众包平台。② 众包平台接收任务请求者上传的任务，从通过平台评估的工作人员中查找合适的人，将任务分配给工作人员。③ 工作人员接收众包平台的信息后，查看分配的任务，通过任务奖励和任务难度决定是否要接收任务。如果工作人员接收任务，那么就前往指定地点完成任务；如果不接收，众包平台接收任务拒绝请求，并将任务分配给新的工作人员。④ 工作人员接收任务并到达指定地点完成任务后，将任务完成情况上传至众包平台，众包平台发送消息到任务请求者处，让任务请求者检查。如果任务请求者满意，众包平台就会将任务奖励发送给工作人员；如果任务请求者不满意，任务请求者可以申请退回奖励或者继续找工作人员完成指定任务。⑤ 如果工作人员认为任务请求者恶意拒绝接收任务，可以向众包平台提出申请，让众包平台作为第三方对提交的任务结果检查。如果众包平台认为任务提交情况符合要求，就会与任务请求者进行调节，如果任务请求者不配合，就会采取扣除信誉分等形式惩罚任务请求者。

综上，众包技术概述图如图2所示。

图2 众包技术概述图Fig.2 Overview of crowdsourcing techniques

此外，众包技术在通信领域也取得了长足进展。例如，众包平台执行任务分配、众包评估或激励时，难以实现的通信算法得以实现。例如，更高效地利用地理位置信息，让任务分配更加快速，增加众包平台的工作效率；使收集工作人员和任务的时空信息更加容易，让攻击者难以攻击，保护隐私安全。

2 任务分配

任务分配是时空众包面临的主要挑战，在介绍任务分配前，需要介绍传统的众包工作流程。首先，任务请求者进入众包平台，发布其想要解决的任务，并为任务附上相关说明和完成任务能得到的奖励。然后，在众包平台注册的工作人员便可以搜寻符合自身能力的任务，尝试完成它。最后，如果工作人员成功完成任务并上传结果，就可以给任务请求者进行检查。任务请求者判断任务完成情况是否满足自己的期望，如果满足，众包平台就会将任务对应的奖励分配给工作人员。

经典的众包工作流程已经不再适用当前基于位置的服务应用，众包平台需要向时空众包平台转型。时空众包平台的特点是工作人员不用自行查找任务，而是平台将工作人员分配到合适的任务中。因为时空众包中所有问题都以任务分配的好坏为基础，所以任务分配被认为是时空众包中最基本的问题。任务分配好坏的标准有很多种，比如任务的奖励程度、工作人员对平台分配任务的接受率、工作人员完成任务需要付出的成本等。本节将从在线场景和离线场景2个维度对任务分配的方法进行分类[3]。但仅有任务分配是不够的，因为任务分配可能会出现任务分配不合理，导致多个工作人员匹配到相同的任务或工作人员取消任务，以致于还需要进一步进行任务调度，用来调度分配不合理的任务。本文对任务调度从在线场景和离线场景2个维度进行分类。

2.1 离线场景的任务分配

在离线场景中，工作人员和任务是静态的，平台一开始就知道他们的时空信息，时空信息包括任务和工作人员的时间和位置信息。假设众包平台中有一组工作人员和一组任务，需要将所有工人都分配到任务中。离线场景因为简化了场景，在实际生活中并不常用，这里不做详细介绍。因为真实场景有时空属性的限制，工作人员全部分配到任务并完成任务是一种理想状态。即使工作人员分配到了任务，但是如果需要经过长途跋涉才能去完成任务，工作人员可能会取消任务。在线场景中如果想优化匹配结果，需要明确优化目标和方向，一般可以从利用最大化和成本最小化2个方面出发。

2.2 在线场景的任务分配

在线场景中，工作人员和任务是动态的，也就是只有任务和工作人员提交信息的时候平台才知道他们的时空信息。在线场景比静态场景更符合现实情况，因为现实生活中任务请求者可以在任何时间任何地点向众包平台提供新的任务，提交的任务会因超过时间限制而过期，工人的数量也会随时变化，所以任务和工作人员的时空信息随时都在变化。众包平台掌握这些信息比较困难，所以对于在线场景随时变化的时空信息，不存在一个将任务分配给工作人员的最优解，通常只能求得局部的最优解。

局部最优解的理论依据在于，虽然工作人员和任务是动态的，但是他们在某一时刻的时空信息是静态的，可以根据某一时刻的时空信息求得瞬时数据，然后根据一段时期的瞬时结果求得局部最优解。解决在线任务分配问题的算法，按照发布的时间进行排序，常见算法包括：最小位置熵优先级算法(Least Location Entropy Priority，LLEP)[4]、任务路径智能个性化模型(Individualized Models for Intellligent Routing of Tasks，IMIRT)[5]和双阶段在线全局微任务分配算法(Two-sided Global Online Micro-task Allocation，TGOA)[6]。

Kazemi等人[4]提出的最小位置熵优先级算法也被称作最小成本算法，包含2个主要步骤：① 利用匈牙利算法寻找最大匹配；② 利用类似分枝定界的整数规划技术，让任务分配的成本最小。

Hassan等人[5]提出一种用于在线任务分配的任务路径智能化模型，将多臂老虎机问题融入到在线分配中。其中，工人视作手臂，任务分配给工人的过程视作游玩多臂老虎机。IMIRT模型的基本思想为：对于一个新到达的任务，选择一个具有最高成功概率的工人让任务成功的概率最大化。成功的概率是从不断测试多臂老虎机中得到的。

Tong等人[6]提出TGOA算法，其基本思路是将所有任务和工人分为2个相同的组，对其采取不同的策略:第1个组采用贪心策略，将每个新到达的任务(或者工作者)分配给能更好完成任务且满足所有约束条件的工作者(或任务)；第2个组采用匈牙利算法，让匈牙利算法找到最优的匹配方案。下面展示TGOA算法的流程，如算法1所示。

算法1:混合端到端训练法输入:一组任务T,一组工人W输出:一个合理的任务分配M1.m←|T|,n←∑w∈WCw, Κ← ⌊(m+n)/2」;2.初始化W△←Φ,T△←Φ;3.FOR平台收到的每个到达的任务或者工人υ DO4. IF | T△|+| W△|

算法1的工作原理为：首先初始化任务的总数m和工人的总数n，将每个有能力完成任务的工人Cw保留下来(第1行)。然后，初始化2个集合来保存平台接收的任务和愿意完成任务并符合条件的工人(第2行)。算法迭代地处理每个新到达的任务或工作者(第3～23行)，前半部分采用贪婪策略(第4～11行)；后半部分采用最优策略(第13～20行)。在最优策略前半部分，分配一个满足所有约束条件且未被分配出去的任务(第6～8行)，或者分配一个满足所有约束条件且未被分配出去的工人(第9～11行)；在最优策略后半部分，采用了匈牙利算法来获得全局的最优匹配Mυ，并更新任务分配的结果M(第13～20行)。最后，更新最开始初始化的2个集合T△和W△，返回一个合理的任务分配结果M。

Xu等人[7]设计了云边缘计算中社会福利最大化的众包市场激励机制，提出了云边缘计算框架下的双作用模型，通过实验评价和对比分析，验证了模型的可用性。图3展示了云计算众包模型工作原理，包括云平台层、网络层和交流层。

图3 云计算众包模型Fig.3 Cloud computing crowdsourcing model

2.3 离线场景的任务调度

任务调度的基本思路为：创建一个任务序列，让工人执行的任务数量最大化。可以通过生成一个空间序列让工人执行任务的成本最小化。解决离线场景任务调度的算法主要有2种：精确算法和贪心算法。因为离线场景在现实场景中不实用，本节只介绍一对多场景的离线场景的任务调度。

一对多的离线场景任务调度的目标是为工作人员找到一条执行任务的路径，让他执行更多的任务，同时成本是工作人员可以接受的。Deng等人[8]首先研究了离线场景中的任务调度，以成本预算为前提，让工作人员执行任务总数量最大化，利用精确算法和贪心算法来解决任务调度。另外，Deng等人提出几种精确算法，包括动态规划算法MST (Maximum Task Scheduling)、2种基于分支定界的算法MST-DP (Maximum Task Scheduling-Dynamic Programming)和MST-BB (Maximum Task Scheduling-Branch and Bound)。上述算法应用了剪枝策略来减少算法运行的时间。

2.4 在线场景的任务调度

在线场景比离线场景更具挑战性，因为工作人员和任务的时空信息是未知的，并且在线场景中众包平台给工作人员分配的任务被拒绝的可能性比离线场景的可能性要高，增加了在线任务分配的复杂性。比如在线场景给工作人员分配远离工作人员当前位置的任务，如果奖励不够，大概率会被工作人员拒绝。本节从一对多和多对多2个方面对在线场景的任务调度进行描述。

一对多的任务调度中，和离线场景一样，目的都是为了让工作人员完成任务的数量最大化。Tong等人[9]提出了一种面向预测的实时空间数据在线任务分配算法，符合实时空间数据中在线任务分配的需求，让分配的效果理想化。Li等人[10]提出了2种基于贪婪算法的方法——Nearest-neighbor heuristic和Earliest deadline heuristic，这2种算法都运用了双向搜索和剪枝策略，提高了算法的执行效率。

多对多的任务调度中，主要针对成本最小化进行综述。针对成本最小化，Ma等人[11]研究拼车服务的在线场景任务调度方法，基于网格索引提出一种框架T-Share，用来调度不合理的任务。Liu等人[12]设计了一种动态树，用来插入和更新工作人员的相关路径，求取成本最小的路径。徐天承等人[13]提出了一种基于轨迹的任务分布预测法，利用图卷积神经网络和全连接卷积神经网络模型进行预测任务成本，更加契合时空众包平台的时效性。

3 众包评估

众包评估是时空众包工作中的关键步骤，如果评估结果不可靠，那么众包平台不能高效运作。众包评估主要是针对工作人员的绩效进行评估，判断工作人员的能力和适合的任务。本节将讨论众包评估的不同指标和评估的方法，以及众包评估过程中的隐私保护。

3.1 评估指标

定义1准确性[14]：任务完成的准确性是众包中使用最广泛的指标，通常以0～1的一个数字来表达准确性。例如，如果一个任务只有正确和错误2种结果，用1来表示任务成功，0表示任务失败。如果一个任务分割成不同的问题，工作人员只完成了其中几个问题，那么完成度可以用0～1的数来表示。

定义2成本[14]：表示为C=，其中w代表工人信息，t代表任务信息。w.l和t.l表示工人和任务的空间信息，w.t和t.t表示工人和任务的时间信息，如工人到达任务地点的之间，任务由任务请求者上传的时间。通过工人和任务的时空信息可以预算成本。

众包平台因为良好的经济性和实用性广泛流行，其中成本是一项重要的评估指标。一般的众包平台中，任务请求者提交的工作内容都有一个预先指定的成本，工作人员根据任务内容和成本判断任务是否合理。

定义3任务完成时间[14]：工作人员完成整个任务花费的时间。众包平台一般会向任务请求者提供任务时间相关信息，同时任务请求者也可以为每个任务设置最大的时间限制。

定义4影响因素[14]：长期影响众包平台的运行质量的因素，是评估指标的一部分，包括任务请求者的满意度、工作人员的离职率和工作人员继续执行任务的可能性等因素。

此外，还有一些根据特殊任务进行特殊考虑的因素，如对隐私保护的力度是音频转录任务的重要评估指标。

3.2 评估方法

工作人员想要继续在众包平台得到任务，就必须接受来自平台的评估，众包平台通过评估工作人员的工作表现，来决定如何分配任务。评估的参考标准可以有多种，例如工作人员得到的总金额、任务完成的速度以及任务请求者的满意度等。本节给出经典的评估方法。

① 金额评估：金额是任务请求者为任务设立的奖励，一般情况众包平台会根据工作人员获取的金额数量来初步判定工作人员的绩效如何。Liu等人[15]通过预测工人能在任务中获得的金额数来判断工人是否胜任该任务；Oleson等人[16]提出一种程序化方法，提出了一种名为编程黄金的模型来收集工作人员以前的金额数据，判断任务是否能够交给工人完成。

② 资格评估：资格评估是工作人员在接收任务前需要完成的一些问题，一般包括工作人员的工作经验、工作背景和职业技能等问题。Stol等人[17]提出在进行翻译任务前，可以设置一些简单的语言测试来为任务设置一个门槛；Gadiraju等人[18]提出考虑设置一些工作人员的自我评估，通过工作人员的自我评估来判断任务能否分配给工作人员。

③ 信誉评估：工作人员在历史任务中，任务请求者对任务的满意度也可以作为信誉评估的指标，并且通过分析工作人员之间的关系也可以为信誉评估加分。例如，Hata等人[19]设计一种名誉分数，通过分数的多少来评估工作人员。这种分数可以给员工带来一种荣誉感和成就感，也可以用分数对员工进行排名。

④ 行为评估：工作人员在工作中的一些行为可以用来预测工作人员的绩效，工作人员的行为因素与工作人员的输出质量有关。Rzeszotarski等人[20]提出了一种基于用户行为轨迹捕捉的方法，分析了工作人员在完成任务期间的一系列动作，用于预测工作人员的绩效。Kazai等人[21]得出结论：在一些任务中，相较于用金钱作为指标，Rzeszotarski的方法的准确性几乎翻了1倍。行为评估是一种有趣的方法，但是由于隐私保护的原因在现实生活中无法大量实施。

3.3 隐私保护

在众包平台的评估工作中，工作人员需要向众包平台公开自己的位置信息，方便任务分配。但是位置信息很敏感，容易遭到攻击，对手可以通过到手的位置信息推断工作人员的隐私。如外界可以根据工作人员前往医院的次数，推断工作人员的职业或健康信息；根据工作人员前往休闲场所的位置，推断工作人员的生活方式和经济情况。即使工作人员使用假身份，位置信息依然可以识别工作人员的移动模式，揭示工作人员的家庭位置或工作场所的信息。本节将从隐身技术、差分隐私技术和加密技术来对工作人员的隐私保护进行综述。隐私保护技术的相关工作总结如表1所示。

表1 隐私保护技术的相关工作总结Tab.1 Summary of related works on privacy protection technology

隐身技术顾名思义就是对工作人员的时空信息进行隐藏。最常用的隐身技术是空间k匿名(Spatial k-anonymity)，这个方法的原理是考虑反向地理编码和共享相似地理标识符的个体数量，减少个体被识别的概率。基于空间k匿名产生的隐私框架PiRi(Partial-inclusive and Range independence)[22]，该框架在任务分配过程中保护员工隐私。

差分隐私技术是指往原信息内人工添加一些信息，让原信息失真。差分隐私技术能让工作人员在发布任务时删除他们自己的敏感数据，且发布的结果不会受到影响，解决了工作人员对个人信息泄露的担忧。差分隐私技术是任务分配过程中保护工作人员隐私最常用的技术，经过差分隐私技术处理的信息被获取后，很难推断出原信息。Wang等人[23]提出了一种基于霍普菲尔德神经网络的多策略差分隐私框架，该框架包含3种不同的差分隐私机制，具有较高的安全性。Wei等人[24]提出了一种基于差分隐私的位置保护(Differential Privacy-based Location Protection,DPLP)方案，该方案能同时保护任务和工作人员的位置隐私，通过自适应三层网格分解算法和基于差分隐私技术的自适应全金字塔网格算法，将工人和任务的准确位置以网格的形式呈现，通过网格来处理工人和人物的信息。

加密技术是指对工作人员和任务的时空信息进行编码，让敏感信息只能由具有解密密钥的授权才能进行解码。Choudhary等人[25]将椭圆曲线解码(Elliptic Curve Cryptography,ECC)与高级加密标准(Advanced Encryption Standard,AES)相结合，实现图像加密和解密的方法，这种混合过程既有对称算法的实现速度和易用性，也有非对称算法的安全性，让工作人员和任务的信息更安全。Meng等人[26]提出了一种策略，利用关键字搜索(Keyword Search,KS)技术保护基于属性的加密(Attribute-based Encryption，ABE)，防止未经授权的用户查看敏感信息。Sun等人[27]提出了一种基于区块链的两阶段隐私保护机制，第1阶段提出了一种双干扰局部差分隐私算法来干扰工作人员的位置。

4 激励机制

成功的众包平台通常集成了较好的激励机制，激励机制不仅能够提高工作人员的积极性，还能吸引更多的工作人员加入众包平台。奖励一般分为内部奖励和外部奖励2种形式。内部奖励可以加快工作人员完成任务的速度，而外部奖励可以提高任务完成的质量。奖励的形式也有所差别，可以是金钱，也可以社会声望，如一些虚拟的荣誉勋章。本节从内部奖励和外部奖励对以上激励策略进行综述。激励机制的内容和适用性如表2所示。

表2 不同激励机制的内容及适用性Tab.2 Contents and applicability of different incentive mechanisms

4.1 内部激励提升

突出贡献：如果工作人员为了任务本身而工作而不是为了金钱奖励，他们便会拿出更高的行动力去执行任务。例如，日常的志愿工作是一种目的性驱动的例子，工作人员如果能理解和认同任务，就会积极参与到任务之中，提高任务的执行速度。Kaufman等人[28]研究表明，具有明确社会目的任务能吸引更多人无偿奉献，并且如果一个任务参与的人越少，那么参与的人往往会更愿意做贡献。

自我竞争：众包平台可以把工作人员之间的关系转变为一种良性竞争模式，设定一个排行榜让工人查看，让他们自发进行比较，从而推动工作人员更好地完成任务。目前很多众包平台都采用了这种方式，Stepanov等人[29]研究了向工作人员展示分数以及排行榜的优势。目前的众包平台已经在广泛使用排行榜。

工作信任：工作人员之间共享身份和行为等信息，通过这种方法让工作人员之间建立信任和联系，有助于让工作人员产生归属感，从而提高任务完成速度。Hosseini等人[30]认为，保持员工之间良好的关系对工作效率会产生积极影响。但因为需要保护隐私，工作人员对这一情况表示支持才能够实施。

4.2 外部激励提升

合适的奖励：任务请求者在设立任务时，奖励是一个必不可少的属性，合适的奖励形式和数量对任务的顺利完成十分重要。Faradani等人[31]研究表明,适当调整奖励金额能让任务获得更好的结果。Singer等人[32]研究了如何利用不同的定价策略在给定的预算下最大限度地完成任务。

额外的奖金：奖金是一种附加的奖励，是平台奖励杰出工作人员的奖励机制，出色的工作人员是指达到预定设立的目标或者达到平台设立的关键绩效指标的人。Difallah等人[33]提出根据员工的绩效来定期授予奖金。Yin等人[34]提出平台除了设立一个任务截至时间，还可以设立一个更短但合理的时间，如果工人能在这个额外时间内完成任务就能获得额外的奖励。

升职的奖励：升职是指让一名工作人员提升到比他当前职位更高的位置上去，升职的对象为那些长期为平台付出的工作人员，这种奖励能够提升工作人员的满足感，同时激励工作人员更好地完成自己的工作。Dow等人[35]建议将满足条件的员工从内容生产者提升为内容管理者。

4.3 激励机制应用

Zhu等人[36]研究了内部激励机制，发现共享知识提升的绩效比私有知识高，从而建立了知识共享激励机制，这种机制可以实现众包平台与工作人员的双赢。知识共享激励机制的关键要素包括：① 众包管理者决定知识共享的奖励；② 任务请求者决定自己任务的知识共享程度;③ 这种机制中存在随机项εi，用于表明不确定性，例如众包管理员由于自身习惯不同，在众包方案上的选择存在不确定性。Shi等人[37]利用用户之间的社会影响力作为激励因素用户参与众包任务，降低招募用户的成本。考虑了3种情况:信息共享、、部分信息共享和信息不共享。根据任务分配和用户招聘机制，在降低激励成本的同时优化数据质量。