## 3 Multi-hop Cluster Based Stable Backbone Trees (MCBT)
### The Clustering Algorithm
Nodes 4 and 6 choose the cluster head with the minimum hops. Here it can be seen that there are three cluster heads (nodes 5, 9, and 11) whose energy is higher than that of the other nodes. Moreover, MCBT constructs three similar-sized clusters. **Algorithm:** MCBT Clustering Algorithm  
**Input:** Undirected Graph(\(G\)), residual energy(\(E_{res}\)), and \(d\)  
**Output:** Cluster heads' ID  
// FloodingArray\({}_{i}\): FloodingArray of node \(i\), CH\({}_{i}\): Cluster head' ID of node \(i\)  
**MCBT\((G,E_{res},d)\)**  
**01:**\(n\leftarrow\) The number of nodes  
**02:**for \(i\gets 1\) to \(n\)  
**03:**do \(f(i,\omega)\leftarrow\omega(\frac{E_{res}}{E_{ini}})+(1-\omega)(\frac{deg_{i}} {\max_{j\in S_{i}}(deg_{j})})\),  
where \(S_{i}\) is a set of neighbors of node \(i\) including itself  
**04:** FloodingArray\({}_{i}[0]\gets f(i,\omega)\)  
// Floodmax Phase  
**05:**for \(k\leftarrow\)1 to \(d\)  
**06:**do for \(i\gets 1\) to \(n\)  
**07:**do BROADCAST(FloodingArray\({}_{i}[k-1]\))  
// A node broadcasts its \((k-1)^{th}\) flooding value to neighbors and receive  
// all neighbors' \((k-1)^{th}\) flooding value  
**08:**do for \(i\gets 1\) to \(n\)  
**09:**do FloodingArray\({}_{i}[k]\leftarrow\max_{j\in S_{i}}(\)FloodingArray\({}_{j}[k-1])\)  
// Floodmin Phase  
**10:**for \(k\gets\)1 to \(d\)* 11:**do for \(i\gets 1\) to \(n\)
* 12:**do BROADCAST(FloodingArray\({}_{i}[k-1+d]\))
* 13:**do for \(i\gets 1\) to \(n\)
* 14:**do FloodingArray\({}_{i}[k+d]\leftarrow\min_{j\in S_{i}}(\text{FloodingArray}_{j}[k-1+d])\) // Cluster head Selection
* 15:**do for \(i\gets 1\) to \(n\)
* 16:**do if (FloodingArray\({}_{i}[2d]\)=FloodingArray\({}_{i}[0]\))
* 17:**then CH\({}_{i}\gets i\)
* 18:**else if(Pair(\(i\)))
* 19:**then CH\({}_{i}\leftarrow\) CH_ID(Pair(\(i\)))
* 20:**else CH\({}_{i}\leftarrow\) CH_ID(FloodingArray\({}_{i}[d]\))  
Pair(\(id\))  
* 01:**for \(i\leftarrow 1\) to \(d\)
* 02:**do for \(j\leftarrow(d+1)\) to \(2d\)
* 03:**do if (FloodingArray\({}_{id}[i]\) = FloodingArray\({}_{id}[j]\))
* 04:**then return FloodingArray\({}_{id}[i]\)
* 05:**return \(0\)  
CH_ID(\(floodingvalue\))  
* 01:**for \(i\gets 1\) to \(n\)
* 02:**do if (FloodingArray\({}_{i}[0]=floodingvalue\))
* 03:**then return \(i\)
* 04:**return \(error\)  
The pseudo code of MCBT clustering algorithm is shown above. Lines 1-4 show that each node computes its flooding value using the residual energy and degree, and makes a (\(2d+1\)) sized FloodingArray. Lines 5-9 explain the process of Floodmax-\(i\) (\(1\leq i\leq d\)). In round \(i\), each node broadcasts its flooding value in the round (\(i-1\)) and receives the neighbors' flooding values. The node then selects the maximum value among its own flooding value and the flooding values received from neighbors. Each node records the selected flooding value as the \(i^{th}\) element in its FloodingArray. Lines 10-14 explain the process of Floodmin-\(j\) (\(d+1\leq j\leq 2d\)), which is the same as Floodmax except a node chooses the smallest value rather than the largest value. In lines 15-20, each node declares itself a cluster head or selects another node as its cluster head based on the cluster head selection rules. Lines 16-17 describe the first cluster head selection rule. If the element in FloodingArray[\(2d\)] is the same as the element in FloodingArray[\(0\)], then that node will declare itself a cluster head. Lines 18-19 show the second cluster head selection rule to select another node as a cluster head. Like the function pair, a node compares \(d\) values from FloodingArray[\(1\)] to FloodingArray[\(d\)] with \(d\) values from FloodingArray[\(d+1\)] to FloodingArray[\(2d\)], to determine whether they are the same value. Line 20 describes the third cluster head selection rule. The node selects another node with the flooding value in Floodmax-\(d\) as the \(0^{th}\) round value. The function CH_ID returns the cluster heads' ID as a result of cluster head selection rules 2 and 3.