0 概述

群智感知是结合众包思想和移动设备感知能力的一种新的数据获取模式^[1]，其通过移动设备形成交互式和参与式的感知网络，并将感知任务发布给网络中的个体或群体来完成，从而帮助专业人员或公众收集数据、分析信息和共享知识。相比传统固定基站的数据收集方式，一方面群智感知模式由于GPS、罗盘、加速计等大量传感器嵌入手机移动设备，用户可方便快捷地参与任务，另一方面在收集大规模和大容量数据时其在质量、速度和效率方面更具优势。本文以群智感知技术为研究背景，提出基于显性时空关联和隐性时空关联的用户激励算法。

1 相关工作

在用户激励机制方面，文献[2]主要从技术层面入手，分析激励机制中的影响因素。文献[3]研究跨空间领域中有关群智感知的用户激励机制、任务请求者以及最终执行任务的用户三者之间的关系和多元互动来激励效率高、质量好的用户参与群智感知任务。文献[4]在移动数据收集过程中设计一种基于时间敏感的用户激励机制，将用户激励问题转化为用户博弈问题，并证明了该博弈满足纳什均衡理论。

在用户招募方面，文献[5]从用户社交性以及用户和感知目标的距离角度进行群智感知用户招募。文献[6]对具有最低花费且用户轨迹覆盖相关兴趣点的用户进行招募，且将招募问题转化为集合覆盖问题。文献[7]建立用户质量模型、估算用户信誉模型来选择高质量用户，且利用沙普利值计算用户酬劳。

在用户时空性方面，文献[8]不仅考虑用户当前位置，而且考虑用户未来轨迹，将用户选择问题转化为NP-Hard问题并提出贪婪算法进行求解。文献[9]结合感知任务的空间性和移动用户的时间性提出LRBA算法，从而将整个任务分配问题划分成若干个子问题。文献[10]研究基于感知任务截止时间的用户选择问题，并证明该问题是NP-Hard问题。文献[11]将感知任务分成时间敏感和延时容忍任务，对于时间敏感任务，招募用户的准则是最小化用户移动的总距离，而对于延时容忍任务，尽可能减少招募的用户数量。文献[12]提出一种依赖时间窗口和对数据完整性有较高要求的激励机制，使用反向拍卖的框架来建立系统模型。

在预测用户时空性方面，文献[13]通过半马尔科夫模型^[14]预测兴趣点轨迹，并充分考虑时间和空间的因素对用户进行选择。文献[15]分析用户完成任务的数量，根据用户上传数据的方式不同（蜂窝网络和WiFi网络），通过马尔科夫模型对用户轨迹进行预测，设计相应的贪婪算法进行满足预算限制和最佳用户的招募。文献[16]针对确定轨迹和不确定轨迹分别提出基于线性规划的遗传算法和贪婪算法，并且保证了算法有效性。文献[17]建立基于兴趣点的轨迹预测模型得到所有任务的完成概率，并提出离线贪婪算法和在线用户招募算法。文献[18]基于群智感知提出实时轨迹追踪系统，实现最大化实时追踪轨迹和真实轨迹的覆盖，并且最小化参与实时轨迹追踪系统的用户数量。

上述传统激励机制未同时考虑时空及时空关联性因素，因此造成很多感知任务难以执行。基于时空因素，文献[19]采用深度学习模型，提出基于时空相关性的短时交通流量预测法，但该方法更多关注显性关联性。文献[20]研究时空因素下的用户招募和激励机制，但未考虑时空重叠和关联性问题，而对比传统激励机制发现，很多任务和用户具有时空重叠和关联特性。为解决感知任务完成率低且花费高的问题，本文提出基于时空关联性的用户激励机制STIM。

2 时空关联模型及问题定义 2.1 系统模型

假设系统中发布一系列群智感知任务 $S= \left\{S_{1}, S_{2}, \cdots, S_{m}\right\}$，对于任意任务$S_{j} \in S$ 均存在时间范围 $T_{j}=\left[t_{j}^{\mathrm{s}}, t_{j}^{\mathrm{e}}\right]$和空间范围 $P_{j}=\left\{l_{1}, l_{2}, \cdots, l_{m}\right\}$，其中，t_j^s表示感知任务的开始时间，t_j^e表示感知任务的结束时间，l_m表示感知任务需要感知的路段。结合时间和空间范围，通过二元组 $\theta_{j}=\left\{T_{j}, P_{j}\right\}=\left\{\left[t_{j}^{\mathrm{s}}, t_{j}^{\mathrm{e}}\right], \left\{l_{1}, l_{2}, \cdots, l_{m}\right\}\right\}$来表示任务时空要求，即在时间范围内经过的路段，例如 $\theta_{1}=\left\{[7: 11], \left\{l_{1}, l_{2}\right\}\right\}$表示任务1需要用户从07：00到11：00经过l₁、l₂两个路段。

