# LoRaWAN Networking in Mobile Scenarios Using a WiFi Mesh of UAV Gateways
## 3 The LoRaUAV System
### Movement Prediction (MP) Algorithm  
The MP algorithm is a solution to recover isolated GNs based on a combination of movement prediction and virtual forces. This last characteristic allows to easily integrate the solution in the system and to preserve the simplicity of the LoRaUAV distributed approach. The algorithm is based on entities called _holograms_, whose purpose is to signal to UAVs the estimated position of isolated GNs. Figure 2: CRM algorithm. A hologram contains a pair of spatial coordinates that can be used to compute a virtual AtG force between the hologram itself and other UAVs. Since GNs are moving, the information about their last known position is not enough to create useful holograms. However, if GNs keep a regular direction and speed for some time, the future position of GNs can be predicted from previous recorded positions and the hologram location can be updated accordingly at each time step. In LoRaUAV, the prediction is based on simple kinematic rules. In order to estimate the kinematic rule parameters, the algorithm uses the GN position updates. The time must thus be treated as a sequence of discrete time steps. If we consider a GN \(i\) at time \(t\), its future coordinate \(x_{i(t+1)}\) is:  
\[x_{i(t+1)}=x_{it}+v_{it}^{x}+\frac{1}{2}\hat{a}_{it}^{x}\cdot\Delta t, \tag{12}\]  
where \(v_{it}\) and \(\hat{a}_{it}^{x}\) are respectively the velocity at time \(t\) and the expected variation of velocity (acceleration) within the update time interval \(\Delta t\). The latter also corresponds to the interval between \(t\) and \(t+1\). As will be seen in Equation (13), \(v_{it}\) is computed as the difference between \(x_{it}\) and \(x_{i(t-1)}\). As such, it already corresponds to the displacement within \(\Delta t\). The computation of all the necessary variables is based on the finite difference method and only requires the knowledge of the three most recent positions of a node, so that:  
\[\left\{ \begin{array}{c}v_{it}^{x}=x_{it}-x_{i(t-1)}\\ v_{i(t-1)}^{x}=x_{i(t-1)}-x_{i(t-2)}\\ v_{i(t-2)}^{x}=x_{i(t-2)}-x_{i(t-3)},\end{array} \right. \tag{13}\]  
\[\left\{ \begin{array}{c}\hat{a}_{it}^{x}=a_{i(t-1)}^{x}+\Delta a_{i(t-1)}^{x} \cdot\Delta t\\ \Delta a_{i(t-1)}^{x}=\frac{a_{i(t-1)}^{x}-a_{i(t-2)}^{x}}{\Delta t}\\ a_{i(t-2)}^{x}=\frac{v_{i(t-1)}^{x}-v_{i(t-2)}^{x}}{\Delta t}\\ a_{i(t-1)}^{x}=\frac{v_{it}^{x}-v_{i(t-1)}^{x}}{\Delta t},\end{array} \right. \tag{14}\]  
It should be noted that, as expected, velocity and acceleration are still related as follows:  
\[v_{i(t+1)}^{x}=v_{it}^{x}+\hat{a}_{it}^{x}\cdot\Delta t, \tag{15}\]  
A similar reasoning applies to coordinate \(y_{i}\). In the current version, in order to simplify the problem, only GNs with constant velocity are considered, so that only the two latest positions, separated at most by \(t_{r}\) seconds, are required. UAVs are responsible for keeping track of lost GNs (in the last \(t_{lost}\) seconds) and for sending to other UAVs the information needed to predict the location of holograms: the last known position of a GN, its velocity vector and the time of its latest recorded position. This information is included in a message called _token_, sent in unicast to every UAV in the routing table. A hologram is created for each token and an expiration timer \(t_{exp}\) is attached to it. To avoid disruptions of AtA and AtG forces, only UAVs that are inactive (\(load=0\)) are influenced by hologram forces. To reduce the amount of exchanged _tokens_, lost GNs can be first clustered in groups using a clustering algorithm. In LoRaUAV, _k-means_[14] is used for clustering and _k-means_++ [15] is used to initialize the centroids and speed up the convergence. The _k-means_ algorithm is run multiple times with different values of \(k\), with \(k\) ranging from 2 to \(k_{max}\), and the quality of the clustering is then assessed through the _average silhouette index_, a metric that measures the similarity among members of the same cluster and their dissimilarity from members of other clusters.