# Energy-Efficient Multi-User Routing in a Software-Defined Multi-Hop Wireless Network
## 4 Strategy of Communication Path Selection
### Combinatorial Optimization Based on the Genetic Algorithm  
With the increment of the scale of the problem, the search space of the combinatorial optimization problem increases sharply. Sometimes, it is difficult to find the optimal solution by the enumeration method. For this reason, people use the genetic algorithm to solve these complex problems, in order to find a satisfactory solution instead of the optimal solution. This paper assumes that the intermediate nodes do not repeatedly provide service for multiple users, in other words, which is the constraint in the combinatorial optimization problem. Therefore, we choose the heuristic genetic algorithm to obtain the routing that meets the conditions and introduce the constraint as penalty into the fitness calculation. On the one hand, the heuristic genetic algorithm can automatically acquire and accumulate knowledge about search space in the search process, and self-adaptively control the search process to obtain the optimal solution. On the other hand, this algorithm does not require continuity or differentiability for objective functions or constraints, as long as the problem is computable. According to the analysis of the combinatorial optimization problem, the problem belongs to integer programming. Therefore, compared with the particle swarm optimization algorithm, the heuristic genetic algorithm is more suitable for our needs. According to the analysis, the genetic algorithm can be used to optimize the combination of alternative path sets for a large number of users, which is in line with practical application scenarios. The algorithm mainly contains the following concepts [28]. Genes and chromosomes: In the process of solving a practical problem, the first step is to build a mathematical model, that is we map the origin problem to a mathematical problem. The possible solution of the problem is a \"chromosome\", which consists of several elements, and each of them is called a \"gene\" of a chromosome. In this experiment, each chromosome is composed of \(M\) genes, which correspond to \(M\) users. By setting different values for each gene, the path in the user's alternative path set is selected for combination. To this end, we describe the problem as follows:  
\[min\{c(p_{1}^{i})+c(p_{2}^{j})+\cdots+c(p_{M}^{l})\}\ \ i,j,l=1,2,\cdots,K \tag{13}\]  
\[s.t.\ \ V_{i}\
eq V_{j},\ \forall\ V_{i},V_{j}\in p_{1}^{i},p_{2}^{j}\cdots,p_{M}^{ l} \tag{14}\]  
where \(K\) represents the number of paths in each user's alternative path set and \(i\), \(j\), and \(l\) are the superscripts to the paths in this set. The fitness function is used to measure the quality of a chromosome, namely whether the corresponding solution of the chromosome matches the search criteria. The algorithm carries out \(n\) iterations in the running process, and each iteration will generate a number of chromosomes. Then, we use the fitness function to calculate the fitness of each chromosome, eliminate the chromosome with low fitness, and keep the chromosome with high fitness for the next iteration. Since the routing requires no repeat nodes of paths, the fitness function can be divided into two parts: the total cost and the penalty for the infeasible solution. The total cost can be calculated by the energy consumption. Firstly, the energy consumption of the \(k\)th routing scheme can be expressed as follows:  
\[v_{k}=c^{k}(p_{1}^{i})+c^{k}(p_{2}^{j})+\cdots+c^{k}(p_{M}^{l})\ \ i,j,l=1,2, \cdots,K \tag{15}\]  
Then, the cost of the routing scheme \(v_{k}\) is:  
\[f(v_{k})=v_{k} \tag{16}\]  
For the penalty of the infeasible solution, it should be related to the number of repeated nodes. Let the number of repeated nodes in the combined path be \(m\), then the penalty item can be recorded as \(g_{k}\) and calculated as follows:  
\[g_{k}=\left\{ \begin{array}{rl}a,\ m=0\\ m*n,\ m\
eq 0\end{array} \right. \tag{17}\]  
where \(n\) represents the evolution algebra and \(a\) is a constant.