논문 2014-51-7-5
IEEE 802.11s 무선 메쉬 네트워크에서 종단간 대역폭 예약을 위한 멀티 인터페이스 멀티 채널 R-HWMP 라우팅 프로토콜
( Multi-Interface Multi-Channel R-HWMP Routing Protocol for End-to-End Bandwidth Reservation in IEEE 802.11s WMNs )
정 회 진*, 김 봉 규***, 이 재 용**, 김 병 철***
( Whoi Jin Jung, Bong Gyu Kim, Jae Yong Lee
ⓒ, and Byung Chul Kim )
요 약
무선 메쉬 네트워크는 인프라 없이 무선 멀티홉으로 네트워크를 구성해야 하는 환경에서 매우 각광받고 있는 기술로서 현 재 IEEE 802.11s 메쉬 네트워크 표준이 제정되었다. 이 표준과 기존 IEEE 802.11과의 큰 차이점 중의 하나는 메쉬 표준에서 QoS를 지원하기 위한 MAC 인 MCCA 가 추가된 것이다. MCCA 는 이웃 노드와의 대역폭 예약을 제공하고 이를 통해 대역 폭 보장의 QoS를 만족할 수 있다. 그러나 MCCA 는 종단간 대역폭을 보장할 수 없는 단점이 있고, 또한 표준에서는 메쉬 노 드가 멀티 인터페이스, 멀티 채널을 지원하는 경우 대역폭 예약 프로토콜과 무선 채널의 예약 방법 등이 규정되어 있지 않다.
이에 본 논문에서는 싱글 인터페이스에서의 종단간 대역폭 예약을 수행하는 예약 기반의 HWMP 프로토콜(R-HWMP)을 멀티 인터페이스, 멀티 채널로 확장한 MIMC R-HWMP를 제안하고, 시뮬레이션을 통하여 멀티 인터페이스를 지원하는 무선 메쉬 네트워크에서 종단간 대역폭의 보장과 인터페이스 확장에 따른 가용 대역폭의 증가를 보였다.
Abstract
Wireless mesh networks have emerged as a key technology in environment that needs wireless multi-hop communication without infrastructure and IEEE 802.11s mesh network standard have currently been established. One of big differences between this standard and the legacy IEEE 802.11 is that MCCA MAC is included to support QoS. MCCA supports bandwidth reservations between neighbors, so it can satisfy the QoS of bandwidth guarantee. However, MCCA has dis-advantages as follow; 1) it can not guarantee end-to-end bandwidth, 2) in multi-interface multi-channel wireless environments, the IEEE 802.11s does not provide a bandwidth reservation protocol and a wireless channel assignment etc.
In this paper, we have proposed MIMC R-HWMP, which expands R-HWMP that was proposed in our previous work[3], to support multi-interface multi-channel. By simulation, we showed end-to-end bandwidth guarantee and the increase in the available bandwidth in multi-interface multi-channel wireless mesh networks.
Keywords: WMN, IEEE 802.11s; Reservation Protocol; QoS; HWMP
* 학생회원, ** 평생회원, 충남대학교 정보통신공학과 (Department of Info. Comm. Engineering, Chungnam National University)
*** 정회원, 국방과학연구소
(Agency for Defense Development)
ⓒ Corresponding Author(E-mail: [email protected])
접수일자: 2014년03월04일, 수정일자: 2014년06월10일 수정완료: 2014년06월23일
Ⅰ. 서 론
무선 메쉬 네트워크는 유선 인프라를 구축하기 어려 운 지역이나, 긴급한 환경 또는 전장에서의 네트워크 구축의 용이성을 제공함으로 최근 많은 연구가 진행되 고 있다.
무선 메쉬 네트워크는 메쉬 라우터와 메쉬 클라이언 트로 구성되며, 메쉬 라우터는 이동성이 적은 특징을 가지고 백본망을 구성한다. 유선 인터넷과 셀룰러, IEEE 802.11, IEEE 802.15, IEEE 802.16, 센서 네트워크 등과의 연동을 위하여 메쉬 라우터는 추가적으로 게이 트웨이와 브릿징 기능을 가질 수 있으며 이런 메쉬 라 우터를 메쉬 포털이라 부른다. 메쉬 클라이언트는 고정 된 형태일 수도 있고, 이동 노드일 수도 있으며, 백본망 과는 다른 클라이언트 메쉬 네트워크를 구성할 수도 있 다. 기본적으로 메쉬 노드들은 호스트로서 동작할 뿐만 아니라 자신의 통신 반경에 위치하지 않은 목적지 노드 까지 데이터를 포워딩해 주기 위한 릴레이 라우터로서 의 기능도 수행한다.
무선 메쉬 네트워크는 애드혹 네트워크와 유사하게 동적으로 자가 구성(self-organized), 자가 설정 (self-configured)되며, 네트워크 내의 모든 노드는 그들 간의 메쉬 연결을 만들고 관리한다. 이와 같은 특징 때 문에 무선 메쉬 네트워크는 적은 초기 구축 비용과 손 쉬운 네트워크 관리, 네트워크 강인성, 신뢰성 있는 서 비스 반경을 제공할 수 있다[1].
무선 메쉬 기술의 표준으로 IEEE 802.11s[2]가 2011년 제정되었고, 이 표준은 물리 계층의 통신 표준과 MAC 계층의 표준으로 EDCA(Enhanced Distributed Channel Access)와 MCCA(MCF Controlled Channel Access)를 권고하고 있다. EDCA 는 IEEE 802.11e에서 사용되던 방식으로 트래픽의 종류에 따라 몇 개의 카테고리로 분 류하여 차별화된 서비스를 제공할 수는 있지만, 대역폭 이나 지연의 보장과 같은 강력한(hard) QoS를 제공하 는 데는 한계가 있다. 이에 반해 MCCA는 이웃 노드와 의 대역폭 예약을 수행하는 TDMA 기반의 MAC 기술 로서 무선 메쉬 네트워크에서 각 노드들 간 채널의 슬 롯을 예약함으로 대역폭의 보장을 확실하게 제공할 수 있다. 그러나 MCCA를 사용하여도 멀티 홉 환경에서 많은 노드들을 경유하는 트래픽의 경우, 종단간의 대역 폭을 보장하지 못 하는 단점이 존재한다. 이에 종단간 의 대역폭 예약을 수행하는 QoS 라우팅 프로토콜인 R-HWMP (Reservation-based HWMP)가 제안되었다
[3]. 그러나 이 또한 인터페이스와 채널이 한 개인 경우 에 한정되어서만 사용이 가능한 제약이 있다.
본 논문에서는 이를 멀티 인터페이스와 멀티 채널 환경에서 사용될 수 있는 MIMC(Multi-Interface
Multi-Channel) R-HWMP로 확장하고, 멀티 채널에서 슬롯 예약을 수행할 때 필요한 몇 가지 슬롯 할당 알 고리즘을 제안하며, 시뮬레이션을 통하여 제안된 프로 토콜의 성능을 분석한다.
무선 메쉬 백본망에서 멀티 인터페이스, 멀티 채널의 적절한 활용에 대한 기존 연구와는 달리, IEEE 802.11s MCCA 프로토콜을 멀티 채널에 활용하며 MCCA의 기 능을 활용하여 종단간 대역폭을 예약하는 QoS 라우팅 프로토콜 방안을 본 논문에서 새롭게 제안한다.
본 논문의 구성은 I장의 서론에 이어, Ⅱ장에서는 IEEE 802.11s 표준의 MAC과 라우팅 프로토콜인 MCCA, HWMP(Hybrid Wireless Mesh Protocol) 그리 고 선행 연구 결과인 R-HWMP에 대해 각각 소개한다.
다음 Ⅲ장에서는 MIMC R-HWMP의 상세한 설계 및 구현 내용을 설명하고, Ⅳ장의 시뮬레이션을 통해 제안 된 프로토콜의 성능을 분석한다. 마지막으로 V장의 결 론으로 본 논문을 마무리한다.
Ⅱ. 관련 연구
이번 장에서는 무선 메쉬 네트워크의 표준인 IEEE 802.11s 의 MAC 프로토콜인 MCCA와 라우팅 프로토 콜인 HWMP에 대해 소개하고, 기존 HWMP 의 문제점 을 보완한 R-HWMP에 대해 기술한다.
1. IEEE 802.11s MCCA[2]
IEEE 802.11s의 MAC 에서는 mandatory MAC인 EDCA와 optional MAC인 MCCA의 두 가지 프로토콜 을 제공한다. EDCA는 IEEE 802.11e에서 사용되던 경 쟁 기반의 채널 접근 프로토콜로서 트래픽에 우선 순위 를 두어 카테고리 별로 처리를 하지만, 사용자가 요구 하는 대역폭, 지연과 같은 QoS 보장은 제공하지 못 한 다. MCCA는 기존의 TDMA 방식과 유사하게 채널의 자원 예약을 통하여 채널에 접근한다. 즉, MCCA가 지 원되는 메쉬 노드는 이를 지원하지 않는 메쉬 노드보다 더 적은 경쟁 확률을 가지고 특정 예약 시간 구간에 채 널에 접근할 수 있도록 하여 대역폭 보장을 제공할 수 있다. 이렇게 예약되는 특정 시간 구간은 MCCAOP (MCCA Opportunity)로 규정되며, 이를 예약하기 위하 여 그림 1과 같이 메쉬 노드들 간의 MCCAOP Setup 과정을 수행한다.
그림 1. MCCAOP 설정 절차 Fig. 1. MCCAOP Setup Procedure.
그림 1에서 MCCAOP Setup Request 프레임을 송신 하는 메쉬 노드를 MCCAOP Owner, 이를 수신하는 메 쉬 노드를 MCCAOP Responder 라고 명명한다.
MCCAOP를 설정하기 위하여 MCCAOP Owner 는 MCCAOP Setup Request 프레임에 예약에 관련된 정 보인 {MCCAOP Duration, Offset, Periodicity, Reservation_ID}를 포함하여 MCCAOP Responder로 송신한다. 이 프레임에서 MCCAOP Duration은 무선 채널에서 사용자가 필요로 하는, 즉 요구 대역폭의 슬 롯의 크기를 의미하고, Offset은 해당 슬롯의 예약이 시 작되는 채널에서의 시작 지점을, Periodicity는 요구 대 역폭의 슬롯 크기를 몇 개의 구간으로 쪼개어 예약할 것인지를 의미하며, 마지막으로 Reservation_ID는 해당 예약 절차를 대표하는 경로 상의 모든 메쉬 노드에서 유일한 ID를 나타낸다. 위와 같은 MCCAOP Setup Request 프레임을 수신한 MCCAOP Responder는 자신 의 예약 상황을 고려하여 요청된 슬롯의 예약이 가능하 면 그림 1과 같이 MCCAOP Setup Reply를 MCCAOP Owner에게 전달함으로 두 메쉬 노드간에 필요한 대역 폭의 예약 설정이 완료된다. 그림 1에서 나타내고 있진 않지만, 설정 과정에서 예약되는 채널 슬롯의 정보는 각 메쉬 노드가 MCCA Advertisement 프레임을 통하 여 모든 이웃 노드에게 브로드캐스팅을 통하여 광고하 여야 한다.
전송할 데이터가 있는 메쉬 노드는 HWMP를 통하여 목적지까지의 경로를 생성하고, 생성된 경로에 위치한 모든 메쉬 노드들 간에 위와 같은 설정 과정을 거쳐 송 수신지 메쉬 노드 간에 요구 대역폭의 보장을 제공할 수 있다. 그러나 MCCA 는 이웃 노드와의 대역폭 예약 만을 제공할 뿐 종단 간의 대역폭 예약은 제공하지 못 하는 단점이 있다. 이를 보완한 종단간의 대역폭 예약
을 제공하는 R-HWMP 프로토콜은 II.3절에서 자세히 설명한다.
2. IEEE 802.11s HWMP
HWMP(Hybrid Wireless Mesh Protocol)는 IEEE 802.11s에서 제안하는 디폴트 라우팅 프로토콜로서 그 림 2의 분류에 나타낸 것과 같이 reactive 방식과 proactive 방식이 조합된 MAC 계층의 라우팅 프로토콜 이다.
그림 2. HWMP 분류 Fig. 2. HWMP Classification.
두 가지 방식 중, proactive 방식은 메쉬 노드 중 하 나를 루트로 선정하여 루트 중심의 트리 경로를 형성하 는 방식으로 메쉬 백본망과 같이 이동성이 적고, 노드 의 수가 비교적 적은 환경에 적합한 방식이고, reactive 방식은 on-demand 방식이라고도 불리며 전송할 데이 터가 있는 경우에 경로 찾기를 수행하는 방식으로 노드 의 이동성이 많은 환경에 적합한 방식이다.
본 논문에서 제안하는 종단간 대역폭 예약 프로토콜 은 reactive 방식의 RM-AODV(Radio Metric-AODV)[4]
를 기반으로 하기 때문에 proactive 방식의 라우팅 프로 토콜은 제외하고, reactive 방식의 라우팅 프로토콜에 대해서만 자세히 기술한다.
RM-AODV 프로토콜에서 사용되는 메시지는 다음과 같은 4가지 종류가 있다.
RANN (Route Announcement): 트리 기반에서 루 트 메쉬 노드와의 거리 및 존재 여부들의 정보를 메 쉬 노드들에게 알려주는 메시지로 브로드캐스팅을 사용함.
PREQ (Path Request): 목적지로 향하는 경로를 찾 고 송신지로 향하는 reverse 경로를 생성하기 위해 송신지에서 목적지로 전송하는 메시지로 경우에 따 라 브로드캐스팅과 유니캐스팅을 구분하여 사용함.
PREP (Path Reply): 목적지로 향하는 forward 경로
를 생성하기 위해 목적지에서 송신지로 전달하는 메시지로, reverse 경로의 확인을 위해 사용하기도 하며 reverse 경로를 따라 유니캐스팅을 사용함.
PERR (Path Error): 송신지와 목적지 사이의 경로 에 문제가 있을 때 사용되는 메시지로 브로드캐스 팅을 사용함.
RM-AODV 는 AODV[5]와 경로 찾기를 수행할 때 사용하는 메트릭이 다르고, 경로 찾기 과정 및 관리 등 의 동작 절차는 동일하며, AODV 는 3계층에서 수행되 고, RM-AODV는 2계층에서 수행되는 차이점을 가진 다. RM-AODV는 reactive PREQ 메시지를 사용하여 경로 찾기가 시작되며, 전송할 데이터를 가지고 있는 경우 수행되고, 목적지까지의 경로를 관리하는 목적의 노드가 별도로 필요하지 않다. 경로 찾기 과정은 AODV와 동일하며 그림 3과 같이 reverse 경로와 forward 경로인 두 경로를 찾는 과정을 가진다.
경로 설정 과정은 전송할 데이터를 가진 송신지에서 PREQ 메시지의 브로트캐스팅에 의해 시작되며, 이때 송신지는 PREQ 메시지 내의 메트릭 필드를 0으로 설 정하고 이를 브로드캐스팅한다. 이를 수신한 메쉬 노드 들은 시퀀스 번호를 비교하여 현재 가지고 있는 송신지 까지 가능한 경로의 시퀀스 번호와 수신된 PREQ 메시 지 내의 시퀀스 번호를 비교하여 현재 시퀀스 번호가 수신된 시퀀스 번호보다 작다면 해당 메쉬 노드는 현재 수신된 송신지까지의 경로가 더 최신 것이라고 생각하 고 해당 경로 정보를 업데이트한다. 또는 시퀀스 번호 는 같지만 PREQ 메시지 내의 메트릭이 더 좋은 값을
그림 3. RM-AODV 경로 찾기 Fig. 3. RM-AODV Path Discovery.
가지고 있을 때도 경로 정보를 새롭게 업데이트 한다.
PREQ 메시지를 수신한 메쉬 노드에서 송신지까지의 경로 정보가 새롭게 생성되거나 업데이트되는 경우, 메 쉬 노드는 이 정보를 브로드캐스팅하여 전체 네트워크 에 PREQ 가 전달되게 한다. 또한 브로드캐스팅하기 전 에 각 메쉬 노드들은 PREQ 메시지 내의 메트릭 필드 를 업데이트해야 한다.
PREQ 메시지를 수신한 목적지를 포함한 모든 중간 메쉬 노드들은 TTL 필드를 1 감소하고, 홉 카운트를 1 증가시키며, 송신지로부터 현재 메쉬 노드까지의 메트 릭을 업데이트한다. PREQ 메시지를 수신한 메쉬 노드 에서 송신지로 가는 경로가 현재 라우팅 테이블에 없다 면 해당 메쉬 노드는 송신지로 가는 경로를 새롭게 라 우팅 테이블에 추가한다.
만약 PREQ 메시지를 수신한 중간 노드가 목적지까 지의 경로를 모두 알고 있다면, 중간 메쉬 노드는 PREP 메시지를 송신지로 전달할 수도 있다. 이때 목적 지 외의 메쉬 노드가 PREP 메시지를 생성해서 전달하 는 것을 원하지 않는다면, PREQ 메시지 내의 TO (Target Only) 플래그를 설정하여 PREQ 메시지를 브 로드캐스팅하면 된다. TO 플래그는 이후 R-HWMP 에 서 종단간 대역폭 예약을 수행하기 위하여 중요하게 사 용되는 플래그이다.
최종적으로 PREQ 메시지를 목적지가 수신하면 목적 지는 PREP 메시지를 생성하여 생성된 reverse 경로를 따라 유니캐스팅으로 송신지까지 전달하며, PREP 메시 지가 송신지까지 전달되면 목적지까지의 forward 경로 가 생성되고, 경로 찾기 과정이 완료된다.
3. Reservation-based HWMP[3]
종단간 대역폭을 예약하는 R-HWMP 프로토콜은 앞 절에서 기술한 RM-AODV를 기초로 한다. 그러나 RM-AODV에서 사용되는 PREQ, PREP, PERR 등의 메시지 포맷의 수정이 필요하고, 경로 찾기와 관리 등 의 알고리즘에 대역폭을 예약하는 등의 추가적인 알고 리즘이 필요하다. R-HWMP의 경로 찾기 과정은 RM-AODV와 유사하게 동작하지만, 경로를 찾기 위한 메트릭으로 가용 대역폭 (available bandwidth)을 검사 하고, 해당 대역폭에 따른 수락 제어 (admission control)을 수행하는 큰 차이점을 가진다. 이에 유선망 에서 제안된 RSVP (Reservation Protocol)[6]에서 사용
하는 TSpec, RSpec을 수정하여 제안된 프로토콜에 적 용하였다. 제안된 프로토콜에서 사용되는 TSpec은 {Token_Bucket_Rate, Token_Bucket_Size, Burst_
Time, Idle_Time, Packet_Size}, RSpec은 {Needed_
Slots}으로 정의한다.
또한 제안된 프로토콜의 동작을 위하여 기존 HWMP 에서 사용하는 PREQ, PREP, PERR 메시지에 TSpec, RSpec을 기입할 수 있는 필드와 SMT(Slot Map Table), 그리고 플로우의 ID 필드, 마지막으로 예약이 실패했음을 알릴 수 있는 Reservation_Failed 필드를 PERR 메시지에 추가한다. 이로써 모든 메쉬 노드는 SMT를 이용하여 자신이 사용할 수 있는 유휴 슬롯 (idle slots)을 계산할 수 있고, 이 값은 경로 찾기 과정 에서 가용 대역폭의 유무를 검사할 때 사용하게 된다.
앞 절에서 언급한 RM-AODV의 경로 찾기 과정과
그림 4. 싱글 인터페이스에서의 PREQ 절차 Fig. 4. PREQ Procedure in Single Interface.
유사한 방식으로 메쉬 노드들은 경로 찾기를 수행하면 서 reverse 경로(목적지에서 송신지로의 경로)를 생성 할 때, 대역폭 예약이 가능한 지를 점검하고 수락제어 를 수행한다. 이때 예약을 수행하지는 않으며 목적지에 서 PREP를 송신자 쪽으로 보내면서 forward 경로를 생성할 때, 다시 한 번 예약이 가능한 지 수락제어를 하 고, 이때 가능하다면 필요한 대역폭 예약을 수행하게 한다.
수락 제어는 reverse 경로를 생성할 때 한번 수행하 고, 다시 forward 경로를 생성할 때 한번 더 수행하여 잘못된 대역폭 예약을 방지할 수 있다. 각 메쉬 노드에 서 PREQ 메시지를 수신하였을 때의 동작 절차는 그림 4와 같고, PREP 메시지를 수신하였을 때의 동작 절차 는 그림 5와 같다.
그림 4에 나타낸 것과 같이 PREQ를 수신한 메쉬 노 드는 가장 먼저 플로우 ID(FID)와 시퀀스 번호를 검사 하고, RM-AODV에서 사용되는 Airtime 링크 메트릭의 값을 비교한 후, 요구 대역폭을 만족하는 가용 대역폭, 즉 슬롯의 수를 검사한다. 가용 대역폭을 만족할 수 없 으면 해당 PREQ를 버리고, 만족할 수 있으면 FID (Flow_ID)를 확인한 후, reverse path entry를 생성하고 PREQ를 re-broadcasting한다. PREQ가 목적지까지 전 달될 때까지 위의 과정을 반복 수행하고, 목적지는
그림 5. 싱글 인터페이스에서의 PREP 절차 Fig. 5. PREP Procedure in Single Interface.
PREQ를 수신하면, 일정 시간 기다린 후 가장 적은 Airtime 메트릭을 가지는 PREQ에 대한 PREP를 생성 하여 송신지까지 전달하며 forward path entry를 생성 한다. 이때 forward path entry를 생성하면서 한번 더 수락제어를 수행하며 실제 MCCA를 통한 대역폭 예약 을 수행한다. 만약 다중 경로를 통해 여러 개의 PREQ 가 수신되는 경우에도 목적지는 가용 대역폭을 만족하 고 최소 Airtime 메트릭을 가지는 하나의 경로만을 선 택하게 된다. 만약 PREQ 메시지가 목적지까지 전달되 기 전에 중간 노드에서 어떤 이유로 버려지게 된다면 송신지는 PREP를 수신하지 못 하고 타임아웃이 발생 하고 새로운 PREQ를 생성하여 경로 찾기 과정을 재수 행한다.
그림 5는 PREP를 수신한 노드의 절차로서, 먼저 PREP를 수신한 노드는 동일한 FID를 가진 플로우에 대해 최신의 PREP인지를 확인하고, Ⅲ장의 수식 (1)을 통하여 계산된 요구대역폭의 필요 슬롯인 만큼 채널 의 슬롯을 예약한다. 위의 과정을 송신지가 PREP를 수 신할 때까지 거쳐 최종적으로 송신지와 목적지 사이의 forward 경로가 생성되고 해당 경로에 요구대역폭의 예 약 절차가 완료된다.
Ⅲ. MIMC R-HWMP 설계
이 장에서는 앞서 설명한 R-HWMP를 멀티 인터페 이스, 멀티 채널로 확장한 MIMC R-HWMP 의 설계에 대해 기술한다. MIMC R-HWMP 프로토콜 역시 종단 간 대역폭의 보장을 기본 목적으로 하되, R-HWMP 에 서 지원되지 않던 멀티 인터페이스, 멀티 채널의 확장 을 주요 설계 내용으로 한다.
1. 개요
제안하는 MIMC R-HWMP 에서 인터페이스의 수는 참고문헌 [7]에서 가정한 것과 같이 3개로 고정하고, 각 인터페이스 별로 서로 겹치지 않는 하나의 채널을 고정 적으로 할당하여 사용함을 가정한다. 또한 각 채널에서 사용 가능한 여유 슬롯은 채널 간의 공유는 허락되지 않고, 각 플로우에 필요한 슬롯은 선택된 하나의 채널 내에서 예약됨을 원칙으로 한다. 향후 각 인터페이스에 동적으로 채널을 할당하는 방안이 연구되어야 하며, 각 채널 별 슬롯을 공유하여 사용하는 슬롯 할당 알고리즘
그림 6. PREQ 형식 Fig. 6. PREQ Format.
그림 7. PREP 형식 Fig. 7. PREP Format.
등이 추가적으로 연구되어야 한다. 본 논문에서는 싱글 인터페이스를 멀티 인터페이스로 확장함으로 링크의 가 용 대역폭 증가에 따른 성능 분석에 초점을 맞추며, 또 한 기존 연구들에서 시도하지 않았던 MCCA를 멀티 인 터페이스에 적용하는 데 의의를 둔다.
MIMC R-HWMP에서 사용되는 메시지인 PREQ, PREP, PERR의 기본 형식은 R-HWMP와 동일하되, 각 메쉬 노드의 SMT는 멀티 채널로 확장되어야 한다. 먼 저 PREQ, PREP 메시지에 TSpec , RSpec을 기입할 수 있는 필드와 모든 채널의 aggregate SMT를 그림 6, 7 과 같이 추가한다.
그리고 PERR 메시지에는 예약이 실패했음을 알릴 수 있는 Reservation_Failed 필드를 그림 8과 같이 추가 한다. 다음 각 메쉬 노드들이 관리하는 라우팅 테이블 의 필드에는 대역폭 예약에 필요한 SMT, Flow_ID를 추가한다. 각 메쉬 노드들은 SMT를 사용하여 각 채널 에 사용할 수 있는 여유 슬롯을 계산할 수 있으며, 계산 된 여유 슬롯의 값은 경로 찾기 과정에서 가용 대역폭 의 유무를 검사할 때 사용하게 된다.
Multi-rate을 지원하는 IEEE 802.11a/g에서 시그널링 을 위한 컨트롤 패킷은 가장 작은 date rate 6Mbps 에 서 전달된다. IEEE 802.11s 표준에서 1 슬롯의 크기를
그림 8. PERR 형식 Fig. 8. PERR Format.
32㎲로 규정하고 있으므로, 100 슬롯을 컨트롤 슬롯으 로 할당한다면 최대 2400 바이트만큼 전송이 가능하다.
PREQ, PREP, PERR 메시지의 크기는 그림 6의 Target Count 필드 값, 그림 6, 7의 SMT 크기, 그림 8의 Reason Code 필드 값에 따라 가변적이기는 하지만, 메 쉬 노드의 인터페이스 수가 3개이고, 채널이 3개인 경 우에는 그 크기가 최대 수십 바이트 내외이기 때문에 본 논문에서 컨트롤 슬롯을 여유있게 100 슬롯으로 결 정하였다.
즉 채널 1, 2, 3에서 각 채널의 슬롯 수가 1000이라 고 하면, 채널 1의 일부분인 100 슬롯은 시그널링을 위 한 컨트롤 슬롯으로 사용되고 나머지 900 슬롯은 데이 터 슬롯으로 사용되며, 나머지 채널 2, 3은 1000 슬롯 을 모두 데이터 슬롯을 위해 사용된다. 경로 찾기 및 경로 관리를 위한 시그널링에 필요한 컨트롤 슬롯은 고정적으로 할당하며 첫 번째 채널의 일부분이 할당됨 을 가정한다.
2. Path Discovery
경로 찾기를 위한 시그널링 절차는 첫 번째 채널의 컨트롤 슬롯을 사용하며 R-HWMP의 경로 찾기 절차 와 유사하게 수행된다. 다만 채널의 수가 하나가 아니 기 때문에 가용 대역폭의 계산과 수락 제어가 각 채널 별로 동작되어야 하는 차이를 가진다.
전송할 데이터를 가진 메쉬 노드가 먼저 PREQ 메시 지를 생성하여 브로드캐스팅한다. 이때 PREQ 메시지 내에 TSpec 정보를 기입하고, TO 플래그를 설정하여 중간에 위치한 메쉬 노드들은 목적지까지의 경로를 알 고 있더라고 PREP를 바로 송신지로 전달할 수 없도록 한다. 이는 중간 메쉬 노드가 알고 있는 목적지까지의 경로가 해당 요구 대역폭을 만족하는지를 알 수 없기 때문에 최소한 한번은 목적지까지 PREQ 메시지가 전 달되어야 함을 의미한다.
PREQ 메시지를 수신한 메쉬 노드의 동작 절차는 그
그림 9. 멀티 인터페이스에서의 PREQ 절차 Fig. 9. PREQ Procedure in Multi-Interface.
림 9에 나타내었다. 모든 동작은 그림 4에 나타낸 싱글 채널에서의 동작과 동일하지만, 각 채널 별로 해당 동 작을 반복 수행하는 기능이 추가되었다. 해당 채널 별 로 가용 대역폭을 계산하고 수락 제어를 채널의 여유 슬롯이 가장 많은 채널부터 내림차순으로 수행하게 되 며, 중간 채널에서 요청된 대역폭의 예약이 가능하면 모든 채널에서 수락 제어를 수행하지 않고 바로 다음 절차인 경로 업데이트를 수행한다.
만약 가용 대역폭이 많더라도 트래픽 전송을 위한 연속된 슬롯을 할당할 수 없다면 다음 채널을 검색하 는 방법을 수행한다. 이 알고리즘은 연속된 슬롯의 크 기가 큰 채널 순으로 검색을 하면 동일한 효과를 얻을 수 있다.
다음으로 그림 10에 나타낸 PREP를 수신한 메쉬 노
그림 10. 멀티 인터페이스에서의 PREP 절차 Fig. 10. PREP Procedure in Multi-Interface.
드들의 동작 절차 역시 그림 5에 나타낸 싱글 채널에서 의 동작과 동일하지만, PREQ 동작 절차와 같이 모든 채널에서의 반복 수행될 수 있는 기능이 추가되었다.
PREQ 의 처리 절차와 마찬가지로 채널 별로 수락 제 어를 수행할 때, 모든 채널이 검사가 다 끝나지 않아도 요구 대역폭을 만족할 수 있는 채널이 선택되면 다음 채널의 검사는 수행하지 않고 바로 해당 대역폭의 예약 을 수행함으로 대역폭 예약에 걸리는 시그널링 오버헤 드를 줄일 수 있다. PREQ 수신 시, 가예약을 수행하지 않기 때문에 PREP를 수신하는 노드는 PREQ 수신시와 동일하게 다시 한 번 수락 제어를 수행하게 되는데, 이 는 그동안 채널 상태가 바뀔 수 있기 때문이다.
만약 중간 메쉬 노드의 모든 채널에서 요구 대역폭을 만족할 수 없으면 해당 메쉬 노드는 PERR 메시지에 Reservation_Failed 플래그, Flow_ID를 추가하여 예약 할 수 없음을 목적지까지 형성된 forward 경로를 따라 전달한다. PERR 메시지가 전달되는 forward 경로 상의 모든 메쉬 노드들은 해당 Flow_ID에 대한 경로를 삭제 하고, 예약되었던 슬롯을 모두 반환한다.
PREQ 메시지를 전송하고 PREP 메시지를 기다리고 있는 송신지는 일정 lifetime 동안 PREP 메시지가 수
신되지 않으면 예약이 실패하였음을 인지하고, 다시 한 번 PREQ 메시지를 브로드캐스팅함으로 새로운 경로 를 찾는 과정을 반복 수행한다. 송신 노드가 7번 예약 을 시도한 후 경로 선택에 최종적으로 실패하면 전송 을 취소하거나 경쟁 기반의 예약 없이 보내는 방안을 시도한다.
PREP 메시지가 정상적으로 송신지까지 전달이 되면, 경로 찾기 과정을 통하여 reverse, forward 경로가 모두 생성되고 송신지에서 요구한 대역폭을 만족할 수 있는 슬롯의 예약이 정상적으로 수행된 것이다.
송신지에서 요구 대역폭의 슬롯의 수를 도출하기 위 해서는 R-HWMP 에서 사용된 다음과 수식 (1)을 사용 한다.
×
×
(1)
위의 수식 (1)에서 는 요구 대역폭을 만족하기 위 해 필요한 슬롯의 수이고, 는 한 DTIM 구간에서 전송되는 패킷의 개수, 은 데이터 패킷의 전송 시간, 은 ACK 패킷의 전송 시간, 은 한 슬롯의 시간 크기를 의미한다[3].3. Path Maintenance
제안된 MIMC R-HWMP 의 경로 관리 알고리즘은 첫 번째 채널의 컨트롤 슬롯을 사용한 주기적인 관리용 HELLO 메시지의 브로드캐스팅을 통하여 수행된다.
HELLO 메시지 내에 각 채널의 SMT를 포함하여 광고 하고, 메쉬 노드의 이동이나 링크의 변경에 따른 링크 의 상황을 광고한다. 이를 수신한 모든 주변 메쉬 노드 들은 자신의 SMT의 업데이트를 수행하고 이에 따른 여유 슬롯의 수를 재계산한다. 또한 HELLO 메시지는 TTL 필드를 1로 설정하여 자신의 1홉 이웃 노드들에 게만 전송하고, HELLO 메시지 내의 SMT 는 항상 최 신으로 업데이트한 후에 추가한다.
예를 들어, 다음 그림 11과 같이 4개의 노드로 구성 된 멀티홉 체인 토폴로지에서 0번 노드가 3번 노드로 하나의 플로우를 보낼 때 채널 1의 슬롯이 그림과 같이 예약이 되어 전송된다고 하면, 각 노드들이 가지고 있 는 SMT는 그림에 나타낸 것과 같다. 이런 경우에 2번
그림 11. 경로 관리 예제
Fig. 11. Path Management Example.
노드의 전송이 완료되어 더 이상 예약된 슬롯을 사용하 지 않는다면, 이를 반영한 관리용 HELLO 메시지를 브 로드캐스팅한단. 이를 수신한 이웃 노드들은 해당 노드 에 의해 사용할 수 없었던 슬롯들을 다시 사용할 수 있 게 반환하여 SMT의 업데이트를 수행한다. 주기적인 관리용 HELLO 메시지를 전송하는 노드의 1홉 이내의 노드들에서 이 메시지를 수신하면 자신의 1홉 이내의 노드들이 사용하는 또는 간섭받는 슬롯을 파악하여 자 신의 SMT를 업데이트할 수 있게 된다. 이렇게 함으로 노드의 이동이나 예약 정보의 갱신, 링크의 단절에 의 한 영향을 SMT에 항상 최신을 반영할 수 있고, 또한 해당 경로의 정보를 항상 최신으로 유지할 수 있다.
4. Admission Control
수락 제어는 모든 메쉬 노드에서 PREQ와 PREP 메 시지를 수신하면 요구 대역폭을 만족하는 각 채널의 가용 대역폭 (여유 슬롯)을 검사함으로 수행된다.
PREQ 메시지를 통하여 reverse 경로를 찾을 때, 가용 대역폭을 가진 메쉬 노드라 하더라도 가예약을 수행하 지 않기 때문에 PREP 메시지를 통한 forward 경로를 생성할 때 네트워크 환경의 다양한 이유로 인해 가용 대역폭이 없을 수 있다. 그렇기 때문에 수락 제어는 PREQ, PREP 메시지를 처리할 때 두 번에 걸쳐 수행 해야 한다.
5. Slot Assignment
요구 대역폭을 만족하는 여유 슬롯이 여러 채널에 있 는 경우, 어떤 채널의 슬롯을 사용할 것인지 결정하여 야 하는 슬롯 할당 알고리즘의 경우 다양한 방안이 제 시될 수 있다.
먼저 싱글 채널에서의 슬롯 할당 알고리즘 중, best fit 알고리즘은 사용할 수 있는 여유 슬롯의 크기를 만.
족하는 가장 작은 곳부터 슬롯을 할당하여 남아 있는 여유 슬롯의 크기를 크게 유지하는 방식이다. 그렇기 때문에 best fit 알고리즘은 이후 플로우가 요청하는 슬 롯의 크기가 큰 경우에 큰 장점을 가질 수 있다. 반면 random fit 알고리즘은 여유 슬롯의 크기를 만족하는 모든 곳 중에서 랜덤하게 선택을 하여 슬롯을 할당하는 방식으로 여유 슬롯의 낭비가 발생할 수 있다[8].
멀티 채널에서의 슬롯 할당 알고리즘으로 first fit 알 고리즘을 제안한다. First fit 알고리즘은 채널이 개인 경우, 어떤 채널에서 best/random fit 알고리즘을 적용 할 것인지 먼저 결정을 하고, 그 후 해당 슬롯 할당 알 고리즘을 적용한다. 즉, 채널 할당의 경우 채널의 가용 대역폭의 크기로 결정을 먼저 하고 그 후 위에 언급한 슬롯 할당 방안을 그 채널에 적용한다. 따라서 가용 대 역폭이 가장 많이 남아 있는 채널에 대하여 먼저 슬롯 을 할당함으로 한 채널 내에 플로우들의 간섭을 최소화 할 수 있고, 또한 부하를 분산시킬 수 있는 장점을 가질 수 있다.
그림 12는 인 경우의 예제로서 한 프레임 내 슬롯의 수가 1000 이고, 컨트롤 슬롯의 크기가 100 슬 롯이라고 하면, 채널 1은 기존에 사용되고 있는 300 슬 롯(주황색)과 컨트롤 슬롯(빨간색)을 제외한 600슬롯이 사용 가능하고, 채널 2와 채널 3은 컨트롤 슬롯이 없으 므로 기존에 사용되고 있던 슬롯을 제외한 각각 900 슬 롯과 750 슬롯이 사용 가능하다. 예를 들어 6개의 플로 우가 각기 다른 요구 대역폭을 가진다면 first fit 알고
그림 12. First-fit 알고리즘의 사용 시 슬롯 할당 위치 Fig. 12. Slot assignment locations with first-fit algorithm
채널 초기 여유 슬롯
f1 (200)
f2 (350)
f3 (200)
f4 (400)
f5 (100)
f6 (250)
Ch. 1 600 600 600 600 600 500 500
Ch. 2 900 700 700 500 100 100 100
Ch. 3 750 750 400 400 400 400 150
표 1. 각 플로우의 요청 슬롯과 각 채널 별 여유 슬 롯
Table 1. Required slots for each flow and free slots at each channel.
리즘(best fit 적용)이 적용된 후의 각 채널의 슬롯 상태 는 표 1과 같다.
먼저 여유 슬롯이 가장 많은 채널에 대하여 best fit 알고리즘을 적용하여 슬롯을 할당할 수 있는 지 검사하 고, 있다면 그곳에 할당하고 알고리즘은 종료되며, 그렇 지 않다면 다음으로 여유 슬롯이 많은 채널로 이동하여 best fit 알고리즘을 반복 수행한다. 그림 11과 표 1에서 f1은 플로우 1, …, f6은 플로우 6을 나타내고, 각 플로 우가 요청하는 슬롯의 개수는 표 1에서 괄호 안에 나타 내었다. 각 플로우는 플로우 1부터 플로우 6까지 순차 적으로 요청이 되었다고 가정한다. 플로우 1의 경우 요 청하는 슬롯의 수는 200이고 초기 여유 슬롯이 각 채널 별, 600, 900, 750이기 때문에, 두 번째 채널에 플로우 1 의 200 슬롯이 할당된다. 다른 플로우들도 차례대로 여 유 슬롯이 가장 많은 채널에 우선 할당되며, 특히 플로 우 4의 요청 슬롯을 할당할 때는 채널 1이 여유 슬롯의 양이 가장 많지만 400 슬롯을 할당할 연속적인 여유 슬 롯이 없기 때문에 그 다음으로 여유 슬롯이 많고 연속 적인 슬롯 할당이 가능한 채널 2에 할당을 한다. 플로 루 6도 마찬가지로 채널 1이 가장 많은 여유 슬롯을 가 지지만 250 슬롯을 할당할 수 있는 연속적인 여유 슬롯 이 없기 때문에 채널 3에 할당을 한다. 만약 여러 채널 에서 연속적인 여유 슬롯이 동일하다면 두 채널 중 랜 덤하게 채널을 선택한다.
표 1은 각 채널의 초기 여유 슬롯의 양과 각 플로우 의 요구 슬롯이 할당된 후의 각 채널 별 슬롯 상태를 나타낸 것이다.
멀티 채널에서의 random fit 알고리즘도 best fit과 동일한 방식으로 수행된다. 즉 멀티 채널 환경에서 각 채널은 독립적으로 동작하고, 채널 간의 슬롯의 공유는
허락되지 않다고 가정한 것이며, 채널 간의 슬롯을 공 유하여 할당하는 방식은 향후 연구 이슈로 남겨 둔다.
Ⅳ. 성능 분석
제안된 MIMC R-HWMP 의 성능을 분석하기 위해 메쉬 노드 4개를 체인 형태(0-1-2-3)로 구성하였다.
각 노드가 가지고 있는 인터페이스와 채널의 수는 3으 로 고정하였으며, 노드 간 링크의 대역폭은 6Mbps로 설정하였다. 즉 3개의 인터페이스를 통한 가용 대역폭 이 싱글 인터페이스일 때보다 약 3배 정도 향상되었다.
또한 각 플로우는 CBR 1Mbps 로 생성하고, 패킷의 크 기는 1000 바이트로 하였으며, 슬롯 할당 알고리즘은 III.5절에서 제안한 first-fit 알고리즘을 사용하였다.
먼저 멀티 인터페이스 멀티 채널이 플로우의 처리율 에 순수하게 미치는 영향을 분석하기 위하여 멀티 홉 체인 토폴로지에서 플로우 6개를 0번 노드에서 3번 노 드로 CBR 1Mbps 로 생성하여 전송할 때, 제안된 프로 토콜을 적용하지 않고 싱글 인터페이스와 멀티 인터페 이스를 사용하는 경우의 실험 결과를 그림 13에 나타냈 다. 그림 13에서 상단 그래프는 싱글 인터페이스의 경 우로 플로우들 간의 간섭과 멀티홉에 따른 성능 감소로 모든 플로우의 처리율이 약 200Kbps로 생성된 트래픽 양인 1Mbps 에 크게 미치지 못함을 알 수 있다. 그림 13의 하단 그래프는 멀티 인터페이스의 경우로 싱글 인 터페이스와 동일하게 플로우들 간의 간섭과 멀티홉에 따른 성능 감소를 보이긴 하지만, 인터페이스와 채널이 3배로 증가하였기 때문에 각 플로우의 처리율이 약 500Kbps로 싱글 인터페이스와 비교해 약 2.5배 이상 향 상된 것을 알 수 있다. 하지만 역시 충돌 기반의 자원 공유를 수행하기 때문에 송신 노드의 발생 트래픽을 효 과적으로 전송하지 못함을 알 수 있다.
제안된 프로토콜을 적용하지 않은 멀티 인터페이스 멀티 채널 노드에서의 채널 선택은 각 플로우별로 라운 드 로빈 방식으로 선택되도록 하였다.
다음은 제안된 프로토콜의 종단간 대역폭 보장을 검 증하기 위하여 멀티 인터페이스 환경에서 6개의 플로 우 중 3개의 플로우는 제안된 프로토콜을 사용하여 대 역폭 예약을 수행하고 나머지 3개의 플로우는 예약을 수행하지 않는 경우에서 실험을 수행하였다. 각 플로우 는 CBR 1Mbps를 생성하여 0번 노드에서 3번 노드로
그림 13. 대역폭 예약을 하지 않은 경우 실험 결과 Fig. 13. Simulation results without bandwidth reservation.
그림 14. MIMC R-HWMP의 처리율 결과 Fig. 14. Throughput Results of MIMC R-HWMP.
전송하였다. 실험 결과는 그림 14와 같으며 제안된 프 로토콜을 사용하여 대역폭 예약이 수행된 3개의 플로 우는 1Mbps의 대역폭을 모두 만족하고, 나머지 3개의 플로우는 그림 13의 상단 그래프에 나타낸 싱글 인터 페이스에서 트래픽 처리율과 비슷하게 보이는 것을 알 수 있다.
이것은 멀티 인터페이스에서 제안된 프로토콜을 적 용한 플로우들이 채널의 슬롯을 먼저 예약하여 사용하 고 기존 플로우들은 예약하고 남은 슬롯을 사용하기 때 문에 제안된 MIMC R-HWMP를 사용하는 경우 각각 의 인터페이스에 1Mbps가 예약되고, 나머지 대역폭을 예약되지 않은 3개의 플로우가 경쟁하여 사용을 하는 것이다.
위의 실험 결과들을 토대로 싱글 인터페이스를 멀티 인터페이스로 확장한 경우 제안된 프로토콜인 MIMC R-HWMP를 통하여 대역폭 예약을 수행하면 성능 보 장이 이루어지면서 좀 더 많은 플로우들을 수용할 수 있다는 것을 알 수 있다.
향후 멀티 인터페이스 멀티 채널 환경의 무선 메쉬
네트워크가 구축되었을 때 선행 연구로 제안된 R-HWMP와 본 논문에서 제안된 MIMC R-HWMP를 활용하면 실시간 멀티미디어 응용들에 대한 종단간 대 역폭을 효과적으로 제공할 수 있을 것이다.
Ⅴ. 결 론
본 논문에서는 선행 연구인 종단간 대역폭 보장을 위 한 R-HWMP 라우팅 프로토콜을 멀티 인터페이스, 멀 티 채널을 지원할 수 있도록 확장하였다. 제안된 MIMC R-HWMP 에 추가적으로 싱글 채널에서의 슬 롯 할당 알고리즘을 멀티 채널로 확장하였다. 멀티 인 터페이스로 확장된 무선 메쉬 노드는 인터페이스에 채 널을 할당하는 알고리즘이 추가적으로 필요하지만, 본 논문에서는 인터페이스의 각 채널은 고정적으로 할당된 다고 가정하였으며, 향후 동적인 채널 할당 알고리즘에 대해 연구를 진행할 것이다.
제안된 MIMC R-HWMP는 멀티 인터페이스에 IEEE 802.11s MCCA MAC 프로토콜을 적용한 최초의 프로토콜이며, 이를 활용할 경우 무선 메쉬 노드가 멀 티 인터페이스를 장착한 경우에도 MCCA 가 제공하는 대역폭 보장을 제공받을 수 있고, 제안된 프로토콜을 통하여 종단간의 멀티 인터페이스를 통한 대역폭을 보 장할 수 있다. 향후 멀티 인터페이스가 장착된 무선 메 쉬 노드로 구성된 메쉬 네트워크가 구축된다면 제안된 프로토콜을 사용하여 대역폭 보장의 QoS를 제공할 수 있을 것으로 생각한다.
REFERENCES
[1] I. F. Akyildiz, X. Wang, and W. Wang,
“Wireless mesh networks: a survey,” Comput.
Networks, vol. 47, no. 4, pp. 445–487, Mar.
2005.
[2] “Specific requirements Part 11 : Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 10 : Mesh Networking.” IEEE Standard 802.11s-2011.
[3] W. J. Jung, S. H. Min, B. G. Kim, H. S. Choi, J.
Y. Lee, and B. C. Kim, “R-HWMP:
Reservation-based HWMP supporting end-to-end QoS in Wireless Mesh Networks,” in The International Conference on Information
저 자 소 개 정 회 진(학생회원)
2005년 충남대학교
전기정보통신공학부 학사 2007년 충남대학교
정보통신공학과 석사 2010년～현재 충남대학교 전자
전파정보통신공학과 박사과정
<주관심 분야 : 무선 메쉬 네트워크, 미래인터넷, 이동인터넷, 이동통신>
이 재 용(평생회원)-교신저자 1988년 서울대학교 전자공학과 학사
1990년 한국과학기술원 전기 및 전자공학과 석사
1995년 한국과학기술원 전기 및 전자공학과 박사
1990년～1995년 디지콤 정보통신 연구소 선임연구원
1995년～현재 충남대학교 정보통신공학부 교수
<주관심분야 : 초고속통신, 인터넷, 네트워크 성 능분석>
김 봉 규(정회원)
1993년 대구대학교 전자공학과 학사
2010년 충남대학교 정보통신 공학과 석사
2010년～현재 충남대학교 전자전파정보통신공학과 박사과정
1993년～현재 국방과학연구소 연구원
<주관심 분야 : 네트워크 성능분석, 무선메쉬 네 트워크, 이동통신>
김 병 철(평생회원)
1988년 서울대학교 전자공학과 학사
1990년 한국과학기술원 전기 및 전자공학과 석사
1996년 한국과학기술원 전기 및 전자공학과 박사
1993년～1999년 삼성전자 CDMA 개발팀
1999년～현재 충남대학교 정보통신공학부 부교수
<주관심 분야 : 이동인터넷, 이동통신 네트워크, 데이터 통신>
Networking 2013 (ICOIN), 2013, pp. 385–390.
[4] L. Feng, Z. Qian, and D. Jin, “Performance analysis of IEEE 802.11s wireless mesh network on RM-AODV path selection protocol,” in 2011 IEEE 3rd International Conference on Communication Software and Networks, 2011, pp. 135–139.
[5] S. Das, E. Belding-Royer, and C. Perkins, “Ad hoc on-demand distance vector (AODV) routing,” IETF RFC 3561, 2003.
[6] J. Wroclawski, “The Use of RSVP with IETF Integrated Services Status,” IETF RFC 2210, 1997.
[7] R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks,”
Proc. 10th Annu. Int. Conf. Mob. Comput. Netw.
- MobiCom ’04, p. 114, 2004.
[8] C. Cicconetti, L. Lenzini, and E. Mingozzi,
“Scheduling and Dynamic Relocation for IEEE 802.11s Mesh Deterministic Access,” in 2008 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, 2008, vol. 19, pp.
19–27.
