# A Safety Resource Allocation Mechanism against Connection Fault for Vehicular Cloud Computing

Authors: Tianpeng Ye; Zhou Su; Jun Wu; Longhua Guo; Jianhua Li; Gaolei Li
Journal: Mobile Information Systems
 (2016)

---

## Abstract

The Intelligent Transportation System (ITS) becomes an important component of the smart city toward safer roads, better traffic control, and on-demand service by utilizing and processing the information collected from sensors of vehicles and road side infrastructure. In ITS, Vehicular Cloud Computing (VCC) is a novel technology balancing the requirement of complex services and the limited capability of on-board computers. However, the behaviors of the vehicles in VCC are dynamic, random, and complex. Thus, one of the key safety issues is the frequent disconnections between the vehicle and the Vehicular Cloud (VC) when this vehicle is computing for a service. More important, the connection fault will disturb seriously the normal services of VCC and impact the safety works of the transportation. In this paper, a safety resource allocation mechanism is proposed against connection fault in VCC by using a modified workflow with prediction capability. We firstly propose the probability model for the vehicle movement which satisfies the high dynamics and real-time requirements of VCC. And then we propose a Prediction-based Reliability Maximization Algorithm (PRMA) to realize the safety resource allocation for VCC. The evaluation shows that our mechanism can improve the reliability and guarantee the real-time performance of the VCC.


---

## Body

## 1. Introduction

Smart city has become a critical way for sustainable urban development [1], which is composed of the smart sensor networks, Internet of Things, social network, and so forth [2–5]. The Intelligent Transportation System (ITS) is instrumental for making the road traffic in smart city safer, more efficient, and more convenient [6]. As the core component of ITS, Vehicular Ad Hoc Network (VANET) can improve the efficiency of the information exchange in road traffic. VANET is a network that vehicles can share the on-road information such as the car crush or the traffic jam on the road ahead. There are two types of communicating mechanism for vehicles to exchange their information in VANET: vehicle-to-vehicle (V2V) where vehicles communicate via on-board radio device directly and vehicle-to-infrastructure (V2I) where vehicles communicate with each other by existing infrastructure on road side. The equipment beside the road is called RSUs (Road Side Units) [7]. The ITS plays an important role in the area of road safety with utilizing the transportation data collected by VANET. Based on these transportation data, more and more complex applications have been implemented into the vehicles to complement the ITS. In this process, the “brain” of vehicle becomes more and more “smart” as the result of the force of applications’ requirements. Some vehicles have sufficient computation and storage resources and these resources are in idle in many conditions. On the contrary, the on-board computers of some vehicles have too limited computing or storage resources to execute the service. In order to solve the imbalance of computational capability in time and space, Vehicular Cloud Computing (VCC) is proposed on the basis of VANET in last several years [8, 9]. As we all know, cloud computing is a technology that provides flexibility to the provision of computing resources by virtualizing all the distributed computing devices as a resource pool in a data center [10]. As further exploitation, VCC coordinates the computing, communication, sensing, and storage resources of the vehicles on the road to balance the requirement of services and the limitation of hardware. In other words, aforementioned resources of the vehicles constitute the cloud resources pool.According to the difference between the functions of the resources, services of VCC can be divided into four types, that is, “Computation-as-a-Service,” “Network-as-a-Service,” “Storage-as-a-Service,” and “Sensing-as-a-Service” [11]. The most important difference between VCC and traditional cloud computing is that the dynamic of resource pool in VCC depends on the mobility of the vehicles. The mobility of vehicles decreases the reliability and availability of the VCC. As a matter of fact, the movement behaviors of vehicles are uncertain. In other words, a vehicle may connect or disconnect the vehicular cloud dynamically based on the complex transportation environments. A service provided to the vehicle can be discomposed into a series of tasks. Some of them required the execution results of other tasks to begin their own tasks. Therefore, there is an execution order in these tasks which is called as task sequence. If a task has been allocated to a vehicle in the Vehicular Cloud (VC), the task will be failure because of the connection fault between this vehicle and the VC. Moreover, the further task sequence which depends on failure task will be interrupted, and related services in ITS will be stopped. It is opposite with the initial goal of using VCC in ITS, which is making the road traffic safer. In traditional cloud computing systems, a lot of fault-tolerance approaches have been proposed to deal with the common node with random failures, such as the work in [12]. The authors established a real-time workflow fault-tolerant model for cloud computing and proposed a fault-tolerant scheduling algorithm which uses primary-backup model. However, these schemes cannot be applied in the vehicles of the traffic system, which have portable predictability behaviors and require high real-time services. Most of them use the backup scheme and recompute the tasks if they cause fault. The computation will introduce additional time overhead and lead to the time delay of the service execution. Thus, these existing works cannot be used directly for the VCC services with real-time requirements. One of the key safety issues in the VCC is the frequent connection faults between the vehicle and the VC when this vehicle is executing the cloud services of ITS.To address above challenges, this paper proposes a safety resource allocation mechanism against connection fault in VCC by using a modified workflow with prediction capability. The proposed mechanism includes two phases. First, the connection fault probability model of the moving vehicles in VC is proposed. Second, a safety resource allocation algorithm, PRMA, is proposed according to the connection fault probability of the vehicle. Based on the outputs of the connection fault probability model, the safety resource allocation algorithm is to maximize the reliability of the VCC under the constraint of the service execution deadline.The rest of this paper is organized as follows. Section2 presents the background knowledge and related literature survey about the topic. Section 3 provides the models of the VCC and the probability models of vehicle connection fault. The formulations of connection fault in VCC are described in Section 4. Section 5 presents the safety resources allocation workflow schedule for VCC. In Section 6, the simulations are implemented to demonstrate the efficiency of the proposed mechanisms. The conclusion and future work are shown in Section 7 at last.


## 2. Related Works

The concept of VCC has been proposed for several years. Eltoweissy et al. and Olariu et al. introduced the concept of the VC that leveraged the spare resource of the vehicles [8, 9]. In their papers, the scenario is that the vehicles can access a wireless network for long times; that is, the vehicles are parked or stuck in a traffic jam and move slowly. The work in [13] solved the problem that the low density of vehicles in some roads cannot be sufficient for the physical resources requirement of ITS by utilizing parked cars as relay nodes. In addition, the work in [14] proposed the Parked Vehicle Assistance (PVA) to make parked vehicles join the VANET. After that, Hussain et al. [15] first proposed the VENAT cloud architecture which was classified into three different architectural frameworks, VC, vehicles using cloud (VuC), and hybrid vehicular clouds (HVC).With the steady basis of the theory system, many applications and optimization of the VCC are proposed. The first direction of the research is that focusing on the security and privacy of the VCC. Yan et al. [16] analyzed the security and privacy challenges of VCC. It is the first paper that pays attention to dealing with secure problems in VCC. After that, some security threats were concluded by several papers [17–19]. Thus this direction is a popular research point.The second one is the efficiency of resources allocation in the VCC. The resource allocation is a traditional issue in the cloud [20]. It can improve the capability and efficiency of the VCC by optimizing the allocation strategy. All of them can be divided into several phases. The basic one is toward the VCC combining with the traditional cloud. The computing resources are in the traditional data center to be provided to the vehicles. A game-theoretical resource allocation approach was presented for central cloud resources [21]. The further one is the cloud composed of on-board computers of the vehicles. Zheng et al. proposed an SMDP-based resource allocation in VCC to maximize the total long-term reward [22].The last one is researches on the dependability and reliability of computing resources in VCC systems. The unpredictable availability of the computational resource of the distributed vehicles has been studied in [23–26]. However, the emphasis of these researches is the variation of the vehicles in the parking lot and ignored the application scenario that the mobility of the vehicles leads to more connection faults and safety risks in VCC.


## 3. Basic Models

### 3.1. The Architecture of VCC

Generally, there are two difference architectures to construct the VCC. Although some new content delivery mechanisms were proposed [27, 28], the typical V2V and V2I communication mechanisms which are the most popular in the realistic traffic environment are considered in our paper. As shown in Figure 1, the underlayer components are vehicles on the road. The vehicles share their resources such as computing capability, communicating bandwidth, and storage space with each other by the direct V2V communication. In our paper, this orientation model of cloud is called the V2V cloud. The advantage of this architecture is the low delay time of communication. However, due to the limited communication range of the vehicular radio, the scale of the cloud is often too small to complete some complex services such as managing evacuation when the density of vehicles is not sufficient in the range of the vehicular radio.Figure 1
The architecture of VCC.In order to address the limitation of this basic architecture, the RSUs are used to provide long-distance transmission for vehicles in different places. It integrates more resources in a larger area despite leading to a little bit more time delay. The most obvious disadvantage of this architecture is that it needs a huge amount of investment to build the infrastructure of this system. This kind of cloud organization model is called the V2I cloud. On the basis of these two main architectures, the VC combined with the traditional cloud becomes a Hybrid Vehicular Cloud. The traditional cloud can provide extensive storage and computing capability. This architecture can be implemented over a large geographical area where there is a data center.Therefore, the VC should be organized by V2V if there is no communication infrastructure for the vehicles on the road and the services in demand need low latency. The VC should be organized by V2I when the following conditions are satisfied. Firstly, the communication infrastructure should be existing in this area. And then, if the large computational resources are required for the services which are provided to the vehicles, it needs to unite all the resources of the vehicles in one area.


### 3.2. Integrated Architecture of Workflow and VCC

