## 4 The Optimal Relay Nodes Placement with Respect to Minimum Overall Power Usage
### Solution to OPT-1
\begin{array}{l}\sum\limits_{i=0}^{n}d_{i}-L=0\\ d_{i}-R\leq 0\\ -d_{i}\leq 0\\ \lambda_{1i}(-d_{i})=0\\ \lambda_{2i}(d_{i}-R)=0\\ \lambda_{1i}\geq 0\\ \lambda_{2i}\geq 0\\ \tilde{e}(\Phi_{2}f\sum\limits_{i=0}^{n}d_{i}^{k}+\sum\limits_{i=0}^{n} \lambda_{1i}(-d_{i})+\sum\limits_{i=0}^{n}\lambda_{2i}(d_{i}-R)+v(\sum \limits_{i=0}^{n}d_{i}-L))\\ \tilde{e}d_{i}\end{array} \right.=0 \tag{8}\]  
After solving this set of equations, we can draw the conclusion that,  
\[d_{0}=d_{1}=\cdots=d_{n}=\frac{L}{n+1} \tag{9}\]  
which means that relay nodes must be put at the equal partition points between two sensor nodes to get the minimum overall energy consumption, since the first term of the objective function of OPT-1 is constant given the value of \(n\). The next step is to decide how many relay nodes should be installed. Since relay nodes should be placed at the equal partition points, the optimization problem OPT-1 can be rewritten as the following optimization problem, denoted as OPT-3,  
\[\min (n+1)(\Phi_{1}+\rho)f+\Phi_{2}f\frac{L^{k}}{(n+1)^{k-1}}\] s.t. \[n\text{ is an integer}\]  
The variable \(n\) of this optimization problem must have an integer value. However, we can first take the unconstrained problem into consideration, _i.e.,_  
\[\min (n_{c}+1)(\Phi_{1}+\rho)f+\Phi_{2}f\frac{L^{k}}{(n_{c}+1)^{k-1}}\]By calculating the second derivative of the objective function, we could find out that this function is strict convex when \(n_{c}\) is greater than zero. Therefore, this problem can be solved by calculating the stationary points of the objective function, _i.e._, if any stationary point exists when \(n\) is greater than zero, it also must be the minimum point. In order to calculate the stationary point, we first calculate the first derivative of the objective function. We have:  
\[ \begin{array}{rcl}&\partial((n_{c}+1)(\Phi_{1}+\rho)f+\Phi_{2}f \frac{L^{k}}{(n_{c}+1)^{k-1}})/\partial n_{c}\\ =&(\Phi_{1}+\rho)f-(k-1)\Phi_{2}f\frac{L^{k}}{(n_{c}+1)^{k}}\end{array}  \tag{10}\]  
Therefore,  
\[n_{c}=L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1 \tag{11}\]  
From the property of convex functions, we have the following conclusions:  
* If \(L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1\) is an integer and \(L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1\geq\lfloor\frac{L}{R}\rfloor\), then \(n=L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1\);
* If \(L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1>\lfloor\frac{L}{R}\rfloor\), but \(L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1\) is not endowed with an integer value, then the value of \(n\) is chosen from \(\lfloor L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1\rfloor\) and \(\lceil L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1\rceil\);
* If \(L(\frac{(k-1)\Phi_{2}}{\Phi_{1}+\rho})^{1/k}-1<\lfloor\frac{L}{R}\rfloor\), then the value of \(n\) is \(\lfloor\frac{L}{R}\rfloor\). Next, the correctness of solving OPT-1 via the given procedure can be validated by contradiction. Assume that the value \(n\) and the relay nodes' placement is not optimal, _i.e._, there exist another value \(n^{\prime}\) and a relay nodes' placement method that lead to a smaller objective value of OPT-1. However, for a given \(n^{\prime}\), due to the result of OPT-2, the objective function can only be minimized by placing relay nodes at the equal partition points. Then, OPT-1 is transformed into OPT-3. Since the value of n is obtained by solving OPT-3, the objective function value must be smaller than that acquired by \(n^{\prime}\), which causes the contradiction. Therefore, the optimality of OPT-1 can be ensured when following the given solution procedure.