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.
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