The workflow technology has been used in traditional cloud to improve the efficiency of resources allocation [29]. A job or a service can be discomposed into a series of tasks according to the workflow theory. The dependence between them is usually described by Directed Acyclic Graph (DAG). The workflow provides some scheduling algorithms to optimize the task execution sequence or processor allocation mechanism to reduce the execution time or execution cost of the job. Naturally, the workflow can be used in VCC to improve its performance. The operation process of workflow in the VCC is shown as illustrated in Figure 2 by us. The architecture of workflow integrated with the VC can be separated into four layers: users, virtualized resources, workflow, and physical resources. The physical resources are composed of the computation, communication, storage, and sensor resources which existed as the CPU devices, bandwidth resources, and disks. All these devices are distributed on the vehicles and RSUs. Above the physical resources layer, the workflow layer works for assigning the tasks to the most suitable physical resources to achieve an optimized execution cost. In our paper, it gets the information of physical layer by monitor module. And then, it has a specific module which is used to calculate the connection fault probability of each vehicle at a given moment. The calculation is based on the monitoring data collected from the vehicles and the environment at that specific moment. The calculation result is delivered to the workflow engine which is used to decide the resources allocation schedule. All tasks composing the job are assigned to the physical resources layer. This process integrates the distributed physical resources to be the virtualized resources. Toward users, they can use the applications in ITS to obtain the services. All the resources in demand can be provided by the virtualized resources layer through the APIs.Figure 2
The architecture of workflow integrated with the VC.


### 3.3. Connection Fault Models in VCC

In the last section, the literature has shown that the variation and nonreliability of vehicle nodes in the parking lot have been researched. But those papers ignored the more complex scenario where the vehicles are driving on the road. The mobility of the vehicles will lead to the connection fault between the vehicle and the VC. In order to deal with this issue, we propose a prediction model of the connection fault for the vehicles driving on the road. It contains three concrete scenarios which present the missing connection of vehicle resources. Particularly, if there is a backbone data center, all the resources can be provided by it and avoid the risk of missing connection with the vehicle resource. However, it also loses the advantage of utilizing the spare resources of the on-board computers. So, in our paper, there is no data center as the cloud resources provider in the VCC and all the scenarios are based on this assumption.In addition, we assume that the velocity of the vehicles is a constant only if the vehicle stops itself to simplify the movement model of vehicles on the road.


#### 3.3.1. Scenario 1: Vehicle Leaves V2V Cloud

The first situation of resources node missing is shown in Figure3. The resources node aforementioned can be regarded as the vehicles which provide the resources like computing, communication, storage, and sensing resources to the VC. Three vehicles composed a mini Vehicular Cloud while they are moving on the road. When the red vehicle reaches its destination such as home, the driver of this vehicle would stop and sputter the engine very quickly for saving gasoline or electric power. Due to the shutdown of the on-board computer, this vehicle as a resource node will leave the original cloud resource pool suddenly and unpredictably. The connection fault with this vehicle leads to the task fault on this vehicle because this vehicle has no time to transport the execution result to the VC. There is no mechanism or constraint to make the on-board computer guarantee the execution result to be returned to the VC before it closed.Figure 3
The situation of vehicle stop.The second situation is a comprehensive set of many situations which can be called the vehicle leaving the communication range of the vehicle cluster. One of the situations can be commonly seen at the crisscross which is shown in Figure4. There are many crisscrosses in traffic road net, especially in the city. Each vehicle would have different destination and travel path. There is a high probability that one of the vehicles constructing the VC leaves the cluster at the crisscross of the road. Even though there are some new vehicles that will join the cluster after passing the crisscross, the task processed on the leaving vehicle is failed.Figure 4
The situation of vehicle leaving the cloud at the crisscross.The third situation is due to the difference between the velocities of the vehicles. In the realistic environment, the velocity of the vehicle is different. The vehicle chases up a vehicle cluster and joins it. However, it leaves the cluster after few minutes because of its higher speed which is shown in Figure5. Otherwise, this vehicle is slower than the vehicle cluster and is chased up by the cluster. Both of them can lead to the missing connection with the resource.Figure 5
The situation of the vehicle leaving the cluster by speeding up.


#### 3.3.2. Scenario 2: Vehicle Leaves V2I Cloud

Scenario 2 is little different from the first one in the architecture of VC. The architecture of the first one used the V2V communication and small amount of vehicles composed the local VC. The last scenario uses the RSUs to transmit the information of all the vehicles in a large geographical area, which is shown in Figure6, and we call it the V2I cloud. All of the authenticated vehicles share the cloud computing resource in this area. The disadvantage is that the infrastructure which can provide the communication functions must be built in advance. But the RSUs cannot spread all over the area where the vehicles want to move under the cost restriction. Hence, in the border of the VC with the RSUs, the vehicle has a high probability to migrate out to the area where there is no signal of RSUs. The resource of the vehicle will be lost if the vehicle drives out of the RSU enabled by VC in this area. This scenario is a little bit like Scenario 1, because in both of them the vehicle moves out of the signal range. But in Scenario 1, the source of the signal, the vehicle cloud cluster, is mobile. In contrary, the locations of the RSUs are stable.Figure 6
The scenario of the vehicle migrating out to the RSUs.The above two scenarios are very common, which leads to the missing connection of vehicle resources with the VC when the vehicle is driving on the road. In this paper, we first pay attention to predicting the probability of the occurrences of above scenarios by mathematical model. The resources with low connection fault probability are regarded as reliable. And then, we propose a workflow resource allocation algorithm to allocate the reliable resources to execute the tasks. It can improve the safety of the whole VCC system.


## 3.1. The Architecture of VCC

Generally, there are two difference architectures to construct the VCC. Although some new content delivery mechanisms were proposed [27, 28], the typical V2V and V2I communication mechanisms which are the most popular in the realistic traffic environment are considered in our paper. As shown in Figure 1, the underlayer components are vehicles on the road. The vehicles share their resources such as computing capability, communicating bandwidth, and storage space with each other by the direct V2V communication. In our paper, this orientation model of cloud is called the V2V cloud. The advantage of this architecture is the low delay time of communication. However, due to the limited communication range of the vehicular radio, the scale of the cloud is often too small to complete some complex services such as managing evacuation when the density of vehicles is not sufficient in the range of the vehicular radio.Figure 1
The architecture of VCC.In order to address the limitation of this basic architecture, the RSUs are used to provide long-distance transmission for vehicles in different places. It integrates more resources in a larger area despite leading to a little bit more time delay. The most obvious disadvantage of this architecture is that it needs a huge amount of investment to build the infrastructure of this system. This kind of cloud organization model is called the V2I cloud. On the basis of these two main architectures, the VC combined with the traditional cloud becomes a Hybrid Vehicular Cloud. The traditional cloud can provide extensive storage and computing capability. This architecture can be implemented over a large geographical area where there is a data center.Therefore, the VC should be organized by V2V if there is no communication infrastructure for the vehicles on the road and the services in demand need low latency. The VC should be organized by V2I when the following conditions are satisfied. Firstly, the communication infrastructure should be existing in this area. And then, if the large computational resources are required for the services which are provided to the vehicles, it needs to unite all the resources of the vehicles in one area.


## 3.2. Integrated Architecture of Workflow and VCC

The workflow technology has been used in traditional cloud to improve the efficiency of resources allocation [29]. A job or a service can be discomposed into a series of tasks according to the workflow theory. The dependence between them is usually described by Directed Acyclic Graph (DAG). The workflow provides some scheduling algorithms to optimize the task execution sequence or processor allocation mechanism to reduce the execution time or execution cost of the job. Naturally, the workflow can be used in VCC to improve its performance. The operation process of workflow in the VCC is shown as illustrated in Figure 2 by us. The architecture of workflow integrated with the VC can be separated into four layers: users, virtualized resources, workflow, and physical resources. The physical resources are composed of the computation, communication, storage, and sensor resources which existed as the CPU devices, bandwidth resources, and disks. All these devices are distributed on the vehicles and RSUs. Above the physical resources layer, the workflow layer works for assigning the tasks to the most suitable physical resources to achieve an optimized execution cost. In our paper, it gets the information of physical layer by monitor module. And then, it has a specific module which is used to calculate the connection fault probability of each vehicle at a given moment. The calculation is based on the monitoring data collected from the vehicles and the environment at that specific moment. The calculation result is delivered to the workflow engine which is used to decide the resources allocation schedule. All tasks composing the job are assigned to the physical resources layer. This process integrates the distributed physical resources to be the virtualized resources. Toward users, they can use the applications in ITS to obtain the services. All the resources in demand can be provided by the virtualized resources layer through the APIs.Figure 2
The architecture of workflow integrated with the VC.


## 3.3. Connection Fault Models in VCC

In the last section, the literature has shown that the variation and nonreliability of vehicle nodes in the parking lot have been researched. But those papers ignored the more complex scenario where the vehicles are driving on the road. The mobility of the vehicles will lead to the connection fault between the vehicle and the VC. In order to deal with this issue, we propose a prediction model of the connection fault for the vehicles driving on the road. It contains three concrete scenarios which present the missing connection of vehicle resources. Particularly, if there is a backbone data center, all the resources can be provided by it and avoid the risk of missing connection with the vehicle resource. However, it also loses the advantage of utilizing the spare resources of the on-board computers. So, in our paper, there is no data center as the cloud resources provider in the VCC and all the scenarios are based on this assumption.In addition, we assume that the velocity of the vehicles is a constant only if the vehicle stops itself to simplify the movement model of vehicles on the road.


