工程科学与技术   2018, Vol. 50 Issue (5): 176-182
OTAP：基于预测的机会群智感知多任务在线分配算法

1. 北京信息科技大学 网络文化与数字传播北京市重点实验室，北京 100101;
2. 北京信息科技大学 计算机学院，北京 100101

OTAP: Online Multi-task Assignment Algorithm with Prediction for Opportunistic Crowd Sensing
LI Zhuo1,2, XU Zhe2, CHEN Xin2, LI Shuqin2
1. Beijing Key Lab. of Internet Culture and Digital Dissemination Research, Beijing Info. Sci. & Technol. Univ., Beijing 100101, China;
2. School of Computer Sci., Beijing Info. Sci. & Technol. Univ., Beijing 100101, China
Abstract: Inter-contact time between different node pairs in opportunistic crowd sensing networks is different, which results in different makespan of tasks when the tasks are taken by different nodes. In order to minimize the average makespan of tasks, an online multi-task assignment algorithm based on prediction (OTAP) was proposed and implemented. Based on the real mobility trace datasets, the distribution of the inter-contact time between nodes was analyzed and a subroutine for discovering the contact law between nodes was developed. Relying on the prediction for inter-contact time between nodes, each time the node responsible for task execution was assigned the most amount of task that could be accomplished before the next contact with the task allocator. Using four different real mobility trace datasets, the performance of OTAP was verified and analyzed by ONE simulator. Experiment results showed that OTAP outperformed the existing algorithm NTA on the average makespan of tasks by 50.49%, 45.34%, 32.71% and 32.23% individually on the four different datasets. Completion ratio of tasks was also improved on two mobility datasets.
Key words: opportunistic crowd sensing    multi-task assignment    online algorithm

1 问题描述 1.1 网络模型

1.2 任务模型

1.3 问题描述

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

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

 图1 cambridge_city数据集中的节点2与其他节点的相遇记录 Fig. 1 Encounter records between node 2 and other nodes in cambridge_city dataset

2.2 节点相遇规律发现算法

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

2）将新生成的记录序列的平均时间间隔记为长相遇间隔 $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）根据相遇历史记录，通过算法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$ 为止。

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 整体任务分配框架

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 算法分析

4 性能评估 4.1 实验环境

4.2 实验结果

 图2 OTAP与NTA、最优解在平均任务完成时间上的性能对比 Fig. 2 Performance comparisons among OTAP, NTA and the Optimal solution on the average makespan

 图3 OTAP与NTA、最优解在最终任务完成数上的性能对比 Fig. 3 Performance comparisons among OTAP, NTA and the Optimal solution on the number of completed tasks

 图4 OTAP与NTA、最优解在时间与任务完成率关系上的对比 Fig. 4 Comparisons among OTAP, NTA and the Optimal solution on the relationship between time and task completion rate

5 结　论