Ⅰ. 서 론

VANET(Vehicular Ad-hoc Network)은 정보통신과 교통기술이 융합되어 ITS(Intelligent Transportation Systems) 산업에서 다양한 서비스를 제공하기 위한 핵심 요소이다. 이러한 VANET이 제공하는 주요 서 비스에는 위험상황에 대한 긴급경고메시지, 도로상 태, 교통 및 날씨정보 등이 있으며 이는 멀티 홉 (multi-hop)형태의 브로드캐스트 방식이 많이 사용 되고 있다[1]. 브로드캐스트는 송신 노드가 전송범 위 내에 있는 모든 노드에게 패킷을 전송하는 것이 다. 브로드캐스트 패킷의 TTL(Time To Live)이 1이 상일 때는 패킷을 수신한 각 노드가 패킷을 재 브 로드캐스트(rebroadcast)하게 되는데 이때 사용되는 대표적인 브로드캐스트 방식을 플러딩(flooding)이 라 한다[2]. 플러딩 방식을 통해 패킷 중복, 루핑 (looping)현상을 방지 할 수 있지만 이 역시 모든 노 드가 패킷전송에 참여하기 때문에 대역폭 낭비와 종단 간 지연이 증가하여 네트워크의 급격한 성능 저하를 가져오게 된다.

본 논문에서는 거리기반의 브로드캐스트 방식을 이용하여 네트워크 트래픽을 감소하고 경로 요청 패킷의 안정성을 향상시키는 알고리즘을 적용한 라 우팅 프로토콜을 제안한다. 또한 도심 환경에서의 성공적인 패킷 전파를 위하여 교차로에서 대기 시 간의 우선순위 차등화 알고리즘을 통해 도심지에서 의 패킷 전송 문제를 해결한다.

본 논문의 구성은 다음과 같다. 2장은 관련연구 로서 VANET 환경에 대한 특성 및 통신 요구사항, 그리고 기존에 제안되었던 애드-혹(ad-hoc) 네트워 크에서의 라우팅 프로토콜에 대하여 알아보고 3장 에서는 본 논문에서 제안하는 알고리즘에 대해 설 명한다. 4장에서 제안한 라우팅 방법과 기존의 라 우팅 방식을 VANET 시뮬레이션 환경에서 성능을 평가한다. 마지막으로 5장에서 본 연구에 대한 전 체적인 평가와 고찰로 결론을 맺는다.

Ⅱ. 관련연구

본 장에서는 VANET 환경에서의 on-demand 방식 라우팅과 위치기반 라우팅, 그리고 table-driven 방식 을 적용한 위치기반 라우팅의 특성을 살펴본다. VANET 환경에서 각 라우팅 알고리즘이 갖는 취약 성을 파악하여 VANET 환경 및 도심지 환경에 적 합한 라우팅 알고리즘 개발의 필요성을 제시한다.

1. AODV(Ad-Hoc On-demand Distance Vector)

AODV는 MANET(Mobile Ad-Hoc Network)기반의 라우팅 프로토콜로서 기본적으로 table-driven 알고리 즘 중 하나인 DSDV(Destination Sequence Distance Vector)와 on-demand 알고리즘인 DSR(Dynamic Source Routing)의 장점을 취합하고 문제점을 해결한 프로토콜이다[3][4][5]. AODV의 경로 요청 과정은 다 음과 같다. 목적지 노드에 대한 경로정보가 자신의 라우팅 테이블에 존재하지 않는 소스 노드는 RREQ(Route Request) 패킷을 생성하여 네트워크로 브로드캐스팅 한다. <그림 1>에 나타내고 있는 RREQ 패킷은 플러딩 방식을 통하여 maximum hop count에 도달할 때 까지 브로드캐스팅 된다. 경로 응 답 과정은 다음과 같다. 경로 요청 과정에서의 RREQ 패킷을 수신한 목적지 노드는 <그림 2>에서 나타내고 있는 RREP 패킷을 생성하여 RREQ 패킷이 경유해온 역 경로를 이용하여 소스 노드까지 유니캐 스트로 전송된다. 소스 노드가 RREP(Route Reply) 패 킷을 수신하게 되면 목적지 노드까지의 경로 설정 과정이 완료되고 데이터 패킷의 송신을 시작한다.

