传统物联网受限于成本、灵活性和管理上的问题，大规模部署受到挑战。随着配备了多种嵌入式传感器的移动智能设备得到普及，出现了一种新的感知模式——群智感知^[1]。不同于由专用固定传感器组成的无线传感器网络^[2]，群智感知设备可利用其移动性以较低成本实现大规模、大范围感知任务。因此，群智感知受到广泛关注和研究^[3–6]。移动终端基本都具备短距离无线通信技术，如蓝牙（Bluetooth）或Wi-Fi等，为避免传统移动蜂窝网络信号强度覆盖不均匀及在特殊场景中不可用的问题，可利用短距离通信技术进行数据机会传输，这种特殊群智感知模式称为机会群智感知^[7]。

在机会群智感知网络中，由于任务的分配与完成都依靠着两节点在相遇时建立的通信链接进行数据通信，所以节点间的相遇时间对任务分配的决策有很大影响。节点的移动具有随机性，任务分发节点在分发任务时，与执行节点之间没有持续连接的通信链路，加之节点的具体信息难以准确获取，所以传统并行机调度^[8]领域的研究无法直接应用于机会群智感知网络。

为减少机会网络中完成感知任务的总时间，国内外已开展了多项研究。移动感知任务可能与任务执行节点的位置相关，针对这种情况，He等^[3]认为，制定位置相关的任务分配解决方案时需要考虑感知任务的地理特征和移动用户的移动性，并提出了两个有效的近似算法，即LRBA和DLBA，但是，文中并未考虑任务的属性，比如任务的质量要求，这在分配期间是必不可少的。Tang等^[9]研究了车载移动网络中的数据收集问题，为了解决智能设备中的存储有限问题，提出了选择策略的优先级概念，并提出了一种基于模拟退火的优先级分配算法，但是文中并没有考虑电池容量的限制。Maia等^[10]在求解优化任务完成时间的问题时，加入了电池容量的限制。Shi等^[11]提出了Water Filling算法用于任务分配，以最小化最长任务执行时间。该算法即不考虑移动节点的实时移动性，也不考虑移动节点的历史移动轨迹。Yao等^[12]以最小化最长任务完成时间为目标，提出了相遇概率敏感的离线和在线任务分配算法。Xiao等^[13]以最小化平均任务完成时间为优化目标，提出了NTA算法，并证明了其近似比与平均任务工作量和节点期望相遇时间相关，但要求分配节点掌握所有节点的信息。徐哲等^[14]针对最小化任务平均完成时间的多任务分发问题，提出一种基于中枢节点的多任务分发算法HTA，与文献[13]相同，该算法要求任务请求者掌握网络全局信息，即所有节点间的相遇概率，但是在实际应用中较难满足该条件。文献[13]中，针对移动节点间的相遇时间间隔采用了指数分布的假设，通过分析真实数据集可发现，指数分布描述的相遇间隔规律与实际情况之间仍有一定偏差，如人类的移动存在间隙性、人类的夜间活动较少甚至停止等情况下难以利用指数分布反映出来。综上所述，文献[11,13–15]等研究中需要掌握整个节点网络的全局信息，这对算法的应用环境提出了较高的要求，限制了算法的实用性。

作者利用局部信息，研究一种面向最小化任务平均完成时间、支持任务动态增加的在线分配算法。经过对真实数据集的分析发现，在机会群智感知网络中，虽然节点的移动具有自主性和随机性，但节点间在不同时刻的相遇仍然有一定的内在联系。基于节点的历史相遇记录可以寻找相遇间隔分布规律，进而对节点的相遇时间进行预测，由此，设计一种基于预测的在线多任务分配（online multi-task assignment based on prediction，OTAP）算法。OTAP算法的核心思想是每次给执行节点分配在与任务分发者下次相遇间隔内能完成的最大任务量，以降低感知节点在完成感知任务后及与任务发布者相遇提交任务结果之间的等待时间。基于unicalsocialblue^[16]、cambridge_city^[17]、infocom2005^[17]、intel^[17]等4个不同数据集，利用ONE机会网络模拟器^[18]进行充分实验，验证提出的节点相遇预测模型的准确性，该算法有效降低了机会群智感知网络中平均任务完成时间。

1 问题描述 1.1 网络模型

