Joint Downlink and Uplink Interference Management for Device to Device Communication Underlaying Cellular Networks

Interference management is one of the most critical issues in underlaying device-to-device (D2D) communication due to the coexistence of D2D pairs and cellular users that operate under the same spectrum. In this paper, we provide the interference management algorithm to maximize the performance of the D2D communication while satisfying the quality-of-service requirements of the cellular communications in both uplink and downlink phases. The proposed algorithm includes: 1) the admission control and power allocation to ensure that the interference from D2D communication does not affect to the cellular communications and 2) the shared channel assignment to maximize the total throughput of the D2D communication. We prove that our proposed algorithm can achieve at least half of the performance of optimal algorithm. The simulation results validate the feasibility, convergence, and optimality of our algorithm: it cannot only closely approximate the optimal throughput of D2D communication but also outperform existing algorithms.

SECTION I. Introduction

Device to device (D2D) communication is currently integrated into the Long-Time Evolution Advance and suggested as the new paradigm to improve the overall network performance [1], [2]. D2D communication can enable the user equipments (UEs) in proximity to directly communicate without relaying data through a evolved Node B (eNB). With this paradigm, D2D communication provides the following potential gains: i) reuse gain due to the sharing spectrum resource with other cellular users (CUs) [3], ii) proximity gain due to the good channel condition of the D2D pairs in proximity, iii) hop gain due to the one-hop communication between two UEs [4].

The access to the spectrum in D2D communication can be done in one of two ways: overlay spectrum sharing and underlay spectrum sharing [2]. In the former one, the fraction of overall spectrum is dedicated to the D2D communication. Because the D2D pair uses separate resource with the CU, this access method is not efficient in reuse gain. Furthermore, the number of active CUs might be reduced due to the lack of spectrum in cellular communication. In the later one, the D2D pair simultaneously uses the same spectrum with the CUs as an underlaying. This approach has the advantages of not affecting to the spectrum of the cellular communication and also achieving the reuse gain in D2D communication [5]. Therefore, in this paper, we focus on the underlay spectrum sharing where the D2D pairs reuse the spectrum of the CUs.

Interference management is the most crucial problem in D2D communication underlaying cellular networks [6]. Due to the coexistence of D2D pairs and CUs that operate under the same spectrum, the D2D pair generates harmful interference towards eNB and CUs. In addition, the CUs also cause the interference to the D2D pairs which significantly reduce the efficiency of the D2D communication. The nodes that are affected by the interference (D2D pairs, CUs, eNB) depend on the shared channel in uplink (UL) and downlink (DL) phases. Therefore, channel assignment is necessary to manage the interference in D2D communication.

Beside, to deal with the interference, the power control algorithms also need to consider at UEs and eNB [7], [8]. By properly adjusting the transmission power of all nodes in the networks, we can achieve the target throughput of the CUs and maximize the overall throughput of the D2D pairs.

A number of the interference management algorithms that aim to guarantee the performance of CUs and maximize the performance of overall network is proposed in literature. The research in [9] considers the D2D communication in both UL and DL phases. The D2D pair shares channel with the CU outside the interference range of the D2D transmitter. However, since the shared channels are assigned without checking all possible assignments, the performance of the networks might not be optimal. In [10] and [11], the authors focus on power control and channel assignment for interference coordination between D2D pair and CU in uplink phase. The D2D pair is allowed to reuse the channel of CU after checking the throughput requirement of CU and the expected throughput of D2D pairs. However, since the D2D pair shares channel with only one CU, it limits the spectrum usage of the D2D communication.

Inspired by these aforementioned works, we propose the interference management algorithm for D2D communication underlaying spectrum sharing in both UL and DL phases. We jointly consider the shared channel assignment and power allocation for D2D communication such that: i) the performance of CUs should not be affected by introducing the D2D communication, ii) the total throughput of the D2D communication is maximized. As opposed to previous work, each D2D pair can reuse channels of multiple CUs while each CU shares channel with only one D2D pair. This approach not only reduces the computational complexity of the CUs but also improves the throughput of the D2D communication when the number of D2D pairs is less than the number of CUs. However, each D2D pair is restricted to reuse a maximum channel called quota due to the limitation of the hardware. The major contributions of this paper are

• We derive the throughput of D2D pair and CU in both UL and DL phases. Then, we formulate our objective as the mix-integer optimization problem (section III).

• We decompose the optimization problem into three sub-problems. First, we derive the admission set of each D2D pair: the set of CUs can share channel with the D2D pair without violating their performance. Then, we jointly coordinate the transmit power of the UEs (D2D pairs, CUs) and the eNB to maximize the throughput of each D2D pair in both UL and DL phases. Finally, we propose the shared channel assignment for D2D pair and CU to maximize the total throughput of all D2D pairs. The proposed algorithm can be implemented in distributed manner and has low complexity. We prove that our algorithm achieves the throughput at least 50% the optimal algorithm. (section IV).

• The simulation results highlight the effectiveness of our approach. By carefully checking all possible assignments between D2D pairs and CUs, the throughput of D2D pair can improve. Furthermore, because the D2D pair reuses channel with multiple CUs, it can achieve high throughput gain, especially when the number of D2D pairs is smaller than the number of CUs. (section V).

SECTION II. Related Work

According to the treatments of interference, the available interference managements can be categorized as the interference avoidance, interference cancellation and interference reduction.

A. Interference Avoidance

In the interference avoidance, the D2D pair shares channel with the CU such that not only the interferences suffered by the CU but also by the D2D pair are mitigated. In [3], the D2D pairs are not permitted to use the channel of the CUs lied inside its interference limited area (ILA). The ILA is defined as the area in which the signal to noise interference ratio of the D2D pair is smaller than the predetermined threshold. A similar approach has been considered in [9] where the ILA is defined base on the channel quality of the CU to the eNB.

