## 3 Multi-hop Cluster Based Stable Backbone Trees (MCBT)
### The Clustering Algorithm  
The proposed cluster formation consists of three steps. First, each node calculates its own flooding value in round \(0\), as mentioned in the previous subsection, and maintains the \((2d+1)\) sized FloodingArray. Second, this is followed by the Floodmax and Floodmin stage; each stage is performed for \(d\) rounds in which each node propagates the flooding value to its \(d\)-hop neighbors. The elements from \(1^{st}\) to \(d^{th}\) in the FloodingArray are the selected the flooding values in Floodmax and the rest from \((d+1)^{th}\) to \((2d)^{th}\) in FloodingArray are the selected flooding values in Floodmin. Finally, after Floodmax and Floodmin, each node looks at the all elements in FloodingArray to best determine its cluster head. The detailed procedures of Floodmax and Floodmin in the second step are as follows:  
_Definition 4_ (Floodmax-\(i\)) - In round \(i\)\((1\leq i\leq d)\) of Floodmax-\(i\), each node broadcasts its flooding value in the round \((i-1)\) and selects the maximum value among its own flooding value and the flooding values received from neighbors, and records it as the \(i^{th}\) element in FloodingArray. This process runs for \(d\) rounds. **Definition 5** (Floodmax-\(j\)) - After Floodmax, Floodmin is performed for \(d\) rounds. In round \(j\)\((d+1\leq j\leq 2d)\) of Floodmin-\(j\), each node broadcasts its flooding value in the round \((j-1)\) and selects the minimum value among its own flooding value and the flooding values received from neighbors, and records it as the \(j^{th}\) element in FloodingArray. In Floodmax, the nodes with the higher flooding value propagate their flooding value in the \(0^{th}\) round to their node's \(d\)-hop neighbors. Therefore, the flooding values selected by each node in Floodmax-\(d\) are the maximum values in the overall network. The nodes with this flooding value are finally selected as cluster heads. However, if nodes with the same flooding value in Floodmax-\(d\) are grouped, there would be a heavy load on the node with the highest flooding value, because the number of cluster members of nodes with higher flooding value increases. Floodmin balances the cluster heads' load by evenly distributing the number of cluster members. Floodmin has the similar process as Floodmax, but each node selects the minimum value among its own flooding value and the flooding values received from neighbors. At the conclusion of Floodmin, the flooding values selected in Floodmax-\(d\) are evenly distributed through the overall network by further propagating lower flooding values. Figure 1 shows a demonstration of Floodmax and Floodmin. Figure 2 presents the network topology with 16 nodes. For simplicity, it is assumed that the weight factor (\(\omega\)) is 1 and the initial energy of each node is 100. Each node records the \(0^{th}\) element in FloodingArray by computing the flooding value using its residual energy and degree. In the case of node 3, the residual energy is 31, thus the flooding value is 0.31 according to Equation (1). In Floodmax-\(1\), each node chooses the largest value among its own flooding value and the flooding values of \(1\)-hop neighbors and records the selected flooding value as \(1^{st}\) element in its FloodingArray. Node 3 selects the highest value, 0.77 among 0.31, 0.42, 0.40, and 0.77, the flooding values in the \(0^{th}\) round of node 3 and its neighbors 1, 2, 5, respectively. In Floodmax-\(2\), 1.00 is selected as the maximum value among its own flooding value and the flooding values of neighbors in Floodmax-\(1\). Figure 2 shows the groups of nodes that select the same flooding value in Floodmax-\(2\). Among the 16 nodes, 11 nodes select the highest flooding value in Floodmax-\(2\), 1.00. Floodmax is a greedy algorithm and may result in an unbalanced load for the cluster heads. However, using Floodmin, we can evenly distribute the flooding values selected in Floodmax-\(d\) to the overall network.