面向依赖关系约束的移动群智感知任务协作

杨桂松 白高磊 何杏宇 贾明权

摘 要：现有移动群智感知中，大多研究将每个任务作为独立个体进行处理，对任务间约束关系缺乏研究，为此，提出了基于感知质量优先级的在线任务协作方法（online task collaboration method based on sensing quality priority，TCSP）。该方法首先使用贪婪算法计算感知质量优先级，对全部任务进行筛选以保证任务完成率；然后将选出任务中存在时间先后或执行逻辑前后关系的多个子任务构建为任务协作图，并将其协作过程建模为有约束的马尔可夫决策过程，通过强化学习算法求出最优协作策略。实验结果表明，与现有基线方法相比，所提出的任务协作方法能够减少依赖任务的平均完成时间，有效降低平台的平均感知成本。

关键词：移动群智感知； 依赖关系； 感知质量优先级； 在线任务协作； 强化学习

中图分类号：TP393   文献标志码：A

文章编号：1001-3695（2023）09-009-0000-00

doi：10.19734/j.issn.1001-3695.2023.02.0048

Dependency constraint oriented task collaboration in mobile crowd sensing

Yang Guisong1a， Bai Gaolei1a， He Xingyu1a，1b， Jia Mingquan2

（1.a.School of Optical-Electrical & Computer Engineering， b.College of Communication & Art Design， University of Shanghai for Science & Technology， Shanghai 200093， China; 2.Southwest China Institute of Electronic Technology， Chengdu 610036， China）

Abstract：In the existing mobile crowd sensing， most studies treat each task as an independent individual， and lack of research on the constraint relationship between tasks. In view of this， this paper proposed an online task collaboration method based on sensing quality priority （TCSP）. Firstly， this method used greedy algorithm to calculate the sensing quality priority， screened all tasks to ensure the task completion rate. Then it constructed a task cooperation graph for multiple subtasks that had time sequence or execution logic relationship in the selected tasks and modelled cooperation process as a constrained Markov decision process， obtained the optimal cooperation strategy through reinforcement learning algorithm. Experimental results verify that compared with the existing baseline methods， the proposed TCSP method can reduce the average completion time of dependent tasks and reduce the average sensing cost of the platform.

Key words：mobile crowd sensing; dependency; sensing quality priority; online task collaboration; reinforcement learning

0 引言

移動群智感知（mobile crowd sensing，MCS）［1］是一种利用大量移动终端随时随地进行感知活动的重要感知范式，已经广泛应用于不同领域，如环境质量监测［2］、交通管理［3］、健康信息搜集［4］、智慧城市监控［5］等。MCS通常由任务请求者、MCS平台和移动工人三个部分组成。具体来说，任务请求者通过MCS平台发布感知需求，MCS平台根据算法将任务分配给合适的工人，工人将感知任务结果提交给平台并得到相应的报酬。在这个过程中，平台需要通过汇聚大量的工人信息和任务信息进行任务与工人之间的匹配以完成感知活动，因此在满足任务约束（时空需求、任务预算）和工人约束（时空特性，感知能力）的条件下，将任务分配给合适的工人是一个关键问题。平台的任务分配能力不仅影响任务的完成速度和成本，而且对于实效性要求较高的任务（城市环境变化情况的持续监测，实时交通情况预测）而言，其直接决定了感知任务是否能够被有效完成。

根据MCS中任务分配时效性的不同可以分为离线任务分配和在线任务分配。对于离线任务分配而言，平台具有全部的工人和感知任务信息，在任务开始执行前就做好所有分配的决策，所有工人根据这个决策来执行。例如工人、任务信息都已知的条件下，文献［6］设计了一种讨价还价的定价机制为所有任务分配工人；文献［7］提出了一种参与者选择框架，最大化地完成任务总数；文献［8］是在成本约束的条件下选择参与者子集，最大化任务满意度。对于在线任务分配而言，平台只具有当前已经到达的任务和参与者的信息，MCS平台需要根据当前的任务和工人情况进行任务分配。例如，文献［9］将在线任务分配视为多轮虚拟离线任务分配，假设某段时间内任务和工人情况不发生改变，解决移动社交网络中人群感知的制造跨度敏感问题；文献［10］提出了一个概率模型来衡量任务的质量，进而可以实时为当前工人分配适当的任务；文献［11～13］通过研究机会传输、时间和空间相关性设计在线任务分配方法，提升平台执行效能。离线任务分配掌握着更多的信息，可以获得更好的性能，但时效性不强；在线方案可以实时作出决策，更加灵活，适合动态实时场景，但是由于在线任务分配缺乏全局信息，很可能导致任务分配失败，这就需要通过有效的方法确保在线任务完成率。

由于工人移动带来的不确定和不可控性，感知质量的优劣是在线任务能否有效完成的关键。文献［14］通过引入特定于任务的最小传感质量阈值重新定义问题，以保证单个任务感知质量的多任务分配；文献［15］利用参与者积累的声誉和意愿来构建服务质量模型，在最大化服務质量的基础上选择最合适的一组参与者，尽可能提高平台的最终收入和参与者的利益；文献［16］定义了一种新的质量覆盖率度量，考虑了传感器读数覆盖的子区域的比例以及每个覆盖子区域中传感数据的质量，以实现基于位置的多样化MCS任务。对于实效性较强的任务，感知质量的好坏是影响任务能否完成的关键环节，因此如何评估感知质量来保证在线任务完成率是一大挑战。

