이동 애드혹 네트워크는 송신노드가 인프라 네트워크를 사용하지 않고, 인접한 통신노드와 직접 통신함으로써 멀리 떨어져 있는 목적지노드와 통신하는 네트워크 구조를 말하며, 주로 IEEE 802.11 무선 랜[1]을 사용한다. 애드혹 네트워크에서는 멀리 떨어져 있는 목적지 노드와 원활하게 통신하기 위해서는 효율적인 라우팅 프로토콜이 필요하다. 이동 애드혹 네트워크용 라우팅 프로토콜은 통신노드의 이동성 등에 의해 채널상태가 빈번하게 변하기 때문에 채널상태 변화에 잘 대응하면서도 동작은 간단하고 신뢰성이 높으며 라우팅 루프가 발생하지 않아야 한다.

지금까지 연구된 라우팅 프로토콜들을 경로 메트릭에 따라 분류하면 링크상태(link-state)에 기반을 두고 통신경로를 찾는 기법과 distance-vector에 기반을 두고 경로를 찾는 기법으로 구분할 수 있으며, distancevector 기법은 주로 송신노드와 목적지노드 사이의 홉수(hop)를 경로 메트릭으로 사용한다. 라우팅 경로를 설정 시점 또는 운영하는 방법에 따라 분류하면 proactive 기법과 reactive 기법으로 분류할 수 있다. Proactive 기법은 모든 통신노드가 라우팅 테이블을 보유하고 있으며, 인접노드들과 라우팅 정보를 교환하면서 통신 네트워크 내 모든 통신노드와의 라우팅 경로를 미리 설정해놓는 방식으로 DSDV[2], OLSR[3,4] 기법이 여기에 해당된다. 반면에 reactive 기법은 송신노드에서 전송할 데이터가 발생하면 경로설정 패킷을 주고받기 시작하여 라우팅 경로를 설정하는 방식으로 AODV[5,6], DSR [7,8] 기법이 있다. Proactive 기법은 모든 통신노드가 라우팅 테이블을 관리하면서 인접노드와 라우팅 정보를 토대로 다른 노드와 라우팅 경로를 설정하기 때문에 table-driven 방식이라고도 하며, reactive 기법은 송신노드가 전송할 데이터가 발생하였을 때 전송경로를 설정절차를 시작하기 때문에 on-demand 기법이라고도 한다. 참고문헌[9]에서는 지금까지 제안된 라우팅 프로토콜들을 각 프로토콜들이 보유한 특징에 따라 9개 범주로 분류하고 각 프로토콜 기법들을 간략하게 설명하였다.

이동 애드혹 네트워크는 이동성이나 무선채널의 변동성 때문에 송신노드가 라우팅 경로를 한 개만 설정하는 것은 통신 신뢰성을 낮출 수 있기 때문에 다수 개의 통신경로를 설정하는 다중경로 라우팅 프로토콜에 대한 연구도 많이 진행되었다. 참고문헌[10]에서는 지금까지 연구된 다중경로 라우팅 기법들을 특징에 따라 5가지 범주로 (delay-aware, reliable, minimum overhead, energy efficient, 하이브리드 기법 등) 분류하였으며, 각 방식을 간략하게 기술하였다. 다중경로를 설정할 때는 두 개 이상의 경로가 서로 겹치지 않아야 신뢰성을 높일 수 있으며, 이렇게 설정한 다중경로는 협력통신(cooperative communication) 기법을 활용하는데도 유용하게 사용할 수 있다[11].

본 논문에서는 다중경로 라우팅 프로토콜 연구에 대한 첫걸음으로 기존 프로토콜들의 장단점을 분석하기 위해 널리 알려져 있는 대표적인 네 가지 단일경로 라우팅 프로토콜을 NS-3 네트워크 시뮬레이터[12]를 사용하여 성능비교를 수행하였다. 본 논문의 구성은 다음과 같다. II장에서는 본 논문에서 성능비교에 사용하는 대표적인 네 가지 라우팅 프로토콜을 자세하게 기술하였으며, III장에서 네 가지 라우팅 프로토콜의 성능평가 결과와 성능비교 결과를 제시하며, IV장에서 결론으로 끝맺는다.

지금부터는 본 논문에서 성능평가에 사용한 네 가지 라우팅 프로토콜을 자세하게 설명한다. Proactive 라우팅 기법과 reactive 라우팅 기법을 대표하는 두 가지 라우팅 프로토콜을 각각 선정하였으며, 선정된 네 가지 라우팅 프로토콜은 모두 NS-3 네트워크 시뮬레이터에 구현되어 있다.

