Design and Evaluation of Schemes for Replacing Multiple Member Vehicles in Vehicular Clouds

Abstract

Vehicular clouds are considered an attractive approach to provide various services such as safety and entertainment applications by sharing resources between vehicles. Due to the free mobility of vehicles, vehicular clouds need to reconstruct by replacing leaving member vehicles with new member vehicles. When multiple member vehicles leave a vehicular cloud at different times, the design of an efficient member vehicle replacement scheme is a very challenging issue on determining the replacement timing. However, the research on the replacement of multiple member vehicles has little interest and is still in its infancy. Therefore, we propose three schemes to replace multiple member vehicles in vehicular clouds at three different replacement timings: MIN, MAX, and AVG. The MIN scheme replaces all of leaving member vehicles at the leaving time of the first leaving member vehicle, while the MAX scheme replaces all of leaving member vehicles at the leaving time of the last leaving member. The AVG scheme replaces all leaving member vehicles at the average time of their leaving times as a compromise between the Min and Max schemes. First, we determine the first leaving time, the last leaving time, and the average leaving time for each scheme by calculating the distance between a cloud requester vehicle and its member vehicles. Next, we choose replacement member vehicles to minimize the wasted resource at the replacement timing in each scheme. Last, we provide the process for releasing the resource of the leaving member vehicles and allocating the resource of the replacement member vehicles in each scheme. Through simulation results conducted in various environments, we compare and evaluate the performance of our three schemes in terms of the success ratio of the cloud maintenance and the amount of the wasted resources.

1. Introduction

The wide deployment of wireless communications and vehicular technologies have enabled vehicular ad hoc networks(VANETs) for data delivery between vehicles to support various applications for intelligent transport systems [1,2,3]. In the intelligent transport system, VANETs provide car accident warnings for active safety, highway traffic information for public services, road congestion notices for improved driving, and commercial advertisement for business and entertainment [4]. Recently, VANETs are receiving requests from vehicle users to provide next-generation vehicular applications such as traffic signal optimization, traffic flow control, and autonomous driving [1,5,6]. For supporting the next-generation vehicular applications, the technology of cloud computing is needed in VANETs, and as a result, the concept of vehicular cloud computing has been developed [7,8,9]. A vehicular cloud is defined as a set of vehicles capable of sharing their own resources such as computing, storage, and sensing resources [10]. In VANETs, a vehicle can construct a vehicular cloud by using the collection of vehicles’ resources to enable a vehicular cloud service for a next-generation vehicular application [11].

In the literature, many studies have proposed schemes to construct vehicular clouds by collaborating between vehicles in VANETs [12,13,14,15,16]. They are categorized into two approaches: single-hop and multiple-hop. The single-hop approach is to construct vehicular clouds by single-hop communications between vehicles [12].

It is very simple to construct vehicular clouds but has not enough single-hop neighbor vehicles as candidates to become member vehicles for the vehicular clouds. As a result, it leads to high failures for constructing vehicular clouds. To increase the candidates, the multiple-hop approach uses multiple-hop neighbor vehicles even though it generates very high traffic due to multiple-hop communications to construct vehicular clouds [13,14,15,16].

In spite of these schemes for constructing vehicular clouds, the movement feature of vehicles brings about a challenging issue on the research of the vehicular cloud. Since vehicles move freely on roads according to their own destinations and trajectories, member vehicles in a vehicular cloud leave the cloud before the end of the cloud service, and thus the vehicular cloud can be destroyed. For this reason, it needs to replace the leaving member vehicles with new member vehicles for maintaining the vehicular cloud. Generally, multiple member vehicles might leave a vehicular cloud at their own different leaving times. Thus, the research on member vehicle replacement should be conducted with determining the effective replacement timing.

A great number of studies have been conducted to handle the issue of maintaining network architectures due to the mobility of vehicles in VANETs [17,18,19,20,21,22]. In particular, the research on clustering has proposed schemes to maintain clusters due to the leaving member vehicles by the mobility of vehicles [23]. They only focused on maintaining the network connectivity between member vehicles within a cluster by replacing new member vehicles, but do not consider the replacement of new member vehicles for maintaining resources needed for cloud services. With regards to cloud resources, several studies have dealt with replacing new cloud virtual machines for maintaining clouds of vehicle users due to leaving some cloud virtual machines on Internet clouds or cloudlets [24,25].

So far, only a few studies [1,15,16,26] have been conducted on replacing the leaving member vehicles related with cloud resources for maintaining vehicular clouds, and thus the research is still in its infancy. In [26], the scheme allows a vehicular cloud to have an entry with a lifetime and to manage member vehicles in the cloud. When the lifetime of the entry expires before finishing the cloud service, the vehicular cloud was completely reconstructed by replacing it with new member vehicles. To replace each individual leaving member vehicle in a vehicular cloud, the scheme in [1] uses a new member search process for searching a new member vehicle, and the scheme in [15] provides the way to calculate the leaving time of a leaving member vehicle based on the connection time between vehicles. The scheme in [16] selects a new member vehicle for replacing a leaving member vehicle with the help of a special device called Roadside Unit (RSU), which enables to manage all vehicles in its coverage and their resource information. However, all of the above-mentioned schemes do not consider replacing multiple leaving member vehicles related to their different leaving times.

Therefore, this paper proposes three schemes to address the issue of replacing multiple leaving member vehicles with different leaving times in vehicular clouds. The three schemes are MIN, MAX, and AVG, respectively, and each of them is designed with a different replacement timing. In this paper, we first define each of them in association with its purpose and operation depending on its replacement timing. The MIN scheme replaces all of leaving member vehicles at the leaving time of the first leaving member vehicle, while the MAX scheme replaces all of leaving member vehicles at the leaving time of the last leaving member. The AVG scheme replaces all leaving member vehicles at the average time of their leaving times as a compromise between the Min and Max schemes.

