## 3 Multi-hop Cluster Based Stable Backbone Trees (MCBT)
### The Clustering Algorithm
In Floodmin-\(3\), each node selects the minimum value among the flooding value of the neighbors including itself in Floodmax-\(2\). Node 3 selects 0.77 in Floodmin-\(3\) and the same number in Floodmin-\(4\). Nodes 3, 5, and 11 regain the flooding value of \(0^{th}\) round or the flooding value in Floodmax-\(1\) by Floodmin. After Floodmax and Floodmin, the node declares itself a cluster head or selects another node as a cluster head using three rules of cluster head selection. _Rule 1_: If a node \(x\) has the same value in Floodmin-\(2d\) of the \(0^{th}\) round value, node \(x\) declares itself a cluster head and skip the rest of the rules. _Rule 2_: If the first rule cannot be applied, node \(x\) compares \(d\) values of Floodmax with \(d\) values of Floodmin in its FloodingArray without order. If there is the value that appears in both Floodmax and Floodmin, node \(y\) that has this value is selected as the cluster head of node \(x\). If node \(x\) has two or more of the same flooding values in its FloodingArray, it selects the node \(y\) that has a lower flooding value. _Rule 3_: If node \(y\)' flooding value in \(0^{th}\) round is the same to the value of Floodmax-d of node \(x\), node \(y\) becomes the cluster head of node \(x\). After cluster head selection, each node broadcasts its elected cluster head's ID to all of its neighbors. If a node receives a different cluster head ID, this node becomes a cluster gateway. Finally, in the case of a cluster head that is on the path between an ordinary node and its elected cluster head, the ordinary node chooses the cluster head with the minimum hops. Applying the first rule, if the flooding value selected in Floodmax-\(d\) is same to the \(0^{th}\) round value, the node declares itself a cluster head. Two cases can be classified. First, in the case of node 9, its flooding value of the \(0^{th}\) round is the maximum value among the flooding values of the \(d\)-hop neighbors, so it continuously selects its flooding value. Second, with nodes 5 and 11, the flooding values in the \(0^{th}\) round are deleted from their FloodingArray, because they select higher flooding values in Floodmax. However,  
Figure 1: \(2\)-hop clustering - Floodmax and Floodmin phase. Figure 2: \(2\)-hop clustering - Resulting network topology. their \(d\)-hop neighbors transmit the flooding values of nodes 5 and 11 and save them in the FloodingArray because these flooding values are higher than the flooding values of their \(d\)-hop neighbors. Then the Floodmin process will successfully propagate these flooding values back to the originating nodes. To select the node that can satisfy the two cases, if the flooding value selected in Floodmin-\(2d\) is its own flooding value in the \(0^{th}\) round, this node will declare itself to be the cluster head. Other nodes select their cluster head by the second and the third rule. Applying the second rule, the node selects one node among cluster heads within \(d\)-hop as its cluster head. Figure 2 shows that node 3 receives again the flooding value 0.77 by Floodmin. Therefore, 0.77 is the pair selected in both the Floodmax and Floodmin and node 3 selects node 5 with this value as the \(0^{th}\) round value as its cluster head. That is, node 3 selects the adjacent node 5, as a cluster head instead of node 9 that has a higher flooding value in the \(0^{th}\) round. As the result, the cluster head that has a lower flooding value can gain more cluster members. All nodes except nodes 5, 9 and 11 conform to the second rule of cluster head selection. The node to which the first and the second rule are not applicable selects the node with the flooding value in Floodmax-\(d\) as the \(0^{th}\) round value; that is, the maximum flooding value among \(d\)-hop neighbors. After the cluster head selection process, each node broadcasts its elected cluster head's ID to all of its neighbors. Nodes 4 and 6 conform to the case of a cluster head being on the path between an ordinary node and its elected cluster head.