Mobile crowd sensing task optimal allocation: a mobility pattern matching perspective

Abstract

With the proliferation of sensor-equipped portable mobile devices, Mobile CrowdSensing (MCS) using smart devices provides unprecedented opportunities for collecting enormous surrounding data. In MCS applications, a crucial issue is how to recruit appropriate participants from a pool of available users to accomplish released tasks, satisfying both resource efficiency and sensing quality. In ordern to meet these two optimization goals simultaneously, in this paper, we present a novel MCS task allocation framework by aligning existing task sequence with users’ moving regularity as much as possible. Based on the process of mobility repetitive pattern discovery, the original task allocation problem is converted into a pattern matching issue, and the involved optimization goals are transformed into pattern matching length and support degree indicators. To determine a trade-off between these two competitive metrics, we propose greedybased optimal assignment scheme search approaches, namely MLP, MDP, IU1 and IU2 algorithm, with respect to matching length-preferred, support degree-preferred and integrated utility, respectively. Comprehensive experiments on realworld open data set and synthetic data set clearly validate the effectiveness of our proposed framework on MCS task optimal allocation.

Keywords

mobile crowd sensing / task allocation / mobility regularity / pattern matching

References

[1] Ganti R K, Ye F, Lei H. Mobile crowdsensing: current state and future challenges. IEEE Communications Magazine, 2011, 49(11): 32–39

[2] Guo B, Wang Z, Yu Z, Wang Y, Yen N Y, Huang R, Zhou X. Mobile crowd sensing and computing: the review of an emerging humanpowered sensing paradigm. ACM Computing Surveys, 2015, 48(1): 7

[3] Yu Z, Xu H, Yang Z, Guo B. Personalized travel package with multipoint- of-interest recommendation based on crowdsourced user footprints. IEEE Transactions on Human-Machine Systems, 2016, 46(1): 151–158

[4] Guo B, Chen H, Yu Z, Xie X, Huangfu S, Zhang D. FlierMeet: a mobile crowdsensing system for cross-space public information reposting, tagging, and sharing. IEEE Transactions on Mobile Computing, 2015, 14(10): 2020–2033

[5] Wang J, Wang Y, Zhang D, Wang L, Chen C, Lee J W, He Y. Realtime and generic queue time estimation based on mobile crowdsensing. Frontiers of Computer Science, 2017, 11(1): 49–60

[6] Xiong F, Liu Y, Cheng J. Modeling and predicting opinion formation with trust propagation in online social networks. Communications in Nonlinear Science and Numerical Simulation, 2017, 44(3): 513–524

[7] Wang J, Gao F, Cui P, Li C, Xiong Z. Discovering urban spatiotemporal structure from time-evolving traffic networks. In: Proceedings of the 16th Asia-Pacific Web Conference. 2014, 93–104

[8] Wang J, Gu Q, Wu J, Liu G, Xiong Z. Traffic speed prediction and congestion source exploration: a deep learning method. In: Proceedings of the 16th IEEE International Conference on Data Mining. 2016, 499–508

[9] Wang J, Chen C, Wu J, Xiong Z. No longer sleeping with a bomb: a duet system for protecting urban safety from dangerous goods. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 1673–1681

[10] Thebault-Spieker J, Terveen L G, Hecht B. Avoiding the south side and the suburbs: the geography of mobile crowdsourcing markets. In: Proceedings of ACM Conference on Computer Supported Cooperative Work and Social Computing. 2015, 265–275

[11] Chon Y, Lane N D, Kim Y, Zhao F, Cha H. Understanding the coverage and scalability of place-centric crowdsensing. In: Proceedings of ACM International Joint Conference on Pervasive and Ubiquitous Computing. 2013, 3–12

[12] Kazemi L, Shahabi C. Geocrowd: enabling query answering with spatial crowdsourcing. In: Proceedings of International Conference on Advances in Geographic Information Systems. 2012, 189–198

[13] He S, Shin D H, Zhang J, Chen J, Chen J. Toward optimal allocation of location dependent tasks in crowdsensing. In: Proceedings of International Conference on Computer Communications. 2014, 745–753

[14] Liu Y, Guo B, Wang Y, Wu W, Yu Z, Zhang D. TaskMe: multi-task allocation in mobile crowd sensing. In: Proceedings of ACM International Joint Conference on Pervasive and Ubiquitous Computing. 2016, 403–414

