# 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.2 Main Clustering  
Once the previous phase is complete, we will have obtained \(\text{k}\) clusters with their CHs and other nodes that were not yet assigned to any clusters (free clusters). We apply Algorithm 2. The ant moves randomly around the grid, calculating the dropping probability function for empty cells along the way after verifying the pick-up probability. If a sensor's drop probability in an empty cell exists, the ant will drop it, and the CN of \(\text{S}_{i}\) will be replaced by the CN of the closest CH in the ant's neighbourhood while verifying the communication range. Otherwise, the ant will randomly place \(\text{S}_{i}\) in a grid cell (without changing the CN of \(\text{S}_{i}\)), which is considered a cluster. ```
1./*Main loop*/
2.fort = 1 to \(\text{t}_{\text{max}}\)do
3.for all ants do
4.If (ant unladen) then
5. Compute \(\text{P}_{\text{pick}}(\text{S}_{i}\ )\) using Equation (13)
6. Select a random real number \(\text{P}_{\text{r}}\in\)[0,1]
7.If (\(\text{P}_{\text{r}}\prec\text{P}_{\text{pick}}(\text{S}_{i}\ )\)) then
8. Pick up \(\text{S}_{i}\)
9.endif
10.Else
11.If (ant carrying object) \(\text{S}_{i}\)) then
12. Find MSCH
13. Compute \(\text{P}_{\text{drop}}(\text{S}_{i}\ )\) using Equation (14)
14.If (\(\text{P}_{\text{r}}\prec\text{P}_{\text{drop}}(\text{S}_{i}\ )\)) then
15. Try to drop \(\text{S}_{i}\ \text{ near MSCH}\)
16.\(\text{S}_{i}\ \text{CN}\leftarrow\text{MSCH}\.\text{CN}\)
17. refreshed_memory(ant)
18.endif
19.Endif
20.if UnsuccessfulTries > \(\delta\)then //\(\delta\) is a predefined threshold
21.\(\alpha\leftarrow\alpha+\Delta\alpha\)
22.endif
23.endfor
24.endfor
```  
**Algorithm 2** main clustering (IAC)  
In addition, as mentioned below, we applied several modifications to the ant clustering algorithm to boost its performance. We used short-term memory for each ant to improve the speed and the quality of clustering [23]. As a result, each ant can remembering a few sites where it has effectively dropped a sensor. Then, upon selecting a new sensor, this memory is checked to bias the ant's direction movement. Eventually, the ant returns to the location where it last dropped a comparable sensor. During the pick-up/dropping function, the extent of similarity between sensor S\({}_{i}\) and its neighbours is calculated as follows (we have changed the fundamental notion of this formula offered by [23] with our clustering problem):  
\[\text{f}(\text{S}_{i}\ )=\text{max}(0;\frac{1}{S^{2}}\sum_{\text{S}_{i}\ \in\text{S}(i)}[1-\left(\frac{\text{d}(\text{S}_{i}\,\ \text{S}_{j})\times C_{\text{range}}(\text{S}_{i}\,\ \text{S}_{j})}{\alpha\mu}\right)] \tag{11}\]  
S(i) signifies the local neighbourhoods surrounding the site of the communication range, and d(S\({}_{i}\,\ \text{S}_{j}\)) specifies the distance between sensors S\({}_{i}\) and S\({}_{j}\), where d is the Euclidean distance and \(\alpha\) is a factor of the scale for dissimilarity. \(\alpha\) is chosen to be very small to prevent the creation of clusters; otherwise, the individual clusters merge. The value of \(\mu\), which is the average of the total sum of the distances between the sensors, is calculated by the following formula:  
\[\mu= \frac{2}{\text{N}(\text{N}-1)}\sum_{i=1}^{\text{N}}\sum_{j=1}^{i-1} \text{d}(\text{S}_{i}\,\ \text{S}_{j})\times C_{\text{range}}(\text{S}_{i}\,\ \text{S}_{j}) \tag{12}\]  
where N denotes the total number of sensors in the system. The probability of an ant picking up or dropping the object is computed when the similarities are assessed as follows:  
\[\text{P}_{\text{pick}}(\text{S}_{i}\ )=(\frac{\text{K}_{1}}{\text{K}_{1}+\text{f}(\text{S}_{i} \ )})^{2} \tag{13}\]  
\[\text{P}_{\text{drop}}(\text{S}_{i}\ )=(\frac{\text{f}(\text{S}_{i}\ )}{\text{K}_{2}+ \text{f}(\text{S}_{i}\ )})^{2} \tag{14}\]  
Choosing the appropriate values for K\({}_{1}\) and K\({}_{2}\) significantly impacts the probability of the sensors being picked up or dropped.