假设机会群智感知网络由 $n$ 个节点组成，节点用 ${v_i} (i = {\rm{0,1,2,3,}} \cdots ,n{\rm{ - 1}})$ 表示。每个节点均携带了具有一定计算、存储、通信能力的智能感知设备。节点间只通过短距离无线通信技术（如Wi-Fi、蓝牙等）建立连接并传输数据。假设节点间的数据传输可在一次相遇机会中完成。

1.2 任务模型

假设上述网络中有一个任务分发者，用 ${v_0}$ 表示。它有 $m$ 个相互独立的感知任务需要其他 $ n-1$ 个节点中的部分或全部节点执行。任务分配方案由 ${v_0}$ 确定。 ${v_0}$ 在与其他节点 ${v_i}$ 相遇时，将根据确定的任务分配策略,将若干任务分发给 ${v_i}$ 。 ${v_i}$ 花费一定量的时间完成被分配的任务。在完成感知任务后， ${v_i}$ 将一直等到与 ${v_0}$ 再次相遇时，再将所得到的任务结果返回给 ${v_0}$ 。使用 ${J_i}(1 \le i \le n - 1)$ 表示节点 ${v_i}$ 执行的任务集合， ${J_i} = \{ j_1^i,j_2^i, \cdots ,j_k^i\} $ ， ${v_i}$ 按照 $j_1^i$ 、 $j_2^i$ 一直到 $j_k^i$ 的顺序依次执行 ${J_i}$ 中的任务。

约束条件：1）每个时刻每个节点只能执行一个任务，每个任务只能被一个节点执行，且任务一旦开始执行不能被中断；2）不考虑任务的优先权。

定　义（任务完成时间makespan）　一个感知任务 ${j_k}$ 的完成时间为 $M({j_k}) = {t_{k1}} + {t_{k2}} + {t_{k3}}$ ，其中， ${t_{k1}}$ 为任务分发者开始分发任务 ${j_k}$ 到节点 ${v_i}$ 接收到任务 ${j_k}$ 的时长， ${t_{k2}}$ 为任务 ${j_k}$ 从节点 ${v_i}$ 接收到执行完成的时长， ${t_{k3}}$ 为节点 ${v_i}$ 将任务结果传递回任务分发者的时长。

1.3 问题描述

作者研究的问题是如何确定一种任务分配策略，使感知任务平均完成时间（average makespan，AM）最小化。用 $J = \{ {j_1},{j_2}, \cdots ,{j_m}\} $ 表示 $ m$ 个独立的感知任务， $ \varPi =({J_1},{J_2}, \cdots ,{J_{n - 1}}) $ 表示一种任务分配策略。当且仅当 ${J_i} \cap {J_j} = \varnothing ,i \ne j$ 且 $\displaystyle\sum\limits_{i=1}^{n- 1} { \cup {J_i} = J} $ ， ${v_0}$ 将 ${J_i}$ 中的所有任务全部分配给用户 ${v_i}$ ；如果 ${J_i}$ 为 $\varnothing$ ，任务分发者 ${v_0}$ 不分配任何任务给用户 ${v_i}$ 。

问　题（最小化平均完成时间的在线多任务分配问题）　 在机会群智感知网络中，给定一个节点集合 $V = ({v_{\rm{1}}},{v_{\rm{2}}}, \cdots ,{v_n})$ 、一个感知任务集合 $J = ({j_{\rm{1}}},{j_{\rm{2}}}, \cdots ,{j_m})$ ，每个感知任务 ${j_j}$ 有相应的任务工作量 ${p_j}$ 和发布时间 ${r_j}$ 。在时间 ${r_j}$ 之前，任务 ${j_j}$ 并不存在，任务分发者无法获知其任何信息。则最小化平均完成时间的在线多任务分配问题就是确定一个任务分配策略 $ \varPi {\rm{ = }}\left\{ {{J_1},{J_2},\cdots,{J_n}} \right\} $ ，使任务平均完成时间最小，即

$\min \;AM(\varPi ) = \frac{1}{m}\sum\limits_{i = 1}^m {M({j_i})} 。$

式中， $M({j_i})$ 表示任务 ${j_i}$ 的完成时间， $AM(\varPi )$ 表示任务分配策略 $\varPi $ 下所有任务的平均完成时间。

