An Optimization-Based User Scheduling Framework for mmWave Massive MU-MIMO Systems

We propose a novel user equipment (UE) scheduling framework for millimeter-wave (mmWave) massive multiuser (MU) multiple-input multiple-output (MIMO) wireless systems. Our framework determines (sub)sets of UEs that should transmit simultaneously in a given time slot by approximately solving a nonconvex optimization problem using forward-backward splitting. Our UE scheduling framework is flexible in the sense that it (i) supports a variety of cost functions, including post-equalization mean square error and sum rate, and (ii) enables precise control over the minimum and maximum number of resources the UEs should occupy. We demonstrate the efficacy of our framework using realistic mmWave channel vectors generated with a commercial ray-tracer. We show that our UE scheduler outperforms a range of existing scheduling methods and closely approaches the performance of an exhaustive search.


I. INTRODUCTION
Millimeter-wave (mmWave) communication combined with massive multiuser (MU) multiple-input multiple-output (MIMO) is expected to be a core component in sixth generation (6G) wireless systems [1]. Combining these two technologies not only promises large beamforming gains to combat the high path loss at mmWave frequencies but also enables highbandwidth data transmission to multiple user equipments (UEs) in the same time-frequency resource.
In order to maximize the quality-of-service (QoS) for all UEs in the network, resource allocation strategies, such as power control and UE scheduling, are necessary. Power control mitigates the near-far problem between the UEs transmitting to an infrastructure basestation (BS). UE scheduling distributes the UEs' requests either in time/frequency or spatially, with the goal of minimizing interference in scenarios where UEs have similar channel impulse responses-this can happen in congested scenarios with many transmitting UEs in close vicinity. The literature focuses almost exclusively on greedy UE scheduling algorithms, where one UE is selected at a time to join a set of scheduled UEs [2], [3]. Such approaches have difficulties scheduling UEs over multiple time slots and fail The work of VP and CS was supported in part by an ETH Research Grant. The work of CS was supported in part by ComSenTer, one of six centers in JUMP, a SRC program sponsored by DARPA. The work of CS was supported in part by the U.S. NSF under grants CNS-1717559 and ECCS-1824379.
We thank Haochuan Song and Seyed Hadi Mirfarshbafan for discussions on FBS and mmWave channels, respectively. We thank Gian Marti and Sueda Taner for comments on an early version of this paper. We also thank Remcom for providing us with a license for the Wireless InSite ray-tracing software.
to consider the scheduling problem globally, which results in error propagation and inevitably leads to sub-optimal QoS.

A. Contributions
We propose a novel UE scheduling framework for mmWave MU-MIMO systems that identifies subsets of UEs that should transmit simultaneously in a given time slot. We formulate a global optimization problem, which supports a variety of cost functions, including post-linear minimum mean-square error (LMMSE) equalization mean square error (MSE) and post-LMMSE equalization sum rate. Our framework also enables precise control over the minimum and maximum number of resources each UE should occupy. In order to efficiently find approximate solutions to the nonconvex UE scheduling problem, we approximately solve a relaxed version using forward-backward splitting (FBS). We use mmWave channel vectors from a commercial ray-tracer to demonstrate that our framework outperforms a range of existing algorithms in terms of bit error rate (BER) and average per-UE rates, often closely approaching the performance of an exhaustive search (ES).

B. Relevant Prior Art
UE scheduling has been studied extensively for mmWave communication [3]- [6] and massive MU-MIMO systems [2], [7]- [10]. Many of the proposed algorithms follow a greedy approach, such as semiorthogonal UE selection (SUS) [2], channel structure-based scheduling (CSS) [3], greedy max-sum rate scheduling (greedy) [3], and chordal distance-based UE scheduling (chordal) [3]. All of these methods iteratively select UEs to greedily maximize a predefined cost function. In stark contrast, we address the UE scheduling problem globally, i.e., we determine the transmitting UEs for all time slots jointly by solving a single optimization problem. Our framework is flexible in (i) the choice of the cost function and (ii) the constraints on the maximum/minimum number of UEs that can transmit per time slot as well as the maximum/minimum number of time slots that a UE is allowed to transmit. Furthermore, most methods proposed in the literature aim at optimizing the signal-to-interference-plus-noise ratio (SINR), chordal distance, or channel capacity [10]. Our framework also allows other, practically relevant cost functions, such as the post-equalization MSE or sum rate. Finally, we note that the majority of results for mmWave systems focus on hybrid analog-digital beamforming architectures [3]- [6]. In contrast, our framework considers all-digital BS architectures, which are recently gaining popularity [11], [12].

