Open access peer-reviewed chapter

User Selection and Precoding Techniques for Rate Maximization in Broadcast MISO Systems

By E. Castañeda, A. Silva and A. Gameiro

Submitted: April 8th 2014Reviewed: August 1st 2014Published: November 26th 2014

DOI: 10.5772/58937

Downloaded: 1309

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 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 [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 (Ntantennas) are used to communicate with one user (Nrantennas) 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 Nt, enhances data rates for a single user specially at low signal-to-noise ratio (SNR) regime, and is robust to CSI uncertainty [1], [3]. SDMA exploits CSI at the BS allowing K>1users to be scheduled at the same time achieving multiplexing gains of minNt,KNrat 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) [4]. 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) [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 Ntand K. Nevertheless, the optimization of the downlink BF weight vectors is a non-convex problem [6]. 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 [6]. 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 [5]. 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 NtKNr, power allocation can be given either by Lagrangian methods (convex optimization [7]) or by equal power allocation (close-to-optimal for the high SNR regime [8]–[12]). However, when the set of users is larger than the number of spatial resources at the BS, i.e., Nt<KNr, 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) [13]. 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 Ntantennas, and a set Sof Ksingle-antenna users (Nr=1)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 kth user is given by:


where skis the intended symbol for user k, xCNt×1is the transmitted signal vector from the base station antennas, hkC1×Ntis the channel vector to the user k. 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. nkCN0,σn2is the additive zero mean white Gaussian noise with variance σn2. The entries of the block fading channel H=[h1T,,hKT]Tare normalized so that they have unitary variance, and the transmitted signal x=k=1Kpkwkskhas an average power constraint ExHxPwhere E[]is the expectation operation. Since the noise has unit variance, Prepresents the SNR.

Figure 1.

Multiuser MISO Broadcast System

For linear spatial processing at the transmitter, the BF matrix can be defined as W =[w1,,wK], the symbol vector as s=[s1,,sK]and P=diagp1,,pKis the matrix whose main diagonal contains the powers. The SINR of the kth user is given by:


and the instantaneous achievable data rate of user kis rk=log21+SINRk.

3. Problem formulation

The performance of a MIMO system is measured by a global objective function of the individual data rates or SINRs Ur1, ,rK. From the system perspective it is desirable to optimize Uinstead of the individual rates ri i Ssince 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 KNtthe general optimization problem is given by

