# Research on the Edge Resource Allocation and Load Balancing Algorithm Based on Vehicle Trajectory

Authors: Shuxu Zhao; Xinyuan Chen; Xiaolong Wang
Journal: Complexity
 (2022)

---

## Abstract

Edge computing empowers the IoV to achieve performance requirements such as low latency and high computational load for in-vehicle services. However, the driving of vehicles is random and unevenly distributed, causing problems such as unbalanced load of edge servers and low edge resource utilization. Therefore, in this article, based on the vehicle trajectories, the edge resource allocation algorithm and load balancing algorithm are used to obtain the load prediction value of the edge server and then calculate the optimal edge resource quantity in order to reduce the resource idleness as much as possible. The experiments demonstrate that the application of the edge resource allocation algorithm and load balancing algorithm based on vehicle trajectory significantly reduces the blocking rate of edge resource requests by vehicles and improves the benefits of the overall IoV edge system.


---

## Body

## 1. Introduction

The Internet of vehicles (IoV) has emerged as a fundamental technique that substantially pushes forward the development of intelligent transportation [1]. The automotive applications that significantly benefit people’s daily activities are increasingly abundant, such as accurate localization, green travel priority plan query, driving judgment, and entertainment information. This may lead to a considerable amount of data and inefficient service quality. With the increasing growth of built-in sensors and actuators, vehicles cannot fulfill the incremental information processing transmitted from the surrounding environment. In general, the IoV services are most delay-sensitive, while vehicles are not integrated with enough computing resources to meet the real-time requirements, leading to the high traffic demands from vehicles to the cloud center. However, the option of requesting to the distal cloud may contribute to the congested backhaul link and unstable connections [2]. As one of the key enabling technologies in the 5G era, the edge computing technology can reduce the cloud computing load and data processing delay by deploying sufficient computing resources as well as adequate storage capacities in the proximity of vehicles. With the configuration of EC, the IoV services can be offloaded to the ENs rather than the remote cloud center, and the transmission latency resulting from the cloud is reduced [3]. However, how much edge resources to deploy is a question, due to the high cost and limited amount of resources deployed at the edge. Therefore, designing an efficient edge resource allocation and selection algorithm will help improve the success rate of the vehicle’s request for edge resources.The authors in [4] propose a proactive resource allocation approach, in which all the cells that are one-hop away from the current cell will be provisioned with resources. The authors in [5] propose to allocate resources to a subset of neighboring cells, in which each cell is marked with different weight values that indicate the handover probability. In [6, 7], a load balancing algorithm between different cells is proposed. This algorithm uses the queueing theory and iterative methods to find the task redirection flow from an overloaded edge server to an unloaded edge server and alleviate the randomness of vehicle driving caused by the unbalanced loads among edge servers and the low resource utilization. In order to incorporate the spatial information of QoS into data prediction and recommendation, the study presented in [8] puts forward a location-aware nonnegative tensor factorization technique, in which a location stamp is attached to each piece of QoS data. The location-aware personalized CF method proposed in [9] leverages both locations of users and web services when selecting similar neighbors for the target user or service. The authors in [10] propose an optimization framework based on stochastic traffic analysis, to minimize the cost of resource provisioning under the premise of ensuring that the service blocking probability is less than a predefined threshold, in order to improve the utilization rate of edge resources. In [11], a citywide and real-time model is proposed for estimating the travel time of any path (represented as a sequence of connected road segments) in real time in a city, based on the GPS trajectories of vehicles received in current time slots and over a period of history, as well as map data sources. In [12, 13], the authors show that each edge server can retrieve data from other edge servers to serve users with a low latency guarantee when another edge server maintains relatively adequate resources in the same area. The authors in [14] propose a selection algorithm between vehicles and edge nodes based on mobile information, server available resources, and Quality of Service (QoS) conditions of service. The algorithm sorts these edge servers around the vehicle based on distance and service delay, in order to reduce the response delay at the edge system of the IoV. Referring to [15], a powerful way to reduce the completion time of a request in the mobile edge environment is to offload its tasks to nearby cloudlets, which consist of clusters of computers. The authors in [16] propose the edge resource allocation algorithm based on the improved vehicle trajectory prediction, the and traffic statistics method is used to obtain the load prediction value of the edge server; then, the optimal number of edge resources is calculated on the premise of reducing resource idleness as much as possible. The authors in [17] propose the task offloading problem from a matching perspective and aim to optimize the total network delay and a pricing-based one-to-one matching algorithm and pricing-based one-to-many matching algorithms for the task offloading. Three load sharing schemes, namely, no sharing, random sharing, and least loaded sharing, are mentioned in [18], which exploit the collaboration between clustered servers in different degrees, and the simulation experiment is conducted by queuing theory.However, these methods do not integrate the calculation of minimum edge resources with the load balancing among edge nodes. In order to incorporate the keeping of QoS into the allocation and selection methods of IoV edge resources, it is challenging to achieve the trade-offs between reducing the expenditure of edge servers and maximizing the success rate of requesting to edge server by connected vehicle. This article is the first attempt to adjust the optimal edge resource in each edge node. The main contributions are summarized as follows:(i)
An optimization framework is developed in order to minimize the cost of configuring edge resources to compute the minimum amount of edge resources in each cell and in each period, while the service blocking probability is guaranteed to be smaller than a predefined threshold(ii)
A novel method is proposed for adjusting the load balancing of different edge servers and making a distribution of the minimum amount of resource among these edge servers, in order to improve the overall benefits of the edge system of the IoV(iii)
An algorithm is developed for connected vehicles to select edge nodes, and then, a set of experiments are performed to evaluate the validity and efficiency of the edge resource allocation and selection method based on vehicle trajectory prediction


## 2. Model of the Edge Computation System for IoVs

In order to show the operational process in IoVs, this article assumes the model of edge computation system for IoV as shown in Figure1. The model is a three-layer architecture, generally including a user layer (data generation), edge layer (data filtering and decision-making), and cloud layer (data fusion, analysis, and macroadjustment).Figure 1
Model of the edge computation system in IoV.In Figure1, the vehicle moves among different adjacent cells. In each cell, there is an amount of edge devices configured servicing passing vehicles covered by the cell, such as roadside base stations (RSU, distributed on both sides of the road) and edge servers. The cloud computing center monitors and adjusts all the operational processes of edge services in all the cells. When a vehicle will soon leave cell A to cell B, the wireless connection between the vehicle and a road site unit (RSU) in cell A interrupts when the connection to B is built.


## 3. Trajectory Prediction Based on Historical Trajectory Data

Assume a working day is divided into a sequence of periods at equal intervals, whereT is the total number of periods. In the interactive environment between the actual vehicle and edge system, the GPS trajectory data can be obtained by the real-time navigation and positioning system, and the future trajectory is predicted based on the fine-grained GPS trajectory data, in order to obtain the movement prediction of the vehicle between different communities. The geometric method is used to predict in advance the location of the vehicle at the beginning of the next period, based on the vehicle’s location, speed, and direction:(1a)Snt=S1t,S2t,…,SNt,(1b)SFnt=SF1t,SF2t,…,SFNt.Since the number of vehicles covered by a cell in different periods is changing, in order to facilitate the comparison between the experimental prediction results and actual results, the fleet distribution vector is defined asSnt0<n≤N;0<t≤T and the vehicle-mounted distribution vector is denoted by SFnt0<n≤N;0<t≤T. They are introduced in equations (1a) and (1b), which represents the actual number of vehicles and the total on-board capacity of vehicles at the beginning of period t covered by cell n, usually determined by the GPS positioning system. Note that N denotes the total number of cells divided in the area:(2a)Ht≔H1,1tH1,2t⋯H1,NtH2,1tH2,2t⋯H2,Nt⋮⋮⋱⋮HN,1tHN,2t⋯HN,Nt,(2b)HF⋮≔HF1,1tHF1,2t⋯HF1,NtHF2,1tHF2,2t⋯HF2,Nt⋮⋮⋱⋮HFN,1tHFN,2t⋯HFN,Nt.In this article, based on the trajectory prediction of GPS trajectory data, the fleet mobility prediction matrix and vehicle-mounted mobility prediction matrix are obtained, as shown in equations (2a) and (2b), where Hi,jt is the number of vehicles transferring from cell i to cell j in period t, and HFi,jt represents the vehicle-mounted capacity of moving from cell i to cell j in period t, which is convenient to distribute requests among vehicle RSU and Cloudlet.


## 4. Analysis of Vehicle Arriving and Leaving

Based on the fleet mobility matrix obtained in Section3, in order to improve the success rate of the vehicle requesting edge resources in the actual situation, it is necessary to estimate the time point when vehicle v removes from cell n to the neighboring cell n′ (i.e., the time when the vehicle reaches the cell boundary). Since it is almost impossible to accurately estimate the vehicle’s travel time, this article uses the probability distribution function of the arrival time, which represents the probability distribution of the arrival time of the vehicle from the perspective of probability [14]. Similarly, the probability distribution function of the departure time of the vehicle is used to represent the probability distribution of the departure time of the vehicle.


### 4.1. Analysis of Vehicle Arriving Flow and Leaving Flow

Pn,tarr and Pn,tdep represent the probability distribution of the arrival time entering cell n and the probability distribution of the departure time leaving cell n of a vehicle in period t, respectively. In this article, the normal distribution is used to represent the probability distribution of the arrival time and departure time, as shown in Figure 2. In fact, based on the fleet mobility matrix H (cf. Section 3), the number of vehicles accounts for the majority in period t when arriving at cell n, and a small number of vehicles do not arrive according to the results given by the vehicle trajectory prediction model.Figure 2
Probability distribution of the arrival/departure time of vehicles in celln.Assuming that the arrival time of all the vehicles arriving in celln in period t follows the same normal distribution, the expected number of vehicles arriving in cell n during period t is denoted by λnt. The computation is shown in the following equation: (3)λnt=0,M=0,∑k=1M∫tt+1Pn,tarrtdt,M≠0,where each integral represents the probability of each vehicle arriving at cell n in period t, and M=∑i=1,i≠nNHi,nt.Similarly, the expected number of vehicles leaving celln during period t is denoted by μnt: (4)μnt=0,M=0,∑k=1M∫tt+1Pn,tdeptdt,M≠0,where each integral represents the probability of each vehicle leaving cell n in period t, and M=∑j=1,j≠nNHn,jt.As the vehicles arrive and leave, the number of vehicles covered by a cell is changing. The expected arrival/departure number of vehicles cannot be directly used to calculate the optimal number of edge resources for each cell. Because the calculated expected average does not take into account all the possible values, if the actual number of vehicles arriving in celln exceeds the expected average value, some vehicles may fail to request the edge resources of cell n.


### 4.2. Dynamic Analysis of Traffic Flow

