# An Efficient Model-Based Clustering via Joint Multiple Sink Placement for WSNs
## 4 Our Proposal
### Improving the Ant Clustering Algorithm for Sensor Node Clustering
#### 4.2.1 Initialization Step  
Firstly, sensors are randomly deployed on a grid with a maximum of one sensor allowed in each cell. In our solution, the grid is represented by a two-dimensional array, where each element contains a number of sensors. Furthermore, empty cells can be assigned to the corresponding element in the array with a predefined value (such as 0). Sparse matrices are effectively utilized to represent the two-dimensional array when the size ofthe grid is very large. Next, we calculate the chance of picking a cluster head node for each node and then choose k cluster heads using Equation (7), which is defined as follows:  
\[\text{Cp}_{\text{i}}=(\frac{\text{R}_{\text{energy}}\left(\text{S}_{\text{i}} \right)}{\text{max\_R}_{\text{energy}}})\times(\frac{\text{C}_{\text{range}_{ \text{i}}}}{\text{max\_C}_{\text{range}}}) \tag{7}\]  
where \(\text{Cp}_{\text{i}}\) is the chance of picking cluster head node i, and \(\text{R}_{\text{energy}}\left(\text{S}_{\text{i}}\right)\) and \(\text{C}_{\text{range}_{\text{i}}}\) are the residual energy and communication range of \(\text{S}_{\text{i}}\), respectively. \(\text{max\_R}_{\text{energy}}\) and \(\text{max\_C}_{\text{range}}\) are the maximum values of the residual energy and the network's maximum communication range, respectively. We determine the optimum number of clusters, k, using one of the widely-used performance measures in cluster analysis, the Silhouette index (SI) [64]. A higher SI value indicates that data points are less similar to other clusters and more similar to their own cluster. The Silhouette index used in distributed clustering is determined as follows:  
\[\text{SI}_{\text{K}}=\left(\frac{1}{\text{NK}}\right)\sum_{\text{k=1}}^{ \text{K}}\sum_{n=1}^{\text{N}}\text{SI}(\text{S}_{\text{i}}) \tag{8}\]  
\[\text{SI}(\text{S}_{\text{i}})=\frac{\text{b}(\text{S}_{\text{i}})-\text{a}( \text{S}_{\text{i}})}{\text{max}(\text{a}(\text{S}_{\text{i}}),\text{b}(\text {S}_{\text{i}}))} \tag{9}\]  
where K is the number of clusters in each experiment, \(\text{a}(\text{S}_{\text{i}})\) is the average dissimilarity of the ith object to all objects in the same cluster, and \(\text{b}(\text{S}_{\text{i}})\) is the average dissimilarity of the ith object with all objects in the closest cluster. ```
1. For each sensor node \(\text{S}_{\text{i}}\)do
2. Calculate \(\text{Cp}_{\text{i}}\) factor using Equation (7)
3. Endfor
4. Sort all the SNs in descending order based on Cp
5. Select the k first SNs that have a maximum value of Cp as CH using Equation (8)
6. \(\text{CHs}=\sum_{\text{j=1}}^{\text{k}}\text{CH}_{\text{j}}\)
7. \(\text{S}_{\text{T}}=\text{S}_{\text{T}}\ -\ \text{CHs}\)
8. for each \(\text{S}_{\text{i}}\) in \(\text{S}_{\text{T}}\)do
9. for each \(\text{CH}_{\text{j}}\) in \(\text{CHs}\) do
10. Calculate \(\text{d}(\text{S}_{\text{i}}\,\text{CH}_{\text{j}})\) using Equation (10)
11. Endfor
12. Select min_d(\(\text{S}_{\text{i}}\,\text{CH}_{\text{j}})\)
13. if\(\text{C}_{\text{range}}(\text{S}_{\text{i}}\,\text{CH}_{\text{j}})\geq\text{min\_d( \text{S}_{\text{i}}\,\text{CH}_{\text{j}})}\)then
14. Put \(\text{S}_{\text{i}}\) near \(\text{CH}_{\text{j}}\)
15. \(\text{S}_{\text{i}}\.\text{CN}\leftarrow\,\ \text{CH}_{\text{j}}\).CN
16. else // \(\text{C}_{\text{range}}\big{(}\text{S}_{\text{i}}\,\text{CH}_{\text{j}})\!<\!\text{min}_{\text{i=1}}^{\text{i=1}}\text{d}( \text{Si}\,\ \text{CH}_{\text{j}})\)
17. Drop \(\text{S}_{\text{i}}\) in a free cell in the grid
18. \(\text{S}_{\text{i}}\.\text{CN}\ \leftarrow\ \text{CH}_{\text{j}}\).CN
19. //NewNumber = total number of clusters + 1
20. Endif
21. Endfor
```  
**Algorithm 1** Initialization phase (IAC)  
Initialized clusters with a most similar cluster head (MSCH) are formulated by selecting the minimal distance min_d(S\({}_{\text{i}}\,\ \text{CH}_{\text{j}}\)) between each sensor node \(\text{S}_{\text{i}}\) and each cluster head CH\({}_{j}\).