# BeiDou Short-Message Satellite Resource Allocation Algorithm Based on Deep Reinforcement Learning
## 3 Algorithm Design
### Regional Division Strategy  
The terminal capacity of the GSMS is about 1 million, and the terminal capacity of the RSMS is about 10 million. If the short-message satellites respond to the task requests of each short-message terminal, the calculation time complexity and space complexity will be high. Therefore, before designing the resource allocation algorithm, the system model needs to be optimized to reduce the overall overheads of the resource allocation algorithm. Because the BDS-3 MEO satellites use the Walker 24/3/1 constellation, an area is often covered by multiple short-message satellites. The coverage area is divided into \(v\) subregions according to the type and number of covering satellites, and is recorded as the set \(\mathbf{A^{r}}=\left\{a_{1}^{r},a_{2}^{r},\cdots,a_{v}^{r}\right\}\), where \(a_{i}^{r}\) is the \(i\)-th subregion, and the maximum number of subregions that can be covered by a single short-message satellite is recorded as \(v_{\max}\). The subregion is represented by a tuple, and for \(a_{v}^{r}\), there is:  
\[a_{v}^{r}\triangleq\left\langle C_{v}^{T},S_{v}\right\rangle \tag{24}\]  
where \(C_{v}^{T}\) is the number of short-message terminals included in subregion \(a_{v}^{r}\). \(S_{v}\) is the number of short-message satellites covering subregion \(a_{v}^{r}\). As shown in Figure 4b, the coverage area can be divided into 11 subregions (because the Walker 24/3/1 constellation can achieve global coverage, the uncovered area in the schematic diagram is not discussed). The number of short-message satellites covered by subregions I, III, V, and XI is 1; therefore, the mission request of the short-message terminal in this region can only be responded to by the covered satellite. There are at least two short-message satellites in other subregions, so the optimal response scheme needs to be considered to satisfy Equation (19). By introducing regional division, short-message terminals in a given subregion are regarded as a whole. The short-message satellite only needs to respond to the subregion, and does not need to respond to each short-message terminal separately. Thus, the satellite dynamic allocation problem of computation to the \(10^{6}\)-\(10^{7}\) power can be transformed into computation to the \(10^{2}\)-\(10^{3}\) power. However, the model proposed in the previous section needs to be improved further. The details are as follows. The purpose of regional division is to approximate the number of short-message terminals in the subregion. Therefore, it is necessary to treat the short-message terminals in the subregion as a whole. Firstly, considering the path transmission loss of a short-message terminal in a subregion, the following definition is given. **Definition 4**. : _The regional distance is the average sum of distances of all the short-message terminals in the subregion from the target short-message satellite, i.e.,_  
\[A^{d}_{ij}=\sum_{\chi\in A}d_{\chi j} \tag{25}\]  
where \(A^{d}_{ij}\) is the regional distance from \(a^{r}_{i}\) to \(SAT_{j}\), and \(d_{\chi j}\) is the distance from \(ST_{\chi}\) to \(SAT_{j}\) in \(a^{r}_{i}\). Equation (5) shows that the path transmission loss \(l^{A}_{ij}\) from the short-message terminal in \(a^{r}_{i}\) to \(SAT_{j}\) is:  
\[l^{A}_{ij}=\lambda\left(92.4+20\log f_{c}+20\log A^{d}_{ij}\right) \tag{26}\]  
where \(\lambda\) is the number of \(SAT_{j}\) responding to short-message task requests in \(a^{r}_{i}\) and \(\lambda\in N^{+}\). The path transmission loss matrix \(\widetilde{\mathbf{L}}_{\
u\times n}\) between the elements of set \(\mathbf{SAT}\) and set \(\mathbf{A^{r}}\) can be expressed as shown in Equation (27):  
\[\widetilde{\mathbf{L}}_{\
u\times n}=\left[ \begin{array}{cccc}1^{A}_{11}&1^ {A}_{12}&\cdots&1^{A}_{1m}\\ 1^{A}_{21}&1^{A}_{22}&\cdots&1^{A}_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ 1^{A}_{11}&1^{A}_{22}&\cdots&1^{A}_{vm}\end{array} \right]. \tag{27}\]  
Figure 4: Schematic diagrams of short-message satellite coverage.