## 3 The Proposed Algorithm
### Markov Decision Process for the Dynamic Channel Allocation Process  
In this paper, the channel status and the call event formed the environment in the channel allocation problem. The transition of the environmental state had the Markov property. The whole channel allocation process was described as per the following MDP model to dynamically adapt to the environmental changes.  
**State \(S\)**: \(s_{t}=(X_{t},e_{t})\) represents the environmental state at time \(t\). \(X_{t}\) is the channel status of the LEO satellite network at time \(t\) and \(e_{t}\) is the call event for the admission service to the terminal users at time \(t\). They are expressed, respectively, by:  
Figure 1: The mobility model of the users.  
\[X_{t}=\begin{bmatrix}x_{t}(1,\,1)&x_{t}(1,\,2)&x_{t}(1,\,3)&\ldots&x_{t}(1,\,k)& \ldots&x_{t}(1,K)\\ x_{t}(2,\,1)&x_{t}(2,\,2)&x_{t}(2,\,,\,,\,,\,3)&\ldots&x_{t}(2,\,k)&\ldots&x_{t}(2,K )\\ \ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\ x_{t}(n,\,1)&x_{t}(n,\,2)&x_{t}(n,3)&\ldots&x_{t}(n,\,k)&\ldots&x_{t}(n,K)\\ x_{t}(N,1)&x_{t}(N,2)&x_{t}(N,3)&\ldots&x_{t}(N,\,k)&\ldots&x_{t}(N,K)\\ \end{bmatrix} \tag{5}\]  
\[e_{t}\,\in\left\{e_{n,t}^{new}\,,\,e_{n,m,k,t}^{handoff}\,,\,e_{n,k,t}^{end}\,\right\} \tag{6}\]  
where \(x_{t}(n,\,k)=0\) represents that channel \(k\) of cell \(n\) is idle at time \(t\) and \(x_{t}(n,\,k)=1\) represents that this channel is occupied. \(e_{n,t}^{new}\) represents a new call event in cell \(n\) at time \(t\). \(e_{n,m,k,t}^{handoff}\) represents that the handoff call event on channel \(k\) in cell \(n\) will hand over to the adjacent cell \(m\) at time \(t\) according to its temporal-spatial correlation. \(e_{n,k,t}^{end}\) represents that the departure call event on channel \(k\) in cell \(n\) occurs at time \(t\).  
**Action \(A\)**: to accept or reject the call event. If a new call arrives, a channel should be occupied. If the call departs, a channel should be free. If the call hands over, the related new call and the departure call should be handled. In this paper, the actions of different call events were expressed by:  
\[A((x_{t},e_{t}))=\left\{\begin{aligned} (n),\,e_{t}=e_{n,t}^{new}\\ \{l\in\text{K},x_{t}(n,l)=1\},\,e_{t}=e_{n,k,t}^{end}\\ A\Big{(}\Big{(}x_{t},e_{n,k,t}^{end}\Big{)}\Big{)}\cup A\big{(} \big{(}x_{t+1},e_{n,t}^{new}\big{)}\,\,e_{t}=e_{n,m,k,t}^{handoff}\end{aligned}\right. \tag{7}\]  
**Immediate reward \(R\)**: the reward obtained from the environment after performing action \(a_{t}\) in the current state \(s_{t}\). In this paper, the immediate reward referred to the total number of calls served in the current network. It was expressed by:  
\[R_{t}=(s_{t},\,\,)\,\,\,\sum_{n=1}^{N}\sum_{k=1}^{K}x_{t+1}\,\,(n,\,k) \tag{8}\]  
where \(x_{t+1}(n,k)\) represents the transformed status of channel \(k\) in cell \(n\) after performing action \(a_{t}\).  
**Policy \(\pi\)**: the mapping from an environmental state to the performed action. The performed action in the current state corresponds with the selected channel for the current call. The relationship between action, state and policy is expressed by:  
\[\text{a}_{t}=\pi(\text{s}_{t}=(\text{X}_{t},\,\text{e}_{t})) \tag{9}\]