# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 4 Dynamic Programming-Based Distributed Algorithm for Optimal Retransmission Thresholds  
As analyzed in Section 3.2, the problem of finding optimal retransmission thresholds is equivalent to the _0-1 Knapsack Problem_. Thus, it can be solved by a dynamic programming-based pseudo-polynomial time algorithm [29]. In this section, we first prove the correctness of the dynamic programming-based algorithm, which can output the optimal resolutions to Equation (3). We design a dynamic programming-based algorithm to solve the proposed _0-1 Knapsack Problem_, and then, according to Theorem 3, the optimal retransmission thresholds can be derived based on the resolutions to Equation (3). **Theorem 5**. : _If \(C_{1,1}^{\prime},C_{1,2}^{\prime},...,C_{n,u_{n}-l_{n}}^{\prime}\) are the optimal solutions to Equation (3), then \(C_{1,2}^{\prime},...,C_{n,u_{n}-l_{n}}^{\prime}\) are the optimal solutions to the following problem._  
\[ \begin{split}&\min\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{u_{i}-l_{i}} C_{i,j}S_{i,j}+p_{i}^{l_{i}}+\sum\limits_{j=2}^{u_{1}-l_{1}}C_{1,j}S_{1,j}+p_{1}^{ l_{1}}\\ & s.t.\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{u_{i}-l_{i}}a_{i}C_ {i,j}+\sum\limits_{j=2}^{u_{1}-l_{1}}a_{1}C_{1,j}+\sum\limits_{i=1}^{n}a_{i}l_ {i}\leq\Delta-a_{1}C_{1,1}^{\prime}\\ &\quad\quad\quad C_{i,j}\in\{0,1\},j\in\{1,...,u_{i}-l_{i}\},i\in \{1,2,...,n\}\end{split}  \tag{8}\]  
Proof. : The proof is by contradiction. If \(C_{1,2}^{\prime},...,C_{n,u_{n}-l_{n}}^{\prime}\) are not optimal solutions to Equation (8), suppose that \(Z_{1,2}^{\prime},...,Z_{n,u_{n}-l_{n}}^{\prime}\) are the optimal solutions of Equation (8). Then, \(C_{1,1}^{\prime},Z_{1,2}^{\prime},...,Z_{n,u_{n}-l_{n}}^{\prime}\) are batter solutions of Equation (3), which leads to a contradiction. The proof demonstrates the correctness of the dynamic programming-based algorithm. To briefly describe the recursive procedure, based on Lemma 2, the following mappings are introduced,  
\[ \begin{split}& f:\text{N}\times\text{N}\rightarrow\text{N},f(i,j)= \sum\limits_{m=0}^{i-1}(u_{m}-l_{m})+j\\ & g:\text{N}\rightarrow\text{N},g(h)=\min\left\{i|h-\sum\limits _{m=0}^{i}(u_{m}-l_{m})\leq 0,i\geq 1\right\}\end{split} \]  
where \(u_{0}=l_{0}=0\). Let \(C_{i,j}=C_{f(i,j)},S_{i,j}=S_{f(i,j)}\) and \(sum=\sum_{m=1}^{n}(u_{m}-l_{m})\), then Equation (3) is equivalent to the following knapsack problem. \[ \begin{split}&\min\sum\limits_{h=1}^{sum}C_{h}S_{h}+\sum\limits _{i=1}^{n}p_{i}^{l_{i}}\\ & s.t.\sum\limits_{h=1}^{sum}a_{g(h)}C_{h}+\sum\limits_{i=1}^{n}a_ {i}l_{i}\leq\Delta\\ &\quad\quad\quad C_{h}\in\{0,1\},h\in\{1,2,...,sum\}\end{split}  \tag{9}\]  
When the object set is \(\{S_{h},S_{h+1},...,S_{sum}\}\) and the capacity is bounded by \(j\), we use \(m(h,j)\) to express the minimum cost. Then, we derive the recursive equation of \(m(h,j)\). \[m(h,j)= \begin{cases}m(h+1,j),&0\leq j-\sum_{h=1}^{n}a_{h}l_{h}<a_{g(h)}\\ \min\left\{m(h+1,j),m(h+1,j-a_{g(h)})+S_{h}\right\},&j-\sum_{h=1}^{n}a_{h}l_ {h}\geq a_{g(h)}\end{cases} \]  
Additionally, the initial conditions are as follows. \[m(sum,j)= \begin{cases}0&0\leq j-\sum_{h=1}^{n}a_{h}l_{h}<a_{n}\\ S_{sum}&j-\sum_{h=1}^{n}a_{h}l_{h}\geq a_{n}\end{cases} \]  
Suppose that node \(j_{i}\) needs to forward a packet with delivery delay \(\Delta^{\prime}\) and that the end-to-end path is \(j_{i},j_{i+1},...,j_{n}\). Since the packet is the first one queued at node \(j_{i}\), \(a_{i}=1\). Therefore, finding the optimal retransmission threshold \(k_{i}\) for the packet over link from \(j_{i}\) to \(j_{i+1}\) is equivalent to solving the following integer optimization problem. \[\min \sum_{v=i}^{n}p_{v}^{k_{v}} \tag{10}\] \[s.t. \sum_{v=i+1}^{n}a_{v}k_{v}+k_{i}\leq\Delta^{\prime}\] \[l_{v}\leq k_{v}\leq u_{v},k_{v}\in Z,v\in\{i,i+1,...,n\}\]  
According to Theorem 3, the above Equation (10) is equivalent to the following knapsack Equation (11).