DSDV (destination-sequenced distance vector) 라우팅 기법은 distance-vector 기법을 사용하여 송신노드와 목적지노드 사이의 최단거리를 찾아내는 벨만-포드 알고리즘을 사용하며, 라우팅 루프를 예방하기 위해 시퀀스 번호를 사용한다. 모든 통신노드는 라우팅 테이블을 관리하며, 라우팅 테이블에는 목적지노드 주소가 테이블 인덱스로 사용되며, 라우팅 테이블의 각 항목에는 다음 노드 (next-hop) 주소, 라우팅 메트릭에 해당하는 목적지노드까지의 홉수, 목적지노드의 시퀀스번호와 라우팅 정보의 참신성을 나타내기 위한 경로 타이머 등의 정보가 저장되어 있다. 각 통신노드는 짝수번호의 시퀀스 번호를 사용하며 새로운 라우팅 정보를 공유하기 위해 라우팅 업데이트 메시지를 전송할 때마다 시퀀스 번호를 2만큼 증가시킨다(즉, SN=SN+2). 하지만 인접노드와의 통신 경로가 파손된 것을 인지하였을 때에는 해당사실을 인접 통신노드에게 급히 알려야 하는데 이때에는 시퀀스 번호를 1만큼 증가한 홀수번호를 사용하며, 파손된 통신 링크를 사용하는 모든 라우팅 경로의 메트릭 값을 무한대 (∞)로 설정하여 만든 라우팅 정보를 인접노드에게 전송함으로써 해당 경로를 더 이상 사용하지 않도록 유도한다. 라우팅 광고 메시지를 수신한 통신노드는 광고 메시지 내에 실려 있는 라우팅 정보와 해당 통신노드가 관리하는 라우팅 테이블 내의 정보를 서로 비교하여 다음 조건을 만족한 경우에는 라우팅 테이블 내의 경로정보를 광고 메시지에 실려 있는 경로정보로 교체한다.

임의의 통신노드가 인접 통신노드와 라우팅 정보를 공유하기 위한 방법으로 해당 통신노드의 라우팅 테이블 정보를 주기적으로 광고하거나, 통신경로 파손 등 경로정보 변동사항이 발생했을 때 즉시 광고하는 두 가지 방법이 있다. 광고 메시지에 경로 정보를 싣는 방법은 라우팅 테이블에 기재된 모든 라우팅 정보를 싣는 full dump 방법과 변경된 경로정보만 싣는 incremental dump 방법이 있다. 광고메시지에 의한 부하 량을 낮추면서 인접노드와 라우팅 정보를 효율적으로 공유하기 위해서는 full dump 방법과 incremental dump 방법을 적절하게 혼용하여 사용하도록 권장하고 있다.

OLSR (optimized link state routing) 프로토콜은 성능비교에 사용한 나머지 세 개 프로토콜과 달리 라우팅 메트릭으로 link state를 사용하였으며, DSDV 프로토콜과 마찬가지로 proactive 기법을 사용하는 라우팅 프로토콜이다. 따라서 라우팅 정보를 인접노드와 공유하기 위해 DSDV 프로토콜과 유사하게 주기적으로 제어 메시지를 교환한다. 그러나 교환하는 메시지의 크기를 줄이고 해당 메시지들의 재전송 횟수를 줄이면서 라우팅 경로 설정 및 운영에 의해 야기되는 망 부하를 감소시켰기 때문에 OLSR 기법을 최적화된 기법이라고 일컫는다.

OLSR 프로토콜은 MPR (multipoint relay) 노드를 사용함으로써 인접 통신노드와 라우팅 정보를 공유하기 위해 주고받는 제어 메시지의 양을 감소시켰다. MPR 노드란 1개 홉 인접노드 (one hop neighbors) 중에서 양방향 링크가 모두 양호한 노드를 의미하며, 모든 목적지노드와의 라우팅 경로를 설정할 때는 반드시 MPR 노드를 사용해야 한다. MPR 노드를 사용하여 통신경로를 설정한 예를 그림 1에 나타내었다.

위 그림은 중앙에 위치한 송신노드 N이 1개 홉 인접노드 8개 중에서 4개 노드를 MPR 노드로 선택하였으며 MPR 노드를 통해 2개 홉 인접노드들과 통신경로를 설정한 예를 보여준다. 여기에서 굵은 선은 인접 통신 노드들과 설정된 라우팅 경로를 의미한다. 모든 통신노드는 인접 통신노드 테이블 (neighbor table), 토폴로지 테이블 (topology table 또는 infra-forwarding DB), 그리고 라우팅 테이블 (routing table)을 관리하며, 이러한 테이블과 제어메시지들을 사용하여 목적지노드들과 통신경로를 설정하는 과정을 아래에 간략하게 기술하였다.

