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

Yuhui Zhang, Ming Li, Dejun Yang, Jian Tang, Guoliang Xue, Jia Xu

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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 OPUMO. For the latter case, we first prove its NP-hardness. We then design a '(1-\epsilon)' -approximation algorithm NPUMN and a fast and effective heuristic algorithm HPUMN. Extensive simulations demonstrate that OLoQ, OPUMO, and HPUMN significantly outperform an existing algorithm.

Original languageEnglish (US)
Article number8988265
Pages (from-to)3535-3544
Number of pages10
JournalIEEE Internet of Things Journal
Issue number4
StatePublished - Apr 2020


  • Crowdsensing
  • k-anonymity
  • location data quality
  • location privacy

ASJC Scopus subject areas

  • Signal Processing
  • Information Systems
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'Tradeoff Between Location Quality and Privacy in Crowdsensing: An Optimization Perspective'. Together they form a unique fingerprint.

Cite this