# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 3 Problem Description
### Problem Definition
According to the construction of the solution, \(C_{i,j}^{*}\) and \(C_{i,j}^{\prime}\) are identical correspondingly, except for \(C_{m,t}^{*}\) and \(C_{m,q}^{*}\). Since \(\sum_{i=1}^{u_{i}-l_{i}}a_{i}C_{i,j}^{*}+\sum_{i=1}^{u_{i}}a_{i}l_{i}\leq\Delta\), we have \(\sum_{i=1}^{u_{i}-l_{i}}a_{i}C_{i,j}^{*}+\sum_{i=1}^{u_{i}}a_{i}l_{i}\leq\Delta\). Thus, \(C_{1,1}^{\prime},C_{1,2}^{\prime},...,C_{n,u_{n}-l_{n}}^{\prime}\) are feasible solutions. Let \(\varepsilon=\sum_{i=1}^{u_{i}-l_{i}}C_{i,j}^{*}S_{i,j}+p_{i}^{l_{i}}-\sum_{i=1 }^{u_{i}-l_{i}}\sum_{j=1}^{u_{i}-l_{i}}C_{i,j}^{\prime}S_{i,j}+p_{i}^{l_{i}}\) be the difference between the values of the two objective functions. It is easily derived that \(\varepsilon=\sum_{j=1}^{u_{n}-l_{m}}C_{m,j}^{*}S_{m,j}-\sum_{j=1}^{u_{n}-l_{m} }C_{m,j}^{\prime}S_{m,j}=S_{m,q}-S_{m,t}\). From Lemma 1, we know \(\varepsilon>0\). Then, \(C_{1,1}^{\prime},...,C_{n,u_{n}-l_{n}}^{\prime}\) are more optimal solutions, and it contradicts the fact that \(C_{1,1}^{*},...,C_{n,u_{n}-l_{n}}^{*}\) are the optimal solutions. Theorem 3: _Suppose that \(C_{1,1}^{*},...,C_{n,u_{n}-l_{n}}^{*}\) are the optimal solutions to Equation (3). For any \(i\in\{1,2,...,n\}\), let \(k_{i}^{*}=\sum_{j=1}^{u_{i}-l_{i}}C_{i,j}^{*}+l_{i}\). Then, \(k_{1}^{*},...,k_{n}^{*}\) are the optimal solutions to Equation (2), and the values of the two objective functions are identical. **Proof. ** Suppose that \(k^{\prime}_{1},...,k^{\prime}_{n}\) are the optimal solutions of Equation (2), then we can construct feasible solutions \(C^{\prime}_{1,1},...,C^{\prime}_{n,u_{n}-l_{n}}\) to Equation (3) as following, where \(i\in\{1,2,...,n\},j\in\{1,...,u_{i}-l_{i}\}\). \[C^{\prime}_{i,j}=\left\{ \begin{array}{ll}1&j\leq k^{\prime}_{i}-l_{i}\\ 0&j>k^{\prime}_{i}-l\end{array} \right. \tag{6}\]  
It can be known that \(\sum_{i=1}^{n}\sum_{j=1}^{u_{i}-l_{i}}a_{i}C^{\prime}_{i,j}+\sum_{i=1}^{n}a_{i }l_{i}=\sum_{i=1}^{n}\sum_{j=1}^{k^{\prime}_{i}-l_{i}}a_{i}C^{\prime}_{i,j}+ \sum_{i=1}^{n}a_{i}l_{i}=\sum_{i=1}^{n}a_{i}l_{i}=\sum_{i=1}^{n}a_{i}k^{\prime }_{i}\). Since \(\sum_{i=1}^{n}a_{i}k^{\prime}_{i}\leq\Delta\), \(C^{\prime}_{1,1},...,C^{\prime}_{n,u_{n}-l_{n}}\) are the feasible solutions to Equation (3). Based on the definition of \(S_{ij}\), it can be derived that \(\sum_{i=1}^{n}p_{i}^{l_{i}+l_{i}^{-}l_{i}}=\sum_{i=1}^{n}\sum_{j=1}^{k^{\prime }_{i}-l_{i}}S_{i,j}+p_{i}^{l_{i}}=\sum_{i=1}^{n}\sum_{j=1}^{k^{\prime}_{i}-l_{ i}}C^{\prime}_{i,j}S_{ij}+p_{i}^{l_{i}}=\sum_{i=1}^{n}\sum_{j=1}^{u_{i}-l_{i}}C^{ \prime}_{i,j}S_{ij}+p_{i}^{l_{i}}\). Thus, the following inequality can be derived. \[\min\sum_{i=1}^{n}p_{i}^{k_{i}}=\sum_{i=1}^{n}p_{i}^{k^{\prime}_{i}}=\sum_{i=1 }^{n}\sum_{j=1}^{u_{i}-l_{i}}C^{\prime}_{i,j}S_{i,j}+p_{i}^{l_{i}}\geq\min\sum_ {i=1}^{n}\sum_{j=1}^{u_{i}-l_{i}}C_{i,j}S_{ij}+p_{i}^{l_{i}}\]  
Therefore, the objective function value of Equation (3) is a lower bound of that of Equation (2). Since \(C^{*}_{n,u_{n}-l_{n}}\) are the optimal solutions of Equation (3), there exist \(j_{1},...,j_{n}\), such that Equation (5) hold according to Lemma 2. For any \(i\), \(\sum_{j=1}^{u_{i}-l_{i}}C^{*}_{i,j}=\sum_{j=1}^{j_{i}}C^{*}_{i,j}=j_{i}\) from Equation (5), then \(\sum_{j=1}^{u_{i}-l_{i}}C^{*}_{i,j}S_{ij}+p_{i}^{l_{i}}=\sum_{j=1}^{j_{i}}S_{ ij}+p_{i}^{l_{i}}=p_{i}^{l_{i}+i}\). Since \(k^{*}_{i}=\sum_{j=1}^{u_{i}-l_{i}}C^{*}_{i,j}+l_{i}=j_{i}+l_{i}\), we have \(\sum_{i=1}^{u}\sum_{j=1}^{u_{i}-l_{i}}a_{i}C^{*}_{i,j}+\sum_{i=1}^{n}a_{i}l_{i }=\sum_{i=1}^{u}\sum_{j=1}^{j_{i}}a_{i}C^{*}_{i,j}+\sum_{i=1}^{n}a_{i}l_{i}= \sum_{i=1}^{n}a_{i}l_{i}=\sum_{i=1}^{u}a_{i}(l_{i}+j_{i})=\sum_{i=1}^{n}a_{i}k^ {*}_{i}\). Since \(C^{*}_{1,1},...,C^{*}_{n,u_{n}-l_{n}}\) satisfy all of the constraints of Equation (3), \(\sum_{i=1}^{n}a_{i}k^{*}_{i}\leq\Delta\). For any \(i\), it is obvious that \(0\leq j_{i}\leq u_{i}-l_{i}\).