值得注意的是，现有任务分配研究中，无论是针对单任务还是多任务的分配方法，大多将每个任务视为一个相互独立的整体，然而随着移动群智感知中任务数量和复杂程度的增加，任务不再独立，多个任务之间存在相互依存的关系［17，18］。在单任务分配研究中，每个任务根据参与者的特点，在满足特定约束的条件下独立地进行分配。文献［19］提出成本公平任务分配算法，将传感任务分配给不同用户，以便所有用户承担的传感成本尽可能平衡，同时可以满足请求者对数据可靠性的要求；文献［20］考虑参与者的异质性导致传感数据可靠性差的问题，提出优化算法以最大限度地提高完成任务的数量。在多任务分配研究中，虽然对任务间的移动关系、需求差异等有所考虑，但每个任务执行过程中仍然是相互独立地进行分配。例如，文献［21］将现有任务序列与用户的移动规律性尽可能地保持一致，基于移动性重复模式发现过程将原有的任务分配问题转换为模式匹配问题；文献［22］根据参与者的任务难度、任务历史、感知能力和感知积极性对参与者的服务效益进行建模，以满足不同任务类型的差异化需求。

现有的多任务分配方法中，每个任务作为独立个体，不能对任务间的约束关系进行有效处理，提升MCS平台对任务间的时间先后或执行逻辑前后等约束关系的处理能力是处理具有依赖关系任务的关键。流式任务的调度和分配问题的研究是分析和处理这种任务间依赖关系的重要途径［23］，例如对于城市环境变化情况持续监测任务，如果要知道当前环境情况，不仅需要获得当前时刻任务的感知数据（温度数据、湿度数据、风速数据等），而且还需要上一时刻任务对历史数据的计算结果，才能对当前任务作出有效预测或计算。因此，针对有时间先后或执行逻辑前后依赖关系约束的任务，如何设计有效的任务协作机制以提升平台的在线任务处理能力是另一个挑战。

一方面，时空覆盖率和数据质量是影响感知任务能否完成的关键因素，时空覆盖率越高参与执行任务的工人越多，数据质量越高参与的工人能力越能满足任务需要。因此在特定时空范围内，对当前平台中不同任务的感知质量（时空覆盖率和数据质量）进行评估并优先执行感知质量最高的任务，可以保证多个子任务执行的有效性、及时性和平台任务完成率等。另一方面，对具有时间先后或执行逻辑前后依赖关系约束的子任务建立有效的任务协作模型是平台能够进行实时计算或预测分析的关键。图结构可以有效地表示这种依赖关系，子任务表示为节点，子任务间的依赖关系表示为边，可以将根据子任务间的依赖关系为每个子任务选择最合适的工人的过程映射为有约束的马尔可夫决策过程，最终通过强化学习方法学习可以得到最优协作策略。

综上所述，针对挑战本文提出了基于感知质量优先级的在线任务协作方法（TCSP）。主要贡献如下：a）使用贪婪算法计算感知质量优先级，对全部任务进行筛选以保证任务完成率，同时也将原问题分解成为多个子问题，减小了任务协作模型的可行域，提高了模型的收敛速度；b）将有时间先后或执行逻辑前后关系的子任务构建为任务协作图，然后将此任务协作过程建模为有约束的马尔可夫决策过程，并通过Q学习算法得到最优协作策略。

1 系统模型

本文考虑一个实际场景，该场景中包括一个平台，多个任务请求方以及多个工人，其中每个任务包含有多个具有依赖关系的子任务，平台可以获取特定时空范围内工人和现有任务的信息。在这种条件下，平台计算出当前时空区域内每个任务与工人的感知质量，并选出感知质量最高的任务作为当前待执行任务。在任务执行过程中，平台根据上一个子任务分配工人后的状态来确定下一个子任务的工人分配策略。任务执行过程如图1所示，a）MCS平台处于等待状态，当有任务发布者把任务需求发送至平台时将唤醒平台进行任务处理；b）平台根据任务信息和激励政策向特定时空区域发送招募需求，收到信息的工人根据招募信息决定是否参与感知活动，如果参与感知活动就上传自身感知能力和位置等工人信息至平台；c）平台先根据工人的感知能力和任务需求计算出当前感知质量最高的任务，然后根据子任务间的依赖关系、子任务执行时产生的激励成本和时间成本为每个子任务选择最合适的工人，循环执行此步骤直到所有子任务协作完成整个任务。工人将感知结果上传至平台并获得相应的报酬，平台持续检查是否还有任务等待执行，如果有就重复此过程，如果没有就进入等待状态。

本文将时空区域定义为由d个子单元组成的感知地图M，集合表示为M={m1，m2，…，mi，…，md}，第i个地图子单元表示为mi（1≤i≤d）。此时空范围内有c个工人参与感知活动，集合表示为W={w1 ，w2，…，wj，…，wc}，第j个工人表示为wj（1≤j≤c）。

工人的感知特性包括感知范围和感知能力两个方面，工人wj的感知范围表示工人在此时空区域内可以感知到的地图子单元，集合表示为Rwj={r1，…，r（k，R（wj）），…，rn}，工人wj第k个感知单元为r（k，R（wj）），1≤k≤n。工人感知能力的大小由感知设备特性决定，如设备计算能力、传感器感知能力、网络传输能力等因素，工人wj感知能力向量表示为P（wj）=|p1，p2…，p（l，P（wj）），…，pf|，工人第l维感知能力为p（l，P（wj）），1≤l≤f，其数值大小表示工人某一方面的能力情况。

