CN109522107A - 一种面向时空约束的任务分配方法及系统 - Google Patents

Abstract

一种通过多个移动终端采集数据的面向时空约束的任务分配方法及系统，该方法包括：任务请求者向云平台提交任务需求；多个用户通过各自的移动终端向云平台提交数据；云平台根据所述任务需求和各个移动终端提交上来的自身数据进行初步任务分配；云平台根据所述初步任务分配的结果，规划每个用户执行任务的顺序，把该顺序发送给用户；所述多个用户依据所规划的顺序，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；云平台将上述回传的数据传输给所述任务请求者。根据所述方法，即满足了任务的时空约束需求又通过计算为用户合理规划了所选择任务集合。

Description

一种面向时空约束的任务分配方法及系统

技术领域

本公开属于信息技术领域，特别涉及一种通过多个移动终端采集数据的面向时空约束的任务分配方法及系统。

背景技术

近年来，随着移动计算和无线通信技术的快速发展，移动智能设备(如智能手机、平板电脑、智能手表等)得到广泛普及，其存储、计算、通信能力得到不断加强，并配备了众多智能传感器，比如摄像头、麦克风、重力仪、GPS、陀螺仪、温度传感器、血压传感器等等。这使得人们通过移动智能设备可以自动、实时地感知和收集周围环境信息，并通过无线通信模块将信息传输到服务器，如云平台，从而可以完成复杂的环境和社会感知任务。云平台需要根据任务请求者的任务需求，将各个任务分配给参与的众多用户，分配的依据是实现特定的优化目标，如最大化任务接收率等。

从目前的研究成果上看，当前任务分配方法只从单一角度考虑任务需求，如任务感知时间长度、任务的地理位置、任务类型和用户能力需求，尚未综合考虑任务的弹性时空约束，比如最早开始时间、最迟结束时间、感知时间长度、地理位置需求，以及用户的实时位置。事实上，随着移动群体感知应用的不断发展和深入，具有综合需求的复杂任务尤其是弹性时空约束的任务越来越受到人们的关注。一个弹性时空约束的任务是指一个感知任务需要用户在某个区域内在某段时间内完成，且对任务的地理区域、最早开始时间、最迟开始时间、感知时间长度均有规定。更为困难的是，一个用户往往被分配多个任务，而每个任务均有上述时间空间约束，因此需要用户对所有分配的任务的执行顺序进行规划，此时需要进一步考虑用户完成任务的代价以及用户移动所产生的代价，这进一步增加了问题的难度。

为了保证任务的时空约束得到满足，同时也为了能够合理规划分配给用户的各任务的执行顺序，设计一种通过多个移动终端采集数据的面向时空约束的任务分配方法是十分必要的。

发明内容

鉴于此，本公开提供了一种通过多个移动终端采集数据的面向时空约束的任务分配方法，包括如下步骤：

S100：任务请求者向云平台提交任务需求，包括任务位置、最早开始时间、最迟结束时间、感知时间长度以及任务预算；

S200：多个用户通过各自的移动终端向云平台提交各自的位置以及最晚工作时间；

S300：云平台根据所述任务需求和各个移动终端提交上来的自身数据进行初步任务分配；

S400：云平台根据所述初步任务分配的结果，规划每个用户执行任务的顺序，把该顺序发送给用户；

S500：所述多个用户依据所规划的顺序，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

S600：云平台将上述回传的数据传输给所述任务请求者。

本公开还提供了一种通过多个移动终端采集数据的面向时空约束的任务分配系统，包括任务请求者、云平台和多个用户，其中，

所述任务请求者向所述云平台提交任务需求，包括任务位置、最早开始时间、最迟结束时间、感知时间长度以及任务预算；

所述多个用户通过各自的移动终端向云平台提交各自的位置及最晚工作时间；

所述云平台根据所述任务需求和各个移动终端提交上来的自身数据进行初步任务分配；

云平台根据所述初步任务分配的结果，规划每个用户执行任务的顺序，把该顺序发送给用户；

所述多个用户依据所规划的顺序，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

云平台将上述回传的数据传输给所述任务请求者。

通过上述技术方案，本公开的方法和系统能够通过计算保证任务的时空约束得到满足，进一步扩展了方法的应用范围。同时，本公开的方法和系统相对于传统方法和系统，增加了为用户进行任务规划的步骤，通过对任务集合进行规划，使得任务的执行更加合理，提高了效率。

附图说明

图1是本公开一个实施例中所提供的一种通过多个移动终端采集数据的面向时空约束的任务分配方法的流程示意图；

图2是本公开一个实施例中所提供的一种通过多个移动终端采集数据的面向时空约束的任务分配系统的结构示意图。

具体实施方式

参见图1，在一个实施例中，本公开提供了一种通过多个移动终端采集数据的面向时空约束的任务分配方法，包括如下步骤：

