International Journal of Computer Networks & Communications (IJCNC)


A Low Complexity User Grouping Strategy For Downlink Multi-User Mimo Scheduling

Nguyen Ngoc Van

School of Electronics and Telecommunications, Hanoi University of Science and Technology, No 1, Dai Co Viet Street, Hai Ba Trung, Hanoi, Vietnam


In this paper, we present a low complexity user grouping algorithm for multi-user MIMO system employing opportunistic fair scheduling (OFS) and zero-forcing beamforming (ZFB), and develop a framework for cross-layer resource scheduling. Given a particular subset of users and their channel conditions, the optimal beamforming scheme can be calculated. The multi-user resource scheduling problem then refers to the selection of the optimal subset of users for transmission at each time instant to maximize the total throughput of the system. The simulation result shows that the performance of resource scheduling algorithm based on user grouping method proposed in this paper is close to the optimal performance which used exhaustion method. In addition, user grouping does not affect the fairness among all users.


Opportunistic fair scheduling (OFS); zero-forcing beamforming (ZFB);

1. Introduction

In the last mid-1990s, Telatar, Foschini and Gans proved that Multiple-Input Multiple-Output (MIMO) techniques can notably increase the channel capacity and diversity gain under the condition of ideal propagation channel model[1][2], theoretically MIMO channel capacity enhances linearly with the number of transmitting and receiving antenna. Since then researchers concentrated on digging up the potential diversity gain and multiplexing gain. Unremitting efforts by scholars in the field of information theory[3][4], people gradually realized that capacity of multi-user MIMO system is much more than a point-to-point system.

In strategies of multi-user transmission, the uppermost one is precoding method, i.e. base-station form a wave beam pointed to the thereby precoding can also be called beam-forming technique. In the implementation perspective, precoding algorithms for multi-user MIMO can be sub-divided into linear and nonlinear precoding types. Linear precoding approaches such as zero-forcing (ZF)[5] can achieve reasonable throughput performance with low complexity relative to nonlinear precoding approaches. Nonlinear precoding can achieve near optimal capacity at the expense of complexity and designed based on the concept of Dirty paper coding (DPC)[6] which shows that any known interference at the transmitter can be subtracted without the penalty of radio resources if the optimal precoding scheme can be applied to the transmit signal.

Due to the rank condition imposed by the fact that each user’s pre-coding matrix lies in the null space of all other user’s channels[7], the number of users that can be simultaneously supported with ZF is limited by the number of transmit antennas. For example, for a single antenna users’ case has to be satisfied for complete zero forcing, where and denote the number of transmit antennas at the BS and the total number of users in the system. So we have to select a subset of users before the process of resource scheduling, and this result of selection will directly affect the performance of the system.

Therefore, user subset selection and resource allocation are two core problems of multiuser MIMO system resource scheduling. In this paper, we establish a general cross-layer resource scheduling model. For the first problem,  we propose one user subset selection algorithm with the aim of maximizing the system utility function. For the second we adopt the Opportunistic Fair Scheduling(OFS)[8][9] which can balance the performance of the system and the fair of users. The rest of this paper is organized as follows. Section II describes the downlink multiuser MIMO system including the user subset selection and beamforming scheme. Section III formulates the user subset selection problem and proposes the low-complexity algorithm for solving it. In section IV, we present a cross-layer resource scheduling strategy based on the OFS employing the algorithm of section III. Simulation results are given in Section V. Section VI contains the conclusions.

2. System Model

We consider a downlink of a multiuser MIMO system as shown in Figure 1 with transmit antennas and receive antennas at mobile user. Each user estimates their respective channel state information (CSI) and feedbacks them to BS, let, denote the downlink channel of the user. The scheduler selects one subset of the user to the data according to system QoS requirement and user’s CSI, then finish the physical layer mapping at the side BS.

We assume the frame structure of physical layer is composed of TDM slot with L assignable slots in the system, so the maximal number of user subsets is L as described in Figure 2. It is known that any multiuser MIMO algorithm may have some constraints of the number of transmitting and receiving antennas. Take the block diagonalization beamforming (DBB)[10] for example, this algorithm demands null space of all other users, i.e.. When the number of transmit antenna cannot constraint the scheduler first chooses a subset of users, the result of selection will directly affect the performance of a system

Figure 1. Downlink multiuser MIMO system

Figure 2. Structure of downlink multiuser MIMO frame

In a practical system, not only does scheduler consider the overall performance of the system takes account of the fairness among all users. We introduce the concept of utility function which can reflect the degree of satisfaction of users to some extent, and system utility function can be defined as the total sum of all user utilities. We suppose the transmission rate of user  is  with corresponding utility function expressed as, then the task of schedule is select one subset of users to maximize the system utility function, denoted as