2. GSR(Geographic Source Routing)

GSR은 DSR의 on-demand 방식과 source routing 방식을 접목하여 위치정보를 이용하는 위치 기반 VANET 라우팅 프로토콜이다[6]. 모든 차량은 지도 정보를 가지고 있다는 가정을 전제로 도심 환경에 서 패킷의 이동 경로를 목적지까지의 각 교차로 정 보를 이용하여 효율적인 전송을 수행하도록 제안하 였다.

GSR에서는 목적지의 위치정보를 획득하는 과정 인 위치정보 서비스를 제안하는 알고리즘의 범위 밖으로 보고 다루고 있지 않고 있다. 많은 연구에서 목적지의 위치를 획득하기 위한 위치정보 서비스에 대한 연구가 진행되고 있다[7]. <그림 3>과 같이 경 로 설정 과정에 있어서 RREQ 패킷을 사용하여 목 적지 노드를 발견하고 RREP 패킷의 수신으로 소스 노드는 목적지 노드의 위치 정보를 획득한다. 목적 지 노드의 위치 정보 획득을 통해 소스노드는 목적 지 노드까지 경유하는 교차로의 순차번호들을 패킷 헤더에 추가하는 source routing 방식을 이용한다. 각 노드는 목적지 노드에 대한 경로정보를 저장하 는 테이블을 갖지 않고 on-the-fly 방식을 통해 데이 터 패킷을 목적지 노드에게 전달한다.

3. POVRP(A Position-Based On-demand Routing Protocol in VANET)

POVRP는 VANET 환경에서 안정적인 경로 설정 및 경로 유지를 위한 유니캐스트 알고리즘과 위치 정보를 이용한 빠른 멀티 홉 브로드캐스트 알고리 즘에 대하여 제안하였다[8]. 차량 운행에서 안전 서 비스와 라우팅 알고리즘의 경로 설정 유지를 위해 주기적인 hello 패킷을 사용한다. hello 패킷은 한 홉 단위로 브로드캐스트 되며 차량의 위치, 속도, 방향 등에 대한 정보를 포함하고 있다. 따라서 모든 노드 는 자신의 한 홉 이내에 있는 이웃 노드들에 대한 정보를 이웃 노드 테이블에 저장 및 갱신함으로서 최신 정보를 유지한다.

일반적인 위치 기반 브로드캐스트는 노드의 통 신 반경에 따른 수신 노드와의 절대적인 거리 차이 에 따라 대기 시간을 산출한다[9]. 그러나 POVRP에 서는 송신 노드와 수신 노드의 거리 차에 따른 적 응적 대기 시간을 산출한다. 이를 통해 멀티 홉 브 로드캐스트 시 불필요한 대기 시간을 단축시킴으로 서 패킷이 보다 빠르게 전파되도록 하였다. 또한 경 로 요청 시 사용되는 RREQ 패킷의 브로드캐스트를 위한 안정적인 임계영역을 설정하였다. 안정적인 임계영역 설정을 위하여 경로 요청 예상 시간 동안 자신의 이웃 노드 테이블에 있는 이웃 노드들 중 상대 속도 차에 의해 통신 반경에서 벗어날 것으로 예상되는 노드와의 거리의 평균값을 이용하였다. 또한 교차로에서의 노드는 가장 짧은 대기시간으로 브로드캐스트 하게 된다. 그 결과 도심 환경에서의 패킷 전파 성공 가능성이 증가하게 되었다. 하지만 교차로에서의 가장 짧은 대기시간을 교차로 내에 위치한 모든 노드에게 동일하게 적용하게 되어 노 드의 밀도가 높아질 경우 충돌로 인한 패킷 전파 효율이 떨어지게 된다.

4. 거리기반 브로드캐스트 (Distance-Based broadcast)