S100：任务请求者向云平台提交任务需求，包括任务位置、最早开始时间、最迟结束时间、感知时间长度以及任务预算；

S200：多个用户通过各自的移动终端向云平台提交各自的位置以及最晚工作时间；

S300：云平台根据所述任务需求和各个移动终端提交上来的自身数据进行初步任务分配；

S400：云平台根据所述初步任务分配的结果，规划每个用户执行任务的顺序，把该顺序发送给用户；

S500：所述多个用户依据所规划的顺序，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

S600：云平台将上述回传的数据传输给所述任务请求者。

就该实施例而言，即保证了任务的时空约束得到满足，又通过计算为用户选择可执行的任务集合并规划所选择任务集合，从而扩大了本方法的应用范围。

在另一个实施例中，所述步骤S100还进一步包括如下步骤：

所述任务需求用集合S＝{s₁，s₂，...，s_i，...，s_n}表示，其中s_i是第i个任务，n为一个有限的自然数，表示任务s_i的位置，表示任务s_i的最早开始时间，表示任务s_i的最迟结束时间，表示任务s_i的感知时间长度， 表示任务s_i的预算。

就该实施例而言，将任务需求采用集合的形式进行表示有助于后面分配方法的建模。

在另一个实施例中，所述步骤S200还进一步包括如下步骤：

所述多个用户以集合U＝{u₁，u₂，...，u_j...，u_k}表示，其中，u_j是第j位用户，k为一个有限的自然数，表示用户u_j的位置，表示用户的最晚工作时间。

就该实施例而言，将多个用户采用集合的形式进行表示有助于后面分配方法的建模。

在另一个实施例中，所述步骤S300还进一步包括如下步骤：

所述初步任务分配按照以下公式计算：

其中，c_ij表示用户u_j执行任务s_i的代价，d_ij表示用户u_j移动到任务s_i所要求的位置而产生的代价，

所述多个用户以集合U＝{u₁，u₂，...，u_j...，u_k}表示，其中，u_j是第j位用户，k为一个有限的自然数，表示用户u_j的位置，表示用户的最晚工作时间；

所述任务需求用集合S＝{s₁，s₂，...，s_i，...，s_n}表示，其中s_i是第i个任务，n为一个有限的自然数，表示任务s_i的位置，表示任务s_i的最早开始时间，表示任务s_i的最迟结束时间，表示任务s_i的感知时间长度， 表示任务s_i的预算；

x_ij＝1表示将任务s_i分配给用户u_j，x_ij＝0则表示不将任务s_i分配给用户u_j；

表示用户u_j到达每个任务s_i(s_i∈S)的时间。

目标函数的目标是最大化收益，即为所有任务的预算之和与所有任务分配所产生代价之和的差值。一个任务分配(用户u_j被分配执行任务s_i)所产生的代价包括两部分：用户u_j执行任务s_i的代价c_ij，用户u_j移动到任务s_i所要求的位置而产生的代价d_ij，

条件1表示一个任务只能由一个用户完成；条件2中x_ij＝1表示将任务s_i分配给用户u_j，反之，x_ij＝0则表示不将任务s_i分配给用户u_j；条件3表示分配给用户u_j的任务最迟结束时间不超过该用户的最晚工作时间；条件4表示用户u_j到任务s_i的时间不超过该任务的最晚开始时间；条件5表示用户执行任务的代价和用户移动到任务所在位置产生的代价之和不超过该任务的预算。

用户u_j执行任务s_i的收益记为w_ij，它的公式表示：w_ij＝b_i-(c_ij+d_ij)。

表示用户u_j的位置坐标，表示任务s_i的位置坐标，两者之间的空间距离表示：用户u_j从它的位置移动到任务s_i位置所带来的移动代价d_ij可以用以下函数定义：

d_ij＝f(s_ij)。

就该实施例而言，通过建模来实现任务分配方法。

在另一个实施例中，所述步骤S300还进一步包括如下步骤：

步骤301：令集合S′表示待分配的任务集合，初始时S′＝S；令U′表示可以选用的用户集合，初始时U′＝U，集合U⁺表示执行任务的用户集合，初始用户u_j(u_j∈U′)分配的任务集合表示为初始

步骤302：按照公式计算所有任务s_i(s_i∈S′)的最晚开始时间，找一个最晚开始时间最小的任务s_i，从用户集合U′找出执行任务s_i总收益最大的用户u_j；

步骤303：判断用户u_j执行任务s_i是否满足三个约束条件：

公式(1)表示u_j执行任务s_i的总代价不超过任务s_i的预算；公式(2)表示任务s_i的最迟结束时间不超过用户u_j的最晚工作时间公式(3)表示用户u_j到任务s_i的时间不超过该任务的最晚开始时间

若以上三个约束条件均成立，就转向步骤304；若是其中一个条件不满足在集合S′删除任务s_i，则转向步骤302；

