Advanced
A Routing Protocol for Improving Path Stability in Mobile Ad-hoc Networks
A Routing Protocol for Improving Path Stability in Mobile Ad-hoc Networks
Journal of the Korea Institute of Information and Communication Engineering. 2015. Jul, 19(7): 1561-1567
Copyright © 2015, The Korean 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 : March 12, 2015
  • Accepted : April 24, 2015
  • Published : July 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
형직 김
선웅 최
schoi@kookmin.ac.kr

Abstract
모바일 애드혹 네트워크의 노드는 일반적으로 에너지의 용량이 제한된 배터리를 사용한다. 경로의 안정성을 유지하기 위해 균형 잡힌 에너지 소비가 중요하다. 본 논문에서는 애드혹 네트워크에서 데이터 전송 경로의 안정성을 향상시키는 것을 목표로 한다. 이를 위해 데이터를 전송할 수 있는 최단 전송 경로 중에서 노드 에너지 잔량의 최소값이 가장 큰 경로를 선택하는 새로운 라우팅 프로토콜을 제안한다. 에너지 잔량의 최소값이 가장 큰 경로는 다른 경로보다 상대적으로 긴 수명을 갖게 되어 데이터 전송에 안정성을 향상 시킬 수 있다. NS-3 시뮬레이터를 사용하여 제안하는 라우팅 프로토콜이 AODV와 EA-AODV보다 수명이 긴 안정적인 경로를 제공하는 것을 확인한다.
Keywords
Ⅰ. 서 론
무선 애드혹 네트워크는 AP(Access Point)가 없이 노드끼리 네트워크를 구성하여 데이터를 전송한다. 데이터를 전송할 때 소스 노드와 목적지 노드의 물리적 거리가 멀 경우에 다른 노드들을 경유하여 데이터를 전송한다. 애드혹 네트워크에서 주로 사용되는 라우팅 프로토콜로는 DSDV, DSR, AODV가 있다 [1 - 3] .
이 중 대표적으로 사용되는 AODV는 유동적인 환경에서도 빠른 경로 형성과 데이터 전송을 보장하지만 무선 애드혹 네트워크에서 노드들은 일반적으로 배터리로 동작하기 때문에 에너지 소비를 분산시키는 것이 중요하다. 데이터를 전송 중에 노드의 배터리가 전부 소모되어 동작을 멈추게 될 경우에 경로를 재탐색하여 데이터를 다시 전송하기 때문에 지연이 발생하게 된다. 지연이 발생하면 데이터 전송의 QoS(Quality of Service)를 보장할 수 없다.
제한된 에너지를 갖는 노드들로 구성된 무선 애드혹 네트워크의 특성을 고려하여, 에너지 사용을 효율적으로 하는 라우팅 프로토콜들이 제안되었다. 이 프로토콜들은 크게 두 가지로 구분될 수 있는데, 최소의 에너지를 사용하는 것을 목표로 하는 라우팅 프로토콜과 네트워크의 수명을 최대로 하는 것을 목표로 하는 것으로 구분할 수 있다 [4] . 최소의 에너지를 사용하는 것을 목표로 하는 라우팅 프로토콜은 소스 노드에서 목적지 노드로 이르는 경로 중에서 에너지를 가장 적게 사용하는 경로를 찾는 것을 목표로 하는 반면에, 네트워크의 수명을 최대로 하는 것을 목표로 하는 라우팅 프로토콜은 네트워크 전체적으로 에너지를 균형적으로 사용하는 것을 목표로 한다.
본 논문에서는 라우팅 경로의 안정성을 향상시키는 것을 목표로 한다. 라우팅 경로 상에 존재하는 노드가 에너지를 소진하고 동작을 멈추면, 라우팅 경로를 재탐색하기 위하여 추가적인 에너지와 시간적인 지연이 발생하게 된다.
본 논문에서는 데이터를 전송할 수 있는 최단 전송경로 중에서 노드 에너지 잔량의 최소값이 가장 큰 경로를 선택하는 새로운 라우팅 프로토콜을 제안한다. 에너지 잔량의 최소값이 가장 큰 경로는 다른 경로보다 상대적으로 긴 수명을 갖게 되어 데이터 전송에 안정성을 향상 시킬 수 있다.
본 논문의 구성은 다음과 같다. 2장에서는 무선 애드혹 네트워크에서 노드의 에너지를 고려한 라우팅 프로토콜인 EA-AODV(Energy Aware-AODV) 라우팅 프로토콜에 대해 설명하고, 3장에서는 본 논문에서 제안하는 프로토콜의 동작을 설명한다. 4장에서는 NS-3 시뮬레이터를 사용하여 본 논문에서 제안하는 프로토콜과 기존의 AODV, EA-AODV 라우팅 프로토콜의 성능을 비교하여 데이터 전송의 안정성 및 라우팅 경로의 안정성이 향상되는 것을 증명하고, 5장에서 결론을 내린다.
Ⅱ. 관련 연구
M. Tamilarasi와 T. G. Palanivelu가 제안한 EA-AODV (Energy Aware AODV) 라우팅 프로토콜은 노드의 에너지 잔량을 고려하는 라우팅 프로토콜로서 AODV를 기반으로 만들어졌다 [5] .
EA-AODV는 AODV와 마찬가지로 RREQ (Route Request)와 RREP (Route Reply) 패킷을 사용하여 데이터 전송 경로를 설정한다. 소스 노드에서 목적지 노드까지 RREQ 패킷을 플러딩(flooding)하는 과정에서는 두 프로토콜의 동작이 동일하다.
RREQ 패킷을 수신한 목적지 노드는 RREP 패킷을 소스 노드로 유니캐스트 방식으로 전송하는데, 두 프로토콜의 차이는 이 과정에 있다. AODV는 경로를 설정할 때 가장 짧은 거리, 즉 홉(hop) 수가 가장 적은 경로를 선택한다. 홉 수가 같을 경우에는 먼저 수신한 RREQ 패킷의 정보를 라우팅 테이블에 저장하고 나중에 수신한 RREQ 패킷들은 전부 폐기한다. EA-AODV의 경우에는, 노드들의 잔여 에너지를 고려하여 데이터 전송 경로를 결정하기 위하여 소스 노드로 전송되는 RREP 패킷에 전송 경로의 잔여 에너지 정보를 저장한다. 전송 경로의 수명은 잔여 에너지가 가장 적은 노드에 의하여 결정이 되기 때문에, RREP 패킷이 지나온 전송 경로 상에 존재하는 노드들의 에너지 잔량 중 최소값이 저장된다. 그리고, 목적지 노드는 잔여 에너지가 가장 많은 경로를 찾기 위하여, 수신한 모든 RREQ 패킷에 대하여 전부 RREP 패킷을 송신 노드로 유니캐스트한다. 그림 1 에 EA-AODV의 동작 알고리즘을 나타내었다.
PPT Slide
Lager Image
EA-AODV의 동작 알고리즘 Fig. 1 Algorithm of EA-AODV
AODV와 EA-AODV의 동작을 비교하기 위하여 그림 2 와 같은 3x3 토폴로지에서 소스 노드(1번 노드)에서 목적지 노드(9번 노드)로 향하는 전송 경로를 설정하는 동작을 예롤 들었다. 그림 2 (a)는 RREQ 패킷이 전송되는 과정의 예이다. 동일한 노드에 먼저 도착한 RREQ 패킷을 1로 표시를 하고, 나중에 도착한 RREQ 패킷은 점선으로 나타내고 2로 표시하였다. AODV는 먼저 도착한 RREQ 패킷의 정보를 저장하고 나중에 도착한 RREQ 패킷은 폐기하므로, 5번 노드는 소스 노드(1번 노드)로 가는 다음 홉(next hop)을 2번 노드로 저장하게 된다. 같은 방식으로 8번 노드는 5번 노드를, 6번 노드는 5번 노드를, 마지막으로 목적지 노드인 9번 노드는 6번 노드를 소스 노드로 가는 다음 홉으로 저장하게 된다. 그림 2 (a)의 과정을 통해 RREQ 패킷이 전송되면, 목적지 노드인 9번 노드는 RREP 패킷을 소스 노드로 유니캐스트하는데, 각 노드에 저장된 라우팅 테이블에 따라 그림 2 (b)와 같은 경로로 전송된다. 8번 노드를 통해 수신된 RREQ 패킷은 이전에 수신된 RREQ 패킷과 홉 수가 동일하기 때문에 무시된다.
PPT Slide
Lager Image
3x3 토폴로지에서 AODV와 EA-AODV의 동작 비교 Fig. 2 Behavior comparison of AODV and EA-AODV in 3x3 topology
EA-AODV는 그림 1 과 같이 에너지 잔량을 반영하여 최선의 경로를 선택한다. 그림 2 (c)에 RREP의 전송경로를 나타내었다. 소스 노드는 2개의 RREP를 수신한다. 두 개의 RREP에 담긴 에너지 잔량을 비교하면 실선으로 된 화살표에 포함된 에너지 잔량은 0.5이고 점선으로 된 화살표에 포함된 에너지 잔량은 0.1이다. 소스노드는 실선으로 된 화살표에 포함된 경로의 에너지 잔량이 더 크기 때문에 실선으로 된 화살표 경로의 역순으로 데이터를 전송한다.
이와 같이 EA-AODV는 홉 수만을 고려하는 AODV와는 다르게 노드의 잔여 에너지를 고려하여 보다 오랜 수명을 기대할 수 있는 전송 경로를 설정하게 된다. 하지만, EA-AODV 역시 최선의 경로를 찾지는 못하는 것을 확인할 수 있다. 그림 2 에서 최선의 경로(경로 상에 있는 노드의 잔여 에너지 최소값이 가장 큰 경로)는 1→ 4 → 7 → 8 → 9이다. EA-AODV는 노드의 잔여 에너지를 고려하기는 하지만, RREQ 패킷을 전송하는 과정에서 AODV와 같이 먼저 수신한 RREQ 패킷의 정보만을 저장하기 때문에 최선의 경로를 찾지 못하는 경우가 발생할 수 있다는 것을 알 수 있다.
Ⅲ. 경로 안정성 향상을 위한 새로운 라우팅 프로토콜의 제안
본 논문에서는 최선의 경로를 보장하지 못하는 EA-AODV를 개선하여 새로운 라우팅 프로토콜을 제안한다. 제안하는 라우팅 프로토콜은 EA-AODV와는 반대로 RREP 패킷이 아닌 RREQ 패킷 전송 과정 중에 에너지 잔량을 비교하여 경로를 결정한다. RREQ 패킷에 노드의 에너지 잔량 정보를 추가하고, RREQ 패킷을 수신한 노드는 라우팅 테이블에 에너지 정보도 함께 저장한다. 각 노드는 RREQ 패킷을 수신하면 먼저 자신의 라우팅 테이블에 같은 목적지를 가진 정보가 저장되어 있는지 확인한다.
같은 목적지를 가진 정보가 없을 경우 라우팅 테이블에 해당 RREQ 패킷의 정보를 저장하고 다시 주변 노드로 RREQ 패킷을 브로드캐스팅 한다. 같은 목적지를 가진 정보가 있을 경우에는 저장되어 있는 홉 수 및 에너지 정보와 비교하여 라우팅 테이블 갱신 여부를 결정한다. 만일 자신이 RREQ 패킷의 목적지 노드인 경우, 첫 RREQ 패킷을 수신한 후에 설정해 놓은 시간만큼 다른 RREQ 패킷의 수신을 허용하여 최적의 경로를 선택한다. 제안하는 라우팅 프로토콜의 동작 알고리즘은 그림 3 에 나타내었다.
PPT Slide
Lager Image
제안하는 프로토콜의 동작 알고리즘 Fig. 3 Algorithm of the proposed protocol
그림 2 에서 AODV와 EA-AODV는 2번째로 도착한 패킷들을 모두 폐기하였다. 하지만 제안하는 프로토콜에서는 즉시 폐기 하지 않고 목적지 정보와 홉 수를 먼저 비교한다. 5번 노드의 경우 4번 노드에게서 나중에 RREQ 패킷을 수신하지만 라우팅 테이블에 저장되어 있는 2번 노드의 RREQ 패킷의 정보와 비교하였을 때 4번 노드의 경로에 포함된 에너지 잔량이 더 크기 때문에 4번 노드에게 수신한 RREQ 패킷의 정보로 라우팅 테이블 정보를 갱신한다. 같은 방식으로 목적지 노드는 RREQ 패킷을 수신한 후에 나중에 도착한 8번 노드가 포함된 경로의 에너지 잔량이 가장 좋기 때문에 그림 4 와 같은 경로로 RREP 패킷이 전송되고, 데이터는 그 반대의 경로로 전송된다.
PPT Slide
Lager Image
제안하는 프로토콜에서 RREP 패킷의 전송 경로 Fig. 4 RREP transmission path of the proposed protocol
Ⅳ. 성능 평가
앞에서 AODV와 EA-AODV, 그리고 본 논문에서 제안하는 프로토콜의 동작을 살펴보았다. 이 장에서는 시뮬레이션을 통하여 각 프로토콜의 성능을 정량적으로 비교하고자 한다. 시뮬레이터로는 NS-3 (Network Simulator – 3) [6] 를 사용하였다. 먼저 그림 2 의 간단한 3x3 격자 형태의 토폴로지를 사용하여 시뮬레이션 하였다. 인접한 노드와의 간격을 80m로 설정하였다. 사용한 통신 방식은 802.11a로 최대 120m의 전송 범위를 가진다. 소스 노드(1번 노드)가 1초 간격으로 1kbyte 크기의 UDP 패킷을 목적지 노드(9번 노드)로 송신하는 시뮬레이션을 30초 동안 실행하였다.
소스 노드에서 목적지 노드까지 패킷이 도달하는데 소요되는 시간을 그림 5 에 나타내었다. AODV는 11번 패킷과 22번 패킷 전송 시에, EA-AODV는 21번 패킷 전송 시에 일시적으로 패킷 전송 지연이 발생하는 것을 볼 수 있다. 이는 데이터 전송 중에 에너지가 모두 소진되어 동작을 멈추는 노드가 발생하였기 때문이다. 그림 2 에서 AODV의 경우에는 6번 노드, EA-AODV의 경우에는 2번 노드와 5번 노드의 에너지가 일찍 소진될 것을 쉽게 예상할 수 있다. 이와 같이 동작을 멈추는 노드들로 인하여 데이터 전송 경로가 끊어지게 되고, 새로운 전송 경로를 재탐색하는 과정에서 지연이 크게 발생하는 것이다. 그에 비하여 본 논문에서 제안하는 프로토콜은 에너지 잔량이 적은 노드가 전송 경로에 포함되는 것을 피하기 때문에 전송 경로의 안정성을 높일 수 있다.
PPT Slide
Lager Image
3x3 토폴로지에서 패킷의 전송 지연 Fig. 5 End-to-end delay of packet in 3x3 topology
다음으로 노드의 수를 36개로 늘리고, 6x6의 격자 형태 토폴로지에서 시뮬레이션을 진행하였다. 패킷의 전송 속도를 1packet/sec에서 10packet/sec까지 변화시키면서 라우팅 프로토콜들의 경로의 생존 시간 비교하였다. 매 시뮬레이션마다 노드의 에너지 잔량을 0.1J과 5.0J 사이에서 랜덤하게 설정하였다. 시뮬레이션 시간은 100초로 설정하였다. 시뮬레이션 결과는 그림 6 에 나타내었다.
PPT Slide
Lager Image
6x6 토폴로지에서 각 라우팅 프로토콜의 경로의 수명 Fig. 6 Path Lifetime of each protocol in 6x6 topology
그림 6 에서 제안한 프로토콜의 경로의 생존 시간이 가장 높은 것을 볼 수 있다. 송신 노드에서 목적지 노드까지의 경로 중에서 가장 에너지 잔량이 높은 경로를 선택하기 때문에 다른 라우팅 프로토콜보다 경로의 수명을 보장하는 것을 확인 할 수 있다. 초당 패킷의 전송량이 많아질수록 노드의 에너지 소모량이 커지기 때문에 노드가 동작을 빨리 멈추게 되고 경로의 생존시간이 짧아진다. 제안하는 라우팅 프로토콜 역시 노드의 에너지 소모량이 커져 경로의 수명은 점점 짧아지지만 최초의 경로를 선택할 때 에너지 잔량이 가장 좋은 경로를 선택하기 때문에 다른 라우팅 프로토콜보다 경로의 안정성을 보장한다.
마지막으로 36개의 노드를 500m x 500m 공간에 완전히 랜덤하게 배치한 토폴로지에서 시뮬레이션 수행하였다. 모든 노드가 동일한 에너지 잔량을 가진 상태에서 일정 시간 동안 데이터를 전송하고 난 후, 각 노드의 잔여 에너지의 표준편차를 계산하여 전체 네트워크에서 노드의 에너지가 얼마나 균형적으로 사용되었는지를 비교하였다. 모든 노드의 잔여 에너지 초기값을 10.0J로 크게 설정하여, 시뮬레이션 시간 동안 에너지가 모두 소진되는 경우가 발생하지 않도록 하였다. 시뮬레이션 시간은 총 800초이고, 100초마다 송수신 노드를 랜덤하게 변경하였다. 패킷의 전송 간격은 1초로 설정하였다. 시뮬레이션 결과는 그림 7 과 같다.
PPT Slide
Lager Image
랜덤 토폴로지에서 노드 잔여 에너지의 표준편차 Fig. 7 Standard deviation of node residual energy in random topology
송수신 노드 및 패킷 전송에 사용된 노드의 에너지 잔량은 다른 노드에 비해 에너지의 소모량이 크다. 송수신 노드가 변경될 때마다 제안하는 라우팅 프로토콜은 현재의 상황에서 잔여 에너지가 큰 노드들로 이루어진 경로를 선택하기 때문에 전체 네트워크에서 노드 에너지를 고르게 사용한다. 그림 7 은 시뮬레이션이 종료 한 후 각 노드에 남아 있는 에너지 값에 대한 표준 편차를 보여 준다. 제안하는 라우팅 프로토콜이 AODV와 EA-AODV에 비해, 노드들의 잔여 에너지의 표준 편차가 작은 것을 확인할 수 있다. 표준편차가 작다는 것은 그만큼 제안하는 라우팅 프로토콜이 전체 네트워크의 밸런스를 유지하는 것을 확인할 수 있다.
위의 시뮬레이션들을 통해서 제안하는 라우팅 프로토콜이 안정성이 높은 전송 경로를 선택하여 높은 패킷 수신율을 보장하고 전체 네트워크의 밸런스를 유지하는 것을 확인할 수 있다.
Ⅴ. 결 론
본 논문에서는 무선 애드혹 네트워크에서 데이터 전송 경로의 안정성 및 전체 네트워크의 밸런스를 높이는 새로운 라우팅 프로토콜을 제안하였다. 제안하는 라우팅 프로토콜은 RREQ 패킷에 노드의 에너지 잔량을 담아 전송하고 갱신함으로써 데이터 전송 시 가장 에너지 잔량이 높은 경로를 선택하게 하였다. NS-3를 이용한 시뮬레이션을 통하여 제안하는 라우팅 프로토콜이 AODV와 EA-AODV보다 안정성이 좋은 경로를 선택하는 것을 검증하였다.
Acknowledgements
This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education, Science and Technology(2011-0023856).
BIO
김형직(Hyungjik Kim)
2012년 국민대 전자공학과 학사
2014년 국민대 전자공학과 석사
2015년 3월-현재 국민대학교 보안-스마트 전기 자동차학과 박사과정
※관심분야 : 무선 통신 네트워크, 센서 네트워크, IoT
최선웅(Sunwoong Choi)
1998년 서울대 전산과학과 학사
2000년 서울대 전산과학과 석사
2005년 서울대 전기,컴퓨터공학부 박사
2005년 9월~2007년 2월 삼성전자 통신연구소 책임연구원
2007년 3월~현재 국민대학교 전자공학부 부교수
※관심분야 : 유무선 통신네트워크, 모바일 컴퓨팅, 시스템 성능 분석
References
Perkins C. , Bhagwat P. 1994 “Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers,” ACM SIGCOMM Computer Communication Review 24 (4) 234 - 244    DOI : 10.1145/190809.190336
Johnson D. , Maltz D. , Broch J. “DSR: the dynamic source routing protocol for multihop wireless ad hoc networks,” Addison-Wesley in Ad Hoc NetworkIng Boston, MA 2001
Perkins C. , Belding-Royer E. , Das S. “Ad hoc On-Demand Distance Vector (AODV) Routing,” RFC 3561 July 2003
Zhu J. , Wang X. 2011 “Model and Protocol for Energy-Efficient Routing over Mobile Ad Hoc Networks,” IEEE Transactions on Mobile Computing 10 (11) 1546 - 1557    DOI : 10.1109/TMC.2010.259
Tamilarasi M. , Palanivelu T. G. 2008 “Integrated Energy-Aware Mechanism for MANETs using On-demand Routing,” International Journal of Computer and Information Engineering 2 (3) 212 - 216
http://www.nsnam.org/