Where is a set of users be transmitted,  represents as rate allocation vector of users concerned with the physical layer transmission scheme,   is global users,   denoted as the optimal scheduling strategy It will theoretically be capable of finding out the best subset by the means of exhaustion method, whereas the complexity of calculation is too high to practical application. Consequently, low-complexity user grouping algorithm of necessity be presented.

3. User Grouping

We define a coefficient for mutual correlations between a user and expressed as, where denotes the normalization factor of a user, i.e. The channel state information can be acquired by the base station. indicates user and user are completely orthogonal;  means correlative; as a general rule. Specifically, we set a threshold ρ. The user with a correlation higher than is considered as highly correlated and are assigned to the different user subset. The correlation coefficient of any two users in one subset is lower than. We next describe the algorithm of user subset selection. In this case, the assumption of channel state information as previously stated has already known in base-station.

The explicit steps of the algorithm are as follows:

Step 1: Construct the matrix of mutual correlations, i.e. takes the empirical value.

Step 2: Search for one of the maximum mutual correlations, if, make the user and user the first user of subset 1 and subset 2 respectively, represented as and.

Step 3: Select users of its correlations with smaller than as the candidate set of subset 1, then add the user from this set with the best orthogonality to subset 1.

Step 4: Find users of correlation with smaller than as the candidate set of subset 1, choose the next user of subset 1 in the same way.

Step 5: Repeat step 4 until the number of users in one subset is up to system constraints or the candidate set is empty.

Step 6: New subset will be generated, provided that there are users not assigned to any subset and their correlations with “new user” are higher than.

Step 7: If the number of subsets exceeds the assignable time slot L, we may augment the value of in order to reduce the quantity.

For example, consider a five-user case. If the correlation matrix is

Figure 2. Subset division results for different threshold value.

4. Cross-Layer Resource Scheduling 

generalized architecture for the OFS in downlink wireless system is proposed in [13,14] and we introduce a new user subset selection module on the basis of OFS as shown in Figure 4. Suppose that there are in total N users in the system. The result of user subset selection is, where M is the sum of subsets.

Figure 4. Cross-layer resource scheduling based on user subset selection.

It is seen from Fig. 4 that at the scheduling interval corresponding to the ith time slot, the inputs to the scheduler are data flows of selected users, and the control parameters produced by the controller:

The scheduler makes the decision of the rates of selected users for the slot i. We have those satisfying is chosen as active users in the currently scheduled subset. The weighted sum rate of mth subset  is defined as

On the other hand, the inputs to the controller corresponding to the time slot are the throughput priorities of users and the rate decision output by (2). The deterministic fairness constraint is given by [8]

In practical systems,  can normally be calculated as the average throughput over a finite-length window. The least mean square-type algorithm is employed to solve the problem of updating the fairness weights [9], denoted a vector as

Define the unbiased noisy observation of  f(w(i)) as

Then, at each control interval, the weight vector w(i)  is updated as[12][13]

For a zero-forcing beam-forming(ZFB) system, the beam-forming vector of selected user can be calculated as[16]

Finally, we propose the resource scheduling algorithm based on the user subset selection.

5. Simulation results

This section, we evaluate the performance of resource scheduling algorithm based on user subset selection as mentioned above. The simulation conditions are as follows. The number of transmit antennas at the BS is,  at MS; the total number of users in the system is; the transmit and noise power are  and; the objective SINR is

A. Efficiency Of Subset Selection

We first compare the performance of instantaneous sum rate with the method of exhaustion. The threshold is; simulation time is 50 slot. As depicted in Figure 5, the performance of algorithm mentioned above is close to that of exhaustion method. It is well worth exchanging small degradation of performance to the large reduction of computational complexity. The principal cause of this degradation is that the period of subset selection is much longer than scheduled, the computational complexity of grouping can be considered negligible. Under the condition of this simulation, a number of user subsets are 9, the corresponding calculated amount is 9, while the exhaustion method is 9,

Figure 5. The comparison of the throughput

B.     Effect of threshold value

Figure 6. Throughput changes with threshold value ρ

Next, we observe the system throughput while the threshold value increases from 0.1 to 0.9 as shown in Figure 6. The performance climbs when is from 0.1 to 0.3, but declines in residual value. The reason for this phenomenon is explained as follows. When is very small approached to zero, the criterion for spatial orthogonality is very strict, then there may be just one or two users in one subset that limits the gain of multiplexing. When takes a relatively large value, more spatial correlative users access to a subset that causes the decrease of performance.

B.     Fairness of users

Thirdly, we review another crucial index of resource scheduling: fairness. The prospective throughput proportion of the 16 users. The fairness as shown in Fig.8 when the time slots are 1000 is better than the case in Figure 7 for 500-time slots. This result corresponds with long-term fairness feature of OFS [13] and demonstrates user grouping does not destroy the fairness between all of the users.


