# Markov Chain Model-Based Optimal Cluster Heads Selection for Wireless Sensor Networks
## 4 The Proposed Clustering Protocol
### Settling Phase
#### 4.4.3 Association of Cluster Members (ACM) and Cluster Formation (CF)  
In current clustering architecture, a sensor node obtains the CH status messages from the chosen CHs. It evaluates their received signal strengths. Then this node joints with a CH which has the strongest received signal strength among them. Whenever a node associates itself with a CH on the basis of receiving signal strengths, then the following major points of concern arise:  
* If CH positioned backward compared to its direction of transmission towards the BS, back transmission occurs. This type of data transmission contributes to extending the general path length traveled by the locally collected data. * The sizes of clusters become non-uniform ensuring the non-uniform overhead on the CHs. To solve the association problems, we consider a specific scenario in which a member node \(N\) receives the \(CH\) status message \(Adv\)-\(O_{CH}\)-\(Msg\) from two \(CHs\), e.g., \(CH_{1}\) and \(CH_{2}\). Then the node locates its distance \(d_{(N,BS)}\) from the BS, and determines a midpoint \(MP\). Afterward, the node compares  
Figure 7: The optimal CHs selection on the basis of residual energy and distance Via BS. the value of received signal from both the CHs at this midpoint. Since at this midpoint the strength of the signal from \(CH_{1}\) is greater than the \(CH_{2}\). As a result, the node \(N\) sends a joint request _Joint-Req-Msg_ to the \(CH_{1}\). The node \(N\) is situated at the lesser distance from \(CH_{2}\) as compared to \(CH_{1}\), but the node joins the \(CH_{1}\) to omit the back transmission. To join with \(CH_{1}\) is beneficial for the node to save the energy. To understand this, we develop the following mathematical expressions:  
\[d_{(CH_{1},BS)}^{2}=H^{2}+(\frac{d_{(N,BS)}}{2}-X)^{2} \tag{14}\]  
where, \(H\) is a line joining \(CH_{1}\) and a point \(Q\), while \(Q\) is a point on the line between \(MP\) and the BS and \(X\) is the distance between point \(Q\) and midpoint \(MP\). \[d_{(N,CH_{1})}^{2}=H^{2}+(\frac{d_{(N,BS)}}{2}+X)^{2} \tag{15}\]  
where, \(d_{(N,BS)}=d_{(N,MP)}+d_{(MP,BS)}\), by adding the Equations (13) and (14), we have:  
\[d_{(CH_{1},BS)}^{2}+d_{(N,BS)}^{2}=2H^{2}+\frac{d_{(N,BS)}^{2}}{2}+2X^{2} \tag{16}\]  
After substituting, \(X^{2}=d_{(MP,CH_{1})}^{2}-H^{2}\)  
\[d_{(CH_{1},BS)}^{2}+d_{(N,CH_{1})}^{2}=2H^{2}+\frac{d_{N,BS}^{2}}{2}+2(d_{(MP, CH_{1})}^{2}-H^{2}) \tag{17}\]  
\[d_{(CH_{1},BS)}^{2}+d_{(N,CH_{1})}^{2}=2H^{2}+\frac{d_{(N,BS)}^{2}}{2}+2(d_{(MP, CH_{1})}^{2})-2H^{2} \tag{18}\]  
\[d_{(CH_{1},BS)}^{2}+d_{(N,CH_{1})}^{2}=\frac{d_{(N,BS)}^{2}}{2}+2(d_{(MP,CH_{1} )}^{2}) \tag{19}\]  
We can note from Equation (18) that the distance of the node from BS \(d_{(N,BS)}\) is constant, and \(d_{(CH_{1},BS)}^{2}+d_{(N,CH_{1})}^{2}\) is directly related to \(d_{(MP,CH_{1})}\). If we minimize this \(d_{(CH_{1},BS)}^{2}+d_{(N,CH_{1})}^{2}\), then, we can attain our objective which is equivalent to \(Min(d_{(MP,CH_{1})})\). Consequently, if a member node selects the CH closer to the midpoint towards the BS, than the squared distance of their communication is smaller, which means that the energy utilization is minimized for that node, leading to increasing the network lifetime. The energy consumption of a node in a cluster formation process is:  
\[E_{N-CF}=2 IE_{elec}+le_{fs}d_{(N,CH)}^{2} \tag{20}\]  
So, the total energy consumed for dividing the whole network into clusters is:  
\[E_{CF}=K\bigg{[}E_{CH}+\bigg{(}\frac{N}{K}-1\bigg{)}E_{N-CF}\bigg{]} \tag{21}\]  
The WSN nodes have inbuilt resource limitations, so, the clustering procedure is commonly adopted for WSN applications to accomplish the energy efficiency. Clustering is an efficient method to organize the WSN nodes into hierarchal groups. This hierarchal structure is adopted at different layers like the Network layer or the Data Link layer according to the system requirement. Clustering improves the system performance by reducing the local network traffic, the long-distance communication, and the routing information of root nodes.