# An Efficient Model-Based Clustering via Joint Multiple Sink Placement for WSNs
## 4 Our Proposal
### Data Routing and Transmission  
A sink creates pathways between CHs and itself once the CHs are picked. Since the BS includes comprehensive topology information, it chooses the best path in such a way that the routing path's overall energy consumption is as low as possible. Then, before constructing any paths, it classifies the routes into Direct_path, Direct_nodes_CH, and Multi_path_R. Direct_path is a path over which nodes communicate directly to the sink without any intermediaries, and those nodes are named Direct_nodes_sink. Direct_nodes_CH is a path of all nodes that use only CHs as intermediate nodes to the sink, and Multi_path_R is a path consisting of multiple intermediate nodes excluding CH. During the transmission phase, the sink verifies whether the CH has sufficient remaining energy to participate. Otherwise, it is replaced by another node in the same cluster as the new CH. However, if its distance from the previous CH is not in the communication range of the old CH or the sink (assigned to this cluster), it will not be considered, and the following node with the next-highest Cp value would be considered instead. This process is successfully executed following Algorithm 3. ```
Input: Old_CH Output: New_CH
```
1.for each SN in a cluster do
2. calculate Cp
3. select node with max Cp
4.if\(C_{\text{range}}(old_{CH},S_{i})\prec d(old_{CH},S_{i})\)
5. select the following nodes with max Cp
6. Else
7. Select S\({}_{i}\) as New_CH
8.Endfor ```
**Algorithm 3**Cluster Head Adjustment  
The sink constructs a Route Set (Multi_path_R) for each CH representing all possible paths to the CH. It already generates a Legitimate Route Set (Multi_path_LR), which includes all of the routes with remaining energy over the threshold energy (\(E_{\text{threshold}}\)). We calculate \(E_{\text{threshold}}\) using Equation (17). A path constitutes several SNs that use multihopcommunication to send packets from the CH to the sink. Any path with a sensor node with residual energy below a predetermined \(\mathrm{E_{threshold}}\) is excluded from the Multi_path_LR set. \[\mathrm{E_{threshold}}=\frac{\sum\mathrm{R_{energy}(S_{i})}}{\mathrm{n_{i}}} \tag{17}\]  
where \(\sum\mathrm{R_{energy}(S_{i})}\) is the sum of all nodes' residual energies of cluster i, and \(\mathrm{n_{i}}\) is the number of existing sensors in cluster i. Then, for all Multi_path_LR, the sink computes the cost of energy, which is the sum of the cost of energy of each node on that path. The optimal path between the CH and sink is thought to be that with the lowest energy cost. We calculate the cost of any route by using Equation (18), which is defined as follows:  
\[\mathrm{cost}(\mathrm{LRj})=\sum_{\mathrm{x}=0}^{\mathrm{v_{X}\in\mathrm{LRj} }}\frac{\mathrm{d}(S_{i},S_{i+1})}{\mathrm{R_{energy}(S_{i})}} \tag{18}\]  
where \(\mathrm{R_{energy}(S_{i})}\) is the residual energy of node \(S_{i}\), and \(\mathrm{d}(S_{i},S_{i+1})\) is the distance between \(S_{i}\) and the next node \(S_{i+1}\). ```
Declare  Direct_nodes_sink = {}  Direct_nodes_CH = {}  Multi_path_R = {}  Multi_path_LR = {}  Multi_path_BR = {} /represents the set of best routes to CH
```
```
1.for each \(S_{i}\) in nodes
2.ifd(\(S_{i}\), \(\mathrm{sink}\)) < d(\(S_{i}\), CH) & \(\mathrm{C_{range}(S_{i}\), \(\mathrm{sink}\)) > d(\(S_{i}\), \(\mathrm{sink}\)) then
3. Add \(S_{i}\) to Direct_nodes_sink
4. Else
5.for each CH do
6.if(\(E_{\mathrm{res}}\) (CH) < \(E_{\mathrm{threshold}}\)) then
7. select new CH using Algorithm 3
8.if\(S_{i}\)\(\mathrm{\ell N(CH)}\) & \(\mathrm{C_{range}(S_{i}\), CH) > d(\(S_{i}\), CH) then
9. Add \(S_{i}\) to Direct_nodes_CH
10. Else
11.for each route \(Rj\in\) Multi_path_R do
12.if\(\forall S_{i}\in Rj\):d(\(S_{i},S_{i+1}\)) \(<\) Dthreshold || \(E_{\mathrm{g}}(S_{i})\) < \(E_{\mathrm{threshold}}\) then
13. Multi_path_LR = Multi_path_LR \(\cup\) Rj
14. End if
15. End for
16.for each route \(L\mathrm{Rj}\in\) Multi_path_LR
17. Calculate cost(LRj) using Equation (18)
18. endfor
19. BR = min(cost(LR))
20. Multi_path_BR = Multi_path_BR \(\cup\) BR
21. End if
22. End if
23.