空间众包中多类型任务的分配与调度方法

doi:10.11772/j.issn.1001-9081.2017071886

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 6-12.DOI: 10.11772/j.issn.1001-9081.2017071886

• 2017年全国开放式分布与并行计算学术年会(DPCS 2017)论文 • 上一篇下一篇

空间众包中多类型任务的分配与调度方法

毛莺池¹, 穆超¹, 包威¹, 李晓芳²

1. 河海大学计算机与信息学院, 南京 211100;
2. 常州工学院计算机信息工程学院, 江苏常州 213032

收稿日期:2017-08-04 修回日期:2017-08-21 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 穆超
作者简介:毛莺池(1976-),女,上海人,副教授,博士,CCF会员,主要研究方向:分布式计算、并行处理、分布式数据管理;穆超(1993-)男,内蒙古赤峰人,硕士研究生,主要研究方向:分布式计算;包威(1990-),男,江苏淮安人,硕士研究生,主要研究方向:分布式计算;李晓芳(1972-),女,内蒙古赤峰人,副教授,博士,主要研究方向:分布式计算。
基金资助:
国家自然科学基金资助项目（U1301252）；国家科技支撑计划项目（2013BAB06B04）；国家重点研发计划项目（2016YFC0400910）；国家科技重大专项（2017ZX07104-001）；中央高校基本科研业务费专项（2015B22214）。

Multi-type task assignment and scheduling oriented to spatial crowdsourcing

MAO Yingchi¹, MU Chao¹, BAO Wei¹, LI Xiaofang²

1. College of Computer and Information, Hohai University, Nanjing Jiangsu 211100, China;
2. College of Computer and Information Engineering, Changzhou Institute of Technology, Changzhou Jiangsu 213032, China

Received:2017-08-04 Revised:2017-08-21 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (U1301252), the National Key Technology R&D Program (2013BAB06B04), the National Key R&D Program of China (2016YFC0400910), the National Science and Technology Major Project (2017ZX07104-001), the Fundamental Research Funds for the Central Universities (2015B22214).

摘要/Abstract

摘要： 针对空间众包多类型任务完成的质量与数量问题，提出多类型任务的分配与调度方法。首先，在任务分配过程中，结合空间众包中多类型任务和用户的特点，对贪婪分配算法改进，提出基于距离ε值分配（ε-DA）算法；然后，将任务分配给附近的用户，以提高任务完成质量；其次，利用分支定界思想（BBS），根据专业匹配分数的大小，对任务序列进行调度；最后，找到最佳的任务序列。针对分支定界思想的调度算法运行速度较慢的问题，提出最有前途分支启发式（MPBH）算法。通过MPBH算法，使得在每次任务分配过程中实现局部最优化，与分支定界思想的调度算法相比，在运行速度上提高了30%。实验结果表明，所提方法能够提高任务完成的质量以及数量，有效地提高了运行速度与精确性。

关键词: 空间众包, 任务分配, 任务调度, 分支定界, 局部最优

Abstract: Aiming at the quality and quantity problem of multi-type task completion in spatial crowdsourcing, a method of multi-type task assignment and scheduling was proposed. Firstly, in the task assignment process, by combining with the characteristics of multi-type tasks and users in spatial crowdsourcing and improving the greedy allocation algorithm, a Distance ε based Assignment (ε-DA) algorithm was proposed. Then the tasks were assigned to the nearby user, in order to improve the quality of task completion. Secondly, the idea of Branch and Bound Schedule (BBS) was utilized, and the task sequences were scheduled according to the size of the professional matching scores. Finally, the best sequence of tasks was found. Due to the low running speed of the scheduling algorithm of branch and bound idea, the Most Promising Branch Heuristic (MPBH) algorithm was presented. Through the MPBH algorithm, local optimization was achieved in each task allocation process. Compared with the scheduling algorithm of branch and bound idea, the running speed of the proposed algorithm was increased by 30%. The experimental results show that the proposed method can improve the quality and quantity of task completion and raise the running speed and accuracy.

Key words: spatial crowdsourcing, task assignment, task scheduling, branch and bound, local optimization

中图分类号:

TP393.027

毛莺池, 穆超, 包威, 李晓芳. 空间众包中多类型任务的分配与调度方法[J]. 计算机应用, 2018, 38(1): 6-12.

MAO Yingchi, MU Chao, BAO Wei, LI Xiaofang. Multi-type task assignment and scheduling oriented to spatial crowdsourcing[J]. Journal of Computer Applications, 2018, 38(1): 6-12.

参考文献

[1] 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.
[2] MUSTHAG M, GANESAN D. Labor dynamics in a mobile micro-task market[C]//Proceedings of the 2013 SIGCHI Conference on Human Factors in Computing Systems. New York:ACM, 2013:641-650.
[3] DOAN A H, FRANKLIN M J, KOSSMANN D, et al. Crowdsourcing applications and platforms:a data management perspective[J]. Proceedings of the VLDB Endowment, 2011, 4(12):1508-1509.
[4] DEUTCH D, MILO T. Mob data sourcing[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2012:581-584.
[5] KAZAI G, KAMPS J, MILIC-FRAYLING N. Worker types and personality traits in crowdsourcing relevance labels[C]//Proceedings of the 20th ACM Conference on Information and Knowledge Management. New York:ACM, 2011:1941-1944.
[6] CHEN L, LEE D, MILO T. Data-driven crowdsourcing:management, mining, and applications[C]//Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway, NJ:IEEE, 2015:1527-1529.
[7] HOWE J. The rise of crowdsourcing[J]. Wired Magazine, 2006, 14(6):1-5.
[8] 冯剑红,李国良,冯建华.众包技术研究综述[J].计算机学报,2015,38(9):1713-1726.(FENG J H, LI G L, FENG J H. Summary of crowdsourcing technology research[J]. Chinese Journal of Computers, 2015, 38(9):1713-1726.)
[9] WONG C W, TAO Y, FU W C, et al. On efficient spatial matching[C]//Proceedings of the 33rd International Conference on Very Large Data Bases.[S.l.]:VLDB Endowment, 2007:579-590.
[10] LEONG H U, MAN L Y, MOURATIDIS K, et al. Capacity constrained assignment in spatial databases[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2008:15-28.
[11] TONG Y, SHE J, DING B, et al. Online mobile micro-task allocation in spatial crowdsourcing[C]//Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Piscataway, NJ:IEEE, 2016:49-60.
[12] TONG Y, SHE J, DING B, et al. Online minimum matching in real-time spatial data:experiments and analysis[J]. Proceedings of the VLDB Endowment, 2016, 9(12):1053-1064.
[13] HO C J, VAUGHAN J W. Online task assignment in crowdsourcing markets[C]//Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2013:45-51.
[14] HO C J, JABBARI S, VAUGHAN A J W. Adaptive task assignment for crowdsourced classification[C]//Proceedings of the 30th International Conference on Machine Learning. Atlanta:ICML, 2013:534-542.
[15] KARGER D R, OH S, SHAH D. Budget-optimal task allocation for reliable crowdsourcing systems[J]. Operations Research, 2011, 62(1):1-24.
[16] KAZEMI L, SHAHABI C. GeoCrowd:enabling query answering with spatial crowdsourcing[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York:ACM, 2012:189-198.
[17] TO H, FAN L, LUAN T, et al. Real-time task assignment in hyperlocal spatial crowdsourcing under budget constraints[C]//Proceedings of the 2016 IEEE International Conference on Pervasive Computing and Communications. Piscataway, NJ:IEEE, 2016:1-8.
[18] DANG H, NGUYEN T, TO H. Maximum complex task assignment:towards tasks correlation in spatial crowdsourcing[C]//Proceedings of the 2013 International Conference on Information Integration and Web-based Applications & Services. New York:ACM, 2013:77-81.
[19] GAREY M R, JOHNSON D S. Computers and Intractability:A Guide to the Theory of NP-Completeness[M]. New York:W. H. Freeman, 1990:11-13.
[20] VANSTEENWEGENAABA P. The orienteering problem:a survey[J]. European Journal of Operational Research, 2011, 209(1):1-10.
[21] LI Y, YIU M L, XU W. Oriented online route recommendation for spatial crowdsourcing task workers[C]//Proceedings of the 14th International Conference on Advances in Spatial and Temporal Databases. New York:ACM, 2015:137-156.
[22] DENG D, SHAHABI C, DEMIRYUREK U. Maximizing the number of worker's self-selected tasks in spatial crowdsourcing[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2013:324-333.
[23] DENG D, SHAHABI C, ZHU L. Task matching and scheduling for multiple workers in spatial crowdsourcing[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2015:Article No. 21.
[24] IPEIROTIS P G, PROVOST F, WANG J. Quality management on Amazon Mechanical Turk[C]//Proceedings of the 2010 ACM SIGKDD Workshop on Human Computation. New York:ACM, 2010:64-67.
[25] LIU X, LU M, OOI B C, et al. CDAS:a crowdsourcing data analytics system[J]. Proceedings of the VLDB Endowment, 2012, 5(10):1040-1051.
[26] CAO C C, SHE J, TONG Y, et al. Whom to ask?:jury selection for decision making tasks on micro-blog services[J]. Proceedings of the VLDB Endowment, 2012, 5(11):1495-1506.
[27] CAO C C, TONG Y, CHEN L, et al. WiseMarket:a new paradigm for managing wisdom of online social users[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2013:455-463.
[28] GAO J, LIU X, OOI B C, et al. An online cost sensitive decision-making method in crowdsourcing systems[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2013:217-228.
[29] KAZEMI L, SHAHABI C, CHEN L. GeoTruCrowd:trustworthy query answering with spatial crowdsourcing[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2013:314-323.
[30] TO H, SHAHABI C, KAZEMI L. A server-assigned spatial crowdsourcing framework[J]. ACM Transactions on Spatial Algorithms & Systems, 2015, 1(1):Article No. 2.
[31] Yelp Inc. Yelp dataset[EB/OL].[2017-03-20]. http://www.yelp.com/datasetchallenge/.

空间众包中多类型任务的分配与调度方法

Multi-type task assignment and scheduling oriented to spatial crowdsourcing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[2]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[3]	王贵林, 李斌. 受春秋战国史实启发的帝国竞争改进算法[J]. 计算机应用, 2021, 41(2): 470-478.
[4]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[5]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[6]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.
[7]	黄冬艳, 付中卫, 王波. 计算资源受限的移动边缘计算服务器收益优化策略[J]. 计算机应用, 2020, 40(3): 765-769.
[8]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[9]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 计算机应用, 2020, 40(2): 358-362.
[10]	刘智翔, 刘慧超, 黄冬梅, 周丽萍, 苏诚. 多种任务调度混合的IB-LBM并行优化方法[J]. 计算机应用, 2020, 40(2): 386-391.
[11]	秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.
[12]	李孜颖, 石振国. 面向大数据任务的调度方法[J]. 计算机应用, 2020, 40(10): 2923-2928.
[13]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[14]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[15]	张译天, 于炯, 鲁亮, 李梓杨. 大数据流式计算框架Heron环境下的流分类任务调度策略[J]. 计算机应用, 2019, 39(4): 1106-1116.