A Preference-aware Many-to-Many TAsk Allocation Algorithm Under Geo-Indistinguishability

ZHANG Peng-fei; ZHAI Rui-chen; CHENG Xiang; ZHANG Zhi-kun; LIU Xi-meng; WANG Jie

doi:10.12263/DZXB.20240938

您当前的位置：

首页 >

文章列表页 >

A Preference-aware Many-to-Many TAsk Allocation Algorithm Under Geo-Indistinguishability

PAPERS | 更新时间：2025-12-08

- A Preference-aware Many-to-Many TAsk Allocation Algorithm Under Geo-Indistinguishability
- ACTA ELECTRONICA SINICA Vol. 53, Issue 3, Pages: 878-894(2025)
- 作者机构：
  
  1.安徽理工大学计算机科学与工程学院，安徽淮南 232001
  2.北京邮电大学计算机学院（国家示范性软件学院），北京 100876
  3.网络与交换技术国家重点实验室（北京邮电大学），北京 100876
  4.浙江大学计算机科学与技术学院，浙江杭州 310058
  5.福州大学计算机与大数据学院，福建福州 350108
  6.安徽理工大学安全科学与工程学院，安徽淮南 232001
- 作者简介：
- 基金信息：
  
  Natural Science Research Project of Anhui Educational Committee(2024AH050364)
- DOI：10.12263/DZXB.20240938
  CLC： TP309;
- Received：17 October 2024，
  
  Revised：2025-01-13，
  
  Published：25 March 2025
- 稿件说明：
移动端阅览
张朋飞, 翟睿辰, 程祥, 等. 满足地理不可区分性的偏好感知多对多任务分配算法[J]. 电子学报, 2025, 53(03): 878-894.

ZHANG Peng-fei, ZHAI Rui-chen, CHENG Xiang, et al. A Preference-aware Many-to-Many TAsk Allocation Algorithm Under Geo-Indistinguishability[J]. Acta Electronica Sinica, 2025, 53(03): 878-894.
张朋飞, 翟睿辰, 程祥, 等. 满足地理不可区分性的偏好感知多对多任务分配算法[J]. 电子学报, 2025, 53(03): 878-894. DOI：10.12263/DZXB.20240938

ZHANG Peng-fei, ZHAI Rui-chen, CHENG Xiang, et al. A Preference-aware Many-to-Many TAsk Allocation Algorithm Under Geo-Indistinguishability[J]. Acta Electronica Sinica, 2025, 53(03): 878-894. DOI：10.12263/DZXB.20240938

摘要

为空间众包中的工人分配任务是后续收集位置相关数据的重要前提.为了应对可能的位置隐私泄露问题，研究者往往结合地理不可区分性进行保护.现有满足地理不可区分性的任务分配方法通常针对一对一场景，其研究目标一般集中在最小化平均旅行距离，而不是最大化任务分配数量；同时，它们假设工人能分配去执行任意的任务.此外，这些研究往往结合平面拉普拉斯机制实现地理不可区分性.上述机制的随机性和无界性会导致工人上传的位置数据包含过量噪音，进而降低任务分配的效用，导致工人平均旅行距离较大或者任务无法完全分配.为解决以上问题，本文提出满足地理不可区分性的偏好感知多对多任务分配算法MONITOR（Many-to-many task allOcation under geo-iNdIsTinguishability for spatial crOwdsouRcing）.该算法主要思想是对工人的偏好任务进行分组加噪并上传工人真实位置到模糊偏好任务位置之间的距离以代替直接上传工人的模糊位置.在MONITOR中，为了收集任务分配必需的工人到任务的距离信息，设计了基于分组的模糊距离收集方法GroCol（Group-based obfuscated distance Collection）；同时为了提高任务分配的效用，设计了参数无关的模糊距离比较方法ParCom（Parameter-free obfuscated distance Comparison）.此外，本文进一步从理论上分析了MONITOR的隐私、效用和复杂度.在2个真实数据集和1个模拟数据集上的实验结果表明MONITOR取得与非隐私任务分配类似的任务分配数量，且较基准方法的旅行距离降低了20%以上.

