# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 5 Linear Programming-Based Approximation Algorithm
### Lagrange Multiplier-Based Distributed O(1)-Approximation Algorithm  
The computation of the logarithm is undesired to execute on the sensor node; the log values needed can be stored on the sensor node in advance. For example, three arrays \(a[99],b[99]\) and \(c[99]\) are forwarded to the sensor node at first, where \(a[h]=\ln h,b[h]=\ln(0.01h),c[h]=\ln\left(-(\ln 0.01h)^{-1}\right)\) and \(h\in\{1,2,...,99\}\). Then, the log values needed by Equation (22) are stored in the sensor node. The proposed Lagrange multiplier-based distributed approximation algorithm is described in Algorithm 3. It is easily known that the computation cost is \(O(n)\), where \(n\) is the number of hops from the source node to the destination node. Since the number of sensor nodes along the given end-to-end delivery path is no more than a few dozen, hence the computation complexity of the algorithm is \(O(1)\). ```
Input:\(T=\{T_{i},T_{i+1},...,T_{n}\},T_{h}=<p_{h},A_{h}>\), for\(h\in\{i,i+1,...,n\},\) \(\Delta,a[99],b[99],c[99],S_{1}=0,S_{2}=0\) Output: retransmission threshold of node \(j_{i}\). for\(h=i\) to \(n\)do \(a_{h}=A_{h}+1,p_{h}=100p_{h}\); for\(h=i\) to \(n\)do \(S_{1}=S_{1}+a_{h}\left(\frac{a[a_{h}]+c[p_{h}]}{b[p_{h}]}\right),S_{2}=S_{2}+ \frac{a_{h}}{b[p_{h}]}\); \(x_{i}=\frac{\Delta-S_{1}}{b[p_{h}]S_{2}}+\frac{a[a_{h}]+c[p_{h}]}{b[p_{h}]}\). return\(\lfloor x_{i}\rfloor-1\);
```  
**Algorithm 3**Lagrange Multiplier-based Distributed Approximation Algorithm for the retransmission threshold (LMDAA). Similarly to the linear programming-based approximation algorithm, approximate solutions to integer optimization Equation (18) can be derived by rounding the optimal fractional solutions. The following theorem guarantees that the ratio bound of the rounding approach is \(1+p_{min}\). Due to \(0<p_{min}<1\), the ratio bound of the Lagrange multiplier-based approximation algorithm is two. **Theorem 12**: _Suppose that \(x_{1}^{\prime},x_{2}^{\prime},...,x_{n}^{\prime}\) are the optimal solutions to Equation (19), then \(\left\lfloor x_{1}^{\prime}\right\rfloor,...,\left\lfloor x_{n}^{\prime}\right\rfloor\) are the feasible solutions to Equation (18). The ratio bound is \(1+p_{min}\), if for any \(i\in\{1,2,...,n\}\), \(\left\lfloor x_{i}^{\prime}\right\rfloor\geq\frac{\ln p_{\min}}{\ln p_{i}}\), where \(p_{\min}=\min\{p_{1},p_{2},...,p_{n}\}\)._  
Proof. : Since \(x_{1}^{\prime},x_{2}^{\prime},...,x_{n}^{\prime}\) are the optimal solutions to Equation (19), \(\sum_{i=1}^{n}a_{i}x_{i}^{\prime}=\Delta\), and hence, \(\sum_{i=1}^{n}a_{i}\left\lfloor x_{i}^{\prime}\right\rfloor\leq\Delta\). Thus, \(\left\lfloor x_{1}^{\prime}\right\rfloor,...,\left\lfloor x_{n}^{\prime}\right\rfloor\) are the feasible solutions to Equation (18). Suppose that \(k_{1}^{\prime},k_{2}^{\prime},...,k_{n}^{\prime}\) are the optimal solutions to Equation (18). Obviously, the objective function value of Equation (19) is an upper bound of that of Equation (18). Thus, the following inequalities can be derived. \[\sum_{i=1}^{n}\left(1-p_{i}^{k_{1}^{\prime}}\right)\leq\sum_{i=1}^{n}\left(1 -p_{i}^{x_{i}^{\prime}}\right)<\sum_{i=1}^{n}\left(1-p_{i}^{\left\lfloor x_{i }^{\prime}\right\rfloor+1}\right)\]  
Let \(p_{\min}=\min\{p_{1},p_{2},...,p_{n}\}\).