# Data Collection Based on Opportunistic Node Connections in Wireless Sensor Networks
## 4 Data Collection Scheme Based on Opportunistic Node Connections
### The Optimal Path Calculation Based on the Opportunistic Connection Random Graph  
Once the OCRG is constructed, it needs to find the optimal path from any node to the mobile sink to realize the reliable sensing data forwarding. In this work, a spanning tree algorithm (Algorithm 2) is designed to calculate the optimal path with the max value of Path Connectivity (PC) (Definition 3) from the mobile sink to each node based on this OCRG. By employing this algorithm, the mobile sink can produce a spanning tree, based on which, each node can get its optimal path to the sink with the corresponding PC of it. Therefore, the mobile sink will broadcast this spanning tree to nodes under the long radio range \(R_{l}\). **Definition 3**. : _Path Connectivity (PC). In the OCRG, the PC of a path is related to the link connectivity between any two adjacent nodes on this path, which is used to reflect the reliability of this path when delivering data. As for a path (\(v_{i}\), \(v_{i+k}\), \(k\)), where node \(v_{i}\) is the source node, node \(v_{i+k}\) represents the node \(k\) hops away from \(v_{i}\) on this path, \(k\) is the hops on the path and satisfies \(1\leq k\leq N-1\), the PC of this path is defined as:_  
\[\text{PC}_{path(v_{i}v_{i+k},k)}=\prod_{j=0}^{k-1}P_{v_{i+j}v_{i+(j+1)}} \tag{15}\]  
During constructing this spanning tree, all nodes in the OCRG are subdivided into two sets: (i) set K: including the nodes whose optimal paths from the mobile sink to themselves are known, and (ii) set U: including the remaining nodes. In the beginning, set K includes only the mobile sink while set U includes the remaining nodes in the OCRG, and a node in set U will be transferred to set K if the mobile sink finds the optimal path to it. The algorithm includes two phases, of which the first phase is initialization. In this phase, the mobile sink calculates the PC of the paths from itself to all nodes in set U as follows:  
\[\text{PC}_{path(v_{\text{sink}},v_{i},*)}=\left\{ \begin{array}{ll}P_{v_{ \text{sink}}v_{i}}&,v_{\text{sink}}\text{ is directly connected to }v_{i}\\ 0&,\text{otherwise}\end{array} \right. \tag{16}\]  
And the nodes on each path can be denoted as follows:  
\[\text{PATH}(v_{\text{sink}},v_{i},*)=\left\{ \begin{array}{ll}\{v_{\text{ sink}},v_{i}\}&,v_{\text{sink}}\text{ is directly connected to }v_{i}\\ \varnothing&,\text{otherwise}\end{array} \right. \tag{17}\]  
In the second phase, the mobile sink selects a node \(v_{i}\) with a max value of PC from set U and transfers it to set K, and then updates the PC of the path from \(v_{\text{sink}}\) to each node \(v_{j}\) in set U but directly connected to \(v_{i}\) as follows:  
Figure 6: An illustration of an Opportunistic Connection Random Graph (OCRG) with three nodes. \[PC_{path(v_{\text{sink},v_{j},*})}\leftarrow\max\Bigl{\{}PC_{path(v_{\text{sink},v_{ j},*})},PC_{path(v_{\text{sink},v_{j},*})}\times P_{v_{j}v_{j}}\Bigr{\}} \tag{18}\]  
For each path, once the PC of it is updated, the nodes on it should be updated as follows:  
\[PATH(v_{\text{sink},v_{j},*})\gets PATH(v_{\text{sink},v_{i},*})+v_{j} \tag{19}\]  
Repeating the work in second phase until set U is empty, a spanning tree with the mobile sink as the root node can be generated. The algorithm improves the efficiency of finding the optimal path. If the mobile sink calculates and selects the optimal path of each node directly, for each node, it needs to explore all the possible paths between them to determine which one has the maximum PC, which is inefficient and brings high delay. Furthermore, when the network density increases or the data collection scope expands, the number of the paths from a node to the mobile sink increases greatly, which could further decrease its efficiency. ```
1. Input: an OCRG;
2. Output: a spanning tree with the mobile sink as the root node;
3. Add \(v_{\text{sink}}\) into set K;
4. Add the remaining nodes in the OCRG into set U;
5. for each node \(v_{i}\) in set U do// initialization
6. if(\(v_{i}\) is directly connected to \(v_{\text{sink}}\))
7.