## 5 Energy-Efficient Resource Matching Algorithm for D2D Relay Communications
### Three-Dimensional Matching Algorithm
#### 5.2.2 Matching  
Similar to the two-dimensional matching problem, a conflict occurs if more than one D2D TR proposes the same RS or RB. Thus, the units contain the conflicting RSs, and RBs are denoted as \(\bar{\Omega}\); and the proposed pricing strategy can also be used to resolve the conflict. Let \(\hat{\mathcal{F}}^{R}=\{\bar{F}_{1}^{R},\cdots,\bar{F}_{r}^{R},\cdots,\bar{F} _{R}^{R}\}\) and \(\hat{\mathcal{F}}^{C}=\{\bar{F}_{1}^{C},\cdots,\bar{F}_{c}^{C},\cdots,\bar{F} _{c}^{C}\}\) denote the prices of RSs and RBs, respectively. The price of RC unit \(RC_{r,c_{f}}\) is the sum price of RS \(r\) and RB \(c_{f}\), and the price set of all of the RC units is denoted as \(\hat{\mathcal{F}}^{RC}=\{\bar{F}_{r,c_{f}}^{RC}\}_{r=1,c_{f}=1,c_{f}=1}^{r=R,c _{f}=C}\). In each iteration, the actual preference of D2D TR \(m\) towards unit \(RC_{r,c_{f}}\) is updated as \(\hat{EE}_{m,r,c_{f},c_{s}}-\bar{F}_{r,c_{f}^{C}}^{RC}\), and the preference list \(\hat{\mathcal{O}}_{m}\) should be updated accordingly. Any D2D TR \(m\) that has not been matched with any RC unit would propose its most preferred RC unit in \(\hat{\mathcal{O}}_{m}\). If both RS and RB in one RC unit receive only one request, the unit would be directly matched with the D2D TR that sends the request. If \(\bar{\Omega}\
eq\emptyset\), the conflicting elements in \(\bar{\Omega}\) would raise their prices with the price step \(s\), until there is only one request left. The iterative process ends when there are no new requests from D2D TRs.  
We summarize the three-dimensional matching algorithm in Algorithm 2, and an illustration of the preference lists' establishment and a stable matching that we expected is shown in Figure 4; the flowchart is given in Figure 5.  
Figure 4: An illustration of the three-dimensional matching in the first hop D2D link.  
```
1:Input:\(\mathcal{M},\mathcal{R},\mathcal{C},s\).
2:Output:\(\hat{\mathcal{K}}\).
3:Initialization:
4: Every D2D TR \(m\in\mathcal{M}\) builds its preference list on \(\mathcal{R}\mathcal{C}\).
5:Set \(\hat{\mathcal{X}}(m)=\emptyset\), \(\forall m\), \(\hat{\Omega}=\emptyset\), \(s=0.1\).
6:while\(\exists\hat{\mathcal{X}}(m)=\emptyset\)do
7:for\(m\in\mathcal{M}\)do
8: D2D TR \(m\) proposes to its most preferred RC unit in updated \(\hat{\mathcal{O}}_{m}\).
9:endfor
10: Count the amount of RSs and RBs that have received requests and put the conflicting elements that have received more than one request into \(\hat{\Omega}\).
11:if\(\hat{\Omega}=\phi\)then
12: Match the RC unit with its requesting D2D pair directly.
13:endif
14:if\(\hat{\Omega}\
eq\phi\)then
15:for\(RC_{r,c_{f}}\in\mathcal{R}\mathcal{C}\)do
16:if RS \(r\) and RB \(c_{f}\) receive requests from more than one D2D pair then
17: RS \(r\) and RB \(c_{f}\) in \(\hat{\Omega}\) increase their prices \(\hat{F}_{r}^{R}\) and \(\hat{F}_{c_{f}}^{C}\) with the price step \(s\), and D2D TR update the preference list \(\hat{\mathcal{O}}_{m}\). After this process, RC unit which includes RS \(r\) and RB \(c_{f}\) would be matched with the last remaining D2D TR \(m\) that proposed to them, denoted by \(\hat{\mathcal{X}}(m)=RC_{r,c_{f}}\). Delete RC unit \(RC_{r,c_{f}}\) from \(\hat{\Omega}\).
18:endif
19:endfor
20:endif
21:Update: Update \(\hat{\mathcal{O}}_{m}\) and \(\hat{\mathcal{E}}_{m}\) for \(\forall m\), \(\hat{\mathcal{X}}(m)=\emptyset\) by deleting the matched RC unit.
22: Set \(\hat{\mathcal{F}}^{\mathcal{K}}=\{0\}\), \(\hat{\mathcal{F}}^{\mathcal{C}}=\{0\}\), \(\hat{\mathcal{F}}^{\mathcal{R}\mathcal{C}}=\{0\}\).
23:endwhile
```  
**Algorithm 2** The Three-Dimensional Matching Algorithm  
Figure 5: Flowchart of the three-dimensional matching algorithm.