차량용 네트워크에서의 성능 향상을 위한 라우팅 프로토콜

Ⅰ. 서 론

애드혹 네트워크(Ad hoc network)는 인프라 구축없이 네트워크 환경을 형성하도록 자체 구성되는 무선 모바일 노드로 구성되는 새로운 기술이라고 할 수 있다. VANET(Vehicular Ad Hoc Networks)[1][2]은 애드혹 네트워크의 한 유형으로서 차량은 네트워크 인프라 구축없이 서로 정보를 교환 할 수 있는 노드 역할을 한다. VANET은 노드의 이동성을 예측하기 힘든 고유한 특성으로 인해 기존 네트워크에 비해 여러 가지 장애 요소를 가지고 있다. VANET에서 해결하여야 할 중요한 과제는 라우팅 성능이라고 할 수 있다.

기존 애드혹 네트워크 기반의 라우팅 프로토콜을 VANET에 적용하게 되면 성능이 떨어지는 문제점을 가지게 된다. VANET 환경에서 중요한 문제는 도시 지역에서의 다양한 건물 형태에 따라 신호 약화와 신호 전달을 더 복잡하게 만드는 점도 고려해야 한다.

라우팅 프로토콜[3][4]은 라우팅 전략에 따라 토폴로지 기반(Topology-based) 라우팅 기법과 위치 기반(Location-based) 라우팅 기법으로 분류할 수 있다. 토폴로지 기반 라우팅은 원천지 노드(Source node)가 목적지 노드(Destination node)까지의 경로를 확보한 후 패킷을 전달하는 방식으로 프로액티브(Pro-active) 방식과 리액티브(Reactive) 방식이 있다.

프로액티브 라우팅 알고리즘은 각 노드가 네트워크상의 모든 다른 노드들에 대한 경로를 라우팅 테이블을 사용하여 유지관리하고 있으며 라우팅 테이블은 주기적으로 갱신된다. 이 기법은 테이블 관리를 위한 제어 메시지의 발생이 많은 문제점을 가지고 있다.

토폴로지 기반 라우팅 프로토콜은 원천지 노드와 목적지 노드 간의 경로를 확보한 후에 패킷 전송을 하기 때문에 확보된 경로 상에 있는 노드 중 하나라도 이동하게 되면 데이터 전달이 실패하게 되며 재전송을 위한 경로를 다시 확보해야 하는 문제점을 가지고 있다.

대부분의 라우팅 프로토콜에서는 각 노드들이 자신의 전송 범위내 이웃 노드의 정보만을 이용하여 패킷을 전달하는 기법을 적용하고 있다. 또한 노드의 밀집도에 관계없이 메시지를 전달 시도를 함으로써 밀집도가 낮은 경우는 목적지 노드를 만날 때가지 많은 시간을 기다리는 경우가 발생하므로 지연 시간이 길어지는 문제점을 가지고 있다.

이러한 문제를 해결하기 위해서 본 논문에서는 원천지 노드에서 메시지를 전송할 때 전송 범위내에서 연결 가능한 노드 수에 따라 전달하는 메시지의 수를 달리함으로써 메시지의 전달율을 높이고 짧은 지연시간을 가지도록 시도한다.

본 논문의 구성은 다음과 같다. 먼저 2장에서는 무선 네트워크 기반의 라우팅 알고리즘들의 특징과 문제점을 알아보고 3장에서는 제안하는 기법을 설명한다. 4장에서는 시뮬레이션을 통해 제안하는 알고리즘과 기존 연구와의 성능 비교를 한다. 마지막으로, 5장에서 본 논문의 결론을 맺는다.

Ⅱ. 관련 연구

VANET[5]-[7]은 종단간 연결을 보장되어 있지 않고 인터넷 환경이 열악한 네트워크에 적합한 차세대 네트워크이다. 종단간 연결이 보장되지 않는 환경에서는 각 노드는 전송할 메시지를 버퍼에 저장하고 노드 이동에 의해서 전송 범위내에서 다른 노드를 만나게 되면 메시지를 전달(Forward)하는 방식을 통해 최종 목적지까지 메시지를 전달하는 Store-and-Carry-Forward를 기반으로 하는 새로운 라우팅 프로토콜의 적용이 필요하다.

