OTAP:基于预测的机会群智感知多任务在线分配算法
OTAP: Online Multi-task Assignment Algorithm with Prediction for Opportunistic Crowd Sensing
作者：李卓(北京信息科技大学 网络文化与数字传播北京市重点实验室, 北京 100101;北京信息科技大学 计算机学院, 北京 100101)；徐哲(北京信息科技大学 计算机学院, 北京 100101)；陈昕(北京信息科技大学 计算机学院, 北京 100101)；李淑琴(北京信息科技大学 计算机学院, 北京 100101)
Author：LI Zhuo(Beijing Key Lab. of Internet Culture and Digital Dissemination Research, Beijing Info. Sci. & Technol. Univ., Beijing 100101, China;School of Computer Sci., Beijing Info. Sci. & Technol. Univ., Beijing 100101, China)；XU Zhe(School of Computer Sci., Beijing Info. Sci. & Technol. Univ., Beijing 100101, China)；CHEN Xin(School of Computer Sci., Beijing Info. Sci. & Technol. Univ., Beijing 100101, China)；LI Shuqin(School of Computer Sci., Beijing Info. Sci. & Technol. Univ., Beijing 100101, China)
收稿日期：2017-09-10 年卷（期）页码：2018,50(5):176-182
期刊名称：工程科学与技术
Journal Name：Advanced Engineering Sciences
关键字：机会群智感知;多任务分配;在线算法
Key words：opportunistic crowd sensing;multi-task assignment;online algorithm
基金项目：国家自然科学基金资助项目（61502040；61370065）；北京市属高校高水平教师队伍建设支持计划青年拔尖人才培育计划资助项目（CIT&TCD201804055）；网络文化与数字传播北京市重点实验室资助项目（ICDDXN001）；北京信息科技大学“勤信英才”培养计划资助项目
中文摘要
机会群智感知网络中，不同节点间的相遇间隔各异，任务由不同节点执行时的时间成本有较大差异性。为最小化任务平均完成时间，设计并实现了一种基于预测的多任务在线分配算法（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.
【关闭】