### 3.3.1. Scenario 1: Vehicle Leaves V2V Cloud

The first situation of resources node missing is shown in Figure3. The resources node aforementioned can be regarded as the vehicles which provide the resources like computing, communication, storage, and sensing resources to the VC. Three vehicles composed a mini Vehicular Cloud while they are moving on the road. When the red vehicle reaches its destination such as home, the driver of this vehicle would stop and sputter the engine very quickly for saving gasoline or electric power. Due to the shutdown of the on-board computer, this vehicle as a resource node will leave the original cloud resource pool suddenly and unpredictably. The connection fault with this vehicle leads to the task fault on this vehicle because this vehicle has no time to transport the execution result to the VC. There is no mechanism or constraint to make the on-board computer guarantee the execution result to be returned to the VC before it closed.Figure 3
The situation of vehicle stop.The second situation is a comprehensive set of many situations which can be called the vehicle leaving the communication range of the vehicle cluster. One of the situations can be commonly seen at the crisscross which is shown in Figure4. There are many crisscrosses in traffic road net, especially in the city. Each vehicle would have different destination and travel path. There is a high probability that one of the vehicles constructing the VC leaves the cluster at the crisscross of the road. Even though there are some new vehicles that will join the cluster after passing the crisscross, the task processed on the leaving vehicle is failed.Figure 4
The situation of vehicle leaving the cloud at the crisscross.The third situation is due to the difference between the velocities of the vehicles. In the realistic environment, the velocity of the vehicle is different. The vehicle chases up a vehicle cluster and joins it. However, it leaves the cluster after few minutes because of its higher speed which is shown in Figure5. Otherwise, this vehicle is slower than the vehicle cluster and is chased up by the cluster. Both of them can lead to the missing connection with the resource.Figure 5
The situation of the vehicle leaving the cluster by speeding up.


### 3.3.2. Scenario 2: Vehicle Leaves V2I Cloud

Scenario 2 is little different from the first one in the architecture of VC. The architecture of the first one used the V2V communication and small amount of vehicles composed the local VC. The last scenario uses the RSUs to transmit the information of all the vehicles in a large geographical area, which is shown in Figure6, and we call it the V2I cloud. All of the authenticated vehicles share the cloud computing resource in this area. The disadvantage is that the infrastructure which can provide the communication functions must be built in advance. But the RSUs cannot spread all over the area where the vehicles want to move under the cost restriction. Hence, in the border of the VC with the RSUs, the vehicle has a high probability to migrate out to the area where there is no signal of RSUs. The resource of the vehicle will be lost if the vehicle drives out of the RSU enabled by VC in this area. This scenario is a little bit like Scenario 1, because in both of them the vehicle moves out of the signal range. But in Scenario 1, the source of the signal, the vehicle cloud cluster, is mobile. In contrary, the locations of the RSUs are stable.Figure 6
The scenario of the vehicle migrating out to the RSUs.The above two scenarios are very common, which leads to the missing connection of vehicle resources with the VC when the vehicle is driving on the road. In this paper, we first pay attention to predicting the probability of the occurrences of above scenarios by mathematical model. The resources with low connection fault probability are regarded as reliable. And then, we propose a workflow resource allocation algorithm to allocate the reliable resources to execute the tasks. It can improve the safety of the whole VCC system.


## 3.3.1. Scenario 1: Vehicle Leaves V2V Cloud

The first situation of resources node missing is shown in Figure3. The resources node aforementioned can be regarded as the vehicles which provide the resources like computing, communication, storage, and sensing resources to the VC. Three vehicles composed a mini Vehicular Cloud while they are moving on the road. When the red vehicle reaches its destination such as home, the driver of this vehicle would stop and sputter the engine very quickly for saving gasoline or electric power. Due to the shutdown of the on-board computer, this vehicle as a resource node will leave the original cloud resource pool suddenly and unpredictably. The connection fault with this vehicle leads to the task fault on this vehicle because this vehicle has no time to transport the execution result to the VC. There is no mechanism or constraint to make the on-board computer guarantee the execution result to be returned to the VC before it closed.Figure 3
The situation of vehicle stop.The second situation is a comprehensive set of many situations which can be called the vehicle leaving the communication range of the vehicle cluster. One of the situations can be commonly seen at the crisscross which is shown in Figure4. There are many crisscrosses in traffic road net, especially in the city. Each vehicle would have different destination and travel path. There is a high probability that one of the vehicles constructing the VC leaves the cluster at the crisscross of the road. Even though there are some new vehicles that will join the cluster after passing the crisscross, the task processed on the leaving vehicle is failed.Figure 4
The situation of vehicle leaving the cloud at the crisscross.The third situation is due to the difference between the velocities of the vehicles. In the realistic environment, the velocity of the vehicle is different. The vehicle chases up a vehicle cluster and joins it. However, it leaves the cluster after few minutes because of its higher speed which is shown in Figure5. Otherwise, this vehicle is slower than the vehicle cluster and is chased up by the cluster. Both of them can lead to the missing connection with the resource.Figure 5
The situation of the vehicle leaving the cluster by speeding up.


## 3.3.2. Scenario 2: Vehicle Leaves V2I Cloud

Scenario 2 is little different from the first one in the architecture of VC. The architecture of the first one used the V2V communication and small amount of vehicles composed the local VC. The last scenario uses the RSUs to transmit the information of all the vehicles in a large geographical area, which is shown in Figure6, and we call it the V2I cloud. All of the authenticated vehicles share the cloud computing resource in this area. The disadvantage is that the infrastructure which can provide the communication functions must be built in advance. But the RSUs cannot spread all over the area where the vehicles want to move under the cost restriction. Hence, in the border of the VC with the RSUs, the vehicle has a high probability to migrate out to the area where there is no signal of RSUs. The resource of the vehicle will be lost if the vehicle drives out of the RSU enabled by VC in this area. This scenario is a little bit like Scenario 1, because in both of them the vehicle moves out of the signal range. But in Scenario 1, the source of the signal, the vehicle cloud cluster, is mobile. In contrary, the locations of the RSUs are stable.Figure 6
The scenario of the vehicle migrating out to the RSUs.The above two scenarios are very common, which leads to the missing connection of vehicle resources with the VC when the vehicle is driving on the road. In this paper, we first pay attention to predicting the probability of the occurrences of above scenarios by mathematical model. The resources with low connection fault probability are regarded as reliable. And then, we propose a workflow resource allocation algorithm to allocate the reliable resources to execute the tasks. It can improve the safety of the whole VCC system.


## 4. Formulations of Connection Fault of VCC

### 4.1. Formulation Definitions of VCC

In this section, the clear definitions for all key concepts in the VCC will be provided and all these concepts compose the three models of the vehicle resource missing connection in the road.Definition 1.
The final aim of the VCC is providing services to the users driving on the road. The service for the vehicles can be substituted with job or workflow in the statement. One job can be divided into amount of tasks and the task set has a processing sequence to complete the whole services. The dependent tasks can be described by a Directed Acyclic Graph (DAG).
A DAG is defined as a 2-tupleG
=
{
T
A
S
K
,
E
}, where T
A
S
K
=
{
t
a
s
k
1
,
t
a
s
k
2
,
…
,
t
a
s
k
n
} is the set of the tasks which composed the job and E
=
{
e
(
t
a
s
k
i
,
t
a
s
k
j
)
∣
t
a
s
k
i
,
t
a
s
k
j
∈
T
} is the set of directed edges that represented the dependencies between the tasks: t
a
s
k
i and t
a
s
k
j. e
(
t
a
s
k
i
,
t
a
s
k
j
) can be simplified as e
i
j to indicate that the input data of the task t
a
s
k
j contains the output data of the task t
a
s
k
i. Hence, the task t
a
s
k
jcannot be executed until the output of the task t
a
s
k
i has been produced and transferred to the resource node running the task t
a
s
k
j.Definition 2.
The elementary unit which was allocated by service workflow schedule can be defined as task. As a minimum independent unit which can be processed in the on-board computer, it needs an input to begin the task execution and produces an output after the execution of this task. The execution time is an important factor as the basis of the service execution time. So the task can be modeled as a triplet
a
s
k
=
(
D
,
w
l
), where D is a square matrix which contains the data length of each task, the element d
i
,
j indicates the data length needed to transfer from task t
a
s
k
i to task t
a
s
k
j, and w
l is the execution workload of this task which can be measured by Million Instructions (MI).Definition 3.
The vehicle is the main body of the computing resource which composes the VC, which is like the servers in the traditional cloud system. However, the vehicle has some new features like mobility, limitation of communication range, and privatization. The vehicle can be modeled asV
e
h
=
(
C
v
e
h
,
T
V
,
V
,
d
,
D
i
U
), where C
v
e
h is the computation capability of the computing resource of the on-board computer in this vehicle. The computation capability can be measured by Million Instructions Per Second (MIPS). T
V is the transmission rate (in Kbps) in the V2V mode,V is the velocity of this vehicle which is a constant assumed in advance, d is the traveling distance of this vehicle in this time which can be measured by kilometers, and D
i
U is the distance away from the signal boundary of the Roadside Unit U.Definition 4.
The Roadside Units (RSUs) are the infrastructure of the VCC to transmit the messages in a long distance. The key factor of the RSUs is the communication range and the communication rate. It is modeled asU
=
(
R
U
,
T
U
u
p
,
T
U
d
o
w
n
), where R
U indicates the communication radius of the radio (in KMs) and T
U
u
p and T
U
d
o
w
n are the rate when the unit forwards the data to the vehicles.
The scenarios of the vehicle leaving the VC have been represented in the last section. In order to avoid that the vehicle misses connection with the VC during execution of the task, a prediction-based workflow schedule mechanism is proposed. Before the workflow engine assigns the tasks to the vehicles, the probability of the vehicle missing connection with the VC will be calculated. The workflow will optimize the task allocation according to the computing result. Hence, the definition of the probability in three difference situations should be formulated. All of them are in what follows.Definition 5.
The total probability is composed of the probabilities of two situations which belong to Scenario 1. So total probability of the missing connection with the resource can be calculated in two different situations. The first one is in the V2V scenario:(1)
P
=
1
-
1
-
P
s
1
-
P
l
=
P
s
+
P
l
-
P
s
P
l
,where P
s is the probability of the vehicle arriving at its destination during the execution time of a task and P
l is the probability of the vehicle leaving the vehicle cluster on the road.
The second one is in the V2I scenario:(2)
P
=
P
m
.
P
m is the probability of the vehicle migration out of the area which has the radio signal of the RSUs. In the V2I scenario, vehicles communicate with each other via RSUs. All the vehicles in the region covered by the infrastructures are the components of the Vehicular Cloud. There are no Scenarios 1 and 2 existing, so the total connection fault probability is equal to P
m.