To obtain the replacement timing of each scheme, we determine the first leaving time, the last leaving time, and the average leaving time based on the distance information between a cloud requester vehicle and member vehicles through their position and speed information.

Then, we choose replacement member vehicles to minimize the wasted resource at the replacement timing of each scheme while satisfying the requested resource for maintaining vehicular clouds.

Last, we provide the process for relieving the resource of the leaving member vehicles and allocating the resource of the replacement member vehicles at the replacement timing in each scheme.

Through simulations conducted in various environments, we compare and evaluate the performance of the three schemes in terms of the success ratio of the cloud maintenance and the amount of the wasted resources. Simulation results show that the MIN scheme achieves better performance than the MAX and the AVG schemes for the success ratio of the cloud maintenance, but the MAX scheme achieves better performance than the MIN and the AVG schemes for the amount of the wasted resources because the MIN and the MAX schemes have a trade-off between them. The AVG scheme has moderate performance compared with the other schemes for both the success ratio of the cloud maintenance and the amount of the wasted resources.

The remainder of the paper is organized as follows. We first explain the related works of this paper in Section 2. The problem statement and the network model for the proposed min, max, and average Cloud Member Replacement (CMR) schemes are presented in Section 3. Section 4 describes the proposed min, max, and average CMR schemes in terms of their definition and procedure in detail. Simulation results are provided in Section 4 to evaluate the proposed schemes. Section 5 concludes the paper.

2. Related Works

This section describes the related works for vehicular cloud computing in VANETs. Many studies focus on the construction of a vehicular cloud in vehicular cloud computing. The vehicular cloud construction is classified into two types based on the vehicular communications, V2V and V2I. The V2V communication is that the vehicles communicate themselves without infrastructure. On the contrary, the V2I communication is that the vehicles communicate with infrastructure. We first review the vehicular cloud construction approach using the V2V communication. Next, we review the vehicular cloud construction using V2I communication.

In general, a V2V cloud construction means that a requester vehicle communicates with an adjacent vehicle to retrieve and request their available resources without the support of an external infrastructure (e.g., RSU in this paper). Some studies have been conducted to support V2V cloud construction in VANETs. Meneguette et al. [13] proposed a peer-to-peer protocol to search and manage resources and services in the vehicular mobile cloud without relying on external infrastructure. They focused on vehicles’ mobility, which is the most important role in the scheme. Based on the mobility of vehicles, resource search time, vehicular cloud construction, maintenance, and service time are limited because of vehicles’ mobility and frequent topology changes. This scheme offers an efficient protocol for allowing the availability of resources to the vehicle, increasing the amount of resources that can be consumed in the vehicle cloud. Meneguette et al. [14] has proposed a new protocol for resource management in the vehicular cloud. Managing available resources in vehicles, it promotes cooperation and collaboration among vehicles. It defined a vehicular cloud as a set of vehicles that share their computation resources without external infrastructure for communication support. It is based on the Gnutella protocol and uses the peer-to-peer concept to create overlays over the vehicular network. It offers an efficient scheduling for vehicular Cloud, considering not only the service requirement, but also the characteristics of vehicular networks. Choi et al. [15] proposed a vehicular cloud construction scheme in the multi-hop communication range. It calculates connection times among vehicles and uses a multi-hop connection time-based intermediate vehicle selection scheme to search for multi-hop resources and find vehicles with sufficient resources. It reduces the probability of cloud failure in multi-hop vehicular cloud construction. The resources for the vehicular cloud are allocated according to the connection time between vehicles and the number of adjacent vehicles.

Unlike the V2V cloud construction, the V2I cloud construction means that a requester vehicle communicates with RSUs to search and request the available resources of other vehicles when it enters into the communication range of the RSUs to connect backhaul networks. The RSUs search and request the available resources of vehicles within their own communication range on behalf of the requester vehicle. Mershad et al. [27,28] proposed a novel system that exploits the presence of RSUs to act as cloud directories that store information about mobile cloud servers. The system selects a “STAR” that allows access to multiple services and resources through RSUs. The RSUs share their registration data so that vehicles can search and consume services of mobile cloud servers within a specific area. In addition, the RSU selects the candidate STAR that best suits the user requirements. Because STAR can be closer to the requester than to the RSU, it can provide a higher quality of service (QoS) in high-density networks and speed up communication between the RSU and the cloud. Lin et al. [29] proposed a Semi-Markov decision process (SMDP) model for the vehicular cloud computing (VCC) resource allocation considering the integration of V2V and V2I. This scheme finds the best strategy for VCC resource allocation. The two additional functions are to refine the SMDP model and show different results from the original model. Its resource pool includes the resource units (RUs) provided by the RSU and the amount of RSU of several vehicle types. It also considers different Poisson distributions for heterogeneous vehicle types. Lee et al. [1] proposed a scheme to discover RSU-enabled vehicle resources and construct a cloud in VANETs. The RSU collects information on transportation and resources as well as location information on all vehicles within their range. The RSU selects provider vehicles to provide the resources required to construct the vehicular cloud of the requested vehicle through the collected information. The criteria for determining provider vehicles for providing resources are a connection period between each candidate vehicle and a requester vehicle, the resource size of each candidate vehicle, and its connection starting time with the requester vehicle.

As mentioned earlier, there are many studies for the vehicular cloud construction. However, the vehicular cloud is constructed based on the mobility of vehicles. Thus, if the mobility of vehicles is changed, the vehicular cloud is easily destructed. To increase vehicular cloud service stability, there is an issue of the vehicular cloud reconstruction. The vehicular cloud can be reconstructed through member replacement. The following studies proposed the vehicular cloud reconstruction.