在感知时空范围内MCS平台收到多个发布者的任务请求，集合表示为TS={T1，T2，…，To，…，Tb}，其中第o个任务为To（1≤o≤b），其由g个前后依赖关系的子任务组成，集合表示为，To={t1，t2，…，t（u，T0），…，tg}，1≤u≤g，t（u，T0）表示To任務的第u个子任务。子任务的感知需求包括感知范围需求和感知量需求，子任务t（u，To）执行需求感知范围集合表示为，E（tu，To）={e1，e2，…，e（v，t（u，To）），…，eh}，其中，第v个子任务的需求地图子单元为e（v，t（u，To））（1≤v≤h）。子任务t（u，To）感知量需求向量为QTotu=|q1，q2…，q（x，t（u，To）），…，pf|，其中q（x，t（u，To））为子任务第x维感知质量需求。

为了更清晰地说明多个子任务之间的约束关系，将任务To的所有子任务之间的关系用有向无环图表示。如图2所示，给出了子任务数量分别为4、6、10个且子任务间依赖关系为图2中的类型1～3的任务模型。其中，以类型2为例，假设任务To由6个子任务t1～t6组成，节点表示子任务，边表示子任务之间的时间先后或执行逻辑前后关系，所有顶点构成集合VTo，有向边构成集合ETo。如果某个子任务节点具有多个前驱节点，那么只有所有前驱节点执行完后这个子任务节点才能执行。例如图2中类型2，t6的依赖关系为边（t3，t6）、（t4，t6）、（t5，t6），只有当t3、t4、t5任务执行完t6后才可以执行。

2 任务感知质量优先级

为了提高任务的有效性和及时性，保证平台任务的完成率，要对当前平台中任务的感知质量进行评估。本文设计了融合贪婪算法的感知质量优先级任务调度模型，分别从时空覆盖率和数据质量两个方面对每个任务的感知质量进行分析，以有效地评估感知质量优劣、提升在线任务的完成率。前者关注的是是否有足够的工人执行任务，后者关注的是工人能力是否满足任务执行的需要，如计算能力、传感器感知能力等。

2.1 时空覆盖率

对于某个任务而言，每个子任务需要的地图子单元与工人的感知范围是否重合决定了此子单元的覆盖情况。基于此，任务的时空覆盖率计算可以用其每个子任务的地图子单元是否有工人覆盖作为计数依据。

对于任务To的任意子任务t（u，To），其工人覆盖情况用二元变量H（e（v，t（u，To）），r（k，R（wj）））表示，当值为1时表示子任务t（u，To）的感知需求地图子单元可以被工人wj感知子单元r（k，R（wj））覆盖到，为0则表示未被覆盖。其中，H（·）为对比函数，两变量相同时值为1，不同时值为0。在当前时空范围内，子任务t（u，To）的需求地图子单元被工人wj覆盖到的数量计算如下：

MATt（u，To）（wj）=∑hv=1∑nk=1H（e（v，t（u，To）），r（k，R（wj）））（1）

任务TO的所有子任务可以被当前时空范围内的工人覆盖的数量计算如下：

FCTo=∑gu=1∑cj=1MATt（u，To）（wj）（2）

子任务t（u，To）的地图子单元的需求数量union（Et（u，To））表示任务需求地图中不同子单元的数量。其中union（·）为集合计数函数，累加不同子单元的个数。因此，任务To的所有子任务感知地图子单元总数量计算如下：

QTo=∑gu=1union（Et（u，To））（3）

对于任务To，时空覆盖率定义为感知范围内所有工人可以覆盖此任务的地图子单元的数量与任务执行需要的所有地图子单元数量的比值，计算如下：

coverTo=FCToQTo（4）

2.2 数据质量

空间中向量之间的距离是两个向量相似程度的反映，因此任务的感知质量需求与工人感知能力之间的相似程度采用欧氏距离来度量。对于每个子任务t（u，To）的感知内容需求向量QTotu与工人wj的感知能力向量P（wj）之间的相似程度可以用dis（P（wj），QTotu），其中函数dis（·）为欧式函数，计算两个向量之间的空间距离。因此，任务To的所有子任务感知质量需求与时空区域内所有工人的感知能力之间的距离计算如下：

LenTo=∑gu=1∑cj=1dis（P（wj），QTotu）（5）

由上面计算可知，对于任务To，数据质量定义为感知时空区域内所有工人的感知能力与任务的感知质量需求距离的倒数，计算如下：

DatTo=1LenTo（6）

根据得到的CoverTo和DatTo，每个任务To的感知质量定义为覆盖率和数据质量的线性组合，计算如下：

QuaTo=σCoverTo+ξDatTo（7）

其中：σ、ξ为给定的常数。

2.3 任务优先级调度算法

算法1是融合贪心算法的感知质量优先级任务调度模型的执行过程。

算法1 任务优先级调度算法

输入：时空单元地图M，工人集合W，每个工人感知范围R和感知能力向量P，任务集合TS，每个任务的子任务集合T，子任务感知范围E和感知质量需求Q。

