차량용 네트워크에서의 패킷 전송율 개선을 위한 지리정보 기반의 라우팅 프로토콜

Ⅰ. 서 론

최근 전자 및 통신 기술을 교통시스템에 활용하는 차세대 지능형 교통시스템(ITS, Intelligent Transportation Systems) 분야에 대한 연구가 활발히 이루어지고 있다. 이러한 연구는 교통 정보 수집을 제공함으로써 다양한 서비스에 활용이 가능하다. 특히 차량의 이동성으로 인해 계속적으로 변화하는 네트워크 환경에 적합한 차량용 애드 혹 네트워크(VANET, Vehicular Ad-hoc NETtwork) 기술에 대한 다양한 연구 결과[1][2]가 발표되고 있다.

차량용 애드 혹 네트워크[3]는 무선 통신 기술이 탑재되어 있는 차량들로 구성되어 있는 네트워크로 각 차량은 서로의 통신 범위 내에서 통신을 하거나 도로를 따라 설치되어 있는 인프라 장치들과 통신을 할 수 있다. 차량과 인프라 장치들과 무선통신망으로 접속되어 운전자에게 교통정보안내와 긴급상황 정보등을 제공함으로써 편리함과 안전성을 증대시킬 수 있다.

차량용 애드 혹 네트워크에 적용되는 라우팅 알고리즘은 기존의 애드혹 네트워크를 위해 제안된 라우팅 프로토콜[4][5]을 기반으로 제안되고 있다. 애드혹 네트워크에서의 라우팅 알고리즘은 토폴로지 기반(Topology-based) 라우팅 기법과 위치 기반(Location-based) 라우팅 기법으로 분류할 수 있다. 토폴로지 기반 라우팅은 원천지 노드(Source node)가 목적지 노드(Destination node)까지의 경로를 확보한 후 패킷을 전달하는 방식으로 프로액티브(Pro-active) 방식과 리액티브(Reactive) 방식이 있다.

토폴로지 기반 라우팅 프로토콜은 원천지 노드와 목적지 노드 간의 경로를 확보한 후에 패킷 전송을 하기 때문에 확보된 경로 상에 있는 노드 중 하나라도 이동하게 되면 데이터 전달이 실패하게 되며 재전송을 위한 경로를 다시 확보해야 하는 문제점을 가지고 있다. 위치 기반 라우팅 프로토콜에서는 각 노드들이 자신의 이웃 노드의 정보만을 가지고 패킷을 전달하는 기법을 사용하고 있다. 일반적으로 위치 기반 라우팅 프로토콜들은 그리디 포워딩(Greedy forwarding) 기반이며 주기적으로 헬로(Hello) 메시지(Beacon)의 교환을 통해 자신의 이웃 노드들의 위치를 관리하고 있다. 패킷을 전달할 때는 노드의 전송 범위내에서 수신 노드와 가장 가까운 이웃 노드를 전달 노드로 선택하여 가능한 가장 멀리 패킷 전송을 시도하기 때문에 그리디(Greedy)라는 용어를 사용하고 있다. 이 기법은 송수신 노드 사이의 경로 설정을 위한 별도의 정보 유지가 필요 없기 때문에 간단하고 효율적인 데이터 전달을 할 수 있다.

그리디 포워딩 알고리즘[6][7]이 효과적으로 동작하기 위해서는 주기적인 비콘 교환으로 이웃 노드의 정확한 위치 정보를 확보하는 것이 전반적인 성능을 결정하는 중요한 요소가 된다. 노드가 빠르고 자주 이동하는 환경에서는 그리디 포워딩 기반의 알고리즘에서는 전송 범위에서 벗어난 이웃 노드에게 패킷 전달을 시도하면 그 노드는 이미 다른 곳으로 이동할 수 있어 데이터의 손실이 발생할 수 있다.

이러한 문제를 해결하기 위해서 본 논문에서는 원천지 노드에서 메시지를 전송할 때 전송 범위내에서 목적지 노드에서 가장 가까운 노드에 메시지를 전달하는 것은 물론 목적지에서 두 번째로 가까운 노드에게도 메시지를 전달함으로써 노드의 이동이 많은 환경에서도 약간의 오버헤드가 발생하지만 패킷 전달율을 높일 수 있도록 시도한다.

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

Ⅱ. 관련 연구

그림 1과 같은 지연허용네트워크(DTN, Delay Tolerant Network)는 우주 통신에서와 같이 종단간 연결을 보장되어 있지 않고 인터넷 환경이 열악한 네트워크에 적합한 차세대 네트워크라고 할 수 있다. 종단간 연결이 보장되지 않는 이러한 환경에서는 Store-Carry-Forward에 기반한 새로운 라우팅 프로토콜의 적용이 필요하다.

Fig. 1.

Traditional network and DTN

이는 각 노드는 전송할 메시지를 버퍼에 저장하고 노드 이동에 의해서 전송 범위내에서 다른 노드를 만나게 되면 메시지를 전달하는 방식을 통해 최종 목적지까지 메시지를 전달하게 된다. VANET 환경에 적용할 수 있는 지연 허용 네트워크용 라우팅 프로토콜은 시간에 따라 변하는 네트워크 형상에 대해서 노드가 향후 네트워크의 정보를 미리 알고 있거나 정확하게 예측할 수 있는 결정적(Deterministic) 프로토콜과 정보를 미리 예측할 수 없는 환경에서 적용되는 동적(Dynamic) 프로토콜로 구분될 수 있다.

결정적 라우팅 프로토콜의 부류에 속하는 오라클(Oracle) 기반의 라우팅 프로토콜은 링크의 대역폭, 링크의 물리적인 전달 지연과 같이 시간 경과와 관련없는 정보를 가지는 연결정보 오라클, 링크의 상태, 전송량과 같이 시간에 따라 변하는 네트워크 특성을 가지는 연결 오라클, 임의의 시간에 임의의 노드에서 생기는 큐 상태에 대한 정보를 가지는 큐 오라클, 향후 발생하는 트래픽에 대한 정보를 뜻하는 교통량 요구 기반의 오라클 등과 같이 4가지의 라우팅 기법이 제안되고 있다.

동적 라우팅 프로토콜은 노드들의 이동성과 망의 상태를 예측할 수 없는 상황에 적합한 라우팅 프로토콜으로서 대표적인 라우팅 프로토콜에는 직접 전송(Direct transmission) 라우팅 프로토콜, Epidemic 라우팅 프로토콜[8], Spray and Wait 라우팅 프로토콜[9], Prophet 라우팅 프로토콜[10]이 있다.

직접 전송 라우팅 프로토콜은 노드의 이동 중 전송 범위내의 만나는 노드가 메시지의 목적지 노드일 경우에만 전송하게 된다.

Epidemic 라우팅 프로토콜은 기본적으로 플러딩(Flooding) 방식을 사용하여 전송 범위내에서 만나는 모든 노드에게 자신이 가진 전송해야 할 메시지를 전달한다. 만나는 모든 노드에게 메시지를 전달하기 때문에 메시지 전달 성공률은 높지만 비교적 많은 트래픽이 발생하고 이에 따라 다른 메시지의 전달이 어려워질 수 있으므로 오히려 전송 성공률이 감소될 수 있다.

Prophet 라우팅 프로토콜은 0부터 1사이의 값으로 표현되는 전달예측성(Delivery predictability) 메트릭(Metric)을 사용하는 확률에 기반을 둔 라우팅 프로토콜이다.

Epidemic 프로토콜 범주에 속하는 GPSR(Greedy Perimeter Stateless Routing)은 그리디 포워딩을 기반으로 하며 각 노드들이 GPS 수신기 등을 사용해 자신의 위치 정보를 알고 있는 것을 가정하고 있다. 송신 노드는 수신 노드의 위치를 알 수 있기 때문에 위치 정보를 패킷의 헤더에 포함시키고 자신의 전송 범위에 속한 이웃 노드들 중에서 목적지 노드와 가장 가까운 노드를 전달 노드로 선택해서 패킷을 전달하게 된다. 패킷을 수신하는 중간 노드들은 이러한 과정을 통해 다음 전달 노드를 선택하고 최종적으로 목적지 노드가 수신할 때까지 반복된다.

그림 2는 GPSR에서 그리디 포워딩 기법을 적용하여 전달 노드를 선택하는 예를 보여준다. 여기서 노드 S는 노드 D가 최종 목적지인 패킷을 가지고 있다.

Fig. 2.

Example of Greedy forwarding

S는 자신의 전송 범위 안에 있는 여러 이웃 노드들 중 노드 D와 가장 가까운 노드인 노드 A를 전달 노드로 선택하고 패킷을 노드 A에게 전달한다. 원천지 노드에서 목적지 노드까지의 경로를 확보해야 하는 토폴로지 기반 라우팅 프로토콜과 달리 그리디 포워딩 기법은 각 노드들이 이웃 노드에 대한 정보만 유지관리하면 되기 때문에 노드의 이동 등으로 토폴로지의 변화가 빈번한 환경에서 좋은 성능을 나타내고 있으며 라우팅 테이블을 유지 관리하기 위한 절차가 필요하지 않다는 정점도 가지고 있다.

GPSR에서는 각 노드들이 전송 범위내의 이웃 노드들의 위치 정보를 알고 있어야 하기 때문에 모든 노드들이 이웃 노드들에게 주기적으로 헬로우(Hello) 메시지와 같은 비콘(Becon)을 전송한다.

비콘 패킷에는 자신의 현재 위치가 포함되어 있으며 MAC 계층에서 브로드캐스트 주소로 전송된다. 비콘메시지를 전송하는 주기가 짧으면 최신의 위치 정보가 반영되지만 트래픽이 증가함으로써 라우팅 오버 헤드가 증가하여 성능이 나빠지는 문제점을 가지고 있다. 반면 비콘 패킷을 발생시키는 주기를 길게 하면 오버헤드는 줄일 수 있지만 각 노드에서 저장하고 있는 이웃 노드 위치 정보가 그 이웃 노드의 이동등으로 인해 달라진 위치 정보가 적용되어 패킷 전달이 되지 않을 수 있는 단점이 있다.

GPSR에서의 패킷을 전송할 때는 그리디 모드와 복구 모드가 사용된다. GPSR에서 적용된 그리디 모드는 임의의 노드가 목적지 노드로 패킷을 전송할 때 임의의 노드의 전송 범위 내의 이웃 노드들 중 목적지 노드와 가장 가까운 노드에게 메시지를 전달한다.

그러나 전송 범위 내의 어떠한 이웃 노드도 현재의 자신 보다 목적지 노드에 가깝지 않은 경우에는 적절한 전달 노드를 선택할 수 없게 되는 로컬 맥시멈(Local maximum) 상태가 되어 더 이상 패킷을 전달할 수 없는 상태가 발생한다. 로컬 맥시멈 상태가 되면 이러한 상태를 벗어나기 위하여 복구 모드 상태로 전이하게 된다. 복구 모드에서는 로컬 맥시멈을 우회하는 역방향으로 전송을 함으로써 로컬 맥시멈 상태를 벗어나는 시도를 한다. 우회된 노드에서의 계산된 거리가 복구모드에서 목적지 노드까지의 거리보다 짧아질 때까지 복구 모드 상태가 계속 된다. 거리 조건을 만족하는 경우가 되면 그리디 모드로 전이를 하여 패킷 전달이 이어 진다. 그러나 복구모드 상태에서는 경로상의 전달 노드의 숫자가 증가되므로 데이터의 손실 및 지연시간이 증가하는 문제가 발생한다.

본 논문에서는 그리디 포워딩 기반의 라우팅 프로토콜인 GPSR 기법과 개선된 기존 기법을 기반으로 노드의 이동 혹은 로컬맥시멈 현상으로 성능이 나빠질 수 있는 문제점을 해결하는 방법을 제시한다. 제안하는 알고리즘은 기존의 알고리즘과 비교하여 시뮬레이션을 통하여 패킷 전달율이 향상됨을 알 수 있다.

Ⅲ. 제안 알고리즘

그리디 포워딩을 기반으로 하는 GPSR과 유사한 알고리즘은 로컬 맥시멈 상태가 되면 복구 모드로 전이를 하고 다시 그리디 모드로 진입하기 위한 시도를 하게 된다. 이러한 과정에서 패킷 재전송 또는 우회 경로로 패킷을 전송함으로써 효율성이 떨어지는 문제가 발생한다. 이러한 문제를 해결하기 위하여 전송 범위에서 목적지와 가장 가까운 노드 A와 두 번째로 가까운 노드 B에게 패킷을 전달하고 이러한 두 개의 패킷을 전달하는 중간 노드에서는 이미 이웃 노드로부터 전달된 패킷을 수신하게 되면 더 이상 이웃 노드로 전달을 하지 않음으로써 트래픽이 증가되는 것을 방지하도록 한다.

