移动群智感知中基于用户意愿的多任务分配模型

Multi-Task Allocation Based on User Willingness in Mobile Crowd Sensing

摘要: 以群智感知平台为中心的任务分配方法中，平台收集用户实时位置、社交关系等信息并进行集中处理，将多个任务分配给用户，以实现感知时间最小化、感知成本最小化等优化目标。但传统方法没有着重考虑用户的执行意愿，与用户意愿相悖的分配方案和大量隐私信息的泄露不利于维护用户的长时参与水平。因此提出基于用户意愿的任务路径分配模型PtrNet-TA，在用户移动端通过本地历史感知数据训练一个seq2seq的指针网络模型，任务分配时将云端服务器提供的待执行感知任务集合作为输入传入本地指针网络模型从而输出符合用户意愿的任务路径分配给对应的用户。通过仿真实验表明，PtrNet-TA序列预测准确度优于分别采用LSTM模型与LSTM + Attention模型的基准方法。

Abstract: In the platform-centric task allocation method, the MCS platform collects information such as real-time location, historical movement trajectory, and social relationship of the user for centralized processing, and assigns multiple tasks to users, so as to optimize targets such as minimizing perceived time and minimizing perceived cost. The conventional method does not focus on the user’s willingness to execute. The distribution scheme which is contrary to the user’s will and the disclosure of a large amount of private information are not conducive to maintaining the long-term participation level of users. Therefore, a task path allocation method PtrNet-TA based on the user’s intention is proposed, and a seq2seq pointer network model is trained on the user mobile terminal through local history sensing data, and the to-be-perceived task set provided by the cloud server is input as an input during task assignment. The local pointer network model is passed in to output a task path that matches the user’s wishes to the corresponding user. Simulation experiments show that PtrNet-TA is better than the benchmark method using LSTM model and LSTM + Attention model.

1. 引言

移动群智感知是一种随着物联网发展而诞生的新兴感知范式，它将用户移动设备(智能手机、平板电脑、可穿戴式)作为基本感知单元，通过不同拓扑结构的移动网络进行连接构成大规模感知系统，从而实现感知数据的收集，并应用在环境监测 [1] [2] [3]、智能交通 [4]、移动社交 [5] 等实际场景中。

任务分配是移动群智感知中的核心问题之一，感知任务分配方案的可行性与参与者选择的合理性对群智感知系统的整体感知性能具有很大的影响。根据对象的不同，任务分配方法可以分为以平台为中心和以用户为中心。前者旨在达到成本最小化、感知时间最小化、感知覆盖度最大化等相关优化目标以实现平台利益最大化。后者从用户角度出发，基于隐私保护、利益最大化等目标设计对应的激励机制以维护用户长时的感知水平。

以平台为中心的任务分配方法本质属于组合优化问题，具有NP难解性，通过线性规划、禁忌搜索、遗传算法等优化方法生成合理的任务分配方案进而实现多目标优化。目前，研究人员在这一方面已取得了较多的研究成果。Xiao等人 [6] 基于贪婪算法设计了截止时间敏感的任务分配方法。通过招募多个感知用户协作执行感知任务，最大化被招募用户的效用，并在截止时间内最小化感知支出。Messaoud等人 [7] 基于禁忌搜索算法提出了信息质量与能量敏感的群智感知机制，能在满足信息质量与能量约束的前提下选择合适的任务执行者，并最大化信息质量与最小化能耗。Wang等人 [8] 引入特定于任务的最小感知质量阈值来重新定义多任务分配问题，为每个工作者分配一组适当的任务使得感知系统效用最大化。Hu等 [9] 利用动态获取的时空知识提出了在线启发式算法，以提升空间众包任务分配的效率；Azzam等 [10] 提出了基于群组的招募系统，利用遗传算法综合用户特征从而选择合适的用户群组执行感知任务。