Wang et al. [26] proposed the reconstruction of vehicular cloud in vehicular cloud management. In a vehicular cloud (VC) table, one entry stores one type of content, and the lifetime field is defined to guarantee that the real-time content is provided. That is to say, if the lifetime in one VC entry expires, the VC reconstruction process is triggered to obtain the real-time content identified by the content ID (CID) in the entry. Lee et al. [1] proposed member replacement for cloud maintenance. A member sends a cloud leave message to the leader on its leaving. Then, the leader selects a replacement among nodes that sent Route Replies (RREPs) in the resource discovery phase and have resources enough to complete the assigned task of the leaving member. The leader distributes the task to the new cloud member and updates the cloud table. Choi et al. [15] proposed replacing the leaving vehicles to the new provider vehicle. The requester vehicle needs to replace the existing provider vehicle to the new provider vehicle. The requester vehicle has the information that the number of neighbor vehicles of the provider vehicle. Using this information, the requester vehicle could select the new provider vehicle through the provider vehicle selection scheme and use cloud service without cloud failure.

Lee et al. [16] proposed a replacement solution using the RSU. The RSU can recognize that a member vehicle is out of the expected trajectory through the periodic signal. The RSU recognizing the change of the member vehicle releases the reserved resource of the member vehicle through the release message. Then, the member vehicle selects the new provider vehicle to provide the promised resource and sends a reallocation message to the requester vehicle. This prevents waste of resources reserved by the member vehicle, and it minimizes the cost of re-search for the new provider vehicle. As discussed earlier, several previous studies on V2V and V2I cloud configurations have reconstruction schemes of vehicular clouds for vehicles to handle cloud destruction. In the V2V cloud construction schemes, if the vehicular cloud is destroyed by the leaving member vehicle, the requester vehicle needs to restart the entire vehicular cloud construction process. On the other hand, in the V2I cloud construction schemes, there is no recovery schemes because the requester vehicle can use the resources of the backhaul network whenever it enters the communication range of the RSU.

Therefore, we propose a scheme to quickly maintain a vehicular cloud in the event of its destruction due to leaving of multiple member vehicles and to efficiently replace the leaving members to new member vehicles using RSU’s high computing and communication facilities so that the requester vehicle can continue using cloud services. Our contribution is as follows. First, we propose the three (MIN, MAX, and AVG) CMR schemes to support cloud member replacement and provide explanations, respectively. Next, the proposed CMR schemes replace the leaving member vehicles with locally optimized new member vehicles to quickly reconstruct the vehicle cloud using the RSU’s high computing and communication capabilities. Finally, we analyze the properties of each proposed CMR scheme.

3. Network Model

In this section, we present the network model of our three schemes (the MIN, the MAX, and the AVG schemes) for replacing multiple member vehicles in vehicular clouds. Figure 1 shows an example of the network model for explaining the proposed schemes, and

Table 1. Notation table.

Symbol	Definition
$V_{req}$	The requester vehicle that wants to maintain
	the vehicular cloud
$Se{t}_{req}$	The set of the vehicular cloud member vehicles
	that provide their resources to $V_{req}$ $\{1,\cdots ,n,\cdots ,N\}$
$Se{t}_{leave}$	The set of the vehicular cloud member vehicles that leave the vehicular cloud $\{1,\cdots ,i,\cdots ,M\}$
$Se{t}_{replace}$	The set of the replacement member vehicles that can
	become the new member vehicles of the vehicular cloud
	$\{1,\cdots ,k,\cdots ,K\}$
$V_n^M$	The n-th member vehicle that provides
	its resources to $V_{req}$ in $Se{t}_{req}$
$V_i^L$	The i-th leaving member vehicle that leaves
	the vehicular cloud of $V_{req}$ in $Se{t}_{leave}$
$V_k^R$	The k-th replacement member vehicle that belongs to
	$Se{t}_{replace}$ and becomes the new $V_M$

is the notation table used for helping understand this paper well.

As a network model in this paper, we consider that a great number of vehicles move according to their traveling routes on roads which have intersections. On the periphery of each intersection, an RSU is deployed to provide Internet connections to vehicles within its communication coverage. In the network model, when a request vehicle $V_{req}$ wants to use a vehicular cloud service, it constructs a vehicular cloud with member vehicles $V_n^M$ which enables to provide their resources and has the same traveling route with $V_{req}$. After constructing the vehicular cloud, $V_{req}$ moves on roads with $V_n^M$ together according to the traveling route while using the vehicular cloud service. During moving, the vehicular cloud might meet an intersection as shown in Figure 1a. When the vehicular cloud enters the intersection, some among the member vehicles $V_n^M$ may leave the vehicular cloud due to their different traveling routes from that of $V_{req}$ after the intersection. As a result, the vehicular cloud is destroyed by the leaving member vehicles $V_i^L$. For maintaining the vehicular cloud to continue the vehicular cloud service, $V_{req}$ needs to search $V_k^R$ to replace $V_i^L$ for supplementing the lack of the resource for the vehicular cloud due to the leaving of $V_i^L$.

To search $V_k^R$ to replace $V_i^L$, $V_{req}$ exploits the RSU on the intersection where it currently locates and connects, instead of using a search way of multiple-hop broadcasting. The RSU, which is deployed on the intersection, advertises its existence to every vehicle in its communication range by periodically sending an advertisement message. When a vehicle enters the communication range of the RSU and receives the advertisement message from the RSU, it sends a beacon message with the information of its ID, location, speed, moving direction, traveling route, and resources to the RSU periodically. Thus, the RSU can opportunistically help to search $V_k^R$ to replace $V_i^L$ for $V_{req}$, because it manages the information of all vehicles in its own communication range.

When $V_{req}$ reaches the intersection and enters the communication coverage of the RSU on the intersection, it sends a Request message with the mobility (position, velocity, and traveling route) information and the resource information of itself and $V_n^M$ to the RSU to search $V_k^R$ as shown in Figure 1a.