HELLO 메시지를 수신한 1개 홉 인접 통신노드들은 수신한 HELLO 메시지를 인접 통신노드들에게 재차 전달하지 않으며, MPR 노드들만 TC 제어 메시지를 전송할 수 있기 때문에 경로설정을 위해 OLSR 프로토콜에서 사용하는 제어 메시지 개수가 다른 라우팅 프로토콜에서 사용한 제어 메시지 개수보다 상대적으로 줄어든다. 그리고 최신 MPR 노드 정보를 관리하기 위해 시퀀스 번호를 사용하며, MPR 노드 집합에 변경이 발생할 때마다 시퀀스 번호 값을 1씩 증가시킨다. 그래서 각 통신노드들이 토폴로지 테이블을 관리할 때 수신한 TC 메시지 정보를 토폴로지 테이블에 반영하기 위해서는 TC 메시지 내의 MPR Selector 시퀀스 번호가 토폴로지 테이블 내의 MPR Selector 시퀀스 번호보다 커야 한다.

AODV (ad-hoc on-demand distance vector) 프로토콜은 송신노드에서 전송할 패킷이 발생했을 때 제어패킷 RREQ (route request)와 RREP (route reply)를 사용하여 목적지노드와 통신경로를 설정하는 on-demand 라우팅 기법으로 통신 루프를 방지하기 위해 DSDV 프로토콜처럼 시퀀스 번호를 사용한다. 시퀀스 번호를 사용함에 있어서 DSDV 프로토콜과의 차이점은 짝수번호가 아니라 순차적으로 증가하는 값을 사용한다는 것이다. DSDV 기법과 같이 distance vector 기법을 사용하며, 모든 통신노드에 대한 경로정보를 관리할 필요가 없기 때문에 각 통신노드의 부하를 줄일 수 있다. 각 통신노드는 시퀀스 번호와 broadcast ID를 관리하며, 새로운 RREQ 패킷을 전송할 때 마다 broadcast ID 값을 증가하기 때문에 <송신노드 주소, broadcast ID>세트는 RREQ 패킷을 완전하게 구분할 수 있다. 송신노드에서 데이터가 발생하면 라우팅 테이블을 검색하여 목적지 노드로의 경로정보가 있는지 먼저 확인한 후, 경로정보가 없을 경우에는 RREQ 패킷을 전송하며 RREQ 패킷에는 다음과 같은 정보가 포함되어 있다.

RREQ 패킷을 수신한 통신노드는 해당 정보를 라우팅 테이블에 저장하고, 홉수를 증가시킨 뒤 인접노드들에게 방송한다. 해당 통신노드가 동일한 RREQ 패킷을 중복 수신한 경우에는 (이전에 수신했던 RREQ 패킷과 지금 수신한 RREQ 패킷의 <송신노드 주소, broadcast ID> 값이 동일한 경우) 해당 RREQ 패킷을 폐기한다. 한편 네트워크 내의 통신노드들이 RREQ 패킷을 인접노드로 전송할 때마다 그림 2와 같이 역방향 라우팅 경로가 만들어진다.

한편 목적지노드가 RREQ 패킷을 수신하면 RREP 패킷을 만들어서 송신노드에게 전송함으로써 송신노드와 목적지노드간의 통신경로 설정을 완성한다. 목적지 노드는 가장 먼저 도착한 RREQ 패킷에 대해서만 응답하며, 그 이후에 도착하는 동일한 <송신노드 주소, broadcast ID> 값을 갖는 RREQ 패킷들은 모두 폐기한다. 목적지노드가 전송한 RREP 패킷은 최초 RREQ 패킷의 역방향 전달경로를 따라서 송신노드로 전달된다. RREP 패킷이 송신노드로 전달될 때마다, 송신노드와 목적지노드가 사용할 순방향 경로가 그림 3과 같이 설정되며, 순방향 경로로 설정되지 못한 나머지 역방향 경로들은 유효시간 이후에 삭제된다.