The interference avoidance using graph theory has been considered in [12] and [13]. Especially, in [12], the interference between D2D pairs shared the same channel is formulated as the graph coloring problem. In addition, the D2D pairs reuse the channel with a CU that is sufficiently far away to avoid the co-channel interference.

However, in these approaches, the multi-user diversity is reduced because the ILA of a D2D pair physically limits the number of CUs share channel. The reused channel are assigned without checking all possible assignments between D2D pair and CU. In addition, the interference region is typically derived with the fixed transmit power at the UEs [3], [12], or based on the distance, channel quality of the UEs [9], [13]. Under such assumptions, the performance of networks might not be optimal.

B. Interference Cancellation

In this approach, the interference at the UE is treated as the noise. In [14], the objective is to find the optimal pre-coding vector of each link to mitigate the interference at the CU. The pre-coding vectors are maintained orthogonality for all D2D pairs. The authors in [15] consider the multiple antennas at the eNB. The partial zero forcing beam-forming method is proposed to eliminate the interference caused by the D2D pair at the CU.

In [16] and [17], the authors apply successive interference cancellation (SIC) to the D2D pair. Especially, in [16], the authors reveal that if the interference from the CU to the D2D pair is lower than a threshold, the D2D pair can decode the data by treating the interference as the noise. Otherwise, the D2D pair needs to perform the SIC to decode the data. The results show that not only the transmission rate at the D2D pair but also the transmission rate at the CUs are improved.

The advantage of these approaches is that the interference can be eliminated without reducing the transmission power. Therefore, the transmission rate also improves. However, it requires the extra computational efforts and communication overhead at the D2D pairs which have limited processing power, battery.

C. Interference Coordination

The D2D pair and CU coordinate their transmit power to optimize the objective function. Various game theoretic models have been proposed to cope this problem. In [18], the Stackelberg game is used to model the behavior of the CU and the D2D pairs. The CU (the leader) owns the channel and charges fee to D2D pair (the follower) to reuse channel. The charged fee is proportional to the received interference at the CU. Based on the fee, the D2D pair should adjust its transmit power to maximize its objective. In [19] and [20], a coalition game has been introduced to assign the channel to the group of CU and D2D pair. Each coalition includes one CU and other D2D pairs that share the same channel. The D2D pair can switch from the current coalition into other coalition if the total utilities in two coalitions increase. Note that in this game, the D2D pairs can belong to one coalition [20] or multiple coalitions [19]. Using game theory can result in high performance gain in comparison with other approaches such as SIC, beam-forming methods. This is because the CU can share the channel with multiple D2D pairs and the D2D pair can also reuse channel of multiple CUs. However, the optimality of the game is usually not proved mathematically. They also introduce significant message overhead between UEs to achieve the equilibrium of the game.

In the conventional optimization, the power control and channel assignment between D2D pair and CU to maximize the total throughput of the networks have been considered in UL phase [10] or DL phase [21]. The extended research of these works studies the partial channel states information [22]. The work in [23] considers D2D communication in both UL and DL phases with only one D2D pair and one CU. They focus on maximizing the throughput of the D2D pair and CU by optimizing the transmit power. In these works, after gathering the channel gain information from the eNB, the algorithm checks all possible assignments to find the optimal one. However, it often requires the centralized computation at the eNB. Furthermore, to reduce the complexity, the D2D pair is allowed to reuse channel with only one CU even that there exists other available CUs that have good channel condition.

On the contrary to previous works, we allow the D2D pair to reuse channels of multiple CUs to improve the throughput. Each D2D pair reuses the same channel in both UL and DL phase. Our proposed algorithm is implemented in distributed way and has low complexity. We also analyze the optimality of the proposed algorithm.

SECTION III. System Model and Problem Formulation

A. Networks Description

Consider a single cell network as shown in Fig. 1, consisting $C$ regular cellular users (CUs) and $D$ D2D pairs. The network bandwidth is divided into $N$ channels. We focus on the off-loaded cell scenarios where all the channels are assigned to the CUs ($N \le C$ ). Each CU shares channel with only one D2D pair while each D2D pair can reuse channels of multiple CUs to transmit data. We limit the number of reused channels of the D2D pair $j$ by the quota $q_{j}$ .

FIGURE 1.

D2D communication underlaying cellular network.

The eNB first allocates the channel to the CUs via scheduling and then our algorithm is applied to share channel to the D2D pair in both UL and DL phases. ¹ In the rest of paper, we call the channel allocated to CU $i$ as the channel $i$ .

We denote by $X=\left \lbrace{ x_{ji}}\right \rbrace$ the assignment vector of the D2D pair, i.e., $x_{ji}=1$ when the D2D pair $j$ reuses the channel of the CU $i$ , otherwise $x_{ji}=0$ . Since each CU shares channel with only one D2D pair and each D2D pair can share channel with a maximum number of CUs, we have

$$\begin{align} \sum \limits _{i \in {C}} {{x_{ji}}}\le&q_{j} \notag \\ \sum \limits _{j \in {D}} {{x_{ji}}}\le&1. \end{align}$$

We denote by $h_{i}^{c}$ , $h_{j}^{d}$ as the direct link gain between CU $i$ and the eNB, the direct link gain between D2D transmitter and D2D receiver $j$ . $h_{ij}^{c}$ , $h_{Bj}^{c}$ are the interference link gain from CU $i$ to D2D receiver $j$ , the interference link gain from eNB to the D2D receiver $j$ . $h_{ji}^{d}$ , $h_{jB}^{d}$ are the interference link gain from D2D transmitter $j$ to CU $i$ , the interference link gain from D2D transmitter $j$ to the eNB. We summarize the notations in Table 1.

