# Enhanced Integrated Satellite-Terrestrial NOMA with Cooperative Device-to-Device Communication
## 3 Satellite-Aided NOMA with Cooperative D2D Communication
### Toy Network
The algorithm starts with the edge weight update procedure by visiting first the vertex \(\text{UE}_{1}\), while updating for each edge \(e_{1,j}\), the weight \(w_{1,j}=R_{1,j}\) of the corresponding edge with \(j=\{2,3,4\}\), following the steps of Algorithm 2. In this way, the weight \(w_{1,j}\) of each edge \(e_{1,j}\) indicates the pair rate that this pair of users \(\text{UE}_{1}\) and \(\text{UE}_{j}\) is able to achieve and contribute to the total system sum rate. Next, the algorithm visits the vertex \(\text{UE}_{2}\) and by following exactly the same procedure, updates for each edge \(e_{2,j}\) the corresponding weight \(w_{2,j}=R_{2,j}\) using the calculated pair rate \(R_{2,j}\) for this pair of users, with \(j=\{3,4\}\). The edge weight update procedure terminates when the algorithm visits vertex \(\text{UE}_{3}\) and updates the weight \(w_{3,4}=R_{3,4}\) of the edge \(e_{3,4}\) to be equal with the calculated pair rate \(R_{3,4}\) for this pair of users \(\text{UE}_{3}\) and \(\text{UE}_{4}\). Now, through the weight update procedure, each edge of the graph \(G\), representing a possible pair, has a positive weight value indicating the achievable sum rate for each possible pair. As a final step, in order to identify the optimal user pairing policy \(\mathbf{u}_{\mathbf{i},\mathbf{j}}^{*}\) and the maximum system sum rate \(R_{\max}\), graph \(G=(E,V)\) with the updated weight values is fed to the Edmonds algorithm which solves the maximum weighted perfect matching problem. As a result, the pair of users maximizing the system sum rate is derived. As a trivial example, consider that \(w_{1,2}=3\), \(w_{1,3}=7\), \(w_{1,4}=1\), \(w_{2,3}=2\), \(w_{2,4}=5\) and \(w_{3,4}=4\). In Table 1, the different possible pairs of users that can be formed with \(N=4\) UEs, and the achievable system sum rate of each possible formation in the system are presented. As it can easily be observed from Table 1, if \(\text{UE}_{1}\) is paired with \(\text{UE}_{3}\), and at the same time, \(\text{UE}_{2}\) is paired with \(\text{UE}_{4}\), the maximum system sum rate \(R_{\max}=w_{1,3}+w_{2,4}=12\) is achieved and those pairs constitute the optimal user pairing policy. This is the optimal formation of the pairs that the Edmonds algorithm gives as a solution to the maximum weighted matching problem, and the maximum sum rate. The graph with the formed pairs maximizing the sum rate for this toy network, is illustrated in Figure 3.  
The possible formed pairs that are presented in Table 1 are unique, because it is not allowed for a vertex in the graph to be unconnected, and at the same time, it is not allowed for an edge to start and end to the same vertex. Furthermore, exactly one edge is allowed to be connected at each vertex of the graph. In other words, each user should form a pair with exactly one other user of the system and it is not allowed to pair itself or to remain unpaired. Finally, it should be noted that during the weight update procedure of Algorithm 2, if D2D communication is not profitable or it is not feasible due to link failures, the result shown in Figure 3 concerning the optimal user pairing policy will be exactly the same as in the case of the downlink NOMA optimal user pairing technique [6]. In conclusion, it is possible that some pairs will cooperate via D2D links and some others will not, which is the philosophy behind SANOCO-D2D. As it will be discussed below, D2D cooperation can provide substantial gains for the sum rate of the system and the spectral efficiency. \begin{table}
\begin{tabular}{c c} \hline \hline
**Possible Formed Pairs** & **System Sum Rate** \\ \hline \(P_{1,2}=\{\text{UE}_{1},\text{UE}_{2}\}\) and \(P_{3,4}=\{\text{UE}_{3},\text{UE}_{4}\}\) & \(w_{1,2}+w_{3,4}=7\) \\ \hline \(P_{1,3}=\{\text{UE}_{1},\text{UE}_{3}\}\) and \(P_{2,4}=\{\text{UE}_{2},\text{UE}_{4}\}\) & \(w_{1,3}+w_{2,4}=12\) \\ \hline \(P_{1,4}=\{\text{UE}_{1},\text{UE}_{4}\}\) and \(P_{2,3}=\{\text{UE}_{2},\text{UE}_{3}\}\) & \(w_{1,4}+w_{2,3}=3\) \\ \hline \hline \end{tabular}
\end{table}