# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 6 Graph-Based RA in CR Networks
### Miscellaneous Methods  
The authors of [81] study channel and power allocation for a CR network which is comprised of stationary CAPs and SUs, with the goal of maximizing the number of SUs served \(N_{SU}^{\prime}\) while imposing constraints on the minimum DL SINR for the SUs \(\gamma_{SU,min}\) and maximum DL interference towards the PUs \(I_{PU,max}\). Each SU can only occupy a single channel, the power level for which is chosen so as to provide \(\gamma_{SU,min}\) according to the path loss (this is coordinated among the CAPs), and all CAPs have information about the SUs (all of them are active). The CR network is represented via a graph, the vertices of which are the SUs, and edges connecting the interfering vertices. It is constructed at the start and its channel allocations change to adjust to the requirements for \(\gamma_{SU,min}\) and \(I_{PU,max}\). Simulations show that \(N_{SU}^{\prime}\) declines linearly with the increase in the number of PUs \(N_{PU}\), of cognitive APs \(N_{CAP}\) and channels \(N_{c}\). This work is expanded in [82] by considering the availability of only local knowledge (each CAP only has information about the SUs within its range). First, the SUs with the smallest channel gains are assigned for each CAP to define the coverage matrix, and power allocation is performed for each CAP-SU link. Then, the active SUs and available channels form a bipartite graph, and the number of disjointed edges is maximized to perform channel allocation. Over 10% more SUs are served using this method in comparison to that in [81], while their number declines exponentially with the increase in PUs. A CR relay network (it includes nodes that serve as relays for the SU's communications) with joint relay selection and channel allocation is considered in [83]. The proposed solution aims to simultaneously minimize the sum transmission power of the CR network and maximize \(N_{SU}^{\prime}\). The channel allocation problem is described via a bipartite graph with the CR transmitter-receiver pairs and the channels as vertices, with the edge's weights representing the sum of CR transmitter and CR relay output power levels among the set of all relay selections for a particular channel. The heuristic algorithm determines the selection of relay nodes and of channels that minimize this sum. Simulations show that the sum of the CR network's total transmission power \(P_{CR,T}\) does not grow over 20% higher than that of the PU network. Channel distribution with the probability of conflict reduction for a CR network is considered in [84]. A graph connects all SUs which have links between each other. The channel distribution is performed using a star graph that has the channels and links between the SUs as vertices, with the edges' weights representing the conflict probability that depends on which channels are perceived as available by each SU. Three heuristics algorithms are introduced to solve this problem, with the node-link-based channel allocation (optimal matching between channels and adjacent links) yielding the highest percentage of assigned SU links, remaining relatively stable with the increase in \(N_{PU}\). A similar scenario is considered in [85], considering both centralized and distributed RA, while protection of the PU communications is facilitated by the list of unavailable (blocked) channels at each SU pair. This list is the attribute of the conflict graph that connects all SU pairs, and their edges' weights are comprised of both the co-channel and adjacent channel interference for each potential conflicting allocation between two links. These attributes combined together form the SU saturation metric, on the basis of which vertex coloring is performed so as to assign the channels. The solution's convergence time increases linearly/exponentially with the number of SUs for the distributed/centralized variants. However, the average throughput per SU \(\bar{R}_{SU}\) declines exponentially.