Utility-maximizing data collection in crowd sensing: An optimal scheduling approach

Sensing data collection is of great significance in mobile crowd sensing. We consider the problem of online maximization of data utility of the sensing data collected from smartphone users under a time average budget constraint. There are several major challenges, including random and unknown phone contexts, budget constraint and existence of data redundancy. Little work has studied this crucial problem. In this paper we formulate it as an online scheduling problem which determines sensing decisions for smartphones that are distributed over different regions of interest We first propose a centralized online scheduling algorithm based on stochastic optimal control. To address the poor scalability issue of the centralized algorithm, we further propose a distributed online scheduling algorithm based on distributed correlated scheduling. It does not require any priori knowledge of future smartphone contexts, and hence sensing decisions can locally be made by individual smartphones. Rigorous theoretical analysis show that our algorithms can achieve a time average data utility that is within O{1/V) of the theoretical optimum. Extensive simulations demonstrate that our algorithms produce high time average data utility.