# Markov Chain Model-Based Optimal Cluster Heads Selection for Wireless Sensor Networks
## 4 The Proposed Clustering Protocol
### Markov Chain Model for Resolving the Optimal Cluster Formation and CH Selection Problems  
The nodes in the sensing field are installed through a distributed algorithm. Therefore, the distribution of nodes in the sensing field is not even. The previously designed clustering protocols [7; 8; 9; 10; 11; 12] use the distributed clustering algorithm for CH selection, which increases the computational overhead on all the nodes. Another problem is that optimum numbers of CHs are also not assured through this distributed algorithm. If the selected number of CHs should not be optimal, this causes the resources to deplete very quickly. The number of CHs selected by using randomized schemes [7; 8; 9; 10; 11], is not guaranteed to be equal to the expected optimal value. To analyze the clustering properties, and to address the problems in cluster formation, we employed a bi-dimensional Markov chain model [21; 26] to inspect their cluster-forming behavior. We use the Markov model to analyze the stochastic properties of MOCHs for the number of CHs in terms of the PMF, the mean, the SD, and the COV of the number of CHs. Through this formulation, the obtained CHs are optimal in number and well-distributed across the network, which leads to higher energy efficiency and better fairness among nodes, and prolonged the network lifetime. Suppose that \(c(t)\) denotes a stochastic process to signify the selected number of CHs at a specific time instant \(t\). As the process of CHs selection starts from the beginning of each round, an integer scale \(t\) and a discrete time \(t+1\) instants are selected in the beginning of two successive rounds. We express that \(r(t)\) is the round at a time instant t, and \(x(t)\) is a stochastic procedure signifies the period of a scheme at a time instant t, which is \(x(t)=r(t)\text{mod}(1/P)\). We also suppose another integer \(1/P\), which denotes \(n=1/P\). The state space of this model is: \(\{0,N\}\bigcup\{(i,x):i\in[0,N]\), \(x\in[1,n-1]\), where, \(i\) and \(x\) are integers\(\}\), as this process \(\{x(t),c(t)\}\) holds the Markov property. To analyze the clustering properties of the proposed model, we utilize these measures: the distribution of CHs in every round, the average selected CHs in every round, the SD of the number of CHs, and the COV of the number of CHs. The target is the optimal number of CHs; the optimal number of CHs allows and guarantees the minimum energy consumption in the network. The SD calculates the variations in the target values, and the COV estimates the distribution of the average number of CHs related to the number of CHs. Let CH is a random variable indicates the total number of CHs in a round. We use the bi-directional Markov chain model stationary distribution and one-step transition probabilities [26] to estimate the PMF for the CHs as follows:  
\[p(CH=L)=\pi_{(0,N)}\cdot\left[P_{(0,N)\rightarrow(1,N-L)}+f_{(n-1,L)}+\sum_{ x=1}^{n-2}\sum_{i=L}^{N}f_{(xi)}\cdot P_{(x,i)\rightarrow(x+1,i-L)}\right] \tag{3}\]  
where \(\pi\) denotes staionary distribution, P is one step transition probablity matrix, and f signifies a factor matrix, \(f_{xi},x\in[1,n-1],and\ i\in[0,N]\) are elements of the factor matrix. Additionally, depending upon the PMF of the number of CHs, we are able to estimate the average number of CHs \((Avg[CH])\), the COV \((COV[CH])\), and the SD \((SD[CH])\):  
\[Avg[CH]=\sum_{L=0}^{N}L\cdot p(CH=L) \tag{4}\]  
\[SD[CH]=\sqrt{\sum_{L=0}^{N}L^{2}\cdot p(CH=L)-\left(Avg[CH]\right)^{2}} \tag{5}\]  
\[COV[CH]=\frac{SD[CH]}{Avg[CH]} \tag{6}\]  
Furthermore, we also consider the case if no CH is selected, then the other phases of this round will be omitted, and the next round will start. By using such enhancement, the CH selection and cluster formation process (the settling phase) becomes more effective and practical.