步骤304：云平台将任务s_i分配给用户u_j，即令x_ij＝1，在集合S′删除任务s_i，更新用户u_j的已分配任务集合如果集合U⁺不存在用户u_j将其添加到集合U⁺；如果集合S′不为空，则转向步骤302；否则转向步骤S400。

就该实施例而言，给出了一种模型的求解方式，即从寻找开始时间最小的任务，找出执行该任务的总收益最大的用户，将满足条件的任务分配给该用户，循环了所有的任务之后，初步任务分配即完成。

在另一个实施例中，所述步骤S400还进一步包括如下步骤：

步骤401：按照公式计算用户u_j到任务集合中每个任务的距离s_ij，其中是其分配的任务集合；令T_j表示用户u_j所分配任务的执行顺序，T_j可用一个有序线性表描述，初始为空；表示用户u_j的位置坐标，表示任务s_i的位置坐标；

步骤402：选择距离用户u_j最短的任务，记为s_i，将任务s_i插入到线性表T_j中，并更新用户u_j的已分配任务集合，为

步骤403：选择下一个任务使其中任务s_i是线性表T_j的最后一个元素，

其中公式(4)中的s_ij指的是用户u_j到线性表T_j中第一个元素s_i的距离；指的是任务s_i和任务之间的时空距离，w₁，w₂为权重系数，满足w₁+w₂＝1，w₁≥0，w₂≥0，取w₁＝0.5，w₂＝0.5，指的是任务s_i和任务之间的空间距离，指的是任务s_i和任务之间的时间距离；

若满足公式(4)和公式(5)，任务是任务s_i到用户u_j的剩余分配任务的距离最短的任务，将任务插入到线性表T_j中最后一个元素之后，并更新用户u_j的已分配任务集合，为如果不为空，找下一个任务到线性表T_j中最后一个元素的时空距离最短；否则放弃任务转到步骤403；

步骤404：求得从用户u_j到达任务集合中所有任务的路径规划，该路径规划是一个依次按时空距离递增的序列；删除U⁺中的用户u_j，若U⁺不为空集，转向步骤401。

就该实施例而言，给出了一种任务执行顺序的规划方法，即依次按时空距离递增的顺序规划任务的执行顺序，通过该种规划方法，可以为用户选择可执行的任务集合并合理规划所选择任务集合的顺序。

在另一个实施例中，所述步骤S403中的时间距离的计算如下：

一个用户依次服务任务s_i和任务任务s_i和任务的时间窗分别为且满足否则任务过期；当两个时间窗口有重叠，则认为这两个任务在相同的时间段内被服务，其时间窗距离为0，如果不重叠，则时间窗距离为后一时间窗的开始时间减去前一时间窗的结束时间，计算公式如下：

其中，为后一任务的结束时间，为前一任务s_i的开始时间。

在另一个实施例中，所述用户u_j到达每个任务s_i(s_i∈S)的时间定义如下：

其中，v表示所有用户u_j∈U的速度，s_ij表示用户到任务s_i的空间距离。

在另一个实施例中，用户执行任务的代价和任务的感知时间长度有关。

就该实施例而言，通常，任务的感知时间长度越大，代价也就越大，一种简单的策略是定义用户执行任务的代价为任务的感知时间长度的函数：

用户u_j到达每个任务s_i(s_i∈S)的时间可以通过以下公式定义：

其中v表示所有用户u_j∈U的速度，s_ij表示用户到任务s_i的空间距离。

在另一个实施例中，参见图2，公开了一种通过多个移动终端采集数据的面向时空约束的任务分配系统，包括任务请求者、云平台和多个用户，其中，

所述任务请求者向所述云平台提交任务需求，包括任务位置、最早开始时间、最迟结束时间、感知时间长度以及任务预算；

所述多个用户通过各自的移动终端向云平台提交各自的位置及最晚工作时间；

所述云平台根据所述任务需求和各个移动终端提交上来的自身数据进行初步任务分配；

云平台根据所述初步任务分配的结果，规划每个用户执行任务的顺序，把该顺序发送给用户；

所述多个用户依据所规划的顺序，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

云平台将上述回传的数据传输给所述任务请求者。

就该实施例而言，该系统即保证了任务的时空约束得到满足，又通过计算为用户选择可执行的任务集合并规划所选择任务集合，进而可以提高用户的参与积极性。

在另一个实施例中，

步骤S100：任务请求者提交的任务集合表示为S＝{s₁，s₂，s₃，s₄}，任务的属性如下表所示：

任务	位置	最早开始时间	最迟结束时间	感知时间长度	预算
						s<sub>1</sub>	(2，6)	1	5	2	10
s<sub>2</sub>	(3，5)	6	13	5	20
						s<sub>3</sub>	(4，6)	2	10	6	10
s<sub>4</sub>	(5，8)	11	20	8	20

