# Cooperative Data Collection Mechanism Using Multiple Mobile Sinks in Wireless Sensor Networks
## 4 The Proposed CDCA Algorithm
### Network Partition Phase
\[s^{best}=\ arg\max_{s_{i}\in T_{i},T_{i}\in N(T^{min})}\frac{dis(s_{i},T_{i}) }{dis\big{(}s_{i},T^{min}\big{)}} \tag{14}\]  
where \(dis(s,T)\) denotes the number of hops from sensor \(s\) to the root of tree \(T\). That is, the sensor that has a large hop distance to the root of tree \(T_{i}\) indicates that the energy consumed for packet forwarding of sensor is large. On the contrary, the sensor that has a small hop distance to the root of tree \(T_{min}\) indicates that the energy consumed for packet forwarding of sensor is small. As a result, the sensor that meets the requirement of Expression (14) can reduce maximal energy consumption of tree \(T_{i}\) and increase minimal energy consumption of tree \(T^{min}\). The aforementioned operations must be repeated until the number of subtree nodes is uniform. That is \(\mid T_{1}\mid=\mid T_{2}\mid=\cdots=\mid T_{k}\mid\). The following presents the proposed \(BTP\) algorithm (Algorithm 1). ```
Input:\(S=\{s_{1},s_{2},s_{3},\cdots s_{n}\},\ T^{\prime}=\varnothing\); Output: A set of balanced subtree \(\mathbf{T^{\prime}}=\{\ T^{\prime}_{1},\ T^{\prime}_{2}\cdots,T^{\prime}_{k}\}\);
1. \(\tilde{\mathrm{N}}\)={sink}
2. While(\(\hat{S}\
eq\varnothing\))
3 Evaluate \(NP(i)\) according to Equation (10), for each \(s_{i}\in S\);
4 Evaluate \(D(i,T)\), according to Equation (11), for each \(s_{i}\in S\);
5 Evaluate \(W_{i}\) according to Equation (12);
6\(s^{\textit{largest}}=\underset{s_{i}\in S}{\textit{arg}\,\underset{s_{i}\in S}{ \textit{max}}\,W_{i}}\);
7. \(\tilde{\mathrm{N}}=\tilde{\mathrm{N}}\cup\left\{s^{\textit{largest}}\right\}\);
8. \(\hat{S}=\hat{S}-\left\{s^{\textit{largest}}\right\}\);
9. Reconstruct \(k\) subtrees \(T=\{T_{1},T_{2},\cdots,T_{k}\}\);
10. } 11. Let \(nb_{i}\) = numbers of nodes in subtrees \(T_{i}\), for \(1\ \leq I\leq k\);
12. \(T_{\textit{arg}}=\frac{\sum_{i=1}^{k}nb_{i}}{k}\);
13. For (\(z=1\); \(z<=k\); \(z++\)){
14. If (\(nb_{z}==T_{\textit{avg}}\)){
15. \(T^{\prime}=T^{\prime}\cup\{T_{2}\}\);
16. \(T\)=\(T-\{T_{2}\}\);
17. Else{
18. \(T^{\textit{max}}=max|T_{i}|\), \(T_{i}\in\{T_{1},T_{2},\ \cdots,T_{k}\}\);
19. \(T^{\textit{min}}=min\Big{|}T_{j}\Big{|}\), \(T_{j}\in\{T_{1},T_{2},\ \cdots,T_{k}\}\);
20. If ( \(T_{i}\) and \(T^{\textit{min}}\) are neighboring trees)
21. \(s^{\textit{best}}=\underset{s_{i}\in T_{i},T_{i}\in N(T^{\textit{min}})}{ max}\frac{dis(s_{i},T_{i})}{dis(s_{i},T^{\textit{min}})}\) ;
22. Remove the edge linking from \(s^{\textit{best}}\) to its parent;
23. Connecting point \(s^{\textit{best}}\) to the nearest node in \(T^{\textit{min}}\);}
```  
**Algorithm 1** Balanced Tree Partition (_BTP_) Algorithm. The following presents an example for operating the proposed _BTP_ algorithm. The proposed _BTP_ algorithm calculates the \(W_{i}\) of each sensor node in tree and then selects \(s_{9}\) which has the maximal value of cost index as the candidate of the new root. The _BTP_ algorithm then adds \(s_{9}\) into tour set \(\tilde{\mathrm{N}}\) and removes \(s_{9}\) and edge (\(s_{5},s_{9}\)) from the minimal spanning tree given in Figure 1(a). As a result, the original MST has been partitioned into two trees, as shown in Figure 1(b). The repetitions of executing _BTP_ algorithm will continuously select one sensor node with the maximal cost index value to play the role of new root until the number of nodes in \(\tilde{\mathrm{N}}\) reaches to \(k\). In the second repetition, the proposed _BTP_ algorithm will select \(s_{16}\) to play the role of new root since \(s_{16}\) has the maximal value of cost index. As shown in Figure 1(c), tree \(T\) has been partitioned into three subtrees \(T_{1},T_{2}\) and \(T_{3}\). Then _BTP_ algorithm tried to balance the subtrees \(T_{1},T_{2}\) and \(T_{3}\).The numbers of nodes in subtrees \(T_{1},T_{2}\) and \(T_{3}\) are 6, 10, 8, respectively. The average number of nodes of the three subtrees is 8. To balance the three subtrees, \(T_{2}\) should move two nodes to \(T_{1}\).