research-article

Social-Aware Task Allocation in Mobile Crowd Sensing

Authors:

Zhiyong Yu Academic Editor:

Kim-Kwang Raymond ChooAuthors Info & Claims

Wireless Communications and Mobile Computing, Volume 2020

https://doi.org/10.1155/2020/8822251

Published: 01 January 2020 Publication History

Abstract

Task allocation is a significant issue in crowd sensing, which trades off the data quality and sensing cost. Existing task allocation works are based on the assumption that there is plenty of users available in the candidate pool. However, for some specific applications, there may be only a few candidate users, resulting in the poor completion of tasks. To tackle this problem, in this paper, we investigate the task allocation problem with the assistance of social networks. We select a subset of users; if a user can not complete the task, he can propagate the task information to his friends. The object of this problem is to maximize the expected number of completed tasks. We prove that the task allocation problem is an NP-hard and submodular problem and then propose a native greedy selection (NGS) algorithm, which selects the user with maximum margin gain in each round. To improve the efficiency of the NGS algorithm, we further propose a fast greedy selection algorithm (FGS), which selects the user who can actually complete the maximum number of tasks. Experimental results show that although FGS gets slightly worse results in terms of the expected number of completed tasks, it can greatly reduce the running time of seed selection.

References

[1]

B. Guo, Z. Wang, Z. Yu, Y. Wang, N. Y. Yen, R. Huang, and X. Zhou, “Mobile crowd sensing and computing: the the review of an emerging human-powered sensing paradigm,” ACM Computing Surveys, vol. 48, no. 1, pp. 1–31, 2015.

Digital Library

[2]

W. Guo, W. Zhu, Z. Yu, J. Wang, and B. Guo, “A survey of task allocation: contrastive perspectives from wireless sensor networks and mobile crowdsensing,” IEEE Access, vol. 7, pp. 78406–78420, 2019.

[3]

J. Wang, L. Wang, Y. Wang, D. Zhang, and L. Kong, “Task allocation in mobile crowd sensing: state-of-the-art and future opportunities,” IEEE Internet of Things Journal, vol. 5, no. 5, pp. 3747–3757, 2018.

[4]

J. Chen and J. Yang, “Maximizing coverage quality with budget constrained in mobile crowd-sensing network for environmental monitoring applications,” Sensors, vol. 19, no. 10, article 2399, 2019.

[5]

S. Morishita, S. Maenaka, D. Nagata, M. Tamai, K. Yasumoto, T. Fukukura, and K. Sato, “Sakurasensor: quasi-real time cherry-lined roads detection through participatory video sensing by cars,” in UbiComp '15: Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, pp. 695–705, New York, NY, USA, September 2015.

Digital Library

[6]

T. Ludwig, C. Reuter, and V. Pipek, “What you see is what I need: mobile reporting practices in emergencies,” ECSCW 2013: Proceedings of the 13th European Conference on Computer Supported Cooperative Work, 21-25 September 2013, Paphos, Cyprus, O. Bertelsen, L. Ciolfi, M. Grasso, and G. Papadopoulos, Eds., pp. 181–206, Springer, London, 2013.

[7]

D. Zhang, L. Wang, H. Xiong, and B. Guo, “4w1h in mobile crowd sensing,” IEEE Communications Magazine, vol. 52, no. 8, pp. 42–48, 2014.

[8]

B. Guo, Y. Liu, L. Wang, V. O. K. Li, J. C. K. Lam, and Z. Yu, “Task allocation in spatial crowdsourcing: current state and future directions,” IEEE Internet of Things Journal, vol. 5, no. 3, pp. 1749–1764, 2018.

[9]

W. Guo, J. Li, G. Chen, Y. Niu, and C. Chen, “A pso-optimized real-time fault-tolerant task allocation algorithm in wireless sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 12, pp. 3236–3249, 2014.

Digital Library

[10]

Y. Liu, B. Guo, Y. Wang, W. Wu, Z. Yu, and D. Zhang, “Taskme: multi-task allocation in mobile crowd sensing,” in UbiComp '16: Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, pp. 403–414, New York, NY, USA, September 2016.

