# An Improved Weighted and Location-Based Clustering Scheme for Flying Ad Hoc Networks
## 3 Preliminaries
### An Improved Weighted and Location-Based Clustering Scheme  
#### Cluster Formation  
The initial number of clusters determination is as follows: In the clustering process, to reduce the clustering overhead and utilize the bandwidth efficiently, the primary number of clusters needs to be optimally determined for the initial clustering center selection. According to [29], the throughput of each CM is  
\[T_{CM}=\Theta(B_{1}/\sqrt{N/k}) \tag{1}\]  
In addition, the throughput of each CH is  
\[T_{CH}=\Theta(B_{2}/\sqrt{k}) \tag{2}\]  
where \(N\) is the number of UAVs, and \(k\) is the number of clusters. \(\Theta(0)\) is the asymptotically tight bound. \(B_{1}\) and \(B_{2}\) are the bandwidth of intra- and inter-cluster communications, respectively. It assumes that the network traffic is uniformly distributed. Because of the throughput balance between the inter-cluster and the intra-cluster communications,  
Figure 1: UAV clustering network structure. Figure 2: HELLO message structure. the proportion of \(T_{CM}\) of a CH used for traffic in/out to other clusters is \((k-1)/k\), and the portion should be smaller or equal to \(T_{CH}\) of that CH [30],  
\[\frac{k-1}{k}T_{CM}\leq T_{CH} \tag{3}\]  
When \(\frac{k-1}{k}T_{CH}\) reaches the maximum throughput, namely, when inequality Equation (3) holds, the primary number of clusters \(k^{*}\) is obtained as  
\[k^{*}=\frac{B_{2}}{B_{1}}\sqrt{N}+1 \tag{4}\]  
If \(N\) is large enough, the number of clusters is approximated to  
\[k^{*}=\frac{B_{2}}{B_{1}}\sqrt{N} \tag{5}\]  
Based on the primary value \(k^{*}\), K-means++ clustering algorithm is further developed to divide \(N\) UAVs into clusters. The K-means++ clustering algorithm can reduce the error of the clustering result and the computational complexity. The UAV nodes are modeled as a point set \(S=\{s_{1},s_{2},\ldots s_{i}\ldots,s_{N}\}\). The procedures of the algorithm are stated as follows. _The initial clustering center selection is as follows_: An initial clustering center \(c_{1}\) is randomly selected from set \(S\), following the uniform distribution. The minimum distance, namely the minimum value of the Euclidean distances between a point \(s_{i}\) and the currently selected clustering centers is denoted as \(D(s_{i})\). Then, we calculate the probability that a point \(s_{i}\) in \(S\) is selected as the next clustering center by using the following equation:  
\[P(s_{i})=\frac{D(s_{i})^{2}}{\sum_{s_{i}\in S}D(s_{i})^{2}} \tag{6}\]  
We select the point with the highest probability as the next center \(c_{i}\). We repeat the above process until a total \(k^{*}\) centers have been chosen, which can be expressed as the set \(C=\{c_{1},c_{2},\ldots,c_{k^{*}}\}\). The \(k^{*}\) centers will be used as the original clustering centers for the K-means++ clustering. _The cluster formation is as follows_: With the original clustering centers, the set \(S\) can be divided into \(k^{*}\) clusters by finding the closest clustering center. The minimum distance from a point \(s_{i}\) in \(S\) to a clustering center can be expressed as \(d_{cs_{i}}\). \[d_{cs_{i}}=\min(d_{c_{1}s_{i}},d_{c_{2}s_{i}},\ldots,d_{c_{k^{*}}s_{i}}) \tag{7}\]  
The point \(s_{i}\) should be clustered into the \(n^{th}\) cluster, if \(d_{cs_{i}}=d_{cs_{i}}\). Then, the clustering centers are updated using the following equation:  
\[C=\{\frac{1}{N_{n}}(\sum_{i=1}^{N_{n}}x_{i},\sum_{i=1}^{N_{n}}y_{i},\sum_{i=1} ^{N_{n}}z_{i})\} \tag{8}\]  
where \(C\) denotes the set of clustering centers and \(N_{n}\) is the number of points in the \(n^{th}\) cluster. The steps (7) and (8) will be repeated until \(C\) convergence. During this process, the actual number of clusters \(K\) could be less than the initial number of clusters \(k^{*}\). The reason is that the adaptive clustering procedure merges the clusters close to each other, to mitigate the cluster with isolated or few numbers of nodes. The pseudocode of the K-means++ clustering algorithm is listed in Algorithm 1.