# A Routing Protocol for Multisink Wireless Sensor Networks in Underground Coalmine Tunnels
## 4 Design of PCEB-MS Protocol
### UCEBA Algorithm
#### 4.2.3 Selection of Final Cluster Head and Cluster Formation  
The final cluster head is generated using a certain competitive strategy. The sensor nodes are unable to supply energy for the coalmine tunnel once they are deployed; therefore, it is necessary to prolong the lifetime of the sensor nodes that are located far from the sink and have low energy. That is to say, the sensor which is closer to the sink node and higher in energy is preferred as the cluster head, thus prolonging the network lifetime. First, each sensor node for the UCEBA saves a list of neighbor nodes. Table 1 presents information relating to neighbor sensor nodes. All sensor nodes receiving the same sink ID are located in the same region. Some of the sensor nodes in the overlapping region will obtain a two sink ID, and these sensor nodes transmit data directly to the closer sink and do not need to join any cluster. Table 1 shows that the list of neighbor nodes comprises the candidate cluster head ID, status, residual energy, and distance to the sink. Each candidate cluster head broadcasts with a competitive radius, \(R_{rn}\), as it transmits its competitive information COMPETE_MSG. All candidate cluster heads in radius \(R_{rn}\) of a candidate cluster head, \(V_{i}\), are regarded as neighbor nodes of this candidate cluster head. The neighbor node of the candidate cluster head \(V_{i}\) is recorded as \(V_{i}\).Neitab. \(V_{i}\).Neitab = \(\{V_{j}\,|\,V_{j}\) refers to the candidate cluster head and range (\(V_{i}\), \(V_{j}\)) \(<\) max(\(V_{i}\).\(R_{rn}\), \(V_{j}\).\(R_{rn}\))\(\}\),  
where range (\(V_{i}\), \(V_{j}\)) denotes the distance between nodes \(V_{i}\) and \(V_{j}\). Each candidate cluster head calculates the average residual energy, \(E_{a}\), of all the sensor nodes in its competitive radius and the average distance, \(D_{a}\), to the sink according to the list of neighbor nodes. \[E_{a}=\frac{\sum\limits_{j=1}^{m}V_{j}.E_{cu}}{m}, \tag{15}\]  
\[D_{a}=\frac{\sum\limits_{j=1}^{m}V_{j}.d_{toSK}}{m}. \tag{16}\]  
Accordingly, \(V_{j}\) (\(1\leq i\leq m\), \(i\
eq j\)) refers to the neighbor sensor node in a radius, \(R_{rn}\), of the candidate cluster head \(V_{i}\), and \(m\) refers to the number of neighboring sensor nodes. Each candidate cluster head then starts timer, \(t\), according to the following equation,  
\[t=k\times t_{0}\times\frac{E_{a}}{E_{cu}}\times\frac{d_{toSK}}{D_{a}}, \tag{17}\]  
where \(k\) refers to the real number evenly distributed in \([0,1]\) at random, and \(t_{0}\) refers to the competitive duration of the candidate cluster head agreed in advance. The candidate cluster head node is successfully competitive if it does not receive the message on the competition victory of the neighbor candidate cluster head node SUCCESS_MSG before time, \(t\). The message SUCCESS_MSG is then sent to the other neighbor candidate cluster nodes. Otherwise, the candidate cluster head is defeated and \begin{table}
\begin{tabular}{c c c c} \hline
**ID** & **State** & **Residual Energy (I)** & **Distance to Sink (m)** \\ \hline
3 & Candidate & 1.38 & 10 \\
7 & Candidate & 0.21 & 20 \\
8 & Candidate & 0.15 & 80 \\
5 & Candidate & 0.38 & 60 \\ \hline \end{tabular}
\end{table} 
Table 1: Neighbor nodes of a candidate cluster head. quits the competition. The aforementioned formula and analysis show that all the sensor nodes in the competitive radius have relatively high residual energy. Moreover, there is a higher probability that a sensor node that is located relatively near the sink will become the final cluster head, and will ultimately and effectively prolong the lifetime of the candidate cluster head nodes located far from the sink that have lower energy. The sensor nodes that do not participate in the competition are woken from their sleeping state after the final cluster head has been selected through competition. The final cluster head broadcasts the competition victory message, CH_ADV_MSG, using \(R_{n}\) as the radius.