### 4.2. Formulations for Connection Fault Models

In this section, we will establish the functions of the probabilities in the previous proposed scenarios.In Scenario 1, it is common sense that the destination of a vehicle can be represented as the traveling distance of the vehicle from the starting. In other words, the settlement of the stopping probability is to build the model of the traveling distance of a vehicle. We can deduce the distribution of the traveling distance by the probability theory. According to the Stochastic Theory, the distance from the starting to the destination is a random value. We assume that the probability of the vehicle stopping in the following distanceΔ
r is proportional to the distancerthe vehicle has traveled. The formula is as follows:(3)
P
r
<
X
≤
r
+
Δ
r
∣
X
>
r
=
λ
1
×
r
×
Δ
r
+
O
Δ
r
,where λ
1 is a constant which has no relationship with the r and Δ
r and O
(
Δ
r
) is the high degree polynomial of the factor Δ
r.The left side of (3) is a conditional probability which can be transformed as follows:(4)
P
r
<
X
≤
r
+
Δ
r
∣
X
>
r
=
F
r
+
Δ
r
-
F
r
1
-
F
r
F
r
=
l
i
m
Δ
r
→
0
F
r
+
Δ
r
-
F
r
Δ
r
=
λ
1
×
r
×
1
-
F
r
.By solving the linear differential equation with the initial condition,F
(
0
)
=
0, we can figure out that the function of the traveling distance distribution obeys the following equations which is Rayleigh distribution. Its traveling distance cumulative probability function and probability density function are as follows:(5)
F
r
=
1
-
exp
⁡
-
0.5
λ
1
r
2
(6)
f
r
=
λ
1
r
exp
⁡
-
0.5
λ
1
r
2
.The basic forms of the Rayleigh cumulative probability function and the Rayleigh density function are shown in Figure7 and this assumption is also used in [27] which can prove that our assumption is reasonable.Figure 7
The function of Rayleigh distribution cumulative probability function and the probability density function.In (5) and (6), the parameterrhas been defined in Definition 3 as symbol d and the parameter Δ
r can be figured out by the value of the vehicle velocity and the total execution time of a task. We can calculate the total execution time of the task t
a
s
k
i that was allocated to a vehicle defined in V
e
h
=
(
C
v
e
h
,
T
V
,
V
,
d
,
D
i
U
)by the following equations:(7)
w
t
=
w
l
C
v
e
h
(8)
c
=
L
+
d
o
T
V
(9)
E
t
i
=
c
+
w
t
=
L
+
d
o
T
V
+
w
l
C
,where w
t is the execution time cost and w
l is the workload of a task and C
v
e
h is the computation capability of the vehicle, which is defined in Definition 3. c is the time cost of the task transmission, and L indicates the communication startup cost. E
t
i is the total execution time of the task t
a
s
k
i and the connection fault could happen in this duration.Therefore, the parameterΔ
r can be represented as follows:(10)
Δ
r
=
V
×
E
t
i
.Based on the calculated aforementioned component, the probability function (5) can be represented as follows:(11)
P
s
=
1
-
e
x
p
-
0.5
λ
1
d
+
V
×
E
t
i
2
-
d
2
.In the second and third situations of Scenario 1, the probability distribution model can imitate from the probability model of other vehicle transportation models. A vehicle distance distribution probability model is found in [30]. It is used to analyze the vehicle collision probability. The vehicle collision event is regarded as the random event. The exponential distribution is used to describe the intervehicle space. Thus, we use random event to describe the events of the second and third situations in Scenario 1. In probability theory, the exponential distribution is used to describe the happening of the event which has no memorability. This character can be represented as(12)
P
T
>
t
+
s
∣
T
>
t
=
P
T
>
s
,
s
>
0
,
t
>
0
,which means the probability of the event happening during the time t to the time t
+
s is equal to the probability of the event happening during the time 0 to the times. The equations of the exponential distribution are as follows: (13)
f
x
=
λ
2
e
-
λ
2
x
,
x
>
0
F
x
=
1
-
e
-
λ
2
x
,
x
>
0
.So in this formulas group, the probability of the vehicle leaving the cluster is just related with the total execution time of the task. HenceP
l can be represented as the following equation:(14)
P
l
=
P
t
<
T
<
t
+
Δ
t
∣
T
>
t
=
P
T
<
Δ
t
=
1
-
e
-
λ
2
Δ
t
,where Δ
t is equal to E
t
i, which is the whole time cost of the task t
a
s
k
i and λ
2 is a constant which has no relationship with Δ
t.In Scenario 2, due to the RSUs being stable, the probability of vehicle migration out of the RSUs region is easily described. The probability is in direct proportion to the velocity of the vehicle and the total execution time of the allocated task, in inverse proportion to the distance away from the signal boundary of the RSUs. So,P
m is as follows:(15)
P
m
=
λ
3
×
V
×
E
t
i
D
i
U
,where λ
3 is a constant which relates with the realistic traffic environment. The transmission rate D
i
U in this equation is determined by RSU U.Statistically, the vehicle resource missing connection with the VC is one of main causes of the service fail. In out paper, we just discuss the service fail probability which is led by the vehicle disconnection. So the total service fail probability is just related with the probability of each vehicle allocated the tasks to execute missing connection with the VC. The event of vehicle connection fault happens independently and arbitrary one task of all fail will lead to the service fail. Hence the total service fail probability is the product of each vehicle reliability which is 1 minus the vehicle connection fault probability. It can be formulated as follows:(16)
P
t
o
t
a
l
=
1
-
∏
j
=
1
N
1
-
P
j
,where P
j should be defined, respectively, in different scenarios. It is defined by (1) in V2V scenario. It is defined by (2) in V2I scenario. It is a conditional probability. The symbol j indicates the vehicle’s serial number and N is the amount of total vehicles that are allocated the tasks in this VC at that moment.The model of vehicle connection fault has been shown in the last section. By analyzing the function of the parametersP
s, P
l, and P
m, it is obvious that the main independent variation in these functions is E
t
i which decides the function result. The probability of the vehicle missing connection will become higher if the execution time of the task running on this vehicle becomes longer. However, the connection fault probability minimum problem cannot be transformed as a problem to minimize the total execution time cost. Because each vehicle has an individual connection fault probability function, the assigning destination of the tasks also has effect on P
t
o
t
a
l. Therefore, a safety resources allocation schedule should be studied to minimize P
t
o
t
a
l.


## 4.1. Formulation Definitions of VCC