步骤S200：收集到的用户集合为U＝{u₁，u₂}，u₁＝<(3，4)，18>，u₂＝<(5，6)，20>，其中u₁的第一个属性(3，4)表示用户的位置，18表示该用户的最晚工作时间。

步骤S300：按照公式(c_ij+d_ij)计算出用户集合中各个用户u₁，u₂执行任务s₁，s₂，s₃，s₄的总代价，其中c_ij指的是用户执行任务的代价，本实施例中d_ij指的是用户u_j从它的位置移动到任务s_i位置所带来的移动代价，本实施例中d_ij＝f(s_ij)＝0.5×s_ij，其中(x_i，y_i)，(x_j，y_j)分别为任务s_i和用户u_j的位置。

计算出的用户集合中各个用户u₁，u₂执行任务s₁，s₂，s₃，s₄的总代价的值用矩阵(a)表示：

按照公式w_ij＝b_i-(c_ij+d_ij)计算用户u_j执行任务s_i的收益记为w_ij，则

用户集合各个用户u₁，u₂执行任务s₁，s₂，s₃，s₄的收益的结果用矩阵(b)表示：

步骤301：令集合S′表示待分配的任务集合，初始时S′＝S。令U′表示可以选用的用户集合，初始时U′＝U，集合U⁺表示执行任务的用户集合，初始用户u_j(u_j∈U′)分配的任务集合表示为初始

步骤302：按照公式计算所有任务s_i(s_i∈S′)的最晚开始时间，计算出所有任务s₁，s₂，s₃，s₄的最晚开始时间分别为3，8，4，12，首先为最晚开始时间最小的任务s₁选择用户，从用户集合U′中执行所有任务收益的矩阵中可以得出用户u₁执行任务s₁的收益大于用户u₂执行任务s₁的收益，所以考虑用户u₁执行任务s₁。

步骤303：判断用户u₁执行任务s₁是否满足三个约束条件：可得即2.12≤10；即5≤18，即2.24≤3，约束条件成立，转向步骤304。

步骤304：云平台将任务s₁分配给用户u₁，即令x₁₁＝1，在集合S′删除任务s₁，将用户u₁添加到集合U⁺，更新用户u₁的已分配任务集合集合S′不为空，则转向步骤302。

步骤302：按照公式计算所有任务s_i(s_i∈S′)的最晚开始时间，计算任务s₂，s₃，s₄的最晚开始时间分别为8，4，12，为最晚开始时间最小的任务s₃选择用户，从用户集合U′中执行所有任务收益的矩阵中可以得出用户u₂执行任务s₃的收益大于用户u₁执行任务s₃的收益，所以考虑u₂执行任务s₃。

步骤303：判断u₂执行任务s₃是否满足三个约束条件：可得即3.5≤10；即10≤20，即1≤4，约束条件成立，转向步骤304。

步骤304：云平台将任务s₃分配给用户u₂，即令x₃₂＝1，在集合S′删除任务s₃，将用户u₂添加到集合U⁺，更新用户u₂的已分配任务集合集合S′不为空，则转向步骤302。

在步骤302：按照公式计算所有任务s_i(s_i∈S′)的最晚开始时间，计算所有任务s₂，s₄的最晚开始时间分别为8，12，为最晚开始时间最小的任务s₂选择用户，从用户集合U′中执行所有任务收益的矩阵中可以得出用户u₁执行任务s₂的收益大于用户u₂执行任务s₂的收益，所以考虑用户u₁执行任务s₂。

在步骤303：判断用户u₁执行任务s₂是否满足三个约束条件：可得即2.5≤20；即13≤18，即1≤9，约束条件成立，转向步骤304。用户u₁执行任务s₂满足三个约束条件。

步骤304：云平台可以将任务s₂分配给用户u₁，即令x₂₁＝1，在集合S′删除任务s₂，因为集合U⁺存在用户u₁，更新用户u₁的已分配任务集合集合S′不为空，则转向步骤302。

在步骤302：按照公式计算所有任务s_i(s_i∈S′)的最晚开始时间，计算任务s₄的最晚开始时间分别为12，为最后一个任务s₄选择用户，从用户集合U′中执行所有任务收益的矩阵可以得出用户u₂执行任务s₄的收益大于用户u₁执行任务s₄的收益，所以考虑用户u₂执行任务s₄。

在步骤303：判断用户u₂执行任务s₄是否满足三个约束条件：可得即5≤20；即20≤20，即2≤12，约束条件成立，转向步骤304。

步骤304：云平台可以将任务s₄分配给用户u₂，即令x₄₂＝1，在集合S′删除任务s₄，因为集合U⁺存在用户u₂，更新用户u₂的已分配任务集合集合S′为空，则转向步骤S400。

所有任务分配结束后，U⁺＝{u₁，u₂}，用户u₁的已分配任务集合记为 用户u₂的已分配任务集合记为