定理1 　在清楚所有节点彼此相遇时间的情况下，问题1为NP–完全问题。

证明：针对单机的最小化平均完成时间的在线多任务分配问题已被证明为NP–完全问题^[19–20]。而单机情况为问题1的特例，故问题1为NP–完全问题。证毕

2 基于预测的在线任务分配算法 2.1 节点移动模型

以往对移动机会网络中任务分配问题的研究均假设节点相遇间隔时间服从指数分布^[20]，基于对多个真实数据集中记录的分析，发现这些数据集中普遍存在一个规律是：节点间的相遇间隔往往存在周期性，即两个节点在长度为 ${T_1}$ 的一段时间内频繁相遇，在之后一段长度为 ${T_2}$ 的时间内又几乎不相遇，如此反复。若将上述过程定义为一个相遇周期，则周期为 $T = {T_1} + {T_2}$ 。以cambridge_city数据集中2号节点为例，图1展示了其与其他节点的相遇情况统计，横轴为时间，纵轴为相遇节点的序号。由图1可以看出2号节点与其他节点间相遇存在周期性。

2.2 节点相遇规律发现算法

根据第2.1节中对节点移动规律的分析，可将两个节点的相遇序列划分为交替的持续相遇阶段和长间隔阶段，其中，持续相遇阶段由短持续时长 $t_ {\rm{s}}^\theta $ 所在序列组成，长间隔阶段由长相遇间隔 $t_ {\rm{l}}^\theta $ 所在序列组成。根据历史相遇记录，判断当前相遇时刻是否处于持续相遇阶段，预测未来相遇时间间隔。短持续时长 $t_ {\rm{s}}^\theta $ 和长相遇间隔 $t_ {\rm{l}}^\theta $ 的定义如下：

对于两个节点的一段相遇时间序列 $\{ {T_1},{T_2}, \cdots ,{T_n}\} $ ，若存在一段最长子序列 $\{ {T_i},{T_{i + 1}}, \cdots ,{T_j}\} $ ，满足 $\forall i \le k < j,{T_{k + 1}} - {T_k} < \theta $ 且 ${T_{j + 1}} - {T_j} \ge \theta $ ，则称 ${T_j} - {T_i}$ 为 $\theta $ 参数的短持续时长,记为 $t_ {\rm{s}}^\theta $ ；称 ${T_{j + 1}} - {T_j}$ 为 $\theta $ 参数的长相遇间隔，记为 $t_ {\rm{l}}^\theta $ 。

节点相遇规律发现算法的基本思路是：

1）遍历所有相遇记录，将两次相邻相遇间隔 $T' <\theta $ 的记录合并，并将合并后的新记录的持续时间增加 $T'$ 。

2）将新生成的记录序列的平均时间间隔记为长相遇间隔 $t_{\rm{l}}^\theta $ ，持续时间的平均值为短持续时长 $t_{\rm{s}}^\theta $ 。

具体实现步骤见算法1。

算法1 　节点相遇规律发现算法（getHistoryRule）

输入：两节点间相遇记录序列 $R$ 、阈值 $\theta $ 。

输出：两节点相遇的长时间间隔 $t_{\rm{l}}^\theta $ 、短持续时长 $t_{\rm{s}}^\theta $ 。

1. 遍历 $R$ ，若相邻两次相遇记录 ${r_1}$ 和 ${r_2}$ 的时间间隔小于 $\theta $ ，则对 ${r_2}$ 做标记；

2. 根据未被标记的记录将 $R$ 分割为若干子序列 ${a_1},{a_2}, \cdots ,{a_x}$ ，未被标记的记录作为首元素；

3. 统计所有子序列 ${a_1},{a_2}, \cdots ,{a_x}$ 中的第1条记录和最后一条记录之间的时间间隔，并求平均值记为 $t_{\rm{s}}^\theta $ ，若子序列长度为1，则时间间隔为零；

4. 提取每个子序列 ${a_i}$ 的第1条记录组成新的子序列 $b$ ，并统计这些记录间的时间间隔，求其平均值记为 $t_{\rm{l}}^\theta $ ，若子序列 $b$ 的长度为1，则 $t_{\rm{l}}^\theta $ 等于无穷大；