[15] Guo B, Liu Y, Wu W, Yu Z, Han Q. ActiveCrowd: a framework for optimized multitask allocation in mobile crowdsensing systems. IEEE Transactions on Human-Machine Systems, 2017, 47(3): 392–403

[16] Feng Z, Zhu Y, Zhang Q, Ni L M, Vasilakos A V. TRAC: truthful auction for location-aware collaborative sensing in mobile crowdsourcing. In: Proceedings of International Conference on Computer Communications. 2014, 1231–1239

[17] Reddy. S, Estrin D, Srivastava M. Recruitment framework for participatory sensing data collections. In: Proceedings of International Conference on Pervasive Computing. 2010, 138–155

[18] Pournajaf L, Xiong L, Sunderam V. Dynamic data driven crowd sensing task assignment. Procedia Computer Science, 2014, 29(1): 1314–1323

[19] Zhang D, Xiong H, Wang L, Chen G. CrowdRecruiter: selecting participants for piggyback crowdsensing under probabilistic coverage constraint. In: Proceedings of ACM International Joint Conference on Pervasive and Ubiquitous Computing. 2014, 703–714

[20] Xiong H, Zhang D, Chen G, Wang L, Gauthier V, Barnes L E. iCrowd: near-optimal task allocation for piggyback crowdsensing. IEEE Transactions on Mobile Computing, 2016, 15(8): 2010–2022

[21] Hachem S, Pathak A, Issarny V. Probabilistic registration for largescale mobile participatory sensing. In: Proceedings of Pervasive Computing and Communications. 2013, 132–140

[22] Kandappu T, Jaiman N, Tandriansyah R, Misra A, Cheng S F, Chen C, Lau H C, Chander D, Dasgupta K. TASKer: behavioral insights via campus-based experimental mobile crowd-sourcing. In: Proceedings of ACM International Joint Conference on Pervasive and Ubiquitous Computing. 2016, 392–402

[23] Kandappu T, Misra A, Cheng S F, Jaiman N, Tandriansyah R, Chen C, Lau H C, Chander D, Dasgupta K. Campus-scale mobile crowdtasking: deployment and behavioral insights. In: Proceedings of the 19th ACM Conference on Computer-Supported Cooperative Work and Social Computing. 2016, 800–812

[24] Wang L, Yu Z, Guo B, Ku T, Yi F. Moving destination prediction using sparse dataset: a mobility gradient descent approach. ACM Transactions on Knowledge Discovery from Data, 2017, 11(3): 37

[25] Wang L, Hu K, Ku T, Yan X. Mining frequent trajectory pattern based on vague space partition. Knowledge-Based Systems, 2013, 50(3): 100–111

[26] McNett M, Voelker G M. Access and mobility of wireless PDA users. ACM Sigmobile Mobile Computing and Communications Review, 2005, 9(2): 40–55

[27] Rhee I, Shin M, Hong S, Lee K, Kim S J, Chong S. On the levywalk nature of human mobility. IEEE/ACM transactions on networking, 2011, 19(3): 630–643

[28] Srikant R, Agrawal R. Mining sequential patterns: generalizations and performance improvements. In: Proceedings of International Conference on Extending Database Technology. 1996, 1–17

[29] To H, Fan L, Tran L, Shahabi C. Real-time task assignment in hyperlocal spatial crowdsourcing under budget constraints. In: Proceedings of Pervasive Computing and Communications. 2016, 1–8

[30] Cheng P, Lian X, Chen Z, Fu R, Chen L, Han J, Zhao J. Reliable diversity-based spatial crowdsourcing by moving workers. Proceedings of the VLDB Endowment, 2015, 8(10): 1022–1033

[31] Wang J, Wang Y, Zhang D, Wang L, Xiong H, Helal A, He Y, Wang F. Fine-grained multitask allocation for participatory sensing with a shared budget. IEEE Internet of Things Journal, 2016, 3(6): 1395–1405

[32] Pournajaf L, Xiong L, Sunderam V, Goryczka S. Spatial task assignment for crowd sensing with cloaked locations. In: Proceedings of the 15th IEEE International Conference on Mobile Data Management. 2014, 73–82

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature