# Beam-Hopping-Based Resource Allocation in Integrated Satellite-Terrestrial Networks
## 4 Resource Allocation Algorithms for MWSC
### Greedy Suboptimal Algorithm
While the number of selected terrestrial BSs is less than \(Q\) and the maximum \(R_{jre}^{Iter}\) of the candidate terrestrial BSs is greater than 0, the time slot \(t\) is allocated to the terrestrial BS \(j^{*}\in\Omega_{t}\) with the maximum \(R_{j,re}^{Iter}\) in each iteration. Then, \(R_{j,re}^{Iter}\) is updated, and the terrestrial BS \(j^{*}\) is removed from \(\Omega_{t}\). To avoid inter-system CCI, \(\Omega_{s}\) is updated based on the inter-system protection distance \(d_{pro}^{st}\). * Allocate the time slot \(t\) to at most \(N_{b}\) satellite terminals (lines 14-20). While \(\Omega_{s}\) is not empty and the number of served satellite terminals is less than \(N_{b}\), the time slot \(t\) is allocated to the satellite terminal \(i^{*}\in\Omega_{s}\) with the maximum \(R_{i,re}^{sat}\) in each iteration. Then, \(R_{i^{*},re}^{sat}\) is updated. To avoid inter-beam CCI and inter-system CCI, \(\Omega_{s}\) and \(\Omega_{t}\) are updated based on \(d_{th}^{sat}\) and \(d_{pro}^{st}\), respectively. * Allocate the time slot \(t\) to the remaining terrestrial BSs in \(\Omega_{t}\) (lines 21-24) since they are outside the protection zones of the served satellite terminals. Repeat the above process until all time slots are allocated, and then decide whether the algorithm can terminate. ```
1:\(\{R_{i}^{sat}\}\), \(\{R_{j,min}^{ter}\}\), \(\{\tilde{c}_{i}^{sat}\}\), \(\{c_{j}^{ter}\}\), \(\{d_{i,j}^{st}\}\), \(\{d_{i,k}^{sat}\}\), \(\forall i,k\in\mathcal{N}_{sat},j\in\mathcal{N}_{ter}\)
2:\(\{x_{i,t}\}\), \(\{y_{i,t}\}\), \(\forall i\in\mathcal{N}_{sat},j\in\mathcal{N}_{ter},t\in\Gamma\)
3:for each \(Q=0,\cdots,N_{ter}\)do
4:\(x_{i,t}\gets 0,R_{i,re}^{sat}\gets R_{i,re}^{sat}\), \(\forall i\in\mathcal{N}_{sat},t\in\Gamma\)
5:\(y_{j,t}\gets 0,R_{jre}^{ter}\gets R_{j,re}^{ter}\), \(\forall j\in\mathcal{N}_{ter},t\in\Gamma\)
6:for each \(t\in\Gamma\)do
7:\(\Omega_{s}\leftarrow\{i\in\mathcal{N}_{sat}|R_{i,re}^{sat}>0\}\)
8:\(\Omega_{t}\leftarrow\mathcal{N}_{(re}\)
9:while\(\sum_{j=1}^{N_{iter}}y_{j,t}<Q\) and \(\max_{j\in\Omega_{t}}\{R_{jre}^{ter}\}>0\)do
10:\(j^{*}\leftarrow\operatorname*{argmax}_{i\in\Omega_{t}}\{R_{jre}^{ter}\}\)
11:\(y_{j^{*},t}\gets 1\)
12:\(R_{jre}^{ter}\gets R_{j^{*},re}^{iter}-c_{j}^{ter}\)
13:\(\Omega_{t}\leftarrow\Omega_{t}-\{j^{*}\}\)
14:\(\Omega_{s}\leftarrow\{i\in\Omega_{s}|d_{i,j}^{st}\geq d_{pro}^{st}\}\)
15:endwhile
16:while\(\Omega_{s}\
eq\emptyset\) and \(\sum_{i=1}^{N_{sat}}x_{i,t}<N_{b}\)do
17:\(i^{*}\leftarrow\operatorname*{argmax}_{i\in\Omega_{s}}\{R_{i,re}^{sat}\}\)
18:\(x_{i^{*},t}\gets 1\)
19:\(R_{i^{*},re}^{sat}\gets R_{i^{*},re}^{sat}-\tilde{c}_{i}^{st}\)
20:\(\Omega_{s}\leftarrow\{k\in\Omega_{s}|d_{i^{*},k}^{sat}\geq d_{th}^{sat}\}\)
21:\(\Omega_{t}\leftarrow\{j\in\Omega_{t}|d_{i^{*},j}^{st}\geq d_{pro}^{st}\}\)
22:endwhile
23:for each \(j\in\Omega_{t}\)do
24:\(y_{j,t}\gets 1\)
25:\(R_{jre}^{ter}\gets R_{jre}^{ter}-c_{j}^{ter}\)
26:endfor
27:endfor
28:if\(\max_{j\in\mathcal{N}_{Iter}}\{R_{jre}^{ter}\}\leq 0\)then
29: break
30:endif
31:endfor
```  
**Algorithm 1** Greedy algorithm for MWSC. The computational complexity of the greedy algorithm for MWSC mainly depends on the number of operations in calculating the transmission capacity of the satellite terminals and the terrestrial systems, as well as the number of operations in updating the candidate sets based on the inter-system and inter-beam distance thresholds. Specifically, it requires \(\mathcal{O}(N_{sat})\) operations to calculate \(c_{i}^{sat}\) for all satellite terminals and \(\mathcal{O}(N_{ter})\) operations to calculate \(c_{j}^{ter}\) for all terrestrial systems before the resource allocation. In the main body of the algorithm, there are at most \(N_{ter}+1\) resource allocation processes since \(Q\) is an integer from 0 to \(N_{ter}\).