## 1. Introduction

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 [1] 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

*(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 [2]. 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 (*multiuser diversity

*(BF) [5] 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., [3], [5]) have shown that it can achieve a large portion of the DPC rate and its performance is close-to-optimal for large*beamforming

## 2. System model

Consider a single-cell with a single base station equipped with

where

For linear spatial processing at the transmitter, the BF matrix can be defined as

and the instantaneous achievable data rate of user

## 3. Problem formulation

The performance of a MIMO system is measured by a global objective function of the individual data rates or SINRs

where

### 3.1. Multiuser scenario

Let

where

Since the computation of the optimal solution of the sum rate maximization problem implies the joint optimization over

## 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 [6]. 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

and the ZFBF matrix is given by the normalized column vectors of (5) as

where

### 4.2. Zero forcing dirty paper

Suboptimal throughput maximization in Gaussian BC channels has been proposed in several works [5], [18], [19] based on the QR-type decomposition of the channel matrix

where

## 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

### 5.1. Null space projection

Considering a given set of users

where * projection power loss factor* since it will affect the effective amount of power that is transmitted over the

where

#### 5.1.1. Orthogonal projector for ZFBF

The computation of

where

The orthogonal projector matrix is given by

The NSP operation in (11) can be also computed by applying GSO to

where the term

The domain of the coefficient is

The orthogonal projection defined in (8) has a direct relationship with the correlation coefficients defined in (13). The normalized power loss experienced by the

where

where

From [24] we have the following result:

which establishes that the orthogonal projector matrix onto

#### 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

and

Observe that user selection and sum rate maximization based on metric (18) implicitly depend on one particular selected encoding order

### 5.2. Approximation of the NSP

The objective function of problem (9) can be further relaxed by using a lower bound of

and using the arithmetic-geometric mean inequality over

Since

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

In [26] 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

Using this metric a suboptimal solution to problem (4) is given by the set of users that solve the following combinatorial problem:

### 5.3. ε-orthogonality

Several user selection algorithms (e.g., [25], [26], [29]) attempt to create groups of quasi-orthogonal users based on the information provided by the coefficient of correlation (13). A set of channels

Some works in the literature define

### 5.4. Orthogonality defect

The orthogonality defect derived from Hadamard's inequality [28] measures how close a basis is to orthogonal. Given the matrix

and

Observe that problem (27) uses a weighted version of the utility function of problem (22) where the weight is defined by the inverse of

### 5.5. Condition number

The ZF-based beamforming methods are in general power inefficient since the spatial direction of

and

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 [34]. The Demmel condition number can be seen as the ratio between the total energy of the channels of

where

## 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 [9]. 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

### 6.1. Metric-based selection

The objective of the metric-based user selection is to find a set

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

Another relevant feature of this generic structure is given by the adjustment of * 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., [10], [11], [18], [38], [39]). 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 [18] was extended in [10] 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 * Search Space Pruning* and is based on the fact that if water-filling allocates

### 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 (

where

and the user selection modeled as an integer program based on the channel norms and correlation coefficients (13) is given by [26]:

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

## 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 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 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 [21] using GSO, [19], [35] using SVD, and the NSP approximation based on (23) proposed in [26]. The optimal solution of (4) is found by exhaustive search subject to

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

In Fig. 5 the average sum rate is a function of the SNR for ZFBF and

## 8. Summary

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.

## Acknowledgments

This work was supported by the Portuguese Fundação para a Ciência e Tecnologia (FCT) ADIN (PTDC/EEI-TEL/2990/2012).

## References

