Index


Figures


Tables

Choi† , Nam†† , and Lee†††: Multi-hop Vehicular Cloud Construction and Resource Allocation in VANETs

Hyunseok Choi† , Youngju Nam†† and Euisin Lee†††

Multi-hop Vehicular Cloud Construction and Resource Allocation in VANETs

Abstract: Vehicular cloud computing is a new emerging technology that can provide drivers with cloud services to enable various vehicular applications. A vehicular cloud is defined as a set of vehicles that share their own resources. Vehicles should collaborate with each other to construct vehicular clouds through vehicle-to-vehicle communications. Since collaborating vehicles to construct the vehicular cloud have different speeds, directions and locations respectively, the vehicular cloud is constructed in multi-hop communication range. Due to intermittent wireless connectivity and low density of vehicles with the limited resources, the construction of vehicular cloud with multi-hop communications has become challenging in vehicular environments in terms of the service success ratio, the service delay, and the transmitted packet number. Thus, we propose a multi-hop vehicular cloud construction protocol that increases the service success ratio and decreases the service delay and the transmitted packet number. The proposed protocol uses a connection time-based intermediate vehicle selection scheme to reduce the cloud failure probability of multi-hop vehicular cloud. Simulation results conducted in various environments verify that the proposed protocol achieves better performance than the existing protocol.

Keywords: Vehicular Cloud , Multi-hop Cloud Construction , Connection Time

최현석† , 남영주†† , 이의신†††

VANET 망에서 다중 홉 클라우드 형성 및 리소스 할당

요 약: 최근 주목받는 기술인 차량 클라우드 컴퓨팅은 운전자들에게 다양한 차량 응용 어플리케이션을 위한 클라우드 서비스를 제공해 줄 수 있다. 차량 클라우드는 각각의 차량들이 보유한 리소스를 서로 공유하는 차량들의 집합이다. 차량 클라우드를 형성하기 위해 차량들은 차량 대 차량(Vehicle-to-Vehicle) 통신을 통해 서로 협력해야 한다. 차량 클라우드 형성을 위해 협력하는 차량들은 각각의 속도와 이동 방향 및 현재 위치가 다르므로 차량 클라우드는 다중 홉에 걸쳐 형성되어야 한다. 다중 홉 통신을 이용한 차량 클라우드 형성은 간헐적인 무선 연결성과 제한된 리소스를 보유한 차량의 수가 적은 환경으로 인해 차량 클라우드의 형성이 어렵다. 따라서, 다중 홉 통신 방식을 이용한 차량 클라우드 형성은 차량 간 통신의 안정성을 높여 클라우드의 형성 및 서비스 효율을 높이고, 서비스 지연시간 및 차량 간 교환 패킷의 수 등에서 개선 방안이 필요하다. 본 논문은 요청 차량과 가용 리소스를 제공하는 제공 차량들 간의 연결 시간을 고려하여 클라우드 형성 및 서비스 효율을 높이고 서비스 지연과 전송 패킷의 수를 줄이는 다중 홉 클라우드 형성 방안을 제안한다. 제안 방안은 차량들 사이의 연결 시간을 기반으로 홉과 홉을 연결하기 위한 중간 차량을 선택하여 다중 홉 차량 클라우드 형성의 실패율을 감소시킨다. 다양한 환경에서 수행된 시뮬레이션은 제안 방안이 기존의 방안보다 향상된 성능을 보이는지 검증한다.

키워드: 차량 클라우드, 다중 홉 클라우드 형성, 연결 시간 기반

1. 서 론

