Fair Energy-efficent Sensing Task Allocation In Participatory Sensing With Smartphones

With the proliferation of smartphones, participatory sensing using smartphones provides unprecedented opportunities for collecting enormous sensing data. There are two crucial requirements in participatory sensing, fair task allocation and energy effi-ciency, which are particularly challenging given high combinatorial complexity, trade-off between energy efficiency and fairness, and dynamic and unpredictable task arrival-s. In this paper, we present a novel fair energy-efficient allocation framework whose objective is characterized by min-max aggregate sensing time. We rigorously prove that optimizing the min-max aggregate sensing time is NP hard even when the tasks are assumed as a priori. We consider two allocation models:offline allocation and on-line allocation. For the offline allocation model, we design an efficient approximation algorithm with the approximation ratio of 2 -1/m, where m is the number of member smartphones in the system. For the online allocation model, we propose two online al-gorithms:Greedy algorithm and Robin-Hood algorithm, which achieve a competitive ratio of at most m and (?)+1, respectively. The results demonstrate our algorithms can largely reduce the total aggregate sensing time compared with baseline algorithm, while keeping good fairness.