Online Scheduling for Energy Efficiency in Real-Time Wireless Networks

Abstract—This paper studies the problem of using min-imum power to provide satisfactory performance for real-time applications over unreliable and fading wireless chan-nels. We demonstrate that this problem can be formulated as a linear programming problem. However, this formu-lation involves exponentially many constraints, and many parameters are either unavailable or difficult to compute, which makes it infeasible to employ standard techniques to solve the linear programming problem. Instead, we propose a simple online scheduling algorithm for this problem. This algorithm has very low complexity and makes scheduling decisions solely based on system history and current channel conditions. It is also compatible with any power control algorithms. We prove that our algorithm provides satisfactory performance to all real-time applications, and the total power consumption can be made arbitrarily close to the theoretical lower bound. Sim-ulation results show that our scheduling algorithm indeed achieves small power consumption with fast convergence. I