# Resource Allocation for GBR Services in D2D-Enabled Communication
## 3 Resource Allocation for GBR Services
### 3-D Assignment of CU, DU, and Channel  
Since we calculated the channel bandwidth for arbitrary matching, \(B_{n,m}^{l}\) in (7), the remaining problem is to find the best matching combination for \(N\) CUs, \(M\) DUs, and \(L\) channels. This 3-D assignment problem can be expressed as  
\[\text{AP1}:\ b(x) =\ \min\left\{\sum_{l=1}^{L}\sum_{m=1}^{M}\sum_{n=1}^{N}\sum_{n=1} ^{N}x_{n,m}^{l}B_{n,m}^{l}\right\} \tag{9a}\] \[s.t.\ x_{n,m}^{l}\in\{0,1\},\ \forall n,m,l\] (9b) \[\sum_{l=1}^{L}\sum_{n=1}^{N}x_{n,m}^{l}\leq 1,\ \forall m\] (9c) \[\sum_{l=1}^{L}\sum_{m=1}^{M}x_{n,m}^{l}\leq 1,\forall n\] (9d) \[\sum_{n=1}^{N}\sum_{m=1}^{M}x_{n,m}^{l}\leq 1,\ \forall l. \tag{9e}\]  
This NP-hard problem is unlikely to be solvable by an algorithm with a time bound that is polynomial in the size of the problem. Meta-heuristic techniques such as Tadu search and Genetic algorithm can be used to solve the NP-hard problem [24; 25; 26]. These techniques try to find an approximate solution through iterative search based on probability. They have advantage of fast convergence to the vicinity of the optimal solution in a short computation time. However, they cannot guarantee how close the approximate solution can be to the optimal solution. In this paper, we use a sub-optimal algorithm based on the Lagrangian relaxation. In this algorithm, to mitigate the computational complexity, a Lagrangian relaxation for constraint (9e) is used. Multipliers \(u_{l}\geq 0\) for \(l=1,\ldots,L\) are introduced and then, the following dual function \(\phi(u)\) can be defined as  
\[\phi(u) =\ \min\left\{\sum_{l=1}^{L}\sum_{m=1}^{M}\sum_{n=1}^{N}x_{n,m}^{l} \Big{(}B_{n,m}^{l}+u_{l}\Big{)}\right\}-\ \sum_{l=1}^{L}u_{l}, \tag{10}\]  
subject to (9b), (9c), and (9d). Then, it is easy to see that the solution for (10) is a lower bound of the problem in (9a), i.e., \(b(x^{*})\geq\phi(u)\). From Reference [27], Equation (10) can be written as:  
\[\text{RP1}:\ \phi(u) =\ \min\left\{\sum_{m=1}^{M}\sum_{n=1}^{N}\xi_{n,m}\underset{l\in \mathcal{L}}{\min}\Big{\{}B_{n,m}^{l}+u_{l}\Big{\}}\right\}\ -\ \sum_{l=1}^{L}u_{l} \tag{11a}\] \[s.t.\ \xi_{n,m}\in\{0,1\}\forall m,n\] (11b) \[\sum_{m=1}^{M}\xi_{n,m}\leq 1\ \forall n\] (11c) \[\sum_{n=1}^{N}\xi_{n,m}\ =\ 1\ \forall m. \tag{11d}\]The optimum solution to (11a), \(\xi^{*}_{n,m}\) does not necessarily satisfy (9e), but it does satisfy the remaining constraints. The decomposition of \(x^{l}_{n,m}~{}=~{}\xi_{n,m}\eta^{l}_{n}\) is used to assign a channel to the matching of CU \(n\) and DU \(m\). Now, let \(\delta^{l}_{n}~{}=~{}\sum\limits_{m~{}=~{}1}^{M}\xi^{*}_{n,m}B^{l}_{n,m}\), and AP1 in (9a) is equivalent to the following problem:  
\[s.t.\ x_{n,m}^{l}\in\{0,1\},\ \forall n,m,l\]0 \[s.t.\ x_{n,m}^{l}\in\{0,1\},\ \forall n,m,l\]1 (12b) \[s.t.\ x_{n,m}^{l}\in\{0,1\},\ \forall n,m,l\]2 (12c) \[s.t.\ x_{n,m}^{l}\in\{0,1\},\ \forall n,m,l\]3  
Constraints (12c) and (12d) can be derived from (9d) and (9e), respectively. Now, the aim is to find a \(u\) that maximizes or nearly maximizes \(\phi(u)\). A sub-gradient algorithm is used for this purpose. The sub-gradient \(v_{l}\) can be obtained by differentiating \(\phi(u)\) by \(u_{l}\), i.e., \(v_{l}~{}=~{}\frac{\partial\phi(u)}{\partial u_{l}}~{}=~{}\sum\limits_{m~{}=~{ }1}^{M}\sum\limits_{n~{}=~{}1}^{N}x^{l}_{n,m}-1\). The Polyak step size is given as \(\sigma~{}=~{}\frac{\phi(u)-\phi(u^{\prime})}{\|\psi\|^{2}_{2}}\), where \(\phi(u^{*})\) is not known, so the lower bound is used [28]. The details of the bounding procedure are summarized in Algorithm 1.