패킷에는 패킷의 아이디, 소스 노드, 목적지 노드 정보로 구성되어 있으며 이웃 노드로부터 수신한 패킷에서 패킷 아이디와 소스 노드가 같으면 해당 패킷을 무시한다. 패킷 수신 후 전송 범위내에 목적지 노드가 없으면 전송 범위내의 노드 중에서 목적지와 가장 가까운 노드(에지 노드 Ea)와 두 번째와 가까운 노드(에지 노드 Eb)의 위치를 구한다. 임의의 노드에서 패킷을 수신하였을 때의 패킷 처리 알고리즘은 그림 3과 같다.

Fig. 3.

Packet Transmission Algorithms

그림 4에서는 소스노드 S이고 목적지 노드 D일 때 제안 알고리즘의 라우팅 예를 보여 주고 있다. 노드 S에서 전송 범위내에서 목적지 노드와 가장 가까운 노드(Ea)인 A와 두 번째 가까운 노드(Eb) B에게 패킷을 전송한다. 노드 A에서는 같은 방법으로 W(Ea)와 X(Eb)에 전송한다. 노드 B에서도 같은 방법으로 C(Ea)와 X(Eb)에 전송한다. 노드 X에서는 같은 패킷을 수신하지만 최초로 받은 패킷만 계속 포워딩되며 이후에 수신된 패킷은 폐기한다. 노드 C, W, X에서는 같은 방법으로 목적지 노드로 패킷을 전송한다. 포워딩 중에 캐싱되는 패킷 정보를 활용하여 중복 포워딩을 피하여 트래픽의 양을 줄일 수 있다.

Fig. 4.

Packet transmission example

Ⅳ. 성능 평가

제안한 제안 알고리즘의 성능을 기존 알고리즘과 성능 비교를 하기 위하여 netsim2[11] 시뮬레이터를 사용하여 시뮬레이션을 실행하였다. 시뮬레이션에서 사용한 여러 값들은 표 1에 제시되어 있다. 시뮬레이션에서는 그리디기반의 알고리즘인 GPSR(그림에서 GPSR로 표기)[3], 개선된 알고리즘(WY로 표기)[12]과 제안된 알고리즘(Proposed로 표기)에 대하여 성능 측정을 실시하였다.

Table 1.

Simulation parameters

성능 비교를 다음과 같은 세 가지 메트릭(Metric)을 사용하여 비교하였다.

• • 메시지 전달율(Message delivery ratio) : 전달 성공한 메시지 수와 생성 된 메시지 수의 비율
• • 평균 시간(Average latency time) : 소스 노드에서 메시지가 생성된 후 목적지 노드에 성공적으로 전달되는 데 소요된 평균 시간
• • 평균 버퍼링 시간(Average buffering time) : 다음 전달 노드에 패킷을 보낼 때까지의 노드에서의 평균 버퍼링 시간

첫 번째 시뮬레이션에서는 노드의 수가 100개와 200개인 경우의 메시지 전달율을 측정하였으며 결과는 그림 5와 그림 6에 표시하였다. 노드의 수가 100개일 때 제시한 알고리즘은 전달율이 노드의 속도가 10 km/h인 경우 0.95에 근접하였지만 노드의 속도가 점점 빨라져 45km/h 일 때는 전달율이 0.7에 근접하는 것을 알 수 있다. 노드의 이동 속도가 빨라짐에 따라 패킷 전달율이 떨어지는 것은 빨라진 속도로 인해 인접 노드의 변화가 빨라져서 페기되는 패킷이 증가하기 때문인 것으로 추정된다.

Fig. 5.

Delivery ratio results(100 nodes)

Fig. 6.

Delivery ratio results(200 nodes)

제안 알고리즘은 GPSR과 WY와 비교할 때 노드의 속도에 관계없이 전반적으로 전달율이 10%정도 우수한 성능을 나타냈다. 이는 미리 전달 경로를 결정함으로써 제안 알고리즘에서 기존 연구의 로컬맥시멈 상태 발생이나 경로 단절로 인해 백트래킹해야 하는 문제점이 개선되었기 때문이다.

두 번째 시뮬레이션에서는 평균 지연 시간을 측정 비교하여 그림 7에 표시하였다. 노드의 속도가 빨라짐에 따라 제안 알고리즘이 GPSR과 WY에 비해서 더 좋은 성능을 나타냄을 알 수 있다. 이는 첫 번째 실험 결과에서도 제시하였듯이 단절된 경로를 미리 피하게 되므로 제안 기법의 성능이 우수한 것으로 판단이 된다.

Fig. 7.

Average latency time results

