Rate Adaptation (RA) is a fundamental mechanism in 802.11 systems which allows the senders in the wireless networks to adapt the modulation and coding scheme as well as the MIMO transmission mode to the wireless channel conditions. For example, a sender may select a (mode, rate) pair on a per-packet basis from a finite set of MIMO transmission modes and transmission rates. The objective of RA mechanism is to maximize the throughput by identifying the (mode, rate) pair as fast as possible which maximizes the product of the rate and the transmission success probability. The challenges in terms of the design of RA algorithm arise from the facts that (i) the transmission success probabilities are not known in advance at the senders, and (ii) these probabilities may evolve over time. RA algorithms, therefore, should estimate the wireless channel conditions in order to learn and track the (mode, rate) pair providing the highest throughput. Basically, there are two approaches to estimate the
wireless channel conditions. The first one is the sampling-based approach, and the second one is the SNR-based approach. It is difficult to predict which approach will be generally adopted in the future, however, the samplingbased RA mechanisms are more popular in the current 802.11 systems.
In this thesis, we focus on the sampling-based RA approach. Most sampling-based RA algorithms are driven by heuristics so far. In constrast, we consider a sampling-based RA algorithm based on theory. More specifically, a sampling-based RA algorithm can be formulated as an online stochastic optimization problem, and solved by mapping the problem into a MAB (Multi-Armed Bandit) problem. The sampling-based RA algorithm driven by solving the MAB problem is asymptotically optimal for stationary radio environments. However, in practice, the wireless channels may be non-stationary due to mobility of stations in the wireless networks, hence the samplingbased RA algorithm based on theory cannot be used directly in practical 802.11 systems. In this thesis, we study how to overcome this inherent limit of the theory-based RA algorithm, and propose a practical version of the theory-based RA algorithm to be suitable for practical 802.11 systems, and we call the practical RA algorithm EW-G-ORS (ExponentiallyWeighted-Graphical-Optimal Rate Sampling). EW-G-ORS is theory-based, sampling-based, and standard-compiant, and we implement the RA algorithm on Qualcomm Atheros chipsets, and deployed them on our 13-node testbed. We evaluate the performance of EW-G-ORS comparing with existing RA solutions in various scenarios on our testbed, and demonstrate that EW-G-ORS is robust in practical 802.11 systems and
outperforms its competitors.
전송 속도 조절 기법은 무선 네트워크의 송신기가 코딩과 모듈레이션 방법, 그리고 다중 안테나 모드를 무선 채널 상태에 맞게 선택할 수 있도록 하는 802.11 시스템의 기본적인 메커니즘이다. 예를 들어, 송신기는 다중 안테나 모드들과 전송 속도들의 유한 집합으로부터 패킷 단위로 모드, 전송 속도 쌍을 선택할 수 있다. 전송 속도 조절 기법의 목적은 가능한 한 빠르게 전송 속도와 해당 전송 속도에서의 전송 성공 확률의 곱이 최대인 모드, 전송 속도 쌍을 확인하여 데이터 전송률을 최대화하는 것이다. 전송 속도 조절 기법을 설계하는 관점에서 어려운 점은 송신기가 전송 성공 확률을 미리 알 수 없다는 사실과 이러한 전송 성공 확률은 시간이 지나면서 변할 수 있다는 사실에 있다. 그러므로 전송 속도 조절 기법은 가장 높은 데이터 전송률을 제공하는 모드, 전송 속도 쌍을 확인하기 위해 계속해서 채널 상태를 추정해야 한다. 전송 속도 조절 기법이 채널을 추정하는 방법은 기본적으로 두 가지가 있다.
하나는 샘플링 기반 접근법이며, 다른 하나는 신호 대 잡음비 기반 접근법이다. 미래에 두 접근법 중 어느 접근법이 일반적으로 채택될 지를 예측하는 것은 어렵지만, 현재 802.11 시스템에서는 샘플링 기반의 전송 속도 조절 기법이 신호 대 잡음비 기반의 전송 속도 조절 기법보다 널리 사용되고 있다.
본 연구는 샘플링 기반의 전송 속도 조절 기법에 초점을 맞춘다. 지금까지 대부분의 샘플링 기반의 전송 속도 조절 기법은 경험적으로 설계되었다. 그와는 대조적으로, 본 연구는 이론에 근거하여 설계된 샘플링 기반의 전송 속도 조절 기법을 고려한다. 더 자세히는, 샘플링 기반의 전송 속도 조절 기법은 최적화 문제로 표현될 수 있으며, 그 문제는 멀티 암드 밴딧 문제로 대응시켜 해결할 수 있다. 멀티 암드 밴딧 문제를 통해 설계된 샘플링 기반의 전송 속도 조절 기법은 각 전송 속도에서의 패킷 전송 성공 확률이 변하지 않는 무선 채널 환경에서 점근적으로 최적이다. 하지만 실제 무선 채널 환경은 노드들의 움직임으로 인해 패킷 전송 성공 확률이 시간이 지나면서 변할 수 있다. 그러므로 이론에 근거하여 설계된 해당 샘플링 기반의 전송 속도 조절 기법은 실제 시스템에서 사용될 수 없다는 본질적인 한계를 갖는다. 본 논문에서 이러한 한계를 극복할 수 있는 방법에 대해 알아보고, 실제 시스템에서 사용할 수 있는 이론에 근거하여 설계된 전송 속도 조절 기법의 실질적 버전인 EW-G-ORS 알고리즘을 제안한다. 따라서 EW-G-ORS 알고리즘은 이론에 근거하고, 샘플링 기반이며, 표준을 준수하는 전송 속도 조절 기법이다. 본 연구에서 EW-G-ORS 알고리즘을 실제 칩셋 위에 구현하였으며, 해당 칩셋들은 13개의 노드들로 구성된 테스트베드 위에서 운용된다. 마지막으로 본 논문은 다양한 시나리오에서 EW-G-ORS 알고리즘과 기존의 다른 전송 속도 조절 기법들과의 성능 평가를 통해, EW-G-ORS 알고리즘이 실제 802.11 시스템에서 견고하게 동작하며, 기존의 다른 전송 속도 조절 기법보다 우수한 성능을 제공한다는 것을 보인다.