무선 애드 혹 통신과 차량 기술의 발전에 따라, VANET은 차량들 사이의 애드 혹 이동 통신 네트워크를 구성하여 차량 간의 데이터 전달이 가능하게 되었다[1]. 다수의 연구 및 프로젝트(VIC’S[2], CarTalk 2000[3], NOW(Network-on-Wheels)와 산업(Car2Car Communication Consortium[4])에서 VANET을 이용하여 지능형 교통 시스템에서, VANET은 운전자와 탑승자에게 안전과 편의를 제공하고, 엔터테인먼트 및 환경 모니터링을 위한 새로운 응용 어플리케이션을 도입한다[5]. VANET에 관련된 많은 연구들은 차량의 액티브 세이프티에 관한 사고 경보, 공공 서비스를 위한 긴급 차량 접근, 원활한 주행을 위한 교통 정체 알림, 기업의 상업 광고와 같은 다양한 분야에서 진행되어 왔다[6-8].

최근 들어, 차량 통신은 새로운 패러다임과 함께 발전하고 있다. VANET 컨텐츠의 특성과 발전하는 VANET 응용 어플리케이션이 컨텐츠를 소비하는 방식이 진보를 주도하고 있다[8]. 차량은 자신이 위치한 지역과 관련된 많은 양의 컨텐츠를 생성하고 소비한다. 차량들은 각자 보유하고 있는 가용 리소스(프로세싱, 메모리, 네트워크, 저장소 등)를 공유하여 부가가치 서비스를 창출하기 위해 협력한다. 차량 클라우드 컴퓨팅[10, 11]은 미래의 VANET 응용 어플리케이션을 지원하기 위해 리소스를 공유하여 차량들이 클라우드 서비스를 이용할 수 있는 새로운 기술이다. 차량 클라우드는 각각의 차량들이 리소스를 서로 공유하는 차량들의 집합이다. 로드 사이드 유닛과 같은 중앙 인프라스트럭처를 항상 이용할 수 없기 때문에, 클라우드 서비스를 원하는 요청 차량은 차량 대 차량(Vehicle-to-Vehicle) 통신을 통해 다른 차량들과 차량 클라우드를 구성하기 위해 서로 협력해야 한다[13]. 또한, 차량 클라우드는 클라우드를 구성하기 위한 충분한 리소스를 제공하는 제공 차량들을 탐색하기 위해 다중 홉 통신 방식을 이용한다[14]. 통신이 불안정하고 제한된 리소스를 가진 차량의 수가 적은 환경에서 다중 홉 통신 방식을 이용한 차량 클라우드 형성은 서비스 효율, 서비스 지연시간, 전송 패킷의 수 등에서 개선 방안이 필요하다.

Table 1.

Comparison of Related works
Proposed Protocol Summary Drawback
CONAWARE[12] To find neighbor vehicles, the requester vehicles uses broadcasting communication. The heavy broadcasting generates a number of packets and causes broadcasting storm.
SMARt[13] The farthest vehicle is selected as a controller in the single-hop of the requester vehicle to search and allocate resources in multi-hop communication range. The connection between the requester vehicle and intermediate vehicle is unstable because it only consider the farthest vehicle as a controller.
PrEPARE[14] It selects the vehicle which has longest connection time with the requester vehicle as an intermediate vehicle called superpeer. Since only consider the connection time between the requester vehicle and superpeer, the vehicular cloud construction is broken frequently.

2. 관련 연구

로드 사이드 유닛과 같은 중앙 인프라스트럭처를 사용하지 않고 다중 홉 통신 방식으로 리소스 탐색을 수행하여 다중 홉 차량 클라우드를 구성하는 방안이 연구되어 왔다[12-14].

Table 1에 나타낸 이전 방안들은 리소스 할당 과정에서 리소스를 제공하는 차량에 인접한 차량들을 고려하지 않아 충분한 리소스를 가진 차량을 탐색하지 못해 차량 클라우드 서비스 효율을 감소시킨다. 게다가, 이전 방안들은 차량 클라우드에서 차량 사이의 연결 실패와 차량 클라우드를 이탈한 차량들을 대체하기 위한 방안을 제시하지 않는다.

CONAWARE는 차량 클라우드를 구성하기 위해 필요한 충분한 리소스를 다중 홉 통신 범위에서 할당 받기 위해 리소스를 가진 모든 인접 차량을 탐색하기 위해 브로드 캐스트를 사용했다[12]. SMARt는 멀티 홉 리소스 탐색 과정에서 모든 인접 차량의 참여를 위해 브로드 캐스트를 이용하여 발생하는 오버 헤드를 감소시키기 위해 요청 차량의 단일 홉 통신 범위에서 가장 먼 거리에 위치한 차량을 컨트롤러라는 중간 차량을 선택하여 요청 차량과 컨트롤러의 통신 범위에서 다중 홉 리소스 탐색 과정을 수행한다[13]. 가장 먼 거리에 위치한 차량을 중간 차량으로 선택하면 연결 실패 확률이 높아지므로, PrEPARE는 요청 차량과 인접 차량들의 연결 시간을 고려하여 단일 홉 내의 연결 시간이 가장 긴 인접 차량을 superpeer라 지칭하는 중간 차량으로 선택한다[14]. 그러나, PrEPARE는 요청 차량과 중간 차량의 단일 홉 연결 시간만을 고려하므로, 다중 홉에 걸쳐 형성된 차량 클라우드의 빈번한 실패를 발생시키기 때문에 잦은 클라우드 재형성을 필요로 한다. 또한, 이전 방안들은 리소스 할당 과정에서 리소스를 제공하는 차량에 인접한 차량들을 고려하지 않아, 충분한 리소스를 가진 차량을 탐색하지 못해 차량 클라우드 서비스 효율을 감소시킨다. 게다가, 이전 방안들은 차량 클라우드에서 차량 사이의 연결 실패와 차량 클라우드를 이탈한 차량들을 대체하기 위한 재형성 방안을 제공하지 않는다.

따라서, 본 논문은 클라우드 형성 및 서비스 이용 효율을 증가시키고, 서비스 지연 시간과 전송 패킷 수를 줄이는 다중 홉 클라우드 구성 방안을 제시한다. 제안 방안은 다중 홉 연결 시간을 기반으로 차량 클라우드를 형성하기 위해 충분한 리소스를 보유한 차량들을 선택하여 클라우드를 형성하고, 중간 차량 선택은 제공 차량이 요청 차량이 클라우드 서비스를 이용하고자 하는 서비스 시간보다 긴 연결 시간을 가진 차량을 선택하여, 연결 실패로 인한 클라우드의 실패 확률과 다중 홉 차량 클라우드 구성을 위한 패킷의 수를 줄인다. 또한, 제안 방안은 다중 홉 차량 클라우드 구성을 위해 인접 차량의 수와 클라우드 서비스 시간을 기반으로 차량의 리소스를 할당한다. 차량 리소스 할당은 리소스를 제공하는 차량의 인접 차량들의 수를 고려하여 선택하므로, 클라우드 형성 실패 확률을 감소시킨다.

제안 방안의 차량 클라우드 재형성 방안은 연결 시간 측정 오류와 클라우드를 구성하는 차량의 예상치 못한 이탈로 인한 클라우드 실패를 기존 차량의 주변 차량으로 대체하여 클라우드를 신속하게 재형성하여 클라우드 서비스 지연을 감소시킨다. 다양한 환경에서 수행된 시뮬레이션 결과는 제안 방안의 클라우드 실패 비율 및 클라우드 형성 지연 시간 측면에서 기존 방안들 중 하나인 PrEPARE 보다 향상된 성능을 보임을 검증한다.

본 논문의 나머지는 다음과 같이 구성된다. 섹션 2에서는 제안 방안의 네트워크 모델을 제시한다. 섹션 3에서는 제안 방안의 전체과정을 상세히 기술하며, 섹션 4에서는 시뮬레이션 결과를 통해 제안 방안의 성능을 평가한다. 섹션 5에서 본 논문의 결론을 내린다.

3. 연결시간 기반의 다중 홉 클라우드 형성 방안

3.1 네트워크 모델

본 논문에서, 요청 차량은 클라우드 서비스를 이용하기 위해 일정량의 리소스와 서비스 시간을 필요로 한다. 리소스는 요청 차량에게 제공할 수 있는 제공 차량이 보유한 가용 리소스를 말하고, 서비스 시간은 제공 차량이 요청 차량에게 리소스를 제공 가능한 시간을 말한다. 요청 차량은 부족한 리소스와 서비스 시간을 보충하기 위해, 단일 홉 또는 다중 홉 통신 범위에서 요청 차량의 통신 범위 내에 위치한 주변 차량들을 검색함으로서 제공 받을 수 있는 리소스와 서비스 시간을 보유한 제공 차량들을 선택한다. 이 과정에서 리소스와 서비스 시간을 보유한 주변 차량은 현재 위치, 속도 및 이동 경로를 포함하는 비콘 신호를 주기적으로 브로드 캐스트 하고 있다. 요청 차량이 클라우드를 형성하기 위해 필요한 리소스를 검색 과정에서, 요청 차량의 주변 차량 중 제공 차량을 선택을 위해 이용하는 파라미터는 제공 가능한 리소스, 서비스 시간, 요청 차량과의 연결 시간 및 주변 차량의 수이다. 모든 차량이 주기적으로 비콘 신호를 브로드 캐스트 하기 때문에 연결 시간은 시간-공간 유사성 알고리즘을 통해 계산된다. 현재 위치(x, y) 및 현재 속도를 이용하여 미래 위치(x’, y’)를 계산한다. 이를 통해, 모든 차량은 단일 홉 통신 범위에서 자신과 주변 차량 사이의 연결 시간을 계산할 수 있다[12, 15]. 계산된 연결 시간은 제공 차량을 선택하기 위한 파라미터 중 하나로 사용된다.

각 차량이 보유한 각 파라미터는 다음과 같다:

리소스 및 서비스 시간 연결 시간 주변 차량의 수

리소스 및 서비스 시간은 제공 차량과 중간 차량 선택에 있어 동등한 우선순위를 가진다. 다음 우선순위를 가진 연결 시간은 시간-공간 유사성 알고리즘에 따라 요청 차량과 제공 차량 사이의 통신이 가능한 시간을 말한다. 마지막 우선순위를 가지는 주변 차량의 수는 다중 홉에서 중간 차량 선택 과정에서 사용되는 중간 차량의 통신 범위 내에 위치해 있는 차량의 수를 나타낸다.

이 파라미터들을 사용하는 이유는 다음과 같다. 먼저, 사용 가능한 리소스와 서비스 시간이 충분해도 요청 차량과 제공 차량 사이의 연결시간이 서비스 시간보다 부족할 경우, 요청 차량이 제공 받은 리소스와 서비스 시간을 완전히 활용하지 못하고 연결이 끊어진다. 다음으로, 요청 차량이 클라우드를 형성하여 클라우드 서비스를 이용하는 도중, 제공차량 중 하나가 연결시간이 0이 되거나, 자신의 클라우드를 형성하기 위해서 서비스 시간과 리소스를 돌려받아 클라우드를 이탈할 수 있다. 이 경우, 요청 차량은 이미 제공차량의 주변 차량 정보를 가진다. 요청 차량은 이 정보를 이용해서 클라우드를 이탈하는 차량의 이웃 차량을 통해 이탈하는 제공차량을 대신할 수 있다. 이 방안은 클라우드 실패를 방지하고, 신속한 제공 차량 교체로 클라우드 안정성을 높인다. 클라우드 서비스는 요청 차량이 필요한 리소스와 서비스 시간을 주변 차량에게 요청한 시점부터 클라우드가 해제 될 때까지로 정의한다.

3.2 리소스 탐색과 할당

리소스 탐색은 요청 차량이 클라우드 형성에 필요한 리소스, 서비스 시간 그리고 제공차량의 주변 차량 숫자에 대한 요청 메시지를 브로드 캐스트 하는 과정이다. 요청 차량의 요청 메시지를 받은 주변 차량들은 요청 차량이 요청한 정보에 대한 응답 메시지를 보낸다. 주변 차량으로부터 응답 메시지를 받은 요청 차량은 주변 차량으로부터 받은 응답 메시지에 포함된 정보를 기반으로 제공차량 선정을 위해 자신과 주변 차량 사이의 연결시간을 계산한다. 주변 차량들과의 연결 시간 계산이 완료되면, 요청 차량은 응답 메시지를 보내온 주변 차량들 중에 제공차량을 선택하고, 제공차량에게 제공 가능한 리소스와 서비스 시간을 요청한다. 요청을 받은 제공 차량은 자신이 제공 가능한 리소스와 서비스시 간을 요청 차량에게 제공한다. 요청 차량은 자신이 보유한 리소스와 제공받은 리소스와 서비스 시간을 이용하여 클라우드를 형성하고 서비스를 이용한다.

Table 2.

Symbols and Definition of The Proposed Protocol
Symbol Definition
Rtotal Total requeired resource of the requester
STtotal Total required service time of the requester
Rn n-hop required resource of the requester
STn n-hop required service time of the requester
Vn A neighbor vehicle with its ID n
ASn An available set of neighbor vehicles for a cloud

1) 단일 홉 리소스 탐색 및 할당

단일 홉 탐색은 위의 리소스 탐색 및 할당 절차와 동일하다. 하지만, 요청 차량이 요구하는 리소스와 서비스 시간을 요청 차량의 단일 홉 통신범위 내의 주변 차량들이 제공할 수 있다. 요청 차량의 요구 리소스와 서비스 시간은 아래와 같이 나타낼 수 있다.

Rsingle-hop Rtotal

STsingle-hop STtotal

Rsingle-hop과 STsingle-hop은 요청 차량의 단일 홉 통신 범위 안에 위치한 제공 차량들이 제공 가능한 총 리소스와 서비스 시간을 의미한다. 요구 차량의 요청을 만족하는 제공 차량의 조합으로 이루어진 이용 가능한 집합을 ASn이라고 하자.

예를 들어, 요청 차량이 50초의 서비스 시간동안 200MB의 리소스를 주변 차량들에게 요청할 때, 5대의 제공차량 (V1, V2, V3, V4, V5)가 존재하며, 각각 아래의 Table 3과 같은 리소스와 서비스 시간을 가지고 있다고 가정한다.

Table 3.

Information of Single-hop Neighbor Vehicle
Vehicle Resource (MB) Service Time Neighbor Vehicle Connection Time
V1 120 20 5 30
V2 100 30 7 60
V3 50 10 3 10
V4 30 5 1 40
V5 10 40 4 100