On receiving the Request message, the RSU determines leaving member vehicles $V_i^L$ for $V_{req}$ as shown in Figure 1b. $V_i^L$ is calculated with the mobility information of both $V_i^L$ and $V_n^M$ included in the Request message. Then, the RSU discriminates the order (that is, the first leaving member vehicle, the second leaving member vehicle, …, the ith leaving member vehicle, …, and the last leaving member vehicle) of $V_i^L$. After determining $V_i^L$, the RSU calculates the lack amount of the resource due to leaving of $V_i^L$ from the vehicular cloud.

Then, among all vehicles in the communication coverage of the RSU, it chooses $V_k^R$ for replacing $V_i^L$ and minimizing the wasted amount of the resource through using the mobility and the resource information of $V_{req}$, $V_i^L$, and all vehicles and sends a Select message with the replacement timing and the requested resource amount to each of $V_k^R$ for requesting its resource to become as new member vehicle as shown in Figure 1c.

At the replacement timing, $V_{req}$ releases all of $V_i^L$ from the vehicular cloud, and each of $V_k^R$ becomes a new member vehicle by sending a Join message to $V_{req}$ and allocating its resource for the vehicular cloud as shown in Figure 1d.

As a result, $V_{req}$ enables us to maintain the vehicular cloud by having $V_k^R$ for replacing $V_i^L$ and uses the vehicular cloud service continuously. Figure 2 shows the common flow chart of the proposed schemes.

As mentioned in the network model, this paper considers the replacement timing to replace all leaving member vehicles with new member vehicles integrally. The selection of the replacement timing is one of the important factors to affect the performance of a scheme for replacing all leaving member vehicles in terms of both the success ratio of the cloud maintenance and the amount of the wasted resources. Thus, this paper proposes three schemes named as the MIN scheme, the MAX scheme, and the AVG scheme which select their own replacement timing differently. We present our three schemes individually in Section 4.

4. The Proposed Schemes: MIN, MAX, and AVG

In this section, we describe our three schemes: MIN, MAX, and AVG in detail. They are distinguished by depending on their own replacement timing to replace the leaving member vehicles with new member vehicles. For the replacement timing, the MIN scheme uses the time when the first leaving member vehicle leaves the vehicular cloud. On the contrary, the MAX scheme uses the replacement timing as the time when the last leaving member vehicle leaves the vehicular cloud. For a compromise between the MIN and the MAX schemes, the AVG scheme uses the average leaving time of all leaving member vehicles as the replacement timing. We explain each of our three schemes in the next subsections, respectively.

4.1. The MIN Scheme

After a vehicular cloud enters the communication range of an RSU, then multiple member vehicles leave the vehicular cloud because their traveling route might be different from that of the requester vehicle for the vehicular cloud. In this situation, the MIN scheme replaces all of the leaving member vehicles with new member vehicles when the first leaving member vehicle leaves the vehicular cloud. With regard to the operation for replacing multiple leaving member vehicles, since the MIN scheme performs the replacement of all leaving member vehicles in advance, it can achieve high cloud service reliability. On the other hand, because the replacement member vehicles have been assigned to the vehicular cloud for providing their resources in advance, their available resources remain in the vehicular cloud for a longer period of time. When the available resources of the replacement member vehicles are larger than the requested resource for replacing the leaving member vehicles in the vehicular cloud, the remaining resources are generated. Then, the remaining resources cannot be used for other vehicular clouds, because they belong to the vehicular cloud already. As a result, the remaining resources are wasted.

In this section, we describe the MIN scheme by using two subsections. First, the MIN scheme needs to predetermine all of the leaving member vehicles and their individual leaving times. With the leaving times of the leaving member vehicles, it selects the first leaving member vehicle and decides the leaving time of the first leaving member vehicle as the replacement timing. Thus, we explain the determination of the leaving member vehicles and the replacement timing in Section 4.1.1. Next, to maintain the vehicular cloud, the MIN scheme needs to choose new member vehicles to replace the leaving member vehicles at the replacement timing. When selecting the new member vehicles, their wasted resources are minimized while guaranteeing the requested resources for maintaining the vehicular cloud. Thus, we explain the selection of the replacement member vehicle by minimizing the wasted resources in Section 4.1.2.

4.1.1. Determination of the Leaving Member Vehicles and the Replacement Timing

The MIN scheme needs to select a replacement timing to replace multiple leaving member vehicles with new member vehicles. As the replacement timing, the MIN scheme uses the time when the first leaving member vehicle leaves the vehicular cloud. Thus, it needs to determine which member vehicle leaves first and when it leaves the vehicular cloud. To do this, when a requester vehicle $V_{req}$ enters the communication range of an RSU, it sends a Request message with the mobility (position, velocity, and traveling route) information and the resource information of itself and its member vehicles $V_n^M$ to the RSU. On receiving the request message, the RSU estimates the position $p_i\left(t\right)$ of each member vehicle $V_i^M$ after t seconds from the time when $V_{req}$ sends the Request message to the RSU. Then, $p_i\left(t\right)$ can be calculated with the mobility information of $V_i^M$ as follows,

$$p_i\left(t\right)=p_i\left(0\right)+{\int }_{}^t{v}_i^M\left(t\right)dt,$$

(1)

where $p_i\left(0\right)$ is the position of $V_i^M$ at the time when $V_{req}$ sends the request message, and $v_i^M\left(t\right)$ is the velocity of $V_i^M$ at the time t, respectively. Accordingly, the RSU can calculate the leaving time $t_{leave}^i$ of each member vehicle $v_i^M\left(t\right)$ by using the distance between the position $p_{req}\left(t\right)$ of $V_{req}$ after t seconds and the position $p_i\left(t\right)$ of $V_i^M$ after t seconds as follows:

