# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 5 Graph-Based RA in D2D Networks
### Lessons Learned and Trends in Development  
Based on the review of graph-based solutions for RA in underlay D2D networks, presented in this section, the following characteristics of current and challenges for future research, can be summarized:  
* Significant emphasis is placed on the modeling of the network as a graph whereas the optimization algorithms are similar in principle. _The main challenge, then, is to define a graph which corresponds well to the real-world relationships between the network nodes and the available frequency and power resources._ On the other hand, introducing new modes of communication (such as NOMA or FD [60; 63; 62]) or application scenarios (such as V2V and V2I [55; 56; 57]) can expand the graph's representation potency. Most of the reviewed methods utilize interference or bipartite grpahs due to their emphasis, either on the mutual influence between CUEs and DUEs, or on the allocation relationships between the nodes and the channels. Usually the solutions are divided into sub-problems which are solved in a particular sequence.
* Social graph and hypergraph structures are notable in some works. The social graph [66] has the benefit of incorporating not just the physical characteristics of the network's nodes, but the user-related ones as well. Therefore, _it is better suited for application-driven algorithms (such as cellular BS offloading), which also underlines its main design challenge, i.e., the definition of the user's social relationship, so as to be described via attributes of the vertices/edges._ The disadvantage of the social graph lies in the determination of the relationships of interest between the users in a D2D network. _They are not directly related to the physical relationships between the communication nodes, and need to be modeled separately, thus potentially increasing the computational cost of the RA algorithm._ The hypergraph, although harder to define, more completely captures the interference and movement dynamics between the incumbent and underlay nodes in the network. _It also has the potential for matching not just multiple types of nodes, but also channel and power allocations at the same time. This model has been shown to be of particular usefulness in vehicular D2D scenarios [55; 56; 57].  
* _As the number of nodes within a macro cell increases, graph-based methods may cause a very significant delay in order to reach convergence_ [73]. Hence, they may be less suitable for scenarios where UEs change their mode from cellular to D2D due to the decreased performance for QoS in the high layers of OSI. _Consequently, it is desirable for graph-based solutions to be evaluated through high-layer performance metrics as well._ Another common limitation of the graph-based solutions is that _each cellular user utilizes only one channel, which is usually not the case in realistic deployments. If different numbers of channels for each user are considered, the resulting graphs may be overly complex, both in their definition and solution._
* Some open questions concerning graph-based methods in D2D networks pertain to (1) _The extent to which they are scalable, and at what D2D deployment density does a method become unreasonably complex._ The graph's topology may provide hints (such as maximum weight, maximum degree, and evaluation of the number of vertices at which the method converges in a reasonable time) as to how to determine such critical density. (2) The delay and the bandwidth needed for overhead exchange in large D2D networks are not usually considered directly. _It would be reasonable to assume, nonetheless, that it may be prohibitive, even if the RA algorithm is itself computationally light._ (3) The lack of perfect CSI at the BS, which may be alleviated through ML. However, _a sufficient amount of training data will be necessary, the generation of which may not be trivial._