假设系统有一系列用户$U=\left\{U_{1}, U_{2}, \cdots, U_{n}\right\}$ ，对于任意用户U_i∈U均存在用户三元组 $\omega_{i}=\left\{T_{i}, P_{i}, c_{i}\right\}=\left\{\left[t_{i}^{\mathrm{s}}, t_{i}^{\mathrm{e}}\right], \left\{l_{1}, l_{2}, \cdots, l_{m}\right\}, c_{i}\right\}$，其中，t_j^s表示用户能参与任务的开始时间，t_i^e表示用户能参与感知任务的结束时间，c_i表示用户花费，例如 $\omega_{1}=\left\{[7: 11], \left\{l_{1}\right\}, 10\right\}$表示用户1从07：00到10：00经过l₁路段，花费为10。

2.2 显性时空关联模型

显性时空关联表示感知任务与感知任务、用户与用户间存在相同时空特性，因此分别定义基于感知任务和用户的显性时空关联。

定义1（基于感知任务的显性时空关联）  对于任意两个任务S_J1，S_J1∈S，满足时空重叠（见式（1）），则称该感知任务集合是基于感知任务的显性时空关联。

$T_{j_{1}} \cap T_{j_{2}} \neq \phi \;\mathrm{and}\; P_{j_{1}} \cap P_{j_{2}} \neq \phi$

(1)

对于任意两个任务S_J1，S_J1∈S，满足时空重叠和时空覆盖（见式（2）），则称该感知任务集合是基于感知任务的覆盖显性时空关联。可见，时空覆盖任务一定是时空重叠任务，但是时空重叠任务不一定是时空覆盖任务，即时空重叠包含时空覆盖。

$\left(T_{j_{1}} \in T_{j_{2}}\right.\;\mathrm{and} \left.P_{j_{1}} \in P_{j_{2}}\right)\;\mathrm{or}\;\left(T_{j_{2}} \in T_{j_{1}}\right.\;\mathrm{and}\; \left.P_{j_{2}} \in P_{j_{1}}\right)$

(2)

将所有基于显性时空关联的感知任务集合视为一个感知任务，用户的时空集合可以同时满足多个任务的时空需求，大幅提高运算效率。

定义2（基于用户的显性时空关联）   对于任意两个招募用户U_i1，U_i1∈U，可能存在部分相同的时空集合（满足式（3）），则称有相同时空的用户集为基于用户的显性时空关联。

$t_{i_{1}} \cap t_{i_{2}} \neq \phi\;\mathrm{and}\;p_{i_{1}} \cap p_{i_{2}} \neq \phi$

(3)

通过式（4）得到相同时空集合{[t', p']}，并将用户集中有相同时空集合视为同一时空集合，这样模型只要支付一次该时空集合的花费，就能节省总花费。

$t_{i_{1}} \cap t_{i_{2}}=t^{\prime}\;\mathrm{and}\;p_{i_{1}} \cap p_{i_{2}}=p^{\prime}$

(4)

图 1表示显性时空关联状态。已知感知任务1~感知任务4，感知任务1的感知时间间隔为08：00—10：00、感知任务2的感知时间间隔为09：00—11：00、感知任务3的感知时间间隔为01：00—03：00、感知任务4的感知时间间隔为01：30—02：30；感知任务1和感知任务2的感知区域有重叠部分，感知任务3的感知区域完全覆盖感知任务4的感知区域。用户A在时间间隔08：00—09：00内停留在感知任务1的感知区域、在时间间隔09：00—11：00内停留在感知任务2的感知区域。用户B在时间间隔08：00—10：00内停留在感知任务1的感知区域、在时间间隔10：00—11：00内停留在感知任务2的感知区域。

感知任务1和感知任务2是基于感知任务的显性时空关联，因为感知任务1和感知任务2有重叠时间，重叠时间间隔为09：00—10：00。另外，空间重叠为阴影部分，在任务发布后用户只需满足该部分的时空要求。感知任务3和感知任务4是基于感知任务的覆盖显性时空关联，因为感知任务3覆盖感知任务4，所以发布任务后只需满足感知任务3的时空要求。

用户A和用户B是基于用户的显性时空关联，如果只招募用户A，感知任务1无法完成，如果只招募用户B，感知任务2无法完成，为保证感知任务1、感知任务2都被完成，任务发布者和参与用户所在的群智感知平台会同时招募用户A和用户B。此时，在用户A和用户B的时空状态中存在重复的时空状态，即在时间间隔08：00—09：00内用户A和用户B均停留在感知任务1的感知区域、在时间间隔10：00—11：00内均停留在感知任务2的感知区域。

