UAV assisted communication for ground users using machine learning and optimization

Vehicle representation

The system model depicted in Figure 1 is divided into three distinct blocks. The first is the data pre-processing, where vehicle location and timestamp information are taken from the Beijing vehicle location dataset in paper ^[10], and ^[11]. Each location data point that falls within the chosen area $$ R $$ has the vehicle ID $$ V_{id} $$ labeled on it. The latitude, longitude, and associated time stamp $$ T $$ are all included in the location data $$ V_{id}^{loc}(t) $$ . Every minute, the data is extracted, cleaned, and stored in a CSV file. In Equation (1), the exact structure of the location data, $$ V_{id}^{loc}(t) $$ , is presented.

Figure 1. System model.

The second block consist of density computation and prediction part, which uses the data from the preceding unit. The traffic density estimation algorithm is then used to calculate the vehicle count. The region $$ R $$ is further subdivided into numerous grids denoted by the symbol $$ G_{ij} $$ , where $$ i, j $$ represent row and column values. The densities are collected as a time series data $$ D_{ij}(t) $$ for each grid. The density $$ D {ij}(t) $$ is the amount of vehicles present in $$ G_{ij} $$ at time $$ t $$ , and it is computed using an algorithm (1).

In the second block, the grid density prediction algorithm, which is built with LSTM neural networks, takes in each grid data $$ G ij $$ . Using previous density values $$ D_ij(t), $$ the prediction algorithm forecasts density values for the future time window $$ t_w $$ .

The final block, known as the optimization block, includes the average number of data packets that each vehicle will transmit as well as the real capacity, $$ R^{cap}_{ij} $$ . The real capacity is calculated using the capacity $$ cap $$ of the communication unit and the signal to interference noise ratio $$ SINR $$ value. Finally, the required number of UAVs to support the vehicles in each grid is determined by sending these two values and constraints into an optimization algorithm.

LSTM modeling

A recurrent neural network-based algorithm called long short-term memory (LSTM algorithm) as in paper ^[12] is applied to obtain the vehicles' anticipated latitude and longitude coordinates. The mentioned algorithm has advantages in compensation for the vanishing gradient problem, which is apparent in recurrent neural networks. The input layer of the LSTM model would take in the location data in the past, e.g., $$ V_{id}^{loc}(t) $$ . Then, it would pass the information to the hidden layers, where there are three categories of gates that determine whether to remember the input sequence or not. These types of gates include forget gates, update gates, and output gates. The value of forget gate $$ \Gamma_f^i $$ is computed in Equation (2) using the aforementioned activation function parameters with bias term. The time reference $$ t $$ in the formula represents the current time, the $$ t-1 $$ represents the past time, and the index number $$ i $$ represents the vehicle ID of the target vehicle. In the same way, the values of update gate $$ \Gamma_u $$ and output gate $$ \Gamma_o $$ are calculated similarly using the activation function in Equation (3) and Equation (4).

A toddler memory unit is also introduced in the hidden layer, and its value is determined through the hyperbolic tangent $$ tanh $$ activation function. The system then determines the memory cell unit value by combining the forget gate value, the output gate value, and the toddler memory unit value. Finally, as discussed in Equation (5) and Equation (6), the prediction $$ \hat{Y} $$ is generated by passing the memory cell and output gate value into $$ tanh $$ and $$ softmax $$ in sequence.

Traffic density analysis

An algorithm is designed as in Algorithm 1 to predict each grid's density value at time reference $$ j $$ . The map is evenly divided into 20 by 20 grids. For each grid, we create a time-dependent series of density values, e.g., $$ Den_{latID_lonID} $$ , where $$ latID $$ denotes that the grid is the $$ latID $$ 'th grid from lower latitude value to higher latitude value, and $$ lonID $$ denotes that it is the $$ lonID $$ 'th grid from lower longitude value to higher longitude value.

