IEEE 802.11은 무선랜(Wireless LAN)의 표준기술 중 하나로써 Wi-Fi Alliance에서는 2015년 IEEE 802.11표준을 사용하는 기기가 20억 개가 넘어갈 것으로 예측하고 있다. 스마트폰의 보급으로 인해 3G/4G와 같은 무선 전화망을 보조하는 네트워크로써의 역할이 높아지고 있으며 이에 높은 전송률(IEEE 802.11ac), 핸드오프(IEEE 802.11ai) 등을 고려한 표준이 채택되고 지속적으로 발전되고 있는 추세이다[1].

IEEE 802.11 WLAN은 CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance) 방식을 기반으로 모든 스테이션이 동등한 관계에서 경쟁을 통해 채널을 사용하는 DCF(Distributed Coordination Function) 를 기본적인 데이터 액세스 방법으로 사용하고 있다. IEEE 802.11 DCF는 BEB(Binary Exponential Backoff) 알고리즘을 기본으로 한다[2]. 즉, 경쟁윈도우(CW, Contention Window)의 값 중 임의의 값을 백오프 카운터(Backoff Count)로 선택하고 채널이 유휴상태일 때 이 백오프 카운터를 줄임으로써 카운터가 0이 되면 해당 스테이션은 전송을 시도하는 구조이다. 전송이 성공하면 다시 최초의 백오프 스테이지로 값이 설정되어 최소경쟁윈도우 값으로 경쟁윈도우를 설정하고, 충돌이 발생하게 되면 백오프 스테이지를 증가시킴으로써 경쟁윈도우의 값을 2배씩 증가시키는 방법을 사용한다. 이러한 BEB 알고리즘의 구조 상 경쟁하는 스테이션의 수가 증가할수록 충돌이 발생할 가능성이 증가하여, 이를 해결하기 위한 많은 연구들이 진행되어 왔다. 그 대표적인 예로 Binachi[3]는 2차원 마르코프 연쇄(Markov Chain)를 이용하여 DCF의 충돌확률을 수학적으로 계산하고 이를 시뮬레이션으로 검증하는 방법을 제안하고, Binachi의 해석방법을 응용하여 EIED(Exponential Increase Exponential Decrease)[4], EILD(Exponential Increase Linear Decrease)[5], MIMD(Multiplicative Increase and Multiplicative Decrease)[6], Slow CW[7], GDCF(Gentle DCF)[8]와 같이 프레임의 전송이 성공하였을 경우 경쟁윈도우를 줄이는 폭을 조절하여 DCF의 충돌확률을 줄이는 방안이 제시되었다. 또한 LILD(Linear Increase Linear Decrease)[9]와 같이 충돌이 발생할 때에도 경쟁윈도우의 크기를 점진적으로 증가시키는 방식과 ADCF(Adaptive DCF)[10]와 같이 네트워크의 전송상태 및 대기상태 정보를 파악하여 각 스테이지의 전송 성공률을 계산함으로써 경쟁윈도우의 크기를 조정하는 방법이 제안되었다. 하지만 언급된 알고리즘들은 모두 충돌이 발생하였을 경우에 대처하는 방안들로, 노드의 수가 최소경쟁윈도우 값 이상으로 증가하게 되면 필연적으로 프레임의 충돌이 발생하게 되는데 이에 대한 고려는 미흡하다.

이러한 배경에서 본 논문은 네트워크에 접속된 스테이션의 수에 따라 백오프 스테이지를 결정함으로써 경쟁윈도우의 크기를 조절하여 스테이션의 증가 시 발생하게 되는 프레임의 충돌 확률을 낮추고 네트워크의 사용량을 높이는 VBS(Variable Backoff Stage)알고리즘을 제안한다. 따라서 2장에서는 제안하는 알고리즘에 대한 설명을, 3장에서는 해석적결과를 이용하여 시뮬레이션 결과와 비교하고, 마지막으로 4장에서 결론을 맺는다.