2.3 隐性时空关联模型

基于用户当前的时间和空间因素，用户仅参与其中某些任务，但是随着用户移动，用户的时间和空间因素会发生改变，此时用户可以参与一些额外任务。对于这种情况的用户，可以称为该用户存在隐性时空关联。在实际情况中无法知道用户未来移动方向，但是可基于用户之前移动情况进行预测，因此考虑马尔科夫模型得到用户在某一时间间隔内从一个路段l₁移动到另一个路段l₂的概率。

本文假设用户i的时空状态为L_i={1, 2, ..., l}，其表示用户当前所在的路段位置；L_iⁿ表示用户i在第n个状态时的路段位置；T_iⁿ表示用户i在第n个时空状态时的开始时间，即用户i进入第n个路段的时间； $S_{i}^{n}=T_{i}^{n+1}-T_{i}^{n}$表示用户i在路段的停留时间。

用户i在时间间隔t内从路段l₁到路段l₂的概率为：

$\begin{aligned} Z_{i}^{l_{1} l_{2}}(t)=& P\left(L_{i}^{n+1}=l_{2}, S_{i}^{n} \leqslant t \mid L_{i}^{0}, L_{i}^{1}, \cdots, L_{i}^{n}\right. ,\\ &\left.T_{i}^{0}, T_{i}^{1}, \cdots, T_{i}^{n}\right)=\\ & P\left(L_{i}^{n+1}=l_{2}, S_{i}^{n} \leqslant t \mid L_{i}^{n}=l_{1}\right) \end{aligned}$

(5)

考虑空间因素，用户i从路段l₁到路段l₂的概率为：

$P_{i}^{l_{1} l_{2}}=P\left(L_{i}^{n+1}=l_{2} \mid L_{i}^{n}=l_{1}\right)=\frac{\operatorname{num}_{i}^{l_{1} l_{2}}}{\operatorname{num}_{i}^{l_{1}}}$

(6)

其中，num_i^l₁l₂代表用户i从路段l₁移动到路段l₂的次数，num_i^l₁代表用户i离开路段l₁的次数。

考虑时间因素，用户i在时间间隔t内从路段l₁到路段l₂的概率为：

$\begin{aligned} G_{i}^{l_{1} l_{2}}(t)=& P\left(S_{i}^{n} \leqslant t \mid L_{i}^{n}=l_{1}, L_{i}^{n+1}=l_{2}\right)=\\ & \sum\limits_{x=1}^{t} P\left(S_{i}^{n}=x \mid L_{i}^{n}=l_{1}, L_{i}^{n+1}=l_{2}\right) \end{aligned}$

(7)

根据式（5）~式（7）得到用户i在时间间隔t内从路段l₁到路段l₂的概率为：

$\begin{aligned} Z_{i}^{l_{1} l_{2}}(t)=& P\left(L_{i}^{n+1}=l_{2}, S_{i}^{n} \leqslant t \mid L_{i}^{0}, L_{i}^{1}, \cdots, L_{i}^{n}\right. , \\ &\left.T_{i}^{0}, T_{i}^{1}, \cdots, T_{i}^{n}\right)=\\ & P\left(S_{i}^{n} \leqslant t \mid L_{i}^{n}=l_{1}, L_{i}^{n+1}=l_{2}\right) \times \\ & P\left(L_{i}^{n+1}=l_{2} \mid L_{i}^{n}=l_{1}\right)=G_{i}^{l_{1} l_{2}}(t) P_{i}^{l_{1} l_{2}} \end{aligned}$

(8)

如图 2所示，通过马尔科夫模型预测用户从路段l₁移动到路段l₂的概率，显示用户1的历史时空状态信息，用户1在08：00到达路段l₁(T₁¹=8, L₁¹=l₁)，在10：00到达路段l₂(T₁²=10, L₁²=l₂)，……，在14：00到达路段l₅(T₁²=14, L₁²=l₅)，在路段l₁停留时间分别为S₁¹={2, 4, 6, 3, 6}。因为从l₁离开的路段总数为num_i^l₁=5，从l₁移动到l₂的总数为num_i^l₁l₂=3，所以从空间上得到 $P_{1}^{l_{1} l_{2}}=\frac{\mathrm{num}_{1}^{l_{1} l_{2}}}{\operatorname{num}_{i}^{l_{1}}}=3 / 5$，时间间隔设置为4 h，10：00和12：00到达l₂的时空状态满足该时间间隔，因此从时间上得到：