Due to complex traffic conditions, different driving habits of different drivers and human subjective factors, it is inevitable that the vehicles will have high mobility problems. In fact, it is difficult to accurately calculate the number of resources that the edge devices need to provide. Even a big gap exists between the estimated number of vehicles covered by a cell and the actual number. In order to analyze the flow of vehicles arriving and leaving celln at period t, the vehicle arriving and leaving flows are modeled as Poisson processes, in which the parameters of the two Poisson processes are λnt and μnt, respectively.


#### 4.2.1. Vehicle Arriving Flow

A random variableDnt is defined in period t indicating the number of vehicles arriving at cell n, and aiming at considering the number of all the possible values, as shown in the following equation: (5)PDntx=λntxe−λntx!,such that 0≤x≤Bˇnt, where Bˇnt represents the maximum possible number of vehicles during period t arriving at cell n, which is usually the upper bound of Dnt. The calculation formula is shown in the following equation:(6)B⌣nt=∑i=1,i≠nNHi,nt.


#### 4.2.2. Vehicle Leaving Flow

A random variableUnt is defined in period t indicating the number of vehicles leaving from cell n, and aiming at considering the number of all the possible values, as shown in the following equation:(7)PUntx=μntxe−μntx!,such that 0≤x≤B^nt, where B^nt represents the maximum possible number of vehicles during period t leaving from cell n, which is usually the upper bound of Unt. The calculation formula is shown in the following equation:(8)B⌢nt=∑j=1,j≠nNHn,jt.


#### 4.2.3. Vehicle Composite Flow

A random variableRnt is defined to consider both the arriving flow and leaving flow while representing the difference between the number of arriving vehicles and the number of leaving vehicles at period t in cell n (cf. equation (9)). It indicates that the required number of edge resources is greater than the number of edge resources to be released.(9)Rnt=Unt−Dnt.In order to consider all the possible values, a joint probability distribution functionRnt is defined to represent the probability distribution of the difference between two independent streams. It is expressed in the following equation:(10)PRntx=∑k=0B⌢ntPUntDntk,k+x,where 0≤x≤Bˇnt.(11)PRntx=∑k=0B⌢ntPUntkPDntk+x.Within a short period of time in celln, the arriving flow can be considered independent of the leaving flow. Therefore, equation (11) can be derived from equation (10).


## 4.1. Analysis of Vehicle Arriving Flow and Leaving Flow

Pn,tarr and Pn,tdep represent the probability distribution of the arrival time entering cell n and the probability distribution of the departure time leaving cell n of a vehicle in period t, respectively. In this article, the normal distribution is used to represent the probability distribution of the arrival time and departure time, as shown in Figure 2. In fact, based on the fleet mobility matrix H (cf. Section 3), the number of vehicles accounts for the majority in period t when arriving at cell n, and a small number of vehicles do not arrive according to the results given by the vehicle trajectory prediction model.Figure 2
Probability distribution of the arrival/departure time of vehicles in celln.Assuming that the arrival time of all the vehicles arriving in celln in period t follows the same normal distribution, the expected number of vehicles arriving in cell n during period t is denoted by λnt. The computation is shown in the following equation: (3)λnt=0,M=0,∑k=1M∫tt+1Pn,tarrtdt,M≠0,where each integral represents the probability of each vehicle arriving at cell n in period t, and M=∑i=1,i≠nNHi,nt.Similarly, the expected number of vehicles leaving celln during period t is denoted by μnt: (4)μnt=0,M=0,∑k=1M∫tt+1Pn,tdeptdt,M≠0,where each integral represents the probability of each vehicle leaving cell n in period t, and M=∑j=1,j≠nNHn,jt.As the vehicles arrive and leave, the number of vehicles covered by a cell is changing. The expected arrival/departure number of vehicles cannot be directly used to calculate the optimal number of edge resources for each cell. Because the calculated expected average does not take into account all the possible values, if the actual number of vehicles arriving in celln exceeds the expected average value, some vehicles may fail to request the edge resources of cell n.


## 4.2. Dynamic Analysis of Traffic Flow

Due to complex traffic conditions, different driving habits of different drivers and human subjective factors, it is inevitable that the vehicles will have high mobility problems. In fact, it is difficult to accurately calculate the number of resources that the edge devices need to provide. Even a big gap exists between the estimated number of vehicles covered by a cell and the actual number. In order to analyze the flow of vehicles arriving and leaving celln at period t, the vehicle arriving and leaving flows are modeled as Poisson processes, in which the parameters of the two Poisson processes are λnt and μnt, respectively.


### 4.2.1. Vehicle Arriving Flow

A random variableDnt is defined in period t indicating the number of vehicles arriving at cell n, and aiming at considering the number of all the possible values, as shown in the following equation: (5)PDntx=λntxe−λntx!,such that 0≤x≤Bˇnt, where Bˇnt represents the maximum possible number of vehicles during period t arriving at cell n, which is usually the upper bound of Dnt. The calculation formula is shown in the following equation:(6)B⌣nt=∑i=1,i≠nNHi,nt.


### 4.2.2. Vehicle Leaving Flow

A random variableUnt is defined in period t indicating the number of vehicles leaving from cell n, and aiming at considering the number of all the possible values, as shown in the following equation:(7)PUntx=μntxe−μntx!,such that 0≤x≤B^nt, where B^nt represents the maximum possible number of vehicles during period t leaving from cell n, which is usually the upper bound of Unt. The calculation formula is shown in the following equation:(8)B⌢nt=∑j=1,j≠nNHn,jt.


### 4.2.3. Vehicle Composite Flow

A random variableRnt is defined to consider both the arriving flow and leaving flow while representing the difference between the number of arriving vehicles and the number of leaving vehicles at period t in cell n (cf. equation (9)). It indicates that the required number of edge resources is greater than the number of edge resources to be released.(9)Rnt=Unt−Dnt.In order to consider all the possible values, a joint probability distribution functionRnt is defined to represent the probability distribution of the difference between two independent streams. It is expressed in the following equation:(10)PRntx=∑k=0B⌢ntPUntDntk,k+x,where 0≤x≤Bˇnt.(11)PRntx=∑k=0B⌢ntPUntkPDntk+x.Within a short period of time in celln, the arriving flow can be considered independent of the leaving flow. Therefore, equation (11) can be derived from equation (10).


## 4.2.1. Vehicle Arriving Flow

A random variableDnt is defined in period t indicating the number of vehicles arriving at cell n, and aiming at considering the number of all the possible values, as shown in the following equation: (5)PDntx=λntxe−λntx!,such that 0≤x≤Bˇnt, where Bˇnt represents the maximum possible number of vehicles during period t arriving at cell n, which is usually the upper bound of Dnt. The calculation formula is shown in the following equation:(6)B⌣nt=∑i=1,i≠nNHi,nt.


## 4.2.2. Vehicle Leaving Flow

A random variableUnt is defined in period t indicating the number of vehicles leaving from cell n, and aiming at considering the number of all the possible values, as shown in the following equation:(7)PUntx=μntxe−μntx!,such that 0≤x≤B^nt, where B^nt represents the maximum possible number of vehicles during period t leaving from cell n, which is usually the upper bound of Unt. The calculation formula is shown in the following equation:(8)B⌢nt=∑j=1,j≠nNHn,jt.


## 4.2.3. Vehicle Composite Flow

A random variableRnt is defined to consider both the arriving flow and leaving flow while representing the difference between the number of arriving vehicles and the number of leaving vehicles at period t in cell n (cf. equation (9)). It indicates that the required number of edge resources is greater than the number of edge resources to be released.(9)Rnt=Unt−Dnt.In order to consider all the possible values, a joint probability distribution functionRnt is defined to represent the probability distribution of the difference between two independent streams. It is expressed in the following equation:(10)PRntx=∑k=0B⌢ntPUntDntk,k+x,where 0≤x≤Bˇnt.(11)PRntx=∑k=0B⌢ntPUntkPDntk+x.Within a short period of time in celln, the arriving flow can be considered independent of the leaving flow. Therefore, equation (11) can be derived from equation (10).


## 5. Traffic Flow Prediction Model

Based on the prediction of the future trajectory of the vehicle, forecasting based on historical traffic flow can improve the success rate of the vehicle requesting edge services. In this article, according to the traffic statistics of the vehicle trajectory data, the historical traffic flow of the vehicles exhibits specific laws, such as the periodic similarity and correlation of the traffic flow. The experimental part of the traffic flow statistics is presented in Section10.2. Although the short-term traffic flow has the characteristics of nonlinearity, uncertainty, and randomness, which brings certain difficulties to the prediction of the traffic flow, its characteristics such as periodic similarity, correlation, and self-organization are convenient for forecasting the traffic volume.


### 5.1. Characteristics of the Traffic Flow

#### 5.1.1. Periodic Similarity of the Traffic Flow

Due to the living habits of travelers, the overall traffic flow distribution presents specific laws. In addition, the traffic flow of some road sections has a high degree of similarity in two different periods.


#### 5.1.2. Correlation of the Traffic Flow

The correlation of the traffic flow in time is reflected by the fact that the traffic flow value of a community is affected not only by the previous period, but also by the traffic flow of the next period. The traffic flow value of a community in several consecutive periods shows a higher similarity.


#### 5.1.3. Self-Organization of the Traffic Flow

All the vehicles follow the same principle in driving, and they all hope to smoothly and quickly reach the destination in order to maximize the group benefits. This phenomenon is referred to as self-organization.


### 5.2. Traffic Flow Statistics

According to the cells where a vehicle appears at the beginning oft1, t2, and t3 in t, the traffic volume of each cell in t is counted. If a vehicle appears in the same cell at the beginning of the three small periods, only one vehicle is added to the cell. Otherwise, these cells where a vehicle occurs will be added. Using this method, the number of vehicles in each cell and in each period will be obtained.


### 5.3. Prediction of the Traffic Flow

Based on the characteristics of the traffic volumeRnt<0, the traffic volume value in period t of cell n is related to the statistical average value of the traffic volume of the continuous-time periods of the last week in cell n, the statistical average value of the traffic volume of the continuous-time periods of the previous day in cell n, and the statistical average value of the traffic volume of the recent continuous periods in a certain extent. Since the linear model can be easily modeled and has a high speed and stable operation, the prediction of the traffic volume is solved by the linear model as(12)ft,nxt,n=wn1xt,n,1+wn2xt,n,2+wn3xt,n,3+bn,xt,n,1=12k+1∑i=t−kt+kD1i,n,xt,n,2=12k+1∑i=t−kt+kD2i,n,xt,n,3=1k∑i=t−kt−1D3i,n,where the input is a vector xt,n=xt,n,1,xt,n,2,xt,n,3T, wn=wn1,wn2,wn3T represents three weight values, D1i,n denotes the traffic volume at period i in cell n of the last week, D2i,n is the traffic volume at period i in cell n on yesterday, D3i,n represents the traffic volume at period i in cell n on today, bn is a constant, k represents the length of the selected periods, and the output ft,nx denotes the estimated traffic volume in cell n during period t.In order to instantiate the linear model of traffic flow prediction, the dataset in the linear model is constructed using the traffic flow statistics of the vehicle GPS trajectory data used in this article. The optimal value ofwn and bn is then obtained using the least squares method. Finally, the generated model is applied to forecast the traffic volume at the next period on cell n based on the existing traffic volume records. In order to simplify the calculation, the dataset is represented by a matrix of Xn with U×4 size and a vector of yn with U×1 size, as shown in equations (13a) and (13b), with vector w^n=wn,bn absorbing wn and bn. The first three columns of each row in Xn are xt,n,1, xt,n,2, and xt,n,3 in different periods in cell n, and yi,n in yn corresponds to the actual traffic flow at period t in cell n:(13a)Xn=x1,n,1x1,n,2x1,n,31x2,n,1x2,n,2x2,n,31⋮⋮⋮⋮xT,n,1xT,n,2xT,n,31,(13b)yn=y1,n,y2,n,…,yT,n,(14)w^n∗=XnTXn−1XnTyn.Different weight vectorsw and the optimal value b for different cells are obtained using equation (14) and then substituted into equation (12) in order to predict the traffic flow of a cell in the next period, so as to improve the load prediction accuracy of the edge device.


