FIMI:A Constant Frugal Incentive Mechanism for Time Window Coverage in Mobile Crowdsensing
Jia Xu1,2, Member, CCF, ACM, IEEE, Jian-Ren Fu1, De-Jun Yang3, Member, IEEE, Li-Jie Xu1,2, Lei Wang1,2, Tao Li1,2, Member, IEEE
1 School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;
2 Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;
3 Department of Computer Science, Colorado School of Mines, Golden 80401, U.S.A
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.
The work was supported by the National Natural Science Foundation of China under Grant Nos. 61472193 and 61472192, the Young Scientists Fund of the National Natural Science Foundation of China under Grant No. 61502251, the Major Research Plan of the National Natural Science Foundation of China under Grant No. 91646116, the Natural Science Foundation of USA under Grant Nos. 1444059, 1420881 and 1717315, and the Natural Science Foundation of Jiangsu Province of China under Grant Nos. BK20141429, BK20151511 and BE2016776.
About author: Jia Xu received his M.S.degree in computer science from Yangzhou University,Yangzhou,in 2006,and his Ph.D.degree in computer science from Nanjing University of Science and Technology,Nanjing,in 2010.He is currently a professor at Nanjing University of Posts and Telecommunications, Nanjing.
Cite this article:
Jia Xu, Jian-Ren Fu, De-Jun Yang, Li-Jie Xu, Lei Wang, Tao Li.FIMI:A Constant Frugal Incentive Mechanism for Time Window Coverage in Mobile Crowdsensing[J] Journal of Computer Science and Technology, 2017,V32(5): 919-935
 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. Crowdsourcingbased 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 feasible mechanisms. 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.