5. 返回 $t_{\rm{l}}^\theta $ 、 $t_{\rm{s}}^\theta $ 。

2.3 任务分配子算法

要使平均任务完成时间最小，即所有任务的完成时间的总和最小。根据第1.2节对任务完成时间的定义，由于任务的工作量固定不变，即执行阶段所消耗的时间是定值。因此，应使分发任务和返回任务结果两个阶段的时间最小。

制定任务分配策略：预测节点间的相遇间隔，每次给执行节点分配在与任务分发者下次相遇间隔内能完成的最大任务量。任务分配子算法的基本思路是：

1）根据相遇历史记录，通过算法1计算节点间相遇规律,得到短持续时长 $t_{\rm{s}}^\theta $ 和长相遇间隔 $t_{\rm{l}}^\theta $ 。

2）获取最近一次长相遇间隔后的第1次相遇时刻 $t'$ 和空闲时刻 $idl{e_i}$ 。

3）根据 $t'$ 和 $t_{\rm{s}}^\theta $ 预测本次持续相遇阶段结束时间 ${t_{\rm{e}}} = t' + t_{\rm{s}}^\theta $ 。

4）如果 ${t_{\rm{e}}}{\rm{ - }}t$ 大于 $t_{\rm{s}}^\theta \times \omega $ ，将预期分配任务量 $\varDelta $ 设置为 ${t_{\rm{e}}} - idl{e_i}$ ；否则， $\varDelta = {t_{\rm{e}}} + t_{\rm{l}}^\theta - idl{e_i}$ 。其中： $ t$ 为当前时刻； $\omega $ 为分配因子，控制分配持续相遇阶段所执行任务的时间窗口在持续相遇阶段所占比例。

5）将待分配任务集中的任务依次分配给节点，直到本次已分配任务的任务量之和大于 $\varDelta $ 为止。

该算法具体步骤见算法2。算法2在获取待分配任务集时，并未要求获取所有的任务信息；同时，利用已有节点间相遇历史对下一次相遇间隔进行预测，因此能够适应任务在线分配的要求。

算法2 　任务分配子算法（assignTasks）

输入：待分配任务集 $J = ({j_{\rm{1}}},{j_{\rm{2}}}, \cdots ,{j_m})$ 、相遇节点 ${v_i}$ 、当前时刻 $t$ 、相遇节点 ${v_i}$ 的空闲时刻 $idl{e_i}$ 、最近一次长时间间隔后的第1次相遇时刻 $t'$ 、长相遇间隔 $t_{\rm{l}}^\theta $ 、短持续时长 $t_{\rm{s}}^\theta $ 、分配因子 $\omega (0 < \omega )$ 。

输出：相遇节点分配到的任务集 ${\varPi _i}$ 。

1. 初始化：将结果置为 $\varnothing$ ， $\varDelta {\rm{ = }}0$

2. ${t_{\rm{e}}} = t' + t_{\rm{s}}^\theta $ ；

3. if $t' = = - 1$ 或 ${t_{\rm{e}}} - t > t_{\rm{s}}^\theta \times \omega $ do

4.　 $\varDelta {\rm{ = }}t' + t_{\rm{s}}^\theta - idl{e_i}$ ；

5. else if ${t_{\rm{e}}} - t \le t_{\rm{s}}^\theta \times \omega $ do

6.　 $\varDelta {\rm{ = }}t' + t_{\rm{l}}^\theta - idl{e_i}$ ；

7. if $\varDelta > 0$ do

8. 将 $ J$ 中的任务按任务量从小到大的顺序分配给节点 ${v_i}$ ，直到新分配任务的任务量之和大于 $\varDelta $ ，或已分配完成所有任务；

9.将新分配的任务加入结果中；

10. return 结果。

2.4 整体任务分配框架

第3.2、3.3节的算法是作者所设计算法的核心内容，下面介绍算法的整体框架,详见算法3。算法3使用算法1进行节点相遇规律计算得到两节点的长相遇间隔和短持续时长用于预测节点相遇时间，使用算法2作为任务分配算法计算得到分配策略。

由于分配到每个节点的任务数一般为多个，所以还涉及到单机任务调度问题，依据最小化平均完成时间的求解目标可知节点应按照任务工作量从小到大的顺序执行。

