Research on Skill-Aware Task Assignment Algorithm under Local Differential Privacy
-
摘要: 空间众包任务分配依托平台将具有地理位置属性的任务指派给周边工人，然而工人在上传实时位置信息过程中，行踪易被泄露或滥用，存在隐私风险。现有方法虽采用可信第3方或差分隐私进行位置扰动，但在多技能任务及技能分布不均场景下难以兼顾隐私保护与分配效率。为此，该文提出一种融合隐私保护与技能感知的协同分配算法。首先采用截断拉普拉斯机制对工人位置加噪，在满足本地差分隐私的同时降低定位偏差；其次引入基于信息熵的技能多样性评估指标，并设计动态策略优化工人集合技能分布；再构建基于技能贡献值的贪婪算法，并结合时空与预算约束提出3种剪枝策略提升计算效率。实验结果表明，该方法在服务质量损失、任务完成率与平均预算剩余率等方面表现优良，实现了隐私保护与任务分配效率之间的有效平衡。Abstract:
Objective With the proliferation of mobile smart devices and wireless networks, Spatial Crowdsourcing (SC) has emerged as a new paradigm for collaborative task execution. By leveraging workers’ real-time locations, SC platforms dynamically assign tasks to distributed participants. However, continuous exposure of location data creates privacy risks, including trajectory inference and identity disclosure, which reduce worker participation and threaten system sustainability. Existing privacy-preserving methods either rely on trusted third parties or apply traditional differential privacy mechanisms. The former incurs high costs and security vulnerabilities, whereas the latter struggles to balance the trade-off between noise magnitude and data utility, often reducing task matching accuracy. To address these challenges, this study proposes a skill-aware task assignment algorithm under Local Differential Privacy (LDP) that simultaneously enhances location privacy protection and task assignment performance. The algorithm is particularly effective in settings characterized by uneven skill distributions and complex task requirements. Methods To protect workers’ location privacy, a Clip–Laplace (CLP) mechanism is applied to perturb real-time location data under Local Differential Privacy (LDP), ensuring bounded noise while maintaining data utility. To mitigate mismatches between heterogeneous task requirements and imbalanced worker skills, an entropy-based metric is used to evaluate skill diversity. When entropy falls below a predefined threshold, a secondary screening strategy rebalances the distribution by suppressing common skills and prioritizing rare ones. A skill-aware Pruning Greedy task assignment algorithm (PUGR) is then developed. PUGR iteratively selects the worker–task pair with the highest marginal contribution to maximize skill coverage under spatiotemporal and budget constraints. To improve computational efficiency, three pruning strategies are integrated: time–distance pruning, high-reward pruning, and budget-infeasibility pruning. Finally, comparative and ablation experiments on three real-world datasets assess the method using multiple metrics, including Loss of Quality of Service (LQS), Average Remaining Budget Rate (ARBR), and Task Completion Rate (TCR). Results and Discussions Experimental results show that the CLP mechanism consistently achieves lower LQS than the traditional Laplace mechanism (LP) across different privacy budgets, effectively reducing errors introduced by noise ( Fig. 2 ). For skill diversity, the entropy-based metric combined with secondary screening nearly doubles the average entropy of candidate workers on the TKY and NYC datasets, demonstrating its effectiveness in balancing skill distribution. In task assignment, the proposed PUGR algorithm completes most worker–task matchings within four iterations, thereby reducing redundant computation and accelerating convergence (Fig. 3 ). Regarding budget utilization, the ARBR under CLP remains close to the No Privacy (NoPriv) baseline, indicating efficient resource allocation (Fig. 4 ,Table 2 ). For task completion, the method achieves a TCR of up to 90% in noise-free settings and consistently outperforms Greedy, OE-ELA, and TsPY under CLP (Fig. 5 ). Ablation studies further validate the contributions of secondary screening and pruning strategies to overall performance improvement.Conclusions This study addresses two central challenges in spatial crowdsourcing: protecting workers’ location privacy and improving skill-aware task assignment. A task assignment framework is proposed that integrates the CLP mechanism with a skill-aware strategy under the LDP model. The CLP mechanism provides strong privacy guarantees while preserving data utility by limiting noise magnitude. An entropy-based metric combined with secondary screening ensures balanced skill distribution, substantially enhancing skill coverage and task execution success in multi-skill scenarios. The PUGR algorithm incorporates skill contribution evaluation with multiple pruning constraints, thereby reducing the search space and improving computational efficiency. Experiments on real-world datasets demonstrate the method’s superiority in terms of LQS, ARBR, and TCR, confirming its robustness, scalability, and effectiveness in balancing privacy protection with assignment performance. Future work will explore dynamic pricing mechanisms based on skill scarcity and personalized, adaptive incentives to foster fairness, long-term worker engagement, and the sustainable development of spatial crowdsourcing platforms. -
表 1 符号及含义
符号 描述 $ {\mathcal{T}} $ 在时间点$p$处的$\mathcal{M}$个空间任务${t_j}$的集合 ${\mathcal{W}}$ 在时间点$p$处的${\mathcal{N}}$个工人${w_i}$的集合 $ \mathcal{W}' $ 实现技能多样性均衡的工人集合 $ {\mathcal{A}} $ 系统中存在的技能集合 ${e_j}$ 到达任务${t_j}$所在位置的截止时间 ${l_i}\left( p \right)$ 工人${w_i}$在时间点$p$时的真实位置 ${l_i}^\prime \left( p \right)$ 工人${w_i}$在时间点$p$时的模糊位置 ${l_j}$ 任务${t_j}$的位置 ${\mathcal{X}_i}$ 工人${w_i}$拥有的一组技能 ${\mathcal{Y}_j}$ 任务${t_j}$所需技能的集合 ${d_i}$ 工人${w_i}$的最大移动距离 ${\mathcal{B}_j}$ 任务${t_j}$的最大预算 $\mathcal{R}$ 时间点$p$时的任务分配结果集 
下载: 导出CSV
表 2 不同数据集上隐私预算对平均预算剩余率的影响
数据集 $\varepsilon $ ARBR PUGR GR OE-ELA TsPY CLP LP CLP LP CLP LP CLP LP TKY 0 0.7890 0.5200 0.7156 0.5441 1 0.7135 0.6431 0.1689 0.1666 0.4460 0.4545 0.4536 0.4091 3 0.7716 0.7153 0.1956 0.1219 0.4832 0.6106 0.5074 0.5033 5 0.8269 0.7505 0.2562 0.4079 0.4395 0.5055 0.5254 0.1512 NYC 0 0.5813 0.4881 0.5998 0.5259 1 0.5108 0.6095 0.1447 0.1604 0.3731 0.3231 0.4070 0.2039 3 0.7535 0.7091 0.1747 0.2404 0.4932 0.5826 0.5487 0.4468 5 0.7141 0.7300 0.3479 0.2246 0.8063 0.5535 0.8979 0.6780
下载: 导出CSV
-
[1] XIE Yuan, WANG Yongheng, LI Kenli, et al. Satisfaction-aware task assignment in spatial crowdsourcing[J]. Information Sciences, 2023, 622: 512–535. doi: 10.1016/j.ins.2022.11.081. [2] XU Lang, LI Jiqiang, ZHANG Hao, et al. A privacy-preserving takeaway delivery service scheme[C]. 17th International Conference on Provable and Practical Security, Wuhan, China, 2023: 385–403. doi: 10.1007/978-3-031-45513-1_21. [3] 孟秀丽, 杨静, 吴一凡. 考虑奖惩机制和成本互担的众包物流服务质量最优控制[J]. 中国管理科学, 2022, 30(11): 182–195. doi: 10.16381/j.cnki.issn1003-207x.2020.0746.MENG Xiuli, YANG Jing, and WU Yifan. Optimal control of crowdsourcing logistics service quality considering reward-penalty mechanism and cost sharing[J]. Chinese Journal of Management Science, 2022, 30(11): 182–195. doi: 10.16381/j.cnki.issn1003-207x.2020.0746. [4] LIN Ping, ZHANG Xiaosan, YAN Shuming, et al. Dynamic capabilities and business model innovation of platform enterprise: A case study of DiDi taxi[J]. Scientific Programming, 2020, 2020(1): 8841368. doi: 10.1155/2020/8841368. [5] WANG Jianqiang, PAN Jialu, ZHENG Liping, et al. A systematic space-time route planning approach coordinated with task assignment for autonomous delivery vehicles fleet[J]. IEEE Access, 2023, 11: 79370–79383. doi: 10.1109/ACCESS.2023.3299856. [6] GUO Bin, LIU Yan, WANG Leye, et al. Task allocation in spatial crowdsourcing: Current state and future directions[J]. IEEE Internet of Things Journal, 2018, 5(3): 1749–1764. doi: 10.1109/JIOT.2018.2815982. [7] 冯登国, 张敏, 叶宇桐. 基于差分隐私模型的位置轨迹发布技术研究[J]. 电子与信息学报, 2020, 42(1): 74–88. doi: 10.11999/JEIT190632.FENG Dengguo, ZHANG Min, and YE Yutong. Research on differentially private trajectory data publishing[J]. Journal of Electronics & Information Technology, 2020, 42(1): 74–88. doi: 10.11999/JEIT190632. [8] NAVIDAN H, MOGHTADAIEE V, NAZARAN N, et al. Hide me behind the noise: Local differential privacy for indoor location privacy[C]. 2022 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW), Genoa, Italy, 2022: 514–523. doi: 10.1109/EuroSPW55150.2022.00061. [9] ZHANG Pengfei, FANG Xiang, ZHANG Zhikun, et al. Horizontal multi-party data publishing via discriminator regularization and adaptive noise under differential privacy[J]. Information Fusion, 2025, 120: 103046. doi: 10.1016/j.inffus.2025.103046. [10] 李可佳, 胡学先, 陈越, 等. 基于主成分分析和函数机制的差分隐私线性回归算法[J]. 计算机科学, 2023, 50(8): 342–351. doi: 10.11896/jsjkx.220800255.LI Kejia, HU Xuexian, CHEN Yue, et al. Differential privacy linear regression algorithm based on principal component analysis and Functional mechanism[J]. Computer Science, 2023, 50(8): 342–351. doi: 10.11896/jsjkx.220800255. [11] ZHANG Pengfei, CHENG Xiang, ZHANG Zhikun, et al. Maximizing area coverage in privacy-preserving worker recruitment: A prior knowledge-enhanced geo-indistinguishable approach[J]. IEEE Transactions on Information Forensics and Security, 2025, 20: 5138–5151. doi: 10.1109/TIFS.2025.3568163. [12] ZHANG Pengfei, SUN Hong, ZHANG Zhikun, et al. Privacy-preserving recommendations with mixture model-based matrix factorization under local differential privacy[J]. IEEE Transactions on Industrial Informatics, 2025, 21(7): 5451–5459. doi: 10.1109/TII.2025.3555993. [13] LIU Yixuan, ZHAO Suyun, XIONG Li, et al. Echo of neighbors: Privacy amplification for personalized private federated learning with shuffle model[C]. The 37th AAAI Conference on Artificial Intelligence, Washington, USA, 2023: 11865–11872. doi: 10.1609/aaai.v37i10.26400. [14] 吴大鹏, 管芃, 张普宁, 等. 群组协作的移动群智感知任务分配方法[J]. 电子与信息学报, 2023, 45(12): 4308–4316. doi: 10.11999/JEIT221046.WU Dapeng, GUAN Peng, ZHANG Puning, et al. Task allocation method of mobile crowdsensing based on group collaboration[J]. Journal of Electronics & Information Technology, 2023, 45(12): 4308–4316. doi: 10.11999/JEIT221046. [15] HUANG Yang, CHEN Honglong, MA Guoqi, et al. OPAT: Optimized allocation of time-dependent tasks for mobile crowdsensing[J]. IEEE Transactions on Industrial Informatics, 2022, 18(4): 2476–2485. doi: 10.1109/TII.2021.3094527. [16] LIU Jiaxu, ZHU Haogang, and CHEN Xiao. Complicated-skills-based task assignment in spatial crowdsourcing[C]. WAIM 2016 International Workshops on Web-Age Information Management, Nanchang, China, 2016: 211–223. doi: 10.1007/978-3-319-47121-1_18. [17] TAO Xi and HAFID A S. DeepSensing: A novel mobile crowdsensing framework with double deep Q-network and prioritized experience replay[J]. IEEE Internet of Things Journal, 2020, 7(12): 11547–11558. doi: 10.1109/JIOT.2020.3022611. [18] SONG Tianshu, XU Ke, LI Jiangneng, et al. Multi-skill aware task assignment in real-time spatial crowdsourcing[J]. Geoinformatica, 2020, 24(1): 153–173. doi: 10.1007/s10707-019-00351-4. [19] HAN Lei, YU Zhiwen, YU Zhiyong, et al. Online organizing large-scale heterogeneous tasks and multi-skilled participants in mobile crowdsensing[J]. IEEE Transactions on Mobile Computing, 2023, 22(5): 2892–2909. doi: 10.1109/tmc.2021.3132616. [20] HONG Yingcong, LI Junyi, LIN Yaping, et al. Trajectory-aware privacy-preserving method with local differential privacy in crowdsourcing[J]. EURASIP Journal on Information Security, 2024, 2024(1): 28. doi: 10.1186/s13635-024-00177-0. [21] WEI Jianhao, LIN Yaping, YAO Xin, et al. Differential privacy-based location protection in spatial crowdsourcing[J]. IEEE Transactions on Services Computing, 2022, 15(1): 45–58. doi: 10.1109/TSC.2019.2920643. [22] WANG Leye, YANG Dingqi, HAN Xiao, et al. Mobile crowdsourcing task allocation with differential-and-distortion geo-obfuscation[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 18(2): 967–981. doi: 10.1109/TDSC.2019.2912886. [23] BÉZIAUD L, ALLARD T, GROSS-AMBLARD D, et al. Lightweight privacy-preserving task assignment in skill-aware crowdsourcing[C]. 28th International Conference on Database and Expert Systems Applications, Lyon, France, 2017: 18–26. doi: 10.1007/978-3-319-64471-4_2. [24] VAZIRANI V V. Approximation Algorithms[M]. Berlin: Springer, 2003: 1–380. doi: 10.1007/978-3-662-04565-7. [25] YANG Dingqi, ZHANG Daqing, ZHENG V W, et al. Modeling user activity preference by leveraging user spatial temporal characteristics in LBSNs[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(1): 129–142. doi: 10.1109/tsmc.2014.2327053. [26] FAROOQ Umar and MAHEEN Barira. Skill-based task assignment[EB/OL]. https://www.kaggle.com/datasets/umerfarooq09/skill-based-task-assignment/data, 2024. (查阅网上资料,未找到本条文献作者和年份,请确认). -
图(5) / 表(2)
计量
- 文章访问数: 16
- HTML全文浏览量: 10
- PDF下载量: 1
- 被引次数: 0
下载:
