Subchannel and Power Allocation for D2D Communication in mmWave Cellular Networks

1. Introduction

RECENTLY , the volume of local data traffic is explosively growing due to various emerging technologies such as Internet of Things (IoT), autonomous car, virtual reality (VR), augmented reality (AR), ultra high definition (UHD) broadcasting, etc. Furthermore, due to the proliferation of mobile devices such as smartphones, tablets, etc., mobile data traffic also increases dramatically. To meet such high demands, 5G systems should achieve very high spectral efficiency and data rates.

Device-to-device (D2D) communication is a promising technology to meet 5G requirements [1]–[7]. Because a D2D transmitter communicates with its intended D2D receiver without going through a base station (BS), D2D communication can improve spectrum utilization, reduce transmission delay, and offload data traffic from the BS. D2D communication becomes a key technology for 5G due to its various advantages. It has been adopted in the 3rd Generation Partnership Project (3GPP) standard since Release 12.

In a cellular network with underlaid D2D communication, D2D users are allocated the spectrum already allocated to the cellular users, which causes mutual interference between D2D and cellular communication. To reduce the mutual interference, resource allocation, such as subchannel and power allocation, is effective.

Resource allocation, which manages interference to improve performance of users, has been widely studied for a cellular network with underlaid D2D communication. In [8], a subchannel allocation scheme is proposed and a low complexity spectrum access scheme for D2D users is also proposed. In [9], subchannel and power allocation schemes for full-duplex D2D communication are proposed under perfect channel state information (CSI) and statistical CSI scenarios. In [10], a subchannel and power allocation scheme is proposed, and allows D2D users to be allocated multiple subchannels to improve the sum rate. In [11], a subchannel allocation scheme is proposed, and allocates either licensed or unlicensed bands to D2D users to increase system capacity.

Allocating millimeter wave (mmWave) spectrum is a way of improving performance of D2D communication [6], [12], [13]. Though there is a lot of free spectrum in mmWave bands, it has not been used in the conventional communication due to vulnerability to blocking of mmWave signals [14]–[16]. The vulnerability in mmWave communication leads to very poor performance, especially when the communication link is in the non line-of-sight (NLOS). Apart from this, this characteristic of mmWave signals brings advantages in D2D communication. Since the distance of the link between a D2D transmitter and its intended receiver is generally short, the probability of the link being in the line-of-sight (LOS) is high, resulting in high signal power at the D2D receiver [14]. Interference from other D2D transmitters and cellular users can be also reduced at receivers due to the vulnerability of mmWave signals. As a result, the signal-to-interference-plus-noise ratio (SINR) at each receiver can be improved.

Recently, a lot of research on using mmWave for D2D communication is introduced. In [17]–[19], performance of mmWave D2D communication, such as coverage probability, spectral efficiency, and energy efficiency, is studied. In [20]– [22], mmWave networks with D2D relays are studied to improve their connectivity and coverage. In [23]–[26], scheduling of D2D users in mmWave networks is investigated in the perspective of spectral efficiency and energy efficiency.

ThoughmmWave D2D communication has been widely studied, there are few works on resource allocation for D2D communication in mmWave cellular networks. In [27], a relay selection and power allocation scheme is studied for full-duplex relayassisted D2D communication in a mmWave cellular network. In [28], a power control strategy for D2D pairs and a resource management scheme for cellular users are studied for a multitier heterogeneous network (HetNet) consisting of microwave and mmWave BSs. To the best of our knowledge, there is no existing work dealing with subchannel and power allocation for D2D communication in mmWave cellular networks. Since a mmWave channel model is different from the existing models, a new resource allocation is necessary to improve performance.

In this paper, we investigate resource allocation for D2D communication in a mmWave cellular network consisting of a single BS, multiple cellular users, and multiple D2D transmitterreceiver pairs. We propose two heuristic algorithms which allocate subchannels to D2D transmitters and find the optimal transmit power of each D2D device to maximize their sum rate. The contributions of this paper are as follows:

We formulate the optimization problem of subchannel and power allocation to maximize the sum rate of D2D transmitters in a mmWave environment. To solve the problem efficiently, we divide it into two subproblems of subchannel allocation and power allocation.

Assuming global CSI is available, i.e., impractical, we propose a heuristic subchannel allocation scheme based on the greedy algorithm as a reference scheme. Then for practical consideration, we assume that only the location of each node is available at the BS. To solve the reformulated subchannel allocation problem, we propose a heuristic subchannel allocation scheme based on a max k-cut problem and Hungarian algorithm.

To maximize the sum rate, the BS finds the optimal transmit power for each D2D transmitter by using a difference of convex (DC) programming. For the given non-convex power allocation problem, we transform it into a convex problem and solve the problem repeatedly.

Extensive simulation results under various system parameters show performance improvement of the proposed subchannel allocation schemes and the optimal power allocation scheme compared to the random subchannel allocation scheme and the equal power allocation scheme.

