Contention-based Wireless Medium Access Control Protocols with Additional Degree of Design Freedom

Abstract

무선 패킷 네트워크에서는 패킷 전송을 위해 공통의 무선 자원을 다수의 사용자가 공유한다. 두 명 이상의 다른 사용자로부터 동시에 패킷이 전송되면 패킷은 서로 간섭을 일으키게 되고 수신단은 이러한 간섭에 의해 패킷을 제대로 디코딩할 수가 없다. 이러한 현상을 충돌이라고 하며, 무선 패킷 네트워크에서는 제한된 전송 전력의 낭비 뿐만 아니라 무선 채널 자원의 낭비 문제로 인해 충돌을 최대한 제어하여야 한다.따라서 MAC 프로토콜은 다수의 사용자가 공유된 무선 자원을 통해 패킷을 전송하는 경우 이러한 간섭효과를 억제하거나 제거하여야 한다.

다중 사용자의 패킷 전송을 제어하는 중앙 제어 디바이스가 존재하는 경우에 대한 잘 알려진 두 종류의 MAC 프로토콜이 존재한다. 중앙 제어 디바이스가 없는 네트워크에서는 경쟁 기반 (임의 접근) MAC 프로토콜이 무경쟁 프로토콜에 비해 선호된다. 예를 들어 IEEE802.11 근거리 통신망 (WLAN)에서는 경쟁 기반의 Distributed Coordination Function (DCF)이 defacto MAC 프로토콜로 정의되어 있다. 이 프로토콜에서 각각의 사용자는 패킷 전송 전에 무선채널을 센싱하고 만일 다른 사용자가 전송 중이라면 충돌을 피하기 위하여 자신의 패킷 전송을 지연시킨다. 그러나, 다수의 사용자가 센싱을 수행하고 동시에 패킷 전송을 시도한다면 여전히 충돌은 발생할 수 있기 때문에, 충돌 확률을 줄이기 위한 목적으로 각각의 전송 이전에 경쟁 윈도우에 따른 임의 백오프 값으로 각 사용자의 전송 시점을 분산시킨다. 불행하게도 이러한 백오프 알고리즘은 네트워크에서의 사용자수가 크게 증가하는 경우에 급격히 성능이 저하된다는 단점을 가지고 있다.

본 논문에서는 DCF 기반 유니캐스트와 브로드캐스트 전송 시나리오에서 이러한 성능 저하의 문제점을 경감시킬 수 있는 단순하면서도 효과적인 메커니즘을 제안하였다. 새로운 메커니즘에서는 기존의 임의 백오프 디자인에 대해 DDoF (Degree of Design Freedom)을 1만큼 확장하였다. 구체적으로 새로운 메커니즘에서는 경쟁 윈도우 상에서의 슬롯 선택 확률인 CSSD (Contention Slot Selection Distribution)를 기존 알고리즘에서와 같이 균일 분포가 아닌 적응적으로 튜닝이 가능한 비균일 분포를 갖도록 디자인하였다. 유니캐스트 DCF에 대하여 본 논문에서는 다이나믹하게 변화하는 kurtosis(a measure of the peakedness of the probability distribution)를 갖는 더블 트렁케이티드 정규 CSSD를 제안하였고, 브로드캐스트 DCF에 대해서는 정적 역지수적 CSSD를 제안하였다. 이론적 분석과 시뮬레이션을 기반으로 본 연구에서는 적절한 성능 평가 메트릭을 고려하여 제안 메커니즘의 우수성을 입증하였다. 유니캐스트 DCF에서 제안 알고리즘은 패킷 지연은 감소시키고 네트워크의 처리률은 최대로 하며, 각각 사용자의 처리률-공정성 또한 최대로 제공할 수 있음을 확인하였다. 마찬가지로 브로드캐스트 DCF에서는 네트워크의 처리률 증대와 더불어 방송된 패킷의 수신률에 대한 신뢰성도 향상시킬 수 있음을 확인하였다. 중요하게는 두 경우 모두에 있어서 네트워크의 사용자 수 증가에도 이러한 성능 메트릭이 우수함을 확인하였다.

제안 메커니즘이 단순 DCF에서 성능 향상을 제공할 수 있음은 확인하였으나, IEEE802.11e에서와 같이 QoS를 제공하기 위해 확장된 EDCD(Enhanced Distributed Channel Access)에 제안 메커니즘을 적용하는 것은 문제가 있었다. 이는 낮은 우선 순위 패킷 전송을 시도하는 각 사용자의 CSSD를 독립적으로 조절하는 것이 EDCA에서와 같이 경쟁 윈도우 사이즈를 우선순위에 따라 분산시키는 방식에 위배되기 때문이다. 따라서, 제안 메커니즘을 그대로 EDCA에 적용하면 채널 접속 기회 관점에서 높은 우선 순위 사용자가 지각하는 QoS 등급이 반전되는 경향이 있으며 이는 낮은 우선 순위 사용자의 부하가 높을 경우에 더욱 심각하다. 따라서 본 연구에서는 CSSD를 조작하여 우선 순위에 따른 성능을 제공할 수 있도록 하였으며 시뮬레이션을 통해 성능을 검증하였다.

