OTAP:基于预测的机会群智感知多任务在线分配算法

OTAP: Online Multi-task Assignment Algorithm with Prediction for Opportunistic Crowd Sensing

机会群智感知网络中,不同节点间的相遇间隔各异,任务由不同节点执行时的时间成本有较大差异性。为最小化任务平均完成时间,设计并实现了一种基于预测的多任务在线分配算法(online multi-task assignment based on prediction,OTAP)。基于真实移动轨迹数据集,分析了节点间相遇间隔分布,设计了节点相遇规律发现子算法;利用对节点间的相遇间隔的预测,每次给执行节点分配在与任务分发者下次相遇间隔内能完成的最大任务量。针对4个不同的真实移动轨迹数据集,利用ONE模拟器,对OTAP算法性能进行了验证与分析。结果显示,相比于已有的NTA算法,OTAP在4个不同数据集中平均任务完成时间分别缩短了50.49%、45.34%、32.71%、32.23%,任务完成率在其中两个移动轨迹数据集中也有所提高。

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.