요청 차량의 요청을 만족시키는 ASn들은 아래 Table 4와 같다. ASn 중에서 네트워크 모델에서 언급된 파라미터들의 우선순위에 따라 요청 차량은 가장 적합한 AS를 선정한다. 모든 ASn이 요청 리소스와 서비스 시간을 만족하므로, 연결 시간과 주변 차량의 수에 따라 선택한다.

Table 4.

Information of Single-hop Available Set
ASn Resource (MB) Service Time Neighbor Vehicle Connection Time
AS1 310 105 20 240
AS2 220 50 12 90
AS3 270 60 15 100
AS4 300 65 16 140

위의 Table 4에서 가장 많은 주변 차량 수와 긴 연결시간을 가진 AS1이 가장 적합한 AS로 선택된다. 요청 차량은 AS1으로부터 리소스와 서비스 시간을 제공 받아 클라우드를 형성하고 서비스를 사용한다. 하지만 주변 차량들의 리소스와 서비스 시간이 부족한 경우, 요청 차량의 요청이 단일 홉 통신 범위에서 만족될 수 없다. 이 경우, 요청 차량은 단일 홉에서 부족한 리소스와 서비스 시간을 중간 차량을 통해 홉 수를 증가시켜 다중 홉 통신 범위에서 탐색한다.

2) 다중 홉 리소스 탐색 및 할당

요청 차량은 단일 홉 리소스 탐색 및 할당과정으로는 부족한 리소스와 서비스시간을 다중 홉 통신 범위에서 제공받기 위해 중간 차량을 선택해야 한다. 요청 차량은 주변 차량과의 연결 시간을 기반으로 중간 차량을 선택해야 한다. 다중 홉에서 이루어지는 리소스 탐색 및 할당 과정은 요청 차량이 단일 홉 탐색 및 할당 과정과 같으며, 이를 중간 차량의 통신 범위에서 반복 실행한다.

