作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2019, Vol. 45 ›› Issue (6): 67-74. doi: 10.19678/j.issn.1000-3428.0053522

• 先进计算与数据处理 • 上一篇    下一篇

基于预测分析的时空众包在线任务分配

张兴盛1,余敦辉1,2,聂茜婵1,袁旭1   

  1. 1.湖北大学 计算机与信息工程学院,武汉 430062; 2.湖北省教育信息化工程技术研究中心,武汉 430062
  • 收稿日期:2018-12-28 出版日期:2019-06-15 发布日期:2019-06-15
  • 作者简介:张兴盛(1998—),男,本科生,主研方向为时空众包技术;余敦辉,副教授、博士;聂茜婵,本科生;袁旭,硕士研究生。
  • 基金资助:

    国家重点研发计划(2017YFB1400602);国家自然科学基金(61572371,61832014);湖北省技术创新重大专项(2018ACA13)。

Spatiotemporal crowdsourcing online task allocation based on predictive analysis

ZHANG Xingsheng 1,YU Dunhui1,2,NIE Xichan1,YUAN Xu1   

  1. 1.School of Computer Science and Information Engineering,Hubei University,Wuhan 430062,China;2.Hubei Provincial Engineering Technology Research Center for Education Informatization,Wuhan 430062,China
  • Received:2018-12-28 Online:2019-06-15 Published:2019-06-15

摘要:

针对时空众包在线任务分配问题,提出任务范围调节算法DMRA与基于预测分析的在线任务分配算法PAMA。DMRA算法以任务位置为中心,根据工人密度动态调整任务的范围。PAMA算法基于历史统计概率,采用贝叶斯分类器预测下一时间戳的对象分布情况,在此基础上,执行带权二分图最优匹配算法以完成任务分配。实验结果表明,将DMRA算法与PAMA算法相结合,能够提升任务分配的总效用,降低工人的差旅成本,任务分配性能优于贪心算法与随机阈值算法。

关键词: 时空众包, 在线任务分配, 分配总效用, 工人差旅成本, 贝叶斯分类预测, 统计预测

Abstract:

Aiming at online task allocation problem of spatiotemporal crowdsourcing,a task range adjustment algorithm DMRA and an online task allocation algorithm PAMA based on predictive analysis are proposed.The DMRA algorithm takes task location as the center and dynamically adjusts the range of tasks according to worker density.The PAMA algorithm uses Bayesian classifier to predict the distribution of the next timestamp object based on historical statistical probability.On this basis,the weighted bipartite graph optimal matching algorithm is executed to complete the task allocation.Experimental results show that the combination of DMRA algorithm and PAMA algorithm can improve the total utility of task allocation and reduce the travel cost of workers,and the performance of task allocation is better than that of greedy algorithm and random threshold algorithm.

Key words: spatiotemporal crowdsourcing;online task allocation, total utility of allocation, travel cost of workers, Bayesian classification prediction, statistical prediction

中图分类号: