# Beam-Hopping-Based Resource Allocation in Integrated Satellite-Terrestrial Networks
## 4 Resource Allocation Algorithms for MWSC
### Optimal Algorithm  
At the beginning of the reformulation, all feasible beam allocation patterns that satisfy the constraint (14) should be found. In each time slot, the satellite selects \(n\) satellite terminals (\(0\leq n\leq\min(N_{b},N_{sat})\)) from \(N_{sat}\) satellite terminals to provide services. Thus, the total number of beam allocation patterns is  
\[M_{BAP}=\sum_{n=0}^{\min(N_{b},N_{sat})}{N_{sat}\choose n}. \tag{18}\]  
Form the \(N_{sat}\times M_{BAP}\) beam allocation pattern matrix \(\mathbf{U}\), where the rows of the matrix correspond to the satellite terminal indices and the columns correspond to the beam allocation pattern indices. For the \(m\)-th beam allocation pattern (the \(m\)-th column of \(\mathbf{U}\)), element \(u_{i,m}\in\{0,1\}\) of the \(i\)-th row indicates whether the \(i\)-th satellite terminal is served by a spot beam. If \(u_{i,m}=1\), the \(i\)-th satellite terminal is served when the \(m\)-th beam allocation pattern is applied.  
Corresponding to the beam allocation pattern matrix, the \(N_{ter}\times M_{BAP}\) transmission pattern matrix \(\mathbf{V}\) for the terrestrial systems can be obtained as follows. The rows of the matrix \(\mathbf{V}\) correspond to the terrestrial BS indices, and the columns correspond to the beam allocation pattern indices. For the \(m\)-th beam allocation pattern (the \(m\)-th column of \(\mathbf{V}\)), element \(v_{j,m}\in\{0,1\}\) of the \(j\)-th row indicates whether the \(j\)-th terrestrial BS can perform downlink transmission. Based on the constraint (16), the value of \(v_{j,m}\) is determined as  
\[v_{j,m}=\begin{cases}1,&\text{if }\min_{i\in\Phi_{m}}d_{i,j}^{st}\geq d_{pro}^{ st}\\ 0,&\text{if }\min_{i\in\Phi_{m}}d_{i,j}^{st}<d_{pro}^{st}\end{cases}, \tag{19}\]  
where the set \(\Phi_{m}=\{k\in N_{sat}|u_{k,m}=1\}\) indicates the satellite terminals that are served by the spot beams when the \(m\)-th beam allocation pattern is applied.  
After obtaining matrices \(\mathbf{U}\) and \(\mathbf{V}\), the transmission capacity of the satellite and terrestrial systems associated with each beam allocation pattern can be determined. In each time slot, when the \(m\)-th beam allocation pattern is applied, the capacity of the \(i\)-th satellite terminal is  
\[\tilde{c}_{i,m}^{sat}=u_{i,m}WT_{slot}\log_{2}\left(1+\frac{\alpha_{i}^{sat}P _{b}^{sat}}{N_{0}^{sat}+\sum_{k=1,k\
eq i}^{N_{sat}}u_{k,m}I_{k,i}^{sat}} \right), \tag{20}\]  
and the capacity of the \(j\)-th terrestrial system is  
\[\tilde{c}_{j,m}^{ter}=v_{j,m}c_{j}^{ter}. \tag{21}\]  
Let the non-negative integer \(\mu_{m}\) denote the number of times slots in which the \(m\)-th beam allocation pattern is applied within a BH time window. Then, introduce the auxiliary variables \(\zeta_{i}\), \(\forall i\in\mathcal{N}_{sat}\), which implies the actual capacity of the \(i\)-th satellite terminal. The optimization problem P1 can be reformulated as the following MILP problem.  
\[\text{P1': }\max_{\{\mu_{m}\}}\sum_{i=1}^{N_{sat}}\zeta_{i}+ \gamma\sum_{m=1}^{M_{BAP}}\left(\mu_{m}\sum_{j=1}^{N_{tar}}\tilde{c}_{j,m}^{ter }\right) \tag{22}\] \[\text{s.t. }\zeta_{i}\leq\sum_{m=1}^{M_{BAP}}\mu_{m}\tilde{c}_{i,m}^{ sat}\;\forall i\in\mathcal{N}_{sat}\] (23) \[\zeta_{i}\leq R_{i}^{sat},\forall i\in\mathcal{N}_{sat}\] (24) \[\sum_{m=1}^{M_{BAP}}\mu_{m}\tilde{c}_{j,m}^{ter}\geq R_{j,min}^{ ter}\;\forall j\in\mathcal{N}_{ter}\] (25) \[\sum_{m=1}^{M_{BAP}}\mu_{m}=N_{slot}\] (26) \[\mu_{1},\ldots,\mu_{M_{BAP}}\text{ are non-negative integer}. \tag{27}\]  
Constraints (23) and (24) mean that the value of \(\zeta_{i}\) depends on the minimum value of \(C_{i}^{sat}\) and \(R_{i}^{sat}\). Constraint (25) is equivalent to Constraint (15). Constraint (26) indicates that the sum of the time slot number for each beam allocation pattern should be equal to \(N_{slot}\).  
The optimal solution of the MILP problem P1' can be obtained by classical optimization algorithms, such as the branch-and-bound algorithm [33].