$$dist(p_{req}\left(t_{leave}^i\right),p_i\left(t_{leave}^i\right))\le r,$$

(2)

where r is the communication range of V2V for communicating between vehicles. By Equation (2), the RSU can determine all of the leaving member vehicles, which cannot connect with $V_{req}$ via single-hop V2V communications. Then, the RSU makes all of the leaving member vehicles as a set $Se{t}_{leave}$. Next, by using $t_{leave}^i$ of each leaving member vehicle, the RSU can calculate the order of the time that every leaving member vehicle leaves the vehicular cloud. Then, the leaving member vehicle with the smallest $t_{leave}^i$ becomes the element $V_1^L$ of the set $Se{t}_{leave}$ as the first leaving member vehicle. On the other hand, the leaving member vehicle with the biggest $t_{leave}^i$ becomes the element $V_N^L$ of the set $Se{t}_{leave}$ as the last leaving member vehicle. Thus, the MIN scheme uses the leaving time $t_{leave}^1$ of the element $V_1^L$ in the set $Se{t}_{leave}$ as the replacement timing.

At the replacement timing $t_{leave}^1$, the MIN scheme releases the resources of all leaving member vehicles and allocates the resources of all the replacement member vehicles. To maintain the vehicular cloud completely, the sum of the resources of the replacement member vehicles should be larger than those of the leaving member vehicles during the requested service time $t_{req}$ for the vehicular cloud. Thus, the RSU needs to calculate the sum of the resources of all leaving member vehicles at $t_{leave}^1$. To do this, with the resource information of $V_i^M$ included in the request message from $V_{req}$, the RSU gets the used resource ${res}_{used}^i$ of each leaving member vehicle $V_i^M$ allocated for the vehicular cloud. Since every leaving member vehicle $V_i^M$ actually releases its used resource ${res}_{used}^i$ after $t_{leave}^1$, ${res}_{used}^i$ should be allocated by replacement member vehicles during a replacement request time $t_{req}-t_{leave}^1$ for maintaining the vehicular cloud. Thus, the total amount ${res}_{leave}$ by all leaving member vehicles in ${Set}_{leave}$ can be obtained as follows.

$${res}_{leave}=\sum _{i\in {Set}_{leave}}(t_{req}-t_{leave}^i)\times {res}_{used}^i$$

(3)

4.1.2. Selection of the Replacement Member Vehicles

With the replacement timing as the leaving time $t_{leave}^1$ of the first leaving member vehicle $V_1^L$, the RSU needs to choose new member vehicles to replace all of the leaving member vehicles. To do this, the RSU finds out replacement member vehicles to replace ${res}_{leave}$ by all the leaving member vehicles. Since the replacement member vehicles should participate in the vehicular cloud at the replacement timing $t_{leave}^1$, the RSU needs to choose candidate vehicles to become replacement member vehicles among vehicles in its communication range at $t_{leave}^1$. To become a candidate replacement member vehicle, a vehicle can connect with $V_{req}$ and have the same moving direction with $V_{req}$ from the intersection at $t_{leave}^1$ and should maintain the connection and the moving direction during the replacement request time $t_{req}-t_{leave}^1$.

The position of the vehicle at $t_{leave}^1$ can be calculated with its mobility information by using Equation (1). The RSU judges whether the vehicle can connect with $V_{req}$ at $t_{leave}^1$ or not by using the position information of the vehicle and $V_{req}$. It also judges whether the vehicle can have the same moving direction with $V_{req}$ or not by using the traveling route information of the vehicle and $V_{req}$. Accordingly, it can choose every candidate replacement member vehicle $V_k^R$ for maintaining the vehicular cloud. Then, it forms all possible combination sets by using $V_k^R$.

They are ${Set}_{replace}^1=\left\{r_1\right\}$,…, ${Set}_{replace}^j=\{r_1,\cdots ,r_k,\cdots \}$, …, and ${Set}_{replace}^J=\{r_1,\cdots ,r_K\}$. Since the available resources of the candidate replacement member vehicles are based on $t_{req}$ and $t_{leave}^1$, the amount ${res}_{replace}^j$ of the replaced resources can be calculated according to the j-th combination set ${Set}_{replace}^j$ of the candidate replacement vehicles as follows:

$${res}_{replace}^j=(t_{req}-t_{leave}^1)\times \sum _{k\in {Set}_{replace}^j}{res}_{avail}^k,$$

(4)

where ${res}_{avail}^k$ is the amount of the available resources of the k-th the candidate replacement member vehicle. Thus, among the all possible combination sets of $V_k^R$, ${Set}_{replace}^j$ which is $({res}_{req}-{res}_{leave}+{res}_{replace}^j)\ge {res}_{req}$ is obtained as a candidate replacement set. As ${res}_{replace}^j$ is larger than $re{s}_{leave}$, the difference of ${res}_{replace}^j$ and $re{s}_{leave}$ cannot be used for other vehicular clouds, because ${res}_{replace}^j$ is allocated to the vehicular cloud for cloud maintenance. As a result, the difference becomes the wasted resources. Moreover, if the difference increases, the wasted resources increase. In order to minimize the wasted resources, the RSU selects ${Set}_{replace}^j$ having the smallest difference (that is, ${res}_{replace}^j-{res}_{leave}$) as the replacement member vehicle set ${Set}_{replace}$, and the resources provided by ${Set}_{replace}$ becomes ${res}_{replace}$.