步骤S400云平台为每一个已分配任务的用户规划任务执行顺序，进一步包括如下步骤。

步骤401：按照公式计算用户u₁到任务集合中每个任务的距离s_ij，其中 是其分配的任务集合，求得s₁₁＝2.24，s₂₁＝1。令T₁表示用户u₁所分配任务的执行顺序，T₁可用一个有序线性表描述，初始为空。

步骤402：选择距离用户u₁最短的任务为s₂，将任务s₂插入到T₁中，并更新用户u₁的已分配任务集合，为

步骤403：因为用户u₁任务列表只有两个元素，任务s₂是当前T₁的最后一个元素，所以考虑选择用户u₁任务集合中的最后一个任务s₁。

因为任务s₁的时间窗为[1，5]，任务s₂时间窗为[6，13]，在计算过程中发现用户u₁执行任务s₂结束后在执行任务s₁时，因为任务s₂的开始时间大于任务s₁的开始时间，所以任务s₁已经过期。所以用户u₁必须放弃任务s₁，u₁的所分配任务的执行顺序的线性表T₁＝(s₂)。

步骤401：按照公式计算用户u₂到任务集合中每个任务的距离s_ij，其中为求得s₃₂＝1，s₄₂＝2。令T₂表示用户u₂所分配任务的执行顺序，T₂可用一个线性表描述，初始为空。

步骤402：选择距离用户u₂最短的任务为s₃，将任务s₃插入到T₂中，并更新用户u₂的已分配任务集合，为

步骤403：因为用户u₂任务列表只有两个元素，任务s₃是当前T₂的最后一个元素，所以考虑选择用户u₂任务集合中的最后一个任务s₄。

按照空间距离计算得出s₃₄＝2.24，s₃₂＝1，按照时间距离公式计算得出T₃₄＝1，w₁s₃₄+w₂T₃₄＝1.62，

计算公式(4)得出，(1+1.62)/1＝2.62，因为2.62≤20(用户u₂的最晚工作时间)，计算公式(5)得出，1.62/1＝1.62≤4(任务的最晚开始时间)。

任务s₄满足上述这两个条件，将任务s₄插入到线性表T₂中最后一个元素(也就是任务s₃)之后，并更新用户u₂的已分配任务集合，为u₂的所分配任务的执行顺序的线性表T₂＝(s₃，s₄)。

步骤404：所有用户路径规划结束后，u₁的所分配任务的执行顺序的线性表T₁＝(s₂)；u₂的所分配任务的执行顺序的线性表T₂＝(s₃，s₄)。

S500：u₁根据T₁＝(s₂)，u₂根据T₂＝(s₃，s₄)，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

S600：云平台将上述回传的数据传输给所述任务请求者。

在另一个实例中：

步骤S100：任务请求者提交的任务集合表示为S＝{s₁，s₂，s₃，s₄，s₅}，任务的属性如下表所示：

任务	位置	最早开始时间	最迟结束时间	感知时间长度	预算
						s<sub>1</sub>	(2，3)	3	7	3	10
s<sub>2</sub>	(3，6)	2	5	2	20
						s<sub>3</sub>	(2，5)	6	11	5	10
s<sub>4</sub>	(4，6)	14	22	14	20
						s<sub>5</sub>	(4，8)	4	13	6	10

步骤S200：收集到的用户集合为U＝{u₁，u₂}，u₁＝<(3，4)，25>，u₂＝<(4，5)，30>，其中u₁的第一个属性(3，4)表示用户的位置，25表示该用户的最晚工作时间。

步骤S300：按照公式(c_ij+d_ij)计算出用户集合中各个用户u₁，u₂执行任务s₁，s₂，s₃，s₄，s₅的总代价，其中c_ij指的是用户执行任务的代价，本实施例中d_ij指的是用户u_j从它的位置移动到任务s_i位置所带来的移动代价，本实施例中d_ij＝f(s_ij)＝0.5×s_ij，其中(x_i，y_i)，(x_j，y_j)分别为任务s_i和用户u_j的位置。

计算出的用户集合中各个用户u₁，u₂执行任务s₁，s₂，s₃，s₄，s₅的总代价的值用矩阵(a)表示：

按照公式w_ij＝b_i-(c_ij+d_ij)计算用户u_j执行任务s_i的收益记为w_ij，则

用户集合各个用户u₁，u₂执行任务s₁，s₂，s₃，s₄，s₅的收益的结果用矩阵(b)表示：

步骤301：令集合S′表示待分配的任务集合，初始时S′＝S。令U′表示可以选用的用户集合，初始时U′＝U，集合U⁺表示执行任务的用户集合，初始用户u_j(u_j∈U′)分配的任务集合表示为初始

