群智感知中基于局部预算共享的多源任务分配方法及系统

摘要

本申请公开了群智感知中基于局部预算共享的多源任务分配方法及系统，其中方法包括：确定角色类型；角色类型包括：任务请求者、移动群智感知平台和移动群智感知参与者；通过移动群智感知平台收集感知任务；根据感知任务，建立多源感知任务分配模型；基于多源感知任务分配模型来获取最佳分配方案。本申请采用聚合的思想，通过将位置相近且相似的感知任务聚合并使他们共享预算。并设计一种路径规划方法帮助参与者在任务截止日期前以较低的成本完成任务。最后迭代地为每个感知任务分配合适的参与者，以实现任务分配的目标：最大化任务完成质量和最小化总的移动距离。解决移动群智感知中感知任务与参与者双重异构的多任务分配问题。

权利要求

1.群智感知中基于局部预算共享的多源任务分配方法，其特征在于，步骤包括：确定角色类型；所述角色类型包括：任务请求者、移动群智感知平台和移动群智感知参与者；

通过所述移动群智感知平台收集感知任务；

根据所述感知任务，建立多源感知任务分配模型；

基于所述多源感知任务分配模型获取所述感知任务的最佳分配方案；建立所述多源感知任务分配模型的方法包括：当感知任务被发布在所述移动群智感知平台后，所述移动群智感知平台在所述感知任务的要求和参与者的属性约束下，同时考虑最大化任务完成质量和最小化总的移动距离来建立所述多源感知任务分配模型；

获取所述最佳分配方案的方法包括：

将所述感知任务聚合成多个任务集合，得到集任务；

为执行所述集任务的参与者规划任务路径，并根据所述路径计算参与者完成所述集任务的报酬，得到临时分配结果；

根据所述临时分配结果计算所述集任务的实现效用，基于所述实现效用获取所述最佳分配方案；

首先，将所述感知任务聚合成多个任务集合，得到集任务；

为求得最佳的任务分配方案，移动群智感知平台首先依据感知任务的位置，感知要求将相近的任务聚合在一起，聚合起来的任务将其表示为集任务；当任务请求者将感知任务提交到移动感知平台后，移动感知平台基于感知任务的地理位置将感知任务分类为多个任务集合，所使用的聚类方法包括：DBSCAN聚类算法；

对上述步骤得到的任务集合依据传感要求相似度进一步分解以保证任务集合的大小满足指定范围：maxPts个任务；对于每个任务集合，随机从中选择一个感知任务，然后依次从中选择与该任务最相似的maxPts‑1个感知任务组成新的任务集合，称之为集任务；重复此过程直到所有的任务都被重新划分；

规划所述任务路径的方法包括：

S301.将参与者所在的位置标记为当前位置，将参与者在所述当前位置的时间标记为当前时间，并设置执行序列为空；

S302.计算所述当前位置对于所述集任务中的每个子任务的紧急度，并根据所述紧急度进行排序，将最紧急的任务标记为候选任务；

S303.计算所述当前位置与其他位置的距离，选择距离最近的感知任务，将其记为第二候选任务，并将所述第二候选任务优于所述候选任务执行；

S304.验证所述候选任务与所述第二候选任务是否均能在任务截止日期前完成，得到验证情况；

S305.根据所述验证情况更新所述当前位置、所述候选任务和所述第二候选任务信息；

S306.重复S301‑S305，直到所述集任务中的每个任务都进入执行序列。

2.根据权利要求1所述的群智感知中基于局部预算共享的多源任务分配方法，其特征在于，所述多源感知任务分配模型的目标包括：最大化任务完成质量和最小化总的移动距离。

3.根据权利要求2所述的群智感知中基于局部预算共享的多源任务分配方法，其特征在于，所述多源感知任务分配模型的约束条件包括：任务必须在有限的预算约束下招募参与者；

每个参与者必须在其传感器的工作负载下执行感知任务；

执行感知任务的参与者拥有的传感器必须覆盖感知任务要求；

执行感知任务的参与者必须在任务截止日期之前到达任务的位置。

