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

Download Now Date Added: Jun 2010
Format: PDF

This paper proposes a dynamic primal-dual type algorithm to solve the optimal scheduling problem in wireless networks subject to uncertain parameters, which are generated by stochastic network processes 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 only queue length information is used for computing the schedules when the arrival rates are uncertain. Using the technique of fluid limits, sample path convergence 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 the uncertain parameters.