# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 5 Graph-Based RA in D2D Networks
### RA Methods in NOMA Systems  
RA in NOMA-based D2D communications is explored in [62]. The system model involves CUEs (each utilizing a single channel orthogonal to the others), as well as D2D groups composed of a transmitting node and multiple receiving ones (operating on a single CUE channel through NOMA). The channel allocation problem is described via a bipartite graph which connects the D2D groups (each represented by its transmitting DUE) and CUEs, the edge's weights being the EE \(\varepsilon\). Then, the optimal allocations (channel sharing between a CUE and a D2D group) are found via the Hungarian algorithm. Afterwards, power allocation is performed via a separate KKT-based method. The proposed solution exhibits a linear increase in the EE with the number of D2D groups; however, it gradually declines as the D2D transmission power is increased. To improve the interference resilience of underlay D2 Ds for NOMA, the authors in [63] propose the interlay spectrum access mode (user multiplexing in the power domain). Thus, based on the interference levels, the proposed solution chooses which of the two modes to assign for a link, together with the power and channel allocation. The graph's vertices represent all possible combinations of underlay D2D pairs, interlay D2D pairs, and their allocated channels. Two vertices are connected via an edge if they do not include the same D2D pairs and the same channel allocations. It is the vertices, rather than the edges, that have a weight attribute, which represents the maximum throughput achieved by the combination. Then, the vertices with maximum weights are determined through a pruning algorithm, and in this way, the channel allocations for the D2 Ds operating in each of the modes are generated. Afterwards, the optimal power for each vertex is determined via an iterative algorithm. To relieve the computational burden of these operations, a bipartite graph connects the D2D pairs and channels, with the throughput for each allocation being the edge's weight. Through the Hungarian algorithm, the allocation is performed with consideration of the choice of mode for each D2D pair that yields less interference. Exponential gain in \(R_{T}\) is reported with the increase in the number of D2 Ds. It is also retained when the CUEs' transmission power increases. Underlay D2D for a mmWave MIMO-NOMA system is considered a model for which user clustering and power allocation solution is employed in [64]. It involves a macro cell, and within its range operate small cells that serve clusters of CUEs with orthogonal channels being assigned to each cluster, while the users in it use NOMA. The underlay D2 Ds within each cluster utilize the same channels as the CUEs, aiming to maximize the network throughput while guaranteeing the QoS of both the DUEs and CUEs. The CUE clustering is performed through a graph with the CUEs as vertices that are connected by edges, the weights of which represent the channel correlations between each two. Then, the vertices are clustered through \(K\)-means on the basis of the correlations between them. The DUE clustering is performed through a graph with the D2 Ds as vertices connected by edges (interference). Finally, the two sets of clusters are matched through a bipartite graph, with the edges' weights being the channel correlations between each CUE and DUE cluster. The power allocation is performed separately via a particle swarm optimization algorithm [72]. Through simulations, it is discovered that the proposed solution achieves fast convergence, as well as the optimal cluster sizes and number of DUEs.