一种基于工人偏好感知的空间众包任务分配方法

摘要

本发明公开了一种基于工人偏好感知的空间众包任务分配方法，首先用一个三维张量对不同工人在不同时间段对于不同类别的任务的偏好进行建模，利用工人的任务执行历史记录和两个上下文矩阵，采用基于历史数据的上下文感知张量分解算法来补充缺失的张量数据，获得工人在不同时间段对于不同类别任务的偏好值；然后在每个时刻设计了三种偏好感知的任务分配算法，针对同一个任务优先考虑偏好值大的工人，最终实现全局任务分配数量最大化。

说明书

技术领域

本发明属于空间众包技术领域，具体涉及一种基于工人偏好感知的空间众包任务分配方法的设计。

背景技术

空间众包(Spatial Crowdsourcing，SC)是指将携带智能设备的人当作工人，让他们移动到特定的地点并完成空间任务，例如拍照、监控交通状况，以及报告当地的热点等。

现有对于空间众包的研究大多集中在任务分配。现有的任务分配研究往往侧重于任务完成总量最大化，工人执行任务的执行路径最优化，或是任务分配的多样性评分最大化。这些研究中都假设任务分配给工人以后，工人愿意执行这些任务。然而，在实际生活中，工人执行任务的意图和偏好不同往往会导致工人的行为不同。例如，如果两个工人对同一类任务的偏好不同，那么他们可能会有不同行为：一个可能由于因为热点受人欢迎而愿意接受报告该热点的任务，另一个却由于报告热点的任务的复杂性而拒绝接受该任务。实际上，如果工人对分配的任务不感兴趣，那么他不会真诚并及时地完成这些任务，这样就会无法保证任务完成的质量。因此，控制任务完成质量的关键在于如何从工人执行任务的情况中精确地捕获到工人对于任务的偏好。工人执行任务时，时间动态信息是一个很重要的因素，因为工人对于任务类型的偏好可能会随着时间的推移而改变。例如，在工人的午休时间，他可能很乐于接受报告商场促销活动的任务，但是在工作时间，工人可能却会坚决拒绝这个任务。因此，在空间任务分配中需要考虑工人偏好的时间动态，这样才能有效地提高空间任务分配的准确性。

现有的空间众包研究往往是从工人的刚完成的任务执行模式或工人的直接反馈来推测工人的偏好。然而，这些研究中没有有效地结合时间动态和工人的历史任务执行记录。工人的总体任务执行情况可能由他长期的兴趣决定。但是在某个时刻，工人暂时的偏好也会受到瞬间事件的影响，例如当时任务的发布和执行情况。此外，由于任务执行数据的稀疏性和冷启动问题(新工人或新任务没有历史执行记录)，以上方法都不能保证任务分配的合理性。在任务分配技术中，考虑基于时间动态的工人偏好是提高空间众包的任务分配质量的一个关键因素。

发明内容

本发明的目的是为了解决现有的空间众包技术无法保证任务分配的合理性，无法实现任务分配数量最大化的问题，提出了一种基于工人偏好感知的空间众包任务分配方法。

本发明的技术方案为：一种基于工人偏好感知的空间众包任务分配方法，包括以下步骤：

S1、采集工人最近和历史任务执行数据，并将其作为数据源。

S2、根据数据源中的数据，采用基于历史数据的上下文感知张量分解算法进行工人时间动态偏好建模，得到工人在不同时间段对于不同类别任务的偏好值。

S3、根据工人在不同时间段对于不同类别任务的偏好值，采用偏好感知任务分配算法对空间众包任务进行分配。

进一步地，步骤S2包括以下分步骤：

S21、根据数据源中的工人最近和历史任务执行数据构建工人-任务-时间张量X。

S22、根据数据源中的工人最近和历史任务执行数据分别构建时间-任务矩阵Y和任务-特征矩阵Z。

S23、协同利用时间-任务矩阵Y和任务-特征矩阵Z对工人-任务-时间张量X进行分解，填充工人-任务-时间张量X中的缺失值，得到工人在不同时间段对于不同类别任务的偏好值。

进一步地，步骤S21中构建的工人-任务-时间张量X具体为：

X＝X_r||X_h

其中X_r表示近期工人-任务-时间张量，且X_r∈R^N×M×L，X_r中的条目X_r(i,j,k)＝e表示近期第i个工人对时隙k中第j个任务类别的偏好e，i＝1,2,...,N；j＝1,2,...,M；k＝1,2,...,L，N表示工人总数，M表示任务类别总数，L表示时隙总数；X_h表示历史工人-任务-时间张量，且X_h∈R^N×M×L，X_h中的条目X_h(i,j,k)＝e表示历史第i个工人对时隙k中第j个任务类别的偏好e。

进一步地，步骤S22中构建的时间-任务矩阵Y具体为：

Y＝Y_r||Y_h