The rest of this paper is organized as follows. We describe the system model of a mmWave cellular network with underlaid D2D communication and formulate the optimization problem of subchannel and power allocation in Section II. We propose two heuristic algorithms for subchannel allocation in Section III. Then we propose an algorithm for obtaining the optimal transmit power of each D2D transmitter in Section IV. Simulation results are shown in Section V, followed by the conclusions in Section VI.

II. SYSTEM MODEL

Consider an uplink mmWave cellular network with a BS, denoted by b, and K cellular users, each denoted by [TeX:] $$\mathcal{K}=\{1, \cdots, K\},$$ in a single cell with radius R, where I D2D transmitter-receiver pairs, each denoted by [TeX:] $$t_{i}-r_{i}, i \in \mathcal{I}=\{1, \cdots, I\},$$ are underlaid. Assume that the BS is located at the center of the cell, the cellular users and the D2D transmitters are uniformly located in the cell, and [TeX:] $$r_{k}$$ is uniformly located at a distance [TeX:] $$d_{k} \text { from } t_{k}.$$

Suppose that the whole spectrum is divided into N subchannels, each with bandwidth B. [TeX:] $$\text { Let } \mathcal{N}=\{1, \cdots, N\}$$ denote the set of subchannels. Assume a simple case that the number of the cellular users and that of subchannels are the same, i.e., K = N. Also assume that a different subchannel is allocated to each cellular user and, without loss of generality, subchannel [TeX:] $$n, n \in \mathcal{N},$$ is allocated to cellular user [TeX:] $$c_{n}.$$ Suppose that the BS allocates a single subchannel to each D2D transmitter. Let [TeX:] $$\rho_{i}^{(n)}, i \in \mathcal{I},$$ denote the allocation indicator for D2D transmitter [TeX:] $$t_{i}$$ on subchannel n, i.e.,

A. Path Loss Model

We define the LOS probability function [TeX:] $$p_{x, y}^{\mathrm{L}}$$ as the probability of the link between node [TeX:] $$x, x \in\left\{c_{1}, \cdots, c_{K}, t_{1}, \cdots, t_{I}\right\},$$ and node [TeX:] $$y, y \in\left\{b, r_{1}, \cdots, r_{I}\right\},$$ being in the LOS. Assume the stochastic blockage model, where blockages are modeled as a rectangle Boolean scheme, then the LOS probability between node x and node y is given by [14], [29]

where [TeX:] $$d_{x, y}$$ is the distance between node x and node y, and " is the parameter determined by the density and the average size of blockages, where the average LOS range is calculated as [TeX:] $$\sqrt{2} / \varepsilon.$$ The path loss from node x to node y is given by [15]

where [TeX:] $$C_{\mathrm{L}} \text { and } C_{\mathrm{N}}$$ are the intercepts of LOS and NLOS path loss functions, and [TeX:] $$\alpha_{\mathrm{L}} \text { and } \alpha_{\mathrm{N}}$$ are LOS and NLOS path loss exponents, respectively.

B. Beamforming Model

Suppose that node [TeX:] $$x, x \in\left\{b, c_{1}, \cdots, c_{K}, t_{1}, \cdots, t_{I}, r_{1}, \cdots, r_{I}\right\}$$ has a uniform planar square antenna array with directional beamforming applied [30]. The antenna gain of node x on subchannel [TeX:] $$n, n \in \mathcal{N}$$ is given by a function of off-boresight angle [TeX:] $$\theta_{x} \in(-\pi, \pi]$$ as

where [TeX:] $$M_{x} \text { and } m_{x}$$ are the main-lobe and side-lobe antenna gains of node x, respectively, and [TeX:] $$w_{x}$$ is the half-power beamwidth of node x. Suppose that the beam of each transmitter is directed toward its intended receiver, and vice versa. Since the beam direction of each D2D transmitter is fixed regardless of the subchannel allocation, the antenna gain of each D2D transmitter is the same for all subchannels, i.e.,

and it is the same for all the receivers.

C. Small-scale Fading Model

In mmWave networks, the Rayleigh fading model is not suitable when directional beamforming is applied [31]. Therefore, we assume independent Nakagami fading for each link with the fading parameters [TeX:] $$\nu_{\mathrm{L}} \text { and } \nu_{\mathrm{N}}$$ for LOS and NLOS paths, respectively. Let [TeX:] $$h_{x, y}^{(n)}$$ denote the small-scale fading coefficient from node [TeX:] $$x, x \in\left\{c_{1}, \cdots, c_{K}, t_{1}, \cdots, t_{I}\right\},$$ to node y, [TeX:] $$y \in\left\{b, r_{1}, \cdots, r_{I}\right\},$$ on subchannel [TeX:] $$n, n \in \mathcal{N}.$$ Then we can compute the variance of [TeX:] $$h_{x, y}^{(n)},$$ containing the effect of beamforming as

Since the antenna gains of each transmitter and receiver are the same for all subchannels, their channel variances are also the same for all subchannels, i.e.

D. Achievable Rate of a D2D Transmitter

