## 3 Cross Deployment Networking Method
### Cross Deployment Networking Method  
Compared with radio communication, acoustic communication has low data transmission rates and high error rates. Therefore, in order to improve the reliability of data transmission and the parallel data transmission capabilities, we have built a \(K\)-Connected \(K\)-Dominating Set (\(K\)-CDS) as the virtual communication backbone, and proposed a Cross Deployment Networking Method (CDNM) of UWSNs suitable for the underwater environment. In CDNM, nodes on the communication backbone are responsible for data transmission. The users can query data by accessing the nodes on this communication backbone.  
Firstly, we introduce the concept of the \(K\)-CDS. A point set \(V\) is \(K\)-connected if and only if the network is still connected after any of the \(K-1\) points is taken out of this set. A point set \(V^{\prime}\subseteq V\) is \(K\)-dominated if and only if the nodes in set \(V\) are in dominating set \(V^{\prime}\) or there are \(K\) neighbor nodes in the dominating set. A point set \(V^{\prime}\subseteq V\) is \(K\)-connected \(K\)-dominated, if \(V^{\prime}\) is \(K\)-dominated, and the induced sub-graph of \(V^{\prime}\) is \(K\)-connected. As shown in Figure 4, \(K=1\), \(2\), \(3\) and \(8\) nodes form the \(K\)-CDS of the point set, in which points marked as concentric circles are selected into the \(K\)-CDS.  
Because the nodes are deployed randomly, the neighbor relationships between nodes are also generated randomly. Therefore, during the \(K\)-CDS building process, we adopt the random method, namely, every node has a probability of \(p_{k}\) of being a backbone node. The \(p_{k}\) is a function that depends on \(K\) and the number of sensors. The algorithm of CDNM (Algorithm 1) is then described as follows:  
```
1:Initial network nodes set \(NNS\) = all node, virtual communication backbone nodes set \(VCB\_set\) = \(\O\), no virtual communication backbone nodes set \(NVCB\_set\) = \(\O\) and setup the initial value of \(p_{k}\); Random select \(N_{i}\) from \(NNS\) as initial node of virtual communication backbone; Put \(N_{i}\) into \(VCB\_set\);
2:For(\(j\) = 0; \(j\) <= the node number of \(NNS\); \(j\)++)
3: Random select \(N_{k}\) from other nodes in \(p_{k}\) probability
4:If(\(N_{k}\) is not a member of \(VCB\_set\) and \(N_{k}\) + \(VCB\_set\) meeting \(K\)-CDS)
5: Put \(N_{k}\) into \(VCB\_set\);
6:else
7: Put \(N_{k}\) into \(NVCB\_set\);
8:endif;
9:endfor;
10:create routing protocol on OSPF;
11:end.
```  
**Algorithm 1**CDNM  
When \(p_{k}\) is appropriate, there is a high probability that the network can be built with \(K\)-CDS and CDNM. For example, in a network which includes 200 nodes, 2-CDS can be built with a probability of 98.2% when \(p_{k}\) is 50%, 3-CDS can be built with a probability of 97.4% when \(p_{k}\) is 60%. The advantage of this approach lies in its simplicity: it can build \(K\)-CDS without interaction with other nodes around it and it is especially suitable for environments with poor underwater communication conditions.  
After the \(K\)-CDS is completed, the network begins to generate the routing, namely, to build the routing table between \(K\)-CDS.