# A Novel Feeder Link Handover Strategy for Backhaul in LEO Satellite Networks
## 4 Problem Analysis and Strategy Design
### Maximum Backhaul Capacity Handover Algorithm  
Based on the handover utility function, we propose a maximum backhaul capacity handover algorithm, as shown in Algorithm 1. The algorithm is divided into two steps: handover decision making and maximum flow calculation.  
(1) Handover decision making: First, the visible satellites of each GS are figured out and added to the visible satellite set. In addition, the remaining service time and handover control factor between each GS and its visible satellites are calculated. The handover decision variables and available satellite capacity are initialized. Then, the handover decisions are looped \(L_{g}M\) times, which is the maximum number of the feeder links. In each loop, the available backhaul capacity is calculated to obtain the handover utility. Then, the \(W_{n,m}(t)\) with maximum value is selected as the handover result in this loop, and the available satellite capacity of all visible satellites is updated.  
(2) Maximum flow calculation: First, the graph must be built for the maximum flow calculation, as shown in Figure 3. The terrestrial network is set as the sink of the graph, since the backhaul traffic would converge to the same terrestrial network. \(M\) edges with infinite capacity are added to the graph to represent the links between GSs and the sink as the red directed arrows show in the figure. In this scenario, the visible satellites can collect backhaul traffic from their USLs or their adjacent invisible satellites by ISLs. These sources are aggregated into a source node to facilitate the computation. \(|\mathbf{V}(t)|\) edges are added between the source and the visible satellites, as the black directed arrows show in the figure. The edge's capacity is the sum capacity of USLs and ISLs connecting with the invisible satellites. In addition, the edges with capacity \(C^{s}\) are added to represent the ISLs between visible satellites. Then, the edges of feeder links are added based on the handover results of Step 1. Finally, the Edmonds-Karp algorithm is used to calculate the maximum flow based on the constructed graph.  
Figure 3: The graph for maximum flow problem.  
```
1:Input: Network Topology, termination time slot \(T\), weights of utility function \(w_{1},w_{2},w_{3}\), parameters of sigmoid function \(\alpha\), \(\beta\).
2:for\(t=0\) to \(T\)do
3:(1) Handover decision:
4: Compute the visible satellites for \(U_{m}\), and put the visible satellites into visible satellite set \(\mathbf{V}(t)\).
5: Compute the remaining service time \(r_{n,m}^{t}(t)\) and the handover control factor \(r_{n,m}^{h}(t)\)between \(U_{m}\) and \(S_{n}\).
6: Initial the available satellite capacity \(C_{i}^{s}(t)=4C^{s}+C^{u}\).
7: Initial the handover decision variables \(x_{n,m}(t)=0\).
8:for\(k=0\) to \(L_{g}M\)do
9:for\(m=1\) to \(M\)do
10:if\(\sum_{n=1}^{N}x_{n,m}(t)<L_{g}\)then
11:for\(S_{n}\) in \(\mathbf{V}(t)\)do
12:if\(\sum_{n=1}^{M}x_{n,m}(t)<L_{s}\)then
13: Compute the normalized value \(r_{n,m}^{b}(t)\) and get the utility \(W_{n,m}(t)\) as Equation (21).
14:endif
15:endfor
16:endif
17:endfor
18: Select the \(W_{n,m}(t)\) with maximum value and let \(x_{n,m}(t)=1\).
19: Update the available satellite capacity for all visible satellites.
20:endfor
21:Output: the handover frequcy \(\sum_{m=1}^{M}\sum_{n=1}^{N}x_{n,m}(t)\).
22:(2) Maximum flow computation:
23: Build graph \(G\) based on the handover decisions and link capacity.
24:while True do
25: Build the augmented graph \(G_{a}\). Compute the path \(p\) from \(s\) to \(d\) with minimum hops.
26:if\(p==\) null then
27:break
28:endif
29: Find the edge with minimum remaining capacity \(f_{min}\) in the path \(p\).
30: Update the flow of all edges in the path.
31:endwhile
32:Output: the maximum flow \(\sum_{m=1}^{M}\sum_{n=1}^{N}x_{n,m}(t)f_{n,m}^{S}(t)\).
33:endfor
```  
**Algorithm 1** Maximum backhaul capacity handover strategy