IEEE802.11 DCF의 기존 많은 연구들은 충돌이 발생한 경우 경쟁윈도우의 크기를 조정하여 네트워크의 처리율을 높이는 방법을 사용한다. 하지만 이는 충돌이 발생한 경우만을 가정하여 일정 수 이상의 스테이션이 동시에 채널을 사용하는 상황에서는 각각의 스테이션들은 접속과 동시에 충돌을 야기하는 문제점을 가진다. 또한 채널의 상태를 분석하여 경쟁윈도우의 크기를 조정하는 방식을 제안한 연구들[10-12]이 있으나 이는 스테이션의 이동이 빈번한 경우 채널의 상태를 예측하기가 쉽지 않은 문제점을 가진다. 따라서 결정된 경쟁윈도우의 크기를 상황에 맞게 가변적으로 조정하지 못하고 교착상태(Dead lock)에 빠질 위험성이 있다.

본 논문에서는 일정 수 이상의 스테이션이 같은 채널상에 존재할 때 필연적으로 발생하는 충돌을 방지하기 위해 최초 백오프 스테이지를 같은 AP에 접속한 스테이션의 수에 따라 가변적으로 조정하는 VBS 알고리즘을 제안한다. 기본적으로 VBS 알고리즘은 데이터의 최초 전송 시와 데이터의 전송이 성공한 경우 AP에 접속된 스테이션의 수에 따라 백오프 스테이지를 결정하여 백오프 알고리즘을 수행하고, 충돌이 발생한 경우 BEB 알고리즘과 같은 방식으로 다음 단계의 백오프 스테이지로 진입함으로써 경쟁윈도우의 크기를 증가시키는 방법을 사용한다.

VBS 알고리즘의 동작을 위해서는 같은 AP에 접속된 스테이션 수를 파악하여야 하며 따라서 본 논문에서는 다음의 2가지 방식을 제안한다.

첫 번째 방식은 그림 1과 같이 AP(Access Point)가 프로브 응답(Probe response) 및 비콘(Beacon) 메시지의 프레임 바디에 스테이션 수(station count)필드를 삽입하여 전송함으로써 접속된 각 스테이션이 같은 AP에 접속된 스테이션 수를 파악 한다.

프로브 응답은 스테이션이 능동(Active) 방식으로 AP에 접속하기 위해 AP로 부터 수신하는 메시지로써 스테이션의 프로브 요청(Probe request) 메시지에 대한 응답 메시지이다. 따라서 채널의 모든 스테이션들은 AP에 다른 스테이션이 접속하고자 할 때 마다 AP에 접속된 스테이션의 수를 파악할 수 있게 된다. 또한 비콘메시지는 AP가 주기적으로 전송하는 메시지로써 스테이션이 수동(Passive) 방식으로 AP에 접속하고자 할 때 사용된다. 비콘 메시지는 100ms 간격으로 주기적으로 전송되며 이를 통해 스테이션은 AP에 접속된 스테이션의 수를 파악 가능하다. 이렇게 AP가 주기적으로 또는 스테이션의 접속 요청 시 전송하는 두 가지 네트워크 설정 메시지에 스테이션 수를 삽입하여 전송함으로써 스테이션의 변동 상태를 보다 실시간으로 파악할 수 있고 이를 통해 제안하는 알고리즘의 정확도를 높일 수 있다. 프로브 응답의 경우는 새로운 스테이션이 네트워크상에 접속하고자 하는 상태이며 이는 곧 스테이션의 수가 증가할 수 있음을 의미하고, 비콘 메시지의 경우주기적으로 네트워크상에 접속이 종료된 스테이션이 있는지를 파악할 수 있게 한다.

두 번째 방식은 IEEE 802.11e 표준상의 비콘 메시지에 포함되는 ‘SS(Basic Service Set) Load Element’를 통해 스테이션의 수를 파악하는 방법이다. 이는 표준상에서 제공하는 요소로써 AP의 수정 없이 네트워크의 스테이션 수를 파악할 수 있으나 100ms 간격의 비콘 메시지에 포함되므로 스테이션 수의 변화를 감지하기 위해 최대 100ms의 지연이 있을 수 있다는 단점이 있다. 본 논문에서는 앞에 기술된 2가지 방식에 의해 각 스테이션은 같은 AP상에 접속된 스테이션의 수를 파악하는 것으로 가정한다.

VBS 알고리즘은 각 스테이션들이 AP상에 접속된 스테이션의 수를 파악하면 이에 따라 알고리즘 상의 시작 백오프 스테이지(start backoff stage)를 결정한다. 같은 AP에 접속된 스테이션 수에 따른 시작 백오프 스테이지의 결정 알고리즘은 다음과 같다.