Figure 7. User average throughput during 500 slots

Figure 8. User average throughput during 1000 slots

6. Conclusions

We have developed a framework for downlink multiuser MIMO system employing multiple transmit antennas, beam forming, and user subset selection to achieve efficient resource scheduling. Subset selection algorithm in this paper guarantee system satisfies the requirement for preprocessing meanwhile not brings the system large computational amount. We present simulation results to demonstrate that the grouping algorithm can effectively find the optimal user subset with good convergence performance, enhances the system spectrum efficiency and greatly reduces the complexity of resource scheduling.


[1]    E.T. Telatar – Capacity of multi-antenna Gaussian channels, AT&T Bell Labs Internal Tech.Memo., June 1995.

[2]   G,J. Foschini and M.J. Gans – On limits of wireless communications in fading environment when using multiple antennas, Wireless personal communications, Mar.1998, vol.6, pp.311-335.

[3]  S.Shamai and A.D.Wyner – Information-theoretic considerations for symmetric, cellular, multiple-access fading channels, IEEE Trans. Inform. Theory, Nov. 1997, vol.43, pp. 1877-1991.

[4]   S.Vishwanath, N.Jindal, and A.Goldsmith – On the capacity of multiple input multiple output broadcast channels, in Proc. ICC 2003, New York, Apr. 2002, pp.1444-1450.

[5]   Jinsu Kim. Sungwoo Park, Jae Hong Lee, et al. – A scheduling algorithm combined with zero-forcing beamforming for a multiuser MIMO wireless system, in Proc. IEEE VTC-2005-Fall, Dallas, Sep. 2005, vol.1, pp.211-215.

[6]   M.Costa(May 1983) – Writing on dirty paper, IEEE Trans. Information Theory 29:439-411.

[7]  Yoo.Taesang,  A.Goldsmith – On the optimal of multiantenna broadcast scheduling using zero-forcing beamforming, IEEE J.Sel. Areas Communication.  Mar. 2006,  vol.24, pp.528-541.

[8]  Min li, Collings I,B, Hanly S.V, Chunshan Liu, Whiting P – Multicel Coordinated Scheduling with multiuser zaro-forcing beamforming, IEEE Transactions on Wireless Communication, V15, n 2, p 827-42, Feb.2016.

[9]  Huang, Shengchun; Yin, Hao; Wu,; Leung, Victor C. M, – User selection for multiuser MIMO downlink with zero-forcing beamforming, IEEE Transactions on Vehicular Technology, v 62, n 7, p 3084-3097, 2013.

[10] Ping Wang, Lei Ding, Huifang Pang, Fuqiang Liu, Nguyen Ngoc Van – Zero Forcing Beamforming Based Coordinated Scheduling Algorithm for Downlink Coordinated Multi-Point Transmission System, IEICE Transations on Communications, Vol.E98-B No.2, Feb 2015.

[11] Zhu Fengchao, GaoFeifei, Yao Minli – Zero-forcing beamforming for physical layer security of energy harvesting wireless communication, EurasipHournal on Wireless Communication and Networking, v2015, n 1, p 1-9, December 1, 2015.

[12] T Tandai,HMori,M Takagi – Cross-layer-optimized user grouping strategy in downlink multiuser MIMO systems, IEEE Vehicular Technology Conference, 2009:1-6

[13] Chuxiang Li, Xiaodong Wang – Adaptive opportunistic fair scheduling over multiuser spatial channels, IEEE Trans. Communications. Oct, 2005 vol.19, no.10, pp.1708-1718.

[14] Patil, Prakash, BorseChaitali – Fair resource allocation to MIMO wireless system using Opportunistic Round Robin scheduling algorithm”, Advance Communication Technology and Application for Society, ICPC 2015, April 15,2015.

[15] Choi, L., Murch, R.D., – A transmit preprocessing technique for multiuser MIMO systems using a decomposition approach, IEEE Trans. on Wireless Communication, Oct. 2004, vol. 3, pp.20-24.

[16] M.Schubert, H.Boche – Solution of the multiuser downlink beamforming problem with individual SINR constraints, IEEE Trans. Veh. Technol.,  Jan.2004, vol.53, pp18-28.


Nguyen Ngoc Van is a lecturer at School of Electronics and Telecommunications in Hanoi University of Science and Technology (HUST). He received the degree of Bachelor and Master in Electronics and Telecommunications from HUST, Vietnam, in 2000 and 2003. From 2009 to 2012 he pursues his PhD degree in communication engineering at Tongji University, Shanghai, China. His main interests are in Relaying and MIMO technologies in broadband wireless communication

%d bloggers like this: