# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 5 Linear Programming-Based Approximation Algorithm
### Mathematical Foundations  
According to \(p_{i},l_{i}\) and \(u_{i}\), piecewise linear function \(f_{i}(z)\) is defined as follows, where \(h\in\{0,1,...,u_{i}-l_{i}-1\}\). We use an example to illustrate the defined function, as depicted in Figure 2.  
\[f_{i}(z)= \begin{cases}(z-l_{i}\text{-}h)(p_{i}^{l_{i}+h+1}-p_{i}^{l_{i}+h})+p_ {i}^{l_{i}+h},&z\in(l_{i}+h,l_{i}+h+1)\\ p_{i}^{z},&z\in\{l_{i},l_{i}+1,...,u_{i}\}\end{cases} \]  
**Lemma 6**. : _For any \(i\in\{1,2,...,n\}\), \(f_{i}(z)\) is a convex function._```
Input:\(U_{i-1},L_{i-1},T=\{T_{i},T_{i+1},...,T_{n}\}\),for\(h=i,i+1,...,n;k_{i}=0\) \(T_{h}=<p_{h},A_{h},L_{h},U_{h}>\), \(Int=\sum_{h=1}^{i-1}u_{h}-l_{h}\), \(sum=\sum_{h=i}^{n}u_{h}-l_{h}\) Output: optimal retransmission threshold of \(j_{i}\). for\(h=i\) to \(n\)do \(a_{h}=A_{h}+1,l_{h}=L_{h}+1,u_{h}=U_{h}+1\); for\(h=i\) to \(n\)do for\(k=1\) to \(u_{h}-l_{h}\)do \(e=f(h,k)\); \(S_{e}=p_{h}^{l_{h}+k}-p_{h}^{l_{h}+k-1}\); \(Low=\sum_{h=i}^{n}a_{h}l_{h}\); for\(j=0\) to \(\min(a_{n}-1,\Delta^{\prime}-Low)\)do \(m(sum,j)=0\) for\(j=a_{n}\) to \(\Delta^{\prime}-Low\)do \(m(sum,j)=S_{sum}\) for\(h=sum-1\) to \(Int+1\)do for\(j=0\) to \(\min(a_{g(h)}-1,\Delta^{\prime}-Low)\)do \(m(h,j)=m(h+1,j)\) for\(j=a_{g(h)}\) to \(\Delta^{\prime}-Low\)do \(m(h,j)=\min(m(h+1,j),m(h+1,j-a_{g(i)})+S_{h})\) if\(\Delta^{\prime}-Low<a_{i}\)then \(m(Int+1,\Delta^{\prime}-Low)=m(Int+2,\Delta^{\prime}-Low)\); else \(min=\min(m(Int+2,\Delta^{\prime}-Low),m(Int+2,\Delta^{\prime}-Low-a_{i})+S_{Int+1})\) \(m(Int,\Delta^{\prime}-Low)=min\); for\(h=Int+1\) to \(Int+u_{i}-l_{i}\)do if\(m\left(h,\Delta^{\prime}-\sum_{k=Int+1}^{h-1}a_{i}C_{k}\right)\)then \(=m\left(h+1,\Delta^{\prime}-\sum_{k=Int+1}^{h-1}a_{i}C_{k}\right)\)then \(C_{Int+1}=0\); else \(C_{Int+1}=1,k_{i}=k_{i}+C_{Int+1}\); return\(k_{i}-1\);
```

**Algorithm 1**Dynamic Programming-based Distributed Algorithm for the optimal retransmission threshold (DPDA). Figure 2: Example of a piecewise linear function. Proof. : For any \(i\), since \(f_{i}(z)\) is a piecewise linear function, \(f_{i}^{\prime\prime}(z)=0\), where \(z\in(l_{i}+h,l_{i}+h+1)\) and \(h\in\{0,1,...,u_{i}-l_{i}-1\}\). Thus, \(f_{i}(z)\) satisfies the sufficient condition of convexity function if \(z\in(l_{i}+h,l_{i}+h+1)\). Now, we prove that \(f_{i}(z)\) is a convex function if \(z\in\{l_{i},l_{i}+1,...,u_{i}\}\). Suppose that \(z=\sum_{h=1}^{n}\lambda_{h}z_{h}\), where \(z\in\{l_{i},l_{i}+1,...,u_{i}\},\lambda_{1},...,\lambda_{n}\in[0,1],z_{1},..., z_{n}\in[l_{i},u_{i}]\) and \(\sum_{h=1}^{n}\lambda_{h}=1\). Since \((p_{i}^{x})^{\prime\prime}>0\), \(p_{i}^{x}\) is a convex function. Thus, \(p_{i}^{z}\leq\sum_{h=1}^{n}\lambda_{h}p_{i}^{z_{h}}\). For any \(z_{h}\), there must exist \(j_{h}\in\{0,1,...,u_{i}-l_{i}-1\}\), such that \(z_{h}\in[l_{i}+j_{h},l_{i}+j_{h}+1]\). From the definition of \(f_{i}(z)\), \(f_{i}(z_{h})=(z_{h}-l_{i}-j_{h})(p_{i}^{l_{i}+j_{h}+1}-p_{i}^{l_{i}+j_{h}})+p_{ i}^{l_{i}+j_{h}}\). Let \(b_{i,z_{h}}^{\prime}=1+l_{i}+j_{h}-z_{h},b_{i,z_{h}}^{\prime\prime}=z_{h}-l_{i }-j_{h}\), we have \(f_{i}(z_{h})=b_{i,z_{h}}^{\prime}p_{i}^{l_{i}+j_{h}}+b_{i,z_{h}}^{\prime\prime }p_{i}^{l_{i}+j_{h}+1}\), \(b_{i,z_{h}}^{\prime},b_{i,z_{h}}^{\prime\prime}\in[0,1]\) and \(b_{i,z_{h}}^{\prime}+b_{i,z_{h}}^{\prime\prime}=1\). Since \(z_{h}=b_{i,z_{h}}^{\prime}(l_{i}+j_{h})+b_{i,z_{h}}^{\prime\prime}(l_{i}+j_{h} +1)\), then \(p_{i}^{z_{h}}\leq f_{i}(z_{h})\) according to the convexity of \(p_{i}^{x}\). Based on the above analysis, it can be derived that \(p_{i}^{z}\leq\sum\limits_{h=1}^{n}\lambda_{h}p_{i}^{z_{h}}\leq\sum\limits_{h=1 }^{n}\lambda_{h}f_{i}(z_{h})\). In conclusion, for any \(i\in\{1,2,...,n\}\), \(f_{i}(z)\) is a convex function. According to the constraints of Equation (2), a general optimization problem can be formulated as follows. \[ \begin{split}&\min\sum\limits_{i=1}^{n}f_{i}(z_{i})\\ & s.t.\sum\limits_{i=1}^{n}a_{i}z_{i}\leq\Delta\\ &\quad l_{i}\leq z_{i}\leq u_{i},i\in\{1,2,...,n\}\end{split}  \tag{12}\]

**Theorem 7**.