Optimal Sleep-Wake Scheduling for Energy Harvesting Smart Mobile Devices

In this paper, we develop optimal sleep/wake scheduling algorithms for smart mobile devices that are powered by batteries and are capable of harvesting energy from the environment. Using a novel combination of the two-timescale Lyapunov optimization approach and weight perturbation, we first design the Optimal Sleep/wake scheduling Algorithm (OSA), which does not require any knowledge of the harvestable energy process. We prove that OSA is able to achieve any system performance that is within O(ϵ) of the optimal, and explicitly compute the required battery size, which is O(1/ϵ). We then extend our results to incorporate system information into algorithm design. Specifically, we develop the Information-aided OSA algorithm (IOSA) by introducing a novel drift augmenting idea in Lyapunov optimization. We show that IOSA is able to achieve the O(ϵ) close-to-optimal utility performance and ensures that the required traffic buffer and energy storage size are O(log (1/ϵ)2) with high probability.