- 1.
D. Tse and P. Viswanath, Fundamentals of Wireless Communication . Cambridge University Press, 2005. - 2.
L. Zheng and D. Tse, “Diversity and multiplexing: A fundamental tradeoff in multiple-antenna channels,” IEEE Trans. Inf. Theory , vol. 1, no. 8, pp. 1–25, 2003. - 3.
M. Sharif and B. Hassibi, “A Comparison of Time-Sharing, DPC, and Beamforming for MIMO Broadcast Channels With Many Users,” IEEE Trans. Commun. , vol. 55, no. 1, pp. 11–15, Jan. 2007. - 4.
M. H. M. Costa, “Writing on dirty paper,” IEEE Trans. Inf. Theory , vol. 29, no. 3, pp. 439–441, 1983. - 5.
G. Caire and S. Shamai Shitz, “On the achievable throughput of a multiantenna Gaussian broadcast channel,” IEEE Trans. Inf. Theory , 2003. - 6.
L. C. Godara, Handbook of Antennas in Wireless Communications . CRC Press, 2002. - 7.
S. Rao, Engineering Optimization: Theory and Practice . John Wiley & Sons, Inc., 2009. - 8.
J. Jiang, R. Buehrer, and W. Tranter, “Greedy scheduling performance for a zero-forcing dirty-paper coded system,” IEEE Trans. Commun. , vol. 54, no. 5, pp. 789–793, 2006. - 9.
P. W. C. Chan and R. S. Cheng, “Capacity Maximization for Zero-Forcing MIMO-OFDMA Downlink Systems with Multiuser Diversity,” IEEE Trans. Wirel. Commun. , vol. 6, no. 5, pp. 1880–1889, 2007. - 10.
J. Wang, D. J. Love, and M. D. Zoltowski, “User Selection With Zero-Forcing Beamforming Achieves the Asymptotically Optimal Sum Rate,” IEEE Trans. Signal Process. , vol. 56, no. 8, pp. 3713–3726, Aug. 2008. - 11.
B. C. Lim, W. A. Krzymień, and C. Schlegel, “Efficient sum rate maximization and resource allocation in block-diagonalized space-division multiplexing,” IEEE Trans. Veh. Technol. , vol. 58, no. 1, pp. 478–484, 2009. - 12.
L.-N. Tran and E.-K. Hong, “Multiuser diversity for successive zero-forcing dirty paper coding: greedy scheduling algorithms and asymptotic performance analysis,” IEEE Trans. Signal Process. , vol. 58, no. 6, pp. 3411–3416, 2010. - 13.
F. Shad, T. D. Todd, V. Kezys, and J. Litva, “Dynamic slot allocation (DSA) in indoor SDMA/TDMA using a smart antenna basestation,” IEEE/ACM Trans. Netw. , vol. 9, no. 1, pp. 69–81, 2001. - 14.
E. Björnson and E. A. Jorswieck, Optimal Resource Allocation in Coordinated Multi-Cell Systems , vol. 9, no. 2–3. Foundations and Trends® in Communications and Information Theory, 2013, pp. 113–381. - 15.
S. Christensen, R. Agarwal, E. Carvalho, and J. M. Cioffi, “Weighted sum-rate maximization using weighted MMSE for MIMO-BC beamforming design,” IEEE Trans. Wirel. Commun. , vol. 7, no. 12, pp. 4792–4799, Dec. 2008. - 16.
Y. Liu, Y. Dai, and Z.-Q. (Tom) Luo, “Coordinated beamforming for MISO interference channel: Complexity analysis and efficient algorithms,” IEEE Trans. Signal Process. , vol. 298, no. 0704, 2011. - 17.
H. Yanai, K. Takeuchi, and Y. Takane, Projection Matrices, Generalized Inverse Matrices, and Singular Value Decomposition . Springer, 2011. - 18.
G. Dimic and N. Sidiropoulos, “On downlink beamforming with greedy user selection: performance analysis and a simple new algorithm,” IEEE Trans. Signal Process. , vol. 53, no. 10, pp. 3857–3868, 2005. - 19.
Z. Tu and R. Blum, “Multiuser diversity for a dirty paper approach,” IEEE Commun. Lett. , pp. 1–3, 2003. - 20.
J. Gentle, Matrix algebra: theory, computations, and applications in statistics . Springer, 2007. - 21.
T. Yoo and A. Goldsmith, “On the optimality of multiantenna broadcast scheduling using zero-forcing beamforming,” IEEE J. Sel. Areas Commun. , vol. 24, no. 3, pp. 528–541, 2006. - 22.
R. Chen, R. W. Heath, and J. G. Andrews, “Transmit selection diversity for unitary precoded multiuser spatial multiplexing systems with linear receivers,” IEEE Trans. Signal Process. , vol. 55, no. 3, pp. 1159–1171, 2007. - 23.
A. Razi, D. Ryan, I. B. Collings, and J. Yuan, “Sum rates, rate allocation, and user scheduling for multi-user MIMO vector perturbation precoding,” IEEE Trans. Wirel. Commun. , vol. 9, no. 1, pp. 356–365, 2010. - 24.
I. Halperin, “The product of projection operators,” Acta Sci. Math.(Szeged) , 1962. - 25.
T. F. Maciel and A. Klein, “On the Performance, Complexity, and Fairness of Suboptimal Resource Allocation for Multiuser MIMO–OFDMA Systems,” IEEE Trans. Veh. Technol. , vol. 59, pp. 406–419, 2010. - 26.
E. D. Castañeda, A. Silva, R. Samano-Robles, and A. Gameiro, “Low-Complexity User Selection for Rate Maximization in MIMO Broadcast Channels with Downlink Beamforming.,” Sci. World J. , vol. 2014, p. 865905, Jan. 2014. - 27.
P. Tejera, W. Utschick, G. Bauch, and J. A. Nossek, “Subchannel allocation in multiuser multiple-input–multiple-output systems,” IEEE Trans. Inf. Theory , pp. 1–34, 2006. - 28.
T. Cover and J. Thomas, Elements of Information Theory , 2nd ed. John Wiley & Sons, Inc., 2006. - 29.
A. Bayesteh and A. K. Khandani, “On the user selection for MIMO broadcast channels,” IEEE Trans. Inf. Theory , pp. 2325–2329, 2008. - 30.
Y. J. Zhang and K. Letaief, “An Efficient Resource-Allocation Scheme for Spatial Multiuser Access in MIMO/OFDM Systems,” IEEE Trans. Commun. , vol. 53, no. 1, pp. 107–116, Jan. 2005. - 31.
E. Driouch and W. Ajib, “Efficient scheduling algorithms for multiantenna CDMA systems,” IEEE Trans. Veh. Technol. , vol. 61, no. 2, pp. 521–532, 2012. - 32.
T. Yoo and A. Goldsmith, “Sum-rate optimal multi-antenna downlink beamforming strategy based on clique search,” IEEE GLOBECOM , p. 5 pp., 2005. - 33.
C. Oestges and B. Clerckx, MIMO wireless communications: from real-world propagation to space-time code design . 2007. - 34.
C. Zhong, M. McKay, T. Ratnarajah, and K.-K. Wong, “Distribution of the Demmel condition number of Wishart matrices,” IEEE Trans. Wirel. Commun. , vol. 59, no. 5, pp. 1309–1320, 2011. - 35.
L.-C. Wang and C. Yeh, “Scheduling for multiuser MIMO broadcast systems: transmit or receive beamforming?,” IEEE Trans. Wirel. Commun. , vol. 9, no. 9, pp. 2779–2791, 2010. - 36.
M. Fuchs, G. Del Galdo, and M. Haardt, “Low-Complexity Space–Time–Frequency Scheduling for MIMO Systems With SDMA,” IEEE Trans. Veh. Technol. , vol. 56, no. 5, pp. 2775–2784, Sep. 2007. - 37.
L. Sun and M. McKay, “Eigen-based transceivers for the MIMO broadcast channel with semi-orthogonal user selection,” IEEE Trans. Signal Process. , vol. 58, no. 10, pp. 5246–5261, 2010. - 38.
Z. Shen, C. Runhua, J. G. Andrews, R. W. Heath, and B. Evans, “Low complexity user selection algorithms for multiuser MIMO systems with block diagonalization,” IEEE Trans. Signal Process. , vol. 54, no. 9, pp. 3658–3663, 2006. - 39.
L.-N. Tran, M. Bengtsson, and B. Ottersten, “Iterative Precoder Design and User Scheduling for Block-Diagonalized Systems,” IEEE Trans. Signal Process. , vol. 60, no. 7, pp. 3726–3739, Jul. 2012. - 40.
S. Karachontzitis and D. Toumpakaris, “Efficient and low-complexity user selection for the multiuser MISO downlink,” 2009 IEEE 20th Int. Symp. Pers. Indoor Mob. Radio Commun. , pp. 3094–3098, Sep. 2009.