For many years, the IEEE 802.11 distributed coordination function (DCF) has been widely used as a dominant Medium Access Control (MAC) protocol in wireless networks and a large number of works have been done for analyzing and improving its performance. Among various performance metrics for the IEEE 802.11 DCF, throughput, fairness, and delay are most widely considered. Through various research works for the IEEE 802.11 DCF, it has been known that the uniform backoff counter selection and doubling the backoff window size, which are adopted in the IEEE 802.11 DCF, need to be modified for optimal throughput, high short-term fairness, and low delay. However, due to complexity in its analysis, there has been few theoretical works for improving performances of the IEEE 802.11 DCF in the open literature.
A well-designed MAC protocol should provide high throughput, fair allocation, and simplicity. Also, the recent proliferation of real-time applications such as voice over Internet on wireless networks has made delay become an important performance metric. In this dissertation, to meet the criteria for a well-designed MAC protocol, we consider a simple MAC protocol, called the renewal access protocol (RAP), as a substitute of the IEEE 802.11 DCF. The RAP adopts all of the legacy 802.11 standard but the backoff stage feature. Each terminal selects its backoff counter value from a fixed sized window according to a priori given selection distribution in the RAP, regardless of the packet transmission result. Thus, the probabilistic properties of the selection distribution affect the performances of the RAP. To meet three objectives in the design of the RAP - optimal throughput, high short-term fairness, and low delay, we develop a mathematical model of the RAP and rigorously analyze the performances of the RAP.
In Chapter 2, we analyze the throughput of the RAP. We first develop an analytic model of the RAP and show that the RAP outperforms the IEEE 802.11 DCF when both are optimized in throughput. We also prove that the throughput performance of the RAP depends only on the expectation of the selection distribution, provided that the number of terminals is fixed, which is in accordance with a well-known result. We also discuss how to implement the RAP in practice. Our analytic results are verified through simulation.
In Chapter 3, with the help of renewal and reliability theories we analyze the short-term fairness of the RAP. We show that, if the RAP has a selection distribution of the NBUE (New Better than Used in Expectation) type, the RAP can guarantee high short-term fairness. Furthermore, we construct a special binomial distribution which is obviously of the NBUE type that can achieve high short-term fairness as well as optimal throughput when used as the selection distribution of the RAP. Finally, by the Poisson approximation for binomial distributions, we propose to use in practice a Poisson distribution corresponding to the special binomial distribution. Numerical and simulation results are provided to validate our analysis.
In Chapter \ref{chap4}, we analyze the delay of the RAP. The total end-to-end packet delay consists of two parts: queueing delay and medium access delay. Regarding medium access delay, we figure out the relation between the distribution of medium access delay and the selection distribution of the RAP by deriving relevant moment generating functions. Regarding queuing delay, with the help of effective bandwidth theory, we derive the conditions for the selection distribution of the RAP that optimizes the queue overflow probability. Furthermore, we construct the delay optimal selection distribution which satisfies the conditions for optimal delay and optimal throughput. However, we show that the delay optimal selection distribution has severely slow convergence rate to the steady state compared with that of the Poisson selection distribution, which is a drawback in practice. Through a comparison study of the RAP between the delay optimal and the Poisson selection distributions, we recommend to use Poisson selection distribution in the sense that the RAP with Poisson selection distribution has fast convergence rate to the steady state and achieves near-optimal delay performance.
수년간 IEEE 802.11 DCF는 무선 통신망의 매체접근제어(MAC) 프로토콜로써 가장 널리 쓰여왔고 이에 대한 성능분석 및 개선을 위해 수많은 연구가 진행되어왔다. 매체접근제어 프로토콜에 대한 여러가지 성능 지표중에서 처리율(throughput), 공평성(fairness), 그리고 지연(delay)이 주로 고려되었다. IEEE 802.11 DCF의 성능에 대한 그간의 수많은 연구를 통해 현재 IEEE 802.11 DCF에서 쓰이고 있는 균등확률분포에 의한 백오프 카운터 값 선택과 백오프 윈도우 크기를 두배로 늘리는 충돌 회피 방식이 최적화된 처리율, 높은 단기공평성 및 낮은 패킷지연의 성능을 위해서는 개선되어야 한다는 것이 알려져왔다. 그러나 분석에 있어서의 복잡성 때문에, 지금까지의 연구문헌들에서는 IEEE 802.11 DCF의 성능개선에 대한 이론적인 연구가 드물었다.
잘 설계된 매체접근제어 프로토콜은 높은 처리율과 공평한 자원분배를 제공하면서 단순해야 한다. 또한, 최근 무선인터넷전화 등 실시간 애플리케이션의 급증으로 인해 패킷지연 또한 주요한 성능 지표가 되었다. 본 논문에서는 잘 설계된 매체접근제어 프로토콜의 기준에 부합하기 위해 IEEE 802.11 DCF의 대체 프로토콜로 Renewal Access Protocol(RAP)이라 불리는 단순한 매체접근제어 프로토콜을 제안한다. RAP는 백오프 카운터 값을 뽑는 방식 말고는 IEEE 802.11 DCF와 같은 방식을 사용한다. RAP에서 각 단말들은 패킷 전송을 위해 이전 전송의 성공이나 실패에 상관없이 고정된 크기의 윈도우에서 미리 정해져있는 (임의의) 선택분포에 따라 새로운 백오프 카운터 값을 뽑는다. 따라서 RAP의 성능은 이 선택분포의 확률적 특성에 의해 결정된다. RAP의 설계에 있어서의 세가지 목표 - 최적화된 처리율, 높은 단기공평성, 낮은 패킷지연 - 달성을 위해 본 논문에서는 RAP에 대한 수리적 모델을 개발하고 엄밀하게 성능을 분석한다.
제 2장에서는 RAP의 처리율을 분석한다. 우선 RAP에 대한 수리적 모델을 개발하고 최적화되었을 때 IEEE 802.11 DCF보다 RAP가 더 나은 처리율 성능을 낸다는 것을 보인다. 또한, 네트워크 상의 단말의 수가 고정되어 있을때, RAP의 처리율 성능은 오직 선택분포의 평균에만 의존하다는 사실을 증명한다. 이는 이미 IEEE 802.11 DCF의 일반화된 연구를 통해 잘 알려진 사실과 부합한다. 그리고 RAP의 실제적인 구현 방법에 대한 논의가 이뤄진다. 본 장에서의 분석적 결과들은 시뮬레이션을 통해 타당성이 확인된다.
제 3장에서는 리뉴얼(renewal) 이론과 신뢰성(reliability) 이론을 활용하여 RAP의 단기공평성을 분석한다. 본 장에서 선택분포가 NBUE(New Batter than Used in Expectation) 타입인 RAP는 높은 단기공평성 성능을 낸다는 것을 보인다. 또한 NBUE 타입으로써 RAP의 선택분포로 사용될 경우 최적화된 처리율 성능과 높은 단기공평성 성능을 보이는 특별한 이항선택분포를 만들어낸다. 마지막 단계로 이항확률분포의 푸아송 근사를 통해 실제적으로는 특별한 이항선택분포에 대응되는 푸아송 분포를 선택분포로 사용하도록 제안한다. 수치적인 시뮬레이션 결과를 통해 본 장에서의 분석에 대한 타당성을 확인한다.
제 4장에서는 RAP의 패킷지연을 분석한다. 종단간 총 패킷지연은 대기지연과 매체접근지연으로 구분된다. 매체접근지연에 대해서는 적률생성함수를 통해 RAP의 선택분포와 매체접근지연 분포의 관계를 규명한다. 대기지연에 대해서는 Effective Bandwidth 이론을 활용하여 큐 오버플로우 확률을 최적화시키는 RAP의 선택분포에 대한 조건들을 유도해낸다. 나아가 최적화된 처리율과 최적화된 대기지연 성능을 위한 조건을 만족하는 최적지연 선택분포를 만들어낸다. 그러나 최적지연 선택분포는 푸아송 선택분포에 비해 정상상태로의 수렴도가 현저하게 떨어지기 때문에 실제적으로 사용하기에는 결점이 있음을 보인다. 최적지연 선택분포와 푸아송 선택분포를 각각 쓰는 RAP에 대한 비교분석을 통해 빠른 수렴도와 거의 최적에 가까운 패킷지연 성능을 보인다는 점에서 푸아송 선택분포를 RAP의 선택분포로 제안한다.
