# Markov Chain Model-Based Optimal Cluster Heads Selection for Wireless Sensor Networks
## 4 The Proposed Clustering Protocol
### Setup Phase
#### 4.3.2 Neighbor Discovery  
The main purpose of neighbor discovery is that in the beginning no reliable infrastructure is found among the \(C_{MNs}\) for communication, and data exchange becomes crucial for WSNs. The setup phase starts with every round with the aim to upgrade the system. When all the \(C_{MNs}\) in a network become familiar about some coordinates related to them, like: received signal strengths, and the node IDs, the probability of successful communications between nodes increases. We use a _NBR-Msg_ exchange method to inform neighbor nodes with the node IDs, the link status, and all other coordinates of the neighbor nodes in a network as depicted in Figure 3.  
The other reason for neighbor discovery is that the sensor nodes in the network decide themselves to be CHs at the beginning of every round with a certain probability. They disseminate their status as a CH _Adv-CHs-Msg_ on intra-cluster transmission range. The nodes which are not elected as a CH receive a message from closer CHs. They send a joint request _Joint-Req-Msg_ to concern CH. A number of sensor nodes in the network do not receive any CH status announcement from any of the CH. These  
Figure 3: The network configuration up-gradation through neighbor discovery.  
Figure 2: **(a)** The angle of signal arrival, (**b**) decrease in signal strength as it propagates from sender towards the receiver nodes, (**c**) neighbor discovery process.  
sensor nodes wait for the CH status message for a predefined time slot and then these nodes become self-generating force CHs. These self-generated CHs can directly communicate with the BS either these nodes are placed close or far away from the BS. These force CHs consume additional energy during their communication to forward data. To triumph over this problem, we employ a simple strategy to handle with these non-associated nodes in our proposed clustering protocol. If a node does not receive any CH announcement message _Adv-CHs-Msg_ it sends a request to CH through the closest neighbor. Then this non-associated node will forward its sensed data to its next neighbor node towards the BS with the help of a CH node. There is no need to send data directly to the BS. The neighbor node will forward this packet to its associated CH.  
After the initialization, all the nodes in network discover their neighbors in finite time.  
Proof.: All the nodes in the network spend a finite time to set the variable \(f(n)\) to themselves, here the \(f(n)\) is the initialization time. For any node j in the network, we suppose that the node j has the minimum number of neighbors i and satisfies \(h(i)=h(j)+g(i,j)\), where, the \(h(i)\) is the initialization time of node i and \(g(i,j)\) is the time taken by node i to discover j neighbor nodes. As the j has the finite number of neighbors i, then node i chooses j and sets the variable \(f(i)\) to j in a finite time. As the node i spends a finite time to set the variable \(f(i)\) of itself and at maximum waits for all the other nodes in the network to discover their neighbors in a finite time.