# Enhanced Integrated Satellite-Terrestrial NOMA with Cooperative Device-to-Device Communication
## 3 Satellite-Aided NOMA with Cooperative D2D Communication
### Toy Network  
Following the operation of Algorithm 1, a network consisting of \(N=4\) UEs is assumed, and so, four vertices are created, where \(v_{1}=\text{UE}_{1}\), \(v_{2}=\text{UE}_{2}\), \(v_{3}=\text{UE}_{3}\) and \(v_{4}=\text{UE}_{4}\), and added to the set of vertices \(V\). Next, starting from \(\text{UE}_{1}\), the algorithm connects this vertex with all the other three vertices using appropriate edge labeling, by initially setting the weight of each edge to zero. Thus, through this step, the vertex \(\text{UE}_{1}\) is connected with the vertex \(\text{UE}_{2}\) via the edge \(e_{1,2}\), with the vertex \(\text{UE}_{3}\) via the edge \(e_{1,3}\) and with the vertex \(\text{UE}_{4}\) via the edge \(e_{1,4}\). The weights \(w_{1,2}=w_{1,3}=w_{1,4}=0\) of the corresponding edges are initially set to zero and all edges are added to the set of edges \(E\) of the graph \(G\). Thereafter, the algorithm visits the next vertex, i.e., \(\text{UE}_{2}\) and connects it with vertices \(\text{UE}_{3}\) and \(\text{UE}_{4}\) via the edges \(e_{2,3}\) and \(e_{2,4}\), where again, the weights are set to zero \(w_{2,3}=w_{2,4}=0\). Obviously, the edge \(e_{1,2}\) that connects the vertex \(\text{UE}_{1}\) with the vertex \(\text{UE}_{2}\), indicating the formation of a possible pair of users, has been already created and added to the set of edges \(E\) during the previous step, and there is no need to create it again. After that, the algorithm visits the vertex \(\text{UE}_{3}\) and connects this vertex with the vertex \(\text{UE}_{4}\) via the edge \(e_{3,4}\) and set the weight \(w_{3,4}=0\) of this edge to zero. Finally, Algorithm 1 visits the last vertex \(\text{UE}_{4}\) and terminates because this vertex has been already connected with all the other vertices of the graph \(G\). In Figure 2, the graph setup that is produced through the execution of Algorithm 1 with \(N=4\) UEs is illustrated. The total number of vertices is equal to the total number of users \(|V|=4\) and the total number of edges is equal to \(|E|=6\). Each edge \(e_{i,j}\) has a weight \(w_{i,j}\) with \(i<j\), initially being equal to zero. Using (16) and (18), if the solution that gives the maximum sum rate through Algorithm 2 connects vertices \(v_{i}\) and \(v_{j}\), \(\text{UE}_{i}\) and \(\text{UE}_{j}\) will form a pair and \(e_{i,j}=1\). Otherwise, vertices \(v_{i}\) and \(v_{j}\) are not connected and \(e_{i,j}=0\). It should be noted that the full mesh network presented in Figure 2 is not the optimal user pairing policy that gives the maximum sum rate of the system, but the graph setup that is created once for this specific number of users (\(N=4\)) through Algorithm 1, representing all the possible pairs of users with their corresponding achievable rates, indicated as a weight of the corresponding edge. Practically the graph illustrated in Figure 2 is an input for the maximum weighted perfect matching problem that is adopted by SANOCO-D2D, and the solution of this problem keeps only the edges from the optimal pair of users \(\mathbf{u}_{i,j}^{*}\)) that gives the maximum sum of weights (maximum sum rate \(R_{\text{max}}\)) with the constraint that each vertex must be connected with exactly one other vertex in the graph, thereby ensuring that each user will be paired with exactly one other user in the system in order to perform NOMA or NOMA-D2D transmission, i.e., SANOCO-D2D. Figure 2: An illustrative example of the graph setup that is used by the proposed technique in order to find the optimal user pairing policy \(\mathbf{u}_{i,j}^{*}\) and the maximum sum rate \(R_{\text{max}}\) for \(N=4\) UEs. Once the graph setup that is shown in Figure 2 is created or loaded for the case of \(N=4\) UEs, the execution of Algorithm 2 starts. Algorithm 2 receives as an input the CSI of each user regarding the channel condition with the satellite, and the D2D CSI between all users.