In this section, the clear definitions for all key concepts in the VCC will be provided and all these concepts compose the three models of the vehicle resource missing connection in the road.Definition 1.
The final aim of the VCC is providing services to the users driving on the road. The service for the vehicles can be substituted with job or workflow in the statement. One job can be divided into amount of tasks and the task set has a processing sequence to complete the whole services. The dependent tasks can be described by a Directed Acyclic Graph (DAG).
A DAG is defined as a 2-tupleG
=
{
T
A
S
K
,
E
}, where T
A
S
K
=
{
t
a
s
k
1
,
t
a
s
k
2
,
…
,
t
a
s
k
n
} is the set of the tasks which composed the job and E
=
{
e
(
t
a
s
k
i
,
t
a
s
k
j
)
∣
t
a
s
k
i
,
t
a
s
k
j
∈
T
} is the set of directed edges that represented the dependencies between the tasks: t
a
s
k
i and t
a
s
k
j. e
(
t
a
s
k
i
,
t
a
s
k
j
) can be simplified as e
i
j to indicate that the input data of the task t
a
s
k
j contains the output data of the task t
a
s
k
i. Hence, the task t
a
s
k
jcannot be executed until the output of the task t
a
s
k
i has been produced and transferred to the resource node running the task t
a
s
k
j.Definition 2.
The elementary unit which was allocated by service workflow schedule can be defined as task. As a minimum independent unit which can be processed in the on-board computer, it needs an input to begin the task execution and produces an output after the execution of this task. The execution time is an important factor as the basis of the service execution time. So the task can be modeled as a triplet
a
s
k
=
(
D
,
w
l
), where D is a square matrix which contains the data length of each task, the element d
i
,
j indicates the data length needed to transfer from task t
a
s
k
i to task t
a
s
k
j, and w
l is the execution workload of this task which can be measured by Million Instructions (MI).Definition 3.
The vehicle is the main body of the computing resource which composes the VC, which is like the servers in the traditional cloud system. However, the vehicle has some new features like mobility, limitation of communication range, and privatization. The vehicle can be modeled asV
e
h
=
(
C
v
e
h
,
T
V
,
V
,
d
,
D
i
U
), where C
v
e
h is the computation capability of the computing resource of the on-board computer in this vehicle. The computation capability can be measured by Million Instructions Per Second (MIPS). T
V is the transmission rate (in Kbps) in the V2V mode,V is the velocity of this vehicle which is a constant assumed in advance, d is the traveling distance of this vehicle in this time which can be measured by kilometers, and D
i
U is the distance away from the signal boundary of the Roadside Unit U.Definition 4.
The Roadside Units (RSUs) are the infrastructure of the VCC to transmit the messages in a long distance. The key factor of the RSUs is the communication range and the communication rate. It is modeled asU
=
(
R
U
,
T
U
u
p
,
T
U
d
o
w
n
), where R
U indicates the communication radius of the radio (in KMs) and T
U
u
p and T
U
d
o
w
n are the rate when the unit forwards the data to the vehicles.
The scenarios of the vehicle leaving the VC have been represented in the last section. In order to avoid that the vehicle misses connection with the VC during execution of the task, a prediction-based workflow schedule mechanism is proposed. Before the workflow engine assigns the tasks to the vehicles, the probability of the vehicle missing connection with the VC will be calculated. The workflow will optimize the task allocation according to the computing result. Hence, the definition of the probability in three difference situations should be formulated. All of them are in what follows.Definition 5.
The total probability is composed of the probabilities of two situations which belong to Scenario 1. So total probability of the missing connection with the resource can be calculated in two different situations. The first one is in the V2V scenario:(1)
P
=
1
-
1
-
P
s
1
-
P
l
=
P
s
+
P
l
-
P
s
P
l
,where P
s is the probability of the vehicle arriving at its destination during the execution time of a task and P
l is the probability of the vehicle leaving the vehicle cluster on the road.
The second one is in the V2I scenario:(2)
P
=
P
m
.
P
m is the probability of the vehicle migration out of the area which has the radio signal of the RSUs. In the V2I scenario, vehicles communicate with each other via RSUs. All the vehicles in the region covered by the infrastructures are the components of the Vehicular Cloud. There are no Scenarios 1 and 2 existing, so the total connection fault probability is equal to P
m.


## 4.2. Formulations for Connection Fault Models

In this section, we will establish the functions of the probabilities in the previous proposed scenarios.In Scenario 1, it is common sense that the destination of a vehicle can be represented as the traveling distance of the vehicle from the starting. In other words, the settlement of the stopping probability is to build the model of the traveling distance of a vehicle. We can deduce the distribution of the traveling distance by the probability theory. According to the Stochastic Theory, the distance from the starting to the destination is a random value. We assume that the probability of the vehicle stopping in the following distanceΔ
r is proportional to the distancerthe vehicle has traveled. The formula is as follows:(3)
P
r
<
X
≤
r
+
Δ
r
∣
X
>
r
=
λ
1
×
r
×
Δ
r
+
O
Δ
r
,where λ
1 is a constant which has no relationship with the r and Δ
r and O
(
Δ
r
) is the high degree polynomial of the factor Δ
r.The left side of (3) is a conditional probability which can be transformed as follows:(4)
P
r
<
X
≤
r
+
Δ
r
∣
X
>
r
=
F
r
+
Δ
r
-
F
r
1
-
F
r
F
r
=
l
i
m
Δ
r
→
0
F
r
+
Δ
r
-
F
r
Δ
r
=
λ
1
×
r
×
1
-
F
r
.By solving the linear differential equation with the initial condition,F
(
0
)
=
0, we can figure out that the function of the traveling distance distribution obeys the following equations which is Rayleigh distribution. Its traveling distance cumulative probability function and probability density function are as follows:(5)
F
r
=
1
-
exp
⁡
-
0.5
λ
1
r
2
(6)
f
r
=
λ
1
r
exp
⁡
-
0.5
λ
1
r
2
.The basic forms of the Rayleigh cumulative probability function and the Rayleigh density function are shown in Figure7 and this assumption is also used in [27] which can prove that our assumption is reasonable.Figure 7
The function of Rayleigh distribution cumulative probability function and the probability density function.In (5) and (6), the parameterrhas been defined in Definition 3 as symbol d and the parameter Δ
r can be figured out by the value of the vehicle velocity and the total execution time of a task. We can calculate the total execution time of the task t
a
s
k
i that was allocated to a vehicle defined in V
e
h
=
(
C
v
e
h
,
T
V
,
V
,
d
,
D
i
U
)by the following equations:(7)
w
t
=
w
l
C
v
e
h
(8)
c
=
L
+
d
o
T
V
(9)
E
t
i
=
c
+
w
t
=
L
+
d
o
T
V
+
w
l
C
,where w
t is the execution time cost and w
l is the workload of a task and C
v
e
h is the computation capability of the vehicle, which is defined in Definition 3. c is the time cost of the task transmission, and L indicates the communication startup cost. E
t
i is the total execution time of the task t
a
s
k
i and the connection fault could happen in this duration.Therefore, the parameterΔ
r can be represented as follows:(10)
Δ
r
=
V
×
E
t
i
.Based on the calculated aforementioned component, the probability function (5) can be represented as follows:(11)
P
s
=
1
-
e
x
p
-
0.5
λ
1
d
+
V
×
E
t
i
2
-
d
2
.In the second and third situations of Scenario 1, the probability distribution model can imitate from the probability model of other vehicle transportation models. A vehicle distance distribution probability model is found in [30]. It is used to analyze the vehicle collision probability. The vehicle collision event is regarded as the random event. The exponential distribution is used to describe the intervehicle space. Thus, we use random event to describe the events of the second and third situations in Scenario 1. In probability theory, the exponential distribution is used to describe the happening of the event which has no memorability. This character can be represented as(12)
P
T
>
t
+
s
∣
T
>
t
=
P
T
>
s
,
s
>
0
,
t
>
0
,which means the probability of the event happening during the time t to the time t
+
s is equal to the probability of the event happening during the time 0 to the times. The equations of the exponential distribution are as follows: (13)
f
x
=
λ
2
e
-
λ
2
x
,
x
>
0
F
x
=
1
-
e
-
λ
2
x
,
x
>
0
.So in this formulas group, the probability of the vehicle leaving the cluster is just related with the total execution time of the task. HenceP
l can be represented as the following equation:(14)
P
l
=
P
t
<
T
<
t
+
Δ
t
∣
T
>
t
=
P
T
<
Δ
t
=
1
-
e
-
λ
2
Δ
t
,where Δ
t is equal to E
t
i, which is the whole time cost of the task t
a
s
k
i and λ
2 is a constant which has no relationship with Δ
t.In Scenario 2, due to the RSUs being stable, the probability of vehicle migration out of the RSUs region is easily described. The probability is in direct proportion to the velocity of the vehicle and the total execution time of the allocated task, in inverse proportion to the distance away from the signal boundary of the RSUs. So,P
m is as follows:(15)
P
m
=
λ
3
×
V
×
E
t
i
D
i
U
,where λ
3 is a constant which relates with the realistic traffic environment. The transmission rate D
i
U in this equation is determined by RSU U.Statistically, the vehicle resource missing connection with the VC is one of main causes of the service fail. In out paper, we just discuss the service fail probability which is led by the vehicle disconnection. So the total service fail probability is just related with the probability of each vehicle allocated the tasks to execute missing connection with the VC. The event of vehicle connection fault happens independently and arbitrary one task of all fail will lead to the service fail. Hence the total service fail probability is the product of each vehicle reliability which is 1 minus the vehicle connection fault probability. It can be formulated as follows:(16)
P
t
o
t
a
l
=
1
-
∏
j
=
1
N
1
-
P
j
,where P
j should be defined, respectively, in different scenarios. It is defined by (1) in V2V scenario. It is defined by (2) in V2I scenario. It is a conditional probability. The symbol j indicates the vehicle’s serial number and N is the amount of total vehicles that are allocated the tasks in this VC at that moment.The model of vehicle connection fault has been shown in the last section. By analyzing the function of the parametersP
s, P
l, and P
m, it is obvious that the main independent variation in these functions is E
t
i which decides the function result. The probability of the vehicle missing connection will become higher if the execution time of the task running on this vehicle becomes longer. However, the connection fault probability minimum problem cannot be transformed as a problem to minimize the total execution time cost. Because each vehicle has an individual connection fault probability function, the assigning destination of the tasks also has effect on P
t
o
t
a
l. Therefore, a safety resources allocation schedule should be studied to minimize P
t
o
t
a
l.


## 5. Safety Resources Allocation Workflow Schedule for VCC

### 5.1. The Fundamental Workflow Schedule