以用户为中心的任务分配方法往往基于报酬激励、隐私保护激励、社会关系激励等设计合理的激励机制用于补偿用户的感知成本并维护长时的参与水平。Liu等人 [11] 针对多任务并发环境提出了参与者选择方案MultiTasker，该方案要求各个用户在规定的时间内尽可能多地完成感知任务，并基于静态固定报酬与动态报酬设计了用户激励机制，其中的动态报酬正比于用户与任务目标位置之间的距离。Wang等人 [12] 基于质量敏感与细粒度模型设计了对应的拍卖方案，该方案将感知任务划分为多个子任务，且各感知用户允许参与多个子任务，在确保子任务质量要求的前提下最小化支出成本。Yu等人 [13] 面向用户区域设计了符合玻尔兹曼分布的用户意愿模型进行动态定价，并根据用户信誉度进行任务分配，实现了隐式的信誉度激励机制。

综上，目前的任务分配方法存在以下不足：

1) 以平台为中心的任务分配方法需要获取用户的实时位置、历史移动轨迹、感知偏好、社交应用情况等信息，不利于用户的隐私保护，影响用户的参与水平。其次，在大量感知任务并发的实际场景中，任务分配模块全部部署在云端，容易使平台处理压力增大，负载超荷。

2) 较多数的已有方法中，每个感知任务的分配被单独考虑，难以适用多任务实时并发的实际场景。

3) 已有的任务分配方法，没有充分考虑用户的意愿。虽然部分以用户为中心的任务分配方法基于损失厌恶、收益最大化、契约理论等经济学理论对用户意愿进行了建模。但现实场景中，用户的异质性与有限理性导致每个用户的意愿是不尽相同的，在同样的感知环境下，用户所自主选择执行的感知任务也不一定一样。统一建模难以实现较为准确与个性化的任务分配，进而难以契合用户意愿以提高参与水平。

2. 系统模型与问题描述

2.1. 系统模型

常规的群智感知系统任务分配模块部署在云端，当平台收到感知任务请求后，获取用户信息(实时位置、移动速度、设备电量、网络流量、历史移动轨迹等)。平台根据收集的用户信息与感知任务信息，进行分析处理，通过启发式算法或智能算法进行组合优化，生成最大化平台利益的任务分配方案。常规群智感知系统模型具体如图1所示。

Figure 1. Task allocation model of typical crowd sensing

图1. 典型群智感知任务分配模型

PtrNet-TA模型将常规群智感知系统中的任务分配模块从云端部署到了每名用户的移动端。将每名用户的本地历史感知数据作为样本集训练一个基于指针网络的任务序列生成模型。

在PtrNet-TA的应用场景中，数据请求者向感知平台发布感知任务，平台将感知任务整理汇总后广播发布给每名用户的移动设备每名移动端将感知任务信息作为输入传入本地训练部署的指针网络 [14]，从而在移动端生成符合用户意愿的任务序列并分配给对应的用户。PtrNet-TA模型具体如图2所示。

Figure 2. Task allocation model of PtrNet-TA crowd sensing

图2. PtrNet-TA群智感知系统任务分配模型

PtrNet-TA使用自训练的指针网络序列生成模型，根据实时的感知任务信息生成任务序列直接分配对应的用户，避免了将个人信息上传至平台，实现隐私保护的同时降低了云端服务器的数据处理压力。

2.2. 问题描述

给定感知任务集合 $T=\left\{t_1,t_2,t_3,\cdot \cdot \cdot ,t_n\right\}$，感知任务表示为3元组： $t_i=\left(x_i,y_i,r_i\right)$。其中 $x_i$， $y_i$ 分别为 $t_i$ 的横纵坐标， $r_i$ 为该感知任务的报酬。给定用户集合 $U=\left\{u_1,u_2,u_3,\cdot \cdot \cdot ,u_m\right\}$，本文仅考虑地理位置相关的感知任务，因此用户 $u_j=\left(u{x}_j,u{y}_j\right)$，仅使用用户的位置信息。