其中Y_r表示近期时间-任务矩阵，且Y_r∈R^L×M，Y_r中的条目Y_r∈(k,j)表示近期在时隙k中已经执行类别j的任务的次数，Y_h表示历史时间-任务矩阵，且Y_h∈R^L×M，Y_h中的条目Y_h∈(k,j)表示历史在时隙k中已经执行类别j的任务的次数。

步骤S22中构建的任务-特征矩阵Z∈R^M×Q，Z中的条目Z∈(j,f)表示第j个任务类别的第f个特征，f＝1,2,...,Q，Q表示特征总数。

进一步地，步骤S23包括以下分步骤：

S231、利用tucker分解法对工人-任务-时间张量X进行分解：

X＝O×W×S×T

其中和分别表示工人、任务类别和时隙的低等级潜在因子矩阵，d_W,d_S,d_T分别表示工人、任务类别和时隙的潜在因子维数，为核心张量，其条目表示工人、任务类别和时隙三个低等级潜在因子之间的相互作用水平。

S232、利用tucker分解法对时间-任务矩阵Y进行分解：

Y＝TS^T

S233、利用tucker分解法对任务-特征矩阵Z进行分解：

Z＝SV

其中表示任务特征的低等级潜在因子矩阵。

S234、基于分解后的分量矩阵O,W,S,T,V构建损失函数L(O,W,S,T,V)：

其中||·||表示Frobenius范数，λ₁,λ₂,λ₃表示分解过程中不同部分的贡献参数。

S235、采用梯度下降算法最小化损失函数L(O,W,S,T,V)，并通过将分解后低等级潜在因子矩阵乘以张量X_rec＝O×W×S×T填充工人-任务-时间张量X中的缺失值，得到工人在不同时间段对于不同类别任务的偏好值。

进一步地，步骤S3包括以下分步骤：

A1、将每个工人w_i映射为一个顶点v_i，将每个任务s_j映射为一个顶点其中i＝1,2,...,|W_i|；j＝1,2,...,|S_i|，W_i为工人集合，|W_i|表示工人集合中的工人总数，S_i为任务集合，|S_i|为任务集合中的任务总数。

A2、构建虚拟源顶点src，并将其映射为v₀，构建虚拟目标顶点dst，并将其映射为

A3、连接源顶点v₀到工人顶点v_i的每条边(v₀,v_i)，设置每条边(v₀,v_i)的容量c(v₀,v_i)＝1，每条边(v₀,v_i)的成本w(v₀,v_i)＝0。

A4、连接任务顶点到目标顶点的每条边设置每条边的容量每条边的成本其中max W_j表示第j个任务最多会被分配给的工人个数。

A5、若任务s_j被分配给了工人w_i，则添加一条从顶点v_i到顶点的边设置边的容量边的成本其中表示工人w_i当前对类别为c的任务s_j的偏好值。

A6、将所有顶点和边构成流网络图G，采用Ford-Fulkerson算法寻找流网络图G中的最大流量的路径，并用线性规划使得该路径成本最小，将该路径中的任务分配给对应的工人。

进一步地，步骤S3包括以下分步骤：

B1、将每个工人w_i映射为一个顶点v_i，将每个任务s_j映射为一个顶点其中i＝1,2,...,|W_i|；j＝1,2,...,|S_i|，W_i为工人集合，|W_i|表示工人集合中的工人总数，S_i为任务集合，|S_i|为任务集合中的任务总数。

B2、构建虚拟源顶点src，并将其映射为v₀，构建虚拟目标顶点dst，并将其映射为

B3、连接源顶点v₀到工人顶点v_i的每条边(v₀,v_i)，设置每条边(v₀,v_i)的容量c(v₀,v_i)＝1，每条边(v₀,v_i)的成本w(v₀,v_i)＝0。

B4、连接任务顶点到目标顶点的每条边设置每条边的容量每条边的成本其中max W_j表示第j个任务最多会被分配给的工人个数。

B5、若任务s_j被分配给了工人w_i，则添加一条从顶点v_i到顶点的边设置边的容量边的成本其中表示工人w_i对任务s_j的空间加权偏好值，其计算公式为。

其中表示工人w_i当前对类别为c的任务s_j的偏好值，σ(w.l,s.l)表示工人空间偏好函数，其计算公式为：

其中d(w.l,s.l)表示工人当前所处地点w.l和任务发布地点s.l之间的欧式距离，w.r表示工人可达区域的半径。

B6、将所有顶点和边构成流网络图G，采用Ford-Fulkerson算法寻找流网络图G中的最大流量的路径，并用线性规划使得该路径成本最小，将该路径中的任务分配给对应的工人。

进一步地，步骤S3包括以下分步骤：

C1、将每个工人w_i映射为一个顶点v_i，将每个任务s_j映射为一个顶点其中i＝1,2,...,|W_i|；j＝1,2,...,|S_i|，W_i为工人集合，|W_i|表示工人集合中的工人总数，S_i为任务集合，|S_i|为任务集合中的任务总数。

