# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 3 Problem Description
### Problem Definition
\[\begin{split}\min\sum_{i=1}^{n}p_{i}^{k_{i}}\\ s.t.\sum_{i=1}^{n}a_{i}k_{i}\leq\Delta\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\[\min \sum_{i=1}^{n}\sum_{j=1}^{u_{i}-l_{i}}C_{i,j}S_{i,j}+p_{i}^{l_{i}} \tag{3}\] \[s.t. \sum_{i=1}^{n}\sum_{j=1}^{u_{i}-l_{i}}a_{i}C_{i,j}+\sum_{i=1}^{n}a_{ i}l_{i}\leq\Delta\] \[C_{i,j}\in\{0,1\},i\in\{1,2,...,n\},j\in\{1,...,u_{i}-l_{i}\}\]  
Lemma 1: _For \(\forall i\in\{1,...,n\}\), the following inequalities hold if \(0<p_{i}<1\) and \(l_{i}<u_{i}\),_  
\[p_{i}^{l_{i}+j}-p_{i}^{l_{i}+j-1}<p_{i}^{l_{i}+j+1}-p_{i}^{l_{i}+j}<0 \tag{4}\]  
_where \(j\in\{1,...,u_{i}-l_{i}\}\)._  
Proof: Let \(g_{i}(x)=p_{i}^{x}\). For any \(i\in\{1,...,n\}\), it is obvious that \(g_{i}(x)\) is a monotone decreasing function; thus, \(p_{i}^{l_{i}+j+1}-p_{i}^{l_{i}+j}<0\). Obviously, \(p_{i}(p_{i}^{l_{i}+j}-p_{i}^{l_{i}+j-1})=(p_{i}^{l_{i}+j+1}-p_{i}^{l_{i}+j})\). Since \(0<p_{i}<1\) and \(p_{i}^{l_{i}+j+1}-p_{i}^{l_{i}+j}<0\), we have \(p_{i}^{l_{i}+j}-p_{i}^{l_{i}+j-1}<p_{i}^{l_{i}+j+1}-p_{i}^{l_{i}+j}\). In conclusion, \(p_{i}^{l_{i}+j}-p_{i}^{l_{i}+j-1}<p_{i}^{l_{i}+j+1}-p_{i}^{l_{i}+j}<0\). Lemma 2: _If \(C_{1,1}^{*},C_{1,2}^{*},...,C_{1,u_{1}-l_{1}}^{*},C_{2,1}^{*},...,C_{n,u_{n}-l _{n}}^{*}\) are the optimal solutions to Equation (3), then there exist \(j_{1},...,j_{n}\), such that:_  
\[C_{i,k}^{*}=\left\{ \begin{array}{cc}1&k\leq j_{i}\\ 0&k>j_{i}\end{array} \right. \tag{5}\]  
_where \(i\in\{1,2,...,n\},k\in\{1,...,u_{i}-l_{i}\}\), \(j_{i}\in\{0,1,...,u_{i}-l_{i}\}\)._  
Proof: The proof is by contradiction. Suppose that \(C_{1,1}^{*},C_{1,2}^{*},...,C_{1,u_{1}-l_{1}}^{*},C_{2,1}^{*},...,C_{n,u_{n}-l _{n}}^{*}\) are the optimal solutions to Equation (3) and that they enable the objective function value to achieve the minimum. For given \(m\), if there is no integer in \(\{0,1,...,u_{m}-l_{m}\}\) such that Equation (5) are true, then there must exist integers \(r,t,q\in\{1,...,u_{m}-l_{m}\}\) such that \(C_{m,r}^{*}=1,C_{m,t}^{*}=0,C_{m,q}^{*}=1\) and \(r<t<q\). We can construct a solution, whose objective function values are less than that of \(C_{1,1}^{*},...,C_{n,u_{n}-l_{n}}^{*}\), by exchanging \(C_{m,t}^{*}\) and \(C_{m,q}^{*}\). Suppose that \(C_{1,1}^{\prime},C_{1,2}^{\prime},...,C_{n,u_{n}-l_{n}}^{\prime}\) are derived by merely exchanging \(C_{m,t}^{*}\) and \(C_{m,q}^{*}\). Firstly, we prove that \(C_{1,1}^{\prime},C_{1,2}^{\prime},...,C_{n,u_{n}-l_{n}}^{\prime}\) are feasible solutions of Equation (3). For any \(i\in\{1,2,...,n\}\) and \(j\in\{1,...,u_{i}-l_{i}\}\), \(C_{i,j}^{*}\) and \(C_{i,j}^{\prime}\) are \(0,1\) variables. It is obvious that \(\sum_{j=1}^{u_{n}-l_{m}}a_{m}C_{m,j}^{*}=\sum_{j=1}^{u_{n}-l_{n}}a_{m}C_{m,j}^{ *}\).