用户意愿任务序列为用户面对实时的感知任务信息时，会主动选取执行的任务序列，表示为 $A{T}_j$。用户 $u_j$ 部署的指针网络 $PtrNe{t}_j$ 根据任务集合T生成 $A{T}_j$，其形式化表示如式(1)所示。

$A{T}_j=PtrNe{t}_j\left(T\right)$ (1)

约束条件为：

$A{T}_j=argmaxP\left(A{T}_j|T,\theta \right)$ (2)

3. PtrNet序列生成模型

3.1. 数据准备及预处理

由于群智感知平台数据较为缺乏，任务分配方法的研究也没有标准的基线方法和专用数据集。因此为了训练及评估模型，采用Q-learning进行样本生成。在真实轨迹数据集D4D中进行采样，初始化感知任务集合的时空分布，感知报酬则从1~30间随机生成。Q-learning属于强化学习，其本质上是一个马尔科夫决策过程(MDP)，可以用四元组表示为(S, Act, P, r)。其中S为状态空间，Act为智能体的动作空间，P为状态转移概率，r为奖励。强化学习通过智能体与环境之间的交互，进行试错学习，最终学习得到智能体的策略。Q-learning是基于价值的强化学习算法，基于特定状态下动作所对应的Q值进行决策。Q值为所获奖励的累积期望，智能体Agent目标学习某一策略使得累积报酬最大化。Q值 [15] 更新公式如下：

$Q\left(s,a\right)=Q\left(s,a\right)+\alpha \left[r\left(s,a\right)\right]+\gamma \max Q^{*}\left(s^{*},a^{*}\right)-Q\left(s,a\right)]$ (3)

其中Agent为用户，在没有真实数据集的情况下为了直观评估模型是否能够预测生成符合用户意愿的任务序列。本文设置2个不同策略的智能体。Agent1的动作策略为移动距离最小化；Agent2的动作策略为激励报酬最大化。Agent1用以代表执行意愿为就近原则的用户，不愿意花太多时间在空间移动上。Agent2用以代表报酬敏感的用户，在执行感知任务中其意愿为最大化自身收益(贪心策略)。Agent1的奖励函数设置为移动距离的负值；Agent2的奖励函数设置了完成对应感知任务所获取的报酬。

由于在实际应用场景中，用户多数情况下并不会执行全部的感知任务，每次选择执行的感知任务数量是不同的。因此生成的标签序列是不定长的，在算法1中，随机初始化序列长度thr用以表示用户在不同感知环境下选取任务的数量。

D4D数据集中的节点分布是通过经纬度表示的，通过反射机制将经纬度转化为二维坐标。将UNIX时间戳进行转化，并拆分成月、日、时、分构成4维特征向量。最后将感知任务数据进行标准化处理，便于神经网络模型进行学习。通过任务信息生成符合用户意愿的任务序列本质不是典型的seq2seq模型，还是set2seq，因此感知任务在输入时不用额外进行统一排序。生成的样本数据如表1所示。

Table 1. Generate sample examples

表1. 生成样本示例

3.2. 网络结构

考虑到每次实时并发的任务数量是不同的，因此基于LSTM的序列生成模型难以解决任务数量不定的问题。本文采用基于Pointer Network的序列生成模型。其网络结构如图3所示。

Figure 3. Network structure of PtrNet sequence generation model

图3. PtrNet序列生成模型网络结构

PtrNet由两个循环神经网络(Recurrent Neural Network)模块构成，分为编码器(Encoder)和解码器(Decoder)。循环神经网络中由LSTM单元(Long Short-Term Memory)组成。解码器与编码器神经元数量相同。模型执行流程为：任务集合 $T=\left\{t_1,t_2,t_3,\cdot \cdot \cdot ,t_n\right\}$ 中的感知任务按序传递给编码器生成隐藏状态向量，解码器输出一个初始输入任务集合的概率分布。其中概率最大的任务被选择加入任务序列中。PtrNet模型的注意力机制如下。

$u_j^i=v^T\tanh \left(W_1{e}_j+W_2{d}_i\right)$ (4)