C2、构建虚拟源顶点src，并将其映射为v₀，构建虚拟目标顶点dst，并将其映射为

C3、连接源顶点v₀到工人顶点v_i的每条边(v₀,v_i)，设置每条边(v₀,v_i)的容量c(v₀,v_i)＝1，每条边(v₀,v_i)的成本w(v₀,v_i)＝0。

C4、连接任务顶点到目标顶点的每条边设置每条边的容量每条边的成本其中max W_j表示第j个任务最多会被分配给的工人个数，s.p表示当前任务的发布时间，s.φ表示当前任务的截止时间，t_i表示随机时刻，s.p≤t_i。

C5、若任务s_j被分配给了工人w_i，则添加一条从顶点v_i到顶点的边设置边的容量边的成本其中表示工人w_i当前对类别为c的任务s_j的偏好值。

C6、将所有顶点和边构成流网络图G，采用Ford-Fulkerson算法寻找流网络图G中的最大流量的路径，并用线性规划使得该路径成本最小，将该路径中的任务分配给对应的工人。

本发明的有益效果是：

(1)本发明在空间众包任务分配中考虑工人对任务的时间动态偏好，并基于该时间动态偏好对空间众包任务进行分配，使得每个时刻的任务分配数量最大化。

(2)本发明为了解决工人任务执行数据的稀疏性和冷启动问题，提出了一种工人时间动态偏好建模(Temporal Preferences Modeling，TPM)方法，并采用基于历史数据的上下文感知张量分解算法(Preference-aware Task Assignment，PTA)补充工人时间动态偏好模型中缺失的数据，以学习得到工人的时间动态偏好，最终得到的工人在不同时间段对于不同类别任务的偏好值更加准确。

(3)本发明提出了三种偏好感知任务分配算法对空间众包任务进行分配，分别考虑了工人对任务的偏好值、工人的旅行时间成本以及任务的截止时间，保证了任务分配的合理性，从而实现任务分配数量最大化。

附图说明

图1所示为本发明实施例提供的一种基于工人偏好感知的空间众包任务分配方法流程图。

图2所示为本发明实施例提供的工人时间动态偏好模型示意图。

图3所示为本发明实施例提供的流网络图。

图4所示为本发明实施例提供的历史数据大小的影响示意图。

图5所示为本发明实施例提供的任务有效时间的影响示意图。

图6所示为本发明实施例提供的工人可达半径的影响示意图。

图7所示为本发明实施例提供的任务数量对CPU开销和分配成功率的影响示意图。

图8所示为本发明实施例提供的任务数量对平均旅行成本和分配任务数量的影响示意图。

具体实施方式

现在将参考附图来详细描述本发明的示例性实施方式。应当理解，附图中示出和描述的实施方式仅仅是示例性的，意在阐释本发明的原理和精神，而并非限制本发明的范围。

在描述本发明的具体实施例之前，首先对本发明中的一些名词进行定义，旨在使本发明的技术方案更加清楚。

定义1：空间任务。

空间任务可以表示为s＝<s.l,s.p,s.φ,s.c,s.max W>，其中s.l表示空间任务s的发布地点，可以用二维空间的一个点(x,y)描述，s.p表示空间任务s的发布时间，s.φ表示空间任务s的截止时间，s.max W表示在同一时刻允许同时执行任务s的工人数量的最大值，每一个任务s都会被标记为某个类别s.c(例如拍照、报告当地的热点等)。

为了简单起见，本发明实施例中假设每个任务的处理时间为0，这意味着一个工人可以在抵达当前任务地点之后直接去下一个任务地点。

定义2：工人。

工人是指携带移动设备并自愿执行空间任务的人，表示为w＝<w.l,w.r>，工人可以选择在线模式或者离线模式。当工人处于在线模式时，表示他已经准备好接受任务。每个在线的工人w都有一个其当前所处的地点w.l，并且该工人可达的区域是以w.l为中心，以w.r为半径的圆形区域，工人只能接受在该区域内的空间任务分配。

在本发明实施例所定义的模式中，每个工人在某个特定时刻只能处理一个任务，这在实际生活中是合理的。一旦服务器将一个任务分配给某个工人，该工人在完成被分配的任务前都会被认为处于正离线模式。

定义3：任务执行历史。

给定一个已经在某段时间内执行了n个任务的工人w，那么他的任务执行历史是一个任务集合每个三元组由所执行的任务s_i、工人的到达任务s_i的地点的时间和离开时间构成。

为了简洁，本发明实施例将简单表示为S_w＝{s₁,...,s_n}。

定义4：基于频率的工人偏好。

给定一个任务类别c和工人w的任务执行历史，那么工人w在确定的时间段T内，对任务类别c的基于频率的偏好用表示，该偏好通过工人在时间段T内执行的属于类别c的任务数量和其在时间段T内执行的任务的总数量的比率求得，即：

其中，N^T(S_w)是工人w在确定的时间段T中执行任务的总数。

