Towards energy-efficient task scheduling on smartphones in mobile crowd sensing systems

In a mobile crowd sensing system, a smartphone undertakes many different sensing tasks that demand data from various sensors. In this paper, we consider the problem of scheduling different sensing tasks assigned to a smartphone with the objective of minimizing sensing energy consumption while ensuring Quality of SenSing (QoSS). First, we consider a simple case in which each sensing task only requests data from a single sensor. We formally define the corresponding problem as the Minimum Energy Single-sensor task Scheduling (MESS) problem and present a polynomial-time optimal algorithm to solve it. Furthermore, we address a more general case in which some sensing tasks request multiple sensors to report their measurements simultaneously. We present an Integer Linear Programming (ILP) formulation as well as two effective polynomial-time heuristic algorithms, for the corresponding Minimum Energy Multi-sensor task Scheduling (MEMS) problem. Extensive simulation results show that the proposed algorithms achieve significant energy savings, compared to a widely-used baseline approach; moreover, the proposed heuristic algorithms produce close-to-optimal solutions.