# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 5 Linear Programming-Based Approximation Algorithm
### Mathematical Foundations
: _The objective function value of Equation (12) is a lower bound of that of Equation (2), which implies that a feasible solution can be derived based on the optimal resolutions of Equation (12)._

Proof. : Suppose that \(k_{1}^{\prime},k_{2}^{\prime},...,k_{n}^{\prime}\) are the optimal solutions to Equation (2). For any \(i\in\{1,2,...,n\}\), let \(x_{i}^{\prime}=k_{i}^{\prime}\). Thus, \(x_{1}^{\prime},x_{2}^{\prime},...,x_{n}^{\prime}\) are feasible solutions to Equation (12), and hence:

\[\min\sum\limits_{i=1}^{n}p_{i}^{k_{i}}=\sum\limits_{i=1}^{n}p_{i}^{k_{i}^{ \prime}}=\sum\limits_{i=1}^{n}f_{i}(x_{i}^{\prime})\geq\min\sum\limits_{i=1}^{n }f_{i}(z_{i})\]

Therefore, the objective function value of Equation (12) is a lower bound of that of Equation (2). **Theorem 8**. : _The proposed optimization Equation (12) is equivalent to the following linear programming problem, and then, the general optimization Equation (12) can be solved by the linear programming technique._

\[ \begin{split}&\min\sum\limits_{i=1}^{n}\sum\limits_{j=0}^{u_{i}-l_{i }}\lambda_{i,j}p_{i}^{l_{i}+j}\\ & s.t.\sum\limits_{i=1}^{n}a_{i}\sum\limits_{j=0}^{u_{i}-l_{i}} \lambda_{i,j}(l_{i}+j)\leq\Delta\\ &\quad\sum\limits_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}=1,0\leq \lambda_{i,j}\leq 1,\\ &\quad j\in\{0,...,u_{i}-l_{i}\},i\in\{1,2,...,n\}\end{split}  \tag{13}\]

Proof. : For any \(i\in\{1,2,...,n\}\), we have \(l_{i}\leq\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}(l_{i}+j)\leq u_{i}\). It is easily known that for any \(z_{i}\in[l_{i},u_{i}]\), there exist \(\lambda_{i,0},...,\lambda_{i,u_{i}-l_{i}}\in[0,1]\), such that \(z_{i}=\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}(l_{i}+j)\) and \(\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}=1\)Additionally, similarly for any \(\lambda_{i,0},...,\lambda_{i,u_{i}-l_{i}}\in[0,1]\), if \(\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}=1\), there must exist \(z_{i}\in[l_{i},u_{i}]\), such that \(z_{i}=\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}(l_{i}+j)\). Suppose that \(\lambda_{1,0},\lambda_{1,1},...,\lambda_{2,0},...,\lambda_{n,u_{n}-l_{n}}\) are feasible solutions of Equation (13). For any \(i\in\{1,2,...,n\}\), let \(z_{i}=\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}(l_{i}+j)\). Thus, \(z_{1},...,z_{n}\) are feasible solutions of Equation (12). According to the convexity of \(f_{i}(z)\), we have \(f_{i}(z_{i})\leq\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}f_{i}(l_{i}+j)=\sum_{j=0} ^{u_{i}-l_{i}}\lambda_{i,j}p_{i}^{l_{i}+j}\), and hence:

\[\min\sum_{i=1}^{n}f_{i}(z_{i})\leq\min\sum_{i=1}^{n}\sum_{j=0}^{u_{i}-l_{i}} \lambda_{i,j}p_{i}^{l_{i}+j} \tag{14}\]

Suppose that \(z_{1}^{\prime},....,z_{n}^{\prime}\) are the optimal solutions to Equation (12); there must exist \(n\) integers \(j_{1},....,j_{n}\), such that \(z_{i}^{\prime}\in[l_{i}+j_{i},l_{i}+j_{i}+1]\). For any \(i\in\{1,2,...,n\}\), let \(\lambda_{i,j_{i}}^{\prime}=1+l_{i}+j_{i}-z_{i},\lambda_{i,j_{i}+1}^{\prime}=z _{i}^{\prime}-l_{i}-j_{i}\), and the others \(\lambda_{i,j}^{\prime}\)s are zero. Obviously, \(\lambda_{1,0}^{\prime},\lambda_{1,1}^{\prime},...,\lambda_{n,u_{n}-l_{n}}^{ \prime}\) are feasible solutions of Equation (13). Based on the definition of \(f_{i}(x)\), \(f_{i}(z_{i}^{\prime})=(z_{i}^{\prime}-l_{i}-j_{i})(p_{i}^{l_{i}+j_{i}+1}-p_{i }^{l_{i}+j_{i}})+p_{i}^{l_{i}+j_{i}}=\lambda_{i,j_{i}}^{\prime}p_{i}^{l_{i}+j_ {i}}+\lambda_{i,j_{i}+1}^{\prime}p_{i}^{l_{i}+j_{i}+1}=\sum_{j=0}^{u_{i}-l_{i} }\lambda_{i,j}^{\prime}p_{i}^{l_{i}+j}\). Thus, we can have the following formula. \[\min\sum_{i=1}^{n}\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}p_{i}^{l_{i}+j}\leq\sum _{i=1}^{n}\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}^{\prime}p_{i}^{l_{i}+j}=\sum_ {i=1}^{n}f_{i}(z_{i}^{\prime})=\min\sum_{i=1}^{n}f_{i}(z_{i}) \tag{15}\]

In conclusion, optimization Equation (12) is equivalent to linear programming Equation (13). ### Linear Programming-Based Approximation Algorithm

Suppose that \(\lambda_{1,0}^{\prime},\lambda_{1,1}^{\prime},...,\lambda_{n,u_{n}-l_{n}}^{ \prime}\) are the optimal solutions to Equation (13).