VBSF(Variable Backoff Stage Factor)는 VBS알고리즘 요소(Factor)를 나타내며, W_i는 i번째 스테이지의 경쟁윈도우의 크기를 나타낸다. SC는 현재 같은 AP에 접속된 스테이션의 수이다. VBSF는 가변으로 설정될 수 있는 인자로써 높은 값을 가질수록 경쟁윈도우의 크기가 증가하므로 충돌확률은 낮아지나 백오프 카운터 단계의 대기시간이 늘어나는 등가교환(Trade-off) 관계이므로 네트워크의 복잡도에 따라 적절히 설정될 필요가 있다. 알고리즘의 동작은 스테이션 수에 대한 정보를 가진 메시지가 수신되어 VBS 알고리즘을 통해 i값이 선택되면 백오프 스테이지의 시작 값 a를 i로 설정함으로써 경쟁윈도우의 시작 크기를 설정한다. 데이터의 전송 성공 시마다 이 a값은 갱신되며, 충돌 발생 시는 기존 BEB 알고리즘과 동일하게 다음 백오프 스테이지로 단계를 진행시킨다. 다음 그림 2는 VBS알고리즘의 동작을 설명한다.

IEEE 802.11 DCF를 분석하기 위한 마르코프 체인모델(Markov chain model)은 [3]에서와 같이 DCF의 충돌확률을 수학적으로 분석하기 위해 사용된 모델로써 각 스테이션들은 한 번의 전송 성공 후 바로 전송할 다른 패킷이 있는 포화상태를(Saturation status)를 가정한다.

VBS 알고리즘을 적용한 마르코프 체인모델은 경쟁 윈도우(W), 백오프 스테이지(a, i, m), 백오프 카운터의3가지 변수를 사용한다. 알고리즘이 적용된 마르코프 체인모델을 설명하면 백오프 스테이지 결정알고리즘으로 선택된 a로 부터 스테이지가 시작되어 스테이지 i는 a≤i≤m의 값을 가지며 W_i= 2ⁱW로 W는 최소경쟁윈도우의 크기를, W_i는 i스테이지의 경쟁윈도우 크기를 나타내며 최대경쟁윈도우인 2^mW까지 증가하고 그 이후 충돌 발생 시에는 이 값을 유지한다.

포화상태에서 네트워크를 해석적으로 표현하기 위해 n개의 스테이션이 존재한다고 가정하고, s(t)와 b(t)를 임의의 시간 t에서 스테이션의 백오프 스테이지와 백오프 카운터 값을 나타내는 랜덤 프로세스라고 하면, VBS 알고리즘을 적용한 백오프 알고리즘은 2차원 마르코프 체인{s(t), b(t)}로 나타낼 수 있으며 이는 이산시간 마르코프 체인(Discrete-time Markov chain)으로써 그림 3과같이 표현된다.

마르코프체인모델에서 a는 VBS 알고리즘에 의해 설정되는 시작 백오프 스테이지, m은 최대 백오프 스테이지를 나타내고, W_i는 (a,m)사이의 값을 가지는 i스테이지의 경쟁윈도우 크기를 나타낸다. 데이터의 충돌이 계속되어 최대 백오프 스테이지에 도달하게 되면 충돌 발생 시 최대 백오프 스테이지 m으로 상태가 유지되며 데이터의 전송이 성공하면 스테이지 a로 다시 복귀한다.

VBS 알고리즘의 시작 스테이지는 지속적으로 갱신되나 해석적인 모델에서는 스테이지가 (a,m)사이의 값으로 결정된 상태로써 전송한 패킷이 충돌확률을 p라고 하면, 마르코프 성질을 이용하여 다음 식(1)과 같이 조건부 확률을 이용하여 상태천이 확률을 구할 수 있다.

첫 번째 식은 슬롯 타임의 시작 시점에서 백오프 카운트의 감소를 나타내고, 두 번째 식은 전송 성공 후 다시 시작 스테이지로 이동하는 것을 나타내는 식이며, 세 번째와 네 번째 식은 전송 실패 시 스테이지 이동을 설명하고 있다. b_i,k=lim_t→∞P{s(t)=i, b(t)=k}, i∈(a,m), k∈(0,W_i-1)를 정상분포(stationary distribution)을 가진다면 연쇄정칙(chain regularities)에 의해 다음 식(2)가 성립한다.