TABLE 1 Summary of Notation

B. Transmission Rate

In this subsection, we derive the transmission rate for CU and D2D pair in both UL and DL phases. The fraction of time for UL phase is denoted by $\gamma$ . Since the source of interference depends on the shared channel in UL or DL phases, the transmission rates are calculated differently for each of them.

1) Uplink Phase

The SINR of the link between CU $i$ and the eNB is given as follows:

$$\begin{equation*} \psi _{i}^{UL,c} = \frac {P_{i}^{c}h_{i}^{c}}{{N_{0} + \sum \limits _{j \in D} {{x_{ji}}P_{j}^{d}h_{jB}^{d}}}}, \end{equation*}$$ where $P_{i}^{c}$ and $P_{j}^{d}$ are the transmit power of the CU $i$ and transmit power of the D2D $j$ . $N_{0}$ is the additive Gaussian noise.

In the UL phase, the CU causes the interference to the D2D pair. The SINR of the D2D pair $j$ under channel $i$ is calculated as:

$$\begin{equation*} \psi _{ji}^{UL,d} = \frac {{P_{j}^{d}h_{j}^{d}}}{{N_{0} + P_{i}^{c}h_{ij}^{c}}}. \end{equation*}$$ Then the transmission rates of CU and D2D pair in UL phase are derived by the Shannon ’s formula: $R _{i}^{UL,c} = \gamma W\log (1 + \psi _{i}^{UL,c})$ and $R _{ji}^{UL,d} = \gamma W\log (1 + \psi _{j,i}^{UL,d})$ , where $W$ is the bandwidth of the channel.

2) Downlink Phase

Similar to the uplink case, the SINR of the link between the eNB and the CU $i$ is given as

$$\begin{equation*} \psi _{i}^{DL,c} = \frac {{P_{i}^{B}h_{i}^{c}}}{{N_{0} + \sum \limits _{j \in D} {{x_{ji}}P_{j}^{d}h_{jB}^{d}}}}. \end{equation*}$$

In the DL case, the eNB generates the interference to the D2D pair. Thus, the SINR of the D2D link $j$ under channel $i$ is calculated as

$$\begin{equation*} \psi _{ji}^{DL,d} = \frac {{P_{j}^{d}h_{j}^{d}}}{{N_{0} + {P_{i}^{B}}h_{Bj}^{c}}}, \end{equation*}$$ where $P_{i}^{B}$ is the transmit power of the eNB to the CU $i$ . Then the transmission rates of CU and D2D pair in DL phase are given as: $R _{i}^{DL,c} = \left ({ 1-\gamma }\right ) W\log (1 + \psi _{i}^{DL,c})$ and $R _{ji}^{DL,d} = \left ({ 1-\gamma }\right ) W\log (1 + \psi _{ji}^{DL,d})$ .

C. Problem Formulation

Our objective is to maximize the total throughput of the D2D pair and guarantee the throughput of the CU by matching each D2D pair to the CU and coordinating their transmission powers. The optimization problem is given as

$$\begin{align}&{\mathop {\mathrm{ maximize}}\nolimits }~\sum \limits _{j \in D}\sum \limits _{i \in C} x_{ji}\left ({ {R_{ji}^{DL,d} + R_{ji}^{UL,d}}}\right ) \\&\text {subject to (1)} \notag \\&\quad \qquad \quad \, R_{i}^{UL,c} \ge R_{\min }^{UL}; {} R_{i}^{DL,c} \ge R_{\min }^{DL} \quad \forall i\in C \\&\quad \qquad \quad \, \psi _{j,i}^{DL,d} \ge \psi _{\min }; {} \psi _{j,i}^{UL,d} \ge \psi _{\min }\quad \forall i\in C,~j\in D \notag \\ \\&\quad \qquad \quad \, P_{i}^{d} \le P_{\max }^{d}; {} P_{i}^{c} \le P_{\max }^{c}\quad \forall i\in C,~j\in D.\notag \end{align}$$

$P_{\max }^{d}$ and $P_{\max }^{c}$ are the maximum transmission power of the D2D pairs and the CUs. The constraint (3) guarantees the target of transmission rate of CUs in both UL and DL phases. The constraint (4) ensures that the D2D pair can transmit data successfully in both phases. Since the optimization problem includes power allocation and channel assignment, it is a mix-integer problem. The complexity exponentially increases with the increasing of number of UEs. In next section, we propose the algorithm to efficiently solve it.

SECTION IV. Solution Approach for Optimization Problems

We decompose the original problem into three sub problems. First, we derive the admission set $\Pi _{j}$ for each D2D pair $j$ . This set includes the potential CUs that can share channel with the D2D pair $j$ without violating the constraint (3), (4). Second, we consider the power control for each D2D pair $j$ and CU $i\in \Pi _{j}$ to maximize total transmission rates of the D2D pair $j$ in both UL and DL phases. Finally, we assign the channel of the CU to the D2D pair to maximize overall transmission rate of the D2D pairs.

A. Admission Set of the D2D Pair

Given a D2D pair $j$ , we now derive the admission set $\Pi _{j}$ . If the CU $i$ belongs to $\Pi _{j}$ , it must satisfy the constraints (3), (4). By letting $g_\gamma ^{UL} = e^{\frac {{R_{\min }^{UL}}}{W\gamma }}-1$ and $g_\gamma ^{DL} = e^{\frac {{R_{\min }^{DL}}}{{W\left ({ {1 - \gamma } }\right )}}}-1$ , the constraint (3), (4) can be written as

