面向单任务质量保障的移动群智感知任务分配

杨桂松，吴笑天，高 丽，何杏宇，3

（1.上海理工大学 光电信息与计算机工程学院，上海 200093；2.上海理工大学 图书馆，上海 200093；3.上海理工大学 出版印刷与艺术设计学院，上海 200093）

0 概述

随着物联网的发展以及移动智能穿戴设备的普及，移动群智感知（Mobile Crowd Sensing，MCS）成为一种新兴物联网感知范式［1］，其利用工人携带的智能穿戴设备来完成感知任务，具有覆盖范围广、部署成本低等优点，在环境监测［2］、交通数据恢复［3］、智慧城市［4］等领域得到广泛应用。典型的MCS 系统通常包含任务请求方、平台和工人这3 种角色，通用的感知过程可以描述为：首先，任务请求方将任务发布到平台；然后，平台雇佣合适的工人来执行任务；接着，在完成任务后工人将感知数据上传到平台并从平台获得相应的报酬；最后，平台整合感知数据，将感知结果反馈给任务请求方以获取收益。

任务分配是MCS 中的一个研究热点，其目标是在各种条件（如平台预算、任务时空需求等）约束下，将任务分配给合适的工人。早期的任务分配研究主要关注单任务分配［5-6］，未考虑任务间的依赖关系（如位置、任务内容等）。随着任务数量的增加以及任务间依赖关系的加深，多任务分配逐渐成为研究热点［7-8］。在多任务分配中，平台拥有一个公共的资源池和任务池，其中，资源池包含有限的工人池和预算，任务池包含平台需要完成的具有依赖关系的任务。研究人员通过挖掘不同的应用场景因素（如任务紧迫性［9］、时空相关性［10-11］等），针对不同的优化目标（如最大化时空覆盖率［12］、最小化感知成本［13］等）设计高效的多任务分配方法，以合理利用平台资源来完成任务池内的任务。

现有多任务分配研究的关注点之一是最大化平台所获得的感知质量，如任务完成率［14］、高质量样本数［15］等。文献［16］分析工人相关属性，提出一种基于迭代贪婪过程的多任务分配框架，其最大化平台所获得的整体数据质量。基于对工人轨迹的分析与预测，文献［17］在平台预算受限的情况下，在每一个感知周期内选择一组工人来执行任务，进而最大化平台的整体时空覆盖质量；文献［18］提出一种细粒度的任务分配方法，以平台总预算为约束，使用迭代贪婪的方法求解一个近似最优任务分配方案（包含一组工人任务对的集合），从而最大化平台所获得的整体数据质量；文献［19］以工人设备可用性和工人感知能力为约束，提出一种两阶段离线多任务分配框架，以最大化系统的整体数据质量。

在现有多任务分配研究中，平台的感知质量通常被计算为每个任务感知质量的加权求和值。当任务数量较少时，任务间的资源竞争不激烈，现有方法可以在有效保障每个任务感知质量的前提下最大化平台的整体感知质量。然而，随着MCS 的发展，任务请求方的需求增强，平台需要具有应对大规模任务分配场景的能力。在大规模任务分配场景下，平台有限的资源将加剧任务间的资源竞争，且由于不同的任务对感知质量存在不同的需求，导致现有多任务分配方法无法有效保障每个任务的感知质量。现有利用加权求和的多任务分配方法未充分分析权重计算的影响因素，该权重值通常和任务重要程度、任务需求、任务执行成本等多种因素相关，随着任务数量的增加，每个任务的权重很难准确计算。除加权求和法之外，一种直观的思路是在平台资源的限制下，根据任务的感知质量需求、重要程度、执行成本等多种因素依次计算出每个任务需要的最低资源，然后根据这些资源来有效保障每个任务的感知质量，但这种操作不符合实际，原因是传统MCS 中不存在恶意工人的假设和现实不符，平台的资源通常允许每个任务存在一定的数据冗余，从而保障其感知质量，而每个任务的感知质量需求和具体的数据冗余量有所不同，平台难以依次准确计算出每个任务所需要的资源。