마르코프 체인의 모든 스테이지의 충돌확률을 더하면 1이 된다는 점을 이용하면 다음과 같이 식(3)을 구할 수 있다.

식(3)으로 부터 b_a,0을 구하면 식(4)와 같다.

τ를 어떤 스테이션이 임의의 슬롯 시간에 전송할 확률이라 하면 τ는 식(5)와 같이 나타낼 수 있다.

전송한 패킷이 충돌할 확률 p는 나머지 (n-1)개의 스테이션중 적어도 하나이상이 그 슬롯 시간에 전송하고 있을 확률로서 식(6)과 같이 표현된다.

전송률을 계산은 [3]에서 제시된 식을 활용한다.

n개의 스테이션이 경쟁하는 채널에서 적어도 1개 이상의 채널이 전송을 시도할 확률을 P_tr, 스테이션이 전송에 성공할 확률을 P_s라고 하면 P_s는 오직 하나의 스테이션이 전송을 시도할 확률이 되므로 다음 식(7), 식(8)과 같이 나타낼 수 있다.

E[P]를 평균 페이로드 크기라고 하면, 성공적으로 패킷을 전송하는데 소요되는 슬롯시간의 평균은 P_trP_sE[P]로 나타낼 수 있으며, 슬롯이 비어있을 확률은 1-P_tr, 전송에 성공할 확률은 P_trP_s, 충돌이 발생할 확률은 P_tr(1-P_s)는 이다. 정규화된 시스템 처리율 S는 전송에 성공한 실제 데이터의 평균 전송 시간과 패킷을 성공적으로 전송하는데 소요된 평균시간의 비율로써 식 (9)와 같이 표현된다. 여기서 T_s는 전송 성공 시 소요되는 평균 시간을 T_c는 전송 실패 시 소요되는 평균 시간, σ는 빈 슬롯 시간의 길이이다.

H=PHY_hdr+MAC_hdr을 패킷 헤더의 전송시간, δ를 전파지연이라고 하면 식(10)으로 T_s와 T_c가 표현가능하다.

VBS 알고리즘의 수학적 모델을 평가하기 위해 시뮬레이션을 수행하여 백오프 스테이지에 따른 네트워크 처리율, 재전송 시도횟수, 각 패킷들의 평균지연시간의 관점에서 분석하였다. 시뮬레이션은 Pamvotis[13]를 수정하여 구현하였으며 시드번호(seed number)를 변경하여 값을 랜덤하게 설정하여 각 5분씩 데이터를 전송하여 평균을 측정하였다.

시뮬레이션을 수행함에 있어 OFDM(Orthogonal Frequency Division Multiplexing) 변조방식을 사용하는 최대 대역폭이 54Mbps인 IEEE 802.11g를 기반으로 테스트를 진행하였으며 시뮬레이션에 설정된 각 파라미터는 표 1과 같이 패킷의 길이는 최대로 32768bits, 경쟁윈도우 최대값과 최소값은 IEEE 802.11g 의 기본으로 설정된 16, 1024, 최대 백오프 스테이지는 6, 재전송 한계 값은 설정하지 않았다. 시뮬레이션은 각 스테이션이 항상 전송할 데이터를 가지고 있는 포화상태를 가정하였으며 전송실패에 의한 재전송은 고려하지 않았다. 또한 VBS알고리즘을 수행함에 있어 고려되어야 할 VBSF를 5와 10으로 설정하고 테스트를 진행하였고 이를 각 VBS5, VBS10으로 명명하였다. VBSF가 높을수록 스테이션 수에 따른 시작 백오프 스테이지 a의 값이 높아지며, 따라서 경쟁윈도우의 크기도 커진다.

그림 4는 스테이션 수의 증가에 따른 네트워크의 처리율과 설정되는 백오프 스테이지를 나타낸 그래프로 써 그래프의 x축은 스테이션의 수를, y축은 네트워크의 사용률을 나타내고 우측은 VBS 알고리즘에서의 스테이션 수에 따른 시작 백오프 스테이지 a값이다. BEB 알고리즘은 VBS5와 VBS10에 비해 스테이션 수의 증가에 따라 처리율이 급격하게 감소하는 것을 확인할 수 있으며, VBS10은 VBS5와 비교하여 2배의 VBSF 크기에 비해 네트워크 사용량의 차이가 크지 않다. 이는 일정 크기 이상의 경쟁윈도우는 데이터의 충돌확률은 줄이는 대신 백오프 대기시간이 증가하여 실질적인 네트워크 사용률을 높이지 못하기 때문으로 해석된다.

