# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 4 Graph-Based RA in Cellular Homogeneous and Het-Nets
### Miscellaneous Methods  
RA and EE with distributed optimization in a Het-Net comprising a fixed number of macro BSs and small BSs (or APs) is studied in [35]. The proposed solution utilizes a Gibbs sampler (describing the SINR of each user) operating on a graph to minimize the interference (and hence optimize the throughput) between a macro BS and a small BS. The users represent the graph's vertices, whereas a user's neighbors receive a signal stronger than a certain threshold (i.e., interference) on the same channel, thus constituting an interference graph. Each vertex has an attribute describing its power and channel allocation, determined by its serving BS. Substantial \(\bar{R}_{u}\) and energy efficiency \(\varepsilon\) gains are achieved. Channel distribution according to the users' location (close to the cell's center or its edge) in the scenario of fixed number of BSs, UEs, and channels, is performed in [36]. The BSs that serve users with unfavorable conditions (DL SINR below a certain threshold), are described as vertices of the graph, while the edges connecting them illustrate the interference levels. The optimization problem aims to maximize the center users' throughput while limiting the BS transmission power allocated to them, and provide orthogonal channels to the cell-edge users. An alternative approach to solving this RA problem is proposed in [37] by dividing it into two sub-problems. Firstly, UA and channel allocations are performed for fixed power from the BSs to the UEs. A bipartite graph is used to describe the connections between them. The channel allocations are performed via the Hungarian algorithm, which aims to match the BSs to the UEs that produce the maximum weighted sum throughput (MC is considered). Then, the power allocations are performed in a separate optimization problem that utilizes the already obtained channel allocations. It is solved via the difference of the convex functions approximations (DCA) method. Finally, the two methods are combined to obtain faster convergence. This study is extended in [38] by considering the co-tier (between the cells of the same type) and cross-tier (cells of different types) interference. The system's resources are divided into regular resource blocks (RRBs) and almost bank resource blocks (ABRBs), the latter being allocated to reduce the cross-tier interference, while allocating orthogonal RBs to neighboring cells aims to deal with the co-tier interference. The two tiers (small cell and macro-cell) are described via two separate interference graphs. Vertices are BSs of the same tier, and if the distance between two of them is greater than a threshold, they are connected with an edge. Afterwards, these graphs are converted to conflict graphs which are composed of the cells' UEs, and there are edges between those served by cells that were connected together in the interference graphs. Then, the groups of two or more distinct adjacent vertices (cliques) form trees that are used for RB allocation in the cells of each of the tiers. The final RB distribution is performed via an exhaustive search algorithm, with the minimum throughput satisfaction rate (TSR) constraint. This solution achieves a relatively stable ratio of ABRB, of \(\theta_{u}\), and of \(\beta\) as the number of small cells increases. Predictive ICI and RA in Het-Nets with spatial division multiple access for a fixed number of BSs and variable number of UEs is proposed in [39]. The DL data stream is divided into frames, and the algorithm determines which BS is to serve which user at each frame (interfering BSs do not transmit for its duration). In addition, each BS has multiple antennas that serve different users, and in this way, each antenna forms a virtual BS. The users and virtual BSs are described as the vertices, whereas their connections--via the edges, their weights being the network utility parameter--are dependent on the TSR \(\theta_{u}\). Then, the graph's vertices are divided into independent sets (a subset such that no two vertices in it are connected).