基于上述分析，现有多任务分配方法难以有效保障大规划任务分配场景下每个任务的感知质量，容易产生以下2 种情况：部分任务获得过量资源，产生过多的冗余数据；部分任务获得较少资源，产生过少的冗余数据。事实上，考虑到感知质量具有子模性［18］，即相同的资源为平台所带来的感知质量提升会随着资源的增多而逐渐变小，因此，任务拥有过量冗余数据会占用过多的资源，造成资源浪费。另外，考虑到实际应用中存在恶意用户，任务拥有过少的冗余数据可能无法保障其感知质量，导致任务需要被重新分配，从而增加系统成本。因此，如何利用有限的资源在保障每个任务感知质量的前提下完成多任务分配，成为当前的研究热点与难点。

本文提出一种面向单任务质量保障的任务分配方法。考虑到任务固有属性和工人理性因素对资源竞争的影响，该方法分别从任务和工人的角度设计时空覆盖效率和工人利用效率，将两者相结合作为平台的系统效用，用于评估最终获取的任务分配方案是否可以有效保障每个任务的感知质量。同时，考虑到群体智能算法在解决NP 难问题方面的优势（如不易陷入局部最优解、寻优速度快等），为寻找最优的任务分配方案，该方法将最大化系统效用作为优化目标，提出一种融合交叉和变异操作的天牛群（Beetle Swarm Optimization，BSO）算法，通过对初始随机任务分配方案进行迭代更新来找出具有最大系统效用的方案。

1 系统模型

本文在系统模型设计时考虑一种常见的MCS应用场景，该场景包含一个平台、多个任务请求方以及一组工人，系统模型工作流程如图1 所示。首先，多个任务请求方分别将由自身数据需求所产生的任务发布至MCS 平台，平台将任务信息发送给工人；然后，工人根据平台的任务信息和激励政策决定是否参与感知活动，如果决定参与感知活动，则需要上传自身信息至平台；之后，平台根据工人信息表（包含工人位置信息、设备感知能力等）与任务，产生最优任务分配方案，并根据该方案进行任务分配；最后，工人完成平台分配的任务，将感知数据上传至平台并获得相应的报酬，平台融合所有感知数据后将结果反馈给任务请求方。

图1 系统模型工作流程Fig.1 System model workflow

为清晰展示任务分配的流程，将系统模型的相关参数定义如下：平台拥有一个总预算（表示为B）、一个包 含r个工人的工人集(表示为W={w1,w2,…，wi,…,wr}) 以及一个包含f个任务的任务集(表示为T={t1,t2,…，tj,…,tf}) 。考虑到任务的时空特征以及工人的感知范围有限，平台将每个任务的感知区域划分为多个子区域，同时基于任务需求将感知周期划分为多个子周期。相应地，平台上f个任务的感知区域构成集合Re={Re1,Re2,…,Rej,…,Ref}，其中包含m个感知子区域的第j个任务感知区域(表示为Rej={rej,1,rej,2,…,rej,m}) ；f个任务的感知周期构成集合Cy={Cy1,Cy2,…,Cyj,…,Cyf}，其中包含n个感知子周期的第j个任务感知周期(表示为Cyj={cyj,1,cyj,2,…,cyj,n}) 。然后，根据任务感知区域和感知周期划分，任务可以被划分为一组时空单元，其中每一个时空单元由一个感知子周期和一个感知子区域组成，需要一个工人来执行该时空单元的任务。之后，根据任务和设备的特性，工人执行任务的能力和任务被执行的需求分别被抽象为工人携带设备拥有的传感器和执行任务需要的传感器。假设和工人执行任务过程相关的传感器一共包含l类，那么工人携带的设备被抽象化为一组二元值，其中，第i个工人的传感器组表示为SWi={swi,1,swi,2,…,swi,k,…,swi,l}。如果工人携带的设备上存在第k类传感器，则swi,k=1，否则为0；任务执行的需求也被抽象化为一组二元值，其中，第j个任务的传感器组表示为STj={stj,1,stj,2,…,stj,k,…,stj,l}，如果任务需要第k类传感器，则stj,k=1，否则为0。

2 问题分析

根据上述系统模型，本节首先设计平台的激励成本，用于计算工人完成任务后平台需要支付的报酬，然后，为保障每个任务的感知质量，考虑任务间的资源竞争来定义任务覆盖效率和工人利用效率，将两者相结合作为平台的系统效用，最大化系统效用即为任务分配的优化目标。

2.1 激励成本设计

在MCS 中，工人理性与平台激励措施密切相关，为激励工人完成任务，工人理性应该被关注，可以通过合理的激励成本设计来达到目的［20］。另外，在平台预算有限时，工人理性也会影响任务间的资源竞争。因此，本文在设计平台的激励成本时充分考虑工人理性，将激励成本分为2 个部分，分别是执行成本设计和执行补偿设计，具体描述如下：

1）考虑到不同任务需要不同类型的传感器，当工人所携带设备的传感器组可以满足任务需求时，工人可以执行任务。若工人wi执行任务tj，工人wi和任务tj可以组成一个可行工人任务对，表示为(wi,tj)，该工人任务对的执行成本定义为：

其中：costk表示第k类传感器被使用时平台需要支付的报酬，其为一个与传感器类型相关的定值。

2）从设备补偿和移动补偿两方面设计执行补偿，即工人执行任务的补偿。其中，设备补偿是指平台需要补偿执行简单任务的高能力工人，其原因是简单任务的报酬较低，从工人理性来看，工人总是追求更高的报酬，长期不考虑设备补偿进行任务分配将影响工人参与感知活动的积极性。移动补偿是指平台补偿在工人密度低的区域执行任务的工人，激励他们执行工人密度低的区域的任务。因此，当工人wi完成任务tj时，平台支付给工人的执行补偿定义如下：

基于上述定义，工人wi执行任务tj的激励成本定义为执行成本与执行补偿之和，计算如下：

2.2 系统效用设计

考虑大规模任务分配场景下任务间的资源竞争，本文从任务和工人2 个角度分别定义任务覆盖效率和工人利用效率衡量指标，然后基于这2 个衡量指标定义平台的系统效用。

在任务感知质量衡量方面，和文献［21-22］类似，本文使用任务的时空覆盖率，其被定义为实际被覆盖的时空单元和需要被覆盖的时空单元之比。任务tj的时空覆盖率计算如下：

为了保障每个任务的感知质量，当任务的时空覆盖率大于预设的最低时空覆盖率阈值且未产生过量冗余数据时，则该任务的覆盖效率较高，其原因由以下2 种情况说明：一是当任务的时空覆盖率未达到阈值时，说明其未获得足够的资源来保证感知质量；二是当任务的时空覆盖率超出阈值较多时，说明其获得过量的资源，造成过多的冗余数据，无法保障其他任务的感知质量。基于上述分析，根据任务tj的时空覆盖率及其阈值，可以定义任务覆盖效率如下：

根据式（5），所有任务的任务覆盖效率计算如下：

从工人的角度来看，在大规模任务分配场景下，多个任务之间对工人资源的竞争加剧，表现为以下2 种情况：一是任务无法获得足够的工人，导致任务无法完成；二是任务获得过多工人，导致工人资源浪费。根据上述分析和最大熵原理，本文定义工人利用效率，具体如下：

首先，与任务最低时空覆盖率阈值相关的任务执行次数分布定义为：

然后，工人利用效率被定义为任务完成次数分布的熵值，如式（8）所示，根据最大熵原理可知，当熵值越大时，任务执行次数分布越均衡，即工人利用效率越高。

当任务分配方案对应的上述2 种效率值越高，该任务分配方案在保障每个任务的感知质量方面越有效。因此，平台的系统效用定义为任务覆盖效率和工人利用效率之和，计算如下：