步骤302：按照计算所有任务s_i(s_i∈S′)的最晚开始时间，计算所有任务s₁，s₂，s₃，s₄，s₅的最晚开始时间分别为4，3，6，8，7，首先为最晚开始时间最小的任务s₂选择用户，从用户集合U′中执行所有任务收益的矩阵中可以得出用户u₁执行任务s₂的收益大于用户u₂执行任务s₂的收益。所以先考虑用户u₁执行任务s₂。

步骤303：判断用户u₁执行任务s₂是否满足三个约束条件：可得即2.91≤20；即5≤25，即1≤3，约束条件成立，转向步骤304。

步骤304：云平台可以将任务s₂分配给用户u₁，即令x₂₁＝1，在集合S′删除任务s₂，将用户u₁添加到集合U⁺，更新用户u₁的已分配任务集合集合S′不为空，则转向步骤302。

步骤302：按照计算所有任务s_i(s_i∈S′)的最晚开始时间，计算所有任务s₁，s₃，s₄，s₅的最晚开始时间分别为4，6，8，7，为最晚开始时间最小的任务s₁选择用户，从用户集合U′中执行所有任务收益的矩阵中可以得出用户u₁执行任务s₁的收益大于用户u₂执行任务s₁的收益，所以考虑用户u₁执行任务s₁。

步骤303：判断用户u₁执行任务s₁是否满足三个约束条件：可得即2≤10；即7≤25，即1.41≤4，约束条件成立，转向步骤304。

步骤304：云平台可以将任务s₁分配给用户u₁，即令x₁₁＝1，在集合S′删除任务s₁，因为集合U⁺存在用户u₁，更新用户u₁的已分配任务集合集合S′不为空，则转向步骤302。

步骤302：按照计算所有任务s_i(s_i∈S′)的最晚开始时间，计算所有任务s₃，s₄，s₅的最晚开始时间分别为6，8，7，为最晚开始时间最小的任务s₃选择用户，从用户集合U′中执行所有任务收益的矩阵中可以得出用户u₁执行任务s₃的收益大于用户u₂执行任务s₃的收益。所以先考虑用户u₁执行任务s₃。

步骤303：判断用户u₁执行任务s₃是否满足三个约束条件：可得即3.9l≤10；即11≤25，即1.41≤6，约束条件成立，转向步骤304。

步骤304：云平台可以将任务s₃分配给用户u₁，即令x₃₁＝1，在集合S′删除任务s₃，因为集合U⁺存在用户u₁，更新用户u₁的已分配任务集合集合S′不为空，则转向步骤302。

步骤302：按照计算所有任务s_i(s_i∈S′)的最晚开始时间，计算任务s₄，s₅的最晚开始时间分别为8，7，为最晚开始时间最小的任务s₅选择用户，从用户集合U′中执行所有任务收益的矩阵中可以得出用户u₂执行任务s₅的收益大于用户u₁执行任务s₅的收益。所以考虑用户u₂完成任务s₅。

步骤303：判断用户u₂执行任务s₅是否满足三个约束条件：可得即6≤10；即16≤30，即3≤7，约束条件成立，转向步骤304。

步骤304：云平台可以将任务s₅分配给用户u₂，即令x₅₂＝1，在集合S′删除任务s₅，将用户u₂添加到集合U⁺，更新用户u₂的已分配任务集合集合S′不空，则转向步骤302。

步骤302：按照计算所有任务s_i(s_i∈S′)的最晚开始时间，计算任务s₄的最晚开始时间分别为8，为最后一个任务s₄选择用户，从用户集合U′中执行所有任务收益的矩阵可以得出用户u₂执行任务s₄的收益大于用户u₁执行任务s₄的收益，所以考虑用户u₂完成任务s₄。

步骤303：判断用户u₂执行任务s₄是否满足三个约束条件：可得即8≤20；即22≤30，即1≤8，约束条件成立，转向步骤304。

步骤304：云平台可以将任务s₄分配给用户u₂，即令x₄₂＝1，在集合S′删除任务s₄，因为集合U⁺存在用户u₂，更新用户u₁的已分配任务集合则转向步骤S400。

所有任务分配结束后，U⁺＝{u₁，u₂}，用户u₁的任务集合记为 用户u₂的任务集合记为

在步骤S400云平台为每一个已分配任务的用户规划任务执行顺序，进一步包括如下步骤。

步骤401：按照公式计算用户u₁到任务集合中每个任务的距离s_ij，其中为是其分配的任务集合，求得s₁₁＝1.41，s₂₁＝1，s₃₁＝1.41。令线性表T₁表示用户u₁所分配任务的执行顺序，初始为空。

步骤402：选择距离用户u₁最短的任务为s₂，将任务s₂插入到线性表T₁中，并更新用户u₁的已分配任务集合，为

步骤403：因为用户u₁任务列表有三个元素，任务s₂是当前线性表T₁的最后一个元素，选择下一个任务使得