Digital Library

[11]

L. Wang, Z. Yu, Q. Han, B. Guo, and H. Xiong, “Multi-objective optimization based allocation of heterogeneous spatial crowdsourcing tasks,” IEEE Transactions on Mobile Computing, vol. 17, no. 7, pp. 1637–1650, 2018.

[12]

E. Wang, Y. Yang, J. Wu, K. Lou, D. Luan, and H. Wang, “User recruitment system for efficient photo collection in mobile crowdsensing,” IEEE Transactions on Human-Machine Systems, vol. 50, no. 1, pp. 1–12, 2019.

[13]

J. Wang, F. Wang, Y. Wang, D. Zhang, L. Wang, and Z. Qiu, “Social-network-assisted worker recruitment in mobile crowd sensing,” IEEE Transactions on Mobile Computing, vol. 18, no. 7, pp. 1661–1673, 2018.

[14]

A.-q. Lu and J.-h. Zhu, “Worker recruitment with cost and time constraints in mobile crowd sensing,” Future Generation Computer Systems, vol. 112, pp. 819–831, 2020.

[15]

S. Reddy, K. Shilton, J. Burke, D. Estrin, M. Hansen, and M. Srivastava, “Using context annotated mobility profiles to recruit data collectors in participatory sensing,” in Location and Context Awareness. LoCA 2009. Lecture Notes in Computer Science, vol 5561, T. Choudhury, A. Quigley, T. Strang, and K. Suginuma, Eds., pp. 52–69, Springer, Berlin, Heidelberg, 2009.

Digital Library

[16]

S. Reddy, D. Estrin, and M. Srivastava, “Recruitment framework for participatory sensing data collections,” in Pervasive Computing. Pervasive 2010. Lecture Notes in Computer Science, vol 6030, P. Floréen, A. Krüger, and M. Spasojevic, Eds., pp. 138–155, Springer, Berlin, Heidelberg, 2010.

Digital Library

[17]

M. Zhang, P. Yang, C. Tian, S. Tang, X. Gao, B. Wang, and F. Xiao, “Quality-aware sensing coverage in budget-constrained mobile crowdsensing networks,” IEEE Transactions on Vehicular Technology, vol. 65, no. 9, pp. 7698–7707, 2015.

[18]

X. Wang, W. Wu, and D. Qi, “Mobility-aware participant recruitment for vehicle-based mobile crowdsensing,” IEEE Transactions on Vehicular Technology, vol. 67, no. 5, pp. 4415–4426, 2017.

[19]

Z. Yu, J. Zhou, W. Guo, L. Guo, and Z. Yu, “Participant selection for t-sweep k-coverage crowd sensing tasks,” World Wide Web, vol. 21, no. 3, pp. 741–758, 2018.

Digital Library

[20]

H. Li, T. Li, and Y. Wang, “Dynamic participant recruitment of mobile crowd sensing for heterogeneous sensing tasks,” in 2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems, pp. 136–144, Dallas, TX, USA, October 2015.

Digital Library

[21]

W. Zhu, W. Guo, Z. Yu, and H. Xiong, “Multi-task allocation to heterogeneous participants in mobile crowd sensing,” Wireless Communications and Mobile Computing, vol. 2018, 10 pages, 2018.

Digital Library

[22]

J. Jiang, B. An, Y. Jiang, C. Zhang, Z. Bu, and J. Cao, “Group-oriented task allocation for crowdsourcing in social networks,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, pp. 1–16, 2019.

[23]

Z. Wang, J. Zhao, J. Hu, T. Zhu, Q. Wang, J. Ren, and C. Li, “Towards personalized task-oriented worker recruitment in mobile crowdsensing,” IEEE Transactions on Mobile Computing, 2020.

[24]

J. Wang, Y. Wang, D. Zhang, F. Wang, H. Xiong, C. Chen, Q. Lv, and Z. Qiu, “Multi-task allocation in mobile crowd sensing with individual task quality assurance,” IEEE Transactions on Mobile Computing, vol. 17, no. 9, pp. 2101–2113, 2018.