4.根据权利要求1所述的群智感知中基于局部预算共享的多源任务分配方法，其特征在于，得到所述集任务的方法包括：所述移动群智感知平台首先根据感知任务的位置将感知任务聚合为多个任务集合；当所述任务集合的大小超过集合最大任务数目时，对所述任务集合进行多次划分，直至所有所述任务集合满足集合大小限制，得到所述集任务。

5.根据权利要求4所述的群智感知中基于局部预算共享的多源任务分配方法，其特征在于，进行所述划分的方法包括：在所述任务集合中选取一个随机任务，并选择与所述随机任务相似度最近的任务与所述随机任务组成任务集合。

6.群智感知中基于局部预算共享的多源任务分配系统，其特征在于，包括：角色划分模块、收集模块、构建模块和优化模块；

所述角色划分模块用于确定角色类型；所述角色类型包括：任务请求者、移动群智感知平台和移动群智感知参与者；

所述收集模块用于通过所述移动群智感知平台收集感知任务；

所述构建模块用于根据所述感知任务，建立多源感知任务分配模型；

所述优化模块用于基于所述多源感知任务分配模型获取所述感知任务的最佳分配方案；

所述优化模块的工作流程包括：

将所述感知任务聚合成多个任务集合，得到集任务；

为执行所述集任务的参与者规划任务路径，并根据所述路径计算参与者完成所述集任务的报酬，得到临时分配结果；

根据所述临时分配结果计算所述集任务的实现效用，基于所述实现效用获取所述最佳分配方案；

首先，将所述感知任务聚合成多个任务集合，得到集任务；

为求得最佳的任务分配方案，移动群智感知平台首先依据感知任务的位置，感知要求将相近的任务聚合在一起，聚合起来的任务将其表示为集任务；当任务请求者将感知任务提交到移动感知平台后，移动感知平台基于感知任务的地理位置将感知任务分类为多个任务集合，所使用的聚类方法包括：DBSCAN聚类算法；

对上述流程得到的任务集合依据传感要求相似度进一步分解以保证任务集合的大小满足指定范围：maxPts个任务；对于每个任务集合，随机从中选择一个感知任务，然后依次从中选择与该任务最相似的maxPts‑1个感知任务组成新的任务集合，称之为集任务；重复此过程直到所有的任务都被重新划分；

规划所述任务路径的方法包括：

S301.将参与者所在的位置标记为当前位置，将参与者在所述当前位置的时间标记为当前时间，并设置执行序列为空；

S302.计算所述当前位置对于所述集任务中的每个子任务的紧急度，并根据所述紧急度进行排序，将最紧急的任务标记为候选任务；

S303.计算所述当前位置与其他位置的距离，选择距离最近的感知任务，将其记为第二候选任务，并将所述第二候选任务优于所述候选任务执行；

S304.验证所述候选任务与所述第二候选任务是否均能在任务截止日期前完成，得到验证情况；

S305.根据所述验证情况更新所述当前位置、所述候选任务和所述第二候选任务信息；

S306.重复S301‑S305，直到所述集任务中的每个任务都进入执行序列。

说明书

群智感知中基于局部预算共享的多源任务分配方法及系统

技术领域

[0001] 本申请涉及计算机网络技术领域，具体涉及群智感知中基于局部预算共享的多源任务分配方法及系统。

背景技术

[0002] 随着智慧城市、数字城市的兴起，越来越多的环境数据需要被监测以便实施相应的政策，加以改正。并且一些公司或科研机构也需要执行相关的感知任务用于研究。然而，建立大规模的、专门的数据监测站是一项巨大的支出，且这些数据监测站位置固定，难以适应复杂、灵活的数据感知需求。移动群智感知模式的出现解决了这一问题。一方面，越来越多的移动终端实现了强大的数据感知能力，其内置的丰富的传感器让完成专业的数据收集任务称为可能。另一方面，移动群智感知平台充分的利用了人群的移动性。由于人的移动性使得感知不仅仅局限在一个区域内，可以适应更加复杂灵活的感知要求。