基于上述讨论，本文任务分配的目标是在预算受限的情况下最大化平台的系统效用：

其中：Ctj表示任务分配方案中任务tj获得一组工人来执行时需要花费的平台预算。式（10）的约束条件是任务分配方案中所有任务花费的平台预算之和小于平台总预算B。

3 任务分配

平台在预算受限情况下为每一个任务分配一组工人来保障其感知质量，同时减少平台的资源浪费。考虑到大规模任务分配是一个NP 难问题且计算复杂度较高，本文使用BSO 算法［23］来为平台寻找最优的任务分配方案，该算法在全局搜索能力和收敛速度方面优于传统的粒子群算法（Particle Swarm Optimization，PSO）［24］、遗传算法（Genetic Algorithm，GA）［25］以及蝗虫优化算法（Grasshopper Optimization Algorithm，GOA）［26］。此外，为丰富算法的种群多样性，在BSO 算法中融入GA 算法的交叉与变异操作。

3.1 BSO 算法基本原理

BSO 算法是一种具有强大全局搜索能力且收敛较快的群体智能算法，该算法结合PSO 算法和天牛须算法，将PSO 算法中的每一个粒子当作一只天牛来实现寻优过程。在寻优过程中，每一只天牛的位置主要根据天牛群的全局最优信息、天牛个体最优信息以及天牛自身左右须的探索信息这3 种因素进行更新。

为便于理解更新过程，定义相关参数如下：假设算法种群大小为g，则一组天牛的位置表示为X={X1,X2,…,Xg}，速度表示为V={V1,V2,…,Vg}。其中，天牛的位置表示待求解问题的可行解，通过更新天牛的位置向最优解寻优，直至算法收敛。此外，在寻优过程中，一组天牛的最优位置表示为Gbest，每只天牛的最优位置表示为Pbest={P1,best,P2,best,…,Pg,best}。更新过程的数学模型如下：

1）位置更新。在寻优过程中，每只天牛的位置根据其速度和运动步长进行更新，如下：

2）速度更新。天牛的速度根据天牛群的全局最优信息和天牛个体最优信息进行更新，如下：

其中：ω表示惯性权重因子，其决定算法的搜索能力，值越大则算法的全局搜索能力越强，值越小则算法的局部搜索能力越强，该值通常随迭代次数递增呈线性递减趋势；c1和c2分别表示天牛的个人学习因子和全局学习因子；r1和r2是随机扰动因子。

3）运动步长更新。天牛的运动步长根据天牛本身左右须的探索信息进行更新，其中，天牛左右须的探索信息计算如下：

天牛的运动步长更新如下：

3.2 融合交叉变异操作的BSO 算法

为寻找具有最大系统效用的任务分配方案，首先根据平台的预算生成一组可行解，将其作为初始天牛群的位置；然后通过BSO 算法的位置更新策略，对代表最优任务分配方案的天牛位置进行更新，在该过程中引入交叉变异操作。交叉和变异操作的过程描述如下：

1）在每一次迭代过程中选择部分天牛进行交叉操作，天牛的被选概率由轮盘赌选择法计算得出。每一只天牛的被选概率与天牛位置对应的适应度值正相关，计算为该位置的适应度值与所有天牛适应度值之和的比值，如下：

2）根据式（16）计算天牛被选概率，被选中天牛的位置将分别和全局最优位置Gbest以及个体最优位置Pbest进行交叉操作，以产生新的天牛位置，即将被选天牛的位置分别与Gbest和Pbest取并集，根据约束条件贪婪地去除新生成天牛位置中多余的系统效用与成本比值较小的工人任务对。在交叉操作完成后，针对新生成的天牛采用更优解保留策略，即将新生成天牛位置对应的适应度值与旧天牛位置对应的适应度值进行比较，若更优，则更新，否则不更新。

为增强算法的局部搜索能力，引入变异操作，即将天牛位置中的部分工人任务对依次变异为随机的工人任务对，并在变异过程中采用更优解保留策略。

