## 5 Heuristic Algorithm Design
### GEO-Free Topology Abstraction-Based Routing Algorithm  
The process of the GEO-free topology abstraction-based routing algorithm (GF-TAR) is detailed in Algorithm 1. This algorithm abstracts the topology of LEO satellites and ground stations for routing, where the LEO is used for QKD and the GEO is used for assisting the transmission of classic signals of the encrypted global keys. Line 1 is used for the initialization of the elements. Under the limitation \(l_{\text{g}}\), we make the LEO satellites establish the quantum channels with several of the closest ground stations in lines 2-11 to produce the max number of secret keys to the QKPs. In this process, we use the First-Fit (FF) algorithm to select the ground stations to be connected, which is efficient and normally used in resource allocation. In lines 12-20, we conduct the similar operation to establish the quantum channels between LEOs under the limitation \(l_{\text{b}}\). The secret keys produced in this time slot \(t_{i}\) are provided to corresponding QKPs in lines 22-24. We update the abstracted topology according to the rest of the key resources on the link in lines 27-32. If the number of keys on the link cannot reach the minimum value of the set of secret keys required for the request \(K_{\text{s}}\), we cut off this link on the abstracted topology until new enough keys are supplied to the QKP on this link. We route for the request on the abstracted topology to obtain the QKD relaying path in line 33. The minimum value of the rest of the key resources on the links along the relaying path is obtained in lines 35-40. In lines 41-47, the comparison between the required key resources and the minimum value of the rest of the key resources on the relaying path is conducted. If the required number of key resources is smaller, we allocate the key resources to implement the request; otherwise, the request fails.  
The time complexity of the GF-TAR algorithm is evaluated as follows. The worst-case time complexities in lines 2-21 and 22-24 are \(O((l_{\text{g}}+l_{\text{b}})\cdot\left|{V_{\text{I}}}\right|)\) and \(O(\left|{V_{\text{g}}\cup V_{\text{I}}}\right|_{2})\), respectively. The time complexity in lines 28-48 is \(O(\left|{V_{\text{g}}\cup V_{\text{I}}}\right|_{2})\). The overall complexity in lines 26-49 is \(O(\left|{R(t_{i})}\right|\cdot\left|{V_{\text{g}}\cup V_{\text{I}}}\right|_{2})\). Hence, the worst-case time complexity of the GF-TAR algorithm in a time slot is \(O(\left|{R(t_{i})}\right|\cdot\left|{V_{\text{g}}\cup V_{\text{I}}}\right|_{2} +(l_{\text{g}}+l_{\text{b}})\cdot\left|{V_{\text{I}}}\right|)\).  
```
1:\(K(t_{i})\), \(R(t_{i})\), \(V_{\text{g}}\), \(V_{\text{I}}\), \(P(t_{i})\) Output:\(SPT(t_{i})\), \(AHT(t_{i})\), \(TKT(t_{i})\), \(P(t_{i+1})\) and solutions for the requests
2: Initialize \(SPT(t_{i})\gets 0\), \(AHT(t_{i})\gets 0\), \(c(m,n,t_{i})\gets 0\), vs. \(\gets V_{\text{g}}\cup V_{\text{I}}\)
3:for\(n\in V_{\text{I}}\)do
4:if\(\sum\limits_{n=\text{C}_{\text{g}}}{(c(m,n,t_{i})>0)}>l_{\text{g}}\)do
5:\(\chi\gets l_{\text{g}}\);
6:else
7:\(\chi\leftarrow\sum\limits_{n=\text{C}_{\text{g}}}{(c(m,n,t_{i})>0)}\) ;
8:endif
9: Find the \(\chi\) largest element in \(v(m,n,t_{i})\), \(m\in V_{\text{g}}\), and record their \(m\) to the set \(\Lambda\);
10:for\(m\in\Lambda\)do
11:\(c(m,n,t_{i})\gets 1\);
```  
**Algorithm 1** GF-TAR algorithm.