Digital Library

[25]

H. Wang, D. Zhao, H. Ma, and L. Ding, “Min-max planning of time-sensitive and heterogeneous tasks in mobile crowd sensing,” in 2018 IEEE Global Communications Conference (GLOBECOM), pp. 1–7, Abu Dhabi, United Arab Emirates, December 2018.

Digital Library

[26]

W. Ni, P. Cheng, L. Chen, and X. Lin, “Task allocation in dependency-aware spatial crowdsourcing,” in 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 985–996, Dallas, TX, USA, April 2020.

[27]

S. Song, Z. Liu, Z. Li, T. Xing, and D. Fang, “Coverage-oriented task assignment for mobile crowdsensing,” IEEE Internet of Things Journal, vol. 7, no. 8, pp. 7407–7418, 2020.

[28]

Z. Peng, X. Gui, J. An, R. Gui, and Y. Ji, “Tdsrc: A task-distributing system of crowdsourcing based on social relation cognition,” Mobile Information Systems, vol. 2019, 12 pages, 2019.

[29]

Y. Yang, Y. Xu, E. Wang, K. Lou, and D. Luan, “Exploring influence maximization in online and offline double-layer propagation scheme,” Information Sciences, vol. 450, pp. 182–199, 2018.

Digital Library

[30]

E. Cho, S. A. Myers, and J. Leskovec, “Friendship and mobility: user movement in location-based social networks,” in KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1082–1090, New York, NY, USA, August 2011.

Digital Library

Cited By

Tu VHuynh VYang HKim SNawaz SNandakumar KZaheer MEl Saddik AMei TCucchiara RBertini MTobon Vallejo DAtrey PHossain M(2023)DCTM: Dilated Convolutional Transformer Model for Multimodal Engagement Estimation in ConversationProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3612857(9521-9525)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3581783.3612857
Zheng CDing WShen SChen P(2023)MAF: Multimodal Auto Attention Fusion for Video ClassificationAdvances and Trends in Artificial Intelligence. Theory and Applications10.1007/978-3-031-36819-6_22(253-264)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36819-6_22

Index Terms

Social-Aware Task Allocation in Mobile Crowd Sensing
1. Networks

Index terms have been assigned to the content through auto-classification.

Recommendations

Multi-task versus consecutive task allocation with tasks clustering for Mobile Crowd Sensing Systems
Abstract
In 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 ...
Multi-Task Allocation in Mobile Crowd Sensing with Individual Task Quality Assurance
Task allocation is a fundamental research issue in mobile crowd sensing. While earlier research focused mainly on single tasks, recent studies have started to investigate multi-task allocation, which considers the interdependency among multiple tasks. A ...
A Real-Time Recommendation Algorithm for Task Allocation in Mobile Crowd Sensing
Wireless Algorithms, Systems, and Applications
Abstract
In mobile crowd sensing, whether or not the results of task allocation are consistent with the user’s preferences will greatly affect the efficiency of task execution. Hence, recent studies have begun to focus on the user’s preference and, based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Wireless Communications & Mobile Computing

Wireless Communications & Mobile Computing Volume 2020, Issue

2020

4630 pages

ISSN:1530-8669

Issue’s Table of Contents

Copyright © 2020 Weiping Zhu et al.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Publisher

John Wiley and Sons Ltd.

United Kingdom

Publication History

Published: 01 January 2020

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tu VHuynh VYang HKim SNawaz SNandakumar KZaheer MEl Saddik AMei TCucchiara RBertini MTobon Vallejo DAtrey PHossain M(2023)DCTM: Dilated Convolutional Transformer Model for Multimodal Engagement Estimation in ConversationProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3612857(9521-9525)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3581783.3612857
Zheng CDing WShen SChen P(2023)MAF: Multimodal Auto Attention Fusion for Video ClassificationAdvances and Trends in Artificial Intelligence. Theory and Applications10.1007/978-3-031-36819-6_22(253-264)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36819-6_22

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.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents