LEPA: Incentivizing Long-term Privacy-preserving Data Aggregation in Crowdsensing

Zhikun Zhang, Shibo He, Mengyuan Zhang, Jiming ChenarXiv 2017 · arXiv

Abstract

Crowdsensing systems face significant challenges in maintaining long-term user participation while protecting individual privacy. This paper introduces LEPA (Long-tErm Privacy-preserving data Aggregation), an online incentive mechanism designed to balance data accuracy, privacy costs, and user retention. By integrating Local Differential Privacy (LDP) with Lyapunov optimization, LEPA transforms long-term participation constraints into a stable queue problem, ensuring users remain active through fair selection and compensation. Experimental results demonstrate that LEPA maintains nearly 100% user retention compared to traditional static models.

Introduction

Mobile crowdsensing (MCS) has become a cornerstone for applications like traffic monitoring (e.g., Waze) and environmental sensing. However, two major hurdles prevent these systems from scaling effectively: privacy concerns and user retention. Users are often hesitant to share raw GPS or sensor data that could reveal sensitive habits. Furthermore, most existing incentive models are "static," focusing on single-round snapshots. If a user is not selected frequently enough, they fail to earn sufficient cumulative compensation to justify the battery and data drain, leading to app uninstallation or "churn."

System Architecture

The LEPA framework consists of a Fusion Center (FC) and a set of Participatory Users (PUs). The FC manages a task pool and employs an incentive mechanism to select winners based on their bids, which reflect both sensing and privacy costs.

System architecture of the LEPA framework, illustrating the interaction between Participatory Users (PUs) and the Fusion Center.

As shown in the architecture, the process involves a multi-step cycle: the FC requests tasks, PUs submit bids, the incentive mechanism selects a winner set and issues payments, and finally, PUs provide perturbed data for aggregation.

Methodology

To address the "strategy coupling" problem—where a selection decision today affects participation tomorrow—the authors propose several key techniques:

  • Local Differential Privacy (LDP): Instead of trusting a central server, users add "well-calibrated" Laplacian noise to their data locally. The paper uses tail bound theory (Chebyshev’s inequality) to quantify how this noise impacts aggregation accuracy, bypassing complex non-integrable distributions.
  • Lyapunov Optimization: To manage long-term participation, the authors maintain a "virtual request queue" for each user. This queue grows when a user is not selected, naturally forcing the system to prioritize neglected users to ensure they earn enough to stay active.
  • Reverse Combinatorial Auction: The mechanism is designed to be Truthful (bidding true cost is the optimal strategy) and Individually Rational (users never lose money). The online auction has a computational complexity of $O(N^3 + N^2M)$, making it suitable for real-time applications.

Evaluation and Results

The paper evaluates LEPA through extensive simulations involving 100 to 200 users and 10 concurrent tasks. The primary metric for success is the ability to maintain a stable user base over time.

Comparison of user retention between the proposed online LPRC auction (LEPA) and a traditional static auction over 100 time slots.

As illustrated in the results, a standard static auction sees more than 50% of users drop out within 100 time slots. In contrast, under the LEPA mechanism (referred to as the Online LPRC auction in simulations), the user base remains almost 100% intact. Additionally, LEPA was found to be more cost-efficient than compulsory selection models, significantly reducing total payments by the Fusion Center while maintaining high data accuracy.

Conclusion

LEPA provides a robust solution for sustainable crowdsensing by aligning system-wide accuracy goals with individual privacy and economic needs. By treating user retention as a stability problem, it ensures the long-term viability of participatory sensing networks. Future work may explore heterogeneous privacy requirements where different users set unique privacy "price tags."

Summary updated

Abstract

In this paper, we study the incentive mechanism design for real-time data aggregation, which holds a large spectrum of crowdsensing applications. Despite extensive studies on static incentive mechanisms, none of these are applicable to real-time data aggregation due to their incapability of maintaining PUs' long-term participation. We emphasize that, to maintain PUs' long-term participation, it is of significant importance to protect their privacy as well as to provide them a desirable cumulative compensation. Thus motivated, in this paper, we propose LEPA, an efficient incentive mechanism to stimulate long-term participation in real-time data aggregation. Specifically, we allow PUs to preserve their privacy by reporting noisy data, the impact of which on the aggregation accuracy is quantified with proper privacy and accuracy measures. Then, we provide a framework that jointly optimizes the incentive schemes in different time slots to ensure desirable cumulative compensation for PUs and thereby prevent PUs from leaving the system halfway. Considering PUs' strategic behaviors and combinatorial nature of the sensing tasks, we propose a computationally efficient on-line auction with close-to-optimal performance in presence of NP-hardness of winner user selection. We further show that the proposed on-line auction satisfies desirable properties of truthfulness and individual rationality. The performance of LEPA is validated by both theoretical analysis and extensive simulations.
BibTeX
@misc{zhang2017lepa,
  author = {Zhikun Zhang and Shibo He and Mengyuan Zhang and Jiming Chen},
  title = {{LEPA: Incentivizing Long-term Privacy-preserving Data Aggregation in Crowdsensing}},
  year = {2017},
  eprint = {1712.08807},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.08807},
}
Figure