# A Location and Velocity Prediction-Assisted FANET Networking Scheme for Highly Mobile Scenarios
## 4 Network Clustering
### Dynamic Clustering Evaluation  
#### 4.3.1 Communication Overhead Metric  
In our proposal, the network is established based on the concept of cluster intending to manage nodes separately and autonomously [24]. The clustering algorithm is usually conducted based on some metrics such as Euclidean distance, cosine distance, Hamming distance, etc. For a given cluster, it consists of a CH and several nearby cluster members (CMs) which are reachable from the CH by single or multiple hops. As such, they need to exchange messages periodically to maintain the existing topology or form a new one. The number of changed edges is highly related to the communication overheads. If a link connecting two nodes breaks, the involved nodes will send cooperative awareness messages (CAMs), containing key safety-related information such as speed and position, and they wait responses from the nearby nodes. Then, a new link will be established with another CH. It can be seen that the new link is established at a cost of additional CAMs. The more links change, the more CAMs are required. Consequently, it is reasonable to use the number of changed links to measure the communication overheads in this paper. Nonetheless, mobile nodes cause time-varying network topology, especially in high-mobility scenarios, yielding rapid cluster stability degradation. As such, it is essential to check and update the network topology periodically and select new CHs for a purpose of adapting to new environments. Generally speaking, the topology variation contains the CM change case and the CH change case. As shown in Figure 4a, for a given topology structure at time \(t\), assume two clusters are constructed and the node \(n_{kj}(t)\) is grouped into the \(k\)-th cluster at time \(t\). As time proceeds, node \(n_{kj}(t)\) moves forward to a new position, which will be classified into the \((k+1)\)-th cluster, denoted as \(n_{k+1,i}(t+\Delta t)\). To complete this procedure, the CHs of these involved two clusters need to exchange control overheads. The second case involving the change of CH is presented in Figure 4b, which indicates the CH of the \(k\)-th cluster changes from time \(t\) to \(t+\Delta t\). Obviously, this case results in more changed links. For instance, a new single-hop link needs to be established in Figure 4a, whereas four new single-hop links are involved in Figure 4b. Assuming the communication overhead cost is proportional to the number of changed links, we consequently focus on this aspect during the mobile process in the following text. To quantify the changed link number, we abstract the topology into an undirected graph with an expression of \(\mathcal{G}=\{V,E\}\) herein, where \(V\) means the vertex set of all nodes, and \(E\) is the edge set connecting two adjacent nodes. To depict the connection relationship between nodes, we establish a binary connection matrix with an expression of \(C=[c_{ij}]_{N\times N}\). As for the matrix element \(c_{ij}\), its value is set according to nodes' connection relationships, i.e.,  
\[c_{ij}= \begin{cases}0&n_{i}\leftrightarrow n_{j}\\ 1&n_{i}\leftrightarrow n_{j}\end{cases}  \tag{20}\]Obviously, if node \(n_{i}\) is connected to \(n_{j}\) directly, then \(c_{ij}=1\). Otherwise, \(c_{ij}=0\). On this basis, the changed edge can be found by comparing two adjacent connection matrices, which is  
\[\mathbf{D}(t,t+\Delta t)=\mathbf{C}(t)\oplus\mathbf{C}(t+\Delta t), \tag{21}\]  
where symbol \"\(\oplus\)\" is the exclusive or operator. Since the connection matrix \(\mathbf{C}\) is symmetric, the changed edge number from time \(t\) to \(t+\Delta t\) can be expressed as  
\[N_{c}=card\{\mathbf{D}\
eq 0\}/2, \tag{22}\]  
where function \(card\{\cdot\}\) calculates the cardinal number of a set.