그림 8은 세 번째 시뮬레이션의 결과로서 노드에서의 버퍼링되는 평균 시간을 측정 비교하여 표시하였다. 노드의 속도가 느린 경우 다음 전달 노드와의 만날 수 있는 시간이 길어지기 때문에 버퍼링 시간이 길어지지만 노드의 속도가 빨라지게 되면 전달 노드를 만날 수 있는 확률이 높아지게 되므로 상대적으로 버퍼링 시간이 줄어드는 것을 알 수 있다.

Fig. 8.

Average buffering time results

평균 버퍼링 시간 측면에서 제안 알고리즘이 GPSR과 WY에 비해서 약 20% 정도 더 개선된 성능을 나타냄을 알 수 있다. 제안 알고리즘은 기존의 연구보다 메시지가 더 빨리 전달되므로 노드의 버퍼링 시간이 상대적으로 짧아짐을 알 수 있다.

Ⅴ. 결론 및 향후 과제

본 논문에서는 그리디 포워딩 기반의 라우팅 프로토콜의 성능을 개선하는 기법을 제안하였다. 먼저 GPSR와 개선된 GPSR등에서 사용되는 그리디 포워딩에서 데이터 전달의 문제점을 해결하기 위해 전송 범위에서 목적지와 가장 가까운 2개의 노드로 패킷을 전달함으로써 로컬 맥시멈 상태를 미리 예방함으로써 패킷 전달율을 높이는 라우팅 기법을 제안하였다.

실험 결과를 통해 새롭게 제안하는 기법이 GPSR 과 같은 그리디 포워딩 기반의 알고리즘에 비해 우수한 성능을 보이는 것을 시뮬레이션을 통하여 확인할 수 있었다.

이번 연구 결과물의 확장과 보완을 통해 다양한 네트워크 환경, 노드의 수, 노드의 이동 패턴등을 적용하여 제안하는 기법의 성능을 기존의 연구와 비교 측정할 예정이다.

Acknowledgments

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

References

• S. Jain, K. Fall, and R. Patra. "Routing in a Delay Tolernt Network", SIGCOMM 2004. [https://doi.org/10.1145/1015467.1015484]
• V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall, and H. Weiss, "Delay-tolerant networking architecture", IETF RFC 4838 (Informational), Apr. 2007. [https://doi.org/10.17487/rfc4838]
• N. Chakchouk, "A Survey on Opportunistic Routing in Wireless Communication Networks", in IEEE Communications Surveys & Tutorials, Vol. 17, No. 4, pp. 2214-2241, Fourthquarter 2015. [https://doi.org/10.1109/COMST.2015.2411335]
• S. Ramanathan and M. Steenstrup, "A survey of routing techniques for mobile communication networks", Mobile Networks and Applications, pp. 89-104, Oct. 1996. [https://doi.org/10.1007/BF01193330]
• M. Abolhasan, T. Wysocki, and E. Dutkiewicz, "A review of routing protocols for mobile ad hoc networks", Ad Hoc Networks, Vol. 2, No. 1, pp. 1-22, Jan. 2004. [https://doi.org/10.1016/S1570-8705(03)00043-X]
• B. Karp and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks", Proceedings of the 6th annual international conference on Mobile computing and networking, Boston Massachusetts USA, pp. 243-254, Aug. 2000. [https://doi.org/10.1145/345910.345953]
• Y. Jiang, G. Xu, H. Dong, Z. Fang, Y. Guan, and Z. Zhang, "Improved GPSR Protocol and Performance Evaluation", 2020 IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE), Yunlin, Taiwan, pp. 234-238, Oct. 2020. [https://doi.org/10.1109/ECICE50847.2020.9301937]
• A. Vahdat and D. Becker "Epidemic Routing for Partially Connected Ad Hoc Networks", Technical Report CS-200006, Duke University, Apr. 2000.
• 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), Philadelphia Pennsylvania USA, pp. 252-259, Aug. 2005. [https://doi.org/10.1145/1080139.1080143]
• A. Lindgren, A. Doria, and O. Schel´en, "Probabilistic routing in intermittently connected networks", Mob. Comput. Commun. Rev., Vol. 7, pp. 19-20, Jul. 2003. [https://doi.org/10.1145/961268.961272]
• Ben Leong, Geographic routing network simulator, http://web.mit.edu/benleong/www/netsim, .
• X. Yang, M. Li, Z. Qian, and T. Di, "Improvement of GPSR Protocol in Vehicular Ad Hoc Network", in IEEE Access, Vol. 6, pp. 39515-39524, Jul. 2018. [https://doi.org/10.1109/ACCESS.2018.2853112]