移动群智感知系统中基于离散布谷鸟搜索算法的任务分配

杨正清 周朝荣 袁姝

摘 要：针对移动群智感知系统中工人积极性低以及任务过期的问题，提出了基于初始成本和软时间窗的任务分配算法。对应的任务分配问题为NP-hard问题，不存在计算有效的最优算法，因此，基于离散布谷鸟搜索算法（Discrete Cuckoo Search Algorithm， DCSA）進行求解。首先，根据问题特征，分别设计了对应的全局搜索过程以及局部搜索过程。其次，根据任务与工人起始位置的距离以及时间窗大小，分析其优先级以便得到更好的解。最后，执行可行化操作，使各次任务分配均满足相关约束。仿真结果表明，与遗传算法和贪婪算法相比，基于DCSA的任务分配算法能够提升工人的参与积极性，解决任务过期的问题，并最终降低系统的总成本。

关键词：移动群智感知;任务分配;初始成本;软时间窗;任务优先级;离散布谷鸟搜索算法

中图分类号：TP393.01

文献标志码：A

Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system

YANG Zhengqing1， ZHOU Zhaorong1，2*， YUAN Shu1

1.School of Physics and Electronic Engineering， Sichuan Normal University， Chengdu Sichuan 610101， China;

2.Meteorological Information and Signal Processing Key Laboratory of Sichuan Higher Education Institutes （Chengdu University of Information Technology）， Chengdu Sichuan 610225， China

Abstract：

Considering the problems of low-enthusiasm workers and task expiration in the mobile crowd sensing system， a task assignment algorithm based on initial cost and soft time window was proposed. As the corresponding task assignment problem belongs to the category of NP-hard problems and the computationally efficient optimal algorithm cannot be found， thus， an algorithm was developed based on Discrete Cuckoo Search Algorithm （DCSA）. Firstly， the corresponding global search process and local search process were designed respectively according to the problem characteristics. Secondly， to derive the better solution， the priorities of tasks with respect to the distance between tasks and workers starting positions as well as the size of time windows were analyzed. Finally， feasible operations were executed to guarantee that the related constraints were satisfied by each task assignment. Compared with genetic algorithm and greedy algorithm， the simulation results show that DCSA-based task assignment algorithm can improve the enthusiasm of workers to participate， solve the problem of task expiration， and ultimately reduce the total system cost.

Key words：

mobile crowd sensing; task assignment; initial cost; soft time window; task priority; Discrete Cuckoo Search Algorithm （DCSA）

0 引言

近年来，随着移动通信技术的快速发展以及移动互联网的广泛应用，智能手机、车载移动设备、可穿戴设备等移动设备得到了日益普及。由于内置了诸如：摄像头、麦克风、GPS等多种高性能的传感器，这些移动设备可以代替传统的静态传感器节点，完成大规模、复杂数据的采集、存储、处理以及应用功能，这种新兴的数据感知模式被称作“移动群智感知”[1]。当前，移动群智感知技术已经应用于智能交通系统[2]、噪声状况收集[3]以及空气质量监测[4]等领域。就移动群智感知系统而言，在满足成本 [5]、隐私保护[6]等约束条件下，如何将数据感知任务分配给合适的用户以优化感知质量[7]、执行任务数量[8]、用户收益 [9]等性能指标是关键，因此，这类系统中的任务分配问题受到了越来越多研究人员的关注。