C. Notation
Upper case and lower case bold symbols denote matrices and vectors, respectively. We use A i,j for the element on the ith row and jth column of A, a j as the jth column of A, and a i as the ith element of vector a. We define I M , 1 L×M , and 0 L×M as the M × M identity matrix, L × M all-one matrix, and L × M all-zero matrix, respectively. The superscript (·) H denotes the Hermitian transpose. A diagonal matrix with a on the main diagonal is denoted by diag(a). The Euclidean and Frobenius norms are denoted by · 2 and · F , respectively. Expectation is E[·] and e ≤ represents element-wise less-than-or-equal-to.

A. System Model
We consider the uplink of a mmWave massive MU-MIMO system in which U single-antenna UEs transmit data to an all-digital BS equipped with a B-antenna uniform linear array (ULA). We consider a block-fading scenario with t = 1, . . . , T time slots and frequency-flat channels with input-output relation Here, y[t] ∈ C B is the receive vector at time slot t, s[t] ∈ C U contains the transmit signals from all U UEs, and n[t] ∈ C B models noise whose entries are i.i.d. circularly-symmetric complex Gaussian with variance N 0 . The effective channel matrix H =H∆ in (1) combines the effect of the MIMO channel matrixH ∈ C B×U and the power control matrix ∆ = diag(δ 1 , . . . , δ U ), whose entries are given by [13] In (2),h u stands for the uth column ofH and η ≥ 0 determines the maximum dynamic range between the weakest and strongest UE receive power in decibel (dB).

B. UE Scheduling
To formalize the UE scheduling problem, we define a binaryvalued UE scheduling matrix C ∈ {0, 1} U ×T , where C u,t = 1 and C u,t = 0 indicate that UE u during time slot t is active and inactive, respectively. Furthermore, we define a diagonal U ×U , where c t is the tth column of C. Through multiplication with s[t], this mask matrix describes which UEs transmit symbols and which UEs are idle in time slot t. We absorb the effect of the mask matrix in the effective channel as H[t] = HD C [t], which now depends on t. Our goal is to develop a framework that determines a UE scheduling matrix C by minimizing a given cost function F (C) subject to constraints that specify the minimum and maximum number of resources that UEs are allowed to occupy.

A. Scheduling as an Optimization Problem
The proposed UE scheduling framework consists of an application-specific cost function F (C) and a set of constraints that determine the resource utilization in time and space. We wish to solve the following optimization problem: with the two constraint sets The set C U in (4) determines the minimum U min and maximum U max number of UEs allowed to transmit simultaneously per time slot; the set C T in (5) determines the minimum T min and maximum T max number of time slots each UE is allowed to transmit. Due to the discrete nature of the UE scheduling matrix C, the problem in (3)

B. Problem Relaxation
To arrive at an efficient UE scheduling algorithm, we relax the binary-valued {0, 1} entries in C to the continuous range [0, 1] as follows: C ∈ [0, 1] U ×T . While this relaxation enables the use of computationally efficient gradient-descentbased methods, it no longer enforces that the solutions are in {0, 1}. To mitigate this issue, we augment the cost function of the relaxed optimization problem with the following regularizer, which promotes binary-valued scheduling matrices C [14]: Here, α ≥ 0 is a regularization parameter, where larger values enforce binary-valued solutions more strictly. By utilizing F (C) = F (C) + R(C) as a new cost function, we are now able to deploy numerical optimization methods to efficiently determine binary-valued solutions to the relaxed problem in (3).
Since the augmented cost function is nonconvex (even if the original cost function F (C) is convex), numerical methods may only converge to a local minimum. Thus, to improve the solution quality, we perform multiple random initializations and use the solution candidate C * with the lowest cost F (C * ).

