Performance Analysis of SNR-Based Scheduling Policies in Asymmetric Broadcast Ergodic Fading Channel

Abstract

We analyze the performance of SNR-based scheduling algorithms in broadcast ergodic fading channels where multiuser selection diversity is exploited. At each channel state, the user with the highest weighted signal-to-noise ratio is selected to be transmitted. The use of weights associated to the users allows us to control the degree of fairness among users and to arrange them according to a prescribed quality of service. These weights parametrize the scheduling algorithms so each set of weights corresponds to a specific scheduling algorithm. Assuming Rayleigh fading broadcast channel, we derive a closed-form expression for the achievable user's rates as a function of the scheduling algorithm, the channel fading statistics of each user, and the transmit power. With the help of this expression, we solve some interesting inverse problems. For example, for a given arbitrary channel statistics we obtain the optimum scheduling algorithm to achieve a prescribed set of users' rates with minimum transmit power.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Recommended by Kwang-Cheng Chen

1, Department of Communications Engineering, University of Cantabria, Avda. de los Castros s/n, 39005 Santander, Spain

Received 1 July 2008; Accepted 26 January 2009

1. Introduction

It is well known that the capacity region of broadcast ergodic fading channels is achieved by superposition coding at the transmitter and successive interference cancellation at the receivers (SC-SIC). Using SC-SIC, the transmitter transmits simultaneously to all users using multiresolution coding, and the receivers perform successive decoding. Although optimum in terms of capacity, SC-SIC is complex, and it is not necessarily the best method to use in practical systems because decoding and channel estimation errors can degrade its performance significantly [1].

More feasible are the orthogonal TDMA strategies based on users opportunistic scheduling, where a single user is selected to be transmitted at each fading state. Once a user is selected, the transmitter allocates all the available resources to him (bandwidth and power) utilizing a code adapted to the channel state. Since the channels between the base station and the users usually fade independently, this scheme effectively exploits the multiuser diversity inherent to the broadcast (BC) channel (see, e.g., [2] and references therein). Opportunistic scheduling is commonly used in modern wireless standards as IS-856 (also called CDMA 2000 1xEV-DO), mobile WIMAX, and HSPA [3-5].

In multiuser diversity, the resulting long-term users' rates are determined by the specific scheduling policy. Many criteria have been proposed to schedule the users. Among them, we focus on the so-called SNR-based scheduling policies where the user with the highest weighted signal-to-noise ratio (SNR) is selected to be transmitted. A particular case is the so-called "absolute SNR-based scheduling" (ASS) [6], where the user with the highest channel gain at each channel state is selected. It is well known that ASS maximizes the overall throughput (sum-rate) [2]. Although ASS achieves the sum-rate, it favors users who have good average channel conditions producing quite different individual users' rates in asymmetric broadcast channels. On the other hand, the "normalized SNR-based scheduling" (NSS) schedules the users according to the instantaneous channel gain normalized by its own average [6, 7]. NSS strategy favors users with poor average channel conditions and penalizes advantaged users producing similar users' rates but at expense of a lower overall throughput. In fact, there is a tradeoff between maximizing the overall throughput and achieving throughput fairness. Other common scheduling criterion is based on the instantaneous achievable rates instead on the SNR. In this case the base station transmits to the user with the highest normalized achievable rate [2, 8, 9]. Since the achievable rate is monotonically increasing with the SNR, both scheduling criteria are interchangeable. Further, in BC channels the power constraint at the base station is usually based on the maximum power rather than the long-term average power. Therefore, we assume that the transmit power is constant.

Some performance analyses of opportunistic scheduling can be found in the technical literature. In [6, 7] closed-form expressions for the achievable rates using ASS and NSS are derived. In [10] analytical expressions for the sum-rate of BC channel are derived using ASS and considering different adaptive power allocation strategies. All these performance analyses are restricted to specific scheduling algorithms.

In this work we derive a general closed-form expression for the rates achievable by any SNR-based scheduling algorithm. It generalizes other expressions proposed in the technical literature that are restricted to a single specific scheduling strategy (e.g., ASS and NSS). Each scheduling algorithm is parameterized by a set of weights assigned to the users, so the user with the best weighted channel is selected at each channel fading state. There is a point-to-point correspondence between the scheduling weights and the boundary points of the achievable rates region. The derived expression explicitly describes this relationship. The expression is a simple function of the channel fading parameters, the transmitted power, and the scheduling weights. With the help of this function we solve some interesting inverse problems. For example, the computation of the minimum required transmit power and the optimum scheduling strategy to achieve a given users' rates. Other problem considered is the computation of the optimum scheduling preserving a given relationship among the users' rates for a given transmit power. These inverse problems are formulated as systems of nonlinear equations involving the derived expression.

