Real-time scheduling for wireless multiuser MISO systems under different fairness criteria

REAL-TIME SCHEDULING FOR WIRELESS MULTIUSER MISO SYSTEMS UNDER DIFFERENT FAIRNESS CRITERIA Diego Bartolom´ e, Daniel P. Palomar, and Ana I. P´ erez-Neira ∗ [email protected], {daniel, anuska}@gps.tsc.upc.es Centre Tecnol`ogic de Telecomunicacions de Catalunya (CTTC) Universitat Polit`ecnica de Catalunya (UPC) c/ Gran Capit`a 2-4, Edifici Nexus I, Planta 2 c/ Jordi Girona 1-3, M`odul D5, Campus Nord UPC 08034 Barcelona (Spain) 08034 Barcelona (Spain) ABSTRACT This paper deals with the spatio-temporal scheduling of a set of users for downlink transmission in a cell where the base station is provided with multiple antennas. Two main issues are addressed: how the users are distributed into space-time groups and how the available power is allocated among the users within a group. Since the former is an NP-complete combinatorial problem, we develop fast and low-complexity algorithms, which might be capable to fulfill the real-time requirements of a practical scheduling scheme. Regarding the power allocation, we consider different fairness criteria under the capacity point of view. To be precise, we compare the alternatives of equal rate and maximum sum rate with our proposed equal proportional rate solution. 1. INTRODUCTION Multiple Element Antenna (MEA) systems may provide a large increase in capacity for future wireless communications standards. Here, we assume that the Base Station (BS) is provided with multiple antennas and the terminals have a single one. Particularly, the problem addressed in this paper consists of the scheduling of a large set of users in the downlink of a TDMA system. The solution to this problem can be separated into three different parts: i) the beamforming technique, ii) the power allocation schemes, and iii) the division of users into groups. Optimal beamforming is solved in [1], but this kind of techniques may be difficult to implement in a practical system if there are real-time and low-complexity requirements. Therefore, a Zero Forcing (ZF) design criterion might provide an acceptable performance with much lower computational load [2]. Furthermore, [2] proves the benefits of assigning each antenna from the BS to a different user instead of assigning all the antennas to the same user. Once a beamforming design is chosen, the total available power shall be distributed among the users. In the literature, two main techniques can be found for this difficult question: the maximum sum rate and the equal rate [4]. Besides, the definition of fairness is not clear. One could consider that fairness implies assigning the same rate to all users, while the so-called proportional fairness aims for providing a higher rate to the users closer to the BS. It is not clear either, which is the optimum rate sharing. Finally, if a huge amount of users are active in the cell, the issue of clustering1them becomes an NP-hard combinatorial prob- ∗ This work has been supported by the CTTC, by the Spanish government under FIT-070000-2000-649 (Medea+ A105 UniLan), TIC200204594-C02 and HF2001-0055, and also by the Catalan government thanks to grants 2001SGR 00268 and 2003FI 00190. 1Clustering refers to the partition of the active users into groups. lem. In [3] the author solves this problem by a graph-theoretical technique, whereas in [4] we proposed the application of Simulated Annealing to this problem. However, this kind of techniques are too costly to be implemented in real-time, which is a mandatory requirement for a practical scheduling technique. This paper addresses those three problems. First, in Section 2 we select ZF as the beamforming design criterion for the sake of simplicity. After that, we focus on the power allocation techniques, comparing the traditional equal rate and maximum sum rate approaches to our novel equal proportional rate scheme. This solution comes naturally with the definition of a fairness index that relates the actual rate with that a user would get if it were alone in the group (see Section 3 for further details and discussions). Finally, in Section 4 we investigate on simple techniques for the user clustering, which might be implemented in real-time and provide a better trade-off between performance and complexity than those in [3] and [4]. The simulations in Section 5 show the performance of the proposed schemes before the final conclusions. 2. PROBLEM STATEMENT In the following, boldface capital (lowercase) letters refer to matrices (vectors). The conjugate transpose of ais given by aHand the element at row ith and column jth of Ais denoted by [A]i,j . The natural logarithm of ais log(a)and (a)+= max(0, a). We consider the downlink of a communication system, where the BS is provided with Qtransmit antennas, although the notation and solutions presented henceforth can be also applied to the uplink. Let K≥Qbe the number of active users in the cell, each having a single antenna. The users shall be distributed into Ggroups. Each group is scheduled for transmission in a different time slot, whereas the Kgusers in the gth group are served simultaneously by a Space Division Multiple Access (SDMA) scheme. As stated before, we have to specify first a bemforming design. Then, the received signal vector for group gat instant nis: y(n) = HBs(n) + w(n)∈CKg×1,(1) where the index gdenoting the group has been omitted for simplicity. The kth position of vector y(n) (s(n)) is the received (transmitted) signal for user k.His the Kg×Qcomplex flatfading channel matrix, the ith row of which contains the 1×Q vector of the channel gains for the ith user, i.e. hH i, which is essentially determined by the Direction of Arrival (DOA) of the user and a scaling due to the path-loss and fast fading, which is the same for each antenna element2. Further, the components of the 2Note that in the more general case of independent fading for each ele- noise vectors are i.i.d. gaussian random variables with zero mean and variance σ2 w. Finally, the beamvectors for the Kgusers are gathered in the matrix B=b1b2...bKg∈CQ×Kg. First, we would like to separate the effect of the channel and that of power allocation. Therefore, given a set of groups, the problem is divided into two parts: first, we apply a unitary beamforming for each user in a group; second, the best-suited strategy for the power allocation within a group is chosen (Section 3). In this paper, we have applied a ZF beamformer design for the downlink communication for simplicity. ZF implies that the Kg channels become parallel and orthogonal, thus there is no interference among the users belonging to the same group. Therefore, we can express the beamforming matrix as B=e BDβ, where e Bdenotes the unitary beamforming and Dβis a diagonal matrix representing the allocated power for each user, i.e. Dβ= diag β1, β2,...,βKg. The effect of the channel is considered in the diagonal matrix He B=Dα=diag α1, α2,...,αKg. With all this, the received signal for user kcan be expressed as: yk(n) = αkβksk(n) + wk(n),1≤k≤Kg,(2) where, as stated, we have a set of parallel and orthogonal channels for each group. With these considerations, we have not yet described how the beamformer is computed. To obtain the beamvector, the ZF criterion requires that Hbk=1k,∀k. Additionally, we apply the normalization factor αk,∀kto guarantee a unitary beamforming. Then, the beamvector is computed as3: e bk=HHHHH−1 1kαk,(3) where αk= 1/q(HHH)−1k,k. We have then two pending issues: the strategies for the power allocation (Section 3) and how the users are divided into groups (Section 4). 3. FAIRNESS AND POWER ALLOCATION The criteria for the power allocation are determined by the fairness definition we consider, for which there are several points of view. A first possibility would consist of assigning the same rate to all users, which will appear as the best solution at a first sight. However, the users that are closer to the BS, i.e. those having a greater mean Signal to Interference and Noise Ratio (SINR), should be granted a better rate if we take into account the proportional fairness rule. On the the other hand, the second option can optimize the total performance of the group regardless of some users that might not even be allocated for transmission. The former is the equal rate scheme, whereas the latter is the maximum sum rate. In this paper, we would like to have an intermediate solution: we wish to have a mean rate slightly lower than what the maximum sum rate achieves, but increasing the fairness. For this purpose, we need to specify first a fairness criterion. In agreement with the proportional fairness, a well-suited index seems to be the one that links the actual rate obtained by a certain user Ckwith the rate it ment, the algorithms would certainly work. However, the DOA would no longer mean a physical angle at the BS. 3The pseudo-inverse reduces to the inverse if we allocate Qusers to Q antennas. And strictly speaking, it is ZF up to a scalar for each substream. would achieve if it were alone in the group Cmax k: Ck=log 1 + |αk|2|βk|2 σ2 w,(4) Cmax k=log 1 + |αk|2PT σ2 w,(5) where SINRk=|αk|2|βk|2 σ2 wand SINRmax k=|αk|2PT σ2 w 4can be defined. The proposed Fairness Index (FI) is then the following: FIk=Ck Cmax k ,(6) which is clearly in the range 0≤FIk≤1. The upper bound occurs if all the available power is allocated to user k, thus getting the capacity Cmax k, while the lower bound reflects a situation of no scheduling or null power. Based on this FI, we propose our novel equal proportional rate in Subsection 3.3. Finally, note that we are evaluating the instantaneous fairness. We can further increase the capacity by taking into account the temporal variation of the channel as in [5]. 3.1. Equal Rate Scheme In this case, we want the same SINR (rate) for all users, regardless of their position or channel quality. Therefore, we have to impose that the product αkβkis the same for all users and equal to ¯ β. This is equivalent to the maximization of the minimum capacity for all users within a group. Recalling the definition of the capacity Ck in (4), the problem is max |βk|2min kCk(7) s.t. Kg X k=1 |βk|2≤PT,(8) where the total output power is limited by PTdue to regulatory issues. Applying the restriction on the total power, ¯ βreduces to ¯ β=sPT tr (HHH)−1,(9) where tr denotes the trace operation. With all this, the capacity is the same for all users in the group, Ck=C, ∀k, and it is given by C=log 1 + 1 σ2 w PT tr (HHH)−1!.(10) 3.2. Maximum Sum Rate In this case, instead of guaranteeing the same SINR for all users, we would like to optimize the global performance of the cell, without considering fairness. It could happen that some users in a group might not be able to transmit, allowing other users to have a higher SINR and thus a higher capacity. Then, we maximize the total capacity subject to an instantaneous power constraint, i.e. max |βk|2 Kg X k=1 Ck(11) s.t. Kg X k=1 |βk|2≤PT.(12) 4Note that in this case |αk|2=khkk2. Table 1: Initialization procedure for user clustering 1. Compute the cost of all possible combinations of two users Ji,j ,∀i6=j. 2. Sort the cost values in descending order in the vector cs, keeping the information of the indexes of users iand j. Set lto 0. 3. Increase land select that position lin cs. If users i, j corresponding to index lhave not yet been assigned, separate them in different groups g(i)6=g(j). Note that g(i)is the group where we put user iand that only one user shall be assigned per group. 4. If the number of assigned users is not G, go to step 3. Taking derivatives of the Lagrangian of the problem with respect to the power allocation factors |βk|2and to the Lagrange multiplier µ, we obtain the following water-filling algorithm: |βk|2=µ−1−σ2 w |αk|2+ ,(13) where µis chosen to satisfy the power constraint in (12) with equality. For implementation issues, we refer the reader to [6]. With this approach, the capacity for the kth user is: Ck=log µ−1|αk|2 σ2 w+ .(14) 3.3. Equal Proportional Rate In this case, for each group we want to equalize and maximize the FI, i.e. the users in a group shall have the same proportion of the rate they would get if they were alone in the group, thus yielding to a proportionally fair solution. This can be expressed as max δ(15) s.t. FIk=δ, ∀k, (16) Kg X k=1 |βk|2≤PT.(17) We expect to have a lower capacity than in the sum rate, but we shall overcome the problem of assigning a null power to certain users. The solution to this problem can be easily found, but it is left out for space limitations. 4. USER CLUSTERING As stated before, user clustering refers to the separation of the users into groups. The optimal solution would imply exhaustive search or techniques based in graph-theory [3], which are NP-hard combinatorial problems. On the other hand, Simulated Annealing can solve the problem in much less time [4], but it may neither fulfill the real-time limitations. Suboptimal approaches where developed in [4]. Since the aim was assuring the same rate for all users (equal rate scheme), the proposed solution had to compute the minimization of the tr HHH−1, which is tantamount to the maximization of the capacity as it is seen in (10). Since the approach in [4] could still be unfeasible for a practical system, we propose here even simpler techniques. Intuitively, the users that are closer in terms of DOA should be distributed into separate groups, since they would require an increase in power. Table 2: Iterative User Clustering 1. Build matrix Das in (19). 2. Store the cost values, i.e. the ratio between the maximum and minimum values for each row in matrix D, in cand keep the information about the user and about the group having the minimum cost for that user. 3. Sort cin descending order, csis the sorted vector. Set position index lto 0. Note that g(l)is the group having minimum cost for the user at position l. 4. Increase land select that position in the sorted vector cs. If the group g(l)has not been filled in current iteration, assign to group g(l)the user corresponding to index l. 5. Go to step 4 until lpoints to the last element of csor if the G groups have been filled by a different user at this iteration. 6. Go to step 1 until every user is assigned to a group. Table 3: Simple User Clustering 1. Sort the users in descending order of khk2in cand set k= 0. 2. Increase index k, and select that position in c. For that user, build the vector dkfor the G0available groups [dk]g0= maxlJk,l. 3. Assign the user corresponding to index kto the group having minimum dk. 4. Go to step 2 until all users are assigned to a group. Therefore, we use the scalar product as a cost function for the clustering techniques, which has a meaning of angle. For each pair of users we define the grouping cost by the following expression Ji,j =hH ihj khikkhjk.(18) Then, the initialization procedure of the two algorithms is described in Table 1. Essentially, the users closer in terms of angle, those having a greater cost in (18), are separated into different groups. After that, Gusers are assigned to Ggroups. Then, at each iteration of the algorithm we need to compute the cost of assigning the user kth to the G0available groups5, i.e. [D]k,g0= max lJk,l,(19) which is the worst case regarding the user clustering, i.e. the cost is determined by the user closer to the desired user in terms of angle. Table 2 describes the first method, which tries to compute iteratively the best group for the users. The main idea behind is to allocate first the users having a greater dispersion in being assigned to the groups, i.e. the users that would penalize the system if they are not assigned to the best possible group. On the other hand, a simpler algorithm has also been evaluated: we sort the users in descending order of the module of hi, and start assigning the users to the groups. Now, the cost for each group is defined by the maximum scalar product, and we assign the user to the group where it is lowest, i.e. to the best worst case (min-max). This is summarized in Table 3. 5. SIMULATIONS In the simulations we have considered a BS with Q= 4 transmit antennas and five groups G= 5 in a fully-loaded system, thus 5We consider that group g0has K0 gusers at that iteration, 1≤l≤K0 g. 0 5 10 15 20 25 30 0 1 2 3 4 5 6 7 8 9 10 SINR [dB] Capacity per user [bits/s/Hz] Outage Mean Capacities (90%) for user clustering with equal proportional rate, Q=4, Nusers=20 Max−min Iterative User Clustering Simple Method Random Groups Figure 1: Mean capacity for the user clustering techniques with equal proportional rate power allocation. the total number of users is K= 20. The channel is flat fading and consists of an equal path-loss and fast fading for all antennas and a DOA, which is distributed uniformly between −60◦and 60◦ (sectored antennas at the BS). The SINR6goes from 0 to 30 dB. First, simulations have been conducted to evaluate the user clustering schemes. In Figure 1, we plot the outage capacity for the users vs. the SINR. We see the performance gain it is obtained if the users are distributed into groups in an intelligent manner rather than with a random scheduling. The best trade-off between performance and complexity is obtained by our simple iterative method, face off the max-min technique developed in [4]. Therefore, the figures are given for this strategy in the following. Note also that the simple user clustering provides an intermediate performance between the random scheduling and the iterative method with much less complexity than the latter. Figure 2 evaluates the power allocation strategies in terms of maximum, mean, and minimum outage capacities for the users. As expected, the mean capacity is maximized by the sum rate approach, but the low minimum capacity indicates that some users might be penalized. The equal rate technique has the same maximum, minimum, and mean values, coming from the design of the problem. The intermediate performance is achieved by the equal proportional rate scheme, which increases the rate of the poor users paying the price of some loss in terms of mean capacity. Finally, in Figure 3 we evaluate the FI for the three proposed techniques. In that case, the FI is optimized by the equal proportional rate approach. Further, we see that the equal rate technique is not fair, since we are wasting some power in poor users and the dispersion from the maximum and minimum fairness index is high. Interestingly, the maximum sum rate solution tends to the equal proportional rate when the power is increased. 6. CONCLUSIONS In this paper, we have studied two main problems, namely the spatio-temporal clustering of a set of users for simultaneous transmission and the power allocation within a given group. We have proposed simple clustering techniques based on the scalar product, providing a good performance compared to other existing approaches. Regarding the power allocation, an evaluation of the 6In this case, the SINR refers to the ratio PT σ2 w. 0 5 10 15 20 25 30 0 2 4 6 8 10 12 14 SINR [dB] Capacity per user [bits/s/Hz] Outage Capacities (90%) for power allocation, Q=4, Nusers=20 Max Sum Rate − Max.Cap. Max Sum Rate − Mean Cap. Max Sum Rate − Min.Cap. Equal Prop. Rate − Max.Cap. Equal Prop. Rate − Mean Cap. Equal Prop. Rate − Min.Cap. Equal Rate − Max.Cap. Equal Rate − Mean Cap. Equal Rate − Min.Cap. Figure 2: Outage maximum (dashed), mean (solid), and minimum (dash-dotted) capacities for the proposed power allocation strategies. The groups are formed by the iterative user clustering. 0 5 10 15 20 25 30 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 SINR [dB] Fairness index Outage Fairness index (90%) for power allocation, Q=4, Nusers=20 Max Sum Rate − Max. FI Max Sum Rate − Mean FI Max Sum Rate − Min. FI Equal Prop. Rate − Max. FI Equal Prop. Rate − Mean FI Equal Prop. Rate − Min. FI Equal Rate − Max. FI Equal Rate − Mean FI Equal Rate − Min. FI Figure 3: Outage maximum (dashed), mean (solid), and minimum (dash-dotted) fairness index for the power allocation strategies. The groups are formed by the iterative user clustering. traditional equal rate and maximum sum rate techniques is performed. The best trade-off is obtained, though, by our novel equal proportional rate scheme. 7. REFERENCES [1] M. Bengtsson and B. Ottersten, “Optimal and suboptimal transmit beamforming,” in Handbook of Antennas in Wireless Communications, Lal Chand Godara, Ed. CRC Press, 2001. [2] R.W. Heath and M. Airy and A.J. Paulraj, “Multiuser Diversity for MIMO Wireless Systems with Linear Receivers,” in Asilomar, 2001. [3] R. Zhang, “Scheduling for Maximum Capacity in SDMA/TDMA Networks,” in ICASSP, 2002. [4] D. Bartolom´e, A. Pascual-Iserte and A. I. P´erez-Neira, “Spatial Scheduling Algorithms for Wireless Systems,” in Proceedings of ICASSP’03, April 2003. [5] D.N.C. Tse, “Multiuser Diversity in Wireless Networks,” Wireless Communications Seminar, Standford University, April 2001. [6] D. P. Palomar and M. A. Lagunas, “Joint Transmit-Receive SpaceTime Equalization in Spatially Correlated MIMO channels: a Beamforming Approach,” to appear in IEEE Journal on Selected Areas in Comm., June 2003.