空间众包中隔离敏感的任务匹配算法

doi:10.3778/j.issn.1002-8331.2309-0118

摘要/Abstract

摘要： 随着移动互联网接入普及和共享经济的增长，空间众包平台得到广泛普及。存在一类众包应用尽量使得众包任务在空间局部范围内完成，即在执行空间任务时减少人员在空间区域间的流动。基于此需求，提出了空间隔离敏感的任务匹配问题，给定具有所属空间区域位置的工人集和任务集，在所有任务均可完成的前提下，使得所有匹配任务的工人移动所产生的跨区域代价之和最小。在线平台中高效的空间隔离敏感的任务匹配算法是研究目标。提出了基于空间层次合并分组的匹配算法，将分布在空间区域中的任务与工人转换到区域邻接图节点，提出了[δ]-clique概念用于将区域节点分组，对分组的节点进行整体匹配，较大程度上提高了匹配算法的效率。在真实数据集上进行充分对比实验，结果表明，与现有的算法相比提出的空间层次合并分组的匹配算法在跨区域代价方面平均减少近16%，在匹配效率方面平均提升近5倍，验证了所提出算法的有效性。

关键词: 空间众包, 区域划分, 跨区域代价, KM算法

Abstract: With the popularity of mobile Internet access and the growth of the sharing economy, space crowdsourcing platforms have gained in widespread popularity. There exists a class of crowdsourcing applications that tries to make the crowdsourcing tasks spatially localized in scope, which is to reduce the movement of people between spatial regions when performing spatial tasks. Based on this requirement, this paper presents the spatially isolation-sensitive task matching problem, which minimizes the sum of the cross-regional costs incurred by the movement of workers for all matched tasks, given the set of workers and the set of tasks with the locations of the spatial regions to which they belong, provided that all tasks can be completed. Efficient spatial isolation-sensitive task assignment algorithms in online platforms are the research objectives. This paper proposes matching algorithm based on spatial hierarchical merging and grouping, which transforms tasks and workers distributed in spatial regions to regional adjacency graph nodes, proposes the concept of [δ]-clique for grouping regional nodes, and then performs overall matching of grouped nodes, which improves the efficiency of the matching algorithm to a greater extent. Finally, the effectiveness of the proposed algorithm is verified by conducting full comparison experiments on real datasets in terms of both cross-region cost and running time, which the proposed algorithms reduce cross regional costs by an average of nearly 16% and improve matching efficiency by an average of nearly 5 times.

Key words: spatial crowdsourcing, regional division, cross region cost, Kuhn-Munkres (KM) algorithm

刘俊岭, 高新宇, 孙焕良, 许景科. 空间众包中隔离敏感的任务匹配算法[J]. 计算机工程与应用, 2024, 60(17): 252-262.

LIU Junling, GAO Xinyu, SUN Huanliang, XU Jingke. Isolation-Sensitive Task Assignment in Spatial Crowdsourcing[J]. Computer Engineering and Applications, 2024, 60(17): 252-262.

参考文献

