For broadcast channels (BC) in multiuser multiple-input multiple-output (MU-MIMO) systems, the overall achievable performance depends on the efficient use of the resources at the base station (BS). When channel state information (CSI) is known at the transmitter the gain is twofold: full spatial degrees of freedom can be attained  and the system can be optimized over a new degree of freedom given by the users. In the literature of MU-MIMO systems two dimensions of optimization are studied: multiplexing diversity and multiuser diversity (MUD). The former is a consequence of the independent fading across all MIMO links, which yields a set of parallel spatial channels where different data streams can be transmitted increasing the system capacity . The latter is given when users that are geographically far apart have channels that fade independently at any point in time. For the system sum rate maximization, such independent fading process is exploited so that the user with the largest channel magnitude will be selected for transmission. In MU-MIMO systems spatial and temporal communication can be performed in two ways: 1) orthogonal multiple access (time, frequency, or code) and 2) spatial-division multiple access (SDMA). To achieve orthogonality in time, all the spatial resources at the BS (antennas) are used to communicate with one user (antennas) at a time, which is known also as time-division multiple access (TDMA). This technique avoids inter-user interference, achieves power gains that scale with , enhances data rates for a single user specially at low signal-to-noise ratio (SNR) regime, and is robust to CSI uncertainty , . SDMA exploits CSI at the BS allowing users to be scheduled at the same time achieving multiplexing gains of at high SNR regime, where the system is limited by the degrees of freedom and not by power. Since the BS has knowledge of the data symbols and CSI, the multiuser transmission can be optimized using coding techniques. The achievable rate region in BC is based on dirty paper coding (DPC) . The principle behind this optimum coding technique is that the BS knows the interference for a given user and can pre-subtract it before transmission, which yields the capacity of an interference free channel. However, DPC is a nonlinear process that requires successive encoding and decoding whose complexity is prohibitive in practical systems and other suboptimal techniques are preferred instead. In the literature, DPC has been interpreted as beamforming (BF)  which is a SDMA scheme where data streams of different users are encoded independently and multiplied by weight vectors in order to mitigate mutual interference. Although BF is a suboptimal multiuser transmission scheme, several works (e.g., , ) have shown that it can achieve a large portion of the DPC rate and its performance is close-to-optimal for large and . Nevertheless, the optimization of the downlink BF weight vectors is a non-convex problem . The specific selection of the weight vector of a given user may affect the performance of other users, i.e., the achievable signal-to-interference-plus-noise ratio (SINR) of one user is coupled with the other users weight vectors and transmit powers . Since the weight vectors must be optimized jointly, optimum BF is a complicated task and suboptimal weights given by Zero-Forcing (ZF) based methods can be used . The joint optimization of the beamforming weights, the power allocation, and the set of links that are scheduled under SDMA mode is performed for a given global objective function. In BC system literature a meaningful figure of merit is the total sum rate since it quantifies the total data flow for a specific BF scheme and the open problems are power allocation and user selection. If the set of scheduled users meets that , power allocation can be given either by Lagrangian methods (convex optimization ) or by equal power allocation (close-to-optimal for the high SNR regime –). However, when the set of users is larger than the number of spatial resources at the BS, i.e.,, user selection is required. The selection of the optimum set of users that maximizes the sum rate for a given BF scheme with optimum power allocation is a mixed non-convex problem. Indeed, in systems where users must be allocated in different radio resources (slots or sub-channels) finding the optimum subsets of users under SDMA mode for each radio resource is a NP-complete problem whose optimal solution can only be found via exhaustive search (ES) . Recent research works have proposed a number of feasible heuristics algorithms that find a suboptimal yet acceptable solution to the sum rate maximization problem with SDMA communication. The literature of MU-MIMO has been focused on ZF-based BF schemes due to their tractability and the fact that some properties of the wireless channels can be used to estimate the reliability of joint transmission for a given set of users. The main objective of joint scheduling and BF is to make better decisions at the media access control (MAC) layer by exploiting information from the physical (PHY) layer. The literature reviewed in this chapter addresses the scheduling (user selection) process in the MAC layer using PHY layer information without considering constraints from upper layers. Our aim is to provide a comprehensive overview of algorithms proposed over the last years regarding joint user selection and SDMA schemes that solve the sum rate maximization problem in MU-MISO BC systems.
2. System model
Consider a single-cell with a single base station equipped with antennas, and a set of single-antenna users (illustrated in Fig. 1. We assume perfect CSI at the BS and the channel coefficients are modeled as independent random variables, with a zero-mean circularly symmetric complex Gaussian distribution (Rayleigh fading). The signal received by the th user is given by:
where is the intended symbol for user , is the transmitted signal vector from the base station antennas, is the channel vector to the user . Each user ignores the modulation and coding of other users, i.e., it is assumed single-user detection where each user treats the signals intended for other users as interference. is the additive zero mean white Gaussian noise with variance . The entries of the block fading channel are normalized so that they have unitary variance, and the transmitted signal has an average power constraint where is the expectation operation. Since the noise has unit variance, represents the SNR.
For linear spatial processing at the transmitter, the BF matrix can be defined as , the symbol vector as and is the matrix whose main diagonal contains the powers. The SINR of the th user is given by:
and the instantaneous achievable data rate of user is .
3. Problem formulation
The performance of a MIMO system is measured by a global objective function of the individual data rates or SINRs . From the system perspective it is desirable to optimize instead of the individual rates since the latter are coupled by the transmit powers and the beamforming weights in (2). Thus the performance depends on how efficiently the resources are allocated to each user and how effectively the interference from other users is mitigated. In this chapter we optimize the global utility function modeled as the sum rate maximization problem using BF subject to global power constraints. For the case where the general optimization problem is given by
where denotes the Frobenius norm, is a priority weight associated to user defined a priory by upper layers of the communications system to take into account QoS, fairness, or another system constraint. Finding a solution of (3) is a complex problem due to the nature of the optimum and and each solution depends on the system requirements expressed by the weights . The computation of optimal beamforming weights involves SINR balancing  and since the weights do not have a closed-form, iterative computational demanding algorithms have been proposed to determine them , . Indeed, problem (3) is NP-hard even when all priority weights are equal .
3.1. Multiuser scenario
Let be the set of all competing users whereis larger than the number of available antennas at the BS, i.e., , where denotes the cardinality of the set . In order to exploit the optimization dimension provided by MUD, it is necessary to select a set of users whose channel characteristics maximize the sum rate when they transmit simultaneously in the same radio resource. Such characteristics are defined by the type of beamforming scheme, the power constraints, the SNR regime, and the deployment characteristics (and ). The sum rate maximization with user selection optimization problem can be defined as:
where is the row-reduced channel matrix containing only the channels of the subset of selected users and is the achievable sum rate for such set. User scheduling is a real time operation whose computational complexity and implementation efficiency affect the performance of upper-layers. Moreover, finding the optimal solution of (4) requires an exhaustive search over a search space of size , which is the number of all ordered combinations of users.
Since the computation of the optimal solution of the sum rate maximization problem implies the joint optimization over , , and , the original problem (4) can be relaxed by taking one or more of the following actions: 1) by using beamforming weights with a defined structure; 2) based on linear beamforming the power allocation can be performed either by Lagrangian methods or by equal power allocation; and 3) based on the structure of the linear beamforming it is possible to design user selection algorithms that exploit information contained in and at the same time, to achieve a good trade-off between performance and complexity. In the following sections we will study systems with equally prioritized users () and the characteristics of state-of-the-art user selection algorithms that find suboptimal yet acceptable solutions to the non-convex and combinatorial problem (4).
4. Linear beamforming
In this section we describe the structure of two sub-optimal linear beamforming schemes and the optimal power allocation for each one of them. It is assumed perfect CSI at the transmitter which can be attained through time-division duplex (TDD) scheme assuming channel reciprocity . Notice that the weight vectors multiply the intended symbols in (1) which can be seen as a form of precoding, henceforward we use the terms beamforming and precoding interchangeably.
4.1. Zero Forcing Beamforming
In Zero Forcing Beamforming (ZFBF), the channel matrix at the transmitter is processed so that orthogonal channels between the transmitter and the receiver are created, defining a set of parallel subchannels . The Moore-Penrose pseudo inverse of is given by :
and the ZFBF matrix is given by the normalized column vectors of (5) as . Under ZFBF scheme the sum rate maximizing power allocation is given by the water-filling algorithm and according to  the information rate achieved with optimum in (3) is given by :
where is the effective channel gain of the th user and its allocated power is , the water level is chosen to satisfy and . If all users in are allocated with nonzero power, the water level has the compact form , : .
4.2. Zero forcing dirty paper
Suboptimal throughput maximization in Gaussian BC channels has been proposed in several works , ,  based on the QR-type decomposition of the channel matrix obtained by applying Gram-Schmidt orthogonalization (GSO) . is a lower triangular matrix and has orthonormal rows. The beamforming matrix given by generates a set of interference channels , while no information is sent to users . In order to eliminate the interference component of the th user, the signals for are obtained by successive dirty paper encoding, where is non-causally known. This precoding scheme was proposed in  and the authors showed that the precoding matrix forces to zero the interference caused by users on each user , therefore this scheme is called zero-forcing dirty-paper (ZFDP) coding. The information rate achieved with optimum in (3) under the ZFDP scheme is given by :
where is the squared absolute value of and is the solution to the water-filling equation , which defines the th power as .
5. Metrics of spatial compatibility
The sum rate maximization problem (4) can be solved by fixing the precoder structure and power allocation method. Under ZF-based precoding the performance strongly depends on the spatial correlation between the components of . The more correlated the channels, the higher the power penalty imposed by ZF schemes which yields a degradation of the achievable SINRs and a poor system performance. For this reason, problem (4) has been tackled in the literature by optimizing the spatial compatibility between scheduled users. This is accomplished by optimizing a specific metric over the channel matrix which can be related or can provide indirect information of the achievable sum rate for a given set of users and channel realization. A metric of spatial compatibility is a function of the CSI at the transmitter so that where the mapping quantifies how profitable is to select for transmission. Different metrics for spatial compatibility have been proposed in the literature and this section presents a unified treatment of the most common metrics used by several algorithms that solve (4) sub-optimally. It is worth mentioning that the optimization over a given metric may bring some advantages in terms of computational complexity, for instance, iterative evaluation of does not require the computation of the optimum power allocation. Some metrics are given by simple relations between the row vectors in which avoids matrix operations. Under certain SNR constraints described in Section 6, the user set that solves problem (4) achieves maximum multiplexing diversity, i.e., its cardinality is equal to . In such a SNR regime, the search space of the solution of problem (4) is reduced from to and optimization over can simplify the search of the optimum user set . In this section we introduce the channel metrics, its main properties, and the relations between them.
5.1. Null space projection
Considering a given set of users with channels and for ZFBF the effective channel gain of the th selected user defined in Section 4.1 is given by :
where is the projector matrix onto the subspace spanned by the rows of the aggregate interference matrix associated with user . is the projector matrix onto the null space of . The operation in (8) is equivalent to the projection of onto the null space spanned by the channel components of illustrated in Fig. 2. Notice that in (8) is affected by the weight which is the squared sine of the angle between the channel vector and the subspace spanned by the components of . The weight is referred in the literature as the projection power loss factor since it will affect the effective amount of power that is transmitted over the th link. Using the properties of water-filling and the strong relationship between the sum rate maximization and the maximization of the terms we elaborate a compact formulation of the maximization of metric (8). Theoretical results in  show that for the MISO BC system a meaningful metric to estimate the achievable performance of is given by under certain constraints over the water level . However, for single antenna receivers the performance gap between the sum and the product of the terms is negligible and hereafter we analyze the metric which is equivalent to a matrix trace operation. Let and be a Wishart matrix and its respective inverse which characterize the interaction of all user channels in . Considering the definitions in (6) and (8) the set of users that achieves a suboptimal solution to problem (4) maximizing the sum of the effective channel gains is given by the set of users that optimally solves of the following combinatorial problem:
where denotes the trace operator. The optimum set for the NSP metric is unique and it will contain the users that maximize . The selection of based on the NSP in (9) yields a close-to-optimal solution to problem (4) for a ZF-based precoding under the following conditions: , , or large values of both and . The term is a critical SNR value that depends on in order to meet the cardinality constraint over . The evaluation of the metric (8) is not unique and several algorithms described in next section use different operations to compute or approximate it in order to define algorithms that solve (9) with less computational complexity than the exhaustive search, especially when . Next we present several methods to evaluate the NSP for ZFBF and ZFDP. The application of each one of these methods lies in the complexity required to evaluate them and the available CSI at the BS. In other words, each method represents a trade-off between accuracy of the NSP evaluation and the required CSI at the transmitter.
5.1.1. Orthogonal projector for ZFBF
The computation of is not unique and different forms to evaluate such matrix can be efficiently used in different contexts, i.e., depending on the available CSI at the transmitter, the required computational complexity, and the deployment. Let us decompose matrix of the th user by means of singular value decomposition (SVD)  as follows:
where contains the basis of the null space of and .
The orthogonal projector matrix is given by and the set in (9) maximizes the objective function . In some scenarios described in the following sections, it is assumed that the BS knows the basis of for any user . Let be the column vectors of defined in (10) and the NSP in (8) for the th user can be computed as follows:
The NSP operation in (11) can be also computed by applying GSO to as in  which represents a lower computational complexity than the SVD approach . Using the basis of the magnitude of the NSP operation is given by where is the projection of onto each one of the orthogonal basis of given by :
where the term represents the coefficient of correlation between the vectors and defined as :
The domain of the coefficient is and means perfect spatial orthogonality. The NSP computation is not unique and different matrix operations can be use to evaluate it. Using the full channel matrix and for all the block matrix determinant formula to compute reads :
The orthogonal projection defined in (8) has a direct relationship with the correlation coefficients defined in (13). The normalized power loss experienced by the th channel when it interacts with the subspace is called the coefficient of determination given by :
where measures how much the vector can be predicted from the channel vectors of . Notice that from (8) and (15) the projection power loss factor of due to the projection onto the null space of is equivalent to which can be evaluated as follows :
where is the th ordered element of and is the partial correlation between the channel vector and the selected vector associated with eliminating the effects due to . Using multiple regression analysis it is possible to evaluate by extracting the partial correlation coefficients from the correlation coefficients choosing one user order out of permutations of the users in . A different approach can be applied if for a given set of channels the orthogonal projector matrix of each channel is known so that .
From  we have the following result:
which establishes that the orthogonal projector matrix onto can be approximated by recurrently projecting onto independent orthogonal subspaces such that their intersection strongly converges to as grows. The NSP measured by has been used by several user selection algorithms either by avoiding the exhaustive search required to solve (9) (e.g., , , ) or by using approximations of metric (8) (e.g., , ).
5.1.2. Orthogonal projector for ZFDP
In Section 4.2 the ZFDP beamforming was introduced and it was mentioned that the received signal of user contains an interference component from all users, i.e., the previously encoded users. Given an specific encoding order , (a permutation of the users in ), the beamforming vectors are computed either by a QR-type decomposition or by GSO as follows :
and with . is the orthogonal projector matrix onto the subspace spanned by all previously encoded users for which . Some authors (e.g., , ) use the following expression as an objective function over the channel matrix for user selection and ZFDP beamforming:
Observe that user selection and sum rate maximization based on metric (18) implicitly depend on one particular selected encoding order out of different valid permutations. Since different encoding order yield different values of (18), in  it was proposed a method to perform the successive encoding optimizing of the order . Such an optimum order is attained by an iterative algorithm that evaluates (8) each iteration for every successive encoded user. An alternative suboptimal approach can be employed as in  where is defined by the descending order of the effective channel gains of the users in .
5.2. Approximation of the NSP
The objective function of problem (9) can be further relaxed by using a lower bound of in order to avoid the computation of the inverse matrix . Considering the definition of trace we have that
and using the arithmetic-geometric mean inequality over it holds that :
Since is constant and independent of the selected channels for all possible user sets, the lower bound on the objective function of (9) can be simplified as:
A suboptimal but less computational demanding way to find a set of users that solves problem (4) is given by the set that solves the following combinatorial problem:
where the optimized objective function only requires to compute the determinant of a matrix product. Observe that the lower bound in (21) is closely related with (14) and the performance degradation for the former metric arises because the terms are neglected.
In  it was presented a greedy algorithm where the metric for user selection is based on an approximation of (16) and the correlation coefficients are used instead of the partial correlation coefficients. Such relaxation neglects the channel gain degradation due to the terms . Given channel matrix , the metric that approximates (19) is defined as follows :
Using this metric a suboptimal solution to problem (4) is given by the set of users that solve the following combinatorial problem:
Several user selection algorithms (e.g., , , ) attempt to create groups of quasi-orthogonal users based on the information provided by the coefficient of correlation (13). A set of channels is called -orthogonal if . Some works addressed problem (4) by scheduling the set of user with minimum -orthogonality measured either over the normal channels  or over the eigenvectors computed by SVD . If the orthogonality among channels in is the only metric considered to define (regardless of the channel gains), problem (4) can be sub-optimally solved by the set that minimizes the -orthogonality among all possible sets formally described as:
Some works in the literature define as the set with minimum sum of correlation coefficients or as the set with minimum average correlation coefficient , . Observe that these objective functions are based on pairwise metrics and they can be negatively biased by few terms with large values neglecting the remaining coefficients with relatively small values. An alternative utility function that can identify such large terms is the geometric mean over all correlation coefficients since it would assign the same priority to each of term. In MU-MIMO systems the user grouping problem based on (25) for scheduling time slots, sub-carriers, or both, can be modeled as a graph coloring problem ,  or graph clique problem  and complexity reduction is the main objective of the proposed grouping algorithms.
5.4. Orthogonality defect
The orthogonality defect derived from Hadamard's inequality  measures how close a basis is to orthogonal. Given the matrix this metric is given by:
and if and only if the elements of are pairwise orthogonal. The metric (26) reflects the orthogonality of the set and has been used to evaluate the compatibility between wireless channels in order to maximize the spatial multiplexing gain . The original problem (4) can be sub-optimally solved by the set that minimizes the orthogonality defect which is formally described as:
Observe that problem (27) uses a weighted version of the utility function of problem (22) where the weight is defined by the inverse of . The orthogonality defect can be seen as a scaled version of the lower bound of metric (19).
5.5. Condition number
The ZF-based beamforming methods are in general power inefficient since the spatial direction of is not matched to . Inverting a ill-conditioned channel matrix yields a significant power penalty and a strong SINR degradation at the receivers. In numerical analysis a metric to measure the invertibility of a matrix is given by the condition number. In MIMO system this metric is used to measure how the eigenvalues of a channel matrix spread out and to indicate multipath richness for a given channel realization. The less spread of the eigenvalues, the larger the achievable capacity in the high SNR regime. For the matrix the condition number is defined as :
and is an indication of the multiplexing gain of a MIMO system. Another definition of the condition number is given by the product for a given non-singular square matrix  and (28) generalizes that metric for any matrix where . If the condition number is small, the matrix is said to be well-conditioned which implies that as the total achievable sum rate in the MISO systems under ZF-based beamforming can achieve a large portion of the sum rate of the inter-user interference free scenario. Problem (4) can be sub-optimally solved by a set of users with the minimum condition number and such set is formally described as:
Another important metric to estimate matrix condition is given by the Demmel condition number. For such metric several applications in MIMO systems have been proposed in recent years, e.g., link adaptation, coding, and beamforming . The Demmel condition number can be seen as the ratio between the total energy of the channels of over the magnitude of the smallest eigenvalue of in the current channel realization and is given by the following expression :
where , i.e., the Frobenius norm is related with the overall energy of the channel. By using (30) the set of users that sub-optimally solves (4) is given by the solution of the following combinatorial problem:
6. User selection algorithms
For MU-MIMO BC systems with ZF-based beamforming the optimum solution to the sum rate maximization problem implies the optimization over the power allocation and user selection as well as the correct dimension and orientation of the signal subspace used by each selected user . Since this optimization is performed over several dimensions (time, space, signal space, power, users) the optimum solution for the MU-MIMO scenario has not been found. Even when the signal space spans over one dimension, i.e. single-antenna users, the optimum solution to the sum rate maximization problem (4) in MU-MISO BC systems is given by an exhaustive search whose computational complexity increases approximately with . In order to find a fair trade-off between complexity and performance, a large number of works have addressed the sum rate maximization problem for ZFBF (e.g., , ,  and ZFDP (e.g., , ) by designing low-complexity algorithms that find a sub-optimal yet acceptable solution to (4). The goal of such algorithms is to construct the solution set of quasi-orthogonal users implementing different iterative approaches. Some works in the literature proposed greedy opportunistic algorithms that exploit the instantaneous channel information. In a greedy selection each new selected user finds a locally maximum for a given global objective function so that the final set of users attempt to converge to a close-to-optimal solution. Another approach to solve (4) is to use channel metrics and reformulate the original problem as an integer program. In this section we present the principles and characteristics of different user selection algorithms proposed in the literature. Our aim is to introduce generic structures of the user selection process and to illustrate under which conditions they can be used to maximize the sum rate and to reduce computational complexity for ZF-based beamforming.
6.1. Metric-based selection
The objective of the metric-based user selection is to find a set of users with spatially quasi-orthogonal channels such that the profit from beamforming is maximized. User selection algorithms can be design to relax the original optimization problem (4) by optimizing a particular channel metric. This kind of optimization may face two main problems: 1) the large search space for the optimum solution, and 2) how to discriminate between metrics of sets with different cardinality without computing the objective function. Both problems are partially solved by imposing a constraint in the optimizations problem, i.e., in problem (4) or by operating in the high SNR regime. This yields a search space of size and metrics that can be easily compared since they are applied over user sets of the same size. In MU-MISO BC systems with ZF-based precoding and optimal power allocation, authors in  showed that there exist a critical SNR that depends on for which the maximum sum rate is achieved by a subset with cardinality . For an operation point the system achieves full multiplexing diversity, i.e.,. The metric-based user selection algorithms solve (4) in two phases. In the first phase is selected in order to optimize a given metric and in the second phase the sum rate is evaluated for the previously defined set. This means that the user selection and the resource allocation problems are decoupled in this approach. The cardinality of is fixed in the first phase and it may be modified during the second phase when the sum rate is evaluated. If power allocation is performed based on water-filling, this might yield a zero power allocation (no data transmission) for some users due to the instantaneous value of .
In the literature of user selection several algorithms solve problem (4) optimizing the NSP by iteratively computing the sum of the effective channel gains each iteration. The optimum set that maximizes the NSP is given by the solution of (9) which is a combinatorial problem that requires the evaluation of matrix product and inversion operations. Therefore, the set is found in a greedy fashion by selecting the user that locally maximizes the total sum of effective channel gains which roughly requires evaluations of the metric . Given in the th iteration, the optimum new user achieves the largest effective channel gain when its channel is projected onto the orthogonal subspace spanned by the previously selected users . In ,  the authors evaluate iteratively at the th iteration the intersection of the null spaces of the previously selected users with each new candidate user by means of GSO. Using this technique, it is not necessary to extract the basis of the subspace spanned by the channel matrix (SVD) or to compute the orthogonal projector matrix at each iteration . Other user selection algorithms based on the NSP further reduce the required computational complexity by approximating any of the its alternative forms described in Section 5.1.1. The algorithm proposed in  approximates (16) by using only the correlation coefficient between the users in . The authors in  select users based on metric (17) where each user computes its own projector matrix and the algorithm approximates the NSP. The optimization of an approximation of the NSP yields a suboptimal set of users and performance degradation regarding to (8) yet some gains in terms of complexity are attained. The general structure of this kind of algorithms is presented in Alg. 1 and is given by any metric defined in Section 5. Notice that the first selected user is the one with the strongest channel which not necessarily belongs to the optimum set. However, this criterion simplifies the initialization of and does not yield a significant performance degradation, specially in the large regime .
Another relevant feature of this generic structure is given by the adjustment of in each iteration. This is relevant in the large regime where the number of operations required to find the next user is roughly which can be computationally demanding. In order to reduce the total number of metric evaluations, an optimization over can be performed. For instance, by performing an optimization similar to (25) per iteration for a given -orthogonality target whose optimal value depends on and . The principle behind this optimization is that the candidate users must satisfy the hyperslab condition for a given vector . The metric-based user selection does not guarantee full multiplexing gain or sum rate maximization and authors in ,  have proposed a second optimization once that have been found. This is referred in Alg. 1 as Removal Optimization and its objective is twofold: to discard inactive users that do not receive data and to maximize the achievable sum rate by optimizing the beamforming weights and powers of the active users.
6.2. Utility-based selection
This class of algorithms perform a joint user selection and resource allocation optimization by evaluating the global utility function (3) each iteration (e.g., , , , , ). The greedy algorithms are highly effective for sum rate maximization and well suited for ZF-based beamforming. However, they require the evaluation of the power allocation and the achievable sum rate for each unselected user in every iteration of the algorithm which involves matrix operations (e.g., SVD or GSO). The algorithm in  was extended in  by computing an inverse matrix operation based on the LQ decomposition avoiding the explicit calculation of the Moore-Penrose pseudo-inverse, and reducing computational complexity. The general structure of the utility-based user selection is summarized in Alg. 2. Notice that as in Alg. 1, the set is initialized with the user with maximum channel magnitude which may not be part of the optimum set. This greedy selection does not attempt to maximize the multiplexing diversity since it will stop the search as soon as the aggregation of a new local optimal user decreases the overall sum rate. In the low SNR regime and for low values of , such stop criterion highly improves the rate performance since power is allocated to strong users and there exist more degrees of freedom (DoF) at the BS to mitigate inter-users interference. This approach may face two drawbacks: 1) the achievable fairness at low SNR and low regimes since less users are scheduled; 2) the complexity in evaluating at most times the achievable sum rate. The fairness issue can be tackled by changing the global utility function, e.g., maximizing the weighted sum rate in (3) using the proportional fairness approach , , . The complexity problem can be alleviated by exploiting the properties of water-filling in order to reduce the computational load of some matrix operations. Further complexity gains can be obtained if the set of candidate users is optimized each iteration, reducing the total number of sum rate evaluations. This refinement proposed in ,  is called Search Space Pruning and is based on the fact that if water-filling allocates to the th user in at the th iteration, such user cannot achieved a nonzero power allocation in future iterations.
6.3. User selection via integer optimization
The sum rate maximization formulation in (4) is a combinatorial problem subject to mixed constraints. Some works in the literature reformulate the original problem similarly to the metric-based approaches, performing user selection () and resource allocation (and ) as independent processes , . The NSP in Section 5.1 can be used to reformulate the utility-based selection presented in Alg. 1 as an integer program with linear objective function and linear constraint . Let us consider that for each user there exists a function that computes the NSP assuming pairwise orthogonality with user . By computing metric (23) over all users in the intersection of the projection onto the null spaces for the th user is given by:
where can be calculated from (13). By applying a change of variables over (32) we have that , where and . In this way, the component related to the channel gains and the one related to the spatial compatibility are decoupled and they can be used to model a bi-criterion problem  or to render the NSP into an integer problem . The user selection based on the NSP seeks the maximum sum of the effective channel gains, which can be approximated by subject to . In order to introduce such constraint, we define the following binary variables:
and the user selection modeled as an integer program based on the channel norms and correlation coefficients (13) is given by :
Notice that the binary programming problem (33) is a reformulation of (24) and in contrast to the metric-based selection in Section 6.1, the order in which the users are selected has no impact on the orthogonality of the elements of . The solution to the user selection problem is given by the binary variables so that and power allocation based on water-filling is performed over the set of selected users according to the employed precoding scheme. Since the objective function is convex and the constraints are given by affine functions, this problem can be solved by the pseudo-dual simplex method  for integer programs or by using standard optimization packages like MATLAB.
7. Numerical examples
In this section we compare the average sum rate achieved when optimal and suboptimal user selection is performed over different metrics of . The simulations consider perfect CSIT, fading channels are generated following a complex Gaussian distribution with unit variance and the average sum rate is given in (bps/Hz). Since we evaluate system performance via Shannon capacity expressions in (6) and (7), the results are independent of the specific implementation on the coding and modulation schemes, which provides us a general design insight.
The curves displayed in Fig. 3 are obtained by optimally solving the combinatorial problems introduced in Section 5 whose optimum user sets are employed to evaluate (4) with ZFBF. Notice that these results are upper bounds of the average sum rate for each metric, which implies that any greedy user selection algorithm can achieve at most the same performance for its optimized metric. The sum rate achieved by in (9) has a negligible performance gap regarding to the optimum set for low values of , and such gap rapidly vanishes as with a cost of matrix product and inversion for each possible set . Due to the properties of water-filling the sum rate is maximized when the terms have larger and uniform values. For low values of there exists a performance gap between and because the probability that the terms have large uniform values is small. As grows this probability increases and the performance gap vanishes. The average sum rate achieved by in (22) computes a lower bound of the NSP metric (8) with a performance gap not larger than 1% regarding to for and such gap vanishes as grows. This result suggest that (21) is a good candidate metric for user selection since it achieves a good trade-off between complexity and performance. The fact that cannot identify with accuracy the set that maximizes the sum rate is because this metric only reflects the degradation of the product of the eigenvalues of with respect to the channel gains. Consider that for a given channel instance the optimum solution of (27) yields which may indicate that forms an orthogonal basis yet this results does not provide information regarding the channel magnitudes. Observe that the optimum channel matrix does not achieve perfect -orthogonality or pairwise orthogonality among its components. The sum rate attained with the solution of problems (27), (29), and (31) degrades as grows. This is due to the fact that for large multiuser diversity the probability of finding a set of users that minimizes the dispersion of the eigenvalues of increases but this does not imply that the maximum sum of effective channel gains or transmitted power is achieved. Metric (23) improves its performance when since the probability that achieves both large sum of effective channel gains and pairwise uncorrelated channels is a function of the multiuser diversity. The performance gap between regarding ranges from 12% for to less than 1% for . The advantage of metric (23) is that only the computation of correlation coefficients in (13) is required avoiding matrix operations. The performance gap between the solutions of (24) and (9) depends on the spatial resources at the transmitter since the probability that two independent channels and are correlated is a decreasing function of . For the -orthogonality optimization in (25), the set may be not unique since two different sets may containing the same maximum correlation coefficient but their achievable sum rates may be quite different. Due to the fact that channel magnitudes are neglected, problem (4) is solved without fully exploiting multiuser diversity.
In Fig. 4 and Fig. 5 we compare several user selection algorithms that find sub-optimal solution to (4), namely the metric-based selection using the NSP metric proposed in  using GSO, ,  using SVD, and the NSP approximation based on (23) proposed in . The optimal solution of (4) is found by exhaustive search subject to , i.e., maximum multiplexing gain. In order to highlight the contribution of multiuser diversity we compare performance with respect to two simplistic user selection approaches, one based on the maximum channel gain (MCG) criterion (selecting the users with higher channels norms), and a second approach performing round robin user scheduling (RRS) policy. We compare the performance of the metric-based selection in Section 6.1 with two greedy utility-based (sum rate) algorithms in Section 6.2  and , and with the integer linear program (ILP) selection described in Section 6.3.
In Fig. 4 we compare the average sum rate as a function of the number of users for different user selection strategies for both precoding techniques. For the case of ZFBF Fig. 4 (a) and , the solution set of the utility-based selection in  is achieved with a cardinality less than compared to the optimum selection. This suggest that when is more efficient to select the users in a greedy fashion as described in Section 6.2, than to perform the selection based on channel metrics. When the number of competing users is large , the performance gap between the three user selection approaches described in Section 6 decreases and all techniques achieve maximum multiplexing gain. For the large K regime, the metric-based selection achieves a performance close to the utility-based selection with less computational effort. Moreover, the performance of the NSP approximation in  converges to one of , ,  with more gains in terms of computational complexity. In the case of ZFDP Fig. 4 (b) all approaches in Section 6 achieve full multiplexing diversity regardless the regime of . This is due to the fact that ZFDP can efficiently use all spatial resources at the transmitter for the high SNR regime. The utility and metric based selection techniques achieve the same performance over all range of . The NSP approximation metric in  achieves more than 95% of the optimum capacity and the performance gap reduces as the number of users increases. Notice that the approach in Section 6.3 optimally solves problem (24) and its performance is an upper bound for the user selection in . The performance of all approaches presented in Section 6 is sub-optimal, yet they represent different and acceptable trade-offs between sum rate performance, computational complexity, and multiplexing gain for different values of and the SNR regime.
In Fig. 5 the average sum rate is a function of the SNR for ZFBF and . The results show that for (dB) the utility-based selection is more efficient than the metric-based selection in the low SNR regime. In the high SNR regime the performance gap between the optimum selection and the approaches in Section 6 is less than 10%. Observe that even the NSP approximation metric in  can efficiently exploit multiuser diversity and the approaches based exclusively on channel magnitudes (MCG) and random selection incur in a large performance degradation. Comparing the performance of the utility-based versus the metric-based user selection is in general not fair since the former will optimize directly its utility function while the latter attempts to reduce computational complexity by optimizing a simpler utility function. The performance gap between the two approaches is large for low SRN and regimes. The reason is that the former directly optimizes the set of selected users while the latter indirectly estimates if a given set can maximize the sum rate. In the high SNR regime, the gap between both approaches diminishes and results in  show that the achievable sum rate in both approaches is proportional to the number spatial resources at the transmitter.
In this chapter, we have presented several metrics and techniques for user selection in multiuser MISO scenarios. This topic has been object of extensive research over the last years for different wireless scenarios. Several metrics that evaluate spatial compatibility, matrix invertibility, pairwise orthogonality, and eigenvalue dispersion were presented and compared for the sum rate maximization with user selection problem. Results show that the null space projection and its approximations are the metrics that most efficiently identify the set of users that maximizes the sum rate for both precoders ZFBF and ZFDP. Since the optimal user selection for sum rate maximization is a complex combinatorial problem different sub-optimal selection strategies were presented. The metric-based and utility-based techniques compute the user selection in a greedy fashion finding close-to-optimal solution. The metric-based selection was reformulated as an integer program selection which provides an upper bound of the performance of a metric based on the null space projection. Numerical results show that depending on the multiuser diversity and SNR regime one strategy of user selection can be preferred over the others reaching a fair trade-off between performance and complexity.
This work was supported by the Portuguese Fundação para a Ciência e Tecnologia (FCT) ADIN (PTDC/EEI-TEL/2990/2012).