Let [TeX:] $$P_{c_{n}} \text { and } P_{t_{i}}$$ denote the transmit power of cellular user [TeX:] $$c_{n}, n \in \mathcal{N},$$ and D2D transmitter [TeX:] $$t_{i}, i \in \mathcal{I},$$ respectively. When transmitter [TeX:] $$t_{i}$$ is allocated subchannel n, the SINR of receiver [TeX:] $$r_{i}$$ is given by

where the first and second terms in the denominator of the right hand side (RHS) are the interference from cellular user [TeX:] $$c_{n}$$ and other D2D transmitters, respectively, and [TeX:] $$\sigma^{2}$$ is the noise variance and assumed to be the same for all subchannels. The achievable rate of D2D transmitter [TeX:] $$t_{i}$$ on subchannel n is given by

E. Optimization Problem Formulation

We formulate an optimization problem of subchannel and power allocation to maximize the sum rate of the D2D transmitters as

where [TeX:] $$\rho=\left[\rho_{1}^{(1)}, \cdots, \rho_{I}^{(N)}\right], \mathbf{P}=\left[P_{t_{1}}, \cdots, P_{t_{l}}\right], P_{\max }$$ is the maximum transmit power of each D2D transmitter and supposed to be the same for all D2D transmitters, and [TeX:] $$I_{\mathrm{th}}$$ is the interference constraint at the BS and supposed to be the same for all subchannels. The constraint (10a) indicates that each D2D transmitter is allocated a single subchannel. The constraint (10b) indicates the power constraint of the D2D transmitters. The constraint (10c) indicates the interference constraint such that interference from D2D transmitters at the BS should be lower than the interference threshold [TeX:] $$I_{\mathrm{th}}$$ on each subchannel.

We can see that [TeX:] $$\mathcal{P} 1$$ is a mixed integer programming problem, which is known to be NP-hard [32]. To handle the problem, we divide it into two subproblems that are the subchannel allocation problem and the power allocation problem. We allocate subchannels to help maximizing the sum rate, and then, allocate power to maximize the sum rate while satisfying the power and interference constraints. In the following, we first propose heuristic subchannel allocation algorithms that operate at the BS in Section III, and find the optimal transmit power for each D2D transmitter for the given subchannel allocation in Section IV.

III. SUBCHANNEL ALLOCATION

A. Problem Formulation

Suppose that the transmit power of each D2D transmitter is given. We formulate the subchannel allocation problem that aims to maximize the sum rate of the D2D transmitters as

Note that [TeX:] $$\mathcal{P} 2$$ is also NP-hard and the computational complexity of the brute-force search is [TeX:] $$\mathcal{O}\left(N^{I}\right),$$ which is too high to obtain the solution. Therefore, the algorithm with low computational complexity is necessary to obtain the solution of [TeX:] $$\mathcal{P} 2.$$ In the following subsections, we propose two heuristic subchannel allocation algorithms, namely the greedy max SINR scheme and the minimum interference scheme.

B. The Greedy Max SINR Scheme

To maximize the sum rate of D2D transmitters, their SINR should be maximized. Assume that global CSI is available at the BS, which means that the BS knows the exact channel coefficients between all nodes on each subchannel. We can maximize the SINR of D2D transmitters via a greedy algorithm, which does not guarantee an optimal solution but has low computational complexity, and provides a reasonable solution in most cases [33]. The details of the algorithm are presented as follows.

Let [TeX:] $$\tilde{\mathcal{I}}=\{1, \cdots, I\},$$ which is the set of D2D transmitters not allocated subchannels yet. Set the transmit power of D2D transmitter [TeX:] $$t_{i}, \forall i \in \mathcal{I},$$ on subchannel [TeX:] $$n, \forall n \in \mathcal{N},$$ as large as possible according to the constraints (10b) and (11b) ignoring the interference from other D2D transmitters, i.e., [TeX:] $$P_{t_{i}}^{(n)}=\min \left\{P_{\max }, I_{\mathrm{th}} /\left|h_{t_{i}, b}^{(n)}\right|^{2}\right\}.$$ Calculate the SNR of each D2D receiver on each subchannel. Since no D2D transmitter is allocated a subchannel in this step, there is no interference from other D2D transmitters. After setting up, do the following procedures. Find the largest SINR, and select the corresponding D2D transmitter [TeX:] $$t_{i^{*}}$$ and subchannel [TeX:] $$n^{*}.$$ Allocate subchannel [TeX:] $$n^{*}$$ to D2D transmitter [TeX:] $$t_{i^{*}}$$ and eliminate [TeX:] $$i^{*}$$ in set [TeX:] $$\tilde{\mathcal{I}}.$$ Update the SINR of D2D receiver [TeX:] $$r_{i}, \forall i \in \tilde{\mathcal{I}},$$ on subchannel [TeX:] $$n^{*}$$ considering the interference from the other D2D transmitters allocated subchannel [TeX:] $$n^{*}.$$ Repeat this procedure until set [TeX:] $$\tilde{I}$$ becomes empty, i.e., all D2D transmitters are allocated subchannels. The pseudo code format of the algorithm is shown in Algorithm 1.