$$\begin{align}&c1: \quad P_{i}^{c} h_{i}^{c} \ge g_\gamma ^{UL}\left ({ N_{0}+P_{j}^{d}h_{j,B}^{d}}\right ) \notag \\&c2: \quad P_{i}^{B} h_{i}^{c} \ge g_\gamma ^{DL}\left ({ N_{0}+P_{j}^{d}h_{j,i}^{d}}\right )\notag \\&c3: \quad P_{j}^{d} h_{j}^{d} \ge \psi _{\min }\left ({ N_{0}+P_{i}^{c}h_{i,j}^{c}}\right ) \notag \\&c4: \quad P_{j}^{d} h_{j}^{d} \ge \psi _{\min }\left ({ N_{0}+P_{i}^{B}h_{B,j}^{c}}\right )\!. \end{align}$$ We derive the feasible transmission powers of D2D pair $j$ , CU $i$ and the eNB from four inequalities (5) as shown in Fig. 2. The coordinates of points A, B, C, D are given as $$\begin{align*} A=&\left \{{ {x_{A};{y_{A}}} }\right \}= \left \{{ \begin{array}{l} N_{0}\dfrac {{h_{j}^{d}g_\gamma ^{UL} + h_{jB}^{d}g_\gamma ^{UL}\psi _{\min }}}{{h_{j}^{d}h_{i}^{c} - g_\gamma ^{UL}\psi _{\min }h_{i,j}^{c}h_{jB}^{d}}};\\ \dfrac {{h_{i,j}^{c}g_\gamma ^{UL}\psi _{\min } + h_{i}^{c}\psi _{\min }}}{{h_{j}^{d}h_{i}^{c} - g_\gamma ^{UL}\psi _{\min }h_{i,j}^{c}h_{jB}^{d}}} \end{array} }\right \}\\ B=&\left \{{ {x_{B};{y_{B}}} }\right \}= \left \{{ \begin{array}{l} N_{0}\dfrac {{h_{j}^{d}g_\gamma ^{DL} + h_{ji}^{d}g_\gamma ^{DL}\psi _{\min }}}{{h_{j}^{d}h_{i}^{c} - g_\gamma ^{DL}\psi _{\min }h_{B,j}^{c}h_{ji}^{d}}};\\ \dfrac {{h_{B,j}^{c}g_\gamma ^{UL}\psi _{\min } + h_{i}^{c}\psi _{\min }}}{{h_{j}^{d}h_{i}^{c} - g_\gamma ^{DL}\psi _{\min }h_{B,j}^{c}h_{ji}^{d}}} \end{array} }\right \}\\ C=&\left \{{ {x_{C};{y_{C}}} }\right \}= \left \{{ \begin{array}{l} P_{\max }^{B};\\ \dfrac {{P_{\max }^{B}h_{i}^{c} - g_\gamma ^{DL}{N_{0}}}}{{g_\gamma ^{DL}h_{ji}^{d}}} \end{array} }\right \}\\ D=&\left \{{ {x_{D};{y_{D}}} }\right \}= \left \{{ \begin{array}{l} P_{\max }^{c};\\ \dfrac {{P_{\max }^{c}h_{i}^{c} - g_\gamma ^{UL}{N_{0}}}}{{g_\gamma ^{UL}h_{jB}^{d}}} \end{array} }\right \}\!. \end{align*}$$

FIGURE 2.

The admission region of the D2D pair.

The CU $i$ belongs to the admission set of the D2D pair $j$ if and only if their channel gains satisfy

$$\begin{align} \left ({ {x_{A};{y_{A}}} }\right )\le&\left ({ {P_{\max }^{c};P_{\max }^{d}} }\right ) \\ \left ({ {x_{B};{y_{B}}} }\right )\le&\left ({ {P_{\max }^{B};P_{\max }^{d}} }\right ) \\ {y_{A}}\le&{y_{C}}; \quad {y_{B}} \le {y_{D}}. \end{align}$$ The inequalities (6), (7) imply that the feasible transmit powers of all UEs ( D2D pairs and CUs) and eNB are not larger than the maximum value. The feasible transmit power of D2D pair in UL and DL phases should be overlapped as in (8), so that the D2D pair can reuse the channel of CU in both UL and DL phases.

B. Power Control For D2D Pair and CU

Supposing that the D2D $j$ reuses channel of the CU $i \in \Pi _{j}$ , e.i., $x_{ji}=1$ , we consider the power allocation problem for CU $i$ and D2D pair $j$ .

$$\begin{align}&{\mathop {\mathrm{ maximize}}\nolimits }~T_{ij}=\gamma W\log \left ({ {1 + \frac {P_{j}^{d}h_{j}^{d}}{{N_{0} + P_{i}^{c}h_{ij}^{c}}}} }\right ) \notag \\&\hphantom {{\mathop {\mathrm{ maximize}}\nolimits }~} + \left ({ {1 - \gamma } }\right )W\log \left ({ {1 + \frac {P_{j}^{d}h_{j}^{d}}{{N_{0} + P_{i}^{B}h_{Bj}^{c}}}} }\right ) \\&\text {subject to}~\frac {P_{i}^{c}h_{i}^{c}}{{N_{0} + P_{j}^{d}h_{jB}^{d}}} \ge g_\gamma ^{UL} \\&\hphantom {{\mathop {\mathrm{ maximize}}\nolimits }~}\frac {P_{i}^{B}h_{i}^{c}}{{N_{0} + P_{j}^{d}h_{ji}^{d}}} \ge g_\gamma ^{DL} \quad \forall i\in C \\&\hphantom {{\mathop {\mathrm{ maximize}}\nolimits }~} P_{i}^{d} \le P_{\max }^{d}; {} P_{i}^{c} \le P_{\max }^{c}\quad \forall i\in C,~d\in D.\notag \end{align}$$

To maximize the objective function (9), we need to increase $P_{j}^{d}$ and decrease $P_{i}^{c}$ , $P_{i}^{B}$ as much as possible. The optimal point is achieved when the constraints in (10), (11) take equalities. Thus, we have