本发明实施例中，在无歧义的情况下，将工人偏好和基于频率的工人偏好统称为工人偏好。

定义5：空间任务分配实例集。

给定在时刻t_i的在线工人集合为W_i＝{w₁,w₂,...}和可用任务集合S_i＝{s₁,s₂,...}，定义A_i是在时刻t_i的所有空间任务分配实例的集合。A_i由一系列二元组元素<w,s>组成，其中在满足所有工人和任务的限制条件后，空间任务s被分配给工人w，用|A_i|表示在时刻t_i任务分配的数量。

问题定义：在空间众包(Spatial Crowdsourcing，SC)平台中，如果给定在当前时刻t_i的在线工人集合为W_i，且可用任务和为S_i，则问题是在考虑工人对任务的时间动态偏好的前提下，找出在时刻t_i能够使任务分配数量(即|A_i|)最大化的对工人和任务进行分配的合理方案。

本发明实施例提供了一种基于工人偏好感知的空间众包任务分配方法，如图1所示，包括以下步骤S1～S3：

S1、采集工人最近和历史任务执行数据，并将其作为数据源。

S2、根据数据源中的数据，采用基于历史数据的上下文感知张量分解算法(History-based Context-aware Tensor Decomposition，HCTD)进行工人时间动态偏好建模(Temporal Preferences Modeling，TPM)，得到工人在不同时间段对于不同类别任务的偏好值。

TPM过程是基于工人最近和历史任务执行数据构建一个三维张量X，其中三维分别代表工人、任务类别和时间段(时隙)，其中每个条目是特定工作者对特定时间段中的特定任务类别的偏好。同时，TPM过程构建了两个上下文矩阵，一个是具有两个维度的时间-任务矩阵Y，分别代表时间段和任务类别，其中每个条目是在一个时间段中执行相应类别中的任务的次数；另一个是任务-特征矩阵Z，其值是从历史工人的配置文件中提取的。在上述两个矩阵的帮助下，张量X的缺失值可以由HCTD填充。然后可以推断出工人在当前时间内对所有类型任务的偏好，其原理是具有类似背景的工人可能有类似的偏好。上下文矩阵揭示了这种内在的相似性，并且具有比X更高的非零项比例，这可以有效地减少分解误差，提高推理准确度。

步骤S2包括以下分步骤S21～S23：

S21、根据数据源中的工人最近和历史任务执行数据构建工人-任务-时间张量X。

如图2所示，工人-任务-时间张量X＝X_r||X_h，其中X_r表示近期工人-任务-时间张量，且X_r∈R^N×M×L，其由工人、任务类别和时隙三个维度组成，X_r中的条目X_r(i,j,k)＝e表示近期第i个工人对时隙k(例如，上午10:00-11:00)中第j个任务类别的偏好e，i＝1,2,...,N；j＝1,2,...,M；k＝1,2,...,L，N表示工人总数，M表示任务类别总数，L表示时隙总数。显然，张量X_r中存在缺失的条目，一旦从其他非零条目中推断出缺失的条目，我们就可以获得所有工人对所有L个时隙中的任何任务的偏好。

然而，由于在短时间内只有少数任务可以由个别工人执行，因此这个张量过大而且存在大量缺失的条目。仅仅根据自己的非零项分解X_r是不够精确的，因此本发明实施例引入另一个张量X_h，即历史工人-任务-时间张量，它是基于在较长时间段(例如一个月)内执行记录的历史任务，是由1到L的对应时隙聚合而成，其结构与图2中所示的X_r相同，X_h∈R^N×M×L，X_h中的条目X_h(i,j,k)＝e表示历史第i个工人对时隙k中第j个任务类别的偏好e。显然，X_h代表历史任务执行模式和工人的长期利益，它比X_r更密集。通过将X_r和X_h一起分解，可以大大减少补充X_r的误差。

S22、根据数据源中的工人最近和历史任务执行数据分别构建时间-任务矩阵Y和任务-特征矩阵Z。

如图2所示，时间-任务矩阵Y＝Y_r||Y_h，根据不同任务类别上的任务执行条件的分布捕获时间相关性，其中每行表示时隙，每列表示任务类别。Y_r表示近期时间-任务矩阵，且Y_r∈R^L×M，Y_r中的条目Y_r∈(k,j)表示近期在时隙k中已经执行类别j的任务的次数，Y_h表示历史时间-任务矩阵，且Y_h∈R^L×M，Y_h中的条目Y_h∈(k,j)表示历史在时隙k中已经执行类别j的任务的次数。本发明实施例中，Y_r和Y_h分别代表了在同一时间段内的最近和历史任务执行条件。因此，两行的相似性表示两个时隙之间任务执行流的相关性。工人可以在时隙t_k和t_g中执行一些类似的任务，因为这两个时隙共享类似的工人任务执行模式。例如，工人的任务执行行为在上午10:00-11:00和下午2:00-3:00可能是相似的，因为他可能会呆在工作场所并愿意执行一些简单的任务，这些任务不会影响他的正常职责。此外，由于Y_r的条目是从所有工人中聚合出来的，因此可以帮助减少分解X_r的错误。Y_h具有与Y_r相同的结构，它存储了基于工作人员的长期任务执行历史在不同时隙中执行具有不同类别的任务的次数。