## 5.1. Characteristics of the Traffic Flow

### 5.1.1. Periodic Similarity of the Traffic Flow

Due to the living habits of travelers, the overall traffic flow distribution presents specific laws. In addition, the traffic flow of some road sections has a high degree of similarity in two different periods.


### 5.1.2. Correlation of the Traffic Flow

The correlation of the traffic flow in time is reflected by the fact that the traffic flow value of a community is affected not only by the previous period, but also by the traffic flow of the next period. The traffic flow value of a community in several consecutive periods shows a higher similarity.


### 5.1.3. Self-Organization of the Traffic Flow

All the vehicles follow the same principle in driving, and they all hope to smoothly and quickly reach the destination in order to maximize the group benefits. This phenomenon is referred to as self-organization.


## 5.1.1. Periodic Similarity of the Traffic Flow

Due to the living habits of travelers, the overall traffic flow distribution presents specific laws. In addition, the traffic flow of some road sections has a high degree of similarity in two different periods.


## 5.1.2. Correlation of the Traffic Flow

The correlation of the traffic flow in time is reflected by the fact that the traffic flow value of a community is affected not only by the previous period, but also by the traffic flow of the next period. The traffic flow value of a community in several consecutive periods shows a higher similarity.


## 5.1.3. Self-Organization of the Traffic Flow

All the vehicles follow the same principle in driving, and they all hope to smoothly and quickly reach the destination in order to maximize the group benefits. This phenomenon is referred to as self-organization.


## 5.2. Traffic Flow Statistics

According to the cells where a vehicle appears at the beginning oft1, t2, and t3 in t, the traffic volume of each cell in t is counted. If a vehicle appears in the same cell at the beginning of the three small periods, only one vehicle is added to the cell. Otherwise, these cells where a vehicle occurs will be added. Using this method, the number of vehicles in each cell and in each period will be obtained.


## 5.3. Prediction of the Traffic Flow

Based on the characteristics of the traffic volumeRnt<0, the traffic volume value in period t of cell n is related to the statistical average value of the traffic volume of the continuous-time periods of the last week in cell n, the statistical average value of the traffic volume of the continuous-time periods of the previous day in cell n, and the statistical average value of the traffic volume of the recent continuous periods in a certain extent. Since the linear model can be easily modeled and has a high speed and stable operation, the prediction of the traffic volume is solved by the linear model as(12)ft,nxt,n=wn1xt,n,1+wn2xt,n,2+wn3xt,n,3+bn,xt,n,1=12k+1∑i=t−kt+kD1i,n,xt,n,2=12k+1∑i=t−kt+kD2i,n,xt,n,3=1k∑i=t−kt−1D3i,n,where the input is a vector xt,n=xt,n,1,xt,n,2,xt,n,3T, wn=wn1,wn2,wn3T represents three weight values, D1i,n denotes the traffic volume at period i in cell n of the last week, D2i,n is the traffic volume at period i in cell n on yesterday, D3i,n represents the traffic volume at period i in cell n on today, bn is a constant, k represents the length of the selected periods, and the output ft,nx denotes the estimated traffic volume in cell n during period t.In order to instantiate the linear model of traffic flow prediction, the dataset in the linear model is constructed using the traffic flow statistics of the vehicle GPS trajectory data used in this article. The optimal value ofwn and bn is then obtained using the least squares method. Finally, the generated model is applied to forecast the traffic volume at the next period on cell n based on the existing traffic volume records. In order to simplify the calculation, the dataset is represented by a matrix of Xn with U×4 size and a vector of yn with U×1 size, as shown in equations (13a) and (13b), with vector w^n=wn,bn absorbing wn and bn. The first three columns of each row in Xn are xt,n,1, xt,n,2, and xt,n,3 in different periods in cell n, and yi,n in yn corresponds to the actual traffic flow at period t in cell n:(13a)Xn=x1,n,1x1,n,2x1,n,31x2,n,1x2,n,2x2,n,31⋮⋮⋮⋮xT,n,1xT,n,2xT,n,31,(13b)yn=y1,n,y2,n,…,yT,n,(14)w^n∗=XnTXn−1XnTyn.Different weight vectorsw and the optimal value b for different cells are obtained using equation (14) and then substituted into equation (12) in order to predict the traffic flow of a cell in the next period, so as to improve the load prediction accuracy of the edge device.


## 6. Resource Allocation Model Based on QoS

Based on the traffic flow prediction model, the QoS model is proposed to achieve a certain degree of success rate of the requesting edge resources by the passing vehicles, according to actual application requirements. This section uses the fleet distribution vectorSt, fleet mobility matrix Ht, vehicle arriving λnt, and vehicle leaving μnt as input to cell n at period t, in order to predict the number of covered vehicles, and to divide the edge resource in each cell at the end of period t or the beginning of period t+1.


### 6.1. Prediction of the Vehicle Traffic Flow

Assuming that there areCnt−1 available edge resources contained in cell n at the beginning of period t, the probability of a request being blocked when the vehicle enters cell n from other cells is expressed in the following equation: (15)P∅|Cnt−1=0,Cnt−1≥B⌣nt,∑Cnt−1+1B⌣ntPRntx,else..where ϕ represents a blocking event.Some of the vehicles appear in celln at the beginning of period t, and stay in cell n during the entire period t. They will not make changes to the edge resources of the cell, because their edge resource requests have already been provisioned at the beginning of period t. It is demonstrated that these requests have been supplied by cell n, and maintain the supplement of edge resources at the beginning of period t +1. Considering the worst case, if all the entering vehicles are earlier than all the vehicles leaving in cell n at period t, the blocking rate of the edge resource request can be easily increased by directly configuring according to the edge resource configuration result obtained by equation (9).


### 6.2. Algorithm Improvement Based on the QoS Model

The estimated value ofCnt−1 should be determined at the beginning of t that has passed. In addition, the accuracy rate of the vehicle transfer prediction for the next period t+1 based on the vehicle trajectory records in period t is low. Therefore, the minimum number of edge resources of cell n at the end of period t or the beginning of period t+1 is predicted based on the predicted transfer situation of vehicles in period t and the distribution of the fleet at the beginning of period t:(16)P∅|Cnt−1≤ϵ.Therefore, the model based on QoS aims at computing the minimum number of edge resources of celln at the end of period t, so that equation (16) is developed, where ϵ is the user-defined service blocking rate, which represents the estimated blocking rate of the vehicle requesting edge resources.


### 6.3. Optimal Resource Allocation

Due to the fact that it is impossible to calculate the optimal value one by one in the case of large data volume, this article uses a grouping and binary search algorithm (two-stage algorithm) in order to calculate the minimum number of edge resources in periodt and in cell n. The corresponding pseudocode is shown in Algorithm 1.Algorithm 1: Two-stage algorithm.
Input: user-defined service blocking rateϵ, maximum capacity of edge device CmaxOutput: Optimal value of edge resourceCmin satisfied by (16)(1)
CL,CH←1(2)
whilePϕ|CH>ϵ:(3)
CL←CH(4)
CH←2×CH(5)
ifCH>Cmaxthen(6)
return false(7)
while True:(8)
Cmin←CL+CH/2(9)
ifPϕ|Cmin≤ϵ:(10)
CH←Cmin(11)
else:(12)
CL←Cmin(13)
ifCH−CL≤1:(14)
returnCmin(15)
else:(16)
return falseUsing Algorithm 1, the optimal value of edge resources divided at the beginning of the next period of each cell is estimated. In addition, the optimal resources are allocated to each edge server according to the adjustment of load balance among different edge servers and the allocation of request redirection, in order to increase the success rate of the vehicles requesting edge resources.


### 6.4. Model Improvement Based on Traffic Flow Prediction

The resultft,n is first obtained from the traffic flow prediction model in cell n and in period t using equation (12):(17)Copti=Cmin,ft,n≤Cmin+Sn−1t,ft,n−Sn−1t,ft,n>Cmin+Sn−1t.It is then compared with the optimal value of edge resourceCopti derived from Algorithm 1, in order to improve the prediction accuracy.


## 6.1. Prediction of the Vehicle Traffic Flow

Assuming that there areCnt−1 available edge resources contained in cell n at the beginning of period t, the probability of a request being blocked when the vehicle enters cell n from other cells is expressed in the following equation: (15)P∅|Cnt−1=0,Cnt−1≥B⌣nt,∑Cnt−1+1B⌣ntPRntx,else..where ϕ represents a blocking event.Some of the vehicles appear in celln at the beginning of period t, and stay in cell n during the entire period t. They will not make changes to the edge resources of the cell, because their edge resource requests have already been provisioned at the beginning of period t. It is demonstrated that these requests have been supplied by cell n, and maintain the supplement of edge resources at the beginning of period t +1. Considering the worst case, if all the entering vehicles are earlier than all the vehicles leaving in cell n at period t, the blocking rate of the edge resource request can be easily increased by directly configuring according to the edge resource configuration result obtained by equation (9).


## 6.2. Algorithm Improvement Based on the QoS Model

The estimated value ofCnt−1 should be determined at the beginning of t that has passed. In addition, the accuracy rate of the vehicle transfer prediction for the next period t+1 based on the vehicle trajectory records in period t is low. Therefore, the minimum number of edge resources of cell n at the end of period t or the beginning of period t+1 is predicted based on the predicted transfer situation of vehicles in period t and the distribution of the fleet at the beginning of period t:(16)P∅|Cnt−1≤ϵ.Therefore, the model based on QoS aims at computing the minimum number of edge resources of celln at the end of period t, so that equation (16) is developed, where ϵ is the user-defined service blocking rate, which represents the estimated blocking rate of the vehicle requesting edge resources.


## 6.3. Optimal Resource Allocation