이러한 네트워크 환경에서 반응형(Reactive 혹은 On-demand) 라우팅 알고리즘은 라우팅 경로가 필요할 때만 경로 검색을 하게 된다. 따라서 다른 노드로 패킷을 보내고자하는 노드는 필요에 따라 경로를 검색하고 연결을 설정하여 패킷을 송수신한다.

이 두 가지 접근 방식은 고유의 장단점이 있으며 가장 많이 알려진 알고리즘은 AODV, DSR, DSDV, OLSR등이 있다. AODV는 동적 링크 상황에서 신속한 적응, 낮은 처리 능력 및 메모리 오버헤드, 낮은 네트워크 사용률을 요구하며 애드혹 네트워크 내의 목적지 노드에 대한 유니캐스트 경로를 결정한다. 시퀀스 번호를 사용하여 경로가 루프 현상을 가지지 않는 특징을 가지고 있다.

DSDV는 기존의 Bellman-Ford 라우팅 알고리즘을 기반으로 라우팅 업데이트를 주기적으로 브로드캐스트하는 라우팅 프로토콜이다. 현재 경로의 일부 링크가 끊어질 때 대체 경로를 사용할 수 있습니다. 이동성이 낮은 네트워크에서는 DSR이 경로 검색을 위해 또 다른 플러딩을 시작하기 전에 대체 경로를 시도 할 수 있으므로 AODV보다 좋은 성능을 가지고 있다.

동적 라우팅 프로토콜은 노드와 네트워크의 상태가 유동적일 때 적합한 라우팅 프로토콜[8]에는 직접 전송(Direct transmission) 방식, 에피데믹(Epidemic) 라우팅 프로토콜[9], 예측(Prophet) 라우팅 프로토콜[10], 스프레이 대기(Spray and wait) 라우팅 프로토콜[11]이 제안되고 있다.

에피데믹 프로토콜은 플러딩을 기본적으로 사용하여 노드가 이동하며 만나는 모든 노드에게 메시지를 전달한다. 패킷 전달 성공률은 높지만 비교적 과도한 트래픽이 발생하여 오히려 패킷 전송 성공률이 감소되는 문제점이 있다.

이러한 문제들을 해결하기 위해서 스프레이 대기 프로토콜이 제시되었다. 이는 전체 네트워크에서의 메시지 복사본 수를 제한함으로써 높은 효율성을 가지도록 시도하였다. 이 기법은 Spray phase와 Wait phase의 2가지 단계로 이루어져있다. Spray phase에서는 설정된 전체 복사본의 수를 N이라고 했을 때 N개의 다른 노드를 만날 때 N/2 개의 메시지를 전달하고 남아 있는 복제본의 수가 1개일 때 Wait phase로 전이한다. Wait phase에서는 해당 메시지의 목적지 노드를 마주치게 되는 경우에만 메시지를 직접 전달하게 된다.

이 기법은 노드의 밀집도에 관계없이 미리 설정된 복제본 개수를 생성시킴으로써 패킷 트래픽의 양이 많아짐으로써 전반적인 성능 저하가 발생할 수 있는 문제점을 가지고 있다.

본 논문에서는 VANET 환경에서 전송 범위내의 연결 가능한 노드 수에 따라 패킷 복제본의 수를 조절함으로써 발생되는 메시지의 수를 줄임으로써 패킷 전달율을 높이는 방법을 제시한다. 제안하는 알고리즘은 기존의 알고리즘과 비교하여 시뮬레이션을 통하여 패킷 전달율이 향상됨을 알 수 있다.

Ⅲ. 제안 알고리즘

제안 알고리즘은 Spray-and-Wait 알고리즘을 기본으로 한다. 전달 노드의 이웃 노드와의 연결 밀집도에 따라 패킷 복제본의 수를 조절함으로써 패킷전달율을 포함한 전반적인 성능 향상을 시도한다.

