Multi-Component V2X Applications Placement in Edge Computing Environment

In the reference model used for the placement of V2X basic services, HWY 416 IC-721A that passes through the city of Ottawa is considered. The edge computing servers are deployed uniformly along the highway as the deployment of RSU is out of the scope of this paper. No communication interference zone exists between any two successive RSUs to avoid the possibility of encountering ping-pong handover cases which will be difficult to handle in an optimization model. Additionally, the vehicles are assumed to be always connected to RSUs throughout their journey. The end-to-end latency of a service is the sum of the communication, processing, transmission and propagation delay. The propagation delay is dependent on the medium of communication which is out of the scope of this paper, and therefore considered negligible. In this model, DSRC, the communication technology between the moving vehicles and RSUs, affects the communication delay. In the proposed model, the processing and transmission delay between the communicated edge servers is considered. Each edge computing server has the same computing and processing power that are expressed by the number of cores and RAM available. Finally, the vehicle density is considered to model real case scenarios.

In the optimization function, a set of edge servers and V2X services are considered. Let $N$ denote the set of edge servers where $n\in N.$ Let $U$ denote the set of unique V2X basic services where $u\in U.$ The availability of the computational resources on the edge is denoted by matrix $Cap$ where $Cap_{kn}$ denotes the $k$th computational resources available on edge server $n$. Matrix $R$ represents the resources required by the V2X basic services where $R_{ku}$ represents the $k$th computational resources required by V2X basic service $u.$ A binary row vector $\overrightarrow{q}$ denotes the edge servers a vehicle can communicate with. Let $C$ be the matrix that represents the processing and the transmission latency between edge servers where $C_{ij}$ represents the latency between edge server $i$ and edge server $j$. Matrix $M$ represents the V2X services needed by V2X applications where $M_{au}=1$ denotes that application $a$ needs V2X basic service $u$. Let $X$ denote the placement matrix where $X_{un}=1$ means that V2X basic service $u$ is placed on edge server $n$. The column $X_{u}$ denotes the placement of the V2X services on edge server $n$. $D_{a}^{v}$ and $D_{a}^{th}$ denote respectively the delay experienced by a moving vehicle $v$ served by application $a$ and the maximum tolerable threshold of this delay. To represent the vehicles’ density, $\gamma$ is used. $d_{com}^{v}$ and $d_{DL}^{v}$ denote respectively the communication and download latency between a vehicle $v$ and a serving edge server. The optimization function used to minimize the delay of V2X application is as follows:

where:

subject to:

In what follows, the explanation of the equations (1)-(5). Equation (1) describes the overall objective which is minimizing the summation of the delay of all V2X application experienced by a vehicle requesting their services. Equation (2) presents the components contributing to the delay of V2X application. The delay of a V2X application is the delay of the V2X services it relies on depending on the edge servers a vehicle can communicate with. Because the functioning of a V2X basic service is independent of other V2X basic services, the delay of a V2X application is defined as the maximum of the delay of its constituent V2X basic services. This value is added to the communication and download link delay. Next, the equations (3) – (5) describe the constraints. Equation (3) defines that the delay of an application should not exceed its maximum defined tolerable delay. Equation (4) ensures that the resources allocated to a V2X service do not exceed the available resource on the hosting edge server. Equation (5) limits placing only one V2X service on each edge server. The following diagram illustrates an example of the communication and processing that takes place for a V2X application that requires CA and DEN services, given that each server has resources reserved for migrating applications denoted by VM 3.

The logic governing the realization of the application is as follows:

(1) The vehicle requests the services of an application. This step incurs communication delay that is denoted by $d_{com}^{v}.$

(2) The CA service found on Edge Server 1 requests the necessary information from the LDM. The processing of the request on the LDM is denoted by $C_{11}$.

(3) Edge server 1 communicates with the closest server that include DEN basic service. No delay is considered in this phase.

(4) DEN queries and receives information from the LDM that is closest to the requesting vehicle. The LDM on edge server 1 has accurate information about the requesting vehicle’s surrounding environment. This delay is the sum of the processing delay of LDM on edge server 1 and the transmission delay between edge server 1 and 2. This is denoted by $C_{12}.$

(5, 6) These steps represent the CA and DEN response to the requesting vehicle. This delay is denoted by $d_{DL}^{v}$.

For basic service CA, the delay is as follows:

Similarly, the delay for DEN is:

Given that the requests for each basic service are executed in parallel and that these services are independent in their execution, the delay experienced by a vehicle $v$ requesting the services of application $a$ is:

In order to evaluate the placement of V2X basic services, a realistic simulation environment must be created. To this end, Simulation of Urban Mobility (SUMO) [17] was used to extract the movement of vehicles along a highway. A 4 km highway that resembles HWY 416 IC-712A was considered as a reference highway. Ontario traffic volume for provincial highways [18] provided the average daily traffic and the accident rates during summer, winter, weekdays and weekends. In the simulation setup, the statistics offered by this report were used to emulate moderate and heavy traffic experienced on HWY 416 IC-712A highway that is expressed through the vehicles per hour parameter in SUMO. Regarding the movement of the vehicles, Table I summarizes the key parameters that are used in the simulation.

