모바일에드혹네트워크의 OLSR(Optimized Link State Routing Protocol) 구현에관한연구 논 문 60P-4-16 The Study on the OLSR(Optimized Link State Routing Protocol) Implementation in the Mobile Ad-hoc Network 조태경 이재희 * (Tae-Kyung Cho Jea-Hee Lee) Abstract - In this paper, we research the OLSR(Optimized Link State Routing Protocol) of the mobile ad-hoc network protocols, and design the system implementation based on the Embedded Linux for the Ubiquitous Space construction. We prove the performance of proposed system in the various experiment environments through several scenarios which is about transmitting the image data on the mobile ad-hoc network environment Key Words : Mobile Ad-hoc, OLSR, MANET, MPR, Ubiquitous * 1. 서론 현재스마트폰 (smart phone) 의등장과더불어센서네트워크 (sensor network) 에대한관심이높아지고있다. 센서네트워크에서사용하는센싱엔진은도처에편재되어있기때문에, 통신거리상의제약을극복하기위해센싱엔진간애드혹네트워크 (ad-hoc network) 를구성하여멀티홉릴레이 (multi-hop relay) 기능을구현하고있다. 이동애드혹네트워크는이동성을가진다수의노드들에의해자율적으로구성되는한시적인통신망으로서, 기반망 (Infrastructure Network) 이존재하지않거나기반망의확장이용이하지않은지역에서한시적으로통신망을구성하기위한목적으로사용되고있다. 최근들어, 이동애드혹네트워크기술은홈네트워킹, 센서네트워크, 개인영역통신망등다양한응용분야에서적용되고있으며, 차세대네트워킹방식의하나로서활발한연구가진행되고있다. 이동애드혹네트워크라우팅프로토콜 [1] 에대한연구는 1970년대이동애드혹네트워크의출현과더불어시작되었으며, 1997년에구성된 IETF MANET(Mobile Ad hoc NETwork) 작업그룹을중심으로표준화작업이진행되고있다. 본논문에서는임베디드리눅스기반의통신장비를애드혹네트워크의단말로동작할수있도록하는소프트웨어모듈개발을수행하였다. 본논문에서수행한연구내용은다음과같다. 먼저이동애드혹네트워크를구성하기위해 OLSR 프로토콜의패킷포맷, 제어메시지, MID 메시지포맷, 정보저장관계등을분석하고, C언어를사용하여구현했다. 또한현재스마트폰의 OS로각광받고있는안드로이드폰의기본커널인임베디드리눅스위에 OLSR 프로토콜을탑재하기위해 Arm9 프로세 교신저자, 정회원 : 상명대학교정보통신공학과교수 공박 E-mail: tkcho@smu.ac.kr 비회원 : 동서울대학정보통신과교수 공박접수일자 : 2011년 6월 13일최종완료 : 2011년 9월 7일 서를이용하여하드웨어를구현했다. 마지막으로임베디드리눅스가이식된하드웨어에본논문에서구현한 OLSR 프로토콜을탑재하고, 실험을통해성능을검증하였다. 2. 이동에드혹네트워크라우팅프로토콜 2.1 대표적이동애드혹네트워크라우팅프로토콜이동애드혹네트워크라우팅프로토콜은프로액티브 (proactive) 라우팅방식과리액티브 (reactive) 라우팅방식으로분류할수있다. 프로액티브라우팅방식은모든이동노드들이항상최신의루트정보를유지하며, 라우팅정보를주기적으로또는네트워크토폴로지상의변경이있을때마다네트워크전체로전파시켜각노드들이자신의라우팅정보를변경한다. 프로액티브라우팅방식은패킷발생시지연없이항상최적의루트를통해서라우팅할수있는장점을가지고있으나네트워크토폴로지의변화가심할경우라우팅정보를네트워크전체로전파하기위한라우팅프로토콜메시지의오버헤드가크다는문제점이있다. 리액티브라우팅방식은트래픽이발생하는시점에서루트를탐색하는방법으로서프로액티브라우팅방식의단점인제어메시지의오버헤드를감소시킬수있다. 또한, 루트정보는루트상의각노드에저장되나일정기간동안해당루트가사용되지않을경우노드로부터삭제된다. 리액티브라우팅방식은트래픽이발생하는시점에서루트를탐색하기때문에루트탐색에추가적인시간이필요하며, 이는트래픽의전송지연을야기하는단점이있다.[2][3] 2.2 Optimized Link State Routing의원리 OLSR 프로토콜은이동애드혹네트워크라우팅알고리즘으로 RFC(Request For Comment)3626에정의되어있다. OLSR은테이블기반의프로액티브라우팅프로토콜에속하는것으로모든이동노드가네트워크상의모든라우팅정보를가지고있다. OLSR은이동애드혹네트워크에서현 모바일에드혹네트워크의 OLSR(Optimized Link State Routing Protocol) 구현에관한연구 257
전기학회논문지 60P 권 4 호 2011 년 12 월 재제안된링크상태알고리즘중에서가장최적화된것으로알려져있으나계층적이지않은네트워크구성으로인한오버헤드를줄이기위해서네트워크구조에계층성을둠으로써브로드캐스트메시지전송으로인한오버헤드를줄인다. OLSR의특징은선택된노드인 MPR(Multi Point Relay) 만이제어메시지를브로드캐스팅한다는것이다. 네트워크상의노드는 1홉 (hop) 거리상의이웃노드중에서 MPR을선택하고 MPR로선택된노드들만이제어메시지를네트워크상에전송할수있다. MPR 선택에있어서단방향링크에서데이터를전송하는문제를회피하기위해서이웃한노드와양방향링크가존재하는지를먼저확인해야한다. 종단간이동노드의메시지송수신을위한경로검색에도 MPR이사용된다. 네트워크의모든노드들은이웃노드들과주기적으로 Hello 메시지를교환하고이메시지를통해각노드들은 MPR set을구성한다. 이때 Hello 메시지에는해당노드가도달가능한이웃노드들의정보가포함된다. MPR을구성하는절차는다음과같다. 1) 1홉거리에있는노드들중 2홉노드에도달하기위해유일한경로를제공하는노드들을 MPRs에추가한다. 2) 2홉거리에있는노드들중현재의 MPRs을통해도달가능한노드들은 2홉노드 set에서제외한다. 3) MPRs에포함되지않은 1홉노드들중 2홉거리에있는노드들은가장많이포함하는노드를 MPRs에추가한다. 4) 2홉거리에있는노드들이모두포함될때까지 2) 의과정부터반복한다. 2.3 OLSR 패킷포맷 OLSR 패킷포맷은헤더 (head) 와바디 (body) 구성되어있다. OLSR 패킷의헤더는패킷길이 (packet length) 와패킷순서번호 (packet sequence number) 로구성되어있다. OLSR 패킷의바디는 1개또는그이상의 OLSR 메시지로구성되어있다. 하나의 OLSR 메시지는메시지타입, Vtime, 메시지크기, 발신주소, Time To Live, 홉카운트, 메시지일련번호, 메시지필드로구성된다.[4] 그림 3 OLSR 패킷포맷 3 OLSR packet format 1 홉 2 홉 3 홉 그림 1 홉에따른정규플러딩 1 Regular flooding according to hop 2.4 OLSR 제어메시지 OLSR 제어메시지는 Hello 메시지, MID 메시지그리고 TC(Topology Control) 메시지로구성된다. OLSR의주된기능은이웃노드검색 (neighbor node discovery) 및영역선전 (topology dissemination) 으로요약할수있다. 이웃노드검색을위해서네트워크상의각노드는 Hello 메시지를주기적으로교환한다. 이 Hello 메시지는 1홉거리에있는이웃노드사이에서만교환되기때문에오버헤드를일으키지않는다. 이외에도네트워크사의모든노드는 Hello 메시지를사용해서 1홉및 2홉거리에있는이웃노드를찾을수있다. 그림 4는 Hello 메시지의포맷이다. Hello 메시지가포함하고있는정보는링크상태 (link state) 정보, 이웃노드정보 (neighbors Information) 이다. 각 1 홉 2 홉 3 홉 그림 2 홉에따른 MPR 플러딩 2 MPR flooding according to hop 그림 4 OLSR Hello 메시지포맷 4 OLSR Hello message format 258
ystembutrans. KIEE. Vol. 60P, No. 4, DEC., 2011 노드들은자신의 1-홉이웃들의정보와 2-홉이웃들의목록을저장한다. 각정보들은홀딩시간 (holding time) 을갖고있고, 가장최신의 MPR Set의정보를알기위해순서번호값을포함하고있고업데이트시, 1씩증가한다. MID 메시지는 Multi-homed 노드들에관한정보를분산시키기위해사용된다. MID 메시지는 OLSR에동작하는노드의인터페이스주소의목록이다. 그림 5에 MID 메시지포맷을나타냈다. 된다. 이러한데이터집합들은수신된제어트래픽에근거하여갱신된다. 그림 7은 OLSR의정보저장의관계를나타내것이다.[5] 3. OLSR의구현 3.1 하드웨어플랫폼그림 8은 OLSR 구현을위해 ARM9을 main CPU로사용하여설계한하드웨어플랫폼의구성도이고, 그림 9는실제구현보드를나타낸것이다. ARM9 Core BOARD 그림 5 MID 메시지포맷 5 MID message format TC 메시지가포함하고있는정보는 MPR Selector, 순서번호이다. 각노드들은 TC 메시지를바탕으로구성 (topology) 테이블을유지하고있다. 그리고라우팅테이블은이구성테이블에의해서계산되어진다. MPR 노드만이주기적으로 TC 메시지를브로드캐스트한다. 만약업데이트가발생하지않으면 TC 메시지를보내지않는다. TC 메시지를받았을때아는도착지인경우, 테이블과메시지와순서번호를비교했을때 TC 메시지의값이더크다면 TC 메시지를무시, 작다면업데이트, 같다면테이블에서홀딩시간을갱신한다. 만약에새로운도착지인경우에는테이블에추가한다. USB Host USB Device 10 BaseTport 10 BaseTport LCD Clock Fresh Memory (Boot loader, Kernel) CS8900#1 CS8900#2 NAND Flash GPIO : General Purpose Input Output UART : Universal Asynchronous Receiver/Transmitter HDLC : High-Level Data Link Control ARM920T 그림 8 하드웨어플랫폼의구성도 8 Hardware platform diagram Push Switch (GPIO) SDRAM Dual UART CAT s4 CMX589 GMSK HDLC CAT : Computer Aided Terminal GMSK : Gaussian Minimum Shift KeyingS그림 6 TC 메시지포맷 6 TC message format 2.5 OLSR 정보저장관계고찰 OLSR 기능은이웃검색 (neighbor sensing), 멀티포인트연결 (multi-point relaying), 링크상태플러딩 (link-state flooding) 등의주요모듈로구성된다. 대부분의제어트래픽은 OLSR에의하여유지되는저장집합 (repositories set) 에의하여발생 그림 9 구현보드 9 Implementation board 표 1은본연구에서구현한보드의주요사양을나타낸것이다. 그림 7 OLSR 정보저장관계에대한구성도 7 The diagram of information repositories relation 표 1 하드웨어플랫폼의주요사양 Table 1 Main specification of hardware platform 구성품 규격 모델명 CPU ARM920T Core, MMU USB Host Internal OHCI Host control USB Device Internal USB Device control S3C2410X-01 Console Port Interanl UART GPIO 4개의버튼사용 RAM 16M byte SDRAM K4S281632 NOR Flash 4M byte NOR Flash Memory AM29LV320 Regulator LDO, Regulator for core power LP3965-1.8 모바일에드혹네트워크의 OLSR(Optimized Link State Routing Protocol) 구현에관한연구 259
mbeddedlinu전기학회논문지 60P 권 4 호 2011 년 12 월 3.2 소프트웨어플랫폼본논문에서구현한소프트웨어는 PicoNet II을근간으로하여임베디드리눅스상에 OLSR 알고리즘을구현하였다. 응용프로그램은크게제어용 S/W, 네트워크응용 S/W, 시스템 S/W로나누어구성하였다. 제어용 S/W는 MMI, Auto Configure로구성하였고 Network 응용 S/W는 Telnet, Ping, 웹서버등으로구성했다. 마지막으로시스템 S/W는 Busy Box 와 Video Capture 기능을수행하는 Vidcat으로구성하였다. 그림 10 에개발시스템의소프트웨어플랫폼을나타냈다.E그림 12는그림 11에나타낸 IP 주소가 192.168.1.1인릴레이노드에 OLSR 을설정하는사용자화면을나타낸것이다. 16 X 2 LCD 4 Push Switch USB 사용 Device LCD KeyPad USB H USB D 응용프로그램 제어용 S/W Network 응용 S/W (MMI, Auto Configure) (Telnet,Ping,Webserver등 ) 시스템관리 S/W (busybox, vidcat) Dynamic Routing Protocol (OLSR, DSR PicoNet II) 제어컴퓨터 컴퓨터 콘솔 Ethernet TCP/IP, PPP AX-25 xp999k I/FGMSK 모뎀상용무전기 I/F 그림 12 릴레이노드에 OLSR 을설정하는사용자화면 12 The setting GUI of relay node in OLSR implement 그림 10 개발시스템의소프트웨어플랫폼 10 The software platform of development system 4. 성능평가본연구에서개발한시스템의성능을평가하기위한실험시나리오는다음과같다. 1) 송신단말기 (IP 주소 : 192.168.2.1) 의웹카메라를통해획득한이미지를수신단말기 (IP 주소 : 192.168.0.123) 로전송하는과정에전파차폐물을삽입하여무선통신회선을단절시킨다. 2) 무선통신회선이단절된상태에서전파차폐를피할수있는곳에본논문에서구현한 OLSR 단말기 (IP 주소 : 192.168.0.1) 를위치시켜릴레이노드의역할을수행하여새로운무선통신회선을확립한다. 3) 새로이확립된무선통신회선을사용하여이미지전송을완료한다. 4) 수신된이미지를분석하여송신이미지가오류없이수신되었음을확인한다. 그림 11에실험시나리오를도시하였다. 그림 13의 (a) 는성능평가시사용한송신영상이고, 그림 13의 (b) 는무선통신회선이단절된상태에서본논문에서구현한 OLSR 단말기를경유하여수신된수신영상의한예이다. 본논문에서는전술한실험시나리오에따라다수의실험을수행하였고그결과데이터패킷손실이전혀발생하지않았고, 따라서수신영상의열화는발생하지않았음을확인하였다. (a) 송신영상 (a) Transmitted image 그림 11 실험시나리오 11 Experiment scenario 그림 13 송 수신영상 (b) 수신영상 (b) Received image 13 Transmitted & Received image 260
Trans. KIEE. Vol. 60P, No. 4, DEC., 2011 5. 결론 본논문에서는임베디드리눅스기반의기존의통신장비를이동애드혹네트워크의단말로동작시킬수있는소프트웨어모듈을개발하였다. 본논문에서구현한소프트웨어모듈은이동애드혹네트워크의라우팅프로토콜로 OLSR을채택하였고, 효과적인구현하기위해 OLSR 프로토콜의패킷포맷, Control 메시지, MID 메시지포맷, 정보저장관계등을분석한후 C언어를사용하여개발하였다. 구현한소프트웨어모듈의기능을검증하기위해, Arm9 프로세서를사용한하드웨어를제작하고임베디드리눅스를이식한시스템을사용하여성능을평가하였다. 다양한환경에서실시한실험결과를통해, 본논문에서구현한소프트웨어모듈의성능을확인하였다. 본논문에서구현한소프트웨어모듈은향후안드로이드 OS를기반으로하는스마트폰에모바일애드혹네트워크기능을구현하는데많은참고가될것으로생각된다. 참고문헌 [1] S. Corson and J. Macker, Routing Protocol Performance Issues and Evaluation Considerations, draft-ietf-manetissues-00.txt [2] C.E. Perkins."Mobile IP, Design Principles and Practices". Addison Wesley,1997 [3] C. Perkins, Mobile Ad Hoc Networking Terminology, draft-ietf-manet-term-00.txt, October 1997. [4] V. Park and M. S. Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proc. IEEE INFOCOM '97, Kobe, Japan(1997). [5] M.S. Corson and A. Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks 1(1995). 저자소개 조태경 ( 趙兌璟 ) 1984년한양대학교전자통신공학과졸업. 1986년한양대학교전자통신공학과석사. 2001년한양대학교전자통신공학과박사. 2003년 ~ 현재상명대학교정보통신공학과교수. Tel : 041-550-5354 E-Mail : tkcho@smu.ac.kr 이재희 ( 李在熙 ) 1985년 2월광운대학교전자통신과졸업. 1987년 2월광운대학교전자통신과석사. 2000년 2월광운대학교전자통신과박사. 1987~1993년국방과학연구소. 1993년 ~ 1999년대덕대학정보통신과교수. 1999년 ~ 현재동서울대학정보통신과교수 Tel : 031-720-2208 E-Mail : ljh7314@dsc.ac.kr 모바일에드혹네트워크의 OLSR(Optimized Link State Routing Protocol) 구현에관한연구 261