이웃 노드의 수가 일정수(Threshold)보다 많을 때는 메시지 복제본의 수를 줄이고 이웃 노드의 수가 적을 때는 메시지 복제본의 수를 늘여 준다. 이웃 노드의 수의 많을 때 복제본의 수를 줄이는 이유는 이웃 노드가 많기 때문에 복제본의 숫자가 작다하더라도 주변의 노드들에게 메시지가 전달될 가능성이 많아질 것을 예측할 수 있기 때문이다.

같은 방법으로 이웃 노드의 수의 적을 때 복제본의 수를 늘리는 이유는 이웃 노드가 상대적으로 적기 때문에 더 많은 복제본을 미리 전달해 두어야 향후 연결되는 노드가 있을 때 주변의 노드들에게 메시지가 전달될 가능성이 많아지기 때문이다. 즉, 이웃 노드가 많으면 메시지 복제본의 수를 줄이고 이웃 노드가 적으면 메시지 복제본의 수를 늘려 메시지 트래픽의 증감을 조절함으로 패킷전달율을 높이는 시도를 한다.

제안 알고리즘은 분배단계와 전달 단계로 이루어져 있으며 그림 1에 표시하였다. 분배 단계에서는 이웃 노드와의 연결도 값이 일정 수보다 크면 L 값을 감소시키고 일정수보다 작으면 L 값을 증가시킨 후 연결 가능한 이웃 노드에게 메시지 복사본의 수를 전달한다. 초기 L 값을 10으로 시뮬레이션을 여러 번 실행결과 성능이 비교적 좋게 나타나는 10으로 설정하였다.

Fig. 1.

Proposed algorithms

L 값이 1일 때는 Wait phase로 전이한다. Wait phase에서는 해당 메시지의 목적지 노드를 마주치는 경우에만 메시지를 직접 전달하게 된다. 일정수의 적정한 값은 시뮬레이션을 통해 L/3으로 설정하였다.

Ⅳ. 성능 평가

제안 알고리즘과 기존 알고리즘의 성능 비교하기 위하여 ONE 시뮬레이터[12]를 사용하여 시뮬레이션을 실행하였다. 시뮬레이션에서 사용한 여러 값들은 표 1에 제시되어 있다. 시뮬레이션에서는 제안 알고리즘(Proposed로 표기), Spray-and-Wait 알고리즘(Spray로 표기)과 Epidemic 알고리즘(Epidemic으로 표기)에 대하여 성능 측정을 실시하였다. 성능 비교를 다음과 같은 메트릭(Metric)을 사용하였다.

• • 메시지 전달율(Packet delivery ratio) : 전달 성공한 메시지 수와 생성 된 메시지 수의 비율
• • 평균 지연 시간(Average latency time) : 소스 노드에서 메시지가 생성된 후 목적지 노드에 성공적으로 전달되는 데 소요된 평균 시간
• • 제어 오버헤드율(Control overhead ratio) : 각 노드에서 수신한 실제 데이터 패킷에 대한 제어 패킷의 비율
• • 평균 버퍼링 시간(Average buffering time) : 다음 전달 노드에 패킷을 보낼 때까지의 노드에서의 평균 버퍼링 시간

Table 1.

Simulation parameters

첫 번째 시뮬레이션에서는 노드의 수를 10~100개로 변화시켜가면서 패킷 전달율의 변화를 시뮬레이션한 결과를 그림 2에서 보여주고 있다.

Fig. 2.

Comparisons of delivery ratio(buffer=5MB)

노드의 수가 40개 이하인 경우는 측정한 3개의 알고리즘이 거의 같은 패킷전달율을 나타내었으나 노드의 수가 많아짐에 따라 제안한 알고리즘의 성능이 비교 알고리즘에 비하여 7~20%정도로 개선됨을 알 수 있다. 노드의 수가 70~80개 구간인 경우 패킷전달율이 거의 동일하게 나타났으며 이는 일시적으로 패킷 발생 비율이 처리 속도를 따라 가지 못하는 것으로 판단이 되며 이는 다음 실험에서 버퍼의 크기를 늘림으로써 개선됨을 확인할 수 있었다.

