A Comprehensive Location-Privacy-Awareness Task Selection Mechanism in Mobile Crowd-Sensing

Ke Yan, Guangchun Luo, Xu Zheng, Ling Tian, Akshita Maradapu Vera Venkata SaiIEEE Access 2019 · OpenReview

Abstract

Mobile crowd-sensing (MCS) is a promising paradigm for the Internet of Things, but location privacy leakage remains a significant barrier to user engagement. This paper proposes a novel framework for task selection that jointly optimizes location privacy, resource consumption, and task profits. We introduce two algorithms, Simple Task Selection (STS) and Location-Privacy-Awareness Task Selection (LPTS), which protect against destination inference and direct location disclosure. Experimental results on real-world data demonstrate that our mechanisms achieve high task earnings while maintaining robust privacy guarantees.

Introduction

The proliferation of smartphones and high-speed networks has enabled Mobile Crowd-Sensing (MCS), where individuals act as mobile sensors to collect data for various urban and environmental applications. While workers are incentivized with rewards, the act of reporting data at specific locations exposes them to severe privacy risks. Malicious entities can analyze these data points to infer sensitive locations, such as homes or workplaces, or predict a worker's future destination.

The Privacy-Utility Trade-off

Existing privacy solutions often rely on a "trusted" platform or simple location obfuscation. However, these methods frequently fail to account for a worker's overall mobility pattern and can significantly reduce the potential rewards, discouraging participation. The challenge lies in creating a mechanism that allows workers to deviate from their shortest path for profit without compromising their long-term privacy.

Methodology: STS and LPTS Algorithms

The authors frame the task selection problem as a constrained optimization problem, proven to be NP-hard. To solve this, they propose two algorithms based on a Branch and Bound approach, designed to operate under three primary constraints:

  • Detour Ratio: The maximum additional distance a worker is willing to travel.
  • Worker Capacity: The limit on the number of tasks a worker can perform.
  • Privacy Threshold: A user-defined level of acceptable risk for destination inference.

Simple Task Selection (STS)

STS focuses on protecting the worker's final destination. It utilizes a first-order Markov model to identify "risk locations"—points that have a high statistical probability of revealing the worker's ultimate destination. By avoiding these leaky intermediate steps, STS preserves destination privacy.

Location-Privacy-Awareness Task Selection (LPTS)

LPTS provides a more comprehensive privacy layer by protecting both the destination and the specific passing locations. It employs Geo-indistinguishability, a form of local differential privacy. This technique adds controlled Laplace noise to the worker's coordinates on their device before the data is transmitted to the platform, ensuring privacy even if the platform itself is malicious.

Comparison of task selection scenarios: (a) local selection, (b) simple path selection, and (c) privacy-aware path selection with detours.

Experimental Results

The framework was evaluated using a dataset from Gowalla, comprising 70,000 check-ins in London. The urban area was modeled as a 20x20 grid to simulate realistic movement and inference attacks.

  • Reward Optimization: The proposed algorithms consistently outperformed greedy selection strategies, securing higher total rewards while adhering to strict privacy and detour limits.
  • Quantifiable Privacy Cost: The study identified a "privacy tax." Implementing LPTS resulted in approximately a 23.5% reduction in profit compared to STS, highlighting the cost of protecting individual passing locations versus just the destination.
  • Computational Performance: Despite the NP-hard nature of the problem, the LPTS algorithm completed task selection in an average of 4 seconds, making it suitable for real-world mobile deployment.

Conclusion

This research provides a robust framework for balancing profit and privacy in MCS. By shifting the power of privacy sanitization to the worker's device and allowing for customized privacy levels, the proposed STS and LPTS algorithms offer a practical solution to the location leakage problem. Future work will focus on developing heuristic algorithms to improve scalability in increasingly complex urban environments.

Summary updated

Abstract

With the boom in the production of smartphones and easy access to networks, mobile crowd-sensing (MCS) is becoming a promising and rapidly growing sensing paradigm for the Internet of Things (IoT). In MCS, workers can get rewarded by participating in data collection while traveling to their destination from some starting point. However, the privacy leakage becomes a serious and unavoidable problem that hinders users' engagement. Taking task at a specific location or even going through some seemingly innocent locations may both disclose user's sensitive location information. Simply concealing or obfuscating the sensitive locations could preserve the privacy to a certain extent, at the cost of reward reduction, which will significantly frustrate the workers. To address these issues, this paper provides a novel framework for task selection in MCS jointly covering comprehensive location privacy preservation, efficient resource consumption, and high task profits. In our framework, workers can select their paths freely, and customize their privacy requirements for protection against both direct location disclosure and destination inference attack. Two corresponding algorithms are proposed for path selection under various stages of privacy preservation. The theoretical analysis demonstrates the performance of two algorithms on both privacy and utility aspects. We also evaluate our proposed mechanisms through extensive experiments on a real-world data set. The results validate that the proposed mechanisms can achieve higher task earnings and better privacy preservation.
BibTeX
@inproceedings{yan2019comprehensive,
  author = {Ke Yan and Guangchun Luo and Xu Zheng and Ling Tian and Akshita Maradapu Vera Venkata Sai},
  title = {{A Comprehensive Location-Privacy-Awareness Task Selection Mechanism in Mobile Crowd-Sensing}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=ktNfNTxzkn},
}
Figure