任务-特征矩阵Z∈R^M×Q，Z中的条目Z∈(j,f)表示第j个任务类别的第f个特征，f＝1,2,...,Q，Q表示特征总数。Z∈(j,f)的值可以是一个实值，表示任务类别的特征权重。矩阵Z通过存储每个类别的任务特征来获取不同任务类别之间的相似性。可以根据不同的应用场景提取许多功能，例如任务流行度、任务难度、任务风险级别、技能要求以及从历史工人配置文件派生的统计信息。

S23、协同利用时间-任务矩阵Y和任务-特征矩阵Z对工人-任务-时间张量X进行分解，填充工人-任务-时间张量X中的缺失值，得到工人在不同时间段对于不同类别任务的偏好值。

由于本发明的目标是模拟所有工人的时间动态偏好，因此需要估计X_r的缺失条目。一个简单的解决方案是利用tucker分解模型，该模型通常应用于高阶主成分分析(Kolda和Bader>r过于稀疏，单独分解X_r无法获得足够准确的结果。例如，在数据集中使用为期一天的任务执行记录并将时间段设置为1小时时，只有0.15％的X_r条目不为零。

步骤S23包括以下分步骤S231～S235：

S231、利用tucker分解法对工人-任务-时间张量X进行分解：

X＝O×W×S×T

其中和分别表示工人、任务类别和时隙的低等级潜在因子矩阵，d_W,d_S,d_T分别表示工人、任务类别和时隙的潜在因子维数，为核心张量，其条目表示工人、任务类别和时隙三个低等级潜在因子之间的相互作用水平。

S232、利用tucker分解法对时间-任务矩阵Y∈R^2L×M进行分解：

Y＝TS^T

S233、利用tucker分解法对任务-特征矩阵Z∈R^M×Q进行分解：

Z＝SV

其中表示任务特征的低等级潜在因子矩阵。可以看出张量X与矩阵Y共享矩阵T，与矩阵Z共享矩阵S，因此基于张量X和两个上下文矩阵Y和Z的知识即可分解X。

S234、基于分解后的分量矩阵O,W,S,T,V构建损失函数L(O,W,S,T,V)：

其中||·||表示Frobenius范数，λ₁,λ₂,λ₃表示分解过程中不同部分的贡献参数，是避免过拟合的惩罚规则化，损失函数L(O,W,S,T,V)用于控制误差。

S235、采用梯度下降算法最小化损失函数L(O,W,S,T,V)，并通过将分解后低等级潜在因子矩阵乘以张量X_rec＝O×W×S×T填充工人-任务-时间张量X中的缺失值，得到工人在不同时间段对于不同类别任务的偏好值。

S3、根据工人在不同时间段对于不同类别任务的偏好值，采用偏好感知任务分配算法对空间众包任务进行分配。

在实时场景中，工人和任务的到达具有动态性并且到达时空间众包(SpatialCrowdsourcing，SC)服务器响应需要具有及时性，这对于实现解决偏好感知任务分配(Preference-aware Task Assignment，PTA)问题的全局最优方案而言是一项重要挑战。由于无论何时，每个SC服务器都只知道局部的可分配任务和工人，而不是所有工人和任务的全局视图，所以在每个时刻，都将通过最大化当前分配，并且同时为更加偏好该任务的工人设置更高优先级的方式使得局部任务分配方案最优。

本发明实施例中提出了三种启发式方法来解决上述问题，包括基本偏好感知任务分配算法(Preference-aware Task Assignment，PTA)、空间加权偏好感知任务分配算法(Spatial-weighted Preference-aware Task Assignment，SPTA)和时间加权偏好感知任务分配算法(Temporal-weighted Preference-aware Task Assignment，TPTA)。下面以三个具体实施例对上述三种算法进行详细描述。

实施例1：

本发明实施例中采用基本偏好感知任务分配算法(Preference-aware TaskAssignment，PTA)，将工人的偏好作为任务分配的优先级，并且通过将偏好感知任务分配问题转化为最小成本最大流(Minimum Cost Maximum Flow，MCMF)问题，提出了一种基本解决方案。

在时刻t_i，MCMF是基于流网络图表示的任务分配问题。其中，流网络图用G＝(V,E)表示，V是图中所有顶点的集合，而E是图中边的集合。具体而言，假设给定在时刻t_i工人集合为W_i＝{w₁,w₂,...}，可分配任务的集合为S_i＝{s₁,s₂,...}，那么顶点集合V和边集合E的大小分别为|W_i|+|S_i|+2和|W_i|+|S_i|+m，其中m是对于所有工人的可分配任务总数。在时刻t_i，工人w(w∈W_i)的可分配任务用A_i^w表示，那么A_i^w应该满足以下三个条件：

(1)d(w.l,s.l)≤w.r；

(2)t_i+t(w.l,s.l)≤s.p+s.φ；

(3)工人w还没有执行任务s。

其中，d(w.l,s.l)是给定的w.l和s.l之间的距离(例如欧氏距离)，而t(w.l,s.l)是从w.l到s.l的行驶时间。本发明实施例中为了简单起见，假设所有工人都具有相同的行驶速度，那么两个地点之间的行驶时间成本就可以用它们之间的欧式距离评估，即t(w.l,s.l)＝d(w.l,s.l)。然而，本发明并不依赖于这个假设而且能够解决工人的行驶速度不同的情况。|A_i^w|表示工人w的可分配任务的数量，这样就能通过对所有工人的可分配任务数量求和来得到m的值，即

基于上述理论，如图3所示，步骤S3包括以下分步骤A1～A6：

A1、将每个工人w_i映射为一个顶点v_i，将每个任务s_j映射为一个顶点其中i＝1,2,...,|W_i|；j＝1,2,...,|S_i|，W_i为工人集合，|W_i|表示工人集合中的工人总数，S_i为任务集合，|S_i|为任务集合中的任务总数。

A2、构建虚拟源顶点src，并将其映射为v₀，构建虚拟目标顶点dst，并将其映射为

A3、连接源顶点v₀到工人顶点v_i的每条边(v₀,v_i)，设置每条边(v₀,v_i)的容量c(v₀,v_i)＝1，每条边(v₀,v_i)的成本w(v₀,v_i)＝0。

由于每个工人在当前时刻只能执行一个任务，所以本发明实施例中将每条边(v₀,v_i)的容量都设置为1。

A4、连接任务顶点到目标顶点的每条边设置每条边的容量每条边的成本其中max W_j表示第j个任务最多会被分配给的工人个数。

A5、若任务s_j被分配给了工人w_i，则添加一条从顶点v_i到顶点的边设置边的容量边的成本其中表示工人w_i当前对类别为c的任务s_j的偏好值。

A6、将所有顶点和边构成流网络图G，此时任务分配问题就被转化为一个在从源顶点src到源顶点dst的流网络图G中的MCMF问题，即使得图G中的流量(即路径通过所有边的容量之和)最大的同时需要成本最小。本发明实施例采用Ford-Fulkerson算法寻找流网络图G中的最大流量的路径，并用线性规划使得该路径成本最小，将该路径中的任务分配给对应的工人。

实施例2：

本发明实施例中采用空间加权偏好感知任务分配算法(Spatial-weightedPreference-aware Task Assignment，SPTA)，步骤S3包括以下分步骤B1～B6：

B1、将每个工人w_i映射为一个顶点v_i，将每个任务s_j映射为一个顶点其中i＝1,2,...,|W_i|；j＝1,2,...,|S_i|，W_i为工人集合，|W_i|表示工人集合中的工人总数，S_i为任务集合，|S_i|为任务集合中的任务总数。

B2、构建虚拟源顶点src，并将其映射为v₀，构建虚拟目标顶点dst，并将其映射为

B3、连接源顶点v₀到工人顶点v_i的每条边(v₀,v_i)，设置每条边(v₀,v_i)的容量c(v₀,v_i)＝1，每条边(v₀,v_i)的成本w(v₀,v_i)＝0。

B4、连接任务顶点到目标顶点的每条边设置每条边的容量每条边的成本其中max W_j表示第j个任务最多会被分配给的工人个数。

B5、若任务s_j被分配给了工人w_i，则添加一条从顶点v_i到顶点的边设置边的容量边的成本其中表示工人w_i对任务s_j的空间加权偏好值，其计算公式为。

其中表示工人w_i当前对类别为c的任务s_j的偏好值，σ(w.l,s.l)表示考虑工人和空间任务接近程度的基础上设置的工人空间偏好函数，其计算公式为：

其中d(w.l,s.l)表示工人当前所处地点w.l和任务发布地点s.l之间的欧式距离，w.r表示工人可达区域的半径。

空间众包(Spatial Crowdsourcing，SC)中有一个重要的问题就是工人必须亲自走到任务所在的地理位置才能执行任务，但是实施例1中的PTA算法并没有考虑工人和其指定任务之间的行驶时间成本。因此本发明实施例用工人w和空间任务s之间的欧氏距离d(w.l,s.l)衡量工人的行驶时间成本。实际上，工人更容易接受距离自己较近的任务，这一事实的启发下，本发明实施例验证了在同一时刻t_i时工人的偏好给更近的任务赋予更高的优先级，即空间加权偏好值

B6、将所有顶点和边构成流网络图G，此时任务分配问题就被转化为一个在从源顶点src到源顶点dst的流网络图G中的MCMF问题，即使得图G中的流量(即路径通过所有边的容量之和)最大的同时需要成本最小。本发明实施例采用Ford-Fulkerson算法寻找流网络图G中的最大流量的路径，并用线性规划使得该路径成本最小，将该路径中的任务分配给对应的工人。

实施例3：

本发明实施例采用时间加权偏好感知任务分配算法(Temporal-weightedPreference-aware Task Assignment，TPTA)，步骤S3包括以下分步骤C1～C6：

C1、将每个工人w_i映射为一个顶点v_i，将每个任务s_j映射为一个顶点其中i＝1,2,...,|W_i|；j＝1,2,...,|S_i|，W_i为工人集合，|W_i|表示工人集合中的工人总数，S_i为任务集合，|S_i|为任务集合中的任务总数。

C2、构建虚拟源顶点src，并将其映射为v₀，构建虚拟目标顶点dst，并将其映射为

C3、连接源顶点v₀到工人顶点v_i的每条边(v₀,v_i)，设置每条边(v₀,v_i)的容量c(v₀,v_i)＝1，每条边(v₀,v_i)的成本w(v₀,v_i)＝0。

C4、连接任务顶点到目标顶点的每条边设置每条边的容量每条边的成本其中max W_j表示第j个任务最多会被分配给的工人个数，s.p表示当前任务的发布时间，s.φ表示当前任务的截止时间，t_i表示随机时刻，s.p≤t_i。

任务的截止日期越晚，该任务就越有可能会更晚才被执行，反之亦然。据此，本发明实施例考虑了时间紧迫性来决定处理任务的顺序。分配任务时，更接近截止日期的任务应该比其他任务的优先级更高。因此，本发明实施例定义在时刻t_i的任务s的优先级等于其剩余时间和有效时间的比值，即并将其作为每条边的成本。

C5、若任务s_j被分配给了工人w_i，则添加一条从顶点v_i到顶点的边设置边的容量边的成本其中表示工人w_i当前对类别为c的任务s_j的偏好值。

C6、将所有顶点和边构成流网络图G，此时任务分配问题就被转化为一个在从源顶点src到源顶点dst的流网络图G中的MCMF问题，即使得图G中的流量(即路径通过所有边的容量之和)最大的同时需要成本最小。本发明实施例采用Ford-Fulkerson算法寻找流网络图G中的最大流量的路径，并用线性规划使得该路径成本最小，将该路径中的任务分配给对应的工人。

下面通过具体实验例对本发明的效果作进一步描述。

本实验例使用twitter签到数据集来模拟本发明实施例中的问题，这是评估空间众包平台的常见做法。由于原始Twitter数据集不包含地点的类别信息，因此需要借助其API从Foursquare中提取与每个地点相关联的类别信息。最终产生的数据集提供了2010年9月至2011年1月期间的美国签到数据，其中不包含阿拉斯加和夏威夷两地。数据集共计62462个地点和61412位用户。

在实验中，假设用户是空间众包系统的工人，因为在不同地点签到的用户可能是在这些地点附近执行空间任务的最佳候选者，并且他们的位置最接近这些签到地点。此外，将时间片段的粒度设为10min(例如10:00am-10:10am)，在此期间任务请求和可用的工人将被打包输入到系统中。假设在一个时间片段签到的所有用户都是该时间片段的在线工人，对于每个签到地点，分别使用其位置和当天最早签到时间作为任务的位置和发布时间。相应地，签到点的类别被视为任务的类别，提取10种签到类别来模拟任务类别。在一个地点签到相当于接受任务。另外，将每个任务的max W设置为一天内相应地点的签到次数，旅行费用根据工人所在地点到任务分配地点之间的欧式距离来计算。表1总结了本实验例中使用的所有参数的默认值。任务分配实验中，运行算法超过一天中的四小时(即10:00am-12:00am)并报告了平均结果。所有算法均在Intel Core i5-2400CPU@3.10GHZ 8GB内存的机器上实现。

表1实验参数

参数默认值历史数据时间跨度4周任务有效时间1h工人可达半径距离5km任务数量2000

(1)时间动态偏好建模(Temporal Preferences Modeling，TPM)性能。

本实验例中首先评估工人时间动态偏好建模阶段的性能及其对后续任务分配的影响。设置1小时为一个时间段并使用超过x周的签到数据(x＝1，2，3，4，默认为4)作为历史数据，使用前一天的签到记录作为最近的数据。张量分解中损失函数的参数(λ₁，λ₂，λ₃)设置为0.01。

为了评估工人对任务偏好的准确率，采用广泛使用的评价标准，平方均值误差(RMSE)和平均绝对误差(MAE)。从张量X_r中随机删除20％的非零项，这将被用于测试集来估计推断值，剩余的80％用于训练集。本实验例引入了一个基准算法，即AVF(Average>

(a)AVF：均值填充方法。

(b)TD：张量分解算法，基于其自身非零项分解张量X_r来填充缺失项。

(c)TD+H：张量分解算法，通过分解带有历史数据的张量来填充缺失项。

(d)TD+H+Y+Z(HCTD)：张量分解算法，通过分解带有历史数据，时间和任务上下文的张量来填充缺失值。

表2时间动态偏好建模不同算法的性能

方法AMERMSEAVF0.29790.3384TD0.26710.3056TD+H0.21290.2406TD+H+Y+Z(HCTD)0.20540.2344

表2显示了评估结果，其中AVF性能最差，HCFD性能最优，其次是TD+H和TD。这表明本发明的方法HCTD可以通过考虑历史数据，时间特征和不同任务类别之间的相关性，能更准确的估计工人偏好。

(2)历史数据的大小h的影响。

通过改变历史数据的大小来进一步评估时间优先建模的性能及其对后续任务分配的影响。特别地，对于偏好估计的准确性，比较了四种不同算法(包括AVF，TD，TD+H，HCTD)的RMSE值。另外，本实验例比较了三种不同任务分配算法(包括基于HCTD的任务分配算法HCTD-TA，基于AVF的任务分配算法AVF-TA和MCTA算法)的任务分配成功率，通过将任务非配问题转化为不考虑工人偏好的最大流问题。当一个空间众包服务器在特定的时间片段分配任务s给工人w时，如果在工人相应时间段T的任务执行列表中存在一个任务和分配任务具有相同类别，则认为任务分配成功。此外本实验例引入分配成功率(ASR)，即在一个时间片段中给所有工人成功分配的任务占据所有任务的比率来评价任务分配的准确性。

如图4所示，除TD算法外所有算法准确率随历史数据时间的时间跨度增加而逐渐增加。TD算法估测准确率不受历史数据影响因为它仅仅分解不带历史数据的张量X_r。AVF算法性能最差。此外，HCFD性能优于TD和TD+H，这验证了历史张量和上下文矩阵的贡献是有效的。就图4中的任务分配成功率而言，MCTA算法保持不变，因为它不考虑历史数据推断的工人偏好。另外，HCTD-TA的任务分配成功率随h变大而提升，由于工人偏好估计的准确率提升，并且针对所有h值它的表现都优于基准算法，这证实了本发明提出算法的优越性。

下面根据HCTD生成的工人时间动态偏好评估本发明实施例1～3中三种不同的任务分配算法：PTA，SPTA和TPTA算法。本实验例使用两个标准来比较三个算法：1)CPU开销，在时间片段中发现任务分配的CPU时间成本；2)ASR：分配成功率。

