# Optimized Dynamic Deployment of UAVs in Maritime Networks with Route Prediction
## 4 Proposed Algorithm
### Ship Trajectory-Prediction Algorithm Based on Improved LSTM  
To improve the accuracy of ship route prediction, this section proposes an LSTM model optimized based on the Sparrow Search Algorithm (SSA) for optimal prediction of AIS datasets. The LSTM performs well in dealing with time-series prediction tasks (e.g., ship route prediction), whereas by mimicking the behavior of sparrow foraging, the SSA can be optimized in a complex, high-dimensional search space hyperparameters of LSTM. Therefore, combining SSA with LSTM can automatically optimize the hyperparameters to improve the prediction performance of the model. The AIS dataset contains data such as latitude, longitude, heading, and speed of different numbered vessels at each moment in the past period, so we performed preprocessing operations on the AIS dataset. First, we performed feature selection and extracted the four features of latitude, longitude, speed (Sog), and heading (Cog) from the ship trajectory data as the input feature matrix \(x\), and the target value \(y\) was set to be the latitude and longitude of the next time step. Then, the input data \(X_{t}=[X_{t-N},X_{t-N+1},\ldots,X_{t-1}]\) and output data \(\gamma_{t}=[lat_{t},lon_{t}]\) are constructed into a time series, and the data of the past \(N\) time steps are used to predict the target value of the next time step, to capture the temporal features and dynamics. To avoid the impact of magnitude differences between feature values on model training, we use min-max normalization to scale the input features and target values into the interval [0, 1]. When inputting the input features into the input layer of the LSTM, we converted them into a 3D tensor that can represent the feature data for multiple time steps, i.e., [number of samples, time step \(N\), number of features], where the number of samples represents the number of time series samples that can be created for the entire dataset, and the number of features is represented as four features (latitude, longitude, speed, and heading) for each time point. In the hidden layer, the LSTM unit processes the input data through a memory and forgetting mechanism to capture the long-term dependencies in the time series. Considering the model performance, training efficiency, and avoiding the risk of overfitting, two LSTM hidden layers are used in the model, and the number of neurons in the first and second layers is set to \(h_{1}\) and \(h_{2}\), respectively, which will be optimized by the SSA. The LSTM updates the hidden state through the gating structure, and the state of the hidden layer's output at the last time step, \(h_{t}\), is denoted by Equation (33), where \(W_{\text{hid}}\) is the weight matrix of the hidden layer, \(b_{\text{hid}}\) is the bias term, and \(f\) is the nonlinear activation function of the LSTM. In the output layer, the model maps \(h_{t}\) to the predicted longitude and latitude, which is calculated as in Equation (34), where \(W_{\text{out}}\) is the weight matrix of the output layer and \(b_{\text{out}}\) is the bias term. \[h_{t}=f(W_{\text{hid}}\cdot X_{t}+b_{\text{hid}}) \tag{33}\]  
\[Y_{t}=W_{\text{out}}\cdot h_{t}+b_{\text{out}} \tag{34}\]  
Finally, we use the mean square error to measure the difference between the predicted and true values of the model, continuously minimize the loss function, and update the weights and biases through the Adam optimizer to improve the prediction accuracy. To prevent overfitting, we introduce L2 regularization in the training process of LSTM networks. The complexity of the model is limited by adding a penalty term \(\lambda\) proportional to the sum of squares of the weights to the loss function, which improves the generalization performance of the model and reduces the risk of overfitting on the training data, and the formula is specified as follows:  
\[L_{\text{total}}=L_{\text{loss}}+\lambda(\|W_{\text{hid}}\|^{2}+\|W_{\text{ out}}\|^{2}) \tag{35}\]  
Here, we optimize the hyperparameters of the LSTM, i.e., the learning rate, epoch, and the number of hidden layer neurons.