目前，已有一些学者针对移动群智感知系统中的任务分配问题进行研究。文献[10]中研究了在激励预算约束下如何指派工人（即携带移动设备的用户）以最大化任务覆盖范围以及给定任务覆盖范围的前提下如何指派工人以最小化成本，但该系统需要针对工人大量过往数据进行分析之后再分配任务，导致系统前期的优化效果不好。文献[11]中通过工人历史移动记录预测工人的行为轨迹，再根据预测结果分配任务，旨在给定激励预算约束下最大化覆盖质量;文献[12]中考虑了任务具有不同的时间敏感度，根据任务的时间敏感度与位置依赖情况分配任务，以便最大化覆盖范围。但前者可能出现工人收益低，进一步导致参与任务工人数低、任务完成率下降的后果;后者只考虑了最大化覆盖范围的因素，忽略被指派的工人数量，缺乏工人数量的限制可能导致参与任务工人数过多、人力浪费的后果。文献[13]中考虑了工人具有最晚工作时间要求，旨在给定时间约束下最大化任务的完成数量;文献[14]中同时兼顾了工人与任务的硬时间窗约束，旨在满足这两类时间窗约束的前提下最大化系统收益。上述两篇文献均假设工人能在其时间约束下完成被分配的任务，但在实际生活中，由于天气、交通等因素，可能存在工人无法在给定时间约束下完成任务的情况。例如：指派工人在下午5点到7点之间去A地完成空气质量收集的任务，若天气恶劣导致工人下午7点3分才到达A地，系统会认为工人未能够成功执行任务且该任务超出时间限制也被归入过期任务，这对于工人以及任务都是一种损失。同理，若工人下午4点半就可提前到达任务所在地，却要等到5点才执行任务，工人的等待也意味着时间的浪费。

为此，本文针对移动群智感知系统中的任务分配问题展开研究。不同于现有研究主要考虑任务覆盖范围[12]等性能指标、忽略工人收益及数量的情况，考虑工人具有初始成本要求，即只要工人被分配执行任务，就获得一个基本的收益保障，从而提升工人的参与积极性，并优化成本以约束工人数量。同时，由于存在工人早到或者迟到的实际情况，任务的硬时间窗约束将导致工人的时间浪费或者任务过期的后果，故放松任务的时间窗要求，结合时间窗惩罚成本提出了软时间窗的概念。软时间窗虽在一定程度上容忍工人早到或者迟到的现象，但迟到或早到的工人将面临相应的惩罚成本，这将促使工人尽量地满足时间窗约束。此外，本文在优化成本时兼顾工人时间成本、初始成本以及惩罚成本等因素，旨在合理的任务分配下，最小化系统的总成本。进一步地，考虑到上述约束条件下的任务分配问题为组合优化问题，属于NP-hard问题的范畴[14]，不存在计算有效的最优算法，为此，本文采用智能算法进行求解。由于布谷鸟搜索算法简单易行、收敛速度快，且具有较好的全局搜索能力[15]，因此，基于离散布谷鸟搜索算法（Discrete Cuckoo Search Algorithm， DCSA）提出任务分配求解算法。在求解的过程中，为了进一步降低工人的时间成本以及惩罚成本，根据任务的时间窗大小以及任务离起始位置的距离，对任务进行优先级排序。仿真结果表明，较之于其他算法，基于离散布谷鸟搜索算法的任务分配算法系统总成本更低，且有助于提高工人的参与积极性，同时，有效地解决了工人时间浪费以及任务过期问题。

1 系统模型

假设移动群智感知系统中有M个工人，对应的工人集合为W={w1，w2，…，wM}，需要完成N个感知任务，对应的任务集合为T={t1，t2，…，tN}，其中，每个任务将被指派给工人执行一次。当任务ti∈T被指派给工人wk∈W时，后者需要移动到该任务所处位置后再执行任务，其中，工人和任务的位置分别表示为（xwk，ywk），（xti，yti）。此外，考虑到电池电量以及时间窗约束，设定每个工人最多可执行Φ个任务。相应地，若工人wk在完成任务ti后继续完成任务tj，则xijk=1;否则，xijk=0。此外，考虑任务的时间窗约束，任务ti的软时间窗为[ai，bi]，所指派的工人会尽量在不早于时间ai以及不晚于时间bi到达任务ti所处位置并执行任务。若指派的工人wk在时间窗外到达，其真实到达时间为Sik，则工人将面临如下的惩罚成本Hi：

Hi=Li·Aik， Sik

0，ai≤Sik≤bi

Ri·Bik，Sik>bi（1）

其中，Li与Ri分别为任务ti的早到时间惩罚因子以及迟到时间惩罚因子，考虑到迟到现象的性质更为恶劣，因此，Ri>Li>0，本文仿真中分别设置Ri=7，Li=4。Aik=ai-Sik与Bik=Sik-bi分别为工人wk到达任务ti位置处的时间提前量以及时间滞后量。