输出：被选取的任务Tprior。

a）如果有新的任务请求，将此任务加入队列；

b）从当前任务队列队头取出任务To；

c）根据式（4）计算出任务To时空覆盖率；

d）根据式（6）计算出任务To数据质量；

e）根据式（7）计算出任务To的感知质量QuaTo；

f）如果队列不为空，跳转至步骤b）；

g）根据每个任务QuaTo的大小进行排序；

h）按照QuaTo从大到小的顺序将任务重新加入队列；

i）采用贪心策略，将队头任务出队并赋值给Tprior。

3 子任务在线协作

3.1 子任务协作模型

3.1.1 子任务激励成本

由于工人移动带来的不确定性，要激励尽可能多的工人参与任务以提升感知质量，需要考虑工人的执行成本和补偿成本。本文定义执行成本为完成子任务t（u，To）需要平台支付产生的成本，其由子任务的感知量QTotu以及平台设定的价格决定，执行成本计算如下：

Cos（tt（u，To））=QtuTopri（8）

其中：向量pri为平台制定支付每类传感器的单价。

执行补偿定义为设备损耗补偿和移动补偿，其中，设备损耗补偿PC为子任务t（u，To）完成后的补偿；移动补偿为子任务所在地图子单元e（v，t（u，To））与工人所在地图子单元r（k，R（wj））之间的距离开销，计算如下：

Com（wj，t（u，To））=PC（t（u，To））+τ|r（k，R（wj））－e（v，t（u，To））|（9）

其中：τ为一个常数系数。

根据得到的执行成本和补偿成本，总的激励成本定义为两者之和，计算如下：

pay（wj，t（u，To））=Cos（tt（u，To））+Com（wj，t（u，To））（10）

3.1.2 子任务执行时间成本

对于在线任务，时效性也是需要关注的问题，任务的完成时间越短，性能越好。优化任务执行时间也是本文要优化的目标，因此，本文在设计子任务时间成本时，将执行时间分为子任务执行时间成本和子任务之间因约束关系而产生的同步时间成本。具体来说，工人wj执行子任务t（u，To）的时间成本定义为子任务每一类工作需求q（x，t（u，To））与工人的对应执行能力p（l，P（wj））的比值之和，运行时间成本计算如下：

run（wj，t（u，To））=δ∑l=x=fl=x=1q（x，t（u，To））p（l，P（wj））（11）

其中：其中δ为常数参数。

同步时间成本为子任务间相互约束关系而产生的收发同步消息时延，定义为子任务t（u，To）感知质量需求QTotu成正比，同步时间计算如下：

syn（wj，t（u，To））=εQTotu（12）

其中：ε为常数参数。

子任務t（u，To），在选择工人wj的情况下，执行总时间成本定义为运行时间与同步时间之和，计算如下：

time（wj，t（u，To））=run（wj，t（u，To））+syn（wj，t（u，To））（13）

3.1.3 优化目标

基于上述分析，任务分配模型的优化目标为：在（wj，tu）二元组构成的离散决策空间中，在满足约束的条件下，为被选择任务的每个子任分配合适的工人，使激励成本大小与任务完成时间最小化。

minF（To）=∑gu=1|θpay（wj，t（u，To））+μtime（wj，t（u，To））|（14）

s.t. To=Tprior（15）

q（x，t（u，To））≤p（l，P（wj））（16）

t（u，To），t（u+1，To）∈To且（t（u，To），t（u+1，To））∈ETo（17）

其中：（wj，tu）∈D，D为子任务与工人二元组的离散决策空间，wj为工人集合W中的任一元素 ，tu为任务To的子任务。约束式（15）表示任务To为算法1筛选出的任务；约束式（16）表示子任务t（u，To）的感知需求小于工人wj的感知能力p（l，P（wj））；约束式（17）表示任务t（u，To），t（u+1，To）为To的子任务，且其构成的边（t（u，To），t（u+1，To））满足任务To子任务间的相互约束关系;θ、μ为给定的常数。

3.2 基于强化学习的子任务协作方法

3.2.1 强化学习进行子任务协作

本文所要解决的问题为式（14）所示的组合优化问题，考虑到子任务间依赖关系约束和任务工人二元组构成的离散决策空间，将此组合优化问题建模为有约束的马尔可夫决策过程，并采用可以在序列决策过程中构建解决方案的Q学习方法进行问题求解。

具体而言，将MCS平台作为智能体，根据当前子任务和已经被执行的子任务的状态，采取为当前子任务选择工人的动作，然后通过计算目标表达式的函数值获得来自环境的奖励。重复此训练过程直到满足算法的终止条件，此时智能体得到的所有状态到动作之间的映射概率关系即为策略，所有工人和任务组成的二元组集合构成此组合优化问题的最优解。

3.2.2 依赖关系约束的状态、动作空间等

1）有约束的动作空间

动作是任意时刻的子任务工人匹配方式，即a=（wj，t（u，To）），a∈A，二元组（wj，t（u，To））表示为子任务t（u，To）分配工人wj，A为动作空间。

约束动作选择空间采用邻接矩阵A表示，假设对nn个子任务、mm个工人进行匹配，那么其中任意一次组合可以用二元组（ii，jj）表示，当为1时表示子任务ii可以分配给工人jj，当为0时表示子任务ii不可以分配给工人jj。由于工人感知能力和子任务感知需求之间的约束关系以及任务协作图中子任务的顺序性约束关系，当执行到不同的子任务，下一步动作的选择必须满足优化目标的约束关系，即满足式（16）（17）的约束条件。

