Fair Energy-Efficient Sensing Task Allocation in Participatory Sensing with Smartphones
Open Access
- 24 February 2017
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 60 (6) , 850-865
Abstract
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 efficiency, which are particularly challenging given high combinatorial complexity, trade-off between energy efficiency and fairness, and dynamic and unpredictable task arrivals. 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 online allocation. For the offline allocation model, we design an efficient approximation algorithm with the approximation ratio of , where m is the number of member smartphones in the system. For the online allocation model, we propose two algorithms: greedy algorithm and Robin-Hood algorithm, which achieve the competitive ratio of at most m and , respectively. The results demonstrate that the approximation algorithm reduces over 81% total sensing time, the online greedy algorithm and Robin-Hood algorithms reduce the total sensing time 73% and 37.5%, respectively. The offline approximation algorithm and online greedy algorithm achieve much better min–max fairness compared to other algorithms.
Keywords
This publication has 5 references indexed in Scilit:
- We Can Hear You with Wi-Fi!IEEE Transactions on Mobile Computing, 2016
- SmartScanner: Know More in Walls with Your Smartphone!IEEE Transactions on Mobile Computing, 2015
- Adaptive Task Scheduling in Service Oriented Crowd Using SLURM2013
- A note on the Hamiltonian Circuit Problem on directed path graphsInformation Processing Letters, 1989
- `` Strong '' NP-Completeness ResultsJournal of the ACM, 1978