# Adaptive Packet Coding for Reliable Underwater Acoustic Communications
## 6 Proposed Two-Step DP Approach
### The Cost of the \(M\)-th Transmission  
At the \(M\)-th transmissions of the \((k+1)\)-th block, the system state \(\mathbf{c}_{M}^{(k+1)}=(q_{M-1}^{(k)},\,h_{M-1}^{(k)},\,q_{M-1}^{(k+1)},\,h_{M-1}^ {(k+1)},\,B_{M}^{(k+1)})\). The expected cost of the \((k+1)\)-th block at the \(M\)-th transmission is similar to (19), which can be computed as  
\[{J^{\prime}}_{M}(\mathbf{c}_{M}^{(k+1)})=\min_{0\leq N_{M}^{(k+1)}\leq B_{M}^{(k+1 )}}\Bigl{\{}\gamma^{M}T_{M}^{(k+1)}+\mathbb{E}\Bigl{[}\pi(q_{M}^{(k+1)})|\mathbf{c }_{M}^{(k+1)}\Bigr{]}\Bigr{\}} \tag{39}\]  
where  
\[T_{M}^{(k+1)}=\left\{ \begin{array}{ll}0,\ \ \text{if}\ q_{M-1}^{(k+1)}\geq W \\ T_{p}N_{M}^{k+1}+T_{\tau},\ \ \text{if}\ q_{M-1}^{(k+1)}<W\end{array} \right. \tag{40}\]  
is the transmission time duration for the \((k+1)\)-th block. The expectation of penalty is given by  
\[\mathbb{E}\Bigl{[}\pi(q_{M}^{(k+1)})|\mathbf{c}_{M}^{(k+1)}\Bigr{]}= \mathbb{E}\Bigl{[}\pi(q_{M}^{(k+1)})|(q_{M-1}^{(k+1)},h_{M-1}^{(k +1)})\Bigr{]}\] \[= C\sum_{s_{M}^{(k+1)}=0}^{u_{M+1}^{(k+1)}}\sum_{l=1}^{L}P_{s}(s_{ M}^{(k+1)},h_{M}^{(k+1)},N_{M}^{(k+1)})P(h_{M}^{(k+1)}=\delta_{l}|h_{M-1}^{(k+1)}) \tag{41}\]  
Next, we consider the expected cost for the overall \(M\)-th transmission, \({J^{\prime}}_{M}(\mathbf{c}_{M}^{(k)})\). At this point, the sender knows the system state \(\mathbf{c}_{M}^{(k)}=(q_{M-1}^{(k)},\,h_{M-1}^{(k)},\,q_{M-2}^{(k+1)},\,h_{M-2}^{( k+1)},\,B_{M}^{(k)})\). It is clear that the calculation of \({J^{\prime}}_{M}(\mathbf{c}_{M}^{(k)})\) highly depends on \(q_{M-1}^{(k)}\) and \(q_{M-2}^{(k+1)}\). The state is different if \(q_{M-1}^{(k)}\) and \(q_{M-2}^{(k+1)}\) are larger or less than \(M\). Thus, the calculation of \({J^{\prime}}_{M}(\mathbf{c}_{M}^{(k)})\) is different with different \(q_{M-1}^{(k)}\) and \(q_{M-2}^{(k+1)}\). So, the analysis of different situations is as follows. If \(q_{M-1}^{(k)}\geq W\) and \(q_{M-2}^{(k+1)}\geq W\), it is obvious that  
\[{J^{\prime}}_{M}(\mathbf{c}_{M}^{(k)})=0 \tag{42}\]  
If \(q_{M-1}^{(k)}\geq W\) and \(q_{M-2}^{(k+1)}<W\), the transmission of the \(k\)-th block is finished. Then, \(N_{M}^{(k)}=0\). It degenerates into the problem in the RLPC-ARQ scheme. At this time, only the \((k+1)\)-th block may need to be transmitted. It relies on the transmission result of the \((M-1)\)-th transmission for the \((k+1)\)-th block. According to (32), \(N_{M-1}^{(k+1)}=B_{M}^{(k)}\). Thus,\[{I^{\prime}}_{M}({\mathbf{c}}_{M}^{(k)}) =\min_{0\leq N_{M}^{(k+1)}\leq Q}\mathbb{E}[J_{M}(h_{M-1}^{(k+1)},q_{ M-1}^{(k+1)})|(h_{M-2}^{(k+1)},q_{M-2}^{(k)},B_{M}^{(k)})]\] \[=\sum_{s_{M-1}^{(k+1)}=0}^{B_{M}^{(k)}}\sum_{l=0}^{L}J_{M}(h_{M-1}^ {(k+1)},q_{M-1}^{(k+1)})P_{s}(s_{M-1}^{(k+1)},h_{M-1}^{(k+1)},B_{M}^{(k)})P(h_{ M-1}^{(k+1)}=\delta_{l}|h_{M-2}^{(k+1)}) \tag{43}\]  
Note that \(q_{M-1}^{(k+1)}=q_{M-2}^{(k+1)}+s_{M-1}^{(k+1)}\). If \(q_{M-1}^{(k)}<W\) and \(q_{M-2}^{(k+1)}\geq W\), then \(B_{M}^{(k)}=Q\). This problem also degenerates into the former problem. \[{I^{\prime}}_{M}({\mathbf{c}}_{M}^{(k)}) =\min_{0\leq N_{M}^{(k+1)}\leq Q}\left\{\mathbb{E}[T_{M}^{(k)}|{ \mathbf{c}}_{M}^{(k)}]+\mathbb{E}\Big{[}\pi(q_{M}^{(k)})\Big{]}\right\}\] \[=J_{M}(h_{M-1}^{(k)},q_{M-1}^{(k)}) \tag{44}\]  
If \(q_{M-1}^{(k)}<W\) and \(q_{M-2}^{(k+1)}<W\), then the expected cost for the overall \(M\)-th transmission is given by  
\[{I^{\prime}}_{M}({\mathbf{c}}_{M}^{(k)}) =\min_{0\leq N_{M}^{(k)}\leq B_{M}^{(k)}}\quad\Big{\{}\gamma^{M} \mathbb{E}[T_{M}^{(k)}|{\mathbf{c}}_{M}^{(k)}]+\mathbb{E}\Big{[}\pi(q_{M}^{(k)})| {\mathbf{c}}_{M}^{(k)}\Big{]}+\mathbb{E}[{J^{\prime}}_{M}({\mathbf{c}}_{M}^{(k+1)})|{ \mathbf{c}}_{M}^{(k)}]\Big{\}} \tag{45}\]  
The first and second term in (45) are the cost from the \(k\)-th block; the third term is from the \((k+1)\)-th block. As analyzed in (35), if \(q_{M-1}^{(k+1)}<W\), the number of \(N_{M}^{(k)}\) does not affect the cost. Thus, in this case,  
\[\mathbb{E}[T_{M}^{(k)}|{\mathbf{c}}_{M}^{(k)}]=0 \tag{46}\]  
If \(q_{M-1}^{(k+1)}\geq W\), then \(N_{M}^{(k+1)}=0\).