In 802.11 systems, Rate Adaptation (RA) is a fundamental mechanism allowing
transmitters to adapt the coding and modulation scheme as well as the MIMO
transmission mode to the radio channel conditions, and in turn, to learn and
track the (mode, rate) pair providing the highest throughput. So far, the
design of RA mechanisms has been mainly driven by heuristics. In contrast, in
this paper, we rigorously formulate such design as an online stochastic
optimisation problem. We solve this problem and present ORS (Optimal Rate
Sampling), a family of (mode, rate) pair adaptation algorithms that provably
learn as fast as it is possible the best pair for transmission. We study the
performance of ORS algorithms in both stationary radio environments where the
successful packet transmission probabilities at the various (mode, rate) pairs
do not vary over time, and in non-stationary environments where these
probabilities evolve. We show that under ORS algorithms, the throughput loss
due to the need to explore sub-optimal (mode, rate) pairs does not depend on
the number of available pairs, which is a crucial advantage as evolving 802.11
standards offer an increasingly large number of (mode, rate) pairs. We
illustrate the efficiency of ORS algorithms (compared to the state-of-the-art
algorithms) using simulations and traces extracted from 802.11 test-beds.

本文提出了 ORS 算法，它采用在线随机优化来解决 802.11 系统中速率自适应机制的设计问题，可以快速学习出提供最高吞吐量的 (模式、速率) 对，且在探索亚最优 (模式、速率) 对时，吞吐量损失不依赖于可用对的数量。