Selecting Optimal Mobile Users for Long-term Environmental Monitoring by Crowdsourcing

Urban environmental monitoring related to such issues as air pollution and noise helps people understand their living environments and promotes urban construction. It is more and more important nowadays. By crowdsourcing, we can get mobile users at a low cost to collect measurement at different locations. This paper studies how to select optimal mobile users to construct an accurate monitoring map under a limited budget. We extend the noise Gaussian Process model to construct the data utility model. Because the monitoring map is updated in each time slot, we try to maximize the time-averaged data utility under the time-averaged budget constraint. This problem is particularly challenging given the unknown future information and the difficulty of solving the one-slot problem: maximizing a non-monotone submodular objective under the budget constraint. To address these challenges, we first make use of Lyapunov optimization to decompose the long-term optimization problem into a series of real-time problems which do not require a priori knowledge about the future information. We then propose a time-efficient online algorithm to solve the NP-hard one-slot problem. As long as the algorithm for the one-slot problem has a competitive ratio e, the time-averaged data utility of our online algorithm has a small gap compared with e times the optimal one. Evaluations based on the real air pollution data in Beijing [2] and real human trajectory data [1] show the efficiency of our approach.