# A Co-Design-Based Reliable Low-Latency and Energy-Efficient Transmission Protocol for UWSNs
## 4 Problem Statement
### Dynamic Routing Problem  
After the layering phase, each node will obtain their neighbor table \(T\). In the neighbor table, all neighbors are classified as lower-layer neighbors (LNs) and higher-layer neighbors (HNs). As long as each node transmits packets to its LNs, all packets will eventually be transmitted to the sink node. Therefore, when node \(n\) has a packet to forward, it will choose several neighbors from its LN as the next-hop. Let \(F_{n}=\{f_{n}^{1},f_{n}^{2},...,f_{n}^{j}\}\) express the forwarding set of \(n\), where \(f_{n}^{j}\) is the \(j^{th}\) LN of node \(n\). Node \(n\) is going to select one or more nodes from \(F_{n}\) as its next-hop. Let selection strategy \(S_{n}=(S_{n}^{1},S_{n}^{2},...,S_{n}^{j})\) indicate the choice of node \(n\) to all LN in \(F_{n}\), where binary \(S_{n}^{j}\in\{0,1\}\) denotes the choice of node \(n\). \(S_{n}^{j}=1\) means node \(n\) will choose node \(j\) as its next-hop, and 0 otherwise.  
According to the forwarding set \(F_{n}\) and the neighbor table \(T\), a \(j*j\) adjacency matrix \(E\) is constructed, where \(E\) is created to express the relationship connectivity between nodes in \(F_{n}\). Let \(f_{n}^{\alpha}\) be one of the vertices \(v_{\alpha}\) in adjacency matrix \(E\), and binary \(e_{\alpha\beta}\in\{0,1\}\) express the neighbor relationship between vertex \(v_{\alpha}\) and vertex \(v_{\beta}\). The element \(e_{\alpha\beta}\) is 1 when vertex \(v_{\alpha}\) and vertex \(v_{\beta}\) are neighbors, and zero when they can not detect each other.  
Due to the existence of the neighbor table, no control packet is needed before sending a data packet. Strategy \(S_{n}\) will select multiple nodes as the next-hop, as long as one node in \(S_{n}\) forwards the packet regarded as a successful transmission. Thus, CDTP will not perform collision detection for each pair of nodes and no longer sends control packets for the MAC-layer. These two aspects will effectively reduce the end-to-end latency. After reducing the end-to-end latency, the selection strategy \(S_{n}\) ought to maximize  
Figure 3: Multi-copy Problem.  
one-hop reliability by avoiding collision and minimize the multi-copy problem to maximize the system performance. This can be formulated as the following optimization problem:  
\[\arg\max_{S_{n}}P^{n\to S_{n}} \tag{1}\]  
This is subject to the following constraints:  
\[\sum_{\beta=2}^{j}\sum_{\alpha=1}^{\beta-1}S_{n}^{\alpha}S_{n}^{ \beta}e_{\alpha\beta}/\sum_{\beta=2}^{j}\sum_{\alpha=1}^{\beta-1}S_{n}^{\alpha }S_{n}^{\beta}=1 \tag{2}\] \[S_{n}^{\alpha},S_{n}^{\beta},e_{\alpha\beta}\in\{0,1\} \tag{3}\]  
\(P^{n\to S_{n}}\) is the probability that at least one chosen forwarder of node \(n\) under strategy \(S_{n}\) receives a packet successfully. However, it is hard to estimate the value of \(P^{n\to S_{n}}\) due to the complex underwater environment and the randomness of the packet generation. To estimate and maximize the value of \(P^{n\to S_{n}}\), we convert this problem to a multi-objective optimization problem in the next section. During this process, the neighbor information between nodes is fully utilized to maximize the transmission reliability hop by hop.  
Equation (2) ensures that the chosen nodes in \(S_{n}\) can detect each other. For any pair of selected nodes \(\alpha\) and node \(\beta\) in \(S_{n}\), \(e_{\alpha\beta}\) all equal to \(1\) indicates that the nodes in the selection strategy satisfy the above condition. This will avoid the special case resulting in the multi-copy problem mentioned earlier.