Near-Optimal Allocation Algorithms for Location-Dependent Tasks in Crowdsensing

Crowdsensing offers an efficient way to meet the demand in large-scale sensing applications. In crowdsensing, optimal task allocation is challenging since sensing tasks with different requirements of quality of sensing are typically associated with specific locations, and mobile users have time cons...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on vehicular technology 2017-04, Vol.66 (4), p.3392-3405
Main Authors: He, Shibo, Shin, Dong-Hoon, Zhang, Junshan, Chen, Jiming
Format: Article
Language:English
Subjects:
Air quality
Algorithm design and analysis
Algorithms
Approximation
Approximation algorithms
Approximation ratio
Chemical sensors
Computer simulation
crowdsensing applications
Detection
location-dependent task allocation
Mathematical analysis
Mobile communication
Resource management
Sensors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Crowdsensing offers an efficient way to meet the demand in large-scale sensing applications. In crowdsensing, optimal task allocation is challenging since sensing tasks with different requirements of quality of sensing are typically associated with specific locations, and mobile users have time constraints. We show that the allocation problem is NP-hard. We then focus on approximation algorithms and devise an efficient local-ratio-based algorithm (LRBA). Our analysis shows that the approximation ratio of the aggregate rewards obtained by optimal allocation to those by LRBA is 5. This reveals that LRBA is efficient, since a lower (but not tight) bound on the approximation ratio is 4. We extend the results to the general scenario where mobile users are heterogeneous. A distributed version of LRBA, namely DLRBA, is designed, which can be iteratively executed at each mobile user without the need for the platform to collect all the information of mobile users. We prove that both centralized and distributed versions can output the same solution. Extensive simulation results are provided to demonstrate the advantages of our proposed algorithms.
ISSN:0018-9545
1939-9359
DOI:10.1109/TVT.2016.2592541