[0003] 任务分配是移动群智感知平台的一个重要的设计要点。一个好的任务分配策略能够帮助任务更加高效的完成。在移动群智感知的场景中，随着通用的移动群智感知平台的建设，越来越多感知要求迥异的感知任务被发布在平台上。并且随着平台规模的壮大，越来越多的参与者注册到移动感知平台上。这些参与者由于其购买设备的不同，在感知能力上存在差异。当前的研究主要关注了任务或工人单方面的任务分配研究。忽略了移动群智感知中感知任务与参与者双边异构的复杂情景。并且处于隐私方面的考虑，工人往往并不愿意公开他们所有的传感器，除非他们获得符合他们期望的报酬。综上，需要一种能够有效应对此情景的任务分配方法来保障移动群智感知平台的平稳运行。

发明内容

[0004] 本申请通过对多源任务分配系统建模，并针对该模型设计了一种基于局部预算共享的思想和求解方法，在参与者与感知任务双重异构的情况下提升了任务的完成质量，并且进一步减少了参与者的移动距离。

[0005] 为实现上述目的，本申请提供了群智感知中基于局部预算共享的多源任务分配方法，步骤包括：

[0006] 确定角色类型；所述角色类型包括：任务请求者、移动群智感知平台和移动群智感知参与者；

[0007] 通过所述移动群智感知平台收集感知任务；

[0008] 根据所述感知任务，建立多源感知任务分配模型；

[0009] 基于所述多源感知任务分配模型获取所述感知任务的最佳分配方案。

[0010] 优选的，建立所述多源感知任务分配模型的方法包括：当感知任务被发布在所述移动群智感知平台后，所述移动群智感知平台在所述感知任务的要求和参与者的属性约束下，同时考虑最大化任务完成质量和最小化总的移动距离来建立所述多源感知任务分配模型。

[0011] 优选的，所述多源感知任务分配模型的目标包括：最大化任务完成质量和最小化总的移动距离。

[0012] 优选的，所述多源感知任务分配模型的约束条件包括：

[0013] 任务必须在有限的预算约束下招募参与者；

[0014] 每个参与者必须在其传感器的工作负载下执行感知任务；

[0015] 执行感知任务的参与者拥有的传感器必须覆盖感知任务要求；

[0016] 执行感知任务的参与者必须在任务截止日期之前到达任务的位置。

[0017] 优选的，获取所述最佳分配方案的方法包括：

[0018] 将所述感知任务聚合成多个任务集合，得到集任务；

[0019] 为执行所述集任务的参与者规划任务路径，并根据所述路径计算参与者完成所述集任务的报酬；

[0020] 根据所述报酬，迭代地为所述集任务招募参与者以获得所述最佳分配方案。

[0021] 优选的，得到所述集任务的方法包括：所述移动群智感知平台首先根据感知任务的位置将感知任务聚合为多个任务集合；当所述任务集合的大小超过集合最大任务数目时，对所述任务集合进行多次划分，直至所有所述任务集合满足集合大小限制，得到所述集任务。

[0022] 优选的，进行所述划分的方法包括：在所述任务集合中选取一个随机任务，并选择与所述随机任务相似度最近的任务与所述随机任务组成任务集合。

[0023] 优选的，规划所述任务路径的方法包括：

[0024] S301.将参与者所在的位置标记为当前位置，将参与者在所述当前位置的时间标记为当前时间，并设置执行序列为空；

[0025] S302.计算所述当前位置对于所述集任务中的每个子任务的紧急度，并根据所述紧急度进行排序，将最紧急的任务标记为候选任务；

[0026] S303.计算所述当前位置与其他位置的距离，选择距离最近的感知任务，将其记为第二候选任务，并将所述第二候选任务优于所述候选任务执行；

[0027] S304.验证所述候选任务与所述第二候选任务是否均能在任务截止日期前完成，得到验证情况；

[0028] S305.根据所述验证情况更新所述当前位置、所述候选任务和所述第二候选任务信息；

[0029] S306.重复S301‑S305，直到所述集任务中的每个任务都进入执行序列。

[0030] 优选的，获取所述最佳分配方案的方法包括：