Algorithm 1 performs an initialization step and I iteration steps. In the initialization step, it calculates NI SINRs. In the i-th iteration step, it calculates (I - i) SINRs. The total number of SINR calculations in the algorithm is given by [TeX:] $$N I+\sum_{i=1}^{I}(I-i)=N I+\left(I^{2}-I\right) / 2.$$ Since [TeX:] $$I \geq N,$$ the computational complexity of the algorithm becomes [TeX:] $$\mathcal{O}\left(I^{2}\right),$$ which is much lower than that of the brute-force search.

C. The Minimum Interference Scheme

In the greedy max SINR scheme, we assumed that global CSI is available at the BS. Because the assumption of global CSI causes enormous feedback overhead, we now assume that only the location of each node is available at the BS via the global positioning system (GPS) [34]. Although the BS does not know exact channel coefficients, it can calculate the channel variances between all nodes according to their locations. This means we can not use the instantaneous sum rate in [TeX:] $$\mathcal{P} 2.$$

Our new objective function aims to maximize the average sum rate of the D2D transmitters. We can obtain its maximum value when the average interference of each D2D receiver is minimized [8], [35]. Then we can reformulate [TeX:] $$\mathcal{P} 2$$ into a problem that aims to minimize the interference from D2D transmitters to D2D receivers as much as possible by using graph theory.

First, we construct a graph [TeX:] $$G_{1}=\left(\mathcal{I}, E_{1}\right),$$ where [TeX:] $$\{1, \cdots, I\}$$ is the vertex set representing the D2D transmitters and [TeX:] $$E_{1}$$ is the edge set representing the average power of mutual interference between two vertices. The edge set is given by

Note that the average interference power from D2D transmitter [TeX:] $$t_{i}$$ to D2D receiver [TeX:] $$r_{j}, \forall i, j \in \mathcal{I}, i \neq j,$$ is [TeX:] $$P_{t_{i}} \Omega_{t_{i}, r_{j}}.$$ If the transmit power of each D2D transmitter is set to the same, i.e., [TeX:] $$\forall i, j \in \mathcal{I}, P_{t_{i}}=P_{t_{j}}.$$ the weight of an edge (i, j) representing the mutual interference power between vertices i and j can be expressed as

Note that [TeX:] $$w_{i, j}=w_{j, i}.$$

Next, we partition the vertex set [TeX:] $$\mathcal{I} \text { into } N$$ disjoint subsets, [TeX:] $$\mathcal{I}^{(1)}, \cdots, \mathcal{I}^{(N)}.$$ The BS allocates subchannel [TeX:] $$n, n \in \mathcal{N},$$ to D2D transmitter [TeX:] $$t_{i}, i \in \mathcal{I}, \text { if } i \in \mathcal{I}^{(n)}.$$ To minimize the average interference from D2D transmitters to D2D receivers, we assign the vertices to the subsets such that the sum of the weights of the edges connecting vertices in different subsets is maximized. In other words, we express the objective function of the optimization problem as

Additionally, we consider three more constraints to improve overall performance. First, we try to assign subchannels fairly to D2D transmitters. If subchannels are not fairly allocated to D2D transmitters, sometimes many D2D transmitters can be assigned to one particular subchannel. Then they will be allocated a small transmit power in the power optimization step due to the interference constraint (10c), which results in performance degradation. To prevent this, we add a new constraint of fair allocation as follows:

where [TeX:] $$\lfloor x\rfloor$$ denotes the largest integer less than or equal to x and [TeX:] $$\lceil x\rceil$$ denotes the smallest integer greater than or equal to x.

Second, we use a new interference constraint. Because global CSI is not available at the BS, the interference constraint (11b) is meaningless since it assumes the exact values of channel coefficients. Therefore we consider a new constraint limiting the interference to the BS. In the mmWave network, the BS suffers strong interference when its receive beam toward the interferer is in the main-lobe. To avoid this strong interference, we restrict subchannel [TeX:] $$n, n \in \mathcal{N},$$ to be allocated to D2D transmitter [TeX:] $$t_{i}, i \in \mathcal{I},$$ if the receive beam of the BS on subchannel n toward D2D transmitter ti is in the main-lobe. In this way, we set [TeX:] $$\mathcal{B}_{i}$$ as the set of subchannels restricted to be allocated to [TeX:] $$t_{i}.$$ A constraint of D2D transmitter [TeX:] $$\mathbf{r} t_{i}$$ restricted to be allocated subchannels in [TeX:] $$\mathcal{B}_{i}$$ is given by

If D2D transmitter [TeX:] $$t_{j}, j \in \mathcal{I},$$ is restricted to be allocated all subchannels, i.e., [TeX:] $$\mathcal{B}_{j}=\mathcal{N},$$ it cannot be allocated any subchannel, which conflicts with the constraint (11a). To prevent this, set [TeX:] $$\mathcal{B}_{j}=\emptyset$$ if D2D transmitter [TeX:] $$t_{j}$$ is restricted to be allocated all subchannels.

