논문 06-31-10B-03 한국통신학회논문지 06-10 Vol.31 No.10B 무선 메쉬 네트워크 환경에서 효율적인 다중 홉 전달 기법 정회원 김 영 안, 박 철 현, 종신회원 홍 충 선 An Effective Multi-hop Relay Algorithm in Wireless Mesh Network Young-an Kim*, Chul-Hyun Park* Regular Members, Choong Seon Hong** Lifelong Members 요 약 무선 메쉬 네트워크(Wireless Mesh Network) 기술은 유선과 비슷한 전송속도를 갖은 무선 통신 기술을 이용해 서 무선 백본망으로 사용하는 기술을 의미하며, 토폴로지는 메쉬 형태를 갖는다. 이러한 형태는 Ad-hoc네트워크와 유사한 점을 가지고 있지만, 운용목적과 내부동작에서 다르기 때문에 경로 설정 방법과 경로를 설정하기 위한 메 트릭이 요구 된다. 본 논문에서는 데이터를 전달하기 위한 루프가 없는 효율적인 다중 홉 전달을 위한 다중 경로 생성 방법과 Hop-by-hop 라우팅기법을 기반으로 경로설정을 하고 물리적인 링크의 성능과 다중 홉 전달을 위한 메트릭(ETR : Expected Transmission Rate)을 제안한다. Key Words : Wireless Mesh Network, Ad-hoc, Hop-by-hop, Metric, Expected Transmission Rate ABSTRACT The Wireless Mesh Network uses a wireless communication technology with transmission rates similar to that of a cable, which is used as a backbone network. The topology structure is in a Mesh form which resembles an Ad-hoc network, however a metric is needed in order to set the channel and channel methods since the operation intentions and interior motions are different. This thesis proposes a metric(etr : Expected Transmission Rate) that sets the channel with physical link performance and multi hop transmission capabilities. This metric will also be based on multi channel creation methods and Hop-by-hop routing techniques for an effective multi hop transmission with no loops. Ⅰ. 서 론 최근 무선 통신 기술의 발달로 사용자는 보다 쉽 게 인터넷에 연결 할 수 있게 되었다. 전송 속도 또한 유선과 비슷한 대역폭을 가질 수 있기 때문에 무선 통신 기술을 이용한 무선망을 백본으로 사용 하고자 하는 연구가 진행 되고 있다 [1-4]. 무선 메쉬 네트워크는 노드들이 무선으로 연결되 어 통신한다는 점에서 Ad-hoc과 비슷한 점을 가지 고 있지만 무선 메쉬 네트워크는 하위 단말들에 대 한 기본 연결 구조를 제공하는 것에 초점을 두고 있다. 이러한 기술은 유선을 설치하기 힘든 섬지역 이나, 군에서 전장지역과 같은 넓은 지역에 저렴한 비용으로 인프라를 제공할 수 있다. 이러한 네트워크 구조는 메쉬 노드로 서로 연결 되어 있으며, 메쉬 노드는 다른 망과 연결되기 위해 브리지(Bridge) 역할과 연결 고리가 되는 게이트웨 이(Gateway) 역할을 하며 무선 백본 망으로서 역할 을 수행한다. 기존의 Ad-hoc네트워크의 노드와는 다르게 이동성이 거의 없고 에너지 제한도 없는 특 이 연구는 이 논문은 2006년 정부(교육인적자원부)의 재원으로 한국학술진흥재단의 지원을 받아 수행된 연구임(KRF-2006-521-D00394). * 경희대학교 컴퓨터공학과 박사과정 (roundsun@networking.khu.ac.kr) ** 경희대학교 전자정보학부 교수 (cshong@khu.ac.kr) ( : 교신저자) 논문번호:KICS2006-08-351, 접수일자:2006년 8월 21일, 최종논문접수일자:2006년 10월 17일 872
논문 / 무선 메쉬 네트워크 환경에서 효율적인 다중 홉 전달 기법 성을 지닌다. 또한 메쉬 노드 사이에는 데이터의 흐 름이 많고, 특히 QoS를 만족시켜야 하는 트래픽이 많이 존재 한다. 그래서 무선 메쉬 노드는 데이터를 전송하기 위해, 성능이 좋은 경로를 찾아 해당 메쉬 노드에 전달해야 한다. 그리고 좋은 경로는 메쉬 노 드 간에 연결되어 있는 링크로 구성되어 있다 [3-5]. 따라서 본 논문에서는 PHY/MAC의 정보를 이용 한 링크의 성능을 정량화 할 수 있는 방법과 이 정 보를 이용한 라우팅 방법에 대해서 제안한다. 본 논문의 구성은 다음과 같다. 2장에서는 무선 메쉬 네트워크에 대한 기본적인 동작 과정을 설명 하고 3장에서는 라우팅 프로토콜의 종류와 라우팅 메트릭의 종류에 대해 설명하고 4장에서는 경로 설 정 방법과 데이터 전달 메트릭에 대해 제안한다. 5 장에서는 제안모델에 대한 성능평가 결과를 보여주 고 6장에서는 결론을 맺는다. Ⅱ. 무선 메쉬 네트워크 무선 메쉬 네트워크는 Ad-hoc네트워크와 달리 하위 노드들에게 인터넷에 접속할 수 있는 인프라 스트럭처를 제공하기 위해 연구되고 있는 네트워크 의 형태이다. 즉 유무선 망의 백본을 그림 1에서와 같이 무선 메쉬 네트워크를 이용함으로서 전송속도 와 링크의 신뢰성을 높이는데 목적을 두고 있다. 네트워크는 메쉬 라우터(Router) 또는 릴레이 (Relay)로 구성되어 있으며, 이웃 메쉬 라우터/릴레 이들과 1:1접속이 아닌 다중 접속을 허용하는 형태 로 구성되어 있으며, 메쉬 라우터/릴레이는 직접 또 는 간접적으로 인터넷에 연결되어 메쉬 라우터/릴레 이에 접속된 단말들에서 인터넷 서비스를 제공한다. 무선 메쉬 네트워크는 무선 상의 고정 또는 이동 성 노드로 구성되며, 정의된 토폴로지에 의해 무선 백본으로 수행한다. 무선 메쉬 네트워크의 하위 구 그림 1. 무선 메쉬 네트워크 조는 기존의 무선기술 IEEE 802.11a/b/g 또는 무선 센서네트워크, 유선랜 구조가 될 수 있다. 또한 이 네트워크에서 성능향상을 위해서 여러 개의 게이트 웨이를 통해 인터넷에 연결된 형태를 가질 수 있다. Ⅲ. 라우팅 방법과 메트릭 3.1 라우팅 프로토콜의 종류 무선 메쉬 네트워크를 위한 라우팅 방법으로 크 게 두 가지로 생각해 볼 수 있다. On-demand 라우 팅 방법 [11-12] 과 Proactive 라우팅 방법이다 [15]. 그리 고 데이터를 전달하는 방법에 따라서 Proactive 라 우팅 방식은 크게 두 가지로 나누어진다. Source Routing방법과 Hop-by-hop방법이다. 이러한 라우팅 방법은 알고리즘에 따라서 메시지의 오버헤드 및 경로를 유지하기 위한 관리상의 복잡성을 갖는다. On-demand방식은 Ad-hoc네트워크를 위한 경로 설정 방법으로 제안되었다. DSR(Dynamic Source Routing), AODV(Ad hoc On-demand Distance Vector), LBAR(Load-Balanced Ad-hoc Routing), DLAR(Dynamic Load-Aware Routing)과 같은 방 법이 대표적이다 [7][9][11]. 이 방법은 송신노드가 수신 노드로 데이터를 전송할 필요가 있을 때, 송신노드 와 수신노드의 경로를 설정한다. 경로를 찾기 위해 서 네트워크상에는 많은 경로 탐색 메시지가 발생 된다. Ad-hoc네트워크에서는 노드의 이동성 때문에 경로탐색 메시지를 발생 시키는 방법을 기반으로 설계되었다. 하지만 무선 메쉬 네트워크는 노드의 이동에 따른 경로에 대한 오류가 없기 때문에, 이전 에 검색된 경로를 반복해서 찾게 된다. 이런 방법은 큰 오버헤드를 발생 시킨다. 그러므로 on-demand기 반의 라우팅 프로토콜은 무선 메쉬 네트워크에 적 합하지 않다. Proactive라우팅 방법은 각각의 노드는 다른 노드 로 전달하기 위한 라우팅 테이블을 가지고 있다. 모 든 노드의 라우팅 테이블은 최신의 정보로 업데이 트하기 위한 방법을 가지고 있으며, 네트워크의 토 폴로지가 변하면 노드들은 이 정보를 주변 노드들 에게 전달하며, 모든 노드들은 이 정보를 업데이트 함으로서 최신의 정보로 갱신한다. 이 라우팅 방법 은 데이터를 전달하는 방법에 따라서 두 가지로 구 분할 수 있다. 첫째로 Source Routing 방법은 송신노드가 데이 터를 전달하기 위한 라우팅 정보를 계산하고 이 라 우팅 정보를 헤더에 포함해서 전달함으로서 데이터 873
한국통신학회논문지 06-10 Vol.31 No.10B 를 목적지까지 전달한다. 대표적인 프로토콜은 LQSR (LinkQuality Source Routing)이다 [3-4]. 중간 노드는 단지 헤더의 정보를 참조해서 다음 노드로 전달하 기만 하면 된다. 하지만 프레임의 페이로드가 줄어 들게 된다. 둘째로 Hop-by-hop 라우팅 방법은 모든 노드가 목적지까지 전달하기 위한 다음 홉의 정보를 모두 가지고 있다. 중간 노드는 헤더의 목적지 정보를 참 조해서 자신이 가지고 있는 라우팅 정보의 다음 홉 으로 프레임을 전달하면 된다. 간단한 방법이기 때 문에 오버헤드가 적으며, 무선 메쉬 네트워크에 적 합하다. 하지만 라우팅 메트릭을 설정하는 단계에 있어서 루프가 발생 될 수 있으므로 루프를 피할 수 있는 방법이 필요하다. 3.2 다중 경로 프로토콜 기존의 경로 설정 방법에서 경로에 대한 신뢰성 을 높이기 위해서 다중 경로 설정 방법에 대해서 연구 되어 왔다. 이는 기본적으로 링크나 노드에 대 해서 비겹침 경로를 선택함으로서 하나의 경로가 오류가 생겼을 때, 대체 경로를 선택하는 방법으로 동작한다. 이에 대한 연구는 SMR(Split Multipath Routing), AOMDV(Ad-hoc On demand Multipath Distance Vector), AODVM(Ad-hoc On demand Distance Vector Multipath Routing)이 있다 [6]. 하지 만 이러한 방법은 기본적으로 2개의 경로를 설정을 하고 있으며, 경로 설정을 위해서 경로요청 메시지 를 주변에 플러딩하는 방법을 사용하기 때문에, 무 선 메쉬 네트워크에 적합하지 않다. 3.3 로드 밸런생 프로토콜 네트워크의 성능을 최대로 사용하기 위해서 로드 밸런싱 기법이 필요하다. 노드의 로드(Load)를 고려 하는 라우팅은 설정된 경로에 대한 트래픽 로드를 경로 설정 메트릭에 사용한다. 이것은 네트워크의 트래픽 분산효과를 가져옴으로서 결국 전체 네트워 크의 처리량을 감소시키게 된다. On-demand방식의 라우팅 프로토콜에서 경로설정 기준이 최단거리가 아닌 전체 네트워크의 성능향상을 고려하는 QoSaware라우팅 프로토콜이 제안되고 있다. QoS-aware 메트릭에는 지연 변화, 대역폭, 패킷 로스 확률 등이 있다. 지금까지 제안된 이동 노 드의 로드를 고려하는 프로토콜에는 DLAR, LBAR, LSR(Load-Sensitive Routing) 등이 있다 [9-11]. 이동 노드의 로드를 고려한 라우팅 프로토콜은 기존의 DSR, AODV와 같은 캐시 메커니즘을 사용 하지 않는다. 캐시 메커니즘은 중간 노드들이 자신 의 라우팅 테이블에 기존에 설정된 경로 정보를 담 아 가지고 있음으로서 또다시 같은 경로를 요청하 는 패킷이 수신되었을 때 즉시 응답해줌으로서 경 로 설정시간을 줄이는 방법이다. 하지만 이러한 방 법은 시간이 오래 지남에 따라 잘못된 경로 정보를 가질 수 있고, 같은 경로를 선택하는 이동 노드가 증가함에 따라 경로에 로드가 증가하게 된다. DLAR은 이동 노드의 로드를 해당 노드의 인터 페이스 큐에 있는 패킷의 개수로 계산한다. LBAR 에서는 해당 노드뿐만 아니라 이웃 노드를 통과하 는 경로의 개수를 모두 합한 수를 해당 노드의 로 드 정보로 사용한다. LSR은 해당 노드와 이웃노드 의 인터페이스 큐에 있는 패킷의 수를 이동 노드의 로드로 정의하고 있다. DLAR은 이웃노드간의 액세 스 경쟁을 고려하지 않았으며, LBAR, LSR은 DLAR의 개념에 액세스 경쟁을 고려한 방법이다. 3.4 라우팅 메트릭의 종류 라우팅 프로토콜에 의해서 좋은 경로를 선택하기 위해서 여러 가지 메트릭이 이용된다. 목적지의 홉 카운트, RTT(Round Trip Time), PktPair(Packet Pair Delay), ETX(Expected Transmission Count), ETT(Expected Transmission Time)와 같은 메트릭 을 기반으로 경로를 결정하게 된다. 홉 카운트를 이 용하는 방법으로는 손실과 대역폭을 고려하지 않는 다 [4]. 즉 신뢰성이 높거나 다른 전송속도를 가진 경 로를 고려하지 않는다. RTT를 이용하는 방법은 Round Trip Time을 측정하는데 오버헤드가 크며, 무엇보다 링크상의 전송 속도를 고려하지 않는다. 또한 Probe패킷을 통해 RTT를 계산하기 때문에, 채널 점유율이 높아진다. PktPair은 RTT와 마찬가 지로 Probe패킷을 사용한다. ETX는 단지 손실률만 고려하고, 각각 링크에 대한 대역폭은 고려하지 않 는다. 즉 각기 다른 대역폭을 갖는 무선 메쉬 네트 워크 환경에는 적합하지 않다. ETT는 ETX의 단점 을 보완하기 위해서 제안되었다. 이것은 ETX를 기 반으로 하여, 데이터의 전송시간을 예측하여 전송하 는 방법이다. 링크에 대한 대역폭을 고려하여 경로 를 선택한다. 하지만 위에서 거론된 방법들은 링크의 성능만을 고려할 뿐, 로드에 대한 고려를 하지 않고 있다. 무 선 메쉬 네트워크에 존재하는 모든 노드들이 좋은 링크들로만 구성된 경로를 선택하여 데이터를 목적 874
논문 / 무선 메쉬 네트워크 환경에서 효율적인 다중 홉 전달 기법 지 또는 게이트웨이까지 전송한다면 대부분의 노드 들은 중복된 경로를 통해서 전송하게 되며, 이 경로 에 많은 부하가 걸리게 되므로 네트워크 전체에 성 능 저하를 가져오게 된다. 이러한 성능 극복을 위해서 본 논문에서는 다중 경로 설정 알고리즘과 Hop-by-hop 전송 메트릭인 ETR(Expected Transmission Rate)를 제안한다. Ⅳ. 제안하는 경로설정 방법 및 ETR 본 장에서는 무선 메쉬 네트워크 환경에서 데이 터를 전달하기 위한 루프가 없는 다중 경로 설정 알고리즘과 Hop-by-hop 라우팅기법을 기반으로 경 로설정을 하고 물리적인 링크의 성능과 부하분산을 고려한 ETR(Expected Transmission Rate)를 이용해 서 데이터를 다음 홉으로 전달하는 방법에 대해서 제안한다. 4.1 다중 경로 설정 방법 제안하는 경로 설정 방식은 목적지로 가는 다음 홉 정보가 여러 개가 존재하므로 경로에 문제가 발 생되더라도 곧바로 다른 경로를 사용할 수 있기 때 문에 데이터 전송에 신뢰성이 높고, 여러 경로를 가 지는 Hop-by-hop 전달 구조에서 루프가 존재 할 수 있다. 단순히 홉 카운트가 적은 경로를 선택하면 루프를 피해 전송되지만, 링크의 품질을 기반으로 전송하는 네트워크 구조에서 홉 카운트와 상관없이 전송하면 루프가 발생가능하다. 그리고 데이터를 보 내기 전에 다음 홉을 선택하여 전달하기 때문에 홉 간 다중 경로가 선택되어 데이터 분산의 효과를 얻 을 수 있다. 그리고 단일 경로로 구성된 노드(이웃 이 2개인 노드)인 경우 축약해 한 홉으로 간주함으 로서 Hop-by-hop의 문제점을 해결할 수 있다. 전달 경로 테이블에 대한 업데이트는 초기 네트워크가 시작되거나 새로운 메쉬 노드가 참여하거나 탈퇴하 는 경우 즉, 토폴로지의 변화가 생긴 경우에만 수행 된다. 메쉬 노드가 데이터를 외부로 보내기 위해서는 게이트웨이로 데이터가 전달되어야한다. 이 경로는 Forward Path과정에서 설정되며, 각각의 노드는 자 신의 이웃만큼의 경로를 가지게 된다. 즉 노드는 자 신의 이웃으로 데이터를 전달함으로서 게이트웨이까 지 전달이 가능하다. 하지만 게이트웨이로 데이터를 전달하기 위해 중 간 이웃노드들에게 전달하는 과정에서 잘못된 이웃 C E 48 48 48 A G/W G/W advertisement Message D 1 st Relay Msg. 48 2 nd Relay Msg. 48 3 rd Relay Msg. B F GW_Addr Hop_Count Path Bandwidth Relay Seq. No. 그림 2. 경로 설정 방법 에게 전달한다면, 루프를 그리면서 전달이 되거나, 멀리 돌아갈 수 있다. 이러한 경우를 피하기 위해서 Primary Path와 Backup Path를 구성한다. 그림 2에 서 굶은 선 경로는 Primary Path이며 가는 선 경로 는 Backup Path이다. 자세한 Path결정은 알고리즘 에 의해 결정된다. Backup Path는 Primary Path로 데이터를 전송할 수 없는 오류상황에만 사용한다. Primary Path : 데이터를 목적지(Gateway)로 전 달하기 위해 성립된 Path로 데이터를 전송하면 데이터 전송 시 루프가 일어나지 않는다. Backup Path : 데이터를 목적지로 전달하기 위 해 성립된 Path로 Primary Path가 고장일 때만 사용하며 다른 노드를 우회하는 경로로서 루프 가 일어날 수 있는 경로이다. 게이트웨이 광고 메시지는 다음과 같은 정보로 구성된다. Gateway Address : 게이트웨이주소를 나타낸다. Hop Count : 게이트웨이 전달경로의 홉-카운트 를 나타낸다. Path Bandwidth : 게이트웨이까지의 전달 경로 의 최대 대역폭을 나타낸다. Message Sequence Number(MSN) : 게이트웨이 가 보내는 새로운 메시지임을 의미한다. 이전 에 MSN보다 현재 수신한 메시지의 MSN이 높으면 현재 수신한 메시지가 새로운 메시지임 을 나타낸다. Relay Sequence Number(RSN) : 메시지가 게이 트웨이로부터 전달되어질 때 메쉬 노드로부터 전달된 횟수를 의미한다. 이 정보를 기반으로 Primary Path와 Backup Path를 구분한다. 메시 노드는 광고 메시지를 처음 수신 후, 그 메시 지를 송신한 노드를 제외하고 모든 이웃 노드 에게 RSN을 1증가시켜 이웃들에게 전달한다. 자신이 전달한 메시지의 RSN보다 큰 RSN이 설정된 광고 메시지로부터 설정된 경로는 875
한국통신학회논문지 06-10 Vol.31 No.10B Backup Path로 설정한다. 이는 우회하여 게이 트웨이로 전달되는 경로이기 때문이다. 단, 자 신의 이웃이 2개가 존재한다면, 해당노드는 독 립된 단일 경로 상에 존재하므로 단일 경로상 의 노드들은 한 Hop으로 간주하기 때문에 RSN을 증가하지 않고 전달한다. 게이트웨이 광고 메시지는 그림 3의 알고리즘과 같은 절차로 전달되어, Forward Path를 설정한다. 1 게이트웨이는 자신을 이웃 노드에게 광고한다. 2광고 메시지는 수신한 이웃 노드는 이전에 수신한 메시지인가를 Message Sequence Number을 검 사한다. Current MSN >= Previous MSN 이전에 수신한 메시지이면 메시지를 버리고, 새로 운 메시지이거나 현재 처리하고 있는 메시지이면 다음을 실행한다. 3 광고메시지의 Relay Sequence Number (RSN) 검사해서 처음 수신한 메지시면 Hop count를 1증가시키고 이웃노드와의 대역폭과 경로 대 역폭 중에서 작은 값으로 전달(Relay) 테이블 에 저장하고 RSN을 1증가 시켜 이웃 노드에 게 전달한다. 4 자신이 RSN을 증가시켜 보낸 메시지보다 RSN이 큰 값이 설정된 메시지는 다른 노드를 우회하여 전달되는 메시지이다. 자신에게 없는 Next_hop을 가지고 있다면 Next_hop을 이용 하는 저장된 전달 경로가 있다면 버린다. 그림 4. 전달(Relay) 경로 테이블 52~4까지의 과정을 반복하여 Primary Path와 Backup Path를 설정하고, 모두 설정된 노드는 위의 과정을 그만둔다. 그림 4는 Forward Path 설정 단계를 통해 생성 된 기본적인 전달(Relay)경로 테이블이다. 각 메쉬 노드는 자신의 이웃을 통해 전달할 수 있는 신호의 세기로 성립된 최상의 대역폭으로 전달할 수 있는 전달 경로는 갖는다. 메쉬 노드 A는 Primary Path 2개만을 가지지만 D와 같은 경우 Primary Path 3 개와 링크 실패시에 사용할 수 있는 백업 전달 경 로(회색) 2개를 가진다. 그리고 Reverse Path설정 과정은 Forward Path설정 과정과 동일하다. 4.2 데이터 전달 메트릭 ETR은 다음 홉으로 전달 기대되는 링크의 전송 속도를 의미한다. 고려되는 요소로는 신호의 세기로 결정되어지는 채널 전송 속도(참고로, 802.11a는, 48, 36, 24, 18, 12, 9, 6)와 링크 채널의 오류율(PER : Packet Error Rate), 그리고 이전 기간 동안 해당 메쉬 노드가 생성한 트래픽 볼륨(Traffic Volume) 그리고 이웃들로부터 데이터를 받아 전달한 트래픽 볼륨의 요소를 이용해서 다음과 같은 값을 구할 수 있다. ETRi (Expected Transmission Rate) = (Bandwidthi * (1-PERi)) (Traffic Volume + Relay Traffic Volume) 그림 3. Path 설정 알고리즘 Bandwidth : 물리적 신호의 세기를 기반으로 변 조방법 결정 후 설정으로 인해 결정된 대역폭 PER : 무선 링크가 가지는 오류율 Traffic Volume : 해당 노드가 단위시간당 전송 한 데이터의 양(또는 예약한 양) 876
논문 / 무선 메쉬 네트워크 환경에서 효율적인 다중 홉 전달 기법 Relay Traffic Volume : 다른 노드에 의해 예약 하지는 않았지만 경유한 단위시간당 트래픽의 양을 의미한다. ETR은 물리적인 대역폭과 오류율 그리고 메쉬 노드에서 자체적으로 사용하는 대역폭과 해당 노드 를 경유노드로 사용하는 노드로부터 예약된 대역폭 을 더한 값이다. 즉, 이 노드를 경유해서 데이터를 보낼 때, 자신이 전송 할 수 있는 기대되는 대역폭 이다. 수식은 크게 두 가지 부분으로 나눌 수 있다. (Bandwidth i * (1-PER i))는 링크에 대한 오류율을 통해서 물리적으로 수용 가능한 대역폭을 의미한다. 메쉬 노드에 여러 개의 인터페이스가 설치되어 있 을 수 있기 때문에 모든 대역폭을 더해줘야 한다. 트래픽 볼륨은 해당노드에 의해서 예약(또는 이전 단계에서 전송한 단위시간당 데이터의 양)이며 Relay Traffic Volume는 해당 메쉬 노드를 경유한 트래픽의 양을 의미한다. 무선 메쉬 노드는 자신의 ETR과 PER을 이웃들 에게 전달하기 위해서 위와 같은 방법을 이용해서 데이터를 전달하게 된다. 제안한 경로 설정 방법과 ETR기반 전송을 위한 링크 상태 전달 메시지를 802.11에 적용하기 위해 서는 다음과 같은 메시지의 포맷을 갖추어야한다. 게이트웨이 광고 메시지를 정의하면 그림 5와 같다. 광고메시지에 대한 갱신을 위해서 MSN을 사용하 며, 광고 메시지가 이웃노드를 경유하는 정보인가를 알기 위해서 RSN을 사용하며, 경로 설정을 위해서 홉 카운트와 경로 대역폭을 사용한다. 2 2 6 6 6 2 0-2312 4 Frame Duration DA SA BSS ID Sequence Frame Body FCS Control Control 그리고 링크에 대한 정보를 이웃들에게 전달하기 위해서 비콘메시지에 담아서 전달할 수도 있지만 PER과 ETR을 비콘에 함께 전달하면, 이를 지원하 지 않는 장비와의 호환성에 문제가 될 수 있다. 그 래서 다음과 같은 추가적인 메시지가 요구되며, 이 웃들에게만 전달되고, 크기가 작기 때문에 네트워크 성능에 거의 영향을 미치지 않는다. 2 2 6 6 6 2 1 1 4 Frame Duration DA SA BSS ID Sequence PER PER FCS Control Control ETR을 이용한 데이터 전송은 데이터를 실제로 보낼 때, ETR을 기반으로 고려하지만, 테이블에 기 입된 BW도 역시 고려한다. BW는 다음 홉이 가지 는 최대 대역폭을 의미한다. 다음 홉의 ETR이 높더 라도 BW값이 가지는 값이 작다면, 좋은 전송 속도 일 수 없다. 경로 상에서 가지는 BW값이 ETR보 다 작으면, BW값을 ETR로 취한다. 각 노드가 가지는 ETR값은 그림 6과 같다. 전송 예제는 간단히 하기 위해서 A가 처음 데이터를 전 송하고, PER은 모두 0으로 가정한다. A가 ETR값 을 참조해서 C->E->GW1로 데이터를 전달한다. F 는 데이터를 전달할 때 GW1로 데이터를 전달한다. B가 데이터를 전달하는 최적의 경로는 D->F->GW1 의 경로이지만, F의 ETR값이 24로 감소함으로서 D 에서 ETR값이 48인 GW1으로 바로 이동하는 경로 를 선택함으로서 B->D->GW1으로 전달하는 경로를 선택하게 된다. A 48 B C 48 D 48 E 48 48 F GW1 A ETR 77 Next BW ETR Dst. Hop CBW PER Traffic Volume 25 C BW1 3 29 77 0 Relay Traffic Volume B BW1 3 48 102 0 0 B ETR 102 Next BW ETR Dst. Hop CBW PER Traffic Volume 0 D BW1 2 150 0 Relay Traffic Volume F BW1 2 48 48 72 0 0 C ETR 77 Next BW ETR Dst. Hop CBW PER Traffic Volume 0 E GW1 2 29 77 0 Relay Traffic Volume A D GW1 2 48 48 150 0 25 25 D ETR 150 Next Dst. Hop BW ETR PER GW GW 1 48 48 48 0 Traffic Volume E GW 2 48 48 29 0 Relay Traffic Volume F GW 2 24 0 0 E ETR 77 Next BW ETR Dst. Hop CBW PER Traffic Volume GW1 GW 1 29 29 0 Relay Traffic Volume A D GW1 2 48 48 102 0 25 25 1 1 1 1 Message Sequence umber Relay Sequence Number 그림 5. 802.11 적용을 위한 메시지 포맷 Hop Counter Path Bandwidth 그림 6. ETR를 이용한 전송 예제 F ETR 72 Next BW ETR Dst. Hop CBW PER Traffic Volume 30 GW1 GW 1 24 24 0 Relay Traffic Volume D GW1 2 48 48 96 0 0 877
한국통신학회논문지 06-10 Vol.31 No.10B Ⅴ. 성능 평가 본 장에서는 ns-2를 이용한 시뮬레이션을 통해서 기존에 제안되었던 단일경로, 이중경로 방법과 제안 한 라우팅 방법 및 ETR과의 성능 평가를 한다. 본 논문에서는 고대역의 무선 네트워크 환경으로 구성 장비의 성능에 대한 제약이 없기 때문에, 전파 지연 및 네트워크 디바이스로 인한 지연은 상당히 작은 변수이기 때문에 고려하지 않는다. 성능평가 항목에는 네트워크 신뢰성, 관리 메시 지의 수, 중간 노드의 로드 변화, 게이트웨이에서의 성능평가를 수행한다. 무선 메쉬 네트워크의 채널 사용 및 매체 접근 방법에 대한 표준화가 진행 중 인 관계로 인해서 표준화된 방법이 존재하지 않고, 성능에 커다란 변화를 가져오지 않으므로, 이에 관 한 요소들은 생략하였다. 5.1 네트워크 신뢰도 그림 7과 같이 네트워크를 구성하고 있을 때, 송 신지 S가 목적지 D로 데이터를 보낼 때 가지는 네 트워크의 신뢰도를 검증하기 위한 그림이다. 그림 7-a는 DSR, AODV와 같은 단일경로 설정을 기반 으로 함으로 공통적인 네트워크 신뢰도를 갖는다. 또한 그림7-b는 다중경로 설정방법의 비겹침 방법을 이용해서 경로를 설정한 방법이다. 이 방법은 분리 된 2개의 경로를 설정하게 된다. 그림7-c는 제안한 방법을 이용하여 데이터를 전송할 때 가지는 경로 를 나타내며, 더 많은 경로의 개수를 가짐으로서 더 높은 신뢰도를 가진다. 단일 경로 기반은 링크에 대한 동작 확률이 p일 때 S-A-B-C-D 또는 S-F-G-H-D 등으로 설정될 수 있는데 이는, 4 hop을 가짐으로서, Rel(경로 1개) = p4, p = 링크의 동작 확률의 네트워크 신뢰도를 갖는다. 다중 경로 기반의 경로 설정 방법은 비겹침 방식으로 경로를 설정하고 기 본적으로 2개의 경로를 설정한다. 이가 가지는 경로 는 S-A-B-C-D와 S-F-G-H-D로 될 수 있으며, 다른 경로의 쌍으로 설정될 수 있다. 네트워크 신뢰도는 다음과 같은 값을 갖는다. Rel(경로 2개) = 2p 4 - p 8, p = 링크의 동작 확률 (2) 제안한 방법은 각 노드가 목적지로 전달하기 위 한 모든 경로를 가지므로 네트워크의 신뢰도는 Rel(제안방법) = 4p 4-2p 6-4p 8 + 4p 10 - p 12 (3) 이며, 각각에 대해서 비교한 그래프는 다음과 같다. 그림 8에서도 알 수 있듯이 단일경로, 다중경로, 제안방법 순으로 네트워크의 신뢰도가 높은 것을 알 수 있다. 각 링크의 신뢰도가 0.2일 때 까지는 별로 차이가 없지만, 그 이상 증가할 때는 링크의 오류에 따른 경로의 신뢰도는 차이가 많이 난다. 이 는 경로 이상으로 인한 경로탐색에 대한 오버헤드를 줄일 수 있으며, 메쉬 노드의 이상으로 인한 내구력 을 가지고 있다. 즉 한 노드의 링크에 오류가 발생 해도 다른 노드는 지속적으로 서비스가 가능하다. 이러한 점은 무선 메쉬 네트워크에서 중요하다. 네트워크 관리 목적 또는 예기치 못한 장비 오류 및 정전으로 인한 경우, 다른 노드는 지속적으로 서 비스가 가능하다. 만약 다른 장비의 이상으로 인해, (a) (b) 1 0.9 경로 1개 경로 2개 0.8 제안 방법 (c) 그림 7. 경로 설정 방법 RelSrc,Dest = Prob(any path from Src to Dest) = 1 - Prob(all paths failed) (1) Graph Reliability. 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Link operating probability 그림 8. 네트워크 신뢰도 878
논문 / 무선 메쉬 네트워크 환경에서 효율적인 다중 홉 전달 기법 주변의 많은 노드가 고장 난다면, 무선 메쉬 네트워 크의 장점이 사라진다. 제안한 Hop-by-hop 다중 경 로를 이용함으로써 네트워크의 전반적인 안정성을 가져올 수 있다. 5.2 관리 메시지의 수 제안한 방법에서 링크의 상태를 이웃들에게 알리 고 유효하게 보존하기위해 전달되는 메시지의 수는 관리 메시지의 수 = n N i (4) i =1 n은 노드의 수, Ni은 노드 i의 이웃의 수를 나타 낸다. 즉 네트워크를 구성하는 노드의 이웃들의 합 만큼의 관리 메시지가 발생된다. 그림 9를 살펴보면, 노드의 수가 증가함에 따라 관리 메시지의 수는 거의 일정하게 증가 된다. On-demand방식으로 경로를 설정하면, 이웃들에게 경로요청메시지를 전달하고 경로를 설정함으로 한 노드가 경로를 유지하기 위해서, 목적지에서 가장 멀리 있는 노드가 제안한 방법과 같은 메시지를 발 생 시킨다. 모든 노드들이 경로를 유지하고 로드를 인지하기 위한 메시지를 보낸다면 네트워크에는 상 당히 많은 경로 유지 메시지가 흘러 다니게 된다. 그림 9. 관리 메시지의 수와 노드 수의 관계 5.3 중간 노드의 로드 변화 표 1은 Ad-hoc 환경에서 대표적인 라우팅 프로 토콜인 AODV과 로드정보를 고려해서 경로를 설정 하는 DLAR과 제안하는 ETR기반의 Hop-by-hop 전송할 때, 중간 노드에 로드의 변화하는 과정에 대 한 실험이다. 네트워크는 25개의 노드로 구성되어 있으며, 노드 S가 목적지 GW로 데이터를 전송하는 시나리오이다. 실험은 100초 동안 지속되며, 50초에 서 중간 노드의 로드가 변화한다. 로드의 패킷 크기 S : Source Node, GW : Gateway Node 표 1. 시뮬레이션 파라미터 주요변수 값 토폴로지 5 x 5 Grid Topology 노드의 수 25 개 노드간의 거리 50 m 전송 거리 50 m MAC Protocol 802.11 Packet Size 1000 byte 패킷 생성율 200 packet/sec, UDP 대역폭 2 로드 이벤트 50 초에서 는 1000byte이며, 200packet/sec로 생성되며, 10초 단위로 DLAR과 제안하는 방식은 로드 감지를 위 한 절차를 수행한다. 실험은 3번 수행하고, 평균값 을 이용하였다. 로드가 변하는 이벤트가 발생하기 전까지는 유사한 성능을 갖는다. 변화하는 로드에 대한 동작이 없는 AODV가 가장 좋은 성능을 갖는 다. 이는 로드 감지에 대한 오버헤드가 발생하지 않 기 때문이라고 생각된다. DLAR은 가장 낮은 성능 을 보여줬는데, 이는 로드 검사를 위해서 네트워크 전반에 메시지를 RREQ/RREP메시지를 브로드캐스 트하고 최적의 경로를 선택하기 때문이다. 50초에 각각의 경로설정 방법에 따라서 선택된 경로의 한 노드에 1000byte이며, 200packet/sec의 로드가 걸리 는 경우(자체 트래픽이나 외부에서 유입된 트래픽), 실험 시작 후 60초에서 Throughput이 급격하게 하 락한다. 하지만 로드 변화에 대한 동작이 정의된 DLAR과 제안한 방법의 경우는 로드 변화에 따른 다른 경로를 설정함으로서 기존의 전송속도를 회복 한다. 하지만 AODV와 같은 경우는 주기적으로 경 로를 재구성하기 위한 메시지 브로드캐스트를 통해 서 로드 변화에 적응하기 때문에, 제안한 방법보다 낮은 성능을 보여준다. 이는 경로를 재설정하기 위 한 노드는 1개만 존재하는 설정이지만 네트워크의 모든 노드가 재설정하기 위한 메시지를 전송한다면, 네트워크 성능은 급격히 저하될 것이다. 879
한국통신학회논문지 06-10 Vol.31 No.10B 표 2. 기존 방식 vs. 제안방식 그림 10. 중간 노드의 로드변화에 따른 Throughput 5.4 게이트웨이에서 성능 측정 이번 시나리오는 그림 2와 같은 네트워크 토폴로 지에서 게이트웨이에서의 성능을 평가한다. 현재 시 뮬레이션 환경은 무선 메쉬 환경과 채널에 대한 표 준이 없으므로, 성능평가하기 위한 특징으로 대역폭, 링크성능, 전송데이터 고려하여 시뮬레이션을 실시 하였다. 그래프를 살펴보면, E가 데이터를 보내는 시점에 서 제안 방법을 이용하면 병목 현상 없이 데이터를 전송함으로서 링크의 성능을 최대한 사용한다. 하지 만 ETT를 기반으로 한 DSDV를 방법을 이용한 방 법을 이용한 전송 방법은 ETT가 좋은 경로를 이용 하는 노드가 증가함으로서 병목현상으로 인해 네트 워크 성능의 저하를 가져왔다. 180 160 140 Throughput 120 DSDV Link Capacity 100 80 GW에서 Throughput 60 40 20 0 A B C D E F 트래픽발생노드 그림 11. 네트워크 Throughput 5.5 기존 라우팅 프로토콜과 비교 표 2는 제안 방법과 기존 경로 설정 방법에 대한 비교분석표이다. Ad-hoc 네트워크에서는 이동성이 란 커다란 성질 때문에 Table Driven방식이 아닌 On Demand 방식을 기반으로 해서 경로 설정 방식 들이 연구되었다. 하지만 무선 메쉬 네트워크는 고 정된 장소에 설치되어 하위 노드에게 서비스를 제 알고리즘 Path Matric Load Balancing Multi- Destination (Gateway) AODV one path Hop count DSR one path Hop count DSDV one path Hop count SMR multi path 짧은지연/ 비겹침노드 AOMDV multi path 짧은지연/ 비겹침노드 AODVM multi path 짧은지연/ DLAR one path 비겹침노드 경로상의 큐의 패킷수 다중경로의 트래픽분산 다중경로의 트래픽분산 다중경로의 트래픽분산 경로설정시 트래픽분산 LBAR one path 경로의 수 경로설정시 로드 감지 전송 경로설정시 LSR one path 범위의 로드 감지 큐의 수 ETR이 큰 제안방법 multi path ETR 경로설정 공한다. 그렇기 때문에 On Demand방식으로 동작할 필요가 없어졌다. 그리고 무선 메쉬 네트워크의 장 점을 살리기 위해서는 다중 경로를 이용한 부하 분 산(Load Balancing)을 지원하는 방법이 뒷받침되어 야 한다. 또한 무선 메쉬 네트워크에서는 인터넷과 연결된 여러 개의 게이트웨이가 존재 할 수 있는데, 일반 메쉬 노드는 게이트웨이를 인지할 방법이 없 다. 제안한 경로 설정 방법은 게이트웨이의 광고 메 시지로 메쉬 네트워크의 노드가 사용하는 Forward Path를 설정함으로 다중 게이트웨이를 지원한다. Ⅵ. 결 론 Ad-hoc네트워크를 기반으로 연구된 경로 설정 방법들은 이동 무선 네트워크에 초점이 맞춰서 연 구되었다. 즉, 무선 네트워크를 효율적으로 사용 하 는 것 보다는, 노드의 에너지 절약, 빠른 경로 설정, 경로 오류에 대비하는 경로 설정을 목표로 연구되 었다. 하지만 무선 메쉬 네트워크는 사용 목적이 이 동 무선 네트워크와 다르다. 무선 메쉬 네트워크는 다른 통신 단말기에 서비스를 하기 위한 무선 기반 시설로 연구되고 있다. 즉, 네트워크의 효율적 사용 및 다른 메쉬 단말의 오류에 상관없이 중단 없는 서비스가 가능해야 한다. 본 논문에서는 이동성이 없는 무선 메쉬 네트워 크에서 데이터를 외부에 전송하기위해 게이트웨이까 지 데이터를 전달하기 위해서, 게이트웨이가 자신을 880
논문 / 무선 메쉬 네트워크 환경에서 효율적인 다중 홉 전달 기법 광고하는 메시지를 통해서 Forward Path설정과 데 이터를 메쉬 노드가 수신하기 위한 Reverse Path 설정 과정에 대해서 제안하고, Forward Path설정 시 데이터를 목적지(게이트웨이)로 전달하기 위한 Primary Path와 Primary Path가 오류가 있어 사용 할 수 없을 때, 사용하기 위한 Backup Path로 나누 었다. 그리고 부하를 분산시키고, 좋은 경로를 선택 하기 위한 메트릭으로 기대되는 전송 속도인 ETR 을 제안함으로서 Hop-by-hop 전송을 위한 메트릭으 로 사용하는 것을 제안하였다. 그리고 Hop-by-hop 전송 시 다음 홉의 상황을 예측하지 못하는 문제에 대한 전략을 제시했다. 또한 경로 설정 시 게이트웨 이가 주도적으로 Forward Path를 설정함으로서 다 중 게이트웨이를 지원 가능한 구조로 전달 테이블 이 설정된다. 제안한 방법을 통해 기존의 라우팅 방법과 비교 해, 부하분산(Load Balancing) 효과와 경로에 대한 신뢰도가 높은 구조임을 증명하였다. 추후 연구에서는 표준화가 진행 중인 무선 메쉬 네트워크의 대표적인 IEEE 802.11s에서 제안되고 있는 다중 인터페이스와 다중 채널에 특성화 된 적 합한 전달 방법과 모든 메쉬 노드에게 공평한 QoS 를 제공할 수 있는 자원 예약 방식 및 스케쥴링 방 법에 대해 검증하는 작업을 수행할 것이며, 다중 홉 을 이용하는 방식으로 실질적으로 각 홉에서의 지 연(Delay)에 대해서 연구를 수행할 것이다. 참 고 문 헌 [1] Ian F. Akyildiz, Georgia Institute of Technology, Xudong Wang, Kiyon, INC A Survey on Wireless Mesh Network, IEEE Radio Communication, pp. 23-30, September 2005. [2] Raffaele Bruno, Marco Conti, and Enico Gregori, National Research Council(CNR), Mech Networks: Commodity Multihop Ad Hoc Networks, IEEE Communications Magazine, pp. 123-131, March 2005. [3] Jian Tang, Guoliang Xue and Weiyi Zhang, Interference-Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks, pp. 68-77, MobiHoc'05. [4] Richard Draves, Jitendra Padhyem Brian Zill, Comparison of Routing Metrics for Static Multi-Hop Wireless Networks, pp. 80-91, SIGCOMM'04. [5] Marc Mosko, J,J Garcia-Luna-Aceves, Multipath Routing in Wireless Mesh Networks. [6] YuHua Yuan, HuiMin Chen, and Min Jia, An Optimized Ad-hoc On-demand Multipath Distance Vector(AOMDV) Routing Protocol, In Asia-Pacific Conference on Communications, pp. 14-23, October 2005 [7] David B.Johnson, David A. Maltz, and Yih-Chun Hu, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks(DSR), IETF Internet draft, draft-ieft-manet-dsr-10.txt, July 2004 [8] Y. Zhenqiang et al., A Framework for Reliable Routing in Mobile Ad Hoc Networks, in Proceedings of IEEE INFOCOM, 2003. [9] S-J Lee and Mario Gerla, Dynamic Load-Aware Routing in Ad Hoc Networks, IEEE International Conference on Communication, pp. 222-232, Aug 2002. [10] Kui Wu, Janelle Harms, Load-Sensitive Routing for Mobile Ad Hoc Networks, IEEE, pp. 0-6, 2001. [11] H. Hassanein and A.Zhou, Routing with Load Balancing in Wireless Ad Hoc Networks in Proc. ACM MSWiM, July 2001. [12] S.-J. Lee and M. Gerla, Split multipath routing with maximally disjoint paths in ad hoc networks, IEEE ICC, pp. 3201-3205, 2001 [13] M. Marina and S. Das, On-demand multipath distance vector routing in ad hoc networks in Proc. ICNP, pp. 14-23, 2001 [14] Perkins, C.E and Royer, E.M., Ad-hoc On-Demand Distance Vector Routing, IEEE WMCSA'99, pp. 525-535, February 1999 [15] C.E Perkins and P.Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile computers, Computer Communication, pp. 234-244, October 1994 881
한국통신학회논문지 06-10 Vol.31 No.10B 김 영 안 (Young-an Kim) 정회원 1988년 2월 금오공과대학 전산 공학과 졸업 1996년 3월 Keio University, Department of Information and Computer Science (공학 석사) 2000년 3월~현재 경희대학교 컴 퓨터공학과 박사과정 <관심분야> 무선 메쉬 네트워크, MAC Protocol 박 철 현 (Chul-Hyun Park) 준회원 2004년 8월 경희대학교 전자계 산공학과 졸업(학사) 2006년 8월 경희대학교 컴퓨터 공학과 졸업(석사) <관심분야> 무선 메쉬 네트워크 홍 충 선 (Choong Seon Hong) 정회원 1983년 경희대학교 전자공학과 졸업(학사) 1985년 경희대학교 전자공학과 (공학석사) 1997년 Keio University, Department of Information and Computer Science (공학박사) 1988년~1999년 한국통신 통신망 연구소 수석연구원/ 네트워킹연구실장 1999년~현재 경희대학교 전자정보학부 부교수 <관심분야> 인터넷 서비스 및 망 관리 구조, 분산 컴포 넌트관리, IP 프로토콜, Sensor Networks, Network Security 882