네트워크의 처리율은 식 9를 통해 설명가능하다. 식9의 분자와 분모를 P_trP_s로 나누어서 정리하면 분모의T_s는 하나의 패킷을 성공적으로 전송하는데 소요되는 시간 1/(P_trP_s)는 전송에 성공할 때까지 소비하는 슬롯타임의 평균, T_c((1/P_tr)-1)는 충돌에 소비되는 시간을 나타낸다.

그림 5는 스테이션의 수에 따른 재전송 시도를 나타내며 VBS5와 VBS10의 경우의 변곡점은 VBS알고리즘에서 스테이션 수에 따라 백오프 스테이지가 증가하는 경우이며 이에 따라 경쟁윈도우 크기가 증가하고 네트워크 전체의 충돌확률이 낮아져 재전송 시도가 감소하는 것이 그래프를 통해 확인 가능하다. BEB 알고리즘의 경우 스테이션이 증가할수록 재전송 시도가 급격하게 증가하며, 이는 잦은 충돌로 인해 네트워크의 처리율을 감소시킴을 의미한다. 또한 전송이 성공한 경우 백오프 스테이지가 0으로부터 다시 시작되며 이는 최소 경쟁윈도우에 보다 많은 수의 스테이션이 네트워크상에 존재하면 충돌 발생 확률이 높아지고 이에 따라 네트워크의 사용량이 감소된다.

그림 6는 각 패킷 당 평균 지연시간을 나타낸다. 각 스테이션의 총 패킷 지연시간을 더하고 이를 테스트한 시간과 송신된 패킷 수로 나누어서 구하였다. 패킷 당 평균 지연시간 또한 BEB 알고리즘이 VBS알고리즘 보다 증가폭이 큼을 확인할 수 있다.

표 2는 AP의 통신거리 상에 약 30개의 스테이션이 동시에 데이터를 전송할 때 시뮬레이터에서 측정된 값이다. 시뮬레이션 결과 기존 DCF 알고리즘인 BEB에 비해 재전송횟수가 대략 VBS5는 1/5, VBS10은 1/10로 현저히 감소했다.

네트워크의 전체 평균 처리량은 BEB 알고리즘에 비해 VBS5는 19%, VBS10은 18% 향상 되었다. 패킷 지연 시간 역시 BEB 알고리즘의 1/12로 현격히 감소되었다. 이는 충돌로 인한 재전송이 네트워크의 사용률, 전송지연에 큰 영향을 미침을 알려준다.

최근 다수의 사용자가 이동 중에 네트워크에 접속하는 지하철역과 같은 장소의 무선 네트워크 서비스에서는 IEEE 802.11ai와 같은 빠른 접속을 중요시하는 연구가 진행되고 있으나 기존 IEEE 802.11 매체접근 알고리즘으로는 다수의 사용자가 동시에 네트워크에 접속하였을 경우 데이터의 잦은 충돌로 네트워크의 효율이 저하된다. 따라서 본 논문에서는 네트워크상에 접속된 스테이션의 수에 따라 시작 백오프 스테이지를 설정함으로써 경쟁윈도우의 크기를 조절하는 방식을 통해 데이터의 충돌확률을 줄이는 알고리즘을 제안하였다. 또한 해석적 모델을 제시하고 OFDM을 사용하는 IEEE 802.11g를 대상으로 시뮬레이션을 통해 처리율, 재전송 시도 횟수, 지연시간 관점에서 이를 증명하였다. 시뮬레이션 결과 스테이션 30개의 경우 BEB 알고리즘에 비해 VBS5와 VBS10이 재전송 시도는 각각 1/5, 1/10으로 줄고 이에 따라 패킷의 평균지연이 두 경우 모두 1/12로 줄었다. 제시된 알고리즘을 실제 네트워크에 적용할 경우 AP의 수정이 필요하나 기존의 알고리즘의 큰 변경없이 적용가능하다는 장점을 가진다. 향후 최적 VBFS값을 찾는 연구가 필요하다.