IEEE 802.11s WLAN mesh network의 HWMP 개선을 위한 변화 예측 기반의 효율적인 알고리즘 = An Efficient Algorithm Based on Prediction of Changes for Improvement of HWMP in IEEE 802.11s WLAN Mesh Networks

국문 초록 (Abstract)

IEEE 802.11s WLAN Mesh Network는 기존의 Mobile Adhoc Network(MANET)로부터 영감을 받은 것으로, Mandatory 라우팅 프로토콜로 MAC Layer에서 라우팅을 담당할 수 있도록 한 Hybrid Wireless Mesh Protocol (HWMP)을 사용하도록 하고 있다.
무선 환경에 적합한 라우팅 프로토콜인 IEEE 802.11s HWMP의 경로 선택을 위한 기준은 link에 대한 cost이며, 이는 Airtime Link Metric이라는 것을 통해 산출된다. HWMP의 Airtime Link Metric을 구성하는 요소에는 data rate, protocol overhead, channel access overhead와 frame을 전송 후 재전송된 frame 개수의 비율을 통한 Packet Error Rate(PER)가 있으며, HWMP에서는 이들을 바탕으로 link에 대한 cost를 계산하고 라우팅 테이블을 업데이트하여 적절한 경로를 선택하도록 하고 있다. 다만, HWMP는 아직 완벽한 라우팅 프로토콜이라고 볼 수는 없으며, 여러 가지 개선을 위한 노력 및 연구들이 이루어지고 있다.
본 논문에서는 아직까지 연구되지 않았던 HWMP의 Airtime Link Metric을 구성하는 PER이 무선 환경에서 갖는 특성으로 인해 발생할 수 있는 잠재적인 문제점을 살펴보고, 이를 해결하기 위한 새로운 방법을 제안하였다. 제안된 방법은 network 상황 변화에 대한 예측을 기반으로 link cost를 산출하는 새로운 알고리즘으로 구성되어 있다.
HWMP 개선을 위해 본 논문에서 제안한 새로운 방법의 검증을 위하여, 네트워크 상용시뮬레이터인 Exata에 C++ 기반으로 알고리즘을 구현한 후 시뮬레이션을 수행하였으며, 그 결과 기존의 HWMP 대비 Application Layer와 MAC Layer에서의 전반적인 성능 향상 및 라우팅 오버헤드의 감소를 확인할 수 있었다.

다국어 초록 (Multilingual Abstract)

The IEEE 802.11s is specially composed of a distinguished routing protocol compared to the conventional routing protocols. Basically, the traditional routing protocols are based on the layer 3 called an IP layer; however, the mandatory routing protocol of the IEEE 802.11s is based on the layer 2 called a media access control (MAC) layer instead.
This routing protocol called a Hybrid Wireless Mesh Protocol (HWMP), and HWMP uses Airtime Link Metric appropriate for a wireless environment. This distinguished routing architecture can have many advantages in a wireless environment, and one of the most distinguished advantages is that the wireless properties can be considered for the routing from a MAC layer. However, HWMP has a lot of factors to be considered for better performance.
In this thesis, we showed a potential problem of HWMP due to the fluctuations of the PER and proposed a new algorithm for solving the problem. The new proposed algorithm is based on the network prediction of changes, and furthermore, it considered the congestion situation due to the increase of the number of neighbors.
We implemented the new algorithm to an Exata commercial network simulator for improvement of HWMP and we setup the simulation environments and mesh network scenarios.
From the results, compared to original HWMP, the new algorithm showed better performance of application layer performance metrics and also proved overall improvement of 802.11s MAC layer statistics metrics. Specifically, it showed better throughput, increased packet delivery ratio, shortened end-to-end delay, overall improvement of the routing protocol overhead, and decreased packet drops.

목차 (Table of Contents)

• 목 차 i
• 그림 목차 iii
• 표 목차 iv
• 수식 목차 iv
• 국문 요지 v
• 1. 서론 1
• 2. 배경 지식 및 관련연구 3
• 2.1. Wireless Mesh Network의 소개 3
• 2.1.1. Wireless Mesh Network의 일반적인 특징 3
• 2.1.2. Wireless Mesh Network의 유형 4
• 2.1.3. Wireless Mesh Network의 라우팅 방식 4
• 2.2. Overview of IEEE 802.11s 5
• 2.2.1. IEEE 802.11s의 등장 배경과 표준화 방향 5
• 2.2.2. IEEE 802.11s의 특징과 목적 6
• 2.2.3. IEEE 802.11s Usage Model 7
• 2.2.4. IEEE 802.11s mesh network의 node와 기본 구성 8
• 2.2.5. IEEE 802.11s Mesh의 생성 및 연결 메커니즘 11
• 2.3. IEEE 802.11s Frame formats 14
• 2.3.1. IEEE 802.11s Mesh Data Frame 14
• 2.3.2. IEEE 802.11s Mesh Management Action Frame 15
• 2.4. Hybrid Wireless Mesh Protocol 16
• 2.4.1. HWMP operating mode 16
• 2.4.2. Airtime Link Metric 17
• 2.4.3. HWMP Path Selection Mechanism 18
• 2.5. 802.11s 라우팅 프로토콜 관련 연구 논문 분석 22
• 3. HWMP 개선을 위한 새로운 알고리즘 24
• 3.1. HWMP 라우팅 프로토콜의 잠재적 문제점 24
• 3.2. 네트워크 상황 예측에 대한 필요성 26
• 3.2.1. 네트워크 상황예측을 위한 자료구조 27
• 3.2.2. 네트워크 상황 예측을 위한 data값의 도출 및 특징 28
• 3.2.3. 네트워크 상황 예측을 위한 추가 고려 사항 30
• 3.3. 네트워크 상황 예측 기반의 link cost 도출 함수 31
• 3.3.1. 지수함수를 이용한 새로운 link cost의 산출 31
• 3.3.2. neighbor node수를 고려한 최종 link cost의 산출 32
• 4. 시뮬레이션 및 결과 분석 35
• 4.1. 시뮬레이션 개요 35
• 4.2. 시뮬레이션 환경 설정 35
• 4.2.1. Path Selection 시나리오 1 36
• 4.2.2. Path Selection 시나리오 2 38
• 4.2.3. Path Selection 시나리오 3 39
• 4.3. 시뮬레이션 결과 분석 40
• 4.3.1. Application Layer 성능 Metric 분석 40
• 4.3.2. MAC Layer IEEE 802.11s Statistics 분석 46
• 5. 결 론 53
• 참고 문헌 54
• Abstract 56