Scheduling in Wireless Networks under Uncertainties

We consider a general scheduling problem in wireless networks under uncertain arrival and channel state statistics. The objective is to minimize a linear cost function, which can be used to model wireless communication constraints, such as power consumption. We assume that the arrival processes and the network states are random, and with unknown distributions. In each time slot, the schedule can only be computed based on past history. We propose a conditional-gradient type scheduling algorithm and a priority queuing mechanism with auxiliary dummy queues. We show that these can achieve an objective function value which is arbitrarily close to the optimal, while guaranteeing network stability. The performance of the algorithm is further confirmed by simulation results.