Min-Max Planning of Time-Sensitive and Heterogeneous Tasks in Mobile Crowd Sensing
Authors: 
Hao Wang, Dong Zhao, Huadong Ma, Lige DingAuthors Info & Claims
Pages 1 - 7
Abstract
With the explosive growth of mobile devices such as smartphones, it is convenient for participants to perform mobile crowd sensing (MCS) tasks. It is a useful way to recruit participants to perform location-dependent tasks. We first propose Min-Max Task (MMT) planning problem in MCS systems, considering time-sensitivity and heterogeneity of sensing tasks. In other words, how to design a cooperation scheme, in which the participants spend as little time as possible. Then, to address MMT problem, we propose a Memetic based Bidirectional General Variable Neighborhood (MBGVN) algorithm, in which all tasks are separated into groups and traveling path is designed for each participant. Finally, extensive experiments are conducted to demonstrate the benefits of our scheme, outperforming other similar state-of-the-art algorithms.
References
[1]
Y. Liu, B. Guo, Y. Wang, W. Wu, Z. Yu and D. Zhang, “Taskme: multitask allocation in mobile crowd sensing,” in Proc. ACM UbiComp, 2016, pp. 403–414.
[2]
B. Guo, H. Chen, Z. Yu, X. Xie, H. Shenlong, and D. Zhang, “Fliermeet: A mobile crowdsensing system for cross-space public information reposting, tagging, and sharing,” IEEE Transactions on Mobile Computing, vol. 14, no. 10, pp. 2020–2033, 2015.
[3]
D. Zhao, X.Y. Li and H.D. Ma, “How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint,” in Proc. IEEE Infocom, 2014, pp. 1213–1221.
[4]
H.-D. Ma, D. Zhao, and P. Yuan, “Opportunities in mobile crowd sensing,” IEEE Communications Magazine, vol. 52, no. 8, pp. 29–35, 2014.
[5]
B. Guo, L. Yang, W. Wu, Z. Yu, and H. Qi, “Activecrowd: a framework for optimized multitask allocation in mobile crowdsensing systems,” IEEE Transactions on Human-Machine Systems, vol. 47, no. 3, pp. 392–403, 2017.
[6]
F. Tian, B. Liu, X. Sun, X. Zhang, G. Cao, and L. Gui, “Movement-based incentive for crowdsourcing,” IEEE Transactions on Vehicular Technology, vol. 66, no. 8, pp. 7223–7233, 2017.
[7]
Gigwalk, “[online] available: http://www.gigwalk.com/”.
[8]
Jana, “[online] available: https://www.jana.com/”.
[9]
Weichaishi, “[online] available: http://www.weichaishi.com/”.
[10]
D. Zhao, H. Wang, H. Ma, H. Xu, L. Liu, and P. Zhang, “Crowdolr: towards object location recognition with crowdsourced fingerprints using smartphones,” IEEE Transactions on Human-Machine Systems, vol. 47, no. 6, pp. 1005–1016, 2017.
[11]
H. Wang, D. Zhao, H.D. Ma, H. Xu and X. Hou, “Crowdsourcing based mobile location recognition with richer fingerprints from smartphone sensors,” in Proc. IEEE ICPADS, 2015, pp. 156–163.
[12]
B. Soylu, “A general variable neighborhood search heuristic for multiple traveling salesmen problem,” Computers & Industrial Engineering, vol. 90, pp. 390–401, 2015.
[13]
Y. W. and Y. Chen and Y. Lin, “Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem,” Computers & Industrial Engineering, vol. 106, pp. 105–122, 2017;.
[14]
H. Wang, D. Zhao, H.D. Ma, and H. Xu, “Ssfs: A space-saliency fingerprint selection framework for crowdsourcing based mobile location recognition,” in Proc. Pacific-Rim Conference on Multimedia, 2016, pp. 650–659.
[15]
J. Xie and J. Dong, “Heuristic genetic algorithms for general capacitated lot-sizing problems,” Computers and Mathematics with Application vol. 44, no. 1, pp. 263–276, 2002.
[16]
J. Hoffman, M. Wilkes, F. Day, D. Bell, and J. Higa, “The roulette wheel: An aid to informed decision making,” PLoS medicine, vol. 3, no. 6, pp. 743–748, 2006.
[17]
S. He, D. Shin, J. Zhang, and J. Chen, “Near-optimal allocation algorithms for location-dependent tasks in crowdsensing,” IEEE Transactions on Vehicular Technology, vol. 66, no. 4, pp. 33921–3405, 2017.
[18]
S. He, D.-H. Shin, J. Zhang, and J. Chen, “Toward optimal allocation of location dependent tasks in crowdsensing,” in Proc. IEEE INFOCOM, 2014, pp. 745–753.
[19]
G. Cardone, L. Foschini, P. Bellavista, A. Corradi, C. Borcea, M. Ta-lasila, and R. Curtmola, “Fostering participaction in smart cities: A geo-social crowdsensing platform,” IEEE Communications Magazine, vol. 51, no. 6, pp. 112–119, 2013.
[20]
V. Coric and M. Gruteser, “Crowdsensing maps of on-street parking spaces,” in Proc. IEEE ICDCS, 2013, pp. 115–122.
[21]
D. Zhang, H. Xiong, L. Wang and G. Chen, “Crowdrecruiter: selecting participants for piggyback crowdsensing under probabilistic coverage constraint,” in Proc. ACM UbiComp, 2014, pp. 703–714.
[22]
Y. Chon, N. Lane, F. Li, H. Cha, and F. Zhao, “Automatically characterizing places with opportunistic crowdsensing using smartphones,” in Proc. ACM UbiComp, 2012, pp. 418–490.
[23]
M. Demirbas, M. Bayir, C. Akcora, and Y. Yilmaz, “Crowdsourced sensing and collaboration using twitter,” in Proc. ACM WoWMoM, 2010, pp. 1–9.
[24]
M. Xiao, J. Wu, L. Huang, Y. Wang and C. Liu, “Multi-task assignment for crowdsensing in mobile social networks,” in Proc. IEEE INFO-COM, 2015, pp. 2227–2235.
Index Terms
- Min-Max Planning of Time-Sensitive and Heterogeneous Tasks in Mobile Crowd Sensing
Index terms have been assigned to the content through auto-classification.
Recommendations
Dynamic Participant Recruitment of Mobile Crowd Sensing for Heterogeneous Sensing Tasks
MASS '15: Proceedings of the 2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)With the rapid increasing of smart mobile devices and the advances of sensing technologies, mobile crowd sensing (MCS) becomes a new popular sensing paradigm, which enables a variety of large-scale sensing applications. One of the key challenges of ...
Multitask Allocation to Heterogeneous Participants in Mobile Crowd Sensing
Task allocation is a key problem in Mobile Crowd Sensing (MCS). Prior works have mainly assumed that participants can complete tasks once they arrive at the location of tasks. However, this assumption may lead to poor reliability in sensing data ...
Multi-task versus consecutive task allocation with tasks clustering for Mobile Crowd Sensing Systems
AbstractIn this paper, we address the problem of multi-task allocation for dense mobile crowd sensing systems (MCS). The multi-task allocation problem is well-known to be time-consuming as the number of tasks or workers increases. However, the problem can ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2018
6265 pages
Copyright © 2018.
Publisher
IEEE Press
Publication History
Published: 09 December 2018
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in