Abstract
In this paper, we propose a novel crowdsensing paradigm called semi-opportunistic sensing, which is aimed to achieve high task quality with low human involvement. In this paradigm, each mobile user can provide multiple path choices to reach her destination, which largely broadens the task assignment space. We formulate the task assignment problem in this paradigm of maximizing total task quality under incentive budget constraint and user travel time constraints. We prove this problem is NP-hard and then propose two efficient heuristic algorithms. First, we propose a Best Path/Task first algorithm (BPT) which always chooses current best path and current best task into the assignment list. Second, we propose an LP-relaxation based algorithm (LPR), which greedily assigns paths and tasks with the largest values in LP relaxation solution. We deduce the computational complexities of the proposed algorithms. We evaluate the performance of our algorithms using real-world traces. Simulation results show that our proposed crowdsensing paradigm can largely increase overall task quality compared with the opportunistic sensing paradigm where each user has only one fixed path. Simulation results also show that our proposed algorithms are efficient and their performance is close to the optimal solution.
This work was supported in part by the NSF of China under Grant Nos. 61531006, 61471339, 61872331, the Natural Sciences and Engineering Research Council (NSERC) of Canada (Discovery Grant RGPIN-2018-03792), and the InnovateNL SensorTECH Grant 5404-2061-101.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Du, D.Z., Ko, K.I., Hu, X.: Design and Analysis of Approximation Algorithms. Springer, New York (2012). https://doi.org/10.1007/978-1-4614-1701-9
Ganti, R.K., Ye, F., Lei, H.: Mobile crowdsensing: current state and future challenges. IEEE Commun. Mag. 49(11), 32–39 (2011)
Gao, R., et al.: Jigsaw: indoor floor plan reconstruction via mobile crowdsensing. In: Proceedings of ACM MobiCom 2014, pp. 249–260 (2014)
Gong, W., Zhang, B., Li, C.: Task assignment in mobile crowdsensing: present and future directions. IEEE Netw. https://doi.org/10.1109/MNET.2018.1700331
Gong, W., Zhang, B., Li, C.: Location-based online task scheduling in mobile crowdsensing. In: Proceedings of IEEE GLOBECOM 2017, Singapore, pp. 1–6, December 2017
Tsai, T.C., Chan, H.H.: NCCU trace: social-network-aware mobility trace. IEEE Commun. Mag. 53(10), 144–149 (2015)
Wang, X., Zhang, J., Tian, X., Gan, X., Guan, Y., Wang, X.: Crowdsensing-based consensus incident report for road traffic acquisition. IEEE Trans. Intell. Transport. Syst., October 2017. https://doi.org/10.1109/TITS.2017.2750169
Xu, C., Li, S., Zhang, Y., Miluzzo, E., Chen, Y.: Crowdsensing the speaker count in the wild: implications and applications. IEEE Commun. Mag. 52(10), 92–99 (2014)
Yang, F., Lu, J.L., Zhu, Y., Peng, J., Shu, W., Wu, M.Y.: Heterogeneous task allocation in participatory sensing. In: Proceedings of IEEE GLOBECOM 2015, pp. 1–6, December 2015
Zhang, B., Song, Z., Liu, C.H., Ma, J., Wang, W.: An event-driven qoi-aware participatory sensing framework with energy and budget constraints. ACM Trans. Intell. Syst. Technol. 6(3), 1–19 (2015)
Zhang, M., et al.: Quality-aware sensing coverage in budget-constrained mobile crowdsensing networks. IEEE Trans. Veh. Technol. 65(9), 7698–7707 (2016)
Zheng, Y., Liu, F., Hsieh, H.: U-Air: when urban air quality inference meets big data. In: Proceedings of ACM KDD 2013, pp. 1436–1444, August 2013
Zheng, Y., Xie, X., Ma, W.Y.: GeoLife: a collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33(2), 32–40 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Gong, W., Zhang, B., Li, C. (2019). Task Assignment for Semi-opportunistic Mobile Crowdsensing. In: Zheng, J., Xiang, W., Lorenz, P., Mao, S., Yan, F. (eds) Ad Hoc Networks. ADHOCNETS 2018. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 258. Springer, Cham. https://doi.org/10.1007/978-3-030-05888-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-05888-3_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05887-6
Online ISBN: 978-3-030-05888-3
eBook Packages: Computer ScienceComputer Science (R0)