3）根据更新后的天牛群重新生成Gbest和Pbest，并将更新后的天牛群作为子代天牛群，进行下一次迭代。

根据上述过程求解最优任务分配方案的算法流程如图2 所示，伪代码如算法1 所示。

图2 BSO 算法流程Fig.2 BSO algorithm procedure

算法1融合交叉变异操作的BSO 算法

4 实验分析

为了进一步验证所提模型保障每个任务感知质量的有效性以及算法性能，本文在MATLAB 中进行仿真实验，其中主要参数设置如表1 所示。此外，为避免随机性，实验结果均为多次重复实验结果的平均值。

表1 实验参数设置Table 1 Experimental parameters setting

4.1 评估指标

本文使用平台的系统效用来评估所提算法的性能，并结合单个任务的时空覆盖率来说明所提算法是否可以有效保障每个任务的感知质量。

平台的系统效用越高，说明任务分配方案的任务覆盖效率和工人利用效率越高。每个任务的时空覆盖率超过其最低时空覆盖率阈值且未产生过多的数据冗余，则表示该任务分配方案可以有效保障每个任务的感知质量。

4.2 对比算法

为验证所提算法在解决任务分配问题时的有效性，选取以下3 种基线方法进行对比实验：

1）PSO 算法。在更新过程中，PSO 算法只考虑粒子每次迭代中的全局最优信息和个体最优信息，以更新粒子的位置，将平台系统效用最大化作为目标来寻找最优解，该解即为平台的任务分配方案。

2）GA 算法。在更新过程中，GA 算法通过交叉和变异操作选择更优的父代染色体以产生子代染色体，以平台系统效用最大化为目标来寻找最优解，将其作为平台的任务分配方案。

3）MTasker［27］。MTasker是一种保证单个任务时空覆盖率满足最低阈值的多任务分配框架，其采用下降贪婪算法，在预算约束下以平台系统效用最大化为目标贪婪地去除多余的工人任务对，直到满足约束，从而获得平台的任务分配方案。

4.3 结果分析

考虑到任务数量、工人数量以及平台总预算的变化对系统效用的影响，本文采用定量分析法开展仿真实验，分析比较不同算法下系统效用的变化，然后结合单个任务的时空覆盖率证明所提算法可以有效保障每个任务的感知质量。此外，为验证所提算法的性能，本文固定任务数量、工人数量以及平台总预算后比较不同算法的收敛速度。

4.3.1 工人数量变化对系统效用的影响

本文固定任务数量和平台总预算分别为10 和100，研究工人数量对系统效用的影响。从图3 可以看出，随着工人数量的增加，不同算法下的系统效用都呈现递增的趋势，且逐渐趋于平缓，原因是当工人数量较小时，任务可竞争的工人资源较少，任务间竞争更激烈，此时系统效用值较小，随着工人数量的增加，任务间竞争变弱，系统效用值相应增大，由于平台预算受限，任务间的竞争对系统效用的影响越来越小，其递增趋势逐渐趋于平缓。此外，从图中可以看出，BSO 算法可以获得更高的系统效用值，较其他基线方法，其系统效用最大值平均提升11.9%，原因是PSO 算法在求解过程中只根据粒子的全局最优信息和个体最优信息进行位置更新，向最优解寻优，GA 算法则主要根据交叉变异操作进行位置更新，与这2 种智能算法不同，BSO 算法考虑天牛全局最优位置信息、个体最优位置信息以及天牛左右须的探索信息进行位置更新，并且融入交叉变异操作来增强算法的全局搜索能力，因此，BSO 算法在全局搜索能力方面优于PSO 算法和GA 算法。由于MTasker框架采用下降贪婪算法来寻找最优任务分配方案，在任务规模较大时，其易陷入局部最优解，因此MTasker 的系统效用较低。

图3 工人数量对系统效用的影响Fig.3 Impact of the number of workers on the system utility

