## 3 TMDP-Based Resource Allocation Algorithm and Problem Linearization
### Optimization Problem Linearization  
We define a vector variable \(\mathbf{u}_{t}\) that combines the variables \(b_{i,t}^{m,k}\) and \(c_{n,t}\), which can be expressed as  
\[\mathbf{u}_{t}=\left[c_{1,t},\dots,c_{N,t},b_{1,t}^{1,1},\dots,b_{1,t}^{1,K},b_{2, t}^{1,1},\dots,b_{2,t}^{1,K},\dots,b_{1,t}^{1,K},b_{1,t}^{2,1},\dots,b_{1,t}^{M,K}\right] \tag{20}\]  
The length of the variable \(\mathbf{u}_{t}\) is \(N+IKM\), and the elements in \(\mathbf{u}_{t}\) are all binary variables; thus, there are \(2^{N+IKM}\) combinations corresponding to the resource scheduling at the current time slot \(t\). This large number of combinations greatly increases the program complexity and computational time. Therefore, it is necessary to eliminate some of the irrational combinations to mitigate this issue. Due to constraints (10) and (12), most values of \(\mathbf{u}_{t}\) are unavailable. It can be seen that the number of element \"1\" in \(\mathbf{u}_{t}\) should be \(N_{0}+IM\); thus, there are actually \(( \begin{subarray}{c}N+1 KM\\ N_{0}+IM\end{subarray} )\) combinations of variable \(\mathbf{u}_{t}\). By traversing these \(( \begin{subarray}{c}N+1 KM\\ N_{0}+IM\end{subarray} )\) combinations, we find that most of them are still unavailable. Therefore, we only consider the combinations that satisfy constraints (10) and (12). As a result, the effective number of combinations in our proposed scheme is significantly reduced, which can be calculated by  
\[Q=\binom{N}{N_{0}}K^{IM} \tag{21}\]  
Then, we define an auxiliary binary variable \(\omega_{t}^{q}\in\{0,1\}\), where \(q\in\mathcal{Q}=\{1,2,3,\ldots Q\}\). The variable \(\omega_{t}^{q}\) represents the satellite beam-hopping scheduling decision and UE transmitting decision at time slot \(t\). For instance, if \(\omega_{t}^{q}=1\), it represents the value of \(\mathbf{u}_{t}\) corresponds to the \(q\)-th combination, which is selected from all the \(Q\) combinations. Obviously, the satellite scheduling decision and UE transmitting decision at time slot \(t\) are unique, which can be expressed as  
\[\sum_{q\in\mathcal{Q}}\omega_{t}^{q}=1 \tag{22}\]  
At time slot \(t\), the value of \(\mathbf{u}_{t}\) is uniquely determined for any \(q\in\mathcal{Q}\), and its corresponding variables \(b_{i,t}^{m,k}\) and \(c_{n,t}\) are also uniquely determined as \(b_{i,t,q}^{m,k}\) and \(c_{n,t,q}\). Therefore, the communication rate of UE \(i\) at time slot \(t\) and scheduling decision \(q\) can be expressed as  
\[\rho_{i,t}^{q}=\sum_{m\in\mathcal{M}}\frac{B}{M}\text{log}_{2}\left(1+\frac{ \sum\limits_{n\in\mathcal{N}}h_{i,n}c_{n,t,q}\sum\limits_{k\in\mathcal{K}}b_{i,t,q}^{m,k}P_{k}}{\sum\limits_{i^{\prime}\in\mathcal{I},i^{\prime}\
eq i}\sum \limits_{n\in\mathcal{N}}h_{i^{\prime},n}c_{n,t,q}\sum\limits_{k\in\mathcal{K} }b_{i^{\prime},t,q}^{m,k}P_{k}+\sigma^{2}}\right) \tag{23}\]  
Similarly, the communication rate of CUE \(j\) at time slot \(t\) and scheduling decision \(q\) can be expressed as  
\[\psi_{j,t}^{q}=\sum_{m\in\mathcal{M}}\frac{B}{M}\text{log}_{2}\left(1+\frac{ \sum\limits_{n\in\mathcal{N}}h_{j,n}c_{n,t,q}\sum\limits_{k\in\mathcal{K}}b_{ j,t,q}^{m,k}P_{k}}{\sum\limits_{j^{\prime}\in\mathcal{I},i^{\prime}\
eq i}\sum \limits_{n\in\mathcal{N}}h_{j,n}c_{n,t,q}\sum\limits_{k\in\mathcal{K}}b_{j,t, q}^{m,k}P_{k}+\sigma^{2}}\right) \tag{24}\]  
We denote \(\chi_{t}^{q}\) as  
\[\chi_{t}^{q}=\sum_{m\in\mathcal{M}}\frac{\sum\limits_{i\in\mathcal{I},i\
otin \mathcal{J}}\sum\limits_{k\in\mathcal{K}}h_{e,j}b_{i,t,q}^{m,k}P_{k}}{\sum \limits_{i\in\mathcal{I}\
eq i,\
otin\mathcal{J}}\sum\limits_{k\in\mathcal{K} }h_{e,j}b_{i,t,q}^{m,k}P_{k}+\sigma_{\epsilon}^{2}} \tag{25}\]  
These above parameters \(\rho_{i,t}^{q}\), \(\psi_{j,t}^{q}\) and \(\chi_{t}^{q}\) can be calculated by traversing all the \(Q\) combinations one by one; thus, they are constants in the optimization problem.