DSR (dynamic source routing) 프로토콜은 송신노드가 목적지노드까지의 라우팅 경로정보를 패킷헤더에 포함시켜 전송하기 때문에 주변 통신노드에서 라우팅 테이블을 관리할 필요가 없으며 주변 통신노드와 라우팅 정보를 공유하기 위해 광고메시지를 전송할 필요가 없다. 다만 경로설정에 참여하는 통신노드들은 라우터 캐쉬(route cache)에 라우팅 경로관련 정보를 임시 저장하여 관리한다. DSR 기법은 다른 방식에 비해 각 통신노드가 갖는 부담은 줄였지만 라우팅 경로정보가 패킷 헤더에 포함되어 있기 때문에 송신노드와 목적지노드 사이의 경로가 길면 패킷의 길이가 증가하므로 DSR 기법은 소규모 통신 네트워크 환경에만 적용할 수 있다.

DSR 프로토콜은 경로설정 과정과 경로관리 과정으로 구성되어 있으며, 송신노드에서 전송할 패킷이 발생하였고 라우터 캐쉬에 목적지노드까지의 통신경로 정보가 없으면 route request 패킷을 전송하면서 경로설정 과정을 시작한다. Route request 패킷에는 송신노드와 목적지노드 주소, request id와 route request 패킷이 전송되면서 거쳐 가는 경로정보를 저장하기 위한 route record 필드를 보유하고 있다. 각 통신노드는 수신한 route request 패킷의 <송신노드 주소, request id> 정보를 발췌하여 라우터 캐쉬에 저장한다. 그래서 임의의 통신노드가 route request 패킷을 수신하면 해당 통신노드의 라우터 캐쉬에 저장되어 있는 <송신노드 주소, request id> 값과 비교하여 동일한 route request 패킷을 수신했는지 검사한다. 그래서 동일한 패킷을 재수신한 경우에는 해당 패킷을 폐기하며, 그렇지 않은 경우에는 해당 노드의 주소를 route request 패킷의 route record에 추가한 뒤 해당 패킷을 인접노드들에게 전송한다. 목적지노드가 route request 패킷을 수신하면 route reply 패킷을 생성하여 송신노드에게 전달하며, 송신노드가 해당 route reply 패킷을 수신하면 송신노드와 목적지노드간의 경로설정이 완료된다.

경로관리 과정은 경로 중간에 위치한 통신링크에 문제가 발생했을 경우 이를 해결하는 과정을 담당한다. 먼저 통신링크 문제를 인지한 해당 통신노드가 route error 패킷을 생성하여 송신노드로 전송하며, 해당 route error 패킷에는 통신링크 양 끝에 위치한 두 개 통신노드의 주소를 포함하고 있다. 따라서 route error 패킷을 수신한 통신노드들은 라우팅 캐쉬를 검색하여 해당 통신링크를 포함하고 있는 모든 통신경로에서 문제가 발생한 해당 통신링크를 절단해낸다.

먼저 라우팅 프로토콜 성능비교를 위해 본 논문에서 사용한 성능평가 환경에 대해서 설명하고자 한다. 먼저 통신영역의 크기는 700m × 700m 정사각형이며, 통신영역 내 모든 통신노드들은 random waypoint 모델[8]에 따라 독립적으로 움직이는 환경을 고려하였다. 각 통신노드들은 IEEE 802.11 무선 랜 표준을 사용하며 통신노드의 개수는 가변이다. Random waypoint 이동성 모델은 각 통신노드들이 해당 위치에서 다음 이동할 목적지 위치를 확률적으로 랜덤하게 결정하고, 균일분포에 따라 (0, υm/s) 구간에서 이동속도를 결정한 뒤, 다음 이동 목적지까지 확률적으로 결정한 이동속도에 따라 움직인다. 이동 목적지에 도달하면 일정한 시간 동안(pause time) 기다린 뒤, 다음 이동 목적지를 선정하는 절차를 반복한다.

각 통신노드의 초기위치는 정사각형 통신영역 내에서의 랜덤 위치에 각각 독립적으로 존재한다고 가정하였다. 통신영역내 송신노드와 수신노드는 1개만 존재하며, CBR(constant bit rate) 트래픽 모델에 따라 고정속도로 데이터 패킷을 주고받는 환경을 가정하였다. 무선통신 채널모델은 로그 거리 전파모델 (log distance propagation loss model)을 사용하였으며, 거리에 따른 전력손실 값은 다음 식으로 표현된다.

여기에서 L₀는 참조거리(d₀)에서의 경로손실 값이며, n는 경로손실 지수이다.

본 논문에서 성능평가는 네트워크 시뮬레이터인 NS-3[12]를 사용하였으며, 성능평가에 사용한 시스템 및 트래픽 파라미터를 표 1에 나타내었다. 성능평가 척도로는 시스템처리량(throughput)과 패킷 전달비율(packet delivery ratio)을 사용하였으며, 두 성능척도의 의미는 다음과 같다. 시스템처리량은 시뮬레이션 동안 수신노드가 성공적으로 수신한 총 패킷 크기(bits)를 패킷을 최종으로 수신한 시간 값과 패킷을 처음 수신한 시간 값의 차이로 나눈 값으로 정의하였으며, 패킷 전달비율은 전송한 총 패킷 크기 (bits) 대비 성공적으로 수신한 패킷 크기(bits)의 비율로 정의하였다.

