Advanced
Channel Aware Reliable Routing Protocol in Wireless Multimedia Sensor Networks
Channel Aware Reliable Routing Protocol in Wireless Multimedia Sensor Networks
Journal of the Korea Institute of Information and Communication Engineering. 2014. Feb, 18(2): 459-465
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/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : October 25, 2013
  • Accepted : November 29, 2013
  • Published : February 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
병석 조
주현 이
형근 박
hkpark@koreatech.ac.kr

Abstract
최근 비디오와 오디오와 같은 멀티미디어 데이터를 전송할 수 있는 무선 멀티 미디어 센서 네트워크의 개발의 필요성이 커지고 있으며, 멀티미디어 데이터의 효율적 전송을 위해서는 QoS의 제공이 중요하다. 애드혹 네트워크 환경에서 널리 사용되는 AODV 라우팅 프로토콜은 소스 노드에서 목적지 노드까지의 홉 수가 가장 적은 경로를 선택하는 알고리즘으로 동작 원리가 단순한 반면, 홉 수 외 다른 것은 고려하지 않기 때문에 QoS 제공에는 적합하지 않다. 본 논문에서는 이러한 점을 보완하기 위해 각 링크의 채널 상태를 고려한 AODV 알고리즘을 제안하고자 한다. 제안하는 알고리즘은 각 링크의 채널 상태를 반영하는 전송 성공률과 이에 따른 재전송 횟수를 계산하여 이를 홉 수에 반영하였다. 제안한 알고리즘은 링크 상태를 홉 수에 반영함으로써 기존의 AODV 알고리즘을 크게 변경시키지 않고 효율적으로 QoS 제공할 수 있다는 장점이 있다.
Keywords
Ⅰ. 서 론
무선 센서 네트워크란 온도나 압력과 같은 정형화된 물리적 현상을 사람의 개입이 없이 스스로 센싱하여, 목적지 노드로 데이터를 전송하는 네트워크 기술이다. 그리고 최근의 카메라와 마이크의 발달로 비디오와 오디오와 같은 멀티미디어 데이터를 전송할 수 있는 무선 멀티 미디어 센서 네트워크의 개발의 필요성이 커지고 있다 [1] .
이러한 무선 센서 네트워크에 있어서 라우팅 프로토콜 선택은 중요한데, 이는 경로를 어떻게 설정하느냐에 따라 데이터 전송의 효율이 극도로 차이가 나기 때문이다. 애드혹 센서 네트워크에 적용되는 라우팅 알고리즘은 Table-driven 방식과 On-Demand 방식으로 구분할 수 있으며 대표적인 알고리즘으로 OLSR(Optimized Link State Routing) [2] , DSDV(Destination-Sequenced Distance-Vector routing) [3] , DSR(Dynamic Source Routing) [4] 및 AODV(Ad hoc On-Demand Distance Vector Routing) [5] 등이 있다. 이중에서 AODV는 단순한 알고리즘으로 애드혹 환경에서 널리 활용되고 있다.
AODV 라우팅은 주변의 노드들을 탐지하여 오직 노드들의 홉수만을 고려하여 전송 경로를 완성하는 프로토콜이다. 다른 타 프로토콜에 비해 동작 알고리즘이 단순하여 손쉽게 적용할 수 있는 프로토콜이긴 하나 홉 수 외에는 다른 어떠한 것도 고려를 하지 않기 때문에 취약점도 존재한다. Hop수만으로 경로가 설정되면 링 크의 수용성이나, 큐의 딜레이, 그리고 전송 확률등을 고려하지 못함으로 최단 Hop수의 경로를 완성 하여도, 극도의 큐 딜레이를 갖거나, 이미 과부하 상태인 링크를 경로로 선정하여 멀티미디어 QoS를 보장해야 하는 네트워크에서는 적절하지 못할 수 있다. 이러한 점을 개선하기 위해 [6] 에서는 End-to-End 대역폭을 계산하는 알고리즘을 이용하여 QoS 경로를 설정하는 방법을 제안하였으며, [7] 경로 설정 시 여러개의 경로를 선택하여 처음 선택한 경로에서 데이터 전송이 실패할 경우 미리 선택한 다른 경로를 통해 전송을 하여 패킷 loss 상황을 방지하는 방법을 제안하였다.
본 논문에선 AODV 프로토콜에 노드간의 각 구간에서의 전송 성공 확률을 적용하여, 보다 성공 확률이 확실한 경로를 채택하는 방법을 제안하고자 한다. 이를 위해 전송 성공 확률을 홉 카운트에 반영한 수정된홉 카운트 개념을 제시하였다. 제안된 알고리즘의 장점은 수정된 홉 카운트를 기존의 AODV 알고리즘에 적용하여 AODV 알고리즘에 큰 변형을 가하지 않고도 링크 상태를 경로 결정에 반영할 수 있다는 데에 있다. 먼저 2장에선 AODV 프로토콜의 기본 동작 과정을 소개 후 3장에서 수정된 AODV 알고리즘을 제안하고, 4장에서 성능에 대한 분석, 5장에서 결론를 도출하도록 한다.
Ⅱ. AODV 라우팅 프로토콜
AODV는 에드혹 네트워크에서 대표적인 On-Demand 방식의 라우팅 프로토콜로써 애드혹 네트워크 내의 모든 노드들은 데이터 전송으로 인한 경로 설정의 필요가 있는 경우에 한에 라우팅 테이블을 갱신한다. 먼저 AODV에 사용되는 용어를 정리하면 다음과 같다.
AOCV 관련 용어Table. 1Terms Used in AODV
PPT Slide
Lager Image
AOCV 관련 용어 Table. 1 Terms Used in AODV
RREQ 는 소스 노드가 목적지 노드를 탐색하기 위해 사용하는 메시지이다. RREQ 를 발송하는 노드는 데이터 전달을 처음에 요구한 소스 노드와 경로단절이 생겼을 때 경로 복구를 위해 경로 복구작업을 시작하는 중간 노드가 될 수 있다. 이들 노드들은 RREQ 메시지를 애드 혹 네트워크 내에 플러딩(flooding)을 한다. RREQ 메시지를 수신받은 노드는 자신이 목적지 노드이거나 또는 목적지까지의 라우팅 경로를 알고 있다면 RREP 메시지를 전송함으로 응답하게 된다. RREP 메시지는 RREQ 메시지를 처음에 송신한 노드에게 유니캐스트 방식으로 전달된다. RREQ 를 받은 노드가 자신이 목적지 노드도 아니고 목적지 노드까지의 경로를 알고 있지 않다면, RREQ 소스노드까지의 역 경로(reverse route)를 라우팅테이블에 저장한 후, 받은 RREQ 메시지를 이웃노드에게 전달(forwarding)하게 된다.
AODV 라우팅 프로토콜의 경로 설정 절차를 정리하면 다음과 같다.
  • 1) 소스 노드에서 인접 노드로 RREQ 메시지를 전송한다.
  • 2) 각 인접노드에서는 수신된 RREQ 메시지의 목적지 노드의 주소와, 현재 지나온 중간노드, Hop수를 확인하고 목적지 노드에 해당 안 될 경우 Hop수를 증가시킨 후 인접노드로 RREQ를 전달한다. RREQ 메시지 발송시 중복 발송을 방지하기 위해 소스 노드는 RREQ ID에 1을 추가 하고 발송을 하며 각 노드를 지나칠 때 마다 Hop 수를 1씩 증가시킨다.
  • 3) 목적지 노드가 모든 RREQ 메시지를 전송 받게 되면 라우팅 테이블의 Hop 카운터를 확인하여 가장 Hop 카운터가 적은 경로를 통해 RREP 메시지를 보냄으로서 전송경로가 완성이 된다.
  • 4) 목적지 노드로부터 RREP를 수신한 소스 노드는 완성된 경로를 통해 데이터를 전송한다. 한편 소스노드가 RREQ 메시지를 보낸 후 일정 시간이 지나도 RREP를 받지 못할 경우, 소스 노드는 더 멀리 있는 노드에게도 RREQ가 전달될 수 있도록 RREQ 전송 범위인 TTL 값을 증가시키고 위의 과정을 반복 수행한다.
