## 3 Cluster Formation
### Optimal Clustering
#### 3.1.1 Cluster Size  
The papers [13, 79] define cluster size as a function of distance to the BS. Based on the type of data transmission from CHs to the BS whether it is direct transmission or multi-hop through other CHs, the number of cluster members in each cluster is manipulated to achieve even energy expenditure within the network. In the Energy Efficient Clustering Scheme (EECS) [79], the original LEACH with 2-hop data transmission is accepted. The energy expenditure of the CHs far from the BS is significantly more in 2-hop transmission, especially in large-scale networks. Therefore, the algorithm justifies the cluster size to balance the load across the network. The cluster sizes of the CHs located farther are smaller than the ones located in close distance to the BS. To do so, the paper proposes a weight function consisting of two factors: node distance to the CH and CH distance from the BS. Using the function each node calculates its cost and joins the CH with the minimum cost. In other words, nodes choose the CH not only based on saving their own energy, but also on balancing the load of the CH which they want to join.  
In contrast with 2-hop transmission schemes, the CHs near the BS shoulder the heavy burden of relaying other CHs' data in algorithms using multi-hop transmission for sending data to the sink node. Thus to balance the energy expenditure of CHs, the algorithm in [13] limits the size of the clusters within a minimum and maximum range, based on a linear relation with the distance of the nodes to the BS. Hence, it leads to generating smaller clusters in near distances and larger clusters in far distances to the BS.  
To generate balanced clusters, the Cluster-based Energy-efficient Scheme (CES) is proposed by [33], which defines cluster size constraint between the upper and lower threshold. In this scheme, the clusters are constructed by the sensor nodes in 2-hop neighborhood and each node has a generic weight that represents the fitness of the node to be a CH. The thresholds can be chosen arbitrarily, or it can be calculated by the Equations (14) and (15) depending on the network topology:  
\[\mathit{Thresh}_{\mathit{Upper}} =\frac{1}{2}\left(\left|N_{12}\left(u\right)\right|+\mathit{Avg}\right) \tag{14}\] \[\mathit{Thresh}_{\mathit{Lower}} =\frac{1}{2}\left(\left|N_{12}\left(v\right)\right|+\mathit{Avg}\right) \tag{15}\]  
where \(u\) and \(v\) are the nodes with the maximum and minimum of 2-hop neighbors, respectively, \(N_{12}\) is the combined set of one-hop and two-hop neighbors of node and \(\mathit{Avg}\) is the average number of 2-hop neighbors of all nodes in the network. Based on the threshold values, CH accepts cluster members until the size of the cluster reaches \(\mathrm{Thresh}_{\mathrm{Upper}}\), and afterwards, it drops the messages of the affiliation request. On the other hand, after finishing the setup phase, there may be some clusters which have not attained the cluster size \(\mathrm{Thresh}_{\mathrm{Lower}}\). Therefore, the algorithm calls a re-affiliation phase by the CHs of the clusters whose size is lower than \(\mathrm{Thresh}_{\mathrm{Upper}}\) and higher than \(\mathrm{Thresh}_{\mathrm{Lower}}\). This sort of CHs broadcast the re-affiliation CH message and the nodes belong to small clusters join a new CH based on the received signal strength. The re-clustering procedure in the algorithm is limited only to clusters with lost CHs and the next CH will be selected among other nodes within the cluster. Although the algorithm properly addresses the uneven cluster size without a centralized controller, it cannot consider the optimum number of clusters, because the cluster formation of 2-hop neighbors is prior to CH selection phase.