We can firstly assume that there areM tasks that need to be allocated and N vehicles prepare to accept task at that moment. To indicate the allocation schedule, let the matrix X be an M
×
N binary matrix corresponding to the schedule of M tasks into the N vehicle on-board computers. In this matrix, the element X
i
j
=
1, if the task t
a
s
k
iis assigned to the vehicle V
e
h
j and X
i
j
=
0 otherwise.E
t
t
o
t
a
l
p represents the actual execution time for multitasks on the particular vehicle V
e
h
p. E
t
t
o
t
a
l
p is different from the summation of E
t
t
o
t
a
l due to the fact that tasks which have dependence with each other could be allocated to the same vehicle. Therefore, the execution result of the parent task is unnecessary to be transferred to other vehicles. It reduces the total execution time E
t
t
o
t
a
l
p of the whole service.(17)
E
t
t
o
t
a
l
p
≤
∑
E
t
i
.We can defineE
t
t
o
t
a
l
p as follows: Firstly, the relationship of the tasks assigned to the vehicle V
e
h
p can be shown in the matrix X. The p
t
h row in X shows that the task t
a
s
k
i is assigned to this vehicle when x
i
p
=
1. we define a new matrix Y
p to represent the possible dependence between the tasks allocated to vehicle V
e
h
p:(18)
y
i
1
i
2
=
x
i
1
p
x
i
2
p
i
1
≠
i
2
y
i
1
i
2
=
0
i
1
=
i
2
,where 1
≤
i
1
,
i
2
≤
M, and y
i
1
i
2 is the element in the matrixY
p
.The actual dependence between the tasks is shown in the setE
=
{
e
(
t
a
s
k
i
,
t
a
s
k
j
)
∣
t
a
s
k
i
,
t
a
s
k
j
∈
T
A
S
K
}, and it can be transferred to a matrix E, and the element e
i
j
=
1 when e
(
t
a
s
k
i
,
t
a
s
k
j
) existed in the set E.So, the actual existing dependence between the tasks assigned to the vehicleV
e
h
p which is named as E
a
c
t
p and the element in it can be indicated as e
i
j
a
c
t:(19)
E
a
c
t
p
=
Y
p
·
E
.So,E
t
t
o
t
a
l
p can be calculated by the following equation:(20)
E
t
t
o
t
a
l
p
=
∑
i
=
1
M
x
i
p
E
t
i
-
∑
i
∑
j
e
i
j
a
c
t
d
o
i
T
p
u
p
+
d
i
j
T
p
d
o
w
n
.


### 5.2. Priority Classification of Tasks

After the derivation ofE
t
t
o
t
a
l
p, to design a workflow schedule, we need to determine the priority compartment for each task to confirm the execution order of these tasks. In this paper, we determine these parameters according to the dependence of each task in the workflow. Then, due to the deadline of the service, we have to separate it into each task to find out the Earliest Starting Time (EST), Earliest Finishing Time (EFT), Latest Finishing Time (LFT), Actual Starting Time (AST), and Actual Finishing Time (AFT) of each task. At last, we can find out the allocation strategy under the task priority and time constraint.At the beginning, we have to consider some definition used in the following priority computation. In (7), w
t refers to the computing time cost of a task which is executed on a vehicle. Therefore, this result can be extended to all the combinations of the tasks and vehicles. A matrix W
M
×
N is set to store the computing time cost, where M is the number of tasks and N is the number of the vehicles. The element w
t
i
,
j in the matrix refers to computing time cost of t
a
s
k
i assigning to V
e
h
j. So, we can get the average execution time for each task:(21)
w
¯
t
i
=
∑
j
=
1
N
w
t
i
,
j
N
.The average communication cost for the edgee
=
{
(
t
a
s
k
i
,
t
a
s
k
j
)
∣
t
a
s
k
i
,
t
a
s
k
j
∈
T
A
S
K
} can be inferred from (8):(22)
c
¯
i
,
j
=
L
¯
+
d
i
,
j
T
V
¯
,where T
V
¯ is the average transfer rate among the vehicles in the VC and L
¯ is the average communication startup time cost.According to [31], the task can be classified into simple task and synchronization task. The task has more than one parent task or its child task is the synchronization task. Otherwise, this task is the simple task. The simple tasks executed between two synchronization tasks are called branches. We can set the same deadline for the several branches between two synchronization tasks.According to [32], the upward rank of a task t
a
s
k
i is recursively defined as(23)
rank
⁡
t
a
s
k
i
=
w
¯
t
i
+
max
tas
k
j
∈
succ
tas
k
i
⁡
c
¯
i
,
j
+
rank
⁡
t
a
s
k
j
,where s
u
c
c
(
t
a
s
k
i
) is the set of immediate successors of task t
a
s
k
i, c
¯
i
,
j is the average communication time cost of edge e
(
t
a
s
k
i
,
t
a
s
k
j
), and w
¯
t
i is the average computing time cost of task t
a
s
k
i. And the upward rank starts from the exit task t
a
s
k
e
x
i
t. The rank value of the exit task is determined by the following equation:(24)
rank
⁡
t
a
s
k
e
x
i
t
=
w
¯
t
e
x
i
t
.So, we can transfer the DAG which is used to describe the task execution time sequence into the rank value for each task to represent its execution time sequence.


### 5.3. Task Execution Deadline Schedule

The EST, EFT, and LFT attributes need to be defined. The EST for entry taskt
a
s
k
e
n
t
r
y can be indicated as follows:(25)
E
S
T
t
a
s
k
e
n
t
r
y
,
V
e
h
p
=
0
.Based on the EST for entry task, the EST, EFT, and LFT values for other tasks are shown in the following equations:(26)
E
S
T
t
a
s
k
i
,
V
e
h
p
=
max
⁡
a
v
a
i
l
p
,
max
tas
k
m
∈
pred
tas
k
i
⁡
A
F
T
t
a
s
k
m
+
c
m
,
i
E
F
T
t
a
s
k
i
,
V
e
h
p
=
w
t
i
,
p
+
E
S
T
t
a
s
k
i
,
V
e
h
p
,where a
v
a
i
l
[
p
]is the ready time of the vehicle V
e
h
p to execute t
a
s
k
i for the situation that there has been a task assigned to the vehicle before task t
a
s
k
i and p
r
e
d
(
t
a
s
k
i
) is the set of immediate predecessor tasks of the taskt
a
s
k
i. In order to start the execution of the task t
a
s
k
i, all immediate predecessor tasks must have been finished. After the task t
a
s
k
m is assigned to the vehicle V
e
h
j, the EST and the EFT of the next task are set to be equal to the AST and the AFT, respectively.


### 5.4. The Fitness Function

In order to suffice the real-time requirement of a service, it must set a deadline for the total service execution time. If the computing resources of the local on-board computer are insufficient to finish the execution before the deadline, the users have to offload the tasks to the VC. It can optimize the total service execution time by using better allocation schedule. However, the first aim of our paper is to guarantee the safety of the service. So, our resource allocation is to minimize the total service fail probability under the constraint of the total execution time. It can improve the safety of the VCC by increasing the reliability of the resource during the service generation process.(27)
L
F
T
t
a
s
k
e
x
i
t
=
D
e
a
d
l
i
n
e
L
F
T
t
a
s
k
i
=
min
tas
k
j
∈
succ
tas
k
j
⁡
L
F
T
t
a
s
k
j
-
w
t
i
,
s
-
c
i
,
j
,
s
,
r
.D
e
a
d
l
i
n
e is the deadline for the exit task t
a
s
k
e
x
i
t as well as the whole workflow. According to the deadline for the whole service, the LFT can be seen as the deadline for each task. The LFT can be calculated in (27).The aim of our schedule is to minimize the probability of service fail due to the connection fault of vehicle resources in VC and promise that all the tasks can be finished before deadline. The fitness function can be formulated as follows:(28)
A
F
T
t
a
s
k
i
,
V
e
h
p
≤
L
F
T
t
a
s
k
i
,
a
t
∀
i
min
⁡
P
t
o
t
a
l
.


### 5.5. Prediction-Based Reliability Maximization Algorithm (PRMA)

In fact, the heuristic algorithm has been used widely to solve the optimization problems of the workflow [33, 34]. The heuristic algorithm is always used to find the locally optimal solution or suboptimal solution. The proposed safety resource allocation mechanism is also based on the workflow theory, so the heuristic algorithm can be used to solve the optimization problem in the proposed mechanism.In this paper, we use the principle of greedy algorithm, which is one kind of heuristic algorithms. The proposed algorithm follows making the choice which has the locally minimized probability at each task assignment with the hope of finding a global minimizedP
t
o
t
a
l. The service fail probability of each vehicle depends on the states of the vehicle and the environment at some moment. It is difficult to make a global decision because it lacks the future information of the vehicle and environment. Therefore, all the decisions should be made locally in the time domain. Thus, the proposed algorithm uses the principle of making locally optimal choice to reduce the value of P
t
o
t
a
lat most. In addition, to decrease the probability of the optimized result becoming the locally minimized probability, the randomized greedy approach is widely used [35, 36]. The proposed algorithm selects randomly some other vehicles besides the vehicle with minimized probability. The vehicle with the minimized probability and aforementioned random vehicles are all selected as the candidate destinations of task assigning. Then, in the vehicular communication fault probability computation, the probabilities of each vehicle under different parent vehicles will be computed, respectively. All the computed probabilities will be compared together. After that, the vehicle which leads to the temporary minimized service fail probability and some random vehicles will be selected as the candidate task assigning destinations. The above process will go on until the last task in the task sequence is assigned. The whole process can decrease the possibility of the optimized result being trapped in the local optimization by randomized algorithm. Before that, the AFT of this task has to be less than the LFT to ensure the whole service can be finished before the deadline. So, the algorithm we proposed, PRMA, is shown in Algorithm 1. In this algorithm, the number of the aforementioned random vehicles is set to two, for example. The number n of the symbols A
n, B
n, and C
n refers to the order number of the task in the task sequence and n
+
1 refers to the next task that will be assigned.Algorithm 1:The PRMA.
(
1
) Input the computation cost of tasks, communication cost of edges with average value and the Deadline of this service.
(
2
) Calculate LFT of each task, starting from the exit task.
(
3
) Compute r
a
n
k
u for each task by DAG, starting from the exit task.
(
4
) Sort the tasks in a sequence by non-increasing order of r
a
n
k
u value.
(
5
)  For each task in the sequence order sorted at step (
3
)  do
(
6
)  For in the condition of each vehicle (the optimized vehicle A
n and two other random vehicles B
n and C
n) chosen at the last loop do
(
7
) Calculate the AFT of this task allocated to every available vehicle in the VC.
(
8
) If AFT of task on one vehicle smaller than the LFT.
(
9
) Calculate P
t
o
t
a
l for the vehicle in the condition that the last loop chosen vehicle is A
n, B
n or C
n.
(
10
)  End If
(
11
)  End For
(
12
) Choose the vehicle A
n
+
1 which has the minimum probability to occur connection fault at that moment from all the vehicles as the branches of three vehicles chosen from last loop and other two random vehicles B
n
+
1 and C
n
+
1 as the allocation destination of this task.
(
13
)  End For


