애드혹 네트워크에서 경로 안정성 향상을 위한 라우팅 프로토콜

A Routing Protocol for Improving Path Stability in Mobile Ad-hoc Networks

  • cc icon
  • ABSTRACT

    모바일 애드혹 네트워크의 노드는 일반적으로 에너지의 용량이 제한된 배터리를 사용한다. 경로의 안정성을 유지하기 위해 균형 잡힌 에너지 소비가 중요하다. 본 논문에서는 애드혹 네트워크에서 데이터 전송 경로의 안정성을 향상시키는 것을 목표로 한다. 이를 위해 데이터를 전송할 수 있는 최단 전송 경로 중에서 노드 에너지 잔량의 최소값이 가장 큰 경로를 선택하는 새로운 라우팅 프로토콜을 제안한다. 에너지 잔량의 최소값이 가장 큰 경로는 다른 경로보다 상대적으로 긴 수명을 갖게 되어 데이터 전송에 안정성을 향상 시킬 수 있다. NS-3 시뮬레이터를 사용하여 제안하는 라우팅 프로토콜이 AODV와 EA-AODV보다 수명이 긴 안정적인 경로를 제공하는 것을 확인한다.


    Nodes of Mobile ad-hoc network usually use the energy-limited battery. Balanced energy consumptionis important to maintain path’s stability. In this paper, we focus on improving the stability of the routing path in mobile ad-hoc networks. For that purpose, we propose a new routing protocol to find the highest minimum node residual energy path among shortest paths. The largest path of minimum value of the remain energy has a longer life than other paths to improve the reliability to data-transmission. Using ns-3 simulator, we show that the proposed routing protocol can provide more long-life stable routing path than AODV and EA-AODV.

  • KEYWORD

    애드혹 네트워크 , 라우팅 프로토콜 , 노드 에너지 , 경로 안정성 , AODV , EA-AODV

  • Ⅰ. 서 론

    무선 애드혹 네트워크는 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의 동작 알고리즘을 나타내었다.

    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 패킷과 홉 수가 동일하기 때문에 무시된다.

    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에 나타내었다.

    그림 2에서 AODV와 EA-AODV는 2번째로 도착한 패킷들을 모두 폐기하였다. 하지만 제안하는 프로토콜에서는 즉시 폐기 하지 않고 목적지 정보와 홉 수를 먼저 비교한다. 5번 노드의 경우 4번 노드에게서 나중에 RREQ 패킷을 수신하지만 라우팅 테이블에 저장되어 있는 2번 노드의 RREQ 패킷의 정보와 비교하였을 때 4번 노드의 경로에 포함된 에너지 잔량이 더 크기 때문에 4번 노드에게 수신한 RREQ 패킷의 정보로 라우팅 테이블 정보를 갱신한다. 같은 방식으로 목적지 노드는 RREQ 패킷을 수신한 후에 나중에 도착한 8번 노드가 포함된 경로의 에너지 잔량이 가장 좋기 때문에 그림 4와 같은 경로로 RREP 패킷이 전송되고, 데이터는 그 반대의 경로로 전송된다.

    Ⅳ. 성능 평가

    앞에서 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번 노드의 에너지가 일찍 소진될 것을 쉽게 예상할 수 있다. 이와 같이 동작을 멈추는 노드들로 인하여 데이터 전송 경로가 끊어지게 되고, 새로운 전송 경로를 재탐색하는 과정에서 지연이 크게 발생하는 것이다. 그에 비하여 본 논문에서 제안하는 프로토콜은 에너지 잔량이 적은 노드가 전송 경로에 포함되는 것을 피하기 때문에 전송 경로의 안정성을 높일 수 있다.

    다음으로 노드의 수를 36개로 늘리고, 6x6의 격자 형태 토폴로지에서 시뮬레이션을 진행하였다. 패킷의 전송 속도를 1packet/sec에서 10packet/sec까지 변화시키면서 라우팅 프로토콜들의 경로의 생존 시간 비교하였다. 매 시뮬레이션마다 노드의 에너지 잔량을 0.1J과 5.0J 사이에서 랜덤하게 설정하였다. 시뮬레이션 시간은 100초로 설정하였다. 시뮬레이션 결과는 그림 6에 나타내었다.

    그림 6에서 제안한 프로토콜의 경로의 생존 시간이 가장 높은 것을 볼 수 있다. 송신 노드에서 목적지 노드까지의 경로 중에서 가장 에너지 잔량이 높은 경로를 선택하기 때문에 다른 라우팅 프로토콜보다 경로의 수명을 보장하는 것을 확인 할 수 있다. 초당 패킷의 전송량이 많아질수록 노드의 에너지 소모량이 커지기 때문에 노드가 동작을 빨리 멈추게 되고 경로의 생존시간이 짧아진다. 제안하는 라우팅 프로토콜 역시 노드의 에너지 소모량이 커져 경로의 수명은 점점 짧아지지만 최초의 경로를 선택할 때 에너지 잔량이 가장 좋은 경로를 선택하기 때문에 다른 라우팅 프로토콜보다 경로의 안정성을 보장한다.

    마지막으로 36개의 노드를 500m x 500m 공간에 완전히 랜덤하게 배치한 토폴로지에서 시뮬레이션 수행하였다. 모든 노드가 동일한 에너지 잔량을 가진 상태에서 일정 시간 동안 데이터를 전송하고 난 후, 각 노드의 잔여 에너지의 표준편차를 계산하여 전체 네트워크에서 노드의 에너지가 얼마나 균형적으로 사용되었는지를 비교하였다. 모든 노드의 잔여 에너지 초기값을 10.0J로 크게 설정하여, 시뮬레이션 시간 동안 에너지가 모두 소진되는 경우가 발생하지 않도록 하였다. 시뮬레이션 시간은 총 800초이고, 100초마다 송수신 노드를 랜덤하게 변경하였다. 패킷의 전송 간격은 1초로 설정하였다. 시뮬레이션 결과는 그림 7과 같다.

    송수신 노드 및 패킷 전송에 사용된 노드의 에너지 잔량은 다른 노드에 비해 에너지의 소모량이 크다. 송수신 노드가 변경될 때마다 제안하는 라우팅 프로토콜은 현재의 상황에서 잔여 에너지가 큰 노드들로 이루어진 경로를 선택하기 때문에 전체 네트워크에서 노드 에너지를 고르게 사용한다. 그림 7은 시뮬레이션이 종료 한 후 각 노드에 남아 있는 에너지 값에 대한 표준 편차를 보여 준다. 제안하는 라우팅 프로토콜이 AODV와 EA-AODV에 비해, 노드들의 잔여 에너지의 표준 편차가 작은 것을 확인할 수 있다. 표준편차가 작다는 것은 그만큼 제안하는 라우팅 프로토콜이 전체 네트워크의 밸런스를 유지하는 것을 확인할 수 있다.

    위의 시뮬레이션들을 통해서 제안하는 라우팅 프로토콜이 안정성이 높은 전송 경로를 선택하여 높은 패킷 수신율을 보장하고 전체 네트워크의 밸런스를 유지하는 것을 확인할 수 있다.

    Ⅴ. 결 론

    본 논문에서는 무선 애드혹 네트워크에서 데이터 전송 경로의 안정성 및 전체 네트워크의 밸런스를 높이는 새로운 라우팅 프로토콜을 제안하였다. 제안하는 라우팅 프로토콜은 RREQ 패킷에 노드의 에너지 잔량을 담아 전송하고 갱신함으로써 데이터 전송 시 가장 에너지 잔량이 높은 경로를 선택하게 하였다. NS-3를 이용한 시뮬레이션을 통하여 제안하는 라우팅 프로토콜이 AODV와 EA-AODV보다 안정성이 좋은 경로를 선택하는 것을 검증하였다.

  • 1. Perkins C., Bhagwat P. 1994 “Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers,” [ACM SIGCOMM Computer Communication Review] Vol.24 P.234-244 google doi
  • 2. Johnson D., Maltz D., Broch J. 2001 “DSR: the dynamic source routing protocol for multihop wireless ad hoc networks,” [in Ad Hoc NetworkIng] google
  • 3. Perkins C., Belding-Royer E., Das S. July 2003 “Ad hoc On-Demand Distance Vector (AODV) Routing,” [RFC 3561] google
  • 4. Zhu J., Wang X. 2011 “Model and Protocol for Energy-Efficient Routing over Mobile Ad Hoc Networks,” [IEEE Transactions on Mobile Computing] Vol.10 P.1546-1557 google doi
  • 5. Tamilarasi M., Palanivelu T. G. 2008 “Integrated Energy-Aware Mechanism for MANETs using On-demand Routing,” [International Journal of Computer and Information Engineering] Vol.2 P.212-216 google
  • 6. http://www.nsnam.org/ google
  • [그림 1.] EA-AODV의 동작 알고리즘
    EA-AODV의 동작 알고리즘
  • [그림 2.] 3x3 토폴로지에서 AODV와 EA-AODV의 동작 비교
    3x3 토폴로지에서 AODV와 EA-AODV의 동작 비교
  • [그림 3.] 제안하는 프로토콜의 동작 알고리즘
    제안하는 프로토콜의 동작 알고리즘
  • [그림 4.] 제안하는 프로토콜에서 RREP 패킷의 전송 경로
    제안하는 프로토콜에서 RREP 패킷의 전송 경로
  • [그림 5.] 3x3 토폴로지에서 패킷의 전송 지연
    3x3 토폴로지에서 패킷의 전송 지연
  • [그림 6.] 6x6 토폴로지에서 각 라우팅 프로토콜의 경로의 수명
    6x6 토폴로지에서 각 라우팅 프로토콜의 경로의 수명
  • [그림 7.] 랜덤 토폴로지에서 노드 잔여 에너지의 표준편차
    랜덤 토폴로지에서 노드 잔여 에너지의 표준편차