2）有约束状态空间与马尔可夫性

状态空间S是智能体能够选择合理动作的基础， 本文将多个子任务tu分配不同工人的情况作为智能体状态空间。对于任意时刻状态用一个2m维变量的函数s（2m）表示，即 s（2m）∈S，前m个维度表示子任务的工人分配情况，后m个维度根据子任务协作图的约束关系表示每个子任务执行完后下一步可以被执行的子任务。

具体来说，为子任务选择工人的过程可以描述为：a）在当前状态下，通过判断前m维变量的值随机选择任一子任务t（u，To），并按照ε贪心方法为其选择满足约束条件的工人wj，更新前m维变量的子任务的分配情况和邻接矩阵A；b）根据由子任务间约束关系构成的后m维变量，随机选择t（u，To）执行完后可以执行的下一个子任务；c）在满足依赖约束的条件下为多个子任务选择工人形成的随机决策序列为S（2m），a，r（s（2m），a），s′（2m），a′，r′（s（2m），a），…。其中s′（2m）、a′、r′（s（2m），a）为下一时刻的子任务状态、动作和奖励。

在本文TCSP算法中，假设子任务和工人的随机选择过程满足马尔可夫特性，即子任务和工人的选择概率只与当前时刻的状态s（2m）有关，公式表示如下：

P（（wj，t（u，To））|s（2m），s′（2m），…）=P（（wj，t（u，To））|s（2m））（18）

其中：s′（2m）为下一个时刻状态。因此，本文将此随机过程建模为有约束的马尔可夫决策过程。

3）奖励函数的设计

对于作为智能体的MCS平台而言，一个子任务分配给某个工人的动作，产生可以作为立即奖励的激励成本和时间成本，即每执行一个动作就从环境中得到一个立即奖励。因此，立即奖赏r（s（2m），a）计算如下：

r（s（2m），a）=θpay（wj，t（u，To））+μtime（wj，t（u，To））（19）

4）优化策略及收敛性证明

子任务协作的目标是为不同子任务tu分配工人wj使目标函数F（To）最小化。平台在为子任务分配工人的过程中通过Q学习算法进行决策判断。具体来说，智能体在为当前子任务tu分配工人时，检查Q表格中与此子任务对应组合的Q值大小，选择Q值最大组合中的工人分配给当前子任务，并根据Q学习策略进行模型更新，最终得到所有子任务的最优协作策略。

Q学习算法是通过迭代训练更新Q表格，使最终状态的Q值可以逼近目标值。Q学习算法当前状态值更新规则，计算如下：

Q（s（2m），a）=Q（s（2m），a）+α［r（s′（2m），a′）+γmaxQ（s′（2m），a′）－Q（s（2m），a）］（20）

其中：r（s′（2m），a′）+γmaxQ（s′（2m），a′）是下一状态目标值，其为下一状态值最大Q值和对应的工人任务立即奖励之和； r（s′（2m），a′）+γmaxQ（s′（2m），a′）－Q（s（2m），a）为Q学习算法的时序差分误差；Q（s（2m），a）的更新为当前值与误差值的和；γ为折扣因子，0≤γ≤1;α为学习率，0≤α≤1。

为了证明通过强化学习算法可以在有约束的马尔可夫决策过程中求出最优协作策略，设

ΔT（s（2m），a）=Q（s（2m），a）－Q*（s′（2m），a′）（21）

由文献［24］中定理2可以证明，Q学习方法在满足其三个约束条件时ΔT（s（2m），a）趋近于0，即该方法可以通过式（20）迭代收敛于最佳状态动作价值函数Q*（s′（2m），a′），进而得到最佳协作策略。

3.2.3 子任务协作算法实现

算法2 子任务在线协作算法

输入：时空单元地图M，工人集合W，每个工人感知范围R和感知能力向量P，任务集合TS，每个任务的子任务集合T，子任务感知范围E和感知质量需求Q，算法1的Tprior。

输出：所有子任务工人二元组集合。

a）初始化Q表格；

b）初始化参数θ、μ、γ、α；

c）判断是否需要循环进行m轮模型训练，如果不需要直接转至步骤j）；

d）工人、任务、时空单元参数随机初始化；

e）为了防止模型陷入局部最优，采用ε贪心策略进行模型训练，即随机生成概率prob，如果prob<ε，随机选取一个动作执行，否则根据约束动作空间A和当前状态s（2m）作出动作选择a；

f）根据式（17）得到智能体的立即奖励r（s（2m），a）；

g）更新为下一时刻状态；

h）根据式（18）更新模型的Q表格；

i） 如果模型训练结束，保存模型参数；

j）读取模型参数值至Q表；

k）根据Tprior的所有子任务情况，输入当前状态s（2m）到Q学习算法中，计算出子任务工人二元组值；

l） 重复执行步骤k）直到协作任务完成；

m）输出所有子任务工人二元组集合。

4 实验及分析