이전 연구에서 요청 차량은 더 많은 리소스와 서비스시간을 탐색하기 위해서 가장 멀리 있는 주변 차량을 중간 차량으로 선택한다. 또 다른 연구에서는 요청 차량이 자신과 중간 차량으로 선정될 차량 간에 연결시간만을 고려하여 가장 긴 연결시간을 가진 중간 차량을 선정하는 방안이다. 이러한 중간 차량 선정 방법은 다음과 같은 문제를 발생시킨다. 먼저, 요청 차량과 중간 차량 사이의 거리로 인한 연결 불안정성이 있다. 또한, 중간 차량의 속도 변화로 인해 클라우드 실패가 발생할 수 있다. 마지막으로, 요청 차량은 리소스와 서비스 시간을 제공받는 차량들과의 연결시간 불충분으로 인해 클라우드 서비스를 충분히 이용하지 못 할 수 있다.

본 논문에서는 앞서 제시한 이전 방안들의 단점을 보완하는 방안을 제시한다. 요청 차량은 단일 홉 통신범위 안에 다수의 주변 차량에게 요청 메시지를 보낸다. 요청메시지를 수신한 주변 차량들은 중간 차량 후보자가 된다. 각각의 중간 차량 후보자는 자신들의 단일 홉 통신범위의 주변차량들과의 연결 시간을 계산하고 요청 차량에게 전달한다. 중간 차량 후보들로부터 전달받은 정보를 이용하여 요청 차량은 Fig 1과 같이 중간 차량 후보들 중 요청 차량과의 연결시간과 중간 차량 후보의 통신 범위 내의 주변 차량들과의 연결시간이 서비스 시간 보다 긴 차량을 중간 차량으로 선택한다.

Fig. 1.

The Controller Selection using the Information of Neighbor Vehicles
1.png

다중 홉 할당은 단일 홉 할당과 유사하다. 중간 차량의 주변 차량들은 자신의 리소스와 서비스 시간을 중간 차량에게 제공한다. 주변의 제공 차량들로부터 리소스와 서비스시간을 받은 중간 차량은 요청 차량에게 이를 제공한다.

예를 들면, 두 홉에서의 탐색 및 할당 절차는 다음과 같다. 요청 차량은 단일 홉 범위의 제공차량으로부터 리소스와 서비스 시간을 제공받는다. 하지만, 요청 차량의 단일 홉 통신 범위에서 제공 받은 리소스와 서비스 시간은 클라우드를 형성하여 서비스를 이용하기에 부족하다. 요청 차량은 부족한 리소스와 서비스 시간을 제공 받을 두 홉 통신범위의 제공 차량들을 탐색하기 위해 통신 범위를 확장시킬 중간 차량을 선정해야 한다. 두 홉 범위에서의 요청 차량이 클라우드 서비스를 이용하기 위해 필요한 리소스와 서비스 시간의 조건은 다음과 같다.

Rtwo-hop Rtotal Rsingle-hop

STtwo-hop STtotal STsingle-hop

요청 차량의 요구조건이 리소스 500MB와 200초의 서비스 시간이라고 하자. 요청 차량은 앞서 언급한 예시의 단일 홉 통신 범위 안의 제공 차량으로부터 제공받는 리소스와 서비스 시간을 제외하고, 이 차량들 중 앞서 언급한 조건에 따라 중간 차량들로 선택하여 부족한 리소스 190MB와 95초의 서비스 시간을 선택된 중간 차량들의 통신 범위에 위치한 주변 차량들로부터 제공받아야 한다.

Table 5.

Information of Single-hop Neighbor Vehicle
Vehicle Resource (MB) Service Time Neighbor Vehicle Connection Time
V6 100 70 8 50
V7 130 40 1 10
V8 40 20 4 20
V9 70 50 6 30

Table 5에 나타난 차량들로 부족한 리소스와 서비스 시간을 보충할 수 있는 ASn은 다음과 같다.

Table 6.

Information of Single-hop Available Set
ASn Resource (MB) Service Time Neighbor Vehicle Connection Time
AS5 240 140 19 110
AS6 300 160 15 90
AS7 210 110 11 60

3개의 집합 모두 리소스와 서비스 시간은 요청 차량이 요구하는 양을 모두 만족 시킨다. 따라서, 앞서 네트워크 모델에서 언급한 파라미터의 우선순위에 따라 가장 적합한 AS을 선택하면, 연결 시간이 110이며, 이웃 차량의 수가 19으로 가장 많은 AS5이 선택되며, 중간 차량은 AS5의 정보를 요청 차량에게 전달하고, 동시에 리소스와 서비스 시간을 대신 제공 받아 요청 차량에게 전달하여 요청 차량이 클라우드를 형성하여 서비스를 이용할 수 있도록 한다.

3) 리소스 탐색 불가

리소스 탐색이 불가한 경우가 발생할 수 있다. 첫 번째 경우는 요청 차량이 부족한 리소스와 서비스 시간을 보충하기 위해 홉 카운트를 증가시키며 다중 홉에서 리소스 탐색을 하는 도중 중간 차량의 통신 범위 내에 차량이 존재하지 않는 경우가 발생한다. 두 번째 경우는 요청 차량이 단일 홉에서 리소스 탐색을 시작할 때, 요청 차량의 통신 범위 내에 위치한 주변 차량이 없는 경우이다. 세 번째 경우는 단일 홉 통신 탐색 후에 중간 차량을 선정하는 과정에서 요청 차량의 요구조건을 만족시키는 중간 차량이 없는 경우이다. 이러한 경우, 요청 차량은 통신 범위 내에서 자신의 요구 조건을 만족 시키는 주변 차량이 존재할 때까지 리소스 탐색을 반복 수행한다.