Due to the fact that it is impossible to calculate the optimal value one by one in the case of large data volume, this article uses a grouping and binary search algorithm (two-stage algorithm) in order to calculate the minimum number of edge resources in periodt and in cell n. The corresponding pseudocode is shown in Algorithm 1.Algorithm 1: Two-stage algorithm.
Input: user-defined service blocking rateϵ, maximum capacity of edge device CmaxOutput: Optimal value of edge resourceCmin satisfied by (16)(1)
CL,CH←1(2)
whilePϕ|CH>ϵ:(3)
CL←CH(4)
CH←2×CH(5)
ifCH>Cmaxthen(6)
return false(7)
while True:(8)
Cmin←CL+CH/2(9)
ifPϕ|Cmin≤ϵ:(10)
CH←Cmin(11)
else:(12)
CL←Cmin(13)
ifCH−CL≤1:(14)
returnCmin(15)
else:(16)
return falseUsing Algorithm 1, the optimal value of edge resources divided at the beginning of the next period of each cell is estimated. In addition, the optimal resources are allocated to each edge server according to the adjustment of load balance among different edge servers and the allocation of request redirection, in order to increase the success rate of the vehicles requesting edge resources.


## 6.4. Model Improvement Based on Traffic Flow Prediction

The resultft,n is first obtained from the traffic flow prediction model in cell n and in period t using equation (12):(17)Copti=Cmin,ft,n≤Cmin+Sn−1t,ft,n−Sn−1t,ft,n>Cmin+Sn−1t.It is then compared with the optimal value of edge resourceCopti derived from Algorithm 1, in order to improve the prediction accuracy.


## 7. Request Allocation for the Edge System in IoV

Based on the nature of the dynamic connection between the vehicle and the edge node, this section proposes a request allocation model between the on-board terminals, edge servers and Cloudlet, so that the average processing time of each edge server in the cell is as equal as possible, in order to improve the performance of the edge system in IoV.


### 7.1. Model of Request Allocation for the Edge System in IoV

Assuming that the total amount of messages received by celln in period t is λ=λe+λv+λc, it is distributed to edge servers, on-board units (OBUs), and Cloudlet. Three different levels of equipment then process the request sent by the vehicle, and send it back to the vehicle. The distribution table is presented in Table 1.Table 1
Distribution table of the vehicular requests.
λiThe amount of vehicular requests received from the coverage byRSUiλieThe amount of vehicular requests allocated to ES connected toRSUiλivThe amount of vehicular requests allocated to on-board units from the coverage ofRSUiλicThe amount of vehicular requests allocated to Cloudlet whichRSUi belong toDue to the uncertainty of user demand and fluctuations in the number of requests received by each RSU in different periods, based on the study presented in [15, 16], the number of arriving vehicles follows the Poisson process. Therefore, this article assumes that the request flow arriving at each RSU from vehicles follows a Poisson process with an arrival rate of λi.This article assumes thatN, R, and M represent the number of Cloudlets in the targeted area, number of edge servers covered by each cell, and expected number of vehicles covered in each cell at the beginning of period t +1, respectively. The main terms of this section are presented in Table 2.Table 2
Distribution of vehicular requests.
NotationDescriptionCThe set of clouds,C=c1,c2,…,cNEThe set of RSU,E=RSU1,RSU2,…,RSURVThe set of vehicles,V=v1,v2,…,vMfi,jRepresenting the number of requests redirected fromRSUi,i∈R to RSUj,j∈RIn addition, this article first analyzes the network performance in a cell as an example and then continuously adjusts the request allocation algorithm according to the experimental results. Afterwards, it is applied to all the other cells. The allocation graphic is presented in Figure3, and the Cloudlet in cell n accepts the number of requests that fail in transmitting to edge server or on-board unit sent by vehicle, in order to relieve, which alleviates the emergency need for vehicular requests.Figure 3
Distribution diagram of the vehicular requests.


### 7.2. The Service Queue Model in IoV

In the edge system of IoV, the total response time can be obtained by:(18)P0λ,μ,l=∑k=0l−11k!λμk+1l!1−ρλμl−1,where dup represents the uploading delay for a request from a vehicle to an RSU, dwait denotes the queueing delay for a request at the edge server wired to the RSU, dpro is the processing delay of the request at the edge server, and ddown represents the feedback delay of the calculation result back to the vehicle:(19)Edwait=fλ,μ,l=lρlρλl!1−ρ2P0.The edge system in IoV can be modeled as a queueing network. The idle probability in the queueing system withl homogeneous servers is expressed in equation (18), where λ represents the request flow waiting for a server to process, and μ denotes the fixed service rate so that the service intensity meets ρ=λ/lμ<1 with an average queueing delay expressed in equation (19).


#### 7.2.1. Queueing Model at Cloudlet

The Cloudlet in celln can be modeled as a M/M/b queue, with b homogeneous servers and fixed service rate μc. Based on the previous assumption, the service intensity at Cloudlet in cell n is ρc=λc/bμc, where λc represents the number of requests to Cloudlet in the unit interval, and the average calculation delay per request is Edpro=1/μc. A network delay dv⟶Cloudlet is incurred by a unit request sent by a vehicle transfer from RSU to Cloudlet, with an ignored feedback delay. The average response delay dstolc of unit request at Cloudlet can then be computed as(20)Edstolc=fλc,μc,b+1μc+dv⟶Cloudlet.


#### 7.2.2. Queueing Model at the Edge Server

Borrowing ideas from Reference [18], it is assumed that cell n contains a number of RSU clusters RS=RSUs1,RSUs2,…,RSUsRS, where RS represents the number of RSU clusters, and each cluster contains bi,i∈R edge servers. A cluster of RSU base stations with close distances is developed to queue up and process the requests sent by the vehicles. Similarly, the cluster can be modeled as a M/M/b queue, and fixed service rate μe, with a service intensity ρe=λe/bμe, where λe represents the number of requests to an edge server in a unit interval, and the average calculation delay per request is Edpro=1/μe. The delay dv⟶RSU is incurred by a unit request transfer from a vehicle to RSU, connected to a corresponding edge server. Afterwards, the average response delay dstole of unit request on the edge server can be computed as(21)Edstole=fλe,μe,b+1μe+dv⟶RSU.


#### 7.2.3. Queueing Model of the Mobile Vehicle Network

This article assumes that each vehicle has an independent computational capacity to share processing requests. Given the number of requests arriving atRSUi with arrival rate λi, the request flow in the waiting queue of moving on-board units covered by RSUi can be considered a subprocess of the request flow arriving at RSUi, with an arrival rate λiv≤λv. When a vehicle comes into the wireless communication range of RSUi, it picks up a request at the front of the waiting queue based on the on-board units and finishes processing before leaving the communication range of RSUi. Based on [10], the request flow in the waiting queue of moving on-board units can be modeled as a Markov chain, and the model can be considered a M/M/1 queue. The service intensity on the queue is computed as ρiv=λiv/μiv, where the total vehicle capacity is μiv=∑j=1aμj with a vehicles covered by RSUi. The average response delay dstolv of unit request on the on-board unit is only related to λiv and μiv. Its value is calculated using the following equation: (22)Edstolv=1μiv−λiv+dv⟶v.Here, the delaydv⟶v is incurred by a unit request transfer from a vehicle to another.


### 7.3. Allocation of Requests Based on Average Delay Minimization

Due to the uncertainty of the trajectory prediction method based on the historical trajectories, the base stations that the vehicle may be connected to at the beginning of the next period form a cluster in order to alleviate the error caused by the vehicle entering different cells with different probabilities in the next period. Assuming that a vehicle submits requestsλi,i∈M in period t, the average response delay is then calculated using equation (23). This indicates that the request λi sent by the vehicle can be divided into three different requests λi=λiv+λie+λiv that are calculated and integrated by the on-board unit, the edge server and the Cloudlet, respectively. The values of average response delay Edi,stolt,c, Edi,stolt,e, and Edi,stolt,v depend on the service intensity on different equipment, calculated using equations (20)–(22):(23)Edi,stolt=maxEdi,stolt,c,Edi,stolt,e,Edi,stolt,v.Therefore, the optimal edge resource allocation problem in IoV is defined as follows. Under the premise that the minimal value of edge resourcesCmin in cell n and ∑i=1RSbi edge servers is deployed, allocating a certain volume of resources of each edge server so that the average response delay in cell n is minimized. The optimization formula is shown in equation (24), where M=∑i=1NHi,ct−1 represents the expected number of vehicles covered by cell n in period t, and MF=∑i=1NHFi,ct−1 denotes the expected total vehicular capacity covered by cell n in period t:(24)argminλie,λjv1M∑i=0MEdi,stolt,s.t.λc+∑i=1RSλie+∑i=1Mλjv≤∑i=1Mλi,λie≤biμe,i∈RS,∑j=1Mλjv≤MF,μe=Cmin−MF∑i=0RSbi.Since multiple variables in the optimal allocation problem are tightly coupled, it is complicated to solve the response time and request allocation and redirection problems. Therefore, in this article, two subprocesses of request allocation optimization and request redirection are used to approximate the optimal allocation problem.


## 7.1. Model of Request Allocation for the Edge System in IoV

Assuming that the total amount of messages received by celln in period t is λ=λe+λv+λc, it is distributed to edge servers, on-board units (OBUs), and Cloudlet. Three different levels of equipment then process the request sent by the vehicle, and send it back to the vehicle. The distribution table is presented in Table 1.Table 1
Distribution table of the vehicular requests.
λiThe amount of vehicular requests received from the coverage byRSUiλieThe amount of vehicular requests allocated to ES connected toRSUiλivThe amount of vehicular requests allocated to on-board units from the coverage ofRSUiλicThe amount of vehicular requests allocated to Cloudlet whichRSUi belong toDue to the uncertainty of user demand and fluctuations in the number of requests received by each RSU in different periods, based on the study presented in [15, 16], the number of arriving vehicles follows the Poisson process. Therefore, this article assumes that the request flow arriving at each RSU from vehicles follows a Poisson process with an arrival rate of λi.This article assumes thatN, R, and M represent the number of Cloudlets in the targeted area, number of edge servers covered by each cell, and expected number of vehicles covered in each cell at the beginning of period t +1, respectively. The main terms of this section are presented in Table 2.Table 2
Distribution of vehicular requests.
NotationDescriptionCThe set of clouds,C=c1,c2,…,cNEThe set of RSU,E=RSU1,RSU2,…,RSURVThe set of vehicles,V=v1,v2,…,vMfi,jRepresenting the number of requests redirected fromRSUi,i∈R to RSUj,j∈RIn addition, this article first analyzes the network performance in a cell as an example and then continuously adjusts the request allocation algorithm according to the experimental results. Afterwards, it is applied to all the other cells. The allocation graphic is presented in Figure3, and the Cloudlet in cell n accepts the number of requests that fail in transmitting to edge server or on-board unit sent by vehicle, in order to relieve, which alleviates the emergency need for vehicular requests.Figure 3
Distribution diagram of the vehicular requests.


## 7.2. The Service Queue Model in IoV