The V2X applications considered are Platooning (PL), Sensor and Sensor State Mapping (SSM), Emergency Stop (ES), Pre-crash Sensing Warning (PSW) and Forward Collision Warning (FCW). Their corresponding performance requirements and service components are presented in Table II [19, 20]. Choosing these V2X applications stems from their importance and stringent performance requirements in the realm of the autonomous cars. In addition, in the context of the defined problem, each of the chosen V2X application offers a unique combination of V2X services. In the simulation procedure, the communication delay between a vehicle and an RSU is 1 ms [21]. In this model, the processing delay is the amount of time required by a Local Dynamic Map to process the data requested by other V2X services either placed on the same or different edge server. In [22], the authors devise an LDM according to the specifications defined by ETSI. The application defines two Application Programming Interfaces (APIs) that retrieve information of the IDs of the vehicles driving on the same road and the vehicle driving immediately ahead of the requesting vehicle. For different number of queried vehicles ranging from 5 to 20 vehicles, the response time was between 3 and 5 ms with no clear correlation between the size of the data and the response time. Consequently, in the simulation setup, the processing delay is generated uniformly between 3 and 5 ms. In the same context, the authors in [23], assumed the transmission latency between two edge servers to be between 1 and 5 ms. Because the simulation procedure takes place under several vehicle densities, the increase of the data processing and transmission overhead with the increase of number of vehicles is inevitable. In this regard, the execution cost increases with the number of vehicles in proximity to the vehicle requesting the V2X application services. As the implementation of LDM did not consider cases beyond 20 vehicles, the added delay for these cases will be in the form of $\log(NC/20)$ where $NC$ represents the number of cars and the expression is derived from the increase of processing delay upon the increase in size of the queried data in SQL [24]. In terms of edge servers, 10 edge servers are deployed every 400 m alongside the highway. Each of the RSUs hosts an LDM, V2X service and an optional migrating service. The computational requirements of CA, DEN and Media services are those of a small, medium and large VMs. Table III summarizes the edge server capabilities and the computational requirements of CA, DEN and Media services. In the experimental procedure, the placement of the V2X basic services is carried out using the defined optimization function. Next, traffic simulation is executed for defined densities that reflect moderate and heavy traffic. The traffic traces were generated for 1500 seconds. Every 10 seconds, a snapshot of the road condition is taken and delays for each V2X application for each vehicle is calculated. Finally, at the end of the simulation, the average delay for each V2X application is obtained.

The optimization function was solved using IBM ILOG CPLEX 12.9.0 through its Python API. The solution is provided instantly for all simulation scenarios with different vehicle densities on a laptop with an Intel Core i7-8750 CPU, 2.21 GHz clock frequency and 16 GB of RAM. The final solution includes the V2X services placed on each edge server.

To evaluate the efficacy of the optimization function, the simulation procedure was carried out using two different traffic scenarios each representing moderate (Scenario 1) and heavy (Scenario 2) traffic models. The results are obtained as an average for five independent runs. To assess the placement function, the average delay of each V2X application under study is obtained and compared it to the maximum tolerable delay. Additionally, the model is evaluated using the probability density function of each of V2X application. The density function provides a more thorough overview about the distribution of the delays in terms of detecting extreme values that are overshadowed by the common values trend. Furthermore, the density functions reveal the shortcomings of the approaches that are concealed by the calculation of the mean. The suggested optimization function failed to converge, so a new heuristic algorithm that relaxes the delay threshold for each application by magnitudes of the reliability metrics is considered and executed. This heuristic algorithm is referred to as: Resource and Delay-aware V2X basic service Placement (RDP). The results of the simulation process in terms of the average delay and the probability densities of each V2X application are presented in Figures 2-5.

Figure 2 shows the mean delay for each of the V2X applications. The results clearly show that the average delay experienced by each V2X application is within the tolerable threshold. These results show that the heuristic algorithm met the stringent V2X application delay requirements. In terms of the traffic effect, the mean of delay of each application has slightly increased but still fulfills the overall objective of the placement function. The vehicles’ density has contributed to an increase in the average delay of the V2X applications in the range of 1.3% to 4.8% whereby the SSM application has experienced the greatest variation. This fact shows that the placement of Media Service, that SSM relies on, is the most sensitive to traffic variation. On the other hand, the probability density functions tell a different story. Figures 3 and 4 depicting the delay distribution for both cases show that the delay is highly skewed to the left which supports the viability of the approach. However, this is not the case for FCW application which shows that for each scenario, 20% and 25% of the experienced delay exceeds the tolerable threshold which is beyond the 5% permitted shown in Table II. In terms of traffic effect, it is observed that there is a slight right shift of the probability distribution in scenario 2. Additionally, it is observed that some applications have similar probability distributions. This is attributed to the fact that these applications need the same V2X services, and as it shows, these services incur the most delay out of the other services that they rely on. The dispersion of some of the probability density function is due to the limited number of edge nodes hosting V2X services. The limited number of edge servers means that vehicles at the start and the end of the route will suffer from prolonged delay due to the distance separating the vehicles and the closest V2X basic services. In the cases of continued route, the suggested approach can be replicated along the highway to ensure that V2X services are delivered as expected. For comparison purposes and to further cement this paper’s approach, a baseline approach that maximizes the resource utilization at each node server is compared to RDP. The baseline approach formulates a placement algorithm that takes into consideration only the available resources at each node. This baseline approach is reffered to as Resource-Aware Algorithm (RAA). The two approaches were evaluated according to the probability density functions of the delays of ES and FCW applications. The probability densities are depicted in Figure 5.

The baseline line approach’s density function shows promising results regarding the ES application as the full delay distribution is below the tolerable threshold. More values are concentrated on the extremes which makes it harder to gauge its value whenever the application is requested. However, for the case of FCW, this approach fails to be within the tolerable threshold rendering this approach ineffective for mission-critical applications. This is to be expected given that FCW application requires CA and DEN basic services. Due to the nature of RAA that maximizes the overall resource utilization, deploying more of CA services results in decreasing the utilization which incurs extra delay for FCW application when requesting the services of CA.