# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 5 Linear Programming-Based Approximation Algorithm
### Mathematical Foundations
For any \(i\in\{1,2,...,n\}\), let \(z_{i}^{\prime}=\sum_{j=0}^{u_{i}-l_{i}}\lambda_{i,j}^{\prime}(l_{i}+j)\). Thus, \(z_{1}^{\prime},z_{2}^{\prime},...,z_{n}^{\prime}\) are the optimal solutions to Equation (12) according to the proof of Theorem 8. To obtain the feasible solutions of integer optimization Equation (2), rounding optimal fractional solutions is a natural idea [29]. The following theorem guarantees that the ratio bound of the rounding approach is \(1+p_{min}\), where \(p_{min}\) is the minimum of the probabilities of one transmission failure along the given end-to-end path. **Theorem 9**. : _For any \(i\in\{1,2,...,n\}\), the ratio bound of the rounding approach is \(1+p_{\min}\), if \(\left\lfloor z_{i}^{\prime}\right\rfloor\geq\frac{\ln p_{\min}}{\ln p_{i}}\), where \(p_{\min}=\min\{p_{1},p_{2},...,p_{n}\}\)._

Proof. : Suppose that \(z_{1}^{\prime},z_{2}^{\prime},...,z_{n}^{\prime}\) are the optimal solutions to Equation (12), which are derived from the optimal solutions of linear programming Equation (13). Denote \(k_{1}^{\prime},k_{2}^{\prime},...,k_{n}^{\prime}\) as the optimal solutions to Equation (1). From Theorem 7, the approximation ratio \(r\) satisfies the following formula. \[r=\frac{\sum\limits_{i=1}^{n}1-p_{i}^{k_{i}^{\prime}}}{\sum\limits_{i=1}^{n}1-p_ {i}^{\left\lfloor z_{i}^{\prime}\right\rfloor}}=\frac{n-\sum\limits_{i=1}^{n}p_ {i}^{k_{i}^{\prime}}}{n-\sum\limits_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{\prime }\right\rfloor}}\leq\frac{n-\sum\limits_{i=1}^{n}f_{i}(z_{i}^{\prime})}{n-\sum \limits_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{\prime}\right\rfloor}} \tag{16}\]

According to the proof of Theorem 8, for any \(i\in\{1,2,...,n\}\), there must exist integer \(j_{i}\) in \(\{0,1,...,u_{i}-l_{i}-1\}\), such that \(z_{i}^{\prime}\in[l_{i}+j_{i},l_{i}+j_{i}+1]\). Based on the convexity of \(p_{i}^{x}\), we know that:

\[f_{i}(z_{i}^{\prime})=(1+l_{i}+h-z_{i}^{\prime})p_{i}^{l_{i}+h}+(z_{i}^{\prime }-l_{i}-h)p_{i}^{l_{i}+h+1}\geq p_{i}^{z_{i}^{\prime}}\]

Let \(p_{\min}=\min\{p_{1},p_{2},..,p_{n}\}\); we have:

\[n-\sum\limits_{i=1}^{n}f_{i}(z_{i}^{\prime})\leq n-\sum\limits_{i=1}^{n}p_{i}^{z_ {i}^{\prime}}<n-\sum\limits_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{\prime}\right\rfloor +1}\leq n-p_{\min}\sum\limits_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{\prime}\right\rfloor}\]Additionally, then, the approximation ratio \(r\) satisfies the following formula:

\[r<\frac{n-p_{\min}\sum_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{\prime} \right\rfloor}}{n-\sum_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{\prime}\right\rfloor} }=\frac{n-np_{\min}+np_{\min}-p_{\min}\sum_{i=1}^{n}p_{i}^{\left\lfloor z_{i }^{\prime}\right\rfloor}}{n-\sum_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{\prime} \right\rfloor}} \tag{17}\] \[=\frac{n-np_{\min}+p_{\min}\left(n-\sum_{i=1}^{n}p_{i}^{\left\lfloor z _{i}^{\prime}\right\rfloor}\right)}{n-\sum_{i=1}^{n}p_{i}^{\left\lfloor z_{i }^{\prime}\right\rfloor}}\] \[=\frac{n-\sum_{i=1}^{n}p_{\min}}{n-\sum_{i=1}^{n}p_{i}^{\left\lfloor z _{i}^{\prime}\right\rfloor}}+p_{\min}\]

For any \(i\in\{1,2,...,n\}\), since \(\left\lfloor z_{i}^{\prime}\right\rfloor\geq\frac{\ln p_{\min}}{\ln p_{i}}\), \(p_{i}^{\left\lfloor z_{i}^{\prime}\right\rfloor}\leq p_{\min}\) and \(\frac{n-\sum_{i=1}^{n}p_{\min}}{n-\sum_{i=1}^{n}p_{i}^{\left\lfloor z_{i}^{ \prime}\right\rfloor}}<1\). In conclusion, the ratio bound is \(1+p_{\min}\). The link properties vary as a result of environmental conditions changing at a longer timescale [6; 15], then the difference of failure transmission probability among links is little. Thus, the premises of Theorem 9 are always satisfied in practical sensor networks. Since the objective function value of Equation (12) is decreasing with respect to \(z_{i}\), its optimum value can be achieved if and only if \(\sum_{i=1}^{n}a_{i}z_{i}=\Delta\). For a general linear programming problem, finding optimal solutions incurs high computational overhead. However, it can be efficiently solved if the problem is to optimize a linear function subject to linear equality constraints [30].