RBF=maxW,P k=1Kβkrk      s.t{WP1/2F2PE3

where Fdenotes the Frobenius norm, βkis a priority weight associated to user kdefined 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 Pand Wand each solution depends on the system requirements expressed by the weights βk[14]. The computation of optimal beamforming weights wkinvolves SINR balancing [11] and since the weights do not have a closed-form, iterative computational demanding algorithms have been proposed to determine them [6], [15]. Indeed, problem (3) is NP-hard even when all priority weights βkare equal [16].

3.1. Multiuser scenario

Let Ω=1,,Kbe the set of all competing users where Kis larger than the number of available antennas at the BS, i.e., Ω=KNt, 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 Swhose 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 (Ntand K). The sum rate maximization with user selection optimization problem can be defined as:


where HSis the row-reduced channel matrix containing only the channels of the subset of selected users Sand RBFHSis 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 L=i=1NtK!/(i!K-i!), 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 P, W, and S, 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 Hand 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 (βk=1 kΩ) 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 [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 Hat the transmitter is processed so that orthogonal channels between the transmitter and the receiver are created, defining a set of parallel subchannels [5]. The Moore-Penrose pseudo inverse of HSis given by [17]:


and the ZFBF matrix is given by the normalized column vectors of (5) as WS=w-1/w-1, ,w-S/w-S. Under ZFBF scheme the sum rate maximizing power allocation is given by the water-filling algorithm and according to [5] the information rate achieved with optimum Pin (3) is given by :


where bi=HSHSHii-1-1is the effective channel gain of the ith user and its allocated power is pi=μbi-1+, the water level μis chosen to satisfy iSμ-bi-1+=Pand x+=maxx,0. If all users in Sare allocated with nonzero power, the water level has the compact form [10], [18]: μ=1SW-SF2+P=1SP+ iSbi-1.

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 HS=LSQSobtained by applying Gram-Schmidt orthogonalization (GSO) [20]. LSis a lower triangular matrix and QShas orthonormal rows. The beamforming matrix given by WS=QSHgenerates a set of interference channels yi=liipisi+j<ilijpjsj+ni, i=1,,k while no information is sent to users k+1,,K. In order to eliminate the interference component Ii=j<ilijpjsjof the ith user, the signals pjsjfor i=1,,kare obtained by successive dirty paper encoding, where Iiis non-causally known. This precoding scheme was proposed in [5] and the authors showed that the precoding matrix forces to zero the interference caused by users j>ion each user i, therefore this scheme is called zero-forcing dirty-paper (ZFDP) coding. The information rate achieved with optimum Pin (3) under the ZFDP scheme is given by [5]:


where di=lii2is the squared absolute value of liiand μis the solution to the water-filling equation iSμ-di-1+=P, which defines the ith power as pi=μdi-1+.

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 HS. 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 f:CS×NtR+where the mapping quantifies how profitable is to select Sfor 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 fHSdoes not require the computation of the optimum power allocation. Some metrics are given by simple relations between the row vectors in HSwhich 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 Nt[5]. In such a SNR regime, the search space of the solution of problem (4) is reduced from Lto LNt=K!/(Nt!K-Nt!)and optimization over fHScan simplify the search of the optimum user set S. 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 Swith channels hiiSand for ZFBF the effective channel gain of the ith selected user defined in Section 4.1 is given by [5]:

bi =1[(H(S)H(S)H)1]i,i=hiQVi2=hi2sin2θVihiE8

where PVi=H~iHH~iH~iH-1H~iis the projector matrix onto Vi=SpH~ithe subspace spanned by the rows of the aggregate interference matrix H~i=h1H,,hi-1H,hi+1H,,hSHHassociated with user i. QVi=I-PViis the projector matrix onto the null space of Vi. The operation in (8) is equivalent to the projection of hionto the null space spanned by the channel components of H~iillustrated in Fig. 2. Notice that hi2in (8) is affected by the weight sin2θVihiwhich is the squared sine of the angle between the channel vector hiand the subspace spanned by the components of H~i. The weight sin2θVihiis referred in the literature as the projection power loss factor since it will affect the effective amount of power that is transmitted over the ith link. Using the properties of water-filling and the strong relationship between the sum rate maximization and the maximization of the terms biwe elaborate a compact formulation of the maximization of metric (8). Theoretical results in [9] show that for the MISO BC system a meaningful metric to estimate the achievable performance of Sis given by iSbiunder certain constraints over the water level μ. However, for single antenna receivers the performance gap between the sum and the product of the terms biis negligible and hereafter we analyze the metric iSbiwhich is equivalent to a matrix trace operation. Let H-S=HSHSHand H˙S=H-S-1be a Wishart matrix and its respective inverse which characterize the interaction of all user channels in S. 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 tr()denotes the trace operator. The optimum set Sωfor the NSP metric is unique and it will contain the users that maximize iShi2sin2θVihi. The selection of Sbased on the NSP in (9) yields a close-to-optimal solution to problem (4) for a ZF-based precoding under the following conditions: P>P0, K>Nt, or large values of both Kand Nt. The term P0is a critical SNR value that depends on HSin order to meet the cardinality constraint over S[5]. 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 K. 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 QViis 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 H~iof the ith user by means of singular value decomposition (SVD) [17] as follows:


where V~H~icontains the Nt-rbasis of the null space of H~iand r=rankH~i.

The orthogonal projector matrix is given by QVi=V~H~iV~H~iHand the set Sωin (9) maximizes the objective function ihiQVi2. In some scenarios described in the following sections, it is assumed that the BS knows the basis of Vifor any user iS. Let vjj=1rbe the column vectors of V-H~idefined in (10) and the NSP in (8) for the ith user can be computed as follows:


The NSP operation in (11) can be also computed by applying GSO to HSas in [21] which represents a lower computational complexity than the SVD approach [22]. Using the basis of Vithe magnitude of the NSP operation is given by hiQVi2=hi2-h^i2where h^iis the projection of hionto each one of the orthogonal basis of Vigiven by [20]:


where the term cosθhivjrepresents the coefficient of correlation between the vectors hiand vjdefined as [17]:


The domain of the coefficient is 0ηhivj=cosθhivj1and θhivj=π2means perfect spatial orthogonality. The NSP computation is not unique and different matrix operations can be use to evaluate it. Using the full channel matrix HSand H~ifor all iSthe block matrix determinant formula to compute detHSHSHreads [23]:


The orthogonal projection defined in (8) has a direct relationship with the correlation coefficients defined in (13). The normalized power loss experienced by the ith channel when it interacts with the subspace Viis called the coefficient of determination given by [17]:


where Vihi2measures how much the vector hican be predicted from the channel vectors of H~i. Notice that from (8) and (15) the projection power loss factor of hidue to the projection onto the null space of Viis equivalent to 1-Vihi2which can be evaluated as follows [17]:


where πkis the kth ordered element of H~iand ηhiπk|π1πk-1is the partial correlation between the channel vector hiand the selected vector associated with πkeliminating the effects due to π1π2πk-1. Using multiple regression analysis it is possible to evaluate hiQVi2=hi21-Vihi2by extracting the partial correlation coefficients from the correlation coefficients choosing one user order πout of S-1!permutations of the users in S[17]. A different approach can be applied if for a given set of channels hj jSthe orthogonal projector matrix of each channel is known so that Qj=I-hjHhjhjH-1hj.

Figure 2.

The spatial relationship between the components of vector hi and Vi.

From [24] we have the following result:


which establishes that the orthogonal projector matrix onto Vican be approximated by recurrently projecting onto independent orthogonal subspaces such that their intersection strongly converges to QVias ngrows. The NSP measured by trH˙Shas been used by several user selection algorithms either by avoiding the exhaustive search required to solve (9) (e.g., [18], [19], [21]) or by using approximations of metric (8) (e.g., [25], [26]).

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 icontains an interference component from all j<iusers, i.e., the previously encoded users. Given an specific encoding order πi, i1,,S(a permutation of the users in S), the beamforming vectors wπiare computed either by a QR-type decomposition or by GSO as follows [27]:

wπ(i)=Tihπ(i)HTihπ(i)H,                      Ti={Ifor i=1Ti1wπ(i1)wπ(i1)Hfor i=2,,q

and i=1,,qwith q=rankHS. Tiis the orthogonal projector matrix onto Sphπj<ithe subspace spanned by all previously encoded users for which hπj<iwπi=0. Some authors (e.g., [25], [27]) use the following expression as an objective function over the channel matrix HSfor 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 S!different valid permutations. Since different encoding order yield different values of (18), in [27] 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 [19] where πis defined by the descending order of the effective channel gains of the users in S.

5.2. Approximation of the NSP

The objective function of problem (9) can be further relaxed by using a lower bound of trH˙Sin order to avoid the computation of the inverse matrix H˙S. Considering the definition of trace we have that


and using the arithmetic-geometric mean inequality over λiH˙Sit holds that [28]:


Since Sis constant and independent of the selected channels for all LNtpossible 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 detH~iH~iH iSare neglected.

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 π1π2πk-1. Given channel matrix HS, the metric that approximates (19) is defined as follows [26]:

Λ(H(S))=i(hi2jisin2θhihj) i,jSE23

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 hi iSis called ε-orthogonal if cosθhihj<ϵ, i,j S[29]. Some works addressed problem (4) by scheduling the set of user with minimum ε-orthogonality measured either over the normal channels [30] or over the eigenvectors computed by SVD [29]. If the orthogonality among channels in HSis the only metric considered to define S(regardless of the channel gains), problem (4) can be sub-optimally solved by the set Sϵthat minimizes the ϵ-orthogonality among all LNtpossible sets formally described as:


Some works in the literature define Sϵas the set with minimum sum of correlation coefficients ijicosθhihj, i,j Sor as the set with minimum average correlation coefficient [25], [29]. 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 [13], [31] or graph clique problem [32] and complexity reduction is the main objective of the proposed grouping algorithms.

5.4. Orthogonality defect

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


and δHS=1if and only if the elements of HSare pairwise orthogonal. The metric (26) reflects the orthogonality of the set hii Sand has been used to evaluate the compatibility between wireless channels in order to maximize the spatial multiplexing gain [29]. The original problem (4) can be sub-optimally solved by the set that minimizes the orthogonality defect which is formally described as:

Sδ=argminSΩ:|S|=Nt δ(H(S))E27

Observe that problem (27) uses a weighted version of the utility function of problem (22) where the weight is defined by the inverse of i=1hi2. 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 wiis not matched to hi. Inverting a ill-conditioned channel matrix HSyields 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 HSthe condition number is defined as [33]:


and κHSis an indication of the multiplexing gain of a MIMO system. Another definition of the condition number is given by the product AA-1for a given non-singular square matrix A[20] and (28) generalizes that metric for any matrix HS  CS×Ntwhere SNt. If the condition number is small, the matrix HSis said to be well-conditioned which implies that as κHS1the 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:

Sκ=argminSΩ:|S|=Nt κ(H(S))E29

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 HSover the magnitude of the smallest eigenvalue of H-Sin the current channel realization and is given by the following expression [34]:


where trH-S=HSF2, 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:

SκD=argminSΩ:|S|=Nt κD(H(S))E31

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 OKNt. 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., [9], [21], [35] and ZFDP (e.g., [18], [19]) 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 Sof 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 Sof 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 Lfor 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., S=Nt SΩin problem (4) or by operating in the high SNR regime. This yields a search space of size LNtand 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 [5] showed that there exist a critical SNR that depends on HSfor which PP0the maximum sum rate is achieved by a subset Swith cardinality S<rankHS. For an operation point P>P0the system achieves full multiplexing diversity, i.e., S=rankHS. The metric-based user selection algorithms solve (4) in two phases. In the first phase Sis 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 Sis 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 P0.

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 LNtmatrix product and inversion operations. Therefore, the set Sis found in a greedy fashion by selecting the user that locally maximizes the total sum of effective channel gains which roughly requires LK=k=1Nt-1K-kevaluations of the metric f. Given Sn-1in the nth iteration, the optimum new user iΩachieves the largest effective channel gain when its channel is projected onto the orthogonal subspace spanned by the previously selected users V=SpHS(n-1). In [10], [21] the authors evaluate iteratively at the nth iteration the intersection of the null spaces of the previously selected users Sn-1with 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 QViat each iteration [19]. 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 [26] approximates (16) by using only the correlation coefficient between the users in Sn. The authors in [36] 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 fis 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 Sand does not yield a significant performance degradation, specially in the large Kregime [21].

Another relevant feature of this generic structure is given by the adjustment of Ωin each iteration. This is relevant in the large Kregime where the number of operations required to find the next user is roughly Kwhich 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 Kand Nt[37]. The principle behind this optimization is that the candidate users must satisfy the hyperslab condition Ωn=hi   i Ωn-1: cosθhigεfor a given vector g[21]. The metric-based user selection does not guarantee full multiplexing gain or sum rate maximization and authors in [10], [25] have proposed a second optimization once that Shave 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.

Alg 1.

Generic structure of the Metric-Based User Selection

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 Sis 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 i*decreases the overall sum rate. In the low SNR regime and for low values of K, 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 Kregimes since less users are scheduled; 2) the complexity in evaluating at most LKtimes 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 [21], [25], [39]. 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 [10], [18] is called Search Space Pruning and is based on the fact that if water-filling allocates pi=0to the ith user in Ω(n)at the nth iteration, such user cannot achieved a nonzero power allocation in future iterations.

Alg. 2.

Generic structure of the Utility-Based User Selection

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 (S) and resource allocation (wiand pi  iS ) as independent processes [25], [26]. 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 [26]. Let us consider that for each user iΩthere exists a function fithat computes the NSP assuming pairwise orthogonality with user ji, jΩ. By computing metric (23) over all users in Ωthe intersection of the projection onto the null spaces for the ith user is given by:


where θhihjcan be calculated from (13). By applying a change of variables over (32) we have that f~i=ai+jibij, where ai=2loghiand bij=2log(sinθhihj). 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 [25] or to render the NSP into an integer problem [26]. The user selection based on the NSP seeks the maximum sum of the effective channel gains, which can be approximated by iSf~isubject to S=Nt. In order to introduce such constraint, we define the following binary variables:

ϕi= {1if user i is selected0otherwise                     φij= {1if users i and j are selected0otherwise

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

max.    iaiϕi+2ij=i+1bijφijs.t.     {iϕi=Ntφijϕi,i,j       φijϕj,i,jϕi+ϕj1+φij,i,j      ϕi{0,1}φij{0,1}E33

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 HS. The solution to the user selection problem is given by the binary variables ϕiso that S=i Ω: ϕi=1and 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 [7] 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 HS. 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 Sωin (9) has a negligible performance gap regarding to the optimum set Sfor low values of K, and such gap rapidly vanishes as Kwith a cost of matrix product and inversion for each possible set S  Ω. Due to the properties of water-filling the sum rate is maximized when the terms bihave larger and uniform values. For low values of Kthere exists a performance gap between Sand Sωbecause the probability that the terms bihave large uniform values is small. As Kgrows this probability increases and the performance gap vanishes. The average sum rate achieved by Sξin (22) computes a lower bound of the NSP metric (8) with a performance gap not larger than 1% regarding to Sfor K=6and such gap vanishes as Kgrows. 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 δHScannot 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 H-Swith respect to the channel gains. Consider that for a given channel instance the optimum solution of (27) yields δHSδ=1which may indicate that HSδforms an orthogonal basis yet this results does not provide information regarding the channel magnitudes. Observe that the optimum channel matrix HSdoes 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 Kgrows. 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 H-Sincreases but this does not imply that the maximum sum of effective channel gains or transmitted power is achieved. Metric (23) improves its performance when Ksince the probability that HSΛachieves both large sum of effective channel gains and pairwise uncorrelated channels is a function of the multiuser diversity. The performance gap between SΛregarding Sranges from 12% for K=6to less than 1% for K=100. 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 hiand hjare correlated is a decreasing function of Nt. For the ε-orthogonality optimization in (25), the set Sϵ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.

Figure 3.

Average sum rate versus the number of users K with SNR=18(dB) and Nt=4.

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 |S|=Nt, 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 Ntusers 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 [18] and [40], 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 K<10, the solution set of the utility-based selection in [18] is achieved with a cardinality less than Ntcompared to the optimum selection. This suggest that when KNtis 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 K Nt, 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 [26] converges to one of [19], [21], [35] 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 K. 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 K. The NSP approximation metric in [26] 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 [26]. 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 Kand the SNR regime.

In Fig. 5 the average sum rate is a function of the SNR for ZFBF and K=10. The results show that for P<P010(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 [26] 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 Kregimes. 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 [18] show that the achievable sum rate in both approaches is proportional to the number spatial resources Ntat the transmitter.

Figure 4.

Average sum rate versus the number of users K with SNR =18 (dB) and Nt=4 for (a) ZFBF and (b) ZFDP.

Figure 5.

Average sum rate versus the SNR for the with K =10, Nt=4, and ZFBF.

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.


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

© 2014 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

E. Castañeda, A. Silva and A. Gameiro (November 26th 2014). User Selection and Precoding Techniques for Rate Maximization in Broadcast MISO Systems, Contemporary Issues in Wireless Communications, Mutamed Khatib, IntechOpen, DOI: 10.5772/58937. Available from:

chapter statistics

1309total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Interference Alignment — Practical Challenges and Test-bed Implementation

By Nima N. Moghadam, Hamed Farhadi, Per Zetterberg, Majid Nasiri Khormuji and Mikael Skoglund

Related Book

First chapter

An Overview of the Physical Insight and the Various Performance Metrics of Fading Channels in Wireless Communication Systems

By K.P. Peppas, H.E. Nistazakis and G.S. Tombras

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us