In the edge system of IoV, the total response time can be obtained by:(18)P0λ,μ,l=∑k=0l−11k!λμk+1l!1−ρλμl−1,where dup represents the uploading delay for a request from a vehicle to an RSU, dwait denotes the queueing delay for a request at the edge server wired to the RSU, dpro is the processing delay of the request at the edge server, and ddown represents the feedback delay of the calculation result back to the vehicle:(19)Edwait=fλ,μ,l=lρlρλl!1−ρ2P0.The edge system in IoV can be modeled as a queueing network. The idle probability in the queueing system withl homogeneous servers is expressed in equation (18), where λ represents the request flow waiting for a server to process, and μ denotes the fixed service rate so that the service intensity meets ρ=λ/lμ<1 with an average queueing delay expressed in equation (19).


### 7.2.1. Queueing Model at Cloudlet

The Cloudlet in celln can be modeled as a M/M/b queue, with b homogeneous servers and fixed service rate μc. Based on the previous assumption, the service intensity at Cloudlet in cell n is ρc=λc/bμc, where λc represents the number of requests to Cloudlet in the unit interval, and the average calculation delay per request is Edpro=1/μc. A network delay dv⟶Cloudlet is incurred by a unit request sent by a vehicle transfer from RSU to Cloudlet, with an ignored feedback delay. The average response delay dstolc of unit request at Cloudlet can then be computed as(20)Edstolc=fλc,μc,b+1μc+dv⟶Cloudlet.


### 7.2.2. Queueing Model at the Edge Server

Borrowing ideas from Reference [18], it is assumed that cell n contains a number of RSU clusters RS=RSUs1,RSUs2,…,RSUsRS, where RS represents the number of RSU clusters, and each cluster contains bi,i∈R edge servers. A cluster of RSU base stations with close distances is developed to queue up and process the requests sent by the vehicles. Similarly, the cluster can be modeled as a M/M/b queue, and fixed service rate μe, with a service intensity ρe=λe/bμe, where λe represents the number of requests to an edge server in a unit interval, and the average calculation delay per request is Edpro=1/μe. The delay dv⟶RSU is incurred by a unit request transfer from a vehicle to RSU, connected to a corresponding edge server. Afterwards, the average response delay dstole of unit request on the edge server can be computed as(21)Edstole=fλe,μe,b+1μe+dv⟶RSU.


### 7.2.3. Queueing Model of the Mobile Vehicle Network

This article assumes that each vehicle has an independent computational capacity to share processing requests. Given the number of requests arriving atRSUi with arrival rate λi, the request flow in the waiting queue of moving on-board units covered by RSUi can be considered a subprocess of the request flow arriving at RSUi, with an arrival rate λiv≤λv. When a vehicle comes into the wireless communication range of RSUi, it picks up a request at the front of the waiting queue based on the on-board units and finishes processing before leaving the communication range of RSUi. Based on [10], the request flow in the waiting queue of moving on-board units can be modeled as a Markov chain, and the model can be considered a M/M/1 queue. The service intensity on the queue is computed as ρiv=λiv/μiv, where the total vehicle capacity is μiv=∑j=1aμj with a vehicles covered by RSUi. The average response delay dstolv of unit request on the on-board unit is only related to λiv and μiv. Its value is calculated using the following equation: (22)Edstolv=1μiv−λiv+dv⟶v.Here, the delaydv⟶v is incurred by a unit request transfer from a vehicle to another.


## 7.2.1. Queueing Model at Cloudlet

The Cloudlet in celln can be modeled as a M/M/b queue, with b homogeneous servers and fixed service rate μc. Based on the previous assumption, the service intensity at Cloudlet in cell n is ρc=λc/bμc, where λc represents the number of requests to Cloudlet in the unit interval, and the average calculation delay per request is Edpro=1/μc. A network delay dv⟶Cloudlet is incurred by a unit request sent by a vehicle transfer from RSU to Cloudlet, with an ignored feedback delay. The average response delay dstolc of unit request at Cloudlet can then be computed as(20)Edstolc=fλc,μc,b+1μc+dv⟶Cloudlet.


## 7.2.2. Queueing Model at the Edge Server

Borrowing ideas from Reference [18], it is assumed that cell n contains a number of RSU clusters RS=RSUs1,RSUs2,…,RSUsRS, where RS represents the number of RSU clusters, and each cluster contains bi,i∈R edge servers. A cluster of RSU base stations with close distances is developed to queue up and process the requests sent by the vehicles. Similarly, the cluster can be modeled as a M/M/b queue, and fixed service rate μe, with a service intensity ρe=λe/bμe, where λe represents the number of requests to an edge server in a unit interval, and the average calculation delay per request is Edpro=1/μe. The delay dv⟶RSU is incurred by a unit request transfer from a vehicle to RSU, connected to a corresponding edge server. Afterwards, the average response delay dstole of unit request on the edge server can be computed as(21)Edstole=fλe,μe,b+1μe+dv⟶RSU.


## 7.2.3. Queueing Model of the Mobile Vehicle Network

This article assumes that each vehicle has an independent computational capacity to share processing requests. Given the number of requests arriving atRSUi with arrival rate λi, the request flow in the waiting queue of moving on-board units covered by RSUi can be considered a subprocess of the request flow arriving at RSUi, with an arrival rate λiv≤λv. When a vehicle comes into the wireless communication range of RSUi, it picks up a request at the front of the waiting queue based on the on-board units and finishes processing before leaving the communication range of RSUi. Based on [10], the request flow in the waiting queue of moving on-board units can be modeled as a Markov chain, and the model can be considered a M/M/1 queue. The service intensity on the queue is computed as ρiv=λiv/μiv, where the total vehicle capacity is μiv=∑j=1aμj with a vehicles covered by RSUi. The average response delay dstolv of unit request on the on-board unit is only related to λiv and μiv. Its value is calculated using the following equation: (22)Edstolv=1μiv−λiv+dv⟶v.Here, the delaydv⟶v is incurred by a unit request transfer from a vehicle to another.


## 7.3. Allocation of Requests Based on Average Delay Minimization

Due to the uncertainty of the trajectory prediction method based on the historical trajectories, the base stations that the vehicle may be connected to at the beginning of the next period form a cluster in order to alleviate the error caused by the vehicle entering different cells with different probabilities in the next period. Assuming that a vehicle submits requestsλi,i∈M in period t, the average response delay is then calculated using equation (23). This indicates that the request λi sent by the vehicle can be divided into three different requests λi=λiv+λie+λiv that are calculated and integrated by the on-board unit, the edge server and the Cloudlet, respectively. The values of average response delay Edi,stolt,c, Edi,stolt,e, and Edi,stolt,v depend on the service intensity on different equipment, calculated using equations (20)–(22):(23)Edi,stolt=maxEdi,stolt,c,Edi,stolt,e,Edi,stolt,v.Therefore, the optimal edge resource allocation problem in IoV is defined as follows. Under the premise that the minimal value of edge resourcesCmin in cell n and ∑i=1RSbi edge servers is deployed, allocating a certain volume of resources of each edge server so that the average response delay in cell n is minimized. The optimization formula is shown in equation (24), where M=∑i=1NHi,ct−1 represents the expected number of vehicles covered by cell n in period t, and MF=∑i=1NHFi,ct−1 denotes the expected total vehicular capacity covered by cell n in period t:(24)argminλie,λjv1M∑i=0MEdi,stolt,s.t.λc+∑i=1RSλie+∑i=1Mλjv≤∑i=1Mλi,λie≤biμe,i∈RS,∑j=1Mλjv≤MF,μe=Cmin−MF∑i=0RSbi.Since multiple variables in the optimal allocation problem are tightly coupled, it is complicated to solve the response time and request allocation and redirection problems. Therefore, in this article, two subprocesses of request allocation optimization and request redirection are used to approximate the optimal allocation problem.


## 8. Load Balancing of the Edge Computing System in IoV

It can be deduced that equation (24) is a nonlinear optimization problem, which is difficult to promptly solve in period t. Therefore, the general idea of the load balancing of the edge computing system in IoV is as follows. (1) According to the requests received in the next period t +1 and in cell n, the amount of requests allocated to on-board units and the amount of requests allocated to edge servers are calculated using the incremental cost method. (2) This article first computes the amount of redirected requests at each RSUs in the next period t +1 in cell t, making these average response delays among all the clusters in cell n similar to dc,tave. (3) According to the actual trajectory of the vehicle, the vehicle decides to select and unload one of the optimal edge servers set, which is configured with the optimal number of edge resources, or to Cloudlet if the unloading fails. (4) The actual blocking rate of requests for edge resources by vehicle will be calculated, and the minimum number of servers required in Cloudlet is determined.


### 8.1. Minimization of the Average Response Delay

Based on the previous assumption, celln contains RS RSU clusters and the total capacity of M vehicles covered expectantly in period t. Therefore, the total requests add up to λ=∑i=1Mλi generated at cell n in the beginning of period t. These overall requests are allocated through the incremental cost method with the following objective:(25)minEdstolt,e+Edstolt,v,s.t.∑i=1RSλie+∑j=1Mλjv≤λ,∑j=1Mλjv≤∑j=1Mμjv.According to equation (25), the condition that the number of requests allocated to the on-board units can be completed within a period is satisfied. In addition, the vehicle then unloads the rest of the requests to the Cloudlet, if the unloading at edge server is in failure, using the cost incremental method expressed in the following equation:λ−w(26)dc,tave=argwminfλ−w,μe,∑i=1RSbi+1μe+1∑j=1Mμjv−w.Here,w is the number of requests unloaded to the on-board units, and the remaining λ−w is the number of requests unloaded to edge servers.According to the calculation result, the allocation plan is stored in each RSU in celln, and the edge resource request sent by the vehicle is given as a reference according to the actual vehicle trajectory. The remaining requests λ−w are allocated to RSUsi,i∈RS according to the GPS historical trajectory. In other words, the vehicle will be the most likely to submit a resource request to the optimal RSU.


### 8.2. Load Balance among Edge Servers

The number of requests unloaded from vehicles inRSUsi,i∈RS in different periods is unstable, due to the driving randomness, and the states of idleness or busyness are inevitable. Therefore, it is assumed that the RSUs can access each other. Even RSUs redirect a part of requests contained to another RSUs. The average response delay for each RSUs in cell n is defined as Etstolλie:(27)Etstolλie=fλie,μe,bi+1μe+dv⟶RSU.In order to obtain the number of requests from the overloaded cluster to unloaded cluster betweenRSUsi,i∈RS, the transmission delay caused by request redirection is ignored. This article assumes that the expected minimum average response delay D in cell n is first calculated, and the number of redirected requests generated from an overloaded RSUs to an unloaded RSUs is then determined, so that the average response time in cell n is close to D. Finally, the value of D is adjusted according to the difference between the outgoing requests from the total overloaded clusters, and the incoming requests to the total unloaded clusters.The initial value ofD is estimated by D=Tmax+Tmin/2, where Tmax=tstolλie|i∈RS and Tmin=tstolλie|i∈RS. All the RSUs cluster are then partitioned in two disjoint sets: the set of overloaded clusters Vo=i|tstolλie>D and the set of unloaded clusters Vu=i|tstolλie<D. Therefore, the definition of the load balancing problem in IoV is provided in the following equation: (28)Etstolλie−ϕi−D≤δ,i∈Vo,Etstolλje+ϕj−D≤δ,j∈Vu,s.t.∑i∈Voϕi=∑j∈Vuϕj.Here,ϕj is the number of the requests redirected from RSUsi,i∈Vo, ϕj represents the number of requests redirected into RSUsj,j∈Vu, and δ denotes a given threshold, which indicates the allowable difference between the average response delay after redirection and the value of D. The values of ϕi,i∈Vo and ϕj,j∈Vu are approximately calculated using the iterative algorithm.