After selecting the replacement vehicle set ${Set}_{replace}$, the RSU sends a select message with the replacement timing $t_{leave}^1$ and the allocated resource amount to each of $V_k^R$ in ${Set}_{replace}$. Additionally, it sends a release message with the replacement timing $t_{leave}^1$ to each of $V_i^L$ in $Se{t}_{leave}$ in order to allow $V_i^L$ to release the resource of $V_i^L$ at $t_{leave}^1$. If it is the replacement timing $t_{leave}^1$, each $V_i^L$ releases its resource and leaves the vehicular cloud. On the other hand, each $V_k^R$ sends a Join message to $V_{req}$ and becomes a new member vehicle for the vehicular cloud. At $t_{leave}^1$, since $V_i^L$ are replaced with $V_k^R$ and ${res}_{replace}$ of $V_k^R$ is larger than ${res}_{leave}$ of $V_i^L$, the vehicular cloud is maintained without destructing.

In the existing schemes different from the MIN scheme, a vehicular cloud is destructed whenever any leaving member vehicle leaves. The destructed vehicular cloud is reconstructed as a new vehicular cloud by re-requesting available resources from neighboring vehicles. However, this way to reconstruct a vehicular cloud causes an increase in delay and network overhead. On the other hand, in the MIN scheme, a vehicular cloud is maintained at a replacement timing that is predetermined by predicting the destruction of the vehicular cloud. Thus, the MIN scheme reduces delays and network loads by maintaining the vehicular cloud efficiently and can provide stable services of the vehicular cloud.

4.2. The MAX Scheme

The MAX scheme replaces the vehicular cloud member vehicles at the time that the last leaving member vehicle leaves after the vehicular cloud enters the communication range of the RSU. In the same way as the MIN scheme, the vehicular cloud is destructed when the first leaving member vehicle leaves. From the time when the first leaving member vehicle leaves the vehicular cloud, multiple member vehicles may leave until the time when the last leaving member vehicle leaves the vehicular cloud. However, the MAX scheme replaces $V_i^L$ to $V_k^R$ at the replacement timing after the last leaving member vehicle leaves the communication of $V_{r}eq$. Since the vehicular cloud is reconstructed after the last leaving member vehicle leaves, more replacement member vehicles are required for the additional requested resources. Thus, the vehicular cloud service reliability is lower than that of the MIN scheme. However, since there are no pre-allocated resources, the few remaining resources are wasted more than those of the MIN scheme.

In this section, we describe the MAX scheme by using two subsections. First, the MAX scheme needs to determine the last leaving member vehicle and its leaving time. With the leaving time of the last leaving member vehicle, it selects the last leaving member vehicle and decides the leaving time of the last leaving member vehicle as the replacement timing. Thus, we explain the determination of the last leaving member vehicle and the replacement timing in Section 4.2.1. Next, to maintain the vehicular cloud, the MAX scheme needs to choose new member vehicles to replace the leaving member vehicles at the replacement timing. When selecting the new member vehicles, their wasted resources are minimized while guaranteeing the requested resources for maintaining the vehicular cloud. Thus, we explain the selection of the replacement member vehicle with minimizing the wasted resources in Section 4.2.2.

4.2.1. Determination of the Leaving Member Vehicles and the Replacement Timing

The MAX scheme replaces the vehicular cloud at the time $t_{leave}^N$ that the last leaving member vehicle N leaves. The vehicular cloud is destructed at the time $t_{leave}^1$ when the first leaving member vehicle leaves so that the service is not continued. We define a set of all member vehicles of the vehicular cloud as ${Set}_{req}$. To get the requested resources ${res}_{req}$ and time $t_{req}$, $V_{r}eq$ additionally replaces the resources of $V_i^L$ to that of $V_k^C$ due to the destruction of the vehicular cloud at $t_{leave}^N$. For this reason, the amount ${res}_{leave}$ of the resources that are required for replacement is calculated as follows:

$$\begin{array}{cc}\hfill {res}_{leave}=& \sum _{n\in {Set}_{req}}(t_{leave}^N-t_{leave}^1)\times {res}_{req}\hfill \\ \hfill & +\sum _{i\in {Set}_{leave}}(t_{req}-t_{leave}^N)\times {res}_{used}^i.\hfill \end{array}$$

(5)

4.2.2. Selection of the Replacement Member Vehicles

The MAX scheme reconstructs the vehicular cloud after the last leaving member vehicle leaves. Since the MAX scheme does not have a replacement member vehicle from the time $t_{leave}^1$ to the time $t_{leave}^N$, the vehicular cloud remains destructed. Therefore, ${res}_{replace}^j$, which is the amount of the resources that can be provided at the time $t_{leave}^N$ by a replacement candidate set ${Set}_{replace}^j$ satisfying $({res}_{req}-{res}_{leave}+{res}_{replace}^j)\ge {res}_{req}$, can be calculated as follows:

$${res}_{replace}^j=(t_{req}-t_{leave}^N)\times \sum _{k\in {Set}_{replace}^j}{res}_{avail}^k$$

(6)

In this scheme, since the replacement member vehicles do not allocate their available resources to the vehicular cloud in advance, only the resources are wasted except the used resources ${res}_{used}^i$ among the available resources ${res}_{avail}^i$ of each vehicle i. In the case of the MIN scheme, since the replacement member vehicles are allocated at the time $t_{leave}^1$ in advance, the replacement member vehicles cannot use all of their available resources until all leaving member vehicles leave the vehicular cloud, and their available resources ${res}_{avail}^i$ become wasted resources. Thus, the MAX scheme is more optimized for saving wasted resources.

However, more vehicles are required because more resources should be provided at the replacement timing $t_{leave}^N$. If multiple $V_{r}eq$ request resources at once, the probability that the requested resources may not be satisfied is increased. This is directly related to the reliability of the service because it can lead to failure in cloud service delivery.

4.3. The AVG Scheme

The AVG scheme is a compromise between the MIN scheme and the MAX scheme. The AVG scheme replaces the vehicular cloud member vehicles at the average time of the leaving time of each leaving member vehicle. The vehicular cloud is destructed from the time of the first leaving member vehicle leaves the vehicular cloud to the time that the average leaving time of each leaving member vehicle. However, since the additional requested resources are smaller than the MAX scheme, the cloud service reliability is higher than that of the MAX scheme. On the other hand, since the replacement members are not assigned too early, the wasted resources are lower than that of the MIN scheme.