버퍼의 크기를 2배(10MB)로 늘려서 실험한 결과는 그림 3에 표시되어 있다. 버퍼의 크기를 늘림으로써 노드에서 패킷의 보관 시간이 더 길어지게 되므로 전반적으로 모든 알고리즘의 패킷전달율이 높아짐을 알 수 있으며 특히 제안한 알고리즘은 타 알고리즘에 비해 좀 더 높은 비율로 패킷전달율이 상승하는 것을 알 수 있다.

Fig. 3.

Comparisons of delivery ratio(buffer=10MB)

두 번째 시뮬레이션에서는 평균 지연 시간을 측정 비교하여 그림 4에 표시하였다.

Fig. 4.

Comparisons of average latency time

노드의 갯수가 많아짐에 따라 제안 알고리즘이 Spray와 Epidemic에 비해서 더 좋은 성능을 나타냄을 알 수 있다. 노드의 수가 70개 정도까지는 평균지연시간이 점점 길어지는 결과가 나왔으나 노드 수가 70개 이상에서는 모든 오히려 알고리즘의 평균지연시간이 조금씩 줄어드는 현상이 발생하는 것을 관찰할 수 있다. 이는 노드의 수가 많아짐에 따라 연결될 수 노드의 개수가 증가하여 패킷전달율이 개선되기 때문에 목적지에 전달되는 지연시간도 줄어드는 것으로 판단이 된다.

제어오버헤드 비율을 실험한 결과는 그림 5에 표시하였다. 노드의 갯수가 점점 증가함에 따라 오버헤드비율이 제안 알고리즘이 제일 우수한 성능을 보이고 있음을 알 수 있다. 제어 오버헤드 비율이 낮다는 것은 그만큼 트래픽의 양이 적기 때문에 상대적으로 패킷 전달율이 우수한 성능을 나타냄을 알 수 있다.

Fig. 5.

Comparisons of average control overhead

그림 6은 노드에서의 버퍼링되는 평균 시간을 측정 비교한 시뮬레이션의 결과를 표시하였다. 노드의 수가 10~50개 구간인 경우 노드의 연결도가 낮아서 다음 전달 노드와의 만날 수 있는 시간이 길어지기 때문에 버퍼링 시간이 점점 길어지지만 노드의 갯수가 더 증가하면 전달 노드를 만날 수 있는 확률이 높아지게 되므로 상대적으로 버퍼링 시간이 줄어드는 것을 알 수 있다. 제안 알고리즘의 버퍼링 시간이 Spray와 Epidemic에 비해서 평균 버퍼링 시간이 더 길게 나타난 것은 패킷이 더 오래 보관이 되어 있게 되어 결과적으로 더 높은 패킷전달율을 나타낸 것으로 보인다.

Fig. 6.

Comparisons of average buffering time

Ⅴ. 결론 및 향후 과제

본 논문에서는 전달되는 복제본의 개수를 조절함으로써 발생되는 메시지의 수를 줄여 전체 발생되는 트래픽을 줄임으로써 패킷 전달율을 높이는 방법을 제시하였다. 기존의 브로드캐스트 기반의 알고리즘은 일반적으로 트래픽이 상당한 규모로 늘어나기 때문에 오히려 전반적인 성능이 떨어져 패킷수를 제한하는 다양한 기법이 제시되었다.

본 논문에서는 이러한 문제점을 해결하고자 이웃 노드의 연결정도에 따라 전달하는 메시지 복사본의 수를 조절하여 발생되는 트래픽의 양을 조정함으로써 패킷 전달율을 포함한 전반적인 라우팅 성능을 높이는 라우팅 기법을 제안하였다.

실험 결과를 통해 새롭게 제안하는 기법이 Spray-and-Wait 프로토콜과 Epidemic 프로토콜과 같은 알고리즘에 비해 우수한 성능을 보이는 것을 시뮬레이션을 통하여 확인할 수 있었다. 이번 연구 결과물의 확장과 보완을 통해 다양한 네트워크 환경, 노드의 컴퓨팅 능력, 노드의 이동 패턴등을 적용하여 제안하는 기법의 성능을 기존의 연구와 비교 측정할 예정이다.