거리 기반 브로드캐스트는 소스 노드가 브로드 캐스트 메시지를 전송하면 이 메시지를 수신한 노 드들은 각각 일정한 대기시간(waiting time)을 가지 며 대기한다. 여기서 대기시간은 소스노드와의 거리 에 따른 것으로 거리가 먼 노드일수록 짧은 시간을 갖는다. 자신의 대기시간동안 동일한 패킷을 다른 노드가 브로드캐스트 했다면 자신은 더 이상 이 패 킷을 재전송하지 않는다. 즉 소스 노드로부터 가장 거리가 먼 노드는 가장 짧은 대기 시간을 가짐으로 써 가장 먼저 브로드캐스트 하게 되고 이 사실을 인 지한 대기 중인 다른 노드들은 전송을 중단하여 결 과적으로 소스 노드로부터 가장 먼 노드만 다시 브 로드캐스트 하게 된다. 만약 가장 먼 노드가 전송에 실패하였다하더라도 그 다음으로 가장 짧은 대기시 간을 갖는 다른 노드에 의해 전송은 이루어진다.

이러한 거리 기반 브로드캐스트 방식에서 대기 시간은 기본적으로 식(1)에서 나타내고 있는 선형 적인 형태를 보인다[10, 11].

본 논문에서 제안하는 알고리즘은 차량의 위치 정보를 이용한 거리기반 브로드캐스트 방식을 이용 한다. 주변 차량의 위치 정보 획득은 이전 연구인 POVRP의 방식과 마찬가지로 주기적인 hello 패킷 을 통해 한 홉 이내에 있는 이웃 노드들에 대한 정 보를 유지한다[8].

Ⅲ. 도심환경을 고려한 위치기반 라우팅 프로토콜

관련연구에서 살펴본 바와 같이 현재까지 개발 된 라우팅 프로토콜은 위치정보 및 차량의 속도정 보를 이용하여 기존 연구에서 보다 발전되어왔다. 그러나 일반적인 고속도로 환경과 전파 장애 요소가 많은 도심환경에서 보다 유연하게 동작할 수 있는 라우팅 프로토콜이 필요한 실정이다. 또한 VANET 환경에서 이용되는 서비스나 유니캐스트를 위한 경 로 요청을 위해 많은 멀티 홉 브로드캐스트 패킷이 발생하게 된다. 멀티 홉 브로드캐스트는 발생 횟수 와 노드의 밀도에 따라 전체 네트워크의 트래픽이 기하급수적으로 늘어나게 된다.

경로 요청 브로드캐스트는 패킷을 재전송하게 되는 전달 노드가 경로 응답 과정을 완료함으로서 유니캐스트 전송을 위한 경로가 된다. 따라서 네트 워크 계층에서 패킷에 대한 정보를 유지해 지속적 인 특성을 가지고 있다. 또한 경로의 이탈이 예상되 는 노드를 전달 노드에서 제외하여 안정적인 경로 를 설정할 수 있는 기능이 요구된다. 또한 도심환경 에서는 교차로에서의 전송 성공이 보장되어야한다. 따라서 본 장에서는 교차로에서의 전송 성공률 보 장과 함께 안정적인 전달 노드를 선정할 수 있는 알고리즘을 설명한다.

1. 교차로에서의 위치에 따른 우선순위 차등화 알고리즘

VANET 환경에서의 경로 요청 브로드캐스트는 <그림 4>에서 보여 지는 것처럼 경로 요청 패킷이 발생 되었을 경우 목적지를 발견할 때까지 멀티 홉 으로 브로드캐스트 된다. 도로상의 노드의 밀도에 따라 패킷은 전송되거나 전송되어지지 않는데 교차 로에서의 전송이 보장되지 않는다면 노드의 밀도가 충분하더라도 경로가 형성되어지지 않는다.

교차로에서의 전송 성공률을 높이기 위해서는 교차로 내에 존재하는 차량의 위치에 따른 적응적 대기시간이 필요하다. 교차로의 반지름과 차량의 통신 반경 그리고 교차로의 중심점으로부터 차량이 위치하는 거리에 따른 대기시간을 산출하기 위한 방법이 식(2)와 식(3)에 나타나 있다.

식(2)은 차량의 통신반경과 교차로의 반지름 거 리를 통해 교차로에서의 최대 대기시간을 산출한 다. 식(3)은 식(2)에서 산출된 교차로에서의 최대 대 기시간을 기반으로 <그림 6>과 같이 교차로에서 차 량 위치에 따른 선형적 대기시간인 T값을 산출한 다. 이러한 과정을 통해 구해진 선형적 대기시간 T 는 식(4)에 적용되어 지수적인 교차로 내에서의 최 종적인 대기시간을 <그림 7>과 같이 결정한다.