[0031] 计算每个参与者执行上述集任务的报酬，得到临时分配结果；

[0032] 根据所述临时分配结果计算所述集任务的实现效用；

[0033] 基于所述实现效用获取所述最佳分配方案。

[0034] 本申请还提供了群智感知中基于局部预算共享的多源任务分配系统，包括：角色划分模块、收集模块、构建模块和优化模块；

[0035] 所述角色划分模块用于确定角色类型；所述角色类型包括：任务请求者、移动群智感知平台和移动群智感知参与者；

[0036] 所述收集模块用于通过所述移动群智感知平台收集感知任务；

[0037] 所述构建模块用于根据所述感知任务，建立多源感知任务分配模型；

[0038] 所述优化模块用于基于所述多源感知任务分配模型获取所述感知任务的最佳分配方案。

[0039] 与现有技术相比，本申请的有益效果如下：

[0040] 解决移动群智感知中感知任务与参与者双重异构的多任务分配问题。本申请采用聚合的思想，通过将位置相近且相似的感知任务聚合并使他们共享预算。并设计一种路径规划方法帮助参与者在任务截止日期前以较低的成本完成任务。最后迭代地为每个感知任务分配合适的参与者，以实现任务分配的目标：最大化任务完成质量和最小化总的移动距离。

附图说明

[0041] 为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

[0042] 图1为本申请的移动群智感知平台各方交互示意图；

[0043] 图2为本申请的移动群智感知平台多源任务分配机制示意图；

[0044] 图3为本申请的系统结构示意图。

具体实施方式

[0045] 下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

[0046] 为使本申请的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本申请作进一步详细的说明。

[0047] 实施例一

[0048] 本实施例中，首先确定角色类型：任务请求者，移动群智感知平台和移动群智感知参与者。任务请求者包括不同的公司、政府机构和个人，每个任务请求者的专业能力不尽相同。因此他们对感知任务有不同的预算和感知要求。感知任务的属性要求包括：（1）执行感知任务的参与者需要在截止日期前到达任务位置；（2）感知任务需要多个参与者执行并提供感知数据；（3）感知任务的预算由任务请求者不同而有差异。参与者受利益驱动注册在移动群智感知平台，他们携带不同的移动设备，且对不同的传感数据具有不同的隐私关注，这些隐私考虑会因为报酬而发生改变。参与者的属性要求为：（1）每个参与者具有不同的传感器集合；（2）每个参与者对传感器的态度不同（即开放或不开放）；（3）当参与者获得一定的额外奖励，参与者会改变对特定传感器的态度；（4）每个参与者有一组经纬坐标表示参与者当前所在的位置。移动群智感知平台负责接收任务和依据任务分配策略将感知任务分配给参与者。移动群智感知平台与任务请求者、参与者的交互过程如图1所示。

[0049] 如图2所示，展示了在移动群智感知平台中多源任务分配机制的过程。

[0050] 首先，通过移动群智感知平台收集感知任务。

[0051] 移动群智感知平台收集来自不同机构、公司或个人的感知任务。同时具有不同感知能力的参与者注册到移动群智感知平台。来自不同公司、机构的任务请求者依据实际需求指定感知任务的要求，然后将感知任务提交在移动群智感知平台，并向平台支付此任务的预算。携带不同的移动设备的参与者受利益驱动注册在移动感知平台，他们对不同的传感数据具有不同的隐私关注。

[0052] 之后，根据感知任务，建立多源感知任务分配模型。

[0053] 当感知任务被发布在移动感知平台后，移动群智感知平台在感知任务的要求和参与者的属性约束下，同时考虑最大化任务完成质量和最小化总的移动距离来建立多源感知任务分配模型。

[0054] 上述的多源任务分配模型，其第一目标为最大化任务的完成质量。任务的完成质量由执行该任务的参与者人数决定，其公式包括：

[0055]

[0056] 其中，Qi表示任务的完成质量， 表示执行任务i的参与者数量， 表示感知任务i最少需要的参与者人数，而 表示感知任务i最多需要的参与者人数。基于公式（1），移动群智感知平台的任务分配的第一个目标可以表示为：