相应地，兼顾移动群智感知系统中的工人初始成本、惩罚成本以及时间成本等因素的任务分配模型给出如下：

优化目标：

Min α·f1+β·f2+γ·f3（2）

约束条件：s.t.

∑ti∈T∑wk∈Wxijk=1; tj∈T（3）

∑ti∈Txihk=∑tj∈Txhjk; th∈T， wk∈W（4）

Sik+tik+dij/Vk-∞（1-∑wk∈Wxijk）≤Sjk ;

ti∈T， tj∈T， wk∈W（5）

Nk≤Φ; wk∈W（6）

其中：式（2）为优化目标，即最小化系统的总成本，即工人初始成本、惩罚成本以及时间成本的加权和。 f1=∑ti∈T∑wk∈WKkx0ik为工人的总初始成本，只与执行任务的工人数有关，与工人执行的任务数量无关，Kk为工人wk的初始成本，x0ik表示工人wk从其初始位置出发执行任务ti。 f2=∑ti∈T∑wk∈WLiAik+∑ti∈T∑wk∈WRiBik为工人的总惩罚成本，由早到惩罚成本和迟到惩罚成本构成。 f3=∑ti∈T∑tj∈T∑wk∈WGk（（x0ikdik+xijkdij+xj0kdjk）/Vk+tik）为工人的总时间成本，由工人的行走时间以及执行任务时间构成，Gk为工人wk单位时间成本，dij为任务ti和任务tj之间的距离，dik为任务ti和工人wk之间的距离，Vk为工人wk的移动速度，tik为工人wk完成任务ti所需的执行时间;α、 β、γ分别为3种成本的权重系数，α+β+γ=1，可通过设置不同的权重系数以体现三种成本各自的重要性。本文中，由于这三种成本对于优化目标有着同等重要的意义，因此，设置权重系数α、 β、γ的取值均为1/3。式（3）对应于每个任务将被指派给工人执行一次。式（4）与（5）表示工人执行任务的行走路线为单向环形，即工人wk进入任务ti位置后必须离开该位置，前往下一任务处或返回起始位置，∞为正无穷大。式（6）保证工人wk执行的任务数Nk不超过系统设定的最高任务数要求。需要指出的是，由式（2）～（6）所确定的优化问题属于NP-hard问题范畴，不存在计算有效的最优算法，只能够考虑次优算法。由于离散布谷鸟算法参数少、易于控制，具有较快的收敛速度以及较强的全局优化能力，可用于求解各类优化问题，因此，基于離散布谷鸟算法求解上述优化问题。

2 任务分配求解

由于任务分配问题（2）～（6）为组合优化问题，标准布谷鸟搜索算法中的位置更新机制将不适用，因此，基于改进后的离散布谷鸟搜索算法进行求解。在离散布谷鸟搜索算法中，每一个鸟蛋位于一个巢穴内，即对应着优化问题的一个可行解，就上述任务分配的优化问题而言，一个可行解即为一条可行的工人行走路线方案。

离散布谷鸟搜索算法根据布谷鸟寻找寄宿鸟巢的方式设计对应的全局搜索过程以及局部搜索过程求解任务分配问题。同时，为了进一步提高算法的性能，在求解的过程中根据各个任务的时间窗大小以及任务与起始位置之间的移动距离对任务进行优先级排序。然后，对参与任务的工人路线进行可行化操作，使任意一条路线均满足任务优先级排序以及软时间窗等约束条件。最后，给出完整的任务分配求解算法，以寻找满意的任务分配方案。

2.1 全局搜索过程

在布谷鸟搜索算法中，布谷鸟采用Lévy飞行随意搜索鸟巢过程即为全局搜索过程。结合参考文献[16-17]以及上述优化模型，在全局搜索过程提出每四个路线采用保留当前路径、Inversion、Swap和Shift方法更新工人路线。对应地，全局搜索过程给出如下：

算法1 离散布谷鸟搜索算法全局搜索过程。

输入种群中所有鸟巢，即每条路线。

有序号的程序——————————Shift+Alt+Y

程序前

1）

for 种群中每4个鸟巢，即每4条路线

2）

for k=1：4 分别取出4条路线中每一条路线

3）

switch k

4）

case 1 使当前路线保留为原路线

5）

case 2 对其原路线采用Inversion法

6）

case 3 对其原路线采用Swap法

7）

case 4 对其原路线采用Shift法

8）

end

9）

end for

10）

end for 直到循环完所有路线

11）

return 更新后的路线方案

程序后

其中的Inversion、Swap和Shift方法设计如下。

1）Inversion方法。

Inversion方法为路线内搜索方法，即对于编码路线中任意i、 j节点，将i节点到j节点的顺序编码进行反转的过程。图1给出i=3、 j=8时，路线编码经过Inversion方法后形成新路线的过程。

2）Swap方法。

Swap方法为路线内搜索方法，即对于编码路线中任意i、 j节点，将i节点和j节点的进行交换的过程。图2给出i=4、 j=7时，路线编码经过Swap方法后形成新路线的过程。

3）Shift方法。

Shift方法为路线内搜索方法，即对于编码路线中任意i、 j节点，将i节点到插入到j节点和j+1节点的过程。图3给出i=3、 j=6时，路线编码经过Shift方法后形成新路线的过程。

2.2 局部搜索过程

布谷鸟搜索算法的寄生性育雏机制显示，寄宿鸟巢主有Pa的概率发现布谷鸟鸟蛋。一旦发现，巢主将舍弃该鸟巢或者将该鸟巢推出去，则该鸟蛋则无法存活。对应于上述任务分配问题则理解为该路线为废弃路线，应更新，这即是局部搜索过程。采用Relocate方法对鸟蛋被发现后的路线进行更新。相应地，给出局部搜索过程如下：

算法2 离散布谷鸟搜索算法局部搜索过程。

输入种群中所有鸟巢，即每条路线。

有序号的程序——————————Shift+Alt+Y

程序前

1）

for 种群中每个鸟巢，即每条路线（解）

2）

随机生成一个数r∈[0，1]

3）

if r

4）

对其原路径采用Relocate法

5）

end

6）

end for 直到循环完所有路线

7）

return 更新后鸟巢（路线）

程序后

其中，Relocate方法为路线内搜索方法，即对于编码路线中任意i、 j节点，选择从j节点开始的m个连续的节点，将这m个节点重新定位在i和i+1之间，进而形成新的路线，如m=2时，将j、 j+1插入到i和i+1之间。图4给出i=2、 j=6时，路线编码经过Relocate方法后形成新路线的过程。

2.3 明确任务优先级的过程

为了进一步降低工人的惩罚成本和时间成本，对任务集T=（t1，t2，…，tN）中的任务进行优先级排序[18]。此处的任务优先级指的是任务被执行的先后次序，由各任务的时间窗大小以及各任务到各工人位置的距离因素共同决定。工人wk 对于任务ti的优先级评价函数fik计算如下：

fik=g1（dik/Vk-ai）（bi-dik/Vk）（dik/Vk-ai）（bi-dik/Vk）1（bi-ai）+

g2min1≤j≤ndjkdik（7）

其中：（dik/Vk-ai）（bi-dik/Vk）（dik/Vk-ai）（bi-dik/Vk）表明工人wk 從所处位置（xwk，ywk）移动至任务ti位置的时间是否满足时间窗约束，若dik/Vk∈[ai，bi]，即满足时间窗约束，则（dik/Vk-ai）（bi-dik/Vk）（dik/Vk-ai）（bi-dik/Vk）=1;若dik/Vk[ai，bi]，即不满足时间窗约束，则（dik/Vk-ai）（bi-dik/Vk）（dik/Vk-ai）（bi-dik/Vk）=-1;同时，0<1/（bi-ai）<1，（bi-ai）越小即时间窗间隔越小，则该值就越大。相应地，满足时间窗约束且时间窗间隔小的任务通过以上两式相乘将获得更大的结果值，进而提高该任务的排序。（min1≤j≤ndjk）/dik为距离因素，其中分子min1≤j≤ndjk为离工人wk 位置最近的任务距离，0<（min1≤j≤ndjk）/dik≤1，任务ti离工人wk 位置越近，该值越大。g1和g2为权重参数，满足0≤g1，g2≤1，且g1+g2=1。若g1=0、g2=1，则表明评价函数只考虑距离因素、不考虑时间窗大小;若g1=1、g2=0，则表明评价函数只考虑时间窗大小、不考虑距离因素;否则，评价函数综合考虑任务的时间窗大小和距离两方面因素进行优先级排序。由于时间窗间隔小的任务有着更高的时间要求，对惩罚成本函数影响更大，因此，优先考虑完成时间窗间隔小的任务，相应地，权重建议g1>g2。最终，根据优先级评价函数fik从大到小的顺序对任务进行排序即可以获得工人wk 执行任务的优先级顺序。