Acknowledgments

이 연구는 금오공과대학교 학술연구비로 지원되었음(2019-104-050)

References

• S. Jain, K. Fall, and R. Patra. "Routing in a Delay Tolernt Network", SIGCOMM 2004, Aug. 2004. [https://doi.org/10.1145/1015467.1015484]
• Cunha F, Villas L, Boukerche A, Maia G, Viana, AC, and Mini R, Loureiro "A. Data communication in VANETs: Protocols, applications and challenges", Ad Hoc Networks, pp. 90-103, Jul. 2016. [https://doi.org/10.1016/j.adhoc.2016.02.017]
• N. Chakchouk, "A Survey on Opportunistic Routing in Wireless Communication Networks", in IEEE Communications Surveys & Tutorials, Vol. 17, No. 4, pp. 2214-2241, Mar. 2015. [https://doi.org/10.1109/COMST.2015.2411335]
• Bengag A and Boukhari M., "Classification and comparison of routing protocols in VANETs", Proceedings of the 2018 International Conference on Intelligent Systems and Computer Vision (ISCV), Fez, Morocco, pp. 1-8, Apr. 2018. [https://doi.org/10.1109/ISACV.2018.8354025]
• Gagan Deep Singh, Ravi Tomar, Hanumat G. Sastry, and Manish Prateek, "A Review on VANET Routing Protocols and Wireless Standards", Smart Computing and Informatics, pp. 329-340, Jul. 2018. [https://doi.org/10.1007/978-981-10-5547-8_34]
• E. Khoza, C. Tu, and P. A. Owolawi, "Comparative Study on Routing Protocols for Vehicular Ad-Hoc Networks (VANETs)", 2018 International Conference on Advances in Big Data, Computing and Data Communication Systems (icABCD), Durban, South Africa, pp. 1-6, Aug. 2018. [https://doi.org/10.1109/ICABCD.2018.8465434]
• F. M. Malik, H. A. Khattak, A. Almogren, O. Bouachir, I. U. Din, and A. Altameem, "Performance Evaluation of Data Dissemination Protocols for Connected Autonomous Vehicles", in IEEE Access, vol. 8, pp. 126896-126906, Jun. 2020. [https://doi.org/10.1109/ACCESS.2020.3006040]
• Silva A, Reza N, and Oliveira A, "Improvement and Performance Evaluation of GPSR-Based Routing Techniques for Vehicular Ad Hoc Networks", IEEE Access, Vol. 7, pp. 21722-21733, Feb. 2019. [https://doi.org/10.1109/ACCESS.2019.2898776]
• Z. Du, C. Wu, T. Yoshinaga, and Y. Ji, "A Prophet-Based DTN Protocol for VANETs", 2018 IEEE SmartWorld, Ubiquitous Intelligence, pp. 1876-1879, Oct. 2018.
• T. Spyropoulos, K. Psounis, and C.S. Raghavendra, "Spray and Wait: an efficient routing scheme for intermittently connected mobile networks", In Proceedings of ACM SIGCOMM 2005 Workshop on Delay Tolerant Networking and Related Networks (WDTN-05), pp. 252-259, Aug. 2005. [https://doi.org/10.1145/1080139.1080143]
• Guizhu Wang, Mei Shao, Run Li, Yao Ma, and Bingting Wang, "Spray and Wait routing algorithm based on Transfer Utility of Node in DTN", 2015 IEEE International Conference on Progress in Informatics and Computing (PIC), pp. 428-432, Dec. 2015. [https://doi.org/10.1109/PIC.2015.7489883]
• Ari Keränen, Jörg Ott, and Teemu Kärkkäinen, "The ONE Simulator for DTN Protocol Evaluation", SIMUTools’09: 2nd International Conference on Simulation Tools and Techniques. Rome, Mar. 2009. [https://doi.org/10.4108/ICST.SIMUTOOLS2009.5674]