开放科学（资源服务）标志码（OSID）：

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平台，平台将任务信息发送给工人；然后，工人根据平台的任务信息和激励政策决定是否参与感知活动，如果决定参与感知活动，则需要上传自身信息至平台；之后，平台根据工人信息表（包含工人位置信息、设备感知能力等）与任务，产生最优任务分配方案，并根据该方案进行任务分配；最后，工人完成平台分配的任务，将感知数据上传至平台并获得相应的报酬，平台融合所有感知数据后将结果反馈给任务请求方。

为清晰展示任务分配的流程，将系统模型的相关参数定义如下：平台拥有一个总预算（表示为B）、一个包含r个工人的工人集$ \left(\mathrm{表}\mathrm{示}\mathrm{为}\boldsymbol{W}=\{{w}_{1}, {w}_{2}, \cdots ，\right. $ $ \left.{w}_{i}, \cdots , {w}_{r}\}\right) $以及一个包含f个任务的任务集$ \left(\mathrm{表}\mathrm{示}\mathrm{为}\right. $ $ \left.\boldsymbol{T}=\{{t}_{1}, {t}_{2}, \cdots ，{t}_{j}, \cdots , {t}_{f}\}\right) $。考虑到任务的时空特征以及工人的感知范围有限，平台将每个任务的感知区域划分为多个子区域，同时基于任务需求将感知周期划分为多个子周期。相应地，平台上f个任务的感知区域构成集合$ {\boldsymbol{R}}_{{e}}=\{{R}_{{e}_{1}}, {R}_{{e}_{2}}, \cdots , {R}_{{e}_{j}}, \cdots , {R}_{{e}_{f}}\} $，其中包含m个感知子区域的第j个任务感知区域$ \left(\mathrm{表}\mathrm{示}\mathrm{为}\right. $$ {R}_{{e}_{j}}=\left.\{{r}_{{e}_{j, 1}}, {r}_{{e}_{j, 2}}, \cdots , {r}_{{e}_{j, m}}\}\right) $；f个任务的感知周期构成集合$ {\boldsymbol{C}}_{{y}}=\{{C}_{{y}_{1}, }{C}_{{y}_{2}}, \cdots , {C}_{{y}_{j}}, \cdots , {C}_{{y}_{f}}\} $，其中包含n个感知子周期的第j个任务感知周期$ \left(\mathrm{表}\mathrm{示}\mathrm{为}{C}_{{y}_{j}}=\{{c}_{{y}_{j, 1}}, {c}_{{y}_{j, 2}}, \cdots , {c}_{{y}_{j, n}}\}\right) $。然后，根据任务感知区域和感知周期划分，任务可以被划分为一组时空单元，其中每一个时空单元由一个感知子周期和一个感知子区域组成，需要一个工人来执行该时空单元的任务。之后，根据任务和设备的特性，工人执行任务的能力和任务被执行的需求分别被抽象为工人携带设备拥有的传感器和执行任务需要的传感器。假设和工人执行任务过程相关的传感器一共包含l类，那么工人携带的设备被抽象化为一组二元值，其中，第i个工人的传感器组表示为$ {\boldsymbol{S}}_{{{W}}_{{i}}}=\{{s}_{{w}_{i, 1}}, {s}_{{w}_{i, 2}}, \cdots , {s}_{{w}_{i, k}}, \cdots , {s}_{{w}_{i, l}}\} $。如果工人携带的设备上存在第k类传感器，则$ {s}_{{w}_{i, k}}=1 $，否则为0；任务执行的需求也被抽象化为一组二元值，其中，第j个任务的传感器组表示为$ {\boldsymbol{S}}_{{{T}}_{{j}}}=\{{s}_{{t}_{j, 1}}, {s}_{{t}_{j, 2}}, \cdots , $ $ {s}_{{t}_{j, k}}, \cdots , {s}_{{t}_{j, l}}\} $，如果任务需要第k类传感器，则$ {s}_{{t}_{j, k}}=1 $，否则为0。