Abstract

In spatial crowdsourcing

task allocation is a crucial prerequisite for subsequent location-aware data collection. To tackle potential location privacy breaches

researchers often adopt geo-indistinguishability. Existing approaches that satisfy Geo-I are often designed for one-to-one scenarios

while implicitly assume that workers can perform any task

and they often focus on minimizing the average travel distance

rather than maximizing the number of task allocation. Furthermore

these studies often incorporate the planar laplacian mechanism to achieve Geo-I. However

due to the randomness and unbounded nature of PL

it can result in excessive noise in the location data uploaded by workers

significantly deteriorating the utility of task allocation. This can lead to either long distances or unassigned tasks. To address these problems

we propose MONITOR (Many-to-many task allOcation under geo-iNdIsTinguishability for spatial crOwdsouRcing)

a new privacy-preserving task allocation approach for many-to-many scenario. The general idea of MONITOR is to upload the distances from each worker’s true location to the obfuscated preferred tasks’ locations instead of uploading each obfuscated worker’s location. In MONITOR

to collect the distances for subsequent task allocation

we design an obfuscated distance collection method

called GroCol (Group-based obfuscated distance Collection). To improve the utility for task allocation

we develop a parameter independent obfuscated distance comparison method called ParCom (Parameter-free obfuscated distance Comparison). To illustrate the effectiveness of MONITOR

we first theoretically analyze its privacy guarantee

task utility

and computational complexity. We then empirically show on two real-world datasets and one synthetic dataset that MONITOR share similar results to that of non-private task allocation about the number of assigned tasks

and reduce the average travel distance by more than 20% compared to the baseline approaches.

关键词

Keywords

references

王健 , 刘嘉欣 , 赵国生 , 等 . 移动群智感知中基于协同排序的任务推荐方法 [J ] . 电子学报 , 2021 , 49 ( 10 ): 2012 - 2019 .

WANG J , LIU J X , ZHAO G S , et al . Task recommendation method based on collaborative ranking in mobile crowd sensing [J ] . Acta Electronica Sinica , 2021 , 49 ( 10 ): 2012 - 2019 . (in Chinese)

蒋伟进 , 张婉清 , 陈萍萍 , 等 . 基于IWOA群智感知中数量敏感的任务分配方法 [J ] . 电子学报 , 2022 , 50 ( 10 ): 2489 - 2502 .

JIANG W J , ZHANG W Q , CHEN P P , et al . Quantity sensitive task allocation method based on IWOA in group intelligence perception [J ] . Acta Electronica Sinica , 2022 , 50 ( 10 ): 2489 - 2502 . (in Chinese)

宋天舒 , 童咏昕 , 王立斌 , 等 . 空间众包环境下的3类对象在线任务分配 [J ] . 软件学报 , 2017 , 28 ( 3 ): 611 - 630 .

SONG T S , TONG Y X , WANG L B , et al . Online task assignment for three types of objects under spatial crowdsourcing environment [J ] . Journal of Software , 2017 , 28 ( 3 ): 611 - 630 . (in Chinese)

