# Energy-Efficient Multi-User Routing in a Software-Defined Multi-Hop Wireless Network
## 4 Strategy of Communication Path Selection
### K-LARAC Algorithm for Multiple Shortest Paths under Constraints  
In order to get the alternative path set for each user, we combine the LARAC algorithm with K-Dijkstra to develop the K-LARAC algorithm to obtain the top \(K\) energy-minimum paths that can meet the delay constraints between nodes.  
As is known to all, multi-path induction is an extension of the shortest path problem, which can generate corresponding subgraphs by deleting edges. The K-shortest-paths algorithm of [PERSON] can be called recursively to find \(K\) paths from the origin to the sink. In addition, the method based on the first \(K-1\) shortest paths and its adjacent points is also feasible. However, these algorithms do not utilize the information of shortest paths between the starting point and the ending point, so the efficiency of searching \(K\) paths is low. In this paper, edges in the shortest path are deleted successively, and then, the LARAC algorithm is called to get the paths to meet the requirements.  
The algorithm for solving K-shortest-paths with constraints between two points is composed of the following steps:  
* Use the LARAC algorithm to find the shortest path from the starting point \((SourceVertex)\) to the ending point \((DestinationVertex)\), and this path is denoted as the first short path (FSP). Then, the number of nodes in the path is calculated as \(n=length(FSP)\), which shows that the number of edges in the shortest path is \(n-1\).
* Delete the last edge in the shortest path, that is set \(Energy(P(n-1),P(n))=inf\). Then, the LARAC algorithm is called again to find the new shortest path that meets the delay constraint. If the path exists, it is saved and recorded as \(ksp_{i}\); where \(Energy\) is a two-dimensional matrix storing the energy consumption model to record the current network topology and \(ksp_{i}\) represents the a sub-optimal path \(i\).
* Delete the second-to-last edge in the shortest path, that is set \(Energy(P(n-2),P(n-1))=inf\), and do the same as above to find the new shortest path. If the path exists, we save it.
* By analogy, until the first edge is deleted, \((n-1)\) paths that satisfy the delay constraint can be obtained.
* The paths are sorted in accordance with the energy consumption value from small to large, and the top \(K\) paths are selected as the alternative paths between the node pairs.  
At this point, we have the K-shortest paths of a user. Next, the K-LARAC algorithm is used to find the alternative path sets for \(M\) users, that is \(M\) alternative path sets can be obtained. The alternative path set of user \(i\) can be represented as follows:  
\[S_{i}=\{p_{i}^{1},p_{i}^{2},\ldots,p_{i}^{K}\}\ \ \ i=1,2,\ldots,M \tag{12}\]  
where \(p_{i}^{1}\), \(p_{i}^{2}\), and \(p_{i}^{K}\) all meet the constraint \(D_{i}\) of user \(i\), and the corresponding energy consumption values of these paths are from small to large. Since our purpose is to solve the global routing strategy of minimum energy consumption for multiple users, the next step is to choose one path from each user's alternative path set to form a routing scheme that cannot only achieve the minimum energy consumption, but also ensure that there are no repeated nodes in each path.