# Energy-Efficient Multi-User Routing in a Software-Defined Multi-Hop Wireless Network
## 5 Experimental Results and Evaluation
### Time Complexity Analysis  
Dijkstra is a typical shortest path algorithm, and the complexity of simple Dijkstra is \(O(n^{2})\). When solving the single source shortest path in the non-negative weight topology, the running speed outperforms Bellman-Ford (BF), Floyd, and shortest path faster algorithm (SPFA). So do the stability issues. Therefore, we chose LARAC based on Dijkstra as the main algorithm to ensure low time complexity. The simulation in this section is to verify the time complexity of the proposed algorithm in solving multi-user routing problems. For this purpose, we provide three experiments for comparison:  
* The proposed algorithm, which combines K-LARAC with the genetic algorithm for path searching, called KLG.
* The K-LARAC algorithm and the full combination algorithm are used to compare the performance of the genetic algorithm.
* The delay-constrained Bellman-Ford (DCBF) algorithm based on Bellman-Ford and the genetic algorithm are used to verify the advantage of K-LARAC.  
Since the DCBF algorithm needs to compare all the paths that are not larger than the upper limit of delay, we retain the paths that meet the conditions in the search process and rank them from small to large according to energy consumption. By adjusting the number of users, we observe the changes of execution time when they are dealt with by the three methods respectively. Suppose the number of user devices \(M=10\) and target devices \(T=10\), several intermediate transmission devices, and the number of alternative paths per user \(K=3\). In order to ensure the experimental results, we simulated 100 times for each input size, and the results are shown in Figure 3.  
By comparing the above experimental results, we know that the full combination can get the optimal solution, but with the increase of the number of users, the time overhead will increase exponentially. At the same time, the processing speed of KLG is also better than the combination of DCBF and the genetic algorithm. This is due to the fact that the average computing time of the genetic algorithm to find the optimal solution does not exceed the square of the scale of the problem, and the full combination needs to traverse \(K^{M}\) solutions. Specifically, we know that the complexity of the Lagrangian relaxation method is \(O(m^{m}\ log^{4}m)\) from [29], where \(m\) denotes the number of edges. Let the average number of edges in FSP be \(q\). Then, finding the K-shortest-paths is by deleting the edges, and the LARAC algorithm is used \(q\) times, so the time complexity of K-LARAC is \(O(qm^{2}\ log^{4}m)\). The time complexity of getting the alternative path set of \(M\) users by K-LARAC is \(O(Mqm^{2}\ log^{4}m)\). Meanwhile, the average computing time of GA is no more than \(O(n^{2})\), where \(n\) refers to the scale of the problem, and it is related to the number of users \(M\). Therefore, the time complexity of the KLG algorithm is \(O(Mqm^{2}\ log^{4}m+n^{2})\), that is the simplified form is \(O(Mm^{2}\ log^{4}m)\). For the DCLC problem, LARAC processes adjacent nodes step by step from the source point, while constrained Bellman-Ford (CBF) always starts from the source point and has repetitive operations. As you can see, the LARAC algorithm is more efficient and does not repeat processing nodes. Therefore, through cross-validation, we observe that the KLG algorithm can complete the path combination in a relatively short time. Next, we need to verify the accuracy of the algorithm.