Abstract
Mobile crowdsensing has become an efficient paradigm for performing large-scale sensing tasks. An incentive mechanism is important for a mobile crowdsensing system to stimulate participants and to achieve good service quality. In this paper, we explore truthful incentive mechanisms that focus on minimizing the total payment for a novel scenario, where the platform needs the complete sensing data in a requested time window (RTW). We model this scenario as a reverse auction and design FIMI, a constant frugal incentive mechanism for time window coverage. FIMI consists of two phases, the candidate selection phase and the winner selection phase. In the candidate selection phase, it selects two most competitive disjoint feasible user sets. Afterwards, in the winner selection phase, it finds all the interchangeable user sets through a graph-theoretic approach. For every pair of such user sets, FIMI chooses one of them by the weighted cost. Further, we extend FIMI to the scenario where the RTW needs to be covered more than once. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve the properties of RTW feasibility (or RTW multi-coverage), computation efficiency, individual rationality, truthfulness, and constant frugality.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Zheng Y D, Cheng R, Maniu S, Mo L Y. On optimality of jury selection in crowdsourcing. In Proc. the 18th Int. Conf. Extending Database Technology, March 2015, pp.193-204.
Zheng Y D, Li G L, Li Y B, Shan C H, Cheng R. Truth inference in crowdsourcing: Is the problem solved? Proc. the VLDB Endowment, 2017, 10(5): 541-552.
Zheng Y D, Li G L, Cheng R. DOCS: A domain-aware crowdsourcing system using knowledge bases. Proc. the VLDB Endowment, 2016, 10(4): 361-372.
Li G L, Wang J N, Zheng Y D, Franklin M J. Crowdsourced data management: A survey. IEEE Trans. Knowledge and Data Engineering, 2016, 28(9): 2296-2319.
Rana R K, Chou C T, Kanhere S S, Bulusu N, Hu W. Earphone: An end-to-end participatory urban noise mapping system. In Proc. the 9th ACM/IEEE Int. Conf. Information Processing in Sensor Networks, April 2010, pp.105-116.
Hu H Q, Li G L, Bao Z F, Cui Y, Feng J H. Crowdsourcing-based real-time urban traffic speed estimation: From trends to speeds. In Proc. the 32nd IEEE Int. Conf. Data Engineering, May 2016, pp.883-894.
Ye H B, Gu T, Tao X P, Lv J. Infrastructure-free floor localization through crowdsourcing. Journal of Computer Science and Technology, 2015, 30(6): 1249-1273.
Zhou P F, Zheng Y Q, Li M. How long to wait?: Predicting bus arrival time with mobile phone based participatory sensing. In Proc. the 10th ACM Int. Conf. Mobile Systems, Applications, and Services, June 2012, pp.379-392.
Jiang Z P, Xi W, Li X Y, Tang S Z, Zhao J Z, Han J S, Zhao K,Wang Z, Xiao B. Communicating is crowdsourcing: Wi-Fi indoor localization with CSI-based speed estimation. Journal of Computer Science and Technology, 2014, 29(4): 589-604.
Yang D J, Xue G L, Fang X, Tang J. Crowd-sourcing to smartphones: Incentive mechanism design for mobile phone sensing. In Proc. the 18th Annual Int. Conf. Mobile Computing and Networking, August 2012, pp.173-184.
Singer Y, Mittal M. Pricing mechanisms for crowdsourcing markets. In Proc. the 22nd Int. Conf. World Wide Web, May 2013, pp.1157-1166.
Feng Z N, Zhu Y M, Zhang Q, Ni L M, Vasilakos A V. TRAC: Truthful auction for location-aware collaborative sensing in mobile crowdsourcing. In Proc. IEEE INFOCOM, April 2014, pp.1231-1239.
Zhao D, Li X Y, Ma H D. How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint. In Proc. IEEE INFOCOM, April 2014, pp.1213-1221.
Zhang X L, Yang Z, Zhou Z M, Cai H B, Chen L, Li X Y. Free market of crowdsourcing: Incentive mechanism design for mobile sensing. IEEE Trans. Parallel and Distributed Systems, 2014, 25(12): 3190-3200.
Singer Y. Budget feasiblemechanisms. In Proc. the 51st Annual IEEE Symp. Foundations of Computer Science, October 2010, pp.765-774.
Archer A, Tardos É. Frugal path mechanisms. ACM Trans. Algorithms, 2007, 3(1): Article No. 3.
Karlin A R, Kempe D. Beyond VCG: Frugality of truthful mechanisms. In Proc. the 46th Annual IEEE Symp. Foundations of Computer Science, October 2005, pp.615-624.
Nisan N, Roughgarden T, Tardos E, Vazirani V V. Algorithmic Game Theory. Cambridge: Cambridge University Press 2007.
Zheng Y D,Wang J N, Li G L, Cheng R, Feng J H. QASCA: A quality-aware task assignment system for crowdsourcing applications. In Proc. the ACM SIGMOD Int. Conf. Management of Data, May 2015, pp.1031-1046.
Fan J, Li G L, Ooi B C, Tan K I, Feng J H. iCrowd: An adaptive crowdsourcing framework. In Proc. the ACM SIGMOD Int. Conf. Management of Data, May 2015, pp.1015-1030.
Hu H Q, Zheng Y D, Bao Z F, Li G L, Feng J H, Cheng R. Crowdsourced POI labelling: Location-aware result inference and task assignment. In Proc. the 32nd IEEE Int. Conf. Data Engineering, May 2016, pp.61-72.
Kazemi L, Shahabi C. GeoCrowd: Enabling query answering with spatial crowdsourcing. In Proc. the 20th Int. Conf. Advances in Geographic Information Systems, November 2012, pp.189-198.
Tong Y X, She J Y, Ding B L, Wang L B, Chen L. Online mobile micro-task allocation in spatial crowdsourcing. In Proc. the 32nd IEEE Int. Conf. Data Engineering, May 2016, pp.49-60.
Tong Y X, She J Y, Ding B L, Chen L, Wo T Y, Xu K. Online minimum matching in real-time spatial data: Experiments and analysis. Proc. the VLDB Endowment, 2016, 9(12): 1053-1064.
Zhang X, Xue G L, Yu R Z, Yang D J, Tang J. Truthful incentive mechanisms for crowdsourcing. In Proc. IEEE Conf. Computer Communications, April 2015, pp.2830-2838.
Xu J, Li H, Li Y X, Yang D J, Li T. Incentivizing the biased requesters: Truthful task assignment mechanisms in crowdsourcing. In Proc. the 14th Annual IEEE Int. Conf. Sensing, Communication, and Networking, June 2017.
Koutsopoulos I. Optimal incentive-driven design of participatory sensing systems. In Proc. IEEE INFOCOM, April 2013, pp.1402-1410.
Xu J, Xiang J X, Yang D J. Incentive mechanisms for time window dependent tasks in mobile crowdsensing. IEEE Trans. Wireless Communications, 2015, 14(11): 6353-6364.
Xu J, Xiang J X, Li Y X. Incentivize maximum continuous time interval coverage under budget constraint in mobile crowd sensing. Wireless Networks, 2017, 23(5): 1549-1562.
Talwar K. The price of truth: Frugality in truthful mechanisms. In Proc. Annual Symp. Theoretical Aspects of Computer Science, February 2003, pp.608-619.
Kempe D, Salek M, Moore C. Frugal and truthful auctions for vertex covers, flows and cuts. In Proc. the 51st Annual IEEE Symp. Foundations of Computer Science, October 2010, pp.745-754.
Elkind E, Goldberg L A, Goldberg P W. Frugality ratios and improved truthful mechanisms for vertex cover. In Proc. the 8th ACM Conf. Electronic Commerce, June 2007, pp.336-345.
Chen N, Elkind E, Gravin N, Petrov F. Frugal mechanism design via spectral techniques. In Proc. the 51st Annual IEEE Symp. Foundations of Computer Science, October 2010, pp.755-764.
Hsu W J, Dutta D, Helmy A. CSI: A paradigm for behaviororiented profile-cast services in mobile networks. Ad Hoc Networks, 2012, 10(8): 1586-1602.
Myerson R B. Optimal auction design. Mathematics of Operations Research 1981, 6(1): 58-73.
Immorlica N, Karger D, Nikolova E, Sami R. First-price path auctions. In Proc. the 6th ACM Conf. Electronic Commerce, June 2005, pp.203-212.
Edmonds J, Karp R M. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 1972, 19(2): 248-264.
Amici R, Bonola M, Bracciale L, Rabuffi A, Loreti P, Bianchi G. Performance assessment of an epidemic protocol in VANET using real traces. Procedia Computer Science, 2014, 40: 92-99.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
ESM 1
(PDF 552 kb)
Rights and permissions
About this article
Cite this article
Xu, J., Fu, JR., Yang, DJ. et al. FIMI: A Constant Frugal Incentive Mechanism for Time Window Coverage in Mobile Crowdsensing. J. Comput. Sci. Technol. 32, 919–935 (2017). https://doi.org/10.1007/s11390-017-1773-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11390-017-1773-4