In this section, we describe the AVG scheme by using two subsections. Aforementioned, the AVG scheme replaces the leaving member vehicles to the new member vehicles at the compromise of the MIN scheme and MAX scheme. First, we explain the determination of the leaving member vehicles and the replacement timing in Section 4.3.1. Next, we explain the selection of the replacement member vehicle with minimizing the wasted resources in Section 4.3.2.

4.3.1. Determination of the Leaving Member Vehicles and the Replacement Timing

The AVG scheme is a compromise between the MAX scheme and the MIN scheme. The AVG scheme replaces the vehicular cloud at the average time $t_{leave}^{av}$ of the replacement timing of the MIN scheme and the MAX scheme. At the time $t_{leave}^1$ when the first leaving member vehicle leaves the vehicular cloud, the vehicular cloud is destructed. The resources that are required to reconstruct the vehicular cloud at the time $t_{leave}^{av}$ are obtained in the same way as the MAX scheme. Since the duration time when the vehicular cloud is destructed is from the time $t_{leave}^1$ to the time $t_{leave}^{av}$, not the duration time from the time $t_{leave}^1$ to the time $t_{leave}^N$, the required resources ${res}_{leave}$ for the replacement are obtained as follows:

$$\begin{array}{cc}\hfill {res}_{leave}=& \sum _{n\in {Set}_{req}}(t_{leave}^{av}-t_{leave}^1)\times {res}_{req}\hfill \\ \hfill & +\sum _{i\in {Set}_{leave}}(t_{req}-t_{leave}^N)\times {res}_{used}^i\hfill \end{array}$$

(7)

4.3.2. Selection of the Replacement Member Vehicles

The AVG scheme does not have the replacement member vehicles at the duration time from the time $t_{leave}^1$ to the time $t_{leave}^{av}$. At the time $t_{leave}^{av}$, $V_{r}eq$ requests the vehicular cloud participation from the existing member vehicles and the replacement member vehicles. Existing member vehicles, except for the vehicles that cannot communicate due to the distance from the requested vehicle at the time $t_{leave}^{av}$, participate in the vehicular cloud again. Thereafter, the leaving member vehicles that leave the vehicular cloud inform to $V_{r}eq$.

Since this scheme prepares the replacement member vehicles at a later time than the MIN scheme, there are relatively few wasted resources that are allocated in advance. In addition, since the leaving member vehicles are replaced at an earlier time than the MAX scheme, there are relatively few resources required for the replacement. Therefore, because a lower number of the replacement member vehicles is needed, the reconstruction success ratio of this scheme is higher than that of the MAX scheme.

5. Performance Evaluation

In this section, we evaluate the performance of our three schemes, the MIN, the MAX, and the AVG schemes through simulations. We first present the environments for our simulations in Section 5.1. The performance of our three schemes is explained through simulation results in Section 5.2.

5.1. Simulation Environments

In this section, we compare the performance of three CMR schemes using NS-3 [30]. To evaluate the performance of three CMR schemes, we compare the variation of the cloud reconstruction success ratio and the size of the wasted resources based on the ratio of the leaving member vehicles in a vehicular cloud, the size of the requested resources, and the number of vehicles.

The ratio of the leaving member vehicles in a vehicular cloud is the ratio of vehicles whose distance from the requester vehicle is longer than the V2V communication range within the RSU communication range. Therefore, the high ratio indicates that the vehicular cloud is more frequently destructed and that more replacement resources are required.

The size of the requested resources is the resources that are required by the requester vehicle. The bigger size of the requested resources denotes that more vehicles are required as vehicular cloud members. Since more vehicles belong to the vehicular cloud, more replacement resources are required if the ratio of the leaving member vehicles is the same.

The number of vehicles denotes the density of the vehicles on the road because the network size is fixed. The cloud reconstruction success ratio indicates the ratio of the successfully reconstructed vehicular clouds among the destructed vehicular clouds. The ratio is the ratio of the reconstructed vehicular cloud among the vehicular clouds that destructed due to the greater requested resources than the available resources of the cloud member vehicles.

The wasted resources denote that the size of the resources among the available resources of the cloud member vehicle that have already been allocated to the vehicular cloud and cannot be used.

Table 2. Simulation parameters table.

Parameters	Value
Network size	2 km2
Mobility model	Manhattan Mobility Model [31,32,33]
Number of lanes	2
RSU transmission range	800 m
Vehicle transmission range	190 m
Distance between RSUs	2 km
Number of vehicles	50/km2
Average speed of vehicles	40 km/h
Resource type	Bandwidth (Mbps)
Communication Protocol	802.11p

shows the parameters for our simulations. Each simulation result was conducted over 1000 times with a 95% Confidence Interval (CI).

To evaluate the proposed schemes, we simulate requests for vehicular resource cloud service in the Manhattan scenario [31,32,33] using NS-3. We consider four lane in the Manhattan scenario. RSUs are placed at each intersection in the simulation scenario area (2 km × 2 km). All nodes, including RSUs and vehicles, can communicate with each other using 802.11p (WAVE) with a maximum vehicle transmission range of 190 m, a maximum RSU transmission range of 800 m and a maximum radio transmission rate of 54 Mbps. RSUs are connected to the backbone and to each other by fibers and have a maximum transmission rate of 10 Gbps and 10 TB of storage. The density of vehicles is 50 km⁻². The average speed of vehicles will be varied between 20 km/h and 60 km/h. The amount of change in speed is set to 20% of the average speed.

5.2. Simulation Results