C. UE Scheduling via Forward-Backward Splitting (FBS)
To solve (3) for the set C ∈ [0, 1] U ×T and the augmented cost functionF (C) = F (C) + R(C), we can use FBS [15]. This technique performs the following step for iterations i = 1, 2, . . . until a stopping-condition is met: Here, the proximal operator prox C U ∩C T (·) is the orthogonal projection onto C U ∩ C T , τ (i) are suitably-chosen step sizes, and ∇F (·) is the gradient ofF (·). FBS is initialized with a matrix C (1) ∈ [0, 1] U ×T drawn uniformly at random and the entries of the matrix in the last iteration C (Imax) are quantized to {0, 1} to satisfy the constraint sets C U and C T .

A. Douglas-Rachford Splitting (DRS)
We now outline the implementation of the proximal operator prox C U ∩C T (·) in (7). This operator is the orthogonal projection onto an intersection of two simplexes. To determine a solution that lies within the two sets, we utilize Douglas-Rachford splitting (DRS) [16]. DRS alternatively projects onto the sets C U and C T until a solution matrix is found. Concretely, we solve the following optimization problem with the two functions Here, β ≥ 0 is a tuning parameter that can be used to accelerate convergence and the constraints are enforced using indicator functions X C U and X C T , which we define as follows: DRS iteratively carries out the two steps [16] V (k+1) = prox ψ G (k) = arg min and is initialized with G (1) = 0 U ×T . After convergence or a maximum number of iterations, DRS outputs the matrix V (Kmax) . The details of this algorithm will be provided in [17].

B. Projection with Inequality Constraints
The steps in (12) and (13) project each column onto the simplexes. Since both of the sets C U and C T are described by inequalities, we need a projection onto a generic simplex with inequality constraints. Given a vector q ∈ R M , our objective is to find a solution vector p * ∈ C M closest to q as follows: To solve this subproblem efficiently, we use a line search approach that requires sorting of q to determine the vector p * satisfying the inequality constraints. The Karush-Kuhn-Tucker (KKT) conditions and the algorithm will be detailed in [17].

V. COST FUNCTIONS
We now discuss the two cost functions considered in this work. Due to space constraints, the gradients as well as other cost functions will be discussed in future work [17].

A. Post-LMMSE Equalization MSE
As our first cost function, we consider the post-LMMSE MSE. We define this cost function as where W

[t] = H[t] H[t]
H H[t] + N0 Es I U −1 is the LMMSE equalization matrix in time slot t and E s is the transmit signal energy. Note that this cost function only accounts for errors from the UEs that transmit in a given time slot t. The gradient for this cost function will be detailed in [17].

B. Post-LMMSE Equalization Sum Rate
As our second cost function, we consider the sum of achievable rates over all UEs and time slots after an LMMSE equalizer. We define this cost function as where the SINR of the uth UE in time slot t is given by The gradient for this cost function will be detailed in [17].

A. Simulation Setup
We consider a mmWave massive MU-MIMO system with a carrier frequency of 60 GHz and a bandwidth of 100 MHz. At the BS, we consider an ULA with λ/2 antenna spacing. The BS and UE antennas are omnidirectional and are at a height of 10 m and 1.65 m, respectively. The UEs transmit 16-QAM symbols and the per-UE power control dynamic range is set to η = 6 dB. We evaluate our framework using mmWave channel vectors generated with Wireless InSite [18]. The channel vectors are generated for 22, 448 UE positions in an area of 109.7 m × 164.7 m. The scenario is depicted in Fig. 1; the BS location is shown with a blue circle. To generate a channel realization, U UE positions are selected uniformly and independently at random. For channel estimation, we use BEACHES [11]. In Table I, we list the four different scenarios considered in what follows and their respective number of random initializations. We set T min = T max = T S and U min = U max = U S . For the gradient step, we set τ (i) = τ to a constant stepsize.