范泽军 , 沈立炜 , 彭鑫 , 等 . 基于约束的空间众包多阶段任务分配 [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 . (in Chinese)

LI Y C , ZHAO Y , ZHENG K . Preference-aware group task assignment in spatial crowdsourcing: A mutual information-based approach [C ] // 2021 IEEE International Conference on Data Mining (ICDM) . Piscataway : IEEE , 2021 : 350 - 359 .

LIU Y , GUO B , WANG Y , et al . TaskMe: Multi-task allocation in mobile crowd sensing [C ] // Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing . New York : ACM , 2016 : 403 - 414 .

YU Y T , XUE X P , MA J X , et al . Efficient privacy-preserving task allocation with secret sharing for vehicular crowdsensing [J ] . IEEE Internet of Things Journal , 2024 , 11 ( 6 ): 9473 - 9486 .

FAN Y , LIU L , ZHANG X X , et al . MAPP: An efficient multi-location task allocation framework with personalized location privacy-protecting in spatial crowdsourcing [J ] . Information Sciences , 2023 , 619 : 654 - 678 .

WANG X D , PENG M Y , LIN H , et al . A privacy-enhanced multiarea task allocation strategy for healthcare 4.0 [J ] . IEEE Transactions on Industrial Informatics , 2023 , 19 ( 3 ): 2740 - 2748 .

DUGUÉPÉROUX J , ALLARD T . From task tuning to task assignment in privacy-preserving crowdsourcing platforms [M ] // Transactions on Large-Scale Data- and Knowledge-Centered Systems: XLIV . Berlin : Springer ,　 2020 : 67 - 107 .

ANDRÉS M E , BORDENABE N E , CHATZIKOKOLAKIS K , et al . Geo-indistinguishability: Differential privacy for location-based systems [C ] // Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security - CCS 2013 . New York : ACM , 2013 : 901 - 914 .

WANG Z H , GUO C Q , LIU J H , et al . Accurate and privacy-preserving task allocation for edge computing assisted mobile crowdsensing [J ] . IEEE Transactions on Computational Social Systems , 2022 , 9 ( 1 ): 120 - 133 .

WANG S P , LI J , WU G J , et al . Joint optimization of task offloading and resource allocation based on differential privacy in vehicular edge computing [J ] . IEEE Transactions on Computational Social Systems , 2022 , 9 ( 1 ): 109 - 119 .

YANG M C , ZHU J H , XI H R , et al . Privacy-aware task allocation based on deep reinforcement learning for mobile crowdsensing [M ] // Wireless Algorithms, Systems, and Applications . Cham : Springer Nature Switzerland , 2022 : 191 - 201 .

JIANG Y L , ZHANG K , QIAN Y , et al . Preserving location privacy and accurate task allocation in edge-assisted mobile crowdsensing [C ] // 2022 IEEE Wireless Communications and Networking Conference (WCNC) . Piscataway : IEEE , 2022 : 704 - 709 .

CHEN Z P , XU M M , SU C X . Online quality-based privacy-preserving task allocation in mobile crowdsensing [J ] . Computer Networks , 2024 , 251 : 110613 .

ZHANG Q , WANG T C , TAO Y , et al . Location privacy protection method based on differential privacy in crowdsensing task allocation [J ] . Ad Hoc Networks , 2024 , 158 : 103464 .

GUO B , LIU Y , WANG L Y , et al . Task allocation in spatial crowdsourcing: Current state and future directions [J ] . IEEE Internet of Things Journal , 2018 , 5 ( 3 ): 1749 - 1764 .

HIEN T , GHINITA G , FAN L Y , et al . Differentially private location protection for worker datasets in spatial crowdsourcing [J ] . IEEE Transactions on Mobile Computing , 2017 , 16 ( 4 ): 934 - 949 .

WANG L Y , YANG D Q , HAN X , et al . Location privacy-preserving task allocation for mobile crowdsensing with differential geo-obfuscation [C ] // Proceedings of the 26th International Conference on World Wide Web . Geneva : International World Wide Web Conferences Steering Committee , 2017 : 627 - 636 .

WANG Z B , HU J H , LV R Z , et al . Personalized privacy-preserving task allocation for mobile crowdsensing [J ] . IEEE Transactions on Mobile Computing , 2019 , 18 ( 6 ): 1330 - 1341 .

WANG L Y , QIN G H , YANG D Q , et al . Geographic differential privacy for mobile crowd coverage maximization [C ] // Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence . New York : ACM , 2018 : 200 - 207 .

HIEN T , SHAHABI C , XIONG L . Privacy-preserving online task assignment in spatial crowdsourcing with untrusted server [C ] // 2018 IEEE 34th International Conference on Data Engineering (ICDE) . Piscataway : IEEE , 2018 : 833 - 844 .

LI M C , WANG J C , ZHENG L B , et al . Privacy-preserving batch-based task assignment in spatial crowdsourcing with untrusted server [C ] // Proceedings of the 30th ACM International Conference on Information & Knowledge Management . New York : ACM , 2021 : 947 - 956 .

TAO Q , TONG Y X , ZHOU Z M , et al . Differentially private online task assignment in spatial crowdsourcing: A tree-based approach [C ] // 2020 IEEE 36th International Conference on Data Engineering (ICDE) . Piscataway : IEEE , 2020 : 517 - 528 .

ZHANG P F , CHENG X , SU S , et al . Task allocation under geo-indistinguishability via group-based noise addition [J ] . IEEE Transactions on Big Data , 2023 , 9 ( 3 ): 860 - 877 .

QIU C X , SQUICCIARINI A , PANG C , et al . Location privacy protection in vehicle-based spatial crowdsourcing via geo-indistinguishability [J ] . IEEE Transactions on Mobile Computing , 2022 , 21 ( 7 ): 2436 - 2450 .

TAO Q , TONG Y X , LI S Y , et al . A differentially private task planning framework for spatial crowdsourcing [C ] // 2021 22nd IEEE International Conference on Mobile Data Management (MDM) . Piscataway : IEEE , 2021 : 9 - 18 .

LIN X C , WEI K M , LI Z T , et al . Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing [J ] . Frontiers of Computer Science , 2023 , 18 ( 6 ): 186605 .

FENG Z H , XIAO R B . Three-dimensional task allocation for smart transportation in spatial crowdsourcing: An intelligent role division approach [J ] . Advanced Engineering Informatics , 2024 , 62 : 102736 .

GONG Z M , LI J Y , LIN Y P , et al . A novel dual cloud server privacy-preserving scheme in spatial crowdsourcing [J ] . Computers & Security , 2024 , 138 : 103659 .

MIAO H , ZHONG X L , LIU J X , et al . Task assignment with efficient federated preference learning in spatial crowdsourcing [J ] . IEEE Transactions on Knowledge and Data Engineering , 2023 , 36 ( 4 ): 1800 - 1814 .

LIN Y M , JIANG Y J , LI Y , et al . Privacy-preserving batch-based task assignment over spatial crowdsourcing platforms [J ] . Computer Networks , 2024 , 241 : 110196 .

RASOOLABADI M N , ZHU H B , WANG C . Solving the many to many grouped task allocation problem via E-CARGO [C ] // 2023 International Conference on Networking, Sensing and Control (ICNSC) . Piscataway : IEEE , 2023 : 1 - 6 .

HUI H W , LIN F H , MENG L , et al . Many-to-many matching based task allocation for dispersed computing [J ] . Computing , 2023 , 105 ( 7 ): 1497 - 1522 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Differentially Private with Sparse and Smooth Self-Distillation

Blockchain-Based Hierarchical Federated Learning System

Hybrid Task Assignment for Crowd Sensing Based on Mobility Prediction

A Study of Truth Discovery Algorithms for Forward Outliers Under Local Differential Privacy

Related Author

ZHAO Deng-feng

XUE Da-xuan

ZHAO Su-yun

CHEN Hong

HU Rong-lei

LIU Si-hui

DUAN Xiao-yi

ZUO Pei-liang

Related Institution

School of Information, Renmin University of China

Department of Electronics and Information Engineering, Beijing Electronic Science and Technology Institute

School of Computer Science, Hunan University of Technology and Business

Xiangjiang Laboratory

Hunan University of Information Technology

⁰