# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 5 Linear Programming-Based Approximation Algorithm
The linear programming-based distributed approximation algorithm running at each sensor node is described in Algorithm 2, which is derived from the convex programming algorithm in [30]. \(f_{h}^{L}(x)\) and \(f_{h}^{R}(x)\) are the left and right derivative of \(f_{h}(x)\), respectively. The proposed algorithm in [30] can yield optimal solutions for the piecewise linear convex function. For any \(i\in\{1,2,...,n\}\), the derivative of \(f_{i}(x)\) is discontinuous and constant. According to the proposed algorithm [30], the termination condition can be satisfied when the optimal retransmission threshold is not \(L_{i}\) or \(U_{i}\). The maximum number for iteration rounds can be assigned in advance. The algorithm can also be stopped if the convergence condition is not achieved. Therefore, figuring out the retransmission threshold of node \(j_{i}\) can be achieved. ## 6 Lagrange Multiplier-Based Distributed \(O(1)\)-Approximation Algorithm

In practical sensor networks, the optimal retransmission thresholds hardly hit the given upper or lower bounds. Therefore, we aim at finding the optimal retransmission thresholds when the ranges of the upper and lower bounds of the retransmission thresholds are big enough. In Section 6.1, we formalize the problem as an integer optimization problem and provide a mathematical method for finding the approximate solution of the problem. Then, a Lagrange multiplier-based distributed \(O(1)\)-approximation algorithm with time complexity \(O(1)\) is provided. ### Mathematical Foundations

Compared to integer optimization Equation (1), the problem of optimal retransmission thresholds in the case that the ranges of the upper and lower bounds of retransmission thresholds are big enough can be formulated as follows, which implies that the optimization problem has no interval constraints of retransmission thresholds. ```
Input:\(t=\infty,T=\{T_{i},T_{i+1},...,T_{n}\},\) \(T_{h}=<p_{h},A_{h},L_{h},U_{h}>\) for \(h=i,...,n\) Output: 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\); \(s_{i}=f(x_{i1})-f(x_{i1}+1),\pi_{1}=s_{i}/a_{i}\); for\(h=i+1\) to \(n\)do if\(h=t\)then \(t_{h}=f(x_{h1})-s_{h}x_{h1}\); else \(s_{h}=s_{i},t_{h}=f(x_{h1})-s_{h}x_{h1}\); \(Low=\sum\limits_{h=i}^{n}a_{h}l_{h}\); for\(h=i+1\) to \(n\)do if\(s_{h}<f_{h}^{R}(l_{h})\)then \(x_{h}^{\prime}=l_{h}\); elseif\(s_{h}\geq f_{h}^{R}(l_{h})\)then \(x_{h}^{\prime}=u_{h}\); else for\(k=l_{h}+1\) to \(u_{h}-1\)do if\(f_{h}^{L}(k)\leq s_{h}\leq f_{h}^{R}(k)\)then \(x_{h}^{\prime}=k\) ;  break; \(y_{h}^{\prime}=f_{h}(x_{h}^{\prime})-s_{i}x_{h}^{\prime},t_{h}=f_{h}(x_{h1})- s_{h}x_{h1}\) ; \(Min=y_{i+1}^{\prime}-t_{i+1}\) for\(h=i+1\) to \(n-1\)do if\(Min\geq y_{h+1}^{\prime}-t_{h+1}\)then \(Min=y_{h+1}^{\prime}-t_{h+1},temp=h+1\); if\(Min=0\)then return\([x_{i1}]\); else if\(x_{i1}\) hits the lower bound \(l_{i}\) or the upper bound \(u_{i}\)then return\(x_{i1}-1\) and stop; else  According to the convex programming algorithm [30], adjust \(x_{i1}\) and \(x_{t}\) ; \[\max \sum\limits_{i=1}^{n}\left(1-p_{i}^{k_{i}}\right)\] \[s.t. \sum\limits_{i=1}^{n}a_{i}k_{i}\leq\Delta\] (18) \[\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}\]0  
The following lemma provides a mathematical method to figure out the optimal solutions of Equation (18) in the real number field; that is for any \(i\), \(k_{i}\) is a real number. Lemma 10 is the foundation for the rounding technique. **Lemma 10**. : _Let \(\Lambda=\sum_{i=1}^{n}\left(1-p_{i}^{x_{i}}\right)+\omega\left(\sum_{i=1}^{n}a_{i} x_{i}-\Delta\right)\).