## 5.1. The Fundamental Workflow Schedule

We can firstly assume that there areM tasks that need to be allocated and N vehicles prepare to accept task at that moment. To indicate the allocation schedule, let the matrix X be an M
×
N binary matrix corresponding to the schedule of M tasks into the N vehicle on-board computers. In this matrix, the element X
i
j
=
1, if the task t
a
s
k
iis assigned to the vehicle V
e
h
j and X
i
j
=
0 otherwise.E
t
t
o
t
a
l
p represents the actual execution time for multitasks on the particular vehicle V
e
h
p. E
t
t
o
t
a
l
p is different from the summation of E
t
t
o
t
a
l due to the fact that tasks which have dependence with each other could be allocated to the same vehicle. Therefore, the execution result of the parent task is unnecessary to be transferred to other vehicles. It reduces the total execution time E
t
t
o
t
a
l
p of the whole service.(17)
E
t
t
o
t
a
l
p
≤
∑
E
t
i
.We can defineE
t
t
o
t
a
l
p as follows: Firstly, the relationship of the tasks assigned to the vehicle V
e
h
p can be shown in the matrix X. The p
t
h row in X shows that the task t
a
s
k
i is assigned to this vehicle when x
i
p
=
1. we define a new matrix Y
p to represent the possible dependence between the tasks allocated to vehicle V
e
h
p:(18)
y
i
1
i
2
=
x
i
1
p
x
i
2
p
i
1
≠
i
2
y
i
1
i
2
=
0
i
1
=
i
2
,where 1
≤
i
1
,
i
2
≤
M, and y
i
1
i
2 is the element in the matrixY
p
.The actual dependence between the tasks is shown in the setE
=
{
e
(
t
a
s
k
i
,
t
a
s
k
j
)
∣
t
a
s
k
i
,
t
a
s
k
j
∈
T
A
S
K
}, and it can be transferred to a matrix E, and the element e
i
j
=
1 when e
(
t
a
s
k
i
,
t
a
s
k
j
) existed in the set E.So, the actual existing dependence between the tasks assigned to the vehicleV
e
h
p which is named as E
a
c
t
p and the element in it can be indicated as e
i
j
a
c
t:(19)
E
a
c
t
p
=
Y
p
·
E
.So,E
t
t
o
t
a
l
p can be calculated by the following equation:(20)
E
t
t
o
t
a
l
p
=
∑
i
=
1
M
x
i
p
E
t
i
-
∑
i
∑
j
e
i
j
a
c
t
d
o
i
T
p
u
p
+
d
i
j
T
p
d
o
w
n
.


## 5.2. Priority Classification of Tasks

After the derivation ofE
t
t
o
t
a
l
p, to design a workflow schedule, we need to determine the priority compartment for each task to confirm the execution order of these tasks. In this paper, we determine these parameters according to the dependence of each task in the workflow. Then, due to the deadline of the service, we have to separate it into each task to find out the Earliest Starting Time (EST), Earliest Finishing Time (EFT), Latest Finishing Time (LFT), Actual Starting Time (AST), and Actual Finishing Time (AFT) of each task. At last, we can find out the allocation strategy under the task priority and time constraint.At the beginning, we have to consider some definition used in the following priority computation. In (7), w
t refers to the computing time cost of a task which is executed on a vehicle. Therefore, this result can be extended to all the combinations of the tasks and vehicles. A matrix W
M
×
N is set to store the computing time cost, where M is the number of tasks and N is the number of the vehicles. The element w
t
i
,
j in the matrix refers to computing time cost of t
a
s
k
i assigning to V
e
h
j. So, we can get the average execution time for each task:(21)
w
¯
t
i
=
∑
j
=
1
N
w
t
i
,
j
N
.The average communication cost for the edgee
=
{
(
t
a
s
k
i
,
t
a
s
k
j
)
∣
t
a
s
k
i
,
t
a
s
k
j
∈
T
A
S
K
} can be inferred from (8):(22)
c
¯
i
,
j
=
L
¯
+
d
i
,
j
T
V
¯
,where T
V
¯ is the average transfer rate among the vehicles in the VC and L
¯ is the average communication startup time cost.According to [31], the task can be classified into simple task and synchronization task. The task has more than one parent task or its child task is the synchronization task. Otherwise, this task is the simple task. The simple tasks executed between two synchronization tasks are called branches. We can set the same deadline for the several branches between two synchronization tasks.According to [32], the upward rank of a task t
a
s
k
i is recursively defined as(23)
rank
⁡
t
a
s
k
i
=
w
¯
t
i
+
max
tas
k
j
∈
succ
tas
k
i
⁡
c
¯
i
,
j
+
rank
⁡
t
a
s
k
j
,where s
u
c
c
(
t
a
s
k
i
) is the set of immediate successors of task t
a
s
k
i, c
¯
i
,
j is the average communication time cost of edge e
(
t
a
s
k
i
,
t
a
s
k
j
), and w
¯
t
i is the average computing time cost of task t
a
s
k
i. And the upward rank starts from the exit task t
a
s
k
e
x
i
t. The rank value of the exit task is determined by the following equation:(24)
rank
⁡
t
a
s
k
e
x
i
t
=
w
¯
t
e
x
i
t
.So, we can transfer the DAG which is used to describe the task execution time sequence into the rank value for each task to represent its execution time sequence.


## 5.3. Task Execution Deadline Schedule

The EST, EFT, and LFT attributes need to be defined. The EST for entry taskt
a
s
k
e
n
t
r
y can be indicated as follows:(25)
E
S
T
t
a
s
k
e
n
t
r
y
,
V
e
h
p
=
0
.Based on the EST for entry task, the EST, EFT, and LFT values for other tasks are shown in the following equations:(26)
E
S
T
t
a
s
k
i
,
V
e
h
p
=
max
⁡
a
v
a
i
l
p
,
max
tas
k
m
∈
pred
tas
k
i
⁡
A
F
T
t
a
s
k
m
+
c
m
,
i
E
F
T
t
a
s
k
i
,
V
e
h
p
=
w
t
i
,
p
+
E
S
T
t
a
s
k
i
,
V
e
h
p
,where a
v
a
i
l
[
p
]is the ready time of the vehicle V
e
h
p to execute t
a
s
k
i for the situation that there has been a task assigned to the vehicle before task t
a
s
k
i and p
r
e
d
(
t
a
s
k
i
) is the set of immediate predecessor tasks of the taskt
a
s
k
i. In order to start the execution of the task t
a
s
k
i, all immediate predecessor tasks must have been finished. After the task t
a
s
k
m is assigned to the vehicle V
e
h
j, the EST and the EFT of the next task are set to be equal to the AST and the AFT, respectively.


## 5.4. The Fitness Function

In order to suffice the real-time requirement of a service, it must set a deadline for the total service execution time. If the computing resources of the local on-board computer are insufficient to finish the execution before the deadline, the users have to offload the tasks to the VC. It can optimize the total service execution time by using better allocation schedule. However, the first aim of our paper is to guarantee the safety of the service. So, our resource allocation is to minimize the total service fail probability under the constraint of the total execution time. It can improve the safety of the VCC by increasing the reliability of the resource during the service generation process.(27)
L
F
T
t
a
s
k
e
x
i
t
=
D
e
a
d
l
i
n
e
L
F
T
t
a
s
k
i
=
min
tas
k
j
∈
succ
tas
k
j
⁡
L
F
T
t
a
s
k
j
-
w
t
i
,
s
-
c
i
,
j
,
s
,
r
.D
e
a
d
l
i
n
e is the deadline for the exit task t
a
s
k
e
x
i
t as well as the whole workflow. According to the deadline for the whole service, the LFT can be seen as the deadline for each task. The LFT can be calculated in (27).The aim of our schedule is to minimize the probability of service fail due to the connection fault of vehicle resources in VC and promise that all the tasks can be finished before deadline. The fitness function can be formulated as follows:(28)
A
F
T
t
a
s
k
i
,
V
e
h
p
≤
L
F
T
t
a
s
k
i
,
a
t
∀
i
min
⁡
P
t
o
t
a
l
.