### 8.3. The Request Redirection between Edge Servers

Based on the previous results of request redirection, the problem of the number of requests generated fromRSUsi,i∈V0 to RSUsj,i∈Vu is transformed into a problem of finding the minimum cost and maximum flow in terms of network delay. Thus, the optimization objective is expressed as(29)argminri,j∑i=1RS∑j=1RSmaxri,j,0⋅cijs.t.ri,j=−ri,j,i≠j,0,i=j,∑i∈Vori,j=ϕj,j∈Vu,∑j∈Vuri,j=ϕi,i∈Vo,where ri,j represents the number of requests redirected from RSUsi,i∈RS to RSUsj,j∈RS, cij is the transmission delay among different clusters, cij=γdij, γ is the proportional coefficient between transmission and distance, and dij is the Euclidean distance between RSUsi and RSUsj. This article uses the Vogel algorithm to calculate a suitable value of ri,j in time, in a limited period t, based on equation (29), and adjust the optimal volume of edge resource at each RSU according to the optimal value of edge resources Copti in cell n.Under the precondition that the amount of deployed edge resources remains unchanged, the virtual amount of resources of each edge server can be adjusted according to the redirection result. Especially when the maximum resource amount of an edge server does not meet the requests issued by the surrounding vehicles, a part of the requests can be redirected to another edge server, so that passing vehicles can increase the success rate of unloading to the RSU, within the limited wireless communication range.


## 8.1. Minimization of the Average Response Delay

Based on the previous assumption, celln contains RS RSU clusters and the total capacity of M vehicles covered expectantly in period t. Therefore, the total requests add up to λ=∑i=1Mλi generated at cell n in the beginning of period t. These overall requests are allocated through the incremental cost method with the following objective:(25)minEdstolt,e+Edstolt,v,s.t.∑i=1RSλie+∑j=1Mλjv≤λ,∑j=1Mλjv≤∑j=1Mμjv.According to equation (25), the condition that the number of requests allocated to the on-board units can be completed within a period is satisfied. In addition, the vehicle then unloads the rest of the requests to the Cloudlet, if the unloading at edge server is in failure, using the cost incremental method expressed in the following equation:λ−w(26)dc,tave=argwminfλ−w,μe,∑i=1RSbi+1μe+1∑j=1Mμjv−w.Here,w is the number of requests unloaded to the on-board units, and the remaining λ−w is the number of requests unloaded to edge servers.According to the calculation result, the allocation plan is stored in each RSU in celln, and the edge resource request sent by the vehicle is given as a reference according to the actual vehicle trajectory. The remaining requests λ−w are allocated to RSUsi,i∈RS according to the GPS historical trajectory. In other words, the vehicle will be the most likely to submit a resource request to the optimal RSU.


## 8.2. Load Balance among Edge Servers

The number of requests unloaded from vehicles inRSUsi,i∈RS in different periods is unstable, due to the driving randomness, and the states of idleness or busyness are inevitable. Therefore, it is assumed that the RSUs can access each other. Even RSUs redirect a part of requests contained to another RSUs. The average response delay for each RSUs in cell n is defined as Etstolλie:(27)Etstolλie=fλie,μe,bi+1μe+dv⟶RSU.In order to obtain the number of requests from the overloaded cluster to unloaded cluster betweenRSUsi,i∈RS, the transmission delay caused by request redirection is ignored. This article assumes that the expected minimum average response delay D in cell n is first calculated, and the number of redirected requests generated from an overloaded RSUs to an unloaded RSUs is then determined, so that the average response time in cell n is close to D. Finally, the value of D is adjusted according to the difference between the outgoing requests from the total overloaded clusters, and the incoming requests to the total unloaded clusters.The initial value ofD is estimated by D=Tmax+Tmin/2, where Tmax=tstolλie|i∈RS and Tmin=tstolλie|i∈RS. All the RSUs cluster are then partitioned in two disjoint sets: the set of overloaded clusters Vo=i|tstolλie>D and the set of unloaded clusters Vu=i|tstolλie<D. Therefore, the definition of the load balancing problem in IoV is provided in the following equation: (28)Etstolλie−ϕi−D≤δ,i∈Vo,Etstolλje+ϕj−D≤δ,j∈Vu,s.t.∑i∈Voϕi=∑j∈Vuϕj.Here,ϕj is the number of the requests redirected from RSUsi,i∈Vo, ϕj represents the number of requests redirected into RSUsj,j∈Vu, and δ denotes a given threshold, which indicates the allowable difference between the average response delay after redirection and the value of D. The values of ϕi,i∈Vo and ϕj,j∈Vu are approximately calculated using the iterative algorithm.


## 8.3. The Request Redirection between Edge Servers

Based on the previous results of request redirection, the problem of the number of requests generated fromRSUsi,i∈V0 to RSUsj,i∈Vu is transformed into a problem of finding the minimum cost and maximum flow in terms of network delay. Thus, the optimization objective is expressed as(29)argminri,j∑i=1RS∑j=1RSmaxri,j,0⋅cijs.t.ri,j=−ri,j,i≠j,0,i=j,∑i∈Vori,j=ϕj,j∈Vu,∑j∈Vuri,j=ϕi,i∈Vo,where ri,j represents the number of requests redirected from RSUsi,i∈RS to RSUsj,j∈RS, cij is the transmission delay among different clusters, cij=γdij, γ is the proportional coefficient between transmission and distance, and dij is the Euclidean distance between RSUsi and RSUsj. This article uses the Vogel algorithm to calculate a suitable value of ri,j in time, in a limited period t, based on equation (29), and adjust the optimal volume of edge resource at each RSU according to the optimal value of edge resources Copti in cell n.Under the precondition that the amount of deployed edge resources remains unchanged, the virtual amount of resources of each edge server can be adjusted according to the redirection result. Especially when the maximum resource amount of an edge server does not meet the requests issued by the surrounding vehicles, a part of the requests can be redirected to another edge server, so that passing vehicles can increase the success rate of unloading to the RSU, within the limited wireless communication range.


## 9. Dynamic Selection of Edge Nodes by Vehicles

For each edge server, the amount of available resource is in a dynamic change in different periodt, with resources continuously occupied and released as the vehicles move. For each connected vehicle, the selection of edge server mainly considers the following factors: the amount of available resource of the edge server, representing the maximum amount of requests that can be offloaded to the edge server, the distance between the vehicle and the edge server, usually affecting the transmission delay of a request, and whether the response delay of the vehicular requests proceeded by the edge server and on-board unit of the vehicle itself can be met within a limited time. This is usually jointly determined by the amount of requests sent by the vehicle and the available resources of the edge server. Therefore it assumes that vehicle v (with vehicular capacity μv) decides to offload itself requests (the amount of the requests is λq) to the edge server e (the amount of available resources of edge server e is μe) at a time point, the delay return function satisfies:(30)argxminRv,e=xμv,E0<λq−xμe+dv⟶RSU<xμv,x∈0,λq.Here, Rv,e represents the delay result when vehicle v selects edge server e. The constraint condition indicates that the response delay at the on-board unit is slightly higher than the selected edge server in the actual offload process during driving.The main thought of dynamic selection for a vehicle to RSU is to first determine the selectable RSU list within a radius ofrd, sorted by distance in ascending order, and then in each iteration selection to determine the delay result Rv,ei such that Rv,ei<Tthreshold, where Tthreshold usually represents the length of period t, and finally confirms to the offload to the selected RSU or to the Cloudlet. The pseudocode of algorithm 2 for dynamic selection for vehicle v in period t is also provided.Algorithm 2: Dynamic selection for vehicles to edge servers.
Input: Distance thresholdrdOutput: offloading decisionrd(1)
Initializexd=0,i=1(2)
Get connectable RSU setRSUs=e1,e2,…,eL according to rd, sort by distance in ascending order SR=e1,e2,…,eL, where L is the number of SR(3)
whilexd=0do:(4)
selectei∈SR:(5)
if(6)
xd=i, break(7)
elsei++(8)
else(9)
else while(10)
ifxd=0:(11)
Offload to Cloud in celln(12)
end if


## 10. Experimental Evaluation

This article uses the vehicle historical trajectory data to conduct experiments and analysis on the proposed edge resource allocation and selection method, and verify its efficiency based on the proposed vehicle trajectory prediction.


### 10.1. Visualization of Vehicle Historical Trajectory Data

In this article, the trajectory data are extracted from the vehicle trajectory data in Chengdu in November 2016 applied by the Didi platform. The data format of each trajectory record information in the dataset is a four-tuple (id, Tstamp, longitude, and latitude) while recording a GPS vehicle trajectory positioning data every 3 s. Among them, id represents the order ID and Tstamp denotes the timestamp.The records of order trajectories are first preprocessed, and the boundary is then determined. The final trajectory map is presented in Figure4, which represents the trajectory of each vehicle from the beginning of the order to its end.Figure 4
Map of the vehicle trajectory.The line represents the trajectory of the vehicle, and the dot denotes the intervals of approximately 1 min. By observing a part of the records, it is deduced that the vehicle trajectory has some common characteristics. For instance, a slow vehicle is more likely to change direction and turn around, while a fast vehicle is more likely to maintain a relatively straight driving state. Based on these trajectory characteristics, geometric methods are used to predict the future trajectory with reference to the historical trajectory of the vehicle.


### 10.2. Statistics of Historical Traffic Volume

By preprocessing the historical trajectory data of vehicles, the traffic flow is calculated in each cell and in each period. The results are shown in Figure5 representing the traffic flow on the 15th, 22nd, and 23rd of November 2016.Figure 5
Results of the traffic flow statistics method.It can be seen from Figure5 that the traffic flow presents the characteristics of cycle similarity, correlation, and self-organization. It can be deduced that the traffic flow of one period of the day is related to the traffic flow of the same period of the previous week, which is also the same period of the previous day. It is convenient to predict the future traffic flow, based on the historical data of the traffic flow, to a certain extent.


### 10.3. Experimental Results Based on the Traffic Flow Prediction Model