The rest of the paper is organized as follows. Section2 shows the BC ergodic channel model. Section 3 presents the parametrization of the SNR-based scheduling policies, where the ASS and the NSS are particular cases. In Section 4 we derive the closed-form expression for the achievable users' rates as a function of the channel fading statistics, the transmit power, and the scheduling algorithm. In Section 5 we pose the inverse problems as set of nonlinear equations involving the derived expression. Simulation results are presented in Section 6. Finally, conclusions are drawn in Section 7.

2. Channel Model

A narrowband broadcast channel with K users is considered. We assume that the transmitter and receivers have a single antenna. The transmitter is subject to an average power constraint denoted by P . We assume independent and identically distributed (i.i.d.) AWGN noise at the Rx antennas, with single-sided power spectral density denoted by _N0 for all users. The receivers' bandwidth is denoted by B , so the noise power at the receivers is B_N0 . The baseband-equivalent channel response between the transmitter and the k th user is denoted by _hk , k=1,...,K . We assume that the _hk are independent and differently distributed (i.d.d.) zero-mean circularly symmetric complex Gaussian (ZMCSCG) random variables. Then, the channel power gains _gk =^{|_hk |2} will be exponentially distributed with cumulative distribution functions (c.d.f.) given by [figure omitted; refer to PDF] where _g¯k denotes the average power gain for the k th user channel: _g¯k =E{_gk } . The probability density functions (p.d.f.) will be [figure omitted; refer to PDF]

We assume, without loss of generality, that the channel is normalized so ^g¯T 1=K , where g¯=[_g¯1 ,_g¯2 ,...,_g¯K^]T and 1 is the all-ones vector of size K . Under this normalization, the SNR averaged for all users and fading states will be ρ=P/B_N0 . Note that the average SNR and the transmit power are interchangeable.

3. SNR-Based Scheduling

The SNR-based scheduling strategies can be parameterized by a set of normalized weights associated with the users, so the system selects the user with the highest weighted channel response.

The set of all possible weight vectors is the subset in ^[real]K given by [figure omitted; refer to PDF]

Then, at each channel state, the system selects the user according to _{arg maxs} {_ηs } , where _ηs =_wsgs .

In particular, the ASS and the NSS algorithms correspond to w=1 and w=a1[sm middot]/ g¯ , respectively, where a is a normalization factor to fulfill the constrain of (3), and [sm middot]/ denotes elementwise division.

Different scheduling weights lead to different achievable users' rates. Therefore, there is a one-to-one correspondence between all the possible weight vectors and the points on the boundary of the rates region. The achievable rates using ASS and NSS are two of such points.

4. Achievable Rates

Let us define the following effective channel gain for the s th user: [figure omitted; refer to PDF] where _η-s =_maxk≠s {_wkgk } . The p.d.f. of ^gs* can be expressed as follows: [figure omitted; refer to PDF] where δ(x) is the Dirac delta function, _fs (x) is given by (2), and _{F -s} (x) is the c.d.f. of _η-s given by [figure omitted; refer to PDF] This expression can be expressed as follows: [figure omitted; refer to PDF] where S is the set of binary words of length K , _ci =(-^{1)iT 1} , _is denotes the s th component of the vector i , and q=[(_g¯1w1^{)-1(_g¯2w2 )-1} ...^{(_g¯KwK )-1]T} . From (7) and (2), the second term of (5) reduces to [figure omitted; refer to PDF]

The rate for the s th user will be the rate of the effective point-to-point channel with channel gain ^gs* . Then, for a given channel distribution g¯ , scheduling vector w and average SNR ρ , the achievable rate by the s th, user will be [figure omitted; refer to PDF]

Substituting (8) in (9), this can be expressed as follows: [figure omitted; refer to PDF] where _E1 ([sm middot]) denotes the exponential-integral function of the first order [11]. Equation (10) explicitly provides the coordinates of the boundary point of the rates region relative to the scheduling vector w , for a given channel distribution g¯ and average SNR ρ . It has some interesting properties.

