Minimum energy scheduling in multi-hop wireless networks with retransmissions

MaxWeight algorithm, a.k.a., back-pressure algorithm [1] - [4], has received much attention as a viable solution for dynamic link scheduling in multi-hop wireless networks. The basic principle of the MaxWeight algorithm is to select a set of interference-free links with the maximum overall link weights in the network, where the link weight is determined by the queue difference between the transmitter and the receiver. While the throughput-optimality of the MaxWeight algorithm is well understood in the literature, the energy consumption induced by the MaxWeight algorithm is less studied, which is of great interest in energy-constrained wireless networks such as wireless sensor networks. In this paper, we propose a minimum energy scheduling (MES) algorithm for multi-hop wireless networks with stochastic traffic arrivals and time-varying channel conditions. We show that our algorithm is energy optimal in the sense that the proposed MES algorithm can achieve an energy consumption which is arbitrarily close to the global minimum solution. Moreover, the energy efficiency of the MES algorithm is achieved without losing the throughput-optimality. In other words, the proposed MES algorithm is still throughput optimal whereas the average consumed energy in the network is significantly reduced, as compared to the traditional MaxWeight algorithm. The theoretical results are substantiated via simulations. © 2006 IEEE.