The traffic flow prediction method proposed in 5.3 is used to predict the traffic flow in the last three weeks of November and compare it with the actual traffic flow statistics. In order to verify the accuracy of the developed traffic flow prediction model, the mean absolute percentage error (MAPE) (cf. equation (31)) and the root mean square error (RMSE) (cf. equation (32)) are used to calculate the actual error of the prediction model:(31)MAPE=∑i=1N∑t=1Tyt,i−ft,ift,i×100NT,(32)RMSE=1NT∑i=1N∑t=1Tft,i−yt,i2.The obtained results are shown in Table3.Table 3
Error calculation results.
Error indexMAPE (%)RMSECalculation result23.6811.21


### 10.4. Experimental Evaluation Method of Edge Server Load

In order to verify the efficiency of the proposed edge resource allocation method (Method-3) based on vehicle historical trajectory data, two benchmark methods are used for comparison:(a)
Complete configuration method (Method-1): according to the exact trajectory, the edge resources are deployed in all the cells along the trajectory(b)
Method based on motion estimation (Method-2): based on the vehicle’s current motion state (speed, direction, and position), it predicts which cluster the vehicle is most likely to appear in the next period, and configure edge resources for the cluster in advance


### 10.5. Experimental Process

This experiment first preprocesses the historical trajectory data of vehicle orders from the Chengdu Didi platform in November 2016. This includes the normalizing data values that are conducive to simplifying the input, deleting the orders with too short time, and supplementing the missing values in the middle. The total number of periods in the time and the total number of cells in the space are then calculated. Afterwards, based on the vehicle density distribution obtained from the GPS trajectory data of the vehicle, RSU base stations are randomly set up at different locations in different cells. This article assumes that the network delay between the RSU and the vehicle is proportional to the physical distance, as in [7]. Due to the randomness of the distance between the RSU and the vehicle, a network delay is assigned according to the normal distribution: 0.05≤N0.05,0.02≤0.25. The two benchmark methods and the proposed method are used to allocate optimal edge resource on each edge server, and then, the three methods are tested using the dynamic selection algorithm. Similarly, the network delay is distributed among other nodes according to the normal distribution, except that the Euclidean distance between each pair of RSUs is used as the transmission delay reference standard in the solution of request redirection. The detailed information about the dataset and the parameter settings are provided in Table 4. The experimental environment is presented in Table 5.Table 4
Settings of the dataset and parameters.
ParametersValueThe length of a cella1.5 kmThe length ofT3 minThe length of time windowk10The amount of request per vehicle and per periodλiU1.6,3.2The number of RSU clusters in each cellb9The number of edge servers in each RSU cluster1−9The service rate an on-board unitμvU0.5,1.0The service rate on Cloudletμc5The transmission delay between vehicle and RSUdv⟶RSUN0.05,0.02The transmission delay between each RSUdRSU⟶RSUN0.15,0.05The transmission delay between each vehicledv⟶vN0.1,0.05The transmission delay between vehicle and Cloudletdv⟶CloudletN0.3,0.05δ0.05γ0.3Destination thresholdrd0.5 kmTable 5
The experimental environment.
SettingDescriptionCPUIntel(R) Core(TM) i7-5500U CPU @2.40 GHz 2.40 GHzRAM16 GBOperating systemWindows 10, 64-bitDevelopmentPython 3.9.7Operating platformPyCharm 2019.2.1For eachRSUs cluster, the expected number of covered vehicles and the total expected vehicle capacity are first calculated in the next period t +1, based on the GPS historical trajectory data. The number of requests for each passing vehicle in the next period t+1 is then randomly generated according to normal distribution. Afterwards, the optimal value of edge resource in each RSU is predicted and adjusted using the request allocation algorithm and load balancing algorithm. Finally, the actual success rate of request offloading and blocking rate are calculated using the dynamic selection of surrounding RSU, based on the actual vehicular trajectory.


### 10.6. Experimental Results

The experimental comparison results between the proposed method and the benchmark methods are shown in Figure6, with 1169 edge servers. The complete configuration method achieves a 100% success rate of vehicle requesting edge resources. The method based on motion estimation achieves 83.86%, and ϵ of 0.01, 0.05, and 0.1 achieves success rates of 90.97%, 88.85%, and 87.61%, respectively. It can be seen from Figure 6 that the complete configuration method can achieve a rate of 100%; however, the rate is achieved based on the cost of more edge resources.Figure 6
Comparison between the proposed and benchmark methods.In order to study the relationship between the actual success rate andϵ, experiments on continuous values of ϵ for different numbers of edge servers are performed. The obtained results are shown in Figure 7. It can be seen that, as ϵ decreases, all the values slowly increase, and the actual success rate of edge resource maintains more than 90% when ϵ≤0.02. In addition, the increase in the number of edge servers alleviates the blocking rate of vehicle requests for edge resources to a certain extent, making the experimental results more averaged.Figure 7
Relationship between the actual success rate andϵ.In order to further study the performance of the proposed edge resource allocation method, its stability is observed from the three perspectives of time, area, and number of vehicles.In order to observe the experimental performance in different periods, vehicle trajectory data from the 17th (the number of edge servers is 1169) are considered, and the actual request success rate in different periods is observed. The experimental results are shown in Figure 8, where the horizontal line represents the average for the whole day, the value of which is 90.97%. It can be seen that the actual request success rate is low during the period of 17 : 00–19 : 00 and high during the period of 23 : 00–03 : 00 (+1). This is due to the fact that the increase in the number of vehicles and the complex traffic conditions during the peak traffic hours in the evening lead to a low efficiency of actual resource allocation. Moreover, the proposed method has a better performance than that of the reference method of motion estimation in terms of edge resource allocation. In addition, the actual edge resource request success rate gradually increases with the decrease in ϵ.Figure 8
The actual success rate of edge resource requests in different periods.In order to observe the impact of different numbers of vehicles on the utilization performance of edge resources, a different number of vehicle subsets from the trajectory datasets on the 17th are randomly selected. The edge resources are allocated to different subsets, under the conditions of different values of ϵ with 1169 servers. The obtained results are shown in Figure 9.Figure 9
Actual success rate for different numbers of vehicles.Figure9 demonstrates that, with the increase in the user’s predefined blocking rate, the actual success rate of different vehicle numbers gradually decreases. When ϵ=0.01, the experimental results of different numbers are the most similar. In addition, with the increase in ϵ, the difference between the actual edge resource request success rates of different numbers gradually increases, and the experimental results are more unstable. This is mainly due to the high mobility of driving behavior, which is prone to the idle state of edge resources and the blocking of actual resource requests. As the value of ϵ decreases, the deviation caused by high mobility can be better alleviated.In order to evaluate the performance of the proposed edge configuration method in different cells, 5 cells are randomly selected on the 17th, and the relation between the actual request success rate and ϵ is assessed. The experimental results are shown in Figure 10.Figure 10
The success rate of edge resource requests on different cells.It can be seen from Figure10 that the results of the actual request success rate calculated from different cells are similar. In addition, they increase as the user predefined blocking rate decreases. This is mainly due to the difference in traffic flow in different cells. For cells with less traffic flow, such as the actual resource request success rate in cell 33, the success rate of the actual resource request greatly varies. Moreover, the traffic flow of cell 2 is relatively large, so that the calculation result is relatively stable and less affected by the change in the user’s predefined blocking rate.In order to study the influence of different numbers of edge servers on the utilization performance of edge resources, the proposed algorithm is implemented for different numbers of edge servers. The obtained results are shown in Figure11.Figure 11
The actual success rate of different numbers of edge servers.Figure11 shows that the results of the success rate of edge resource requests calculated by different numbers of edge servers are similar. In addition, they increase with the increase in the number of edge servers. The proposed method proposed is better than the mobile estimation, in terms of the actual success rate of edge resource requests. This is due to the fact that with the increase in the number of edge servers, the deployment is relatively balanced, which alleviates the prediction error caused by the high mobility of the driving, to a certain extent.Based on the experimental results obtained from the three perspectives of user’s predefined blocking rate, number of vehicles, and region, the proposed method allows to obtain the minimum number of cloud servers in different cells and alleviate the emergency needs of the request after failing to offload to edge devices.In order to study the relationship between the number of servers in Cloudlet and different edge resource allocation methods, experiments on continuous values ofϵ under the condition of different numbers of edge servers are performed. The obtained results are shown in Figure 12. It can be seen that, as the value of ϵ decreases, the number of cloud servers slowly increases, and the average value becomes close to 11. The resultant value based on the motion estimation method is almost 12.Figure 12
The minimum number of servers in Cloudlet using different methods.In order to evaluate the influence of different numbers of vehicles on the minimum number of servers in Cloudlet, subsets with different numbers of vehicles are randomly selected from the trajectory dataset on the 17th, and edge resource allocation is performed on different subsets under different values ofϵ and motion estimation methods, with 1169 servers. The obtained results are shown in Figure 13.Figure 13
The minimum number of servers in Cloudlet for different numbers of vehicles.Figure13 shows that, as the number of vehicles increases, the minimum number of servers in Cloudlet that need to be deployed gradually increases, and the gap between the different values of ϵ gradually increases. This is mainly due to the fact that, when the value of ϵ is determined, the more the number of vehicles is, the more requests blocked are sent by vehicles, and the more cloud servers are required.The main conclusions are summarized based on the experimental results. (1) The motion estimation method seemingly fail to be applied in practice, and the method proposed in this article not only reduces the redundant cost of resource allocation but also approaches the result of the complete configuration method. (2) The method proposed in this article can effectively improve the actual use efficiency of edge servers, thereby reducing the deployment cost of servers in Cloudlet. (3) The method proposed in this article conducts the optimization in resource provisioning in each period while ensuring QoS service quality.


## 10.1. Visualization of Vehicle Historical Trajectory Data

In this article, the trajectory data are extracted from the vehicle trajectory data in Chengdu in November 2016 applied by the Didi platform. The data format of each trajectory record information in the dataset is a four-tuple (id, Tstamp, longitude, and latitude) while recording a GPS vehicle trajectory positioning data every 3 s. Among them, id represents the order ID and Tstamp denotes the timestamp.The records of order trajectories are first preprocessed, and the boundary is then determined. The final trajectory map is presented in Figure4, which represents the trajectory of each vehicle from the beginning of the order to its end.Figure 4
Map of the vehicle trajectory.The line represents the trajectory of the vehicle, and the dot denotes the intervals of approximately 1 min. By observing a part of the records, it is deduced that the vehicle trajectory has some common characteristics. For instance, a slow vehicle is more likely to change direction and turn around, while a fast vehicle is more likely to maintain a relatively straight driving state. Based on these trajectory characteristics, geometric methods are used to predict the future trajectory with reference to the historical trajectory of the vehicle.


## 10.2. Statistics of Historical Traffic Volume

By preprocessing the historical trajectory data of vehicles, the traffic flow is calculated in each cell and in each period. The results are shown in Figure5 representing the traffic flow on the 15th, 22nd, and 23rd of November 2016.Figure 5
Results of the traffic flow statistics method.It can be seen from Figure5 that the traffic flow presents the characteristics of cycle similarity, correlation, and self-organization. It can be deduced that the traffic flow of one period of the day is related to the traffic flow of the same period of the previous week, which is also the same period of the previous day. It is convenient to predict the future traffic flow, based on the historical data of the traffic flow, to a certain extent.


