|
|
|
Mobile crowd sensing task optimal allocation: a mobility pattern matching perspective |
Liang WANG1,2( ), Zhiwen YU1, Bi GUO1, Fei YI1, Fei XIONG3 |
1. School of Computer Science, Northwestern Polytechnical University, Xi’an 710072, China
2. School of Electrical and Control Engineering, Xi’an University of Science and Technology, Xi’an 710054, China
3. School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China |
|
|
|
|
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
|
|
Corresponding Author(s):
Liang WANG
|
|
Just Accepted Date: 22 August 2017
Online First Date: 06 March 2018
Issue Date: 23 March 2018
|
|
| 1 |
Ganti R K, Ye F, Lei H. Mobile crowdsensing: current state and future challenges. IEEE Communications Magazine, 2011, 49(11): 32–39
https://doi.org/10.1109/MCOM.2011.6069707
|
| 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
https://doi.org/10.1145/2794400
|
| 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
https://doi.org/10.1109/THMS.2015.2446953
|
| 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
https://doi.org/10.1109/TMC.2014.2385097
|
| 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
https://doi.org/10.1007/s11704-016-5553-z
|
| 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
https://doi.org/10.1016/j.cnsns.2016.09.015
|
| 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
https://doi.org/10.1109/ICDM.2016.0061
|
| 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
https://doi.org/10.1145/3097983.3097985
|
| 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
https://doi.org/10.1145/2675133.2675278
|
| 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
https://doi.org/10.1145/2493432.2493498
|
| 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
https://doi.org/10.1145/2424321.2424346
|
| 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
https://doi.org/10.1109/INFOCOM.2014.6848001
|
| 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
https://doi.org/10.1145/2971648.2971709
|
| 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
https://doi.org/10.1109/THMS.2016.2599489
|
| 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
https://doi.org/10.1109/INFOCOM.2014.6848055
|
| 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
https://doi.org/10.1007/978-3-642-12654-3_9
|
| 18 |
Pournajaf L, Xiong L, Sunderam V. Dynamic data driven crowd sensing task assignment. Procedia Computer Science, 2014, 29(1): 1314–1323
https://doi.org/10.1016/j.procs.2014.05.118
|
| 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
https://doi.org/10.1145/2632048.2632059
|
| 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
https://doi.org/10.1109/TMC.2015.2483505
|
| 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
https://doi.org/10.1145/2971648.2971690
|
| 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
https://doi.org/10.1145/3051128
|
| 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
https://doi.org/10.1016/j.knosys.2013.06.002
|
| 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
https://doi.org/10.1145/1072989.1072995
|
| 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
https://doi.org/10.1109/TNET.2011.2120618
|
| 28 |
Srikant R, Agrawal R. Mining sequential patterns: generalizations and performance improvements. In: Proceedings of International Conference on Extending Database Technology. 1996, 1–17
https://doi.org/10.1007/BFb0014140
|
| 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
https://doi.org/10.1109/PERCOM.2016.7456507
|
| 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
https://doi.org/10.14778/2794367.2794372
|
| 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
https://doi.org/10.1109/JIOT.2016.2608141
|
| 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
https://doi.org/10.1109/MDM.2014.15
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