[1] TONG Y, ZHOU Z, ZENG Y, et al. Spatial crowdsourcing: a survey[J]. The VLDB Journal, 2020, 29(1): 217-250.
[2] GUMMIDI S R B, XIE X, PEDERSEN T B. A survey of spatial crowdsourcing[J]. ACM Transactions on Database Systems, 2019, 44(2): 1-46.
[3] GUO B, LIU Y, WANG L, et al. Task allocation in spatial crowdsourcing: current state and future directions[J]. IEEE Internet of Things Journal, 2018, 5(3): 1749-1764.
[4] ZHAO Y, CHEN X, DENG L, et al. Outlier detection for streaming task assignment in crowdsourcing[C]//Proceedings of the ACM Web Conference 2022, 2022: 1933-1943.
[5] LI X, ZHAO Y, ZHOU X, et al. Consensus-based group task assignment with social impact in spatial crowdsourcing[J]. Data Science and Engineering, 2020, 5(4): 375-390.
[6] ZHU H B. Group role assignment via a Kuhn-Munkres algorithm-based solution[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2012, 42(3): 739-750.
[7] YUAN Z W, ZHANG H. Research on application of Kuhn-Munkres algorithm in emergency resources dispatch problem[C]//Proceedings of the 2012 9th International Conference on Fuzzy Systems and Knowledge Discovery, 2012: 2774-2777.
[8] ZHENG X, MA C. An intelligent target detection method of UAV swarms based on improved KM algorithm[J]. Chinese Journal of Aeronautics, 2021, 34(2): 539-553.
[9] YAO Y, QIN Y, FENG W , et al. KFTO: Kuhn-Munkres based fair task offloading in fog networks[J]. Computer Networks, 2021, 195(12): 108131.
[10] XU Z, YUAN G Z, WANG X D, et al. Kuhn-Munkres algorithm-based matching method and automatic device for tiny magnetic steel pair[J]. Micromachines, 2021, 12(3): 316.
[11] CHEN X, ZHAO Y, ZHENG K, et al. Influence-aware task assignment in spatial crowdsourcing[C]//Proceedings of the 2022 IEEE 38th International Conference on Data Engineering, 2022: 2141-2153.
[12] ZHAO Y, ZHENG K, LI Y, et al. Destination-aware task assignment in spatial crowdsourcing: a worker decomposition approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2019: 2336-2350.
[13] ZHAO Y, ZHENG K, GUO J, et al. Fairness-aware task assignment in spatial crowdsourcing: game-theoretic approaches[C]//Proceedings of the International Conference on Data Engineering, 2021: 265-276.
[14] ZHAO Y, XIA J, LIU G, et al. Preference-aware task assignment in spatial crowdsourcing[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 2629-2636.
[15] ZHAO Y, ZHENG K, CUI Y, et al. Predictive task assignment in spatial crowdsourcing: a data-driven approach[C]//Proceedings of the 2020 IEEE 36th International Conference on Data Engineering, 2020: 13-24.
[16] TAO Q, ZENG Y, ZHOU Z, et al. Multi-worker-aware task planning in real-time spatial crowdsourcing[C]//Proceedings of the Database Systems for Advanced Applications: 23rd International Conference, 2018: 301-317.
[17] 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, 2016: 49-60.
[18] ZENG Y, TONG Y, CHEN L, et al. Latency-oriented task completion via spatial crowdsourcing[C]//Proceedings of the 2018 IEEE 34th International Conference on Data Engineering, 2018: 317-328.
[19] 徐天承, 乔少杰, 武俊, 等. 一种基于时空位置预测的空间众包任务分配方法[J]. 计算机研究与发展, 2022, 59(2): 310-328.
XU T C, QIAO S J, WU J, et al. A spatial crowdsourcing task assignment approach based on spatio-temporal location prediction[J]. Journal of Computer Research and Development, 2022, 59(2): 310-328.
[20] 陈宝童, 王丽清, 蒋晓敏, 等. 群智协同任务分配研究综述[J]. 计算机工程与应用, 2021, 57(20): 1-12.
CHEN B T, WANG L Q, JIANG X M, et al. Survey of task assignment for crowd-based cooperative computing[J]. Computer Engineering and Applications, 2021, 57(20): 1-12.
[21] 范泽军, 沈立炜, 彭鑫, 等. 基于约束的空间众包多阶段任务分配[J]. 计算机学报, 2019, 42(12): 2722-2741.
FAN Z J, SHEN L W, PENG X, et al. Multi stage task allocation on constrained spatial crowdsourcing[J]. Chinese Journal of Computers, 2019, 42 (12): 2722-2741.
[22] WANG Z, ZHAO Y, CHEN X, et al. Task assignment with worker churn prediction in spatial crowdsourcing[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021: 2070-2079.
[23] JOSHI M, SINGH A, RANU S, et al. FoodMatch: batching and matching for food delivery in dynamic road networks[J]. ACM Transactions on Spatial Algorithms and Systems, 2022, 8(1): 1-25.
[24] ZHAO Y, GUO J, CHEN X, et al. Coalition-based task assignment in spatial crowdsourcing[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering, 2021: 241-252.
[25] BOUTSIS I, KALOGERAKI V. On task assignment for real-time reliable crowdsourcing[C]//Proceedings of the IEEE 34th International Conference on Distributed Computing Systems, 2014: 1-10.
[26] ABOUOUF M, MIZOUNI R, SINGH S, et al. Multi-worker multi-task selection framework in mobile crowd sourcing[J]. Journal of Network and Computer Applications, 2019, 130(1): 52-62.
[27] XIAO M, MA K, LIU A, et al. SRA: secure reverse auction for task assignment in spatial crowdsourcing[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(4): 782-796.
[28] ISLAM F T, HASHEM T, SHAHRIYAR R. A privacy-enhanced and personalized safe route planner with crowdsourced data and computation[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering, 2021: 229-240.
[29] WEN H, LIN Y, WU F, et al. Package pick-up route prediction via modeling couriers' spatial-temporal behaviors[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering, 2021: 2141-2146.
[30] ZHENG B, HUANG C, JENSEN C S, et al. Online trichromatic pickup and delivery scheduling in spatial crowdsourcing[C]//Proceedings of the 2020 IEEE 36th International Conference on Data Engineering, 2020: 973-984.
[31] WANG T, XIE X, CAO X, et al. On efficient and scalable time-continuous spatial crowdsourcing[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering, 2021: 19-22.
[32] LI Y, ZHAO Y, ZHENG K. Preference-aware group task assignment in spatial crowdsourcing: a mutual information-based approach[C]//Proceedings of the 2021 IEEE International Conference on Data Mining, 2021: 350-359.
[33] ZHAO Y, ZHENG K, YIN H, et al. Preference-aware task assignment in spatial crowdsourcing: from individuals to groups[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(7): 3461-3477.
[34] 刘润涛, 董庆宇, 吴昊天. 基于Voronoi图的方向区域查询方法[J]. 计算机工程与应用, 2022, 58(8): 83-89.
LIU R T, DONG Q Y, WU H T. Direction region query method based on Voronoi diagram[J]. Computer Engineering and Applications, 2022, 58(8): 83-89.