2.4 明确可行解的过程

将种群中的工人路线编码映射为满足任务执行优先级以及约束条件的可行解过程， 即为明确可行解的过程。明确可行解的流程如图5所示。

为了更好地理解明确可行解的过程，对步骤“根据任务优先级确定工人路线”举例说明如下：

存在路径编码为H：2 5 6 10 1 4 7 3 8 9。首先，选中工人wk1 执行任务，由任务优先级中评价函数得到工人wk1 的任务优先级关系为：1 2 3 4 5 6 7 8 9 10。根据优先级关系得出工人wk1 的任务分配为（2 5 6 10），相应的，Nk1=4。然后，选中工人wk2 执行任务，工人wk2 的任务优先级关系为：5 2 1 3 4 6 9 10 8 7。除去已分配的任务，根据优先级得出工人wk2的任务分配为（1 4 7），相应的，Nk2=3。同理，对于工人wk3 存在优先级为：1 5 3 2 7 8 4 6 9 10，除去已分配的任务，得出工人wk3任务分配结果为（3 8 9），Nk3=3。由于此时无任务需被分配，相应的，路线编码H被分配完成。考虑到工人均从所处位置出发去执行任务，并最终返回所处位置。因此，工人路线Qh={k1 2 5 6 10 k1 0 k2 1 4 7 k2 0 k3 3 8 9 k3}，0代表工人与工人间的分隔符。

2.5 完整的任务分配求解算法

基于上述的4个过程，给出完整的任务分配求解算法如下：

算法3 任务分配求解。

输入：工人集W、任务集T、初始化种群、参数Pa等;

输出：最佳路线optrout，最小成本mincost。

有序号的程序——————————Shift+Alt+Y

程序前

1）

对任务集T中的任务进行优先级排序;

2）

对初始化种群进行可行解操作;

3）

寻找初始化种群中最佳路线optrout，计算相应成本为mincost;

4）

repeat

5）

采用全局搜索过程进行种群更新;

6）

对更新后种群进行可行解操作;

7）

寻找更新后种群的最佳路线optrout1，计算相应成本为mincost1;

8）

if mincost1

9）

optrout=optrout1;

10）

end if

11）

采用局部搜索过程进行路线更新;

12）

对更新后种群进行可行解操作;

13）

寻找更新后种群的最佳路线optrout2，计算相应成本为mincost2

14）

if mincost2< mincost

15）

optrout=optrout2;

16）

end if

17）

until最大迭代次数

程序后

2.6 算法的计算复杂性

假设上述任务分配算法的最大迭代次数为S，初始化种群规模（鸟巢数）为P。全局搜索过程和局部搜索过程时均与初始化种群规模有关，对应的时间复杂度均为O（P）;明确优先级过程的时间复杂度为O（N），其中，N为任务数;明确可行解过程的时间复杂度为O（P）。相应地，完整的任务分配求解算法的时间复杂度为O（S（P+N））。由此可以看出，在给定迭代次数S以及種群规模P的前提下，完整的任务分配算法的时间复杂性随着任务数N呈线性增长的趋势，可在多项式时间内求解，是求解任务分配问题的有效算法。

3 实验结果与分析

本章将分别通过基于DCSA改进的任务分配算法、遗传算法（Genetic Algorithm， GA）以及贪婪算法（Greedy）求解移动群智感知系统中基于离散布谷鸟搜索算法的任务分配问题，并根据仿真结果比较这三种算法的性能。同时，研究基于DCSA改进的任务分配算法下不同系统条件对系统总成本、工人参与率以及时间窗约束满足率的影响。为保证仿真结果准确性，每种情况系统都将运行多次并选用其平均值作为结果。系统的仿真参数设置如表1所示。