각 차량은 자신의 위치가 교차로 내부에 있다고 판단 될 경우 교차로 외부에 있는 차량보다 항상 작은 대기시간을 가짐으로서 먼저 브로드캐스트 할 수 있는 우선순위를 갖게 된다. 또한 교차로 내부에 있는 차량들 사이에서도 교차로 중심점으로 부터의 거리에 따른 적응적 대기시간을 적용함으로서 차량 이 동시에 전송하여 충돌이 발생할 수 있는 경우를 최소화한다.

2. 안정적인 경로설정을 위해 상대속도를 이용한 우선순위 알고리즘

Table-driven 라우팅 방식을 사용하는 프로토콜의 경우 경로 요청 과정에서의 전달 노드들은 경로 응 답 과정에서 성공했을 때 목적지로 패킷을 보내기 위한 경로가 된다. 따라서 경로 요청 과정에서의 전 달 노드 선택 방법은 안정적인 경로를 확보하기 위 한 전제조건이라 할 수 있다.

<그림 8(a)>는 greedy forwarding을 이용하여 전달 노드를 선택하는 과정을 보이고 있다. 그러나 상대 속도 차이가 클 경우 전달노드가 통신 반경에서 벗 어날 가능성 역시 크다고 할 수 있다. 전달 노드가 소스 노드의 통신 반경에서 벗어날 경우 경로 단절 현상이 발생하게 된다. 따라서 <그림 8(b)>와 같이 소스 노드와의 상대속도를 고려하여 경로 이탈이 예측되는 노드를 전달 노드에서 배제해야할 필요성 이 있다.

제안하는 내용은 다음과 같다. <표 1>에서 보이 는 바와 같이 소스노드는 이웃 노드 중 경로 요청 예상시간 동안 상대 속도 차이에 의해 자신의 통신 반경을 벗어날 것으로 예상되는 노드 중 가장 긴 거리를 D2로 설정한다. 경로 요청 예상 시간은 식 (5)를 통해 알 수 있다.

여기서 경로 요청 예상 시간은 목적지를 찾기 위 해 경로 요청 패킷이 전송 될 수 있는 최대 홉 수인 TTL과 1-hop 간 전송 시 예상되는 전송 시간, 그리 고 경로 응답 과정을 통해 진행된 경로로 다시 되 돌아오는 시간을 고려해 배수를 적용하여 설정하였 다. 이를 통해 경로 요청 패킷으로 인한 경로 응답 패킷의 수신까지 최대 시간을 산출할 수 있으므로 이를 경로 요청 예상 시간으로 설정한다.

D1영역은 소스노드로부터 가장 가까운 거리에 위치한 노드와의 거리로 설정한다. 이 영역은 가장 낮은 우선순위를 가지며 불필요한 대기시간을 단축 하기 위하여 사용된다. 결과적으로 <그림 9>에서 보여 지는 것처럼 D1으로 설정된 영역은 가장 낮은 우선순위를 갖는다. 그리고 D2영역이 두 번째 우선 순위를 가지며 노드의 통신반경 중 D1과 D2영역을 제외한 영역이 가장 안정화된 영역으로 판별된다.

<그림 10>은 차량의 전후방에 따른 영역의 구분 을 나타낸다. D1영역과 D2영역은 소스 노드를 중심 으로 이웃 노드간의 상대속도 정보를 이용하여 예 측되는 거리로 나타내어진다. 따라서 도로를 따라 토폴로지가 형성되는 VANET의 특성상 차량의 전 방과 후방의 교통 상황이 달라질 수 있으므로 이에 대한 고려가 필요하다. 소스 노드는 자신의 이웃 노 드테이블에 있는 정보를 토대로 하여 전방과 후방 에 대한 D1, D2영역의 거리 값을 경로 요청 패킷에 추가하여 브로드캐스트 한다. 패킷을 수신한 노드 는 자신이 소스 노드 기준으로 전방 또는 후방에 있는지에 대하여 판별하고 패킷 내 영역 정보를 이 용하여 자신의 대기시간을 산출한다. 대기시간 동 안 동일한 패킷의 송신 여부가 판별되지 않는다면 자신의 이웃 노드 테이블로부터 D1과 D2영역에 대 한 정보를 경로 요청 패킷에 갱신한 후 브로드캐스 트 한다. 전·후방에 대한 D1과 D2영역의 거리를 구 하는 식은 각각 식(6)와 식(7)을 통해 알 수 있다.

