# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 5 Graph-Based RA in D2D Networks
### Miscellaneous Methods  
The authors of [65] propose distance-dependent RA (which does not require the users' channel state information, or CSI, at the BS) through two separate approaches for minimization of the outage probability \(P^{out}\) (likelihood of not reaching a certain critical SNR at some D2D receiver). To describe the optimization problems, they are modeled via a bipartite graph, the vertices of which are the D2D pairs and CUEs, while its edges are weighted by the \(P^{out}\) for each connection. Both a shortest path (finding the one with the lowest outage) algorithm and binary search (choosing the topology that yields \(P^{out}\) under a predefined threshold) are used to determine how channels are to be allocated for the D2D pairs, considering that they are all used by the CUEs. Simulations show that \(P^{out}\) increases exponentially with the target SINR \(\gamma_{T,CUE}\) of the CUEs, and \(N_{CUE}\), while it decreases linearly with the increase in \(N_{DUE}\), and their target SINR \(\gamma_{T,DUE}\). Introducing social relationships between the mobile users into the graph-based RA for D2D and cellular coexistence (i.e., considering both the social and physical domains) has been explored in [66]. Thus, social and an interference graphs are constructed, which both include the CUEs and DUEs as vertices, while their edges describe the closeness coefficient which denotes their social relationships (in the former graph) or interference levels (in the latter graph). Then, the problem is formed as optimization of the social utility function \(U_{s}\) that is composed of the CUE and DUE throughputs, and their closeness, under the constraint that a D2D pair employs only one RB. A Nash equilibrium potential game is defined to perform the channel allocation. Simulations have shown that \(U_{s}\) increases with the number of DUEs, whereas the fairness exhibits a relative decline. Furthermore, increasing the social link probability yields throughput gains because it means that more D2 Ds are eligible to share common content and offload traffic from the BS. Channel and power allocation in the condition of limited CSI (geographical locations of DUEs, and CSI from the CUEs) at the BS and fixed number of CUEs, DUEs, and channels is considered in [67]. A bipartite graph connects the sets of CUEs and channels, the edges' weights being the average throughput achieved for each separate allocation. Afterwards, the CUEs and DUEs are connected via an undirected graph, with the received signal for each connection describing the respective weights. Due to the lack of CSI, however, these weights need to be estimated separately. Then, the most appropriate allocations are made by describing every possible link between each DUE and all CUEs in a bipartite graph and finding those with smallest weights. Accordingly, clusters are formed, with each one containing only a single D2D pair. Power allocation is performed for each cluster via a Nash equilibrium potential game, the solution of which is estimated via a Q-learning method. A relatively stable utility function \(\Omega_{U}\) is obtained. A different approach to the RA problem is taken in [68]. Allocation of multiple RBs to a D2D pair is considered, with the limitation of preserving the CUEs' desired throughput, while their channels are preliminarily allocated by the BS. The D2D pairs and available RBs are connected via a bipartite graph, the edges' weights being expressed by the proportional fair (PF) metric, which is a function of the achievable throughput. Multiple RB allocation is described by the same graph with the modification of repeating the vertices corresponding to the DUEs; \(T_{RB}\) times (\(T_{RB}\) is the maximum number of RBs per D2D link). The scenario is comprised of a fixed number of CUEs and channels, and a variable number of DUEs within the coverage of a single macro BS. It is notable from the results that DUEs throughput declines with the distance between them, but increases with their number for \(T_{RB}=1\).