图6给出DCSA、GA以及Greedy算法下不同任务数的总成本。从图6可看出：在不同任务数下，DCSA的总成本最低，其次是GA，Greedy算法的总成本最高;且随着任务数的增加，DCSA的总成本低于GA，Greedy算法的趋势更为明显。这表明与GA与Greedy算法相比，基于DCSA的任务分配算法能更好地优化工人初始成本、惩罚成本以及时间成本，使得不同任务数下基于DCSA的任务分配总成本更低。

图7给出有无对任务优先级排序对系统总成本的影响。从图7可看出，不同任务数下，有任务优先级排序时的总成本低于无任务优先级排序时的总成本，且二者差值随着任务数的增加而增大。这是由于在任务优先级排序下，时间窗间隔小且距离工人位置更近的任务将优先被完成，进而降低工人的时间成本与惩罚成本。这表明任务优先级排序的存在具有降低总成本的作用，该作用随着任务数的增加更为明显，任务优先级排序更适用于任务数量大的移动群智感知系统。

图8给出有无初始成本对工人平均收益的影响。从图8可看出，不同任务数下，有初始成本时，工人平均收益总是大于无初始成本时的工人平均收益。这是由于考虑初始成本时，工人有基本的收益保证，进而提高工人平均收益，以提高其参与积极性。这表明初始成本的存在具有提高工人平均收益的作用。

图9给出有无惩罚成本对时间窗约束满足率的影响，此处的时间窗约束滿足率等于满足时间窗约束的任务数与系统存在总任务数的比值。从图9可看出，不同任务数下，有惩罚成本下的时间窗约束满足率总是高于没有惩罚成本下的时间窗约束满足率。这是由于软时间窗约束虽然放宽了任务的时间要求，允许工人迟早或早到;然而，相应提出的惩罚成本正比于工人的早到或者迟到时间，这将促使工人尽可能满足任务的时间窗约束。这表明惩罚成本的存在具有提高时间窗约束满足率的作用。

4 结语

本文研究了移动群智感知系统中基于离散布谷鸟搜索算法的任务分配问题。考虑到现有任务分配问题中忽略工人收益以及工人数量进而造成工人参与积极性下降的现象，提出工人具有初始成本。同时，针对硬时间窗约束造成的工人时间浪费或任务过期的后果，结合时间窗惩罚成本提出了软时间窗的概念。由于对应的任务分配问题为组合优化问题，不存在计算有效的最优算法，因此，基于简单易行、收敛速度快，全局搜索能力强的DCSA提出任务分配求解算法，以最小化工人的时间成本、初始成本以及惩罚成本。此外，在求解过程中，为进一步降低工人时间成本与惩罚成本，根据任务的时间窗大小以及任务离起始位置的距离，对任务进行优先级排序。仿真结果表明，与其他算法相比，基于DCSA改进的任务分配算法总成本更低，且有助于提高工人的参与积极性，同时有效地解决了时间浪费和任务过期问题。

参考文献

[1]GONG W， ZHANG B， LI C. Task assignment in mobile crowdsensing： present and future directions [J]. IEEE Network， 2018， 32（4）： 100-107.

[2]MANOLOPOULOS V， TAO S， RODRIGUEZ S， et al. MobiTraS： a mobile application for a smart traffic system [C] // Proceedings of the 2010 8th IEEE International NEWCAS Conference. Piscataway， NJ： IEEE， 2010： 365-368.

[3]MAISONNEUVE N， STEVENS M， NIESSEN M E， et al. NoiseTube： measuring and mapping noise pollution with mobile phones [M]// ATHANASIADIS I N， RIZZOLI A E， MITKAS P A， et al. Information Technologies in Environmental Engineering， Environment Science and Engineering. Berlin： Springer， 2009： 215-228.

[4]DUTTA P， AOKI P M， KUMAR N， et al. Common sense： participatory urban sensing using a network of handheld air quality monitors [C]// Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. New York： ACM， 2009： 349-350.

