Tradeoff Between Location Quality and Privacy in Crowdsensing: An Optimization Perspective

Crowdsensing enables a wide range of data collection, where the data are usually tagged with private locations. Protecting users' location privacy has been a central issue. The study of various location perturbation techniques, e.g., k-anonymity, for location privacy has received widespread attention. Despite the huge promise and considerable attention, provable good algorithms considering the tradeoff between location privacy and location information quality from the optimization perspective in crowdsensing are lacking in the literature. In this article, we study two related optimization problems from two different perspectives. The first problem is to minimize the location quality degradation caused by the protection of users' location privacy. We present an efficient optimal algorithm OLoQ for this problem. The second problem is to maximize the number of protected users, subject to a location quality degradation constraint. To satisfy the different requirements of the platform, we consider two cases for this problem: 1) overlapping and 2) nonoverlapping perturbations. For the former case, we give an efficient optimal algorithm OPUM
_O
. For the latter case, we first prove its NP-hardness. We then design a (1-E)-approximation algorithm NPUM
_N
and a fast and effective heuristic algorithm HPUM
_N
. Extensive simulations demonstrate that OLoQ, OPUM
_O
, and HPUM
_N
significantly outperform an existing algorithm.