进一步，针对MCS中有依赖约束任务的在线协作问题，本文综合考虑了工人、任务的时空特性，感知质量特点和子任务之间的依赖約束等因素，以最小化系统激励成本与时间成本为目标，基于贪心和强化学习算法设计了一种在线任务协作算法。为了评估本文算法的性能，在Python实验环境中，首先对本文提出的TCSP算法的收敛特性、最优协作策略和任务数量变化的影响进行分析，然后通过对比实验进行算法性能验证。实验的主要参数设置如表1所示。

4.1 TCSP算法特性分析

为评估TCSP算法，本文从工人数量和子任务数量两个因素对算法模型的影响进行实验分析。具体来说，首先对图2中类型2任务进行模型的收敛性和最优协作策略分析；然后，固定工人数量为20个，增加子任务数量分别为4、6、10个且依赖关系为图2中类型1～3时进行模型的性能变化分析。在实验中每次对模型进行1000轮训练，观察并分析每一轮训练完成后平台智能体获得的奖励和的变化规律，基于此进行模型特性分析。

图3显示了工人个数取不同值时模型奖励和的变化。从图3中可以看出，工人数在不同情况下，随着迭代轮数的增加模型的奖励和都在逐渐增大，最终趋于一个稳定值。表明TCSP算法在针对有依赖的协作任务进行训练时可以得到稳定的算法模型，即可以得到稳定的任务协作策略。另一方面，从图3中还可以看出当工人数从10个变化到20个时，模型的奖励和最终收敛值约有10%的提升；继续将工人数从20个增加到30个时，模型的最终奖励和无明显提升，表明在任务数量固定的情况下，当20个工人时TCSP算法可以训练得到最优任务协作策略。

图4显示工人数量固定为20个时，子任务数量取不同值且依赖关系为不同类型的情况下模型奖励和的变化。一方面从图中可以看出，子任务数在不同情况下，随着迭代轮数的增加模型的奖励和都在逐渐增大，最终趋于一个稳定值。表明TCSP算法在针对有不同数量和依赖关系的协作子任务进行训练时都可以得到稳定的任务协作策略。另一方面，从图4中可以看出当子任务数量为4个且依赖关系为图2中类型1时模型可以很快在80轮左右收敛；当子任务数量为6个且依赖关系为图2中类型2时模型可以在150轮左右收敛，比子任务数量为4个时收敛速度稍慢。值得注意的是，当子任务数量为10个且依赖关系为图2中类型3时模型在700轮左右才收敛且优化能力下降约7%，表明此时工人数量不足导致算法的任务协作性能下降。如果工人数量固定数量为20个时，继续增加子任务数量和依赖关系复杂度，模型的收敛性将会较难保证，即此时较难训练得到最佳协作策略。

4.2 对比算法

为了评估本文的TCSP算法性能，选取以下两种算法作为基线进行对比实验：

a）时间约束下多任务分配算法（MATC-GA）［25］。MATC-GA将有时间约束下的多任务分配构建为组合优化问题，采用基于GA的分配方案实现多任务协作分配，以最大化MCS平台的效用。MATC-GA算法从时间约束角度分析任务间的依赖关系，是较典型的有约束任务协作方法。

b）参与者密度约束下全局贪婪算法（GGA）［26］。GGA是一种采用全局贪婪机制对所有任务进行分配的算法，其通过模糊逻辑控制方法得到不同时空的参与者密度，进而获得所有任务的效用以对所有任务进行分配。GGA算法从参与者密度约束角度进行全局贪婪任务分配，可以从全局解决多任务协作问题。

4.3 评估性能指标

为了验证TCSP算法的有效性，分别从任务完成率、任务平均完成时间和平均感知成本三项指标对算法进行评估，分析工人数量变化对指标的影响。

a）任务完成率。定义为完成任务数与平台执行总任务数量的比值，其值介于［0，1］，用来衡量不同条件下平台完成任务能力的大小，其中完成任务数为包含多个依赖子任务的任务数量。

任务完成率=完成任务数总任务数

b）平均完成时间。定义为任务完成总时间与完成任务数的比值，用于评估平台有效完成单个任务速度的快慢，其中任务完成总时间为成功任务的执行时间和失败任务的执行时间之和。

平均完成时间=任务完成总时间完成任务数

c）平均感知成本。定义为完成协作任务所需要的激励总成本和时间总成本之和与平台总任务数的比值，表示平均每个任务被完成所产生代价的大小，其中成本之和为平台完成所有协作任务而产生的成本累加。

平均感知成本=激励总成本+时间总成本总任务数

4.4 对比实验结果与分析

为说明工人数量变化对实验结果的影响，本文固定平台中任务数为20，每个任务的子任务数量为6，工人感知半径为8。通过改变工人的数量从任务完成率、平均完成时间和平均感知成本三个方面对TCSP、MATC-GA和GGA算法进行对比分析。为了避免随机性因素产生的影响，实验结果均为多次重复实验产生结果的平均值。

图5显示了工人数量变化对任务完成率的影响。可以看出，TCSP算法具有更高的任务完成率，GGA算法完成率由低逐渐变高，MATC-GA算法完成率具有波动性。其原因是，GGA在工人数量很少的条件下不能有效地在任务感知半径内寻找到合适的工人，当工人数量增加到30个，其找到合适工人的可能性增加，因此任务完成率也开始增加。MATC-GA是通过基因的交叉变异来对任务协作目标进行优化，但由于有约束的依赖任务每次完成的路径存在多条，使算法的适应度函数具有多个优化目标，进而导致其分配结果存在多种可能，所以MATC-GA任务完成率的波动性较其他算法大。随着工人数量的增加，三个算法的任务完成率都在逐渐增加，其中TCSP在工人为30个的条件下很快趋于稳定，GGA在工人数为80左右时与TCSP的任务完成率都逐渐稳定到70%左右；MATC-GA的任务完成率具有波动性，但当工人数量增加时其平均完成率也在逐渐上升。

