# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 4 Graph-Based RA in Cellular Homogeneous and Het-Nets
### RA Methods in OFDMA Systems
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Reference** & **Application** & \begin{tabular}{c} **Graph Model** \\ **Type** \\ \end{tabular} & \begin{tabular}{c} **Tasks Solved** \\ **via Graphs** \\ \end{tabular} & \begin{tabular}{c} **Graph** \\ **Formulation** \\ \end{tabular} & \
\begin{tabular}{c} **Optimization** \\ **Method** \\ \end{tabular} &
\begin{tabular}{c} **Performance** \\ **Assessment** \\ \end{tabular} \\ \hline
[34] & \begin{tabular}{c} Channel \\ allocation in a \\ WLAN \\ \end{tabular} & Conflict graph & Channel allocation & \begin{tabular}{c} Vertices--APs; \\ edges--between \\ APs within a \\ certain range \\ \end{tabular} & \
\begin{tabular}{c} &
\begin{tabular}{c} Over 90\% \\ spectrum \\ utilization for \\ 10 APs and \\ 3 channels \\ \end{tabular} \\ \hline
[35] & RA and EE in \\ HetNet & Interference & Channel and & \begin{tabular}{c} Vertices--UEs; \\ edges-- \\ interfering \\ UEs \\ \end{tabular} & \
\begin{tabular}{c} &
\begin{tabular}{c} 1.8 b/s/Hz, \\ and \& of \\ 3 b/s/Hz/W \\ 96 UEs, with \\ a dedicated \\ channel for each \\ \end{tabular} \\ \hline
[36] & \begin{tabular}{c} Channel and \\ power allocation \\ in a Het-Net \\ \end{tabular} & Interference & Power and \begin{tabular}{c} channel \\ allocation \\ \end{tabular} & \
\begin{tabular}{c} Vertices--BSs ; \\ edges-- \\ interfering \\ BSs \\ \end{tabular} & KKT &
\begin{tabular}{c} \(\bar{R}_{c}\) of up to \\ 100 Mb/s (UL) \\ and 80 Mb/s \\ (DL), and \(\bar{R}_{u}\) of \\ up to 550 kb/s \\ (UL) and \\ 250 kb/s (DL) \\ for 100 UEs and \\ up to 4 small \\ cells and \\ 1 macro-cell \\ \end{tabular} \\ \hline
[37] & \begin{tabular}{c} Channel and \\ power allocation \\ in an OFDMA \\ Het-Net \\ \end{tabular} & Bipartite graph & Channel allocation & \begin{tabular}{c} Vertices--BSs \\ and UEs; \\ edges--between \\ allocation \\ \end{tabular} & \
\begin{tabular}{c} \(R_{T}\) of up to \\ 55 b/s/Hz for \\ algorithm, DCA \\ with adequate \\ SINR \\ \end{tabular} &
\begin{tabular}{c} \(R_{T}\) of up to \\ 55 b/s/Hz for \\ 50 kb/s \\ and 6 small cells \\ and 1 macro-cell \\ \end{tabular} \\ \hline
[38] & RA for OFDMA & \begin{tabular}{c} Conflict/ \\ credit/tree \\ graph \\ \end{tabular} & RB allocation & \
\begin{tabular}{c} Vertices--BSs \\ cells/UEs; \\ edges-- \\ interfering \\ cells/UEs \\ \end{tabular} &
\begin{tabular}{c} Convergence for \\ \(\beta\), \(\alpha_{u}\), and \(\theta_{u}\) for \\ 50 small cells \\ and 50 RBs \\ \end{tabular} \\ \hline
[39] & \begin{tabular}{c} Predictive RA \\ for Het-Net \\ \end{tabular} & Conflict graph & Channel allocation & \
\begin{tabular}{c} Vertices—BSs \\ and UEs; edges-- \\ interfering cells \\ and served UEs \\ \end{tabular} &
\begin{tabular}{c} \(\theta_{u}\) of up to 80\% \\ and \(R_{T}\) of \\ algorithm \\ 16 b/s/Hz for \\ 30 UEs \\ \end{tabular} \\ \hline
[40] & \begin{tabular}{c} EE, channel and \\ power allocation \\ \end{tabular} & Bipartite graph & Channel allocation & \begin{tabular}{c} Vertices--UEs; \\ edges-- \\ channels \\ \end{tabular} & \
\begin{tabular}{c} Dual Lagrangian \\ algorithm \\ \end{tabular} &
\begin{tabular}{c} \(\varepsilon\) of 12 b/s/Hz/J \\ for up to 5 UEs \\ and 5 BSs \\ \end{tabular} \\ \hline \hline \end{tabular}
\end{table} 
Table 6: _Cont._a Minimum Cost Network Flow (MCNF) graph model, which is similar to a bipartite graph but with the difference that its vertices can have self-connections (an edge connecting a vertex to itself). These describe the vertices' parameters (their throughput gain). The graph connects all channels to each of the users, and describes the resulting throughput, which a particular allocation can generate. Through the simplex network algorithm, the optimal allocations are determined, such that every user's minimum requirement is satisfied. Linear increase in the total throughput \(R_{T}\) with the number of users and nearly constant average throughput per user \(\bar{R}_{u}\) are reported.