Title: Task allocation for crowdsensing based on submodular optimisation

Authors: Zhiyong Yu; Weiping Zhu; Longkun Guo; Wenzhong Guo; Zhiwen Yu

Addresses: College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China; Key Laboratory of Spatial Data Mining and Information Sharing, Ministry of Education, Fuzhou 350003, China; Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116, China ' College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China ' College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China ' College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China; Key Laboratory of Spatial Data Mining and Information Sharing, Ministry of Education, Fuzhou 350003, China; Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116, China ' School of Computer Science, Northwestern Polytechnical University, Xi'an 710129, China

Abstract: Crowdsensing is becoming a hot topic because of its advantages in the field of smart city. In crowdsensing, task allocation is a primary issue which determines the data quality and the cost of sensing tasks. In this paper, on the basis of the sweep covering theory, a novel coverage metric called 't-sweep k-coverage' is defined, and two symmetric problems are formulated: minimise participant set under fixed coverage rate constraint (MinP) and maximise coverage rate under participant set constraint (MaxC). Then based on their submodular property, two task allocation methods are proposed, namely double greedy (dGreedy) and submodular optimisation (SMO). The two methods are compared with the baseline method linear programming (LP) in experiments. The results show that, regardless of the size of the problems, both two methods can obtain the appropriate participant set, and overcome the shortcomings of linear programming.

Keywords: crowdsensing; task allocation; participant selection; submodular optimisation; SMO.

DOI: 10.1504/IJAHUC.2020.104716

International Journal of Ad Hoc and Ubiquitous Computing, 2020 Vol.33 No.1, pp.48 - 61

Received: 07 Nov 2018
Accepted: 04 Mar 2019
Published online: 29 Jan 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article