Ⅲ. 신뢰성향상을 위한 AODV 알고리즘
기존의 AODV 알고리즘은 비교적 간단한 과정으로 가장 적은 홉 수로 구성된 경로를 설정할 수 있다. 하지만 홉 수만으로 경로를 선택하기 때문에 링크 상태가 좋지 못한 경로를 선택하여, 전송 성능 저하 및 전송 지연 등을 초래할 수 있고 이는 QoS 보장이 필요한 멀티미디어 센서 네트워크 환경에 적합하지 못하다. 따라서 본 논문에서는 이러한 점을 보완하기 위해 각 링크의 전송 성공률을 고려한 AODV 알고리즘을 제안하고자 한다. 제안하는 알고리즘의 기본 아이디어는 상태가 좋지 않은 링크에서 발생하는 전송 지연을 홉 수가 증가해서 발생하는 전송 지연과 동일하게 보고 이를 홉 수에 반영한 것이다.
- 3.1. 채널 상태 기반 수정된 홉 수
알고리즘 설명에 앞서 수정된 홉 수의 계산을 위한 관련 파라미터를 표 2 .과 같이 정의 하였다.
수정된 Hop카운터 계산을 위한 관련 파라미터Table. 2Parameters Used in Modified Hop Count
PPT Slide
Lager Image
수정된 Hop카운터 계산을 위한 관련 파라미터 Table. 2 Parameters Used in Modified Hop Count
본 논문에서는 각 노드에서 RREQ 발송 시 채널 상태를 판단하기 위한 파일럿(pilot) 신호를 추가함으로써 RREQ가 거쳐간 링크의 채널상태를 알 수 있다고 가정하였다. 각 노드는 수신된 RREQ의 파일럿 신호를 바탕으로 각 링크의 Pi 를 계산 할 수 있다.
또한 본 논문에서는 각 노드가 데이터 전송 시 전송 실패가 발생하면 재전송을 한다고 가정하였다. 여기서 재전송 과정은 하나의 홉이 추가되는 것과 동일하게 볼 수 있을 것이다. 이러한 재전송이 발생하는 경우를 고려하면 링크의 전송성공률을 높일 수 있을 것이며, 그림 1 에서 이를 확인할 수 있다.
PPT Slide
Lager Image
재전송 횟수에 따른 전송성공률 Fig. 1 Successful transmission rate according to retransmission count
본 논문에서는 이를 역으로 이용하여 특정 링크에서 요구 전송 성공률에 도달하기 까지 발생할 수 있는 재전송 횟수를 계산하였다. 먼저 각 링크의 전송 성공률에 요구 전송성공률 Pr 을 만족시키기 위한, 즉 Pi > Pr 이 되기 위한 재전송 횟수 K의 값을 구하기 위해 식 (1)을 전개하여 식 (2)와 같이 최대 재전송 횟수를 구하였다.
PPT Slide
Lager Image
PPT Slide
Lager Image
하지만 여기서 결정된 재전송 횟수 K의 값은 요구 전송 성공률에 도달하기까지 재전송에 실패한 경우의 총 재전송 횟수, 즉 요구 전송 성공률에 도달하기 위한 최대 재전송 횟수이므로 이를 그대로 수정된 Hci 로 적용하는 건 적절하지 않다. 따라서 식 (1)에서 구한 최대 재전송 횟수 K를 바탕으로 평균 재전송 횟수를 구하면 식 (3)와 같다.
PPT Slide
Lager Image
식 (3)에서 구한 요구 전송확률을 만족시키는 평균 재전송 횟수 Hci 기존의 AODV 알고리즘에 적용함으로서 채널 상태를 보장할 수 있는 AODV 알고리즘을 만들 수 있다.
- 3.2. 채널 상태 기반 홉 수를 적용한 AODV 알고리즘
본 논문에서는 이렇게 수정된 홉 수 계산과정을 기존의 AODV 알고리즘에 적용함으로서 경로 선정 시 채널 상태를 고려할 수 있도록 하였다. 목적지 노드에서는 홉 수를 최종적으로 계산할 때 수정된 Hci 들을 합산 함으로서 최종 홉 수를 계산하고 이 값들을 비교하여 가장 홉 수가 작은 경로를 채택하게 된다. 수정된 홉 수의 합은 링크간의 전송 성공률을 고려하였기 때문에 최종적으로 홉 수를 보고 경로를 정했을 지라도, 전송 성공률 또한 가장 좋은 경로를 택하게 되는 것이다.
이런 방식을 기존 AODV 알고리즘에 적용을 하면 다음과 같다.
  • (1) 시작 노드는 주변 노드를 탐지하여 RREQ 메시지에 노드 정보와 식(3)을 활용한 전송 성공률에 따른 변화된 Hop수를 전송한다.
  • (2) RREQ 메시지를 받은 중간 노드는 다시 다음 노들에게 전송 성공률에 따른 변화된 Hop수 정보를 목적지 노드가 받을 때 까지 전송한다. 일정 시간 경과 후에도 RREP 메시지가 전송 되지 않을 경우는 TTL의 범위를 확장하여 RREQ를 재전송 한다.
  • (3) 목적지 노드가 RREQ메세지들을 받게 되면 합쳐진 수정된 Hop수 중 가장 적은 수를 가진 경로를 선택하여 RREP메시지를 전송함으로 최종 경로 완성이 된다.
