# Energy-Efficient Multi-User Routing in a Software-Defined Multi-Hop Wireless Network
## 4 Strategy of Communication Path Selection
### Lagrange Relaxation-Based Aggregated Cost
#### 4.1.1 Problem Formulation  
With the analysis of the problem and the construction of the parameter model, the routing of a single user is described formally as follows:  
\[min\{e(p):p\in P(s,t)\ and\ d(p)\leq\Delta_{delay}\} \tag{6}\]  
The problem is a typical NP-hard problem, and P (s, t) is the set of paths from the source node \(s\) to the destination node \(t\). Unless P = NP, the optimal solution cannot be obtained in polynomial time under the existing constraint. In this case, we can try to get the maximum lower bound of all the solutions and find an approximate solution path that satisfies the constraint. Lagrangian relaxation is a common method to calculate the lower bound, which can be used to find the optimal parameter between two variables. The proportion of energy consumption and delay in the aggregate cost is adjusted on the basis of the residual time, which greatly reduces the difficulty of solving the problem and makes it possible to find the optimal solution in polynomial time after reducing some constraints.  
Therefore, Lagrange relaxation-based aggregated cost (LARAC) is proposed, and this algorithm uses parameter \(\lambda\) to aggregate energy and delay: \(C_{\lambda}\ =c+\lambda\cdot d\). For a given \(\lambda\), we can easily calculate the minimal path \((p_{\lambda})\). If \(\lambda\) = 0 and \(d(p_{\lambda})\leq\Delta_{delay}\), we find an optimal solution for the original problem. If \(d(p_{\lambda})>\Delta_{delay}\), we must increase \(\lambda\), which increases the weight of delay in the aggregate cost and penalizes the infeasibility of the solution. By adjusting \(\lambda\), the time delay is reduced, while the energy consumption is increased until the delay constraint is satisfied. According to the brief analysis of the algorithm, the most vital step to obtain the optimal solution under constraints is to calculate the value of \(\lambda\). Hereby, the next step is to introduce the process of solving \(\lambda\). Above all, the original problem can be described as:  
\[E=min\{e(p):p\in P(s,t)\} \tag{7}\]  
\[s.t.\ d(p)\leq\Delta_{delay} \tag{8}\]  
The main idea of the Lagrangian relaxation algorithm is to build a function with \(\lambda\), which is a parameter for the control constraints of the original problem. Hence, for a given \(\lambda\geq 0\), the Lagrange relaxation of \(\lambda\) is defined as:  
\[L(\lambda)=min\{e(p):p\in P(s,t)\}+\lambda(d(p)-\Delta_{delay}) \tag{9}\]  
Let \(p^{*}\) denote an optimal solution of Formula (6), then we can get Formula (9) \(\leq c(p^{*})\). A feasible solution that satisfies Formula (8) naturally satisfies Formula (9), which indicates that Lagrangian relaxation is the lower bound of the original problem. We need to maximize the function \(L(\lambda)\) by solving the following formula:  
\[L^{*}=max\ L(\lambda) \tag{10}\]  
On account of the fact that solving the dual problem does not necessarily optimally solve the primal problem, we say that there is a duality gap. What we get is the boundary of the solution; this means how far away the optimal solution is. Formula (9) is known as the Lagrangian dual of the original problem, and we can use it to obtain an approximate optimal value, which is the lower limit of the path with the lowest energy consumption under the constraints. The key issue in solving this problem is how to search for the optimal \(\lambda\) and set the appropriate termination conditions.