Leveraging GPS-Less Sensing Scheduling for Green Mobile Crowd Sensing

In this paper, we consider leveraging GPS-less energy-efficient sensing scheduling for mobile crowd sensing. We present a probabilistic model for sensing coverage without accurate location information (provided by GPS), based on which we formally define the Energy-constrained Maximum Coverage Sensing Scheduling (E-MCSS) problem for maximum coverage and the Fair Maximum Coverage Sensing Scheduling (F-MCSS) problem for fairness. Assuming that moving trajectories of mobile users are known beforehand, we present a (1 - 1/e)-approximation algorithm and a 1/2-approximation algorithm to solve the E-MCSS and F-MCSS problems in polynomial time, respectively, which can serve as benchmarks for performance evaluation. Under realistic assumptions, we present a GPS-less energy-efficient protocol for sensing scheduling based on the proposed algorithms. We developed an Android-based mobile crowd sensing system, on which we implemented the proposed protocol. Simulation results and experimental results (from a field test) are presented to validate and justify effectiveness of the proposed algorithms and protocol.