Task allocation for crowdsensing based on submodular optimisation. (28th January 2020)

• Record Type: Journal Article
• Authors: Yu, Zhiyong; Zhu, Weiping; Guo, Longkun; Guo, Wenzhong; Yu, Zhiwen
• Is Part Of: International journal of ad hoc and ubiquitous computing. Volume 33:Number 1(2020)
• Page Start: 48
• Page End: 61
• Publication Date: 2020-01-28
• Subjects: crowdsensing -- task allocation -- participant selection -- submodular optimisation -- SMO; Ubiquitous computing -- Periodicals; Embedded computer systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Wireless communication systems -- Periodicals; Computer architecture -- Periodicals; 004.2
• Languages: English
• ISSNs: 1743-8225

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.