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

[1. 논문 선정 이유]

 

해당 논문은 '데이터 통신 및 네트워크' 전공 수업을 수강 중인 나에게 매우 유익할 것으로 예상되어 선정했다. 최근에 배운 '패킷 전송율' 개념을 심화하여 적용해보고자 했다. 또한, 차량용 네트워크에 대한 관심이 있었는데, 이는 수업에서 다루지 않은 주제였다. 이 논문을 통해 차량용 네트워크에 관한 새로운 이야기를 알아갈 수 있을 것을 기대했다.

 

---

[2. 논문 분석 내용]

 

 

---

Ⅰ. 서론

 

1. 배경 지식

 

(1)*차세대 지능형 교통시스템 분야에 대한 연구는 교통 정보 수집을 제공함으로써 다양한 서비스에 활용이 가능하다.

*차세대 지능형 교통시스템 (ITS, Intelliget Transportation Systems): 전자 및 통신 기술을 교통 시스템에 활용

 

 

(2) 차량용 애드 혹 네트워크:

- 각 차량은 서로의 통신 범위 내에서 통신을 하거나 도로를 따라 설치되어 있는 인프라 장치들과 통신을 할 수 있다.

- 차량과 인프라 장치들과 무선통신망으로 접속되어 운전자에게 교통정보안내와 긴급상황 정보등을 제공함으로써 편리함과 안전성을 증대시킬 수 있다.

 

 

(2) 차량용 애드 혹 네트워크에 적용되는 라우팅 알고리즘은 기존의 애드혹 네트워크를 위해 제안된 라우팅 프로토콜을 기반으로 제안되고 있다.

 

애드혹 네트워크에서의 라우팅 알고리즘: 

① 토폴로지 기반 라우팅 기법:

- 원천지 노드(Source node)가 목적지 노드(Destnation node)까지의 경로를 확보한 후 패킷을 전달하는 방식

- 프로액티브(Pro-active) 방식과 리액티브(Reactive) 방식이 있다.

- 원천지 노드와 목적지 노드 간의 경로를 확보한 후에 패킷 전송을 하기 때문에 확보된 경로 상에 있는 노드 중 하나라도 이동하게 되면 데이터 전달이 실패하게 된다. -> 재전송을 위한 경로를 다시 확보해야 한다.

 

② 위치 기반 라우팅 기법

- 각 노드들이 자신의 이웃 노드의 정보만을 가지고 패킷을 전달하는 기법을 사용하고 있다.

- 일반적으로 그리디 포워딩(Greedy forwarding) 기반

- 주기적으로 헬로(Hello) 메시지(Beacon)의 교환을 통해 자신의 이웃 노드들의 위치를 관리

- 패킷을 전달할 때는 노드의 전송 범위내에서 수신 노드와 가장 가까운 이웃 노드를 전달 노드로 선택하여 가능한 가장 멀리 패킷 전송을 시도(-> 그리디라는 용어를 사용하는 이유)

- 이 기법은 송수신 노드 사이의 경로 설정을 위한 별도의 정보 유지가 필요 없기 때문에 간단하고 효율적인 데이터 전달을 할 수 있다.

 

③ 그리디 포워딩 알고리즘

- 주기적인 비콘 교환으로 이웃 노드의 정확한 위치 정보 확보-> 이는 성능을 결정하는 중요 요소가 됨.

- 노드가 빠르고 자주 이동하는 환경에서는 그리디 포워딩 기반의 알고리즘에서는 전송 범위에서 벗어난 이웃 노드에게 패킷 전달을 시도하면 그 노드는 이미 다른 곳으로 이동할 수 있어 데이터의 손실이 발생할 수 있음.-> 문제 발생

 

 

 

2. 논문 주제

 

- 그리디 포워딩 알고리즘에서 노드가 빠르고 자주 이동하는 환경에서의 데이터 손실 문제를 해결하기 위한 시도를 하는 것이 본 논문의 주제 및 목적이다.

 

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

 

 

---

Ⅱ. 관련 연구 (기존에 해결하지 못한 문제 상황)

 

 

그림 1과 같은 지연허용네트워크(DTN, Delay Tolerant Network)는 우주 통신에서와 같이 종단간 연결이 보장되어 있지 않고 인터넷 환경이 열악한 네트워크에 적합한 차세대 네트워크이다.

 

종단간 연결이 보장되지 않는 이러한 환경에서는 Store-Carry-Forward에 기반한 새로운 라우팅 프로토콜의 적용이 필요

 

--> 이는 각 노드는 전송할 메시지를 버퍼에 저장하고 노드 이동에 의해서 전송 범위내에서 다른 노드를 만나게 되면 메시지를 전달하는 방식을 통해 최종 목적지까지 메시지를 전달하게 된다.

 

 VANET  환경에 적용할 수 있는 지연 허용 네트워크용 라우팅 프로토콜