(i) _Rs (g¯,w,ρ) is always a continuous strictly increasing function of ρ , for any g¯ and w . It is demonstrated from (9) that the log function is continuous strictly increasing and that ^fs* (x) is positive and continuous. Therefore, for a given channel distribution g¯ , the boundaries of the rates region for different values of ρ never overlap.

(ii) For any g¯ and ρ the rates region is convex.

(iii): _Rs (g¯,w,ρ) is continuously differentiable in the convex region _Sw . The derivatives with respect to w are [figure omitted; refer to PDF] where x=_ws^qT i/ρ .

5. Inverse Problems

With the help of expression (10), it is easy to solve some interesting inverse problems.

Problem 1.

Given a channel distribution ^g¯o objective rates vector ^Ro =[^R1oR2o ...^RKo]T , to find the minimum required average SNR (or transmit power) and the scheduling vector to achieve such rates, this problem can be formulated as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

Considering the constrain ^wT 1=K , the expression (12) is a system of K nonlinear equations with K unknowns. Since R(^g¯o ,w,ρ) is one-to-one and continuous, there will be a unique solution.

Problem 2.

Given a channel distribution ^g¯o and an average SNR ^ρo , to find the maximum achievable rates preserving a given relationship among the users' rates as well as the scheduling vector to achieve such rates, this problem can be formulated as follows: [figure omitted; refer to PDF] where a is a scale factor to be determined, and ^r0 is any vector fulfilling the desired relationship among the users' rates. Considering the constrain ^wT 1=K , expression (14) is a system of K nonlinear equations with K unknowns including a . Again, it has a unique solution (^w* ,^a* ) which provides the required scheduling strategy and the maximum achievable rates R=^a*ro .

Other similar problems can be formulated. Due to the properties of R(g¯,w,ρ) (see Section3), all these problems are well suited to be solved by using conventional gradient-based iterative algorithms. For each problem, the Jacobian matrix can be easily obtained from (11).

6. Numerical Results

Expression (10) gives the achievable users' rates for a given broadcast channel distribution, defined by g¯ , for a given weight vector w and for a given average SNR ρ . By varying w in (10), we obtain the boundary points of the rates region. As examples, Figures 1 and 2 show the rates regions for a two-users broadcast channel where _g¯1 / _g¯2 =2 and _g¯1 / _g¯2 =10 , respectively. The different curves correspond to different values of average SNR, or equivalently to different transmit powers. The figures also show the points that give the maximum sum-rate, which is achieved using ASS.

Figure 1: Ergodic rates' regions for a two-users channel when _g¯1 / _g¯2 =3 dB .

[figure omitted; refer to PDF]

Figure 2: Ergodic rates' regions for a two-users channel when _g¯1 / _g¯2 =10 dB .

[figure omitted; refer to PDF]

Figures 3 and 4 show the individual users rates, as a function of the average SNR, for a 10-users channel using NSS and ASS, respectively. The average channel gains are linearly distributed according to _g¯k =ak, k=1,...,K , where a=2/(K+1) is a constant determined by the channel normalization and K=10 .

Figure 3: Individual rates for the 10-users channel using NSS.

[figure omitted; refer to PDF]

Figure 4: Individual rates for the 10-users channel using ASS.

[figure omitted; refer to PDF]

Figure 3 shows that the NSS algorithm is not totally fair in terms of rates (it is strictly fair in terms of channel access time). The fair scheduling vector can be obtained solving Problem 2 for ^ro =1 . Figure 5 shows the optimum weights and the resulting individual rate for different values of average SNR. The optimum scheduling vector changes slowly with the average SNR, especially in the high-SNR regime. We have used a conventional iterative Gauss-Newton method to solve (14). Figure6 shows the convergence of the users' weights for ρ=10 dB. Starting at _w0 =1 , the algorithm finds the solution after only 4 iterations. To reduce the number of iterations, the starting weights can be heuristically chosen as a function of the average channel gains by assigning higher weights to the worse users' channels. For example, _w0 =1[sm middot]/g¯ would be a better starting point.

Optimum weight vectors for fair scheduling in the 10-users channel and individual rate.

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Figure 6: Convergence of the weight vectors for fair scheduling in the 10-users channel using a conventional Gauss-Newton method. The average SNR is ρ=10 dB.

[figure omitted; refer to PDF]

