# Energy-Efficient Clustering Multi-Hop Routing Protocol in a UWSN
## 3 Energy-Efficient Clustering Multi-Hop Routing Protocol
### Energy-Efficient Clustering Multi-Hop Routing Protocol  
The proposed energy-efficient clustering multi-hop routing protocol (EECMR) consists of two phases: a set-up phase and a steady-state phase. Cluster formation consists of  
Figure 2: Absorption coefficient for the medium. sub-phases: broadcast information, cluster head selection, cluster formation, and scheduling transmission. In EECMR, the node becomes a CH, CM, or CR. For example, the node becomes a CH in the first round, the node becomes a CR in the second round, and the node may become a CM in the third round. Each node calculates a weight value based on the residual energy and distance to the sink. The weight of each node is used to decide whether or not to become a cluster head for the current round. The weight of \(S_{i}\) is calculated as follows:  
\[W_{i}=\frac{\Delta t}{T}+\alpha\frac{d(i,S_{0})}{L}+\beta\frac{E_{Res}}{E_{Init}} \tag{8}\]  
where \(d(i,S_{0})\) denotes the distance between node \(S_{i}\) and the sink, \(E_{Res}\) denotes the residual energy, \(E_{Init}\) denotes the initial energy, \(\alpha\) and \(\beta\) denote the coefficient such that \(\alpha+\beta=1\), \(\Delta t\) denotes the time for which the nodes adopt the role of cluster head, and \(T\) is the total operating time. The EECMR protocol is described in Algorithm 1. At the start \(t_{0}\), the node does not have information about the surrounding environment. In State 1 from lines 3 to 7, each node broadcasts a \"\(HELLO\)\" message to the neighbors. The message includes information of the location and estimated distance to the sink. According to the successfully received \"\(HELLO\)\" message, nodes store their neighbors' information in order to select the cluster, which is shown in lines 8 to 11. To prevent a long waiting time, the timeout value is set to the maximum propagation delay of one hop, as in [8]. The maximal propagation delay is calculated as \(\tau=Tx/v_{0}\), where \(Tx\) is the maximum transmission range and \(v_{0}=1.5\times 10^{3}\) m/s is the speed of sound propagation in the water. Each node can elect to become a cluster head according to the weight compared to that of its neighbors, as in State 2 in Algorithm 1. If the node has the highest weight compared to that of its neighbors, the node will broadcast the \"\(J\)\(O\)\(I\)\" message to its neighbors in order to form a cluster, as indicated in lines 14 to 17. Otherwise, the node will wait for the \"\(J\)\(O\)\(I\)\(I\)\" message; if the node receives only one message, it will become a cluster member of the cluster. If the node receives many \"\(J\)\(O\)\(I\)\(I\)\" messages, it will select the sender node with the highest received power or the node with the nearest distance. We assume that the cluster can be formed between the nearby nodes to reduce energy consumption and transmission time. However, because the nodes at depth \(D_{2}\) and \(D_{3}\) may not transmit data directly to the sink due to the limited transmission range, we assume that some nodes will become the CR to forward data to the sink. State 3 of Algorithm 1 shows the steps in the selection of the relay node. Assumed nodes which are not the CH will become a CR or CM. From lines 24 to 26, if the node receives the \"\(J\)\(O\)\(I\)\(I\)\" message from both \(D_{m}\) and \(D_{m-1}\), which are broadcasted by nodes of upper and lower depths, the node elects to become a CR, which will be a forwarder in the routing path. From lines 28 to 29, the nodes only receive a \"\(J\)\(O\)\(I\)\(I\)\" message from the CHs at the same depth. The nodes send a \"\(RESPONSE\)\" message to the CH to confirm the cluster ID. State 4 of Algorithm 1 and its multi-hop routing path creation show how the cluster at the deeper layer can forward the packet to the sink via the forwarders or the CR. In line 33, if the CH \(S_{i}\) receives a \"\(RELAY\)\" message from \(S_{k}\), node \(S_{i}\) checks the depth of \(S_{k}\).