Advanced
Mesh Routing Algorithm for TDMA Based Low-power and Ad-hoc Networks
Mesh Routing Algorithm for TDMA Based Low-power and Ad-hoc Networks
Journal of the Korea Institute of Information and Communication Engineering. 2014. Aug, 18(8): 1955-1960
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/ by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : May 02, 2014
  • Accepted : June 16, 2014
  • Published : August 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
소영 황

Abstract
저전력 애드혹 네트워크 환경에서 명령 및 데이터의 전달을 위해 라우팅 기법은 필수적이며 최근에는 신뢰성과 확장성을 고려한 네트워킹 기법에 대한 연구가 많이 이루어지고 있다. 저전력 네트워킹 기술에서 네트워크 계층의 성능은 하위 데이터 링크 계층의 동작과 밀접한 연관이 있으며 신뢰성과 확장성을 지원하기 위해 TDMA 기반의 메쉬 라우팅 기법이 고려되고 있다. 본 논문에서는 TDMA 기반 저전력 애드혹 네트워크에서 TDMA MAC의 특성과 토폴로지 기반으로 할당된 주소를 활용한 메쉬 라우팅 알고리즘을 제안한다. 또한, TDMA MAC이 동작하는 센서 네트워크 플랫폼에서 제안한 기법을 구현한 결과를 제시한다.
Keywords
Ⅰ. 서 론
저전력 애드혹 네트워크로 대표되는 무선 센서 네트워크 환경에서 노드 간 명령 및 데이터 전송을 위한 다양한 라우팅 기법이 제시되었다 [1 - 3] . 최근에는 신뢰성과 확장성을 고려하여 TDMA (Time Division Multiple Access) 기반의 메쉬 라우팅 기법이 고려되고 있으며 저전력 네트워크를 위한 표준 기술 중 메쉬 라우팅을 지원하는 것으로 IEEE 802.15.5의 Low-rate WPAN (Wireless Personal Area Networks) Mesh 와 ZigBee alliance에서 AODV (Ad-hoc On-demand Distance Vector)를 기반으로 한 메쉬 라우팅이 대표적이다.
IEEE 802.15.5 Low-rate WPAN Mesh는 IEEE 802.15.4 PHY/MAC을 기반으로 동작하며 Mesh coordinator를 중심으로 블록 어드레싱을 수행하고, 노드들이 지정한 홉수 내에서 주기적으로 hello command를 브로드캐스팅하여 지정한 홉수 내의 이웃 노드들 정보를 수집한다. 이를 neighbor table로 관리하여 메쉬 라우팅이 가능하도록 한다 [4 , 5] .
ZigBee alliance에서 제안한 메쉬 라우팅 기법은 종래의 MANET (IETF Mobile Ad-hoc Networks working group)에서 제안된 AODV 방식을 차용하여 소스 노드는 목적지 노드에 도달하기 위한 경로를 탐색하기 위해 RREQ (Route Request) 메시지를 방송하고, 이를 수신한 목적지 노드는 소스 노드에 이르기까지 RREP (Route Reply) 메시지를 전달하여 소스 및 목적지 간 경로를 설정하는 방식이다 [6] .
IEEE 802.15.5 Low-rate WPAN Mesh의 경우 메쉬 라우팅을 위해 hello command의 주기적인 브로드캐스팅이 필요한데 이는 네트워크를 구성하는 노드의 밀집도가 증가할 경우 그 부하가 기하급수적으로 증가하게 된다. ZigBee alliance의 AODV 기반 메쉬 라우팅 기법도 RREQ 메시지의 브로드캐스팅에 기반하고 있기 때문에 경로 설정을 위한 제어 트래픽의 부하가 매우 크다는 단점을 갖는다. 또한 이들은 TDMA 기반의 MAC에서는 동작이 어려운 구조이다.
본 논문에서는 TDMA 기반 저전력 애드혹 네트워크에서 TDMA MAC의 특성과 토폴로지 기반으로 할당된 주소를 활용한 메쉬 라우팅 알고리즘을 제안하고 구현 결과를 제시한다. 저전력 네트워크를 위한 표준 기술의 네트워크 계층 기법 및 제안하는 기법의 특징을 표 1 에 제시하였다 [5 - 7] .
저전력 네트워크를 위한 표준 기술의 네트워크 계층 기법 비교Table. 1Comparisons of Network Layer Scheme in Standards for Low-power Networks
PPT Slide
Lager Image
저전력 네트워크를 위한 표준 기술의 네트워크 계층 기법 비교 Table. 1 Comparisons of Network Layer Scheme in Standards for Low-power Networks
논문의 구성은 다음과 같다. 2장에서 TDMA 기반 저전력 애드혹 네트워크를 위한 메쉬 라우팅 알고리즘을 제안하고 3장에서 제안한 알고리즘의 구현 결과를 다룬다. 마지막 4장에서 논문의 결론을 맺는다.
Ⅱ. TDMA 기반 저전력 애드혹 네트워크를 위한 메쉬 라우팅 알고리즘
- 2.1. 알고리즘 동작 환경
제안하는 메쉬 라우팅 알고리즘은 TDMA MAC을 기반으로 동작하는 저전력 애드혹 네트워크에서 동작한다. 네트워크를 구성하는 모든 노드들은 주기적으로 비컨 (beacon) 메시지를 방송하고 이를 통해 TDMA를 위한 시각 동기 및 이웃 노드 (neighbor node) 정보를 수집한다. 또한, 네트워크의 형성은 ZigBee에서 제안한 바와 같이 초기 파라미터만을 이용하여 분산적으로 주소를 할당하도록 한다. 즉, 토폴로지 구조에 맞추어 노드의 주소를 할당함으로써, 네이버 테이블의 구성없이, 또한 RREQ/RREP와 같은 제어 메시지의 교환 없이 네트워크 내부에서 트리 라우팅을 이용하여 멀티 홉 데이터 전송을 수행할 수 있다. 하지만, 트리 라우팅은 실제 목적지가 가까이 있음에도 불구하고 네트워크 접속 과정에서 서로 다른 서브 트리에 속한 경우 메시지 중계 횟수가 증가하게 되고 이는 네트워크의 트래픽과 데이터 전송 지연을 높이는 단점이 있다.
- 2.2. 메쉬 라우팅 알고리즘
제안하는 메쉬 라우팅 알고리즘은 네트워크 형성 과정에서 수집한 이웃 노드 정보 혹은, 접속 후 주기적으로 수신한 비컨 메시지에서 수집한 이웃 노드 주소 리스트를 하위 MAC 계층에서 주기적으로 브로드캐스팅하는 비컨 메시지 내 비컨 페이로드 (beacon payload)에 탑재하여 브로드캐스팅하도록 한다. 주변 노드들로부터 비컨 메시지를 수신한 노드는 비컨 페이로드에 탑재된 이웃 노드 주소 리스트를 추출하여 네트워크 테이블을 생성 및 관리한다. 이때, 비컨 페이로드에 탑재되는 이웃 노드 정보의 범위는 지정된 값에 의해 정해질 수 있다. 즉, 2-hop 이웃 노드에 대해 테이블을 관리하고자 한다면 노드는 비컨 전송시 노드 접속 과정에서 수집한 이웃 노드의 주소 혹은, 비컨 수신을 통해 수집한 이웃 노드의 주소를 비컨 페이로드에 탑재하여 브로드캐스팅하면 된다. 지정된 비컨 수신 기간 동안 이웃 노드들의 비컨을 수신한 노드는 각 비컨을 전송한 노드의 주소 및 해당 비컨 페이로드에 탑재된 이웃 노드 주소를 테이블로 생성 관리함으로써 네트워크 테이블을 유지하게 된다. 같은 방법으로 3-hop 이상의 이웃 노드 정보도 자신이 관리하는 이웃 노드 테이블 정보를 비컨 페이로드에 탑재하여 브로드캐스팅하고 해당 비컨을 수신한 노드가 테이블에 추가하여 관리하면 지정된 범위까지의 노드 정보를 네트워크 테이블로 관리할 수 있게 된다. 그림 1 은 비컨 메시지 수신을 통해 네트워크 테이블을 생성한 예를 나타낸 것이다.
PPT Slide
Lager Image
비컨을 활용한 네트워크 테이블 생성 (2-hop neighbor) Fig. 1 Generation of network table using beacon (2-hop neighbor)
비컨은 주기적으로 계속 브로드캐스팅되기 때문에 개별 노드는 자신의 이웃 노드 정보를 주기적으로 전송 및 수신함으로써 네트워크 테이블을 유지관리 할 수 있다. 노드 혹은 링크 손상에 의해 통신할 수 없는 노드가 생겼을 때 비컨을 이용해 네트워크 테이블 갱신의 예를 그림 2 에 제시하였다.
PPT Slide
Lager Image
비컨을 활용한 네트워크 테이블 갱신 Fig. 2 Network table update using beacon
이와 같은 방법으로 네트워크를 구성하는 모든 노드는 추가의 제어 트래픽을 생성하지 않고도 지정한 범위내의 이웃 노드 정보를 구성하게 된다. 그리고, 이를 바탕으로 메쉬 라우팅을 수행하게 된다.
네트워크 내 임의 노드가 지정된 목적지로 명령 혹은 데이터를 전송하고자 할 경우 노드는 자신이 관리하는 네트워크 테이블에 해당하는 목적지 주소가 있는지를 검사한다. 만약, 목적지 주소가 자신이 관리하는 네트워크 테이블에 존재하면 해당 목적지로 가기 위한 다음 홉 (next-hop) 주소를 테이블에서 추출하여 명령 혹은 데이터를 전달한다. 그리고, 해당 명령 혹은 데이터를 수신한 노드는 목적지 주소가 자신의 주소와 같은지를 체크하고 같지 않을 경우는 앞서 기술한 바와 같은 방법으로 명령 혹은 데이터를 전달하고 목적지에 이르기까지 반복하면 된다.
그림 3 은 소스 노드의 네트워크 테이블내 목적지 주소가 존재할 경우 목적지에 이르기 위한 다음 홉 주소를 추출하여 라우팅을 수행하는 예를 나타낸 것이다.
PPT Slide
Lager Image
네트워크 테이블 기반 메쉬 라우팅의 예 Fig. 3 An example of mesh routing based on network table
만약, 명령 혹은 데이터를 전송하고자 하는 노드의 네트워크 테이블에 목적지 주소가 존재하지 않을 경우는 해당 네트워크에 적용된 주소 할당 방식에 따라 전달하면 된다. 제안하는 알고리즘은 토폴로지 기반 라우팅이 가능한 분산 주소 할당 방식의 네트워크 형성을 이루는 환경에서 동작한다. 따라서, 목적지 주소만으로 다음 홉 주소를 결정할 수 있기 때문에 이를 바탕으로 명령 혹은 데이터를 전달한다. 이를 수신한 노드는 자신의 네트워크 테이블을 검색하여 목적지가 존재하면 테이블에 근거하여 다음 홉을 정하고 그렇지 않으면, 주소 기반으로 데이터를 전달하면 된다.
그림 4 는 소스 노드의 네트워크 테이블에 목적지가 존재하지 않을 경우 토폴로지 기반으로 데이터를 전달하고 수신한 노드의 네트워크 테이블에 목적지가 존재하여 네트워크 테이블 기반으로 라우팅을 수행하는 예를 나타낸 것이다.
PPT Slide
Lager Image
주소와 네트워크 테이블을 혼용한 메쉬 라우팅의 예 Fig. 4 An example of mesh routing using address and network table
Ⅲ. 구현 결과
제안한 라우팅 알고리즘은 TDMA 기반 MAC과 토폴로지 기반의 주소할당을 통해 네트워크를 구성하는 실제 센서 노드를 대상으로 구현하였다. 구현 결과를 확인하기 위하여 그림 5 와 같은 시험 환경을 구성하였다.
PPT Slide
Lager Image
시험 환경 구성도 Fig. 5 Architecture of test environment
시험 환경은 개발 PC와 저전력 애드혹 네트워크를 구성하는 코디네이터 (coordinator)와 라우터 (router)로 구성되며, 모든 디바이스는 디버깅 및 동작 확인을 위하여 개발 PC와 serial(USB)로 연결된다. 개발 PC에는 USB 포트를 이용하여 개발 PC에 연결된 디바이스로 원하는 명령어를 내보내고, 그 결과를 확인하는 GUI 프로그램이 설치된다. 또한, 무선으로 디바이스간에 주고 받는 데이터의 분석을 위하여 무선 패킷 수신기와 PC에 설치되어 동작하는 분석기가 요구된다.
메쉬 라우팅 알고리즘의 동작을 검증하기 위한 실험 환경은 그림 6 과 같다. 코디네이터와 라우터 디바이스는 개발 PC와 USB를 통하여 연결되고, 각 라우터 디바이스들은 코디네이터의 자식으로 접속되도록 하였다.
PPT Slide
Lager Image
메쉬 라우팅 실험 환경 Fig. 6 Test environment for mesh routing
그림 7 은 라우터 노드 1에서 라우터 노드 2로 데이터를 전송한 결과를 나타낸 것이다. 기존의 주소 기반 라우팅이 적용된 경우라면 코디네이터를 통해 라우팅이 이루어지지만 제안한 메쉬 라우팅 알고리즘을 적용할 경우 이웃 노드 정보를 이용해 직접 데이터 전달이 가능해진다. 그림 8 은 MAC 계층의 비컨 프레임에 이웃노드 정보가 포함된 내용을 패킷 스니퍼를 통해 분석한 것이다.
PPT Slide
Lager Image
라우터 노드들의 메시지 송수신 결과 (a) 라우터 노드 1의 터미널 화면 (b) 라우터 노드 2의 터미널 화면 Fig. 7 Result of routing (a) Terminal display of router node 1 (b) Terminal display of router node 2
PPT Slide
Lager Image
비컨 프레임에 포함된 이웃노드 정보 Fig. 8 Information of neighbor nodes in beacon frame
Ⅳ. 결 론
본 논문에서는 TDMA 기반 저전력 애드혹 네트워크를 위한 메쉬 라우팅 알고리즘을 제안하였다. 제안한 알고리즘은 TDMA MAC의 특성과 토폴로지 기반으로 할당된 주소를 이용한 메쉬 라우팅 기법으로 TDMA MAC의 비컨 메시지를 활용하여 라우팅을 위한 네트워크 테이블을 생성, 관리함으로써 부가의 제어 트래픽 발생없이 메쉬 라우팅이 가능하도록 하였다.
또한, 제안한 기법을 TDMA MAC이 동작하는 센서 네트워크 플랫폼에서 구현하여 알고리즘의 동작을 시험하였다. 향후 기존 표준 기술에서 제안된 라우팅 기법과의 성능 비교가 필요하다.
Acknowledgements
본 연구는 2013년도 부산가톨릭대학교 교내학술연구비 지원에 의하여 이루어진 연구로서, 관계부처에 감사 드립니다.
BIO
황소영(Soyoung Hwang)
1999년 부산대학교 전자계산학과 (이학사)
2001년 부산대학교 전자계산학과 (이학석사)
2006년 부산대학교 전자계산학과 (이학박사)
2006년 ~ 2010년 2월 한국전자통신연구원 선임연구원
2010년 3월 ~ 현재 부산가톨릭대학교 소프트웨어학과 조교수
※관심분야 : 임베디드 시스템, 통신 및 네트워크, 시각동기, e-Navigation
References
Al-Karaki J.N. , Kamal A.E. 2004 “Routing Techniques in Wireless Sensor Networks: A Survey,” IEEE Wireless Communications 6 - 28
Karl H. , Willig A. 2005 Protocols and Architectures for Wireless Sensor Networks John Wiley & Sons
Akkaya K. , Younis M. 2005 "A Survey on routing Protocols for Wireless Sensor Networks," Elsvier Ad Hoc Networks Journal 3 (3) 325 - 349    DOI : 10.1016/j.adhoc.2003.09.010
2006 IEEE 802.15.4, IEEE Standard for Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs)
2009 IEEE Recommended Practice for Information Technology-Telecommunications and information exchange between systems - Local and metropolitan area networks - Specific requirements Part 15.5: Mesh Topology Capability in Wireless Personal Area Networks (WPANs)
2007 ZigBee Specification: Document 053474r17 (ZigBee 2007 Specification)
2006 ZigBee Specification: Document 053474r13 (ZigBee 2006 Specification)