## 3 Multi-hop Cluster Based Stable Backbone Trees (MCBT)  
### Motivation and New Factor  
Backbone nodes consume more energy than ordinary nodes. It is important to form a stable backbone by taking into account the node's residual energy and degree in order to prolong the network lifetime. MCBT constructs a stable backbone by selecting nodes with higher energy or degree as the cluster heads and distributes the role of packet forwarding among nodes around the cluster heads to enhance the network lifetime. In this paper, we consider a new factor: the flooding value. Using the flooding value, we can simultaneously consider the residual energy and degree, which are the core factors to evaluate the stability of the sensor node. If the node has high residual energy and degree, it has a high flooding value.  
_Definition 2_ (Round) - Round is the stage in which each node exchanges flooding values with \(1\)-hop neighbors, and chooses the flooding value among its own and the neighbors' flooding values. Round \(0\) is the computation step of the flooding value and MCBT performs the \((2d+1)\) rounds to form the \(d\)-hop clusters.  
_Definition 3_ (FloodingArray) - FloodingArray is the \((2d+1)\) sized array to record the selected flooding value for each round. The first element of FloodingArray is the flooding value in round \(0\). Flooding values selected from round \(1\) to round \(2d\) are sequentially recorded in the array.  
Each node exchanges the flooding values with its neighbors for \(2d\) rounds to form \(d\)-hop clusters and selects the node with higher flooding value as the cluster head. In each round, all nodes broadcast the flooding values selected in the previous round to their \(1\)-hop neighbors and select one value by comparing among its own flooding value and the flooding values received from neighbors. This process is repeatedly performed for \(2d\) rounds. The algorithm selects the nodes with a higher flooding value as cluster heads, applying the cluster head selection rule based on all values saved in FloodingArray. Using the following criterion, the flooding value takes both the node's residual energy and degree into account:  
\[f(i,\omega)=\omega(\frac{E_{res}}{E_{ini}})+(1-\omega)(\frac{deg_{i}}{\max_{j \in S_{i}}(deg_{j})}) \tag{1}\]  
where \(S_{i}\) is a set of neighbors of node \(i\) including itself.  
Let \(f(i,\omega)\) denote the flooding value of the node \(i\); \(\omega\) is the weight factor that adjusts the priority and \(\omega\in[0,1]\). A large \(\omega\) gives more weight to the node's residual energy than its degree. \(E_{ini}\) is the initial energy of a node and \(E_{res}\) is the residual energy of the node \(i\). The \(deg_{i}\) is the number of nodes that are within the node \(i\)'s transmission range, namely its neighbors. The \(\max_{j\in S_{i}}(deg_{j})\) is the maximum degree among its own degree and the degrees of the neighbors of the node \(i\). Note that \(\frac{E_{res}}{E_{ini}}\in[0,1]\) and \(\frac{deg_{i}}{\max_{j\in S_{i}}(deg_{j})}\in(0,1]\). Suppose \(\frac{E_{res}}{E_{ini}}\) remains constant; in this case, the flooding value increases when the degree increases. On the contrary, suppose \(\frac{deg_{i}}{\max_{j\in S_{i}}(deg_{j})}\) and \(E_{ini}\) are constant; then, the flooding value increases as \(E_{res}\) increases.