(1)  결정적(Deterministic) 프로토콜: 시간에 따라 변하는 네트워크 형상에 대해서 노드가 향후 네트워크의 정보를 미리 알고 있거나  정확하게  예측할 수 있다.

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

 

(2) 동적 라우팅 프로토콜:

• 직접 전송(Direct transmission) 라우팅 프로토콜: 노드의 이동 중 전송 범위내의 만나는 노드가 메시지의 목적지 노드일 경우에만 전송하게 됨.
• Spray and Wait 라우팅 프로토콜
• Prophet 라우팅 프로토콜: 0부터 1사이의 값으로 표현되는 전달예측성(Delivery  predictability)  메트릭(Metric)을 사용하는 확률에 기반을 둔 라우팅 프로토콜이다. 
• Epidemic 라우팅 프로토콜: 기본적으로 플러딩(Flooding) 방식을 사용하여 전송 범위내에서 만나는 모든 노드에게 자신이 가진 전송해야 할 메시지를 전달함. 만나는 모든 노드에게 메시지를 전달하기 때문에 메시지 전달 성공률은 높지만 비교적 많은 트래픽이 발생하고 이에 따라 다른 메시지의 전달이 어려워질 수 있으므로 오히려 전송 성공률이 감소될 수 있다.

 

 

GPSR(Greedy Perimeter  Stateless  Routing):

 

(Epidemic 라우팅 프로토콜 범주에 속함.)

그리디 포워딩을 기반으로 하며 각 노드들이 GPS  수신기 등을 사용해 자신의 위치 정보를 알고 있는 것을 가정.

송신 노드는 수신 노드의 위치를 알 수 있기 때문에 위치 정보를 패킷의 헤더에 포함시키고 자신의 전송 범위에 속한 이웃 노드들 중에서 목적지 노드와 가장 가까운 노드를 전달 노드로 선택해서 패킷을 전달하게 된다.  패킷을 수신하는 중간 노드들은 이러한 과정을 통해 다음 전달 노드를 선택하고 최종적으로 목적지 노드가 수신할 때까지 반복된다. 

 

그리디 포워딩 기법을 적용하여 전달 노드를 선택하는 예

 

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

 

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

 

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

 

>> 결론: 그리디 포워딩 기반의 라우팅 프로토콜인 GPSR  기법과 개선된 기존 기법을 기반으로 노드의 이동 혹은 로컬맥시멈 현상으로 성능이 나빠질 수 있는 문제점을 해결하는 알고리즘을 제안한다. 

 

 

---

Ⅲ. 제안 알고리즘 (해결 방안)

 

 

문제: 그리디 포워딩을 기반으로 하는 GPSR과 유사한 알고리즘은 로컬 맥시멈 상태가 되면 복구 모드로 전이를 하고 다시 그리디 모드로 진입하기 위한 시도를 하게 된다.  이러한 과정에서 패킷 재전송 또는 우회 경로로 패킷을 전송함으로써 효율성이 떨어진다.

 

해결 방안: 전송 범위에서 목적지와 가장 가까운 노드 A와 두 번째로 가까운 노드 B에게 패킷을 전달하고 이러한 두 개의 패킷을 전달하는 중간 노드에서는 이미 이웃 노드로부터 전달된 패킷을 수신하게 되면 더 이상 이웃 노드로 전달을 하지 않음으로써 트래픽이 증가되는 것을 방지하도록 한다.

 

패킷: 패킷의 아이디, 소스 노드, 목적지 노드 정보로 구성

규칙1: 이웃 노드로부터 수신한 패킷에서 패킷 아이디와 소스 노드가 같으면 해당 패킷을 무시

규칙2: 패킷 수신 후 전송 범위내에 목적지 노드가 없으면 전송 범위내의 노드 중에서 목적지와 가장 가까운 노드(에지 노드 Ea)와 두 번째와 가까운 노드(에지 노드 Eb)의 위치를 구한다.

 

임의의 노드에서 패킷을 수신하였을 때의 패킷 처리 알고리즘

 

 

소스노드 S 이고 목적지 노드 D 일 때 제안 알고리즘의 라우팅 예

 

[규칙]

1. 노드 S에서 전송 범위내에서 목적지 노드와 가장 가까운 노드(Ea)인 A와 두 번째 가까운 노드(Eb) B에게 패킷을 전송한다.
2. 노드 A에서는 같은 방법으로 W(Ea)와 X(Eb)에 전송한다.
3. 노드 B에서도 같은 방법으로 C(Ea)와 X(Eb)에 전송한다.
4. 노드 X에서는 같은 패킷을 수신하지만 최초로 받은 패킷만 계속 포워딩되며 이후에 수신된 패킷은 폐기한다.
5. 노드 C,  W,  X에서는 같은 방법으로 목적지 노드로 패킷을 전송한다.
6. 포워딩 중에 캐싱되는 패킷 정보를 활용하여 중복 포워딩을 피하여 트래픽의 양을 줄일 수 있다. 

 

 