图6显示了工人数量变化对平均完成时间的影响。可以看出，TCSP算法的平均完成时间低于MATC-GA和GGA算法。其原因是GGA从全局的角度对所有的任务和工人进行贪心匹配，容易使单个子任务陷入局部最优。MATC-GA在面对依赖约束的任务时不能在模型的优化迭代策略上进行有效的改进，只能在适应度函数上进行限制，虽然也可以进行任务协作分配，但是这个约束不能在決策方法上体现，所以限制了算法的性能。本文算法一方面针对任务对工人进行全局感知质量评估，选取感知质量最高的任务作为当前执行任务，这有效地提高了任务的完成率；另一方面，本文算法2强化学习模型在训练的过程中将任务的约束关系用状态空间表示并进行训练，使得TCSP得到的最优任务协作策略可以较好地泛化到不同的工人和任务情况中。随着工人数量的增加，三个算法的平均完成时间都在逐渐减小，其中TCSP和GGA的平均完成时间在工人数为30左右都开始下降，并且TCSP比GGA更快地趋于稳定。

图7显示了工人数量变化对平均感知成本的影响。可以看出在工人数量较少时，TCSP算法比GGA的平均感知成本更快地收敛。其原因是，GGA进行全局贪心搜索，不能综合考虑激励成本和时间成本，容易陷入局部最优，但当工人数达到一定阈值之后，由于贪心算法而产生的局部性影响逐渐变小，所以其与TCSP的平均感知成本逐渐接近。随着工人数量的增加，三个算法的平均感知成本都在逐渐减小。当工人数量不足30个，GGA比TCSP的平均感知成本高18%左右，其原因是，TCSP中的任务协作策略综合考虑了激励成本和时间成本两种因素进行工人分配，而GGA只是简单地考虑感知范围内能够完成任务的工人，导致此算法不能更好地综合考虑激励成本和时间成本两种因素。当工人数大于40个，TCSP和GGA的平均感知成本都能趋于一个较接近的稳定值。

5 結束语

在移动群智感知研究中，随着移动群智感知中任务数量和复杂程度的增加，每个任务逐渐不再能独立地完成，然而目前缺乏对任务间约束关系的研究。基于此，提出了基于感知质量优先级的在线任务协作方法，该方法首先使用贪婪算法计算感知质量优先级对全部任务进行筛选以保证任务完成率，然后将选出任务中存在时间先后或执行逻辑前后关系的多个子任务构建为任务协作图，并将其协作过程建模为有约束的马尔可夫决策过程，通过强化学习算法求出最优协作策略。仿真结果表明，提出的任务协作方法可以有效地对感知任务执行过程进行优化并提升平台效益。在未来的工作中应考虑更多可能存在的约束关系对任务协作的影响，并探索新的优化方法和理论基础。

参考文献：

[1]Ganti R K，Ye Fan，Lei Hui，et al.Mobile crowdsensing：current state and future challenges［J］.IEEE Communications Magazine，2011，49（11）：32-39.

［2]Dinh T A N，Nguyen A D，Nguyen T T，et al.Spatial-temporal coverage maximization in vehicle-based mobile crowdsensing for air quality monitoring［C］//Proc of IEEE Wireless Communications and Networking Conference.Piscataway，NJ：IEEE Press，2022：1449-1454.

［3]Nandagopal C，Naveen V，Suriya M，et al.Traffic congestion monitoring based on cloud using crowd sensing［C］//Proc of International Conference on Sustainable Computing and Data Communication Systems.Piscataway，NJ：IEEE Press，2022：1307-1314.

［4]Jovanovic＇ S，Jovanovic＇ M，koric＇ T，et al.A mobile crowd sensing application for hypertensive patients［J］.Sensors，2019，19（2）：https：//doi.org/10.3390/s19020400.

［5]A Sawafi Y，Touzene A，Day K，et al.Mobile Crowd Sensing RPL-based Routing Protocol for Smart City［J］.International Journal of Computer Networks and Communications，2020，12（2）：49-69.

［6]He Shibo，Shin D H，Zhang Junshan，et al.Toward optimal allocation of location dependent tasks in crowdsensing［C］//Proc of IEEE Conference on Computer Communications.Piscataway，NJ：IEEE Press，2014：745-753.

［7]Yan Liu，Guo Bin，Wang Yang，et al.TaskMe：multi-task allocation in mobile crowd sensing［C］//Proc of ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York：ACM Press，2016：403-414.

［8]Song Zheng，Liu C H，Wu Jie，et al.QoI-aware multitask-oriented dynamic participant selection with budget constraints［J］.IEEE Trans on Vehicular Technology，2014，63（9）：4618-4632.

［9]Xiao Mingjun，Wu Jie，Huang Liusheng，et al.Online task assignment for crowdsensing in predictable mobile social networks［J］.IEEE Trans on Mobile Computing，2017，16（8）：2306-2320.

