# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 5 Graph-Based RA in D2D Networks
### Hypergraph-Based RA Methods  
A more thorough interference coordination for RA in underlay inband D2D communication for a variable number of CUEs and DUEs within the coverage of a single macro BS is performed in [54] using a hypergraph-based method. It is a generalization of the standard graph, in which the hyperedges connect any subsets of the vertices, rather than just two, and its topology is reflected in the incidence matrix only. The CUEs and DUEs constitute the hypergraph's vertices, while their interference defines the hyperedges depending on whether the individual nodes or multiple users cumulatively introduce interference greater than a predefined SINR threshold. As determined empirically, a hyperedge may encompass, at most, two other vertices apart from the one considered (increasing the hyperedge's scope does not yield meaningful gains). Channels are allocated through graph coloring, with the limitation that within one hyperedge, only one channel may be used for each vertex. The proposed solution achieves near optimal results, as \(R_{T}\) increases with both \(N_{CUE}\) and \(N_{DUE}\). An alternative vehicular communications scenario is considered for the RA problem in [55], with the goal of providing channel allocation between a fixed number of vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) nodes. The former communicate with the BS (their links are prioritized), while the latter communicate with each other (their links are subject to optimization). V2V links are clustered according to their interference, operating on one RB allocated for a V2I link, while neighboring clusters have to use different RBs. A tripartite hypergraph is composed of the RBs, V2I and V2V nodes as vertices, with their edges' weights corresponding to the achievable throughput. Each cluster of V2 Vs is considered in a separate hyperedge connected to the RBs and V2I vertices. Power allocation is performed separately. The proposed solution shows increased V2I total throughput for the high SINR levels at the V2 Vs, and so exhibits resilience in fast fading. The study [56] explores a NOMA-based vehicular communications scenario with channel allocation between V2 Is, broadcast V2 Vs (a group of V2 Vs where one of them transmits messages to all the others), and standard V2 Vs, each of these types forming separate communication groups (the latter two being underlay users of the V2I spectrum). Two kinds of interference are considered--between each group, and within the groups themselves. The broadcast V2 Vs and standard V2 Vs are divided into clusters (using the Hungarian algorithm) based on their mutual interference. Then a tripartite hypergraph is constructed, which has the clusters, V2 Is and RBs (they are all of an equal number) as its vertices, and the matching relationships between them as hyperedges (their weights being the achievable throughput for each allocation). The algorithm aims to maximize their weights through either a greedy or an iterative algorithm, which both exhibit similar performance, but the former has lower complexity. Simulation results show exponential gain in \(R_{T}\) with the increase in the number of nodes, as well as a decline in performance as the vehicles' speeds increase. The authors of [57] consider the channel allocation between CUEs, V2V, and V2I nodes (all operating within the range of a single macro BS), such that the probability of outage requirements for V2 Vs and the SINR requirement of the cellular users are met, while the throughput of V2 Is is maximized. Power allocation is performed separately via the Newton method. A hypergraph is constructed similarly to [58], with all three types of users being represented as vertices, while their edges describe the interference from individual neighboring nodes, and hyperedges denote the cumulative interferers for each vertex. Then, the RB allocation is performed through graph coloring on the condition that two vertices connected by an edge cannot share the same RB.