基于预测分析的时空众包在线任务分配
|
摘要
针对时空众包在线任务分配问题,提出任务范围调节算法DMRA与基于预测分析的在线任务分配算法PAMA。DMRA算法以任务位置为中心,根据工人密度动态调整任务的范围。PAMA算法基于历史统计概率,采用贝叶斯分类器预测下一时间戳的对象分布情况,在此基础上,执行带权二分图最优匹配算法以完成任务分配。实验结果表明,将DMRA算法与PAMA算法相结合,能够提升任务分配的总效用,降低工人的差旅成本,任务分配性能优于贪心算法与随机阈值算法。
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.
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.
引文
[1] HOWE J.The rise of crowdsourcing[J].Wired Magazine,2016,14(6):1-4.
[2] 芮兰兰,张攀,黄豪球,等.一种面向众包的基于信誉值的激励机制[J].电子与信息学报,2016,38(7):1808-1815.
[3] 施战,辛煜,孙玉娥,等.基于用户可靠性的众包系统任务分配机制[J].计算机应用,2017,37(9):2449-2453.
[4] SCHEE B A V.Crowdsourcing:why the power of the crowd is driving the future of business[J].American Journal of Health-System Pharmacy,2010,67(4):1565-1566.
[5] LI Yu,YIU M L,XU Wenjian.Oriented online route recommendation for spatial crowdsourcing task workers[C]//Proceedings of the 14th International Conference on Advances in Spatial and Temporal Database.New York,USA:ACM Press,2015:137-156.
[6] ALT F,SHIRAZI A S,SCHMIDT A,et al.Location-based crowdsourcing:extending crowdsourcing to the real world[C]//Proceedings of Nordic Conference on Human-computer Interaction.New York,USA:ACM Press,2010:13-22.
[7] MUSTHAG M,GANESAN D.Labor dynamics in a mobile microtask market[C]//Proceedings of 2013 SIGCHI Conference on Human Factors in Computing Systems.New York,USA:ACM Press,2013:641-650.
[8] TO H,GHINITA G,SHAHABI C.A framework for protecting worker location privacy in spatial crowd-sourcing[J].Proceedings of the VLDB Endowment,2014,7(10):919-930.
[9] CHENG Peng,LIAN Xiang,CHEN Zhao,et al.Reliable diversity-based spatial crowdsourcing by moving workers[J].Proceedings of the VLDB Endowment,2015,8(10):1022-1033.
[10] DENG Dingxiong,SHAHABI C,DEMIRYUREK U.Maximizing the number of worker’s self-selected tasks in spatial crowdsourcing[C]//Proceedings of ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2013:324-333.
[11] 童咏听,袁野,成雨蓉,等.时空众包数据管理技术研究综述[J].软件学报,2017,28(1):35-58.
[12] HASSAN U U,CURRY E.Efficient task assignment for spatial crowdsourcing:a combinatorial fractional optimi-zation approach with semi-bandit learning[J].Expert Systems with Applications,2016,58(C):36-56.
[13] DENG Dingxiong,SHAHABI C,ZHU L.Task matching and scheduling for multiple workers in spatial crowdsourcing[C]//Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2015:165-175.
[14] 刘辉,李盛恩.时空众包环境下基于统计预测的自适应阈值算法[J].计算机应用,2018,38(2):415-420.
[15] 张晨,郭玉超,林培光,等.空间众包中基于位置预测的任务分配算法[J].南京大学学报(自然科学版),2018,54(2):471-480.
[16] CHENG Peng,SHAHABI C,CHEN Lei,et al.Prediction-based task assignment in spatial crowdsourcing[C]//Proceedings of IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2017:152-160.
[17] 李志聪,钟绍春.自适应学习系统中朴素贝叶斯分类的应用研究[J].计算机工程与科学,2009,31(9):102-104.
[18] 张亚萍,陈得宝,侯俊钦,等.朴素贝叶斯分类算法的改进及应用[J].计算机工程与应用,2011,47(15):134-137.
[19] 张登兵.统计预测效果的评价方法[J].统计与决策,2012(21):99-101.
[20] MEHTA A.Online matching and ad allocation[M].[S.l.]:Now Publishers Inc.,2013.
[21] TONG Yongxin,SHE Jieying,DING Bolin,et al.Online mobile micro-task allocation in spatial crowdsourcing[C]//Proceedings of 2016 IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2016:49-60.
[22] CHEN Zhao,FU Rui,ZHAO Ziyuan,et al.gMission:a general spatial crowdsourcing platform[EB/OL].[2018-12-05].http://www.vldb.org/pvldb/vol7/p1629-chen.pdf.
[2] 芮兰兰,张攀,黄豪球,等.一种面向众包的基于信誉值的激励机制[J].电子与信息学报,2016,38(7):1808-1815.
[3] 施战,辛煜,孙玉娥,等.基于用户可靠性的众包系统任务分配机制[J].计算机应用,2017,37(9):2449-2453.
[4] SCHEE B A V.Crowdsourcing:why the power of the crowd is driving the future of business[J].American Journal of Health-System Pharmacy,2010,67(4):1565-1566.
[5] LI Yu,YIU M L,XU Wenjian.Oriented online route recommendation for spatial crowdsourcing task workers[C]//Proceedings of the 14th International Conference on Advances in Spatial and Temporal Database.New York,USA:ACM Press,2015:137-156.
[6] ALT F,SHIRAZI A S,SCHMIDT A,et al.Location-based crowdsourcing:extending crowdsourcing to the real world[C]//Proceedings of Nordic Conference on Human-computer Interaction.New York,USA:ACM Press,2010:13-22.
[7] MUSTHAG M,GANESAN D.Labor dynamics in a mobile microtask market[C]//Proceedings of 2013 SIGCHI Conference on Human Factors in Computing Systems.New York,USA:ACM Press,2013:641-650.
[8] TO H,GHINITA G,SHAHABI C.A framework for protecting worker location privacy in spatial crowd-sourcing[J].Proceedings of the VLDB Endowment,2014,7(10):919-930.
[9] CHENG Peng,LIAN Xiang,CHEN Zhao,et al.Reliable diversity-based spatial crowdsourcing by moving workers[J].Proceedings of the VLDB Endowment,2015,8(10):1022-1033.
[10] DENG Dingxiong,SHAHABI C,DEMIRYUREK U.Maximizing the number of worker’s self-selected tasks in spatial crowdsourcing[C]//Proceedings of ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2013:324-333.
[11] 童咏听,袁野,成雨蓉,等.时空众包数据管理技术研究综述[J].软件学报,2017,28(1):35-58.
[12] HASSAN U U,CURRY E.Efficient task assignment for spatial crowdsourcing:a combinatorial fractional optimi-zation approach with semi-bandit learning[J].Expert Systems with Applications,2016,58(C):36-56.
[13] DENG Dingxiong,SHAHABI C,ZHU L.Task matching and scheduling for multiple workers in spatial crowdsourcing[C]//Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2015:165-175.
[14] 刘辉,李盛恩.时空众包环境下基于统计预测的自适应阈值算法[J].计算机应用,2018,38(2):415-420.
[15] 张晨,郭玉超,林培光,等.空间众包中基于位置预测的任务分配算法[J].南京大学学报(自然科学版),2018,54(2):471-480.
[16] CHENG Peng,SHAHABI C,CHEN Lei,et al.Prediction-based task assignment in spatial crowdsourcing[C]//Proceedings of IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2017:152-160.
[17] 李志聪,钟绍春.自适应学习系统中朴素贝叶斯分类的应用研究[J].计算机工程与科学,2009,31(9):102-104.
[18] 张亚萍,陈得宝,侯俊钦,等.朴素贝叶斯分类算法的改进及应用[J].计算机工程与应用,2011,47(15):134-137.
[19] 张登兵.统计预测效果的评价方法[J].统计与决策,2012(21):99-101.
[20] MEHTA A.Online matching and ad allocation[M].[S.l.]:Now Publishers Inc.,2013.
[21] TONG Yongxin,SHE Jieying,DING Bolin,et al.Online mobile micro-task allocation in spatial crowdsourcing[C]//Proceedings of 2016 IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2016:49-60.
[22] CHEN Zhao,FU Rui,ZHAO Ziyuan,et al.gMission:a general spatial crowdsourcing platform[EB/OL].[2018-12-05].http://www.vldb.org/pvldb/vol7/p1629-chen.pdf.