Now, assume that we are interested in achieveing different users' rates in the same asymmetric channel. The users are divided in two groups; so the objective rates for the first group double the rates for the second. The first group comprises the users from one to five and the second group from six to ten. To obtain the required scheduling vectors, we solve (14) for ^rko =2, k=1,...,5 and ^rko =1, k=6,...,10 . Figure 7 shows the achievable individual rates and the scheduling weights to obtain such rates relationship. The convergence to the optimum weights, using a conventional Gauss-Newton algorithm, is depicted in Figure 8 when the average SNR is ρ=10 dB. After 5 iterations, the algorithm finds the optimum weights.

Optimum weights and achievable rates for the two groups of users. The first five curves correspond to the first five users.

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Figure 8: Convergence of the weight vectors in the 10-users channel using a conventional Gauss-Newton method. The average SNR is ρ=10 dB.

[figure omitted; refer to PDF]

As example of Problem 1, we compute the minimum average SNR to achieve the following set of rates ^Rko =k/K, k=1,...,K . Again, we consider a 10-users channel but now the average channel gains are given by _g¯k =a for k=1,...,4 and by _g¯k =aΔ, for k=5,...,8 , where a=2/(Δ+1) . Note that the users are grouped in two sets. In each set the channels are identically distributed. The ratio between the average channel gains of the two sets is determined by the parameter Δ . Figure 9 shows the required average SNR to achieve the objectives rates ^Rko =k/Kbps/Hz and the optimum scheduling weights, as a function of Δ . Note that as the average channel gains diverge (Δ increases), the required SNR increases.

Mininum required average SNR and optimum scheduling weights to achieve the objective rates in different channels determined by the parameters Δ .

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

7. Conclusions

In this paper we studied the performance of the multiuser selection diversity, in broadcast ergodic fading channels, under different SNR-based scheduling schemes. At each fading state, the base station transmits to the user with the highest weighted SNR. By assigning the weights to the users, the base station can arrange the users according to a prescribed quality of service or degree of fairness. Each set of weights corresponds to a specific scheduling policy. We have derived a closed-form expression for the achievable users' rates as a function of the scheduling weights, the transmit power, and the channel fading statistics. With the help of this expressions, we show how to obtain the optimum (in terms of transmit power) scheduling policy to achieve a prescribed set of users' rates. Also, given a transmit power, we obtain the scheduling policy that maximizes the overall throughput preserving a given relationship among the users' rates.

Acknowledgment

This work has been supported by the Spanish Government under projects TEC2007-68020-C04-02/TCM and CSD2008-00010(COMONSENS).

References

[1] A. Goldsmith Wireless Communications , Cambridge University Press, Cambridge, UK, 2005.

[2] P. Viswanath, D. N. C. Tse, R. Laroia, "Opportunistic beamforming using dumb antennas," IEEE Transactions on Information Theory , vol. 48, no. 6, pp. 1277-1294, 2002., [email protected]; [email protected]; [email protected]

[3] "Ist-856, high rate packet data air interface specification, document c.s0024 v3.0," December 2001, http://www.3gpp2.org

[4] WiMAX forum, "Mobile WiMAX--part II: a comparative analysis," http:/www.wimaxforum.org

[5] A. Farrokh, V. Krishnamurthy, "Opportunistic scheduling for streaming users in high-speed downlink packet access (HSDPA)," in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '04), vol. 6, pp. 4043-4047, Dallas, Tex, USA, [email protected]; [email protected], November-December 2004.

[6] L. Yang, M.-S. Alouini, "Performance analysis of multiuser selection diversity," IEEE Transactions on Vehicular Technology , vol. 55, no. 6, pp. 1848-1861, 2006., [email protected]

[7] F. Berggren, R. Jantti, "Asymptotically fair transmission scheduling over fading channels," IEEE Transactions on Wireless Communications , vol. 3, no. 1, pp. 326-336, 2004., [email protected]; [email protected]

[8] D. N. C. Tse, P. Viswanath Fundamentals of Wireless Communications , Cambridge University Press, Cambridge, UK, 2005.

[9] J. M. Holtzman, "Asymptotic analysis of proportional fair algorithm," in Proceedings of the 12th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC '01), vol. 2, pp. F33-F37, San Diego, Calif, USA, September-October 2001.

[10] J. Pérez, J. Ibáñez, I. Santamaría, "Exact closed-form expressions for the sum capacity and individual users' rates in broadcast ergodic Rayleigh fading channels," in Proceedings of the 8th IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC '07), pp. 1-5, Helsinki, Finland, [email protected], June 2007.

[11] M. Abramowitz, I. A. Stegun Handbook of Mathematical Functions , Dover, New York, NY, USA, 1970.