Third, to avoid strong interference from cellular users to D2D receivers, similar to before, we restrict subchannel [TeX:] $$n, n \in \mathcal{N},$$ to be allocated to D2D transmitter [TeX:] $$t_{i}, i \in \mathcal{I},$$ if the transmit beam of cellular user [TeX:] $$c_{n}$$ toward D2D receiver [TeX:] $$r_{i}$$ is in the main-lobe. In this way, we set [TeX:] $$\mathcal{C}_{i}$$ as the set of subchannels restricted to be allocated to [TeX:] $$t_{i}.$$ A constraint of D2D transmitter [TeX:] $$t_{i}$$ restricted to be allocated subchannels in [TeX:] $$\mathcal{C}_{i}$$ is given by

Similar to the constraint (16), set [TeX:] $$\mathcal{C}_{j}=\emptyset, j \in \mathcal{I}$$ if D2D transmitter [TeX:] $$t_{j}$$ is restricted to be allocated all subchannels.

From the graph [TeX:] $$G_{1}=\left(\mathcal{I}, E_{1}\right)$$ and the new constraints (15), (16), and (17), we reformulate[TeX:] $$\mathcal{P} 2$$ as

where the constraints (18a) and (18b) are equivalent to the constraint (11a) such that each D2D transmitter should be allocated a single subchannel, and the constraint (18d) comes from the constraints (16) and (17).

Since [TeX:] $$\mathcal{P}_{3}$$ is known as NP-hard, solving it directly is inefficient [36]. Thus we try to solve [TeX:] $$\mathcal{P}_{3}$$ in two steps. In the first step, we find groups of the D2D transmitters without considering what subchannels will be allocated to them, i.e., ignoring the constraint (18d). In the second step, we match a subchannel to each group considering the constraint (18d).

Step 1: Let [TeX:] $$\hat{\mathcal{I}}^{(m)}, m \in \mathcal{N},$$ be the group of the D2D transmitters allocated the same subchannel, which can be any subchannel, not necessarily to be m. We formulate the problem of D2D grouping as

We can see that [TeX:] $$\mathcal{P} 4$$ is a capacitated max k-cut problem [37]. Though it is also an NP-hard problem, a near optimal solution can be obtained by a heuristic algorithm with low computational complexity in [37]–[40]. Before presenting the details of the algorithm, we define the sum of the weights of edges connecting a vertex [TeX:] $$i, i \in \mathcal{I},$$ to the vertices in the subset [TeX:] $$\hat{I}^{(m)}$$ as

The details of the algorithm are presented as follows.

Assign vertex [TeX:] $$i, \forall i \in \mathcal{I}, \text { to } \hat{\mathcal{I}}^{(m)}, \forall m \in \mathcal{N},$$ arbitrarily while satisfying the constraint (19c). Determine if there exist a pair of vertices [TeX:] $$i \in \hat{\mathcal{I}}^{(m)} \text { and } j \in \hat{\mathcal{I}}^{(l)}, m, l \in \mathcal{N}, m \neq l,$$ such that

If such a pair of vertices exist, reassign vertex [TeX:] $$i \text { to } \hat{\mathcal{I}}^{(l)}$$ and vertex [TeX:] $$j \text { to } \hat{\mathcal{I}}^{(m)}.$$ Repeat this procedure until there is no pair of vertices satisfying (21). After this, if all subsets do not have the same size, i.e., [TeX:] $$\exists m, l \in \mathcal{N},\left|\hat{\mathcal{I}}^{(m)}\right|>\left|\hat{\mathcal{I}}^{(l)}\right|,$$ we additionally perform vertex movement procedures. For any vertex sets satisfying [TeX:] $$\left|\hat{\mathcal{I}}^{(m)}\right|>\left|\hat{\mathcal{I}}^{(l)}\right|,$$ check whether there exists a vertex [TeX:] $$i \in \hat{\mathcal{I}}^{(m)}$$ such that

If such a vertex exists, reassign vertex [TeX:] $$i \text { to } \hat{\mathcal{I}}^{(l)}.$$ Repeat this procedure until there is no vertex satisfying (22). The pseudo code format of the algorithm is shown in Algorithm 2.

We can obtain a suboptimal solution of [TeX:] $$\hat{\mathcal{I}}^{(m)}, \forall m \in \mathcal{N},$$ via Algorithm 2. The computational complexity of the algorithm is known as [TeX:] $$\mathcal{O}\left(I^{2} \bar{w}_{\mathrm{sum}}\right)$$ in [40], where

and [TeX:] $$\beta=1 / \min _{i, j \in \mathcal{I}, i \neq j} w_{i, j}.$$

Step 2: In this step, we match subchannels [TeX:] $$n, \forall n \in \mathcal{N},$$ to the sets [TeX:] $$\hat{\mathcal{I}}^{(m)}, \forall m \in \mathcal{N},$$ in a one-to-one manner. If the set [TeX:] $$\hat{\mathcal{I}}^{(m)}, m \in \mathcal{N},$$ is matched to subchannel [TeX:] $$n, n \in \mathcal{N},$$ the D2D transmitters in the set [TeX:] $$\hat{\mathcal{I}}^{(m)}$$ will be allocated subchannel n. Let

[TeX:] $$\zeta_{m, n}$$

denote the matching indicator for [TeX:] $$\hat{\mathcal{I}}^{(m)}$$ as follows:

Due to the characteristic of the one-to-one matching, the following two equalities should be satisfied:

We construct a bipartite graph [TeX:] $$G_{2}=\left(U, V, E_{2}\right)$$ to formulate the problem, where [TeX:] $$U=\left\{u_{1}, \cdots, u_{N}\right\} \text { and } V=\left\{v_{1}, \cdots, v_{N}\right\}$$ are disjoint vertex sets representing the group of the D2D transmitters and subchannels, respectively, and [TeX:] $$E_{2}$$ is the edge set where each edge connects a vertex of U to a vertex of V , i.e.,

Let [TeX:] $$\xi_{i}^{(n)}, i \in \mathcal{I}, n \in \mathcal{N},$$ denote the indicator for confining D2D transmitter [TeX:] $$t_{i}$$ to subchannel n, i.e.,

We set the weight of each edge (m, n) as the number of D2D transmitters restricted to be allocated subchannel n in the set [TeX:] $$\hat{\mathcal{I}}^{(m)}$$, i.e.,

To satisfy the constraint (18d), the set [TeX:] $$\hat{\mathcal{I}}^{(m)}, m \in \mathcal{N},$$ is matched to subchannel [TeX:] $$n, n \in \mathcal{N},$$ only if there is no D2D transmitter restricted subchannel n in the set [TeX:] $$\hat{\mathcal{I}}^{(m)}.$$ In other words, if [TeX:] $$\zeta_{m, n}=1,$$ then [TeX:] $$W_{m, n}=0.$$ Therefore, the sum of[TeX:] $$\zeta_{m, n} W_{m, n}$$ is zero for all [TeX:] $$m, n \in \mathcal{N}$$ since either the value of [TeX:] $$\zeta_{m, n} \text { or } W_{m, n}$$ is zero. Since [TeX:] $$\zeta_{m, n} W_{m, n} \geq 0,$$ it is sufficient to minimize the sum of [TeX:] $$\zeta_{m, n} W_{m, n}$$ to satisfy the constraint (18d). We formulate the problem of subchannel matching as

where [TeX:] $$\zeta=\left[\zeta_{1,1}, \cdots, \zeta_{N, N}\right].$$ We can see that [TeX:] $$\mathcal{P} 5$$ is a minimum weight matching problem. Its optimal solution can be obtained by the Hungarian algorithm [41], [42].

The computational complexity of the Hungarian algorithm is known as [TeX:] $$\mathcal{O}\left(N^{3}\right)$$ in [42]. The overall computational complexity of the minimum interference scheme becomes [TeX:] $$\mathcal{O}\left(I^{2} w_{\mathrm{sum}}+\right.\left.N^{3}\right).$$ Since the following inequality holds,

he overall computational complexity of the minimum interference scheme is [TeX:] $$\mathcal{O}\left(I^{2} w_{\mathrm{sum}}\right),$$ which is larger than that of the greedy max SINR scheme but much lower than that of the bruteforce search.

After determining the matching indicator [TeX:] $$\zeta,$$ we determine the set of D2D transmitters allocated subchannel n as

IV. POWER ALLOCATION

Suppose that after allocating subchannels, the BS collects local CSI on each subchannel to allocate transmit power to each D2D transmitter. That is, for subchannel n, the BS collects the channel coefficients between the BS and cellular user [TeX:] $$u_{n},$$ D2D transmitter [TeX:] $$t_{i}$$ and D2D receiver [TeX:] $$r_{j},$$ the BS and D2D transmitter [TeX:] $$t_{i},$$ cellular user [TeX:] $$u_{n}$$ and D2D receiver [TeX:] $$r_{j}, \forall i, j \in \mathcal{I}^{(n)}.$$ We formulate the optimization problem of power allocation as

In [TeX:] $$\mathcal{P} 6,$$ we obtain the optimal transmit power of each D2D transmitter on subchannel [TeX:] $$n, n \in \mathcal{N},$$ independently of the power allocation on other subchannels because the D2D transmitters allocated to subchannel n do not suffer interference from other D2D transmitters allocated other subchannels. Therefore, we can divide [TeX:] $$\mathcal{P} 6$$ into N subproblems which independently optimize the transmit power of each D2D transmitter on each subchannel. We formulate the power allocation problem on subchannel n as

where [TeX:] $$\mathbf{P}(n)$$ is the transmit power vector of the D2D transmitters in the set [TeX:] $$\mathcal{I}^{(n)}.$$ Note that [TeX:] $$\mathcal{P} 7$$ is not convex since its objective function is not convex. To tackle this problem, we rewrite the objective function as

