Differentially Private Task Allocation Algorithm Under Preference Protection

Abstract

Mobile crowdsensing has been widely applied as a kind of perception paradigm, and task allocation is a fundamental research issue in mobile crowdsensing. Existing task allocation algorithms under differential privacy are not suitable for preference protection scenarios as they may inject too much noise. To this end, in this paper, we propose a differentially private task allocation algorithm with preference protection, referred to as SLEPT. In SLEPT, we divide privacy budget into three parts. Specifically, we first use one part of privacy budget to perturb the location of each worker. Then we use another part of privacy budget to perturb the preference information of him. In particular, to relieve the problem that perturbation may lead to that tasks will not be allocated, we propose a two-phase preference collection mechanism called TPC. Finally, we propose a task allocation sequential updating mechanism TASU using the remaining privacy budget. It aims to reduce the travel distance of workers and improve the success rate of task allocation. Theoretical analysis shows that SLEPT satisfies differential privacy. Time complexity analysis shows that it is linearly related to the number of tasks. The results on two public datasets verify the effectiveness of SLEPT. It is worth noting that although SLEPT is proposed for task allocation, its idea is also applicable to other crowdsensing scenarios, such as high-dimensional data collection.

Keywords

• Crowdsensing
• differential privacy
• geo-indistinguishability
• preference protection
• task allocation