## 10.3. Experimental Results Based on the Traffic Flow Prediction Model

The traffic flow prediction method proposed in 5.3 is used to predict the traffic flow in the last three weeks of November and compare it with the actual traffic flow statistics. In order to verify the accuracy of the developed traffic flow prediction model, the mean absolute percentage error (MAPE) (cf. equation (31)) and the root mean square error (RMSE) (cf. equation (32)) are used to calculate the actual error of the prediction model:(31)MAPE=∑i=1N∑t=1Tyt,i−ft,ift,i×100NT,(32)RMSE=1NT∑i=1N∑t=1Tft,i−yt,i2.The obtained results are shown in Table3.Table 3
Error calculation results.
Error indexMAPE (%)RMSECalculation result23.6811.21


## 10.4. Experimental Evaluation Method of Edge Server Load

In order to verify the efficiency of the proposed edge resource allocation method (Method-3) based on vehicle historical trajectory data, two benchmark methods are used for comparison:(a)
Complete configuration method (Method-1): according to the exact trajectory, the edge resources are deployed in all the cells along the trajectory(b)
Method based on motion estimation (Method-2): based on the vehicle’s current motion state (speed, direction, and position), it predicts which cluster the vehicle is most likely to appear in the next period, and configure edge resources for the cluster in advance


## 10.5. Experimental Process

This experiment first preprocesses the historical trajectory data of vehicle orders from the Chengdu Didi platform in November 2016. This includes the normalizing data values that are conducive to simplifying the input, deleting the orders with too short time, and supplementing the missing values in the middle. The total number of periods in the time and the total number of cells in the space are then calculated. Afterwards, based on the vehicle density distribution obtained from the GPS trajectory data of the vehicle, RSU base stations are randomly set up at different locations in different cells. This article assumes that the network delay between the RSU and the vehicle is proportional to the physical distance, as in [7]. Due to the randomness of the distance between the RSU and the vehicle, a network delay is assigned according to the normal distribution: 0.05≤N0.05,0.02≤0.25. The two benchmark methods and the proposed method are used to allocate optimal edge resource on each edge server, and then, the three methods are tested using the dynamic selection algorithm. Similarly, the network delay is distributed among other nodes according to the normal distribution, except that the Euclidean distance between each pair of RSUs is used as the transmission delay reference standard in the solution of request redirection. The detailed information about the dataset and the parameter settings are provided in Table 4. The experimental environment is presented in Table 5.Table 4
Settings of the dataset and parameters.
ParametersValueThe length of a cella1.5 kmThe length ofT3 minThe length of time windowk10The amount of request per vehicle and per periodλiU1.6,3.2The number of RSU clusters in each cellb9The number of edge servers in each RSU cluster1−9The service rate an on-board unitμvU0.5,1.0The service rate on Cloudletμc5The transmission delay between vehicle and RSUdv⟶RSUN0.05,0.02The transmission delay between each RSUdRSU⟶RSUN0.15,0.05The transmission delay between each vehicledv⟶vN0.1,0.05The transmission delay between vehicle and Cloudletdv⟶CloudletN0.3,0.05δ0.05γ0.3Destination thresholdrd0.5 kmTable 5
The experimental environment.
SettingDescriptionCPUIntel(R) Core(TM) i7-5500U CPU @2.40 GHz 2.40 GHzRAM16 GBOperating systemWindows 10, 64-bitDevelopmentPython 3.9.7Operating platformPyCharm 2019.2.1For eachRSUs cluster, the expected number of covered vehicles and the total expected vehicle capacity are first calculated in the next period t +1, based on the GPS historical trajectory data. The number of requests for each passing vehicle in the next period t+1 is then randomly generated according to normal distribution. Afterwards, the optimal value of edge resource in each RSU is predicted and adjusted using the request allocation algorithm and load balancing algorithm. Finally, the actual success rate of request offloading and blocking rate are calculated using the dynamic selection of surrounding RSU, based on the actual vehicular trajectory.


## 10.6. Experimental Results

The experimental comparison results between the proposed method and the benchmark methods are shown in Figure6, with 1169 edge servers. The complete configuration method achieves a 100% success rate of vehicle requesting edge resources. The method based on motion estimation achieves 83.86%, and ϵ of 0.01, 0.05, and 0.1 achieves success rates of 90.97%, 88.85%, and 87.61%, respectively. It can be seen from Figure 6 that the complete configuration method can achieve a rate of 100%; however, the rate is achieved based on the cost of more edge resources.Figure 6
Comparison between the proposed and benchmark methods.In order to study the relationship between the actual success rate andϵ, experiments on continuous values of ϵ for different numbers of edge servers are performed. The obtained results are shown in Figure 7. It can be seen that, as ϵ decreases, all the values slowly increase, and the actual success rate of edge resource maintains more than 90% when ϵ≤0.02. In addition, the increase in the number of edge servers alleviates the blocking rate of vehicle requests for edge resources to a certain extent, making the experimental results more averaged.Figure 7
Relationship between the actual success rate andϵ.In order to further study the performance of the proposed edge resource allocation method, its stability is observed from the three perspectives of time, area, and number of vehicles.In order to observe the experimental performance in different periods, vehicle trajectory data from the 17th (the number of edge servers is 1169) are considered, and the actual request success rate in different periods is observed. The experimental results are shown in Figure 8, where the horizontal line represents the average for the whole day, the value of which is 90.97%. It can be seen that the actual request success rate is low during the period of 17 : 00–19 : 00 and high during the period of 23 : 00–03 : 00 (+1). This is due to the fact that the increase in the number of vehicles and the complex traffic conditions during the peak traffic hours in the evening lead to a low efficiency of actual resource allocation. Moreover, the proposed method has a better performance than that of the reference method of motion estimation in terms of edge resource allocation. In addition, the actual edge resource request success rate gradually increases with the decrease in ϵ.Figure 8
The actual success rate of edge resource requests in different periods.In order to observe the impact of different numbers of vehicles on the utilization performance of edge resources, a different number of vehicle subsets from the trajectory datasets on the 17th are randomly selected. The edge resources are allocated to different subsets, under the conditions of different values of ϵ with 1169 servers. The obtained results are shown in Figure 9.Figure 9
Actual success rate for different numbers of vehicles.Figure9 demonstrates that, with the increase in the user’s predefined blocking rate, the actual success rate of different vehicle numbers gradually decreases. When ϵ=0.01, the experimental results of different numbers are the most similar. In addition, with the increase in ϵ, the difference between the actual edge resource request success rates of different numbers gradually increases, and the experimental results are more unstable. This is mainly due to the high mobility of driving behavior, which is prone to the idle state of edge resources and the blocking of actual resource requests. As the value of ϵ decreases, the deviation caused by high mobility can be better alleviated.In order to evaluate the performance of the proposed edge configuration method in different cells, 5 cells are randomly selected on the 17th, and the relation between the actual request success rate and ϵ is assessed. The experimental results are shown in Figure 10.Figure 10
The success rate of edge resource requests on different cells.It can be seen from Figure10 that the results of the actual request success rate calculated from different cells are similar. In addition, they increase as the user predefined blocking rate decreases. This is mainly due to the difference in traffic flow in different cells. For cells with less traffic flow, such as the actual resource request success rate in cell 33, the success rate of the actual resource request greatly varies. Moreover, the traffic flow of cell 2 is relatively large, so that the calculation result is relatively stable and less affected by the change in the user’s predefined blocking rate.In order to study the influence of different numbers of edge servers on the utilization performance of edge resources, the proposed algorithm is implemented for different numbers of edge servers. The obtained results are shown in Figure11.Figure 11
The actual success rate of different numbers of edge servers.Figure11 shows that the results of the success rate of edge resource requests calculated by different numbers of edge servers are similar. In addition, they increase with the increase in the number of edge servers. The proposed method proposed is better than the mobile estimation, in terms of the actual success rate of edge resource requests. This is due to the fact that with the increase in the number of edge servers, the deployment is relatively balanced, which alleviates the prediction error caused by the high mobility of the driving, to a certain extent.Based on the experimental results obtained from the three perspectives of user’s predefined blocking rate, number of vehicles, and region, the proposed method allows to obtain the minimum number of cloud servers in different cells and alleviate the emergency needs of the request after failing to offload to edge devices.In order to study the relationship between the number of servers in Cloudlet and different edge resource allocation methods, experiments on continuous values ofϵ under the condition of different numbers of edge servers are performed. The obtained results are shown in Figure 12. It can be seen that, as the value of ϵ decreases, the number of cloud servers slowly increases, and the average value becomes close to 11. The resultant value based on the motion estimation method is almost 12.Figure 12
The minimum number of servers in Cloudlet using different methods.In order to evaluate the influence of different numbers of vehicles on the minimum number of servers in Cloudlet, subsets with different numbers of vehicles are randomly selected from the trajectory dataset on the 17th, and edge resource allocation is performed on different subsets under different values ofϵ and motion estimation methods, with 1169 servers. The obtained results are shown in Figure 13.Figure 13
The minimum number of servers in Cloudlet for different numbers of vehicles.Figure13 shows that, as the number of vehicles increases, the minimum number of servers in Cloudlet that need to be deployed gradually increases, and the gap between the different values of ϵ gradually increases. This is mainly due to the fact that, when the value of ϵ is determined, the more the number of vehicles is, the more requests blocked are sent by vehicles, and the more cloud servers are required.The main conclusions are summarized based on the experimental results. (1) The motion estimation method seemingly fail to be applied in practice, and the method proposed in this article not only reduces the redundant cost of resource allocation but also approaches the result of the complete configuration method. (2) The method proposed in this article can effectively improve the actual use efficiency of edge servers, thereby reducing the deployment cost of servers in Cloudlet. (3) The method proposed in this article conducts the optimization in resource provisioning in each period while ensuring QoS service quality.


## 11. Conclusion

In this article, starting from the demand for edge resources of connected vehicles and the resource allocation benefits of the entire edge system, an edge resource allocation and selection method based on vehicle trajectory prediction is proposed. The proposed algorithm fully considers the high mobility of vehicles and the characteristics of historical traffic flow. It divides the minimum number of edge resources and deploys minimum servers in Cloudlet on the premise of not being higher than the user’s predefined blocking rate. The experimental results demonstrate that the proposed algorithm has a high performance in edge resource utilization and a high prediction accuracy.The future work should include the upgrading of mobility estimation strategy and requests allocation method between on-board-unit, edge server and cloud. The upgrading of mobility estimation strategy is replacing the cell in which a connected vehicle most likely appear withkk>2 cells and weight these different cells. Another possible future goal consists in improving the success rate of edge resource requests using the proposed method by dynamic allocation of edge server clusters, according to the driving conditions of connected vehicles and the load conditions of edge servers.



---

*Source: 5090875-2022-05-09.xml*