where

and

Since [TeX:] $$f_{i}\left(\mathbf{P}^{(n)}\right) \text { and } g_{i}\left(\mathbf{P}^{(n)}\right)$$ are the logarithmic functions of affine functions, they are concave functions. To solve [TeX:] $$\mathcal{P} 7,$$ DC programming can be applied, which uses the first order Taylor series approximation with an iterative method [43]. Let [TeX:] $$n_{l}$$ be the index of the l-th D2D transmitter in the set [TeX:] $$\mathcal{I}^{(n)}.$$ The gradient of [TeX:] $$g_{i}\left(\mathbf{P}^{(n)}\right)$$ is given by

where [TeX:] $$\vec{e}_{l}$$ is a row vector with its l-th element one and the others zero. Let [TeX:] $$\mathbf{P}_{q}^{(n)}$$ denote the transmit power vector at the q-th iteration. We can write the first order Taylor series approximation of [TeX:] $$g_{i}\left(\mathbf{P}^{(n)}\right)$$ at point [TeX:] $$\mathbf{P}_{q}^{(n)}$$ as

By using the approximation of the objective function, we reformulate [TeX:] $$\mathcal{P} 7$$ as

Since [TeX:] $$\mathcal{P} 8$$ is convex, we can solve this by using any convex solver. Using the solution of [TeX:] $$\mathcal{P} 8$$ and an iterative algorithm, we can allocate the optimal transmit power to each transmitter. The details of the algorithm in the pseudo code format, given in Algorithm 3, are presented as follows.

Set a small positive variable [TeX:] $$\epsilon>0$$ to check the convergence of the sum rate. Set the initial transmit power [TeX:] $$\mathbf{P}_{0}^{(n)}, \forall n \in \mathcal{N},$$ as any value in the feasible region satisfying the constraints (33a) and (33b). After setting up, do the following procedures on subchannel [TeX:] $$n, \forall n \in \mathcal{N}.$$ Set the iteration number q = 0 and calculate the sum rate of the D2D transmitters [TeX:] $$R_{0}^{(n)}=\sum_{i \in \mathcal{I}(n)}\left(f_{i}\left(\mathbf{P}^{0}\right)-g_{i}\left(\mathbf{P}^{0}\right)\right).$$ In the q-th iteration step, find the optimal transmit power [TeX:] $$P^{*}$$ by solving [TeX:] $$\mathcal{P} 8.$$ Increase the iteration number q by one and update the transmit power as [TeX:] $$\mathbf{P}_{q}^{(n)}=\mathbf{P}^{*}.$$ Calculate the sum rate of the D2D transmitters [TeX:] $$R_{q}^{(n)}=\sum_{i \in \mathcal{I}(n)}\left(f_{i}\left(\mathbf{P}_{q}^{(n)}\right)-g_{i}\left(\mathbf{P}_{q}^{(n)}\right)\right).$$ Repeat the procedures until the sum rate converges, i.e., [TeX:] $$\left|R^{q}-R^{q-1}\right| \leq \epsilon.$$

Now, we check the convergence of Algorithm 3. Since [TeX:] $$g_{i}(\mathbf{P})$$ is concave, the following inequality always holds:

Using (41), we can obtain following inequality:

where in (a) we use that [TeX:] $$\mathbf{P}_{q}^{(n)}$$ is the solution of [TeX:] $$\mathcal{P} 8$$ for (q - 1)-th iteration. From this, we can see that [TeX:] $$R_{q}^{(n)}$$ is increased or unchanged in each iteration. Since [TeX:] $$R_{q}^{(n)}$$ does not converge to infinity, the inequality [TeX:] $$\left|R_{q}^{(n)}-R_{q-1}^{(n)}\right| \leq \epsilon$$ is always satisfied after some iteration. This proves the convergence of Algorithm 3.

V. SIMULATION RESULTS

In this section, we use MATLAB with the Monte Carlo method to obtain simulation results. We assume the mmWave carrier frequency of 38 GHz and use the simulation parameter from [31], Unless it is specified, simulation parameters are set according to Table 1.

In the legends of figures, greedy max SINR and minimum interference indicate that subchannels are allocated to D2D trans-

mitters according to the algorithms in Sections III.B and III.C, respectively, and random allocation indicates that subchannels are randomly allocated to D2D transmitters. Optimal power indicates that the transmit power is allocated to D2D transmitters according to the algorithm in Section IV and equal power indicates that the transmit power is equally allocated to D2D transmitters with the maximum power satisfying the interference constraints at the BS.