$$\begin{align} P_{i}^{*c}=&\frac {{g_\gamma ^{UL}}}{h_{i}^{c}}\left ({ {N_{0} + P_{j}^{d}h_{jB}^{d}} }\right ) \notag \\ P_{i}^{*B}=&\frac {{g_\gamma ^{UL}}}{h_{i}^{c}}\left ({ {N_{0} + P_{j}^{d}h_{ji}^{d}} }\right ). \end{align}$$

Substituting (12) into the objective function (9), we have

$$\begin{align}&\hspace {-1pc}\gamma W\log \left ({ {1 + \frac {h_{j}^{d}}{{\frac {N_{0}}{P_{j}^{d}}\left ({ {1 + \frac {{g_\gamma ^{UL}h_{ij}^{c}}}{h_{i}^{c}}} }\right ) + \frac {{g_\gamma ^{UL}h_{jB}^{d}h_{ij}^{c}}}{h_{i}^{c}}}}} }\right ) \notag \\&+ \left ({ {1 - \gamma } }\right )W\log \left ({ {1 + \frac {h_{j}^{d}}{{\frac {N_{0}}{P_{j}^{d}}\left ({ {1 + \frac {{g_\gamma ^{DL}h_{Bj}^{c}}}{h_{i}^{c}}} }\right ) + \frac {{g_\gamma ^{DL}h_{ji}^{d}h_{Bj}^{c}}}{h_{i}^{c}}}}} }\right )\!. \notag \\ {}\end{align}$$

Since the objective function (13) is monotonically increasing with $P_{j}^{d}$ , the maximum of the objective function is obtained by setting the transmission power of D2D pair $j$ as high as possible. From the figure 2, we have

$$\begin{equation} P_{j}^{*d} = \min \left \{{ {P_{\max }^{d},{y_{C}},{y_{D}}} }\right \}\!. \end{equation}$$ From equations (9), (12), and (14), we can calculate the optimal transmit powers of UEs, eNB and optimal throughput $T_{ij}$ of D2D pair $j$ under channel $i$ .

C. Channel Assignment for D2D Pair

Now, we find the optimal assignment for D2D pair $j$ and CU $i$ to maximize total throughput of all D2D pairs.

$$\begin{align}&{\max _{{x_{ji}}}}~\sum \limits _{j \in D} {\sum \limits _{i \in {\Pi _{j}}} {{x_{ji}}{T_{ji}}}} \notag \\&\text {subject to} \notag \\&\hphantom {{\mathop {\mathrm{ subject to}}}~}\sum \limits _{i \in {\Pi _{j}}} {{x_{ji}}} \le q_{j}\notag \\&\hphantom {{\mathop {\mathrm{ subject to}}}~}\sum \limits _{j \in D} {{x_{ji}}} \le 1\notag \\&\hphantom {{\mathop {\mathrm{ subject to}}}~}{x_{ji}} = \{ 0,1\}. \end{align}$$ This assignment problem can be optimally solved by using global optimization algorithms such as branch-and-bound, brute search. However, they require huge centralized computations at the eNB and the complexity grows exponentially with the increasing of the number of UEs. To overcome this, we propose the efficient algorithm to find the channel assignment in distributed manner and low complexity.

We observe that all CUs and D2D pairs form two sets, and each element in D2D set wants to match with other elements in CU set to maximize its throughput. Therefore, we apply the one-to-many matching approach to solve the problem (15).

We consider the one-to-many matching problem $F< D, C,\left \lbrace{ T_{ji}}\right \rbrace _{j \in D; i\in C}, \left \lbrace{ q_{j} }\right \rbrace _{j\in D} >$ , where $D$ , $C$ are the set of D2D pairs and CUs, $T_{ji}$ is the throughput when D2D pair $j$ is matching with CU $i$ , $\left \lbrace{ q_{j} }\right \rbrace$ is the reused channel quota for D2D pair $j$ .

Definition 1 ( Matching):

A matching $F$ is from the set $D$ into the set $C$ such that for each CU $i \in F(j)$ if and only if $F^{-1}(i)=j$ and for all $j\in D$ , we have $\left |{ F(j) }\right | \le q_{j}$ , where $F^{-1}$ is an inverse matching of $F$ .

Definition 2 (Stable Matching):

