A study on Contention Resolution Algorithms for Performance Enhancement in BWAl

Abstract

유무선 경쟁 기반 채널 접근 네트워크에서 CRA (Collision Resolution Algorithm) 기법을 처리률, 접속 지연 등 전반적인 네트워크 성능에 대한 중요한 역할을 한다. 최근 OFDM이 광대역 트래픽에 대한 고속 전송을 지원할 수 있는 방식으로 각광을 받고 있고, OFDMA는 다중 접속 방식으로 선호되고 있다. 본 연구에서는 무선 네트워크에서 OFDM 기반 다양한 시스템에서의 성능을 향상시키고자 하는 목적으로 CRA 알고리즘의 성능 향상에 대한 연구를 수행하였다. CRA 알고리즘에 대한 분석적인 연구를 토대로 CBELB (Combined Binary Exponential and Liner Backoff), UBB (Utility Based Backoff)라는 처리률과 지연 특성에 효과적인 두 가지 새로운 알고리즘을 제시하였고, 이러한 알고리즘은 802.16 BWA 시스템에 적용하였다.

CBELB는 초기 전송시도에서 지수적으로 경쟁 윈도우를 증가시키지만 몇 번의 시도 이후에는 선형적으로 증가시키는 복합형태의 CRA 기법이다. CBELB 알고리즘에 대한 우리의 분석적 모델에서는 초기 4번째까지의 충돌에 대해서 충돌한 SS는 자신의 경쟁 윈도우 사이즈를 2의 제곱에 따라 지수적으로 증가시키고 이후 추가적인 충돌에 대해서는 최대 재전송 횟수에 도달할 때까지 경쟁 윈도우 사이즈를 선형적으로 증가시킨다. 전송에 성공한 경우 혹은 최대 재전송 횟수 이후의 충돌 발생 경우에 해당 SS는 새로 진입한 SS와 마찬가지로 처음부터 다시 시작한다. OFDMA 기반 BWA에서 CBELB 알고리즘은 BEB 알고리즘에 비해 성공적인 레인징 전송에 있어서의 평균 접속 지연 시간을 단축시켰다. SS 증가에 따른 접속 지연은 BEB와 CBELB에서 같이 공통적으로 증가되지만, CBELB에서 상대적으로 덜 증가한다.

UBB는 이전 전송에서 선택된 백오프 값에 대한 만족도(satisfaction)에 기반한 새로운 CRA 알고리즘이다. UBB 알고리즘에서는 SS가 레인징 전송 중 충돌을 경험할 때마다 이전 전송 시도에서 임의로 선택된 백오프 값에 대한 유틸리티 혹은 만족도 기반의 새로운 경쟁 윈도우 사이즈를 설정한다. 백오프 값이 클수록 유틸리티는 작으며 반대의 경우에도 동일하다. 이 방식의 핵심 아이디어는 이전 시도에서 오랫동안 기다린 SS에 대해 주어진 낮은 유틸리티에 따라 SS에 적은 백오프 경쟁 윈도우를 할당한다는 것이다. 전송이 성공할 때까지 혹은 최대 재전송 시도에 도달할 때까지 이 과정이 반복된다. OFDMA 기반 BWA 네트워크에 적용된 UBB 알고리즘은 BEB 알고리즘에 비해 평균 접속 지연이 적으며, 시스템의 부하가 작은 경우 처리률도 BEB에 비해 UBB가 더 높았다.|In contention based channel access networks, whether wireless or wired, CRA (Contention Resolution Algorithm) plays an important role in an overall network performance indicator such as throughput, access delay, etc. In wireless networks, these days, OFDM (Orthogonal Frequency Division Multiplexing) has become a promising technique to support high speed transmission of broadband traffic, and OFDMA (Orthogonal Frequency Division Multiple Access) is regarding as the superior and preferred choice of multiple access. They seem to be key techniques for the future networks as well. Hence, with the precise goal of improving the network performance of such wireless networks, we investigate the performance enhancement in CRA which could be applied to a broad range of OFDMA based wireless networks. The detailed carried investigation makes a way for two new throughput and delay efficient CRAs, named CBELB (Combined Binary Exponential and Liner Backoff) and UBB (Utility Based Backoff), both of which are easily applicable to IEEE 802.16 based BWA (Broadband Wireless Access) systems.

CBELB is the hybrid CRA scheme which accounts on exponential increment of contention windows followed by the linear increment after few numbers of previous transmissions. In our analyzed model of CBELB algorithm, for the first four initial collisions, the colliding SS increases its contention window size exponentially with the factor of 2, whereas in case of further successive collision, the SS increases the contention window size linearly until the maximum number of retransmission is reached. In case of successful transmission, or collision after maximum retransmission, SS starts from the beginning as the newly arrived SS. Implementation of CBELB algorithm in the OFDMA based BWA network reduces the average access delay for the successful ranging request transmission in comparison to legacy BEB. Medium access delay increased linearly with increase in number of SS in both BEB and CBELB algorithm but the increase in delay is comparatively less in CBELB algorithm.

UBB is the novel CRA which is based on the satisfaction of the SS on self selected backoff value in previous transmission/s. In UBB algorithm, whenever an active SS experiences a collision during ranging request transmission, it accomplishes its new contention window size based on the utility, satisfaction, upon its randomly selected backoff value on the previous transmission attempt. Higher the deferred backoff value lower will be the utility and vice versa. The key idea of this algorithm is to give less backoff window to the SS according to the given utility, if it has been waiting for longer duration in the previous trail and vice versa. The process is repeated unless the request is transmitted successfully, or until the maximum retransmission attempt is reached. UBB algorithm applied to OFDMA based BWA network reduces the average medium access delay for the successful request transmission in comparison to BEB. Even more, throughput for the lower offered load is higher in UBB than BEB.