WLAN에서와 같이 표준 경쟁 기반의 MAC 프로토콜 성능 향상을 위한 본 논문에서 제시한 메커니즘들은 실제 구현에 있어서도 장점들이 있으며 이는 다음과 같다. 첫째 제안된 메커니즘들은 경쟁 윈도우 기반의 채널 접속 메커니즘의 단순함을 그대로 상속하고 있다. 둘째 제안 메커니즘들은 표준 메커니즘과 호환성이 높고 표준에 쉽게 추가될 수 있다. 즉, 표준에서 제시된 시그널링 메커니즘의 어떠한 변형도 요구하지 않으며 표준 프레임 구조 변경을 요구하지 않는다.|In wireless packet networks, multiple users share a common wireless medium to transmit their packets. Should there occur two or more simultaneous transmissions from different users, the transmitted packets may interfere with each other and may not be decoded by the designated receivers. This phenomenon is commonly known as packet collisions. Over wireless packet networks, collisions are strongly undesirable because they not only waste limited transmitting power but also waste the scare wireless channel resource. Hence, every Medium Access Control (MAC) protocol that are fully responsible to coordinate the transmission of multiple users in the shared medium are focused on either eliminating or mitigating such interference.

Two classes of MAC protocols have been popularly used in wireless packet networks depending on the availability of a central entity that coordinates the transmission of multiple users. In the network without any central entity that takes the role of coordinating the access of the users, contention-based (random access) MAC protocols are preferred over their contention-free counterpart. For example, in IEEE 802.11 Wireless Local Area Networks (WLANs), a contention-based Distributed Coordination Function (DCF) is a defacto MAC protocol. According to this protocol, each user senses (listen to) the wireless channel before transmitting and defers the transmission to prevent packet collisions if it detects the ongoing transmission. Since collisions can still occur if multiple users sense and initiate their transmissions at the same time, the protocol introduces a random backoff that is regulated using temporal Contention Window (CW) before each transmission to further reduce the chances of collisions. Unfortunately, it has been found that the performance of this protocol deteriorates as the number of users in the network increases.

In this dissertation, we present a simple mechanism to alleviate the problem related to the performance deterioration of DCF in both its unicast and broadcast versions. The new mechanism extends the conventional random backoff design by increasing its Degree of Design Freedom by one (i.e., by adding an additional configurable parameter in its design space). More precisely, according to the new mechanism, the Contention Slot Selection Distribution (CSSD) over the contention window is no more restricted to have only the uniform shape but is allowed to have a properly designed and adaptively tunable non-uniform shape. For the unicast DCF we design a doubly truncated Normal CSSD with dynamically varying kurtosis (kurtosis is a measure of the peakedness of the probability distribution) while for the broadcast DCF we adopt the static reverse-exponential CSSD. Based on theoretical and simulation based analysis, we show the benefit of the proposed mechanism in terms of most relevant performance metrics. Inclusion of the proposed mechanism in the unicast DCF not only maximizes network throughput and throughput-fairness of each user, but also reduces packet delay. Likewise, the inclusion of the proposed mechanism in broadcast DCF concurrently enhances network-throughput and reliability of the broadcasted packets. More importantly, the performance gain in terms of all of those metrics increases with increase in the number of users in the network.

Despite such a potential of the proposed mechanism in enhancing performance of DCF, it is quite challenging to adopt the proposed mechanism in Enhanced Distributed Channel Access (EDCA) protocol, a Quality of Service (QoS) extension to DCF introduced in IEEE 802.11e, because the independently tuned CSSDs of the users attempting to transmit lower priority packets may violate the CW-size differentiated relative differentiation principle adopted in EDCA. Such a violation results in frequent priority inversions (in terms of channel access) thereby reducing the perceived QoS grade of the higher priority packets, especially when the number of lower priority users is high. In the real-world sense, manifest consequences would be elongated jitter and reduced-throughput for the higher priority audio or video services due to the increase in the lower priority data traffic load. We introduce a simple correction mechanism that manipulates the CSSDs of the lower priority users to overcome that problem and verify the efficacy of the mechanism using computer simulations.

The mechanisms that we have introduced in this dissertation for improvising the standard contention-based MAC protocols in WLAN are attractive for practical implementations due to several reasons. Firstly, those mechanisms adheres the simplicity of CW-based channel arbitration mechanism and well retain that simplicity. Secondly, those mechanisms are fully-standard compliant and backward-compatible; they neither require modifications in the standardized signalling mechanism used for transmitting a frame nor in the standardized frame structure.

Index Terms: Unicast and broadcast MAC protocols, Non-uniform contention slot selection distribution, Improvised collision avoidance, Short-term fairness, Discrete time Markov chain, Renewal reward process, Cross-layer analysis, IEEE 802.11, DCF, QoS differentiation, EDCA, Network simulator (ns-2)