算法3 　在线多任务分配算法（OTAP）

输入：待分配任务集 $J = ({j_{\rm{1}}},{j_{\rm{2}}}, \cdots ,{j_m})$ 、候选节点集 $V = ({v_{\rm{1}}},{v_2}, \cdots ,{v_n})$ 、候选节点与任务分发节点的相遇历史记录 $ H$ 、阈值 $\theta $ 、分配因子 $\omega (0 < \omega )$ 。

输出：分配策略 ${\varPi _i}$ 。

1.将 $ H$ 按 $ V$ 中节点分组，并按时间先后排序得 $R{\rm{ = (}}{r_1}{\rm{,}}{r_2}{\rm{,}} \cdots {\rm{,}}{r_k})$ ；

2. for $i \in [1,n - 1]$ do

3.　 ${J_i} = \varnothing $ ；

4.　 $idl{e_i} = 0$ ；

5.　 ${\tau _i} = 0$ ；/*记录 ${v_0}$ 与 ${v_i}$ 最后一次相遇的时刻*/

6. $\varPi {\rm{ = }}\left\{ {{J_1},{J_2}, \cdots ,{J_n}} \right\}$ ；

7. for ${r_i} \in R$ do

8. 　 $(t_{{\rm{l}},i}^\theta ,t_{{\rm{s}},i}^\theta )$ =getHistoryRule $({r_i},\theta )$ ；/*调用算法1*/

9. 对 $ J$ 中任务按任务量从小到大排序得有序数组 $J'$ ；

10. While每次与某节点 ${v_j}$ 相遇 and任务未分配完毕 do

11.　令 $ t$ 为当前时刻；

12.　if $idl{e_j} < t$ do

13.　　 $idl{e_j} = t$ ；

14.　if ${\tau _j} = = 0$ 或 $t - {\tau _j} > t_{{\rm{s}},j}^\theta $ do

15.　　 ${\tau _j} = t$ ；

16. ${J_j}'$ =assignTasks $(J',{v_j}, t,idl{e_j},{\tau _j},t_{{\rm{l}},j}^\theta ,t_{{\rm{s}},i}^\theta ,\omega )$ ；/*调用算法2*/

17. 将 ${J_j}'$ 中的全部任务分配给 ${v_j}$ 执行， $ J' = J' -$ ${J_j}'$ ， ${J_i} + = {J_j}'$ ；