## 5.5. Prediction-Based Reliability Maximization Algorithm (PRMA)

In fact, the heuristic algorithm has been used widely to solve the optimization problems of the workflow [33, 34]. The heuristic algorithm is always used to find the locally optimal solution or suboptimal solution. The proposed safety resource allocation mechanism is also based on the workflow theory, so the heuristic algorithm can be used to solve the optimization problem in the proposed mechanism.In this paper, we use the principle of greedy algorithm, which is one kind of heuristic algorithms. The proposed algorithm follows making the choice which has the locally minimized probability at each task assignment with the hope of finding a global minimizedP
t
o
t
a
l. The service fail probability of each vehicle depends on the states of the vehicle and the environment at some moment. It is difficult to make a global decision because it lacks the future information of the vehicle and environment. Therefore, all the decisions should be made locally in the time domain. Thus, the proposed algorithm uses the principle of making locally optimal choice to reduce the value of P
t
o
t
a
lat most. In addition, to decrease the probability of the optimized result becoming the locally minimized probability, the randomized greedy approach is widely used [35, 36]. The proposed algorithm selects randomly some other vehicles besides the vehicle with minimized probability. The vehicle with the minimized probability and aforementioned random vehicles are all selected as the candidate destinations of task assigning. Then, in the vehicular communication fault probability computation, the probabilities of each vehicle under different parent vehicles will be computed, respectively. All the computed probabilities will be compared together. After that, the vehicle which leads to the temporary minimized service fail probability and some random vehicles will be selected as the candidate task assigning destinations. The above process will go on until the last task in the task sequence is assigned. The whole process can decrease the possibility of the optimized result being trapped in the local optimization by randomized algorithm. Before that, the AFT of this task has to be less than the LFT to ensure the whole service can be finished before the deadline. So, the algorithm we proposed, PRMA, is shown in Algorithm 1. In this algorithm, the number of the aforementioned random vehicles is set to two, for example. The number n of the symbols A
n, B
n, and C
n refers to the order number of the task in the task sequence and n
+
1 refers to the next task that will be assigned.Algorithm 1:The PRMA.
(
1
) Input the computation cost of tasks, communication cost of edges with average value and the Deadline of this service.
(
2
) Calculate LFT of each task, starting from the exit task.
(
3
) Compute r
a
n
k
u for each task by DAG, starting from the exit task.
(
4
) Sort the tasks in a sequence by non-increasing order of r
a
n
k
u value.
(
5
)  For each task in the sequence order sorted at step (
3
)  do
(
6
)  For in the condition of each vehicle (the optimized vehicle A
n and two other random vehicles B
n and C
n) chosen at the last loop do
(
7
) Calculate the AFT of this task allocated to every available vehicle in the VC.
(
8
) If AFT of task on one vehicle smaller than the LFT.
(
9
) Calculate P
t
o
t
a
l for the vehicle in the condition that the last loop chosen vehicle is A
n, B
n or C
n.
(
10
)  End If
(
11
)  End For
(
12
) Choose the vehicle A
n
+
1 which has the minimum probability to occur connection fault at that moment from all the vehicles as the branches of three vehicles chosen from last loop and other two random vehicles B
n
+
1 and C
n
+
1 as the allocation destination of this task.
(
13
)  End For


## 6. Evaluations

We simulate the process of the tasks assigned to the vehicles. In the simulation, the service executed in the VCC is invariable. It means that the relationship among the tasks is confirmed before the simulation beginning. Therefore, the degrees of tasks, which are used to indicate the number of their children tasks, are constants in the simulation. However, there are also some random parameters in the simulation. Vehicles have different velocities, travel distances, communication capabilities, and computational capabilities. In addition, each task composing the service has different random parameters, such as the amount of the communication data and workload. Due to the complexity of the real vehicular and traffic environment, we present the range of the parameters in our simulation for the algorithms as a matter of experience as in Table1.Table 1
The range of the parameters values in simulation.
Parameter
Value
Unit
Vehicle number
5~30
/
Task number
30
/
Degrees for each task
0~3
/
Workload
20~70
MI
Computing capability
5~10
MIPS
Communication capability
7~13
Mbps
Average communication startup time cost
3
s
λ
1
0.9
×
10
-
5
~
1.1
×
10
-
5
/
λ
2
0~10−4
/
λ
3
0.05
/
Velocity
10~20
m/s
Communication data
1~40
Mb
Travel distance
0~100
Km
Distance to radio boundary
4000~6000
m
Service fail probability
0~1
/First, to get a better value of the deadline for workflow allocation schedule, we simulate the execution using the Heterogeneous-Earliest-Finish-Time (HEFT) Algorithm, which is the well-known makespan minimization algorithm. It is an application scheduling algorithm for a bounded number of heterogeneous processors to schedule each selected task on its “best” processor, which minimizes the task’s execution time [32]. The execution time of the service using the HEFT schedule is used as the parameter of the deadline calculation in our workflow schedule.(29)
D
e
a
d
l
i
n
e
=
α
·
E
t
H
E
F
T
,where α is a factor and it is always set in the range from 1.5 to 5 [37]. We assume α
=
1.5 in our simulation.The average execution time of algorithm HEFT and PRMA is shown in Figure8. It is the average value of 20 times simulations and each time uses the new random parameters. As can be seen, the execution time of PRMA is smaller than 1.5 times of the value of HEFT which is set as the deadline for the service accomplishment using PRMA. In other words, the PRMA can suffice the requirement with the constraint of deadline. On the other hand, with the increase of the number of vehicles, which means the sufficiency of computing resources, the average execution time of the whole service is decreased from 135.7 s to 118.2 s (HEFT) and from 181.5 s to 150.6 s.Figure 8
Average execution time for whole service depends on vehicle numbers.The service fail probability can be calculated by (12). We also use the vehicle connection fault probability model to calculate the service fail probability of HEFT as a contrast. The comparison between two algorithm service fail probabilities of V2V is shown in Figure 9. We can see that the service fail probability of PRMA is much smaller than HEFT. The probability of HEFT is about 4.9% and the probability of PRMA is about 2%. With the increase of the number of vehicles, which means the task allocation destination has more choices, the probability of PRMA shows the decreasing trend from 2.04% to 0.80%. However, the probability of HEFT does not show this trend because its resources allocation is based on makespan minimization which is a random value on the vehicle connection fault probability. In addition, the scenario of V2I is also simulated. The number of vehicles in V2I scenario is much larger than V2V. The changes of the service fail probability are less than 0.1% when the number of vehicles increases from 100 to 200. This is because the task allocation destination has enough choices and the increase of vehicle numbers has no obvious influence on the result.Figure 9
Average service fail probability depends on vehicle numbers.Figures10 and 11 show that the average service fail probability depends on vehicle velocity in V2I and V2V, respectively. In V2I scenario, the service fail probability of PRMA increases from about 0.45% to 21.4% when the mean value of the vehicle velocity increases from 5 m/s (18 km/h) to 30 m/s (108 km/h). And the probability of HEFT increases from about 3.7% to 35.2% in the same condition. The increase rate of HEFT is larger than the increasing rate of our scheme because the vehicles, which have a higher velocity, have a higher possibility to leave the RSUs signal area than the low-velocity vehicles during the same time.Figure 10
Average service fail probability depends on vehicle velocity in V2I.Figure 11
Average service fail probability depends on vehicle velocity in V2V.Figure12 shows that the average service fail probability depends on communication capability in V2I and V2V, respectively. We can see that the probabilities decrease with the increase of the communication capability mean value in these two scenarios. In V2I scenario, the service fail probability of PRMA decreases from about 13.4% to 7% when the mean value of communication capability increases from 5 Mbps to 30 Mbps. In V2V scenario, this parameter decreases from about 1.57% to 0.96%. All of them are smaller than the values of HEFT. The communication time cost is one of the main components of the service total execution time. The increase of the communication capability is one of the main causes which lead to the reduction of the service execution time. Thus, according to (9), (14), and (15), the service fail probability will decrease.Figure 12
Average service fail probability depends on communication capability.In summary, we can conclude that the PRMA can increase the reliability of the VCC during the service execution duration and suffice the requirement of deadline constraint.


## 7. Conclusions

The vehicle connection fault issue will lead to the service failure of VCC in ITS, which makes the transportation unsafe. To address this challenge, a safety resource allocation mechanism against the connection fault for VCC was proposed in this paper. In this mechanism, the connection fault probability models of the vehicles traveling on the road were built and they were used to predict the vehicle connection fault probability according to the real-time monitoring data from the VC. After that, the prediction results can be used by the workflow schedule to improve the reliability of the task assignment. An heuristic algorithm PRMA which is based on the greedy algorithm and task priority calculation method were proposed to minimize the probability of connection fault. Thus VCC can complete the service before the deadline to suffice the real-time requirement of the services in ITS. Evaluations show that our mechanism can improve the reliability and real-time performance of VCC. The future work is to optimize the prediction model of vehicle connection fault probability. In the real traffic environment, many other factors also will lead to the communication fault, such as the radio shielding by the building and the fluctuation of the terrain. All these factors could be considered in the future to make the prediction model more precise. The heuristic algorithm also can be optimized in the aspect of improving the balance between the computational complexity and the optimized results.



---

*Source: 2747808-2016-11-29.xml*