# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 4 Graph-Based RA in Cellular Homogeneous and Het-Nets
### RA Methods with User and Cell Clustering  
RA in Het-Nets via clustering of APs and users is explored in [22]. The number of APs, users and channels are fixed, and they are considered to be distributed in rooms on a single floor of a building in this scenario. An interference graph which connects all users is utilized to describe the network, with the edges' weights being determined as the maximum interference among the two connected users. The users and their serving APs are divided into clusters according to their interference vertices (users), with the minimum degree between themselves forming a cluster. The algorithm aims to choose channels and power which ensure that the intra-cluster interference (between the edges of the users within a cluster) is minimized. Notable performance gains are reported for both the \(R_{u}\) and the average throughput per cell \(\bar{R}_{c}\). This problem is further expanded by considering User-Pair Resource Allocation, i.e., users served by different APs are grouped together so RA is performed on clusters instead of individual UEs [23]. The optimization problem is decomposed into multiple minimum path selection sub-problems which are formed by clusters of varying sizes, such that the weighted sum-rate (WSR) of each user-pair is maximized. The WSR is comprised of the throughputs of the pair and arbitrarily weighted according to the quality-of-service (QoS) requirements of each user. These weights are updated after each RA instance. Similar to [22], the clusters are formed by intra-path sum-weights, i.e., the sum of all edges weights between the vertices within a path. User-centric (UC) clustering in a cellular network, comprised of a fixed number of UEs moving in an area covered by a variable number of BSs, is used as the scenario for which RA with overhead minimization is studied in [24]. The particular aim of this work is to allocate channels for the overhead needed for the formation of user clusters. The graph's vertices describe the BSs, their color illustrates the channel which they utilize (in time domain), while the edges represent conflict in the channel allocations (i.e. the critical interference threshold is exceeded) between two BSs. Then, the problem is solved by arranging the BSs such that maximal orthogonality between the channels allocated to them is achieved. BSs and UEs are clustered on the basis of the channel gain between them. The results show that \(R_{T}\) increases linearly with the number of BSs and channels per BS, as well as with the cell radius. A multiple connectivity (MC) cellular scenario, characterized by the association of one UE to multiple BSs, is used as a basis for the RA method in [25]. The scenario includes multiple small cells and UEs, to be allocated a fixed set of channels, and distributed within the coverage area of a single-macro BS. Additionally, downlink/uplink (DL/UL) decoupling is applied for some UEs, i.e., they associate with different BSs for their DL and UL connections. An interference graph is constructed for user clustering. The set of UEs comprises the vertices, all of them are connected via edges, and the sum of their DL and UL interference describes the edges' weights. The users are grouped in clusters according to their interference, so that the sum of the weights in any cluster is maximized. To distribute the resource blocks (RBs) among the users, a bipartite graph is formed by the sets of user clusters and RBs (they are of the same number), with the achievable throughput for each RB-user pair describing the edges' weights. Linear throughput gain with the increase in the number of small cells is reported. User grouping for RA in a non-orthogonal multiple access (NOMA) cellular network that includes a single macro BS serving a variable number of UEs is proposed in [26]. The power consumption and externality (PCE) function is introduced to characterize a user's power consumption, as well as the interference that the user creates toward the others in a group.