## 2 Cluster Head Selection
### Self-Organized Schemes
#### 2.1.2.1 Energy Expenditure
\begin{array}{l}\frac{\text{P}_{CH}}{1-P_{CH}*\left(r \bmod\frac{1}{p_{CH}}\right)}[\frac{\text{E}_{c}}{\text{E}_{i}}+\left(1- \frac{\text{E}_{c}}{\text{E}_{i}}\right)\frac{\text{N}_{b}}{1/P_{CH}-1}], \text{if n \in G}\\ \\ 0,\text{otherwise}\end{array} \right. \tag{5}\]  
where \(N_{b}\) is the number of the neighbours and other variables are the same as what they are in Equation (2). In [18], Weighted Spanning Tree for LEACH (WST-LEACH) is proposed that is based on a weighted consideration of the remaining energy, distribution density and the distance of nodes from the BS. In a network with \(N\) nodes, the algorithm considers variant weights for three following ratios as a coefficient to be applied to T(n): ratio of the residual energy Eresidual to initial energy \(E_{0}\), ratio of the number of neighbours N\({}_{b}\) in predefined radius R to the average number of nodes in accordance with the probability \(P_{r}\) and inverse correlation of the nodes' distances from the BS (d\({}_{\text{BS}}\)). The modified threshold value in Equation (6) improves the stochastic method of CH selection in LEACH to a multi-criteria decision-making process. However, the appropriate selection of the ratio weights is essential in generating an efficient threshold value, which does not degrade the network performance either by decreasing the average chance of the nodes to be selected as CH or by proliferation of the network with redundant number of CHs:  
\[T^{\prime}(n)=\frac{P_{CH}}{1-P_{CH}*(rmod1/P_{CH})}\times\{\text{W}_{1}* \frac{E_{r,residual}}{E_{0}}+\text{W}_{2}*\frac{N_{b}}{p_{r}*N}+\text{W}_{3}* \frac{1}{d_{BS}}\} \tag{6}\]  
Other than selection of CHs through modification of LEACH probabilistic threshold scheme, there are some algorithms [19, 20] in which CHs are chosen according to a time contest. In these schemes, the CH selection procedure is through participation in a contest for the broadcast time of the CH advertisement by setting up a random timer according to their resource information. The nodes of which their timers expires earlier, broadcast the CH advertisement message, while other nodes that receive the advertisement messages and their timers are not expired, drop the competition for CH role and join the CH with the minimum communication cost. The timer in More Energy-efficient LEACH for Large-scale sensor networks (MELEACH-L) algorithm [19] is a function of residual energy of nodes and duration of the CH selection phase. As it can be seen in Equation (7), the timers of the sensor nodes having higher energy level expire earlier at higher probability, and hence the nodes with lower battery power level close to high-energized nodes have little chance to be as CH:  
\[T_{i}=[\alpha_{c}\frac{E_{start}-E_{residual,i}}{E_{start}}+(1-\alpha_{c})random (0,1)].\mathcal{\delta} \tag{7}\]  
Where \(\alpha_{c}\) is a constant, which determines the weight of the energy resource and random number in lateness of the timer, \(\delta\) is the time duration of the CH selection phase. In the Energy-Efficient Distributed Multi-level Clustering (EEDMC) algorithm [20], at the beginning of each round, each node broadcasts a message to the neighbouring nodes consisting of their node IDs and residual energy. In this way, each node saves a table of its neighbouring nodes and their remaining energy, and calculates the average residual energy of its neighbours as a parameter to generate the timer value by Equation (8):  
\[t_{i}=p\times T\times(1-\frac{\sum\limits_{j=1}^{m}E_{rj}}{N_{b}}) \tag{8}\]  
where \(p\) is a random number between [0.95, 1] to avoid advertisement message collision of the nodes with the same remaining energy, \(T\) is the predefined maximum time of CH competing duration, \(N_{b}\) is the number of neighbouring nodes and \(E_{rj}\) is the residual energy of the neighbouring node \(j\). Equation (8) gives negative results for the average energy level over one unit, hence, to avoid this, the remaining energy level of the nodes should be normalized by their initial energy level.