(3)任务有效时间的影响。

首先研究任务有效时间的影响。如图5所示，对于CPU开销所有方法具有相似的性能。这是因为这些方法都采用最大流最小成本(MFMC)算法，只需改变流网络图中边的权重，这不会影响计算复杂度。另一个注意点是所有方法的CPU成本几乎与线性增加，因为当变长时，时间片段中可用任务数量增加，这反过来导致MFMC的流网络图中的更多边被检索。所有方法的ASR值随着的增加而增加，因为当变长时，工人有更多机会被分配感兴趣的任务。SPTA和TPTA的表现比TPA差，因为它们分别考虑了工人的旅行费用和任务的到期时间，这削弱了工人偏好对任务分配的影响，导致更不准确的任务分配。

(4)工人可达半径r的影响。

本实验例中将工人可达半径距离从5公里变为20公里来研究r的影响。从图6可以看出，当r增长时，所有方法的CPU开销都有类似的增长趋势。这背后的原因是所有方法都应用MFMC算法，并且更多具有更远可达距离的工人通常具有更多可用任务分配，这导致MFMC流网络图具有更多的边。如图6所示，随着r增大，三种方法分配成功率呈增长趋势，这和任务有效时间影响原因相似，即工人可达区域越大，空间众包服务端将会有更多机会为工人分配他们感兴趣的任务。

(5)任务数量|S|的影响。

为了研究提出算法的扩展性，本实验例在一天的四小时(10:00am-2:00pm)从原始数据集中随机选择500-2500个任务来生成5个数据集。除了CPU成本和分配成功率外，还比较三种方法的另外两个指标：1)所有任务分配的平均旅行成本；2)分配任务的总数。正如预期所示，尽管CPU开销随|S|增加而增加，然而本发明提出的算法在提高任务分配成功率方面表现良好，如图7所示。

图8显示了所有算法的平均旅行成本降低，因为分配的任务更接近任务密集区域中的工作者的概率更高。此外，SPTA以惊人的幅度(高达42％)优于PTA和TPTA，这证明了空间(旅行成本)启发式的有效性。如图8所示，当存在更多任务时，所有方法的分配自然会增加。该图还说明了TPTA与PTA和SPTA相比在任务分配数量(高达40％)方面的优越性，这源于应用时间启发式算法。此外，随着任务数量的增加，时间启发式的影响将变得更加显著。其背后的原因时随着任务数量增加，更多任务即将到期，因此优先处理即将到期的任务将变得更加有效。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。