# Cooperative Data Collection Mechanism Using Multiple Mobile Sinks in Wireless Sensor Networks
## 4 The Proposed CDCA Algorithm
### Network Partition Phase  
Given a \({}_{\text{min}}\)imum spanning tree (MST) \(T\), the root of tree \(T\) can be considered as the sink and there is a mobile sink \(m_{0}\) located at the root. The Network Partition Phase aims to partitions \(T\) into \(k\) disjoint subsets \(T=T_{1},T_{2},\ldots,T_{k}\) such that the sizes of them are similar. Each mobile sink \(m_{i}\) will be allocated to \(T_{i}\) for data collection. Let \(S\) denote the set of all sensor nodes. Let \(\tilde{\text{N}}\) and \(\hat{S}=S\backslash\tilde{\text{N}}\) denote the sets of selected and not selected roots for \(k\) subtrees, respectively. Let \(s^{largest}\) denote the sensor with largest cost in \(\hat{S}\). The basic concept of this phase is to find the sensor \(s^{largest}\) in \(\hat{S}\) in each run to play the role of tree root until \(k\) roots are selected. In each run, the selected \(s^{largest}\) will join set \(\tilde{\text{N}}\). After that, the minimum spanning tree will be restructured. The following gives the general descriptions for the sink to split up the MST \(T\). Let \(D(i,T)\) represent the number of hops from sensor \(s_{i}\) to the root of its tree. Let \(NS(i,T)\) denote the number of sensors rooted by \(s_{i}\). Assume that each sensor creates one packet in each round. Let \(NP(i)\) represent the number of packets received by sensor node \(s_{i}\), including its own reading. Equation (10) presents the relation of \(NP(i)\) and \(NS(i,T)\). \[NP(i)=NS(i,T)\ +\ 1 \tag{10}\]  
Let \(Hops(i,sink)\) denote the number of hops from \(s_{i}\) to the sink contains sensor node \(s_{i}\). If sensor \(s_{i}\) is selected as the root of some subtree \(T_{i}\), the number of packets saved by selecting \(s_{i}\) as the \(CP\) is evaluated as shown in Equation (11). \[D(i,T)=Hops(i,sink)\ \times\ NP(i) \tag{11}\]  
Let \(W_{i}\) denote the cost obtained by selecting \(s_{i}\) as the tree root. The value of \(W_{i}\) is measured by the number of packets saved for transmission from some \(s_{j}\in P\) to \(s_{i}\), as shown in Equation (12). \[W_{i}=D(i,T)\ \times\ NP(i) \tag{12}\]  
The sink calculates the \(W_{i}\) of each \(s_{i}\in\hat{S}\) and selects the sensor \(s^{largest}\) with the largest cost. Expression (13) reflects the condition of sensor, which can be selected as the tree root. \[s^{largest}=arg\max_{s_{i}\in\hat{S}}W_{i} \tag{13}\]  
After that, the sensor \(s^{largest}\) is added into \(\tilde{\mathrm{N}}\) and is removed from \(\hat{S}\). The aforementioned operations will be repeated executed round by round until \(k\) roots are selected in \(\tilde{\mathrm{N}}\). As a result, the final selected largest cost set \(\tilde{\mathrm{N}}=\{\tilde{\mathrm{N}}_{1},\tilde{\mathrm{N}}_{2},\cdots \tilde{\mathrm{N}}_{k}\}\). The \(k\) nodes in \(\tilde{\mathrm{N}}\) will construct \(k\) subtrees \(T_{1},T_{2},\ldots,T_{k}\). Till now, this paper have partition the tree \(T\) into several subtrees \(T_{1},T_{2},\ldots,T_{k}\). The next operation is trying to balance the subtrees. Let \(T^{max}\) and \(T^{min}\) denote the trees with maximal and minimal numbers of sensor nodes, respectively. Let \(\Theta(T)\) denote the number of nodes in tree \(T\). The next step is to balance the tree size. The tree balancing can be achieved by moving some nodes of other tree to tree \(T^{min}\) or moving some nodes from tree \(T^{max}\) to other trees. To achieve this, the following defines neighboring trees which allow them to move node from one to another. Two trees \(T_{i}\) and \(T_{j}\) are said to be neighboring trees if there exist \(s_{i}\in T_{i}\) and \(s_{j}\in T_{j}\) such that \(s_{i}\) and \(s_{j}\) are neighbors. The following illustrates how the tree balancing can be achieved. Let \(N(T)\) denote the set of neighboring trees of tree \(T\). Let sensor \(s^{best}\) denote the sensor that will be moved to tree \(T^{min}\). The sensor that satisfies Expression (14) will be selected to move to tree \(T^{min}\).