무선 센서 네트워크란 온도나 압력과 같은 정형화된 물리적 현상을 사람의 개입이 없이 스스로 센싱하여, 목적지 노드로 데이터를 전송하는 네트워크 기술이다. 그리고 최근의 카메라와 마이크의 발달로 비디오와 오디오와 같은 멀티미디어 데이터를 전송할 수 있는 무선 멀티 미디어 센서 네트워크의 개발의 필요성이 커지고 있다[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는 에드혹 네트워크에서 대표적인 On-Demand 방식의 라우팅 프로토콜로써 애드혹 네트워크 내의 모든 노드들은 데이터 전송으로 인한 경로 설정의 필요가 있는 경우에 한에 라우팅 테이블을 갱신한다. 먼저 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 알고리즘은 비교적 간단한 과정으로 가장 적은 홉 수로 구성된 경로를 설정할 수 있다. 하지만 홉 수만으로 경로를 선택하기 때문에 링크 상태가 좋지 못한 경로를 선택하여, 전송 성능 저하 및 전송 지연 등을 초래할 수 있고 이는 QoS 보장이 필요한 멀티미디어 센서 네트워크 환경에 적합하지 못하다. 따라서 본 논문에서는 이러한 점을 보완하기 위해 각 링크의 전송 성공률을 고려한 AODV 알고리즘을 제안하고자 한다. 제안하는 알고리즘의 기본 아이디어는 상태가 좋지 않은 링크에서 발생하는 전송 지연을 홉 수가 증가해서 발생하는 전송 지연과 동일하게 보고 이를 홉 수에 반영한 것이다.

알고리즘 설명에 앞서 수정된 홉 수의 계산을 위한 관련 파라미터를 표 2.과 같이 정의 하였다.

본 논문에서는 각 노드에서 RREQ 발송 시 채널 상태를 판단하기 위한 파일럿(pilot) 신호를 추가함으로써 RREQ가 거쳐간 링크의 채널상태를 알 수 있다고 가정하였다. 각 노드는 수신된 RREQ의 파일럿 신호를 바탕으로 각 링크의 P_i를 계산 할 수 있다.

또한 본 논문에서는 각 노드가 데이터 전송 시 전송 실패가 발생하면 재전송을 한다고 가정하였다. 여기서 재전송 과정은 하나의 홉이 추가되는 것과 동일하게 볼 수 있을 것이다. 이러한 재전송이 발생하는 경우를 고려하면 링크의 전송성공률을 높일 수 있을 것이며, 그림 1에서 이를 확인할 수 있다.

본 논문에서는 이를 역으로 이용하여 특정 링크에서 요구 전송 성공률에 도달하기 까지 발생할 수 있는 재전송 횟수를 계산하였다. 먼저 각 링크의 전송 성공률에 요구 전송성공률 P_r 을 만족시키기 위한, 즉P_i>P_r이 되기 위한 재전송 횟수 K의 값을 구하기 위해 식 (1)을 전개하여 식 (2)와 같이 최대 재전송 횟수를 구하였다.

하지만 여기서 결정된 재전송 횟수 K의 값은 요구 전송 성공률에 도달하기까지 재전송에 실패한 경우의 총 재전송 횟수, 즉 요구 전송 성공률에 도달하기 위한 최대 재전송 횟수이므로 이를 그대로 수정된 H_ci로 적용하는 건 적절하지 않다. 따라서 식 (1)에서 구한 최대 재전송 횟수 K를 바탕으로 평균 재전송 횟수를 구하면 식 (3)와 같다.

식 (3)에서 구한 요구 전송확률을 만족시키는 평균 재전송 횟수 H_ci 기존의 AODV 알고리즘에 적용함으로서 채널 상태를 보장할 수 있는 AODV 알고리즘을 만들 수 있다.

본 논문에서는 이렇게 수정된 홉 수 계산과정을 기존의 AODV 알고리즘에 적용함으로서 경로 선정 시 채널 상태를 고려할 수 있도록 하였다. 목적지 노드에서는 홉 수를 최종적으로 계산할 때 수정된 H_ci들을 합산 함으로서 최종 홉 수를 계산하고 이 값들을 비교하여 가장 홉 수가 작은 경로를 채택하게 된다. 수정된 홉 수의 합은 링크간의 전송 성공률을 고려하였기 때문에 최종적으로 홉 수를 보고 경로를 정했을 지라도, 전송 성공률 또한 가장 좋은 경로를 택하게 되는 것이다.

이런 방식을 기존 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이하 일 때 가장 적합한 차이를 보인다고 결론지을 수 있다.

그림 3은 노드 밀도의 변화에 따른 총 전송구간의 지연 상태를 보여준다. 여기서 전송 지연은 소스노드에서 전송된 패킷이 목적지 노드에 도착하기 까지 걸리는 평균 지연 시간을 의미하며, 이러한 지연 시간은 목적지 노드까지의 홉 수 및 재전송 횟수 등으로 결정된다. 본 실험에서는 한 홉을 단위 시간으로 보았으며 지연 시간을 홉 수로 나타내었다. 이 시뮬레이션을 통하여 제안된 알고리즘이 기존의 AODV 알고리즘에 비해 전송 지연이 적으며 재전송 가능 횟수가 작아질수록 이러한 전송 지연이 커지는 것을 알 수 있다. 이는 기존의 방식이 적은 홉수의 경로를 선택하더라도 데이터 전송과정에서 제안한 방식보다 전송 실패확률이 높아 재전송이 더 자주 발생하기 때문이다. 한편 본 실험에서도 그림 2에서와 같이 노드 밀도가 어느 정도 높아지게 되면 제안한 방식이 노드 밀도가 적었을 때보다 많은 홉 수를 포함하는 경로를 선택할 가능성이 커지므로 지연 성능의 차이가 거의 없어지는 것을 알 수 있다.

그림 4는 노드 밀도를 0.5로 고정하고 시작 노드와 목적지 노드 간의 거리를 10m×10m부터 50m×50m까지 변화를 주며 시뮬레이션 한 결과이다. 전반적으로 노드 간 거리가 멀어질수록 전체적인 전송성공률은 떨어지는데 이는 거리가 멀어질수록 목적지 노드까지 도달하는데 필요한 홉 수가 증가하고 목적지 노드까지의 홉 수가 늘어나면 반대로 전송성공률은 떨어지기 때문이다. 이 결과에서도 마찬가지로 제안한 방식이 기존의 방식에 비해 전반적으로 높은 전송성공률을 나타내는 것을 알 수 있으며, 노드 간의 거리가 멀어질수록 이러한 전체 전송성공률의 차이는 더 커지는 것을 확인할 수 있다.

그림 5는 노드 밀도를 0.3으로 고정한 상태에서 시작 노드와 목적지 노드의 거리를 10m×10m부터 50m×50m까지 변화에 따른 총 전송 지연 상태를 나타낸 것이다. 전체적으로 노드간 거리가 멀어질수록 전송 지연이 커지는데 이는 거리가 멀수록 전송에 필요한 홉 수가 늘어나고 전송 성공률이 떨어지면서 재전송 횟수 또한 증가하기 때문이다.

이 시뮬레이션 결과에도 제안된 알고리즘이 기존의 AODV 알고리즘에 비해 전반적으로 전송 지연이 적으며 이는 재전송 가능 횟수가 높아질수록 이러한 전송 지연이 작아지는 것을 알 수 있다.

본 논문에서는 멀티미디어 센서 네트워크에서 QoS를 제공하기 위한 수정된 AODV 알고리즘을 제안하였다. 제안된 알고리즘은 각 링크의 전송 성공률에 따른 재전송 횟수를 계산하여 AODV 라우팅을 위한 홉 수에 반영함으로써, 기존의 AODV 알고리즘에 큰 수정을 가하지 않고 링크 상태를 반영하였다. 시뮬레이션 결과 제안된 알고리즘의 기존의 방식에 비해 소스노드에서 목적지 노드까지의 전체 전송성공률과 지연시간에서 더 우수한 성능을 보였다. 또한 이러한 성능 차이는 노드 간 밀도가 작고 노드 사이의 거리가 멀수록 증가하는 경향을 보이는 것을 확인할 수 있다.