---

Ⅳ. 성능 평가

 

 

제안한 제안 알고리즘의 성능을 기존 알고리즘과 성능 비교를 하기 위하여 netsim2[11] 시뮬레이터를 사용하여 시뮬레이션을 실행

 

시뮬레이션에서는 그리디기반의 알고리즘인 GPSR(그림에서  GPSR로  표기), 개선된  알고리즘(WY로  표기)과 제안된 알고리즘(Proposed로 표기)에 대하여 성능 측정을 실시하였다.

 

시뮬레이션에서 사용한 여러 값들

 

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

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

 

 

 

[첫 번째 시뮬레이션]

 

• 노드의 수가 100개와 200개인 경우의 메시지 전달율을 측정하였으며 결과는 그림 5와 그림 6에 표시하였다.

 

• 결과1: 노드의 수가 100개일 때 제시한 알고리즘은 전달율이 노드의 속도가 10km/h인 경우 0.95에 근접하였지만 노드의 속도가 점점 빨라져 45km/h 일 때는 전달율이 0.7에 근접하는 것을 알 수 있다. (속도가 증가함에 따라 패킷 전달율이 떨어짐)
• 분석1: 노드의 이동 속도가 빨라짐에 따라 패킷 전달율이 떨어지는 것은 빨라진 속도로 인해 인접 노드의 변화가 빨라져서 폐기되는 패킷이 증가하기 때문인 것으로 추정된다. 
• 결과2: 제안 알고리즘은 GPSR과 WY와 비교할 때 노드의 속도에 관계없이 전반적으로 전달율이 10%정도 우수한 성능을 나타냈다.
• 분석2: 미리 전달 경로를 결정함으로써 제안 알고리즘에서 기존 연구의 로컬맥시멈 상태 발생이나 경로 단절로 인해 백트래킹해야 하는 문제점이 개선되었기 때문이다. --> 기대 효과 도출

 

 

[두 번째 시뮬레이션]

 

• 평균 지연 시간을 측정 비교하여 그림 7에 표시

 

• 결과1: 노드의 속도가 빨라짐에 따라 제안 알고리즘이 GPSR과 WY에 비해서 더 좋은 성능을 나타냄을 알 수 있다.
• 분석1: 이는 첫 번째 실험 결과에서도 제시하였듯이 단절된 경로를 미리 피하게 되므로 제안 기법의 성능이 우수한 것으로 판단이 된다.

 

[세 번째 시뮬레이션]

 

노드에서의 버퍼링되는 평균 시간을 측정 비교하여 표시

 

분석1: 노드의 속도가 느린 경우 다음 전달 노드와의 만날 수 있는 시간이 길어지기 때문에 버퍼링 시간이 길어지지만 노드의 속도가 빨라지게 되면 전달 노드를 만날 수 있는 확률이 높아지게 되므로 상대적으로 버퍼링 시간이 줄어드는 것을 알 수 있다. 

 

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

 

 

---

Ⅴ. 결론 및 향후 과제

 

 

이 논문은 GPSR와 개선된 GPSR와 같은 그리디 포워딩 기반의 라우팅 프로토콜에서 발생하는 데이터 전달의 문제점을 해결하기 위한 기법을 제안한다. 이를 위해, 패킷을 전달할 때 전송 범위 내에서 목적지와 가장 가까운 2개의 노드로 전달함으로써 로컬 맥시멈 상태를 미리 예방하고 패킷 전달율을 높이는 방법을 제시한다. 실험 결과를 통해 이 새로운 기법이 기존의 GPSR과 같은 그리디 포워딩 알고리즘보다 우수한 성능을 보임을 확인한다. 또한, 이 연구의 결과를 확장하고 보완하여 다양한 네트워크 환경, 노드 수, 노드 이동 패턴 등을 고려하여 제안된 기법의 성능을 기존 연구와 비교하고 측정할 예정이다.

 

---

[3. 배운 점 및 느낀 점]

 

논문에서 제시된 GPSR 및 개선된 GPSR과 같은 그리디 포워딩 기반의 라우팅 프로토콜은 효율적인 경우가 많지만, 로컬 맥시멈 상태와 같은 문제가 발생할 수 있다는 점을 이해했다.

논문을 이해하며 네트워크 구조에 사용되는 용어들에 더욱 친숙해졌다.

전송 범위 내에서 목적지와 가장 가까운 2개의 노드로 패킷을 전달하여 로컬 맥시멈 상태를 예방하는 아이디어는 간단하면서도 효과적이다. 이는 라우팅 프로토콜에 대한 깊은 이해를 기반으로 한 문제 해결 능력을 보여준다고 생각한다.

 

 

---

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

0.83MB