In the algorithm, the system scans through each vehicle, e.g., $$ V_{id} $$ , location in terms of latitude and longitude at each time reference $$ j $$ and determine each corresponding grid id $$ G_{latID_lonID} $$ for each moment using a while loop. The determined grid id is recorded by incrementation of the corresponding density value $$ Den_{latID_lonID} $$ . More specifically, at each time reference for each vehicle, a comparison is made between the recorded latitude and longitude value and a set of boundaries $$ latn, lonn $$ to determine the resulted $$ latID $$ and $$ lonID $$ , which denotes the corresponding grid. The system then increment the density value $$ Den_{latID_lonID} $$ . As a result, the recorded $$ Den_{latID_lonID} $$ is presented in the matrix below.

The resulting traffic density data is recorded as shown in Figure??, where $$ Den_{mn} $$ represents the traffic density value in different grids with respect to their time-stamp $$ t $$ .

Linear optimization

Linear programming (LP) optimization is a method for the optimization of objective function, dependent upon equality or inequality constraints. It is used in various fields of engineering to make the process cost effective and efficient. Currently they are used in energy, manufacturing and engineering sectors. There are several tools and libraries available to solve the LP problem. In this work PULP as in article ^[29] a python based library is used to model the objective function. The Equation 4.4 has the objective function $$ F(X) $$ and the objective variable to be minimized is $$ X $$ . The constraint X $$ > $$ 0 and Ax $$ > $$ b makes the objective variable to be not less that or equal to zero and the coefficients A and b maintains the objective variable X with in the bounds. These two are the conditions defining the convex polytope across which the objective function should be minimized. The function $$ G(X) $$ in Equation 4.4 is another way of expressing the inequality constraint equation. Where the function holds the value X with other coefficients to modify the optimization. It also has $$ g_{lb} $$ and $$ g_{ub} $$ , which are the upper and lower bounds of the function.

Figure 2. Matrix demonstration of traffic density data.

Quality of service requirements

