# Matching-Based Resource Allocation for Satellite-Ground Network
## 3 System Model
### Three-Sided Cyclic Matching Algorithm  
We added two restrictions from TMSC to form R-TMSC. Every GEO satellite has a user preference list that is derived from a master list. It is arranged in descending order based on the priority of the user. Users who demand lower delay will pay more and enjoy greater favor with GEO satellites. The preference list of all GEO satellites comes from the main list. In our example, the identical preference list \(PL_{k}^{g}\) is generated by all GEO satellites. (We assume that every GEO satellite can serve every user.) \[PL_{k,t,i}^{g}=\varepsilon_{i,t} \tag{19}\]  
On the other hand, according to the service quality measured by delay \(T_{i,j,t}^{ul}\) (generate an acceptable set by Formula (3)), this ranks acceptable LEO satellites. Therefore, the user selects the LEO satellite according to the reciprocal of the expected delay. We represent the user's preference list \(PL_{i}^{u}\) as:  
\[PL_{i,j,t}^{u}=1/T_{i,j,t}^{ul} \tag{20}\]  
According to the previous subsection, the GEO satellite is independent of the LEO satellite. That is to say, each LEO satellite's preference list \(PL_{j}^{l}\) contains a constraint, and the ranking of all LEO satellites is the same, which can be expressed as:  
\[PL_{j,k,t}^{l}=1 \tag{21}\]  
Before proposing our algorithm, the following notations are defined. \[\Pi^{+1}\big{(}\Sigma^{t},\ g_{k}^{t}\big{)}=\left\{u_{i}^{t}|u_{i}^{t} \succ_{g_{k}^{t}}\Sigma^{t}\big{(}g_{k}^{t}\big{)},u_{i}^{t}\in PL_{k,t}^{g}\right\} \tag{22}\]represents the set of users that \(g_{k}^{t}\) prefers over its current matching partner \(\Sigma^{t}\big{(}\,g_{k}^{t}\big{)}\). \[\Pi^{+1}\big{(}\Sigma^{t},\ u_{i}^{t}\big{)}=\Big{\{}\,l_{j}^{t}\Big{|}l_{j}^{t} \succ_{u_{i}^{t}}\Sigma^{t}\big{(}u_{i}^{t}\big{)},l_{j}^{t}\in PL_{i,t}^{u} \Big{\}} \tag{23}\]  
means the LEO satellite set that \(u_{i}^{t}\) prefers to its present matching partner \(\Sigma^{t}(u_{i})\). \[\Pi^{-1}\big{(}\Sigma^{t},\ g_{k}^{t}\big{)}=\Big{\{}\,l_{j}^{t}\Big{|}l_{j}^{ t}\in L_{t},g_{k}^{t}\in PL_{j,t}^{S},\ \mathcal{N}\big{(}\Sigma^{t},\ l_{j}^{t}\big{)}<N_{L}\Big{\}} \tag{24}\]  
represents the LEO satellite set that still has capacity for GEO satellite \(g_{k}^{t}\). \[\Pi^{-2}\big{(}\Sigma^{t},\ g_{k}^{t}\big{)}=\Big{\{}\,u_{i}^{t}\big{|}\ \ \Pi^{+1}\big{(}\Sigma^{t},\ u_{i}^{t}\big{)}\cap\Pi^{-1}\big{(}\Sigma^{t},\ g_{k}^{t} \big{)}\
eq\varnothing,u_{i}^{t}\in\mathcal{U}^{t}\Big{\}} \tag{25}\]  
indicates the user set, where a LEO satellite \(l_{j}^{t}\) is preferred by \(u_{i}^{t}\) above its current partner \(\Sigma^{t}\big{(}u_{i}^{t}\big{)}\), and \(l_{j}^{t}\) is also capable of matching with \(g_{k}^{t}\). According to above definitions, we propose Algorithm 1. Our algorithm is to look for the \"best\" triple and add it to the matching \(\Sigma^{t}\) each time, starting from an empty set. Each \"best\" triple (\(u_{i}^{t}\), \(l_{j}^{t}\), \(g_{k}^{t}\)) is produced by first choosing a GEO satellite that meets specific criteria, after which this chosen GEO satellite selects the best user that satisfies its criteria, and finally this chosen user selects the most qualified LEO satellite. ```
1.Phase 1: Initialization;
2.Input:\(\mathcal{U}^{t},\mathcal{L}^{t},\mathcal{G}^{t}\);
3. Set \(\Sigma^{t}=\varnothing\), symbol=1;
4. Phase 2: Matching;
5. while symbol \(==1\) perform;
6. Set symbol \(=0\);
7. for each \(g_{k}^{t}\in\mathcal{G}^{t}\) perform;
8. \(\hat{\mu}=\Pi^{+1}(\Sigma^{t},\ g_{k}^{t})\cap\Pi^{-2}(\Sigma^{t},\ g_{k}^{t})\);
9. if \(\hat{\mu}\
eq\varnothing\) then;
10. \(u_{i}^{t}=Top(\hat{\mu},g_{k}^{t})\);
11. \(\hat{L}=\Pi^{+1}(\Sigma^{t},\ u_{i}^{t})\cap\ \Pi^{-1}(\Sigma^{t},\ g_{k}^{t})\);
12. \(l_{j}^{t}=Top(L,u_{i}^{t})\);
13. if \(\mathcal{N}(\Sigma^{t},\ g_{k}^{t})==N_{G}\) then;
14. Choose the worst matched triple \(\sqcup_{\textit{worst}}=(\Sigma^{t}(g_{k}^{t}),\ \Sigma^{t}(\Sigma^{t}(g_{k}^{t})),g_{k}^{t}\ )\) for \(g_{k}^{t}\);
15. \(\Sigma^{t}=\Sigma^{t}\sqcup_{\textit{worst}}\);
16. symbol \(=1\);
17. end if:
18. if \(\mathcal{N}(\Sigma^{t},\ u_{i}^{t})==1\) then;
19.