$\begin{aligned} G_{1}^{l_{1} l_{2}}(4)=& P\left(S_{1}^{1}=2 \mid L_{1}^{1}=l_{1}, L_{1}^{2}=l_{2}\right)+\\ & P\left(S_{1}^{1}=4 \mid L_{1}^{1}=l_{1}, L_{1}^{2}=l_{2}\right) 1 / 3+1 / 3=2 / 3 \end{aligned}$

综合时间和空间因素，用户1在4 h内从l₁到l₂的概率为 $Z_{1}^{l_{1} l_{2}}(t)=G_{1}^{l_{1} l_{2}}(t) P_{1}^{l_{1} l_{2}}=3 / 5 \times 2 / 3=2 / 5$。

定义3（隐性时空关联）  对于任意两个任务存在时空二元组 $\theta_{j_{1}}=\left\{T_{j_{1}}, P_{j_{1}}\right\}=\left\{\left[t_{j_{1}}^{\mathrm{s}}, t_{j_{1}}^{\mathrm{e}}\right], \left\{l_{1}\right\}\right\}, \theta_{j_{2}}=\left\{T_{j_{2}}, P_{j_{2}}\right\}=\left\{\left[t_{j_{2}}^{\mathrm{s}}, t_{j_{2}}^{\mathrm{e}}\right], \left\{l_{2}\right\}\right\}$。对于任意一个用户存在用户时空信息三元组 $\omega_{i}=\left\{\left[t_{i}^{\mathrm{s}}, t_{i}^{\mathrm{e}}\right], \left\{l_{1}, l_{2}\right\}, c_{i}\right\}$以及通过马尔科夫模型得到的预测三元组$\omega_{i}^{\prime}=\left\{\left[t_{i}^{\prime \mathrm{s}}, t_{i}^{\prime \mathrm{e}}\right], \left\{l_{1}, l_{2}\right\}, c_{i}^{\prime}\right\}$ 。如果满足式（9）~式（13），则认为该用户存在隐性时空关联：

