满足地理不可区分性的偏好感知多对多任务分配算法

张朋飞; 翟睿辰; 程祥; 张治坤; 刘西蒙; 王杰

doi:10.12263/DZXB.20240938

您当前的位置：

首页 >

文章列表页 >

满足地理不可区分性的偏好感知多对多任务分配算法

学术论文 | 更新时间：2025-12-08

- 满足地理不可区分性的偏好感知多对多任务分配算法
- A Preference-aware Many-to-Many TAsk Allocation Algorithm Under Geo-Indistinguishability
- 电子学报 2025年53卷第3期页码：878-894
- 作者机构：
  
  1.安徽理工大学计算机科学与工程学院，安徽淮南 232001
  2.北京邮电大学计算机学院（国家示范性软件学院），北京 100876
  3.网络与交换技术国家重点实验室（北京邮电大学），北京 100876
  4.浙江大学计算机科学与技术学院，浙江杭州 310058
  5.福州大学计算机与大数据学院，福建福州 350108
  6.安徽理工大学安全科学与工程学院，安徽淮南 232001
- 作者简介：
  
  [ "张朋飞男，1992年1月出生于河南省鄢陵县.现为安徽理工大学计算机科学与工程学院讲师、研究生导师.主要研究方向为数据隐私保护与可信人工智能.E-mail: zpf.bupt@bupt.cn" ]
  [ "翟睿辰男，2001年3月出生于安徽省马鞍山市.现为安徽理工大学计算机科学与工程学院硕士研究生.主要研究方向为数据隐私保护.E-mail: ruichenzhai@aust.edu.cn" ]
  [ "程祥男，1984年10月出生于北京市.现为北京邮电大学计算机学院教授、博士生导师.主要研究方向为数据隐私保护与可信人工智能.E-mail: chengxiang@bupt.edu.cn" ]
  [ "张治坤男，1993年8月出生于浙江省杭州市.现为浙江大学计算机科学与技术学院副教授、博士生导师.主要研究方向为隐私计算、数据隐私保护、机器学习隐私与安全.E-mail: zhikun@zju.edu.cn" ]
  [ "刘西蒙男，1988年10月出生于福建省福州市.现为福州大学计算机与大数据学院教授、博士生导师.主要研究方向为数据隐私保护与数据安全.E-mail: nbnix@qq.com" ]
  [ "王杰男，1964年1月出生于重庆市.现为安徽理工大学安全科学与工程学院教授、博士生导师.主要研究方向为数据隐私保护、智能检测与智能仪表、粉尘防治技术.中国电子学会会员编号：E190103366M.E-mail: 2024095@aust.edu.cn" ]
- 基金信息：
  
  安徽高校自然科学研究项目(2024AH050364)
- DOI：10.12263/DZXB.20240938
  中图分类号： TP309;
- 收稿：2024-10-17，
  
  修回：2025-01-13，
  
  纸质出版：2025-03-25
- 稿件说明：
移动端阅览
张朋飞, 翟睿辰, 程祥, 等. 满足地理不可区分性的偏好感知多对多任务分配算法[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 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于稀疏平滑自蒸馏的差分隐私深度学习方法

基于区块链的分层联邦学习系统

基于移动性预测的群智感知混合式任务分配

本地差分隐私下面向离群点的真值发现算法研究