Learning algorithms for scheduling in wireless networks with unknown channel statistics

Abstract We study the problem of learning channel statistics to efficiently schedule transmissions in wireless networks subject to interference constraints. We propose an algorithm that uses greedily-constructed schedules in order to learn the channels’ transmission rates, while simultaneously exploiting previous observations to obtain high throughput. Comparison to the offline solution shows our algorithm to have good performance that scales well with the number of links in the network. We then turn our attention to the stochastic setting where packets randomly arrive to the network and await transmission in queues at the nodes. We develop a queue-length-based scheduling policy that uses the channel learning algorithm as a component. We analyze our method in time-varying environments and show that it achieves the same stability region as that of a greedy policy with full channel knowledge.