［10]Kang Yanrong，Miao Xin，Liu Kebin，et al.Quality-aware online task assignment in mobile crowdsourcing［C］//Proc of the 12th IEEE International Conference on Mobile Ad Hoc and Sensor Systems.Piscataway，NJ：IEEE Press，2015：127-135.

［11]Li Yanqiang，Zhu Bin，Huang Tao，et al.Mota：multi-stage multi-task online assignment algorithm based on opportunistic crowdsensing［C］//Proc of the 16th International Computer Conference on Wavelet Active Media Technology and Information Processing.Piscataway，NJ：IEEE Press，2019：345-348.

［12]Wang Liang，Yu Zhiwei，Zhang Daqing，et al.Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation［J］.IEEE Trans on Mobile Computing，2019，18（1）：84-97.

［13]Gong Wei，Zhang Baoxian，Li Cheng.Location-based online task scheduling in mobile crowdsensing［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2017：1-6.

［14]Wang Jiangtao，Wang Yasha，Zhang Daqing，et al.Multi-task allocation in mobile crowd sensing with individual task quality assurance［J］.IEEE Trans on Mobile Computing，2018，17（9）：2101-2113.

［15]Jiang Weijin，Chen Junpeng，Liu Xiaoliang，et al.Participant Recruitment Method Aiming at Service Quality in Mobile Crowd Sensing［J］.Wireless Communications and Mobile Computing，2021，2021：articleID 6621659.

［16]Wei Xiaohui，Wang Yongfang，Gao Shang，et al.Data quality aware task allocation with budget constraint in mobile crowdsensing［J］.IEEE Access，2018，6：48010-48020.

［17]李卓，徐哲，陈昕，等.面向移动群智感知的位置相关在线多任务分配算法［J］.计算机科学，2019，46（6）：102-106.（Li Zhuo，Xu Zhe，Chen Xin，et al.Location-related online multi-task assignment algorithm for mobile crowd sensing［J］.Computer Science，2019，46（6）：102-106.）

［18]李卓，徐哲，陈昕，等.基于预测的机会群智感知多任务在线分配算法［J］.工程科学与技术，2018，50（5）：176-182.（Li Zhuo，Xu Zhe，Chen Xin，et al.Online multi-task assignment algorithm with prediction for opportunistic crowd sensing［J］.Advanced Engineering Sciences，2018，50（5）：176-182.）

［19]Sun Guodong，Wang Yanan，Ding Xingjia，et al.Cost-fair task allocation in mobile crowd sensing with probabilistic users［J］.IEEE Trans on Mobile Computing，2021，20（2）：403-415.

［20]Zhu Weiping，Guo Wenzhong，Yu Zhiyong，et al.Multitask allocation to heterogeneous participants in mobile crowd sensing［J］.Wireless Communications & Mobile Computing，2018，2018：articleID 7218061.

［21]Wang Liang，Zhi Wenyu，Guo Bin.Mobile crowd sensing task optimal allocation：a mobility pattern matching perspective［J］.Frontiers of Computer Science，2018，12（2）：231-244.

［22]Li Zhidu，Liu Hailiang，Wang Ruyan.Service benefit aware multi-task assignment strategy for mobile crowd sensing［J］.Sensors，2019，19（21）：https：//doi.org/10.3390/s19214666.

［23]胡华，张强，胡海洋，等.基于Q-learning的移动群智感知任务分配算法［J］.计算机集成制造系统，2018，24（7）：1774-1783.（Hu Hua，Zhang Qiang，Hu Haiyang，et al.Q-learning based sensing task assignment algorithm for mobile sensing system［J］.Computer Integrated Manufacturing Systems，2018，24（7）：1774-1783.）

［24]Melo F S.Convergence of Q-learning：a simple proof［EB/OL］.（2007-02-12）.http：//users.isr.ist.utl.pt/～mtjspaan/readingGroup/ProofQlearning.pdf.

［25]Li Xin，Zhang Xinglin.Multi-Task Allocation Under Time Constraints in Mobile Crowdsensing［J］.IEEE Transactions on Mobile Computing，1 April 2021，20（4）：1494-1510.

［26]杨桂松，张杨林，何杏宇.面向模糊逻辑控制的移动群智感知多任务分配［J］.小型微型计算机系统，2020，41（10）：2068-2074.（Yang Guisong，Zhang Yanglin，He Xingyu.Multi-task allocation based on fuzzy logic controlin mobile crowd sensing［J］.Journal of Chinese Computer Systems，2020，41（10）：2068-2074.）

收稿日期：2023-02-24；

修回日期：2023-04-11

基金项目：国家自然科学基金资助项目（61802257，61602305）；上海市自然科学基金资助项目（18ZR1426000，19ZR1477600）；南通市科技局社会民生计划项目（MS12021060）；浦东新区科技发展基金产学研专项资助项目（PKX2021-D10）；敏捷智能计算四川省重点实验室开放式基金资助项目

作者简介：杨桂松（1982-），男，河南漯河人，副教授，硕导，博士，主要研究方向为物联网与普适计算等；白高磊（1990-），男，河南禹州人，硕士研究生，主要研究方向為移动群智感知和共识协同方法；何杏宇（1984-），女（通信作者），湖南岳阳人，副教授，硕导，博士，主要研究方向为物联网和移动群智计算（xy_he@usst.edu.cn）；贾明权（1982-），男，四川合江人，高级工程师，博士，主要研究方向为先进智能计算.