# Adaptive Packet Coding for Reliable Underwater Acoustic Communications
## 6 Proposed Two-Step DP Approach
### The Cost of the First Transmission  
For \(i=1\), \(\epsilon_{1}^{(k+1)}=(q_{0}^{(k)}\), \(h_{0}^{(k)}\), \(q_{0}^{(k+1)}\), \(h_{0}^{(k+1)}\), \(B_{1}^{(k+1)})\). Note that \(q_{0}^{(k)}=q_{0}^{(k+1)}=0\) and the transmitter have no feedback information about the channels. Thus, we use the steady-state probability to present the probability. Then, we have  
\[J_{1}^{\prime}(\epsilon_{1}^{(k+1)})=\min_{N_{1}^{(k)}}\left\{\gamma(T_{1}^{(k +1)})+\mathbb{E}\Big{[}l_{2}^{\prime}(\epsilon_{2}^{(k)})|\epsilon_{1}^{(k+1)} \Big{]}\right\} \tag{54}\]  
where  
\[\mathbb{E}\Big{[}l_{2}^{\prime}(\epsilon_{2}^{(k)})|\epsilon_{1}^{(k+1)}\Big{]} =\sum_{s_{1}^{(k)}=0}^{N_{1}^{(k)}}\sum_{l=1}^{L}l_{2}^{\prime}( \epsilon_{2}^{(k)})P_{s}(s_{1}^{(k)},h_{1}^{(k)},N_{1}^{(k)})P_{\pi}(h_{1}^{(k )}=\delta_{l}) \tag{55}\]  
Similarly, \(\epsilon_{1}^{(k)}=(q_{0}^{(k)},h_{0}^{(k)},q_{-1}^{(k+1)},h_{-1^{\prime}}^{ (k)},B_{1}^{(k)})\); the cost for the overall \(M\) transmissions is given as  
\[\begin{split} l_{1}^{\prime}(\epsilon_{1}^{(k)})& =\min_{N_{m}^{(k)}}\Big{\{}\gamma(T_{1}^{(k)})+\mathbb{E}\Big{[}l _{1}^{\prime}(\epsilon_{1}^{(k+1)})|\epsilon_{1}^{(k)}\Big{]}\Big{\}}\\ &=\min_{N_{m}^{(k)}}\Big{\{}\gamma(T_{p}N_{1}^{(k+1)}+2T_{g}+T_{ \text{ACK}})+\mathbb{E}\Big{[}l_{1}^{\prime}(\epsilon_{1}^{(k+1)})|\epsilon_ {1}^{(k)}\Big{]}\Big{\}}\end{split} \tag{56}\]  
where  
\[\mathbb{E}\Big{[}l_{1}^{\prime}(\epsilon_{1}^{(k+1)})|\epsilon_{1}^{(k)} \Big{]}=\sum_{l=0}^{L}l_{2}^{\prime}(0,h_{1}^{(k)},0,h_{0}^{(k+1)},N_{1}^{(k) })P_{\pi}(h_{1}^{(k+1)}=\delta_{l}) \tag{57}\]  
The two-step DP approach also first finds the optimal solution for each state and records it into a table. Then, the sender chooses the optimal \(N_{i}^{(k)}\) and \(N_{i}^{(k+1)}\) according to system state. The details of the proposed optimal two-step DP policy are summarized in Algorithm 1.  
```
1:Let \(\epsilon_{M}^{(k+1)}=(q_{M-1^{\prime}}^{(k)},h_{M-1^{\prime}}^{(k+1)},q_{M-1^ {\prime}}^{(k+1)},h_{M-1^{\prime}}^{(k+1)})\).
2:Calculate \(l^{\prime}_{M}(\epsilon_{M}^{(k+1)})\), \(\forall q_{M-1^{\prime}}^{(k)}\), \(\forall h_{M-1}^{(k)}\), \(\forall q_{M-1}^{(k+1)}\), \(\forall h_{M-1}^{(k+1)}\), \(\forall B_{M}^{(k+1)}\), based on (39) and save in the table.
3:Let \(\epsilon_{M}^{(k)}=(q_{M-1}^{(k)},h_{M-1}^{(k)},q_{M-2}^{(k+1)},h_{M-2}^{(k)}, B_{M}^{(k)})\).
4:Calculate \(l^{\prime}_{M}(\epsilon_{M}^{(k)})\), \(\forall q_{M-1}^{(k)}\), \(\forall h_{M-1}^{(k)}\), \(\forall q_{M-2}^{(k+1)}\), \(\forall h_{M-2}^{(k+1)}\), \(\forall B_{M}^{(k)}\), based on (50) and save in the table.
5:\(i=M-1\).
6:while\(i\geq 0\)
7:Let \(\epsilon_{i}^{(k+1)}=(q_{i-1}^{(k)},h_{i-1}^{(k)},q_{i-1}^{(k+1)},h_{i-1}^{(k)}, B_{i}^{(k+1)})\).
8:Calculate \(l^{\prime}_{i}(\epsilon_{i}^{(k+1)})\), \(\forall q_{i-1}^{(k)}\), \(\forall h_{i-1}^{(k)}\), \(\forall h_{i-1}^{(k)}\), \(\forall h_{i}^{(k+1)}\) based on (51) and save in the table
9:Let \(\epsilon_{i}^{(k)}=(q_{i-1}^{(k)},h_{i-1}^{(k)},q_{i-2}^{(k+1)},h_{i-2}^{(k)}, B_{i}^{(k)})\).
10:Calculate \(l^{\prime}_{i}(\epsilon_{i}^{(k)})\), \(\forall q_{i-1}^{(k)}\), \(\forall h_{i-1}^{(k)}\), \(\forall q_{i-2}^{(k+1)}\), \(\forall h_{i-2}^{(k)}\), \(\forall B_{i}^{(k)}\) based on (53) and save in the table
11:Find the optimal (\(N_{i}^{(k)}\), \(N_{i}^{(k+1)}\)) to maximize \(l^{\prime}_{i}(\epsilon_{i}^{(k+1)})\)
12:\(i=i-1\);
13:endwhile
14:for\(i=1\); \(i\leq M\) ; \(i=i+1\)do
15:Find the optimal (\(N_{i}^{(k)}\), \(N_{i}^{(k+1)}\)) based on line 9.
16:Update the \(\epsilon_{i}^{(k)}\) and \(\epsilon_{i}^{(k+1)}\).
17:endfor
```  
**Algorithm 1** The proposed two-step DP algorithm.