按照空间距离计算得出s₂₁＝3.16，s₂₃＝1.41，按照时间距离公式计算得出T₂₁＝0，T₂₃＝l，w₁s₂₁+w₂T₂₁＝1.58，w₁s₂₃+w₂T₂₃＝1.21，因为1.58＞1.21，所以考虑任务s₃作为线性表T₁中的任务s₂的下一个任务，

如果

计算得出任务s₃满足上面两个公式，所以将任务s₃插入到线性表T₁中最后一个元素(也就是任务s₂)之后，并更新用户u₁的已分配任务集合，为

考虑任务s₃之后的下一个任务，因为中仅剩下任务s₁，所以直接计算w₁s₃₁+w₂T₃₁，但是发现用户u₁执行任务s₃结束后在执行任务s₁时，任务s₁已经过期。所以用户u₁必须放弃掉任务s₁，u₁的所分配任务的执行顺序的线性表T₁＝(S₂，S₃)。

步骤401：按照公式如计算用户u₂到任务集合中每个任务的距离s_ij，其中为是其分配的任务集合，求得s₄₂＝1，s₅₂＝3。令线性表T₂表示用户u₂所分配任务的执行顺序，初始为空。

步骤402：选择距离用户u₂最短的任务为s₄，将任务s₄插入到线性表T₂中，并更新用户u₂的已分配任务集合，为

步骤403：因为用户u₂任务列表只有两个元素，任务s₄是当前线性表T₂的最后一个元素，考虑任务s₅，计算w₁s₄₅+w₂T₄₅，但是发现用户u₂执行任务s₄结束后在执行任务s₅时，任务s₅已经过期。所以用户u₂必须放弃掉任务s₅，u₂的所分配任务的执行顺序的线性表T₂＝(s₄)。

步骤404：所有用户路径规划结束后，u₁的所分配任务的执行顺序的线性表T₁＝(s₂，s₃)；u₂的所分配任务的执行顺序的线性表T₂＝(s₄)。

S500：u₁根据T₁＝(s₂，s₃)，u₂根据T₂＝(s₄)，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

S600：云平台将上述回传的数据传输给所述任务请求者。

以上对本公开进行了详细介绍，本文中应用了具体个例对本公开的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本公开的方法及其核心思想；同时，对于本领域技术人员，依据本公开的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本公开的限制。

Claims (10)

1.一种通过多个移动终端采集数据的面向时空约束的任务分配方法，包括如下步骤：

S100：任务请求者向云平台提交任务需求，包括任务位置、最早开始时间、最迟结束时间、感知时间长度以及任务预算；

S200：多个用户通过各自的移动终端向云平台提交各自的位置以及最晚工作时间；

S300：云平台根据所述任务需求和各个移动终端提交上来的自身数据进行初步任务分配；

S400：云平台根据所述初步任务分配的结果，规划每个用户执行任务的顺序，把该顺序发送给用户；

S500：所述多个用户依据所规划的顺序，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

S600：云平台将上述回传的数据传输给所述任务请求者。

2.根据权利要求1的方法，优选的，所述步骤S100还进一步包括如下步骤：

所述任务需求用集合S＝{s₁，s₂，...，s_i，...，s_n}表示，其中s_i是第i个任务，n为一个有限的自然数，表示任务s_i的位置，表示任务s_i的最早开始时间，表示任务s_i的最迟结束时间，表示任务s_i的感知时间长度， 表示任务s_i的预算。

3.根据权利要求1的方法，所述步骤S200还进一步包括如下步骤：

所述多个用户以集合U＝{u₁，u₂，...，u_j...，u_k}表示，其中，u_j是第j位用户，k为一个有限的自然数，表示用户u_j的位置，表示用户的最晚工作时间。

4.根据权利要求1的方法，所述步骤S300还进一步包括如下步骤：

所述初步任务分配按照以下公式计算：

s.t.1.

2.

3.

4.

5.

其中，c_ij表示用户u_j执行任务s_i的代价，d_ij表示用户u_j移动到任务s_i所要求的位置而产生的代价，

所述多个用户以集合U＝{u₁，u₂，...，u_j...，u_k}表示，其中，u_j是第j位用户，k为一个有限的自然数，表示用户u_j的位置，表示用户的最晚工作时间；

所述任务需求用集合S＝{s₁，s₂，...，s_i，...，s_n}表示，其中s_i是第i个任务，n为一个有限的自然数，表示任务s_i的位置，表示任务s_i的最早开始时间，表示任务s_i的最迟结束时间，表示任务s_i的感知时间长度， 表示任务s_i的预算；

x_ij＝1表示将任务s_i分配给用户u_j，x_ij＝0则表示不将任务s_i分配给用户u_j；

表示用户u_j到达每个任务s_i(s_i∈S)的时间。

5.根据权利要求4的方法，所述步骤S300还进一步包括如下步骤：

