Minimum delay in class of throughput-optimal control policies on wireless networks

This paper considers the problem of average network delay minimization on multiclass, multihop, stochastic wireless networks subject to inter-channel interference and time-varying topology. We present a network control policy that solves this problem in the class of all policies whose control decision is a function only of current queue congestion and current channel states, including policies that have perfect knowledge of probabilities associated with future random events. As important features of our proposed control policy, it is throughput-optimal in the sense that it can stabilize queues for any stabilizable arrival rate, it is robust to varying network topology and arrival rates, and it is implemented without requiring any knowledge of statistics and probabilities in the system. The proposed control policy is analyzed via the theory of stochastic discrete-time Lyapunov drift with a significant difference that unlike prior works that merely push down an upper-bound on the drift, our design genuinely minimizes the drift itself.