本文结合单个任务的时空覆盖率说明所提算法可以有效保障每个任务的感知质量。图4 显示工人数量和平台总预算分别为1 000 和100 时10 个任务的时空覆盖率。从图4 可以看出，每个任务的时空覆盖率都高于其最低时空覆盖率阈值，原因是平台的资源可以支持所有任务都获得足够的数据。此外，考虑到感知质量子模性，从图4 可以看出，相较其他基线方法获得的单个任务时空覆盖率，BSO 算法可以更有效地保障每个任务的感知质量，原因是与最低时空覆盖率阈值相比，BSO 算法获得的任务分配方案中每个任务的时空覆盖率更均衡。均衡是指每个任务的时空覆盖率与最低时空覆盖率阈值相比，其偏离程度更小，可以用方差表示，该方差的计算方法是先累加每个任务的时空覆盖率和其最低时空覆盖率阈值间差值的平方，再除以任务的数量。

图4 固定任务数量和平台总预算情况下的任务时空覆盖率Fig.4 Task temporal-spatial coverage with fixed number of tasks and total budget of the platform

表2 展示工人数量在1 000～6 000 范围内时4 种算法获得的时空覆盖率方差。从中可以看出，相较其他方法，BSO 算法获得的任务时空覆盖率方差最小，说明该算法获得的任务分配方案可以有效保障每个任务的感知质量，即不存在任务的时空覆盖率超过其最低时空覆盖率阈值过多或过少的情况。BSO 算法具有更强的全局搜索能力，获得了更高的系统效用，系统效用值越高，其获得的任务分配方案在保障单任务质量方面更有效，每个任务的时空覆盖率相较其最低时空覆盖率阈值的偏离程度更小。此外，随着工人数量的增加，任务时空覆盖率方差逐渐变大，这是因为工人数量的增加会降低任务之间的竞争，在预算有限的情况下，每个任务的时空覆盖率会增加。同时，由于平台预算受限，其方差增长趋势也逐渐变小。

表2 固定任务数量和平台总预算情况下的任务时空覆盖率方差Table 2 Variance value of task temporal-spatial coverage with fixed number of tasks and total budget of the platform

4.3.2 任务数量变化对系统效用的影响

本文固定工人数量和平台总预算分别为6 000和100，研究任务数量对系统效用的影响。如图5 所示，随着任务数量的增加，不同算法下的系统效用都呈现递增的趋势，根据前文内容分析可知，平台的系统效用和任务数量成正相关。随着任务数量的增加，任务覆盖效率和工人利用效率提高，系统效用提升。此外，从图5 可以看出，BSO 算法可以获得更高的系统效用，较其他基线方法，其系统效用最大值平均提升13.9%，这是因为BSO 算法在全局搜索能力方面优于PSO算法、GA算法和MTasker框架。

图5 任务数量对系统效用的影响Fig.5 Impact of the number of tasks on the system utility

图6 显示工人数量和平台总预算分别为6 000和100 时10 个任务的时空覆盖率。从图6 可以看出，相较最低时空覆盖率阈值，BSO 算法获得的任务时空覆盖率更均衡，原因是BSO 算法相较其他基线方法可以获得更高的系统效用，保障了每个任务的感知质量。

图6 固定工人数量和平台总预算情况下的任务时空覆盖率Fig.6 Task temporal-spatial coverage with fixed number of workers and total budget of the platform

表3 展示任务数量在10～35 范围内时4 种算法获得的时空覆盖率方差。从中可以看出，相较其他基线方法，BSO 算法获得的任务时空覆盖率方差最小，原因是其获得了更高的系统效用，降低了每个任务时空覆盖率相较最低时空覆盖率阈值的偏离程度。此外，随着任务数量的增加，任务时空覆盖率方差由增加状态转为递减状态，这是因为平台的预算有限，当任务数量达到一定值时，任务之间的资源竞争将导致每个任务获得的时空覆盖率降低，而任务最低时空覆盖率阈值不变，因此，任务时空覆盖率方差减小。