步骤301：令集合S′表示待分配的任务集合，初始时S′＝S；令U′表示可以选用的用户集合，初始时U′＝U，集合U⁺表示执行任务的用户集合，初始用户u_j(u_j∈U′)分配的任务集合表示为初始

步骤302：按照公式计算所有任务s_i(s_i∈S′)的最晚开始时间，找一个最晚开始时间最小的任务s_i，从用户集合U′找出执行任务s_i总收益最大的用户u_j；

步骤303：判断用户u_j执行任务s_i是否满足三个约束条件：

公式(1)表示u_j执行任务s_i的总代价不超过任务s_i的预算；公式(2)表示任务s_i的最迟结束时间不超过用户u_j的最晚工作时间公式(3)表示用户u_j到任务s_i的时间不超过该任务的最晚开始时间

若以上三个约束条件均成立，就转向步骤304；若是其中一个条件不满足在集合S′删除任务s_i，则转向步骤302；

步骤304：云平台将任务s_i分配给用户u_j，即令x_ij＝1，在集合S′删除任务s_i，更新用户u_j的已分配任务集合如果集合U⁺不存在用户u_j将其添加到集合U⁺；如果集合S′不为空，则转向步骤302；否则转向步骤S400。

6.根据权利要求1的方法，所述步骤S400还进一步包括如下步骤：

步骤401：按照公式计算用户u_j到任务集合中每个任务的距离s_ij，其中是其分配的任务集合；令T_j表示用户u_j所分配任务的执行顺序，T_j可用一个有序线性表描述，初始为空；表示用户u_j的位置坐标，表示任务s_i的位置坐标；

集合U⁺表示执行任务的用户集合；

所述多个用户以集合U＝{u₁，u₂，...，u_j...，u_k}表示，其中，u_j是第j位用户，k为一个有限的自然数，表示用户u_j的位置，表示用户的最晚工作时间；

所述任务需求用集合S＝{s₁，s₂，...，s_i，...，s_n}表示，其中s_i是第i个任务，n为一个有限的自然数，表示任务s_i的位置，表示任务s_i的最早开始时间，表示任务s_i的最迟结束时间，表示任务s_i的感知时间长度， 表示任务s_i的预算；

步骤402：选择距离用户u_j最短的任务，记为s_i，将任务s_i插入到线性表T_j中，并更新用户u_j的已分配任务集合，为

步骤403：选择下一个任务使其中任务s_i是线性表T_j的最后一个元素，

其中公式(4)中的s_ij指的是用户u_j到线性表T_j中第一个元素s_i的距离；指的是任务s_i和任务之间的时空距离，w₁，w₂为权重系数，满足w₁+w₂＝1，w₁≥0，w₂≥0，取w₁＝0.5，w₂＝0.5，指的是任务s_i和任务之间的空间距离，指的是任务s_i和任务之间的时间距离；

若满足公式(4)和公式(5)，任务是任务s_i到用户u_j的剩余分配任务的距离最短的任务，将任务插入到线性表T_j中最后一个元素之后，并更新用户u_j的已分配任务集合，为如果不为空，找下一个任务到线性表T_j中最后一个元素的时空距离最短；否则放弃任务转到步骤403；

步骤404：求得从用户u_j到达任务集合中所有任务的路径规划，该路径规划是一个依次按时空距离递增的序列；删除U⁺中的用户u_j，若U⁺不为空集，转向步骤401。

7.根据权利要求6的方法，所述步骤S403中的时间距离的计算如下：

一个用户依次服务任务s_i和任务任务s_i和任务的时间窗分别为且满足否则任务过期；当两个时间窗口有重叠，则认为这两个任务在相同的时间段内被服务，其时间窗距离为0，如果不重叠，则时间窗距离为后一时间窗的开始时间减去前一时间窗的结束时间，计算公式如下：

其中，为后一任务的结束时间，为前一任务s_i的开始时间。

8.根据权利要求4的方法，所述用户u_j到达每个任务s_i(s_i∈S)的时间定义如下：

其中，v表示所有用户u_j∈U的速度，s_ij表示用户到任务s_i的空间距离。

9.根据权利要求4的方法，用户执行任务的代价和任务的感知时间长度有关。

10.一种通过多个移动终端采集数据的面向时空约束的任务分配系统，包括任务请求者、云平台和多个用户，其中，

所述任务请求者向所述云平台提交任务需求，包括任务位置、最早开始时间、最迟结束时间、感知时间长度以及任务预算；

所述多个用户通过各自的移动终端向云平台提交各自的位置及最晚工作时间；

所述云平台根据所述任务需求和各个移动终端提交上来的自身数据进行初步任务分配；

云平台根据所述初步任务分配的结果，规划每个用户执行任务的顺序，把该顺序发送给用户；

所述多个用户依据所规划的顺序，利用其携带的移动终端采集相应的数据，并回传所采集的数据给云平台；

云平台将上述回传的数据传输给所述任务请求者。