Ⅳ. 시뮬레이션 결과
제안된 Hop 카운터 계산방식에 대한 성능분석을 위해 Matlab 시뮬레이션을 통하여 성능 평가를 하였다. 시뮬레이션은 기존의 AODV 알고리즘과 논문에서 제안한 수정된 AODV 알고리즘의 전체 전송성공확률 및 지연시간을 비교 시뮬레이션 하였다. 두 가지 경우 모두 전송 확률은 재전송 없이 이루어진 경우, 재전송 1번까지 고려한 경우, 재전송 2번까지 고려한 경우 까지 총 세 가지 경우를 시뮬레이션 하였다.
그림 2 그림 3 는 목적지 노드와 시작 노드의 거리는 20m × 20m 으로 고정한 상태에서 각각 밀도의 따른 총 전송구간의 전송확률을 및 지연상태를 보여준다. 여기서 전체전송성공 확률은 최종 결정된 경로의 있는 모든 구간의 전송성공확률 곱한 값으로 정의 하였다. 그림 2 에서 제안된 방식의 경우 Hop 카운터가 전송구간의 전송성공확률을 고려하여 계산되기 때문에 기존의 방식보다 더 높은 전체 전송성공확률을 보여주며 재전송을 더 많이 고려할수록 전체 전송성공 확률이 높아지는 것을 확인할 수 있다. 그러나 노드의 밀도가 높아질수록 기존방식과 제안된 방식의 수치가 비슷해지는 결과를 볼 수 있는데 그 이유는 노드의 밀도가 높아질수록 기존의 방식이 수정된 방식에 비해 훨씬 더 적은 홉 수를 가진 경로를 선택하게 되고 따라서 모든 구간의 전송성공확률의 곱으로 계산되는 전체 전송성공확률이 높아지기 때문이다. 여기서 제안된 방식은 노드의 밀도가 0.5이하 일 때 가장 적합한 차이를 보인다고 결론지을 수 있다.
PPT Slide
Lager Image
노드 밀도에 따른 전체 전송성공률 Fig. 2 Successful transmission rate according to node density
PPT Slide
Lager Image
노드 밀도에 따른 지연 시간 Fig. 3 Transmission delay according to node density
그림 3 은 노드 밀도의 변화에 따른 총 전송구간의 지연 상태를 보여준다. 여기서 전송 지연은 소스노드에서 전송된 패킷이 목적지 노드에 도착하기 까지 걸리는 평균 지연 시간을 의미하며, 이러한 지연 시간은 목적지 노드까지의 홉 수 및 재전송 횟수 등으로 결정된다. 본 실험에서는 한 홉을 단위 시간으로 보았으며 지연 시간을 홉 수로 나타내었다. 이 시뮬레이션을 통하여 제안된 알고리즘이 기존의 AODV 알고리즘에 비해 전송 지연이 적으며 재전송 가능 횟수가 작아질수록 이러한 전송 지연이 커지는 것을 알 수 있다. 이는 기존의 방식이 적은 홉수의 경로를 선택하더라도 데이터 전송과정에서 제안한 방식보다 전송 실패확률이 높아 재전송이 더 자주 발생하기 때문이다. 한편 본 실험에서도 그림 2 에서와 같이 노드 밀도가 어느 정도 높아지게 되면 제안한 방식이 노드 밀도가 적었을 때보다 많은 홉 수를 포함하는 경로를 선택할 가능성이 커지므로 지연 성능의 차이가 거의 없어지는 것을 알 수 있다.
그림 4 는 노드 밀도를 0.5로 고정하고 시작 노드와 목적지 노드 간의 거리를 10m×10m부터 50m×50m까지 변화를 주며 시뮬레이션 한 결과이다. 전반적으로 노드 간 거리가 멀어질수록 전체적인 전송성공률은 떨어지는데 이는 거리가 멀어질수록 목적지 노드까지 도달하는데 필요한 홉 수가 증가하고 목적지 노드까지의 홉 수가 늘어나면 반대로 전송성공률은 떨어지기 때문이다. 이 결과에서도 마찬가지로 제안한 방식이 기존의 방식에 비해 전반적으로 높은 전송성공률을 나타내는 것을 알 수 있으며, 노드 간의 거리가 멀어질수록 이러한 전체 전송성공률의 차이는 더 커지는 것을 확인할 수 있다.
PPT Slide
Lager Image
노드간 거리에 따른 전체 전송성공률 Fig. 4 Successful transmission rate according to node distance
그림 5 는 노드 밀도를 0.3으로 고정한 상태에서 시작 노드와 목적지 노드의 거리를 10m×10m부터 50m×50m까지 변화에 따른 총 전송 지연 상태를 나타낸 것이다. 전체적으로 노드간 거리가 멀어질수록 전송 지연이 커지는데 이는 거리가 멀수록 전송에 필요한 홉 수가 늘어나고 전송 성공률이 떨어지면서 재전송 횟수 또한 증가하기 때문이다.
PPT Slide
Lager Image
노드간 거리에 따른 전체 지연 시간 Fig. 5 Transmission delay according to node distance
이 시뮬레이션 결과에도 제안된 알고리즘이 기존의 AODV 알고리즘에 비해 전반적으로 전송 지연이 적으며 이는 재전송 가능 횟수가 높아질수록 이러한 전송 지연이 작아지는 것을 알 수 있다.
Ⅴ. 결 론
본 논문에서는 멀티미디어 센서 네트워크에서 QoS를 제공하기 위한 수정된 AODV 알고리즘을 제안하였다. 제안된 알고리즘은 각 링크의 전송 성공률에 따른 재전송 횟수를 계산하여 AODV 라우팅을 위한 홉 수에 반영함으로써, 기존의 AODV 알고리즘에 큰 수정을 가하지 않고 링크 상태를 반영하였다. 시뮬레이션 결과 제안된 알고리즘의 기존의 방식에 비해 소스노드에서 목적지 노드까지의 전체 전송성공률과 지연시간에서 더 우수한 성능을 보였다. 또한 이러한 성능 차이는 노드 간 밀도가 작고 노드 사이의 거리가 멀수록 증가하는 경향을 보이는 것을 확인할 수 있다.
BIO
조병석(Byeong Seok Cho)
2008년 3월 ~ 현재 : 한국기술교육대학교 전기전자통신공학부
※관심분야 : 무선통신, 멀티미디어 센서네트워크
이주현(Juhyeon Lee)
2006년 2월 한국기술교육대학교 정보기술공학부 (공학사)
2010년 2월 한국기술교육대학교 전기전자통신공학과 (공학석사)
2010년 3월~현재: 한국기술교육대학교 전기전자통신공학과 박사과정
※관심분야 : M2M, 무선자원관리, 인지무선통신
박형근(Hyung-Kun Park)
1995.년 2월고려대학교 전자공학과 (공학사), 1997년 2월고려대학교 전자공학과 (공학석사)
2000년 8월고려대학교 전자공학과 (공학박사)
2000년 9월~2001년 8월: University of Colorado at Colorado Springs, Postdoc.
2001년 9월~2004년 2월: 현대시스콤, 선임연구원
2004년 3월~현재 : 한국기술교육대학교 전기전자통신공학부 부교수
※관심분야 : M2M, 무선자원관리, 인지무선통신
References
Akyildiz I. F. , Melodia T. , Chowdhury K. R. 2007 “A survey on wireless multimedia sensor networks” Computer Networks 51 (4) 921 - 960    DOI : 10.1016/j.comnet.2006.10.002
Clausen T. , Jacquet P. 2003 “Optimized Link State Routing Protocol (OLSR).” RFC 3626 IETF Network Working Group
Perkins C. E. , Bhagwat P. 1994 "Highly dynamic destinationsequenced distance-vector routing (DSDV) for mobile computers." ACM SIGCOMM Computer Communication Review 24 (4)
Johnson D. B. , Maltz D. A. 1996 "Dynamic source routing in ad hoc wireless networks." Kluwer International Series in Engineering and Computer Science 353 153 - 181    DOI : 10.1007/978-0-585-29603-6_5
Perkins C. E. , Royer E. M. 1999 "Ad-hoc on-demand distance vector routing," in Proceedings of Second IEEE Workshop on Mobile Computing Systems and Applications 90 - 100
Lee S. J. , Gerla M. 2000 "AODV-BR: Backup routing in ad hoc networks." in Proceedings of WCNC. 2000 IEEE 3 1311 - 1316
Sedrati M. , Bilami A. , Benmohamed M. 2011 "M-AODV: AODV variant to Improve Quality of Service in MANETs." International Journal of Computer Science Issues 8 (1) 429 - 436