[5]CHENG P， LIAN X， CHEN L， et al. Prediction-based task assignment in spatial cowdsourcing [C]// ICDE 2017： Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2017：997-1008.

[6]WANG L， YANG D， HAN X， et al. Location privacy-preserving task allocation for mobile crowdsensing with differential geo-obfuscation [C]// Proceedings of the 26th International Conference on World Wide Web. Perth： International World Wide Web Conferences Steering Committee， 2017： 627-636.

[7]HU T， XIAO M， HU C， et al. A QoS-sensitive task assignment algorithm for mobile crowdsensing [J]. Pervasive and Mobile Computing， 2017， 41： 333-342.

[8]LUAN T， TO H， FAN L， et al. A real-time framework for task assignment in hyperlocal spatial crowdsourcing [J]. ACM Transactions on Intelligent Systems and Technology， 2017， 9（3）： 1-25.

[9]CHENG P， LIAN X， CHEN L， et al. Task assignment on multi-skill oriented spatial crowdsourcing [J]. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（8）： 2201-2215.

[10]MRS D S B， MRV S K， THANEERU L， et al. A survey on mobile crowd sensing using MCS task allocation [J]. International Journal of Research， 2017， 4（5）： 600-607.

[11]XIONG H， ZHANG D， CHEN G， et al. CrowdTasker： maximizing coverage quality in piggyback crowdsensing under budget constraint [C]// Proceedings of the 2015 IEEE International Conference on Pervasive Computing and Communications. Piscataway， NJ： IEEE， 2015： 55-62.

[12]CHEUNG M H， SOUTHWELL R， HOU F， et al. Distributed time-sensitive task selection in mobile crowdsensing [C]// Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM， 2015： 157-166.

CHEUNG M H， SOUTHWELL R， HOU F， et al. Distributed time-sensitive task selection in mobile crowdsensing [EB/OL]. [2019-01-07]. https：//arxiv.org/pdf/1503.06007v1.pdf.

[13]李洋，賈梦迪，杨文彦，等.基于树分解的空间众包最优任务分配算法[J].软件学报，2018，29（3）：824-838.（LI Y， JIA M D， YANG W Y， et al. Optimal task assignment algorithm based on tree-decouple in spatial crowdsourcing [J]. Journal of Software， 2018， 29（3）： 824-838.）

[14]WU S， GAO X， WU F， et al. A constant-factor approximation for bounded task allocation problem in crowdsourcing [C]// GLOBECOM 2017： Proceedings of the 2017 IEEE Global Communications Conference. Piscataway， NJ： IEEE， 2017： 1-6.

[15]YANG X-S， DEB S. Cuckoo search via Lévy flights [C]// NaBIC 2019： Proceedings of the 2009 World Congress on Nature and Biologically Inspired Computing. Piscataway， NJ： IEEE， 2009： 210-214.

[16]JATI G K， MANURUNG H M， SUYANTO. Discrete cuckoo search for traveling salesman problem [C]// ICCCT 2012： Proceedings of the 2012 7th International Conference on Computing and Convergence Technology. Piscataway， NJ： IEEE， 2012： 993-997.

[17]ZHENG H， ZHOU Y， LUO Q. A hybrid cuckoo search algorithm-GRASP for vehicle routing problem [J]. Journal of Convergence Information Technology， 2013， 8（3）： 821-828.

[18]张丽萍，柴跃廷，曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统，2002，8（6）：451-454.（ZHANG L P， CHAI Y T， CAO R. Improved genetic algorithm for vehicle routing problem with time windows [J]. Computer Integrated Manufacturing Systems， 2002， 8（6）：451-454.）

This work is partially supported by the Open Program of Meteorological Information and Signal Processing Key Laboratory of Sichuan Higher Education Institutes （QXXCSYS201704）， the Key Project of Sichuan Provincial Education Department （15CZ0004）.

YANG Zhengqing， born in 1994， M. S. candidate. Her research interests include mobile crowd sensing.

ZHOU Zhaorong， born in 1975， Ph. D.， associate professor. His research interests include wireless network.

YUAN Shu， born in 1995， M. S. candidate. Her research interests include spatial crowd sourcing.