[0057]

[0058] 其中，T表示移动群智感知平台中的任务集合。

[0059] 而多源任务分配模型的第二个目标为：最小化总的移动距离。

[0060] 总的移动距离被定义为执行任务的参与者的总的移动距离。

[0061]

[0062] 其中，P表示执行任务的参与者集合,  表示是否将任务 分配给参与者j执行，特别地， 表示将任务 分配给参与者j执行。而 表示参与者j执行感知任务i的移动距离。

[0063] 需要说明的是，多源任务分配的约束条件包括：

[0064] （1）任务必须在有限的预算约束下招募参与者；即

[0065]

[0066] 其中， 表示参与者j执行感知任务 时，平台需要向参与者j支付的报酬， 表示感知任务 的预算。

[0067] （2）每个参与者必须在其工作负载下执行感知任务；即

[0068]

[0069] 其中， 时表示参与者j执行感知任务 时使用了传感器 。 表示参与者j的传感器 的工作负载。

[0070] （3）执行感知任务的参与者拥有的传感器必须覆盖感知任务要求。即：

[0071]

[0072] 其中 表示感知任务i需要的传感器集合，而 表示参与者p具有的传感器集合。

[0073] （4）执行感知任务的参与者必须在任务截止日期之前到达任务的位置。即：

[0074]

[0075] 其中， 表示参与者j当前时间，而v表示参与者的移动速度。 表示感知任务的截止时间。

[0076] 最后，基于多源感知任务分配模型来获取最佳分配方案。

[0077] 获得最佳分配方案步骤包括：将感知任务聚合在一起，得到集任务；为执行集任务的参与者规划任务路径；根据任务路径，获取最佳分配方案。

[0078] 首先，将所述感知任务聚合成多个任务集合，得到集任务。

[0079] 为求得最佳的任务分配方案，移动群智感知平台首先依据感知任务的位置，感知要求（即完成感知任务所需传感器）将相近的任务聚合在一起，聚合起来的任务将其表示为集任务。当任务请求者将感知任务提交到移动感知平台后，移动感知平台基于感知任务的地理位置将感知任务分类为多个任务集合，所使用的聚类方法包括但不限于DBSCAN聚类算法。

[0080] 对上述步骤得到的任务集合依据传感要求相似度进一步分解以保证任务集合的大小满足指定范围（如maxPts个任务）。对于每个任务集合，随机从中选择一个感知任务，然后依次从中选择与该任务最相似的maxPts‑1个感知任务组成新的任务集合，称之为集任务。重复此过程直到所有的任务都被重新划分。

[0081] 之后，为执行集任务的参与者规划任务路径。

[0082] S301.当将一个集任务分配给参与者时，平台需要为其规划一条任务完成路径，以保证集任务中的每个任务能在任务截止前被完成的同时最小化参与者的移动距离。

[0083] S302.将参与者所在的位置标记为当前位置，此时的时间标记为该参与者当前时间。并设置执行序列为空。

[0084] S303.计算当前位置对于集任务中的每个子任务的紧急度。计算完成后，将该集任务中的所有子任务按照紧急度进行排序，越紧急的任务排名越靠前。将最紧急的任务记为候选任务。参与者j对任务 的紧急度定义如下：

[0085]

[0086] S304.计算当前位置与其他位置的距离。选择距离最近的感知任务，将其记为第二候选任务。并尝试将第二候选任务优于候选任务执行。

[0087] S305.验证候选任务与第二候选任务是否均能在任务截止日期前完成。若均能被完成则执行以下操作：①将第二候选任务加入执行序列；②将当前位置更新为第二候选任务，并将第二候选任务从剩余任务中移除；③跳转至步骤S304继续执行，直到所有的感知任务均被加入到执行序列中。若调整之后，存在某个任务不能被完成，则执行以下操作：I.将候选任务加入执行序列；将当前位置更新为候选位置，并将候选任务从剩余任务中移除；II.跳转至步骤S303继续执行，直到所有的感知任务均被加入到执行序列中。

[0088] 移动群智感知平台为执行集任务的参与者规划一条完成集任务的任务路径，并计算平台雇佣此参与者完成此集任务所需要支付的报酬。

[0089] 最后，根据参与者完成集任务的报酬，迭代地为每个集任务招募参与者以获得最佳分配方案。

[0090] 平台将集任务以及独立任务分配给合适的参与者执行。执行感知任务的参与者，在执行独立任务时，在感知完成将感知数据返回给移动群智感知平台。在执行集任务时，参与者按照平台规定的任务执行路径感知数据，在集任务被完整执行完后，将感知数据返回给移动群智感知平台。

[0091] a.由于原问题模型优化方向相反，难以判断分配结果优劣。故将最大化任务完成质量转化为最小化完成任务质量的损失。完成任务质量的损失由最大任务完成质量与实际任务完成质量的差表示，即：

[0092]

[0093] 其中， 表示完成任务质量的损失， 表示任务的完成质量。

[0094] 此时任务分配模型的目标为：

[0095]

[0096] b.对于每个感知任务（集任务），计算每个参与者执行此任务需要的报酬。将所有报酬按小到大的顺序排序，并在该任务的预算约束下，贪心的选择参与者。需要注意的是，集任务的预算为集任务包含的所有任务的预算之和。

[0097] c.由步骤b得到的临时分配结果计算每个感知任务（集任务）接收相应的任务分配方案后所能实现的效用。效用定义感知质量的折损率与移动距离的线性加权和。即：

[0098]

[0099] 其中 是权衡因子， 表示参与者完成任务 所移动的总距离。

[0100] d.移动感知平台将效用最小的感知任务（集任务）的分配方案加入平台任务分配方案中。更新感知任务和参与者的状态，跳转至步骤b继续执行，直到所有的任务都被分配出去或所有的感知任务（集任务）的效用为0。

[0101] 以综合移动群智感知平台为例，来自不同的机构的任务请求者向平台提交了他们的任务要求和预算。如某市环保局提交噪声监测任务，该任务需要用到音频传感器和GPS且需要3个参与者完成，其预算为30元；某市大气环境研究所提交了空气质量监测任务，该任务需要用到图像传感器和GPS且需要6个参与者完成，其预算为45元。多个具有不同设备状况和隐私关注的参与者注册在移动群智感知怕平台上，如参与者A具有图像传感器和GPS,但是其不愿意开放图像传感器，除非他能获得5元的额外报酬，且其图像传感器能执行两个任务而GPS可以执行三个任务；参与者B具有图像传感器、音频传感器和GPS，他愿意开放所有的传感器，每个传感器都可以执行四个任务。移动群智感知平台在接收到任务请求者的请求后，基于所提出的任务打包算法将感知任务重新划分，重新定义集任务的属性并使集任务中任务共享预算。接着，平台依据所提出的路径规划算法为每个参与者执行集任务计算一条任务执行序列。最后，基于贪婪的思想，迭代地为每个任务选择参与者。在每一次的迭代中，优先为每个任务招募需要报酬最少的参与者并计算该任务所能实现的效用。效用最小的任务被首先分配参与者。集任务共享预算的思想使得集任务有更多的机会选择更多的参与者，进而增加了任务的完成质量。参与者在或者索要执行的任务后，移动到任务所在的位置感知数据。如果需要执行的任务是独立任务时，参与者在感知完成将感知数据返回给移动群智感知平台。如果要执行的任务是集任务时，参与者按照平台规定的任务执行路径感知数据，在集任务被完整执行完后，将感知数据返回给移动群智感知平台。

[0102] 实施例二

[0103] 如图3所示，为本实施例的系统结构示意图。首先利用角色划分模块确定角色类型：任务请求者，移动群智感知平台和移动群智感知参与者。任务请求者包括不同的公司、政府机构和个人，每个任务请求者的专业能力不尽相同。因此他们对感知任务有不同的预算和感知要求。感知任务的属性要求包括：（1）执行感知任务的参与者需要在截止日期前到达任务位置；（2）感知任务需要多个参与者执行并提供感知数据；（3）感知任务的预算由任务请求者不同而有差异。参与者受利益驱动注册在移动群智感知平台，他们携带不同的移动设备，且对不同的传感数据具有不同的隐私关注，这些隐私考虑会因为报酬而发生改变。参与者的属性要求为：（1）每个参与者具有不同的传感器集合；（2）每个参与者对传感器的态度不同（即开放或不开放）；（3）当参与者获得一定的额外奖励，参与者会改变对特定传感器的态度；（4）每个参与者有一组经纬坐标表示参与者当前所在的位置。移动群智感知平台负责接收任务和依据任务分配策略将感知任务分配给参与者。移动群智感知平台与任务请求者、参与者的交互过程如图1所示。

[0104] 如图2所示，展示了在移动群智感知平台中多源任务分配机制的过程。

[0105] 首先，收集模块通过移动群智感知平台收集感知任务。

[0106] 移动群智感知平台收集来自不同机构、公司或个人的感知任务。同时具有不同感知能力的参与者注册到移动群智感知平台。来自不同公司、机构的任务请求者依据实际需求指定感知任务的要求，然后将感知任务提交在移动群智感知平台，并向平台支付此任务的预算。携带不同的移动设备的参与者受利益驱动注册在移动感知平台，他们对不同的传感数据具有不同的隐私关注。

[0107] 之后，构建模块根据感知任务，建立多源感知任务分配模型。

[0108] 当感知任务被发布在移动感知平台后，移动群智感知平台在感知任务的要求和参与者的属性约束下，同时考虑最大化任务完成质量和最小化总的移动距离来建立多源感知任务分配模型。

[0109] 上述的多源任务分配模型，其第一目标为最大化任务的完成质量。任务的完成质量由执行该任务的参与者人数决定，其公式包括：

[0110]

[0111] 其中， 表示任务的完成质量， 表示执行任务i的参与者数量， 表示感知任务i最少需要的参与者人数，而 表示感知任务i最多需要的参与者人数。基于公式（12），移动群智感知平台的任务分配的第一个目标可以表示为：

[0112]

[0113] 其中，T表示移动群智感知平台中的任务集合。

[0114] 而多源任务分配模型的第二个目标为：最小化总的移动距离。

[0115] 总的移动距离被定义为执行任务的参与者的总的移动距离。

[0116]

[0117] 其中，P表示执行任务的参与者集合,  表示是否将任务 分配给参与者j执行，特别地， 表示将任务 分配给参与者j执行。而 表示参与者j执行感知任务i的移动距离。

[0118] 需要说明的是，多源任务分配的约束条件包括：

[0119] （1）任务必须在有限的预算约束下招募参与者；即

[0120]

[0121] 其中， 表示参与者j执行感知任务 时，平台需要向参与者j支付的报酬， 表示感知任务 的预算。

[0122] （2）每个参与者必须在其工作负载下执行感知任务；即

[0123]

[0124] 其中， 时表示参与者j执行感知任务 时使用了传感器 。 表示参与者j的传感器 的工作负载。

[0125] （3）执行感知任务的参与者拥有的传感器必须覆盖感知任务要求。即：

[0126]

[0127] 其中 表示感知任务i需要的传感器集合，而 表示参与者p具有的传感器集合。

[0128] （4）执行感知任务的参与者必须在任务截止日期之前到达任务的位置。即：

[0129]

[0130] 其中， 表示参与者j当前时间，而v表示参与者的移动速度。 表示感知任务的截止时间。

[0131] 最后，优化模块基于多源感知任务分配模型来获取最佳分配方案。

[0132] 优化模块的工作流程包括：将感知任务聚合在一起，得到集任务；为执行集任务的参与者规划任务路径；根据任务路径，获取最佳分配方案。

[0133] 首先，将所述感知任务聚合成多个任务集合，得到集任务。

[0134] 为求得最佳的任务分配方案，移动群智感知平台首先依据感知任务的位置，感知要求（即完成感知任务所需传感器）将相近的任务聚合在一起，聚合起来的任务将其表示为集任务。当任务请求者将感知任务提交到移动感知平台后，移动感知平台基于感知任务的地理位置将感知任务分类为多个任务集合，所使用的聚类方法包括但不限于DBSCAN聚类算法。

[0135] 对上述流程得到的任务集合依据传感要求相似度进一步分解以保证任务集合的大小满足指定范围（如maxPts个任务）。对于每个任务集合，随机从中选择一个感知任务，然后依次从中选择与该任务最相似的maxPts‑1个感知任务组成新的任务集合，称之为集任务。重复此过程直到所有的任务都被重新划分。

[0136] 之后，为执行集任务的参与者规划任务路径。

[0137] S301.当将一个集任务分配给参与者时，平台需要为其规划一条任务完成路径，以保证集任务中的每个任务能在任务截止前被完成的同时最小化参与者的移动距离。

[0138] S302.将参与者所在的位置标记为当前位置，此时的时间标记为该参与者当前时间。并设置执行序列为空。

[0139] S303.计算当前位置对于集任务中的每个子任务的紧急度。计算完成后，将该集任务中的所有子任务按照紧急度进行排序，越紧急的任务排名越靠前。将最紧急的任务记为候选任务。参与者j对任务 的紧急度定义如下：

[0140]

[0141] S304.计算当前位置与其他位置的距离。选择距离最近的感知任务，将其记为第二候选任务。并尝试将第二候选任务优于候选任务执行。

[0142] S305.验证候选任务与第二候选任务是否均能在任务截止日期前完成。若均能被完成则执行以下操作：①将第二候选任务加入执行序列；②将当前位置更新为第二候选任务，并将第二候选任务从剩余任务中移除；③跳转至步骤S304继续执行，直到所有的感知任务均被加入到执行序列中。若调整之后，存在某个任务不能被完成，则执行以下操作：I.将候选任务加入执行序列；将当前位置更新为候选位置，并将候选任务从剩余任务中移除；II.跳转至步骤S303继续执行，直到所有的感知任务均被加入到执行序列中。

[0143] 移动群智感知平台为执行集任务的参与者规划一条完成集任务的任务路径，并计算平台雇佣此参与者完成此集任务所需要支付的报酬。

[0144] 最后，根据参与者完成集任务的报酬，迭代地为每个集任务招募参与者以获得最佳分配方案。

[0145] 平台将集任务以及独立任务分配给合适的参与者执行。执行感知任务的参与者，在执行独立任务时，在感知完成将感知数据返回给移动群智感知平台。在执行集任务时，参与者按照平台规定的任务执行路径感知数据，在集任务被完整执行完后，将感知数据返回给移动群智感知平台。

[0146] a.由于原问题模型优化方向相反，难以判断分配结果优劣。故将最大化任务完成质量转化为最小化完成任务质量的损失。完成任务质量的损失由最大任务完成质量与实际任务完成质量的差表示，即：

[0147]

[0148] 其中， 表示完成任务质量的损失， 表示任务的完成质量。

[0149] 此时任务分配模型的目标为：

[0150]

[0151] b.对于每个感知任务（集任务），计算每个参与者执行此任务需要的报酬。将所有报酬按小到大的顺序排序，并在该任务的预算约束下，贪心的选择参与者。需要注意的是，集任务的预算为集任务包含的所有任务的预算之和。

[0152] c.由步骤b得到的临时分配结果计算每个感知任务（集任务）接收相应的任务分配方案后所能实现的效用。效用定义感知质量的折损率与移动距离的线性加权和。即：

[0153]

[0154] 其中 是权衡因子， 表示参与者完成任务 所移动的总距离。

[0155] d.移动感知平台将效用最小的感知任务（集任务）的分配方案加入平台任务分配方案中。更新感知任务和参与者的状态，跳转至步骤b继续执行，直到所有的任务都被分配出去或所有的感知任务（集任务）的效用为0。

[0156] 以上所述的实施例仅是对本申请优选方式进行的描述，并非对本申请的范围进行限定，在不脱离本申请设计精神的前提下，本领域普通技术人员对本申请的技术方案做出的各种变形和改进，均应落入本申请权利要求书确定的保护范围内。