# Cooperative Data Collection Mechanism Using Multiple Mobile Sinks in Wireless Sensor Networks
## 4 The Proposed CDCA Algorithm
### CP Selection and Path Construction Phase  
This phase aims to select \(k_{i}\) CPs from the sensors in \(T_{i}\) and construct a path \(\pi_{i}\) which visits the \(k_{i}\) CPs for data collection.  
Let \(P_{i}\) denote the set of data collection points which has been selected to play the role of root in subtree \(T_{i}\). Let \(S_{i}\) denote the set of all sensors in subtree \(T_{i}\) and \(S_{i^{\prime}}\) denote the set of sensors that are not  
Figure 2: An example of network partition phase. (**a**) Given a minimal spanning tree; (**b**) Selecting sensor node \(s_{9}\) as subroot; (**c**) Selecting sensor node \(s_{16}\) as new root; (**d**) Three subtree \(T_{1},T_{2}\) and \(T_{3}\); (**e**) Selecting sensor node \(s_{6}\) to move from \(T_{2}\) to \(T_{1}\); (**f**) Selecting sensor node \(s_{7}\) to move from \(T_{2}\) to \(T_{1}\).  
selected to play the role of CPs. This phase firstly selects one best sensor node \(s^{best}\) from set \(S_{i^{{}^{\prime}}}\) at a time. Then the selected \(s^{best}\) will join the set \(P_{i}\) and be removed from \(S_{i^{{}^{\prime}}}\). After that, the subtree will be restructured. Data collected by each node in set \(P_{i}\) can be directly sent to the mobile sink \(m_{i}\), since the mobile sink \(m_{i}\) will visit each selected \(CP\) in set \(P_{i}\). In this way, the energy consumption for those sensors that should forward the data of \(CP\) can be further saved.  
Let \(P_{i}=\left\{p_{i,1},p_{i,2},p_{i,3},\cdots,p_{i,y}\right\}\) denote the set of \(y\) CPs, which have been selected from in subtree \(T_{i}\). Let \(R_{i}\) denote the shortest Hamiltonian route the connects \(y\)\(CP\)s in \(P_{i}\). Since the selection of each \(CP\) can construct a new subtree, it is obvious that subtree \(T_{i}\) has been partitioned into \(y\) subtrees. Let \(p_{i,1}\) denote the root of tree \(T_{i,j}\). Let \(s_{x}\) be any sensor in tree \(T_{i,j}\). Let \(p^{closest}\) denote the CP which is closest to sensor node \(s_{x}\). Equation (15) derives \(p^{closest}\).  
\[p^{closest}=arg\min_{1\leq h\leq y}\left(dist(p_{i,h},\ s_{x})\right) \tag{15}\]  
Let \(b_{x}\) denote the benefit index obtained by determining \(s_{x}\) as the data collection point. The value of \(b_{x}\), as derived in Equation (16), can be evaluated by the number of packets that are saved for transmission divided by the cost of distance from some \(s_{i,j}\in P_{i}\) to \(s_{i,j}\).  
\[b_{x}=\frac{D(i,T)\ \times\ NP(i)}{dist\ p^{closest},\ s_{x}} \tag{16}\]  
This phase will calculate \(b_{x}\) for each \(s_{x}\in S_{i^{{}^{\prime}}}\) and select the best node \(s^{best}\) to play the role of \(CP\), where \(s^{best}\) satisfies the following condition. Equation (17) derives \(s^{best}\).  
\[s^{best}=arg\max_{s_{x}\in T_{i,j}}\ b_{x} \tag{17}\]  
Then a new Hamiltonian route will be constructed by adding the new \(CP\)\(s^{best}\) to the existing route \(R_{i}\) for mobile sink \(m_{i}\), where \(R_{i}\) connects all (\(y+1\))\(CP\)s in set \(P_{i}=P_{i}\cup\left\{s^{best}\right\}\) and checks whether or not the length \(|\pi_{i}|\) is smaller than the length bound \(L_{max}\). If it is the case, the proposed algorithm will add the collection point \(s^{best}\) to set \(P\) and remove the \(s^{best}\) from set \(V\). The edge that connects \(s^{best}\) and its parent will be removed accordingly. Otherwise, the selection operation will be terminated. The set \(P_{i}\) will be the output of this phase.