IndexFiguresTables |
Yun Seong Jeong♦ and Seung Hyong Rhee°Optimal Control of Contention Windows for the Number of Stations in IEEE802.11 DCFAbstract: This paper proposes an algorithm that maximize the performance of the Distributed Coordination Function(DCF), the MAC protocol used in IEEE 802.11 WLAN, according to the number of stations. The standard DCF algorithm, which adopts a random backoff mechanism, may suffer from performance degradations especially when data traffic surges or declines rapidly, and many studies have been conducted to address the issue. In this letter, we propose a new algorithm which maximizes the WLAN throughput by optimizing the contention window parameters according to the number of stations. Analytical modeling using Markov chains shows that our mechanism outperforms the previous mechanisms as well as the DCF. Keywords: IEEE 802.11 WLAN , Distributed Coordination Function , Medium Access Control , Backoff Algorithm 정윤성♦, 이승형°IEEE 802.11 DCF에서 단말의 수에 따른 최적의 혼잡 윈도우 제어요 약: 본 논문은 IEEE 802.11 WLAN의 다중접속 프로토콜인 DCF에서 단말의 수에 따라 최적의 전송성능을 보이는 알고리즘을 제안하였다. 랜덤 백오프(Random backoff)를 사용하는 DCF 알고리즘은 네트워크의 데이터가 급증하거나 급감하는 경우 성능이저하되는 단점을 가지고 있으며, 이를 보완하기 위한연구가 지속적으로 수행되었다. 본 논문에서는 기존에제안된 방식들을 개선하여 단말의 수에 따라 최적의혼잡 윈도우(Contention Window) 제어가 가능한 알고리즘을 제안하고, 이를 Markov chain으로 모델링하여 성능을 분석한다. Ⅰ. 서 론IEEE 802.11 표준[1]의 DCF 알고리즘은 단말들 간의 패킷 충돌을 회피하기 위하여 CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) 방식을 사용하는데, 단말의 수가 많은 dense한 환경에서 충돌이 발생할 확률이 증가하고 sparse한 환경에서는 전송을 시도하기까지 불필요한 대기시간을 가질 수 있다. 이를 해결하기 위해 기존에 많은 연구가 진행이 되었으며, 특히 802.11 PLUS[3] 및 VBS(Variable Backoff Stage) 알고리즘[4]에서는 단말의 개수가 많은 dense한 환경에서의 DCF 성능을 개선하기 위한 방법을 제안하고 성능을 분석한 바 있다. 본 논문은 기존의 연구에서의 제안된 방식들을 개선하여, 네트워크에 접속된 단말의 개수에 따른 최적의 시작 백오프 단계(Starting backoff stage)를 추청하고, 이를 이용하여 단말의 수가 많은 밀집환경에서 DCF 성능을 최대화하는 알고리즘을 제안한다. Ⅱ. 관련 연구Bianchi[2]는 IEEE 802.11 WLAN DCF의 성능분석을 위한 마르코프 체인 모델을 제시하고 포화 처리량을 수학적으로 분석한 바 있다. 이후 이 모델은 많은 연구자들이 새로운 DCF 알고리즘들을 제안하고 그 성능을 비교평가 하는데 널리 응용되었다. 802.11 PLUS[3]에서는 기존의 DCF 방식과 달리, 단말이 패킷전송에 성공했을 경우 첫 백오프 단계로 천이하는 것이 아니라, 성공한 백오프 단계 바로 이전의 단계로 천이하는 방식을 제안하였다. 또한 VBS 알고리즘[4]에서는 시작 백오프 단계를 네트워크의 상태에 따라 가변적으로 조정하는 방식을 제안하여 DCF의 성능을 개선하였는데, 이들 모두 Bianchi의 markov chain 모델을 응용하여 전송 성능을 비교분석 한 바 있다. 이러한 가변 백오프 방식은 최근까지 관심을 받고 있다[5]. Ⅲ. 제안하는 알고리즘본 논문에서는 기존에 제안되었던 연구들을 개선하여, 네트워크의 환경에 따른 충돌확률을 최소화 하고 DCF 성능을 최대화하기 위한 모델을 제안하고, 이의 성능을 수학적으로 비교분석 한다. 802.11 PLUS[3]에서와 같이 패킷전송에 성공했을 경우 바로 이전의 단계로 천이하지만, 단말의 수에 따라서 시작하는 백오프 단계를 필요 없이 초기화하지 않고 일정한 값으로 고정한다. 또한, Markov chain 모델을 사용하여 성능을 최대화하기 위한 최적의 시작 백오프 단계를 구하고, 이를 이용하여 전송성능을 최대화 한다. 그림 1은 본 연구에서 제안하는 Markov chain 모델인데, 802.11 PLUS[3]과 달리 네트워크 상태에 따라 a번째 백오프 단계에서 시작한다. 또한, 패킷전송에 성공할 경우 VBS 알고리즘[4]과 달리 처음 백오프 단계가 아닌 바로 이전의 백오프 단계로 전이하며, 특히, 최적의 시작 백오프 단계를 사용하여 성능을 최대화 하게된다. 본 연구에서 제안하는 방식의 상태천이 확률은 다음과 같다.
[TeX:] $$\left\{\begin{array}{ll} P\{i, k \mid i, k+1\}=1, & k \in\left(0, W_i-2\right), i \in(a, m) \\ P\{a, k \mid a, 0\}=(1-p) / W_a, & k \in\left(0, W_a-1\right) \\ P\{i, k \mid i+1,0\}=(1-p) / W_i, & k \in\left(0, W_i-1\right), i \in(a, m) \\ P\{i, k \mid i-1,0\}=p / W_i, & k \in\left(0, W_i-1\right), i \in(i, m) \\ P\{m, k \mid m, 0\}=p / W_m, & k \in\left(0, W_m-1\right) \end{array}\right\}$$ 구간 [TeX:] $$i \in(a, m), k \in\left(0, W_i-1\right)$$에서 Markov chain 모델의 극한확률은 다음과 같이 정리할 수 있다.
[TeX:] $$\begin{aligned} & b_{a, 0}=b_{a, 0}(1-p)+b_{a+1,0}(1-p) \rightarrow b_{a+1}=\frac{p}{1-p} b_{a, 0} \\ & b_{i, 0}=b_{i-1,0} p+b_{i+1}(1-p) \rightarrow b_{i, 0}=\left(\frac{p}{1-p}\right)^{i-a} b_{a, 0} \\ & b_{m, 0}=b_{m-1,0} p+b_{m, 0} p \rightarrow b_{m, 0}=\left(\frac{p}{1-p}\right)^{m-a} b_{a, 0} \end{aligned}$$ 마르코프 체인 모델의 모든 상태전이 확률의 합은 1이 된다는 점을 이용하여 Bianchi의 모델과 같은 방법을 사용하여 위의 식들을 정리하면, 최종적으로 slot time 안에서 패킷을 전송하는 전송확률인 τ를 다음 식과 같이 표현할 수 있다.
[TeX:] $$\begin{aligned} \tau & =\sum_{i=a}^m b_{i, 0}=\sum_{i=a}^m\left(\frac{p}{1-p}\right)^{i-a} b_{a, 0} \\ & =b_{a, 0}\left(\frac{(1-p)\left(1-\left(\frac{p}{1-p}\right)^{m-a+1}\right)}{1-2 p}\right) \end{aligned}$$ 이 이후에 DCF 알고리즘의 성능을 평가하기 위해서 네트워크의 처리량 S를 구하는 과정은 Bianchi[2]의 모델에서 사용하는 방법과 동일하다. 이상의 Markov model을 사용하여 시작 백오프 단계에 따른 포화처리량의 변화를 그림 2에서와 같이 나타낼 수가 있는데, 이에 의하여 단말의 개수에 따른 최적의 시작 백오프 단계값을 구할 수 있다. 표 1에서는 단말의 개수가 많아짐에 따라서 최적의 시작 백오프 단계 값이 증가함을 볼 수 있는데, 이를 이용하여 네트워크의 상태에 따라 전송성능을 최대화 하는 것이 가능하다. 그림 3에서는 주어진 네트워크에서 최적의 시작 백오프 단계값을 사용하여 포화처리량을 구하고, 이를 기존의 802.11 DCF[2], 802.11 PLUS[3] 및 VBS 알고리즘[4]의 성능과 비교하였다. 본 논문에서 제안하는 알고리즘은 단말의 개수가 많아지는 상황에서도 계속해서 높은 포화처리량을 유지하는 것을 볼 수 있다. AP가 단말의 개수에 따라 정한 시작 백오프 단계를 단말들에게 알려주는 시나리오를 가정한다. 표(Table) 1. 단말의 개수(n)에 따른 최적의 시작 백오프 단계값(a) (Optimal backoff stage values(a) according to the number of stations(n))
Ⅳ. 결 론기존에 제안되었던 802.11 DCF[2], 802.11 PLUS[3] 및 VBS 알고리즘[4] 모두 단말의 개수가 늘어남에 따라 포화처리량이 급격히 감소하는 단점을 보인다. 본 논문에서 제안한 알고리즘은 단말의 개수에 따라 최적의 시작 백오프 단계값을 구하고 이를 적용하여, 네트워크의 상황에 적응하여 포화처리량의 값을 유지하는 장점을 갖는다. 이 방식을 적용하기 위해서는 주어진 네트워크의 파라미터 값들에 따른 포화처리량을 일일이 구해서 최적의 시작 백오프 단계값을 알아내야 한다. 향후에는 최적의 시작 백오프 단계값을 근사값으로 추정해낼 수 있는 개선된 모델과 함께, 가변 백오프[5]가 DCF의 성능에 미치는 영향에 대한 연구가 진행될 수 있다. References
|
StatisticsCite this articleIEEE StyleY. S. Jeong and S. H. Rhee, "Optimal Control of Contention Windows for the Number of Stations in IEEE 802.11 DCF," The Journal of Korean Institute of Communications and Information Sciences, vol. 50, no. 2, pp. 293-295, 2025. DOI: 10.7840/kics.2025.50.2.293.
ACM Style Yun Seong Jeong and Seung Hyong Rhee. 2025. Optimal Control of Contention Windows for the Number of Stations in IEEE 802.11 DCF. The Journal of Korean Institute of Communications and Information Sciences, 50, 2, (2025), 293-295. DOI: 10.7840/kics.2025.50.2.293.
KICS Style Yun Seong Jeong and Seung Hyong Rhee, "Optimal Control of Contention Windows for the Number of Stations in IEEE 802.11 DCF," The Journal of Korean Institute of Communications and Information Sciences, vol. 50, no. 2, pp. 293-295, 2. 2025. (https://doi.org/10.7840/kics.2025.50.2.293)
|