B. Performance Metrics and Baseline Algorithms
We consider the uncoded BER and average per-UE rate, both evaluated after utilizing an LMMSE equalizer. In our simulation results, we refer to the post-LMMSE equalization MSE as "opt.based MSE" and to the post-LMMSE equalization sum rate as "opt.-based rate." In order to compare our framework with baseline methods, we also simulate the "SUS" [2], "CSS" [3], and "greedy" [3] algorithms. For all of the mentioned baseline methods, we schedule the UEs for the first time slot and then schedule the remaining unscheduled UEs in the subsequent time slots until all of the UE requests are spread over T time slots. We also consider a baseline, which picks the subsets of UEs uniformly at random (called "random") and a "no scheduling" baseline, in which all of the UEs are scheduled in all the time slots. For Scenario S1, we also consider an ES, which tests every possible scheduling matrix C and selects the one that minimizes the given cost function. Fig. 2 shows the simulation results for Scenario S1. In Fig. 2(a), we see that our UE scheduling framework, both with the "opt.-based MSE" and "opt.-based rate" cost functions are comparable to the optimal baselines "ES-MSE" and "ES-rate," reaching a BER of less than 0.1% at a signal-to-noise ratio (SNR) of 25 dB. In Fig. 2(b), we observe the same behavior: the performance of our UE scheduling framework is nearly indistinguishable from that of an ES. Compared to existing baseline algorithms, our "opt.-based MSE" and "opt.-based rate" methods achieve superior performance. For example, compared to "CSS," "opt.-based rate" realizes a gain of over 4 dB at 1% BER. Compared with the "no scheduling," "opt.-based MSE" and "opt.-based rate" are superior in terms of BER for all SNR values and in terms of average per-UE rate at high SNR. Fig. 3(a), Fig. 3(b), and Fig. 3(c) show simulation results for Scenarios S2, S3, and S4 in terms of BER while Fig. 3(d),   2. (a) BER and (b) average per-UE rate for Scenario S1 with 10 2 channel realizations and 10 5 transmissions. The proposed UE scheduling algorithm is comparable to an ES for the MSE and sum rate criteria, in terms of BER and average per-UE rate. Our methods can reach a BER of less than 0.1% at a SNR of 25 dB. Compared to baseline methods from the literature, our framework provides a gain over 4 dB at 1% BER, for example. Fig. 3(e), and Fig. 3(f) present the same scenarios in terms of average per-UE rate. In Fig. 3(a), we see that our "opt.based MSE" and "opt.-based rate" UE scheduling algorithms have a gain of at least 3 dB when compared to the best baseline algorithm at 1% BER. In terms of average per-UE rate, we see in Fig. 3(d) that the performance of our framework outperforms existing algorithms, albeit only slightly. In Fig. 3(b) and Fig. 3(e), we consider a system in which the number of scheduled UEs is equal to the number of BS antennas. Even with the use of UE scheduling, we observe that we cannot provide reasonable QoS, especially in terms of uncoded BER where it can provide a BER of approximately 10% at an SNR of 25 dB with the best scheduling method. This behavior is mainly due to the use of an LMMSE equalizer. To improve performance, one could spread the UE requests over more time slots, so that U S < B, which is what we have done in Scenario S4. We see in Fig. 3(c) and Fig. 3(f), that the performance of our "opt.-based MSE" and "opt.-based rate" algorithms is superior to the baseline methods, with a gain of at least 3 dB at 1% BER, for example.

C. Simulation Results
Not surprisingly, we see that utilizing the "opt.-based MSE" cost function provides better BER performance than "opt.based rate." Furthermore, we observe that in all scenarios, the "no scheduling" baseline yields extremely poor BER performance, which is due to the suboptimal LMMSE equalizer. When it comes to the average per-UE rate, as the UE to BS antenna ratio U B or the SNR increases, the performance of "no scheduling" decreases. No scheduling can be beneficial at low SNR in terms of average per-UE rate, but realizing these gains would require sophisticated forward error correction strategies.

VII. CONCLUSIONS
We have proposed a novel optimization-based UE scheduling framework for mmWave massive MU-MIMO systems. The framework supports a range of cost functions and constraints that specify the UE resource allocation. For a small system with B = 16 and U = 16, we have shown that the performance   of the proposed methods is comparable to that of an exhaustive search, whereas existing baseline algorithms perform (often significantly) worse. In larger systems with U S < B, we have shown that the proposed methods outperform existing methods in terms of BER and average per-UE rate. In scenarios where U S ≥ B, even our framework together with an LMMSE equalizer cannot achieve acceptable performance. Thus, one can schedule the UE requests over more time slots so that U S < B, as it has been shown in Fig. 3(c) and Fig. 3(f).
In [17], we will introduce a range of other cost functions as well as their respective gradients. In addition, we will present the complete derivation of the projection on the simplex with inequality constraints and include a complexity analysis.