# A Novel Resource Allocation Scheme in NOMA-Based Cellular Network with D2D Communications
### Proposed Tree-Based Search Algorithm (TSA) for Power Allocation  
In this section, we first define two kinds of judgement standards for selecting the candidate nodes and decide which nodes should result in survival. One of the standards about the power allocation coefficients \(\beta_{k,m}\) is  
\[\Omega_{s,m}=\sum\
olimits_{k=1}^{s}\beta_{k,m},\ s\in n_{m} \tag{28}\]  
which represents the summary of \(\beta\) from the first layer to the \(s-\)th layer. For \(n_{m}\in N\), the number of the CUs on each SC, we have \(\Omega_{n_{m}}=1\) according to (25). Another standard is for the data rates,  
\[\Gamma_{s,m}=\sum\
olimits_{k=1}^{s}R_{s,m},\ s\in n_{m} \tag{29}\]  
which denotes the summary of the data rates of CUs from \(1\) to \(s\). For \(n_{m}\), \(\Gamma_{n_{m}}\) represents the summary of the data rates from CU \(1\) to CU\(n_{m}\). The TSA achieves the power allocation of the CUs within each SC and finds a suboptimal solution, as shown in Algorithm 2. The detailed process of TSA is described as the following steps:  
1. Initialization: First, we initialize the standards (28) and (29) mentioned above and the channel gain of each CU on the same SC. 2. Calculate the values of the power allocation coefficients: Calculate the matrix of candidate power allocation coefficients \(\beta_{k,m}\) in the \(k-\)th layer, according to (26) and (27), determined by the number of survival nodes of the previous layer and the minimum interval \(\Delta\) of the power allocation coefficients. 3. Delete the redundant nodes: We first divide the nodes into several groups. In each group, through (26), we calculate \(\Omega_{k,m}=\Omega_{k-1,m}+\beta_{k,m}\) and find out the nodes belong to the \(k-\)th layer which has the same \(\Omega_{k,m}\) to be classified to the same group. Then through the formulation \(\Gamma_{k,m}=\Gamma_{k-1,m}+R_{k,m}\) derived from (26), we get the results of \(\Gamma_{k,m}\) in each group and pick out the maximum nodes. Finally, we select the survival nodes and delete the redundant paths. 4. Select the final survival path: Repeat step (2) and step (3) until the last layer where \(\beta_{n_{m}}=1-\Omega_{n_{m}-1}\) and the number of the branches equals to the number of the survival nodes in the previous layer. Satisfying the unique value of \(\Omega_{n_{m}}\), i.e., \(\Omega_{n_{m}}=1\), we pick out the group of survival nodes with the maximum \(\Gamma_{n_{m}}\) and get the final survival path. 5. Output: From final survival path we can get the suboptimal set of power allocation coefficients \(\left\{\beta_{1}^{*},\ \ldots\,\beta_{n_{m}}^{*}\right\}\). Figure 3 shows the flow chart of the tree-based search power allocation algorithm (TSA). For the suboptimal solution from Algorithm 1, the combinations of the searching process would be  
\[M!\left\{\left(\left( \begin{array}{c}n\\ 1\end{array} \right)+\left( \begin{array}{c}n\\ 2\end{array} \right)+\cdots+\left( \begin{array}{c}n\\ U_{\max}\end{array} \right)\right)+\left(\left( \begin{array}{c}L\\ 1\end{array} \right)+\left( \begin{array}{c}L\\ 2\end{array} \right)+\cdots+\left( \begin{array}{c}L\\ U_{\max}^{D2D}\end{array} \right)\right)\right\}, \tag{30}\]  
On the other hand, the complexity of the proposed algorithm is less than the complexity of ESA which would be  
\[O\left(N!\left(2^{n}+2^{L}\right)\right), \tag{31}\]Figure 4 investigates the comparison of the computational complexity cost between TSA and ESA with \(\Delta=0.01\) which represents the minimum interval of the power allocation coefficients [38]. Because NOMA allows the receiver to remove the part of the interference coming from the users who have larger power, it decreases the search times for each user. The complexity cost of TSA is \(Q\big{(}\frac{1}{\Delta^{2}}\big{(}1-\frac{1}{n}\big{)}\big{)}\) and this is lower than ESA whose complexity cost is \(O\big{(}\frac{1}{\Delta^{n-1}}\big{)}\)[31]. The total computational complexity cost of the proposed TSA algorithm with the searching process is \(O\big{(}\frac{1}{\Delta^{2}}\big{(}1-\frac{1}{n}\big{)}\big{)}+M!\left\{ \left(