Redundancy-Aware and Budget-Feasible Incentive Mechanism in Crowd Sensing. (11th January 2019)

• Record Type: Journal Article
• Authors: Li, Juan; Zhu, Yanmin; Yu, Jiadi
• Editors: Berenbrink, Petra
• Is Part Of: Computer journal. Volume 63:Number 1(2020)
• Page Start: 66
• Page End: 79
• Publication Date: 2019-01-11
• Subjects: crowd sensing -- incentive mechanism -- redundancy-aware data utility -- budget feasibility -- auction -- truthful; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy139
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Crowd sensing has emerged as a compelling paradigm for collecting sensing data over a vast area. It is of paramount importance for crowd sensing systems to provide effective incentive mechanisms. This paper studies the critical problem of maximizing the aggregate data utility under a budget constraint in incentive mechanism design in crowd sensing. This problem is particularly challenging given the redundancy in sensing data, self-interested and strategic user behavior, and private cost information of smartphones users. Most of existing mechanisms do not consider the important performance objective—maximizing the redundancy-aware data utility of sensing data collected from smartphones users. Furthermore, they do not consider the practical constraint on budget. In this paper, we propose an incentive mechanism based on a reverse auction framework. It consists of an approximation algorithm for winning user determination and a critical payment scheme. The approximation algorithm guarantees an approximation ratio for the aggregate data utility at polynomial-time complexity. The critical payment scheme guarantees truthful bidding. The rigorous theoretical analysis demonstrates that our mechanism achieves truthfulness, individual rationality, computational efficiency and budget feasibility.