Figure 3 shows the success ratio of the cloud reconstruction according to the variation in the vehicle density. When the vehicle density is concentrated, the probability of having a better replacement candidate vehicle increases, and thus the success ratio of the cloud reconstruction increases. In the case of the MAX scheme, a large number of replacement candidate vehicles are required because the required replacement resources are relatively large. Therefore, although the density of vehicles increases, it has the lowest success ratio than the others. In the case of the MIN scheme, since the replacement resources that are required to reconstruct the vehicular cloud are the smallest, a small number of replacement candidate vehicles is required. In other words, it has a number of candidate vehicles and quickly replaces the leaving member vehicle as a new member vehicle. Therefore, it has the highest success ratio. The AVG scheme showed 94.7% performance on the success rate of the MIN scheme as a compromise between the two schemes.

Figure 4 shows the wasted resources according to the variation in the vehicle density. The MIN scheme, which has the most resources for pre-allocated replacement candidate vehicles, wastes the most resources. Until the vehicular cloud is reconstructed, the resources of pre-allocated replacement candidate vehicles can not be used. Thus, it has the largest wasted resources. On the other hand, in the MAX scheme, the vehicular cloud is destroyed after the last leaving member vehicle leaves the vehicular cloud. Since the MAX scheme does not have a pre-allocated replacement candidate vehicle until the vehicular cloud is reconstructed, the least resources are wasted. The AVG scheme has a high success ratio despite 15.4% savings in wasted resources than the MIN scheme.

Figure 5 shows the success ratio of cloud reconstruction according to the size of the requested resources. If the required resource is large, more replacement candidate vehicles are required, so the success ratio of the vehicular cloud reconstruction is reduced. The MAX scheme, which requires the most replacement candidates, has the lowest success ratio. The MIN scheme has the highest success ratio because it requires the fewest replacement candidate vehicles. The AVG scheme has an average success rate of 85.6% compared to the MIN scheme.

Figure 6 shows the wasted resources according to the size of the requested resources. When the required resource is large, a larger number of member vehicles are required to construct a vehicular cloud. Accordingly, since the number of the leaving member vehicles in the vehicular cloud also increases, more replacement resources are required. When the replacement resources are large, more unused wasted resources of the candidate vehicle increase because more replacement candidate vehicles are required. In the case of the MIN scheme, since there are many candidate vehicles allocated in advance, almost resources are wasted. In the case of the MAX scheme, since there are no candidate vehicles allocated in advance, only unused resources among the resources of the allocated replacement vehicles cannot be provided to other vehicles, which are wasted. The AVG scheme saves more wasted resources than the MIN scheme while maintaining a higher success ratio than the MAX scheme.

Figure 7 shows the success ratio of the vehicular cloud reconstruction according to the percentage of the leaving member vehicles. When the percentage of the leaving vehicle is low, the performance of the three schemes is the same because the member vehicle does not leave the vehicular cloud or only one member vehicle leaves the vehicular cloud. When two or more member vehicles leave, the replacement timing varies, so there is a difference in the performance of the three schemes. When there are many leaving vehicles in the vehicular cloud, the MAX scheme may lack the number of replacement candidate vehicles because it requires huge resources at the time of replacement. Therefore, it has the lowest success ratio compared to the other two schemes. However, since there is no pre-allocated replacement candidate vehicle, the most resources may be saved. Since the MIN scheme has the largest number of pre-allocated replacement candidate vehicles, it has the highest success ratio compared to the two schemes, although there are the most wasted resources. The AVG scheme is a compromise between the two other schemes and has moderate performance for the two schemes.

Figure 8 shows the wasted resources according to the percentage of the leaving member vehicles. When the percentage of the leaving vehicle is low, the performance of the three schemes is the same because the member vehicle does not leave the vehicular cloud or only one member vehicle leaves the vehicular cloud. When there are many leaving vehicles in the vehicular cloud, the MAX scheme reconstructs the vehicular cloud later than the others. Until the vehicular cloud is reconstructed, the resources of replacement candidate vehicles are not allocated. In other words, since there is no pre-allocated replacement candidate vehicle, almost resources may not be wasted. On the other hand, the MIN scheme has the largest number of pre-allocated replacement candidate vehicles, and it has the highest wasted resources because the resources of pre-allocated replacement candidate vehicles are wasted until the vehicular cloud is reconstructed. The AVG scheme has moderate performance for the two schemes.

6. Conclusions

Vehicular cloud is considered an attractive approach in vehicular ad hoc networks. The vehicular cloud is a set of vehicles that cooperate using resources to create value-added services such as safety and entertainment applications. To this end, numerous studies have proposed to construct a vehicular cloud consisting of vehicles. However, since vehicles move freely, the multiple member vehicles in the vehicular cloud may leave the cloud before the cloud service is terminated, and the vehicular cloud may be destructed. Therefore, in order to maintain the vehicular cloud, it is necessary to replace the multiple leaving member vehicles with new member vehicles. Therefore, we propose three schemes based on the replacement timing: the MIN, MAX, and AVG schemes for maintaining the vehicular cloud.

First, we derive the replacement timing for each of the MIN, MAX, and AVG schemes and select the optimal replacement member vehicles at the replacement timing in each scheme through our numerical model. Next, we describe each of them on its operation and analyze its properties to support cloud member replacement, respectively. Finally, we evaluate the performance of the three schemes through simulations performed in various environments. Simulation results show that there is a performance trade-off between the MIN and MAX schemes in both aspects of the success ratio of the cloud reconstruction and the wasted resources. On the other hand, the AVG scheme has an approximately middle performance between the MIN and MAX schemes.

In the future work, we need to subdivide the timing to calculate the optimal reconstruction timing and increase service reliability based on various applications because each leaving member vehicle leaves the vehicular cloud at different timing. The optimization in VANETs requires high computational capability and lots of information exchange due to the vehicles’ mobility. Thus, we need to propose an optimal vehicular reconstruction scheme based on the Machine Learning in the future work.