Scheduling in Wireless Networks under Uncertainties: A Greedy Primal-Dual Approach

This paper proposes a dynamic primal-dual type scheduling algorithm in wireless networks, which achieves optimal throughput even with uncertain parameters. In wireless networks, such uncertain parameters are generated by complicated stochastic dynamics, such as random packet arrivals, channel fading, and node mobilities. The algorithm is a generalization of the well-known max-weight scheduling algorithm proposed by Tassiulas et al., where the only uncertain parameters are the packet arrival rates. Using the technique of fluid limits, sample path convergence result of the algorithm to an arbitrarily close to optimal solution is proved, under the assumption that the Strong Law of Large Numbers (SLLN) applies to the random processes which generate these uncertain parameters. The performance of the algorithm is further verified by simulation results. This method may potentially be applied to other cross-layer optimization problems, where dynamic algorithms for convex problems with uncertain parameters are needed.