Open access

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

Written By

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

Submitted: April 8th, 2014 Published: November 26th, 2014

DOI: 10.5772/58937

From the Edited Volume

Contemporary Issues in Wireless Communications

Edited by Mutamed Khatib

Chapter metrics overview

View Full Metrics

2. System model

Consider a single-cell with a single base station equipped with Nt antennas, and a set S of K single-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:

yk=pkhkwksk+i¹kKpihkwisi+nk=hkx+nkE1

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

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,,pK is the matrix whose main diagonal contains the powers. The SINR of the kth user is given by:

SINRk=pk|hkwk|2ikpi|hkwi|2+σn2E2

and the instantaneous achievable data rate of user k is 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 U instead of the individual rates ri i S 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 KNt the general optimization problem is given by

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

where F denotes the Frobenius norm, βk is a priority weight associated to user k 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 P and W and each solution depends on the system requirements expressed by the weights βk [14]. The computation of optimal beamforming weights wk involves 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 βk are equal [16].

3.1. Multiuser scenario

Let Ω=1,,K be the set of all competing users where K is 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 S 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 (Nt and K). The sum rate maximization with user selection optimization problem can be defined as:

(S)=maxSΩ:|S|NtRBF(H(S))E4

where HS is the row-reduced channel matrix containing only the channels of the subset of selected users S and RBFHS 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 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 H 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 (β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 H at 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 HS is given by [17]:

W ¯(S)=H(S)H(H(S)H(S)H)1E5

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 P in (3) is given by :

RZFBF(H(S))=i=1|S|(log(μbi))+E6

where bi=HSHSHii-1-1 is 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+=P and x+=maxx,0. If all users in S are 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=LSQS obtained by applying Gram-Schmidt orthogonalization (GSO) [20]. LS is a lower triangular matrix and QS has orthonormal rows. The beamforming matrix given by WS=QSH generates 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<ilijpjsj of the ith user, the signals pjsj for i=1,,k are obtained by successive dirty paper encoding, where Ii is 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>i on each user i, therefore this scheme is called zero-forcing dirty-paper (ZFDP) coding. The information rate achieved with optimum P in (3) under the ZFDP scheme is given by [5]:

RZFDP(H(S))=i=1|S|(log(μdi))+E7

where di=lii2 is the squared absolute value of lii and μ 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 S 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 fHS does not require the computation of the optimum power allocation. Some metrics are given by simple relations between the row vectors in HS 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 Nt [5]. In such a SNR regime, the search space of the solution of problem (4) is reduced from L to LNt=K!/(Nt!K-Nt!) and optimization over fHS can 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 S with channels hiiS and 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~i is the projector matrix onto Vi=SpH~i the subspace spanned by the rows of the aggregate interference matrix H~i=h1H,,hi-1H,hi+1H,,hSHH associated with user i. QVi=I-PVi is the projector matrix onto the null space of Vi. The operation in (8) is equivalent to the projection of hi onto the null space spanned by the channel components of H~i illustrated in Fig. 2. Notice that hi2 in (8) is affected by the weight sin2θVihi which is the squared sine of the angle between the channel vector hi and the subspace spanned by the components of H~i. The weight sin2θVihi 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 ith link. Using the properties of water-filling and the strong relationship between the sum rate maximization and the maximization of the terms bi we 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 S is given by iSbi under certain constraints over the water level μ. However, for single antenna receivers the performance gap between the sum and the product of the terms bi is negligible and hereafter we analyze the metric iSbi which is equivalent to a matrix trace operation. Let H-S=HSHSH and H˙S=H-S-1 be 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:

Sω=argminSΩ:|S|=Nttr(H ˙(S))E9

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 S based 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 K and Nt. The term P0 is a critical SNR value that depends on HS in 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 QVi 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 H~i of the ith user by means of singular value decomposition (SVD) [17] as follows:

H ˜i=UH ˜iΣH ˜i[V ¯H ˜iVH ˜i]HE10

where V~H~i contains the Nt-r basis of the null space of H~i and r=rankH~i.

The orthogonal projector matrix is given by QVi=V~H~iV~H~iH and 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 Vi for any user iS. Let vjj=1r be the column vectors of V-H~i defined in (10) and the NSP in (8) for the ith user can be computed as follows:

hiQVi2=hi(Ij=1rvjvjH)2E11

The NSP operation in (11) can be also computed by applying GSO to HS as in [21] which represents a lower computational complexity than the SVD approach [22]. Using the basis of Vi the magnitude of the NSP operation is given by hiQVi2=hi2-h^i2 where h^i is the projection of hi onto each one of the orthogonal basis of Vi given by [20]:

h ^i=j=1rhicosθhivjvjvjHE12

where the term cosθhivj represents the coefficient of correlation between the vectors hi and vj defined as [17]:

cosθhivj=hivjHhivjE13

The domain of the coefficient is 0ηhivj=cosθhivj1 and θhivj=π2 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 HS and H~i for all iS the block matrix determinant formula to compute detHSHSH reads [23]:

det(H(S)H(S)H)=det(H ˜iH ˜iH)hiQVi2E14

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 Vi is called the coefficient of determination given by [17]:

ΔVihi2=hiPVihiHhihiHE15

where Vihi2 measures how much the vector hi can be predicted from the channel vectors of H~i. Notice that from (8) and (15) the projection power loss factor of hi due to the projection onto the null space of Vi is equivalent to 1-Vihi2 which can be evaluated as follows [17]:

1ΔVihi2=(1ηhiπ(1)2)(1ηhiπ(k)|π(1)π(k1)2)E16

where πk is the kth ordered element of H~i and ηhiπk|π1πk-1 is the partial correlation between the channel vector hi and the selected vector associated with πk eliminating the effects due to π1π2πk-1. Using multiple regression analysis it is possible to evaluate hiQVi2=hi21-Vihi2 by 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 jS the orthogonal projector matrix of each channel is known so that Qj=I-hjHhjhjH-1hj.

From [24] we have the following result:

QVi=(ji,jSQj)n,nE17

which establishes that the orthogonal projector matrix onto Vi can be approximated by recurrently projecting onto independent orthogonal subspaces such that their intersection strongly converges to QVi as n grows. The NSP measured by trH˙S has 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 i contains an interference component from all j<i users, 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πi are 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,,q with q=rankHS. Ti is the orthogonal projector matrix onto Sphπj<i the 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 HS for user selection and ZFDP beamforming:

f(H(S))=i=1|S|hiTi2E18

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˙S in order to avoid the computation of the inverse matrix H˙S. Considering the definition of trace we have that

tr(H ˙(S))=iλi1(H ¯(S))E19

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

|S|iλi1/|S|(H ˙(S))tr(H ˙(S))E20

Since S is constant and independent of the selected channels for all LNt possible user sets, the lower bound on the objective function of (9) can be simplified as:

iλi(H ˙(S))=det(H ¯(S))1E21

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:

Sξ=argmaxSΩ:|S|=Ntdet(H ¯(S))E22

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 iS are 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:

SΛ=argmaxSΩ:|S|=NtΛ(H(S))E24

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 iS is 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 HS is 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 LNt possible sets formally described as:

Sϵ=argminSΩ:|S|=Nt(maxi,jScosθhihj)E25

Some works in the literature define Sϵ as the set with minimum sum of correlation coefficients ijicosθhihj, i,j S or 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 HS this metric is given by:

δ(H(S))=i=1hi2i=1λi(H ¯(S))E26

and δHS=1 if and only if the elements of HS are pairwise orthogonal. The metric (26) reflects the orthogonality of the set hii S and 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 wi is not matched to hi. Inverting a ill-conditioned channel matrix HS 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 HS the condition number is defined as [33]:

κ(H(S))=|λmax(H ¯(S))||λmin(H ¯(S))|E28

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

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

κD(H(S))=tr(H ¯(S))λmin(H ¯(S))E30

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 S 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 S 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 L 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., S=Nt SΩ in problem (4) or by operating in the high SNR regime. This yields a search space of size LNt 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 [5] showed that there exist a critical SNR that depends on HS for which PP0 the maximum sum rate is achieved by a subset S with cardinality S<rankHS. For an operation point P>P0 the system achieves full multiplexing diversity, i.e., S=rankHS. The metric-based user selection algorithms solve (4) in two phases. In the first phase S 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 S 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 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 LNt matrix product and inversion operations. Therefore, the set S is 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-k evaluations of the metric f. Given Sn-1 in 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-1 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 QVi at 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 f 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 S and does not yield a significant performance degradation, specially in the large K regime [21].

Another relevant feature of this generic structure is given by the adjustment of Ω in each iteration. This is relevant in the large K regime where the number of operations required to find the next user is roughly K 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 K and 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 S 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., [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 S 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 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 K regimes since less users are scheduled; 2) the complexity in evaluating at most LK 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 [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=0 to the ith user in Ω(n) at the nth 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 (S) and resource allocation (wi and 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 fi that 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:

fi=hi2jisin2θhihjE32

where θhihj can be calculated from (13). By applying a change of variables over (32) we have that f~i=ai+jibij, where ai=2loghi and 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~i subject 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 ϕi so that S=i Ω: ϕi=1 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 [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 S for low values of K, and such gap rapidly vanishes as K with 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 bi have larger and uniform values. For low values of K there exists a performance gap between S and Sω because the probability that the terms bi have large uniform values is small. As K grows 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 S for K=6 and such gap vanishes as K 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 δHS 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 H-S with respect to the channel gains. Consider that for a given channel instance the optimum solution of (27) yields δHSδ=1 which 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 HS 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 K 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 H-S 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 K since 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 S ranges from 12% for K=6 to 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 hi and hj are 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.

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 Nt 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 [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 Nt compared to the optimum selection. This suggest that when KNt 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 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 K and 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 K 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 [18] show that the achievable sum rate in both approaches is proportional to the number spatial resources Nt at the transmitter.

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. 1. D. Tse and P. Viswanath, Fundamentals of Wireless Communication. Cambridge University Press, 2005.
2. 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. 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. 4. M. H. M. Costa, “Writing on dirty paper,” IEEE Trans. Inf. Theory, vol. 29, no. 3, pp. 439–441, 1983.
5. 5. G. Caire and S. Shamai Shitz, “On the achievable throughput of a multiantenna Gaussian broadcast channel,” IEEE Trans. Inf. Theory, 2003.
6. 6. L. C. Godara, Handbook of Antennas in Wireless Communications. CRC Press, 2002.
7. 7. S. Rao, Engineering Optimization: Theory and Practice. John Wiley & Sons, Inc., 2009.
8. 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. 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. 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. 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. 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. 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. 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. 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. 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. 17. H. Yanai, K. Takeuchi, and Y. Takane, Projection Matrices, Generalized Inverse Matrices, and Singular Value Decomposition. Springer, 2011.
18. 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. 19. Z. Tu and R. Blum, “Multiuser diversity for a dirty paper approach,” IEEE Commun. Lett., pp. 1–3, 2003.
20. 20. J. Gentle, Matrix algebra: theory, computations, and applications in statistics. Springer, 2007.
21. 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. 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. 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. 24. I. Halperin, “The product of projection operators,” Acta Sci. Math.(Szeged), 1962.
25. 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. 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. 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. 28. T. Cover and J. Thomas, Elements of Information Theory, 2nd ed. John Wiley & Sons, Inc., 2006.
29. 29. A. Bayesteh and A. K. Khandani, “On the user selection for MIMO broadcast channels,” IEEE Trans. Inf. Theory, pp. 2325–2329, 2008.
30. 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. 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. 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. 33. C. Oestges and B. Clerckx, MIMO wireless communications: from real-world propagation to space-time code design. 2007.
34. 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. 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. 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. 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. 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. 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. 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.

Written By

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

Submitted: April 8th, 2014 Published: November 26th, 2014