ML System for Routing Decision in Urban VANET - 1

* 본 글은 IA Machine Learning System for Routing Decision-Making in Urban Vehicular Ad Hoc Networks 의 내용을 이해하며 작성됨. (출처 :https://journals.sagepub.com/doi/10.1155/2015/374391)

0. Abstract

---

! 배경 지식 공부

 

- Ad hoc network

중앙 제어 없이 노드들이 동적으로 연결되어 통신하는 네트워크. 

중앙 집중식의 기반 구조나 인프라가 없어도 임의의 위치에서 노드 간 통신이 가능하도록 하는 통신 형태이다.

주요 특징은 다음과 같다.

 

1. 분산 통신

2. 동적으로 네트워크를 형성 (노드들이 언제든지 네트워크에 참여, 이탈이 가능.)

3. 자율성 : 노드들이 자체적으로 통신을 제어.

4. 유연성 : 특별한 인프라가 없어도 동작이 가능해 특정 지역이나 환경에서 즉시 구성이 가능하다.

 

이러한 특징 때문에 재난 구호, 군사 작전등에서 다양하게 응용되고 있으며 네트워크 환경이 dynamic한 만큼 라우팅 프로토콜과 알고리즘이 굉장히 중요한 역할을 가지고 있다.

(사례 : 도시 환경에서 자율 주행 차량은 서로 통신하여 교통 정보를 공유하고 협력한다.)

 

- Source routing protocol

출발지에서 미리 경로를 전부 세팅해두고, 패킷에 그 경로를 적어둔 뒤 전송시키는 방식으로 동작한다.

미리 경로를 설정해야하기 때문에 실시간 네트워크 상황 변화에 대해 반응성이 느려지고, 패킷의 자체 크기가 증가하는 단점이 있다.

---

Vehicular Ad hoc Networks(이하 VANETs)의 Topology와 link들은 동적인 구조를 가지며 차량의 높은 mobility 특징 때문에 빈번하게 변경되는 특징이 있다.

VANETs에서 라우팅을 할 때, 대부분의 연구는 traffic을 감지하고, packet을 전송하기 위해 traffic density가 높은 도로를 선택하는데 중점을 두어서 carry-and-forward scenario를 피하고, delay를 줄여왔다.

( ! Carry-and-Forward scenario : 이동 노드들끼리 직접 통신이 불가능하거나 연결이 끊긴 경우에 발생하는 통신 방법. 이동 노드들이 직접 통신할 수 없을 시, 다른 이동노드로 우회하여 목적 노드까지 돌아가는 방법을 의미한다.)

그러나, 이러한 접근법은 traffic density가 매우 빠르게 변화하는 VANETs의 특성상 주기적으로 모니터링하는 것 만으로 정확한 real-time traffic density를 얻을 수 없다는 단점이 있다.

따라서 본 논문에서는 Routing protocol에 필요한 정보들을 예측하기 위해 Machie Learning-Assisted Route Selection(이하 MARS)라는 새로운 routing information system을 제안하고 있다.

 

MARS에서 도로 정보는 ML의 도움으로 roadside unit으로 유지될 수 있게 된다.

따라서 우리는 ML을 이용하여 차량들의 움직임을 예측하고 Transmission capacity가 더 좋은 Route를 선택하는 방식을 적용할 수 있게 된다.

또한 MARS는 목적지의 예측된 위치위 예측된 transmission delay들에 따라 두 RSU 사이의 forwarding direction을 결정하는데 도움을 줄 수도 있다.(RSU : Roadside Unit. 각 도로에 설치된 통신 장비를 의미.)

따라서 MARS는 VANET에 대한 시간 내 라우팅 정보를 제공하고 네트워크 성능을 크게 향상시킬 수 있다고 한다.

 

 

1. Introduction

VANET은 Mobile Ad hoc Network(MANET)의 subtype이다.

MANET은 Ad hoc network와 Wireless Local Area Network(WLAN)을 혼합한 기술이다.

Wireless Communication이 가능한 도로 위의 차량은 RSU 또는 다른 차량과 통신이 가능하다.

운전자는 원하는 서비스를 얻기 위해 언제든지 인터넷에 연결이 가능하며, VANETs의 Application area로는 운전자 지원, 도로 안전, 교통 효율성 향상, 모바일 엔터테인먼트 서비스 등이 있다.

이러한 VANET에는 V2I(Vehicle to Infrastructure), V2R(Vehicle to Roadside) 및 V2V(Vehicle to Vehicle).

총 3가지 유형이 일반적인 Communication model로 전재한다.

 

VANET 상에서 차량은 높은 mobility를 지니며, 이로 인해 network topology의 변화와 연결 불안정이 발생된다.

IEEE 802.11p 표준에서는 최대 전송 범위를 1km로 정의하지만, 실제로는 차량의 속도와 다양한 간섭 요인 때문에 더 제한이 된다.

만약 Source to destination distance가 매우 긴 상황을 가정한다면, Source Vehicle은 transmission range 이내에 위치한 인접 Vehicle로 packet을 전송한다. (Carry-and-Forward scenario)

만약 어떠한 vehicle도 범위내에 존재하지 않는다면, 자신이 전송 가능한 범위 이내에 차량이 나타날 때까지 메시지를 전달한 다음 패킷을 forwarding 한다.

Carry&Forward 과정을 살펴보면 transmission delay time을 증가시킴을 쉽게 예상할 수 있다.

그러므로, Routing protocol을 설계할 때 가능하면 Traffic density가 높은 도로에 있는 인접 차량을 선택해야, C&F scenario의 발생을 최소화할 것이라고 결론 내릴 수 있고, 이것이 일반적인 전략이다.

현재까지 많은 VANET routing protocol이 개발되었고, 일부 Routing mechanism은 도로 구간의 traffic density를 주기적으로 감지하여 routing path를 결정한다.

그러나, 이러한 감지가 주기적으로만 발생할 경우 문제가 발생할 수 있다.

1. 차량이 스스로 도로 구간의 density를 감지하여 다른 차량들과 정보를 교환하는 구조이므로, 많은 양의 control overhead가 발생한다.

2. Traffic density는  VANET에서 빠르게 변하므로 수렴하는데 많은 시간을 필요로 한다.

(Ad hoc network + high-mobility Mobile Host)

이 결과로 차량이 얻게 될 데이터는 real-time data가 아닐 가능성이 존재하게 되며, 이는 특히 source routing protocol에 불리하다.

3. 차량은 인접한 도로 구간에 대한 정보만 받아볼 수 있다. 만약 Routing protocol이 hop 단위 계산 방법을 쓴다면, local optimum 문제에 빠지게 된다.

이러한 점을 개선시키고자 MARS가 대안이 될 수 있다.

MARS에서 RSU는 ML의 도움을 받아 도로 상의 traffic information을 유지한다. MARS는 차량의 다음 움직임을 예측하고, 다른 RSU의 범위 내를 지나갈 확률을 계산한다. 이러한 예측 덕분에,packet은 더 적절한 routing path로 전달이 될 수 있다.

따라서 VANET에서 돌아갈 routing protocol을 위한 reference information을 제공하기 위해서는 real time state detection of urban traffic을 활용할 필요가 있다.

 

해당 논문에서는, ML을 사용하여 차량의 movement behavior와 routing paths의 transmission capacity를 예측한다.

이 때, 데이터의 유사성을 판단하고 이러한 데이터를 동일한 cluster로 그룹화할 수 있는지 여부를 결정하기 위해서는 unsupervised clustering approach가 활용된다.

그 다음, 각 cluster를 따라 미리 정의된 class로 매핑한 다음 새로 도착하는 차량에 대한 예측을 수행하는 과정을 거쳐 MARS가 구현된다.