$p\left(g{t}_i|g{t}_1,\cdot \cdot \cdot ,g{t}_{i-1},T\right)=softmax\left(u^i\right)$ (5)

其中 $GT=\left\{g{t}_1,\cdot \cdot \cdot ,g{t}_n\right\}$ 为最终生成的序列。

考虑用户只选择感知任务中的部分任务进行执行。网络模型输入除了任务集合 $T=\left\{t_1,t_2,t_3,\cdot \cdot \cdot ,t_n\right\}$ 以外。我们设置了两个额外的标签输入：Start与End。

$Start=\left(u{x}_i,u{y}_i,0,umo{n}_j,uda{y}_j,uhou{r}_j,umi{n}_j\right)$ (6)

$End=\left(0,0,0,0,0,0,0\right)$ (7)

解码器输出为End时，则结束序列生成。

3.3. 模型训练及优化

解码器与编码器单元数量相同，由于考虑到模型只基于本地数据进行训练，实际场景中样本数量理论上来说较少。因此仅使用2000个序列样本作为训练数据，500个序列样本作为测试数据。

为了避免模型结构过于复杂而导致过拟合，LSTM内部隐藏层采用64个节点单元。优化器采用RMSProp.梯度下降算法，学习率设置为0.03。

由于样本数量较少，不采用留出验证，使用K折随机交叉验证。将数据样本划分为10折，batch_size设置为1，进行交叉验证。

通过最大似然法使得序列在感知环境下的出现概率最大化，求解得到损失函数 [16]。如式(8)、(9)所示。

${\theta }^{\ast }=\underset{\theta }{argmax}{\displaystyle \underset{T,GT}{\sum }\log p\left(GT|T;\theta \right)}$ (8)

$loss=-{\displaystyle \underset{i=1}{\overset{\left|GT\right|}{\sum }}\log p\left(g{t}_i|g{t}_1,\cdot \cdot \cdot ,g{t}_{i-1},T\right)}$ (9)

4. 实验评估与分析

将seq2seq的LSTM模型与LSTM-Attention模型作为基准方法进行对比实验。其结果如表2所示。

Table 2. ACC、SDD evaluation of model

表2. 模型的ACC、SDD评估

由表2可得，PtrNet模型具有较好的鲁棒性，并且在训练感知任务数量多于测试任务数时，也能够较为准确地生成序列。原因在于PtrNet能够将解码器输出映射为输入元素的概率分布，因此能够解决感知任务不定长的问题。PtrNet的ACC值总体优于基线模型，其SDD指标也明显较小，从侧面反映了即使在预测不完全正确的情况下，PtrNet的生成序列较基线方法与用户的意愿序列的相似度较高，在没有完全预测准确时，PtrNet的生成序列也在一定程度上符合用户的意愿。

5. 结语

提出了一种基于用户意愿的任务序列生成方法以实现个性化的多任务分配。主要工作分为两个部分：1) 提出新的群智感知架构。将任务分配模块转移部署到用户移动端，在不需要上传个人信息的情况下生成符合用户意愿的任务分配方案，有利于隐私保护及降低云端平台数据处理压力。2) 基于指针网络构建了set2seq的任务生成模型，将感知任务信息及用户信息作为输入生成任务序列。模型在强化学习生成的样本数据上，预测准确率较高，并且鲁棒性较好，在没有完全预测成功的情况下也接近真实的用户意愿序列。

移动端的指针网络生成模型虽然能够避免隐私泄露，但用户个人的历史感知数据可能数量较少，难以训练一个性能优异的模型。但随着时间推移，用户每执行一次感知任务，都可以添加新的样本到训练数据集以不断优化模型。因此后续工作需要针对感知数据小样本特性进行研究提出性能更加优良的模型。其次，本文仅考虑了基于地理位置的感知任务，考虑的感知任务属性较少，后续需要对感知任务进行合理建模，丰富模型的应用场景。

NOTES

^*通讯作者。