D1과 D2영역의 구분과 이로 인한 우선순위 적용 에 따른 대기시간은 각각 <그림 11>, <그림 12>와 같다. 노드가 교차로 내에 위치할 경우를 제외하고 우선순위가 가장 높은 D1과 D2사이 구간은 거리가 가장 먼 구간에서부터 가장 짧은 대기시간을 가지 며 증가한다. 브로드캐스트 패킷의 재전송이 이 영 역에서 이루어지지 않는다면 D2영역부터 거리가 먼 쪽으로 대기시간이 증가한다. D2영역은 노드의 이탈이 예상되는 영역이므로 거리가 늘어날수록 대 기시간이 증가한다. 가장 낮은 우선순위를 갖는 D1 영역은 브로드캐스트 패킷 전송 시 노드가 존재하 지 않는 영역이지만 이 영역 자체가 예측된 값을 사용하는 것이므로 경로 요청 시간 내에도 D1 영역 내에 노드가 존재 할 수 있다. D1과 D2의 값을 이 용한 대기시간은 식 (8)을 통해 알 수 있다.

D2영역에 두 번째 우선순위를 부여하여 상대적 으로 Greedy forwarding에 비해 소스 노드에 보다 가까운 노드가 전달 노드로 선정될 가능성이 높다. 따라서 경로상의 홉 카운트가 낮고 초기 지연시간 이 적게 발생할 것이다. 그러나 경로 이탈 가능성이 예측되는 노드의 우선순위를 낮춤으로써 유니캐스 트 전송에서 보다 안정적인 데이터 전송이 가능하 게 된다.

Ⅳ. 성능평가

1. 성능평가 환경

성능 평가를 위한 시뮬레이터는 Qualnet 4.5를 사 용하였다. 시뮬레이션 환경은 서론에서 언급되었던 WAVE 환경에 부합되도록 설정하였다. <표 2>은 시뮬레이션에서 사용되는 주요 파라미터 값을 나타 내고 있다.

시뮬레이션 공간은 2200m X 1500m 의 크기를 갖는 맨하탄 모델을 사용하였다. 격자 형태를 가지 고 있는 맨하탄 모델은 도심 환경에서의 시뮬레이 션을 위해 많은 연구가 이루어지고 있다[10][11]. 본 논문에서는 <그림 13>과 같이 실제 맨하탄의 도심 지를 모델링하여 시뮬레이터에 적용하였다. 또한 도심지 모델에서 교통공학적인 차량의 움직임을 재 현하기 위하여 SUMO(Simulation of Urban MObility) 시뮬레이터를 이용하였다[12].

2. 성능분석

성능분석은 제안된 알고리즘을 적용한 라우팅 프로토콜과 기존 연구의 방식을 비교하여 수행하였 다. <그림 14>의 종단 간 패킷의 평균 지연시간을 보면 AODV 경우 차량의 밀도가 증가하면서 지연 시간이 감소하는 현상을 보인다. 그러나 차량의 밀 도가 가장 높을 경우 패킷의 충돌과 재전송으로 인 한 지연시간이 급격히 상승하게 된다. 그에 비해 거 리기반 브로드캐스트 방식을 사용하는 그 외 프로 토콜들의 경우 밀도가 증가함에 따라 지연 시간이 감소하는 현상을 보이며 프로토콜 간 지연시간의 큰 차이를 보이지 않는다.

<그림 15>와 같이 RREQ 패킷 전송률의 경우 차 량의 밀도가 증가함에 따라 전반적으로 전송률의 증가를 보이고 있다. 제안하는 알고리즘은 교차로 에서의 우선순위 차등화를 통해 전송 안정성을 도 모하여 차량의 밀도가 증가할수록 다른 프로토콜들 에 비해 전송률의 격차가 커지는 것을 보이고 있다. POVRP에 비해 최대 약 8%의 전송률이 향상되었음 을 알 수 있다. 또한 모든 노드가 재전송에 참여하 게 되는 플러딩 방식을 사용하는 AODV의 경우 차 량의 밀도가 증가함에도 패킷의 전송률 증가폭이 크지 않음을 확인할 수 있다.