3.3 클라우드 관리

요청 차량이 클라우드를 형성하여 서비스를 이용하는 도중 요청 차량과 제공 차량 사이의 연결시간이 0이 되는 경우와 제공 차량이 자신의 클라우드를 형성하기 위해 요청 차량의 클라우드를 이탈하는 경우가 발생한다.

이 경우, 요청 차량은 기존 제공 차량을 대신할 새로운 제공 차량이 필요하다. 이를 위한 방안으로, 앞서 네트워크 모델에서 언급한 제공 차량의 주변 차량을 이용한다. 요청 차량은 제공 차량의 주변 차량들의 정보를 가지고 있으므로 이 정보를 이용하여 요청 차량은 제공 차량 선정 방식을 통해 기존 제공 차량을 대체할 새로운 제공 차량을 선정하여 클라우드를 재형성하는 시간을 줄일 수 있다.

4. 성능 평가

본 절에서는 NS-3 네트워크 시뮬레이터를 이용하여 제안 방안의 성능 평가를 나타낸다[16]. 제안 방안의 성능을 평가하기 위해 이전 연구의 PrEPARE 방안과 비교한다.

PrEPARE는 요청 차량의 클라우드의 실패가 발생하면 클라우드 서비스를 이용하기 위한 리소스 탐색 및 할당의 모든 과정을 처음부터 재실행한다. 이는 요청 차량이 클라우드를 형성하여 서비스를 이용하기까지 큰 지연시간을 발생시킨다.

반면, 제안 방안은 제공 차량의 주변차량 정보를 사용하여 클라우드 실패가 발생하더라도 전체 과정을 새로이 시작할 필요 없이 PrEPARE보다 빠르게 클라우드를 재형성 할 수 있다. 이에 대한 성능 평가를 위해, 차량의 밀도와 클라우드 서비스 이용에 필요한 리소스의 양, 차량들 사이의 상대 속도에 따른 클라우드 실패율과 지연시간을 성능 비교한다.

Table 7.

Simulation Parameters
Parameters Value
Transmission Power 10 dBm
Propagation Loss Model Range Propagation Loss Model
Transmission Range 80m
WiFi Model 802.11b
Bandwidth 6 Mbps
Network Size 2 km
Total Participation Vehicles 100
Simulation Time 55 s

클라우드 실패율은 제공 차량이 자신의 클라우드를 형성하거나 요청 차량과의 연결시간이 0이 되어 클라우드를 이탈하여 요청 차량이 더 이상 클라우드를 유지할 수 없는 경우를 말한다. 지연 시간은 클라우드 실패가 발생할 때, 요청 차량이 부족한 리소스를 탐색 및 할당 과정을 통하여 클라우드를 재형성하는데 소요되는 시간을 의미한다. 성능 평가를 위한 시나리오는 2km 편도 이차선 고속도로 환경이며, 100대의 차량들이 고속도로 내의 임의의 위치에서 요청 차량과 순방향 혹은 역방향으로 이동 중이다. 각 차량들은 80~140km 의 속도로 이동하며, 0~100MB 사이의 리소스를 보유하고 있다.

Fig. 2에서 제안 방안이 클라우드를 재형성하는데 소요되는 지연 시간이 더 적은 것을 확인할 수 있다. 이는 제안 방안이 제공 차량의 주변 차량 정보를 이용하여 중간 차량을 선택하기 때문이다. 하지만, PrEPARE는 단순히 요청 차량과 제공 차량 사이의 연결시간만을 사용해서 중간 차량을 선택하기 때문에, 중간 차량의 통신 범위 내에 차량이 없으면 클라우드 실패율이 높아진다. 클라우드가 형성되는 통신 범위 내에 차량의 수가 충분할 때, 클라우드 실패율은 두 방안 모두 감소한다.

Fig. 3에서 제안 방안과 PrEPARE은 차량 밀도가 4일 때, 지연 시간이 가장 크다. 차량 밀도가 4 이상으로 커지면, 클라우드의 범위가 단일 홉에서 다중 홉으로 확장되기 때문이다. 이는 클라우드 실패율의 원인과 유사하다. 지연 시간은 클라우드 실패가 발생할 때마다 증가한다. 클라우드가 형성되는 통신 범위 내에 차량의 숫자가 증가할수록 클라우드 실패율이 감소하여 클라우드가 재형성되는 횟수가 줄어들게 되어 지연 시간도 감소한다.

Fig. 4에서 요청 차량이 요구하는 리소스가 증가할수록 요청된 리소스의 양을 만족시키기 위해 다중 홉 통신 범위의 차량의 수가 증가해야 한다. 이는 통신 홉 수의 증가로 이어지며, 홉 수의 증가는 차량들 사이의 연결성이 약해지는 원인이 되며, 이로 인해 클라우드 실패 빈도가 높아진다. 클라우드 서비스 리소스의 양이 150MB인 시점부터 통신범위는 단일 홉에서 다중 홉으로 확장되며, 클라우드 실패가 발생하면, 대처 방안이 없는 PrEPARE의 클라우드 실패율은 크게 증가한다. 반면에, 제안 방안은 클라우드 실패가 발생하면 제공 차량의 주변 차량을 이용해서 기존의 제공 차량을 빠르게 대체한다. 제안 방안도 통신 범위가 확장될수록 클라우드 실패율이 증가하지만, PrEPARE과 비교해 현저히 낮은 클라우드 실패율을 가진다.

