# Beam-Hopping-Based Resource Allocation in Integrated Satellite-Terrestrial Networks
## 4 Resource Allocation Algorithms for MWSC
### Greedy Suboptimal Algorithm  
The optimal algorithm in Section 4.1 can provide an optimal solution to improve the spectrum efficiency of the ISTN. However, the number of optimization variables increases dramatically with \(N_{sat}\) and \(N_{b}\), which brings obstacles to real-time resource allocation because of the high computational complexity. Therefore, a greedy suboptimal algorithm is proposed to solve P1 with low complexity. To satisfy constraint (15), the resource guarantee factor \(Q\) is defined in the greedy algorithm. The value of \(Q\) is an integer from 0 to \(N_{Iter}\), which implies the priority of resource allocation for the terrestrial systems. If \(Q=0\), the capacity requirements of the terrestrial systems are not considered when the time slots are allocated to the satellite terminals, so the flexibility of resource allocation is maximized. If \(Q=N_{Iter}\), time slots are allocated to all terrestrial BSs in priority to meet the minimum capacity requirements. For a certain value of \(Q\), the main idea of the greedy algorithm can be described as follows. For each time slot in a BH time window, select \(Q\) terrestrial BSs with the maximum remaining capacity requirements and allow them to perform transmission in this time slot. Then, subject to constraints (14) and (16), the time slot is allocated to at most \(N_{b}\) satellite terminals with higher remaining capacity requirements. Finally, whether the remaining terrestrial BSs can perform transmission is determined according to the resource allocation results of the satellite terminals. On the other hand, as mentioned in Section 2.3, the transmission capacity of each satellite terminal is related to the inter-beam CCI. When multiple adjacent satellite terminals are served simultaneously, CCI will significantly degrade the SINR of these satellite terminals. To avoid CCI, an inter-beam distance threshold \(d_{th}^{sat}\) is introduced to ensure isolation among the spot beams. If both the \(i\)-th and \(k\)-th satellite terminals are served in the same time slot, the distance \(d_{i,k}^{sat}\) between them should not be less than \(d_{th}^{sat}\). When \(d_{th}^{sat}\) is large enough, the inter-beam interference power is far less than the noise power \(N_{0}^{sat}\)[23; 24]. Thus, inter-beam CCI can be neglected, and the transmission capacity of the \(i\)-th satellite terminal in each time slot can be expressed as  
\[\varepsilon_{i}^{sat}=x_{i,t}WT_{slot}\log_{2}\Bigg{(}1+\frac{\alpha_{i}^{sat }P_{b}^{sat}}{N_{0}^{sat}}\Bigg{)}. \tag{28}\]  
The above simplification can help further reduce the complexity of solving the resource allocation problem. On this basis, the greedy algorithm for MWSC is summarized in Algorithm 1. At the beginning of the algorithm, the resource guarantee factor \(Q\) is initialized to 0 (line 1). If the minimum required capacity of all the terrestrial systems is achieved after the resource allocation process (lines 2-25), the algorithm terminates (lines 26-28); otherwise, repeat the resource allocation process with \(Q=Q+1\) until \(Q=N_{Iter}\). During the resource allocation process, \(R_{i,re}^{sat}\) and \(R_{jre}^{Iter}\) denote the remaining requested capacity of the \(i\)-th satellite terminal and the remaining required capacity of the \(j\)-th terrestrial system, which are initialized to \(R_{i}^{sat}\) and \(R_{j,min}^{iter}\) (lines 2-3), respectively. For each time slot \(t\in\Gamma\), the resource allocation results can be obtained as follows:  
* Initialize the candidate sets \(\Omega_{s}\) and \(\Omega_{t}\) (lines 5-6). \(\Omega_{s}\) indicates the candidate satellite terminals that can be served in time slot \(t\). The satellite terminals without remaining requested capacity should be removed from \(\Omega_{s}\). \(\Omega_{t}\) indicates the candidate terrestrial BSs that can perform transmission in time slot \(t\), which is initialized to \(\mathcal{N}_{iter}\). * Allocate the time slot \(t\) to at most \(Q\) terrestrial BSs (lines 7-13).