2 问题分析

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

2.1 激励成本设计

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

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

$ \begin{array}{c}\mathrm{Exe}{\mathrm{c}}_{\mathrm{C}\mathrm{o}\mathrm{s}\mathrm{t}}\left({w}_{i}, {t}_{j}\right)=\sum\limits _{k=1}^{l}{s}_{{t}_{j, k}}\cdot {\mathrm{cost}}_{k}\end{array} $

(1)

其中：$ \mathrm{c}\mathrm{o}\mathrm{s}{\mathrm{t}}_{k} $表示第k类传感器被使用时平台需要支付的报酬，其为一个与传感器类型相关的定值。

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

$ \begin{array}{c}{\mathrm{Comp}}_{\mathrm{C}\mathrm{o}\mathrm{s}\mathrm{t}}\left({w}_{i}, {t}_{j}\right)=P{C}_{{w}_{i}}^{{r}_{{e}_{j, m}}, {c}_{{y}_{j, n}}}+\alpha \cdot \sum\limits _{k=1}^{l}\left({s}_{{t}_{{j}^{\text{'}}, k}}-{s}_{{t}_{j, k}}\right)\end{array} $

(2)

其中$ ：P{C}_{{w}_{i}}^{{r}_{{e}_{j, m}}, {c}_{{y}_{j, n}}} $代表工人$ {w}_{i} $所在时空单元$ ({r}_{{e}_{j, m}}, {c}_{{y}_{j, n}}) $的参与补偿；$ \alpha $表示设备成本补偿系数；$ {s}_{{t}_{{j}^{\text{'}}, k}} $表示工人$ {w}_{i} $能够完成的获得最大利益的任务$ {t}_{{j}^{\text{'}}} $所需要的第k类传感器；$ {s}_{{t}_{j, k}} $表示平台需要工人$ {w}_{i} $完成的任务$ {t}_{j} $所需要的第k类传感器。

基于上述定义，工人$ {w}_{i} $执行任务$ {t}_{j} $的激励成本定义为执行成本与执行补偿之和，计算如下：

$ \begin{array}{c}{C}_{{w}_{i}, {t}_{j}}={\mathrm{Exec}}_{\mathrm{C}\mathrm{o}\mathrm{s}\mathrm{t}}\left({w}_{i}, {t}_{j}\right)+{\mathrm{Comp}}_{\mathrm{C}\mathrm{o}\mathrm{s}\mathrm{t}}\left({w}_{i}, {t}_{j}\right)\end{array} $

(3)

2.2 系统效用设计

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

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

$ \begin{array}{c}{\mathrm{Covered}}_{{t}_{j}}=\frac{\sum\limits _{{w}_{i}\in W}{w}_{i\left({t}_{j}\right)}^{{r}_{{e}_{j, m}}, {c}_{{y}_{j, n}}}}{m\times n}\end{array} $

(4)

其中$ ：{w}_{i\left({t}_{j}\right)}^{{r}_{{e}_{j, m}}, {c}_{{y}_{j, n}}} $是一个二元值，表示工人$ {w}_{i} $是否可以覆盖任务$ {t}_{j} $的时空单元$ ({r}_{{e}_{j, m}}, {c}_{{y}_{j, n}}) $，若可以，则其值为1，否则为0。

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

$ {\varphi }_{{t}_{j}}=\left\{\begin{array}{ll}(1-{\gamma }_{{t}_{j}})\cdot {\varphi }_{\mathrm{m}\mathrm{a}\mathrm{x}}, {\gamma }_{{t}_{j}}\ge 0& \\ {\gamma }_{{t}_{j}}\cdot {\varphi }_{\mathrm{m}\mathrm{a}\mathrm{x}}, {\gamma }_{{t}_{j}} < 0& \end{array}\right. $

(5)

其中：$ {\gamma }_{{t}_{j}}=\frac{\mathrm{C}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{e}{\mathrm{d}}_{{t}_{j}}-\mathrm{Q}\mathrm{T}\left({t}_{j}\right)}{\mathrm{Q}\mathrm{T}\left({t}_{j}\right)} $是任务覆盖效率系数；$ \mathrm{Q}\mathrm{T}\left({t}_{j}\right) $表示任务$ {t}_{j} $的最低时空覆盖率阈值；$ {\varphi }_{\mathrm{m}\mathrm{a}\mathrm{x}} $表示任务的最佳时空覆盖效率，其为一个定值。

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

$ \begin{array}{c}\varphi =\sum\limits _{{t}_{j}\in T}{\varphi }_{{t}_{j}}\end{array} $

(6)

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

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

$ \begin{array}{c}P\left\{X={t}_{j}\right\}=\frac{{\beta }_{j}\cdot \mathrm{A}\mathrm{c}{\mathrm{h}}_{\mathrm{N}\mathrm{u}\mathrm{m}}^{{t}_{j}}}{\sum\limits _{j=1}^{f}{\beta }_{j}\cdot \mathrm{A}\mathrm{c}{\mathrm{h}}_{\mathrm{N}\mathrm{u}\mathrm{m}}^{{t}_{j}}}\end{array} $

(7)

其中：$ \mathrm{A}\mathrm{c}{\mathrm{h}}_{\mathrm{N}\mathrm{u}\mathrm{m}}^{{t}_{j}} $表示任务$ {t}_{j} $的被执行次数；$ {\beta }_{j}=\frac{\mathrm{Q}\mathrm{T}\left({t}_{j}\right)}{\sum\limits _{j=1}^{f}\mathrm{Q}\mathrm{T}\left({t}_{j}\right)} $表示任务$ {t}_{j} $的被执行次数权重。

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

$ \begin{array}{c}H=-\sum\limits _{j=1}^{f}P\left({t}_{j}\right)\cdot \lg P\left({t}_{j}\right)\end{array} $

(8)

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

$ \begin{array}{c}Q=\varphi +H\end{array} $

(9)

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

$ \begin{array}{ll}\mathrm{m}\mathrm{a}\mathrm{x}\;\;Q& \\ \mathrm{s}.\mathrm{t}.\;\;\;\;\sum\limits _{{t}_{j}\in \boldsymbol{T}}{C}_{{t}_{j}} < B& \end{array} $

(10)

其中：$ {C}_{{t}_{j}} $表示任务分配方案中任务$ {t}_{j} $获得一组工人来执行时需要花费的平台预算。式（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，则一组天牛的位置表示为$ \boldsymbol{X}=\{{X}_{1}, {X}_{2}, \cdots , {X}_{g}\} $，速度表示为$ \boldsymbol{V}=\left\{{V}_{1}, {V}_{2}, \cdots , {V}_{g}\right\} $。其中，天牛的位置表示待求解问题的可行解，通过更新天牛的位置向最优解寻优，直至算法收敛。此外，在寻优过程中，一组天牛的最优位置表示为$ {G}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $，每只天牛的最优位置表示为$ {P}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}=\left\{{P}_{1, \mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}, {P}_{2, \mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}, \cdots , {P}_{g, \mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}\right\} $。更新过程的数学模型如下：

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

$ \begin{array}{c}{X}_{g}^{K+1}={X}_{g}^{K}+\lambda {V}_{g}^{K+1}+\left(1-\lambda \right){\xi }_{g}^{K+1}\end{array} $

(11)

其中：$ {X}_{g}^{K+1} $、$ {V}_{g}^{K+1} $和$ {\xi }_{g}^{K+1} $表示第g只天牛在第K+1次迭代时的位置、速度和运动步长；K表示迭代次数；$ \lambda $表示权重因子。

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

$ \begin{array}{c}{V}_{g}^{K+1}=\omega {V}_{g}^{K}+{c}_{1}{r}_{1}\left({P}_{g, \mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{K}-{X}_{g}^{K}\right)+{c}_{2}{r}_{2}\left({G}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{K}-{X}_{g}^{K}\right)\end{array} $

(12)

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

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

$ \begin{array}{c}X{l}_{g}^{K+1}={X}_{g}^{K}-d\cdot {V}_{g}^{K}\end{array} $

(13)

$ \begin{array}{c}X{r}_{g}^{K+1}={X}_{g}^{K}+d\cdot {V}_{g}^{K}\end{array} $

(14)

其中：$ X{l}_{g}^{K+1} $、$ X{r}_{g}^{K+1} $分别表示第g只天牛在第K+1次迭代时左右须的位置；d表示天牛左右须触角之间的距离。

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

$ \begin{array}{c}{\xi }_{g}^{K+1}={\delta }^{K}\cdot {V}_{g}^{K}\cdot \text{sign}\left(f\left(X{l}_{g}^{K+1}\right)-f\left(X{r}_{g}^{K+1}\right)\right)\end{array} $

(15)

其中：$ {\xi }_{g}^{K+1} $表示第g只天牛在第K+1次迭代后的步长；$ f\left(·\right) $表示适应度值计算函数；$ \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left(·\right) $表示符号函数，若$ f\left(X{l}_{g}^{K+1}\right) > f\left(X{r}_{g}^{K+1}\right) $，该值取1，否则为$ - $1；$ {\delta }^{K} $表示天牛的步长因子。

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

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

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

$ \begin{array}{c}P\left({X}_{g}\right)=\frac{f\left({X}_{g}\right)}{\sum\limits _{{X}_{g}\in X}f\left({X}_{g}\right)}\end{array} $

(16)

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

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

3）根据更新后的天牛群重新生成$ {G}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $和$ {P}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $，并将更新后的天牛群作为子代天牛群，进行下一次迭代。

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

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

输入   工人集W，任务集T，总预算B，最大迭代次数K_max，种群大小Size

输出   全局最优位置G_best对应的最优任务分配方案

1.for t_j$ \in $T //对所有任务

2.计算可行的工人任务对，生成解空间

3.end for

4.初始化算法参数：天牛位置X、速度V以及左右须距离d；惯性权重因子$ {\rm{ \mathsf{ ω} }}$；权重因子$ {\rm{ \mathsf{ λ} }}$；个人学习因子$ {\mathrm{c}}_{1} $；全局学习因子$ {\mathrm{c}}_{2} $

5.计算适应度值以更新$ {\mathrm{G}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $和$ {\mathrm{P}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $

6.for K = 1：K_max

7.根据式（12）计算天牛的移动速度

8.根据式（13）和式（14）更新天牛左右须的位置信息

9.根据式（15）计算天牛的运动步长

10.根据式（11）更新天牛位置

11.更新天牛左右须距离d和惯性权重因子$ {\rm{ \mathsf{ ω} }} $

12.概率选择更新后的天牛与$ {\mathrm{G}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $和$ {\mathrm{P}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $进行交叉操作

13.采用更优解保留策略生成新的天牛个体

14.随机选择天牛进行变异操作

15.采用更优解保留策略生成新的天牛个体

16.for g = 1：Size

17.计算第g只天牛的适应度值

18.if $ \mathrm{f}\left({\mathrm{X}}_{\mathrm{g}}^{\mathrm{K}+1}\right) > \mathrm{f}\left({\mathrm{P}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}\right) $ then

19.更新$ {\mathrm{P}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $

20.end if

21.if $ \mathrm{f}\left({\mathrm{X}}_{\mathrm{g}}^{\mathrm{K}+1}\right) > \mathrm{f}\left({\mathrm{G}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}\right) $ then

22.更新$ {\mathrm{G}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $

23.end if

24.end for

25.end for

4 实验分析

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

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的系统效用较低。

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

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

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

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

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

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

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

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

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

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

4.3.4 算法寻优曲线对比

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

5 结束语

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