Fig. 5에서 지연시간의 증가는 Fig. 4의 클라우드 실패율 증가와 유사하다. 클라우드 서비스 리소스의 양이 150MB인 시점부터 지연 시간이 크게 증가한다. 이는 앞서 언급했듯이 통신 범위가 확장됨에 따라, 클라우드 실패가 발생할 때마다 지연 시간이 증가하기 때문이다. 요청된 리소스가 150MB이상으로 커지면 통신 홉 수가 증가하고, PrEPARE의 클라우드 실패율은 크게 증가한다. 하지만, 제안된 프로토콜의 클라우드 실패율은 상대적으로 낮은 증가율을 보인다.

Fig. 6 에서는 차량들 사이의 상대 속도가 증가함에 따라 제공 차량은 더 빠른 속도로 요청 차량의 통신 범위를 이탈하게 되고, 이는 요청 차량과 제공 차량의 연결 시간을 감소시키며, 결과적으로 클라우드 실패를 발생시키는 원인이 된다. 클라우드가 다중 홉 통신 범위에 걸쳐 형성되어 있다면, 클라우드 실패는 더욱 빈번하게 발생하게 된다.

Fig. 7에서 지연 시간 증가는 Fig. 6의 클라우드 실패율이 증가하는 원인과 유사하게 지연 시간을 증가시킨다. 지연시간은 차량 사이의 상대속도 증가로 인해, 요청 차량의 통신 범위를 제공 차량이 빠르게 이탈하므로, 클라우드 실패가 발생할 때마다 증가하게 된다.

Fig. 2.

The Cloud Failure Ratio for the Vehicle Density
2.png

Fig. 3.

The Delay of Cloud Construction for the Vehicle Density
3.png

Fig. 4.

The Cloud Failure Ratio for the Amount of Cloud Service Resource
4.png

Fig. 5.

The Delay of Cloud Construction for the Amount of Cloud Service Resource
5.png

Fig. 6.

The Cloud Failure Ratio for the Relative Velocity
6.png

Fig. 7.

The Delay of Cloud Construction for the Relative Velocity
7.png

5. 결 론

본 논문에서 제안하는 방안은 차량 클라우드를 구성하는 차량들 사이의 연결 시간을 고려하고, 클라우드를 이탈하는 제공 차량이 발생할 경우 제공 차량의 주변 차량을 이용하여 기존 제공 차량을 빠르게 대체하여 클라우드 재형성 시간을 감소시켜 클라우드 안정성을 향상시킨다. 이전 연구들은 클라우드를 구성하는 차량들의 리소스 양 또는 연결 시간만을 고려하여 차량 클라우드를 효율적으로 형성하고 서비스를 사용하는지에 대한 방안을 제시한다. 하지만, 형성된 차량 클라우드의 관리 및 클라우드 실패 시 대처 방안 또한 중요한 이슈이다. 차량 클라우드 통신 범위가 단일 홉에서 다중 홉으로 확장될 때, 클라우드 실패가 빈번하게 발생하고, 이에 따라 클라우드를 재형성되기까지 큰 지연시간이 소요된다. 따라서, 제안방안은 차량 클라우드를 구성하는 모든 차량들 사이의 연결 시간을 고려한 클라우드 형성과 형성된 클라우드의 유지 및 관리, 클라우드 실패에 대한 대처 방안을 제시한다. 클라우드 실패가 발생할 때, 이전의 방안은 전체 클라우드 형성 절차를 모두 다시 수행한다. 반면에, 제안 방안은 클라우드 실패가 발생할 때, 제공 차량의 주변 차량 정보를 이용하여 기존 제공 차량의 이탈이 발생하면 빠르게 대체하는 방안을 통해 차량 클라우드의 재형성에 소요되는 지연 시간을 감소시켜 클라우드 안정성을 높인다. 기존 PrEPARE 방안과 차량의 밀도, 클라우드 서비스에 필요한 리소스의 양, 상대속도에 따른 클라우드 실패율, 지연 시간을 성능 비교 평가한다. 제안 방안은 모든 비교 지표에서 기존 방안보다 적은 클라우드 실패율과 지연시간을 보인다.

Biography

최 현 석

https://orcid.org/0000-0001-9410-7244

e-mail : hschoi@chungbuk.ac.kr

2017년~현 재 충북대학교 전자통신공학과 석박사 통합과정

관심분야 : 무선 센서 네트워크, 차량 네트워크, 클라우드 컴퓨팅

Biography

남 영 주

https://orcid.org/0000-0003-3971-0715

e-mail : imnyj@chungbuk.ac.kr

2019년 충북대학교 전자통신공학과(석사)

현 재 충북대학교 전자통신공학과 박사과정

관심분야 : 무선 센서 네트워크, 차량 네트워크, 캐싱 최적화

Biography