그림 4와 그림 5는 통신노드의 random waypoint 이동성 모델에서 이동속도가 υ = 5m/s이며, 통신영역 내의 통신노드 개수가 각각 40, 50, 60, 70, 그리고 80개인 경우 네 가지 라우팅 프로토콜의 성능을 비교하였다. 먼저 그림 4에는 시스템처리량 성능 비교결과를 나타내었으며, 성능비교 결과를 참조하면 AODV 프로토콜의 시스템 처리량이 전반적으로 우수하며, DSR 프로토콜의 시스템 처리량이 상대적으로 낮음을 알 수 있다. 특히 DSR 프로토콜은 시스템 처리량의 변화가 통신노드 개수에 따라 변화폭이 큼을 알 수 있다.

그림 5는 그림 4와 동일한 환경에서 네 가지 라우팅 프로토콜의 패킷 전달비율 성능을 서로 비교하였다. 성능평가 결과에 따르면 그림 4 결과와 유사하게 AODV 프로토콜의 패킷 전달 비율이 대체적으로 우수하며, DSR 프로토콜의 패킷 전달 비율이 상대적으로 낮음을 알 수 있다.

그림 6에서 그림 9까지는 random waypoint 이동성 모델에서 통신노드의 이동속도가 가변인 경우(2, 5, 10m/s) 통신영역 내의 통신노드 개수가 각각 40, 50, 60, 70, 그리고 80개인 경우 각 통신 프로토콜 별로 시스템처리량 성능을 비교하였다. 먼저 그림 6에는 AODV 프로토콜의 시스템처리량 성능을 다양한 이동성 환경에서 서로 비교하여 나타내었다. 성능평가 결과에 따르면 통신노드의 이동속도가 증가할수록 시스템 처리량 성능이 감소함을 알 수 있다. 즉 통신노드의 이동속도가 증가하면 통신경로의 가변성이 증가하여 통신경로를 재설정하는 빈도가 증가하기 때문에 시스템 오버헤더가 증가하여 시스템처리량이 감소한다.

그림 7에는 통신노드의 이동속도 변화에 따른 DSDV 프로토콜의 시스템처리량 변화를 나타내었다. 그림 6의 AODV 프로토콜 성능평가 결과와 유사하게 통신노드의 이동속도가 증가할수록 DSDV 프로토콜의 시스템처리량 성능도 감소함을 알 수 있다. DSDV 프로토콜은 proactive 라우팅 기법이기 때문에 통신경로 가변성이 증가하면 라우팅 오버헤더가 증가하여 시스템 처리량 성능이 점차 감소함을 알 수 있다.

그림 8에는 통신노드의 이동속도 변화에 따른 DSR 프로토콜의 시스템처리량 변화를 나타내었다. DSR 프로토콜은 다른 세 가지 프로토콜보다 통신노드의 개수와 통신노드의 이동속도 변화에 따른 시스템처리량 변화가 매우 큼을 알 수 있다.

그림 9에는 통신노드의 이동속도 변화에 따른 OLSR 프로토콜의 시스템처리량 변화를 나타내었다. 성능평가 결과에 따르면 OLSR 프로토콜이 다른 세 가지 프로토콜과 비교하여 시스템처리량 변화폭이 상대적으로 작을 뿐만 아니라 시스템처리량의 평균값도 다른 세 가지 기법에 비해 상대적으로 낮음을 알 수 있다.

본 논문에서는 이동 애드혹 네트워크용 라우팅 프로토콜 네 개를 선정하여 NS-3 네트워크 시뮬레이터를 사용하여 성능평가를 수행한 후 성능결과를 서로 비교하고 분석하였다. 라우팅 프로토콜은 proactive 기법 2개(DSDV, OLSR)와 reactive 기법 2개(AODV, DSR)를 사용하였으며 성능평가 척도로는 시스템처리량과 패킷 전달비율을 사용하였다. 성능비교 결과 전반적으로 AODV 기법의 성능이 우수함을 알 수 있었다.

차후 연구에서는 협력통신에서 다중경로를 설정하여 송수신 노드가 통신할 수 있는 라우팅 프로토콜을 설계하고 성능평가를 수행할 예정이다.