A matching $F$ is stable if for every D2D pair $j$ and CU $i$ satisfies $i \notin F(j)$ , then if $T_{jF(j)}\leq T_{ji}$ , there exists D2D pair $j^{'}$ such that $i \in F(j^{'})$ and $T_{j^{'}i}\geq T_{ji}$ . In other word, if a matching $F$ is stable, no D2D pair or CU can do better by unilaterally changing its matching, i.e. changing its matching while others are fixed.

Next, we propose the Algorithm 1 based on the Gale-Shapley method [24] to obtain the stable matching in distributed manner. Each D2D pair $j$ proposes to match with their preferred CU $i^{*}$ in the admission set (line 3). If the CU is not assigned to other D2D pairs, it will match with the proposed D2D pair (line 4,5). Otherwise, the CU determines if it prefers the proposed D2D pair over the D2D pair it is current matching $j^{'}$ by comparing the utility (line 6-8). If the CU prefers the proposed D2D pair $j$ , they become matching, while the other D2D pair $j^{'}$ removes CU $i^{*}$ from its matching set (line 9,10). Otherwise, the CU $i^{*}$ still matches with its current D2D pair $j^{'}$ . Finally, we update the admission set of the D2D pair $j$ by removing the proposed CU $i^{*}$ (line 14). The algorithm executes until the quotas of all D2D pairs are exceeded or the admission sets of all D2D pairs are empty (line 2).

Algorithm 1 Distributed Stable Matching for D2D Pair

1:

Initialize all CUs and D2D pair to be free.

2:

while There exists a D2D pair $j$ such that $|F(j)|< q_{j}$ and $\Pi _{j} \neq \emptyset$ do

3:

$i^{*}=\arg \max _{i\in \Pi ^{d}_{j}} T_{ji}$

4:

if CU $i^{*}$ is still unmatching: $F^{-1}(i^{*})=\varnothing$ then

5:

Match D2D pair $j$ to CU $i^{*}$ : $F(j)=i^{*}$

6:

else

7:

CU $i^{*}$ is matching to $j^{'}$ : $F(j^{'})=i^{*}$

8:

if $T_{ji^{*}} > T_{j^{'}i^{*}}$ then

9:

Match D2D pair $j$ to CU $i^{*}$ : $F(j)=i^{*}$

10:

Remove CU $i^{*}$ from matching set of D2D pair $j^{'}$ : $F(j^{'})=F(j^{'}) \backslash i^{*}$

11:

else

12:

Keep matching D2D pair $j^{'}$ to the CU $i^{*}$

13:

end if

14:

Remove $i^{*}$ from $\Pi _{j}$

15:

end if

16:

end while

Remark 1:

The stable matching generated by algorithm 1 is locally optimal,i.e., all D2D pairs can not increase their throughput unilaterally.

Remark 2:

Each D2D pair proposes at most $\Pi _{m}$ times, where $\Pi _{m}=\max _{j\in D} \left |{ \Pi _{j}}\right |$ . Therefore, at most $D\Pi _{m}$ rounds, all D2D pairs converge to the stable matching. Moreover, many D2D pairs might propose to the CU simultaneously if their admission regions are not overlapped. Hence, the number of rounds to converge is usually much less than $D\Pi _{m}$ .

D. Further Discussion

In the remaining of this section, we analyze some properties of the Algorithm 1. Firstly, we derive the uniqueness of the stable matching by the Lemma 1.

Lemma 1 (Uniqueness of the Stable Matching):

Given throughput matrix $T=\left \lbrace{ T_{ji}}\right \rbrace$ in which all the elements are different, the algorithm 1 yields the unique stable matching.

Proof:

We prove this by induction. In case of $C=1$ , the result is trivial because the CU will match with the D2D pair who has the highest throughput. Assume that the result is true with $C\geq 1$ , we now proof that it still holds for $C+1$ .

Let $T_{j^{*}i^{*}}$ be the biggest element in $T$ . Obviously, if $F_{S}$ is the stable matching for $T$ , then $i^{*} \in F_{S}(j^{*})$ . Furthermore, from the algorithm 1, $F_{S}\setminus \left \lbrace{ j^{*},i^{*}}\right \rbrace$ is a stable matching for $T^{'}$ , where $T^{'}$ is the matrix $T$ after removing column $i^{*}$ . By induction, since there exists unique stable matching $F_{S}^{'}$ for matrix $T^{'}$ , the stable matching for matrix $T$ is also unique and calculated as $F_{S}=F_{S}^{'}\cap \left \lbrace{ j^{*},i^{*}}\right \rbrace$ .

Optimality of the Algorithm: We analyze the performance of the Algorithms 1 and the optimal matching by the Lemma 2.

Lemma 2 (The Price of Anarchy):

Let F be an arbitrarily matching function of the problem $F< D,C,\left \lbrace{ T_{ji}}\right \rbrace _{j \in D; i\in C}$ , $q >$ and $F_{S}$ be the stable matching by the algorithm 1, then we have

$$\begin{equation} \sum \limits _{\left \{{ {j,i} }\right \} \in {F_{S}}} {{T_{ji}}} \ge \frac {1}{2}\sum \limits _{\left \{{ {ji} }\right \} \in F} {{T_{ji}}}. \end{equation}$$

Proof:

The proof is given in the Appendix.

According to the Lemma 2, the ratio of the throughput under Algorithms 1 to the optimal matching is $\frac {1}{2}$ . In addition, when $q \ge \Pi _{m}$ , the stable matching $F_{S}$ is optimal. The reason is that each D2D pair $j$ proposes to every CU in its admission set since its quota $q_{j} \ge \Pi _{j}$ . The CU accepts the proposal if it gives the highest throughput to D2D pair $j$ by comparing with other D2D pairs. Therefore, the stable matching leads to the maximum sum combination of throughput of all D2D pairs.

Computational Complexity: The complexity of the proposed algorithm is the complexity to calculate the admission set $\Pi$ , the transmit power for UEs, and the channel assignment. To obtain the admission set, we need to check the inequality (6)–(8) for each D2D pairs and CUs. Therefore, the complexity is $O(CD)$ to check all possibilities. Similarly, the transmit power allocation needs to solve two linear equations (12), (14) for each D2D pair and CU. The complexity of the power allocation is also $O(CD)$ . The complexity of channel assignment in Algorithm 1 is $O(CD\log (C))$ , where $O(\log (C)$ is the complexity by using the binary search to find the prefer CU for each D2D pair (line 2, Algorithm 1). In consequence, the computational complexity of our algorithm is polynomial time $O(CD\log (C))$ .

Message Passing: The Fig. 3 illustrates the procedure of the proposed interference management algorithms. At first, the eNB collects channel gain from all UEs and broadcasts these information to the D2D pairs. Since all the UEs are under the control of the eNB in LTE system, it is natural that the channel gain information can be obtain at the eNB. This process can be done during the special sub-frame period [25]. Then, each D2D pair $j$ determines the admission set $\Pi _{j}$ , the transmit power, and the throughput $T_{ij}$ as in section IV-A and section IV-B without additional exchange messages. After that, the D2D pair executes Algorithm 1 to find the CU that shares the same channel with.

FIGURE 3.

The procedure of the proposed interference management.

During the execution of the Algorithm 1, each D2D pair $j$ sends the one bit message to the CU $i^{*}$ (line 2). The CUs feedback to the D2D pair by sending one bit message to indicate acceptance or rejection. Therefore, in the worst case, the number of additional exchanged bits between D2D pair and CU during Algorithms 1 is $2CD$ bits.

SECTION V. Performance Evaluation

In this section, we conduct the simulation to verify the optimality of the proposed algorithm and to compare with few existing algorithms under different performance criteria. We implement the following algorithms for comparison

• Heuristic-based algorithm (HBA) assigns the CU to the D2D which has the lowest interference gain to the CU. In this algorithm, each D2D pair is assigned to only one CU. We also apply the power control in section IV-B for each CU and D2D pair.

• Uplink-based algorithm (UBA) [10] is the variant of our algorithm. Since only considering the UL phase, the UBA constructs the admission set of the D2D pair without considering the constraint (8). Therefore, more D2D pairs and CUs can coordinate in UL phase. We apply our algorithm to assign the channel and allocate the transmit power in UL phase.

  In the DL phase, the UBA allocates maximum transmit power for both D2D communication and cellular communication. If the throughput of CU is violated, the eNB stops sharing the channel with D2D pair in DL phase.

We consider the random network topology where the CUs and D2D pairs are uniformly distributed in the circular cell with radius 500m. The number of the CUs is 30. The maximum distance between the transmitter and receiver in a D2D pair is 20m. The bandwidth of the system is 5 MHz and divided into 25 channels of 180 KHz. The eNB determines the set of active CU at each time slot based on the proportional fair scheduling.

The channel gain includes three components as ${h} = PL{\xi }{\zeta }$ , where $P{L}$ being a path loss related to the type of communication (D2D communication or cellular communication), $\xi$ being a lognormal shadow fading variable $10\log \xi \sim {\mathrm{ N}}\left ({ {0,\sigma _{sd}^{2}} }\right )$ , and $\zeta$ being the fast fading channel followed the independent complex Gaussian distribution $\zeta \sim CN\left ({ {0,1} }\right )$ . The main simulation parameters are listed in the Table 2

TABLE 2 Simulation Parameter

A. Convergence of the Proposed Algorithm

We verify the optimality of our algorithm by investigating the throughput of D2D pair over 50 iterations. We set the number of D2D pairs to 10. For the comparison, we implement the algorithm based on graph theory to obtain the optimal solution of the assignment problem [26]. The evolution of the D2D throughput is given in the Fig. 4. After almost 30 iterations, our algorithm converges to the stable point. The throughput of D2D pair exceeds 50% of the optimal throughput. These results are consistent with our discussion in Lemma 1 and Lemma 2.

FIGURE 4.

Convergence of the Algorithms 1.The dot lines represent the optimal solution in each case.

Beside, our proposed algorithm performs close to the optimal one when the quota is large. Especially, when the quota is equal to the number of channels ($q=25$ ), our algorithm achieves exactly optimal assignment. However, there is a trade-off between the optimality and the convergence speed: more quotas impose more proposals at the D2D pair to reach the convergence point. In the remaining paper, we set the quota to 5.

B. Impact of the Fraction of UL time

Fig. 5 investigates the throughput and the admission rate of D2D pairs under three algorithms. The admission rate is the ratio between the number of D2D pairs allowed to share channel with CUs and the number of D2D pairs. There are two interesting features from the result. First, by comparing both figures, we observe that even the UBA admits more D2D pairs than our algorithm, its throughput is still lower than our method. The reason is that our algorithm carefully considers the reused channel in both UL and DL to reduce the violated CUs and provide more spectrum for D2D communication. The admission set is smaller than that of the UBA, which considers only the uplink phase. However, in our proposed algorithm, the D2D pair always transmits in both UL and DL phases.

FIGURE 5.

Impact of the fraction of UL phase to the system performance, $R_{min}^{UL}= R_{min}^{DL}= 1Mbps$ , $|D|= 16$ . (a) Throughput of the D2D pair. (b) Addmission rate of the D2D pair.

Second, the results also suggest that the fraction time of UL phase should set from 0.4 to 0.6 to maximize the throughput of the D2D and the number of admitted D2D pairs. If the fraction of UL phase is too small (or too big), the transmission rate of the CU is small in UL phase (or DL phase). The D2D pair might not be able to reuse the channel of the CU without violating throughput requirement of CU.

C. Impact of the Number Of D2D Pairs

Since the throughput strongly depends on the number of D2D pairs, we evaluate the performance of these algorithms under different number of D2D pairs. We set the number of D2D pairs from 4 to 25 and measure the throughput and admission rate of D2D pairs as in Fig. 6. Obviously, the throughput increases with the increasing of the number of D2D pairs. However, there exists a saturated point for these algorithms. If the number of D2D pairs is larger than 20 pairs, the throughput of D2D pair almost the same regardless the number of D2D pairs. This behavior also has been illustrated in [10].

FIGURE 6.

Impact of the number D2D pair to the system performance, $R_{min}^{UL}= R_{min}^{DL}= 1Mbps$ . (a) Throughput of the D2D pair. (b) Addmission rate of the D2D pair.

Contrary to the previous scenarios, the throughput does not increase proportionally to the admission rate of D2D pair: the throughput increases while the admission rate decreases. Because in our algorithm, the D2D pair is allowed to reuse channel with multiple CUs if this assignment can provide high throughput to the D2D. Other D2D pairs might not have available CUs to share the channel, especially when the number of D2D pairs is large. Thus, by letting the D2D pairs more freedom to reuse channel of multiple CUs, the proposed algorithm provides more throughput, but reduces the number of admitted D2D pairs.

Beside, our algorithm can significantly improve the throughput of D2D pairs when the number of D2D user is small. It can increase the throughput by 63 % when the number of D2D pairs is 7 and 14% when the number of D2D pairs is 25. This gain depends on the value of the quota $q$ as we explain in Lemma 2 and Fig. 4.

D. Impact of the QoS CU

We set the fraction time for UL equal to 0.5 and vary the throughput requirement for each CU from 100 Kbps to 900 Kbps. As in Fig. 7, the throughput of D2D pair and the admission rate are decreased with the increasing the throughput requirement of CU. Since the transmit power of the CU is increased to guarantee its throughput requirement, the CU generates more interferences to its reused D2D pair. Therefore, it limits the number of admitted D2D pair.

FIGURE 7.

Impact of the throughput requirement of CUs to the system performance. (a) Throughput of the D2D pair. (b) Addmission rate of the D2D pair.

The admission rate of the ULB is the same with the HBA and is higher than our proposed algorithm. This is because the ULB considers the throughput requirement in only UL. As a result, more D2D pairs are allowed to share channel with CU. However, since both eNB and D2D pairs transmit at the maximum power during the DL phase, the throughput of D2D pair under ULB is degraded.

E. Power Consumption

We vary the throughput requirement of each CU and evaluate the power consumption of the networks. The power consumptions of the CUs and eNB are lower than other algorithms as in Fig. 8. It implies that the proposed algorithm does not significantly affect to the power consumption of the existing cellular communication like other algorithms: the CU does not need to increase its transmit power to combat the interference from D2D pairs. On the contrary, the D2D pairs need to increase their power carefully to maximize their throughput and to not violate the performance of the CU. In consequence, our algorithm can increase the throughput of the D2D pair while still does not affect to the operation of the existing CUs.

FIGURE 8.

Power consumption of the UEs an eNB under different algorithms. (a) Average transmit power of the CU. (b) Average transmit power of the eNB. (c) Average transmit power of the D2D pair.

SECTION VI. Conclusion

D2D communications underlaying cellular networks are considered one of the promising technique to improve the throughput of the current mobile networks. Interference management is one of the key to control the performance of the D2D communication. We propose here the interference management algorithm that includes admission control, power allocation and channel assignment to improve the performance of D2D communication while guaranteeing the performance of existing cellular networks. The D2D pair can reuse channels of multiple CUs to improve the throughput of D2D communication. Simulation results highlight the effectiveness of these features to improve the D2D throughput and guarantee the performance of the CU.

We now investigate the scenarios in which the CUs are allowed to share channel with multiple D2D pairs. In particular, the CUs need to limit the set of potential D2D pairs that can share the channel simultaneously. This approach will require huge computation at the eNBs if we check all possibilities as in our algorithm.

Appendix Proof of Lemma 2

We consider the matching problem $F< D,C,\left \lbrace{ T_{ji}}\right \rbrace _{j \in D; i\in C}, \left \lbrace{ q }\right \rbrace >$ . We prove Lemma 2 by induction.

For given arbitrary $D$ , the proof is trivial when $C=1$ , since the CU will be matched with the D2D pair which yields highest throughput. Suppose that the inequality (16) holds for $C\geq 1$ , now we prove that it also holds for $C+1$ . Let $T_{j^{*}i^{*}}$ be the largest element in the matrix $T$ . We also denote $T^{'}$ by the matrix $T$ after removing column $i^{*}$ . Notice that since $T^{'}$ is the $D\times (C)$ matrix, the inequality (16) also holds.

Obviously, we have $i^{*} \in F_{S}(j^{*})$ . Consider an arbitrarily matching $F$ . We have two cases. First, if $i^{*} \in F(j^{*})$ , it follows that

$$\begin{align*} \sum \limits _{\left \{{ {j,i} }\right \} \in {F_{S}}} {{T_{ji}}}=&{T_{j^{*}{i^{*}}}} + \sum \limits _{\left \{{ {j,i} }\right \} \in {F_{S}^{'}}} {{T_{ji}}}\\\ge&\frac {1}{2}\left ({ {T_{j^{*}{i^{*}}}} + \sum \limits _{\left \{{ {i,j} }\right \} \in {F^{'}}} {{T_{ji}}}}\right ) \\=&\frac {1}{2}\sum \limits _{\left \{{ {j,i} }\right \} \in F} {{T_{ji}}} \end{align*}$$ where $F^{'}$ and $F_{S}^{'}$ are the arbitrarily matching and stable matching of the matching $F$ after removing CU $i^{*}$ .

Second, if $i^{*} \notin F(j^{*})$ , then there are at most two other matching pairs in $F$ that belong to the column and row of pair $\left ({j^{*}, i^{*} }\right )$ . From the definition of pair $\left \lbrace{ j^{*},i^{*} }\right \rbrace$ , $2T_{j^{*}i^{*}}$ is greater than their sums. It follows that

$$\begin{align*} \sum \limits _{\left \{{ {i,j} }\right \} \in {F_{S}}} {{T_{ji}}}=&{T_{j^{*}{i^{*}}}} + \sum \limits _{\left \{{ {j,i} }\right \} \in {F_{S}^{'}}} {{T_{ji}}}\\\ge&\frac {1}{2}\left ({ {{T_{{F^{ - 1}}\left ({ {i^{*}} }\right ){i^{*}}}} + \sum \limits _{i \in F\left ({ {j^{*}} }\right )} {{T_{j^{*}i}}} + \sum \limits _{\left \{{ {i,j} }\right \} \in {F^{'}}} {{T_{ji}}}} }\right ) \\=&\frac {1}{2}\sum \limits _{\left \{{ {j,i} }\right \} \in F} {{T_{ij}}}. \end{align*}$$