이 의 신

https://orcid.org/0000-0002-0422-0647

e-mail : eslee@chungbuk.ac.kr

2008년 충남대학교 컴퓨터공학과(석사)

2012년 충남대학교 컴퓨터공학과(박사)

2014년~현 재 충북대학교 전자통신공학부 교수

관심분야 : 무선 센서 네트워크, 차량 네트워크, 클라우드 컴퓨팅, 컨텐츠 캐싱

References

  • 1 F. Li, Y. Wang, "Routing in Vehicular Ad Hoc Networks: Survey," IEEE Vehicular Technology MagazineJun, vol. 2, no. 2, pp. 12-22, 2007.custom:[[[-]]]
  • 2 S. Yamada, "The strategy and deployment plan for VICS," IEEE Communicationvol. 34, no. 10, pp. 94-97, 1996.doi:[[[10.1109/35.544328]]]
  • 3 D. Reichardt, M. Miglietta, L. Moretti, P. Morsink, W. Schulz, "CarTAKL 2000: safe and comfortable driving based upon inter-vehiclecommunication," in Proc. IEEE Intelligent Vehicle SymposiumJun, 2002.custom:[[[-]]]
  • 4 C.Consortium, www.car-2-car.org
  • 5 F. Bai, B. Krishnamachari, "Exploiting the Wisdom of the Crowd: Localized, Distributed Information-Centric VANETs," IEEE Commun. Mag.vol. 48, no. 5, pp. 138-46, May, 2010.doi:[[[10.1109/MCOM.2010.5458375]]]
  • 6 E. Schoch, F. Kargl, M. Weber, T. Leinmuller, "Communication Patterns in VANETs," IEEE Communications Magazine, pp. 119-125, Nov, 2008.doi:[[[10.1109/MCOM.2008.4689254]]]
  • 7 V. Kumar, S. Mishra, N. Chand, "Applications of VANETs: Present and Future," Communications and Network5, pp. 12-15, 2013.custom:[[[-]]]
  • 8 S. Y. Park, Y. W. Kim, "An Analysiss of the Interaction Effect of Benefit and Cost on Cloud Computing Service," KIPS Transactions on Computer and Communication Systemsvol. 2, no. 1, . DOI:10.3745/KTCCS..2.1.27, pp. 27-34, 2013.custom:[[[-]]]
  • 9 E. Lee et al., "Vehicular Cloud Networking: Architecture and Design Principles," Published in: Communications MagazineIEEE (Volume: 52, Issue: 2), ruary, pp. 148-155, Feb, 2014.doi:[[[10.1109/MCOM.2014.6736756]]]
  • 10 M. Gerla, "Vehicular cloud computing," in 2012 The 11th IEEE Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net), pp. 152-155, 2012.custom:[[[-]]]
  • 11 M. Whaiduzzaman et al., "A survey on vehicular cloud computing.," Journal of Network and Computer ApplicationsVolume 40, pp. 325-344, 2013.custom:[[[-]]]
  • 12 R. E. Siba, T. Atchian, J. B. Abdo, R. Tawil, J. Demerjian, "Connectivity-aware service provision in vehicular cloud," in Proc. Of the International Conference on Cloud Technologies and Applications (CloudTech), June, 2015;pp. 1-5. custom:[[[-]]]
  • 13 R. Meneguette, A. Boukerche, R. De Grande, "SMART: an efficient resource search and management scheme for vehicular cloud-connected system," in 2016 IEEE Global Communications Conference: Mobile and Wireless Networks (Globecom2016 MWN), Washington, USA, Dec. custom:[[[-]]]
  • 14 R. Meneguette, A. Boukerche, "Peer-to-peer Protocol for Allocated Resources in Vehicular Cloud Based on V2V Communication," in 2017 IEEE Wireless Communications and Networking Conference (WCNC), San Francisco, CA, USA, Mar. custom:[[[-]]]
  • 15 T. Atechian, Protocole de routage géo-multipoint hybride et mécanisme d'acheminement de données dans les réseaux ad hoc de véhicules (VANETs), INSA de lyon, 2010.custom:[[[-]]]
  • 16 NS-3, http://www.nsnam.org/

Statistics


Cite this article

IEEE Style
H. Choi, Y. Nam, E. Lee, "Multi-Hop Vehicular Cloud Construction and Resource Allocation in VANETs," KIPS Transactions on Computer and Communication Systems, vol. 8, no. 11, pp. 263-270, 2019. DOI: 10.3745/KTCCS.2019.8.11.263.


ACM Style
Hyunseok Choi, Youngju Nam, and Euisin Lee. 2019. Multi-Hop Vehicular Cloud Construction and Resource Allocation in VANETs. KIPS Transactions on Computer and Communication Systems, 8, 11, (2019), 263-270. DOI: 10.3745/KTCCS.2019.8.11.263.


TKIPS Style
Hyunseok Choi, Youngju Nam, Euisin Lee, "Multi-Hop Vehicular Cloud Construction and Resource Allocation in VANETs," KIPS Transactions on Computer and Communication Systems, vol. 8, no. 11, pp. 263-270, 11. 2019. (https://doi.org/10.3745/KTCCS.2019.8.11.263)