$\left\{\begin{array}{l}T_{j_{1}} \cap T_{j_{2}}=\phi \text { or } P_{j_{1}} \cap P_{j_{2}}=\phi &&&&&(9)\\ t_{i}^{\mathrm{s}} \leqslant t_{j_{1}}^{\mathrm{s}} \text { and } t_{i}^{\mathrm{e}} \geqslant t_{j_{1}}^{\mathrm{e}} \text { and } P_{j_{1}} \in P_{\omega_{i}} &&&&&(10)\\ t_{i}^{\mathrm{s}}>t_{j_{2}}^{\mathrm{s}} \text { or } t_{i}^{\mathrm{e}}<t_{j_{2}}^{\mathrm{e}} \text { or }\left(! P_{j_{2}} \in P_{\omega_{i}}\right) &&&&&(11)\\ t_{i}^{\prime \mathrm{s}} \leqslant t_{j_{2}}^{\mathrm{s}} \text { and } t_{i}^{\prime e} \geqslant t_{j_{2}}^{\prime e} \text { and } P_{j_{2}} \in P_{\omega_{i}}^{\prime} &&&&&(12)\\ Z_{i}^{P_{j_{1}} P_{j_{2}}}\left(t_{j_{2}}^{\mathrm{s}}-t_{j_{1}}^{\mathrm{e}}\right) \geqslant \alpha&&&&&(13)\end{array}\right.$

式（9）表示两个感知任务不存在任何显性时空关联，即两个完全独立的感知任务。式（10）表示用户i的第1个时空信息三元组ω_i可以参与任务j₁，即满足第1个感知任务的时空要求。式（11）表示ω_i不满足第2个感知任务ω_i'的时空要求。式（12）表示用户i的第2个信息三元组可以参与任务j₂，即满足第2个感知任务的时空要求。式（13）表示用户i在 $\left(t_{j_{2}}^{\mathrm{s}}-t_{j_{1}}^{\mathrm{e}}\right)$时间间隔内（第2个感知任务开始时间与第1个感知任务结束时间的差值），从路段P_j1移动到路段P_j2的概率需要大于设定的阈值a，只有满足该条件，马尔科夫模型预测用户i的时空状态才能被认为是相对准确的。

隐性时空关联状态如图 3所示。目前已知感知任务1和感知任务2，感知任务1的感知时间间隔为01：00—03：00、感知任务2的感知时间间隔为04：00—06：00；用户A在感知时间间隔01：00—03：00内停留在感知任务1的感知区域，通过预测1 h后的时空状态得到用户A在感知时间间隔04：00—06：00内停留在任务2的感知区域。

由于用户A为隐性时空关联，因此用户A的时空状态满足感知任务1的时空要求，通过预测1 h后用户A的时空状态，用户A还可以完成感知任务2的时空要求，存在有效预测的时空状态，即在感知时间间隔04：00—6：00内停留在感知任务2的感知区域。

2.4 最大化社会收益问题模型

定义4（用户收益）  群智感知平台给用户的报酬与用户参与任务的花费之间的差值即为用户收益u_i，即：

$u_{i}=\left\{\begin{array}{l}0, \forall j \in S, x_{i j}=0 \\ p_{i}-\sum\limits_{j \in\left\{j |x_{i j}=1, j \in S\right\}} c_{i j}, \text { 其他 }\end{array}\right.$

(14)

对于所有感知任务，如果用户一个感知任务都没有完成，则表示用户没有参与任何感知任务，收益为0，x_ij表示用户i没有参加感知任务j，x_ij表示用户i参加感知任务j。如果用户完成任务，则有相应收益，p_i表示平台给用户的报酬，c_ij表示用户i参与任务j的总花费。

定义5（社会收益）  社会收益包含平台收益和用户收益，即：

$\begin{aligned} w=&\left(\sum\limits_{j \in S} v_{j}-\sum\limits_{i \in U} p_{i}\right)+\sum\limits_{i \in U} u_{i}=\left(\sum\limits_{j \in S} v_{j}-\sum\limits_{i \in U} p_{i}\right)+\\ &\left(\sum\limits_{i \in U} p_{i}-\sum\limits_{i \in U} \sum\limits_{j \in\left\{j\mid {x}_{i j}=1, j \in S\right\}} c_{i j}\right)=\\ & \sum\limits_{j \in S} v_{j}-\sum\limits_{i \in U} \sum\limits_{j \in\left\{j\mid {x}_{i j}=1, j \in S\right\}} c_{i j} \end{aligned}$

(15)

其中，v_j表示平台收益。可以发现平台给用户的报酬被抵消，因此得出社会收益由平台收益和用户参与任务的花费之间的差值所决定。社会收益越大，平台和用户会获得更多的收益，双方会更加有动力去完成群智感知任务，有利于平台对于优质用户的激励。

建立如式（16）所示的目标函数，考虑时空关联的情况下实现最大化社会收益并完成用户激励。

$\max \left(\sum\limits_{j \in S} v_{j}-\sum\limits_{i \in U} \sum\limits_{j \in\left\{j\mid {x}_{y}=1, j \in S\right\}} c_{i j}\right)$

(16)

在所有感知任务发布确定的情况下，由于平台收益固定，即v_j为固定值，因此为最大化社会收益，则需要最小化用户总花费。目标函数转化为时空关联情况下最小化用户总花费并完成用户激励：

$\min \sum\limits_{i \in U} \sum\limits_{j \in\left\{j \mid x_{y}=1, j \in S\right\}} c_{i j}$

(17)

受限于：

$\sum\limits_{i \in U} \sum\limits_{j \in S} x_{i j}=n$

(18)

$\forall j \in S, \sum\limits_{i \in U} x_{i j}=1$

(19)

$\forall j \in S, i \in U, x_{i j}=\{0, 1\}$

(20)

式（18）表示所有感知任务由用户完成；式（19）表示所有任务只能分配给一个用户完成；式（20）表示x_ij为0或1，1表示用户i完成任务j，反之用户无法完成该任务。如果是显性时空关联问题，则需满足式（1）~式（4）；如果是隐性时空关联问题，则需满足式（9）~式（13）。

3 用户激励机制设计

定理1   基于时空关联性的用户激励问题为NP-Hard问题。

证明  为证明STIM问题是NP-Hard问题，将该问题转化为传统最小化集合覆盖问题。因为最小化集合覆盖问题是NP-Hard问题，所以STIM问题是NP-Hard问题。给定包含n个元素的总集合U和一系列集合U的子集S₁S₂, ..., S_k，并且每一个子集S_k都有花费C_k，为保证总集合U被全部覆盖，传统最小化集合覆盖算法最终选择总花费最小且集合覆盖个数多的子集，即 $\min \frac{c_{k}}{U \cap S_{k}}$。STIM问题的给定情况为多个包含2个元素（时间和空间）的感知任务总集合θ和一系列用户的时空集合 $\omega_{1}, \omega_{2}, \cdots, \omega_{k}$，其中用户集合包含3个元素（时间、空间和花费），需要确保感知任务总集合θ被完全覆盖。为最小化用户花费，STIM问题可转化为传统最小化集合覆盖问题，因此STIM问题即为NP-Hard问题得以证明。

3.1 基于显性时空关联的用户激励算法

由于STIM问题是NP-Hard问题，因此利用贪婪算法求解该问题。基于显性时空关联的用户激励算法DTS如算法1所示，贪婪策略的核心是最小化用户总花费和集合覆盖个数的比值，即 $\min \frac{c(S)}{|S \cap T|}$。

算法1   基于显性时空关联的用户激励算法

输入   感知任务时空集合θ，用户时空集合ω

输出   招募的用户集合a，用户总花费C

1. $\alpha \leftarrow \varphi, \mathrm{T} \leftarrow \varphi, \mathrm{S} \leftarrow \phi, \mathrm{C}=0$//初始化变量

2.WHILE T ≠ θ DO//循坏终止条件为所有任务时空集//合被覆盖

3.β=0；ε←ϕ；μ←ϕ；//初始化变量

4.FOR EACH $\gamma \in \omega$ DO//遍历任务时空集合

5. $\mathrm{S}=\gamma \cap \;$ θ；//得到用户时空集合和任务时空集合的交集

6. $\mathrm{IF} \;\mathrm{S} \neq \phi \mathrm{THEN} \varphi=\mathrm{c}(\mathrm{S}) /|\mathrm{S}|$；//计算贪婪策略比值

7.IF $\varphi>\beta \;\mathrm{THEN}$ //如果当前贪婪策略比值比历史贪婪//策略比值大

8.β=φ；ε←γ；μ←S；//记录该比值、用户和交集

9.END FOR

10.α←α∪ε,C=C+c(μ)//招募具有最大比值的用//户并增加花费

11.T←T∪μ,θ←θ-μ//增加被覆盖任务的时空集//合，目标覆盖任务的时空集合减去用户提供的时空集合

12.END WHILE

13.FOR EACH γ∈α AND γ'∈α DO//遍历所有招募的//用户集合

14.γ ∩ γ'；//得到两个用户的时空集合交集

15.IF τ ≠ ϕ THEN C = C-c(τ)//减去重复的花费

16.END FOR

17.输出招募的用户集合α，用户总花费C

以DTS算法为例，已知感知任务的时空要求 $\theta=\{\{[1: 2], \{A\}\}, \{[2: 3], \{B\}\}, \{[3: 4], \{C\}\}\}$，用户1的时空集合为 $\omega_{1}=\{[1: 2], \{B\}, 3\}$，用户2的时空集合为 $\omega_{2}=\{[2: 3], \{B\}, 4\}$，用户3的时空集合为 $\omega_{3}=\{\{[1: 2], [2: 3]\}, \{A, B\}, 5\}$，用户4的时空集合为$\omega_{4}=\{\{[2: 3], [3: 4]\}, \{B, C\}, 9\}$ 。DTS算法得到结果为招募用户3和用户4，最终总花费为9+5-4=10。因为用户3和用户4具有相同的时空状态，即用户2的时空状态为$\omega^{\prime}=\{[2: 3], \{B\}, 4\}$ 。

3.2 基于隐性时空关联的用户激励算法

在解决隐性时空关联的用户激励问题时，考虑用户的历史时空状态以及用户当前提交的时空状态，利用马尔科夫模型预测用户的未来时空状态，再结合显性时空关联的用户激励算法得到最终结果。基于隐性时空关联的用户激励算法RTS如算法2所示。

算法2  基于隐性时空关联的用户激励算法

输入  感知任务时空集合θ，用户时空集合ω用户历史时空集合δ，预测概率阈值ρ

输出  招募的用户集合α，用户总花费C

1.FOR EACH $\gamma \in \omega$ DO //遍历用户时空集合

2.IF $\omega_{\gamma}^{1} \in \delta \mathrm{AND} \mathrm{Z}_{\gamma}^{1, 1+1} \geqslant \rho$THEN//如果用户当前l状态//的时空集合属于用户历史时空集合，并且预测得到l+1//（下一个状态）的时空集合的准确概率大于ρ

3. $\omega_{\gamma} \leftarrow \omega_{\gamma} \cup \omega_{\gamma}^{1+1}$ //预测后的时空集合加入原用户中

4.END FOR

5.调用算法1 $\operatorname{DTS}(\theta, \omega)$

6.输出招募的用户集合 <italic>a</italic>，用户总花费C

以RTS算法为例，已知感知任务的时空要求： $\theta=\{\{[1: 2], \{A\}\}, \{[2: 3], \{B\}\}, \{[3: 4], \{C\}\}\}$，用户1的时空集合为 $\omega_{1}=\{\{[1: 2], [2: 3], [3: 4]\}, \{A, B, C\}, 10\}$，用户2的时空集合为 $\omega_{2}=\{\{[1: 2], [2: 3]\}, \{A, B\}, 5\}$。经过马尔科夫模型预测后得到最终结果为$\omega_{2}=\{\{[1: 2], [2: 3], [3: 4]\}, \{A, B, C\}, 7\}$ 。因为预测的时空状态 $\omega^{\prime}=\{[3: 4], \{C\}, 6\}$，花费要比用户本身直接提供的时空集合花费低，所以RTS算法得到的结果为招募用户2，总花费为7。

4 实验与结果分析 4.1 仿真数据设置

仿真数据实验时间序列列举24 h，即24个点，空间序列列举26个点。单一感知任务的时空要求分别从时间序列和空间序列中随机各取一个点构成，需要注意多个感知任务的时空要求不能重复，在此实验环境下最多产生24×26=624个感知任务，因此选择400个感知任务作为基数。单一用户的时空集合分别从时间序列和空间序列中各取一个点构成，时间序列先随机选中一个开始时间点，然后按照顺序选取 $1 \rightarrow 2 \rightarrow \cdots \rightarrow 24 \rightarrow 1 \rightarrow 2 \rightarrow \cdots \rightarrow 24$；空间序列随机选取，为完成所有感知任务，最终选择10 000个用户作为基数。设置一天工作时间为8 h，因此默认单一用户提供的时空集合数为8。预测概率阈值默认设置为0.80。本文实验采用单一变量法控制思想，在改变某一参数值的情况下，其他参数值皆为默认参数值。

本文提出的显性时空关联算法DTS为执行MCO算法后去掉重复的时空集合并减去相应的花费，隐性时空关联算法RTS为经过预测得到预测时空集合后执行DTS算法，其实验对比算法具体如下：1）最小化花费（Minimum Cost，MC）算法，每次选择花费低的用户；2）最大化覆盖（Maximum Overlap，MO）算法，每次选择时空集合覆盖最多的用户；3）最小化花费覆盖数比值（Minimum Cost Overlap，MCO）算法，每次选择花费和集合覆盖个数比值小的用户。本文实验对比参数为总花费、用户选择数和迭代次数，可变参数为感知任务数、用户数、单一用户提供的时空集合数和预测概率阈值。

4.2 仿真数据的实验结果分析

图 4表示感知任务数对总花费的影响。随着感知任务数的增加，5种算法的总花费都增加，主要原因为平台需要招募更多的用户来完成更多的感知任务，所以总花费增加。对于总花费而言，算法顺序依次为RTS < DTS < MCO < MO < MC，其中MC总花费最高，因为感知任务越多，需要完成的时空集合越多，招募的时空集合个数少的用户越多，而时空集合个数少的用户花费小于时空集合个数多的用户，但多个时空集合个数少的用户总花费远大于单一时空集合个数多的用户，因此涨幅最大；MO < MC主要原因为MO优先选择时空集合覆盖多的用户，单一用户提供的时空集合越多，该单一用户的总花费越低，随着感知任务数的增加，MO会招募越来越多的时空集合覆盖越来越多的用户来完成所有任务；由于MCO是综合选择花费与覆盖集合个数的比值小的用户，因此MCO < MO；DTS < MCO的主要原因为DTS在MCO的基础上去除了重复的时空集合，所以删减了相应的花费；RTS在DTS的基础上，预测用户未来的时空集合并提供更多的时空集合，同时隐性部分时空集合对应的花费比原时空集合低，因此RTS < DTS。

图 5表示感知任务数对用户选择数的影响。随着感知任务数的增加，5种算法的用户选择数随之增加，主要原因为平台需要招募更多的用户来完成更多的感知任务。对于用户选择数而言，算法顺序依次为RTS < DTS=MCO < MO < MC。基本规律及原因和总花费大致相同，但不同的是DTS和MCO，因为DTS在MCO执行完成后对已确定选择的用户进行重复时空集合的减少操作，但并不会减少用户数量，所以DTS=MCO。

图 6表示感知任务数对迭代次数的影响。随着感知任务数的增加，5种算法的迭代次数随之增加，主要原因是为完成所有感知任务，平台需要招募更多的用户来完成更多的感知任务，所以相应算法的迭代次数会增加。对于迭代次数而言，算法顺序依次为RTS < MCO < DTS < MO < MC。基本规律及原因和总花费大致相同，但不同的是RTS < MCO < DTS，因为DTS在MCO执行完成后，对已确定选择的用户进行重复时空集合的删减操作，此时会增加迭代次数，而RTS迭代次数最少，虽然RTS比DTS增加预测操作，进一步增加迭代次数，但是由于其提供更多花费低的时空集合，因此导致RTS在招募用户时会大幅减少迭代次数。

图 7表示用户数对总花费、用户选择数和迭代次数的影响。总体而言，随着用户数的增加，5种算法得到的总花费、用户选择数和迭代次数基本没有太大变化，大致呈现小幅度减少趋势，甚至有时出现总花费高、用户选择数多和迭代次数多的情况。其主要原因为平台发布的感知任务数已经固定，虽然用户数增加，但符合感知任务时空要求的用户数不一定再增大，反而会出现更多时空集合覆盖少、花费高的用户。因此，对于总花费和迭代次数而言，算法顺序依次为RTS < DTS < MCO < MO < MC；对于用户选择数而言，算法顺序依次为RTS < DTS=MCO < MO < MC。

图 8表示用户时空集合数对于总花费、用户选择数和迭代次数的影响。随着单用户时空集合数增加，用户选择数以及迭代次数持续减少，但是总花费持续增加，对于MC而言，增大幅度最大，其主要原因为相对于单用户时空集合个数少的情况，MC每次选择的用户是花费较高的用户（时空集合多且花费高），而且这些用户的时空集合中只有少部分符合感知任务的时空要求，因此MC涨幅最大；DTS和RTS基本保持不变，用户的时空集合多，总花费高。因此，对于总花费和迭代次数而言，算法顺序依次为RTS < DTS < MCO < MO < MC，对于用户选择数而言，算法顺序依次为RTS < DTS=MCO < MO < MC。

图 9表示预测概率阈值增大对于总花费、用户选择数和迭代次数的影响。预测概率阈值的增大主要影响RTS算法，可以看出其他4种算法的预测概率阈值增大对于总花费、用户选择数和迭代次数的影响较小。随着预测概率阈值的增大，预测得到的用户时空状态集合越来越少，RTS得到的结果越来越趋近DTS。因此，对于算法的总花费和迭代次数顺序依次为RTS < DTS < MCO < MO < MC；对于算法用户选择数顺序依次为RTS < DTS=MCO < MO < MC。

4.3 真实数据集设置

真实数据集实验采用意大利罗马30天内320辆出租车的轨迹数据集^[21]，采集时间为2014年2月1日至2014年3月2日，约7 s更新一次经纬度，数据格式为出租车ID、日期时间、经纬度。为更加契合仿真实验的参数设置，将罗马地区分为大小为100×100的网格，每辆出租车的轨迹经纬度转化为网格序号，表示出租车所在的空间范围；将每辆出租车进入和离开网格的时间表示出租车的时间范围。实验中用户数及单一用户提供的时空集合数为固定，因此改变感知任务数和预测概率阈值来验证算法的有效性，其他参数设置和仿真数据实验参数设置保持一致。

4.4 真实数据集的实验结果分析

图 10表示感知任务数对总花费、用户选择数和迭代次数的影响。对比仿真数据实验结果，对于总花费而言，算法顺序依次为RTS < DTS < MCO < MC < MO。在仿真数据实验中感知任务数增大对于总花费影响中MO < MC，其主要原因为真实数据集中用户有大量的时空集合，但是仿真数据模拟很多仅有一个时空集合的用户，导致真实数据集实验中MC招募少量时空集合的用户数量大幅减少，总花费小于MO。对于用户选择数而言，算法顺序依次为RTS < DTS=MCO < MO < MC；对于迭代次数而言，算法顺序依次为RTS < DTS < MCO < MO < MC。

图 11表示预测概率阈值对总花费、用户选择数和迭代次数的影响。对比仿真数据实验的结果，除了总花费的影响外，其他没有太大变化，规律和逻辑都与仿真数据实验一致，随着预测概率阈值的增加，RTS越来越趋近DTS。因此，对于总花费而言，算法顺序依次为RTS < DTS < MCO < MC < MO；对于用户选择数而言，算法顺序依次为RTS < DTS=MCO < MO < MC；对于迭代次数而言，算法顺序依次为RTS < DTS < MCO < MO < MC。

5 结束语

本文将时空关联的用户激励问题分为显性时空关联和隐性时空关联的用户激励问题，并提出RTS算法和DTS算法对其进行求解。通过仿真数据实验和真实数据集实验可以得出，RTS算法和DTS算法相比MC算法、MO算法、MCO算法具有更低的总花费、用户选择数和迭代次数，从而验证基于时空关联性的用户激励机制的有效性。然而本文在考虑隐性时空关联性时对于用户任务执行情况的预测存在不确定性，后续将对此做进一步研究，实现更高效的用户激励机制。