This work aims not only to find the required number of UAVs but also to satisfy the quality of service requirements (QoS requirements. The QoS considered here is to maximize the throughput for the uplink scenario, i.e., to receive the data packets transmitted from the ground vehicles. Since the data packet size is very small, an ideal MAC layer is considered for this scenario. The QoS is determined using the probability of successfully transmitting data packets over a channel to the UAVs, as the SINR and channel capacity are the resources that significantly influence the transmission's performance. Therefore, the system is simulated in this work by including the SINR and the channel capacity as QoS parameters.

Optimization algorithm

The whole system aims to find the minimum number of UAVs to support the vehicles in each grid based on the supply and demands. Linear optimization is considered from paper ^[13] is used to develop a cost function for the problem. First, the UAV ($$ U $$ ), density ($$ D $$ ), throughput ($$ \lambda $$ ), capacity ($$ cap $$ ), and the Signal to Noise Ratio ($$ SINR $$ ) are initialized, and from these variables, the cost function is derived as shown in Equation 9. The cost function is split into two different parts, the Equation 7 is the supply part, which determines the real capacity $$ R_{cap} $$ of each UAV to receive the data packets by including the $$ SINR $$ associated with it. Then the demand part is formulated using density $$ D $$ and throughput $$ \lambda $$ value. From Equation 8 the demand is found.

The cost function holds an objective variable, $$ U $$ , where $$ U $$ gets the number of UAVs to support the users. As the region's size is $$ 20X20 $$ , the variables $$ m $$ and $$ n $$ represent the grid size, and the objective function in Equation 9 is summed over the area to consider the density values at each grid. Finally, the communication unit's capacity ($$ cap $$ ) is also considered and used in the optimization function to determine the UAVs count.

Optimization variables are initialized to lower bound values and they are made to be subjected to $$ constraint1 $$ and $$ constraint2 $$ . The $$ constraint1 $$ in the model makes the objective function to be no less than zero, and $$ constraint2 $$ makes the UAV count to stay positive. The density of each grid is taken at a time to perform optimization on the objective function. Once the objective becomes zero, optimization is stopped. Finally, the output of the objective variables are taken, and they are merged to determine the final count of the UAV.

Problem setting

This project is based on data from Taxi Software's published trace files in China as in paper ^[10] with over ten thousands trace files. Each row of the trace file would record the driver's identification number, the date and time reference of the row, the Longitude, and the Latitude. An row demonstration for taxi driver with id 9862 is listed in table 2

For accuracy and convenience of grid prediction, this study eliminates repeating data points, applies a consistent interval approach as in article ^[30], and transfers the time reference from date and time into timestamps. Also, to balance the need for location accuracy and sufficient amounts of vehicle for prediction, the calculated is proceed in the center part of Beijing. The map is divided into 20 by 20 grids that are about 1.6km by 1.3 km.

Grid data analysis

With more than 10, 000 drivers' trace files, it was plausible to create a density map to describe the density characteristics in each grid. We defined the time-dependent grid density as the number of vehicles in it given a specific time.

Traffic density model prediction and results

We iterated through each driver's trace file and found the corresponding gird for each moment in our approach. If the vehicle were in the map chosen, we would increment the density in the landed grid. After going through all trace files, we gathered the density.

First, we needed to extract the data required for the grid's simulation and prediction from each driver. So we created a density file with 8882 minutes in length and four hundred grids in width. We then scanned through each driver's file and checked for the area it stayed at each reference. We then find the corresponding time reference and the grid of the vehicle's location in the density file and add one to the density number. Thus, after scanning through all the driver's data files, we successfully extracted the density file we desired. A preview of the desired file is shown in Table 3:

Table 3

Preview of density file

Time	A_1, 1	A_1, 2	A_1, 3	......	A_2, 1	A_2, 2	A_2, 3	......	A_20, 18	A_20, 19	A_20, 20
0	0	0	0	......	0	0	0	......	0	2	2
61	0	0	0	......	0	0	0	......	0	3	2
......	......	......	......	......	......	......	......	......	......	......	......
18001	0	0	0	......	0	0	0	......	4	2	1
18061	0	0	0	......	0	0	0	......	4	2	1
......	......	......	......	......	......	......	......	......	......	......	......
532801	0	0	0	......	1	0	0	......	0	0	0
532861	0	0	0	......	0	0	0	......	0	0	0

After having the grid's density data for each time reference, we could train each grid individually using LSTM models. We utilized an LSTM model with two layers with n units, a dropout of 0.05, and a dense layer with one unit. We used three epochs and a batch size of thirty while fitting. For accuracy, we could see that using the same model for all four hundred grids is a challenge, while it was not practical to form four hundred different models. One approach is to normalize all the processing data into the desired range. Since the model described above performs better when predicting series about five, we built the normalization this way:

（10） $$ {D'_i}=\frac{D_i}{\bar{D}}+5 $$

In the above equation, $$ D'_i $$ was the normalized density, $$ D_i $$ was the original density, and $$ \bar{D} $$ was the average of densities in a specific grid. We also rounded the predicted result since densities should only be non-negative integers. In coordination with the application and other models, we would use the first eight thousand minutes for training and the sixty minutes right after the training data for testing. After normalization, the predictions of each grid were acceptable for describing the density of each grid at a given time. A graph representing the training data and the prediction for lower density value is shown in Figure 3.

Figure 3. Grid density training example for small density (density less than 2).

We see this model would successfully capture the character of a lower density grid. A graph representing the training data and the prediction for density value up to ten is as shown in Figure 4.

Figure 4. Grid density training example for average density (density of about 10).

Again, the models gave an acceptable range of density that is accurate enough in comparing densities during path planning. A graph representing the training data and the prediction for density value up to thirty is as shown in Figure 5

Figure 5. Grid density training example for large density (density of about 30).

The models gave an acceptable range of density that was accurate enough in comparing densities during path planning. Throughout all the grids, almost all of the densities were below sixty, and the above three situations should be representative enough to prove the accuracy of our models.

After modeling for all the grids, we tested the validations and their root-mean-square-error for each model. We could see that all the root-mean-square-error are less than one, meaning that the density difference between reality and prediction is less than one vehicle per grid in each minute, which was acceptable for our path planning. Demonstrations of the testing results are included in Figures. 6, 7, and 8.

Figure 6. Grid density testing example for area with longitude id of 6 and latitude id of 10.

Figure 7. Grid density testing example for area with longitude id of 7 and latitude id of 8.

Figure 8. Grid density testing example for area with longitude id of 10 and latitude id of 1.

Optimization results

After getting appropriate traffic density values in each grid, the optimization algorithm elaborated in the problem formulation is obtained to find the number of UAVs allocated for each grid. For that, the traffic grid density data is collected, and the SINR is chosen as the Quality of Service Parameter. The grid is nothing but the area that is chosen during map processing, where the beijing downtown has been subdivided into smaller regions (grids). Based on the vehicle count in each grid, the UAVs to support them are found.

The simulation part of the system uses the input density data $$ D_{ij} $$ from each grid, the throughput $$ \lambda_{ij} $$ , and the actual capacity $$ R^{cap}_{ij} $$ value for that specific grid, as indicated in Equation. A region of 100 grids with a high density is chosen for simulation purposes. The settings used for simulation are shown in Table 4; the capacity $$ cap $$ is set to 30 and the $$ SINR $$ is supplied as a range of values between 0.5 and 1. Throughput $$ \lambda $$ represents the number of packets transferred from each user, and transmission power of the communication unit is set to 1 W. For the purpose of determining the necessary number of UAVs for the specified region, the Eq 9 is simulated for various $$ SINR $$ values.

Two inequality constraints in 9 are included in the optimization problem, and the optimization function should satisfy them. The cost function and optimization variables $$ U $$ are then used to feed the numerical data and constraints into the cost function to determine the UAV count. The value of the variable $$ U $$ is determined based on the supply and demand components throughout each loop, with the goal of the model being to approach the minimal value, which is close to or equal to zero.

After the first set of simulations, Figure. 9 shows the users' density in each grid and associated UAVs for it. Based on the QoS parameter, i.e., at SINR 0.75 and the quantity of users in each grid, the UAVs are pushed through optimization to support the ground users. The graph also shows that UAV count is incremented whenever the users count reaches or exceeds the capacity of the communication unit. Figure 10 shows the result of UAVs for each grid concerning different SINR values. Basically, it depicts how the UAV count varies based on different SINR values. When the interference increases the count of UAVs are also increased regardless of the users count. To give a detailed picture, Figure 11 shows the count of UAVs with respect to the vehicle densities and different SINR values.

Figure 9. Vehicle Density Vs UAV count (with respect to each grid).

Figure 10. UAV count with respect to grid for different SINR values.

Figure 11. UAV count with respect to vehicles.

From Figure 12, a minimum of 20 UAVs are required to support a region when SINR is high. At the same time, when SINR becomes low, extra UAVs are pushed to maintain the QoS requirements. As a result, the UAV count becomes 32 to support the same users. The results show that the optimization algorithm finds the minimum number of UAVs by maintaining the QoS and thus it improves the quality of the connection by 50% to support the users.

Figure 12. UAV count with respect to SINR values.

Authors' contributions

Major contributions in doing the simulation and writing the paper: Ravi P, Zang T

Revision of the manuscript: Wang M

Validation of results and Manuscript revision: Scott MJ, Wang M

All authors read and approved the final manuscript.

Availability of data and materials

Not applicable.

Financial support and sponsorship

None.

Conflicts of interest

All authors declared that there are no conflicts of interest.

Ethical approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Copyright

© The Author(s) 2022.