Fig. 1 shows the sum rate of the D2D transmitters according to the maximum transmit power at each D2D transmitter. It shows that the sum rate of the D2D transmitters increases with the maximum transmit power. For the same power allocation scheme, two proposed subchannel allocation schemes outperform the random subchannel allocation scheme, and the greedy max SINR scheme achieves the highest sum rate. For the same subchannel allocation scheme, naturally the optimal power allocation scheme outperforms the equal power allocation scheme. It shows that the gap between the optimal and equal power allocation schemes with the same subchannel allocation scheme increases with the maximum transmit power. This is because when the maximum transmit power is high, the equal power allocation scheme is more affected by the interference constraint than the power constraint while the optimal power allocation scheme has more options.

Fig. 2 shows the sum rate of the D2D transmitters according to the interference threshold. It shows that the sum rate increases with the interference threshold. The sum rates of the optimal and equal power allocation schemes with the same subchannel allocation scheme converge as the interference threshold increases. This indicates that without the interference threshold, allocating the maximum transmit power to each D2D transmitter is an optimal strategy in a mmWave network, which is different from a conventional network [44]. This is because that, in the mmWave network, signals are vulnerable to blockages which reduce the interference received at each D2D receiver while its desired signal is rarely affected by blockages due to its short distance.

Fig. 3 shows (a) sum rate and (b) individual rate of each D2D transmitter according to the number of D2D pairs. The sum

rate of the D2D transmitters increases with the number of D2D pairs. Since the sum rate is proportional to the number of D2D transmitters, it is hard to interpret the effects of the number of D2D pairs in the graph. Therefore, we add a graph of the individual rate in the figure. The individual rate of each D2D transmitter decreases with the number of D2D pairs. Without the optimal power allocation scheme, it shows that the sum rate of the minimum interference scheme is little higher than that of the random subchannel allocation scheme. However, when the transmit power is optimally allocated, the minimum interference scheme outperforms the random subchannel allocation scheme.

Fig. 4 shows the sum rate of the D2D transmitters according to the number of subchannels. It shows that the sum rate of the D2D transmitters increases with the number of subchannels. In the minimum interference scheme, when the number of subchannels is close to that of D2D pairs, the sum rates of the optimal and equal power allocation schemes are getting close. This is because most of subchannels are allocated only to a single user when the number of subchannels is large due to the fair allocation constraint (15). When the number of subchannels increases, the sum rate of the random subchannel allocation scheme with optimal power allocation is getting close to that of the minimum interference scheme with optimal power allocation. This indicates that the minimum interference scheme is inefficient when the numbers of subchannels and D2D transmitters are similar.

Fig. 5 shows the sum rate of the D2D transmitters according to the NLOS path loss exponent. Due to the vulnerability to blockages of mmWave signals, they have a high NLOS path loss exponent while conventional microwave signals have a low NLOS path loss exponent. The high NLOS path loss exponent can be regarded as mmWave networks while the low NLOS paht loss exponent as conventional networks. The sum rate of D2D transmitters increases with the NLOS path loss exponent. This indicates that D2D communication has advantages in mmWave networks compared to conventional networks.

Fig. 6 shows the sum rate of the D2D transmitters according to the average LOS range. This figure compares the sum rate

of the D2D transmitters in rural and urban environments. The large value of the average LOS range indicates a rural environment while the small value indicates an urban environment. It shows that the sum rate is maximized for the value of average LOS range 100 m, and an urban environment achieves higher sum rate than a rural environment. This is because in a rural environment, most of the paths become LOS which results in large interference.

Fig. 7 shows the average running time for each scheme according to the number of D2D pairs. Note that the vertical axis is in log scale. It shows that the random allocation is fastest while minimum interference schemes is slowest. We can see that this results well match with the computational complexity derived in Section III. Though the minimum interference scheme is slowest, it just needs only one second to perform algorithm for 100 D2D pairs, which is fast enough. Brute-force search can be regarded as performing random allocation [TeX:] $$N^{I}$$ times, which is much slower than the minimum interference scheme and this

VI. CONCLUSION

In this paper, we proposed two subchannel allocation schemes and an optimal power allocation scheme for multiple D2D pairs underlaid in an uplink mmWave cellular network. We formulated an optimization problem to allocate subchannels and transmit power, which aims at maximizing the sum rate of D2D transmitters. We decomposed the problem into two subproblems: a subchannel allocation problem and a power allocation problem. To solve the subchannel allocation problem, we considered two heuristic algorithms of the greedy max SINR scheme and the minimum interference scheme. Different from the greedy max SINR scheme which needs global CSI, the minimum interference scheme uses only the location of each node, which is practical. After subchannel allocation, we performed the transmit power allocation by using DC programming.

Through simulation, we confirm that the two proposed subchannel allocation schemes outperform the random subchannel allocation scheme and the power allocation helps to achieve higher sum rate. Moreover, the minimum interference scheme with optimal power allocation is efficient when the number of D2D pairs is large compared to that of subchannels. We also revealed that D2D communication has more advantages in mmWave networks than in conventional networks, and its performance is better in an urban environment compared to a rural environment. In future work, we will allocate resources to not only D2D transmitters but also cellular users, extend our scheme to a case with multi-cell environments, and allow each D2D transmitter to be allocated multiple subchannels to improve performance.