결과적으로 <그림 16>의 시간 당 처리량을 보면 제안된 알고리즘의 경우 안정적인 경로 설정을 통 한 패킷 전송으로 인해 차량의 밀도가 증가함에 따 라 처리량이 향상되는 것을 알 수 있다. 이는 경로 요청 과정에서의 안정적인 경로 설정과 교차로에서 의 RREQ 패킷 도달률이 향상된 결과로 볼 수 있을 것이다. POVRP와 GSR의 경우 차량의 밀도가 증가 함에 따라 처리량이 늘어나는 것을 확인할 수 있으 나 그 차이가 크지 않다. 이는 경로 요청 과정의 성 공 여부와 잦은 경로 이탈을 원인으로 파악할 수 있다. AODV는 높은 네트워크 트래픽으로 인해 패 킷의 처리량이 매우 저조하게 나타나고 있다.

<그림 17>은 시간의 증가에 따른 전체 네트워크 의 오버헤드를 나타낸다. AODV의 경우 플러딩 방 식으로 인한 매우 높은 오버헤드 증가율을 보인다. GSR은 패킷의 헤더에 경로정보를 추가하는 source routing 방식으로 인해 다소 높은 오버헤드를 갖는 다. POVRP의 경우 제안된 알고리즘과 큰 차이를 보이고 있지 않다. 그러나 시간이 증가함에 따라 근 소한 차이를 보이고 있다. 이는 경로 설정 과정에서 의 차이로 인해 POVRP가 좀 더 많은 제어 패킷을 발생시키는 것으로 파악할 수 있다.

결과적으로 패킷 전송 시 평균 지연 시간은 플러 딩 방식을 사용하는 AODV에서 높은 값을 보인다. 차량의 밀도가 높아질수록 큰 폭의 상승을 보이고 있다. 이는 플러딩 방식에서의 네트워크의 트래픽 증가로 인해 발생된 많은 패킷 손실을 원인으로 볼 수 있다. 그 밖의 프로토콜들에서는 전송 지연에 있 어 큰 차이를 보이고 있지 않다. RREQ 패킷 전송 률에서는 낮은 트래픽을 발생하는 greedy forwarding 프로토콜이 우수한 성능을 보이며 제안된 알고리즘 의 경우 차량의 밀도가 높아짐에 따라 전송률의 상대 적 차이가 더 높아지는 현상을 보이고 있다. 시간당 처리량을 나타내는 단위 시간당 처리량(throughput)에 서는 경로 복구 메커니즘과 각 프로토콜에서 발생 되는 트래픽 양에 따라 AODV와 GSR의 성능차이 를 보이고 있다. 제안된 알고리즘은 이전 연구인 POVRP에 비해 교차로에서의 전송 향상과 안정적 경로 획득을 통하여 차량의 밀도가 증가할수록 높 은 차이를 보이고 있다.

Ⅴ. 결 론

차량 간 애드-혹 통신은 기반 시설 없이 차량 간 의 무선 통신을 통해 운전자에게 안전성과 편의성 을 제공해 줄 수 있다. 그러나 차량의 속도가 빠르 고 토폴로지가 빈번하게 변화할 수 있는 차량 간 통신의 특징은 데이터를 안정적으로 전송함에 있어 네트워크 부하 및 전송 지연이 매우 중요하다고 할 수 있다. 본 논문에서 제안하고 있는 멀티 홉 브로 드캐스트 알고리즘은 거리 기반 브로드캐스트 방식 과 경로 요청 과정에서의 안정적인 전달 노드의 선 택으로 인해 이전 연구에 비해 네트워크 오버헤드 를 8% 감소하였으며 패킷의 처리량을 25%향상시 킬 수 있었다. 또한 교차로에서의 우선순위 차등화 를 통하여 도심 환경에서도 전파 장애 요인을 극복 하여 전체적인 네트워크 성능의 향상을 확인할 수 있었다.