DOWNLINK SCHEDULING OPTIMIZATION AND P E R F O R M A N C E ANALYSIS OVER FADING CHANNELS IN A C D M A N E T W O R K by R A Y M O N D K W A N B.A.Sc, University of British Columbia, 1996 M.A.Sc , University of British Columbia, 1998 A THESIS SUBMITTED IN PARTIAL F U L F I L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF DOCTOR OF PHILOSOPHY in T H E FACULTY OF G R A D U A T E STUDIES (Electrical and Computer Engineering) T H E UNIVERSITY OF BRITISH COLUMBIA February 2006 © Raymond Kwan, 2006 Abst rac t Due to technological advances in mobile communications, together with the explosive growth of internet access, transmitting multimedia applications over wireless channels is no longer a remote concept. In third generation (3G) multimedia C D M A networks, a variety of tech-niques will be used to meet the quality of service (QoS) requirements for various types of traffic. These include adaptive modulation and coding (AMC) which improves performance by adapting the employed modulation and coding scheme (MCS) to changing channel condi-tions and multicode transmission which provides higher bit rates to mobile stations (MS's). The problem of allocating radio resources in the downlink of a C D M A network is first studied. In particular, the modulation and coding schemes, numbers of multicodes, and transmit powers used for all MS's are jointly chosen so as to maximize the total transmission bit rate, subject to certain constraints. In addition, a scheduler which uses knowledge of MS traffic loads is also proposed and shown to yield a significant improvement in throughput. The proposed multiuser schedulers are optimal in terms of system throughput. However, the implementation complexity can be high. Consequently, a suboptimal scheme is proposed, in which resources are allocated sequentially on a per-MS basis. Essentially, the sequential scheme reduces the problem of multiuser resource optimization to a single user problem, thereby greatly reducing complexity. Numerical results show that the performance of the sequential scheme is generally close to optimal if the MS's are ordered optimally. The thesis also addresses the problem of downlink single user scheduling in the context of A M C and multicodes with imperfect channel estimation. Since the selection of MCS and number of multicodes requires an estimation of the downlink channel quality, it is important ii to assess the performance degradation due to estimation errors. It is shown that the system throughput is quite sensitive to channel estimation errors, and methods are proposed to reduce the resulting degradations. In multiuser scheduling, the aim is to select users with good channel conditions so as to improve the system performance. The selection process is a classical problem in the theory of order statistics. Since users are generally located in different parts of a cell, their respective channels can often be assumed independent, but their fading statistics are not necessarily identical. In this thesis, some useful general results assuming independent and non-identically distributed (i.n.d.) order statistics over the Nakagami and Weibull fading channels are derived. The thesis also proposes a new statistical distribution for the C D M A downlink signal-to-interference ratio given that the simultaneously transmitted interfering and desired signals from the same base station undergo the same fading process. Finally, a simple method for approximating complex statistical distributions which arise in the study of wireless communications is investigated. The resulting relatively simple approximations are shown to be quite accurate. iii Table of Contents Abstract ii Table of Contents iv List of Tables viii List of Figures ix List of Abbreviations xiii List of Symbols xv Acknowledgments . . . . xviii Dedication xix Chapter 1 Introduction 1 1.1 Background 1 1.1.1 W C D M A Transport Channels for Packet Access 5 1.1.2 High Speed Downlink Packet Access 8 1.1.3 Adaptive Modulation and Coding 9 1.1.4 Adaptive Modulation and Coding with Multicodes 10 1.2 Motivation 11 1.2.1 Issues in Multiuser Scheduling 11 1.2.2 Issues in Channel Statistical Characterization 13 1.3 Thesis Overview 15 Chapter 2 Optimal Downlink Scheduling Schemes for C D M A Networks 23 2.1 Introduction 23 2.2 . System Model 25 2.3 Joint Optimization Model 26 2.3.1 Channel-Based Model 26 2.3.2 Load-Based Model 27 2.3.3 Numerical Results . . 29 2.4 Sequential Optimization Model 38 2.4.1 Channel-based Model 38 iv 2.4.2 Load-Based Model 43 2.4.3 Numerical Results 47 2.5 Conclusions 55 Chapter 3 Scheduling for the Downlink in a C D M A Network with Imper-fect Channel Estimation 58 3.1 Introduction 58 3.2 System Model 60 3.3 Optimal Bit Rate Allocation with Adaptive Modulation and Coding and Mul-ticodes 61 3.4 Effect of Estimation Error 65 3.5 Load-Based Scheduling with Estimation Error 67 3.6 Numerical Results 69 3.7 Conclusions 71 Chapter 4 Adaptive Modulation and Coding with Multicodes over Nak-agami Fading Channels 77 4.1 Introduction 77 4.2 Adaptive Modulation and Coding with Multicodes 78 4.3 Performance Analysis over Nakagami Fading Channels 80 4.3.1 The case 7 > Kj 83 4.3.2 The case 7 < Kj 84 4.4 Results and Discussion 86 4.5 Conclusions 87 Chapter 5 Performance of a C D M A system employing A M C in the Pres-ence of Channel Estimation Errors 92 5.1 Introduction 92 5.2 H M M Formulation 93 5.3 Transition Probabilities Estimation 96 5.4 Performance Measures . . . ' 97 .5.5 Numerical Results 98 5.6 Conclusions 99 Chapter 6 Gamma Variate Ratio Distribution with Application to C D M A Performance Analysis 102 6.1 Introduction 102 6.2 System Model and SIR Statistics '. 103 6.3 Application in Adaptive Modulation and Coding and Multicodes 112 6.4 Numerical Results 116 6.5 Conclusions 117 v Chapter 7 General Order Selection Combining for Non-Identically Dis-tributed Fading Channels 125 7.1 Introduction . . . 125 7.2 General Order Selection Statistics 126 7.2.1 Weibull Fading Channels 127 7.2.2 Nakagami-m Fading Channels 130 7.3 Symbol Error Rate Analysis 131 7.3.1 Weibull Fading Channel 132 7.3.2 Nakagami Fading Channels ' 134 7.4 Numerical Results 137 7.5 Conclusions - 138 Chapter 8 An Accurate Method for Approximating Probability Distrib-utions in Wireless Communications 143 8.1 Introduction 143 8.2 Systems of Distributions 144 8.2.1 Pearson Type I ( - 0 0 < K < 0) 145 8.2.2 Pearson Type IV (0 < K < 1) 146 8.2.3 Pearson Type VI (1 < K < co) 147 8.2.4 Transition Types 148 8.3 Some Applications 149 8.3.1 M R C over Non-Identical Weibull Fading Channels 149 8.3.2 General Order Selection Combining over Non-Identical Weibull Fading Channels 151 8.3.3 Generalized Selection Combining (GSC) over Non-Identical Weibull Fading Channels 152 8.3.4 Equal-Gain Combining (EGC) over Correlated, Non-Identical Nak-agami Fading Channels 153 8.4 Numerical Results 154 8.5 Conclusions - 155 Chapter 9 Conclusions and Future Work 163 9.1 Summary of Contributions 163 9.2 Future Work • • • • 165 Appendix A Linearization of the MINLP models 171 A . l Assigned Bit Rate Based Model 171 A. 2 Load-Based Model 172 Appendix B Proof of Theorems and Clarifications in Chapter 3 174 B. l Proof of theorem 3.1 174 B.2 Proof of Theorem 3.2 175 B.3 Proof of theorem 3.3 178 B.4 Relationship between of1 and <7j 178 vi Appendix C Derivation of the integral in (4.28) 180 Appendix D Optimality with an integer number of multicodes 182 Appendix E Derivation of (7.17) 184 Appendix F Derivation of (8.15) and (8.31) 185 F . l Derivation of (8.15) 185 F.2 Derivation of (8.31) 186 vii Lis t of Tables 2.1 List of parameter values 33 4.1 List of parameter values 88 8.1 Transition types and associated parameter values 156 8.2 Parameter values used in Figs. 8.1-8.4 156 viii Lis t of Figures 1.1 UMTS Network elements 6 1.2 (Left) Code division for the dedicated channel, and (right) time division for the shared channel 7 2.1 Total bit rate as a function of the maximum allowable power, Pmax, for a = 0.1 and 0.4, assuming an integer and a continuous number of multicodes 34 2.2 Allocated MS power as a function of the maximum allowable power, Pmax- Top: a = 0.1, Bottom: a — 0.4, assuming an integer number of multicodes 34 2.3 Total bit rate as a function of the maximum allowable power, Pmax at a — 0.1 and 0.4 for the proposed model and the single user model, assuming an integer number of multicodes 35 2.4 (Top) Total bit rate Rtot (Bottom) Scheduler efficiency n as a function of to-tal normalized buffer size D for a — 0.1, Pmax = 10W, NitTnax = 10, D/Z?i = (1 2.2 3.5) and vi = (0.007 0.0065 0.006) for both basic and load-based models. 35 2.5 (Top) Total bit rate Rtot (Bottom) Scheduler efficiency 77 as a function of to-tal normalized buffer size D for a — 0.1, Pmax = 10W, Ni^max = 10, T)/D\ — (1 2.2 3.5) and v x = (0.005 0.006 0.008) for both basic and load-based models. 36 2.6 Power efficiency r\v as a function of total normalized buffer size D for a = 0.1, Pmax = WW, NitTnax = 10, D/D: = (1 2.2 3.5) and v x = (0.007 0.0065 0.006) for both basic and load-based models 36 2.7 Power efficiency r\v as a function of total normalized buffer size D for a — 0.1, Pmax = 10W, NitTnax = 10, D/Z?! = (1 2.2 3.5) and vj = (0.005 0.006 0.008) for both basic and load-based models 37 2.8 Deviation factor £ as a function of total normalized buffer size D for a — 0.1, Pmax = 10W, iV i i m a x = 10, D/Z?i = (1 2.2 3.5) and (Top) vi = (0.007 0.0065 0.006) (Bottom) vi = (0.005 0.006 0.008) for both basic and load-based models 37 2.9 Allocated MS bit rate as a function of 7- 39 2.10 Total bit rate Rtot as a function of the maximum allowable power Pmax with vi = [0.005 0.006 0.007] for both joint and sequential optimization, assuming a continuous and an integer number of multicodes 49 2.11 Power efficiency function of the maximum allowable power Pmax with vi = [0.005 0.006 0.007] for both joint and sequential optimization, assuming a continuous and an integer number of multicodes 50 ix 2.12 Total bit rate Rtot as a function of the maximum allowable power Pmax for joint and sequential optimization, (case 1) v i = [0.8 0.8 0.8] and (case 2) v x = [0.005 0.005 0.005]. 50 2.13 Total bit rate Rtot as a function of the maximum allowable power Pmax with v i = [0.2 0.6 0.9] for joint optimization, and (case 1) v i = [0.2 0.6 0.9] and (case 2) v i = [0.9 0.6 0.2] for sequential optimization 51 2.14 Total bit rate Rtot as a function of the maximum allowable power Pmax with v i = [0.005 0.006 0.007] for joint optimization, sequential optimization, and sequential optimization with equal power allocation, given that NitJnax = 5 51 2.15 Total bit rate Rtot as a function of the maximum allowable p ower Pxnax with v^ — [0.005 0.006 0.007] for joint optimization, sequential optimization, and sequential optimization with equal power allocation, given that Ni<max = 10 52 2.16 Total bit rate Rtot as a function of the maximum allowable power Pmax for joint optimization and sequential optimization with and without optimal ordering, with D = [2.0, 0.8, 0.5] 54 2.17 Power efficiency r?p as a function of the maximum allowable power Pmax for joint optimization and sequential optimization with and without optimal ordering, with D = [2.0, 0.8, 0.5] 54 2.18 Total bit rate Rtot as a function of the total normalized buffer size D = YA=I A f° r joint optimization and sequential optimization with and without optimal ordering, with D/7J»3 = [3.5, 2.5, 1.0], and Pmax = 10 W 55 3.1 MS bit rate and 7 i relationship with MCS's 63 3.2 Averaged normalized effective bit rate i?j(7j |Aj)/W as a function of 7J with af ^ = 0.1. • 72 3.3 Normalized effective bit rate WR as a function of the relative estimation error /37i with af = 0.1 72 3.4 Averaged effective bit rate ratio rfa as a function of the conservative factor Aj with af = 0.1 73 3.5 Averaged effective bit rate ratio rJR as a function of the standard deviation af with 7 i = 2.5 73 3.6 Averaged effective bit rate ratio ffa as a function of the standard deviation af with 7 i = 1-8 74 3.7 Averaged effective-to-requested bit rate ratio as a function of the standard deviation af with Di — 0.85, Aj = 0 and different values of 7$ 74 3.8 Averaged effective-to-requested bit rate ratio as a function of the conservative factor Aj with af = 0.1, Di = 0.85 and different values of 7J 75 3.9 Averaged effective-to-requested bit rate ratio as a function of the standard deviation af with 7J = 2.5, _Dj = 0.85 and different values of Aj 75 4.1 Allocated MS bit rate as a function of 7 79 4.2 Frame error rate as a function of SNR for 4 MCS's 88 4.3 Normalized average conditional bit rate R(-y)/W as a function of the estimated SNR, 7 , with m = 15, and f = 2.5, at p = 0.001 and p = 0.3 89 x 4.4 Conditional pdf PCTIT) °f the actual SNR, F, given the estimated SNR, 7 , with f = 2.5, m = 5, and (top) p = 0.001, (bottom) p = 0.5. 89 4.5 Normalized average bit rate R/W as a function of the average channel SNR, f, with p = 0.001 and p = 0.3 when m = 15 90 4.6 Normalized average bit rate R/W as a function of the correlation coefficient p, with m = 35, and f = 2.5 90 5.1 Improvement factor, n/, as a function of the observation noise standard deviation. 99 5.2 Improvement factor, rjf, as a function of the LAF window size, Z, with ay = 0.6. 100 6.1 Allocated MS bit rate as a function of 7 117 6.2 The pdf / r (7 ) for five different values of ai with a2 — 1, a\ — 3, a2 = 2, Xi = 1.5, andX2 = l 118 6.3 Outage probability as a function of E[F] for different values of ai when a.\ — 2, a 2 = 2, X2 = 1.6, a2 = 0.35, and Z = -7 dB 119 6.4 Outage probability as a function of the outage threshold, Z, for three different values of a\ (and corresponding values of a2) with a\ = 2, a>2 = 2, Xi = 0.5, X2 = 0.25 and E[F) = 3.0 dB • : . 120 6.5 Outage probability as a function of the outage threshold, Z, with (a) E[T] = 3.0 dB and (b) E[F] = 5.4 dB. For the proposed distribution, a.\ = 2, a2 = 2, X\ = 0.5, X2 = 0.25, a2 = 0.25, with (a) ax = 0.3478 and (b) ax = 0.1557. For the Gaussian approximation, a\ = 2, X\ = 0.5, with the relative noise power (a) iV"o = 0.25 and (b) N0 = 0.1429 121 6.6 Normalized average bit rate bounds as a function of a\ for three different values of 0,2 with a.\ —b, a2 = 2, X\ = 0.2, X2 = 0.25, Nmax — 10 and a target frame error rate of 1% 122 7.1 Average bit error rate, Ps, for BPSK on Weibull fading channels, as a function of Xavg for different values of q, a= [2 2 2 2]: X / X i = [1111] (i.i.d. case), and X / Z i = [1 3 5 7] (i.n.d. case). 139 7.2 Average symbol error rate, Ps, for 4-QAM on Weibull fading channels, as a function of Xavg for different values of q, a— [2 2 2 2]: X / X i = [1111] (i.i.d. case), and X / X i = [1 3 5 7] (i.n.d. case) 139 7.3 Average symbol error rate, Ps, for 8-PSK on Nakagami fading channels, as a func-tion of f3avg for different values of q with (a) a= [2 2 2 2], f3'/Pi = [1 1 1 1] (i.i.d. case) and (b) a= [1 2 3 2], = [1 3 5 7] (i.n.d. case). 140 7.4 Average symbol error rate, Ps, for 4-QAM on Nakagami fading channels, as a function of j3avg for different values of q with (a) a= [2 2 2 2], (3/81 = [1111] (i.i.d. case) and (b) Q= [1 2 3 2], j3/Bi = [1 3 5 7] (i.n.d. case) 140 8.1 Complementary cdf and cdf of MRC output SNR for Weibull fading channels. . . 157 8.2 Complementary cdf and cdf of the second and third largest GOSC output SNR for Weibull fading channels 157 8.3 Complementary cdf and cdf of GSC output SNR for Weibull fading channels. . . 158 xi 8.4 Complementary cdf and cdf of EGC output SNR for Nakagami fading channels with p = 0.15 158 8.5 Average BER for BPSK with EGC over Nakagami fading channels with p = 0.15. 159 9.1 Cooperation between the dedicated and the shared channels 167 B . l Lambert W function. The dotted line corresponds to the real branch -1, while the solid line corresponds to the real branch 0 177 D . l The bit rate as a function of SIR for MCS i and MCS j assuming an integer and a continuous number of multicodes 183 xii Lis t of Abbrevia t ions 3GPP Third Generation Partnership Project. A F Amount of Fading. A M Adaptive Modulation. A M C Adaptive Modulation and Coding. A Q A M Adaptive Quadrature Amplitude Modulation. B E R Bit Error Rate. B L E R Block Error Rate. BPSK Binary Phase Shift Keying. BS Base Station. CDF Cumulative Distribution Function. C D M A Code-Division Multiple Access. CSI Channel State Information. E G C Equal-Gain Combining. E M Expectation Maximization. FSMC Finite-State Markov Chain. GSC Generalized Selection Combining. GOSC General Order Selection Combining. H M M Hidden Markov Model. HSDPA High Speed Downlink Packet Access. IID Independent and Identically Distributed. xiii IND Independent and Non-identically Distributed. JO Joint Optimization. OVSF Orthogonal Variable Spreading Factor. MCS Modulation and Coding Scheme. M G F Moment Generating Function. MINLP Mixed Integer Nonlinear Programming. MRC Maximal Ratio Combining. MS Mobile Station. OVSF Orthogonal Variable Spreading Factor. PDF Probability Density Function. PF Proportional Fair. M P F Modified Proportional Fair. Q A M Quadrature Amplitude Modulation. QoS Quality of Service. QPSK Quadrature Phase Shift Keying. R R M Radio Resource Management. RV Random Variable. SC Selection Combining. SER Symbol Error Rate. SINR Signal-to-Interference-and-Noise Ratio. SIR Signal-to-Interference Ratio. SNR Signal-to-Noise Ratio. SO Sequential Optimization. TTI Transmission Time Interval. W C D M A Wide-band Code Division Multiple Access. xiv Lis t of Symbols a Orthogonality factor aij, Pi Distribution parameters of the fading channel models for the ith branch diver-sity combining ak(j) Forward probability of state j at time k Pi Skewness of a distribution (in the context of Pearson's systems of distribution) Pi Kurtosis of a distribution (in the context of Pearson's systems of distribution) Pk(j) Backward probability of state j at time k A j Conservative factor eo QoS related frame error rate target e7i Estimation error for the received SIR 7J Received SIR for MS i ltjin\%j A M C selection thresholds for MS i and MCS j 7- Maximum possible downlink SIR for MS i if a power Pj is allocated to MS i 7 i Estimated received SIR for MS i £ Scheduling deviation factor rj Scheduling efficiency r]f Improvement factor r]p Power efficiency rjR Effective bit rate ratio fjR Average effective bit rate ratio K Selection parameter for Pearson's systems of distributions xv Ajj SIR requirement for MCS j and MS i at a given QoS 7Tfc(i) The probability that the channel is in state k at time k p Correlation coefficient O j j Transition probability that the channel SIR is in state j given that the it was in state i at the pervious scheduling instant dij Estimated state transitional probability from state i to state j h{Vk) The condition pdf of the observation given that the channel is in state % at time k Bi The number of bits in the buffer for MS i at the beginning of a scheduling period Di Normalized buffer size for MS i g Spreading factor hi Path gain between the desired BS and MS i hk^ Path gain between BS k and MS % I-r^ Received interference power at MS i IN Thermal noise J Maximum number of MCS's L Number of MS's to be scheduled; number of branches for selection diversity Mj Number of points in the signal constellation for MCS j rii Number of multicodes for MS i Nmax Maximum number of multicodes (channelization codes) for the BS Nitmax Maximum number of multicodes (channelization codes) that MS i can support Pi Downlink transmit power for MS i Pmax Maximum power allocated for scheduling at the BS Ps Average symbol probability PT Total available downlink transmit power for the BS Pi Maximum downlink power available to MS i r j j Basic bit rate for MCS j and MS i xvi Code rate for MCS j Ri Bit rate (assigned) for MS i Ri{ii\ii) Effective bit rate for MS i at 7$ for a given value of 7; Effective bit rate for MS i at 7$ Ri{ii\&i) Average effective bit rate given a specific value of Aj R Average effective bit rate Rtot Total bit rate for all scheduled MS's T J- a Scheduling period Vk,i The ratio of the path gain between BS k and MS i to the path gain between the desired BS and MS i, i.e. hk,i/hi W Chip rate Note: In this thesis, in order to distinguish a random variable from its outcome, the former is denoted by a capital letter, whereas the latter is denoted by a small letter. xvii Acknowledgments This work would not have been possible without the support of many people. I am most of all indebted to my advisor, Dr. Cyril Leung, who has shown immense patience and support throughout many years - making himself available even outside regular working hours. His comments are always useful and constructive. Thanks to the Natural Sciences and Engineering Research Council (NSERC) of Canada for awarding me a Post Graduate Scholarship (PGS) as well as support from NSERC Grant OGP0001731 and the UBC PMC-Sierra Professorship in Networking and Communications. They have provided me with the financial means to engage in and complete this work. I would like to thank my thesis examination committee members and the external examiner for their time and efforts. And finally, thanks to my wife Jenny and my parents, who have helped and supported me in all possible ways. xviii To my family. xix Chapter 1 Introduction 1.1 Background Due to the ubiquity of Internet access, together with the technological advances in mobile communications, wireless multimedia applications have become a reality. However, such applications can potentially be very resource demanding. Due to the nature of multimedia applications, many types of traffic can be encountered with different characteristics and Quality of Service (QoS) requirements [1]. The ability to allocate limited radio resources efficiently to these different traffic types while meeting their QoS requirements is a difficult task. Thus, radio resource management (RRM) is considered to be an important topic in the wireless industry. As pointed out in [1], the R R M functionalities and requirements for the downlink and the uplink of a Code Division Multiple Access (CDMA) system are different. For example, the total transmit power at the base station is limited, and is shared among users. Thus, as the number of users increases, the average power allocated to each user decreases. In other words, the number of supported downlink users is limited by the available power at the base station. On the uplink, on the other hand, the power resource is not centrally shared by the users as in the downlink, since each user has its own power amplifier. However, each additional user increases the interference level at base station receiver. Thus, the number of supported uplink users is related to the amount of interference that the base station receiver experiences. In general, the goal of downlink resource management is to efficiently allocate the limited downlink power to maximize the throughput, while the goal of uplink resource 1 management is typically to minimize the mobile transmit power so that less interference is seen at the base station and to extend battery life. A number of papers have addressed the issues of uplink scheduling [2]-[16]. In [2, 3], an uplink dynamic resource scheduling mechanism is suggested for QoS provisioning in Wide-Band Code Division Multiple Access (WCDMA) by means of optimal power assignment and code hopping. The transmit power level is minimized while meeting the QoS requirements for the admitted users. In addition, the spreading gain for variable bit rate (VBR) services is dynamically adjusted so that a higher spreading gain can be used when the required bit rate is low. With a higher spreading gain, a lower uplink transmit power is required, and the interference can be reduced. Such reduction in interference can lead to an overall increase in capacity. In [4], a combined rate and power control scheme for the uplink is proposed in which the transmission rate is kept constant while the power is adjusted via power control when the channel condition is above a certain threshold. On the other hand, when the channel condition falls below the threshold, the power is kept constant while the transmission rate is reduced. This simple hybrid power/rate control effectively reduces the interference in the uplink, and leads to a capacity increase. In [5], resource allocation is formulated as a constrained optimization problem. The ob-jectives are to minimize power or to maximize bit rates on the uplink of a C D M A system. The former reduces the interference seen in other cells, and the latter tries to achieve the best possible throughput for the users. Bounds were developed on the total number of users of each class that can be supported simultaneously while meeting the QoS and resource constraints. In [6], two transmission modes are considered for maximizing the throughput for delay tolerant users. In the first mode, all users are allowed to transmit when they wish, whereas in the second mode, users are time-scheduled so that only a limited number of them can transmit at any given time. It has been shown that the second mode effectively reduces the interference seen by the transmitting users so that higher bit rates can be achieved, even 2 though only a fraction of the time is allowed for each user. In [7], a non-linear optimiza-tion problem is considered in which the total power of different mobiles is minimized while achieving their minimum guaranteed throughput. In [8], a jointly optimal power and spreading gain allocation strategy is provided to maximize the instantaneous non-real-time throughput for the uplink C D M A network, subject to constraints on peak mobile transmission power and the total received power at the base station. In the model, the spreading gain is assumed to be continuous, and there is no constraint on the bit rate. In [9]-[ll], the problem of optimal rate and power adaptation for multirate C D M A on the uplink is considered, in which each user has a bit error rate (BER) constraint while having a fixed set of transmission rates to select from. An optimal uplink rate adaptation scheme is proposed and analyzed, in which the optimal number of multicodes are allocated to each scheduled user, and the minimum needed power for each user is determined. In [12], the throughput maximization problem for a C D M A uplink is expressed in terms of the spreading gains and transmit powers of the users, and the problem is solved using nonlinear programming. The results suggest that all resources should be allocated to the user with the highest path gain. This approach maximizes the total throughput at the expense of fairness. The authors then extend the proposed strategy by allowing all users to be served on a time-sharing basis. The results suggest a modest loss in the total throughput, but a significant increase in fairness. In [13]-[16], a scheme for optimal resource management for uplink transmission in W C D M A is proposed. The idea is to guarantee the quality-of-service (QoS) by efficiently allocating radio resources such as power and bit rate. The model takes the form of a mathematical programming optimization problem, in which the main objective is to maximize a utility function subject to certain QoS requirements. In [13], both the single and multiple-cell scenarios are considered. In particular, the multiple-cell scenario is formulated as a mixed integer non-linear programming problem. In this work, the bit rate is assumed to be con-3 tinuous. Since the downlink transmit power of the base station is shared among users, intelligent scheduling is typically desirable to efficiently utilize such a limited resource. A number of studies are devoted to downlink scheduling [17]-[34]. In [17, 18], the optimization problem for the downlink W C D M A system is examined using dynamic programming. The objective is to maximize the total offered bit rate by allocating user specific power and bit rate given a total power constraint at the base station. In all cases, no limits on the user bit rate or the number of channelization codes are considered. In [19, 20, 21], the issues of the optimum rate and power allocation for the downlink C D M A system in a multiple cell environment are addressed based on the channel condition of each user at the beginning of each scheduling period. The idea is to maximize the sum of the assigned bit rates for all users under certain SIR and downlink transmit power constraints. In [22, 23], it is shown that in a C D M A network, the optimal strategy for scheduling downlink transmission to data users is to transmit to one user at a time at full power rather than transmit to several users simultaneously. In [24], it is also found that such one-by-one scheduling for downlink can yield superior throughput performance compared to that of the simultaneous transmission case. The authors also point out that the one-by-one scheme is more energy efficient compared to other scheduling schemes in requiring less energy for delivering the same amount of data. Also discussed is a distributed power assignment scheme for such one-by-one scheduler in a non-fading environment. In [25], the one-by-one scheduling scheme is discussed for a fading environment, and different scheduling algorithms are compared in terms of their fairness. In [26], the problem of optimum power allocation for sharing the capacity in a fair way over the whole network is investigated. A distributed power control algorithm is proposed which allocates the powers so that a uniform throughput is obtained among users. Although throughput is an important measure of network performance, fairness is also needed to ensure user satisfaction [27]-[34]. In [27], a user with the highest measure T is 4 given the downlink power P(t), where r _ (c/i)k(t) n n Rk(t) { • ] and (C/I)k{t) is the signal-to-interference ratio of the kth user at time t, and Rk{t) is the throughput of user k averaged over a certain time window up to time t. Thus, instead of giving resources to the user with the highest C/I, the incorporation of the throughput Rk{t) in the selection criterion introduces fairness by "punishing" a user who has enjoyed a high throughput. A proportional fair (PF) algorithm for the downlink is proposed in [28], in which the power P is allocated to the m best users based on their channel conditions. Each user k receives his share of power Pk, which is proportional to the channel gain of that user. An asymptotic analysis of such an algorithm is provided in [29]. In [30], delay sensitivity is incorporated into the proportional fair algorithm. The new modified proportional fair (MPF) scheduling algorithm is shown to be able to provide effective and fair service to both real and non real time data. In [31, 32], an optimization model is proposed for maximizing a certain utility function given a probabilistic fairness constraint. In this model, only a single user out of N users is allowed to be scheduled at each given time slot. However, on average, each user is to be scheduled for a pre-defined fraction of the total time. The goal of the scheduling scheme is to maximize the average system performance by exploiting the time-varying channel conditions. Following [31, 32], the authors in [33, 34] extend previous works by incorporating multiple users. 1.1.1 WCDMA Transport Channels for Packet Access One of the most popular technologies being proposed for the air interface of third generation mobile networks is code division multiple access (CDMA). The specification of W C D M A has been developed in the 3GPP (3rd Generation Partnership project) standardization forum 5 [1, 35]. A W C D M A network consists of a number of logical network elements, which are grouped into the Radio Access Network (RAN), which handles all radio-related function-alities, and the Core Network (CN), which is responsible for switching and routing calls and data connections to the external networks. In the 3GPP specification, the Radio Access Network is termed UMTS Terrestrial Radio Access Network (UTRAN). A reference diagram of the network elements is given in Figure 1.1. More detailed descriptions of the elements can be found in [1, 35]. In W C D M A , there are three types of transport channels that can be used to transmit packet U u l u b l u I 11 l i I j [_]_ U E U T R A N C o r e N e t w o r k ( C N ) Figure 1.1: UMTS Network elements. data [1, 36]. They are the common, the dedicated, and the shared transport channels. Com-mon channels do not have a feedback channel, and, therefore, cannot have fast closed loop power control, but only open loop power control or fixed power. In addition, these channels do not support soft handover. Due to the lack of fast closed loop power control, more inter-ference is generated, and, therefore, they are only designed to carry a small amount of data. The dedicated channel, on the other hand, requires dedicated resources. The advantage of the dedicated channel is that it supports fast closed loop power control and soft handover. As a result, less interference is generated than for the common channels. The disadvantage is that more time is required to set up a dedicated channel through signalling than a common channel. In addition, a dedicated channel ties up radio resources for the entire call duration, 6 and, thus, is not resource-efficient for bursty traffic. The shared channels are designed to carry bursty packet data by sharing a single physical channel, i.e. orthogonal code, be-tween a number of users in a time division multiplex manner. The advantage of the shared channels is that they do not tie up resources as the dedicated channel does, and, thus, are more resource efficient. In addition, transmitting data in a time division fashion improves the overall throughput by reducing the own-cell interference [22]. The conceptual difference between the dedicated and the shared channels is illustrated in Figure 1.2. Throughout this document, the terms time-shared channel and shared channel will be used interchangeably. The transport channel for packet data is selected based on the resource requirements of the Code division <D S n 7 6 o Time division M _ —3-i I IP y///\ 8 Time Time Figure 1.2: (Left) Code division for the dedicated channel, and (right) time division for the shared channel. services, the amount of data, and the interference levels in the air interface. In W C D M A , the Downlink Shared Channel (DSCH) is a shared transport channel, which is intended to carry packet traffic in the user plane from the U T R A N network to the User Equipment (UE). The DSCH is a time-shared channel with fast power control and fast scheduling but without soft handover. Some examples of simulation studies on the system performance with DSCH can be found in [37]-[39]. Recently, in 3GPP, a scheme called the High Speed Downlink Packet Access (HSDPA) has been proposed, in which a number of new features are incorporated into the DSCH, resulting a new transport channel called the High Speed Downlink Shared Channel (HS-DSCH). 1.1.2 High Speed Downlink Packet Access The development of the third generation (3G) wireless network infrastructure allows a rich variety of traffic types, each with its own QoS rquirements, to be transmitted over the wireless channel. Efficient radio resource allocation algorithms are therefore important. In addition, it is anticipated that the downlink traffic will be especially important because much of the high-speed internet access and broadcast services are transmitted in the downlink. In order to offer such broadband packet data transmission services, HSDPA [1, 40] is currently under investigation in 3GPP. HSDPA is the Release 5 extension of the W C D M A specification with a new transport channel called High-Speed Downlink Shared Channel (HS-DSCH). The special feature of this channel is that a certain amount of channelization codes and power in a cell are considered as a common resource that is dynamically shared among users in the time domain. Instead of using power control as in the case of the dedicated channel (DCH), HS-DSCH keeps the transmit power constant while adjusting the bit rate according to the channel condition via Adaptive Modulation and Coding (AMC). Additional features include multicode transmis-sion, Multiple-Input-Multiple-Output (MIMO), and fast Hybrid Automatic Repeat reQuest (HARQ) [41]. A number of HSDPA simulation studies on the network performance have been reported [42]-[46], which focus mainly on the most popular scheduling algorithms such as the round robin (RR) algorithm, the Maximum C/I (signal-to-interference ratio) algorithm, and the proportionally fair (PF) algorithm. The idea of the first scheme is to schedule the queued user in a first-come-first-served basis, and is generally known to be fair from the user's point of view. The second scheme requires knowledge of the user's channel quality, and selects the user with the best channel quality so that the network resource usage can be optimized. This scheme generally yields the highest throughput, but handicaps users with poor channels. The third scheme is a compromise in which users are assigned radio resources 8 that are proportional to the ratio of their instantaneous to long term channel qualities. In these papers, the number of multicodes is assumed to be statically allocated. In [47]-[49], the A M C and the number of multicodes are jointly selected for a single user based on the channel quality. In all cases, the power and multicode resources are not optimized for serving multiple users simultaneously. 1.1.3 Adaptive Modulation and Coding It is well known that adapting the transmission parameters in a wireless system to changing channel conditions can be advantageous. In the case of fast power control [1, 35], the transmission power is adjusted based on the channel fading. Thus, a good channel condition requires lower transmission power to maintain the target signal quality at the receiver. The process of changing transmission parameters to compensate for variations in channel conditions is known as link adaptation. Besides power control, adaptive modulation and coding (AMC) is also used for link adaptation [41],[50]-[54]. The goal of A M C is to change the modulation and channel coding scheme according to the varying channel conditions. In this scheme, a terminal with favorable channel conditions can be assigned a higher order modulation with a higher channel coding rate, and a lower order modulation with a lower channel coding rate when channel conditions are unfavourable. Higher order modulations provide better spectral efficiency at the expense of worse error rate performance. A lower channel coding rate provides better error correction capability than the same type of coding with a higher coding rate. Thus, with a proper combination of the modulation order and channel coding rate, it is possible to design a set of modulation and coding schemes (MCS), from which an adaptive selection is made per transmission-time-interval (TTI) such that an improved spectral efficiency can be achieved under good channel conditions. At each selection of the MCS, the criterion should be such that the probability of erroneous decoding of a Transmission Block is below a threshold value. In [55, 56], the signal-to-interference (SIR) ratio as well as the A C K / N A C K feedback 9 information of the Hybrid ARQ (HARQ) are used to control the threshold values for choosing the MCS. It is proposed in [55] that when the current received SIR falls within a limited range (±a ) on either side of one of the current thresholds, then the threshold value is increased by Aup if an A C K is recevied, and decreased by Adown if a N A C K is received. Subsequently, the next appropriate MCS is chosen based on the updated set of thresholds. In [57], it is proposed to perform the MCS selection based solely upon the A C K / N A C K feedback information of the HARQ. The idea is to decrease the MCS order by one if a number of consecutive or accumulative NACK's are received, and increase the MCS order by one if a number of consecutive ACK's are received. A higher MCS order provides a higher bit rate at the expanse of a power/error rate performance. A number of variations have also been proposed. With these schemes, no feedback information regarding the received signal quality is needed, thereby reducing the system complexity. In [58], the average channel signal-to-noise ratio (SNR) over a frame duration is quantized and modelled as a first-order finite-state Markov process. The MCS is selected in each state of this Markov model in order to maximize the average throughput in that state. 1.1.4 Adaptive Modulation and Coding with Multicodes Multicode transmission is employed [1, 10] to increase the bit rate by splitting the bits of a Transmission Block to more than one channelization code at each transmission interval (TI). Thus, during each transmission interval, more data can be transmitted. In this scheme, a high rate data stream is divided into a number of lower, rate data sub-streams, which are transmitted in parallel synchronous orthogonal multicode channels. It has been shown that multicode yields better performance compared to the single code scheme in a multipath environment [59, 60]. With the single code scheme, a lower spreading factor is required to provide the same bit rate as that of the multicode scheme. From the perspective of power and bandwidth, both schemes provide the same throughput. However, in the presence of multipath fading, the single code scheme suffers a slightly greater performance degradation. 10 In [61], it is proposed to select the number of multicodes based on the amount of data in the downlink data buffer so as to avoid assigning more multicodes than needed. However, the MCS and the corresponding number of multicodes are selected separately, resulting in sub-optimal resource allocation. Simulation studies of the HSDPA performance with multicodes have been performed in [42, 47, 48]. In [47, 48], the multicodes and MCS are selected dynamically in the HSDPA transmission environment with an extensive dynamic W C D M A network simulator [62]. A single user algorithm for joint optimization of MCS and multicodes given the power and code constraint has been proposed in [49]. The idea is to use as many multicodes as possible for the lowest order MCS. Note that every time an extra code is used, more power is required to maintain a given QoS requirement. Once the code resource is exhausted, and if more power resource is still available, the next higher order MCS is invoked with the highest possible number of multicodes that the power limit allows. The whole procedure is repeated until all the code and power resources are exhausted. Finally, the combination of the number of multicodes and the MCS is selected which gives the highest bit rate. 1.2 M o t i v a t i o n 1.2.1 Issues in Multiuser Scheduling In a typical communication channel, the transmission rate is closely related to the SIR, which, in turn, is tightly influenced by the transmission power. Such coupling between the transmission rate and power gives rise to a rich variety of schemes which can enhance the performance of a C D M A network in both uplink and downlink. The downlink is particularly relevant to consider because it is commonly expected that data traffic will be asymmetric with the bulk of the traffic directed from the base station to the user. In [22], using a simplified model which assumes a linear relationship between bit rate and transmit power, it was found that it is optimal for a base station to transmit to only one data user at a time. 11 Moreover, it was shown that a base station, when on, should transmit at maximum power for optimality. The above-mentioned assumptions may often not be valid. For example, the introduction of adaptive modulation results in a non-linear relationship between the bit rate and transmit power. In such a case, an optimal power allocation (to maximize the total allocated bit rate) may result in transmissions to more than one mobile at a time. In [49], an algorithm is provided for jointly selecting an optimal combination of MCS and the number of multicodes for a single user in the context of HSDPA, given code and power constraints, as well as the user's channel condition. The first objective of this thesis is to examine the resource allocation problem for many users. At first glance, it may appear that to optimize the total throughput in a multi-user system, the single-user algorithm given in [49] can by applied with minor modifications. Unfortunately, this is not the case. Unlike the single user case, in which the MCS, the power, and the number of multicodes are the main concerns, the multiuser case also has to deal with how the optimal sharing of code and power resources is done among the users. Some important issues that need to be addressed are (1) if transmitting to a single mobile is not necessarily optimal from the total throughput point of view, what is the optimal number of mobiles be given a fixed set of orthogonal codes and a maximum power of the base station that are to be shared among these mobiles? (2) How would the code and power resources be optimally allocated to each mobile given that the total reserved power and codes are limited? (3) Which modulation scheme should each allocated mobile use? A similar allocation problem was studied using exhaustive search in [63]. However, the complexity using exhaustive search is very high [64]. In most existing throughput optimization problems, it is assumed that users always have data to be sent. However, in reality, the user data are not always back-logged, and the throughput may be different from the total assigned bit rate. By taking into account not only the channel conditions of the users, but also the amount of data in the user buffers, the actual throughput can be improved. In [65], the authors studied the issue of dynamic 12 fair scheduling in the uplink W C D M A system by taking into account the traffic information. In [66, 67], single user scheduling schemes are proposed in the downlink, which use both the traffic information and channel variations in order to reduce the waiting and processing delays. The scheduling in [65] addresses only the uplink W C D M A , in which the power and code resources are not shared among different users centrally as in the downlink. The proposed scheduling schemes in [66, 67] are designed to take into account the user traffic load as a mean to reduce the overall delay and the throughput is not necessarily optimal. The problem of load-sensitive, joint optimization for multiple users will be investigated, and the model will include A M C and multicodes. To schedule resources efficiently, the channel quality for each user is needed. However, the quantity may not be very accurate since some kind of estimation from the mobile is typically involved. As a result, the system performance degrades. The impact of imperfect channel estimation upon the system performance is a topic which is studied. 1.2.2 Issues in Channel Statistical Characterization Since the use of A M C relies on the channel quality indicator fed-back from the mobile, statistical characterizations of the received channel quality is important for studying average throughput performance. In addition, if the distribution of the channel gain is known, more intelligent scheduling schemes can be designed. For example, most link adaptation systems rely mainly on the mean of the downlink SIR over a scheduling period as a way to quantify the channel quality. More complete knowledge of the distribution can be helpful in further optimize resource allocation. For example, it opens up the possibility for the base station to optimize resources statistically, taking into account the possible extent of each mobile's channel variations at a given time. More specifically, such additional knowledge enables the construction of stochastic optimization models, whereby uncertainties can be incorporated 13 [68, 69, 70]1. A stochastic approach for optimizing scheduling is not considered in this thesis. Rather, the probability distributions of the downlink received SIR are derived. Traditionally, a Gaussian approximation (GA) is often used to model the statistics of the interference for a C D M A system. However, as pointed out in [71], G A is not necessarily accurate in the context of the downlink performance analysis. The reason is that GA is based on the central limit theorem (CLT), which is not really applicable for the downlink since the interference due to the simultaneously transmitted signals by the same base station to different users are not statistically independent. In addition, CLT assumes a large number of interfering signals, which is not necessarily the case for downlink multiuser scheduling, due to the limited available downlink orthogonal channelization codes as in HSDPA. In downlink scheduling, selecting the user with the best channel condition has been suggested to maximize the network throughput [22]. However, as mentioned earlier, this scheme is not necessarily optimal due to the non-linear nature of the rate and transmit power relationship. A sub-optimal method for multiuser scheduling is to allocate resources to users sequentially based on their channel conditions. In fact, from the system throughput point of view; it is more efficient to allocate resources to the user with the best channel condition, and the remaining resources to the next best user and so on. For performance analysis, such a scheme motivates the need to obtain the ranked statistics of the channel conditions among users. In this thesis, the term general selection diversity is used as compared to selection diversity where the statistics of only the highest channel condition is examined as in the context of antenna selection combining [72]. In addition, since the users are situated at different locations of the cell, it is reasonable to assume that their channels are independent but non-identically distributed (i.n.d.). One aim of this thesis is to examine the statistics of such ranked channel conditions for different fading models. 1Note that if the knowledge of higher order statistics of the channel are known, more sophisticated optimization models can be developed. 14 1.3 Thesis Overv iew This thesis is written in the manuscript-based format according to the guideline specified by the University of British Columbia, in which each individual chapter is a published, in-press, accepted, submitted or draft manuscript written in a common format. The entire thesis is divided into two parts. The first part, which consists of chapters 2 -5 , focuses mainly on the issues of adaptive modulation and coding with dynamic multicodes and power allocations. The second part, which consists of chapters 6 - 8 , examines the statistical distributions of the received channel quality over fading channels. In chapter 2, the problem of joint multiuser optimization is addressed in the context of A M C and multicodes for a downlink C D M A system with and without user traffic load information. Instead of allocating resources for multiple users jointly at the base-station, a sub-optimal approach is taken in which the resources are allocated sequentially among users. The proposed sequential method eliminates the need for mathematical programming, making it an attractive alternative for performance analysis. In chapter 3, the effect of imperfect channel estimation on system performance is addressed. The imperfect channel model is further extended to the Nakagami fading channel in chapter 4. By casting the fading channel model into a discrete-state Hidden Markov Model (HMM), it is shown in chapter 5 that the effect of the imperfect channel estimate from the mobile can be reduced with an appropriate channel state estimation at the base station. In chapter 6, a new statistical model for the downlink received SIR over the Nakagami fading channel is proposed, in which the interfering signals from the same base station are dependent on the desired signal. In chapter 7, some statistical results are presented for general selection diversity, in which the fading channels are assumed to be i.n.d. Finally, in chapter 8, a statistical method known as the Pearson system of distributions is proposed to approximate complex statistical distributions which arise in wireless communications. Such an approximation is very useful especially for performance analysis when the distribution of certain channel parameter cannot 15 expressed in closed-form. References [1] H. Holma and A. Toskala, Eds., WCDMA for UMTS Radio Access for Third Generation Mobile Communications. John Wiley & Sons, 2002. [2] H. O. O. Gurbuz, "Dynamic Resource Scheduling for Variable QoS Traffic in W-CDMA," in Proc. of IEEE International Conference on Communications, ICC'99, vol. 2, June 1999, pp. 703 - 707. [3] , "Dynamic Resource Scheduling Schemes for W - C D M A Systems," IEEE Commu-nication Magazine, vol. 38, no. 10, pp. 80 - 84, October 2000. [4] W. L. J. Liu, S. Zhu, "A Combined Rate and Power Control Scheme and Its Impact on the Capacity of Multimedia DS-CDMA Systems," in Proc. of International Conference on Info-tech and Info-net, ICII'01, vol. 2, October - November 2001, pp. 156 - 161. [5] A. Sampath, P. Kumar, and J. Holtzman, "Power Control and Resource Management for a Multimedia C D M A Wireless System," in Proc. of 6th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications PIMRC'95, vol. 1, September 1995, pp. 21-25. [6] S. Ramakrishna and J. Holtzman, "A Scheme for Throughput Maximization in a Dual-Class C D M A System," IEEE Journal on Selected Areas in Communication, vol. 16, no. 6, pp. 830 -844, August 1998. [7] S. B. S. Kandukuri, "Simultaneous Rate and Power Control in Multirate Multimedia C D M A Systems," in Proc. of 6th IEEE International Symposium on Sread Sprectrum Technology and Application, vol. 2, September 2000, pp. 570 - 574. [8] S. J. Oh and K. M . Wasserman, "Adaptive Resource Allocation in Power Constrained C D M A Mobile Networks," in Proc. of IEEE Wireless Communications and Networking Conference, WCNC'99, vol. 1, September 1999, pp. 510 - 514. [9] S. A. Jafar and A. Goldsmith, "Optimal Rate and Power Adaptation for Multirate CDMA," in Proc. of 52th IEEE Vehicular Technology Conference, Fall, vol. 3, Sept. 2000, pp. 994 -1000. [10] , "Adaptive Multicode C D M A for Uplink Throughput Maximization," in Proc. of IEEE Vehicular Technology Conference, Spring, vol. 1, May 2001, pp. 6-9. [11] , "Adaptive Multirate C D M A for Uplink Throughput Maximization," IEEE Trans-actions on Wireless Communications, vol. 2, no. 2, pp. 218-228, March 2003. [12] S. Ulukus and L. J. Greenstein, "Throughput Maximization in C D M A Uplinks Using Adaptive Spreading and Power Control," in Proc. of 6th IEEE International Symposium on Sread Sprectrum Technology and Application, vol. 2, September 2000, pp. 565 - 569. 17 [13] M . Soleimanipour, W. Zhuang, and G. H. Freeman, "Optimal Resource Management in Wireless Multimedia Wideband C D M A Systems," IEEE Transactions on Mobile Computing, vol. 2, no. 3, pp. 143-160, April-June 2002. [14] , "An Algorithm for Maximal Resource Utilization in Wireless Multimedia C D M A Communication," in Proc. of 48th IEEE Vehicular Technology conference VTC'98, vol. 3, May 1998, pp. 2594 - 2598. [15] , "Modeling and Resource Allocation in Wireless Multimedia C D M A Systems," in Proc. of 48th IEEE Vehicular Technology conference VTC'98, vol. 2, May 1998, pp. 1279 - 1283. [16] , "Optimal Resource Management in Multimedia W C D M A Systems," in Proc. of IEEE Global Telecommunication Conference GLOBECOM 2000, vol. 3, Nov.-Dec. 2000, pp. 1544-1547. [17] S. Kahn, M . K. Gurcan, and O. O. Oyefuga, "Downlink Throughput Optimization for Wideband C D M A Systems," IEEE Communication Letters, vol. 7, no. 5, pp. 251 - 253, May 2003. [18] S. Kahn and M . K. Gurcan, "A Reduced Dimensionality Algorithm for Downlink Throughput Optimization in Wideband C D M A Systems," in Proc. of IEEE Global Telecommunication Conference GLOBECOM'02, vol. 1, November 2002, pp. 794 - 798. [19] R. Vannithamby and E. S. Sousa, "An Optimum Rate/Power Allocation Scheme for Downlink in Hybrid C D M A / T D M A Cellular System," in Proc. of IEEE Vehicular Tech-nology Conference, Fall VTC'00, vol. 4, September 2000, pp. 1734 - 1738. [20] , "Resource Allocation and Scheduling Schemes for W C D M A Downlinks," in Proc. of IEEE International Conference on Communications ICC'01, vol. 5, June 2001, pp. 1406 - 1410. [21] D. I. Kim, E. Hossain, and V. K. Bhargava, "Downlink Joint Rate and Power Allocation in Cellular Multirate W C D M A Systems ," IEEE Transactions on Wireless Communi-cations, vol. 2, no. 1, pp. 69 - 80, January 2003. [22] A. Bedekar, S. C. Borst, K. Ramanan, P. A. Whiting, and E. M . Yeh, "Downlink Scheduling in C D M A Data Network," Centrum Voor Wiskunde en Informatica, Prob-ability, Networks, and Algorithms (PNA) PNA-R9910, Oct. 1999. [23] , "Downlink Scheduling in C D M A Data Network," in Proc. of IEEE Global Telecommunications Conference, GLOBECOM '99, vol. 5, Dec. 1999, pp. 2653-2657. [24] F. Berggren, S. L. Kim, R. Jantti, and J. Zander, "Joint Power Control and Intracell Scheduling of DS-CDMA Nonreal Time Data," IEEE Journal on Selected Areas in Communications, vol. 19, no. 10, pp. 1860-1870, Oct. 2001. 18 [25] F. Berggren and R. Jantti, "Asymptotically Fair Scheduling on Fading Channels," in Proc. of 56th IEEE Vehnicular Technology Conference VTC'02, vol. 4, September 2002, pp. 1934 -1938. [26] F. Berggren, "Distributed Power Control for Throughput Balancing in C D M A Sys-tems," in Proc. of 12th IEEE International Personal, Indoor and Mobile Radio Com-munications, vol. 1, Sept.- Oct. 2001, pp. C-24 - C-28. [27] D. Tse, "Forward-Link Multiuser Diversity Through Rate Adaptation and Scheduling," Bell Laboratories Presentation, 1999. [28] J. M . Holtzman, "CDMA Forward Link Waterfilling Power Control," in Proc. of 51st IEEE Vehicular Technology Conference, vol. 3, May 2000, pp. 1663 -1667. [29] , "Asymptotic Analysis of Proportional Fair Algorithm," in Proc. of 12th IEEE International Symosium on Personal, Indoor and Mobile Radio Communications, vol. 2, September-October 2001. [30] G. Barriac and J. M . Holtzman, "Introducing Delay Sensitivity into the Proportional . Fair Algorithm for C D M A Donwlink Scheduling," in IEEE 7th Symp. on Spread-Spectrum Tech. & Appl, Sept 2002, pp. 2-5. [31] X . Liu, E. K. P. Chong, and N. B. Shroff, "Transmission Scheduling for Efficient Wireless Utilization," in Proc. of IEEE INFOCOM, 2001, pp. 776 - 785. [32] , "Opportunistic Transmission Scheduling With Resource-Sharing Constraints in Wireless Networks," IEEE Journ. on Selected Areas in Communications, vol. 19, no. 10, pp. 2053 - 2063, October 2001. [33] Y . Liu and E. Knightly, "Opportunistic Fair Scheduling over Multiple Wireless Chan-nels," in Proc. of IEEE INFOCOM Conference, vol. 2, March 30 - April 3 2003, pp. 1106 - 1115. [34] J. W. Lee, R. R. Mazumdar, and N. B. Shroff, "Opportunistic Power Scheduling for Multi-Server Wireless Systems with Minimum Performance Constraints," in Proc. of IEEE INFOCOM Conference, 2004. [35] Http://www.3gpp.org. [36] "Technical Specification Group Radio Access Network; Physical channels and map-ping of transport channels onto physical channels (FDD)," 3rd Generation Partnership Project, Tech. Rep. [37] A. Ghosh, M . Cudak, and K. Felix, "Shared Channels for Packet Data Transmission in W-CDMA," in Proc. of 50th IEEE Vehicular Technology Conference (VTC), vol. 2, September 1999, pp. 943 - 947. [38] R. Kwan and M . Rinne, "Performance analysis of the Downlink shared channel," in International Conference of Telecommunication (ICT), 2001. 19 [39] A. Mate, C. Caldera, and M . Rinne, "Performance of the Packet Traffic on the Downlink Shared Channel in a W C D M A Cell," in International Conference of Telecommunication (ICT), 2001. [40] S. Parkvall, E. Englund, P. Malm, T. Hedberg, M . Persson, and J. Peisa, "WCDMA evolved - High-speed packet-data services ," Ericsson Review, no. 2, pp. 56 - 65, 2003. [41] "Physical Layer Aspects of U T R A High Speed Downlink Packet Access," 3rd Generation Partnership Project, Technical Report 3G TR25.858, 2002. [42] T. J. Moulsley, "Throughput of High Speed Downlink Packet Access for UMTS," in Proc. of 2nd IEE International Conference on 3G Mobile Communication Technologies, no. 477, March 2001, pp. 363 - 367. [43] , "Performance of MTS High Speed Downlink Packet Access for Data Streaming Applications," in Proc. of 3rd IEE International Conference on 3G Mobile Communi-cation Technologies, no. 489, May 2002, pp. 302 - 307. [44] R. Love, A. Ghosh, and L. J. R. Nikides, "High Speed Downlink Packet Access Perfor-mance," in Proc. of 53th IEEE Vehicular Technology Conference VTC'01, vol. 3, May 2001, pp. 2234 - 2238. [45] Y . Ofuji, A. Morimoto, S. Abeta, and M . Sawahashi, "Comparison of Packet Scheduling Algorithms Focusing on User Throughput in High Speed Downlink Packet Access," in Proc. of 13th IEEE International Conference on Persoanl, Indoor and Mobile Radio Communications, vol. 3, September 2002, pp. 1462 - 1466. [46] A. Furuskar, S. Parkvall, M . Persson, and M . Samuelsson, "Performance of W C D M A high speed packet data," in The 55th IEEE Proc. of Vehicular Technology Conference (VTC), vol. 3, May 2002, pp. 1116 - 1120. [47] E. Poutiainen, R. Kwan, S. Hamalainen, and P. Chong, "Performance Study of the High Speed Downlink Packet Access (HSDPA) in a W C D M A Network," in CDMA International Conference CIC'01, Nov. 2001. [48] R. Kwan, P. Chong, and M . Rinne, "The Effect of Code-Multiplexing on the High Speed Downlink Packet Access (HSDPA) in a W C D M A Network," in Wireless Communication and Networking Conference WCNC, vol. 3, March 2003, pp. 1728 - 1732. [49] , "Analysis of the adaptive modulation and coding algorithm with the multicode transmission," in Proc. of 56th IEEE Vehicular Technology Conference VTC'02, vol. 4, September 2002, pp. 2007 - 2011. [50] Y . Zhao, "Theoretical Study of Link Adaptation Algorithms for Adaptive Modulation in Wireless Mobile Communication Systems," in IEEE Proc. of Universal Personal Communications, ICUPC'98, vol. 1, October 1998, pp. 587 - 591. 20 [51] K. Chawla and X . Qiu, "Throughput Performance of Adaptive Modulation in Cellular Systems," in Proc. of IEEE Universal Personal Communications, ICUPC'98, vol. 2, October 1998, pp. 945-950. [52] N . C. Ericsson, "Adaptive Modulation and Scheduling for Fading Channels," in Proc. of IEEE Global Telecommunications Conference, Globecom'99, vol. 5, December 1999, pp. 2668-2672. [53] , "Adaptive Modulation and Scheduling of IP traffic over Fading Channels," in Proc. of IEEE Vehicular Technology Conference, VTC'99-fall, vol. 2, September 1999, pp. 849-853. [54] S. Falahati. and A. Svensson, "Hybrid Type-II ARQ Schemes with Adaptive Modulation Systems for Wireless Channels," in Proc. of IEEE Vehicular Technology Conference, VTC'99-fall, vol. 5, September 1999, pp. 2691-2695. [55] M . Nakamura, Y . Awad, and S. Vadgama, "Adaptive Control of Link Adaptation for High Speed Downlink Packet Access (HSDPA) in W-CDMA," in Proc. of 5th Interna-tional Symposium on Wireless Personal Multimedia Communications, vol. 2, October 2002, pp. 382 - 386. [56] "Selection of MCS levels in HSDPA," NEC and Telecom Modus, Technical Document Rl-01-0589, May 2001. [57] J. Lee, R. Arnott, K. Hamabe, and N. Takano, "Adaptive Modulation Switching Level Control in High Speed Downlink Packet Access Transmission," in Proc. of 3rd IEE SG Mobile Communication Technologies, May 2002, pp. 156 - 159. [58] A. K. K. J. Yang, N . Tin, "Adaptive Modulation and Coding in 3G Wireless Systems," in Proc. of IEEE Vehicular Technology Conference VTC'02, vol. 1, September 2002, pp. 544 - 548. [59] S. J. Lee, H. W. Lee, and D. K. Sung, "Capacities of Single-Code and Multicode DS-C D M A Systems Accommodating Multiclass Service," IEEE Trans, on Vehicular Tech-nology, vol. 48, no. 2, pp. 376 -384, March 1999. [60] M . Fan, T. Minn, and K. Y . Siu, "Performance of Multirate Techniques in WCDMA," in Proc. of 54th IEEE Vehicular Technology Conference, vol. 4, Oct. 2001, pp. 2262-2266. [61] W. S. Jeon, D. G. Jeong, and B. Kim, "Design of Packet Transmission Scheduler for High Speed Downlink Packet Access Systems," in Proc. of 55th IEEE Vehicular Technology Conference VTC'02, vol. 3, May 2002, pp. 1125 - 1129. [62] S. Hamalainen, H. Holma, and K. Sipil, "Advanced W C D M A Radio Network Simula-tor," in Proc. of IEEE Personal, Indoor and Mobile Radio Communications, PIMRC'99, vol. 2, September 1999, pp. 951-955. 21 [63] D. I. Kim, E. Hossain, and V. K. Bhargava, "Dynamic rate and Power Adaptation for Forward Link Transmission Using High-Order Modulation and Multicode Formats in Cellular W C D M A Networks," in Proc. of 53th IEEE GLOBECOM, vol. 1, December 2003, pp. 393 - 397. [64] E. A. Eiselt and C.-L. Sandblom, Integer Programing and Network Models. Springer, 2000. [65] L. Xu , X . Shen, and J. W. Mark, "Dynamic Fair Scheduling With QoS Constraints in Multimedia Wideband C D M A Cellular Networks," IEEE Trans, on Wireless Commu-nications, vol. 3, no. 2, pp. 60 - 73, January 2004. [66] M . Hu, J. Zhang, and J. Sadowsky, "Size-Aided Opportunistic Scheduling in Wire-less Networks," in Proc. of IEEE Global Telecommunications Conference GLOBECOM, vol. 1 ,1-5 December 2003, pp. 538 - 542. [67] Z. Gao and S. Q. L i , "A Packet Scheduling Scheme in Wireless C D M A Data Network," in Proc. of IEEE International Conference on Communications, Cicuits, and Systems, and West Sino Expositions, vol. 1, June 29 - July 1 2002, pp. 211 - 215. [68] F. S. Hillier and G. J. Kieberman, Introduction to Mathematical Programming, 2nd ed. McGraw-Hill, Inc, 1995. [69] J. K. Sengupta, Stochastic Programming. New York: North-Holland, 1972. [70] S. Sen and J. L. Higle, "An Introductory Tutorial on Stochastic Linear Programming Models," Interfaces, vol. 29, no. 2, pp. 33 -61 , March-April 1999. [71] J. O. Sebeni and C. Leung, "Performance of Concatenated Walsh/PN Spreading Se-quences for C D M A Systems," in Proc. of 49th IEEE Vehicular Technology Conference (VTC), Houston, Texas, May 1999. [72] M . K. Simon and M.-S. Alouini, Digital Communication over Fading Channels, 2nd ed. John Wiley & Sons, 2005. 22 Chapter 2 Optimal Schemes Downlink Scheduling for CDMA Networks 2.1 I n t r o d u c t i o n The development of the third generation (3G) wireless network infrastructure allows a rich variety of traffic to be transmitted over the wireless channel. Each type of traffic has its own quality of service (QoS) requirements. Radio resource allocation algorithms are needed which will yield efficient use of resources. It is anticipated that downlink traffic will be especially important since most of the high-speed internet access and broadcast services traffic is in the downlink direction. In order to offer such broadband packet data transmission services, a high speed downlink packet access (HSDPA) channel has been incorporated in the 3GPP standard [1]. It is well known that adapting the transmission parameters in a wireless system to chang-ing channel conditions can be advantageous. In the case of fast power control [2], the transmission power is adjusted based on channel fading. Under good channel conditions a relatively low transmission power is required to maintain the target signal quality at the receiver. The process of changing transmission parameters to compensate for variations in channel conditions is known as link adaptation. Besides power control, adaptive modulation 1 The material in this chapter is largely based on the following: (1) R. Kwan and C. Leung, "Optimal Downlink Scheduling Schemes for C D M A Networks." Proc. of IEEE Wireless Communications and Networking Conference (WCNC'04), vol. 4, Atlanta, Georgia, March 2004. (2) R. Kwan and C. Leung, "Downlink Scheduling Optimization in C D M A Networks." I E E E Communica-tions Letters, vol. 8, No. 10, 2004. (3) R. Kwan and C. Leung, "Channel-Based Downlink Scheduling Schemes for C D M A Networks." Proc. of IEEE Vehicular Technology Conference (VTC'04), vol. 1, Los Angeles, California, Sept. 2004. (4) R. Kwan and C. Leung, "Load-Based Downlink Scheduling Schemes for C D M A Networks." Proc. of IEEE Vehicular Technology Conference (VTC'04), vol. 1, Los Angeles, California, Sept. 2004. 23 and coding (AMC) is another means for performing link adaptation [1, 3], and is used in the 3GPP HSDPA channel. The goal of A M C is to change the modulation and channel coding according to the varying channel conditions. In order to increase the bit rate, orthogonal multicode transmission is also used in the 3GPP standard [1, 2]. A scheme is proposed in [4] for maximizing the uplink throughput in a C D M A network by selecting the appropriate transmit powers and multicodes used by the mobile stations (MS's). In [5], the authors proposed a single user algorithm for selecting the MCS and the number of multicodes for HSDPA. In [6], the single user algorithm is applied sequentially for multiple users. In [7], it is found that the optimal strategy for scheduling downlink transmission in a C D M A network is to transmit to one MS at a time at full power rather than to transmit to several MS's simultaneously. This finding is based on a model which assumes that a linear relationship exists between the transmission bit rate and the transmit power for a fixed modulation scheme and error rate. This assumption is not valid when A M C is employed. The model also does not include any MS constraints such as maximum bit rate. In addition, in HSDPA [2], even though the orthogonal codes are used, orthogonality between two codes are not necessarily maintained due to multipath. In this chapter, a more realistic model is used to examine the problem of joint optimization using mathematical programming for multiple users in terms of MCS's schemes, number of multicodes, and transmit powers in the downlink of a C D M A system. This model is termed the channel-based model, which takes into account only the MS channel conditions. An optimization model which takes into account the amount of data in the MS buffers is also proposed. In this approach, the optimization takes into account both the MS channel conditions as well as the MS buffer sizes, and is termed the load-based model for simplicity. Simple analytical models for the single MS optimization are also developed, which take into account A M C and multicodes, as well as the power and multicode constraints, with-out the use of mathematical programming. Based on the single MS analysis, a sequential optimization algorithm is described for the multiple MS scenario. The idea is to allocate 24 resources to MS's one at a time. Finally, the performance attainable with the proposed sequential optimization algorithm is compared to that obtainable with joint optimization. 2.2 S y s t e m M o d e l We consider the model of a target base station, BS A , with a downlink high-speed traffic channel which employs A M C and multicodes. The downlink per-code signal-to-interference ratio (SIR), 7*, at MS i, i = 1,..., L , is given by where Pj is the power that BS A has allocated for the traffic channel to MS i, and n» is the number of multicodes allocated by BS A to MS i. The term represents the ratio of the total received interference and noise power I-r^ to the path gain hi between BS A and MS i. It is assumed in (2.1) that each multicode of MS i is allocated the same power. We assume that the BS A performs a resource allocation once every scheduling period of duration Ta seconds, and the value of & is assumed to be constant during Ta. In order to satisfy the block error rate (BLER) QoS requirement when MS i uses modu-lation and coding scheme (MCS) j,j — l,...,J,we require that 7* > Xij, where \itj is the SIR requirement for MCS j to achieve MS Vs target B L E R of ej. Using (2.1) and setting 7i = \ j , the minimum required power allocation Pitj(rii) for MS i which employs MCS j with rii multicodes is given by For a given target B L E R value e0, \ij can be obtained from fj(Xij) = e0, where fj(.) represents the B L E R vs. SIR relationship for MCS j. The transmission bit rate to MS i li = hi Pi/Hi _ Pj/Uj (2.1) PijiP'i) — Hi^iyjii- (2.2) 25 assuming MCS j and n; multicodes is given by (2.3) where the basic bit rate r, j is given by R^log2Mj. (2.4) In (2.4) W is the chip rate, R^ is the code rate for MCS j, Mj is the number of points in the modulation constellation for MCS j and g is the spreading factor. For simplicity, it is assumed that all MS's use the same spreading factor. In this model, it is also assumed that the multipath interference due to the desired and interfering, signals coming from BS A have the same effect on the detection of the desired signal, and that the allocation does not affect the interference. The objective is to maximize the sum of the bit rates assigned to all MS's for each scheduling period Ta, given a maximum allowable BS high-speed traffic channel power, P m a x , a max-imum number, Nmax, of multicodes that the BS can allocate collectively to all MS's and certain per-MS constraints. Specifically, the optimization problem is formulated as a mixed integer, non-linear programming (MINLP) problem as follows: 2.3 J o i n t O p t i m i z a t i o n M o d e l 2.3.1 Channel-Based Model (2.5) 26 subject to Oij e {0,1}, (2.6) X > . = 1, (2-7) .max > (2.8) L E " * ^ N m a x , (2.9) i=l J J E P i < Pmax- (2.H) i=l In (2.5) a = [aitj] is a L-by-J matrix, and n = [ni, n 2 , n L ] . The integer programming variable atj takes on value 1 if and only if MS i is to use MCS j. The parameter Ni<max represents the maximum number of multicodes that MS i can be allocated and is typically less than Nmax [1]. The term p is a factor which is introduced to minimize the required power and the number of multicodes needed in maximizing the total bit rate. It is convenient to use v = r(^f^ + ^^) (2.12) where r is a small constant, e.g. 10~3, used to ensure that the factor v has a negligible effect on the value of the objective function (2.5). 2.3.2 Load-Based Model In section 2.3.1, the optimization model implicitly assumes that the buffer for each MS at the BS is never empty, i.e. there are always data to be sent to all MS's. In such a case, the transmit bit rate is identical to the assigned bit rate. However, this is not so if MS's are not always back-logged. It would be wasteful to assign more resources to an MS in a scheduling 27 period than what is needed to empty the MS's buffer. The problem of allocating resources should then take into account the amount of data waiting in the MS buffers. In this section, we consider such an optimization problem and study the resulting ef-ficiency gains. Similar to the channel-based model, we assume that the BS A performs a resource allocation once every scheduling period of duration Ta seconds and that new data arrive at the MS buffers only just before the start of a new scheduling period. The channel is assumed to be more or less constant during any Ta seconds. Let j Ri = ^2 a^TijUi, Vi = 1,..., L (2-13) j=i be the bit rate allocated to MS i. Let Bi be the number of bits in the buffer for MS i at the beginning of a scheduling period. For convenience, we define the normalized buffer size for MS i as A = Bi/WTa, Vz = l , . . . , L . (2.14) The optimization problem is then formulated as ^ { E ^ E ^ . A ) - , } , (2.15) subject to (2.6)-(2.11). Let Ai = RiTa and Qi denote the number of bits allocated and the number of bits actually sent to MS i during the scheduling period. We can write Qi = mm {Ai*,Bi}. (2.16) where Ai* = TaRi* and Ri* is the allocated bit rate for MS i with the optimal values a^*, n* and P*. Denote the total number of bits sent and the total number of bits allocated 28 during the scheduling period by Q = Vjf = 1 Qi and A = Vjf = 1 A respectively. The total bit rate during the scheduling period is given by Rtot = Q/Ta (2.17) = E M I N ( E < , < ^ . A ^ ) (2.18) i=i i=i Three other measures of the effectiveness of a scheduling scheme are useful. The scheduler efficiency, n, is defined as V = Q/A. (2.19) and the scheduler deviation factor, £, is defined as C = T J T V E I A - ^ I . (2.20) The power efficiency r\v is defined as VP = ^ 7 7 - (2-21) The term r\ is used to quantify the efficiency of the scheduling. Ideally, 77 should be as close to 1 as possible, so that the allocated resources are utilized efficiently. The term £ is used to quantify the discrepancy between the normalized buffer size and the actual allocation. It is desirable to have as small a value of £ as possible. The power efficiency r\v describes the total bit rate achieved per unit of power, and should be as high as possible. 2.3.3 Numerical Results A model for the joint optimization of variable parameter values in a C D M A downlink high-speed traffic channel was formulated in Section 2.3.1. We now provide some numerical 29 results obtained by solving (2.5) using the linearized models described on the Appendix A. For illustration purposes, let the received total interference and noise power, l\T\ for MS i be / | r ) = ahiPT+Y^hhkA + lN, (2.22) k€B where PT is the total transmit power of the target BS A , Ik is the transmit interference power due to the kth BS in the interfering BS set B and IN is the background noise power. The term h^^ is the path gain from interfering BS k to MS i. The orthogonality factor, a, is used to model possible intra-cell interference. Correspondingly, is given by £ = aPT+^hh^/hi + lN/hi, (2.23) k€B = a P T + Y,IkVk,i + lN/hi, (2.24) fees where v^i = hk,i/hi. To simplify the presentation of results, we assume that there is only one BS in the interfering BS set B, and that the effect of background noise is negligible. The default parameter values used are listed in Table 2.1. For the results obtained in this section, the value vH = 0.0016 is used. Fig. 2.1 shows the total bit rate, Rtot = £f=i R*, for the optimal values of a , P,n as a function of the maximum allowable power Pmaxi with a = 0.1 and 0.4 for both a continuous and an integer number of multicodes, assuming that the MS buffers are backlogged. It can be seen that the commonly used, but unrealistic assumption of a continuous number of multicodes results in a slight overestimation of the total bit rate. Fig. 2.2 shows the allocated MS powers as a function of F m a x . Depending on the values of a and Pmax, the BS may transmit to only one MS or to several MS's simultaneously. We note that this finding differs from that in [7] which states.that the BS should only transmit to one MS at a time in order to reduce the intra-cell interference. The difference is due to 30 three main factors: (1) the non-linear relationship between the allowed user bit rate R4 and power Pi when A M C is used, (2) the absence in [7] of any constraints on the bit rates or powers which can be allocated to MS's, and (3) the difference between SIR expressions in (2.1) and [7]. In our model, an increase in Pj does not necessarily yield an increase in R4. An incremental increase in Pmax causes a power reallocation among the MS's in such a way as to realize the greatest incremental increase in bit rate. It can be seen that for a. = 0.1 the power allocated for transmission to MS 1 saturates at 7.2 W. This can be explained as follows: when Pmax reaches 12.9 W, MS 1 is using the maximum number of multicodes. The total bit rate, Rtot, is plotted as a function of Pmax for a = 0.1 and 0.4 in Fig. 2.3. Curves for two cases are shown: in Case 1, the BS is constrained to only transmit to one MS at a time whereas in Case 2 it can transmit to any number of MS's at a time. It can be seen that Rtot can be significantly higher in Case 2 compared to Case 1. For example, for a = 0.1 and Pmax = 14.0 watts, Rtot = 8.4 Mbps for Case 2; this value drops to 3.6 Mbps if transmission is restricted to one MS at a time as in Case 1. The results shown in Fig. 2.4 are for a = 0.1, and v i = (0.007 0.0065 0.006) where the zth component of v x is the ratio of the path gains for the interfering BS and own BS of MS i. Assume a maximum of 3 MS's are allocated resources at the beginning of every scheduling period. The buffer content size ratio vector for the three MS's with respect to the first MS is D / A = (A D2 D3)/D1 = (1 2.2 3.5). The top part of Fig. 2.4 shows the total bit rate Rt0t as given in (2.18) as a function of total normalized buffer content size D = YA=I A f ° r both the basic (channel-based) and load-based models2. It can be seen that a modest bit rate increase can be obtained with load based optimization. It might be noted that due to the limit on the available power and the number of multicodes, the total bit rate approaches a limiting value as D is increased. The bottom part of Fig. 2.4 shows the scheduler efficiency as a function of D. The load based optimization may result in a much 2For the basic model, the values for a* • and n* are obtained based on (2.5), so that the assignments are independent on the MS buffer sizes. 31 higher efficiency even though the difference in bit rates of the basic and load-based models is relatively small. This is because some of the allocated rates in the basic model may be much higher than the corresponding rates in the load-based model. Fig. 2.5 is similar to Fig. 2.4, except that v i = (0.005 0.006 0.008). In this case, the MS with the best channel condition among the three MS's, i.e. MS 1, has the smallest buffer content size. Since the basic scheduler only takes the channel condition into account, the highest bit rate would naturally be assigned to MS 1. However, MS 1 has the least amount of data to send and may not fully utilize its allocated amount. As a result, Fig. 2.5 shows that the load-based scheduler yields a significantly higher bit rate than the basic scheduler. Fig. 2.6 shows the power efficiency rjp as a function of total normalized buffer content size D for a = 0.1, T>/Dx = (1 2.2 3.5) and v x = (0.007 0.0065 0.006) for both the basic and load-based models. Fig. 2.7 is similar to Fig. 2.6, except that v x = (0.005 0.006 0.008). In both cases, the value of rjp is higher for the load-based scheduler as compared to the basic scheduler. The reason is that the former attempts to allocate resources taking into account the load information. Thus, less resources will generally be allocated to an MS with a smaller amount of data to transmit. Without knowing the load information, the basic scheduler allocates the same resources regardless of the amount of data in the MS buffers. As a result, extra resources may be unnecessarily allocated. Since the allocated rates for the load-based scheduler depend on D, the discrete nature of the A M C and multicodes gives rise to the fluctuations in the curve for the load-based scheduler. Fig. 2.8 shows the deviation factor £ as a function of total normalized buffer content size D for a = 0.1, D/Dx = (1 2.2 3.5) for both the basic and load-based models. The top part of Fig. 2.8 corresponds to v x = (0.007 0.0065 0.006), while the bottom part corresponds to V i = (0.005 0.006 0.008). From the definition, when ( is small, there is little difference between the number of allocated bits and the actual number of bits in the buffer at the beginning of a scheduling period. Ideally, £ should be as close to zero as possible. However, this may not always be possible due to the following reason: when the traffic load is high, 32 the amount of data in the buffers exceed what can be allocated given the available resources. As shown in Fig. 2.8, the load-based scheduler has a significantly smaller deviation factor compared to the basic scheduler at low to moderate traffic loads. At high traffic load, both schedulers can only deliver a small portion of data in the buffer during Ta due to the limited available resources, and the deviation factors increase. The deviation factors for the two schedulers approach one another at high load. This is because when the buffers are always back-logged the basic and load-based schedulers produce the same resource allocation. Parameter Value MCS QPSK(l /2 , 3/4), 16-QAM(l/2, 3/4) Channel Coding Turbo Code Chip rate (W) 3.84 Mcps Spreading Factor (g) 16 N 15 PT 18 watts h 18 watts a 0.1 T 0.001 IN negligible eo ~ 10"3 Table 2.1: List of parameter values. 33 10 0 . 2 4 6 8 10 12 14 16 18 Maximum allowable power (Watt) Figure 2.1: Total bit rate as a function of the maximum allowable power, Pmax, for a = 0.1 and 0.4, assuming an integer and a continuous number of multicodes. 8 o' MS 1 MS 2 . MS3 1 i 1 I 1 1 1 A / . 1 v. 0 2 4 6 8 10 12 14 16 18 Maximum allowable power (Watt) 10 Maximum allowable power (Watt) Figure 2.2: Allocated MS power as a function of the maximum allowable power, Pmax- Top: a = 0.1, Bottom: a = 0.4, assuming an integer number of multicodes. 34 a 0 proposed model, ct=0.1 x- single user model, ct=0.1 - - e - proposed model, a=0.4 G- single user model, a=0.4 • i j O- O • ( 3 . . . . 0 . . . •o >• °' 6 o c 0 2 4 6 8 10 12 14 16 18 Maximum allowable power (Watt) Figure 2.3: Total bit rate as a function of the maximum allowable power, Pmax at a = 0.1 and 0.4 for the proposed model and the single user model, assuming an integer number of multicodes. Figure 2.4: (Top) Total bit rate Rtot (Bottom) Scheduler efficiency 77 as a function of total normalized buffer size D for a = 0.1, Pmax = WW, Niymax = 10, T>/Dx = (1 2.2 3.5) and vi = (0.007 0.0065 0.006) for both basic and load-based models. 35 Figure 2.5: (Top) Total bit rate Rtot (Bottom) Scheduler efficiency 77 as a function of total normalized buffer size D for a = 0.1, Pmax — 10W, Ni:Tnax = 10, D/Di = (1 2.2 3.5) and v i = (0.005 0.006 0.008) for both basic and load-based models. Figure 2.6: Power efficiency r]p as a function of total normalized buffer size D for a — 0.1, Pmax = WW, NiiTnax = 10, D/Di = (1 2.2 3.5) and v x = (0.007 0.0065 0.006) for both basic and load-based models. 36 Figure 2.7: Power efficiency np as a function of total normalized buffer size D for a = 0.1, Pmax = WW, Ni>max = 10, D/JDI = (1 2.2 3.5) and v i = (0.005 0.006 0.008) for both basic and load-based models. Figure 2.8: Deviation factor £ as a function of total normalized buffer size D for a = 0.1, Pmax = 10W, Ni<max = 10, D / D j = (1 2.2 3.5) and (Top) v i = (0.007 0.0065 0.006) (Bottom) v i = (0.005 0.006 0.008) for both basic and load-based models. 37 2 .4 S e q u e n t i a l O p t i m i z a t i o n M o d e l In section 2.3, an optimization approach was used which jointly optimizes the power, number of multicodes and MCS for each MS and implicitly, the number of MS's which are allocated resources in order to maximize the allocated bit rate for the system. While this may be a desirable goal, the computational complexity associated with mixed-integer, nonlinear programming (MINLP) can be high [8]. One way to reduce the computational burden is to independently optimize the bit rate for each MS instead of optimizing the sum of the bit rates for all MS's. After allocating resources for the first MS, the optimization for the next MS is based on the remaining resources. Such a sequential optimization (SO) technique can lower the computational complexity by allowing the optimization to be done independently for each MS. However, the optimized sum of the MS bit rates is generally higher than the sum of the optimized MS bit rates. This optimization is used in the multiple MS sequential optimization algorithm described in sections 2.4.1 and 2.4.2 for the channel-based and load-based optimization models respectively. 2.4.1 Channel-based Model Single M S Optimizat ion - Continuous Number of Mult icodes Let the downlink maximum possible received signal-to-interference ratio (SIR) of MS i be given by l[ = Pillu (2-25) where is the power available to MS i. Assuming that multicode transmission is used, that the number of multicodes is continuous, and that all codes share the power equally, the maximum number, Nitj , of codes that can be transmitted while achieving the target B L E R 38 of eo for each code is given by 7» Nid = min [ —-, NitTI The bit rate for MS i with MCS j given JVjj multicodes would be (2.26) rij ( A^) , if ii < KjNi, r- -N- if > A- -JV-(2.27) (2.28) where the basic bit rate r^j is given in (2.4). In the model, it is assumed that {Xitj < Xij+i, j = 1 , J — 1}, and {r^j < r ; j + i , j = 1,..., J — 1}, which are realistic in practical applications of A M C . It is also assumed that the ratio ritj/\ij decreases with j [2]. With the combination of A M C and multicodes, at a given JI, the optimal MS bit rate Ri is the maximum bit rate that can be provided among all MCS's, i.e. Ri = max R; ,•. ie{i,..,J} (2.29) r N i,J i,max\ r N i,3 i, max r . -JV. r,2 f, max r.,N. (min) fr=3 /c=2 v (min) ft i,2 (min) '/.3 (min) y 7-Figure 2.9: Allocated MS bit rate as a function of 7^ . A typical plot of Ri as a function of 7- is shown in Fig. 2.9. As 7- increases from 0, an 39 increasing number of multicodes can be utilized, resulting in an increase in R4. For 7^ close to 0, MCS 1 would be used due to the poorer error performance of higher order MCS's. As 7^ reaches 7^1, the maximum number, Ni>inaxi of multicodes allowed for MS i is used. Further increase in 7- does not allow a higher number of multicodes to be allocated. At this stage, the next higher order MCS still gives a lower bit rate due to the poorer error performance. When 7^ reaches 7 - ™ n \ j = 2 (i.e. MCS 2) is selected, and R4 = Ri,2- In a similar way, Ri increases with increasing 7- until j = J and N^max is reached. Therefore, given 7^ , the problem of evaluating Ri reduces to determining the set of thresholds Vj = 1,..., J} and {7i ,7 m ) ,Vj = 1,..., J}. The threshold jij is given by %j = K,jNitmax,j = 1 , J . (2.30) The threshold 7 - ™ ^ can be obtained by solving the equation relating the highest effective bit rate of the MCS j - 1 with the lowest effective bit rate of the MCS j. Thus, ~{min) Ni^axfij-l = ri,j T ) J = 2 , . . . J , (2-31) which yields = \ ^ ^ W , J = 2,...,J. (2.32) It might be noted that ^ m m ' = 0 and 7-™+i = 00. The optimal number, Nit of multicodes for MS i is given by rii = < N- • < V < ^™in) 1 < i < J 40 Subsequently, the optimal single MS bit rate Ri and transmit power Pi are given by Ri Ti} j Tli, Pi XijTli^i. (2.34) (2.35) Note that the index j in (2.34) and (2.35) is selected based on a suitable value obtained in (2.33). Integer Number of Mult icodes With an integer number of multicodes, the optimization becomes difficult due to the fact that the range of 7- over which MCS j is optimal may consist of several disjoint intervals. We consider here a procedure which gives near optimal results. The term T |™"^ can be obtained as follows. Let 3^ £ ( 0 , 0 0 ) be the smallest value such that L^i,j ^ fi,j-lNitmax, 2 < j < J. (2.36) Then ~ (min) ^i,j 0 , j = 1 A j , K j < J OO , j = J + 1. (2.37) The number, n;, of multicodes for MS i is now given by [ i i i K j \ , 7 & i n ) < i < 7 « , 1 < j < J Ni ^ 1 - ~ (min) * ^ • T (2.38) ,max Using (2.38), the power Pi and bit rate Ri allocated to MS i are given by (2.35) and (2.34) respectively. 41 Multi-MS Sequential Optimization In section 2.4.1, we considered the channel-based optimization of MCS and number of multi-codes for a single MS. The joint optimization for many MS's can be computationally complex. Based.on the results for a single MS, we now consider a (sub-optimal) successive optimization procedure which takes into account multiple MS's at each scheduling instant. The main idea is to schedule each MS independently based on the available remaining resources. Generally, to maximize the assigned total bit rate, the MS's should be ordered accordingly to channel conditions with the first MS having the best channel condition. The procedure is outlined in the following: 1. Set i = 1 2. Set P\ — Pmaxi and Nitmax min{iVj ] m a x , Nmaxj 3. Compute \j as given in (2.30), and 7!™"' as given in (2.32) for the continuous case or (2.37) for the integer case 4. Using (2.33) or (2.38), (2.34) and (2.35), compute the number of multicodes n i ; the bit rate Ri, and the power Pi allocated to MS i 5. Calculate the remaining resources Nmax < N m a x Tij, (2.39) Pmax * Pmax P%- (2.40) 6. If N m a x > 0 and P m a x > 0, increment i by 1 and go to step 2; otherwise go to step 7 7. Prepare for the next scheduling period. 42 2.4.2 Load-Based Model Single MS Optimization - Continuous Number of Multicodes If packets arrive at the buffers for the different MS's in a random fashion, the buffer content sizes can be taken into account to improve resource allocation. Given that the normalized buffer content size for MS i is Di, the bit rate required to empty the buffer in Ta second is DiW. Furthermore, let C^k\k = 1,2,..., J + 1 be the event that DiW falls in the k th bit rate region shown in Fig. 2.9, i.e. ritk-iNUmax < DiW < ritkNi!max, k = 1, 2 , . . . , J + 1, (2.41) where r^n = 0 and r^j+i = oo. The basic idea behind load-based scheduling is to tailor the number of multicodes and power depending upon the bit rate region which DiW falls into. We choose to maximize the allocated bit rate Ri while using the minimum amount of power. An alternative is (r) to maximize Ri using the minimum number of multicodes. The required number, n\ , of multicodes, the MS bit rate rf, and the MS power are given by ( r ) f (DiW)/ruk, if eg, k = l, 2 , . . . , J, n\ = i (2-42) I Ni,maX, if Citk , k = J + 1, rf = rhjnf, (2.43) P / r ) = A y n ^ , (2.44) and the selected MCS j is given by j = m in (M) if Cg,/c = l , 2 , . . . , J + l . (2.45) 43 The corresponding required SIR is given by r) (2.46) When power resources are unlimited, (2.42), (2.43), and (2.44) are optimal given the buffer content size J5j. However, due to the varying channel conditions, the available i[ might not be able to support what is required from (2.46). Under such a circumstance, the allocation of resources should not only reflect the buffer content size E>i, but also the available SIR j[. Let Qj and dj be the conditions such that 7T~ = !y- • < V < ~(mi") 1 < 7 < J — lz,j ^ li ^ 7 i j+i ' 1 — J — J (2.47) (2.48) are true. The resulting optimal number, n;, of multicodes, the bit rate B4, and the power P» for MS i are given by rii = < n. (r) , i f 7 i ( r ) < 7 i , Pi = 5^- , if {li^ > li) A Cjj, iVi,max, if ( 7 i W >7i) A Q J . (2.49) (2.50) (2.51) Integer Number of Multicodes With an integer number of multicodes, the optimization becomes difficult due to the fact that the range of i\ over which MCS j is optimal may consist of several disjoint intervals. We consider here a procedure which gives near optimal results. The term i \ c a n be obtained as follows. Let Bitj G (0, 00) be the smallest value such 44 that .Kj. — 11,] — X1 yi,r, 2 < j < J, (2.52) and is given by ~ (min) o , j = i Pi,j, l<j<J oo , j = J + 1. (2.53) Due to the discrete nature of the multicodes, (2.42) must be modified. The desired number of multicodes for MS i is given by (r) n) = IXAWO/ri,*!, if C j J , l < f c < J, Ni, if ctlk = j + \. (2.54) (r) Again, due to the available 7^ for MS i, the desired power P, and number of multicodes n. may not always be allocated. Taking 7^ into account, the resulting number of multicodes n-, bit rate Pt-, and power P/ are given by P' n. (r) if it] < ii, » L T ^ T J , if [if > l'i) A ^ i , J ) A W , if (7i r ) >7i) A C ~ . ri,jnii Kjni£i (2.55) (2.56) (2.57) Let j be the selected MCS. Due to the function [J in (2.55), the performance can still be 45 improved when the condition Citj — {fi,j — l-Ni,max ^ Ri) A (Aj j_ iA^ ] T n a x ^ 7i)> j = 2,...,J (2.58) is taken into account. The number of multicodes n,, bit rate Pj , and power Pj are given by m = I *' M ' (2.59) Ri = { P = < if TV- if Ai) R'i, if fi,j—\Nitmax > if P ' if c|J Xij — \Ni:max £ if (2.60) (2.61) Subsequently, the required SIR for MS i would then be 7* = Pj/£;. Multi-MS Sequential Optimization The multi-MS sequential optimization for the load-based system is similar to that described in section 2.4.1, except that (2.49)-(2.51) or (2.59)-(2.61) are used instead in step 4. The total bit rate Rtot is given by L Rtot = ^ m i n ( P j , A V K ) , (2.62) i = l where Pj is given in (2.50) or (2.60) for continuous or discrete multicodes respectively. Due to differences in the channel conditions and buffer content sizes among the MS's, the order of resource allocation to the MS's will generally affect the total allocated bit rate. The optimal ordering can be determined exactly by exhaustive search when the number of 46 MS's is small3, or heuristically using a combinatorial technique [9] such as Tabu search when the number of MS's is large. 2.4.3 Numerical Results Channel-Based Model Using the default parameter values listed in Table 2.1, we now provide some numerical results obtained by solving (2.5) for the joint optimization, and the procedure outlined in section 2.4.1 for the sequential optimization. Fig. 2.10 shows the total bit rate Rtot = Y^f=i Ri as a function of P m a x when v x = [viti vi>2 1*1,3] = [0.005 0.006 0.007] and Ni>max = 5 for both joint and sequential optimization, assuming a continuous and an integer number of multicodes. As Pmax increases, higher order MCS's can be supported. As a result, higher bit rates can be obtained. As expected, the Rtot obtained from joint optimization is always superior to that obtained from sequential optimization. With joint optimization, Rtot increases monotonically with Pmax- The joint optimization model ensures that just enough power is allocated to maximize the total bit rate. Thus, increasing P m a x will not result in a decrease in Rtot- On the other hand, the sequential optimization procedure does not guarantee that Rtot increases monotonically with P m a x . A scenario is possible in which increasing P m a x results in the first MS taking most if not all of the power available to achieve a certain bit rate. However, if P m a x is slightly reduced, the first MS might require much less power, leaving enough power for the second MS so that the combined bit rate for both MS's might exceed that of the MS in the first scenario. It can also be observed that for joint optimization, a continuous number of multicodes typically provides a slightly higher bit rate than the integer number of multicodes case. In contrast, for sequential optimization, the bit rate with an integer number of multicodes can be higher and the difference in Rtot can be much bigger. 3 This case may generally be valid in the context of HSDPA since with a fixed spreading factor of 16, the number of multicodes, and hence the number of simultaneously supported MS's, is limited [1]. 47 Fig. 2.11 shows the power efficiency TJP as a function of Pmax when v i = [0.005 0.006 0.007] for both joint and sequential optimizations. As expected, a higher bit rate can be achieved using a higher order MCS at the expense of a higher transmit power. It can be seen that rjp decreases monotonically with Pmax for joint optimization. This is not always true for sequential optimization. Fig. 2.12 shows the total bit rate Rtot as a function of Pmax for joint and sequential optimization for two different channel conditions (case 1) v i = [0.8 0.8 0.8] and (case 2) v i = [0.005 0.005 0.005]. It can be seen that even though joint optimization can provide a significantly higher bit rate Rtot compared to sequential optimization when the channel conditions are good (i.e. case 2), the improvement is relatively small when the channel conditions are poor (i.e. case 1). The reason is that when the interference level is high, the limited resources can be allocated to fewer MS's. Fig. 2.13 shows Rtot as a function of Pmax when V i = [0.2 0.6 0.9] for joint optimization, and (case 1) v i = [0.2 0.6 0.9] and (case 2) v i = [0.9 0.6 0.2] for sequential optimization. The result shows that the order of allocation of resources to MS's based on their channel conditions is important for sequential optimization. It also suggests that a higher assigned total bit rate can generally be achieved when the MS's are ordered according to their channel conditions with the first MS having the best channel condition. It is interesting to compare the system performance obtained by our channel-based op-timization model with a more restrictive sequential optimization model presented in [6], in which the maximum allowable power is shared equally among the MS's. This model can be viewed as a special case of our proposed sequential model. The performance of this model is evaluated using simulations in [6]. In order to distinguish the model [6] from our model, the former will be referred to as sequential optimization with equal power allocation (SO-EPA), while latter is simply referred to.as sequential optimization (SO). Figs. 2.14 and 2.15 show the total bit rate Rtot as a function of the maximum allowable power Pmax with v x = [0.005 0.006 0.007] for JO, SO, and SO-SPA, for Nitmax = 5 and 48 Ni,max = 10 respectively. As shown in Fig. 2.14, SO does not necessarily perform better than SO-SPA. In this example, the first MS has the best channel quality, followed by the second MS and then the third MS. Since the maximum number, NitTnax, of multicodes is 5, SO attempts to achieve a higher bit rate for the first MS using a higher order MCS, which, in turn, requires a higher power allocation. As a result, less power is available to MS 2 and MS 3, and their available multicodes may not be fully utilized. Since the available power is shared equally under SO-EPA, a higher multicode utilization can be achieved. Since it is more power efficient to increase bit rate using more multicodes than higher order modulations [5], SO is not necessarily better than SO-SPA when Nitmax or Pmax is small. However, for larger values of Ni>max or Pmax, the performance of SO is generally better than that of SO-SPA as shown in Fig. 2.15. In all cases, JO outperforms both SO and SO-SPA as expected. 5 1 i 1 o ' : ' ' j.o 9 «• J£ . » • • a./ \ - i 9 -O - Sequential Optimal (continuous) Sequential Optimal (integer) • O Joint Optimal (continuous) Joint Optimal (integer) * 0\1 1 1 1 1 I I I 0 2 4 6 8 10 12 14 16 16 Maximum allowable power (Watt) Figure 2.10: Total bit rate Rtot as a function of the maximum allowable power Pmax with vi = [0.005 0.006 0.007] for both joint and sequential optimization, assuming a continuous and an integer number of multicodes. 49 2 0.9 [ .9,' Joint Optimal (integer) t ; • *. '*•. o. . : :* . - . '——2 '• • • 6 • < • :• + - e - Sequential Optimal (continuous) ^ » F - Sequential Optimal (integer) 6 8 10 12 Maximum allowable power (Watt) Figure 2.11: Power efficiency rjp as a function of the maximum allowable power Pmax with vi = [0.005 0.006 0.007] for both joint and sequential optimization, assuming a continuous and an integer number of multicodes. Figure 2.12: Total bit rate Rtot as a function of the maximum allowable power Pmax for joint and sequential optimization, (case 1) v x = [0.8 0.8 0.8] and (case 2) v x = [0.005 0.005 0.005]. 50 Figure 2.13: Total bit rate Rtot as a function of the maximum allowable power Pmax with vi = [0.2 0.6 0.9] for joint optimization, and (case 1) vi = [0.2 0.6 0.9] and (case 2) \ \ = [0.9 0.6 0.2] for sequential optimization. 1 ..o 0 " ' o" c ? '.o - * - Joint Optima! G Sequential Optimal -H— Sequential Optimal (equal power allocation) „ ! ? 1 1 1 1 • I • I I I 'I 0 2 4 6 8 10 12 14 16 18 Maximum allowable power (Watt) Figure 2.14: Total bit rate Rtot as a function of the maximum allowable power Pmax with vi = [0.005 0.006 0.007] for joint optimization, sequential optimization, and sequential optimization with equal power allocation, given that NiyTnax = 5. 51 6 i 1 1 0 . .0 . . . 0 " ' j 1 %s \ ; P , . Q : Jf p / - * - Joint Optimal 0 Sequential Optimal -4— Sequential Optima! (equal power allocation) 0 2 4 6 8 10 12 14 16 18 Maximum allowable power (Watt) Figure 2.15: Total bit rate Rtot as a function of the maximum allowable power Pmax with vj = [0.005 0.006 0.007] for joint optimization, sequential optimization, and sequential optimization with equal power allocation, given that NitTnax = 10. Load-Based Model Using the default parameter values listed in Table 2.1, we now provide some numerical results for the joint and sequential load-based optimizations. The results also assume V i = K i ui,2 vii3] = [0.15 0.010 0.0015], and Niitnca = 10. Figure 2.16 shows the total bit rate Rtot as a function of Pmax for JO and SO with and without optimal ordering, with D = (2.0 0.8 0.5). The value of RtQt for the joint and sequential models can be obtained using (2.18) and (2.62) respectively. In this case the MS with the largest buffer content size experiences the worst channel condition and vice versa. The result shows that JO provides a higher total allocated bit rate than SO. It can also be seen that with SO, optimal ordering can provide a significant improvement. With JO, Rtot increases monotonically with Pmax- However, with sequential optimization, a higher Pmax may allow more resources to be allocated to the first MS, leaving less resources for other MS's. As a result, a higher Pmax does not guarantee a higher Rtot for SO. The assumption that the number of multicode 52 is continuous leads to a slightly higher Rtot for JO. The reason is due to the more relaxed constraint. In the case of SO with optimal ordering, a greater increase in RtQt can be observed when the number of multicodes is assumed to be continuous. Figure 2.17 shows the power efficiency, n p , as a function of Pmax for JO as well as SO with and without optimal ordering. A higher bit rate can be achieved using higher order MCS's at the expense of a higher transmit power. The figure shows that rjp generally decreases with increasing Pmax- Note that since r\v is not the optimization objective function, r]v for JO can be lower than that for SO. Figure 2.18 shows the total bit rate, Rtot, as a function of the total normalized buffer size D — Di f ° r JO and SO with and without optimal ordering, with D / D 3 = [3.5, 2.5, 1.0], and Pmax = 10 W.. At low traffic loads, radio resources are not a limiting factor and there is little difference among the three schemes. As the traffic load increases, JO exhibits a significant improvement over SO with no optimal ordering. Since Rtot is sensitive to the combination of channel condition and buffer content size, the first MS with a bad combination can leave little resources for subsequent MS's resulting in a poor overall performance. Figure 2.18 suggests that SO with optimal ordering can provide a relatively good performance. 53 i i i o }o~^ v » if ' •¥ ' • ' .-x> - •• • x • "Js : : / \ J ••* / '* - * - S O , integer - « - S O (Optimal Ordering), integer - e - JO , integer * S O , continuous « S O (Optimal Ordering), continuous o JO, continuous 0 2 4 6 8 10 12 14 16 18 Maximum allowable power (Watt) Figure 2.16: Total bit rate Rtot as a function of the maximum allowable power Pmax for joint opti-mization and sequential optimization with and without optimal ordering, with D — [2.0, 0.8, 0.5]. Figure 2.17: Power efficiency T]P as a function of the maximum allowable power Pmax f° r joint opti-mization and sequential optimization with and without optimal ordering, with D = [2.0, 0.8, 0.5]. 54 - * - SO, integer - * - S O (Optimal Ordering), integer - e - JO , integer * SO, continuous • •»• • S O (Optimal Ordering), continuous o JO, continuous I I I l 1 1 F 0 1 2 3 4 5 6 Total normalized buffer size D Figure 2.18: Total bit rate Rtot as a function of the total normalized buffer size D = J2f=i Di f° r joint optimization and sequential optimization with and without optimal ordering, with D / D 3 = [3.5, 2.5, 1.0], and Pmax = 10 W. 2.5 C o n c l u s i o n s The allocation of radio resources for the downlink of a C D M A network has been formulated as a mixed-integer nonlinear programming problem in which resources allocated to MS's are jointly optimized. It is shown that due to the non-linear nature of A M C as well as the maximum number of multicodes which can be assigned to an MS, an optimal allocation generally involves simultaneous transmissions to several mobiles. An optimal scheduling scheme which takes into account the amount of traffic destined for the different MS's was also proposed and studied. The results show that such a scheduler provides significant performance gains over schedulers which ignore MS traffic loads. In order to reduce computational complexity, a sequential optimization procedure was presented in which resource allocation is performed successively for each MS. For the channel-based model, numerical results show that when the interference level is low, joint optimiza-tion can provide a significant improvement in total bit rate over sequential optimization. 55 When the interference level is high, the improvement is smaller. It is shown that the order of allocation plays an important role for sequential optimization. For the load-based model, it is found that the total bit rate is quite sensitive to the order in which MS's are allocated resources. Numerical results further .show that sequential optimization with proper order-ing can be an attractive sub-optimal alternative to the more computationally complex joint optimization. 56 References 1] "Physical Layer Aspects of U T R A High Speed Downlink Packet Access," 3rd Generation Partnership Project, Technical Report 3G TR25.858, 2002. 2] H. Holma and A. Toskala, Eds., WCDMA for UMTS Radio Access for Third Generation Mobile Communications. John Wiley &; Sons, 2002. 3] Y . Zhao, "Theoretical Study of Link Adaptation Algorithms for Adaptive Modulation in Wireless Mobile Communication Systems," in IEEE Proc. of Universal Personal Com-munications, ICUPC'98, vol. 1, October 1998, pp. 587 - 591. 4] S. A. Jafar and A. Goldsmith, "Optimal Rate and Power Adaptation for Multirate CDMA," in Proc. of 52th IEEE Vehicular Technology Conference, Fall, vol. 3, Sept. 2000, pp. 994 -1000. [5] R. Kwan, P. Chong, and M . Rinne, "Analysis of the adaptive modulation and coding algorithm with the multicode transmission," in Proc. of 56th IEEE Vehicular Technology Conference VTC'02, vol. 4, September 2002, pp. 2007 - 2011. [6] , "The Effect of Code-Multiplexing on the High Speed Downlink Packet Access (HS-DPA) in a W C D M A Network," in Wireless Communication and Networking Conference WCNC, vol. 3, March 2003, pp. 1728 - 1732. [7] A. Bedekar, S. C. Borst, K. Ramanan, P. A. Whiting, and E. M . Yeh, "Downlink Schedul-ing in C D M A Data Network," Centrum Voor Wiskunde en Informatica, Probability, Networks, and Algorithms (PNA) PNA-R9910, Oct. 1999. [8] C. A. Floudas, Nonlinear and Mixed-Integer Optimization. Oxford University Press, Inc, 1995. [9] E. A. Eiselt and C.-L. Sandblom, Integer Programing and Network Models. Springer, 2000. 57 Chapter 3 Scheduling for the Downl ink in a C D M A Network w i t h Imperfect Channe l Es t imat ion 3.1 Introduction In third generation (3G) multimedia C D M A networks, a variety of techniques are used to meet the quality of service (QoS) requirements for different types of traffic. With adaptive modulation and coding (AMC) [1], performance is improved by adapting the employed modulation and coding scheme (MCS) to changing channel conditions. A mobile station (MS) with favorable channel condition can be assigned a higher order modulation with a higher channel coding rate whereas a lower order modulation with a lower channel coding rate is assigned when channel conditions are unfavorable. For example, A M C is used in the High Speed Downlink Packet Access (HSDPA) enhancement adopted for the 3GPP cellular standard [2]. Multicode transmission [3] is a technique which can be used to provide higher bit rates to MS's. It is well known that adapting the transmission parameters in a wireless system to chang-ing channel conditions can be beneficial. In the case of the fast power control [1], the trans-mission power is adjusted based on the channel fading. Thus, transmission over a good channel requires less power to maintain the target signal quality at the receiver. The process of changing transmission parameters to compensate for variations in channel condition is known as link adaptation. 1The material in this chapter is largely based on R. Kwan and C. Leung, "Scheduling for the Downlink in a C D M A Network with Imperfect Channel Estimation." Proc. of IEEE International Workshop on Adaptive Wireless Networks (AWIN), IEEE Global Telecommunication Conference (Globecom'04), Dallas, Texas, Dec. 2004. 58 Besides power control, A M C is also used for link adaptation [1, 2, 4]. A higher order modulation provides better spectral efficiency at the expense of a worse bit error rate (BER) performance. A lower channel coding rate provides greater error correction capability at the expense of information transmission rate. Thus, with a proper combination of the modulation order and channel coding rate, it is possible to design a set of MCS, from which an adaptive selection is made per transmission-time-interval (TTI) so that an improved spectral efficiency can be achieved under good channel conditions. At each selection of the MCS, the criterion is to keep the probability of erroneous decoding of a transmission block below a threshold value. Multicode transmission can be employed [1, 5] to increase the bit rate by splitting the bits of a transmission block to more than one channelization code at each TTI. In this scheme, a high rate data stream is divided into a number of lower rate data sub-streams, which are transmitted in parallel synchronous orthogonal multicode channels. An algorithm for jointly selecting the MCS and number of multicodes to maximize the assigned bit rate given power and code constraints has been proposed in [6] in the context of HSDPA. An analytical formulation for this problem is given in [7]. Since the selection of MCS and the number of multicodes is based on knowledge of the channel condition, an incorrect estimation of the channel condition can degrade the system throughput. In this chapter, an analytical formulation is provided for jointly selecting the MCS and number of multicodes to maximize the effective bit rate in the presence of signal-to-interference ratio (SIR) estimation errors. This is then used to study the impact of SIR estimation errors on the performance. The formulation is also extended to take into account the actual MS traffic load. 59 3.2 S y s t e m M o d e l Let the downlink received signal-to-interference ratio (SIR) of MS i be given by hiPi (3-1) 7* = Ii where Pi is the downlink power transmitted to MS i from the target base station BS A, hi is the path gain from BS A to MS i, and Ii is the total received interference for MS i. In addition, let Aitj be the required SIR for achieving the target error rate of Sij for MS i and MCS j when a single code is used. Assuming that multicode transmission is used, the number of multicodes is continuous, and all codes share the power equally, the number, n$, of codes that can be transmitted while achieving an error rate of C j j is given by where Nitrnax is the maximum number of multicodes that can be assigned to MS i and Aj. is the SIR per code for MS i and MCS j which achieves an error rate of eitj. The effective bit rate2 for MS i with MCS j given 7* would be (3.2) (3-3) where the basic bit rate ritj is given by W (3-5) 9 2It is also used interchangeably with the term 'throughput' in this thesis. 60 In (3.5), W is the chip rate, g is the spreading factor, is the code rate for MCS j, and Mj is the number of points in the modulation constellation for MCS j. In the model, it is assumed that {riyj < r i J + 1 , j = 1 , J - 1}, and {eitj(ji) < e i j + 1 ( 7 i ) , j = 1 , J — 1}, which are realistic in practical applications of adaptive modulation and coding. 3.3 O p t i m a l B i t Ra te A l l o c a t i o n w i t h A d a p t i v e M o d u l a t i o n and C o d i n g and M u l t i c o d e s Assume that tij(Xij) is a continuous, monotonically decreasing function of Xij, and ap-proaches zero as Xij —> oo. From (3.4), it can be seen that the choice of Xij (which depends on e$j) has a direct impact upon the effective bit rate Rij. Since eitj decreases monotonically with Xij, a smaller value of requires a higher value of Xij. The max-imum bit rate rijNiiTnax(l — ^ij(Xij)) can be achieved if 7 , > XijNiiTnax, but cannot be attained if 7 ; < XijNitinax. Increasing Xij results in a lower e^ j but a lower number, n*, of multicodes. This suggests that there exists a value of AJJ^ which maximizes Rij in the region 7 ; < XijNi<max. The following theorems provide optimality conditions in the region Theorem 3.1: The effective bit rate R\j is maximized at A'j*^ given by 6ij(x\jPt^) — A!J%(A!J4))-I = O^ ^(AJJVO. Proof: See Appendix B . l . Theorem 3.1 provides the conditions to be satisfied by A-J*\ However, it is possible that these conditions are also satisfied by other local extrema. By assuming that tij(x) takes the form of a sigmoid function, it can be shown that any Xij that satisfies the conditions in theorem 3.1 is a unique optimal solution. 61 Theorem 3.2: Assume that the error rate curve ti,j(x) can be modelled by a sigmoid func-tion. Then any SIR Xij that satisfies the conditions in Theorem 3.1 is a unique solution that maximizes the effective bit rate Rij. Proof: See Appendix B.2. Although the sigmoid function model in Theorem 3.2 is not exact, it is a very good approx-imation to the error curves in [8].. According to Theorem 3.2, the optimal value of A J ^ can be expressed in terms of the Lambert W function [9] as given by (B.31). If A j f } < Aij, the chosen SIR requirement per code must be at least Aitj in order to satisfy the QoS require-ment. In this case, using Theorem 3.3, we can conclude that the optimal value of Xitj is Aj j . Thus, in order to satisfy the QoS requirement, the optimal value, A* •, of the SIR per code is given by A*, = max(Al j t ) ,A i , j ) . (3.6) Theorem 3.3: Assuming that the error rate curve £ij(x) can be modelled by a sigmoid function, the effective bit rate R\j decreases monotonically with Ajj in the region [A - J^co) . Proof: See Appendix B.3. With the combination of A M C and multicodes, at a given 7*, the effective MS bit rate Ri(ji) is the maximum bit rate that can be provided among all MCS's. In other words, Hi( 7 i ) = max({^ i j-(7i),Vj = l , . . . ) J} ) , (3.7) j where Ri,j(ji) is the effective bit rate for MCS j at X*j. A rough plot of Ri^i) is shown in Fig. 3.1. 62 r. J V . i, / /, ma) r W /,3 /, max r JV i,2 i, max r.,JV. (min) .; v (min) • • • k=3 k=2 • i,2 Yi,2 yi,i (min) '/,3 ij (min) ri,J Figure 3.1: MS bit rate and ji relationship with MCS's. As ji increases from 0, an increasing number of multicodes can be utilized, resulting in an increase of Ri(ji). In this case, Ri,i(ji) = ma,x(Rij(ji), Vj = 1,... J), since the effective bit rate is lower for j > 1 due to poorer error performance. As ji reaches 7^1, the maximum number, NitTnax, of multicodes allowed for MS i is used and a further increase in ji will not allow a higher number of multicodes to be allocated. At this stage, the next higher order MCS still gives a lower effective bit rate due to the poorer error performance. As ji reaches jl™m\ MCS 2 is selected, and Ri{ji) = Ripili)- In a similar way, Ri{ji) increases with increasing ji until j = J and Nitmax multicodes are used. Given ji, the problem of evaluating Ri(ji) reduces to the determination of the set of thresholds {jij,Vj = 1,...J} a n d a ( 7 n ) , V j = l , . . . J} . Let jij be Kj = Kj Nhmax, Vj = 1, ..., J (3.8) 63 By definition, 7 } ™ ^ can be obtained by solving the equation relating the highest effective bit rate of the MCS j — 1 with the lowest effective bit rate of the MCS j. Thus, / -(min) \ Ni^maxTij—l I 1 ^ij —l(~TT ) J = V **i,max J ( ~ (min) \ l - e i j ( ^ — )J , \fj = 2,...J (3.9) - (min) = ( i - tiAKji) . Vj = 2,... J. (3.10) Assuming the difference between A ^ m ^ and A J ™ ^ is reasonably large, and since ^ > Kj-lNi>max, Vj = 2, . . , J, (3.11) the quantity eij-\(ji™%n^'/NitTriax) is negligibly small, and 7J™ l T ^ can be well approximated as ~(min) ^i,maxfi,j — l ,* 7i j 7 \~ i j j ^ l 1 - tiAKj)) Vj = 2,...,J. (3.12) Without the loss of generality, we set 7^™"' = 0 and il™™} = oo. The corresponding minimum number of multicodes for the jth MCS is then given by ~ (min) n£™> = Vj = l , . . . , J . (3.13) Let C^j (7i) and eg (7^) take the truth values of the conditions TJJ"1^ < 7i < 7 ^ and 7i,j < 7i < 7i,7+i' respectively. With the constraint on the number of multicodes, the optimal effective bit rate Ri(ji) is given by i?i(7i) = { rhjNi!max ( l - tijWjj) , if Cg>(Ti) 64 VJ = I , . . . , J . (3.14) 3.4 Effect o f E s t i m a t i o n E r r o r In reality, some error in estimating 7, is inevitable. Let 7; be the estimated value of 7*, and is given by Ii = 7i + e 7i, ( 3 - 1 5 ) where e 7 i is the estimation error for 7;. As a result of the estimation error, the number of multicodes and the MCS may be allocated sub-optimally. Let j' and n\ be the assigned MCS and the number of multicodes based on 7;, where n\ is given by n'i = min ^-,NUmax^j (3.16) Let C^,(ji) and cf-,(ji) take the truth values of the conditions 7-™"^ < 7i < Jij' and 7ij' < 7i < 7i™+i respectively. The sub-optimal effective bit rate P,(7j|7i) is given by Ri{ii\ii) = n,i<{i-e%A%)) if C $ ( 7 0 [ ^ ^ , m a x ( l - e ^ ( ^ ) ) if C g t o ) V / = 1,...,./, (3.17) if <$( 7 , ) V / = 1,...,J. (3.18) 65 It is convenient to express the estimated SIR 7* in terms of a multiplicative factor of the actual SIR 7*, i.e. 7i = 7 iU + /V)> ^ > - l (3-19) where /37i = e 7 i /7 i is typically a sample of some random variable. From (3.18) and (3.19), we can observe that as f3lt increases from 0, more multicodes would be allocated, but at the expense of a lower SIR per code. On the other hand, as j37i decreases from 0, the SIR per code improves, but at the expense of fewer allocated multicodes. From a practical point of view, the former typically results in a rapid decrease in bit rate due to the fact that an over-estimation of 7; generally results in a rapid increase in e^ -. In the latter case, the effect upon the bit rate due to a small improvement in tij is generally small compared to that of the reduced multicode allocation. In other words, while an under-estimation of 7; roughly translates in a reduction in bit rate due to under-allocation of multicodes or allocation of a lower order MCS, over-estimation of 7$ gives rise to the same effect due to the degradation in error performance (in the physical layer3). However, the impact upon bit rate due to under or over-estimation of ji is asymmetrical: while under-estimation has a roughly linear effect upon the bit rate, over-estimation usually has a much more detrimental impact due to the nonlinear nature of the physical layer error performance as a function of the channel condition.4 The above observation suggests that if 7; is intentionally assumed to be lowered by a conservative factor Aj than what is observed, the chance of over-estimation can be reduced. In this case, (3.19) is modified to 7i = 7 l ( l + / 3 7 i ) ( l - A , ) , / ? 7 4 > - l , O ^ A ^ l . (3.20) 3The term 'physical layer' is used to distinguish the error performance at the physical layer from that of the estimation error. 4For example, with turbo codes, the error performance generally improves very rapidly once the SIR exceeds a certain threshold [10]. 66 Since it would be more harmful to allow over-estimation than vice versa, the introduction of such conservative factor Aj is, on average, expected to provide gain in the presence of estimation errors. Note that in the region jij < 7J < 7j™"^ where the bit rate is code-limited, over-estimation would be less harmful, since more multicodes are not allowed to further reduce the SIR per code, and, hence, decreasing the chance of further transmission error. Using (3.20), (3.18) can be re-written as Riijilji) = i ^ A j , / ^ ) , (3.21) and the average effective bit rate given Aj is given by /oo _ i?j( 7j|Aj,/3 7 i)/B(/? 7 i)ri/3 7 i, (3.22) -oo where /s(/37i) is the probability density function (pdf) of £?7 i. 3.5 L o a d - B a s e d S c h e d u l i n g w i t h E s t i m a t i o n E r r o r In the case when the MS traffic is not back-logged, and the amount of data, Bi, in the buffer (i.e. the buffer content size) is known for each MS i, the code and power resources can be allocated more efficiently. Let A = Bi/(WTa) be the ratio of the buffer content size in bits to the number of bits that a full bandwidth W can carry over the scheduling period Ta. Thus, the required bit rate can be defined as Rreq = D{W. Furthermore, let Q \ t ) = {C{rk\ 1 < k < J + 1} be the set of conditions for MS i such that DiW falls into one 67 (r) of J + 1 bit rate regions as shown in Fig. 3.1, where Q f c is given by 'i,k ri,k-lNi<max(l - €i,k(K,k)) < DiW .max (1 - eiik(Xlk)), 1 < k < J, ri:jNitmax(l - eitJ{Kj)) < DiW> k = J + l. (3.23) where r^o = 0. The basic idea behind load-sensitive scheduling is to tailor the number of multicodes and power depending upon the bit rate region where the buffer content size Di resides. Thus, the required MS bit rate r|r^ and the corresponding SIR if are given by (r) if Cfl \<k<J, Ar) li (r). l-e<,fc(AJifc) ; r- ,/V- if CKn 'i,Jlyi,maxi 1 1 \* N. if -\j i vi,max, U 0i,J+l (3.24) (3.25) Ideally, when the multicode and power resources are unlimited, (3.24) is optimal given the buffer content size Bi. However, in reality, it is possible that Bi is too large or ii is too small to support il^ due to the undesirable channel condition. Thus, the allocation of resources should reflect not only the buffer content size Bi, but also the current SIR 7*. Let c\j\ii) and C-2- (ii) take the truth values of the conditions 7 - ™ ^ < 7* < %j and 7^ < 7 i < li™+i respectively. The resulting effective bit rate Rfb\li\li) is given by r | r ) ( l - e i j » ( 7 i A ^ / 7 | r ) ) ) , rij'x^- i l - tiAiiKrhi))» Ti jiNi<max (1 eiji(ii/Ni^max)), i f 7 { r ) < 7 « , Cg , i f 7 i r ) > 7 i , C $ ( 7 0 , i f 7 i ( r ) > 7 i , C$( 7 i ) , (2)/ 1 < k < J+ 1 1 < f < 13.26) 1 < f < J, 68 where f is the selected M C S when C\j\(%) or C ^ T * ) is true, and j" = min(fc, J) is the selected M C S when is true. The average effective bit rate given Aj is given by R?b\li\\) = (™ Rfh\il\Ai)Bli)fB(6li)d6li, (3.27) J —OO where Rfb\ii\Ai, B1%) is the effective bit rate as a function of 7* given the conservative factor Ai and the relative estimation error 31{. 3.6 N u m e r i c a l R e s u l t s Numerical results are now provided to show the impact of estimation errors upon the system performance. The estimation error B7i is assumed to have a truncated Gaussian distribution 1 e - / 3 y 2 o f if/5 > _ i where Cp is a normalizing constant, 5 is the Dirac delta function, and 0* is the standard devia-tion of the untruncated Gaussian distribution5. The simulations assume #=16, Niy7nax=5, and the MCS's consist of QPSK 1/2, QPSK 3/4, 16-QAM 1/2, and 16-QAM 3/4. The link-level results are taken from [8]. Also, let nR = 7^( 7 i |Aj,/? 7J/.Rj(7i) and TJR = Ri(ii\Ai)/Ri^i) be the effective bit rate ratio and the averaged effective bit rate ratio respectively, which quantify the relative degradation of the effective bit rate due to estimation errors. Figure 3.2 shows the averaged normalized effective bit rate Ri(ii\Ai)/W as a function of 7i with erf1 = 0.1 for various A -5 , where af^6 is the standard deviation of (3.28). As expected, when A i = 0 and in the presence of estimation errors, a significant degradation in bit rate can be observed compared to the case without estimation errors. However, by selecting an 5Note that the standard deviation of /s(/?7i) is slightly different from <r; due to the truncation. However, when <7j is small, the difference is negligible. 6See appendix B.4 for the relationship between cr-*' and cr,. 69 appropriate conservative factor Aj, the effect of estimation errors can be reduced, especially in the region 7 ^ < 7; < Figure 3.3 shows the normalized effective bit rate TJR as a function of the relative estima-tion error /37i with af = 0.1 and Aj = 0. The results clearly show the asymmetrical effect of the estimation error upon the effective bit rate. The bit rate generally decreases much more rapidly as /?7 i increases from 0 than as /3 7 i decreases from 0. The curve for 7; = 2 is flat because it falls in a flat region of the bit rate vs. % curve, i.e. in the range (71,3,7!™"^) as can be seen in Fig. 3.2. Figure 3.4 shows the averaged effective bit rate ratio TJR as a function of the conservative factor A; with af =0.1. The cases 7; = 0.2 and 2.5 fall within the sloped regions of the "no error, Aj = 0" curve in Fig. 3.1. In these cases, the system can only achieve about 70% of the estimation-error-free bit rate with no conservative factor, i.e. Aj = 0. However, by an appropriate selection of Aj, approximately equal to af, a significant increase in TJR can be obtained. The cases 7J = 1.8,3.2 and 4.5 lie in the flat regions of the "no error, Aj = 0" curve in Fig. 3.1. As a result, TJR is relatively less sensitive to the estimation error and a small value of Aj has little effect on the bit rate. Figures 3.5 and 3.6 show the averaged effective bit rate ratio ^ as a function of the standard deviation af with 7J = 2.5 (sloped region) and 1.8 (flat region) respectively. The results show that for 7J = 2.5, IJR decreases quite rapidly with af when Aj = 0. However, with an appropriate value of Aj, TJR can be made much less sensitive to estimation errors. For 7J = 1.8, 7}R does not vary much with small values of af. In the case of the load-based model, it is convenient to quantify performance degradation by comparing the effective bit rate to the requested bit rate. Let the averaged effective-to-requested bit rate ratio r)ff be Rf\'ji\Ai)/(DiW). Figure 3.7 shows rj^. as a function of af with Di = 0.85, Aj = 0 and four different values of 7J. It can be seen that when 7J is small, the effective bit rate cannot support the requested bit rate DiW, resulting in a low value of 77^ even when no error is present. It can be observed that even a small error can 70 cause a big decrease in nR ' when 7, lies in the sloped regions (i.e. 7$ = 0.25,1.25 and 2.5. Figure 3.8 shows the averaged effective-to-requested bit rate ratio 77 as a function of the conservative factor Aj with erf = 0.1, A = 0.85 and different values of 7*. The results show that generally a good choice of Aj can improve 77^. As a rule of thumb, a good choice of Aj is in the range af to 1.5af. Figure 3.9 shows the averaged effective-to-requested bit rate ratio 77jf^ as a function of the standard deviation af with 7* = 2.5, A = 0.85 for four different values of Aj . It can be seen that a good choice of Aj can greatly reduce the effect of channel estimation errors (lb) on rjR '. 3.7 C o n c l u s i o n s In this chapter, the problem of optimal scheduling for a single MS on the downlink of a W C D M A network was studied. Analytical expressions were derived for the optimal effective bit rate when adaptive modulation and coding and multicode transmission are employed. For link adaptation, the selection of the MCS and the number of multicodes is based on an estimation of the downlink SIR. It was shown that a small estimation error can result in a bad selection of MCS and number of multicodes leading to a significant degradation in the effective bit rate. It was shown that the impact of SIR estimation errors can be greatly reduced by using a conservative margin with the estimated SIR value. 71 72 0 0.05 0.1 0.15 0.2 0:25 0.3 0.35 0.4 0.45 0.5 Conservative factor A. i Figure 3.4: Averaged effective bit rate ratio WR as a function of the conservative factor A , with o f = 0.1. 1.2 S 0.9 0.8 0.6 0.51 - * - A ./a w = 0 = 0.5 _ ,_ A|/a[" = 3.0 X , . ~ ' y. = 2.5 ;l I I I I I 0 0.05 0.1 0.15 0.2 0.25 Standard deviation oj1' Figure 3.5: Averaged effective bit rate ratio TJR as a function of the standard deviation a] with H = 2.5. 73 0.1 Standard deviation ov 0.15 Figure 3.6: Averaged effective bit rate ratio 77^ as a function of the standard deviation af with 7i = 1-8. 11 o 2 0.9 o CO ~ 0.8 'n •o to 0.7 D = 0.85 fe— -e- y|= 1.25 . . . . y| = 2.5 yj = 3.5 Figure 3.7: Averaged effective-to-requested bit rate ratio as a function of the standard deviation af with Di = 0.85, Aj = 0 and different values of 7J. 74 Figure 3.8: Averaged effective-to-requested bit rate ratio as a function of the conservative factor Aj with cr® = 0.1, Di = 0.85 and different values of 7$. Figure 3.9: Averaged effective-to-requested bit rate ratio as a function of the standard deviation cr® with 7; = 2.5, Di = 0.85 and different values of Aj. 75 References [1] H. Holma and A. Toskala, Eds., WCDMA for UMTS Radio Access for Third Generation Mobile Communications. John Wiley & Sons, 2002. [2] "Physical Layer Aspects of U T R A High Speed Downlink Packet Access," 3rd Generation Partnership Project, Technical Report 3G TR25.858, 2002. [3] S. J. Lee, H. W. Lee, and D. K. Sung, "Capacities of Single-Code and Multicode DS-C D M A Systems Accommodating Multiclass Service," IEEE Trans, on Vehicular Tech-nology, vol. 48, no. 2, pp. 376 -384, March 1999. [4] Y . Zhao, "Theoretical Study of Link Adaptation Algorithms for Adaptive Modulation in Wireless Mobile Communication Systems," in IEEE Proc. of Universal Personal Communications, ICUPC'98, vol. 1, October 1998, pp. 587 - 591. [5] S. A. Jafar and A. Goldsmith, "Optimal Rate and Power Adaptation for Multirate CDMA," in Proc. of 52th IEEE Vehicular Technology Conference, Fall, vol. 3, Sept. 2000, pp. 994 -1000. [6] R. Kwan, P. Chong, and M . Rinne, "Analysis of the adaptive modulation and coding algorithm with the multicode transmission," in Proc. of 56th IEEE Vehicular Technology Conference VTC'02, vol. 4, September 2002, pp. 2007 - 2011. [7] R. Kwan and C. Leung, "Channel-Based Downlink Scheduling Schemes for C D M A Networks," in Proc. of IEEE Vehicular Technology Conference (VTC), Los Angeles, California, September 2004. [8] M . Dottling, J. Michel, and B. Raaf, "Hybrid ARQ and Adaptive Modulation and Coding Schemes for High Speed Downlink Packet Access," in Proc. of IEEE Interna-tional Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), September 2002. [9] R. M . Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, "On the Lambert W Function," Adv. Comput. Math., vol. 5, pp. 329 - 359, 1996. [10] C. Berrou, A. Glavieux, and P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1," in Proc. of IEEE International Conference on Communications (ICC), vol. 2, May 1993, pp. 1064 - 1070. 76 Chapter 4 Adap t ive M o d u l a t i o n and C o d i n g w i t h Mul t i codes over Nakagami Fading Channels 4.1 I n t r o d u c t i o n Third generation (3G) cellular networks allow a wide variety of traffic to be carried over the wireless channel. Radio resource allocation algorithms are needed which make efficient use of resources while at the same time satisfying the quality of service (QoS) requirements of each type of traffic. It is expected that downlink traffic will be especially important since most of the high speed internet access and broadcast services traffic is in the downlink direction. In order to support broadband packet data services, a high speed downlink packet access (HSDPA) channel has been incorporated in the 3GPP standard [1, 2]. Link adaptation refers to the process of changing transmission parameters to account for changes in channel conditions. Power control and adaptive modulation (AM) are two methods for implementing link adaptation [2]-[6]. In A M , the modulation scheme is changed according to the channel condition so as to improve the spectral efficiency. In [4], the impact of channel estimation delay on the bit error rate (BER) is analyzed for adaptive quadrature amplitude modulation (AQAM) over Nakagami fading channels. In [5], the design of an optimum A M scheme is studied for the flat Rayleigh fading channel when channel prediction is employed. The goal is to choose optimal thresholds for modulation selection using the second-order statistics of the channel prediction error. In [6], the impact of channel estimation errors on A M performance in flat fading is examined. The adaptation 1 The material in this chapter is largely based on R. Kwan and C. Leung, "Adaptive Modulation and Coding with Multicodes over Nakagami Fading Channels." Proc. of IEEE Wireless Communications and Networking Conference (WCNC'05), vol. 2, New Orleans, Louisiana, March, 2005. 77 schemes in [4, 5, 6], are based on uncoded quadrature amplitude modulation (QAM). The 3GPP HSDPA channel uses adaptive modulation and coding in which channel coding is applied on top of each modulation scheme to improve power efficiency [1] and multicode transmission is employed to increase bit rate [2]. The advantages of using multicodes are discussed in [7]. In [8], the problem of code and power allocation in the downlink of a C D M A network is studied. The modulation and coding schemes (MCS) and the number of multicodes are jointly optimized based on the given power and multicode constraints. Also, the effects of imperfect channel state estimation are considered. In contrast to the Q A M case, no known analytical expressions are available for the error rates of the MCS's used in HSDPA. In this chapter, these error rate curves are approxi-mated using sigmoid functions. Based on this error rate model, an analysis of the bit rate performance of A M C combined with multicodes over Nakagami fading channels is carried out. In Section 4.2, the bit rate model with A M C and multicode is described, followed by the performance analysis in Section 4.3. Numerical results are presented in Section 4.4 and the main findings are summarized in Section 4.5. 4.2 A d a p t i v e M o d u l a t i o n a n d C o d i n g w i t h M u l t i c o d e s Let the downlink received signal-to-noise ratio (SNR) for mobile station (MS) i, be 7i = hPilh (4.1) where hi is the path gain from the base station, BS A , to MS i, Pi is the power that BS A has allocated for the traffic channel to MS i, and It is the total received interference and noise power at MS i. Since we will only consider a single MS, the subscript i will henceforth be dropped. 78 With A M C and orthogonal multicodes, the optimal effective bit rate Rj(j) for MCS j for a given value of 7 is [8] R(l) = r ^ . ( 7 ) ( l - £ j ( A * ) ) , (4.2) where \*j is the required SNR for a single code with MCS j to meet a pre-defined error requirement £?(A*). For simplicity, it is assumed that the number, r i j (7 ) , of multicodes is continuous, i.e. can take on any real value, in which case the optimal value is given by [8] 7 ^ ( 7 ) = 7 / A * , l [ r n ) < 7 < 7i, 1 < 3 < J N„ ~ - ~ (min) t ^ • ^ r , 7 j < 7 < 7)+i , 1 < J < J, (4.3) where J is the number of available MCS's, and Nmax is the maximum number of multicodes that can be assigned to the MS. The basic bit rate rj in (4.2) is given by rj = —R^\og2Mj, 1 < j < J, (4.4) where W is the chip rate, R^ is the code rate for MCS j, Mj is the number of points in the modulation constellation for MCS j and g is the spreading factor. As shown in Fig. 4.1, r.N J max r.N '• 3 max. r„JV 2 max r.N 1 max + j=1 (rain) « ^ (min) « —y=2 ^—y=3-^ (min) ^ y Figure 4.1: Allocated MS bit rate as a function of 7 . the terms ^ j m m ) and 7, correspond to a set of decision thresholds which specify the optimal 79 MCS and number of multicodes for a given value of 7 . The decision thresholds ^ j m m ) a n d 7 j can be obtained as [8] 13 = A * i V m a x ; \<j<J (4.5) ~(min) y Tj-l N 0 < 7 < 7 (4 6) It might be noted that ^ r n m ) = 0 and 7 ^ ™ " ^ = 00. 4.3 P e r f o r m a n c e A n a l y s i s over N a k a g a m i F a d i n g C h a n n e l s In practice, the actual received SNR, 7 , may not be identical to the estimated version, 7 . Thus, instead of A*, the actual SNR per (multi)code, A ( 7 , 7 ) would be A ( 7 , 7 ) = ^ (4.7) A * 7 / 7 , l [ r n ) < 1 < % 1<J<J i/Nmax, % < 7 < jjTin)> 1<J<J-The probability density function (pdf) of the channel gain A for Nakagami-m fading is given by [9] = v ^ Q m a 2 m - 1 ^ ' (4-9) where Q, = E(A2) is the average power gain, m is the Nakagami fading parameter (m > 1/2), and T(.) is the gamma function. The pdf p r (7 ) .o f the received SNR T is given by 80 where T is the average received SNR. Let A and A be the actual and estimated channel gains. Assuming that these two channel gains are correlated with the same average power, their joint pdf pA A(a, a) is given by [10] _ 4(aa)" (m\ m+l X (2mJ~paa\ ( m(a2 + a 2 ) \ In (4.11), p is the correlation coefficient of A 2 and A 2 . Using (4.9) and (4.11), the conditional pdf of T given T can be obtained as [4] / \ (m-l)/2 pnrhl7) = ( ! ~ r ( ^ ) >< ( ( W ) T j e x p • <4-12> Due to the nature of the selected MCS's, it is difficult to obtain the corresponding error rates analytically [11]. Instead, we approximate them using sigmoid functions. Such an approximation is quite accurate, as depicted in Fig. 4.2, where the simulated frame error rates of the selected MCS's are obtained from the first transmission results in [11]. Let the error rate Sj(x) for MCS j be eAx) = ^ T T T — , a[j\ a(2j) > 0. (4.13) A ' l + a ^ e x p ^ V ) The effective bit rate, i?(7|-y), at 7 given 7 is given by R{l\l) = W 7 ) 0 ; ( A ( 7 , 7 ) ) (4-14) 81 where *i(A(7,7)) = and 4j)(7) = { l - e , ( A ( 7 , 7 ) ) a^exp(c^(7)7/7) l + a '^)exp(4i) (7)7/7) a^A*, if 7 f i n ) < 7 < 7,' [ a{23)i/Nmax, if 7j < 7 < 7J+1 (min) The average conditional bit rate, R(j), at a given 7, is given by (4.15) (4.16) (4.17a) (4.17b) ^(7) = JQ ^(7l7)Pr|f(7l7)^7- (4.18) The term <£j(A(7,7)) in (4.16) can be written as a power series as follows where = < ^ ( - l ) n ( a ^ e c " > t t ) 7 / i , ) - n , n=0 1/2, ^ ( _ l ) « - l ( a 0 ' ) E 4 J ' ) ( 7 ) 7 / 7 ) n ) L n=l if 7 > A j if 7 = A~j if 7 < Kj (4.19a) (4.19b) (4.19c) A"j = -i\na?/#\<y). (4.20) It can be seen that (4.19a) converges for 7 G (Aj,co), and diverges for 7 £ [0, Aj], whereas (4.19c) converges for 7 £ [0, Aj) and diverges for 7 € [Aj,co). Let (TIT) a n d R+(7\l) be the effective bit rates given 7 when the parameter 7 lies in the regions [0, Aj) and (A*j,oo) respectively. The resulting average conditional bit rates 82 R (7) and -R +(7) given 7 for the lower and upper regions are respectively given by rKj-e R-(j) = l imjf 3 £iT(7|7)Pr|f(7l7)d7 (4.21) /•oo i ? + ( 7 ) = l i m / i? +(7|7)Pr|f(7l7)d7 (4.22) For j — Kj, the conditional bit rate -R -(7) given 7 is given by R=(j) = J i m ^ 6 ^ ^ - ( 7 ^ ( 7 1 7 ) ^ 7 (4-23) 2 0, i f / t x l . (4.24) Note that Kj defined in (4.20) is generally different from 7, and (4.24) most likely vanishes even at p = 1. Finally, ^ (7) is given by i?( 7 ) = J R-( 7 ) + JR=(7) + J R + (7) . (4.25) 4.3.1 The case 7 > Kj Using (4.14) and (4.19a), the term Rfij) given in (4.22) can be expressed as roo R+(j) = lim / r ,-71,(7) x 00 ... ^ ( - i r ^ ^ W h / ^)" B Pr |f(7l7)d7 (4-26) 71=0 OO = ^ . ( 7 ) ^ ( - i r ( a ^ ) - " $ „ ( 7 ) (4.27) n=0 where $-1(7) is given by ' $ n ( 7 ) = l i m / 0 0 e - n c " ) ^ p r | f ( 7 | 7 ) r f 7 - (4-28) 83 Using the Generalized Marcum Q-function [9, 12], 1 f°° Qm(a,P) = ——[ / x m J m _ i ( a x ) -am 1 J/3 dx, exp or + a" (4.29) the term &n(j) can be expressed as * n (7) = lim 7717 0 J J ) 1 / p n c ^ ( 7 ) m 7 \ P l 4J)(7) J ^ r ( l - p ) c ^ ( 7 ) ' V (4.30) and the details of the derivation are given in the Appendix C. The terms ci\j) and ci\j) are given by 4%) n c i \ l ) m + \ 7 T(l-p)) m-j + f (1 - p^c^ij) (4.31) (4.32) Due to the rapid convergence of the series in (4.27), R^tf) can be accurately computed using a limited number, N+, of terms so that n=0 (4.33) 4.3.2 The case 7 < if. Using (4.14) and (4.19c), the term Rrtf) in (4.21) can be expressed as R ( 7 ) = l imj f TjUjici) x 00 ... X : ( - l ) " - 1 ( a ^ ' ) e c ( 1 J ) ^ ) > r | f ( 7 | 7 ) r f 7 71=1 (4.34) 84 = r jn i( 7)E(- 1) n" 1(ai , ' )r x n=l lim jf e ^ ' ^ ^ p r i f (7l7)^7 (4.35) Unfortunately, no closed-form solution was found for the integral in (4.35). Instead, we approximate 0j(A(7,7)) in (4.14) by a piece-wise constant function. Then, from (4.21), R~(j) can be approximated as L(/fi/«)-iJ £ - ( 7 ) ~ rjrijij) Yl <t>j(Xj(l>KJ-k5))x k=0 rKj-k5 / s Prif(7l7)t-7 L(*i/*--)J k=0 {Qm{a,(5k)-Qm{a,(5k+)) (4.36) (4.37) where a Pk 2m/ry ( W ) T 2m(iT j - (fc + 1)5) 2m{KL-k5) \] ( 1 - P ) f (4.38) (4.39) (4.40) Due to the nature of the sigmoid function defined in (4.16), and since Rj{j) is defined in the region 7 G [0,7C,), the weight of (4.37) lies mainly in the region near 7 = Kj, and (4.37) decreases rapidly as 7 decreases from Kj. Thus, (4.37) can be approximated using finite number of terms, N~, as N-R (7) ~ TjUjij) £ ^ ( 7 , Kj - k5)) x fc=0 (Qm(a,(3k)-Qm(a,p+)) (4.41) 85 The average effective bit rate2, R, is then given by R = / R{i)vt{l)dl (4.42) Jo where R(j) and Pf (7) are given by (4.25) and (4.10) respectively. 4.4 R e s u l t s a n d D i s c u s s i o n The performance analysis presented in the previous section of A M C with multicodes in a C D M A system over Nakagami fading channels can be used to provide some numerical results for'#(7) and R given in (4.25) and (4.42) respectively. These results are compared against the numerical results obtained by applying (4.14) and (4.16) directly to (4.18) in Fig. 4.3. In order to distinguish between the two set of results, the former will be referred to as approximate and the latter as exact. In Figs. 4.5 and 4.6, the numerical results are compared against simulations for numerical convenience. The parameter values which were used are listed in Table 4.1. The values of and are obtained using the first transmission error rates of the selected MCS's in [11]. For computational efficiency, the Marcum Q-function was approximated using the results in [12]. Fig. 4.3 shows the normalized average conditional bit rate R(j)/W for p = 0.001 and p = 0.3 as a function of the estimated SNR, 7, with m = 15 and f = 2.5. It can be seen that R(j)/W varies a lot with 7. Due to the rapid increase (from nearly 0 to nearly 1) in the error rate curve for MCS j as a certain SNR threshold 7} is crossed, a high penalty in bit rate is incurred if the actual SNR, 7, is lower than the estimated value, 7. When 7 < f, i?(7) does not always increase with p. This somewhat surprising result is due to the fact that when 7 < T, the probability that T > 7 is higher when p is small. On the other hand, when 7 exceeds T, the probability that T > 7 is higher when p is larger. In the region 3 < 7 < 4.5, where the bit rate is limited by the maximum number of multicodes, Nmax, an increase in 2 I t is also used interchangeably wi th the term 'average throughput ' in this thesis. 86 7 implies an increase in T when p — 0.3. As a result, R(j) increases due to the increased value of A(7,7). It can be observed that R(j) decreases to almost zero when 7 > 4.7. The reason is because the actual channel SNR is being significantly over-estimated. Fig. 4.4 shows the conditional pdf, p(7|7), of the actual SNR, 7, given the estimated SNR, 7, for T = 2.5, m = 5, and (top) p = 0.001, (bottom) p = 0.5. This figure illustrates that when p is small (top), the actual SNR, 7, distribution is more or less independent of the estimated SNR, 7. On the other hand, when p is large (bottom), the change in the distribution of T with 7 is evident. The figure also shows that when 7 < f, the probability that T > 7 is higher for p = 0.001 than for p — 0.5. Fig. 4.5 shows the normalized average bit rate R/W as a function of the average SNR, f, for p = 0.001 and p = 0.3 with m = 15. The figure indicates that R/W may not increase monotonically with f when the channel estimation error is large. It can also be seen that the average bit rate drops severely as p decreases from 1 to 0.3. A decrease in p from 0.3 to 0.001 results in only a slight degradation in average bit rate. Fig. 4.6 shows the normalized average bit rate R/W as a function of the channel cor-relation p, when m = 35, and f = 2.5. Note that when p approaches 1, the approximated results become numerically unstable. In such cases, only simulation results are shown. It can be seen that p has to be close to 1 for the degradation on average bit rate to be small. 4.5 C o n c l u s i o n s In this chapter, the average bit rate performance of A M C with multicodes is analyzed for a C D M A system experiencing Nakagami fading and channel estimation errors. Efficiently computable approximations are obtained and shown to be fairly accurate. Numerical results show that significant performance degradations can occur in the presence of fading when the estimated channel state is erroneous. 87 Parameter Value MCS QPSK 1/2, 16-QAM 1/2, QPSK 3/4, 16-QAM 3/4 Channel Coding Turbo Code Spreading Factor (g) 16 N 10 N+ 8 N~ 15 5 0.001 Table 4.1: List of parameter values. SNR Figure 4.2: Frame error rate as a function of SNR for 4 MCS's. 88 2 1.2 2 2.6 3 Estimated SNR Figure 4.3: Normalized average conditional bit rate R^/W as a function of the estimated SNR 7 , with m = 15, and f = 2.5, at p = 0.001 and p = 0.3. UJ 0.2 = 0.001 Estimated y =0.5 • Estimated y =2.5 - Estimated y =5 1 ^ — I 1 ) 1 2 3 4 Actual Y 5 6 7 £ ! 'p = 0.5 i — Estimated Y =0.5 ••• Estimated Y =2.5 Estimated Y =5 / ; \ ! -3 1 2 3 4 5 6 7 £ Actual Y Figure 4.4: Conditional pdf p (7 |7 ) of the actual SNR, T, given the estimated SNR, 7 , with T 5, and (top) p = 0.001, (bottom) p = 0.5. 2.5 m 89 • S;:::::.,:.< No estimation error, p=1 - G - Approx., p=0.001 - * - Simulation, p=0.001 O Approx., p=0.3 Simulation, p=0.3 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Average channel SNR Figure 4.5: Normalized average bit rate R/W as a function of the average channel SNR, T, with p = 0.001 and p — 0.3 when m = 15. 1 1 1 1 1 1 1 1 No estimation error,p=1 - e - Approx. —*— Exact 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Correlation coefficient p Figure 4.6: Normalized average bit rate R/W as a function of the correlation coefficient p, with m = 35, and T = 2.5. 90 References [1] "Physical Layer Aspects of U T R A High Speed Downlink Packet Access," 3rd Generation Partnership Project, Technical Report 3G TR25.858, 2002. [2] H. Holma and A. Toskala, Eds., WCDMA for UMTS Radio Access for Third Generation Mobile Communications. John Wiley &; Sons, 2002. [3] N . C. Ericsson, "Adaptive Modulation and Scheduling for Fading Channels," in Proc. of IEEE Global Telecommunications Conference, Globecom'99, vol. 5, December 1999, pp. 2668-2672. [4] S. A. Jafar and A. Goldsmith, "Adaptive Multicode C D M A for Uplink Throughput Maximization," in Proc. of IEEE Vehicular Technology Conference, Spring, vol. 1, May 2001, pp. 6-9. [5] S. Falahati, "Adaptive Modulation systems for Predicted Wireless Channels," IEEE Transactions on Communications, vol. 52, no. 2, pp. 307 - 316, Feb. 2004. [6] J. F. Paris, M . C. Aguayo-Torres, and J. T. Entrambasaguas, "Impact of Channel Esti-mation Error on Adaptive Modulation Performance in Flat Fading," IEEE Transactions on Communications, vol. 52, no. 5, pp. 716 - 720, May 2004. [7] S. J. Lee, H. W. Lee, and D. K. Sung, "Capacities of Single-Code and Multicode DS-C D M A Systems Accommodating Multiclass Service," IEEE Trans, on Vehicular Tech-nology, vol. 48, no. 2, pp. 376 -384, March 1999. [8] R. Kwan and C. Leung, "Scheduling for the Downlink in a C D M A Network with Im-perfect Channel Estimation," in Proc. of IEEE Global Telecommunications Conference - Adaptive Wireless Network Workshop, Dallas, Texas, December 2004, pp. 469-476. [9] J. G. Proakis, Digital Communications, 4th ed. McGraw-Hill, 2001. [10] M . Nakagami, "The m-Distribution: A General Formula of Intensity Distribution of Rapid Fading," in Statistical Methods in Radio Wave Propagation. Oxford, U.K.: Pergamon Press, 1960, pp. 3-36. [11] M . Dottling, J. Michel, and B. Raaf, "Hybrid ARQ and Adaptive Modulation and Coding Schemes for High Speed Downlink Packet Access," in Proc. of IEEE Interna-tional Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), September 2002. [12] G. E. Corazza and G. Ferrari, "New Bounds for the Marcum Q-Function," IEEE Trans-actions on Information Theory, vol. 48, no. 11, pp. 3003 - 3008, Nov. 2002. 91 Chapter 5 Performance of a C D M A system employing A M C in the Presence of Channe l Es t imat ion Errors 5.1 I n t r o d u c t i o n Adaptive Modulation and Coding (AMC) has been adopted in the 3GPP standard in order to improve spectral efficiency [1]. In order to increase the granularity of the adaptation and to provide higher bit rates, multicode transmission [2] is employed. Multicode transmission increases the bit rate by dividing a high rate data stream into a number of lower rate sub-streams. These sub-streams are transmitted in parallel synchronous multicode channels so that inter-stream interference is avoided in the absence of multipath. On the downlink to a target mobile station M S A , the base station (BS) typically acquires the channel state information (CSI) from M S A via an uplink feedback channel. Based on the newly acquired CSI, the BS assigns an appropriate modulation and coding scheme (MCS) and number of multicodes to M S A for use in the next scheduling period. Since the use of A M C requires knowledge of the channel state, it is important to assess the performance degradation which would result from inaccuracies in estimating the channel state. This chapter examines the performance of using (1) a simple averaging filter (2) a hidden Markov model (HMM) based filter in a C D M A system employing A M C and multicodes. An H M M formulation of the system is presented in Section 5.2. The performance evaluation measures are discussed in Section 5.4. Some numerical results are presented in Section 5.5. l rThe material in this chapter is largely based on R. Kwan and C. Leung, "An H M M Approach to Adaptive Modulation and Coding with Multicodes for Fading Channels." Proc. of IEEE Canadian Conference on Electrical and Computer Engineering (CCECE'05), Saskatoon, Saskatchewan, May, 2005. 92 5.2 H M M F o r m u l a t i o n The assigned bit rate for any given scheduling period can take on one of a finite set of values, depending on the MCS and the number of multicodes which are selected. We choose to associate a channel state with each possible value of the assigned bit rate. The channel is then modelled as a finite state Markov Chain (FSMC) [3]. Since the true channel state is not available at the BS, a H M M formulation is appropriate [4]. It is shown in [5] that the average throughput2 for a C D M A system with A M C and multicodes can be written as J ( Nmax-l ^ R * E <h(J)+ E M3,k) (5.1) where M,k) = rjk(l-e0)[Fr((k + l)\J)-Fr(k\j)] (5.2) MJ) =rJNmax(l-e0)[Fr(^T})-Fr(lj)] (5-3) and Fr(j) is the cumulative distribution function (cdf) of the signal-to-noise ratio (SNR), T. The terms j{min^ and jj correspond to a set of decision thresholds which specify the MCS and number of multicodes for the near-optimal throughput for a given value of 7 [5], and e0 denotes the maximum tolerable frame error rate (FER). The basic bit rate, rj, for MCS j is given by • r5 = jR^\og2Mh l<j< J, (5.4) where W is the chip rate, g is the spreading factor, R^ is the code rate for MCS j and Mj is the number of points in the modulation constellation for MCS j, Nmax is the maximum 2 I t is used interchangeably wi th the term 'average effective bit rate' in this thesis. 93 number of multicodes that can be assigned to an MS, and Aj is the minimum required SNR per code for MCS j to achieve an F E R of £Q. This allows us to determine a near-optimal mapping from a given value of 7 to an assigned bit rate, based on [5], as follows. Let C be the set of possible assigned bit rates such that C = 0 , if 0 < 7 < Ai rjkj , if kjXj < 7 < (kj + l)Aj • (5.5) A T T - ^ - ~(min) TjNmax , if 7 j < 7 < 7j+i where [jj^/Xjj < kj < Nmax - 1. For notational convenience, let the set C be expressed as C = {CUC2,...,CN} (5.6) where C i < C 2 < • • • < CN, and N is the number of possible assigned bit rates. For any value of 7 which maps to an assigned bit rate of Cj, we say that the channel is in state i. The throughput R in (5.1) can then be written as R « ( l - e o ) f ; C i p ( z ) ( 5- 7) i=i where p(i) is the probability that the channel is in state i. Let xk G {1,2 , . . . , ./V} denote the channel state at time k. Also, let Ukii) = P{Xk = i) be the probability that the channel is in state i at time k, and 7rfc = [^(1),... ,7Tk(N)]. For small values of the normalized Doppler rate (defined as the product of the Doppler rate of the channel and the scheduling period), the sequence of channel states can be modelled as a first order Markov process. Then, the probability vector at time k + 1 is given by 2Efc+i = TIfeA (5.8) 94 where A = {a^}, i,j = 1,..., N is the state transition probability matrix, and aitj is the probability that Xk = j given that Xk-i = i. We model the observed channel state as • yk = xk + vk (5.9) where vk represents the observation noise and is the outcome of an independent random variable (rv) V with pdf fv(v). Denote the conditional pdf of Yk by h(yk) = fYk(yk\xk = i). (5.10) We are interested in minimizing the variance of the state estimate, i.e. E[(Xk — Xk)2], where Xk is the estimated state and Xk is the actual state. Given a sequence of observations y^ = [yi, y2, • • •, yk], up to time k, the minimum variance state estimate is given by [6] xk = E[Xk\y}% (5.11) Let the forward probability be ak(j) = P{Xk = j,y}k^). From (5.11), the optimal filter is given by * = f l ^ , (5-12) where ak(j) can be computed recursively as [6] N ak{j) = bj(yk)Y^ai,jak-\(i) (5.13) i=i with a\(m) = bm(y\)P(X\ = m), m = 1,..., N as the initial distribution. 95 5.3 T r a n s i t i o n P r o b a b i l i t i e s E s t i m a t i o n In section 5.2, the transition probabilities {a^} are assumed to be known. In practice, these probabilities can .be estimated using the expectation-maximization (EM) algorithm. The idea behind the E M algorithm is as follows. Let XJ^ — [X\,X2, • • •, XK], where K is the number of observation samples. Also, let 9 and be the true parameters and the initial estimate of the parameters respectively. Using Q(°\ the E M algorithm iteratively generates a sequence of estimates {9®, I = 1,2,... ,L} based on the following steps: • Expectation: To obtain the auxiliary3 likelihood Q{0\6®) = E [in ( p (XW yW|c?)) \y{K\9^} ; (5.14) • Maximization: To maximize the auxiliary likelihood such that 0 ( ' + 1 ) = maxQ(0|0 ( J )). (5.15) If bj(yk) is known, the estimated transition probabilities {ajjj} after I iterations can be obtained using standard constrained optimization techniques, and are given by [6] Efc=2afc-iWAfc-iW where = 6i(yfc)EtfM'li(0 (5-17) i=l -The auxi l iary l ikelihood Q(6\6^) is used instead of the true l ikelihood L(6,K) = p{y^K^\9) because the former is easier to optimize, and maximizing the former has the same effect as maximizing the latter [6]. 96 and 3k\j) is known as the backward probability, with P^+iU) — 1-(') 5.4 P e r f o r m a n c e M e a s u r e s In general, the estimated state xk in (5.12) takes on continuous values. However, xk should take on one of the allowed discrete values as described earlier. Thus, xk can be modified according to the following mapping: N , if xk > 2JV-1 1 , if x f c < § ,N- 1. (5.19) As discussed in [7], the effect of estimation error is asymmetrical. Over-estimation typically gives rise to a worse throughput degradation than under-estimation. Thus, the instantaneous throughput Rk(xk) can be approximated as Rk(ik) (1 - e0)Ci , iixk>xk = i 0 , if xk < xk (5.20) The average throughput is then given by 1 R = J i m TT2ZRk(xk) (5.21) Let Rf be the average throughput for the case when no filtering is performed, and is given by (5.21) except that the instantaneous throughput is modified to be Rk(yk), where yk can be obtained from (5.19), with xk and xk replaced by yk and yk respectively. The average 97 improvement factor 77/ is given by Vf = ( ^ = = ^ ) x l 0 0 (5.22) where Ms is the total number of observation instances. 5.5 N u m e r i c a l R e s u l t s The MCS set consists of turbo coded QPSK and 16-QAM with code rates of 1/2 or 3/4. A maximum of 2 multicodes can be assigned to each user; the spreading factor is 16 as specified in [8] and a target frame error rate of 1% is assumed. The values of j{mm^ and are obtained using the first transmission error rates of the selected MCS's in [9]. The MCS and number of multicodes assignment is performed at the BS once every scheduling period, during which the channel is assumed to be constant. The signal amplitude is assumed to follow a Rayleigh fading distribution and the average signal SNR is normalized to unity. For simplicity, the observation noise V ~ N(0,av) is assumed. The estimate of noise variance, cry can be computed as [6] The number of iterations, L , for the E M algorithm is set to 5. Using a higher value for L resulted in little change in the normalized throughput. For the results presented in this section, the 95% confident interval lies within 3% of the values shown. Fig. 5.1 shows the improvement factor, 77/, as a function of the observation noise standard deviation for the normalized doppler frequencies faT = 0.005 and f^T = 0.025 respectively. For comparisons, the improvement for a system employing a linear averaging filter (LAF) with a window size Z is also shown. The results show that the improvements of both systems over the unfiltered system increase with the observation noise. In all cases, the performance 98 of the H M M system is always superior to that of the L A F system. The results also suggest that both systems provide greater improvement when the channel changes more slowly. However, it can be seen that the performance of a L A F system is very sensitive to the choice of zT, i.e. a reasonably good value of Z for a given value of faT can be in fact unacceptable for another value of f^T. As shown in Fig. 5.2, an appropriate value of Z has to be chosen for a L A F system to achieve a reasonable improvement 77/ . However, such value of Z is not always available in practice. 5.6 C o n c l u s i o n s In this chapter, the impact of channel state estimation errors in a system employing A M C and multicodes was studied. An H M M filter was employed to alleviate the effects of estimation errors. It was shown that H M M filtering can significantly reduce the state estimation error, and improve the system throughput. HMM - - © - Linear averaging filter, Z = 2 - B - Linear averaging filter, Z = 5 — e •— W ~ " i fj= 0:005 • i 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 Observation noise standard deviation fj= 0.025 i ____ ; ; " j * ; : " : : L T j r . " . - - © - — ^ - * - HMM —a- Linear averaging filter, Z = 2 . -a- Linear averaging filter, Z = 5 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 Observation noise standard deviation Figure 5.1: Improvement factor, 77/, as a function of the observation noise standard deviation. 99 8 E i i i i * * 1 / T = 0 . 0 0 5 k - * - HMM - a - Linear averaging filter 2 3 4 5 6 7 Window size, Z (in samples) 2.5 3 3.5 Window size, Z (in samples) Figure 5.2: Improvement factor, rjj, as a function of the LAF window size, Z, with cry = 0.6. 100 References [1] H. Holma and A. Toskala, Eds., WCDMA for UMTS Radio Access for Third Generation • Mobile Communications. John Wiley & Sons, 2002. [2] S. J. Lee, H. W. Lee, and D. K. Sung, "Capacities of Single-Code and Multicode DS-C D M A Systems Accommodating Multiclass Service," IEEE Trans, on Vehicular Tech-nology, vol. 48, no. 2, pp. 376 -384, March 1999. [3] C.-D. Iskander and P. T. Mathiopoulos, "Fast Simulation of Diversity Nakagami Fad-ing Channels Using Finite-State Markov Models," IEEE Transactions on Broadcasting, vol. 49, no. 3, pp. 269 - 277, September 2003. [4] R. J. Elliott, L. Aggoun, and J. B. Moore, Hidden Markov Models, Estimation and Control. New York: Springer-Verlag, 1995. [5] R. Kwan and C. Leung, "Order Statistics for Non-Identically Distributed Nakagami Fad-ing Channels with An Application," in Proc. of IEEE Vehicular Technology Conference (VTC), September 2005. [6] T. K. Moon and W. C. Stirling, Mathematical Methods and Algorithms for Signal Process-ing. New Jersey: Prentice Hall, 2000. [7] R. Kwan and C. Leung, "Scheduling for the Downlink in a C D M A Network with Im-perfect Channel Estimation," in Proc. of IEEE Global Telecommunications Conference -Adaptive Wireless Network Workshop, Dallas, Texas, December 2004, pp. 469-476. [8] "Physical Layer Aspects of U T R A High Speed Downlink Packet Access," 3rd Generation Partnership Project, Technical Report 3G TR25.858, 2002. [9] M . Dottling, J. Michel, and B. Raaf, "Hybrid ARQ and Adaptive Modulation and Coding Schemes for High Speed Downlink Packet Access," in Proc. of IEEE International Sym-posium on Personal, Indoor and Mobile Radio Communications (PIMRC), September 2002. 101 Chapter 6 G a m m a Varia te Ra t io D i s t r i bu t ion w i t h App l i ca t i on to C D M A Performance Analys i s 6.1 I n t r o d u c t i o n In wireless communication systems, interference is usually considered undesirable since it corrupts the desired signal and generally lowers the probability of correct reception. On the downlink of a cellular network employing Code Division Multiple Access (CDMA) the interference experienced by a mobile station (MS) is dominated by the signal transmitted by the same cell base station (BS) and signals from BS's in neighboring cells [1]. Typically, both the desired and interfering signals undergo multipath fading [2]. In the performance analyses of C D M A systems, the total interference often modelled as Gaussian noise with a time invariant power. While this Gaussian approximation facilitates the analysis, it may yield inaccurate results [3]. The reason is that the Gaussian approximation, which is based on the central limit theorem, relies on statistical independence among all the signals. However, this assumption may not be valid, especially on the downlink of a C D M A system. In this chapter, a model for the received signal-to-interference ratio (SIR) on the downlink of a C D M A network is studied. Statistical characterizations of the SIR are derived. To illustrate their usefulness, the results are applied to assess the performance of a C D M A system which employs adaptive modulation and coding (AMC). 1 The material in this chapter is largely based on R. Kwan and C. Leung, "Gamma Variate Ratio Distri-bution with Application to C D M A Performance Analysis." Proc. of IEEE Sarnoff Symposium on Advances in Wired and Wireless Communication, Princeton, New Jersey, April, 2005. 102 6.2 S y s t e m M o d e l a n d S I R S t a t i s t i c s Let the downlink received SIR at the target MS be r = (hGP (6.1) ahG(l - C)P + a'h'G'P + h"G"I where P is the total power transmitted by the home cell BS, BS A , £ is the fraction of P allocated to target MS, and I is the power transmitted by the dominant interfering BS, BS B. The terms h and h" are the long-term path gains from BS A to the MS and from BS B to the MS respectively. The terms G and G" represent the corresponding short-term path gains. The terms h' and G' correspond to the long-term and short-term path gains of the second strongest multipath component due to BS A 's transmission2. The term a G [0,1] is used to model the effect of intra-cell interference due to the possible use of non-orthogonal codes, and a G [0,1] is used to model the effect of non-orthogonality due to multipath interference. In the case when orthogonal codes are used, a = 0. The numerator in (6.1) is the power of the desired signal in the strongest multipath; the first term in the denominator is the interference power in the strongest multipath due to multicode non-orthogonality; the second term is the interference power due to the second strongest multipath, and the third term is interference due to BS B. In this chapter, we study the effects of short-term fading3 and assume that the long-term path gains are constant [4]. Also, we assume that the relative delay between the first and second strongest multipath components are much smaller than the channel coherence time, so that G ~ G'. Then (6.1) reduces to 2We assume that the interfering effect due to the weaker multipath components are negligible. 3Note that since G, G', and G" denote the random variables corresponding to the respective short-term path gains, the term T is also a random variable, with the corresponding outcome denoted by 7. r = (6.2) a,\X\ + (I2X2 103 where ai = (ah(l-() + a h')/((h), a2 = h"/((h), X\ = GP, and X2 = G"I. Assuming that the short-term signal amplitude follows a Nakagami-m distribution [2], the random variables (rv) X\ and X2 have gamma distributions G(Xi,a.i), given by <r. T r & ~ w * * > » . « - ' . 2 (") where Xi is the average value of Xi: and a* > 0 is a shaping parameter, and T(.) is the Gamma function. The pdf and mth moment of the rv T in (6.2) are derived in Theorems 2.1 and 2.2 respectively. Statistical characteristics of T have been studied for the special cases of a\ = 0 and ai = a2 in [5, 6]. It might be noted that the results can be applied to the case involving multiple interfering BS's since the pdf of the sum of gamma rv's can be well approximated by another gamma pdf [7]. Theorem 2.1: Let T = Xi/(a\X\ + a2X2), where a\ and a2 are positive constants, and Xi and X2 are gamma distributed with pdf Q(Xx,ai) and Q(X2,a2) respectively. Then the pdf of the rv F is given by /r(7) = K l 2 l ^ - \ \ - a n r - V i + c 2 7 ) ^ M ) , 0 < 7 < 1/ai (6.4) where C = ^ - (6.6) X2a2 X\ X2a2 c2 = - o r - ^ r - , (6-7) 104 and .6(0:1,0:2) is the beta integral, which is defined as [8] Proof: The joint pdf of two independent gamma rv's, X\ and X2, with pdf given in (6.3) is f « M - ( - ) " ( - ) - ( i ^ ) ^ - . - ? - ^ ( - ( ^ + ^ ) > l 9 ) Defining r = YX2 Y ( 6 . 1 0 ) a - A - + a 2 A 2 5 = a 1 X 1 + a 2 X 2 (6.11) we have Xi = TS (6.12) X2 = — S ( l - a - r ) . (6.13) &2 From (6.10), it can be seen that as the term a2X2 approaches zero, T attains its maximum value of 1/a-. Using a standard result on the functional transformation of rv's [9], the joint pdf, /r,s(7, s), of T and S is given by / r , s (7 , s ) = (6.14) x i = 7 S , X 2 = - ^ s ( l - a i 7 ) 105 where J (^^r) is the Jacobian of the transformation from (xx,x2) to (7, s), i.e. J x\,x2 7,s dx\ df 8x2 9x1 3s 7 s a-2 (6.15) (6.16) (6.17) We then have X 1 a-2 02_\^ a 2 / ,OLX a 2 ' . 6 X P V ^X~XJS X~2~a~2 ~ ai \ a i ( a 2 \ a - X T (a 1 ) r (a 2 ) / «i 1 ^ Q.2 a - ^ s j X 2 a 2 X2 a-2 a2_y 2 ( XJ \X2J \T{ai)r(a2)J \a2 s d + a - - l 7 a i - l ( 1 _ a i 7 ) a 2 - l e - s ( c 1 + C 2 7 ) — X (6.18) (6.19) (6.20) Using (6.20) and the identity [8] POO 1 J x^e'^dx = — 1 » , 11 > 0, zy > 0, (6.21) the pdf of T can be written as poo / r (7) = / fr,s(l,s)ds Jo (6.22) 106 = J r r 1 2 7 Q l " 1 ( l - a i 7 ) a 2 " 1 ( c 1 + c 2 7 ) - ( a i + Q 2 ) , (6.23) where Kx2, C - , and c 2 are given by (6.5), (6.6), and (6.7) respectively. • In the special case of ctxjXx = a2/X2, and ax = a2 = 1, the pdf reduces to the standard beta distribution [5], i.e. / r (7 ) = R L 1\ . 0 < 7 < 1 . (6-24) S (a i , a 2 ) On the other hand, if ax/Xx = a2/X2, a- = 0, and a 2 = 1, the pdf reduces to a beta prime distribution [5] * W = b p T T T ( 6 ' 2 5 ) The case ct\jXx ^ a2/X2, and ax = a2 = 1 is treated in [6]. We now derive the mth moment of T. Theorem 2.2: The mth moment of T is given by E[Tm] = K12c7{ai+a2)a7{ai+m)B(a2,a1 + m)x 2 F i ( a i + ct2, ai + m; a 2 + ct\ + m;-—aT/1), (6.26) where 2-P1O - s hypergeometric function [8], given by 2Fx(a,b-c\t) = — — - — - f1 xb-v(l-x)c-b-1(l-xt)-adx, Re c > Re 6 > 0.(6.27) . D ( O , C — 0) Jo Proof: Expressing the density function / r (7) in the form /r(7) = J r r i 2 a r - 1 c 2 - ( a i + a 2 ) 7 a i - 1 ( a r 1 - 7 r - 1 ( ^ + 7) , (6.28) 107 we can write E[Fm] = jT Tfv{l)dl = KnaT-lc-2{ai+a2) x f 1 1 7 Q 1 + r o - 1 ( a 1 - 1 - 7 ) a 2 _ 1 (- + 7 -(0:1+0:2) (6.29) (6.30) Using the identity [8], / " x " " 1 (x + a)\u - xY-ldx = Jo a^+^B(/i,iy)2F1(-X,u;iil/--u/a), v > 0, \i > 0 (6.31) (6.30) can be expressed as (6.26). The central moments can be evaluated using the following result. Theorem 2.3: The mth central moment of F is given by k=0 ( \ m \ k 1 C2 m-k -{ai+012) (-Mr) m - f c c: a 1 " ( Q 1 + f c ) 5 ( a 2 , a 1 + fc) x 2^(0:1 + a2, ai + k; a2 + ax + /c; ——ax 1), (6.32) where fir = E\T]. Proof: Using (6.31), (6.28) and the binomial expansion, we can write E[(F-nTr] = r ( 7 - M r ) m / r ( 7 ) d 7 Jo = #12 E fc=0 vfc / (-/x r)m- f cc2-•m-k- (0:1+0:2) X (6.33) 108 ra\ 1 , / r-i \—(01+02) a"2~Jo 7 1(ar1-7r_1(^ + 7 j ^7 (6.34) which can be put in the form of (6.32). • An expression for the moment generating function (MGF) of T is derived in Theorem 2.4. Theorem 2.4: The M G F of T is given by fc=0 I C l 2F\(ax + a2, ax + k; a2 + ax + k; —axlc2/cx) (6.35) Proof: Using (6.28) and expanding the exponential term as an infinite series, we have /OO / r ( 7 ) e ^ 7 (6.36) -00 = KX2aT~lc2 { a i + a 2 ) r 7 Q l " V i ~ 1 - 7 r _ 1 x • Jo R, \ -(01+02) OO ( c<y)k 7 + 7 ) £^Uy (6.37) = K l 2 a ? - l c 2 { M ) Y , T \ 7a i + f c _ 1(«r1-7)a 2-1x fc=o fc- J o £ l + 7 V ( ° ' + ° " l ( ; 7 (6.38) c 2 / Using (6.31), the last expression can be reduced to (6.35). The mth derivative of $r(s) is given by 00 Jk—m) ax{ax+k)2Fx{ax + a 2 , c*i + k; a2 + ax + k; -axlc2/cx) (6.39) 109 and the mth moment of F can also be obtained as E[Fm] = 4 m ) ( 0 ) (6.40) An expression for the cumulative distribution function (cdf) of F is given by Theorem 2.5. Theorem 2.5: If a2 is an integer, the cdf of F can be expressed as Fr(l) = WQ 1 + Q 2 ) E (-1) OC2 — 1 ( a 2 - l \ 9 = 0 a n V Q J x c 2 2 i ? i ( Q ! i + a2, a1+q;l + a1 + q; 7). 1^ (6.41) Proof: Using the binomial expansion (a + xT = E fc=o / \ n xkan'k, (6.42) the term (1 - a^)012 1 in (6.4) can be expressed as = a f 2 _ 1 ( 6 i - 7 ) a 2 - 1 02 —1 = a ? " 1 E (-1) 9 9 = 0 a 2 — 1 V 9 J 7 (6.43) (6.44) (6.45) where 6a = 1/ai. Using (6.45), the pdf of F in (6.4) can be written as C*2 — 1 /r(7) = tf12ar*-1cr(ai+aa) E (-1)9 9 = 0 I a 2 - l \ v ? / , / Co \ - ( Q i + a 2 ) 6 « 2 - i - 9 7 a 1 + , - i ^ + i?_ 7j ( 6 _ 4 6 ) 110 Using the identity [8] / xfl-1{l +Px)-Udx = — 2Fl{v,li;l + n,-(3u), Jo u arg(l + (3u)\ < IT, Re \x > 0, (6.47) and (6.46), Fr(7i) can be written as Frill) = / fv{l)di Jo Ot2 — 1 1 i ^ a2 - 1 Jo V ci 9=0 C 2 ^ - ( a l + - l 2 ) C l »1 « 2 — 1— q \ " J dj C(2 —1 = i v 1 2 c 7 ( Q l + Q 2 ) £ (-1)" 9=0 a 2 - 1 \ *1 ai+<2 i « ; oti+q 7i * x 2 F i ( a 1 + a 2 , a i + g; 1 + a i + g; -—7i)-C i (6.48) (6.49) (6.50) Note that in obtaining (6.50), the condition Q2 arg(l H 7i)| < u C l (6.51) must be satisfied. This can be verified by substituting (6.6) and (6.7) into (6.51), and realizing that | arg(l + c 2 7i/ci) | < | arg(l + (c 2 /c x )(l/ai)) | . Thus, we have |arg(l + ^ l ) | C i a i arg ( l + ( f " (x2a2\ 1 X2a2J \ a2 ) ax a2ax \ arg / ctxX2a2\ \a2Xxaxj < IT. (6.52) (6.53) 111 6.3 A p p l i c a t i o n i n A d a p t i v e M o d u l a t i o n a n d C o d i n g a n d M u l t i c o d e s It is well known that adapting the transmission parameters in a wireless system to changing channel conditions can be advantageous. In the case of fast power control [10], the transmis-sion power is adjusted based on channel fading. Under good channel conditions a relatively low transmission power is required to maintain the target signal quality at the receiver. The process of changing transmission parameters to compensate for variations in channel condi-tions is known as link adaptation. Besides power control, adaptive modulation and coding (AMC) is another means for performing link adaptation [11, 12], and is used in the 3GPP High Speed Downlink Packet Access (HSDPA) channel. The goal of A M C is to change the modulation and channel coding according to the varying channel conditions. In order to increase the bit rate, multicode transmission is also used in the 3GPP standard [10, 11]. The multicode scheme [13] increases the bit rate by splitting the bits of a Transmission Block to more than one channelization code in a scheduling period. In this scheme, high rate data stream is divided into a number of lower rate data sub-streams. Al l the sub-streams are transmitted in parallel synchronous multicode channels so that interchannel interference is avoided. Some scheduling issues regarding A M C and orthogonal multicodes have been studied in [14]. The model in [14] mainly addresses the throughput performance on a per scheduling period basis. In contrast, the analysis presented below examines the average throughput performance by taking into account the time-varying nature of the channel. With A M C and orthogonal multicodes, the effective bit rate, R(j), at a given SIR, 7, is given by [14] R(l) = W ( 7 ) ( l - e;(7)), 3 = 1,...,J (6.54) 112 where £7 (7) is the frame error rate of modulation and coding scheme (MCS) j and J is the number of available MCS's. For a given maximum number, Nmax, of multicodes, the number, 7^(7), of multicodes that can be assigned to the MS is given by [14] 7^(7) = { LT/A.J , 7 f m ) < 7 < 7 7 N„ (min) (6.55) lj<l< 7)+i where Xj is the minimum SIR required per code for MCS 3 to achieve its target frame error rate. The basic bit rate Tj in (6.54) is given by = jR^\og2Mj, l<j<J, (6.56) where W is the chip rate, R^ is the code rate for MCS j, Mj is the number of points in the modulation constellation for MCS j and g is the spreading factor. As shown in Fig. 6.1, the terms <yjmm) and 7,- correspond to a set of decision thresholds which yield near-optimal choice of the MCS and number of multicodes for a given value of j4 Following a procedure similar to that in [14], the set of decision thresholds jj and 7 } c a n be obtained as 7j ~ (min) ^jNmax, 1 < j < J Aj ,.j = l (3j , K j < J 00 , j = J + 1 (6.57) (6.58) where Pj € (0,00) is the smallest value such that A,-(1 - e^A,)) > rj^Nmax, 2 < j < J. (6.59) 4 For illustration purposes, Fig. 4.1 assumes that the number of multicodes is a real number. In this case the proposed scheme is bit rate optimal [14]. For an integer number of multicodes, the rising slopes are replaced by staircases. The effect on optimality is discussed in Appendix D. 113 For simplicity, the reasonable assumption that £j-\(Bj/Nmax) is negligible is made in (6.59). The average bit rate R over 7 is then given by 7 •.(min) R = W ( 7 ) ( l - e i ( 7 ) ) / r ( 7 ) r f 7 , 1 •/'Y-(6.60) where ^•(7) = Q (7/^(7)) ~ (mm) ^ ^ ~ 7} < 7 < 7? ^ ^ ~ (mm) 7j < 7 < Tj+i (6.61) (6.62) and £7(7) is t n e frame error rate of MCS j at an SIR value of 7. The SIR per code for ~(mm) < ^ < c a n k e expressed as 7 7, 7/2, A,- < 7 < 2Aj 2Aj < 7 < 3Aj L7/AjJ l/Nmax, (Nmax - l)Aj < 7 < NmaxXj l/k, k\j <j<(k+ l)Xj, l<k< Nmax - 1 (6.63) (6.64) Using (6.62) and (6.64), the average effective bit rate R in (6.60) becomes R = E ( / J l , W ( 7 ) ( l - e i ( 7 ) ) M 7 ) d 7 + 7=1 V 7 , ( m i n ) / 7 j + 1 W ( 7 ) ( l - £ j ( 7 ) ) / r ( 7 ) d 7 = £ < £ 0i(j,fc) + <Mj) (6.65) (6.66) 114 where the quantities <j)\{j, k) and faij) are given by -(fc+l)A M,k) = k ( i _ C . ( I ) ) / r ( 7 ) d 7 (6.67) JkXj K ~ (min) MJ) =NmaxrJ+1 (l-Q(-J-))fr(>y)dr (6.68) J 7, V m,a.T Since 7 J - m m ^ and 7 j are chosen so that Cj(^) < Eo and Cj(jv7 ) — e o ; where eo is the target frame error rate, lower bounds to (6.67) and (6.68) can be written as ^k) = fc(l-eo) / /r(7)rf7 (6.69) ~(min) M) = Nmax(l-e0) P + 1 fr(j)d7 (6.70) Using Theorem 2.5, (6.69) and (6.70) can be written as M,k) = k(l-e0)(Fr((k+l)Xj)-Fr(k\j)) (6.71) Uj) = Nmax(l - e0) (Wj+i0) - W;)) (6-72) where Fr(.) is given in (6.41). Thus, a lower bound on the average bit rate is given by R- = Eo E M,k) + <hU) \fc= L 7J m i n ) /A J J / (6.73) An upper bound on the average bit rate is given by R+ = — ~ R . (6.74) 1 - £ 0 115 6.4 N u m e r i c a l R e s u l t s As shown in (6.2), the received SIR T is a ratio involving X\ and X2. Thus, the unit for the means of X\ and X2 is arbitrary. Fig. 6.2 shows the pdf / r ( 7 ) for different values of ai with a2 = 1, a\ = 3, a2 = 2, = 1.5 and X 2 = 1. As expected, the curve for a\ — 0.01 approaches the beta prime pdf whereas the curve for a a = 0.99 is close to the beta pdf. It can be seen that as a\ increases, the pdf / r ( 7 ) becomes narrower since the influence of X2 is reduced. Fig. 6.3 shows the outage probability, Po(Z) = / 0 Z / r ( 7 ) ^ 7 , as a function of E[T] for different values of a\ when ct\ = 2, a2 = 2, X2 = 1.6, a2 = 0.35 and Z = 0.2. The value of E[T] is changed by varying X\. For the chosen value of Z, the outage probability decreases with a i . However, this may not be the case for other values of Z as indicated in the next paragraph. Fig. 6.4 shows the outage probability as a function of the outage threshold, Z, for three different values of a-^ (and corresponding values of a2) with a\ = 2, a2 = 2, Xx = 0.5, X2 = 0.25 and E[T] = 3 dB. Even though the .E[r]'s are the same for all three cases, the outage probabilities are quite different. The outage probability curves grow sharper as ci\ increases (and a2 decreases). It can also be seen that the outage probability does not necessarily decrease with a,\. Fig. 6.5 shows the outage probability as a function of the outage threshold, Z, with (a) E[Y] = 3 dB and (b) E[T) = 5.4 dB. For the proposed model, ax = 2, a2 = 2, Xx = 0.5, X2 = 0.25, a2 = 0.25, with (a) a x = 0.3478 and (b) <n = 0.1557. For the Gaussian approximation, a.\ = 2, X\ = 0.5, with the relative noise power (a) 7Y0 = 0.25 and (b) N0 — 0.1429. Note that for the proposed model, the outage probability is 1 when Z > 1/a. The results show that the Gaussian approximation can be quite inaccurate as it ignores the fading of the interfering signal. Fig. 6.6 shows the average bit rate (normalized to the chip rate) bounds as a function 116 of a\ when «i = 5, a2 = 2, X\ = 0.2, X2 = 0.25 and Nmax = 10 for different values of a 2 , with a target frame error rate, e0, of 1%. The spreading factor g is assumed to be 16. The modulation schemes are QPSK and 16-QAM and the codes are of rates 1/2 or 3/4. For simplicity, the SIR thresholds used to achieve eo for each MCS are based on the first transmission results in [15]. As expected, at a given a2, increasing the value of ax effectively increases the home BS interference and results in a poorer bit rate performance. The same observation holds if a2 is increased while a\ is kept fixed. 6.5 C o n c l u s i o n s In this chapter, the pdf of T = Xi/{axXi + a2X2), where X\ and X2 are gamma variates, and a- and a2 are arbitrary constants is derived. The pdf simplifies to the beta distribution and the beta prime distribution in special cases. Analytical expressions for the moments, the moment generating function and the cumulative distribution function are obtained in terms of the hypergeometric function. Finally, the usefulness of the distribution of R is illustrated for the problem of adaptive modulation and coding with multicode transmission in a C D M A network. R(r) r.N J max r.N '• 3 max 2 max r.N 1 max . (min) j=1 % (min) « y (min) « '2 ^2 *3 3 — j=2 >~*—7=3-(min) s 'J -j=J Figure 6.1: Allocated MS bit rate as a function of 7 . 117 118 E[n (dB) Figure 6.3: Outage probability as a function of E[T] for different values of a\ when ot\ = 2, a2 = 2, X2 = 1.6, a2 = 0.35, and Z = -7 dB. 119 10"' o =0.4826, a =0.02 - e - a =0.3478, o2=0.25 o =0.185, a=0.72 I L i 1 1 - 1 0 - 8 - 6 - 4 - 2 0 2 4 6 Outage threshold (dB) Figure 6.4: Outage probability as a function of the outage threshold, Z, for three different values of a\ (and corresponding values of a2) with u\ = 2, a2 — 2, X\ = 0.5, X2 = 0.25 and E[T] = 3.0 dB. 120 -20 -15 -10 -5 0 5 10 15 Outage threshold (dB) Figure 6.5: Outage probability as a function of the outage threshold, Z, with (a) E[T] — 3.0 dB and (b) E[T] = 5.4 dB. For the proposed distribution, c*i = 2, a 2 = 2, Xi = 0.5, X2 = 0.25, a2 = 0.25, with (a) a\ = 0.3478 and (b) a\ = 0.1557. For the Gaussian approximation, cx\ — 2, Xi = 0.5, with the relative noise power (a) A^ 0 = 0.25 and (b) N0 = 0.1429. 121 O) re > re -o o N "S E 1.8 1.6 1.4 1.2 0.8 0.6 0.4 °2 = 0.15, Upper bound a2 = 0.15, Lower bound - e -a2 = 0.35, Upper bound • • © • • °2 = 0.35, Lower bound _,_ "l = 1, Upper bound . , + . . ° 2 = 1, Lower bound Figure 6.6: Normalized average bit rate bounds as a function of a\ for three different values of a2 with a\ = 5, a 2 = 2, Xi = 0.2, X2 = 0.25, Nmax — 10 and a target frame error rate of 1%. 122 References [1] A. J. Viterbi, CDMA - Principles of Spread Spectrum Communication. Addison-Wesley, 1995. [2] M . K. Simon and M.-S. Alouini, Digital Communication over Fading Channels: A Unified Approach to Performance Analysis. John Wiley & Sons, 2000. [3] J. O. Sebeni and C. Leung, "Performance of Concatenated Walsh/PN Spreading Se-quences for C D M A Systems," in Proc. of 49th IEEE Vehicular Technology Conference (VTC), Houston, Texas, May 1999. [4] T. S. Rappaport, Wireless Communications Principles and Practice. New Jersey: Prentice-Hall PTR, 1996. [5] A. Zellner, An Introduction to Bayesian Inference in Econometrics. John Wiley & Sons, 1971. [6] K. O. Bowman, L. R. Shenton, and P. C. Gailey, "Distribution of the Ratio of Gamma Variates," in Commumications in Statistics, Simulation and Compututation. Texas, USA: Marcel Dekker Inc., 1998, vol. 27, no. 1, pp. 1-19. [7] C. Mun, C.-H. Kang, and H.-K. Park, "Approximation of SNR Statistics for MRC Diversity Systems in Arbitrarily Correlated Nakagami Fading Channels," Electronics Letters, vol. 35, no. 4, pp. 266-267, February 1999. [8] I. S. Gradshteyn and I. M . Ryzhik, Table of Integrals, Series, and Products. Academic Press Inc., 1980. [9] L. Couch, Digital and Analog Communication Systems, 4th ed. New York: Macmillan, 1993. [10] H. Holma and A. Toskala, Eds., WCDMA for UMTS Radio Access for Third Generation Mobile Communications. John Wiley &; Sons, 2002. [11] "Physical Layer Aspects of U T R A High Speed Downlink Packet Access," 3rd Generation Partnership Project, Technical Report 3G TR25.858, 2002. [12] M.-S. Alouini and A. J. Goldsmith, "Adaptive Modulation over Nakagami Fading Chan-nels," in Wireless Personal Communications. Netherlands: Kluwer Academic Publish-ers, 2000, vol. 13, pp. 119-143. [13] S. J. Lee, H. W. Lee, and D. K. Sung, "Capacities of Single-Code and Multicode DS-C D M A Systems Accommodating Multiclass Service," IEEE Trans, on Vehicular Tech-nology, vol. 48, no. 2, pp. 376 -384, March 1999. [14] R. Kwan and C. Leung, "Channel-Based Downlink Scheduling Schemes for C D M A . Networks," in Proc. of IEEE Vehicular Technology Conference (VTC), Los Angeles, California, September 2004. 123 M . Dottling, J. Michel, and B. Raaf, "Hybrid ARQ and Adaptive Modulation and Coding Schemes for High Speed Downlink Packet Access," in Proc. of IEEE Interna-tional Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), September 2002. 124 Chapter 7 General Order Selection C o m b i n i n g for Non-Ident ical ly Dis t r ibu ted Fading Channels 7.1 I n t r o d u c t i o n In performance analyses of selection combining (SC) [1, 2], the statistics of the maximum of a set of random variables (rv's) are needed. In [3], the cumulative distribution function (cdf) of the output signal-to-noise ratio (SNR) for a L-branch SC system over independent, identically distributed (i.i.d.) Nakagami fading channels is derived assuming that the fading figure [4] is an integer. In [5], an exact expression for the moment generating function (MGF) is obtained in terms of the Laurecella hypergeometric function. In [1], a unifying M G F based approach is used to study the performance of dual branch SC over correlated slow Rayleigh and Nakagami-m fading channels. In [6], an expression for the average output SNR for SC with three correlated Nakagami fading branches is obtained as an infinite series. In [7], a closed-form expression for the M G F of SC over i.i.d. Weibull fading channels is obtained in terms of the Meijer G function. SC for independent but not necessarily identically distributed (i.n.d.) Weibull fading channels is studied in [8]. In particular, a closed-form expression is derived for the general moment of the SC output SNR and symbol error rate (SER) expressions for a number of modulation schemes are obtained in terms of the Meijer l rThe material in this chapter is largely based on R. Kwan and C. Leung, "General Order Selection Combining for Non-Identically Distributed Fading Channels." Proc. of IEEE Wireless Communications and Networking Conference (WCNC'06), Las Vegas, April 2006. 125 G function. Generalized SC (GSC), in which the signals from the N strongest paths among the L available resolvable paths are combined, represents a compromise between the SC and maximal ratio combining (MRC) techniques [1]. In [9], the performance of GSC over i.i.d. Weibull fading channels is analyzed. In [10], the probability density function (pdf) and cdf for an L-branch GSC system are obtained for i.i.d. Nakagami fading channels. In [11, 12], expressions for the M G F of a L-branch GSC system are derived assuming the L branch gains are i.n.d. More recent analyses of variants of GSC appear in [13, 14, 15]. In studying problems such as multiuser scheduling [16, 17, 18, 19], we are interested in the performance of not only the user with the highest SNR, but also those of other users. The GSC model is not applicable in this case. Rather, we are interested in general order selection combining (GOSC), i.e. the statistics of the qth largest SNR. In this chapter, the qth order statistic of a set of L i.n.d. rv's is examined for both Nakagami and Weibull fading channels. Using a basic result for the pdf of the qth order statistic for independent rv's and transforming this pdf into an appropriate form, exact, closed-form expressions for the M G F and the general moment of the qih largest SNR are derived in section 7.2. Exact closed-form expressions for the SER for a number of modulation schemes are obtained in section 7.3. Numerical results are presented in section 7.4, followed by conclusions in section 7.5. 7.2 G e n e r a l O r d e r S e l e c t i o n S t a t i s t i c s The following result [20] for the pdf of the qth order statistic for a set of independent rv's will be used in the sequel. Theorem: Let Xx, X2,... ,Xi be L independent rv's. The corresponding order statistics are obtained by arranging the L XiS in a non-increasing order, denoted by X 2 : L , . . . , XL.L, or X(i),X(2), • • •, X(Ly Thus, X^ corresponds to the largest of the Ays. Let fj(x) and Fj(x) 126 denote the pdf and cdf of Xj respectively. The pdf of the qth order statistic, Xq:L, is then given by fg-Av) (q-l)\(L-q)\ Fi(y) • • • FL(y) Fi(y) /i(y) l-F^y) FL(y) h(y) 1 - FL(y) 1-F1{y) ••• l-FL(y) L — q identical rows } 1 row (7.1) > q — 1 identical rows where the symbol + | A | + denotes the permanent of matrix A [21]. Using this theorem, the statistics of GOSC in Weibull and Nakagami fading channels are studied in sections 7.2.1 and 7.2.2 respectively. 7.2.1 Weibull Fading Channels The pdf of the Weibull distribution is given by2 m > 0, r > 0 e x p ( - ^ ) 0, r < 0 • (7.2) where m is the Weibull fading parameter and a; is a positive, moment-related parameter given by LU = E[R-21 \ m / 2 r(l + 2/m) (7.3) In (7.3), r(.) denotes the Gamma function. 2 The term R here is conveniently denoted as the envelop of the faded signal, which is different from the bit rate defined earlier in this thesis. 127 Let Si = pidi + rii, where di is the signal component of the ith user, and n, is the corresponding noise component. The term pi = R\edi denotes the complex channel gain for user i. Let Es/N0 be the received energy per symbol to noise power spectral density (PSD). Then the received SNR is X i = i? t 2(£ s/JV 0), with pdf auPiX? 1exp(-pixfi), Xi>0, •fx^ = { (7.4) 0, Xi < 0 where a; = mi/2, and r ( i + a- 1) A = (7-5) are the channel parameters for user i, and Xi is the mean of Xi. The cdf of Xi is given by 1 -exp(- /3 ixf ) , X i > 0 (7.6) 0, ^ < 0. It might be noted that Xi also has a Weibull distribution [9, 7]. Let {Xi,i = 1, 2 , . . . , L} be a set of i.n.d. Weibull distributed rv's and let Y — X(qy For notational convenience, let fi(xi) = fx^Xi), i = 1,. • • ,L. (7.7) The pdf of Y can be obtained from (7.1) as L L-q+1 L &Hv) = Y,fiM £ II fl,(v) II ( i -^(y) ) (7-8) = zZfhiv) Yl p 2 ~ q + \ y ) Q L L - q + 2 { y ) (7.9) where Sx,g,/i is the set of all combinations of L—q indices chosen from the set {1 ,2 , . . . , L}—1\. 128 Assuming ax = a 2 • • • = a L = a 3 and using (7.6), the term Q£_ 9 + 2 (y ) = Ylu^L-qA1-Fiu(y)) is given by QUAy) = e~Pluya- (7-10) u=L-q+2 After simplification, the term P2L~q+1(y) — V^Z2qArl Fij(y) c a n D e expressed as P2L~q+1(y) = E(-i) f c £ n e - ^ (7.ii) k=0 2 < n i < n 2 < . . . < n f c < L - q + l p=l Following further simplification, the pdf of Y in (7.9) can be written as &\V) = E ^ E E V l ) " E y « - X e - ^ a (7.12) ' l = l sL,q,ll fc=0 2 < n i < 7 i 2 < . . . < n f c < L - g + l with CFC = Ep=i Pinp + E £ = L - , + 2 A « + A , . For the special case of SC, i.e. q = 1, (7.12) reduces to [8, eq. (5)]. Equation (7.12) shows that the pdf of Y can be written as linear combinations of Weibull pdf's with parameters £fc and a. Using [22, eq. (3.478)], the nth moment can be written as E\r\ = EA, E E(-i) f c E 4 ^ r ( ^ ) . (7.i3) il=l sL,q,lx k=0 2<n1<n2<...<nk<L-q+l Using [23, eq. (21)], and the fact that [23, eq. (11)] \ (7.14) 3 T h e term a is conveniently denoted as the fading parameter of the distr ibut ion in the case when al l a^s are equal, which is different from the orthogonality factor defined earlier in this thesis. — ^ 0 , 1 129 the M G F of Y can be obtained as ( f ) 1 / 2 A a S -'l=l fc=0 2<ni<n2<...<nk<L-q+l (27r) i = l ,2 , . . . ,A {£}, z = 0, (7.15) where A and K are positive integers chosen so that \/K = a and G"'J(.) is the Meijer G function [22]. 7.2.2 Nakagami-m Fading Channels For Nakagami-m channels, the received SNR is gamma distributed, i.e. terr£exp(-^), *<>() 0, Xi < 0, (7.16) where a; is the fading figure and $ is the mean of Xi4. Assuming that OJJ takes on integer values, the pdf of Y can be expressed as - Try (^Y'tll £ £ ••• £ 2 < n i < . . . g + 1 mi=0 mfc=0 £ m i = 0 air - 1 m ' = 0 \t=l fe Ci ILi m t ! E ( n ^ ) i i r w i + " ',-1 C "v n ,t'=i (7.17) where fe 9 - 1 ^ = E M* + E m * ' + a ' i t=i f=i fe L = E Cin t + E + t=l t'=L-g+2 (7.18) (7.19) *Note that the definitions of a , and /3j are different for the Nakagami and Weibu l l models. 130 (lu — alu/Plu (7.20) The derivation of (7.17) is given in Appendix E. With appropriate scaling factors, the pdf of Y is essentially a linear combination of gamma distributions. This characteristic can be very useful for performance analysis as the properties of the gamma distribution are well-known. From (7.17), together with [22, page 310, 3.351.3], the M G F can be obtained as M{f\s) = r fi?\y)eavdy Jo (7.21) = E E E (%•) - U L E E E A K^liJ 2<nx<...<nk<L-q+\ m i=0 m f c =0 k = 0 h = \ S L i q i h \Ai a, L-g+2 £ m i = 0 -1 /•mt\ ( q - \ / - " V S ' n . \ I T T S ' L - Q + l + t ' =1 mt'-J \t"l m't'] (^-s)-"*K-l)!(7.22) From (7.22), the n t / l moment of Y can be obtained as E[y n ] r i n A4 9 ) (s ) s=0 VAJ r K ) 2<ni<...<Tifc<i—9+1 mi=0 mk=0 = E E E E E m ' x=0 E n m ' = 0 \ t= l ^ TT "1 K + 7 1 - !) ! -Jll m't>-^ + n \ u k - l ) \ (7.24) (7.23) iyk -1)! 7.3 Symbol Error Rate Analysis The general formula for calculating the average SER is Ps = [°° Ps(y)tiq)(y)dy, Jo (7.25) where Ps(y) is the SER for the given modulation scheme at an SNR value of y. 131 7.3.1 Weibull Fading Channel The average SER can be obtained by substituting the appropriate expression for Ps(y) together with (7.12) into (7.25). After simplification, we have L-q PS = £ E ( - i ) f e E U=l sL,qAi k = ° 2<m<n2<...<nk<L-q+l (7.26) where *fc = 7 ya-re-^ Ps(y)dy. Jo (7.27) Binary Phase Shift Keying (BPSK) For BPSK, the B E R expression is given by Ps(y) = cQlJby), (7.28) with 6 = 2 and c = 1. Substituting (7.28) into (7.27), and using [23, eq. (21)], together with the fact that [24, p. 645] erfc (N/Z) = ( G1'2 7T 2,0 X \ (7.29) 5 I we have — Ak, where 2 v ^ (27T) G o ,2A ^2A,*+A a i — ) , i = l , 2 , . , A , i x />J=1,2,...,A "a,b,k y { ^ } , i ' = 0 , l , . . , K - l , { ^ T 2 } . i'=0,\,...,\-\J (7.30) 132 In (7.30), a = X/K, and (|) A -For the special case of SC, i.e. q = 1, (7.26) reduces to [8, eq. (13)]. The SER for a variety of modulation schemes over a non-fading AWGN channel can be expressed as (7.28) with different values of b and c [1]. For example, the SER for M-ary Differential Phase Shift Keying (M-DPSK) is well approximated by (7.28), with [25] c = 2.06, 1 + C 0 S ^ (7.32) b = 2 ( l - c o s ^ ) . (7.33) M-ary Quadrature Amplitude Modulation (M-QAM) The SER for M - Q A M , where M — 2K and K is an even integer, over a non-fading AWGN channel is given by [1] Ps(y) = ^Q[\f^)-^v2Q2{\lby) (7.34) where V = ^ (7.35) 'M Using [1] Qn^by) < (2nby)-n/2e-^, (7.37) 133 together with (7.27), (7.34) and [23, eq. (21)], the integral Bk = /0°°ya~l e~^ya Q2 (jby~)dy can be upper bounded by poo = (2irb)-1 / ya~2e-^y e-bydy Jo (27T) K + X -1 KL-A {i^+I} , i = i ) 2 > . . . , A (7.38) (7.39) The term $ k in (7.27) is then lower and upper bounded respectively by = 4pAk-4p2B+ (7.40) and <j>t = 4pAk. (7.41) Since Ak = /0°° y ^ e ' ^ Q (V5y) dy and Bk = /0°° y ^ e ' ^ Q 2 (v%) dy, it follows that Bk « Ak for large values of y. For large values of y, the bound in (7.37) is very tight and hence Bk « Bk. Then, the lower and upper bounds in (7.40) and (7.41) are very close. This will be the case as the average channel gains increase. 7.3.2 Nakagami Fading Channels The average SER can be obtained by substituting the appropriate expression for P3(y) together with (7.17) into (7.25). After simplifying, we have ( - l ) f c - L ~ q L / f t , \ a ' i a l n i ~ l " ' n f c - 1 Q ' L - , + 2 - 1 £ E ••• E E 2 < n i<...<7ifc< L - g + i m i = 0 mfc=0 a l L - \ E m'g-l=° 134 k (™t FT "* g-l / • t , 4 ' = 1 S(//fc,z/fc) where (7.42) /•OO Jo (7.43) The exact expression for E(/j,k,i/k) depends on the type of modulation used. B P S K Substituting (7.28) into (7.43), and making use of [1, (5A.4a)], we have dk = Ck 1 + cfc 2/Ufc' (7.44) (7.45) (7.46) For the sake of notational simplicity, the dependence of [ik on dk and ck is not explicitly shown. M - Q A M Substituting (7.34) into (7.43), and using [1, (5A.4'a)] and [1, (5.30)], the average SER can be expressed as in (7.42); the term E(/j,k, vk) in (7.42) is now =(/ifc, Vk) 1 1 2p /2A / i - 4x n -4p'{---dk 4 7T 1 - sin (tan 1 dk) __ __ — %3 £ £ J (1 + CkV 135 ( c o s ( t M - 4 ) ) 2 " - " + ' ] } } I M where dk and ck are given by (7.45) and (7.46) respectively. M - P S K The SER for M - P S K over a non-fading AWGN channel is given by , (M-I)TT (7.47) P.(V) = - I M e x P ( — ^ y ) d 0 (7.48) 7T Jo \ sin V J 9 = s i „ * ( j L ) . (7.49) The SER can be obtained by substituting (7.48) and (7.17) into (7.25). Since (7.17) is a linear combination of h(vk, Hk,y) = yVk~x exp (—piky), the evaluation of (7.25) involves the double integral S(^fc,^ fe) = - / / exp(—T^rzy] x ir Jo Jo V sin 0 / h(vk,fj,k,y)d6dy. (7.50) where Using the Laplace transform, /•oo MY{fk,^k,s) = / esyh(uk,nk,y)dy (7.51) (7.52) S(/Jfe,ffc) can be re-written as E(nk,uk) = - MY(vk,p,k,—r^BJdd (7.53) 7T 7o V sin BJ 136 rK) 1 + Pk sin 9 (7.54) Using [1, (5.80)], S(i/fc,/ifc) can be written as (7.55) In (7.55) Afc = dk cot ) (7.56) where dk is given by (7.45), and ck — g/pk-7.4 N u m e r i c a l R e s u l t s Let a = [OL\, ... ,aL], where {aj, i = 1,... ,L) are defined in sections 7.2.1 and 7.2.2 for the Weibull and Nakagami models repectively. Similarly, let X = [X^,...,Xi] and 3 = ... ,BL], where {Xi, i = 1,..., L} and {Bi} i = 1,..., L] are defined in sections 7.2.1 and 7.2.2 respectively. Finally, let Xavg = YH=\ Xi/L and Bavg = Y,i=\ Pi/L be the overall average SNR among all users for their respective channel models. Figs. 7.1 and 7.2 show the average SER, Ps, for BPSK and 4-QAM on Weibull fading channels as a function of Xavg for different values of q with a = [2 2 2 2] and X / X i = [1111] (i.i.d. case) or X / X a = [1 3 5 7] (i.n.d. case). Generally, the average SER for i.i.d. channels is lower for large q values compared to i.n.d. channels. For small values of q and Xavg, the 137 average SER for i.n.d. channels is lower than for i.i.d. channels. From Fig. 7.2, it can be seen that the lower and upper bounds from (7.40) and (7.41) are very tight, especially as Xavg increases. This is to be expected, as discussed in section 7.3. Figs. 7.3 and 7.4 show the average SER, Ps, for 8-PSK and 4-QAM respectively on Nakagami fading channels as a function of f3avg for different values of q with a = [2 2 2 2] and /3= [1 1 1 1] (i.i.d. case) or Q= [1 2 3 2] and p/p\ = [1 3 5 7] (i.n.d. case). The results are qualitatively similar to those for Weibull fading channels. 7.5 C o n c l u s i o n s In this chapter, some new analytical results for general order selection over Weibull and Nakagami fading channels are presented. By transforming the pdf into an appropriate form, exact expressions for the M G F and general moment of the g-th order statistic for i.n.d. Weibull and Nakagami fading channels were derived. Expressions for the average SER for several common modulation schemes are also obtained. Numerical results show that for large values of q, the average SER is generally lower with i.i.d. fading channels. For smaller values of q, this is not always the case. 138 : :l: : : : : : : : : J: : : : : : : : : J: Figure 7.1: Average bit error rate, Ps, for BPSK on Weibull fading channels, as a function of Xavg for different values of q, a= [2 2 2 2]: X / X i = [1111] (i.i.d. case), and X / X i = [1 3 5 7] (i.n.d. case). Figure 7.2: Average symbol error rate, Ps, for 4-QAM on Weibull fading channels, as a function of Xavg for different values of q, a= [2 2 2 2]: X / X i = [1111] (i.i.d. case), and X / X i = [1 3 5 7] (i.n.d. case). 139 OS 10 I— g E on <u 10" > < . -*- 9=1, i.i.d. - e - 9 = 2, i.i.d. —<- 9 = 3, i.i.d. —t— 9 = 4, i.i.d. • • * • 9=1, i.n.d. o 9 = 2, i.n.d. • *. 9 = 3, i.n.d. • •+ • 9 = 4, i.n.d. P (dB) Figure 7.3: Average symbol error rate, Ps, for 8-PSK on Nakagami fading channels, as a function of j3avg for different values of q with (a) a= [2 2 2 2], p/p\ = [1111] (i.i.d. case) and (b) a= [1 2 3 2], /3/A = [1 3 5 7] (i.n.d. case). (2 io" o fc w •u 10 » 9 = 3 , i.n.d. ••+• 9 = 4 , i.n.d. 10 12 14 16 P (dB) Figure 7.4: Average symbol error rate, Ps, for 4-QAM on Nakagami fading channels, as a function of 0avg for different values of q with (a) a= [2 2 2 2], /3//3x = [1111] (i.i.d. case) and (b) a= [1 2 3 2], /3/A = [1 3 5 7] (i.n.d. case). 140 References [1] M . K. Simon and M.-S. Alouini, Digital Communication over Fading Channels, 2nd ed. John Wiley & Sons, 2005. [2] W. C. Jakes, Microwave Mobile Comunications. John Wiley & Sons, Inc., 1974. [3] C.-D. Iskander and P. T. Mathiopoulos, "Finite-State Markov Modeling of Diversity Nakagami Channels," in Proc. of the Seventh Canadian Workshop on Information The-ory, Vancouver, B.C., June 2001. [4] J. G. Proakis, Digital Communications, 4th ed. McGraw-Hill, 2001. [5] R. Annavajjala, A. Chockalingam, and L. B. Milstein, "Performance Analysis of Coded Communication Systems on Nakagami Fading Channels With Selection Combining Di-versity," IEEE Transactions on Communications, vol. 52, no. 7, pp. 1214 - 1220, July 2004. [6] D. A. Zogas, G. K. Karagiannidis, and S. A. Kotsopoulos, "On the Average Output SNR in Selection Combining With Three Correlated Branches Over Nakagami-m Fading Channels," IEEE Transactions on Wireless Communications, vol. 3, no. 1, January 2004. [7] J. Cheng, C. Tellambura, and N. C. Beaulieu, "Performance of Digital Linear Mod-ulations on Weibull Slow-Fading Channels," IEEE Transactions on Communications, vol. 52, no. 8, pp. 1265 - 1268, August 2004. [8] N . C. Sagias, G. K. Karagiannidis, D. A. Zogas, and P. T. Mathiopoulos, "Selection Diversity for Wireless Communications with Non-Identical Weibull Statistics," in Proc. of IEEE Global Telecommunication Conference GLOBECOM 2004, December 2004, pp. 3690 - 3694. [9] M.-S. Alouini and M . Simon, "Performance of Generalized Selection Combining over Weibull Fading Channels," in Proc. of 54th IEEE Vehicular Technology Conference VTC, Fall, vol. 3, Atlantic City, New Jersey, October 2001, pp. 1735-1739. [10] A. Annamalai and C. Tellambura, "Performance evaluation of generalized selection diversity systems over Nakagami-m fading channels," Wireless Communications and Mobile Computing, vol. 3, no. 1, pp. 99 - 116, February 2001. [11] Y . Ma and C. C. Chai, "Unified Error Probability Analysis for Generalized Selection Combining in Nakagami Fading Channels," IEEE Journal on Selected Areas in Com-munications, vol. 18, no. 11, pp. 2198 - 2210, November 2000. [12] Y . Ma and S. Pasupathy, "Efficient Performance Evaluation for Generalized Selection Combining on Generalized Fading Channels," IEEE Transactions on Wireless Commu-nications, vol. 3, no. 1, pp. 29 - 34, January 2004. 141 [13] R. K. Mallik, R Gupta, and Q. T. Zhang, "Minimum Selection GSC in Independent Rayleigh Fading," IEEE Transactions on Vehicular Technology, vol. 54, no. 3, pp. 1013 - 1021, May 2005. [14] Y . Ma, R. Schober, and S. Pasupathy, "Performance of M-PSK with GSC and E G C with Gaussian Weighting Errors," IEEE Transactions on Vehicular Technology, vol. 54, no. 1, pp. 149 - 162, January 2005. [15] Y . Chen and C. Tellambura, "Performance Analysis of Three-Branch Selection Com-bining over Arbitrarily Correlated Rayleigh-Fading Channels," IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 861 - 865, May 2005. [16] F. Berggren and R. Jantti, "Multiuser Scheduling over Rayleigh Fading Channels," in Proc. of IEEE Global Telecommunication Conference GLOBECOM 2003, vol. 1, December 2003, pp. 158 - 162. [17] R. Kwan and C. Leung, "Downlink Scheduling Optimization in C D M A Networks," IEEE Communications Letters, vol. 8, no. 10, pp. 611 - 613, October 2004. [18] , "Channel-Based Downlink Scheduling Schemes for C D M A Networks," in Proc. of IEEE Vehicular Technology Conference (VTC), Los Angeles, California, September 2004. [19] S. K. Kim and C. G. Kang, "Delay Analysis of Packet Scheduling with Multi-Users Diversity in Wireless C D M A Systems," Wireless Networks, vol. 11, pp. 235 - 241, 2005. [20] R. J. Vaughan and W. N. Venables, "Permanent expressions for order statistics densi-ties," J. Roy. Statist. Soc. Ser. B, vol. 34, pp. 308 - 310, 1972. [21] A. C. Aitken, Determinants and Matrices. Edinburgh, Oliver &; Boyd, 1956. [22] I. S. Gradshteyn and I. M . Ryzhik, Table of Integrals, Series, and Products. Academic Press Inc., 1980. [23] V. S. Adamchik and O. I. Marichev, "The Algorithm for Calculating Integrals of Hy-pergeometric Type Functions and its Realization in R E D U C E System ," in Proc. of International Conference on Symbolic and Algebraic Computation, Tokyo, Japan, 1990, pp. 212 - 224. [24] A. P. Prudnikov, Y . A. Brychkov, and O. I. Marichev, Integrals and Series, More Special Functions. N . Y. : Gordon and Breach Science Publication, 1986, vol. 3. [25] R. F. Pawula, "Asymptotics and Error Rate Bounds for M-ary DPSK," IEEE Trans-actions on Communications, vol. 32, no. 1, pp. 93 - 94, January 1984. 142 Chapter 8 A n Accura te M e t h o d for A p p r o x i m a t i n g P robab i l i t y Dis t r ibut ions in Wireless Communicat ions 8.1 I n t r o d u c t i o n Diversity combining is a commonly employed technique for reducing the effects of fading over wireless communication channels. The motivation behind diversity combining is to exploit the stochastic nature of the gains experienced on different links (branches). Common types of diversity combining include maximal-ratio combining (MRC), equal-gain combining (EGC), and selection combining (SC) [1]. More recently, a hybrid of MRC and SC, known as generalized selection combining (GSC), in which a certain number of the strongest branch signals are selected and combined, has received much attention [1]. Although diversity combining is a well-studied topic, the analysis techniques and results are in general rather complicated. For example, in many cases, exact closed-form expressions for the probability density function (pdf) or the cumulative distribution function (cdf) of the signal-to-noise ratio (SNR) at the combiner output are very complex, if not impossible, to derive [1]. An alternative approach is to explore methods for approximating the probability distri-butions using simpler expressions. In this chapter, we use the method of Pearson systems [2] to obtain approximate expressions for pdf's. A summary of Pearson systems is given in l rThe material in this chapter is largely based on R. Kwan and C. Leung, "An Accurate Method for Approximating Probability Distributions in Wireless Communications." Proc. of IEEE Wireless Communi-cations and Networking Conference (WCNC'06), Las Vegas, April 2006. 143 section 8.2. In section 8.3, the method is applied in various diversity schemes for wireless communications. Numerical results are provided in section 8.4 to illustrate the accuracy of the approximations. 8.2 S y s t e m s o f D i s t r i b u t i o n s Pearson systems arise as solutions to a simple differential equation [2]. Such solutions lead to seven different families of curves, characterized by their skewness and kurtosis [3]; these families are referred to as systems of distributions, systems of frequency curves or, simply, Pearson systems [3]. Pearson systems were originally intended to approximate a wide variety of distributions based on empirical observations. According to the procedure outlined in [3], a selection parameter K can be computed based on the first four moments of the empirical data in order to determine the appropriate family of curves for the approximation. Depending on the value of K, the exact form of the curve can be obtained. The selection parameter, K, is given by ft(ft + 3)2 " 4 ( 4 f t - 3 f t ) ( 2 f t - 3 A - 6 ) ^ • > where /3j and @2 are the skewness and kurtosis respectively [4], and are defined as (5\ — n\ and = /WA^- ^ n e terms fit = E[(Z — u\)1} and i/j = E[Zl] are the ith central and non-central moments respectively. It may be noted that "general" distributions such as Weibull, lognormal, gamma and Student's t are associated with lines on the /?i,/?2 plane, while more limited models such as normal, exponential and uniform are represented by points in the /?i,/32 plane [5]. The most common (main) types of curves are the type I, type IV, and type VI curves, which correspond to the cases K < 0, 0 < K < 1, and K > 1 respectively. There are a number of less common "transition" types which correspond to different values of K, PI and j32- In 144 addition, there are a number of so-called "uncommon" types which are of little practical interest. More details on the different types of curves can be found in [3]. 8.2.1 Pearson Type I ( - 0 0 < K, < 0) The expression for the type I curve is given by where and K0(i + ^(i-f-2y>, -b1<z<b2 0, otherwise (8.2) 0i = eliee22 bx + b2 + 0 2 ) e i + e 2 J B(0i + 1,<?2 + 1) t-2 - s*t(t + 2)J^-V K-i t-2 + sH(t + 2)J&-V * M 1 2 0i b0 b2 = b0 - h (8.3) (8.4) (8.5) (8.6) (8.7) bo t = ^ 2 { / 3 i ( * + 2)2 + 16(i+l)} = /31(i + 2)2 + 16 (£+ l ) 6 ( f t - f r - l ) s = 6 + 3/?i - 2/32 sign(^3)-(8.8) (8.9) (8.10) (8.11) 145 The peak (mode) of (8.2) occurs at z — 0. To approximate the pdf of Z, the mean of (8.2) is set equal to that of Z, i.e. v\. This results in fz(z) = #o(l + ^ ) * ( l - ^ ) * , - & i + A < z < b2 + A 0, otherwise (8.12) where the adjustment factor A is given by " i - f2 zfizI)(z)d &o(*i + 1) = v\ QX+Q2 + 2 + h (8.13) (8.14) A closed-form expression for the cdf of Z is not given in [3], but can be obtained as (see Appendix F) Fz(z) = b1KoPe>r{ei+1)Bx(z){61 +1,02 + 1) z > —b\ + A (8.15) 0, otherwise where Bx(z)(.,.) is the incomplete beta function [6], with I = p'/p, p = 1 + (bi/b2), p' = h/h, and x(z) = l(l + ff). 8.2.2 Pearson Type IV (0 < re < 1) The expression for the type IV curve is given by S[zV\z) = K0(l + ^j exp ( -02 tan" 1 £ ) , -oo < z < oo (8.16) 146 where 0i a K0 -(r + 2) - r ( r - 2 ) V A 72 — y/l6(r - 1) - 31{r - 2)= ^2 ( 1 6 ( r - l ) - ^ ( r - 2 ) 2 ) 16 (aF(r,0 2))- a (8.17) (8.18) (8.19) (8.20) and 6(ft — — r 2/32 - 3/?i - 6 /•f F(r,62) = / cosr(u) exp(—d2u)du. (8.21) (8.22) To approximate the pdf of Z, the mean of (8.16). is set equal to that of Z, i.e. v\. This results in fz(z) = / £ J V ) ( * - A ) , - o o < z < o o (8.23) where A = v\ + d2a/r. In this case, a closed-form expression for the cdf of Z cannot easily be obtained but it can be computed via numerical integration. 8.2.3 Pearson Type VI ( ! < « . < oo) The expression for the type VI curve is given by KQ (Z - of2 z-61, a<z<oo 0, otherwise (8.24) 147 where and K0 r(r + 2) fp\ r-2 i = 1,2 5 v ) r(0 x - 6?2 - i)r(#2 + I) r = 6(^2 - A - l ) 6 + 3/3i - 2/32 A = /?!(r + 2) 2 + 16(r + l ) . (8.25) (8.26) (8.27) (8.28) (8.29) In (8.27), T(.) denotes the Gamma function [6]. After equating the mean of (8.24) to that of Z, i.e. Ui, the resulting pdf is given by (8.30) where A = v\ — a{Q\ — l)/(#i — 92 — 2). Although a closed-form expression for the cdf of Z is not given in [3], it can be obtained as (see Appendix F) Fz{z) = 1 - Koa^-^B^. (0j - e2 - 1, e2 + 1) a + A < z < oo 0, otherwise. 8.2.4 Transition Types For K = ±oo, the pdf corresponds to the type III curve, and is given by fz"%) a) (8.31) (8.32) 148 where KQ — p p + 1 / (e p r(p+ 1)) is a normalization constant with p = ja, and the expressions for a and 7 can be found in [3]. By letting x = (1 + (z/a))/b, X = jab, and m — ja + 1, (8.32) can be transformed into the well-known gamma pdf fx(x) = —-xm-le-Xx, x > 0. (8.33) 1 [m) The parameters m and A can be obtained by matching the moments and are given by 1 7 1 = i ^ - „ 2 and A = ^ . For large values of |«|, the gamma pdf can still provide a good approximation. The various transition types and their associated parameter values are summarized in Table 2.1. 8.3 S o m e A p p l i c a t i o n s 8.3.1 M R C over Non-Identical Weibull Fading Channels The performance of MRC diversity systems has been studied extensively for Rayleigh, Rician and Nakagami channel models [1],[7]-[11]. A lesser-known distribution for modelling fading channels is the Weibull distribution. Experimental data for the indoor wireless channel have been found to closely match the Weibull distribution [12, 13]. This distribution can also be a good model for the outdoor fading channel [14, 15, 16]. Recently, closed-form expressions for the moments and the moment generating function (MGF) of the SNR at the output of a maximal-ratio combiner, assuming the branch SNR's are non-identically Weibull distributed, have been derived in [17]. However, to the authors' best knowledge, exact closed-form expressions for the corresponding pdf and cdf of the SNR are not available. Let {Xi, i = 1,..., L} be the SNR of the ith input branch of a L-branch maximum ratio 149 combiner; Xi has a Weibull distribution, a j 7 i x Q i 1 exp (—7jX Q i ) , x > 0 0, otherwise. (8.34) where ajj is the fading figure and 7* is the moment-related parameter2. The M R C output SNR is given by Xi + x2 + ... + XL. (8.35) The mth moment of Z can be obtained using the multinomial expansion, and is given by E[Zn m m\ m.L-2 E E - E m i = 0 r a 2 = 0 m £ , _ i = 0 m mi m 2 1 ' m L _ 2 ^ m L _ i J E \x™-mi] E [ X 2 m i ~ m 2 l x . . . x E \x™Li2~mL-1] E [X^-1] (8.36) where E[Xi] = r 1 + a,-(8.37) Instead of trying to obtain exact expressions for the pdf and cdf of Z, they can be accurately approximated using the first four moments of Z and the Pearson method outlined in section 8.2. 2 The term 7» is conveniently denoted as the moment-related parameter for the distribution, which is different from the SIR defined earlier in this thesis. 150 8.3.2 General Order Selection Combining over Non-Identical Weibull Fading Channels SC is a simple diversity technique in which the branch with the highest SNR is selected [1]. A closed-form expression is derived for the moments of the output SNR of an L-branch SC with non-identical Weibull fading branches in [18]. Average symbol error rate expressions for a number of modulation schemes are given in terms of the Meijer G function. In some scenarios, such as multiuser scheduling, it is useful to examine the performance of not only the user with the highest SNR, but also other users who are in the queue during the same scheduling period [19]. The selection of the rth highest order statistics is referred to as general order selection combining (GOSC). In [20], some results for GOSC over non-identical Nakagami fading channels are presented. However, similar results for Weibull channels are not available. In this chapter, it is shown that the pdf and cdf of the SNR for GOSC over non-identical Weibull fading channels can be accurately approximated using the Pearson method. Let {Xi, i = 1,..., L} be a set of independent, non-identically distributed Weibull variates as in (8.34). The corresponding order statistics are obtained by arranging these L Xi's in a non-decreasing order and are denoted by X{\),X{2), • • •,-X'(L)- Thus, X(L) is the largest of the Xj's. In the case when OL\ = a 2 = . . . = OIL = & 3 , it is shown in [21] that the mth moment of X^ is given by /42 = B(m,a)IL (8.38) where I, = y -. r - r . (8.39) l<h<t2<-<ij<L ^ h l h 2 ' ' ' h i ' 3The term a is conveniently denoted as the fading parameter of the distribution in the case when all Qj's are equal, which is different from the orthogonality factor defined earlier in this thesis. 151 The m moment of X(r) can be obtained recursively as /"S = /4-L + £M™> a)IL.r+j, r = 2,... ,L (8.40) where Ajfaa) = (-1)i"1(iJ"_7)B(m'a)' v M l ) Once the first four moments are obtained from (8.40), the pdf and cdf can be accurately approximated using the Pearson method. 8.3.3 Generalized Selection Combining (GSC) over Non-Identical Weibull Fading Channels The idea behind GSC is to combine the signals from the I strongest paths out of the L available paths, and represents a compromise between the SC and MRC techniques [1, 22, 23]. For GSC over non-identical Weibull channels, exact closed-form expressions for the pdf or cdf of the SNR at the combiner output are difficult to obtain. Let Z — X(L) + X(L_!) + . . . + X(L-l+l)- (8.42) The mth moment of Z can be expressed as m m i v_ ^ ^ ( m X E[zm\ = E E ••• E m i = 0 ra2=0 m ; _ i = 0 E [X\ K m 2 j ( \ mi-2 y mi-i J m—m\ ymi—m2 v m ' - 2 — m l - l y m l - l (L-l+1) A ( L - / + 2 ) • • • ^(L-l) (8.43) Unfortunately, the random variables (r.v.'s) {X^, i = L — I + 1,..., L} are no longer 152 independent, and their general product moments are very difficult to obtain analytically. However, the first four moments can be readily estimated using relatively short simulations. It is shown in section 8.4 that the cdf can hence be accurately approximated. 8.3.4 Equal-Gain Combining (EGC) over Correlated, Non-Identical Nakagami Fading Channels Let {Ri, i — 1,..., L} be the gain of the ith branch of a L-branch pre-detection E G C diversity receiver. Assuming that equally likely symbols of energy Es are transmitted over a Nakagami fading channel and the received signal is corrupted by the additive white Gaussian noise (AWGN) with two-sided power spectral density No/2, the instantaneous SNR per symbol at the E G C output is given by [1] Z = -^(Rl + R2 + ... + RL)2. (8.44) The instantaneous SNR, Xi = ESR2/N0, for each branch follows the gamma distribution [1] where Xt is the average value of Xt, and a, > 0 is a shaping parameter. The performance of E G C systems has been extensively studied [1], [24]-[28] In [26], an infinite series expression for the pdf of the sum of two correlated Nakagami-m r.v.'s is de-rived. Subsequently, the symbol error rates for different modulation schemes are obtained for dual-branch E G C over correlated Nakagami-m channels. In [27], the M G F of Z is approxi-mated using the Pade approximation. For correlated branch SNR r.v.'s {Xi, i = 1,..., L], statistical parameters such as the kth moment, the skewness and kurtosis of Z are derived in [28]. However, available results suggest that exact closed-form expressions for the pdf or cdf of Z would be very complicated, if at all possible [26]. 153 Instead of exact expressions, simple accurate approximations for the pdf and cdf of Z can be obtained using the first four moments of Z [28, eqs. (4) and (14)] in conjunction with the method outlined in section 8.2. 8.4 N u m e r i c a l R e s u l t s In this section, results are provided to illustrate the accuracy of the approximate cdf curves obtained using Pearson's method. These curves are compared with cdf curves obtained using Monte-Carlo simulation. Figs. 8.1, 8.2 and 8.3 show the cdf and the complementary cdf of the SNR at the output of the MRC, GOSC and GSC receivers respectively for the Weibull channel with L = 3 and different values of and ji as defined in (8.34). The a = [ai a2 atz] and 7 = [71 72 73] values used are listed in Table 8.2. It can be seen that the approximate and simulation curves agree closely in all three figures. Fig. 8.3 shows that the approximate cdf curve is quite insensitive to the number, Nsampies, of samples used to estimate the moments. On the other hand, the simulation cdf curve is quite sensitive to Nsampies. For EGC, we consider L = 2. The a = [aa a2\ and X = [Xi X2] (as defined in (8.45)) values used are given in Table 8.2. Fig. 8.4 shows the cdf and the complementary cdf of the EGC output SNR for dual-branch Nakagami fading channels as described in section 8.3.4. The moments of the E G C output SNR are obtained using [28, eq. (14)]. In this example, significant discrepancies between the approximate and simulation results can be observed at the lower end of the cdf's. Fig. 8.5 shows the average Bit Error Rate (BER) for Binary Phase Shift Keying (BPSK) modulation as a function of the average E G C output SNR over the same fading model as for Fig. 8.4, with X_/X2 = [1.4 1.0]. It can be seen that the approximate cdf from the Pearson method yields reasonably accurate B E R results. 154 8.5 C o n c l u s i o n s In this chapter, the Pearson system of distributions has been used to approximate the pdf's and cdf's of the combiner output SNR's for a number of well-known diversity techniques in Nakagami and Weibull fading channels. Although exact closed-form expressions for some of the distributions are difficult to obtain, relatively simple approximations are shown to be quite accurate. 155 Type A 02 K III 262 - 3A - 6 = 0 ±oo II 0 < 3 0 Gaussian 0 3 0 VII 0 > 3 0 V - 1 Table 8.1: Transition types and associated parameter values. Fig. 8.1 Case 1 a = [4.50 3.30 3.75] 7 = [1.00 2.50 3.85] Case 2 a = [3.00 2.20 2.50] 7 = [1.00 0.40 0.60] Fig. 8.2 a = [2.00 2.00 2.00] 7 = [0.10 0.24 0.08] Case 1 r = 2 Case 2 r = 1 Fig. 8.3 a = [4.00 4.00 4.00] 7 = [0.40 1.00 0.70] Case 1 NsamPles = 4000000 Case 2 Nsampies = 8000 Fig. 8.4 a = [2.00 2.00] p = 0.15 Case 1 X = [1.50 2.25] Case 2 ' ' X = [0.70 0.50] Table 8.2: Parameter values used in Figs. 8.1-8.4. 156 - 2 - 1 0 1 2 3 4 5 Combiner Outpul SNR dB Figure 8.1: Complementary cdf and cdf of MRC output SNR for Weibull fading channels. Figure 8.2: Complementary cdf and cdf of the second and third largest GOSC output SNR for Weibull fading channels. 157 3 3.5 4 4.5 5 5.5 6 6.5 7 Combiner Output SNR dB -2 -1 0 1 2 3 4 5 Combiner Output SNR dB Figure 8.3: Complementary cdf and cdf of GSC output SNR for Weibull fading channels. -10 -8 -6 -4 -2 0 2 4 6 8 10 Combiner Output SNR dB gure 8.4: Complementary cdf and cdf of EGC output SNR for Nakagami fading channels with = 0.15. 158 0 2 4 6 8 10 12 14 16 18 Combiner Output SNR dB Figure 8.5: Average BER for BPSK with EGC over Nakagami fading channels with p = 0.15. 159 References [1] M . K. Simon and M.-S. Alouini, Digital Communication over Fading Channels, 2nd ed. John Wiley k Sons, 2005. [2] K. Pearson, "Contributions to the Mathematical Theory of Evolution. II. Skew Vari-ations in Homogeneous Material ," Philosophical transactions of the Royal Society of London, Series A, vol. 186, pp. 343 - 414, 1895. [3] W. P. Elderton and N. L. Johnson, Systems of Frequency Curves. Cambridge University Press, 1969. [4] A. Stuart and J. K. Ord, Distribution Theory, 6th ed., ser.- Kendall's Advanced Theory of Statistics. Edward Arnold, 1994, vol. 1. [5] B. Schmeiser, "Methods for Modelling and Generating Probabilitic Components in Dig-ital Computer Simulations when the Standard Distributions are not Adequate: A Sur-vey," in Winter Simulation Conference, December 1977, pp. 50 - 57. [6] I. S. Gradshteyn and I. M . Ryzhik, Table of Integrals, Series, and Products. Academic Press Inc., 1980. [7] Q. T. Zhang, "Maximal-Ratio Combining over Nakagami Fading Channels with an Arbitrary Branch Covariance Matrix," IEEE Transactions on Vehicular Technology, vol. 48, no. 4, pp. 1141 - 1150, July 1999. [8] V. A. Aalo, "Performance of Maximal-Ratio Diversity System in a Correlated Nakagami-Fading Environment," IEEE Transactions on Communications, vol. 43, no. 8, pp. 2360 - 2369, August 1995. [9] M . Z. Win, G. Chrisikos, and J. H. Winters, "MRC Performance for M-ary Modulation in Arbitrarily Correlated Nakagami Fading Channels," IEEE Communications Letters, vol. 4, no. 10, pp. 301 - 303, October 2000. ' [10] J. Luo, J. R. Zeidler, and S. McLaughlin, "Performance Analysis of Compact Antenna Arrays with M R C in Correlated Nakagami Fading Channels," IEEE Transactions on Vehicular Technology, vol. 50, no. 1, pp. 267 - 277, January 2001. [11] Q. T. Zhang, "A Generic Correlated Nakagami Fading Model for Wireless Commu-nications," IEEE Transactions on Communications, vol. 51, no. 11, pp. 1745 - 1748, November 2003. [12] H. Hashemi, "The Indoor Radio Propagation Channel," in Proc. of IEEE, vol. 81, July 1993, pp. 943 - 968. [13] F. Babich and G. Lombardi, "Statistical Analysis and Characterization of the Indoor Propagation Channel," IEEE Transactions on Communications, vol. 48, pp. 455 - 464, March 2000. 160 [14] N . S. Adawi et al, "Coverage Prediction for Mobile Radio Systems Operating in the 800/900 MHz Frequency Range," IEEE Transactions on Vehicular Technology, vol. 37, no. 1, pp. 3 - 72, February 1988. [15] N . H. Shepherd, "Radio Wave Loss Deviation and Shadow Loss at 900 MHz," IEEE Transactions on Vehicular Technology, vol. 26, pp. 309 - 313, 1977. [16] G. Tzeremes and C. G. Christodoulou, "Use of Weibull Distribution for Describing Outdoor Multipath Fading ," in IEEE Antennas and Propagation Society International Symposium, vol. 1, 2002, pp. 232 - 235. [17] G. K. Karagiannidis et al, "Equal-Gain and Maximal-Ratio Combining Over Nonidenti-cal Weibull Fading Channels," IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 841 - 846, May 2005: [18] N . C. Sagias, G. K. Karagiannidis, D. A. Zogas, and P. T. Mathiopoulos, "Selection Diversity for Wireless Communications with Non-Identical Weibull Statistics," in Proc. of IEEE Global Telecommunication Conference GLOBECOM 2004, December 2004, pp. 3690 - 3694. [19] R. Kwan and C. Leung, "Downlink Scheduling Optimization in C D M A Networks," IEEE Communications Letters, vol. 8, no. 10, pp. 611 - 613, October 2004. [20] , "Order Statistics for Non-Identically Distributed Nakagami Fading Channels with An Application," in Proc. of IEEE Vehicular Technology Conference (VTC), September 2005. [21] H. M . Barakat and Y . H. Abdelkader, "Computing the Moments of Order Statistics from Nonidentically distirbuted Weibull Variables," Journal of Computational and Applied Mathematics, vol. 117, pp. 85 - 90, 2000. [22] Y . Ma, R. Schober, and S. Pasupathy, "Performance of M-PSK with GSC and EGC with Gaussian Weighting Errors," IEEE Transactions on Vehicular Technology, vol. 54, no. 1, pp. 149 - 162, January 2005: [23] Y . Chen and C. Tellambura, "Performance Analysis of Three-Branch Selection Com-bining over Arbitrarily Correlated Rayleigh-Fading Channels," IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 861 - 865, May 2005. [24] A. Annamalai, C. Tellambura, and V. K. Bhargava, "Equal-Gain Diversity Receiver Performance in Wireless Channels," IEEE Transactions on Communications, vol. 48, pp. 1732 - 1745, October 2000. [25] R. K. Mallik, M . Z. Win, and J. H. Winters, "Performance of M - Q A M with Coher-ent Equal Gain Combining in Correlated Nakagami-m Fading," IEEE Transactions on Communications, vol. 50, pp. 1041 - 1044, July 2002. 161 [26] C.-D. Iskander and P. T. Mathiopoulos, "Performance of Dual-Branch Coherent Equal-Gain Combining in Correlated Nakagami-m Fading," IEE Electronics Letters, vol. 39, no. 15, pp. 1152 - 1154, July 2003. [27] G. K. Karagiannidis, "Moments-Based Approach to the Performance Analysis of Equal Gain Diversity in Nakagami-m Fading," IEEE Transactions on Communications, vol. 52, no. 5, pp. 685 - 690, May 2004. [28] G. K. Karagiannidis, D. A. Zogas, and S. A. Kotsopoulos, "Statistical Properties of the E G C Output SNR Over Correlated Nakagami-m Fading Channels ," IEEE Transactions on Wireless Communications, vol. 3, no. 5, pp. 1764 - 1769, September 2004. 162 Chapter 9 Conclusions and Future W o r k 9.1 S u m m a r y o f C o n t r i b u t i o n s The main contributions of this thesis are summarized below: • The problem of allocating radio resources in the downlink of a C D M A network is studied. The modulation and coding schemes, numbers of multicodes, and transmit powers used for all mobile stations (MS's) are jointly chosen so as to maximize the total transmission bit rate, subject to certain constraints. Based on the discrete and non-linear nature of the proposed model, a mixed-integer non-linear programming optimization problem is formulated. It is found that the optimal allocation generally involves simultaneous transmissions to several MS's. A scheduler which uses knowledge of MS traffic loads is also proposed and shown to yield a significant improvement in throughput. • Analytical expressions are derived for optimal resource allocation in the case of a single MS. Based on the single-MS solution, a sub-optimal, sequential optimization procedure for multiple MS's is presented. Numerical results show that joint optimiza-tion performs noticibly better than the sequential procedure when radio resources are abundant. However, when the MS's are optimally ordered based on their channel con-ditions and/or traffic loads, the sequential solution is an attractive alternative to the more complex joint optimization. • Since the selection of the modulation and coding scheme (MCS) and the number of 163 multicodes requires an estimation of the downlink channel quality, it is important to assess the performance degradation due to estimation errors. It is shown that the throughput is quite sensitive to channel quality estimation errors. The sensitivity can be reduced by using a more conservative estimate of the channel quality. The above analysis does not include any fading statistics. Subsequently, the estimation error analysis is extended to include the Nakagami fading channel model. By modelling the channel dynamics using a Hidden Markov Model (HMM), the impact of channel estimation errors in a system employing A M C and multicodes is studied. Unlike the previous studies, the channels are modelled as discrete states. An H M M filter is used and shown to yield an improved estimate of the channel state. Simulation results show that the H M M filter provides a significant throughput improvement over the unfiltered case, especially when the channel state information (CSI) is quite noisy or the normalized Doppler rate (defined as the product of the Doppler rate of the channel and the transmission period) is small. An expression for the probability density function (pdf) is derived for the ratio, T, of gamma variates of the form T = X\/{a\X\ + a2X2), where a\ and a2 are constants and X\ and X2 are independent gamma distributed random variables. This distribu-tion arises naturally in performance analyses of the downlink on which simultaneously transmitted interfering and desired signals from the same base station normally un-dergo the same fade. The result is used to analyze the performance of a downlink C D M A system involving A M C and multicodes. Exact closed-form results for general order selection (GOS) over independent but not necessarily identically distributed (i.n.d.) Weibull and Nakagami fading channels are presented. The GOS model is important in performance analyses of multiuser schedul-ing, where the statistics of ranked channel conditions are desired. Exact closed-form expressions for the symbol error rate are obtained for a number of modulation schemes. 164 Numerical results show that for the same average channel gains, the performance on i.n.d. channels may be better or worse than on i.i.d. channels. • The Pearson system of distributions is examined as a means to approximate statistical distributions which are often difficult to derive in closed-form. The usefulness of this approach is illustrated for a number of diversity techniques employed on Nakagami and Weibull fading channels. The resulting relatively simple approximations are shown to be quite accurate. 9.2 F u t u r e W o r k In a W C D M A network, the High Speed Downlink Shared Channel (HS-DSCH) is designed to carry packet data from the radio access network to the user. Although most research efforts so far have been devoted to "best effort" packet services, the HS-DSCH is also intended to support other kinds of applications' such as interactive and streaming traffic [1]. If a shared channel is used to carry real-time traffic, the delay and jitter requirements have to be much more stringent. As a result, the study of delay sensitivity issues on the shared channel is very important. A number of articles have addressed the problem of scheduling delay-sensitive traffic [2]-[13]. In [12], the issue of delay-sensitive scheduling in W C D M A networks is investigated. In this work, real-time data are sorted based on their deadlines, and those with the earliest deadline are given a higher priority for transmission. However, the authors do not take into account the buffer content sizes, and resources are not jointly optimized for multiple users. In [13], a general structure of opportunistic scheduling policies is presented, which exploit channel and/or buffer content variations for achieving the required QoS. Subsequently, the performance is compared for a number of special but well-known cases of the general policy. According to the 3GPP specification [14, 15, 16], the shared channel such as the HS-DSCH in W C D M A does not operate in isolation. It is only designed to be an advanced 165 alternative to the more traditional dedicated channel in the downlink. The HS-DSCH does not employ fast power control to compensate for channel variations. Instead, to maximize the throughput in the downlink, the data rate is adjusted to match the instantaneous channel condition. In contrast to the HS-DSCH, the dedicated channels are designed to maintain a constant data rate by means of fast power control. Such an arrangement allows the dedicated channels to be natural candidates for voice services [16]. In addition, the dedicated channels have the diversity advantage of soft-handover, which is not present in the shared channels. Figure 9.1 shows the relationship between the dedicated and the shared channels. Since both the shared and dedicated channels require power and code resources, it is important to allocate these resources to both types of channels efficiently. It has been shown in [17] by simulations that HS-DSCH can increase the system throughput significantly due to the fact that less reservation of power control headroom is required for HSDPA. However, both power and code resources are assumed to be statically allocated. In [18], the dedicated channels, i.e. the voice traffic, are given a higher priority over the shared channel in terms of the power allocation. On the other hand, the maximum code resource for the shared channels is assumed to be fixed. Since the dedicated and shared channels are competing for resources, any resources al-located to the shared channel has a direct impact upon the performance of the dedicated channels, and vice versa. If the maximum allowable power and code resources allocated to the dedicated and shared channels are dynamically changed based on the traffic load and the channel conditions, a significant performance gain might be achieved. The following summarizes some of the possible topics for future study: • The issue of resource-sharing between the shared and the dedicated channels can be investigated. To optimally allocate the maximum allowable power and code resources dynamically between the shared and the dedicated channels is important from the radio resource management point of view. By carefully selecting the maximum allowable resources, a relatively small sacrifice of the shared channel performance could result in 166 CO •__\ la o //«(// i i i fill 00« 1 User Shared Channels Dedicated Channels Time Figure 9.1: Cooperation between the dedicated and the shared channels, a significant improvement in the performance of the dedicated channel and vice versa. • A new optimization model may address the issues of jointly minimizing the amount of power and code resources in the context of shared and dedicated channels, when both real-time and non-real-time traffic are present. • It would be useful to examine the possibility of incorporating the technique of O F D M into the current model involving A M C , downlink transmit power, and multicodes. This would add an extra degree of freedom in the optimization procedure. • The effects of channel estimation errors on the ranked SNR statistics in the context of general order selection diversity should be examined. • The analysis of general order selection diversity discussed in this thesis is based on user channel conditions. However, if the selection also includes the amount of user data in the buffer, or the packet delays, the statistics of the resulting selection criterion would 167 be more complicated. The derivation of the statistics for such a selection criterion is an interesting problem. By incorporating the statistical distribution of the downlink received SIR, stochastic optimization models can be developed in order to take into account the uncertainties of the system, which are often more realistic in practice. 168 References [I] "Physical Layer Aspects of U T R A High Speed Downlink Packet Access," 3rd Generation Partnership Project, Technical Report 3G TR25.858, 2002. [2] Z. Gao and S. Q. L i , "A Packet Scheduling Scheme in Wireless C D M A Data Network," in Proc. of IEEE International Conference on Communications, Cicuits, and Systems, and West Sino Expositions, vol. 1, June 29 - July 1 2002, pp. 211 - 215. [3] M . Andrews, K. Kumaran, K. Ranaman, A. Stolyar, and P. Whiting, "Providing Quality of Service over a Shared Wireless Link," IEEE Communications Magazine, vol. 39, no. 2, pp. 150 - 154, February 2001. [4] M . Kazmi, P. Godlewski, and C. Cordier, "Admission Control Strategy and Scheduling Algorithms for Downlink Packet Transmission in W C D M A , " in Proc. of 52nd IEEE Vehicular Technology Conference, VTC'OO, vol. 2, September 2000, pp. 674 - 680. [5] N . Joshi, S. R. Kadaba, S. Patel, and G. S. Sundaram, "Downlink Scheduling in C D M A Data Network," in Proceedings of the 6th annual international conference on Mobile computing and networking, 2000, pp. 179 - 190. [6] P. Liu, R. Berry, and M . L. Honig, "Delay-Sensitive Packet Scheduling in Wireless Net-works," in IEEE Proc. of Wireless Communications and Networks Conference WCNC, vol. 3, 16-20 March 2003, pp. 1627 - 1632. [7] K. Chang and Y . Han, "QoS-Based Adaptive Scheduling for a Mixed Service in HDR System," in The 13th IEEE International Conference on Personal, Indoor and Mobile Radio Communications (PIMRC), vol. 4, 15-18 Sept. 2002, pp. 1914 - 1918. [8] S. Shakkottai and A. L. Stolyar, "Scheduling Algorithm for a Mixture of Real-Time and Non-Real-Time Data in HDR," in Proc. of MIT Information Technology Conference (ITC), November 2001. [9] S. Shakkottai and R. Srikant, "Scheduling Real-Time Traffic With Deadlines over a Wireless Channel," Wireless Networks, Kluwer Academic Publishers, vol. 8, no. 1, pp. 13 - 26, August 2002. [10] "Streaming support for HSDPA," Siemens, Sophia Antipolis, France, Technical Docu-ment R2-022882, 12-15 November 2002, 3GPP TSG-RAN2 meeting 33. [II] P. Hosein, "Capacity of Voice Services over Time-Shared Wireless Packet Data Chan-nels," in Proc. of IEEE INFOCOM, March 2005, pp. 2032 - 2043. [12] E. H. Kuang and H. W. Chang, "A QoS-based Hybrid Multiple Access Transmission Strategy in W C D M A Downlink," in Proc. of IEEE Wireless Communications and Net-working Conference WCNC, vol. 3, March 2003, pp. 1685 - 1690. 169 [13] A. Farrokh, F. Blomer, and V . Krishnamurthy, "A Comparision of Opportunistic Scheduling Algorithms for Streaming Media in High-Speed Downlink Packet Access (HSDPA)," in Proc. of Interactive Multimedia and Next Generation Networks: Second International Workshop on Multimedia Interactive Protocols and Systems, MIPS, ser. Lecture Notes in Computer Science, vol. 3311. Springer, November 2004, pp. 130 -142. [14] H. Holma and A. Toskala, Eds., WCDMA for UMTS Radio Access for Third Generation Mobile Communications. John Wiley & Sons, 2002. [15] Http://www.3gpp.org. [16] S. Parkvall, E. Englund, P. Malm, T. Hedberg, M . Persson, and J. Peisa, "WCDMA evolved - High-speed packet-data services ," Ericsson Review, no. 2, pp. 56 - 65, 2003. [17] K. I. Pedersen, T. F. Lootsma, M . St0ttrup, F. Frederiksen, T. E. Kolding, and P. E. Mogensen, "Network Performance of Mixed Traffic on High Speed Downlink Packet Access and Dedicated Channels in WCDMA," in Proc. of IEEE Vehicular Technology Conference (VTC), vol. 6, September 2004, pp. 4496-4500. [18] A. Furuskar, S. Parkvall, M . Persson, and M . Samuelsson, "Performance of W C D M A high speed packet data," in The 55th IEEE Proc. of Vehicular Technology Conference (VTC), vol. 3, May 2002, pp. 1116 - 1120. 170 A p p e n d i x A Linear iza t ion of the M I N L P models A . l A s s i g n e d B i t R a t e B a s e d M o d e l In this appendix , it is shown that we can linearize the MINLP problems for both the basic and load-based models. Solving the linearized versions to obtain the results in section 2.3.3 in a 1.7 GHz personal computer with 384 MBytes of R A M was found to take much less time (typically a factor of 7) than the non-linearized version. Using the substitution, rriij = dijUi (A.l) Kij = Xij{aPT + J2 hhki/hi + IN/hi). (A.2) fcetf the MINLP problem in (2.5) can be transformed to an equivalent mixed-integer linear prob-lem as ( L J mgx \ J2 23 mij ra -v(> (A-3) a,P,n [ i = l j = 1 J subject to linear constraints 1....J (A.4) (A.5) (A-6) (A.7) e {0,l},Vi = l , . . . ,L,\/j J = I Hi < N- V? = 1 ...,L L 2 > i < N i = l 171 £ P i < Pmax (A-8) i=l j^mijKii < Pu Mz = l,...,L (A.9) "T-ij < ™i, Vi = 1, Vj = 1,...,J (A.10) m.jj ^ ^ i , m a x ^ i j i Mi = Vj = l , . . . , J (A . l l ) Mi = 1,...,L, Vj = l , . . . , J (A.12) m y > 0, Vz = 1,...,L, Vj = l , . . . , J (A.13) A.2 L o a d - B a s e d M o d e l Using the substitution Yi = Y.m^/W, (A.14) the MINLP problem in (2.15) can be transformed into an equivalent mixed-integer linear problem as max < U — v }, (A. 15) a P n Uti J subject to the constraints (A.4) - (A.13), together with U < A , Mi = l,...,L (A.16) U + Mt'i > Di, Mi = \,...,L (A.17) U < Yh Mi = l,...,L (A.18) 172 U + Mt'l > Yi, Vi = l , . . . , L .(A.19) ti + t! = 1, Vi = l , . . . , L (A.20) Wl G {0,1}, Vi = l , . . . , L . (A.21) where M £ TZ+ and M » 0. 173 A p p e n d i x B P r o o f of Theorems and Clarif ications in Chapter 3 B . l P r o o f o f t h e o r e m 3.1 Proof: The extrema of Rij(Xij) can be obtained by setting dRiij(Xiij)/dXij = 0. Thus, IMhA = ri]1.J^(l^MhA\ ( B . i ) dXij ' dXij y Xij J r „ f Kit1 ~ ZijiKj))' ~ I 1 ~ tiAKj)) \ /o n\ = TijJii - ^ j - ; > (B.2) = 0 (B.3) = • CijiXij) - KAA^J) - 1 = 0 (B-4) To determine which solution in (B.4) is a maximum, we need the second derivative of Rij(Xij), which is given by d2Rij(Xij) _ d2 /1 — Ci,j(Xjj) dXfj •' dXfj \ X^j t j . . J -KAAKJ) + 2 A ^ ( A y ) + 2 ^ ( 1 - ejjjXjj)) } ' ^ to be negative. Substituting (B.4) into (B.6), we require 174 to be negative, i.e. < , ( A i r } ) >0. (B.8) B . 2 P r o o f o f T h e o r e m 3.2 Proof: We assume that the link-level error rate curve ti,j{x) can be modelled by a sigmoid function, i.e. Ci.-fx) = r, x>0 (B.9) where {ax,a2} £ 7l+ and a 3 G 71 are constants. From Theorem 3.1, an optimal solution should satisfy eij(x) — xe'ij(x) — 1 = 0, where -a1a2ea2(-x-a3) € i ' j [ X > ~ (1 + axea^x-a*))2 (B.10) Thus, we have 1 + a i e a 2 ( ^ - a 3 ) • (1 + a i e a 2 ( x - a 3 ) ) 2 (1 + aie a 2 ( x - a 3 )) + xaxa2ea^x~a3) = 0 (B.12) -(1 + a i e a 2 ( x - Q 3 ) ) 2 (1 + axea^x-a^) + xaia2ea^x-a^ = 0 (B.13) -(1 + 2axea^x-a^ + a 2 e 2 a 2 ( x - a 3 ) ) a 2x - aie° 2 (*-° 3) = 1. (B.14) 175 To isolate x, further algebraic manipulations give a2x = aiea2Xe~a2a3 + 1 (B.15) e~a2X(a2x) = aie-a2a:i + e-a2X (B.16) e - a 2 X + l { _ a 2 X + l ) = _aie-a2a3 + l ( B 1 ? ) -a2x + l = W ( - a i e - a 2 a 3 + 1 ) (B.18) W (-a1e-a2a3+1 - 1 X = ' <B"19> where the function W(.) is called Lambert W function, and is defined to be the multivalued inverse function of w i—• wew. According to [1], if u is real, then for — 1/e < u < 0, there are two possible values of W(u). As shown in Fig. B . l , the branch satisfying — 1 < W(u) is usually denoted as W0(u), while the branch corresponding to W(u) < —1 is usually given as W-i(u). On the other hand, if u is real, and u > 0, then W(u) only has a single value. Now, since — aie~a2a3+1 < 0, if real solutions exist, they must take on values x0 and x_i corresponding to the branches 0 and —1 respectively. In order for real solutions to exist, - e " 1 < - a i e - a 2 a 3 + 1 (B.20) a i e - a 2 a 3 + i < e - i (B.21) e l -a 2 0 3 +ln (a i ) < g - l (g 22) 1 - a 2 a 3 + ln(ai) < - 1 . (B.23) Now, according to Theorem 3.1, in order to maximize Rij, the solution(s) given in (B.19) should lie in the region such that e"j(x) > 0. In other words, e'l^x) > 0 2a\a22e2aAx~a^ axa\ea2{x-a3) (1 + a 1 e a 2( a ; - a 3 ) )3 (1 + a i e a 2 ( x - a 3 ) ) 2 > a i e a 2 ( x - a 3 ) _ 1 > 0 176 (B.24) (B.25) (B.26) a2x > ln(l /ai) + a 2 a 3 1 + ln(ai) — 0,2(13 > 1 — a2x. (B.27) (B.28) Using (B.28), (B.23) and (B.18), we have — 1 > 1 — a2x -1 > W ( - a i e - a 2 a 3 + 1 ) . " (B.29) (B.30) Thus, (B.30) shows that in order to maximize Rij, the optimal solution should lie in branch — 1, which is uniquely given by X-i = (-a1e~a2a3+l) - 1 -a2 (B.31) 1 1 1 i -1 /e Real Branch - 1 Real Branch 0 \ \ s \ \ \ \ \ \ \ \ i i r - 3 0.5 1 X Figure B . l : Lambert W function. The dotted line corresponds to the real branch -1, while the solid line corresponds to the real branch 0. 177 B . 3 P r o o f o f t h e o r e m 3.3 Proof: From Theorem 3.2 it is known that AJJ^ is the unique value which corresponds to a maximum of Rij(Xij). Thus if there exists a value of Xij such that Xij > AJJ^ and i?i,-(Aj,-) > 0, lim Ri,j{Xij) will be unbounded. However, this contradicts the fact that lim Ri,j(Xij) = 0 as can be seen from the first part of (3;4). Hence, Rij(Xij) decreases monotonically with Xij for Xij > X\jpt\ • B . 4 R e l a t i o n s h i p b e t w e e n of^ a n d Oi The relationship between the standard deviation of the Gaussian distribution and that of the truncated version is now obtained. Let the pdf of the truncated Gaussian random variable be _ J L _ p - 0 ? 4 / 2 a J : f Q > 1 (B.32) where the constant Cp is given by - 1 1 a 0y> = f -jL-e-KJ^d^ (B.33) The standard deviation of the truncated Gaussian is given by °?] = v ^ J - W ^ . (B.35) where 31 EK] = r ^ e - ^ l ^ d P l i + {-lfC^ (B.36) J-l x/Z-KGi 178 -0l/v°2i) J -1 27T(7j o 2 e- 1 / { 2 o-Z.\lZ erfc (B.37) (B.38) /OO -1 ?^e-WU3li + (-l)C01i Ziro~i -1 2TT a i e - ^ / ( 2 - 2 ) + (-i)c^ J - l (B.39) (B.40) (B.41) 179 A p p e n d i x C Der iva t ion of the integral i n (4.28) To simply notations, let C\ = 0^(7) , k x = nci, and a = Kj + e. The objective is to evaluate the integral / = [°° e - k ^ % ^ ) d 7 , ( C l ) Ja m - l _ f°° -kxlh m (2L\ 2 - J a e ( l - p ) r U ; x / 2my7>n\ ( m(frf + j)\ /•oo Ja (T 1 e 7 ^(l-p)r' 1 (i-p)r x (1 - P)T m—1 m — 1 where A\ and A2 are given by 7 ( i - p ) r Letting z = A 2 7 , and, subsequently, z = q2/2, (CA) becomes poo I = Ai m — 1 PI 180 \~(T=W-j A ~ > d z (C.7) r'W9 e 2 7™-i(^3?Mg ( C 9 ) 13" ^ ^ 2 ^ ( m - l ) m 1 2 . - i=±li (i-p)r \2frf e - A M 3 n - 1 Q m (^3 , v / 2A 2 ^) (CIO) where A 3 and b are given by A , = ( c„) ( 1 - P)r 2m2 py2 \ (l-^fcia-^f+ m 7 ) (C.12) * - Wi W 1r\ - ( a i 3 ) fci(l - p)T + mj and Qm(.) is the generalized Marcum Q-function defined in (4.29). Substituting (C.6), (C . l l ) , and (C.13) into (C.10), and after some algebraic manipulations, (C.10) becomes / = ( m \ Y c ( pkxTnJ \ x [k^l - p)F + my) W \ ki(l - p)? + mi) Qn 2/9m 2 7 2 ^Til-p^hil-p^ + mj) which is identical to the integral in (4.30). (C.14) 181 A p p e n d i x D Opt ima l i t y w i t h an integer number of multicodes The problem of choosing the optimal MCS and number of multicodes for a given SIR amounts to a discrete optimization problem. This problem is usually difficult and not amenable to an analytical solution [2]. In [3], it was possible to derive an analytical solution for the optimal bit rate for a single user by assuming that the number of multicodes is a real value. The solution may not be optimal if the number of multicodes is an integer. Fig. D . l shows the bit rate as a function of SIR for MCS i and MCS j assuming integer and continuous multicodes. In this figure, MCS j is assumed to provide the highest bit rate among all MCS's when the multicodes are assumed to be take on continuous values. When the discrete multicode model is obtained by applying the floor function as in (6.55), a series of staircases is generated. Since the staircases can potentially overlap each other, especially in the low SIR region, the bit rate for MCS j may no longer be optimal over the entire SIR region. Let \(k + — Alk+ij, (k + l)Aj], k = 1,..., Nmax be the intervals within which the bit rate corresponding to MCS i with a continuous number of multicodes exceeds that corresponding to MCS j with an integer number of multicodes. Fig. D . l shows that this occurs when (A; + l)Xj - Alk+ij < k'Xi <{k + 1)A,-, k = 1,..., Nmax, k' = l,..., Nmax, Vi ± j. (D.l) The bit rate results presented in this paper do not satisfy (D.l), and are, therefore, optimal. 182 Figure D . l : The bit rate as a function of SIR for MCS i and MCS j assuming an integer and a continuous number of multicodes. 183 Appendix E Derivation of (7.17) Using [4, page 940, 8.352.1], the term 1 - F/U(y) in (7.8) can be expanded as = i'-fkr^'&f} (E1) V A« / m = o \ A« / m! In (7.9), the term Q£_ g + 2 (y ) = Il£=L_,+2(l - Fiu(v)) can be re-written as - g+2vyj = exp j - ^ ^ 11 — • L p - E =L-q+2 = E ••• E 771^ =0 yEt' = l"V exp (E.3) x E 6 ( ,v), (E-4) \ t'=L-q+2 J where £/u = aiu//3iu and a; u is assumed to take on integer values. Using the result for the first order statistics [5], together with some algebraic manipulations, the term P 2 L ~ 9 + 1 (y) = Il j=2 9 + 1 Fijiv) c an be expressed as L-q a ' n 1 - 1 a i n k ~ l Ptq+\y) = E ( - i ) * E E ••• E /c=0 2<ni<...<nfc<L—g+1 mi=0 m,k=0 / k fc / k \ ( n ^ ) y ^ - a x p ( - g ^ , ) . (E.5) Substituting (E.4) and (E.5) into (7.9), the desired result follows. 184 A p p e n d i x F Der iva t ion of (8.15) and (8.31) F . l D e r i v a t i o n o f (8.15) Let z' = z — A . The pdf in (8.12) can be expressed as fz,(z') = K0(l + f )*(1 - T ) 6 \ -h<z'<b2 (F.l) Furthermore, let w = l + (z'/b1),p = 1 + (bx/b2), and p' = h/b2, Fz,(z') = £' fz>(z')dz' becomes r l + ( u ' / 6 i ) 10 -bx <u' <b2 (F.2) / • l ( ' lFz,(v!) = / KQbxwex{p-p'w)e2dw, JoLetting I = p'/p, w' = Iw, and x(u') = 1(1 + (u'/bi)), Fz>(u') becomes Fz,(u>) = r{u'] bxK0peH-^ x Jo w'9l(l - w')e2dw', -bx<u' <b2 (F.3) = b1K0pd2r^Bx{u,)(91 + 1,02 + 1) (F.4) Finally, letting vl — u — A , the result follows. 185 F.2 Der iva t ion of (8.31) Let z' = z — A and t' = t — A , the cdf of (8.24) can be written as Fz[t') = f K0(z'-a)e*(z')-eidz' (F.5) - / > ° m ( H f e ( £ T ° v (R6) Furthermore, let u = a/z', we have Fz(t')= J%a^ ( i - l ) 2 ( i ) " ( - a u - 2 ) d u (F.7) = / ' #oa 0 2 ~ 0 1 + 1 ( l - u ) 0 2 n e i - e 2 - 2 r i ^ (F.8) v = 1 - [f K0ae^+1(l - u)e*ue>-e*-2du (F.9) Jo Using the definition of the incomplete beta function [4], the desired result follows. 186 References [1] R. M . Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, "On the Lambert W Function," Adv. Comput. Math., vol. 5, pp. 329 - 359, 1996. [2] R. Kwan and C. Leung, "Optimal Downlink Scheduling Schemes for C D M A Networks," in Proc. of IEEE Wireless Communication and Networking Conference (WCNC), At-lanta, Georgia, March 2004. [3] , "Channel-Based Downlink Scheduling Schemes for C D M A Networks," in Proc. of IEEE Vehicular Technology Conference (VTC), Los Angeles, California, September 2004. [4] I. S. Gradshteyn and I. M . Ryzhik, Table of Integrals, Series, and Products. Academic Press Inc., 1980. [5] R. Kwan and C. Leung, "Selection Diversity in Non-Identically Distributed Nakagami Fading Channels," in Proc. of IEEE Sarnoff Symposium, Princeton, New Jersey, April 2005. 187
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Downlink scheduling optimization and performance analysis...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Downlink scheduling optimization and performance analysis over fading channels in a CDMA network Kwan, Raymond 2006
pdf
Page Metadata
Item Metadata
Title | Downlink scheduling optimization and performance analysis over fading channels in a CDMA network |
Creator |
Kwan, Raymond |
Date Issued | 2006 |
Description | Due to technological advances in mobile communications, together with the explosive growth of internet access, transmitting multimedia applications over wireless channels is no longer a remote concept. In third generation (3G) multimedia CDMA networks, a variety of techniques will be used to meet the quality of service (QoS) requirements for various types of traffic. These include adaptive modulation and coding (AMC) which improves performance by adapting the employed modulation and coding scheme (MCS) to changing channel conditions and multicode transmission which provides higher bit rates to mobile stations (MS's). The problem of allocating radio resources in the downlink of a CDMA network is first studied. In particular, the modulation and coding schemes, numbers of multicodes, and transmit powers used for all MS's are jointly chosen so as to maximize the total transmission bit rate, subject to certain constraints. In addition, a scheduler which uses knowledge of MS traffic loads is also proposed and shown to yield a significant improvement in throughput. The proposed multiuser schedulers are optimal in terms of system throughput. However, the implementation complexity can be high. Consequently, a suboptimal scheme is proposed, in which resources are allocated sequentially on a per-MS basis. Essentially, the sequential scheme reduces the problem of multiuser resource optimization to a single user problem, thereby greatly reducing complexity. Numerical results show that the performance of the sequential scheme is generally close to optimal if the MS's are ordered optimally. The thesis also addresses the problem of downlink single user scheduling in the context of AMC and multicodes with imperfect channel estimation. Since the selection of MCS and number of multicodes requires an estimation of the downlink channel quality, it is important to assess the performance degradation due to estimation errors. It is shown that the system throughput is quite sensitive to channel estimation errors, and methods are proposed to reduce the resulting degradations. In multiuser scheduling, the aim is to select users with good channel conditions so as to improve the system performance. The selection process is a classical problem in the theory of order statistics. Since users are generally located in different parts of a cell, their respective channels can often be assumed independent, but their fading statistics are not necessarily identical. In this thesis, some useful general results assuming independent and non-identically distributed (i.n.d.) order statistics over the Nakagami and Weibull fading channels are derived. The thesis also proposes a new statistical distribution for the CDMA downlink signal-to-interference ratio given that the simultaneously transmitted interfering and desired signals from the same base station undergo the same fading process. Finally, a simple method for approximating complex statistical distributions which arise in the study of wireless communications is investigated. The resulting relatively simple approximations are shown to be quite accurate. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0065608 |
URI | http://hdl.handle.net/2429/18252 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2006-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2006-130121.pdf [ 7.38MB ]
- Metadata
- JSON: 831-1.0065608.json
- JSON-LD: 831-1.0065608-ld.json
- RDF/XML (Pretty): 831-1.0065608-rdf.xml
- RDF/JSON: 831-1.0065608-rdf.json
- Turtle: 831-1.0065608-turtle.txt
- N-Triples: 831-1.0065608-rdf-ntriples.txt
- Original Record: 831-1.0065608-source.json
- Full Text
- 831-1.0065608-fulltext.txt
- Citation
- 831-1.0065608.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065608/manifest