## 5 Analysis of Prominent Clustering Routing Protocols in WSNs
### Cluster-Construction Based Clustering Routing Protocols
#### 5.1.2 Heed  
Hybrid Energy-Efficient Distributed clustering (HEED) [15], introduced by [PERSON] and [PERSON], is a multi-hop WSN clustering algorithm which brings an energy-efficient clustering routing with explicit consideration of energy. Different from LEACH in the manner of CH election, HEED does not select nodes as CHs randomly. The manner of cluster construction is performed based on the hybrid combination of two parameters. One parameter depends on the node's residual energy, and the other parameter is the intra-cluster communication cost. In HEED, elected CHs have relatively high average residual energy compared to MNs. Additionally, one of the main goals of HEED is to get an even-distributed CHs throughout the networks. Moreover, despite the phenomena that two nodes, within each other's communication range, become CHs together, but the probability of this phenomena is very small in HEED. In HEED, CHs are periodically elected based on two important parameters: residual energy and intra-cluster communication cost of the candidate nodes. Initially, in HEED, a percentage of CHs among all nodes, \(C_{\text{prob}}\), is set to assume that an optimal percentage cannot be computed a priori. The probability that a node becomes a CH is:  
\[CH_{\text{prob}}=C_{\text{prob}}\frac{E_{\text{residual}}}{E_{\text{max}}} \tag{2}\]  
where \(E_{\text{residual}}\)is the estimated current energy of the node, and \(E_{\text{max}}\) is a reference maximum energy, which is typically identical for all nodes in the network. The value of \(CH_{\text{prob}}\), however, is not allowed to fall below a certain threshold that is selected to be inversely proportional to \(E_{\text{max}}\). Afterwards, each node goes through several iterations until it finds the CH. If it hears from no CH, the node elects itself to be a CH and sends an announcement message to its neighbors. Each node doubles its \(CH_{\text{prob}}\) value and goes to the next iteration until its _CH_prob reaches 1. Therefore, there are two types of status that a sensor node could announce to its neighbors: tentative status and final status. If its _CH_prob is less than 1, the node becomes a tentative CH and can change its status to a regular node at a later iteration if it finds a lower cost CH. If it's _CH_prob has reached 1, the node permanently becomes a CH. In HEED, every node elects the least communication cost CH in order to join it. On the other hand, CHs send the aggregated data to the BS in a multi-hop fashion rather than single-hop fashion of LEACH. The advantages of the HEED protocol are as follows: (1) It is a fully distributed clustering method that benefits from the use of the two important parameters for CH election; (2) Low power levels of clusters promote an increase in spatial reuse while high power levels of clusters are required for inter-cluster communication. This provides uniform CH distribution across the network and load balancing; (3) Communications in a multi-hop fashion between CHs and the BS promote more energy conservation and scalability in contrast with the single-hop fashion, _i.e._, long-range communications directly from CHs to the sink, in the LEACH protocol [64]. However, there are some limitations with HEED as follows: (1) The use of tentative CHs that do not become final CHs leave some uncovered nodes. As per HEED implementation, these nodes are forced to become a CH and these forced CHs may be in range of other CHs or may not have any member associated with them. As a result, more CHs are generated than the expected number and this also accounts for unbalanced energy consumption in the network [65]; (2) Similar to LEACH, the performing of clustering in each round imposes significant overhead in the network. This overhead causes noticeable energy dissipation which results in decreasing the network lifetime; (3) HEED suffers from a consequent overhead since it needs several iterations to form clusters. At each iteration, a lot of packets are broadcast.