表3 固定工人数量和平台总预算情况下的任务时空覆盖率方差Table 3 Variance value of task temporal-spatial coverage with fixed number of workers and total budget of the platform

4.3.3 平台总预算变化对系统效用的影响

本文固定工人数量和任务数量分别为1 000 和10，研究平台总预算对系统效用的影响。如图7 所示，随着平台总预算的增加，不同算法下的系统效用都呈现递增趋势，原因是随着平台总预算的增加，雇佣的工人数量增多，任务的时空覆盖率增大。根据前文内容分析可知，任务覆盖效率与任务的整体时空覆盖率呈正相关，即平台总预算带来的任务时空覆盖率增大会导致系统效用值增大。此外，由于BSO 算法具有更强的全局寻优能力，因此在相同情况下该算法可以获得更高的系统效用，较对比方法，其系统效用最大值平均提升14.7%。

图7 平台总预算对系统效用的影响Fig.7 Impact of the total budget of platform on the system utility

图8 显示工人数量和任务数量分别为1 000 和10 时每个任务的时空覆盖率。从图8 可以看出，相较最低时空覆盖率阈值，BSO 算法获得的任务分配方案中每个任务的时空覆盖率更均衡，原因是其获得了更高的系统效用。

图8 固定工人和任务数量情况下的任务时空覆盖率Fig.8 Task temporal-spatial coverage with fixed number of workers and tasks

表4 展示平台总预算在100～150 范围内时4 种算法获得的时空覆盖率方差。从中可以看出，BSO算法所获得的任务分配方案具有更低的任务时空覆盖率方差，原因是其获得了更高的系统效用。另外，随着平台总预算的增加，任务时空覆盖率方差持续增长，原因是平台总预算增大使得平台可以雇佣更多的工人，从而提高任务的时空覆盖率。值得注意的是，随着平台总预算的增加，方差最终会收敛，这是因为平台的工人和任务是有限的，当所有工人都被雇佣或任务的时空覆盖率达到1 时，方差最终会收敛到某一固定值。

表4 固定工人和任务数量情况下的任务时空覆盖率方差Table 4 Variance value of task temporal-spatial coverage with fixed number of workers and tasks

4.3.4 算法寻优曲线对比

本文固定工人数量和任务数量分别为6 000 和35，研究不同算法在最大化系统效用方面的寻优效率。如图9 所示，随着迭代次数的增加，平台的系统效用逐渐增加直至收敛，原因是这3 种算法的初始随机解并不是最优任务分配方案，其系统效用值不高，随着迭代次数的增加，这3 种算法生成的初始随机解将会根据其各自的寻优策略向最优解迭代更新，直至系统效用值收敛。此外，从图9 可以看出，由于BSO 算法具有更强的全局搜索能力，因此其获得的系统效用优于PSO 算法和GA 算法。同时，在寻优速度方面，BSO 算法较对比算法平均提升了40.61%。

图9 3 种算法的迭代曲线对比Fig.9 Iteration curves comparison of three algorithms

5 结束语

在大规模任务分配场景下，现有任务分配方法大多难以保障每个任务的感知质量。针对该问题，本文提出一种面向单任务质量保障的多任务分配方法。分析工人和任务的相关属性，设计一种合理的激励机制，同时，考虑到任务之间对工人、预算等资源的激烈竞争，分别从任务和工人的角度设计任务覆盖效率和工人利用效率这2 种衡量指标，将这2 种指标相结合作为平台的系统效用，用以评估不同任务分配方案的性能优劣。为获取具有最大系统效用的任务分配方案，提出一种融合交叉和变异操作的BSO 算法。仿真结果表明，该算法的系统效用最大值较对比方法平均提升13.51%，并且具有更快的寻优速度，能有效保障每个任务的感知质量，解决具有不同任务需求的大规模任务分配问题。下一步将探索并挖掘更多影响感知质量的因素，研究在线场景下的感知质量优化问题，分析动态任务和动态工人的时序性，并采用更高效的智能算法来优化系统平台的任务分配过程。