18.　 $idl{e_j}{\rm{ + = sum(}}{J_j}')$ ；

19. return $\varPi $ 。

3 算法分析

对算法各部分的复杂度和可行性进行分析。

定理2 　算法3的复杂度为 $O(nk + m\log m)$ ，其中, $n$ 为网络中节点个数， $k$ 为相遇记录个数， $m$ 为待分配任务个数。

证明：首先对算法1的复杂度进行证明。算法1将相遇记录序列划分为两个子序列，再分别遍历每个子序列作加减操作，最多做 ${\rm{2}}k$ 次基本操作，因此复杂度为 $O\left( k \right)$ 。

算法2中，对于7～8行的语句，最坏情况下的执行次数为 $m$ 次，因此算法2的复杂度为 $O\left( m \right)$ 。

算法3中，首先，对 $n{\rm{ - 1}}$ 个节点调用 $n{\rm{ - 1}}$ 次算法1，因此该部分的复杂度为 $O\left( {nk} \right)$ ；接着，对所有任务进行排序，设任务个数为 $m$ ，则排序任务的复杂度为 $O(m\log m)$ ；然后，调用若干次算法2，直至所有任务分配完毕，由于最多分配 $m$ 个任务，因此该部分的复杂度为 $O(m)$ ；所以，算法3的复杂度为 $O(nk + m\log m)$ O(nk+mlog m)。证毕

算法3在对节点 ${v_i}$ 进行任务分配时只用到节点 ${v_i}$ 自身的历史相遇记录，不涉及其他节点，即不需要了解全局信息。由于算法2使用渐进式分配策略，并非一次性将任务分配给节点 ${v_i}$ ，算法3中的待分配任务集可以是动态增加的，因此，算法3具有实时在线分配的能力。与离线多任务分配算法相比，算法3的竞争比是由节点间相遇间隔的预测准确度决定的。

4 性能评估 4.1 实验环境

采用ONE（opportunistic networking environment）机会网络模拟器^[18]，使用Crawdad网站提供的4个移动轨迹数据集cambridge_city、infocom2005、intel和unicalsocialblue对OTAP算法的性能进行评估。两个对比算法为：作者实现的NTA算法，及依据文献[13]给出的计算方法得到了最优任务分配策略，前提是将节点间未来的相遇时刻作为已知条件。选择任务平均完成时间、任务完成率作为性能评价指标。任务完成率定义为是 $\displaystyle\frac{{{\rm{|}}{J_{\rm{f}}}|}}{{|J|}}$ ，其中， ${\rm{|}}{J_{\rm{f}}}|$ 表示截止到移动轨迹数据集的最后一条相遇记录时任务分发者成功接收到执行结果的任务数量， $|J|$ 表示待分配任务的总数。

因为OTAP、NTA算法均需要根据一定数量的历史记录对节点间的相遇规律进行分析，因此实验中需要划分数据集为训练集和测试集。训练集用于算法初始化阶段的规律分析，测试集作为任务分发过程中节点间的相遇记录。数据集的详细介绍及参数配置见表1。此外，使用的感知任务集为通过程序以均匀分布的统计特性随机生成，任务集规模为50、100、150、200、250、300时，最小工作量为100 s，最大工作量为2 000 s。

根据对数据集中各节点的相遇间隔进行采样统计分析后，可知所有节点在相遇时间间隔分布上以小于1时和大于等于2 h为主要分布点；并且根据对部分数据的初步试验，发现 $\omega $ 设置为0.75时，算法在各数据集的性能最稳定。因此，将算法1中参数 $\theta $ 设置为1 h，算法2中参数 $\omega $ 设置为0.75。

4.2 实验结果

首先，评估算法的任务平均完成时间。图2对比了在4种不同移动轨迹数据集中，采用OTAP、NTA算法以及最优策略对不同配置的任务集进行任务分配时所得到的任务平均完成时间。

从图2可以看出，OTAP算法在4个不同移动轨迹数据集中分配各任务集时所得到的平均完成时间均低于NTA算法，但比最优任务分配策略高。在4个不同移动轨迹数据集unicalsocialblue、cambridge_city、infocom2005、intel中，OTAP算法在不同任务集规模中所得到的平均任务完成时间比NTA算法平均缩短了50.49%、45.34%、32.71%、32.23%。

评估算法性能的另一个指标是任务完成率。图3对比了使用4个不同移动轨迹数据集进行实验时，OTAP、NTA算法、最优任务分配策略在任务完成数与任务集规模的关系（即任务完成率）。如图3（a）所示，OTAP和NTA算法所得任务完成率均达到了100%。如图3（b）和（d）所示,在cambridge_city和intel数据集中，OTAP算法的任务完成率高于NTA算法，平均分别高了16.55%、4.57%。如图3（c）所示，在infocom2005数据集中，除任务集规模为50时以外，OTAP的任务完成率均低于NTA算法，平均低了2.75%。其具体原因在于：infocom2005数据集的活动时间较短；OTAP算法在分析和利用节点移动规律时，没有充分发挥出其优势。

图4对比了4个不同数据集中，任务集规模为300时，OTAP、NTA算法以及最优任务分配策略的任务完成率与时间的关系。从图4中可以看出OTAP算法比NTA算法的任务策略完成更快。

5 结　论

针对机会群智感知网络中的多任务在线分配问题开展研究。基于真实数据集分析了移动节点的相遇规律，将节点间相遇过程分为若干周期，每个周期包含持续相遇阶段和长间隔阶段。据此规律设计了一种基于预测的在线任务分配（OTAP）算法，以缩短任务平均完成时间。OTAP算法的核心思想是对节点间的相遇间隔进行预测，每次给执行节点分配在与任务分发者下次相遇间隔内能完成的最大任务量。在4个不同数据集上进行实验，结果显示本文提出的OTA算法比NTA算法缩短了至少32.23%的任务平均完成时间，同时,任务完成率在其中两个移动轨迹数据集中也有所提高。在未来的研究工作中，将基于不同感知任务的相关性分析、感知任务分布与用户移动性的时空关联分析等对机会群智感知任务分配机制做进一步优化。