Some Cross-Layer Design and Performance Issues in Wireless Networks by M d . Jahangir Hossain M . A . S c , The University of Victoria, Victoria, B C , 2003 B . S c , Bangladesh University of Engineering and Technology, 2000 A THESIS S U B M I T T E D I N P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Doctor of Philosophy in The Faculty of Graduate Studies (Electrical and Computer Engineering) The University Of British Columbia October, 2007 © M d . Jahangir Hossain , 2007 Abstract Present and future generation wireless systems are designed to support a wide variety of services, including video conferencing, media streaming, Internet access, email transfer, remote file access and web-browsing. Different applications have different traffic charac-teristics and quality of service (QoS) requirements. These QoS parameters include delay constraint, packet loss rate (PLR) and packet error rate (PER) requirement. For example, depending on the throughput or delay requirements of the services, wireless data services have already been classified as guaranteed or best-effort services. Mobi le wireless links are time-varying in nature and error prone. In addition, communication resources, e.g., transmit power and bandwidth, are scarce. Through a cross-layer design approach, these inherent quality parameters of different services can facilitate efficient use of limited com-munication resources. In particular, the relative delay tolerance of data applications, in conjunction with the bursty activity patterns and time-varying nature of the wireless chan-nels, opens up the possibility of scheduling transmissions to efficiently allocate limited wireless communication resources. The main contribution of this dissertation is the design of innovative scheduling schemes through cross-layer design approach that jointly considers the time-varying nature of wire-less channels as well as the required QoS parameters of different services. This disser-tation makes four major contributions, as follows. First, we develop modulation-assisted two-user opportunistic scheduling schemes. The novelty of the proposed schemes is im-proved delay performance and fairness for the serviced users in wireless networks without degradation of the system spectral efficiency (SE), compared with the classical single best user scheduling (SBS) scheme. Second, we develop an adaptive scheduling protocol for multi-resolution image/video data transmission over time-varying channels. The protocol is optimized for real-time multi-resolution data transmission in order to maintain a given quality of the received multi-resolution data. Third, we devise a novel variance-bounded rate adaptation ( V B R A ) scheme for delay-constrained communications. We explore an ap-i i plication of the proposed V B R A scheme for media streaming over time-varying channels in order to minimize the transmit power while maintaining a low play-out buffer outage probability. Fourth, we develop link adaptation algorithms for a multicarrier system for generalized delay-constrained communication over time-varying channels. i i i Table of Contents A b s t r a c t i i T a b l e o f C o n t e n t s iv L i s t o f T a b l e s x L i s t o f F i g u r e s x i L i s t o f A b b r e v i a t i o n s xv A c k n o w l e d g e m e n t s xv i i i D e d i c a t i o n xix S t a t e m e n t o f C o - A u t h o r s h i p xx 1 I n t r o d u c t i o n 1 1.1 General Background and Motivation 2 1.1.1 Opportunistic scheduling 2 1.1.2 Multi-resolution image/video data transmission 4 1.1.3 Link adaptation for OFDM-based systems 5 1.1.4 Variance-bounded rate adaptation for delay-constrained communi-cations 7 1.2 Thesis Outline 8 B i b l i o g r a p h y 9 2 M u l t i - U s e r O p p o r t u n i s t i c S c h e d u l i n g U s i n g P o w e r - C o n t r o l l e d H i e r a r c h i c a l C o n -s t e l l a t i o n s 12 iv 2.1 Multi-User Opportunistic Scheduling 13 2.1.1 Hierarchical constellations 13 2.1.2 Hierarchical constellation-based multi-user opportunistic schedul-ing 16 2.1.3 Comparison with uniform Q A M constellation-based scheme . . . . 17 2.2 Performance Analysis and Results 17 2.2.1 Outage probability 18 2.2.2 Average transmit power 19 2.2.3 Buffer density and packet loss probability . . 21 2.3 Conclusion 24 B i b l i o g r a p h y 26 3 R a t e A d a p t i v e H i e r a r c h i c a l M o d u l a t i o n - A s s i s t e d T w o - U s e r O p p o r t u n i s t i c S c h e d u l -i n g 28 3.1 Channel Model and Hierarchical Constellations 29 3.1.1 Channel model 29 3.1.2 Hierarchical constellations 30 3.2 Two Best-User Opportunistic Scheduling 32 3.2.1 General assumptions 32 3.2.2 Overall system description 32 3.2.3 Rate adaptation process 33 3.3 Performance Analysis 39 3.3.1 Average spectral efficiency 39 3.3.2 Access probability 43 3.3.3 Effect of constellation parameter 45 3.4 Conclusion 48 B i b l i o g r a p h y 49 4 T w o - U s e r O p p o r t u n i s t i c S c h e d u l i n g u s i n g H i e r a r c h i c a l M o d u l a t i o n s i n W i r e -l e s s N e t w o r k s w i t h H e t e r o g e n o u s A v e r a g e L i n k G a i n s 50 4.1 System and Channel Models 51 v 4.2 Classical Single User Scheduling: Overview 52 4.2.1 Absolute CNR-based single best user scheduling 52 4.2.2 Normalized CNR-based single user scheduling 52 4.3 Proposed Two-User Opportunistic Scheduling 53 4.3.1 Two-best user scheduling 53 4.3.2 Newly proposed hybrid two-user scheduling 55 4.4 Performance Analysis 56 4.4.1 Two-best user scheduling 56 4.4.2 Hybrid two-user scheduling 60 4.4.3 Single user scheduling 61 4.5 Numerical Results 63 4.6 Conclusion 65 B i b l i o g r a p h y 67 5 Q u e u i n g D e l a y a n d B u f f e r D i s t r i b u t i o n o f T w o - U s e r O p p o r t u n i s t i c S c h e d u l i n g S c h e m e s i n W i r e l e s s N e t w o r k s 68 5.1 Overall System Description and Two-User Scheduling Schemes 69 5.1.1 Rate adaptive hierarchical modulation-assisted T B S scheme . . . . 69 5.1.2 Rate adaptive hierarchical modulation-assisted H T S 71 5.2 Formulation of the Queueing Model 72 5.2.1 Markov chain analysis 72 5.2.2 Matrix-analytic solution for steady state distributions 77 5.2.3 Derivation of performance measures 77 5.3 Comparison with Classical Single User Scheduling 79 5.4 Numerical Results 80 5.4.1 I.I.D. fading environment 80 5.4.2 I .N.D. fading environment 81 5.4.3 Simulation results for M M P arrival process 85 5.5 Conclusion . 89 B i b l i o g r a p h y 93 vi 6 H i e r a r c h i c a l C o n s t e l l a t i o n f o r M u l t i - R e s o l u t i o n D a t a T r a n s m i s s i o n o v e r B l o c k -F a d i n g C h a n n e l s 94 6.1 System and Channel Models 95 6.1.1 Overall system description 95 6.1.2 Hierarchical 4 / 1 6 - Q A M 96 6.1.3 General assumptions 98 6.1.4 Channel model 99 6.2 Proposed Protocol 101 6.2.1 Protocol description 101 6.2.2 Protocol modelling 103 6.3 Performance Analysis 106 6.3.1 Average packet loss rate 107 6.3.2 Average packet transmission rate 108 6.4 Numerical Results 109 6.4.1 Average packet loss rate 109 6.4.2 Average packet transmission rate 113 6.5 Real-time Multi-Resolution Data Transmission over Correlated Fading Chan-nels 115 6.5.1 Overall system description 116 6.5.2 Problem formulation 120 6.5.3 Power-distortion model 122 6.5.4 Results 123 6.6 Conclusion 124 B i b l i o g r a p h y . . . 126 7 L i n k A d a p t a t i o n f o r O F D M S y s t e m s f o r D e l a y - C o n s t r a i n e d C o m m u n i c a t i o n o v e r C o r r e l a t e d F a d i n g C h a n n e l s 128 7.1 System Model 129 7.1.1 Channel models 130 7.1.2 Incoming traffic model 131 7.1.3 Adaptation model 132 7.2 Scheduling Algorithms 134 v i i 7.2.1 Problem formulation 134 7.2.2 Optimal scheduling 138 7.2.3 Suboptimal algorithm 141 7.3 Effect of Correlation among Subcarriers' Fading Gains 148 7.3.1 Channel and rate allocation model 148 7.3.2 Rate allocation with no delay constraints 149 7.3.3 Rate allocation with hard delay constraints 151 7.4 Conclusions 153 B i b l i o g r a p h y 155 8 V a r i a n c e - B o u n d e d R a t e A l l o c a t i o n f o r C o n s t a n t R a t e M e d i a S t r e a m i n g . . . 157 8.1 System Model 158 8.2 Variance-Bounded Rate Allocation 160 8.3 Constant Rate Play-Out under the Receiver Buffer Outage Probability Con-straint 163 8.3.1 Overall description 164 8.3.2 Joint PDF methodology for calculation of the receiver buffer out-age probability 165 8.3.3 Diffusion approximation for calculation of the receiver buffer out-age probability 166 8.3.4 Results ... 169 8.4 Conclusions 171 B i b l i o g r a p h y 172 9 C o n c l u s i o n 173 9.1 Future Research Challenges 176 9.1.1 Opportunistic subcarrier allocation for OFDM-based system . . . .176 9.1.2 Designing multiple-best user scheduling scheme 176 9.1.3 Rate adaptation for hybrid ARQ-based system for real-time multi-resolution data transmission 177 9.1.4 Hybrid policy for media streaming over fading channels 177 viii 9.1.5 Effect of imperfect channel state and slow adaptation for time chan-nels 177 Appendices 179 Appendix A 179 Appendix B 181 ix List of Tables 6.1 Significance of the scheduling states 104 x List of Figures 2.1 Hierarchical 4 / 1 6 - Q A M constellation 14 2.2 Normalized (by NQ) average transmit power versus the number of users. . . 20 2.3 Markov chain representation of the buffer dynamic with power-controlled modulation-assisted two-best user scheduling 22 2.4 Buffer distribution and average buffer occupancy level 23 2.5 Packet loss probability versus packet arrival probability 24 3.1 Hierarchical 4 / 6 4 - Q A M constellation 30 3.2 System model of B S scheduler 33 3.3 Flow chart of proposed rate adaptive modulation-assisted T B S scheme. . . 35 3.4 Example: Joint C N R s to constellation mapping 38 3.5 Overall S E versus number of users (SE curves for single and two-best user scheduling overlap) 44 3.6 Information access probability versus number of users 44 3.7 Average SE versus priority parameter p (gQ = 15[dB]) 46 3.8 Second best user information access probability versus priority parameter p (g0 = 15[dB]). 47 4.1 Average system's fairness versus number of users 64 4.2 Link spectral efficiency versus number of users (link S E curves for T B S , SBS and HTS overlap) 65 5.1 Buffer distribution (i.i.d. fading, Bernouli arrival with packet arrival prob-a b i l i t y ^ . 15 and number of users, K=10) 81 5.2 C D F of the queuing delay (i.i.d. fading, Bernouli arrival with packet arrival probability=0.15 and number of users, K=10) 82 x i 5.3 Buffer distribution of the near-end user (i.n.d. fading, Bernouli arrival with packet arrival probability=0.4 and number of users, K=10) 83 5.4 C D F of the queuing delay of the near-end user (i.n.d. fading, Bernouli arrival with packet arrival probability=0.4 and number of users, K=10). . . 84 5.5 Buffer distribution of the far-end user (i.n.d fading, Bernouli arrival with packet arrival probability=0.01 and number of users, K=10) 85 5.6 C D F of the queuing delay of the far-end user (i.n.d. fading, Bernouli arrival with packet arrival probability=0.01 and number of users, K=10) 86 5.7 Buffer distribution (i.i.d. fading, M M P arrival and number of users, K=10). 87 5.8 C D F of the queuing delay (i.i.d. fading, M M P arrival and number of users, K=10) 88 5.9 Buffer distribution of the far-end user (i.n.d. fading, M M P arrival and num-ber of users, K= 10) 89 5.10 C D F of the queuing delay of the far-end user (i.n.d. fading, M M P arrival *and number of users, K=10) 90 5.11 Buffer distribution of the near-end user (i.n.d fading, M M P arrival and number of users, K=10) 91 5.12 C D F of the queuing delay of far-end user (i.n.d. fading, M M P arrival and number of users, K=10) 92 6.1 Block diagram for multi-resolution video/image data transmission 6.2 Hierarchical 4 / 1 6 - Q A M constellation 6.3 Scheduling state diagram when the maximum number of retransmissions is equal to one (i.e., Nm = 1) 6.4 Scheduling state diagram when the maximum number of retransmissions is equal to two (i.e., Nm = 2) 6.5 Transition out of state Sitj (0 < i < Nm - 1 , 1 < j < % - 1) when the maximum number of retransmissions is equal to Nm 6.6 Effect of the constellation priority parameter p on the average packet loss rate (Nm=2 and m=l) 6.7 Effect of the allowed maximum number of retransmissions, Nm on the av-erage packet loss rate (m = 1, p = 5, 71 = 15.39[dB], and 72 = 27.69[dB]) x i i 6.8 Effect of the Nakgami m fading parameter on the average packet loss rate (Nm=2, p = 5, 71 = 15.39[dB], and 7 2 = 27.69[dB]) 112 6.9 Effect of the constellation priority parameter p on the average packet trans-mission rate (Nm=2 and m=l) 113 6.10 Effect of the Nakgami m fading parameter on the average packet transmis-sion rate (Nm=2, p = 5, 71 = 15.39[dB], and 72 = 27.69[dB]) 114 6.11 Adaptive system for layered real-time image/video data transmission. . . . 117 6.12 Buffer state space 120 6.13 Comparison of hierarchical and uniform constellation-based schemes. . . . 124 7.1 Scheme of the O F D M system 130 7.2 Optimal delay and aggregate B E R trade-offs with different number of car-riers (Doppler frequency, fd =300Hz) . 140 7.3 Optimal delay and power tradeoffs with different number of carriers (Doppler frequency, f d =100Hz) 141 7.4 Optimal and sub-optimal delay and aggregate B E R trade-offs for different fading rates in two carrier case 143 7.5 Optimal and sub-optimal delay and aggregate B E R trade-offs for different fading rates in three carrier case 144 7.6 Sub-optimal delay and aggregate B E R trade-offs for different fading rates in four carrier case 145 7.7 Optimal and sub-optimal delay and power trade-offs for different fading rates in two carrier case. 146 7.8 Optimal and sub-optimal delay and power trade-offs for different fading rates in three carrier case 147 7.9 Sub-optimal delay and power trade-offs for different fading rates in four carrier case 147 7.10 Power versus rate constraint for delay limited and non-delay limited rate allocation 152 8.1 Scheme of the variance-bounded rate allocation 159 8.2 Channel gain versus transmission rate (R = 2[Mbits/Sec], W = l [ M H z ] and ho = 10) 162 x i i i 8.3 Variance versus transmit power (ho = 10) 163 8.4 Buffer outage probability versus transmission rate variance (W = 4 [ M H z ] , and/in = 10) 170 8.5 Buffer outage probability versus transmit power (W = l [ M H z ] , and h0 = 10). . 170 xiv List of Abbreviations A D S L : Asynchronous digital subscriber line A R Q : Automatic repeat request A S S : Absolute CNR-based single user scheduling A W G N : Additive white Gaussian noise B E R Bi t error rate B S : Base station C D F : Cumulative distribution function C D M A : Code division multiple access C M D P : Constrained Markov decision process C N R : Carrier-to-noise ratio C R C : Cycl ic redundancy check CSI : Channel state information D A : Diffusion approximation D C T : Discrete cosine transform D O F : Degree of fairness I.n.d. : Independent but non-identical distribution D T M C : Discrete time Markov chain D V B - T : Digital video broadcasting-Terrestrial F E C : Forward error correction Fps : Frame per second F S M C : Finite state Markov chain G A : Gaussian approximation H T S : Hybrid two-user scheduling I In-phase I.i.d. : Identically and independently distributed I.n.d. : Independently but non-identically distributed ISI : Inter symbol interference JPDF : Joint probability density function L P : Linear Programming L S B Least significant bit L S P Least significant part M C Multicode M C M Multicarrier modulation M D P Markov decision process M I M O Multi-input multi-output M M P Markov modulated Poisson M S B Most significant bit M S P Most significant part NSS Normalized CNR-based single use scheduling O F D M Orthogonal frequency division multiplexing . O F D M A Orthogonal frequency division multiplexing access P D F Probability density function P E R Packet error rate PFS Proportional fair scheduling PI Policy iteration P L R Packet loss rate P S K Phase shift keying Q Quadrature phase Q A M Quadrature amplitude modulation Q B D Quasi birth-death QoS Quality of Service R V I Relative value R W Random walk SBS Single best user scheduling S E Spectral Efficiency T B S : Two-best user scheduling T D : Temporal diversity T D M A : Time division multiple access U M D P : Unconstrained Markov decision process V B R A : Variance-bounded rate adaptation xvi i Acknowledgements I would first like to express my gratitude towards my supervisor, Professor Vijay K . Bhar-gava without whose guidance, attention to detail, and encouragement, I could not have completed this work. At the same time, special thanks go to Prof. Mohamed-Slim Alouini for his invaluable suggestions and helpful advice. The friendly and supportive atmosphere inherent to the Communication Group at U B C contributed essentially to the final outcome of my studies. I would like to take this opportunity to thank some of my fellows Dr. Dejan, Mamun, and Chandika. It is not possible to mention all the people that have in some way influenced this work. Specially, my wife Sharmin Ferdous helped me a lot while I was warping up my thesis through her continuous support. Last, but not the least, the biggest personal thanks goes to my family, especially to my parents. xv i i i Dedication To my beloved parents and to the members of my family whose blessing, love and affection have been the greatest possession in my life. xix Statement of Co-Authorship I was the primary researcher for this dissertation. The details of my contributions are as follows. For contributions is Chapters 2, 3, 4, 5, 6 and 7,1 have identified and formulated the research problems. For the contribution presented in Chapter 8, my co-author has partly identified and formulated the research problem. I have analyzed performances for all of our designed schemes. These analyzes have resulted closed-form expressions for useful performance metrics. I have also written M A T L A B program and evaluated the performance via computer simulation. I have compared computer simulation results with analytical counterparts. Finally, I have materialized the ideas and prepared manuscripts for scholarly publication. xx Chapter 1 Introduction Wireless networks are expected to support a wide variety of services. Some examples of these services are video conferencing, Internet access, email transfer, and web-browsing. Different applications have different traffic characteristics and quality of service (QoS) re-quirements. These QoS parameters include delay constraint, packet loss rate (PLR) and packet error rate (PER) requirements. For example, depending on the throughput or delay requirements of the services, wireless multimedia services have already been classified as guaranteed or best-effort services [1]. In guaranteed services, the guarantee may be in the form of ensuring that the throughput is greater than some minimum value, or that the delay experienced is smaller than some threshold. Mobi le wireless links are time-varying in na-ture and error prone. In addition, communication resources, for example, transmit power and bandwidth, are scarce. Through a cross-layer design approach, these inherent qual-ity parameters of different services can facilitate efficient use of communication resources (see, for example, [2]). Specifically, the relative delay tolerance of data applications, with the bursty activity patterns and time-varying nature of wireless channels, opens up the pos-sibility of scheduling transmissions to efficiently allocate limited wireless communication resources. Common thread of our research presented in this dissertation is to design innovative schedulers by joint consideration of the time-varying nature of wireless channels as well as the QoS parameters of the services that are to be transmitted. Specifically, we design schedulers for two-user opportunistic scheduling, multi-resolution image/video data trans-mission, rate adaptation for high-quality media streaming, and link adaptation for orthog-onal frequency division multiplexing (OFDM)-based systems for delay-constrained com-munications. The design goals of these schedulers depend on the specific applications for which they are designed. For example, in the case of two-user opportunistic scheduling, the base station (BS) scheduler selects the user(s) as well as the number of packets that are to be transmitted to the selected user(s). On the other hand, the scheduler for multi-1 resolution image/video data transmission selects the packets that are to be transmitted for a given channel condition and a power budget in order to maintain the quality of the received video/image. In what follows, we provide a general background and motivation for the specific research work reported in this dissertation. 1.1 General Background and Motivation 1.1.1 Opportunistic scheduling Independent channel variations among the users in a multi-user environment can be ex-ploited to increase the system's overall throughput by opportunistic scheduling (also known as multi-user diversity) [3], [4]. In opportunistic scheduling, the scheduler at the B S selects a single "best" user in each time slot based on available channel^ state information, and transmits information only to this selected user. Although this classical single best user scheduling (SBS) maximizes the average overall throughput, it suffers from one main dis-advantage, in that the serviced users may have a low frequency of information access. The low frequency of information access has two end effects. First, it leads to a certain degra-dation of system fairness. In a heterogenous fading environment where different users have different average link gains, the users with relatively strong average link gains enjoy a higher frequency of information access than the users with weaker average link gains; thus, long-term fairness degrades. Second, in a homogenous environment where the users have the same average link gain, the low information access frequency with SBS can result in higher queuing delay of the packets at the transmitter buffer. For a memory-limited system, the P L R can be quite high. In this regard, let us consider a system of K users with identical average link gains, and with each user having a transmission buffer at the transmitter where packets are queued until they are served to the desired users. We assume a fixed transmis-sion rate of K packets per transmission slot. With SBS in this homogenous environment, on average each user w i l l get access to one out of K slots, and w i l l receive K packets. Therefore, the average waiting time for the packets at the transmission buffer is almost K time slots. On the other hand, i f the frequency of information is doubled, on average each user w i l l get access to one out of K/2 slots, and wi l l receive K/2 packets. Although in both cases the users wi l l have same the average throughput, the latter one wi l l offer less queuing 2 delay of the packets at the transmission buffer. In addition, the delay jitter (variance of the delay) wi l l be reduced with higher frequency of channel access as higher frequency of information access smoothes out the packet delivery process to the users. The increased queuing delay can also result considerable packet loss due to buffer over-flow for a system with limited buffer size. In a wireless network where different users are located in different locations from the BS resource sharing among the users may be monopolized by the users who are located close to the B S . Consequently, fairness among the users decreases [4]. In order to alle-viate the fairness issue, proportional fair scheduling (PFS) was proposed in [4]. The PFS achieves better fairness among the users at the expense of a certain amount of system spec-tral efficiency (SE). Therefore, there is a trade-off between achievable multiuser diversity gain and fairness among the serviced users. The above-mentioned constraints motivate the design of an opportunistic scheduling scheme that can offer more frequent channel access yet still exploit the multiuser diversity gain. Recently, the concept of multiple best user scheduling has been proposed for multi-code (MC) code division multiple access ( C D M A ) systems [5], [6]. The schemes proposed in [5] and [6] transmit information to two users by assigning a different number of orthog-onal codes to these users thereby improving system fairness. A generalized opportunistic scheduling scheme for multiple users simultaneously using multiple interfaces, for exam-ple, multicarrier C D M A , multi-input and multi-output (MEMO) and orthogonal frequency division multiple access ( O F D M A ) systems, has been studied in [7]. A l l of these schemes consider that there are a number of parallel transmission channels between the users and the access point/BS. Contrary to the multiple interface-based multiple best user schedul-ing schemes examined in [5], [6], [7], in this dissertation, we propose modulation-assisted two-user opportunistic scheduling schemes. Our work differs from the existing schemes in that it proposes a modulation-assisted solution and considers that there is only one trans-mission link between the users and the access point/BS. Our proposed scheme can be used in a narrow-band time division multiple access ( T D M A ) system as well . 3 1.1.2 Multi-resolution image/video data transmission As we mentioned earlier, the present and next generation of mobile communication sys-tems wi l l support the transmission of images as well as video. Some examples of these types of transmission are video conferencing, emergency medical services, and site sur-veys. For reliable digital data transmission over these error prone channels, there are mainly two error-control strategies, namely forward error correction (FEC) schemes and automatic repeat request (ARQ) schemes [8]. Ideally, with A R Q protocols, an error-free transmission is possible i f the allowed maximum number of retransmissions is equal to in-finity. In real-time applications, such as in video transmission, an arbitrary large number of retransmissions for certain packets may lead to large round-trip delays and buffer sizes. Therefore, A R Q schemes with a limited number of maximum retransmissions (also known as truncated, constrained retransmission A R Q ) , are typically used in many applications (see, for example, [9]). This class of A R Q schemes meets a prescribed delay requirement of services by dropping an erroneous packet at the data link layer after a certain number of retransmissions. A l l A R Q schemes require redundancy, and involve decoding complexity as well as delay for using error-detecting codes. Recently, a carrier-to-noise ratio (CNR) threshold-based1 retransmission strategy was proposed in [10] in order to reduce redun-dancy, decoding complexity, and delay. The proposed system assumed that the service (e.g., video-to-car) to be transmitted has a target PER, P E R 0 , as well as a delay constraint. Therefore, a packet is considered to be received "unsuccessfully" and a retransmission is requested i f the instantaneous C N R is less than a C N R threshold (determined by P E R 0 ) during the transmission of the packet. On the other hand, most of video streams have a layered structure where different layers have different transmission priorities and sensitivities. For instance, M P E G - 4 embraces the multi-resolution model as a mechanism to spatially and temporally adjust a video stream to a given channel bandwidth. To transmit these different multi-resolution (i.e., layered) video streams, rather than applying a uniform data protection method to the whole video stream, it is more efficient if the higher sensitive portion of video data is protected by a higher reliable data protection [9] method. Similarly, some source coding schemes, such as 'Throughout this dissertation, CNR threshold means the required CNR value in order to maintain a target bit error rate (BER). 4 discrete cosine transform (DCT), can divide images into several parts depending on their importance. In these source coders, the sensitivity of the channel error varies significantly depending on the importance of the corresponding bits. In the context of multi-resolution transmissions, video streams or image sources can be encoded into classes of different resolution levels with the following main features. 1. Higher-level information cannot be used unless all of the lower-level information is received correctly. For instance, i f Level 1 represents the lowest Level of resolution and Level 2 represents the successive higher level of information, Level 2 information is useless i f Level 1 information is not received correctly. 2. Since higher-level information is useless without all the lower-level information, dif-ferent resolution levels have different transmission priorities. Specifically, a given resolution level has a higher transmission priority than its successive higher resolu-tion levels. For example, Level 1 information has a higher transmission priority than Level 2 information. A hierarchical image transmission scheme using a hierarchical quadrature amplitude modulation ( Q A M ) constellation was proposed in [11] to protect different resolution com-ponents differently. This scheme proposed to devote the first level of hierarchy (i.e., the highest protected sub-channels) of the hierarchical 4 / 1 6 - Q A M constellation for basic in-formation transmission while transmitting refinement information in the second level of hierarchy (i.e., the lowest protected sub-channels). Non-uniform signal constellations in conjunction with the A R Q scheme were used in [12] to adapt the data rate of a single res-olution message string transmitting over fading channels. For the same reason as [10], the system proposed in [12] also used an instantaneous C N R threshold-based retransmission scheme. Inspired by this application of non-uniform constellations, in Chapter 6 of this dis-sertation, we propose a new multi-resolution data transmission technique over block-fading channels. 1.1.3 Link adaptation for OFDM-based systems O F D M , a form of multicarrier modulation scheme [15], is a promising technology designed to meet the demands of high data rate traffic for wide band wireless communications. In an 5 O F D M system, a high data rate system is divided into a number of parallel low data rate streams, each of which is then modulated in a given narrow band frequency channel using orthogonal subcarriers. Each narrow band channel (also called a sub-carrier) undergoes frequency flat fading and thus eliminates the complex equalizer design at the receiver in order to combat intersymbol interference (ISI) in multi-path fading environments. Another advantage of the O F D M modulation technique is the possibility of exploiting different fad-ing gains among the subcarriers in a given channel access and thus loading (power or bit or both power and bit) different subcarriers according to their respective gains. Due to its high spectral efficiency and resistance to multi-path fading channels, the O F D M mod-ulation technique is already being used in several fixed and mobile radio systems, such as asymmetric digital subscriber lines ( A D S L ) , and wireless L A N s ( I E E E 802.1 la/g and I E E E 802.16). It has also been standardized for digital video terrestrial (DVB-T) and audio broadcasting [16]. Since different subcarriers in an O F D M system may have different fading gains in a given channel access, use of the same modulation order in all subcarriers leads to ineffi-cient utilization of the overall spectrum [17]. Assuming that the channel state information (CSI) for all subcarriers is available at the transmitter, different power or bit or both power and bit loading schemes have been proposed in literature. Different loading algorithms have different end goals [18]. One broad class of bit-loading algorithms minimizes the transmit power while attaining a fixed transmission rate as well as a given target B E R (see, for example, [19], [20]). In another version of bit-loading algorithms, average capacity is maximized at a fixed transmit power. These are the two extreme of link adaptation algo-rithms from a delay perspective. The loading algorithms that maximize average capacity or transmission rate are suitable for services that have no delay constraint, theoretically infi-nite delay. On the other hand, the algorithms that maintain a fixed transmission irrespective of channel quality are useful for services that have hard delay constraints. In order to allocate communication resources efficiently, recently adaptive transmis-sion techniques, which vary transmission rate or power jointly considering channel quality, traffic arrival statistics and the buffer state have been proposed in [21], [22]. Through cross-layer design and optimization, the proposed schemes study the optimal trade-offs between different conflicting objectives, for example, buffering delay and transmit power, in single carrier transmission systems. In Chapter 7 of this dissertation, we develop link adaptation 6 algorithms for a multicarrier system for generalized delay-constrained communications. 1.1.4 Variance-bounded rate adaptation for delay-constrained communications In order to take advantage of the time-varying nature of wireless channels, transmit power, rate or both rate and power are varied according to the channel quality [13]. Specifically, for a fading wireless channel, the water-filling policy has been proven to maximize average transmission capacity for an average transmit power constraint [13]. The water-filling pol-icy suggests transmitting information at a higher rate with higher power when the channel quality is relatively better. As a consequence, the packets may need to wait at the transmit-ter buffer until the channel quality becomes relatively better. However, in order to satisfy some upper-layer QoS parameters, e.g., delay requirements, buffer underflow probability, the transmission system should not only maintain an average transmission rate but also may require guaranteeing a bound on the variance of the transmission rate. For example, in case of high-quality video streaming over wireless links, there should sufficient packets at the play-out buffer so that the video frames can be played in a timely manner without interrup-tion (see, for example, [14]). In other words, in order to play out the entire video sequence smoothly, the buffer should not experience an underflow. Constant rate downloading from the server can avoid buffer underflow. But this constant rate downloading policy may not lead to a power-efficient downloading scheme. On the other hand, from channel quality variation point of view, packet transmission should be scheduled at a higher rate during relatively better channel qualities, as suggested by the water-filling algorithm. This water-filling policy, which guarantees an average rate constraint, may cause too much play-out buffer outage due to the unavailability of the video frames on time. Since the video frames are to be available at the buffer at their taken out time instants, instead of having constant rate download some variance in the downloading rate can be tolerated. Therefore, a question arises as to how to schedule transmissions such that minimize the transmit power is minimized while the play-out buffer outage is kept very low, i.e. below a desired level. Motivated by the aforementioned question, in Chapter 8, we propose a new rate allocation scheme, namely variance-bounded rate adaptation (VBRA). Our newly proposed V B R A scheme is not limited to "on-demand" media streaming. In general, it is 7 useful to any application where the transmission rate is bounded by a given variance that is related to some upper layer QoS parameters, e.g., delay, jitter. A closed-form solution of the optimal transmission rate, which minimizes the transmit power while maintaining a given average transmission rate and a variance of the transmission rate, is presented. Using this solution, we explore the optimal power and variance trade-offs for a given average rate constraint. 1.2 Thesis Outline The remainder of this dissertation is organized as follows. Chapter 2 presents a two-best user opportunistic scheduling (TBS) scheme using power-controlled hierarchical modula-tion and Chapter 3 details a rate adaptive hierarchical modulation-assisted T B S scheme. The performances of these schemes are also analyzed in respective chapters. In Chapter 4 , we analyze the performance of the T B S in a heterogenous wireless network where dif-ferent users have different average link gains. In this chapter, we also propose a hybrid two-user scheduling (HTS) scheme. In Chapter 5 , we analyze delay statistics and buffer distribution of the T B S scheme using queuing analysis. In Chapter 6 , we propose adap-tive scheduling protocols for multi-resolution image/video data transmission over fading channels. Chapter 7 presents transmission frameworks for an OFDM-based system for generalized delay-constrained communications. In Chapter 8 , we describe V B R A scheme for media streaming over time wireless links. Finally, Chapter 9 concludes the dissertation and outlines some future interesting research avenues ensuing it. 8 Bibliography [1] S. Shakkottai, T. S. Rappaport, and R C. Karlsson, "Cross-layer design for wireless networks," submitted for possible Journal publication, Jun. 2003, also available online: http://www. ece. utexas. eduJ shakkott/Pubs/cross-layer.pdf. [2] R. Berry and R. Gallager, "Communication over fading channels with delay con-straints," IEEE Trans. Inform. Theory, vol. 48, pp.1135-1149, M a y 2002. [3] R. Knopp and R A . Humblet "Information capacity and power control in single-cell multiuser communications," in Proc. IEEE Int. Conf. Commun. (ICC'95), Seattle, U S A , Jun. 1995, pp. 331-335. [4] D . N . Tse, P. Viswanath, and R. Laroia, "Opportunistic beamforming using dumb antennas," IEEE Trans. Inform. Theory, vol. 48, pp. 1277-1294, Jun. 2002. [5] D . I. K i m , "Two-best user scheduling for high-speed downlink multicode C D M A with code constraint,", in Proc. IEEE Conf. Global Telecommun. (Globecomm' 04), Dallas, T X , Oct. 2004, pp. 2659- 2663. [6] S. Dost, M . Oguz Sunay, and V. K . Bhargava, " A feasibility study of two user down-link transmission for IS-856 system,", in Proc. Personal and Indoor Commun. Conf. (PIMRC'04),, Bercelona, Spain, Sep. 2004, pp. 2029 - 2033. [7] S. Kulkarni and C. Rosenberg, "Opportunistic scheduling for wireless systems with multiple interfaces and multiple constraints," in Proc. of the 6th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, San Diego, C A , U S A , Sep. 2003, pp. 11-19. [8] S. L i n and D . J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Prentice Hal l : Englewood Cliffs, NJ , 1983. 9 [9] C . -C . L i u and S.-C. S. Chen, "Providing unequal reliability for transmitting layered video streams over wireless networks by mul t i -ARQ schemes," in Proc. IEEE Int. Conf. Image Processing (ICIP' 99), Kobe, Japan, Oct. 1999, pp. 100-104. [10] Q. L i u , S. Zhou, and B . Giannakis, "Jointly adaptive modulation and packet retrans-mission over block-fading channels with robustness to feedback latency," in Proc. Conf. Information Sciences and System (CISS 2003), The Johns Hopkins University, U S A , Mar. 2003. [11] M . Morimoto, M . Okada, and S. Komaki, " A hierarchical image transmission system in fading channel," in Proc. IEEE Int. Conf. Univ. Personal Commun. (ICUPC 95), Tokyo, Japan, Oct. 1995, pp. 769-772. [12] R. Otnes and T. Maseng, "Adaptive data rate using A R Q and non-uniform constel-lations," in Proc. IEEE Veh. Technol. Conf. (VTC 01-Spring), Rhodes, Greece, M a y 2001, pp. 1211-1215. [13] A . J. Goldsmith, "The capacity of downlink fading channels using varaible power and variable rate," IEEE Trans. Veh. Technol, vol. 46, pp. 569-580, Aug . 1997. [14] Y. L i , A . Markopoulou, N . Bambos, and A . J. Apostolopoulos, "Joint power/playout control schemes for media streaming over wireless links," IEEE Trans. Multimedia, vol. 8, pp. 830-843, Aug. 2006. [15] J. A . C. Bingham, "Multicarrier modulation for data transmission: an idea whose time has come," IEEE Commun. Mag., vol. 28, pp. 5-14, May 1990. [16] DVB-T Standard: ETS 300 744, Digital Broadcasting Systems for Television, Sound and Data Services: Framing Structure, Channel Coding and Modulation for Digital Terrestrial Television, ETSI Draft EN300 744, 1999-1, 1999. [17] T. Keller and L . Hanzo, 'Multicarrier modulation: a convenient framework for time-frequency procesing in wireless communications," Proc. of the IEEE, vol. 88, pp. 611-640, May 2000. 10 [18] A . T. Toyserkani, J. Ayan, S. Naik, Y. Made, and O. Al-Askary, 'Sub-carrier based adaptive modulation in H I P E R L A N / 2 system," in Proc. IEEE Int. Conf. Commun. (ICC04), Paris, France, Jun. 2004 pp. 3460-3464. [19] L . Goldfeld and V. Lyandres, 'Capacity of the multicarrier channel with frequency-selective Nakagami fading," IEICE Trans. Commun., vol. E83-B, pp. 697-702, Mar. 2000. [20] C. Y. Wong, R. S. Cheng, K . B . Letaief, and R. D . Murch, "Multiuser O F D M with adaptive subcarrier, bit, power, and power allocation," IEEEJ. Select. Areas Commun., vol. 17, no. 10, pp. 1747-1758, Oct. 1999. [21] A . T. Hoang and M . Motani, "Buffer and channel adaptive modulation for transmis-sion over fading channels," in Proc. IEEE Int. Conf Commun. (ICC03), Anchorage, A K , vol. 4. pp. 2748-2752, May 2003. [22] D. Djonin, A . K . Karmokar, and V. K . Bhargava, "Delay-constrained rate and power adaptation over correlated fading channels," in Proc. IEEE Global Teleommun. Conf. (Globecom'04), Dallas, T X , Sep. 2004, pp. 3448- 3453. 11 Chapter 2 Multi-User Opportunistic Scheduling Using Power-Controlled Hierarchical Constellations 2 A s it was mentioned in Section 1.1.1 that classical SBS scheme provides low frequency of information access to the serviced users in a wireless network. This leads to higher average queuing delay and packet loss rate for a finite buffer system. On the other hand, hierar-chical constellations consist of non-uniformly spaced signal points (see, for example, [23], [24]). Due to the capability of providing different levels of protection, this type of con-stellations has been proposed in many applications including broadcast channel [27], mul-timedia transmission [25], downlink multiplexing [26] and superposing bits from different users in the same sub-carrier of an O F D M system [31]. It has also been included in digi-tal video broadcasting (DVB-T) [28], Med iaFLO [29], Ultra Mobi le Broadband ( U M B ) , a 3.5th generation mobile network standard developed by 3GPP2 [30]. The above mentioned power efficient hierarchical multiplexing schemes motivates us to study an application of hierarchical constellations in multi-user opportunistic schedul-ing which transmits information to multiple best users simultaneously rather than a single best user in a given time slot. This way the users are given more frequent information access in order to reduce queuing delay and loss rate of the packets at the transmission buffer. The detailed description of our proposed scheme w i l l be given in Section 2.1.2. We present expressions for the average transmit power, and the outage probability with trun-cated channel inversion power control for a fading environment where the users' channels' fading gains are identically and independently distributed (i.i.d). Using these expressions, 2The research work presented in this chapter has been published as M d . J. Hossain, M.-S. Alouini, and V. K. Bhargava, "Multi-user Opportunistic Scheduling using power-controlled Hierarchical Constellations", IEEE Trans. Wireless Commun., Vol. 6, pp. 1581-1586, May 2007. 12 we explore the trade-offs between these higher layer performances and the power efficiency of multi-user opportunistic scheduling using hierarchical constellations. We also analyze higher layer performances, for example, buffer distribution, average buffer occupancy, and loss probability of the packets at the transmission buffer via queuing analysis. We finally compare in this chapter the hierarchical multi-user scheduling scheme with a time-slotted multi-user opportunistic scheduling. In this time-slotted scheme two or more best users are scheduled for transmission in a mini time-slotted fashion. 2.1 Multi-User Opportunistic Scheduling 2.1.1 Hierarchical constellations Throughout the chapter, we limit ourselves two best user opportunistic scheduling using hierarchical 4 / 1 6 - Q A M constellation which is constructed with two levels of hierarchy. However, our approach can easily be generalized for the scheduling of more than two best users using higher order hierarchical constellations [24]. A hierarchical 4 / 1 6 - Q A M constellation (see, for example, [23]), is shown in Fig . 2.1 and can be modelled as follows. We assume that there are two streams of data where one stream requires higher level of protection than the other. For every channel access two bits are chosen from each level. The two bits requiring the highest protection are assigned to the most significant bit (MSB) position in the inphase (I) and quadrature (Q) phase channels. Consequently, the two bits that require the least protection are assigned to the least signif-icant bit (LSB) position in the I and Q channels. In Fig . 2.1, the fictitious black symbols represent a 4 - Q A M constellation (referred to as the first hierarchy and denoted by H i ) . The distance between the symbols in the first hierarchy is represented by d\. The actual trans-mitted symbols are the white symbols and they represent a 1 6 - Q A M constellation. This is the second level of hierarchy (denoted by hierarchy H 2 ) . One of these white symbols surrounding a selected black symbol in the first hierarchy is selected by the two bits that requires the least protection. The distance between the symbols in the second hierarchy is denoted by d2. The exact B E R expressions over additive white Gaussian noise ( A W G N ) channel for this hierarchical 4 / 1 6 - Q A M constellation were derived in [24]. The B E R equations in [24] 13 o o o 01 o 10 10 o 11 o 10 o 11 o 00 00 o 01 o 01 o 00 o 11 11 o 10 o -11 o 10 • o 01 01 o 00 o Figure 2.1: Hierarchical 4/16 i - Q A M constellation. are not invertible in terms of transmit power and the constellation priority parameter for given other parameters. However, the well known SNR-gap approximation [33] can be easily inverted in terms of the transmit power and this leads to a simple design of hierarchi-cal constellations (see [31]). As such, we use this SNR-gap approximation to evaluate the average transmit power analytically. According to the SNR-gap approximation, the average power of kth hierarchy is given by [31], [33] P. = (2.D 0 where is the distance between the constellation symbols in the kth hierarchy and m is the number of bits assigned to fcth hierarchy which is equal to two in the case of hierarchical 4 / 1 6 - Q A M . The distances d\ and d2 as shown in Fig. 2.1 are calculated recursively as follows. The distance between the actual constellation (16-QAM) symbols, d2 is calculated < h - f ^ , (2.2) where a2 is the received power channel gain of the user assigned to second hierarchy, No is the one sided noise power spectral density, and 0 is the SNR-gap of the uncoded Q A M constellation and given by /BERn x 2 I" 4 (2.3) where Q _ 1 ( ) is the inverse standard Gaussian Q-function and B E R 0 is the target B E R . The distance between the actual symbols in different quadrant d' as shown in Fig . 2.1, can be calculated as where (52 is the received channel fading power gain of the user assigned to the first hier-archy. Now the distance between fictitious symbols (4 -QAM) in the first hierarchy can be written as (see Fig . 2.1) d!=d' + d2. (2.5) Using Eqs. (2.1)-(2.5), the total transmit power with hierarchical 4 / 1 6 - Q A M constellation (assuming that the second hierarchy is assigned to a user with channel fading gain a2 and that the first hierarchy is assigned to a user with channel fading gain 01) can be expressed 15 as P(a,/?) = ^ f + C 2 {a2 + 2aP + p2) (2.6) a2p2 where the constant C2 = 2N0Q(22 - 1). 2.1.2 Hierarchical constellation-based multi-user opportunistic scheduling To describe our proposed multi-user opportunistic scheduling let us consider a BS trans-mitting to K users opportunistically. The users have to meet a predetermined target B E R , B E R 0 and the channel variation among the users is assumed to be i.i.d. The channel fading amplitude of a given user is Rayleigh faded which corresponds to the following probability density function (PDF) for the fcth user channel fading gain hk, Phk(hk) where h0 is the identical average channel fading gain of the users. We now describe the scheduling as well as the corresponding adaptation process. • Step 1: Based on users' channel qualities, the scheduler at the B S ranks the users and picks up the first (denoted by U(i)) and the second best user (denoted by U(2)). Without loss generality, let us consider the fading gains of the users U(i) and U(2) are denoted by and fy2), respectively. • Step 2: If the channel fading power gain of the second best user, hr2) is above a threshold h\, go to the next step. Otherwise declare a transmission outage for that time step and restart from step 1 in the next time slot. • Step 3: Since the user, U(i) requires less protection than user U( 2), hierarchy H 2 is assigned to the user U(i) whereas hierarchy Hi is assigned to the user U( 2). With this assignment, the transmitter adapts the transmission power as well as the relative distances between the symbols (di, d2 and d') such as the target B E R , B E R 0 is met with the corresponding channel fading power gains hi\) and fy2). The position of the bits in a transmitted symbol for the selected users are sent via a feed-forward channel. Thus the selected users receive the symbols and look only for the bits (2.7) 16 in particular positions within the symbol. Since the average transmit power with channel inversion power control policy on Rayleigh faded channel is infinite [32], a truncation threshold h\ is used in the channel inversion power control. This threshold fv\ is set to a value such that a pre-specified transmission outage probability is met. The expression for the outage probability wi l l be given in closed-form in Section 2.2.1. In Step 3, the required power as well as the constellation parameter can be found numerically solving B E R expressions of the hierarchical 4 / 1 6 - Q A M [24]. However, as mentioned above for analytical tractability, we use the approximations in Eq . (2.6). 2.1.3 Comparison with uniform Q A M constellation-based scheme Multi-user scheduling is also possible using uniform Q A M modulation in a time division fashion. Basically, the whole transmission slot is divided into a number of mini-slots and in each mini-slot the data of a particular user is transmitted. In two user scheduling, the transmission slot is divided into two mini-slots. The first best user is scheduled in the first mini-slot whereas the second best user is scheduled in the second mini-slot. The transmit power in each mini-slot is adjusted according to the corresponding selected user's channel gain so that the bits are transmitted below the target B E R using uniform 1 6 - Q A M over an A W G N channel. 2.2 Performance Analysis and Results In this section, we derive analytical expressions for the average transmission power and the outage probability. We also analyze the buffer distribution function, the average buffer occupancy, and the P L P for all the schemes under consideration. Some selected numerical results obtained via computer simulations are also presented to compare the performance of the schemes under consideration. We use an uncoded target B E R , B E R 0 of 1 0 - 4 and a pre-specified outage probability of 1 0 - 3 . We assume channel variation among the users is i.i .d with an average channel fading gain of 5[dB]. 17 2.2.1 Outage probability For two-user opportunistic scheduling a transmission outage occurs i f the channel fading gain of the second best user, hp) is less than a threshold h\. Therefore, the outage proba-bility of two-user scheduling, O 2 1 can be written as °cU, = / / Phwh{2)(h{1),hm)dh(x)dhp) (2.8) where P/ i { 1 ) / i ( 2 ) (fyi) , hp)) is the joint P D F of the largest two channel gains and can be ex-pressed as [34] f h ^ K(K-l) ( h w \ ( hp)\ VHwhw{h^hp)) = - ^ ^ ^ - — j ^ ^ — j x f l - exp I —^ j J ; h w > hp) > 0. (2.9) Using Eq. (2.9) we can evaluate the integral in Eq. (2.8) as follows: x M - e x p f — j ~ ) ) dh{1)dhp) For single-user scheduling a transmission outage occurs i f the channel gain of the first best user is below a threshold h\ and thus the outage probability of single-user scheduling, 0^, can be written as Ol = f %hm(h(1))dh{1) (2.11) Jo where ph (h(i)) is the P D F of the largest channel gain and is known to be given by [34] Using Eq . (2.12) in Eq. (2.11), the outage probability for single user scheduling can be written in the desired closed-form Solving Eqs. (2.10) and (2.13) for a given transmission outage, we can find the values of the thresholds h\ and h\, respectively. 18 2.2.2 Average transmit power Averaging Eq . (2.6) over the channel gain joint P D F of the two best users, the average trans-mit power in two-user hierarchical constellation-based scheduling, P 2 can be expressed as r+oo r+oo r (J Q , / / TT^ + T - \ v ~ (hm + 2 J h w h ( 2 ) + hm) Jhi Jhm Lty i) ^(1)^(2) v p2 = 1 H I l Jh{2) Phwh(2) (h(i), h<2))dh(i)dh<2). (2.14) Substituting Eq. (2.9) in Eq. (2.14), the expression of P 2 can be simplified as C2K(K - 1) (M 2 xexp h (i) h0 r+oo r+oo hi • '/l(2) exp ( h m K ho + 2-1 + -K-2 1 — exp (2) C 2 K { K - l ) _ t ^ f K - 2 ^ { _ l ) l (hof x E i (2) i=0 + E ho h (2) exp h0 r+oo / 2 (i + l)h{2) dhri)dht2) ho dh (2) where the function E n ( - ) is defined as E„(x) = J +oo exp (—xt) dt. (2.15) (2.16) Similarly the average power in uniform 1 6 - Q A M constellation-based two user schedul-ing, P 2 can be written in simplified form as r 'h{2) i=0 p 2 = C 4 K ( K - l ) ^ f K - 2 \ { i ) t 2{hof r E l (: Jhi V ' ( i + 2)/i; ho ho (2.17) where the constant C\ = 2 A r 0 6 ( 2 4 — 1). Unfortunately, the integrals in Eqs. (2.15) and (2.16) cannot be evaluated in simple closed-form. However, it can be evaluated numerically and consequently the average transmit power for T B S scheme can be obtained. The average transmit power for single-user scheduling can be expressed as +0° CA Phw(h(i))dh{1). (2.18) 19 — Two-best user scheduling (mini-slotted scheme) • e Two-best user (hierachical scheme) Single best user scheduling (classical scheme) 15 20 Number of users in the system 30 Figure 2.2: Normalized (by No) average transmit power versus the number of users. Substituting Eq . (2.12) in Eq. (2.18), P 1 can be simplified to P 1 +oo hi K-l ho exp h (i) h0 1 — exp hi) ho K-l dh (i) i=0 i + 1 h0 (2.19) The average power for different schemes is plotted in Fig . 2.2. There are two obser-vations from this figure. First, the two user scheduling always requires more power than the single user scheduling. This is due to the inclusion of the second best user in the trans-mission. Second, the required additional power decreases as the number of users in the system increases. This can be explained by the fact that as the number of users increases in the system, the frequency of having higher difference between the first largest channel gain h'i) and the second largest channel gain hp) decreases. Therefore, the average power required to transmit to the second best user decreases. On the other hand, the hierarchi-cal schemes always require less power than the uniform constellation-based mini-slotted scheme. This is expected due to the superposition of the information bits for two different users in the same message symbol. It is also obvious from Fig . 2.2 that the required ad-20 ditional power with mini-slotted scheme decreases as the number of users increases in the system. This is again expected, as the frequency of having higher difference between h(i) and hp) decreases with the number of users in the system. 2.2.3 Buffer density and packet loss probability In this section, we analyze and compare the buffer distribution, average buffer occupancy, and packet loss probability of all the schemes under consideration. We assume that each user has a transmission buffer where packets are queued until they are served to the desired users. The system is assumed to be a homogenous system where all users have the same (i) buffer length, (ii) packet arrival statistics, and (iii) average link gain. Therefore, we are interested in the queuing analysis of a given user's buffer. Other users' buffer w i l l have the same performance. The finite buffer size is assumed to be B packets and the packet arrival process is assumed to be Bernoulli with arrival probability a in each time slot. We assume that a packet arriving during time slot n — 1 cannot be transmitted until time interval n. Since with the two-best user scheduling schemes (both hierarchical and mini-slotted schemes) two packets are transmitted from one of the selected buffers per time slot, the number of packets transmitted during time interval n is min(6 n , 2), where bn is the buffer occupancy at time slot n. For i.i .d. channel variations among K users, the probability that a user wi l l get an access to the channel, in given time slot, is 2/K. Therefore, the probability of serving a given queue, s 2 , f ° r a pre-specified outage probability 0 0 U t , is expressed as 3 * 2 = - | ( l - 0 o u t ) . (2-20) The dynamics of the buffer with the proposed two-best user scheduling is shown in F ig . 2.3. The discrete time Markov chain describing the buffer dynamics has the following 3 For the sake of simplicity of the analysis we assume the fading gain of a given user varies independently from one time slot to the next. 21 Figure 2.3: Markov chain representation of the buffer dynamic with power-controlled modulation-assisted two-best user scheduling. transition matrix b P = a 0 0 0 bs2 as2 + bv2 av2 0 0 bs2 as2 bv2 av2 0 0 bs2 as2 bv2 av2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 bs2 as2 bv2 av2 0 0 bs2 as2 bv2 + av2 where b = 1 — a and v2 = 1 — s2. The steady-state probability 7r = [7r0 7ri obtained solving the following equations booP - 7T B 5>fe = 1. fe=0 (2.21) •KB] can (2.22) (2.23) The steady-state probability density function can be obtained using the standard proce-dures, such as the ones outlined in [35]. Similarly we can construct the Markov chain for the SBS scheme. Since four packets are taken out of the buffer per channel access, we assume that the number of packets trans-22 0.7 — Two-best user scheduling (proposed scheme) v Single best user scheduling (classical scheme) 0 1 2 3 4 5 6 7 8 9 10 z [packets] Figure 2.4: Buffer distribution and average buffer occupancy level. mitted during time interval n is min(6 n , 4). In this case the probability s i that a given queue wi l l be served in given time slot can be written as S l = - ^ ( l - 0 o u l ) . (2.24) The corresponding steady-state buffer distribution can be obtained using standard proce-dures. The steady-state buffer distribution function is plotted in Fig . 2.4. In the numerical example we consider K = 10, B = 10, and a = 0.1. From Fig . 2.4 we can observe that the buffer occupancy with power-controlled modulation-assisted T B S is concentrated in the low occupancy region with higher probability compared with the SBS. Therefore, power-controlled T B S scheme results into a lower average buffer occupancy (consequently, lower average delay for the packets) which is also obvious from the marked points on the x-axis of Fig . 2.4. The buffer distribution which is concentrated in the low occupancy region with two best user scheduling also results into a lower packet loss probability due to the buffer overflow as we wi l l see from the following analysis and example. The packet loss probability, P L P defined as the probability that a packet is dropped due to buffer overflow corresponds to the probability that the buffer is full and a packet arrives 23 10 ' 10J t-£• io"! •5 10 10 10 Single best user scheduling (classical scheme) Two-best user scheduling (proposed scheme) 0.06 0.08 0.1 0.12 0.14 Packet arrival probability, a 0.16 0.18 Figure 2.5: Packet loss probability versus packet arrival probability. in the buffer. Therefore, the P L P can be written as P L P = nBa. (2.25) The packet loss probability with different schemes are shown in Fig . 2.5 for different values of packet arrival probability. This figure shows that the two best user scheduling always offer less packet loss probability. The is because of the comparatively lower probability of buffer occupancy in the high buffer occupancy region with two best user scheduling as mentioned above. 2.3 Conclusion In this chapter, we proposed and studied a new hierarchical constellation-based multi-user opportunistic scheduling scheme. The multi-user scheduling provides lower average buffer occupancy (i.e., queuing delay) and loss probability for the packets at the transmission buffer at the expense of transmit power compared with the classical single user schedul-ing. The required additional power decreases as the number of users increases in the 24 system. The hierarchical scheme has been compared with a uniform constellation-based mini-slotted scheme. This mini-slotted scheme provides similar higher layer performances as the hierarchical scheme but requires higher transmit power. This additional power re-quirement decreases as the number of user increases in the system. 25 Bibliography [23] M . Morimoto, M . Okada, and S. Komaki, " A hierarchical image transmission system in fading channel," in Proc. IEEE Int. Conf. Univ. Personal Commun. (ICUPC 95), Tokyo, Japan, Oct. 1995, pp. 769-772. [24] P. K . Vitthaladevuni and M . - S . Alouini , " A recursive algorithm for the exact B E R computation of generalized hierarchical Q A M constellations," IEEE Trans. Inform. Theory, vol. 49, pp. 297-307, Jan. 2003. [25] M . B . Pursley and J. M . Shea, "Adaptive non-uniform phase-shift-key modulation for multimedia traffic in wireless networks," IEEE Journal Select. Areas Commun., vol. 18, pp. 1394-1407, Aug . 2000. [26] M d . J. Hossain, P. K . Vitthaladevuni, M . - S . Alouin i , and V. K . Bhargava, "Hierar-chical modulations for multimedia and multicast transmission over fading channels," in Proc. IEEE Veh. Technol. Conf. (VTC'03 Spring), Jeju, Korea, Apr. 2003, pp. 2633-2637. [27] T. Cover, "Broadcast channel," IEEE Trans. Inform. Theory, vol. IT-18, pp. 2-14, January 1972. [28] D V B - T standard: ETS 300 744., "Digital Broadcasting Systems for Television, Sound and Data Services: Framing Structure, Channel Coding and Modulation for Digital Terrestrial Television" (ETS Draft, 1.2.1, EN300 744, 1999-1 ). [29] F L O Forum and Qualcomm. Flo technology overview: Revolutionizing multimedia, http://www.floforum.org/, 2007. 3GPP2. [30] Ultra mobile broad physical layer, C.P0084-001, Feb. 2007. 26 [31] S. Pietrzyk and G . J. M . Janssen, "Subcarrier and power allocation for QoS-aware O F D M A systems using embedded modulation," in Proc. Int. Conf. Commun. (ICC 04), Paris, France, Jun. 2004, pp. 3202-3206. [32] A . J. Goldsmith, "The capacity of downlink fading channels using variable power and variable rate," IEEE Trans. Veh. Technol., vol. 46, pp. 569-580, Aug . 1997. [33] J. M . Cioffi, " A multicarrier premier," November 1991, also available in http://www.stanford.edu/group/cioffi/pdf/multicarrier.pdf [34] T. Eng, N . Kong, and L . B . Milstein, "Selection combining schemes for R A K E re-ceivers," in Proc. 4th Int. Conf. Univ. Personal Commun. (ICUPC'95), Tokyo, Japan, Nov. 1995, pp. 426-430. [35] F. Gebali, Computer Communication Networks: Analysis and Design, NorthStar Digital Design, Inc., Victoria, B C , Canada, 2002. 27 Chapter 3 Rate Adaptive Hierarchical Modulation-Assisted Two-User Opportunistic Scheduling insp i red by the power efficient hierarchical multiplexing schemes, in previous chapter (also refer to [36]), we studied a multi-user opportunistic scheduling scheme using a vari-able power fixed size hierarchical constellation. However, due to the inclusion of second best user in each transmission, the scheme proposed in [36] offered more frequent informa-tion access to the users at the expense of certain amount of transmit power compared with the classical SBS scheme. In this chapter, we propose and study a two-best user oppor-tunistic scheduling scheme using fixed power discrete rate adaptive hierarchical constella-tions. Rather than including the second best user in each transmission as in [36], the newly proposed scheme judiciously decides whether the second best can be included in a given transmission or not. As such the frequency of channel access of the users increases without any expense of overall average SE compared with the classical SBS scheme. Specifically, according to the channel quality of the first best user, the alphabet size of the square quadra-ture amplitude modulation ( Q A M ) is selected in order to maximize the SE . However, i f the first best user's channel quality is good enough to decode the information transmitted in the second hierarchy of the selected size hierarchical Q A M constellation while the second best user's channel quality is capable of decoding the information transmitted in the first hier-archy, information is transmitted to both the selected first and second best users using the hierarchical Q A M constellation. Otherwise, information is transmitted only to the first best user using the selected size uniform Q A M constellation. We present expressions for the 4The research work presented in this chapter has been published as Md. J. Hossain, M.-S. Alouini, and V. K. Bhargava, "Rate Adaptive Hierarchical Modulation-Assisted Two-User Opportunistic Scheduling", IEEE Trans. Wireless Commun., Vol. pp. 2076-2085, Jun. 2007. 28 information transmission probability and the overall average SE [Bits/Sec/Hz] defined as the overall average transmitted data rate per unit bandwidth for a specified number of users, a specified average C N R , and B E R . Numerical results for a fading environment where the channel variation among the users is i.i.d. are presented. The novelty of the fixed power discrete rate adaptive hierarchical modulation-assisted two-best user scheduling is that it provides more frequent access to the information (almost double) without any average S E degradation compared with the classical single best user opportunistic scheduling. 3.1 Channel Model and Hierarchical Constellations 3.1.1 Channel model Let the total system bandwidth be W[Hz] . Given the channel fading amplitude of kth user, Oik and a white noise power spectral density of N0[W/rlz], let us define the normalized fading gain at receiver for kth user hk = (ak)2/N0W. For a transmit power of P[W], the received symbol C N R of A;th user's receiver gk = hkP. We consider that the fading amplitude of the users is characterized by the Rayleigh P D F which leads to the following P D F of the fcth user received symbol C N R g^, p9k(gk) PgM = ^-exp ( ) , gk>0 (3.1) gk \ gk/ where g~k is the average C N R of user k. For total K users whose channels vary identically and independently, the P D F of the largest C N R g^), (g^)) can be expressed as [39] ' ^ > - s - ' ( - ? ) ( 1 - * ( - ¥ ) ) ' " • ^ ° <3'2) where go is the identical average C N R of the users. The joint P D F of the two largest C N R s gw and g{2), P 3 ( 1 ) P ( 2 ) 0(2)) can be expressed as [39] p ^ t a i , . ^ ) = n s ? « p ("Sexp ("S f1 -e x p (3.3) where g{1) > g{2) > 0. 29 d3=d2/2 d. 0000 0001 0101 0100 • • • • o o 0010 0011 0111 0110 • • • • 01 1010 1011 n i l m o o o 1000 1001 HOI 1100 1000 1001 1101 1100 L ^ o o 1010 i o n 1111 1110 11 0010 0011 1111 1110 o o 0^00 0^)1 1^1 1^0 0100 0101 0001 0000 o o 0110 0111 0011 0010 • • „ „• • 00 1110 1111 1011 1010 o o 1100 1101 1001 1000 1100 1101 1001 1000 • 11C o o 1110 1111 1011 1010 10 0 1 1 0 0111 0011 0010 • • • • o o 0KI0 0^1 00^1 00^0 Figure 3.1: Hierarchical 4 / 6 4 - Q A M constellation. 3.1.2 Hierarchical constellations Due to their inherent SE square Q A M constellations have received considerable attention in mobile communication (see, e.g., [38]). We consider only square M = 2 2 r - Q A M con-stellations, where r = 1,2, • • • , Q, in our proposed scheme. The detailed description of generalized hierarchical constellations can be found, for ex-ample, in [37]. Briefly a generalized hierarchical 4 /16/ • • • /M(= 22r) Q A M constellation has m levels of hierarchies and the relative distances between the symbols within the con-stellation are described by a set of r distances [37]. The distance set can be represented as a vector [37] d= [di d2 • • • dr] (3.4) where dk is the distances between the symbols in kth hierarchy. Since our proposed scheme transmits information to two best users using hierarchical constellation, we use a family of hierarchical N{= 2 2 s ) / M ( = 2 2 r ) - Q A M constellations, where r = 2,3, ••• ,Q and s = 0,1, • • • ,r — 1. We assume that there are two incoming streams of data where one stream has higher priority than the other. With hierarchical N(— 22s)/M(= 2 2 r ) - Q A M 30 constellation, the first priority 2s bits are assigned to the most significant s bit positions in the I and Q phase channels. The lowest priority 2(r — s) information bits are assigned to the rest of the positions in the in-phase and quadrature-phase. For example, see 4 / 6 4 - Q A M constellation with Karnaugh map style Gray mapping in Fig . 3.1. In this figure, one of the fictitious 4 - Q A M symbols (denoted by the grey circle) is selected by the highest priority two bits. The black symbols are the actual transmitted symbols. The one of the black 16-Q A M symbols surrounding the selected 4 - Q A M symbol is choosen by the least priority four bits. In order to avoid confusion between the generalized 4/16 •• • / 2 2 r - Q A M and 2 2 s / 2 2 r -Q A M constellations, it is important to mention that the first s hierarchies of the general-ized 4 /16 / • • • / 2 2 r - Q A M constellation are considered as one hierarchy in 2 2 s / 2 2 r - Q A M constellation which we refer as the first hierarchy (namely hierarchy H i ) . The distances between these s (1 < s < r) hierarchies are uniformly spaced i.e., [37] di_1 = 2di, % = s, s - 1,, • • • ,2 . (3.5) The rest r — s hierarchies of the generalized hierarchical constellation are considered as another hierarchy which is referred as the second hierarchy (namely hierarchy H 2 ) . The distances between these r — s hierarchies are also uniformly spaced i.e., di+i = ^, % = s + l , a + 2, • • • , r - 1. (3.6) Therefore the relative symbol positions within the hierarchical 2 2 s / 2 2 r - Q A M constellation are defined by two distances; ds and ds+i in contrast to r distances in generalized hierarchi-cal 4 /16 / • • • / 2 2 r - Q A M constellation. A constellation priority parameter p can be defined as P = - T - - - (3-7) For uniform square Q A M constellations, the value of p is two (see, e.g., [37]). For a given constellation size M ( = 2 2 r ) , there can be a set of hierarchical constellations with different number of bits in each of the two hierarchies as described above. A s such the set is denoted by C r = { 2 2 / 2 2 r , 2 4 / 2 2 r • • • , 2 2 ( r ~ 1 ) / 2 2 r } . Later on we wi l l use the set of the hierarchical constellations of a given size to allocate the available transmission rate among the selected two users. 31 The exact B E R expressions over A W G N channels were shown in [37] as the summation of weighted Q-functions and to be solely dependent on the constellation size M, the C N R g, and the priority parameter p. Therefore, in general, the B E R expressions for the bits in the first hierarchy, B E R i can be written as Similarly, the B E R expressions for the bits in the second hierarchy, B E R 2 can be written as 3.2 Two Best-User Opportunistic Scheduling 3.2.1 General assumptions Our proposed scheme has the following operating assumptions: A l : A single B S is transmitting information to K users opportunistically. A 2 : The channel variation among the users is independent. A 3 : The channel qualities of the users are reported to the B S in the form of instantaneous C N R via the feedback channel. A 4 : The users have a target PER, P E R 0 and a F E C strategy is used. Specifically, the packets are encoded with block coding for example, B C H code which is capable of correcting up to t errors. For a given F E C scheme with capability of correcting t errors, the target B E R , B E R 0 in order to meet the target P E R , P E R 0 can be obtained easily i f the error event is random. This random error event can be achieved by using proper interleaving. 3.2.2 Overall system description The block diagram of our proposed rate adaptive hierarchical modulation-assisted T B S is shown in Fig. 3.2. In what follows, we describe the general working principle of our proposed scheme. According to the available instantaneous C N R estimate of all the users, the BS scheduler selects two users, namely the first best user (denoted as U(i)) and the second best user (denoted as U( 2)), whose instantaneous C N R s are the first and second highest, respectively. Without loss of generality let us denote, the C N R s of user U(i) and BER! = f1(M,p,g). (3.8) B E R 2 = / 2 ( M , p , p ) . (3.9) 32 Information" b i t s for the users _ FEC block 2(r-s) bits for the —I first best user B i t a s s i g n e r Channel CNR of the second best user, g,3, I-phase S i g n a l mapper QAM I modulatorf" 2s bits for the-second best user Constellation size Mr=2ar Q-phase C o n s t e l l a t i o n s i z e s e l e c t o r Channel CNR of the first best user, g n Two best user s e l e c t o r Channel q u a l i t y feedback of K users Figure 3.2: System model of B S scheduler. U( 2) by #(1) and g^), respectively with > g^)- According to the first best user's channel C N R , ^(i), the size of the constant power Q A M constellation is selected by the constellation size selector as shown in Fig . 3.2. Next, jointly considering the channel C N R s of both the selected best users, U(i) and U(2), the bit assigner (see Fig . 3.2) decides how the available total transmission rate is divided among the selected users U(i) and U( 2 ) . The constellation size as well as the bit assignment procedure w i l l be described in details in the next section. When information bits are transmitted to both the users U(i) and U( 2 ) , a hierarchical N/M-QAM is used and since first hierarchy is more protected than the second hierarchy, the second best user's transmission is scheduled in the first hierarchy whereas the first best user's transmission is scheduled in the second one. The decision i.e., the position and the number of bits in the transmitted symbol for the selected users, is informed to the users' receiver via the control channels. Therefore, the selected users receive the symbols and look only for the bits in particular positions within the symbol. 3.2.3 Rate adaptation process In this section, we describe how the constellation size is selected according to the first best user channel quality and how the total available transmission rate is allocated between the 33 two best users jointly considering their instantaneous link qualities. For convenience the rate adaptation process of our rate adaptive T B S scheme is summarized via a flowchart in Fig. 3.3. D i s c r e t e c o n s t e l l a t i o n s i z e s e l e c t i o n To minimize the power consumption, the proposed scheme does not attempt to transmit when the first best user's instantaneous C N R , g<i) is not good enough to support the satis-factory communication using the 4 - Q A M constellation. In other words, the transmission is suspended if the estimated C N R , <7(i) is less than 71 (as shown in Fig . 3.3) where 71 is obtained from the exact B E R of uniform 4 - Q A M modulation in A W G N 5 given by In order to maximize the overall S E our proposed scheme selects the constellation size according to the first best user's received C N R as follows. The C N R range of the user U(i), ^(i) is divided into Q + 1 fading regions; namely r = 0,1, 2, • • • , Q. Each fading region is assigned a unique constellation size. Specifically, the constellation size Mr = 2 2 r (where 2r is the total number of bits per M r - Q A M symbol) is assigned to the rth fading region (r = 0,1,2, • • • , Q). When the received C N R of the user U(i) , <?(i) is estimated to be in the rth fading region, the constellation size MT is selected to be transmitted as shown in F ig . 3.3. Choosing the constellation size M 0 in region r = 0 corresponds to no data transmission. The region boundaries (or constellation size switching thresholds) { T T } ^ 1 are set to the C N R such that the information bits are sent below the target B E R , B E R 0 using the uniform M r - Q A M constellation. This is very similar to a conventional discrete rate adaptive transmission system [38]. Since the exact B E R expressions for uncoded M-Q A M in A W G N [37] are not invertible, the region boundaries 7 r (r = 1,2, • • • , Q + 1) are obtained by numerically solving the B E R equations of the uniform M r - Q A M in A W G N for C N R and setting 7 Q + 1 = +00. 5In all the schemes under consideration, the choices of constellation size and bit assignments to the users are done in a conservative fashion. Specifically, the alphabet size M is selected and the available transmission rate is divided among the two best users such that their instantaneous channel qualities support the bits below the target BER. In addition, we assume that the fading gains remain constant over the symbol period. Therefore, the BER expressions in A W G N are used to set the switching thresholds. (3.10) 34 Input a l l the users' CNR, g k k = l , 2 , . . . K Pick up the f i r t best user, U ( 1 and the second best user U l 2 , and t h e i r channels gains, g ( 1 , and g 1 2 l , respect ively gui and 9(j) Yes Transmit 4-QAM: I-pahse b i t for U| U and Q-phase b i t for U, : Transmit 4-QAM for user U ( 1 | Transmit information to both users U ( l l and U ( a ) using h i e r a r c h i c a l 22*/ 22r-QAM Transmit information only to user U ( 1 , using uniform 22r-QAM Figure 3.3: Flow chart of proposed rate adaptive modulation-assisted T B S scheme. 35 T r a n s m i s s i o n r a t e a l l o c a t i o n t o t h e s e l e c t e d u s e r s U ( i ) a n d U(2) To transmit information to the selected second best user opportunistically, the scheme switches between the uniform and hierarchical constellations jointly considering the C N R estimate fluctuation of the two best users as follows. As we have described in Section 3.1.2 that a Q A M constellation of order MT = 22r, (r = 2,3, • • • , Q) can form a set of hierar-chical constellations Cr. Each hierarchical constellation in the set, C r specifies a unique combinations of bits in two different hierarchies. Therefore, in a given fading region, the number of bits within the constellation that can be assigned to the users U(i) and U( 2) jointly depends on the received C N R estimate of both the users. To assign the available transmis-sion rate (i.e., the number of the bits) to the selected users, U(i) and U( 2 ) , each of the fading regions, except r = 1, is divided into a number of fading sub-regions and each sub-region supports a unique combination of bits in the first and second hierarchies. Specifically, the rth fading region (r = 2,3, • • • ,Q) is divided into s = 0,1, • •• , r - 1 sub-regions and when the C N R of the first best user is estimated in the sth sub-region s, 2(r — s) bits in the second hierarchy can be decoded by the first best users with required reliability 6 . The sub-region boundaries {jr,s}?=2~s=i 3 1 6 obtained by numerically solving the B E R equations of the hierarchical 2 2 s / 2 2 r - Q A M such that the bits assigned in the second hierarchy are sent below the target B E R , B E R 0 . For example, the sub-region boundary 7 | 2 for the 2nd sub-region of the 3rd fading region are obtained by numerically solving (3.9) for the C N R such that / 2 (M3 ,p ,73 2 ,2)=BER 0 . , (3.11) Although the first best user can decode the 2(r — s) information bits transmitted in the second hierarchy of the hierarchical 2 2 s / 2 2 r - Q A M with given reliability i f its C N R estimate falls in the sth subregion of rth fading region, the 2s bits transmitted in the first hierarchy may not be decoded by the second best user with the required reliability. It depends on the C N R of the second best user, gp). Therefore, in order to decide whether to transmit information to the user U( 2) or not, the bit assigners checks the channel C N R , gp). If gp) is good enough to decode the 2s information bits transmitted in the first hierarchy with the required reliability, the bit assigner assigns these bits to the user U( 2 ) . Consequently, hierar-6 In sub-region 0 of a given region r corresponds to transmission to only the first best user using uniform 2 2 r - Q A M . 36 chical 2 2 * / 2 2 r - Q A M is transmitted from the demodulator as shown in Fig. 3.3. Otherwise, the available total transmission rate r is assigned to the user U(i) using the uniform 2 2 r -Q A M . Therefore, if the channel CNR, falls in a given sub-region, the demodulator can transmit either the uniform constellation or the hierarchical constellation depending on the CNR estimate <?(2). The switching between the uniform and the hierarchical constellations in a sub-region s (s = 1,2, • • • , r — 1) of the fading region r (r = 2,3 • • • , Q) depends on the CNR, <7(2) and is determined by the thresholds, {"fr s}?=2~s=i- These thresholds 7* are selected such that the s bits assigned in the first hierarchy of 2 2 s / 2 2 r - Q A M are transmitted below the target BER, B E R n . For example, the switching threshold 73 2 in the second sub-region of the 3rd fading region are obtained by numerically solving Eq. (3.8) for the CNR such that / i ( M 3 j p , 7 i 2 ) = BERo. (3.12) For instance, the details of bit assignment to the selected users in different sub-regions for a maximum constellation size of 8 bits (i.e., 256-QAM) are summarized in Fig. 3.4. The joint PDF of the channel CNRs, <?(i) and gt2) is a two dimensional space, the valid region is defined by the condition: g/^ > g/2) > 0 as shown in Fig. 3.4. This valid region is divided into a number of boxes. The region boundaries of each box are determined by the thresholds which are shown symbolically. Each box is assigned with a constellation (either uniform or hierarchical) as written on the box. In the region where 2 2 s / 2 2 r - Q A M constellation is transmitted information is transmitted to both users U(i) and U(2) while in the region where 2 2 r - Q A M constellation is transmitted, information is transmitted only to user U(i). For example, if the channel CNR, g^ is above 7 2 2 but less than 7 2 3 , information is transmitted both the selected users using hierarchical 16/256-QAM provided that the channel CNR gr2) falls above 7 J 2 . If 9(2) is less than 7 ] 2 although g^ falls in the above mentioned sub-region, no data is transmitted to the second best user because it cannot decode the information bits transmitted in the first hierarchy. In this case, information is only transmitted to the first best user using the uniform 256-QAM constellation as shown in Fig. 3.4. The figure shows that in the Oth sub-region of any fading region, no data is transmitted to the second best user because the first best user's channel quality is not good enough to decode the information transmitted in the second hierarchy. In fading region (r =1), the scheme proposes to transmit 4 -QAM which has only one hierarchy. However, it has two different phases ;I and Q phases. If the second best user's CNR can support 4-37 Figure 3.4: Example: Joint CNRs to constellation mapping. 38 Q A M as well, an information bit is transmitted in one of the phases for the first best user and an information bit is transmitted in the other phase for the second best user. 3.3 Performance Analysis In this section, we derive analytical expressions for the average spectral efficiencies and the information transmission probability. Numerical results obtained via computer simulation are also presented for an i.i.d Rayleigh fading environment. A target BER, B E R 0 of 1CT4 is used. We use the M A T L A B Communication Toolbox to obtain the numerical results. We assume perfect channel estimation, coherent phase detection at the receiver, and Gray coding for bit mapping on the signal constellations, as shown in Fig. 3.1. In the examples, we use a maximum constellation size of 1024 for both hierarchical and uniform Q A M constellations. 3.3.1 Average spectral efficiency The probabilities, ar<a that the 2 2 s / 2 2 r - Q A M constellations are transmitted i.e., the CNR 5(2) is above the threshold 7* while the CNR <?(i) falls in sth sub-region in the rth (r > 1) fading region is given by GT fi(1>9(i)9(2)(5(i).9(2))d5(2)rf3(i) s = r - 1. (3.13) J 7 r , s J 7 r , s Using the expressions of the joint PDF, P f l ( 1 ) S ( 2 ) (<7(i)> 5(2)) of the largest two CNRs for i.i.d. case in Eq. (3.3), the integrals in Eq. (3.13) can be evaluated in closed-form as shown in Appendix A. Using the results in Appendix A and after some manipulations, the probabil-ities {artS}sszri~2 in Eq. (3.13) can be expressed in closed-form as follows: K-2 A:=0 k + 1 where A(x) = exp ^(7r,.+i)exp (fc + l ) 7 ^ \ B(^s+1) 5o k + 2 5o exp x 5o (3.14) (3.15) 39 and B(x) = exp (k + 2 f t exp (k + 2)x (3.16) 0o J - \ 9o Similarly, the probabilities { a r ] S } s = r _ i in Eq . (3.13) can be expressed in closed-form as follows: K-2 ar,s — K(K -\)(K- 2 fc=0 k + l k ( - l )f c ^(7r+i)exp -0 0 A; + 2 (3.17) Recall from Section 3.2.3 that in a given region r (r = 2,3, • • • , Q), in two situations, information is transmitted only to the first best user U(i) using uniform 2 2 r - Q A M ; i f the C N R <7(i) falls in the 0th sub-region or the C N R g>2) is less than the threshold 7* although the C N R <7(i) falls in sth sub-region in the rth fading region. Therefore, the total probability, arfi that the uniform 2 2 r - Q A M constellation is transmitted in the rth fading region is the summation of all the individual probabilities and can be written as P9m(9(i))d9(i) + 2^ / P9mgm(9(i),9(2))dg(2)dg{i). (3.18) 3=1 J1r,s J0 Again using the expressions of the P D F p9(1) (gw) and the joint PDF, Pgw9(2) (0(i), 0(2)) for i.i .d. case in Eqs. (3.3) and (3.2), respectively, Eq . (3.18) can be expressed in closed-form as (see Appendix 9.1.5 for details): K-l ar,0 — I J"fr M - E ^ f : 1 ) ( - D ' k + 1 k=0 r-1 +E 3 = 1 K-2 E ,k=0 k exp {k + l ) 7 r 0o exp 0o ( Ir.s ~ 0 0 , exp )V,8+1 9o . X K(K - 1) (K - 2 k + l \ k ( - l )f c 1 — exp 0 0 (3.19) The probability of transmitting information only to the user U(i) using uniform 4 - Q A M constellation corresponds to the probability that the C N R falls in the region, r = 1 but not the C N R gp) and is given by f!2 fjl a>i,o 71 Jo Pg(i)gi2)(9(i),g(2))dg(2)dg(i). (3.20) 40 Using Eq. (3.3), the probability in Eq . (3.20) for i.i .d case can be expressed as K-2 a-i,o X • 7 i exp ( - -9o 1 — exp exp .11 9o (fc + l ) 7 i 90 (3.21) Similarly, the probability a^i that information is transmitted to both the selected users using uniform 4 - Q A M constellation can be expressed as (3.22) 0-1,1 ri2 r9(i) / / P9(i)9(2)(9(i),9m)dg{2)dgw. •/ 71 J 71 '71 Jl\ For the i.i.d. case, the integral in Eq. (3.22) can be evaluated in closed-form (see the Appendix 9.1.5). K-2 K{K-l)(K-2\/ + ! / (fc + 2 ) 7 A k=0 —exp k + 1 12 go ( - 1 ) * k + 2 exp exp (fc + l ) 7 i \ , e x P 9o + 9o (fc+l)72 \ so y V fc + 2 (3.23) The average link spectral efficiencies (Rr^/W (i = 1,2) for information transmission to the users U(i) and U( 2 ) , respectively, are just the sum of data rates associated with the in-dividual sub-regions of each region, weighted by the probabilities aTiS and can be expressed as w w. Q r-1 ^ ^ 2 ( r - s) ar,s + fli,i, r-l s=0 Q r-l = ^ 2 \ y 2 2 s ar,s+ai,i-(3.24) (3.25) r=2 s=l Using Eqs. (3.14), (3.17), (3.21) and (3.23), the average spectral efficiencies in Eqs. (3.24) and (3.25) for the i.i.d. case can be expressed in closed-form. For the two-best user opportunistic scheduling the sum average SE can be obtained by adding the individual S E of the selected users. The sum average S E (R2)/W is, therefore, given by (R2) _ (RW) (R{2)) (3.26) W W W In SBS the overall average S E using discrete rate adaptive square uniform Q A M con-stellations, (Rl) jW is given by w Q (3.27) r=0 41 where ar are the probabilities that the C N R g^ falls in the regions r (r = 0,1, • • • , Q) and can be expressed as For a given constellation parameter, p the achievable overall average SE with our pro-posed rate adaptive T B S scheme, in an i.i.d. fading environment, is plotted in Fig . 3.5. The achievable S E in SBS is also plotted in this figure. According to classical theory, one would expect a degradation of the overall average S E i f second best user is included in a transmission. However, from Fig. 3.5, we observe that there is no degradation of overall average S E with our proposed two-best user scheduling scheme. This is because our pro-posed scheme selects the constellation size according to the first best user's channel C N R in order to maximize the S E while satisfying a target B E R . Then second best user is in-cluded in the transmission i f and only i f its channel quality is good enough to support the information transmitted in the first hierarchy of the selected size hierarchical constellation while the first best user can decode information transmitted in the second hierarchy with required reliability. Otherwise information is transmitted only to the first best user using the selected size uniform Q A M constellation. In other words, our proposed scheme exploits the finite C N R gap between the two rate switching thresholds in conjunction with hierar-chical constellations to include the second best user in a transmission. Therefore, inclusion of the second best user in a transmission system does not affect the selected discrete con-stellation size (i.e., the instantaneous SE) at all and two-best user scheduling experiences no degradation of overall average S E compared with the single best user scheduling. It is also obvious from Fig. 3.5 that the overall S E increases as the number of users increases in the system for a given value of the average C N R , g0. This is due to the multiuser diversity gain. The overall SE also increases as the average C N R of the users increase for a given number of users in the system, as expected from the concept of adaptive modulation (e.g., see [38]). . (3.28) Using Eq . (3.2), Eq. (3.28) can be expressed in desired closed-form as (3.29) 42 3.3.2 Access probability Since the proposed scheme transmits information to the first best user irrespective of the second best user i f its channel C N R is above the threshold 71, the probability, P a : 1 that the selected first best user gets information access with or without second best user is given by r+oo pa:i = / Pgm(9(i))dg(i)- (3.30) Using Eq . (3.2), the probability, P a :, in Eq. (3.30) can be written in desired closed-form as P-' = E (Kk *) ( ~ 1 ) f c f c T T e x p { ~ { k + l h l / 9 o ) • ( 3 3 1 ) fe=0 ^ / For i.i .d. channel variations among K users, the probability that a user w i l l be selected to be transmitted in single best user scheduling is 1/K. Therefore, i f discrete rate adaptive Q A M constellations are used in single user scheduling, the information access probability of a given user is expressed as p2- = jc E (Kk ') (- 1 ) f cfcfl e x p {~ { k + l h M • ( 3 3 2 ) k=0 ^ ' The probability of transmitting information simultaneously to both selected users U(i) and U( 2 ) , is the sum of all the individual information transmission probabilities to these users in each fading sub-region. These probabilities are denoted by {or,s}ffij=i a n d con-sequently the information access probability of the users U ( 1 ) and U( 2) simultaneously, P S 2 can be expressed as Q r - l r = l s = l Using the values of {ar>s}f=^s=i which have been derived in Section I V - A , the probability P S 2 in Eq . (3.33) can be evaluated in desired closed-form. The probability of transmitting information to the selected first best user, U(i) without user U(2) is equal to the probability, P a : , that the selected first best user gets information access with and without user U( 2) minus the probability, P S 2 that both users U(i) and U( 2) get information access simultaneously. This probability denoted by Psj can be written as P S l = P a : , - P S 2 . (3-34) 43 4.5 — Two-best user scheduling (proposed scheme) * Single best user scheduling (conventional scheme - — 7 - -'— Ave rag / e CNR, g^lSdB ' Average CNR, g^=12dB r / — 7 Average CNR, ^=10 dB 91 I I 1 1 1 5 10 15 20 25 30 Number of users in the system Figure 3.5: Overall S E versus number of users (SE curves for single and two-best user scheduling overlap). Figure 3.6: Information access probability versus number of users. 44 For i.i .d. channel variations among K users, the probability that a user w i l l be selected to be transmitted in two-best user scheduling is 2/K. Therefore, the probability of informa-tion access by a user, P 2 c c c s s is expressed as P 2 = — P S l + — P S 2 - (3-35) access J£ s l 1 j£ *2 ^ ' Using Eqs. (3.32), (3.33) and (3.34) and after some manipulations, Eq. (3.35) can be expressed as \K-\ , r , l N „ Q r - l P> - I access E ( K k 1 ) ( - 1 ) ^ n p ( - ( f c + 1 ) ^ ) + E E ^ fc=U ^ ' r = l s=l (3.36) The information transmission probabilities with single and two-best user opportunistic scheduling schemes are plotted in Fig . 3.6. This figure shows that in an i.i.d. fading environment our proposed two-user scheduling offers almost double information access probability compared with the conventional single best user scheduling. This result is ex-pected because the proposed scheme includes the second best users in the transmission. The figure also shows that the information access probability changes as the average C N R of the users is varied. Since the proposed scheme schedules opportunistically the second best user, by jointly considering the first and second best users' channel C N R s (as shown in Fig. 3.4), the access probability depends on the shape of the joint PDF. Obviously, the shape changes with different values of the average C N R and consequently, the access prob-ability changes. In addition, as expected, the access probability also decreases with the number of users. 3.3.3 Effect of constellation parameter As we have described in Section 3.1.2 that each hierarchical constellation has a priority parameter, p which controls the relative positions of the symbols within the constellation. The relative importance level of the bits transmitted in different hierarchies can be varied by changing the parameter p as illustrated in [37]. Equivalently, the two hierarchies require two different C N R s in order to meet a given target B E R . These C N R thresholds can also be varied by changing the parameter p. In this section, we study the effect of the priority parameter on the average S E and the information access probability. Since the alphabet size of uniform Q A M constellations is selected according to the first best user's C N R , there is 45 Figure 3.7: Average S E versus priority parameter p (g0 = 15[dB]). no effect of p on the overall average SE. However, the parameter p has an effect on the individual S E of the first and second best which are plotted in F ig . 3.7. This figure shows that for a given number of users in the system as the value of p increases, the second best user's average S E decreases while that of first best user increases. We can also observe that the SE curves of the first best user with different number of users intersect each other. The main reason of the intersection is as follows. Both the selected users' information access 1/2 probability as well as the S E depends on the values of switching thresholds, jr's and the shape of the two dimensional joint P D F Pp (1) f f (2)(<7(i), <7(2)) with respect to the switching thresholds. The shape of the joint P D F changes as the number of users changes in the system. On the other hand, i f the values of constellation parameter p are changed, the values of the thresholds are changed. Therefore, for some values of K and p, it can happen that the location and shape of the joint P D F in g^) — gp) plane and the switching thresholds are in a good fit which results in higher transmission opportunity for the first best user than that with some other values of K and p. A s such the S E for the first best user intersects with, each other for different values of K and p as observed in Fig . 3.7. The information probability of the first best user does not change with p as information 46 1 rjl i i 1 1 1 1.5 2 2.5 3 3.5 4 Constellation priority parameter, p Figure 3.8: Second best user information access probability versus priority parameter p (g0 = 15[dB]). is transmitted to the first best user as soon as it's channel quality is good enough to support 4 - Q A M . However, the information access probability of the second best user is changed with p as shown in Fig . 3.8. Since the first best user's information access probability does not depend on p, maximizing the second best user's information access probability with respect to p maximizes the overall information access probability of a given user. F ig . 3.8 shows that there is a specific value of p for which second best user has a maximum value of information access probability and consequently the overall information access of a given user is maximized. There is also intersection between the curves of information access probability of user U( 2) for different values of K as observed in Fig . 3.8. The main reason of this intersection is similar as the reason explained for the intersection of the average S E curves earlier. 47 3.4 Conclusion In this chapter, we have proposed and studied a new discrete rate adaptive hierarchical modulation-assisted T B S scheme. The newly proposed scheme proposes to transmit in-formation to single or two best users judiciously by the joint consideration of the channel qualities of the users. As such the frequency of information of the users increases without any degradation of overall S E compared with the classical single best user scheduling. For our newly proposed scheme we have derived expressions for the achievable overall S E and the information access probability. The presented numerical results, for an i.i .d. Rayleigh faded environment, have shown that our proposed scheme offers more frequent information access without any overall S E degradation compared with the conventional single best user scheduling. 48 Bibliography [36] M d . J. Hosssain, M . - S . Alouini , and V. K . Bhargava, "Multi-user opportunistic scheduling using power-controlled hierachical constellations," IEEE Trans. Wireless Commun., to appear in M a y 2007. [37] P. K . Vitthaladevuni and M . - S . Alouini , " A recursive algorithm for the exact B E R computation of generalized hierarchical Q A M constellations," IEEE Trans. Inform. Theory, vol. 49, pp. 297-307, Jan. 2003. [38] A . J. Goldsmith and S.-G. Chua, "Variable-rate variable-power M Q A M for fading channels," IEEE Trans. Communs., vol. 45, pp. 1218-1230, Oct. 1997. [39] T. Eng, N . Kong, and L . B . Milstein, "Selection combining schemes for R A K E re-ceivers," in Proc. 4th Int. Conf. Univ. Personal Commun. (ICUPC'95), Tokyo, Japan, Nov. 1995, pp. 426-430. 49 Chapter 4 Two-User Opportunistic Scheduling using Hierarchical Modulations in Wireless Networks with Heterogenous Average Link Gains 7In [43], authors have analyzed various performances of single user selection diversity schemes in a multiuser environment. There are two important metrics in order to compare performance of opportunistic scheduling schemes. One is the degrees of fairness (DOF) which gives the measure of how the total resource, e.g., system's SE, is shared among the users. For a system with identical average fading gain, in the long run, all the users in the system have the fair sharing of the system's resource. However, DOF metric is very impor-tant for a multiuser system where different users have different average channel qualities. Another important metric is the frequency of information access which corresponds to the average wait time in order to get information access. This is important for the time-out consideration in the upper-layer protocols [43]. Even if the users have identical average channel fading gain, lower frequency of information access may result in higher queuing delay and packet loss rate for memory limited system [42]. In Chapter 3 we have proposed a rate adaptive hierarchical modulation-assisted TBS. The performance of the proposed TBS is also analyzed in a fading environment where all the users in the network experience identical average channel fading gain. In an wireless system, where cell size is not smaller and slow power control is used, identical average channel quality for different users can be achieved. However, for cellular system with 7 The research work presented in this chapter is submitted as Md. J. Hossain, M.-S. Alouini, and V. K. Bhargava, "Two-User Opportunistic Scheduling using Hierarchical Modulations in Wireless Networks with Heterogenous Average Link Gains", submitted IEEE Trans. Commun., May 2007. 50 larger cell size, different users may have different average channel quality due to the path-loss and shadowing differences. In this chapter, first, we analyze the performance of the rate adaptive hierarchical modulation-assisted T B S in a heterogenous fading environment where different users have non identical average link fading gains. Specifically, we present expression for the S E of the users and using this expression, we compare D O F of the T B S with that of classical single user opportunistic scheduling schemes, namely, absolute CNR-based SBS and normalized C N R based PFS. Second contribution is that we propose a new H T S scheme based on our earlier proposed T B S in Chapter 3 (also refer to [40]). This H T S selects the first user based on the largest absolute C N R value among all the users while the second user is selected based on the ratios of the absolute C N R s to the corresponding average C N R s of the remaining users. The total transmission rate i.e., the constellation size is selected according to the absolute C N R of the first best user. The total transmission rate is then allocated among these selected users by joint consideration of their absolute C N R s and allocated number of information bit(s) are transmitted to them using hierarchical modulations. Numerical results are presented for a fading environment where different users experience independent but non-identical (i.n.d.) channel fading. 4.1 System and Channel Models We consider a single cell system where K users are communicating with a single B S . The B S transmits a fixed amount of power in each channel access unless a transmission outage is declared. It is assumed that the channel qualities of the users are perfectly estimated and reported to the BS without negligible delay in the form of absolute C N R . We consider that the fading amplitude of the users is characterized by the Rayleigh P D F which leads to the following P D F of fcth user C N R gk, p9k (g) where gk is the average channel gain of user k. Cumulative distribution function (CDF) of (4.1) A;th user's C N R , P9k (x) is expressed as (4.2) 51 4.2 Classical Single User Scheduling: Overview 4.2.1 Absolute CNR-based single best user scheduling According to the classical opportunistic scheduling with uncoded adaptive Mr — 2 2 r - Q A M constellations (r £ {1,2, • • • , Q}), the scheduler at the B S selects the user (denoted by U(i)) who has the largest C N R among all the users. If the C N R of the user U(i) , <?(i) falls in the rth fading region, the constellation size Mr is transmitted. The region boundaries {lr}®=i are set to the C N R such that the information bits are sent below the target B E R , B E R 0 using the uniform M r - Q A M constellation. A transmission outage occurs i f the #(i) falls below the threshold 71 . Since this scheme selects the user in a given time slot accord-ing to the absolute value of the instantaneous C N R , it is referred to as absolute CNR-based single user scheduling scheme (ASS) [43] 4.2.2 Normalized CNR-based single user scheduling The PFS scheme selects a single user to be transmitted based on the relative channel strength [41] which is defined as the ratio of the data rate each individual's channel can afford to its average throughput. A n alternate view point of the original PFS is presented in [44]. Basically, according to this view point, the B S transmits to user k with the largest ratio of the instantaneous C N R to its own short-term average C N R . This alternate view point is used in order to select the second best user in our newly proposed H T S scheme. Without loss of generality, let us consider rath user is the first best user at time slot n and its absolute C N R is gm(n). Then basically, the selected second user is the user who has the highest k^m, (4.3) 9k where gk(n) and gk are kth user instantaneous C N R at time slot n. Once a user is selected to be transmitted, the constellation size Mr is transmitted i f the instantaneous C N R of the selected user falls in the rth fading region. Since in each time slot, the B S selects the user with the largest C N R to its own average C N R , it has been referred to as the normalized C N R based scheduling scheme (NSS) in the literature. It offers the highest fairness among the users at the expense of certain amount of multiuser diversity gain. 52 4.3 Proposed Two-User Opportunistic Scheduling Since we analyze the performance of the rate adaptive T B S in an i.n.d. fading environment and a H T S is proposed based on the T B S , in what follows, we briefly describe the hierar-chical modulation-assisted T B S (refer to [40] for the detailed description of the T B S and its performance in an i.i.d fading environment). We then present our newly proposed H T S in Section 4.3.2. 4.3.1 Two-best user scheduling The details of rate adaptive T B S scheme has been described in Chapter 3 (also refer to [40]). However, since in this chapter we propose a H T S capitalized on the concept of the rate adaptive hierarchical modulation-assisted T B S , we present a brief over view on this scheme. Basically, according to the available instantaneous C N R reporting from all the users, the B S scheduler selects two users, namely the first best user (denoted as U(i)) and the second best user (denoted as U( 2)), whose channel gains are the first and second highest, respectively. Without loss of generality let us denote, the channel gains of user U(i) and U( 2) by g^) and <?(2), respectively with g(i) > g(2). The working principle of the rate adaptive hierarchical modulation-assisted T B S can be divided into two phases as described below. C o n s t e l l a t i o n s i z e , Mr s e l e c t i o n The constellation size is selected according to the first best user C N R , g^. Basically, the C N R range of the user U(i), g<i) is divided into Q + 1 fading regions; namely r = 0,1,2, • • • , Q. When the received C N R , g^ is estimated to be in the rth fading region, the constellation size Mr = 22r (where 2r is the total number of bits per M r - Q A M symbol) is transmitted. The region boundaries (or constellation size switching thresholds) {ir}r=i are set to the C N R s such that the information bits are sent below the target B E R , B E R 0 using the uniform M r - Q A M constellation. Once the constellation size is selected, the total available transmission rate 2r is divided among the selected best users, U(i) and U( 2) jointly considering their channel C N R s as described below. 53 Transmission rate allocation to the selected users U(i) and U(2) To transmit information to the selected second best user opportunistically, the scheme switches between the uniform and hierarchical constellations jointly considering the C N R estimate fluctuation of the two-best users as follows. A s described in [40] that a Q A M constellation of order Mr = 2 2 r, (r = 2,3, • • • , Q) can form a set of hierarchical con-stellations Cr = {2 2/2 2 r, 2 4 /2 2 r • • • , 2 2 ( r - 1 V2 2 r }. Each hierarchical constellation in the set, C r has two different hierarchies, namely first and second hierarchies and it specifies a unique combinations of bits in two different hierarchies. Furthermore, these two different hierarchies have two different C N R requirements in order to decode the transmitted bits with a given reliability. Therefore, in a given fading region, the number of bits within the constellation that can be assigned to the users U(i) and U( 2) jointly depends on the received C N R estimate of both the users. To assign the available transmission rate (i.e., the number of the bits) to the selected users, U(i) and U( 2 ) , the rth fading region (r = 2,3, • • • , Q) is divided into s = 0,1, • • • , r — 1 sub-regions. The sub-region boundaries {7r,s}r=2~s=i ^ obtained by numerically solving the B E R equations of the hierarchical 2 2 s / 2 2 r - Q A M such that the bits assigned in the second hierarchy are sent below the target B E R , B E R 0 . When the C N R of the first best user is estimated in the sth sub-region in the rth fading region, 2(r — s) bits in the second hierarchy can be decoded by the first best users with the required reliability 8 . However, in order to decide whether to transmit information to the user U(2) or not, the channel C N R of the second best user, g/2) is checked. If g@) is good enough to decode the 2s information bits transmitted in the first hierarchy with the required > reliability, these bits are transmitted to the user U( 2 ) . Consequently, hierarchical 22s/22r-Q A M is transmitted from the demodulator. Otherwise, the available total transmission rate r is assigned to the user U(i) using the uniform 2 2 r - Q A M . Therefore, i f the channel C N R , ^(i) falls in a given sub-region, the demodulator can transmit either the uniform constellation or the hierarchical constellation depending on the C N R estimate g^)- The switching between the uniform and the hierarchical constellations in a sub-region s (s = 1,2, • • • , r - 1) of the fading region r (r = 2,3 • • • , Q) depends on the C N R , g<2) and is determined by the thresholds, {ll 8}®=2~s=v These thresholds 7 * are selected such that the 8In sub-region 0 of a given region r corresponds to transmission to only the first best user using uniform 2 2 r - Q A M . 54 s bits assigned in the first hierarchy of 2 2 s / 2 2 r - Q A M are transmitted below the target B E R , B E R 0 . It is important to mention that in the first fading region (r = 1 ) , the scheme proposes to transmit 4 - Q A M which has only one hierarchy. However, it has two different phases; in-phase and quadrature phase. If the second best user's C N R can support 4 - Q A M as well , an information bit is transmitted in one of the phases for the first best user and an information bit is transmitted in the other phase for the second best user. 4.3.2 Newly proposed hybrid two-user scheduling We wi l l see in the numerical results section, in this chapter, that the T B S scheme can in-crease the system's fairness without any degradation of link S E compared with the classical SBS scheme. However, the system's fairness can further be improved i f the second user is selected according to a selection criterion that is equivalent to the selection criterion of the PFS scheme. For the newly proposed HTS, the first user selection, the constellation size selection and the rate allocation procedures remain same as described in Section 4 . 3 . 1 . The only difference is in the selection procedure of the second user. The proposed H T S scheme is described below in details. • Step 1: Select the first best user, U(i) and its instantaneous C N R g^, based on the absolute values of instantaneous C N R s of the users. • Step 2: Remove user U(i) from the users' set. Then calculate gk using Eq. ( 4 . 3 ) for all k except user U(i) who has selected as the best first user in Step 1. • Step 3: Find rh such that rh = argmax(<7fc) V k except user ( 4 . 4 ) and set 9(2) - 9m- ' ( 4 . 5 ) • Step 3: Select the constellation size, Mr = 2 2 r i f g^ falls in [ 7 , . , 7 r + i ] . • Step 4: Check whether g m falls in [7^.7^+1] a n d 9(2) falls in [7r, s ,7r , a +i ] - I f 1 1 i s true, transmit 2s bits of information for the user tj(2) and 2 ( r — s) bits of informa-5 5 tion for the user U(i) using hierarchical 2 2 s / 2 2 r - Q A M constellation. Otherwise, 2r information bits are transmitted for user U(i) using M r - Q A M constellation. It is important to mention that both users, in rate adaptive T B S scheme, are selected according to the absolute C N R s of the users. In contrast, the newly proposed H T S scheme selects the first user based on the largest value of absolute C N R of all the users whereas the second user is selected based on the ratio of absolute C N R s to the corresponding average C N R s of the users except the user who has been selected as the first user. The newly proposed two-user opportunistic scheduling is, therefore, referred to as the hybrid two-user scheduling. 4.4 Performance Analysis 4.4.1 Two-best user scheduling In our following analysis, we consider j t h user as the tagged user. Without loss of gener-ality, we denote the first and the second largest C N R of all the users' C N R s except user j, by g*^ and g*2y respectively. It is important to mention that basically there are three possibilities, namely, Scenario 1, Scenario 2 and Scenario 3 of receiving information by user j with the rate adaptive T B S scheme. These scenarios and the associated probabilities are described below. S c e n a r i o 1 - I n f o r m a t i o n t r a n s m i s s i o n o n l y t o u s e r j a s t h e first b e s t u s e r : In such sce-nario, 2r information bits are transmitted only to jth user using uniform 2 2 r - Q A M constel-lation. This happens again in two cases. One is that i f the C N R of jth user, gj is greater or equal to the largest C N R of all other users, gfo and it falls in the Oth sub-region of fading region r (r = 2,3 • • • ,Q). The other is that the first largest C N R of all other users, gfo is less than the threshold 7* a although the C N R gj is greater than or equal to g*^ and falls in sth sub-region (s = 1,2, • • • , r - 1) in the rth fading region (see Fig . 3.4 for details). Therefore, the total probability, a^J that the uniform 2 2 r - Q A M constellation is transmitted to jth user in the rth fading region is the summation of all the individual probabilities and can be written as aH= / P9j(x) / Pg*w{.z)dzdx-+Yl / ' P9j(x) / Pg*w{z)dzdx (4-6) J-yr Jo s = 1 J-y?<s JO 56 where pg* (x) is the P D F of the largest C N R of all the users' C N R except user j and which is expressed as [45] K K E n p ^ ) - (4-7> k=l,k^j m=l,m^k,j The first integral in Eq . (4.6) has the form of integral / { ( t i , ^ ) presented in Eq . (9.4) of Appendix B whereas the second integral has the form of integral (*i ^ ^2, h) presented in (9.6) of Appendix B . Therefore, a^'J in Eq. (4.6) can expressed as r - l «S = H(lr,7?i) + E ^ ^ 1 , 7 ^ ) ' (4-8) s = l where the integrals i i (•, •) and (-,-,•) are evaluated in closed-form in Eqs. (9.5) and (9.7) of Appendix B , respectively. S c e n a r i o 2 - I n f o r m a t i o n t r a n s m i s s i o n t o u s e r j a s t h e first b e s t u s e r a l o n g w i t h t h e s e c o n d b e s t u s e r : In such scenario, 2(r — s) information bits are transmitted to j th user (as the first best user) and 2s information bits are transmitted to another user (as the sec-ond best user) using hierarchical 2 2 s / 2 2 r - Q A M constellation. The probability, aj'j that the 2(r - s) bits of information are transmitted to j th user using 2 2 s / 2 2 r - Q A M constellation corresponds to the probability that the C N R , is greater than g*,x) and falls in sth sub-region in the rth (r > 1) fading region while g*IVj is above the threshold 7 ^ . Therefore, the probabilities a£j can be written as /7?;+1 P9j (x) p g h (y)dydx, s = 1,2, • • • , r - 2, (4.9) ur,s 2 { Q*1 Pa>(x) A . P s ^ (y)dydx> s =r - 1 . Both integrals in Eq. (4.9) have the form of integral P3(ti, t2, £3) which is evaluated in closed-form in Eq . (9.9) of Appendix B . Therefore, the probabilities a£j. can be expressed as al<] = \ ^ ^ 7 * 8 + 1 ' ^ * = 1> • • • , r - 2, ( 4 i Q ) ( ^ ( 7 r 2 , S . 7 r + l » 7 r , J S = T - 1. Recall from Section 4.3.1 that in fading region r = 1, 4 - Q A M constellation is transmit-ted and the first best user receives information along with the second best user i f the second 57 best user's channel quality is above the threshold 71 . In such scenario, 1 bit of information is transmitted in the inphase channel for the first best user and 1 bit of information is trans-mitted for the second best user in other phase. The probability, a]'* that 1 bit of information is transmitted to j th user using uniform 4 - Q A M constellation while it is the first best user, can be written as I P9j(x) / pg*w(y)dydx. (4.11) n , i '71 J t i The integral in Eq. (4.11) has the form of integral l£(ti, i 2 , h) in Eq . (9.8) which is given in closed-form in Eq. (9.9) of Appendix B . Therefore, o?{l can be expressed as a i i = ^ ( 7 i , 7 2 , 7 i ) - (4-12) S c e n a r i o 3 - I n f o r m a t i o n t r a n s m i s s i o n t o u s e r j a s t h e s e c o n d b e s t u s e r a l o n g w i t h t h e first b e s t u s e r : In this scenario, j t h user receives 2s bits of information as the second best user along with the another user (as the first best user) using hierarchical 2 2 s / 2 2 r - Q A M constellation. This happens i f gj is equal to or greater than c/(*2) as well as it falls above 7 ^ while the C N R g*{1) falls in the sth subregion (s = 1,2, • • • , r - 1) of the rth fading region. This probability, a3)2 can be written as f 2 7r,.9+l rx 0% = £ r + ^ , 3 ^ W s = l , 2 , . - . , r - 2 , (4.13) k fiC1 A . P« { V ) ^0 P S(V(2) ^ Z)dzdVdX- S = r 1 where Pg*wg*{2) (x,z) is the joint P D F of the largest two C N R s of all the users' C N R s except user j and which is given by [45] K K K P9U)9U)(X>Z) = Z ^ f a ) Yl P9l(Z) II ^ ( 4 < 4 ' 1 4 ) k,k^j l=l,lyij,k m=l,m^j,k,l The integrals in Eq . (4.13) are of the form of integral li(ti,t2, t3) i n E q . (9.10) of Appendix B . Therefore, a3)2 can be expressed as . 0 Mi(7r , s> 7r , s +i) 7r,s) s = l , - - - , r — 2, a>ri = \ . (4-15) [ ^ ( 7 r 2 , s > 7 r2+ i , 7 r , s ) s = r - l where IJ4(-, •, •) is evaluated in closed-form in Eq. (9.11) of Appendix B . 58 The probability, aj ' 2 that 1 bit of information is transmitted to j t h user using the uniform 4 - Q A M constellation while it is the second best user can be expressed as [•12 rx ry a\l= I I Pgjiy) p9'W9{2)(x>z)dzdydx- (4-16) J 71 J 71 J 0 This integral has the form of integral l((ti, t2,t3) in Eq . (9.10) of Appendix B . Therefore, a{i can be expressed as < i = ^ ( 7 i , 7 2 , 7 i ) - (4-17) S p e c t r a l e f f i c i e n c y The average link spectral efficiencies of j th user as the first and the second best user, re-spectively, {Rj/€))/W (i = 1,2) are just the sum of data rates associated with the individual sub-regions of each region, weighted by the probabilities a£j. and aJr'2s, respectively and can be expressed as <4)> Q r-l r = l s=0 ^ = £ 5 > a « + a g . ( 4 . 19 ) r=2 s = l Since a given user can get information access in a given time slot either being as the first best or as the second best user, the overall S E of ;'th user with T B S , L - ^ L is the summation of individual S E as the first and second best users i.e., <z4s> _ (4)> (4)) W W W Using Eqs. (4.18) and (4.19), in Eq . (4.20) can be written as Q r-l Q r-l + ^ ^ . (4.20) (RjB w = £ £ 2(r - *) °H+<i + £ £ 2 * « + < 4 - 2 1 ) r=l s=0 r=2 s = l The system's link SE with T B S , can be obtained by adding users' individual spectral efficiencies as follows: w -I-, w • .7=1 59 Using Eq. (4.21) in Eq . (4.20), c a n expressed as w K / Q r - l Q r - l {RTBS} W j=l \ r = l s=0 r=2 s=l Degree of fairness There are different ways to quantify the D O F (see [43] and references there in). In this dissertation, the D O F for j t h user is measured as the portion of the system's link SE is attributed by j th user. Therefore, the D O F of user j, FJ, in general, is defined as l 0 e ( 1 0 § ^ (R)/W ) p = v y " / (4.24) where (RJ)/W is the j th user's SE, (R)/W is the system's link SE . Therefore, F° is the proportion of system's resource (e.g., the link SE) attributed to user j . In general, the average fairness of a multiuser system is then defined as F ~ ^ (R)/W log(*) • ( 4 ' 2 5 ) Therefore, the average fairness of a multiuser system with T B S scheme, F T B S can be written as F t B S " " log(iv) • ( 4 - 2 6 ) F T B S in Eq . (4.26) can be evaluated using Eqs. (4 .21) and (4.23). 4.4.2 Hybrid two-user scheduling In order to evaluate the S E performance for our proposed rate adaptive H T S , we need the expresssion for the joint P D F of the channel fading gains of the first best user and second user who is selected according to the normalized C N R . Once the expression of the joint P D F is available, the SE well as the D O F performances of the H T S can be found analytically using similar methodology as described above. However, to the best of our knowledge, the expression for the joint P D F is not known. Finding this expression remians as open research problem. We evaluate the performance of the proposed H T S via computer simulation as reported in Section 4.5. 6 0 4.4.3 Single user scheduling Spectral efficiency In absolute CNR-based SBS, the S E of jth user and the system's link SE with adaptive M - Q A M transmission, ffi can be written as w Q (4.27) r=0 where o?r are the probabilities that j t h user's C N R is larger than the largest C N R of all other users' C N R and falls in the rth fading region. Therefore, o?T can be expressed as a i = P9j(x) / Pg;(y)dydx. J~lT JO Using Eqs. (4.1) and (4.7), a?T can be evaluated as 4 = f P9j(x) f t ( l - e x p ( - — ) )dar hr V 9k)) = / Pfjix) V, sign(r')exp (—T'X) dx JIT , ' c T i f (4.28) exp — X(T + —) ) dx 9j V 9j sign(r') ^ r'gj + 1 7 r ( ^ 7 r ' + 1) exp | - v \ ) - exp 9j lr+l(9jT + 1) 95 .(4.29) <*ASS> Using Eq . (4.29) in Eq . (4.27), average S E of j th user, can finally be expressed as (Rjss) w Q = £ £ r=0 r'eT* 2rsign(r') (r'gj +1) e x p f - 7 ^ I + 1 ) V e x P ^ ^ r ' + lY 9j 9j (4.30) The system's link SE with A A S scheme, is the summation of individual user's S E and can be expressed in desired closed-form as follows: (RASS) w K Q = £ £ £ 2rsign(r') (r'9j + 1) L e x p ( _ 7 , f e V + l ) ^ _ e x p / ^ 7 r + i ( f t - r + l ) ' 9j 9j (4.31) 61 In NSS scheme, BS selects user j if it has the largest normalized CNR, i.e., [43] 9j 9j (4.32) and the PDF of rjj is given by pVj(x) = exp(-s). Therefore, in NSS scheme, the SE of jth user, -^p- can be obtained as (4.33) w Q (4.34) r=0 where 6£ are the probabilities that the jth user normalized CNR is larger than the maximum normalized CNR of all other users' normalized CNR and its absolute CNR falls in the rth fading region. Equivalently, 6£ can be expressed as rir+i hi rtr i rx = / PVJ(x) / Pvi(y)dvdx A r JO (4.35) Ijr JO where {•jr}rrZ<Q+1 are the values of constellation size switching thresholds normalized by the average CNR of jth user i.e., % = ^r/9j- Using Eqs. (4.33) and (4.7), Vr can be evaluated as K n v + i " K = Pm(x) 11 ( 1 - e x p (-a;)) jAtr fc=l,fc#j = l exp (—x) (1 - exp(-z)) ldx >1r l_ K Using the Eq. (4.36) in Eq. (4.34), average SE of jth user, can be written in simplified form as K (4.36) ( • R N S S ) W r=0 , , , 7 r \ / 7r+l l - | „ p , - - j - „ p ( - _ K (4.37) The system's link SE with NSS scheme, can finally be written as K Q (RN W 2r K K (4.38) 62 D e g r e e o f f a i r n e s s The D O F of user j with A S S scheme, Fiss can be written as F A S S — ^ ] K (4.39) (R^)/W \og{K) FASS in Eq . (4.39) can be evaluated using Eqs. (4.30) and (4.31). Similarly, the D O F of a multiuser system with NSS, F A s s can be expressed as (RL)/w v l Q g (few) (4.40) ^ {RNSS)/W \og(K) which can be evaluated using Eqs. (4.37) and (4.38). 4.5 Numerical Results We assume a target B E R of 10 - 4 and a maximum M - Q A M constellation size of 1024. Further, we assume a 10 users system where different users are located in 10 different tiers inside the cell. The tiers are uniformly distributed. The average link gain of the far-end user which is located in the cell boundary is assumed to be 10[dB]. We consider that kth user is located in tier k from the cell boundary and its average C N R , gk = (10 + Ag" x A;)[dB] where Ag[dB] is the deviation of average link gains of two successive users due to the path-loss. The near-end user is the closest user to the B S and it has the highest average channel fading gain. For this set up, the system's D O F is plotted in Fig . 4.1 for various values of deviation of average link gains of near-end and far-end users by varying the value of Ag. Four different scheduling schemes are considered in this figure. This figure shows that the newly proposed H T S scheme considerably increases the system's fairness in comparison to the classical absolute CNR-based SBS. Interestingly, there is no degradation of the system SE in comparison to the classical SBS as seen from Fig . 4.2. The reason is that H T S selects the constellation size according to the largest instantaneous C N R fluctuations and the second user is included in a transmission judiciously using the hierarchical modulations. It is also important to mention that since the newly proposed H T S selects the second user based on the normalized C N R criteria, it achieves better fairness than the T B S scheme. On the other hand, the NSS schme i.e., the equivalent PFS, has the highest system's fairness as 63 N I "5 W D i2 m c >> o S> 5 o 15 Q . . in 4 - e - Hybrid two user (HTS) * Absolute CNR two-best user (TBS) — Normalized CNR single user Absolute CNR single-best user (SBS) V 8 ,/ / / i A A j i A J8; 4 6 8 10 12 14 16 Deviation of average CNRs of near-end and far-end users in dB 18 20 Figure 4.2: L ink spectral efficiency versus number of users (link SE curves for T B S , SBS and H T S overlap). observed in Fig . 4.1 but this fairness comes at the expense of a certain amount of link S E as observed in Fig . 4.2. 4.6 Conclusion In this chapter, we have analyzed the performance of the hierarchical modulation-assisted T B S in a fading environment where different users have different average link qualities. Specifically, we have derived the expressions for the SE, and the D O F of the users. Using these expressions we have compared the D O F of our earlier proposed rate adaptive T B S scheme with those of classical single user opportunistic scheduling schemes. We have also proposed a new HTS scheme. Some selected numerical results showed that the T B S 65 offers higher D O F in a multiuser system with heterogenous link gains than the classical SBS scheme without any degradation of system SE. The HTS scheme offers higher D O F than both T B S and SBS without any degradation of system SE. Compared with the NSS scheme, both T B S and H T S has lower D O F but NSS suffers from certain degradation of system SE. 66 Bibliography [40] M d . J. Hosssain, M . - S . Alouini , and V. K . Bhargava, "Rate adaptive hierarchical modulation-assisted two-user opportunistic scheduling," IEEE Trans. Wireless Com-mun., to appear in Jun. 2007. [41] D. N . Tse, P. Viswanath, and R. Laroia, "Opportunistic beamforming using dumb antennas," IEEE Trans. Inform. Theory, vol. 48, pp. 1277-1294, Jun. 2002. [42] M d . J. Hosssain, M . - S . Alouini , and V. K . Bhargava, "Upper-layer performance anal-ysis of multiple best user opportunistic scheduling scheme using power-controlled hi-erarchical constellations," in Proc. of IEEE Global Telecommun. Conf. (Globecom'06), pp. 1267-1272, San Fransisco, C A , Nov. 2006, pp. [43] L . Yang, and M . - S . Alouini , "Performance analysis of Multiuser Selection Diversity," IEEE Trans. Veh. Technol., vol. 55, pp. 1003-1018, M a y 2006. [44] F. Berggren and R. Jantti, "Asymptotically fair transmission schedulign over fading channels," IEEE Trans. Wireless Commun., vol. 3, pp. 326-336, Jan. 2004. [45] T. Eng, N . Kong, and L . B . Milstein, "Selection combining schemes for R A K E re-ceivers," in Proc. 4th Int. Conf. Univ. Personal Commun. (ICUPC'95), Tokyo, Japan, Nov. 1995, pp. 426-430. 67 Chapter 5 Queuing Delay and Buffer Distribution of Two-User Opportunistic Scheduling Schemes in Wireless Networks 9 A s we mentioned in Chapter 1 that serviced users in a wireless network with classical SBS scheme suffers from low frequency of information access. This results in higher queuing delay of the packets at the transmitter buffer. This has motivated us to design two-user opportunistic scheduling schemes which are presented in Chapters 2, 3 and 4. In Chap-ter 2, we also analyzed some link layer performances of our proposed power-controlled hierarchical modulation-assisted multi-user opportunistic scheduling scheme. Specifically, we analyzed and compared buffer distribution, average buffer occupancy (or delay) and P L P of both SBS scheme and power-controlled hierarchical modulation-assisted T B S via simple queuing analysis. Recently authors in [47] have analyzed various delay statistics of the classical SBS scheme via queuing analysis. The importance of delay analysis is to facilitate an admission controller design in order to maintain a statistical guarantee of delay bound. On the other hand, buffer distribution provides a picture of the average buffer occu-pancy level and consequently, the average delay. Inspired by the work in [47], we analyze in this chapter, buffer and delay distributions of our proposed rate adaptive hierarchical modulation-assisted T B S and HTS schemes. Then we compare these distributions with those of the classical single user scheduling schemes namely, SBS and NSS . 9The research work presented in this chapter is submitted as Md. J. Hossain, M.-S. Alouini, and V. K. Bhargava, "Queuing Delay and Buffer Distribution of Two-User Opportunistic Scheduling Schemes in Wireless Networks", to be submitted in IEEE Trans. Wireless Commun., June 2007. 68 5.1 Overall System Description and Two-User Scheduling Schemes Let us consider a BS that is transmitting to K mobile users opportunistically. We assume that the channel fading gain among the users varies independently. The users have a target P E R requirement and a corresponding B E R . It is also assumed that the channel fading of a given user varies independently from one time slot to the next time slot. For these K users, there are K separate radio link level buffers that are located at the B S . Data packets are arriving from upper-layer to these buffers with a Bernouli arrival process 1 0. A scheduler is deployed at the BS to schedule the transmissions corresponding to different users in a T D M fashion. Transmissions occur within the fixed-sized time slots. Once a user is selected to be transmitted with a granted transmission rate, the granted number of packets are taken out from selected user's BS buffer and transmitted over the downlink to the selected user. With classical SBS, only one user is granted to receive information in a given time slot. With rate adaptive modulation assisted two user scheduling schemes, one or two users are granted to receive information in a given time slot depending on the channel qualities of the selected users. The details of the rate adaptive modulation-assisted T B S and H T S schemes were described in Chapter 3 and 4, respectively. However, we provide a brief description on each scheme. 5.1.1 Rate adaptive hierarchical modulation-assisted T B S scheme Basically, according to the available instantaneous C N R reporting from all the users, the B S scheduler selects two users, namely the first best user (denoted as U(i)) and the second best user (denoted as U( 2)), whose channel gains are the first and second highest, respectively. Without loss of generality let us denote, the channel gains of user U(i) and U( 2) by gri) and <7(2), respectively with > gi2y The working principle of the rate adaptive hierarchical modulation-assisted T B S can be divided into two phases as described below. l 0 For the sake of simplicity, we use Bernouli arrival process. However, we also provide simulation results for Markov modulated Poisson (MMP) arrival process. 69 C o n s t e l l a t i o n s i z e , Mr s e l e c t i o n The constellation size is selected according to the first best user C N R , g^. Basically, the C N R range of the user U(i), g^ is divided into R -\- 1 fading regions; namely r — 0,1,2, • • • , Q. When the received C N R , g^ is estimated to be in the rth fading region, the constellation size Mr = 2 2 r (where 2r is the total number of bits per M r - Q A M symbol) is transmitted. The region boundaries (or constellation size switching thresholds) { 7 r J v ^ 1 are set to the C N R s such that the information bits are sent below the target B E R , BERn using the uniform M r - Q A M constellation. Once the constellation size is selected, the total available transmission rate 2r is divided among the selected best users, U(i) and U( 2) jointly considering their channel C N R s as described below. T r a n s m i s s i o n r a t e a l l o c a t i o n t o t h e s e l e c t e d u s e r s U ( i ) a n d U ( 2 ) To transmit information to the selected second best user opportunistically, the scheme switches between the uniform and hierarchical constellations jointly considering the C N R estimate fluctuation of the two-best users as follows. A s described in [46], a Q A M constel-lation of order Mr = 2 2 r, (r = 2,3, • • • , Q) can form a set of hierarchical constellations Cr = {22/22r, 2 4 /2 2 r • • • , 2 2 ( r - 1 V2 2 r }. Each hierarchical constellation in the set, Cr has two different hierarchies, namely first and second hierarchies and it specifies a unique com-binations of bits in two different hierarchies. Furthermore, these two different hierarchies have two different C N R requirements in order to decode the transmitted bits with a given reliability. Therefore, in a given fading region, the number of bits within the constellation that can be assigned to the users U(i) and U( 2) jointly depends on the received C N R esti-mate of both users. To assign the available transmission rate (i.e., the number of the bits) to the selected users, U(i) and U( 2 ) , the rth fading region (r = 2,3, • • • , Q) is divided into s = 0,1, • • • , r — 1 sub-regions. The sub-region boundaries {lr,s}?=2~s=i are obtained by numerically solving the B E R equations of the hierarchical 2 2 s / 2 2 r - Q A M such that the bits assigned in the second hierarchy are sent below the target B E R , B E R 0 . When the C N R of the first best user is estimated in the sth sub-region in the rth fading region, 2(r — s) bits in the second hierarchy can be decoded by the first best users with the required reliabili ty 1 1 . However, in order to decide whether to transmit information to the "In sub-region 0 of a given region r corresponds to transmission to only the first best user using uniform 70 user U( 2) or not, the channel C N R of the second best user, g^) is checked. If gt2) is good enough to decode the 2s information bits transmitted in the first hierarchy with the required reliability, these bits are transmitted to the user U( 2 ) . Consequently, hierarchical 2 2 s / 2 2 r -Q A M is transmitted from the demodulator. Otherwise, the available total transmission rate r is assigned only to user U(i) using the uniform 2 2 r - Q A M . Therefore, i f the channel C N R , ^(x) falls in a given sub-region, the demodulator can transmit either the uniform constellation or the hierarchical constellation depending on the C N R estimate g<2). The switching between the uniform and the hierarchical constellations in a sub-region s (s = 1,2, • • • , r — 1) of the fading region r (r = 2,3 • • • , Q) depends on the C N R , g^2) and is determined by the thresholds, {lr,s}?=2~s=i- These thresholds 7* s are selected such that the s bits assigned in the first hierarchy of 2 2 s / 2 2 r - Q A M are transmitted below the target B E R , B E R 0 . It is important to mention that in the first fading region (r = 1), the scheme proposes to transmit 4 - Q A M which has only one hierarchy. However, it has two different phases; in-phase and quadrature phase. If the second best user's C N R can support 4 - Q A M as well , an information bit is transmitted in one of the phases for the first best user and an information bit is transmitted in the other phase for the second best user. 5.1.2 Rate adaptive hierarchical modulation-assisted H T S The details of the proposed H T S scheme is described in what follows: • Step 1: Select the first best user, U(i) and its instantaneous C N R g^, based on the absolute values of instantaneous C N R s of the users. • Step 2: Remove user U(i) from the users' set. Then calculate gk using Eq . (4.3) for all k except user U(i) who has selected as the best first user in Step 1. • Step 3: Find m such that m = arg max (gk) V k except user (5.1) g(2) = gfh- (5-2) and set 2 -QAM. 71 • Step 3: Select the constellation size, Mr = 2 2 r i f falls in [7r, 7 r + i ] . • Step 4: Check whether g{1) falls in [7 r 2 s, 7r,s+i] and 5(2) falls in [7^,7^+1]- I f 'li i s true, transmit 2s bits of information for the user U( 2) and 2(r — s) bits of informa-tion for the user U(i) using hierarchical 2 2 s / 2 2 r - Q A M constellation. Otherwise, 2r information bits are transmitted for user U(i) using M r - Q A M constellation. 5.2 Formulation of the Queueing Model Let random variable rJn represent the number of packets that are granted to transmit to user j at time slot n . We assume that random variable represents the number packets at j t h buffer at time slot n and a packet arriving during time interval n — 1 cannot be transmitted until time interval n. If, in a given time slot, n buffer of jth user has less number of packets than the granted transmission rate rJn, min(fr£, rJn) packets are transmitted from jth buffer during that transmission slot. Traffic arrival probability of Bernouli arrival process at the j th buffer process is assumed to be pp. Without loss of generality, we consider the j th user's buffer as the target queue for queuing analysis and drop the superscript for user number in our formulation presented in the next sections. Assuming an infinite buffer size, the state space of the j th user's buffer occupancy and its buffer serving process can be written as follows: ft ={bn, s„) ; bn > 0; s n e {0,1}. 5.2.1 Markov chain analysis We model the system as a discrete time Markov chain ( D T M C ) whose transition matrix can be derived in terms of the state space above by considering the system dynamics. In order to find the transition probability matrix for the joint state of j t h buffer, we derive the state transition matrix for service process r n , M as follows: r0->0 I"0->2 Tn->3 r 0 _ 2 Q r i ^ 2 r l - 2 Q T2-»0 T2^1 f2->2 r 2-»3 r 2 _ > 2 Q i"2Q->o r 2 Q _ i r 2Q-»2 r2<2_,3 • • • r 2 Q _ , 2 Q 72 where r ; _ f c is the probability that the serving rate of target buffer transits from rate / to k and 2Q is the possible maximum transmission rate. These transition probabilities depend on the scheduling policy that are employed at the B S . In fact, the presented analysis can be used for any scheduling policy once the transition matrix in Eq . (5.3) is known for that policy. In this chapter our objective is to analyze the buffer distribution and C D F of queuing delay of our proposed rate adaptive hierarchical modulation-assisted T B S as well as the HTS schemes and compare their performances with those of the classical single user scheduling schemes. Therefore, in what follows, we describe the service rate process and its transition probabilities for our proposed rate adaptive T B S scheme. As it was described in Section 5.1.1, we use square Q A M constellation of sizes 2 2 r (r = 1,2, • • • , Q) for our proposed rate adptive T B S scheme. The total transmission rate, therefore, in a given time slot belongs to the set {2,4,6, • • • , Q}. With the rate adaptive T B S the total transmission rate is allocated among the selected users according to their channel qualities. Recall from Section 5.1.1 that when both selected users' channel qual-ities can support 4 - Q A M constellation, one packet is transmitted for each of the selected users. Therefore, the transmission rate with our rate adaptive T B S scheme, rn belongs to the set 71 = {0 ,1 ,2 ,4 ,6 , • • • , 2Q}. Assuming that users' channels vary independently from one time slot to the next time slot, the transition probability, r ^ f c corresponds to the probability that I packets are transmitted from j th buffer in a given time slot. This proba-bility, Prob.(r n = I) can be written as f a i ' l + a f i , i f Z = l , ' Prob.(r n = I) = { ' n ' , / 9 _ (5.4) \ E j L i EZo aft + £?=i/2+i <i> i f ^ 0,1 where denote the probabilities that 2(r — s) information packets are transmitted to j t h user that is selected as the first best user. Similarly aJrfs denote the probabilities that 2s packets are transmitted to j th user that is selected as the second best user. These proba-bilities have been evaluated in Eqs. (4.10), (4.12), (4.14) and (4.16) of Chapter 4. Please refer to these equations and there after for further details. The probability that no packet is 73 served from j th buffer in a given time slot, Prob.(r n = 0) can be expressed as Prob.(r„ = 0) = 1 - ]T Prob.(r n = I) ie{l,2,4,-,2Q} / Q r-l/2 Q \ - l ~ £ • E E < ! + £ «S • (6{1,2,4,-,2Q} \r=i/2 s=0 r=«/2+l / A s we can see from the feasible rate set of T B S , 1Z, the rate adaptive modulation-assisted T B S scheme does not support odd transmission rate except transmission rate of one, i.e., r n 3,5 • • • 2Q — 1. Therefore, transition probabilities for infeasible transmission rates i.e., r/_»fe (/ = 3,5, 7 • • • , 2Q — 1; Vfc) are set equal to zero in Eq . (5.3). Using the transition probabilities in Eq. (5.3) and assuming an infinite buffer space, the state transition matrix for the D T M C describing the system can be written as Eq . (5.6) in next page. 74 (95) ° H _ T H • • • - ( £ - & Z ) H - ( Z _ & ^ H - ( L _ & E ) H + T H ° H T H + T H ° H ZH R H " & E H + I H OTT -^TT • • • - ^ W u - U - & e J „ +TTT OTT ... -(Z~&Z) -(Z~&Z) + I H ° H ( - ; H -&Z - d - b z ) u ( s ) H ( T ) H ( o ) H ( 0 ) H B y constructing blocks of submatrices as shown in Eq . (5.6), we can obtain a quasi-birth-and-death (QBD) process transition matrix as follows: P -Lo Fo Bx U F B L F B L F (5.7) Now we define a new matrix Kj from matrix M in Eq . (5.3) by keeping the (j + l)stth row and zeroing out other rows as follows: 0 0 0 0 0 0 0 0 r?-o r , -_i Tj^2 r,-_ 3 0 0 0 0 0 0 0 With this matrix defined, we can derive the inner submatrices of P in eq. (5.6) as follows: H 1 + (o) _ H H 0 ( l - / x ) M pM /xK<°> ( 2Q ( l - | i ) E K y ) , if d = c j=c 2Q M E ^ ' + a - ^ - 1 ) , i f d = c - i j=c [ ^ + ( 1 - ^ ) i f l < d < c - l 2Q ( l - p ) K ( ° ' + ^ K ( i ) i=i ( l - r i K i n ^ 1 ' (5.8) (5.9) (5.10) (5.11) A i K ( d + 1 ) + (1 - /x)K (5.12) (5.13) (5.14) 76 5.2.2 Matrix-analytic solution for steady state distributions With the system described by a Q B D type chain whose block matrices are derived in the previous subsection, we can now apply the matrix-analytic method [48] to find its steady state distributions. From these steady state probability distributions, we can derive the steady state probability vectors TT = [ir0,7Ti, 7r 2, • • • ] for queue lengths in the buffer. In fact, the steady-state probability n satisfies the following equations: TTP = TT (5.15) oo = 1 (5.16) i=0 where 1 is a column vector of all ones with appropriate dimension. We can find 7T0, 7T I , and 7 r 2 using the boundary and the normalization conditions. Other values of 7T; (i > 2) can be calculated from 7r 2 through a non-negative matrix R as follows: [48] 7Tj = 7 T 2 R i _ 2 . (5.17) Once the steady state vector, 7r is obtained for the Q B D process, we need to partition 7Tj to obtain the steady-state probability vector of the original transition matrix in Eq . (5.6). Let Nl = [2Q + 1),N2 = 2Q{2Q + 1), and b , = [0 • • • Im • • • 0}T (i = 1,2,, N) be a matrix of size N2 x Nl, where I ^ i is an identity matrix at the ith position. We then user these matrices to obtain the partitions of 7T. The steady-state probability vector representing the case of having I packets in the buffer can be written as: x 0 = TT0 (5.18) x ; = 7 ^ , 1>1, (i-l)N <l<iN and h = l - ( i - l ) N . (5.19) 5.2.3 Derivation of performance measures After finding the state vector, we now can determine the performance measures of interest. We are mainly interested about two important performance measures: the queue length distribution and the distribution of queuing delay for packets belonging to the target queue j. We denote by queuing delay the time between the moment a packet arrives at jth buffer and the moment the packet gets access into the medium for transmission. In other words the queuing delay gives a measure of number of times slots that an incoming packet has to wait at the transmission buffer. 77 Q u e u e l e n g t h d i s t r i b u t i o n The marginal probability of finding I packets in the queue can be written as: PL(1) = b , . l (5.20) where PL{1) is the probability that the buffer has I packets at an arbitrary time. D e l a y d i s t r i b u t i o n The queuing delay distribution for a packet belonging to the tagged user queue is derived by considering an absorbing Markov chain. The chain initializes from the state when the packet arrives the corresponding queue and gets absorbed when the packet reaches the position where it can be selected for transmission by the subsequent time slot. Note that, in this case, there is no arrival in that particular queue while the process moves towards the absorbing state. Therefore, the transition matrix Pabs of the chain can be constructed by setting p = 0. The next step for finding the delay distribution is to determine the initial probability vector for this absorbing Markov chain. However, since the arrival process is memoryless, the steady state probability vector for b packets in the buffer as seen by an arriving packet is nb. Therefore, the initial probability vector for the Markov chain can be written as £ ( 0 ) = 7T. (5.21) After d time slots the state vector of the absorbing chain is £ { d ) = * ( 0 ) P i . (5-22) where Pfbs is the transition matrix derived by multiplying P Q b s with itself d times. Assum-ing that f(d) can be partitioned level by level to reach elements f we can write the CDF of the queuing delay D, Po(d) as r=0,l,-,2Q KJ.tJ) 0<x<r As we mentioned in Chapter 4 that with our proposed H T S scheme finding the proba-bilities that information packets are transmitted to j t h user renders joint P D F of the C N R s of the first best user and second user who has the highest normalized C N R except first best 78 user. Since the expression of this joint P D F is not known, we cannot find the rate transition matrix in Eq. (5.3). However, in Section 5.4, we compute buffer distribution and C D F of queuing delay of our proposed H T S scheme via computer simulation. 5.3 Comparison with Classical Single User Scheduling According to the classical SBS with uncoded adaptive Mr = 2 2 r - Q A M constellations (r e {1,2, • • • , Q}), the scheduler at the B S selects the user (denoted by U(i)) who has the largest C N R among all the users. If the C N R of the user U(i) , g/y falls in the rth fading region, the constellation size Mr is transmitted. In order to evaluate the buffer distribution and delay statistic, we need to obtain the serving rate transition probabilities in Eq. (5.3). Since the considered SBS scheduling scheme supports even transmission rate with square Q A M , the transition probabilities, r/_^ (I = 1,3, •• • ,2Q — l;Vfc) in Eq . (5.3) are set to zero. For a fading environment where the channel fading gain of a given user varies independently one time slot to the next, the probability rj_fc corresponds to the probability that I packets are transmitted from jth buffer. This probability, Prob.(r n = /) can be expressed as Prob.(r n = I) = a\ (5.24) where a\ denotes the probability that jth user is selected as the first best user and its fading gain falls in the Zth fading region. The probabilities a\ (I = 0 ,2 ,4• • • ,2Q) have been evaluated in closed-form in E q (4.27) in Chapter 4. According to the NSS (or equivalent PFS) scheme with uncoded adaptive Mr = 2 2 r -Q A M constellations (r e {1,2, • • • , Q}), the scheduler at the B S selects the user who has the largest normalized C N R among all the users. If the instantaneous C N R of the selected user in the rth fading region, the constellation size Mr is transmitted. Similarly, we can obtain the transition probabilities in Eq. (5.3). Specifically, the transition probabilities, r^k (I = 1,3, • • • , 2Q - 1; Vfc) in Eq . (5.3) are set to zero and the probability, Prob.(r„ = I) can be expressed as Prob.(r n = l)=bj (5.25) where bj denotes the probability that j t h user has the highest normalized channel fading gain and its instantaneous fading gain falls in the Ith fading region. The probabilities bj 79 (I = 0, 2,4 • • • , 2Q) have been evaluated in closed-form in E q (4.34) in Chapter 4. Given the fact that the transition probabilities in Eq. (5.3) are obtained for classical SBS and NSS, we can evaluate the buffer distribution and delay distribution of these schemes using the similar methodology that is described in Sections 5.2.2 and 5.2.3. 5.4 Numerical Results For our numerical results we consider both i.i .d. and i.n.d fading environments. We con-sider a system of 10 users and maximum constellation size of 1024 which corresponds to maximum transmission rate of 10 packets per slot. We assume that users have a target B E R of 1 0 - 4 . We use M A T L A B optimization toolbox to find the rate switching thresholds and statistical toolbox to generate independent Rayleigh fading channel gains for the users. We assume Bernouli packet arrival process to the users' buffers at the B S . We also provide computer simulation results for M M P arrival process. 5.4.1 I.I.D. fading environment For the i.i.d. fading environment, it is assumed that users have an average channel fading gain of 15[dB] and an identical packet arrival statistic. Since we consider a homogenous system, all users have similar buffer distribution and delay performance. Therefore, we consider user 1 as the tagged user and plot its buffer distribution as well as C D F of queuing delay of packets. For a packet arrival probability of 0.15 for Poisson arrival process, the buffer distributions with our proposed rate adaptive hierarchical modulation-assisted T B S and the classical SBS are plotted in Fig . 5.1 whereas the C D F of delay is plotted in Fig . 5.2. From Fig . 5.1, we observe that our proposed rate adaptive modulation-assisted T B S has higher probability that the buffer w i l l remain at low occupancy region than that of the classical SBS . This wi l l lead to low buffer overflow probability for a memory limited system. Fig . 5.2 clearly shows that the T B S can improve the queuing delay of the packets compared with the classical SBS . In other words, with our T B S scheme the probability that an arriving packet w i l l experience less queuing delay is higher compared than that of the SBS . This is because T B S scheme offers more frequent channel access to the users. Therefore, the probability that an arriving packet waits a longer period of time in the buffer 80 Proposed rate adaptive TBS - * - Classical SBS 0.45 r Buffer occupancy, x in packets Figure 5.1: Buffer distribution (i.i.d. fading, Bernouli arrival with packet arrival probabil-i t y ^ . 15 and number of users, K=10). is lower compared with the SBS. 5.4.2 I.N.D. fading environment For the i.n.d. fading environment, we assume that users are located in 10 different tiers in-side the cell. The tiers are uniformly distributed. The average link gain of the far-end user which is located in the cell boundary is assumed to be 20[dB]. We consider that the kth user is located in tier k from the cell boundary and its average C N R , gk = (10 + Ag x fc)[dB] where AgfdB] is the deviation of average link gains of two successive users due to the path-loss. The near-end user is the closest user to the B S and it has the highest average channel fading gain. Since in this i.n.d. fading environment, different users have different average channel fading gains, different users have different buffer distributions and delay performances. Specifically, the near-end user has higher frequency of information access and thus better delay performance. On the other hand, the far-end user experiences low frequency of information access and hence it w i l l have worst delay performance. In our 81 0.9 0.8 o 0.7 w TD II » 0.6 TO 0) !d 0.5 o Js 0.4 S 0.3 o 0.2 o.v 0 1 • HHk-*-*-: / •• / / // / — Proposed rate adaptive TBS - * - Classical SBS i i i 10 15 20 25 30 Delay, d in slots 35 40 45 50 Figure 5.2: C D F of the queuing delay (i.i.d. fading, Bernouli arrival with packet arrival probability=0.15 and number of users, K=10). 82 0.35 HTS • — Classical SBS - * - Proposed rate adaptive TBS - e - NSS S. 0.25 0.15 0.05 — < ? -8 10 12 Buffer occupancy, x in packets 14 16 18 Figure 5.3: Buffer distribution of the near-end user (i.n.d. fading, Bernouli arrival with packet arrival probability=0.4 and number of users, K=10). comparison, we consider the two extreme scenarios; the far-end and near-end users' queues as the target queues. For the far-end user, the packet arrival probability of Poisson arrival is assumed to be 0.01 whereas for the near-end user this probability is assumed to be 0.4. In Fig. 5.5, we plot buffer distribution for the scheduling schemes under consideration. It is important to mention that the buffer distribution of H T S scheme is simulated for the considered i.n.d. fading environment as we cannot evaluate its performance analytically. From this figure we can easily observe that the HTS scheme offers almost similar buffer distribution as the NSS . On the other hand, rate adaptive modulation-assisted T B S has bet-ter buffer distribution than the SBS scheme as buffer distribution is concentrated in the low occupancy region. The C D F of the delay for various schemes are plotted in Fig . 5.6. This figure clearly shows that our proposed H T S significantly improves the delay performance of the far-end user's packet than the T B S and SBS in a i.n.d. fading environment. This is because the HTS scheme selects the second user based on the normalized C N R s of the users and hence the far-end user can get more frequent access to the channel. H T S has cer-tain degradation in delay performance compared with the NSS scheme which significantly 83 Figure 5.4: C D F of the queuing delay of the near-end user (i.n.d. fading, Bernouli arrival with packet arrival probability=0.4 and number of users, K=10). 84 — Classical SBS - * - Proposed rate adaptive TBS HTS -e- NSS 4 5 6 Buffer occupancy, x in packets 10 Figure 5.5: Buffer distribution of the far-end user (i.n.d fading, Bernouli arrival with packet arrival probability=0.01 and number of users, K=10). increases the queuing delay for the near-end user as shown in Fig . 5.3. This is because with NSS scheme the far-end user gets more frequent channel access than the H T S at the expenses of reduced frequency of the near-end user. 5.4.3 Simulation results for M M P arrival process A s we mentioned the assumption of Bernouli arrival process simplifies our queuing anal-ysis presented in this chapter. This is because, in a given time slot, only one packet may arrive. However, in what follows with M M P arrival which is an well accepted traffic model for video traffic over wireless network, queuing analysis becomes more complicated as there are may be infinite number of arrivals in a time slot. In addition due to a memory in the packet arrival process, analysis of delay distribution is not straightforward. Queuing analysis for delay distribution for M M P arrival remains an open research problem. How-ever, we obtain buffer and delay distribution of different scheduling schemes with M M P arrival via computer simulation. In our simulation, we use an arbitrary M M P with two 85 Figure 5.6: C D F of the queuing delay of the far-end user (i.n.d. fading, Bernouli arrival with packet arrival probability=0.01 and number of users, K=10). 86 0.45 0.4 "5 0.35 ° 0.25 & 4 0.2 0.15 S 0.1 0.05 L — Proposed rate adaptive TBS -*- Classical SBS \ L . . \ \ \ \\ \\ i— •—* t- * t— *- « k •——> 6 8 10 Buffer occupancy, x in packets 12 14 16 Figure 5.7: Buffer distribution (i.i.d. fading, M M P arrival and number of users, K=10). possible rates A i = 0.1 and A 2 = 0.2 for arrival traffic. A n arbitrary transition matrix for the rates, P , is assumed to be r 0.6 0.4 0.2 0.8 P A = (5.26) and the initial distribution of the arrival rate, TT°X is assumed to be TT°X = [0.35 0.65]. (5.27) For the i.i .d. fading environment, buffer distribution with the considered M M P arrival is plotted in Fig. 5.7 whereas C D F of the delay is plotted in F ig . 5.8. These figures clearly show that our proposed rate adaptive T B S scheduling scheme outperforms classical S B S . This is expected as mentioned in Section 5.4.1 For the i.n.d. fading environment, buffer distribution and delay C D F of the far-end user with the considered M M P arrival are plotted in Figs. 5.9 and 5.10, respectively. From Fig . 5.9, we observe that HTS has quite similar buffer distribution as the NSS and better than the T B S and SBS schemes. Fig. 5.10 clearly shows that H T S has significant improvement 87 Figure 5.8: C D F of the queuing delay (i.i.d. fading, M M P arrival and number of users, K=10). 88 10 12 14 Buffer occupancy, x in packets Figure 5.9: Buffer distribution of the far-end user (i.n.d. fading, M M P arrival and number of users, K=10). in delay performance compared to the T B S and SBS schemes as observed with Poisson arrival in 5.4.2. It has certain degradation of delay performance compared with the NSS scheme. 5.5 Conclusion In this chapter, we have analyzed the buffer distribution and C D F of delay of our earlier proposed rate adaptive modulation-assisted T B S and HTS schemes via queuing analysis. We have also compared these performances with those of the classical single user schedul-ing schemes. Some selected numerical results showed that for an i.i .d. fading environment for both Bernouli and M M P arrival the T B S outperforms the classical SBS in terms of buffer distribution, average buffer occupancy, delay distribution. In other words, this fig-ure clearly shows that the probability that an incoming packet w i l l be transmitted within d time slots from a given user's buffer is higher than that of the classical SBS . Therefore, T B S can be used in order to improve the radio link layer performances for an i.i .d. fading 89 10 20 30 40 50 60 70 80 90 100 Delay, d In slots Figure 5.10: C D F of the queuing delay of the far-end user (i.n.d. fading, M M P arrival and number of users, K=10). environment. Selected numerical results in an i.n.d. fading environment have shown that our proposed H T S scheme significantly improve the buffer and delay distribution of the packets at the transmission buffer. This improved delay performance with T B S w i l l help in admitting more number of users than the classical SBS for a given statistical delay con-straint. It is important to mention that this improved performance is coming without any degradation of system's overall throughput. 90 0.35 g. 0.25 0.15 S 0.1 0.05 Proposed rate adaptive TBS Classical SBS HTS -e- NSS 8 10 12 Buffer occupancy, x in packets Figure 5.11: Buffer distribution of the near-end user (i.n.d fading, M M P arrival and number of users, K=10). 91 10 12 Delay, d in slots Figure 5.12: C D F of the queuing delay of far-end user (i.n.d. fading, M M P arrival and number of users, K=10). 92 Bibliography [46] M d . J. Hosssain, M . - S . Alouini , and V. K . Bhargava, "Rate Adaptive Hierarchical Modulation-Assisted Two-user Opportunistic Scheduling" IEEE Trans. Wireless Com-mun., to appear Jun. 2007. [47] L . B . Le , E . Hossain, and A . S. Alfa , "Queueing analysis and admission aontrol for aulti-rate wireless networks with opportunistic scheduling and ARQ-based error control," in Proc. of IEEE Int. Conf. on Commun. (ICC'05), Seoul, Korea, May 2005, pp. 3329 - 3333. [48] M . F. Neuts, "Matrix geometric solutions in stochastic models - an algorithmic ap-proach", John Hopkins Univ. Press, Baltimore, M D , 1981. 93 Chapter 6 Hierarchical Constellation for Multi-Resolution Data Transmission over Block-Fading Channels 1 2 A s we mentioned in Section 1.1.2 that a hierarchical image transmission scheme using a hierarchical Q A M constellation was proposed in [50] to protect different resolution com-ponents differently. This scheme proposed to devote the first level of hierarchy (i.e., the highest protected sub-channels) of the hierarchical 4 / 1 6 - Q A M constellation for basic in-formation transmission while transmitting refinement information in the second level of hierarchy (i.e., the lowest protected sub-channels). Non-uniform signal constellations in conjunction with A R Q scheme were used in [51] to adapt data rate of a single resolution message string transmitting over fading channels. For the same reason as [49], the system proposed in [51] also used a instantaneous C N R threshold-based retransmission scheme. Inspired by this application of non-uniform constellations, we propose, in this chapter, a new multi-resolution data transmission technique over block-fading channels. The pro-posed scheme uses a threshold-based retransmission strategy to meet a prescribed error performance of the transmitted services while taking advantage of the hierarchical constel-lation to provide different levels of protection to different resolution levels. In addition, it uses an adaptive scheduling protocol to give different transmission priorities to differ-ent resolution levels. Specifically, depending on the scheduling and channel state of the previous transmission, it dynamically selects packets from different resolution levels for the current transmission and the bits from these selected packets are assigned to different hierarchies of a hierarchical 4 / 1 6 - Q A M constellation. 1 2The work presented in this chapter has been published as Md. J. Hossain, M.-S. Alouini, and V. K. Bhargava, "Hierarchical Constellation for Multi-Resolution Data Transmission over Block Fading Channels", IEEE Trans. Wireless Commun., vol. 5, pp.849 - 857, April 2006. 94 The selection of packets for transmission and the assignment of these selected packets to different hierarchies of the hierarchical constellation are referred to as the scheduling pro-tocol in our proposed scheme. We model this protocol by a finite state first order Markov chain and obtain the packet loss rate and the packet transmission rate over Nakagami-m block-fading channel in closed-form. We then we propose a power-distortion optimized real-time multi-resolution video/image data transmission technique which jointly considers the timeliness requirements of the streaming application, the importance levels of different resolution levels and the time-varying channel property. A joint optimization of the pro-posed transmission framework is proposed by formulating it as a Markov decision process (MDP) . 6.1 System and Channel Models 6.1.1 Overall system description The block diagram of our proposed scheme is shown in Fig . 6.1, where we assume two layer image/video coding, namely, the base information layer (layer 1) and the refinement information layer (layer 2). The level 1 information layer contains the most significant part (MSP) and the information layer 2 contains the least significant part (LSP). According to the scheduling and channel state of the previous transmission, the packet selector selects two packets (namely packet 1 and packet 2 as shown in Fig . 6.1) 1 3 to be transmitted for the current transmission. For this transmission, the bits from the selected two packets are assigned to two different hierarchies of the hierarchical 4 / 1 6 - Q A M constellation. In our proposed scheme, the selection of packets and assignments of these packets to different hierarchies of the hierarchical Q A M constellation are performed by the adaptive scheduler as shown Fig . 6.1, whose mode of operation is going to be described in Section 6.2.1. 1 3 In general, these two packets may be selected from any resolution (i.e., not necessarily always from resolution 1 and resolution 2, respectively). 95 Adaptive Schedular Input Image/Video Layered Coder Level 2 (LSP) L e v e l 1 (MSP) Packet S e l e c t o r ( H i e r a r c h i c a l 4/16-QAM Output S i g n a l Feedback Channel Figure 6.1: Block diagram for multi-resolution video/image data transmission. 6.1.2 Hierarchical 4/16-QAM Our proposed scheme uses hierarchical 4 / 1 6 - Q A M constellation where there are two levels of hierarchies which we refer to as first and second level of hierarchies, respectively. The detailed description of these constellations are given, for example, in [50, 52]. Without going into all these details, a brief review of these constellations is given below. A hierar-chical 4 / 1 6 - Q A M constellation, shown in Fig . 6.2, can be modeled as follows. We assume that there are 2 bit streams of data. Each one of these incoming streams carries information of a particular priority. For every channel access two bits are chosen from each level of priority. The two bits from the highest priority stream are assigned to the M S B position in the I and Q channels. Consequently, the two bits from the least priority stream are assigned to the least significant bit L S B position in the I and Q channels. In Fig . 6.2, the fictitious 4 - Q A M constellation denoted by the black circle represents the highest priority (hereafter referred to as the first level of hierarchy). The distance d\ represents the first priority. The actual transmitted white symbols represent the 1 6 - Q A M constellation. This is the second level of hierarchy and the distance d2 represents the second priority. The exact B E R expressions over A W G N channel for this hierarchical 4 / 1 6 - Q A M con-stellation were derived in [52]. For instance, the B E R expression for the two bits in the first hierarchy, B E R i is given by 96 00 t ° 10 o 10 o 00 o to to 10 • 00 • 01 1 o 11 o 11 o 01 o 01 o 11 • 11 o 11 o 01 • 01 o 00 " o 2d 2 10 o 10 o 00 o 2dj Figure 6.2: Hierarchical 4 / 1 6 - Q A M constellation. whereas the B E R expression for the two bits in the second hierarchy, B E R 2 is given by where p = di/d2 is the constellation priority parameter, g is the symbol C N R and erfc(-) is the complementary error function. From (6.1) and (6.2), it is evident that for a given value of the parameter p, the two hierarchies have two different B E R performances for a fixed C N R . Equivalently, the two hierarchies require two different C N R s in order to meet a given target B E R or correspond-ingly a given target P E R and these C N R thresholds can be controlled by changing the parameter p. 6.1.3 General assumptions Our proposed scheme has the following operating assumptions: A l : We consider a stop-and-wait retransmission strategy i.e., the transmitter sends two packets simultaneously (one in the first level of hierarchy and the other in the second level of hierarchy of the hierarchical constellation) and waits for a reply from the receiver before transmitting the next two packets. A 2 : The maximum allowable number of retransmissions of a packet is Nm. Constrained retransmission is employed to meet the delay requirements of the video/image source. In addition, in order to maintain a target PER, we use the same retransmission strategy (i.e., the instantaneous C N R threshold-based strategy) that was used in [49]. However, cyclic redundancy check (CRC)-based A R Q scheme can also be used in conjunction with our proposed scheduling algorithm. In this case, rather than accepting packets below a target PER, data link layer w i l l accept only error-free packets (assuming probability of undetected error is zero) at the expense of redundancy, decoding complexity, and delay. The effects of using CRC-based A R Q scheme wil l also be briefly discussed in the following sections. A 3 : The time duration for simultaneous transmission of two packets is always the same and it is called a time step. For convenience, this discrete time step is denoted by n (n = 0,1, • • •) in the description of our proposed scheme. We also use the term "trans-(4p 2 - Ap + 1) 2(1 +p2) (6.2) 98 mission" for simultaneous transmission of any two packets during a time step. A 4 : The channel fading is assumed to be remain roughly the same over the whole time step. In other words, we are using the so called block-fading channel model as it was used, for example, in [53], [54], [55]. A 5 : The C N R g is independently distributed from one transmission to another for a specific user. This is, for example, valid for a T D M A multiuser environment because the time dura-tion between two transmissions to a specific user is typically larger than this user's channel coherence time. 6.1.4 Channel model A s we mentioned above, we use a block-fading channel model which is a well accepted model for wireless communication environments with slowly moving terminals. Since the Nakagami-m distribution captures a large class of fading channels, we use it in our block-fading channel model and this implies the following P D F for the received C N R g per block [56]: PM= fe)mnfSexpH^)> 9>0 (6-3) where g0n and mn are the average C N R and the Nakagami fading parameter (mn > 1/2) at time step n, respectively and T(m) := / n + 0 ° £ m _ 1 e - ' dt is the gamma function. Since two different hierarchies of the hierarchical 4 / 1 6 - Q A M constellation require two different C N R thresholds to meet a target P E R and the instantaneous C N R g is an indepen-dent random variable in each time step (according to assumption A5) , the channel can be represented by a three state memory less channel. Without loss of generality, let us con-sider 71 and 72 are the required C N R thresholds for the first and second level of hierarchy, respectively, with 71 < 72. The states and the associated probabilities for the three state memory less channel are given below: State C n : Both packets in the first and second hierarchies are received successfully (i.e., 72 < g). The associated probability 1 4 of receiving both packets successfully pn is l 4 The state probabilities are in general function of the time index n. However, since we are interested to. evaluate the performance of our proposed scheme for specific average CNR go and fading parameter m, we 99 thus given by r+°° r(m, m 3 2 ) P l l = / pg(g)dg = \ 9 0 (6.4) where r(x, a) := ta~le~l dt is the complementary incomplete gamma function. State C \ Q \ The packet transmitted in the first hierarchy is received successfully while the packet in the second hierarchy is not received successfully (i.e., 71 < g < 72). The associated probability pw is thus given by P10 '71 /•12 / pB(g)dg T(m) r(m) • • y ' } State C 0 0 : None of the packets are received successfully (i.e., 71 > g). The associated probability p0n is thus expressed as ni r(m, m 2 1 ) Poo When a CRC-based A R Q scheme is used, the channel w i l l have another extra state C 0 i that the packet transmitted in the second hierarchy is received successfully while the packet in the first hierarchy is not received successfully. The probability of this event p 0 i is very unlikely specially with highly asymmetric constellations and consequently we can still use the memory less three states ( C n , C 1 0 and C0o) channel model. In this case, the state probabilities, px\c, p^0, and Poo° cannot be expressed in terms of C N R thresholds 71 and 72 as in (6.4), (6.5) and (6.6) since there is no C N R threshold to meet a target PER. However, they can be expressed in terms of the instantaneous B E R expressions as given below: p™ = [ l - B E R 1 ( ^ p ) ] ^ x [ l - B E R 2 ( 5 , p ) ] A r p (6.7) p 1 0 c = [ l - B E R 1 ( ^ p ) ] ^ x [ l - [ l - B E R 2 ( 5 , p ) ] ^ ] (6.8) p c 0 R 0 c = [ l - [ l - B E R 1 ( ^ p ) ] ^ ] x [ l - [ l - B E R 2 ( ^ p ) ] ^ ] (6.9) where Np is the packet length in bits per packet and p is the constellation priority parameter as defined before. drop the time index n without loss of generality. 1 0 0 Poo Pn Figure 6.3: Scheduling state diagram when the maximum number of retransmissions is equal to one (i.e., Nm = 1). 6.2 Proposed Protocol 6.2.1 Protocol description To describe the protocol, let us consider a simple example where we limit the allowed maximum number of retransmissions, Nm to one (i.e., one original transmission plus one retransmission). Initially, we select one packet from each level of information to transmit. Since level 1 information packet requires the highest protection, it is assigned to the first hi-erarchy of the 4 / 1 6 - Q A M constellation. Correspondingly, the second hierarchy is assigned to level 2 information packet. This is the initial state of our scheduling protocol and as such is denoted by S0,n as shown in Fig. 6.3. Without loss of generality, let us consider that at the n-th time step (n = 0,1, • • •), the scheduling state is S0,o- Depending on the channel states (Coo, Cio and C n ) , the scheduler has three modes of operation at the (n + l)-th time step. The three modes of operation are given below. Channel is in state C n : Both level 1 and level 2 packets are transmitted successfully. In this case, new packet from level 1 in the first hierarchy and a new packet from level 2 in the second hierarchy are scheduled to be transmitted at the (n + l)-th time step. So, the scheduling for the next transmission remains same as So,o with a probability of pu as shown in Fig . 6.3. 101 C h a n n e l i s i n s t a t e C i 0 : Only level 1 packet is transmitted successfully at the n-th time step. The level 2 unsuccessfully transmitted packet at the n-th time step is discarded and new packet from level 2 in the second hierarchy with a level 1 new packet in the first hier-archy is scheduled to be transmitted at the (n + l )- th time step. So, there is a loss of level 2 packet and the scheduling remains in the same state S0,o for the next transmission with a probability of pin as shown in Fig . 6.3. It is important to note that the level 2 unsuc-cessfully received packet is discarded (i.e., no retransmission is requested) because level 1 information packet is given higher priority than level 2 packet. C h a n n e l i s i n s t a t e C00: Both level 1 and level 2 packets fail to be transmitted successfully at the n-th time step. In this case, the level 1 old packet is rescheduled for first retransmis-sion in the first hierarchy. Two packets (unsuccessfully transmitted packet at the n-th time step and the new packet corresponding to the new level 1 packet selected to be transmit-ted) are discarded from level 2, and a new packet from level 1 is selected to be transmitted in the second hierarchy. Both packets are selected from level 1 information to give higher transmission priority to level 1 information which is the M S P of the video/image data. This scheduling state is represented by S i i 0 as shown in Fig . 6.3. Once the scheduler is in state S i ) 0 at time step (n + 1), again depending on the channel state, three situations may occur. Depending on these three situations, the adaptive sched-uler has following mode of operations at the (n + 2)-th time step: C h a n n e l i s i n s t a t e C n : Both level 1 packets are transmitted successfully. In this case, the scheduling for the (n + 2)-th time step is S0,n with a probability pn as shown in Fig . 6.3. C h a n n e l i s i n s t a t e C 1 0 : Only the level 1 packet transmitted in the first hierarchy is received successfully at the (n + l)-th time step. For the next time step, the level 1 unsuccessfully transmitted packet in the second hierarchy is retransmitted in the first hierarchy to give the highest protection while a new packet from level 1 is transmitted in the second hierarchy. The level 2 packet corresponding to the level 1 new packet just selected for transmission is discarded. So, there is a loss of level 2 packet. C h a n n e l i s i n s t a t e C0r> Both level 1 packets fail to be received successfully at the (n +1)-th time step. The packet in the first hierarchy is discarded as it has completed the allowed maximum number of retransmission (i.e., one retransmission). So, there is a loss of level 1 packet. The unsuccessfully transmitted packet in the second hierarchy is now assigned 102 to the first hierarchy to give the higher protection and a level 1 new packet is assigned to the second hierarchy to be transmitted in the (n + 2)-th time step. Here again the level 2 packet corresponding to the level 1 new packet just selected for transmission is discarded. So, there is a loss of level 2 packet. After all, the scheduling, for the next step, remains same as S i ) 0 with a probability of p0o as shown in Fig . 6.3. When the maximum number of retransmissions is equal to one, the scheduler has only two states (S0,o and S i | 0 ) and it jumps between these two states from one time step to another depending on the channel state as described above. Using the same methodology and assuming that the allowed maximum number of retransmissions is equal to two (i.e., Nm=2), we arrive at a scheduling state diagram which is shown in Fig . 6.4. It is important to note that this scheduling state diagram has two extra states, S2,o and S 2 , i , compared with the state diagram shown in Fig . 6.3. The state S 2,n shown in this figure represents the second retransmission of a level 1 packet in the first hierarchy and the original transmission of a level 1 packet in the second hierarchy. Similarly, the scheduling state S 2 i i represents the second retransmission of a level 1 packet in the first hierarchy and first retransmission of a level 1 packet in the second hierarchy. In this case, the scheduler has as such only four scheduling states and makes transitions between these states depending on the channel state. 6.2.2 Protocol modelling From the description of our proposed protocol in the previous section, it is clear that the transmission scheduling at time (n + 1) only depends on the scheduling at time n and the transitions between scheduling states are associated with certain transition probabili-ties. In addition, the scheduler has a finite number of states for a finite number of allowed maximum retransmissions. In general, for an allowed maximum number of Nm retrans-missions, there wi l l be [Nm(Nm + l ) /2] + 1 states and the scheduler makes transition between these states from one time step to the next. The protocol, therefore, can be rep-resented by a [Nm(Nm + l ) /2] + 1 states first order Markov chain where the states of scheduler represent the states of the Markov chain. A l l possible states as well as their sig-nificance are listed in Table 6.1. For clarity, only the possible transitions out of states S j j (i = 1,2, • • • , Nm - 1 and j = 0,1, • • • , i - 1) are shown in F ig . 6.5. The probable 103 Table 6.1: Significance of the scheduling states State Significance S0,o Scheduling a level 1 and a level 2 packet in the first and second hierarchy, respectively, for original transmission. S y Scheduling a level 1 packet for i-th (i = 1,2, • • • , JV m ) retrans-mission and a level 1 packet for j-th (j = 0 ,1, • • • , % — 1) retrans-mission in the first hierarchy and second hierarchy, respectively. 104 transitions between all states and the associated probabilities are given below: S i j (n) POO Si+l,j+i(n + 1), 1 < i < Nm - 1, 0 < j < i - 1, S j + 1 , 0 ( n + 1), i = Nm, 0 < j < N m - l y S j + 1 , 0 ( n + 1), 1 < i < Nm, 0 < j < % - 1, S 0 , 0 (n + 1), 1 < % < Nm, 0 < j < i - 1, (6.10) SI,O(TZ + 1), S0,o(n + l), S 0 , 0 ( n + 1). where (k) (k — 0 ,1,2, • • •) is scheduling state at time step k. Using Chapman-Kolomogrov equation, state transition equation can be expressed as c I \ P10 s i , i ( n ) c I \ P°° So,o(«) So,o(^ ) P7r(n + 1) = 7r(n), (6.11) where 7r(/c) is the [ J V m ( ^ m + 1 ^ + 1] x 1 scheduling probability distribution vector at time k and P is [ J V m ( ^" 1 + 1 ) + 1] x [ N m ( ^ " + 1 ) + 1] one step transition probability matrix whose elements are obtained from (6.10). For example, the state transition probability matrix, P , when the allowed maximum number of retransmissions is equal to two, is given by P = Vw + Pio Pn Pn Pu Poo Pw Pw 0 0 0 0 poo+Pio 0 Poo Poo 0 (6.12) At steady-state condition, (6.11) can be represented by the following matrix equation [[57], Chap. 4]: P7r*=7r* (6.13) where TT* is the steady-state scheduling probability distribution vector and which is repre-sented as 7T* = 7T, 0,0 7 T 1,0 7T Nmfi (6.14) 105 where the element 7r,* • indicates the probability that the scheduler is at state Sitj at steady-state condition. The steady-state scheduling probabilities, TTQ 0 and 7^ * • (i = 1,2, • • • , A r m , j 0,1, • • • , i — 1), can be obtained by solving the set of linear equations in (6.13) and using the fact that summation of all the scheduling probabilities is equal to 1 i.e., ITT = 1 (6.15) where 1 is all one vector of appropriate dimension. Specifically, the first equation in (6.13) gives us J V m i-l (pn + Pw)K,o + Y Y nh P u = no,o- (6-16) i=l j=0 Substituting (6.4)-(6.6) and (6.15) in (6.16), TTQ 0 can be solved in closed-form as r ( m , ^ ) r ( m ) - r ( m , ^ ) + r ( m , ^ ) ' (6 .17 ) 90 ' • - v go It is important to note that the proposed protocol as well as the modelling of the protocol is valid when CRC-based constrained A R Q scheme is used in conjunction with hierarchical constellation except that the closed-form expressions for the steady-state probabilities TT* • wi l l be rather obtained in terms of p^\c, p^, and p^. 6.3 Performance Analysis Based on the Markov chain representation of our proposed protocol and the corresponding steady-state scheduling probabilities, in what follows, we derive the closed-form expres-sions for packet loss rate, P l o s s defined as the average number of packets that are discarded per time step at the scheduler and packet transmission rate, P m i l defined as the average number of packets successfully transmitted per time step after scheduling step 1 5 1 5In our analysis, we only take into account the packets that have been decided to be transmitted or dis-carded at the scheduler. In other words, we do not use any packet arrival model and include upper-layer effects. However, the overall packet loss rate can easily be derived by taking into account packet discarding probabilities at upper-layers. In this case, packet transmission rate can be derived from overall packet loss rate. 1 0 6 6.3.1 Average packet loss rate There is a level 1 packet loss when a level 1 packet is retransmitted for the iV m - t h time (i.e., the allowed maximum number of retransmissions) but this packet fails to arrive at the receiver successfully. Thus, the level 1 packet loss rate at steady-state condition, P£ s s can be expressed as J V m - l P L = E ^ W P o ° packets/time step, (6.18) j=o where 7rJ^m • is the steady-state probability that a level 1 packet is scheduled for Nm-th retransmission in the first hierarchy and a level 1 packet is scheduled for j-th (j = 0,1, • • • , Nm — 1) retransmission in the second hierarchy. A s mentioned above, this steady-state probability can be obtained by solving the set of linear equations in (6.13) and (6.15). Substituting (6.6) in (6.18), we obtain the following expression for P£ s s as: J V m _ 1 r ( m ) — T ( m m 3 1 ) PL= E v(m)' 9 Packets/time step. (6.19) i=o ^ ' A level 2 information packet is lost i f a level 2 packet is scheduled for transmission but is not successfully transmitted or i f a new level 1 packet is assigned to be transmitted in the second hierarchy discarding the corresponding level 2 packet. The joint probability of scheduling a level 2 packet for transmission in the second hierarchy and not receiving the packet successfully is 7TQ 0 ( p i 0 + Poo). The probability of assigning a new level 1 packet in the second hierarchy and discarding the corresponding level 2 packet is given by Nm-l Nm i-1 P " = K,o Poo + E **NmJ Poo + E E <3 Pio- ( 6 - 2 ° ) j=0 i = l j=0 Thus, the level 2 packet loss rate, P ^ at steady-state can be expressed as P.7I = K o (Pw + Poo) + P " packets/time step. (6.21) Using (6.4)-(6.6), (6.15), (6.17), and (6.20) in (6.21), P/j s can finally be written as „ r ( m ) [ r ( r a , m j ) + r ( m i m j ) ] - [ r ( m , m g f - [ r ( m , m g ] 2 P loss r ( m ) [ r ( m ) - r ( m , ^ ) + r ( m , ^ ) ] T(m)-T(m,m^) + > TT*N , — — — packets/time step. (6.22) m , j Tim) 3=0 V 7 107 6.3.2 Average packet transmission rate The average level 1 packet transmission rate, P^ n at steady-state condition and is given by P L = V\ + P2 + 2p3 packets/time step (6.23) where the probability Pi = K,o(Pn + Pw) (6-24) is the probability of transmitting one packet from level 1 and this packet is successfully transmitted, the probability Nm i-l Pz = YYl ntj P w = ~ ^0,0) Pw (6.25) i=l j=0 is the probability of transmitting two packets from level 1 and only the packet in the first hierarchy is successfully transmitted, and finally the probability Nm i-l Pz = YJ2 *h P u = (1~ n*ofi) Pn (6.26) i = i 3=0 is the probability of transmitting two packets from level 1 and both of them are success-fully transmitted. Using (6.4)-(6.6) and (6.17) in (6.24)-(6.26), the average level 1 packet transmission rate, P^ n , in (6.23) can be expressed, after some manipulations, as 1 - 2T(m, ^ i ) + [r(m, ^ l ) ] 2 p ~ " ' - r W [ r w - r ; , ? ) + r ( ; ? ) i s.eP. ( , 2 7 > The average number of level 2 packet successfully transmitted per time step is the number of packet from level 2 scheduled for transmission per time step multiplied by the probability that the packet is transmitted successfully. Clearly this probability corresponds to pu and as a consequence P^7 n can be expressed as P 7 / n = 7TQ 0 p i i packets/time step. (6.28) Using (6.4) and (6.17) in (6.28), P^ n can be written as P ," T(m, z o a ) « r(m){T(m)-T(m^) + T(m,^)} packets/time step. (6.29) 90 ' v ' 90 108 When CRC-based A R Q strategy is used in our proposed scheduling algorithm, it is straightforward to obtain the closed-form expressions for packet transmission rate and packet loss rate for both resolutions in terms of p^0, p ^ c , and p^c which are functions of instantaneous C N R g. Therefore, packet loss rate and packet transmission rate wi l l be function of the instantaneous C N R g and their average value can be obtained simply by taking the expectation with respect to the C N R g. 6.4 Numerical Results In this section, we present some numerical results to show the performance of our proposed scheme. Specifically, we plot packet loss rate and packet transmission rate as a function of average C N R g0 for different values of Nakagami fading parameter m, different constella-tion priority parameter p, and different allowed maximum number of retransmissions Nm. In our numerical results, we used an uncoded average packet error rate, P E R 0 = 1 0 - 3 and a packet length of 1000 bits (i.e., Np = 1000 bits/packet). So, the target uncoded average B E R , B E R 0 = 1 - (1 - P E R 0 ) 1 / A r p = 1 0 - 6 . The C N R thresholds, 71 and 72 are found by solving (6.1) and (6.2), respectively, numerically for a given priority parameter p. We used M A T L A B Statistical Toolbox to get simulation results which we compared with our analysis-based numerical results. 6.4.1 Average packet loss rate The average packet loss rate over Rayleigh fading channel (m = 1) is plotted in Fig . 6.6 for different constellation priority parameter p (or equivalently different C N R thresholds). We limit the allowed maximum number of retransmissions, Nm to two. This figure shows that as the value of p increases, the packet loss rate for level 1 information decreases while that of level 2 information increases. This is expected as the value of p increases, the difference between the two C N R thresholds, 71 and 72, increases and consequently the packet in the first level of hierarchy gets higher priority than the packet in the second hierarchy. Level 1 information, therefore, gets higher transmission priority than the level 2 information. The average packet loss rate over Rayleigh fading channel is plotted in F ig . 6.7 for dif-ferent allowed maximum number of retransmissions. This figure shows that as the allowed 109 Figure 6.6: Effect of the constellation priority parameter p on the average packet loss rate (7Vm=2 and m=l) . maximum number of transmissions, Nm increases, the level 1 packet loss rate decreases. This is also expected since a level 1 information packet gets more time to be transmit-ted successfully before it is discarded as the number of allowed maximum transmission increases. The average packet loss rate, for different values of Nakagami fading parameter m with a given priority parameter p and allowed maximum two retransmissions, is shown in Fig . 6.8. From this figure, it is evident that at high average C N R regions as the value of m increases, the packet loss rate for both level 1 and level 2 information decreases. This is due to the fact that the amount of fading decreases as the value of m increases. On the other hand, at low average C N R regions the packet loss rate for both level information packets increases as the value of m increases. This is because the shape of the Nakagami m distribution becomes narrower centred around the average C N R as the value of m increases [56]. Therefore, at low average C N R and at higher value of m , the probability having of 110 Average carrier-to-noise ratio in dB Figure 6.7: Effect of the allowed maximum number of retransmissions, Nm on the average packet loss rate (TO = 1, p = 5, 71 = 15.39[dB], and 72 = 27.69[dB]). I l l Average carrler-to-noise ratio in dB Figure 6.8: Effect of the Nakgami m fading parameter on the average packet loss rate (Nm=2, p = 5, 71 = 15.39[dB], and 7 2 = 27.69[dB]). 112 0.9 £ 1 0.7 v o 03 f 0 . 6 2 I 0.5 'E § 0.4 o §. 0.3 <u S 0.2 0.1 I I p=5 (7^15.38 dB,72=27.69dB) p=3 (7,=17.25 dB, 72=23.55 dB) _ _ p=2 (7,=20.26 dB, 72=20.53 dB) . / u ^ 1 ' » i // / J/ / W i T ' 1.. i / / i / / Level 1 > i i i / / / j A • • \ / X / ' i f \ . i 1 \< / / ' / / i .evel2 / 1 11 f 1 I 1 i i 1 i J 1 T 1 1 1 i f i i 1 1 i / —*—* <—i ^ 10 15 20 25 30 Average carrier-to-noise ratio in dB 35 40 Figure 6.9: Effect of the constellation priority parameter p on the average packet transmis-sion rate (Nm=2 and m=l) . better channel condition is lower and consequently packet loss rate increases. 6.4.2 Average packet transmission rate The average packet transmission rate over Rayleigh fading channel (m = 1) and for dif-ferent constellation priority parameter, p is plotted in Fig . 6.9 for Nm — 2. This figure shows that as the value of p increases, the packet transmission rate for level 1 information increases while that of level 2 information decreases. Again, this is expected since the level 1 information gets a higher transmission priority than the level 2 information as the priority parameter p increases. Finally, the average packet transmission rate plotted in Fig . 6.10 for a given priority pa-rameter, p, shows that at high average C N R regions as the value of m increases, the packet transmission rate increases. A t low C N R regions, we got different scenario; as the value of m increases, the packet transmission rate decreases. These are again expected since the amount of fading decreases as the value of m increases and at low average C N R region, the 113 Average carrier-to-noise ratio in dB Figure 6.10: Effect of the Nakgami m fading parameter on the average packet transmission rate (Nm=2, p = 5, 7 l = 15.39[dB], and 7 2 = 27.69[dB]). 1 1 4 probability of having better channel quality decreases as the value of m increases. 6.5 Real-time Multi-Resolution Data Transmission over Correlated Fading Channels 1 6 In Section 6.2, we have proposed an adaptive scheduling protocol for multi-resolution image/video data transmission over a time-varying link. This protocol used a fixed trans-mit power in each time slot and a retransmission scheme with a maximum allowed number of retransmissions. This retransmissions limit is assumed to be dictated by the delay re-quirement of the packets that arrive at the transmission buffer. In other words, it did not consider any explicit delay requirements for the arrival packets. In addition, we have also considered that the fading gain varies independently from one time slot to the next. Intuitively, using higher number of retransmissions for more important packets should provide a better video quality. However, the allowed number of retransmissions for the current packet affects the residual communication resources for the subsequent packets in a streaming application where the packets have a real-time deadline constraint. Specifically, i f the sender chooses a higher number of chances for the current packet, the chances of successfully receiving that packet increases. However, the packets that are waiting in the buffer to be transmitted are left with less chances before the presentation deadline at the receiver. This may cause the sender to use smaller number of retransmissions or to discard some packets without being sent as their deadlines have been expired. Therefore, the choice of the number of retransmissions or transmission opportunities for individual packets are not independent. The problem is even more complex in a multi-resolution data transmission system because the system has to consider not only the individual deadline of the packets waiting at the buffer but also their importance levels. For example, let us consider two packets are waiting at the buffers. One is from higher importance level but has less closer deadline and the other is from lower importance level but has more closer deadline. If the transmitter can transmit only one packet per transmission block which packet should 1 6This Section has been published as Md. J. Hossain, M.-S. Alouini, and V. K. Bhargava, "Real-time Multi-Resolution Data Transmission over Correlated Fading Channels using Hierarchical Constellations', in Proc. of IEEE Veh. Technol. Conf. (VTC'06 Spring), vol. 5, pp.2068-2072, May 2006. 115 be selected by the packet scheduler to be transmitted for current transmission in order to achieve a given quality of the received image/video? In addition, the transmitter needs to select the transmit power level according to the time-varying property of the wireless channel, the importance level of the packets and their deadline i f there is a given power budget. On the other hand, i f the transmitter wants to transmit both packets simultaneously using a hierarchical constellation, which is capable of providing different level of protection to the transmitted messages [50], [52], how much relative protection levels should be given to the individual packets at the physical layer. Motivated by the aforementioned challenging tasks, in this section, we propose a power-distortion optimized real-time multi-resolution video/image data transmission technique which jointly considers the timeliness requirements of the streaming application, the im-portance levels of different resolution levels and the time-varying channel property. Basi-cally, depending on the current buffer occupancy and channel state, it dynamically selects transmit power level, a constellation priority parameter as well as packets from different resolution levels to be transmitted for the current time transmission block. A joint opti-mization of the proposed transmission framework is proposed by formulating it as a M D P . The power-distortion trade-offs curve is plotted for a given fading rate. We also compare the proposed scheme with a scheme employing uniform signal constellation. In a related work, a multi-layer video transmission technique using non-uniform phase shift keying (PSK) constellation was proposed in [58]. The scheme in [58] proposed to se-lect the constellation parameter as well as the coding rate according to the wireless channel quality. However, it did not consider any buffering of the packets with a real-time deadline constraint and the correlation among the fading gains from one time slot to the next. 6.5.1 Overall system description The block diagram of our proposed scheme is shown in Fig . 6.11, where we assume two layer image/video coding, namely, the base information layer, (denoted by R i ) and the refinement information layer (denoted by R 2 ) . The R i information layer contains M S P and the R 2 information layer contains the LSP. We consider that packets from both resolutions arrive in a batch i.e., every time slot two packets arrive simultaneously. The R i information packet waits at buffer 1 and the corresponding R 2 information packet waits at buffer 2 at 116 Ri Buffer Video/Image Two Layer Source Source Coder R 2 Buffer Buffer State, B„ Packet 1 Packet Selector Hierarchical 4 /16-QAM Modulator Packet 2 Power Level P n Selector Constellation Parameter, pn Selector Channel State, Cn Feedback from Receiver Figure 6.11: Adaptive system for layered real-time image/video data transmission. the transmitter. For a real-time deadline constraint, packets can wait only two time-slot after they arrive at the buffer 1 7. More specifically, the packet that arrives in a time-slot n can be transmitted only in the time-slot n or (n + 1) other wise it is discarded due to missing presentation deadline at the receiver. According to channel state and buffer occupancy of both resolutions, the packet selector selects two packets (namely packet 1 and packet 2, as shown in Fig . 6.11). In general, these two packets may be selected from any resolution, not necessarily always from R i and R 2 information, respectively. For this transmission, the bits from the selected two packets are assigned to two different hierarchies (namely, H x and H 2 ) of the hierarchical 4 / 1 6 - Q A M constellation. The selection of packets for transmission and the assignment of these selected packets to different hierarchies of the hierarchical constellation are referred to as the packet scheduling protocol in the proposed transmission system. Finally, the transmit power level, P and the constellation priority parameter, p are selected and accordingly the symbols are transmitted from hierarchical 4 / 1 6 - Q A M modulator in a given time-slot. Wireless channel model In a time-varying wireless channel, the quality of the channel at a given time is correlated to the previous channel conditions and this kind of behavior can be modelled as a finite state Markov chain (FSMC) [59]. F S M C models can be constructed by partitioning the 1 7 For simplicity, we consider a two-time slot deadline. However, more than two-time slot deadline can be used in the proposed transmission framework and in that case the complexity of the system increases. 117 fading gain value into a finite set of ranges. Let us consider that the fading power gains are partitioned into a set of Q ranges where H = {c i , c 2 , • • • , CQ} denote the Q states of the F S M C and 4> — [<fii, 4>2, • • • , </>Q+I]t are the fading gain thresholds in increasing order with </>i = 0 and 4>Q+I = oo. Then the fading gain ranges [fa, </>i+i), I = 1,2, • • • , Q are mapped into the channel states q , I = 1,2, • • • , Q, respectively. The channel fading gain corre-sponding to state q is denoted by hi and obtained by averaging the fading gain over the range [4>i, 4>i+\). Several methodologies can be used for partitioning the fading gain (e.g., see [59]) and calculating the state transition probabilities. We use the equal-probability method i.e., the fading gain of the channel is partitioned such as the stationary probability associated with all the states is equal [59]. The channel fading gain is assumed to remain roughly the same over the whole transmission block. In other words, we are using the so called block-fading channel model as it was used, for example, in [53], [55]. We assume that the channel states associated with consecutive blocks are assumed to be neighboring states. Therefore, the channel Markov process can be described as a birth-death process. For a given transmission rate and maximum doppler frequency fd these probabilities can be found in [59]. Since two packets are transmitted in two different hierarchies of the hi-erarchical 4 / 1 6 - Q A M constellation in a transmission block, the transmitter can have four different observation signals. These observations as well as their associated probabilities are given below. Observation O1: Both packets in hierarchies Hi and H 2 are received successfully. Observation O2: The packet transmitted in hierarchy Hi is received successfully while the packet in hierarchy H 2 is not received successfully. Observation O3: The packet transmitted in hierarchy H2 is received successfully while the packet in hierarchy H i is not received successfully. Observation O4: None of the packets is received successfully. Corresponding probabilities of these observations for a transmit power level P \ a con-stellation priority parameter p1 and, a fading power gain hi of the channel are thus given 118 by frob.(O1|Pi,p>',/0 = [ l - B E R 1 ( P i , p ' ' , r i i ) ] J V ' ' x [1 - BER2(Pi,pithi)]N'i(6.30) P r o b . ( 0 2 | P \ p i , hi) = [1 - B E R i f P y , h i ) ] N ' x [ l - [ l - B E R 2 ( P i , ^ > i ) ] i V p ] (6-31) P r o b . ( 0 3 | F , ^ , / i < ) = [ I - [ l - B E R ^ F , p i , h i ) } N ' } x [ l - B E R 2 ( P i ) 7 y , / i i ) 3 i V p , (6.32) P r o b . ^ l F , ^ , ^ ) = [l-[l-BER1(Fi,pl,hi)]N»] x [1-{1-BER2(? , p i , hi)}N»] (6.33) where N p is the packet length in bits per packet, B E R i ( P l , p J " , h i ) and B E R 2 ( P * , p 7 , h i ) are the B E R s of the bits in the first and second hierarchies, respectively (given in Eqns. (6.1) and (6.2), respectively). M a r k o v d e c i s i o n p r o c e s s e s A M D P is a model for deciding how to act in a stochastic environment where outcomes are uncertain. A M D P is described through a set of states S = {s1, s2, • • • , sN}, a set of actions A = { a 1 , a 2 , • • • , au}, a set of state and action dependent immediate costs c: K, i—> E , and a set of state and action dependent transition probabilities. Set /C = {(s, a)} : s e S, a e As is the set of state-action pairs. While the system is in state sn = sl e S at decision epoch or time-slot n , the controller or decision maker selects an action a n from the set of actions Asi available at state sl G S, where UsieSAsi = A. In the next time-slot, the system moves to a state s j £ S according to the transition probability p ( s n + i = sj\sn = s \ a n ) and the decision maker incurs a one step immediate cost c ( s n , a n ) . A policy as a mapping from state to actions specifies the decision rule to be used at all time slot or decision epoch. With a policy ip, which does not depend on time slot, n (called as stationary policy), the expected long-term average cost per stage is 1 M Jf = J m T7J2EMSn,<P{Sn))l (6.34) M — > o o M I£—' n = l where expectation, E s is over the random evolution of the states of the M D P . A n optimal policy denoted by (p* is the one that incurs the minimum average cost per stage i.e., (p* = arg min Jv (6.35) • p e n 119 R?W R|(") Packet Selector o1 R2(n + 1) Rj(n+1) Buffer State, B 1 o2 R3(n + 1) R|(n + 1) R^+(n) Buffer State, B 2 o3 R2(n + 1) R j » R|(n + 1) Buffer State, B 3 R?(n+1) Rl(n) n|(» + 1) Buffer State, B Figure 6.12: Buffer state space. where II is a set of all stationary admissible deterministic policies. In general, this mini-mization should be performed over the set of all causal policies. However, for our transmis-sion frameworks, optimal policy for the resulted M D P exists and is contained within the set of stationary deterministic policies [60]. The optimal policy for an M D P can be found in different ways for example using the relative value iteration algorithm (RVI) or the policy iteration (PI) algorithm [61]. 6.5.2 Problem formulation Buffer dynamics, packet scheduling, and composite state space Since a packet can wait at most two time-slot at the buffer, each buffer can contain at most two packets. To describe the dynamics of the buffer, without loss of generality, let us con-sider that, at the n-th time slot a packet from each resolution, is waiting at its respective buffer as shown in Fig. 6.12. The number of time slots they can wait at the buffer before the presentation deadline is two (i.e., n or (n + l)-th time slot). A s such this buffer state is denoted by B 1 and the notation R i (n ) , in general, denotes that the packet is from i-th resolution level of n-th batch and can wait at most j time-slot at the buffer. A t this state of buffer occupancy since level 1 information packet requires the highest protection, it is 120 assigned to hierarchy Hi of the hierarchical 4 / 1 6 - Q A M constellation. Correspondingly, hierarchy H 2 is assigned to the level 2 information packet. This packet scheduling option is represented by a circle in Fig . 6.12. Depending on the acknowledgement signal, On at time-slot n , buffers can have the following states of occupancy in the next time step: On=0 1 : Both level 1 and level 2 packets of m-th batch are transmitted successfully. A new batch (i.e., (n + l)-th batch) arrives at the buffers and the buffers remain at the same state B 1 as shown in Fig . 6.12. On=02: Only level 1 packet, which was assigned to hierarchy H i , is transmitted success-fully. Therefore, the corresponding level 2 packet of n-th batch remains in the buffer. A s such this packet is denoted as R 2 + ( n ) in Fig . 6.12. Here the "+" sign is to denote that the corresponding (level 1 or level 2) packet has been received successfully at the receiver. In addition, the new batch of packets arrives at the buffer. This buffer state is denoted as B 2 . On=03: Only the level 2 packet of m-th batch is transmitted successfully and a new batch arrives at the buffer. The level 1 packet from n-th batch, waiting at the buffer, is denoted as R* + . This buffer state is represented by B 3 as shown in Fig . 6.12. On=04: None of the packets of n-th batch are transmitted successfully and a new batch arrives at the buffer. As such this buffer state is denoted by B 4 in F ig . 6.12. Once the buffer is in state B 1 at time-slot (n + 1), the packet selection procedure is straight forward as mentioned above. However, i f the buffers are in state B 2 , B 3 , or B 4 , the buffers have more than two packets to be transmitted and these packets have different importance levels as well as different deadlines. Since the transmitter can send only two packets per time-slot, it has a number of packet scheduling options in these buffer states. For example, at state B 2 , the R 2 information packet of the n-th batch is waiting at the buffer which has less priority in terms of received quality of the image or video as already the cor-responding Ri information packet is received correctly. If the packet R i + ( n ) is selected to be transmitted, one of the packets from (n + l)-th batch cannot be transmitted and conse-quently the number of transmission opportunities before the presentation deadline for this packet reduces to one. In general, the transmitter has (*) packet selection options when there are total k packets in the buffers and two of them are selected to be transmitted. In addition, selected two packets can be assigned to two different hierarchies (Hi and H 2 ) of the hierarchical constellations. Therefore, there are ( 2* f e) scheduling options when the buffer has k packets. For notational convenience, let us consider that the scheduling options 121 that are available at buffer states B \ i — 1,2,3,4 is denoted by a set Pg i , i = 1,2,3,4, respectively. Using the same methodology as described above (also in Fig. 6.12), it can be observed that with any available packet scheduling option, the buffers can have only these four states and switches between one to another depending on the acknowledgement sig-nals. The transition probabilities of the buffer states depend on transmit power level, con-stellation priority parameter, channel state, and the packet scheduling option. Although it is not possible to represent the buffer state transition probabilities in generic form, they can be found by constructing the tree diagram for each buffer state as well as packet scheduling option in this state as shown in Fig. 6.12. To represent the transmission framework in terms of an MDP model, the state space of this model is S = B x li where B = {B 1 B 2 B 3 B 4} is the state space of the buffers' occupancy. Note that the total number of states in S, N is equal to 4 x Q. Act ion and state pairs We assume that the transmission power level Pn=PJ at time-slot n is chosen among / dis-crete power levels of the set 77={P1, P 2 , • • •, P7} and that the constellation priority param-eter pn = pi is selected from among J priority parameters of the set £ = {p1, p2, • • •, pJ}. Then the action space for state s\ Asi = U ? L ) £ where the function <j){s) returns the buffer state of the composite state s. 6.5.3 Power-distortion model Since our objective is to find an optimal policy which minimizes the transmission power so that the average distortion in the received application remains below certain bounds, the immediate objective cost function of the associated MDP can be given as only the power cost i.e., the transmitted power level in each state. We use a very generalized distortion model. Similar type of distortion model was used in [62]. In general, the distortion for the packets of n-th batch is given by e= < 0 A c 2 A c 1 A c 3 if both packets are received successfully, if only Ri (n) packet is received successfully, if only R2(n) packet is received successfully, if none of the packets are received successfully. (6.36) 122 Therefore, the expected distortion can be expressed as D a v s = p 1 0 A c 1 + poi A c 2 + poo A c 3 , (6.37) where pw is the probability of receiving R x packet of i-th batch only, p 0 i is the probabil-ity of receiving R 2 packet of i-th batch only and poo is the probability of receiving none of the packets of i-th batch. Since R 2 packet of a given batch is not useful without the. corresponding Ri , a high value is assigned to A c 2 . 6.5.4 Results We formulate the problem as an unconstrained Markov decision process ( U M D P ) with a trade-off factor. The immediate cost function under a stationary deterministic policy ip is where ft (> 0) is a trade-off factor and by changing its value we can obtain different trade-offs between average transmit power and the average distortion. For a given ft, the stationary deterministic optimal policy ip* is obtained using relative value iteration. In F ig . 6.13, we plot the power-distortion trade-offs curves of optimal transmitter for a given fading rate (i.e., doppler frequency /<*) using the following settings: average channel gain ho = 10[dB], and the noise power ui2 = l [mW] . Two power levels, namely P1 = 2[mW] and P 2 = 20[mW] and three priority parameter options, namely p 1 = 2 (uniform constellation), p 2 = 3, and p 3 = 4 are used in our simulations: In the same figure, we have also plotted power-distortion trade-offs using a uniform constellation-based scheduling scheme. With the uniform constellation-based scheme a uniform 1 6 - Q A M constellation is used i.e., the priority parameter p = 2. The figure shows that as the distortion cost increases, the required average transmit power reduces. This is expected as we increase the transmit power level, the chances of receiving the packets successfully increases. It is also evident from Fig . 6.13 that the uniform constellation-based scheduling scheme requires higher power than the hierarchical constellation-based scheme for the same distortion cost. This is due to the fact that hierarchical constellation can offer different level of protections to the transmitted packets according to their priorities at the physical layer by changing the parameter p. c(sn, (p(sn)) = P„ + /3D: |3Vg n (6.38) 123 Figure 6.13: Comparison of hierarchical and uniform constellation-based schemes. 6.6 Conclusion In this chapter, a multi-resolution transmission system using hierarchical constellation in conjunction with a C N R threshold-based retransmission strategy has been proposed. The proposed scheme not only takes advantage of hierarchical constellation but also uses an adaptive scheduling protocol to give different transmission priorities to different resolution levels. A Markov chain model of this protocol leads to closed-form expressions for the average packet loss rate and the average transmission rate. Numerical results, which were validated by computer simulations, show that the proposed scheme can control the rela-tive transmission priorities in terms of transmission rate as well as loss rate of different resolution levels by varying the asymmetry of the constellation and the maximum num-ber of allowed retransmissions. Then we have proposed an integrated packet scheduling and unequal error protection strategy for real-time packetized multi-resolution (layered) image/video data transmission over correlated channel. In order to select transmit power level, a constellation priority parameter and the packets from different resolution levels, the proposed system considers the timeliness requirements and the importance levels of 124 different packets and time-varying channel property. A joint optimization of the proposed transmission framework has been done formulating it as a M D P . The proposed hierarchical scheme has also been compared with an optimized scheme which uses uniform signal con-stellation. The scheme with uniform constellation requires higher average transmit power than the hierarchical scheme in order to maintain the same average distortion. 125 Bibliography [49] Q. L i u , S. Zhou, and B . Giannakis, "Jointly adaptive modulation and packet retrans-mission over block-fading channels with robustness to feedback latency," in Proc. Conf. Information Sciences and System (CISS 2003), The Johns Hopkins University, U S A , Mar. 2003. [50] M . Morimoto, M . Okada, and S. Komaki, " A hierarchical image transmission system in fading channel," in Proc. IEEE Int. Conf. Univ. Personal Commun. (ICUPC 95), Tokyo, Japan, Oct. 1995, pp. 769-772. [51] R. Otnes and T. Maseng, "Adaptive data rate using A R Q and non-uniform constel-lations," in Proc. IEEE Veh. Technol. Conf. (VTC 01-Spring), Rhodes, Greece, M a y 2001, pp.1211-1215. [52] P. K . Vitthaladevuni and M . - S . Alouini , " B E R computations of 4 / M - Q A M hierarchi-cal constellations," IEEE Trans. Broadcasting, vol. 47, no. 3, pp. 228-239, Sep. 2001. See also correction in IEEE Trans. Broadcasting, vol. 49, pp. 408, Dec. 2003. [53] E . Biglieri , G . Caire, and G . Taricco, "Limiting performance of block-fading channels with multiple antennas," IEEE Trans. Inform. Theory, vol. 47, no. 4, pp. 1273-1289, May 2001. [54] E . Malkamaki and H . Leib, " Coded diversity schemes on block-fading Rayleigh channels," in Proc. IEEE Int. Conf. Univ. Personal Comm. (ICUPC 97), San Diego, C A , Oct. 1997 pp. 494-499. [55] L . H . Ozarow, S. Shamai, and A . D . Wyner, "Information theoretic considerations for cellular mobile radio," IEEE Trans. Veh. Technol., vol. 43, pp. 359-378, M a y 1994. 126 [56] M . Nakagami, "The ra-distribution-A general formula of intensity distribution of rapid fading," in Statistical Methods in Radio Wave Propagation., Oxford, U K : Perga-mon, 1960, pp. 3-36. [57] F. Gebali, Computer Communication Networks: Analysis and Design, NorthStar Digital Design, Inc., Victoria, B C , Canada, 2002. [58] Y. Pei and J. W. Modestino, "Multi-layered video transmission over wireless channels using an adaptive modulation and coding scheme," in Proc. Int. Conf. Image Process-ing (ICIP'01), Thessaloniki, Greece, Oct. 2001, pp. 1009-1012. [59] H . S. Wang and N . Moayeri, "Finite-state Markov channel-A useful model for radio communication channels," IEEE Trans. Veh. Technol., vol.44, pp. 163-171, Feb. 1995. [60] M . L . Putterman, "Markov decision processes: discrete stochastic dynamic program-ming," New York : John Wiley & Sons, 1994. [61] D . P. Bertsekas, Dynamic programming and Optimal Control. 2nd ed. vol. I and II, Belmont, Massachusetts: Athena Scientific, 2001. [62] L . Yan and N . Bambos, "Power-controlled wireless links for video streaming appli-cations," in Proc. IEEE Veh. Technol. Conf. (VTC'04 Fall), Los Angeles, C A , Vol . 4, Sep. 2004, pp. 2577-81. 127 Chapter 7 Link Adaptation for OFDM Systems for Delay-Constrained Communication over Correlated Fading Channels 1 8 As we have mentioned in Chapter 1 that in order to take advantage of time-varying na-ture of subcarrier fading gains in an O F D M system, link adaptation has been proposed in wireless communications standard. There are two extremes of bit-loading algorithms from the perspective of delay-constrained communication over fading channels. One is hard delay-constrained case and the other is no delay constrained case. However, the ar-rived data packets may tolerate some intermediate queuing delay at the transmission buffer rather than having hard delay constraint or no delay constraint. Recently channel and buffer adaptive transmission techniques, which schedule packet transmission in order to meet a target delay constraint while minimizing average transmit power, have been proposed for single carrier case [64], [65], [66]. Transmission rate has been optimized via a cross layer optimization technique and the optimal trade-offs between different conflicting objectives has been studied formulating the problem as a M D P . Best to our knowledge, despite that the performance of buffer adaptive multi-carrier transmission scheme has been analyzed in [70], no study has been done on multicarrier loading algorithms that minimize the aggre-gate B E R with a fixed transmit power or minimize the total average transmit power with a target error probability for a given delay-constrained communication over correlated fading channels. In this chapter, we study and offer some novel results on adaptive loading algorithms for O F D M systems for delay-constrained services. Specifically, we propose and study two 1 8The research presented in this chapter is to be revised and submitted as Md. J. Hossain, D.-V. Djonin, and V. K. Bhargava, "Delay limited power and bit-loading algorithms for O F D M systems for delay-constrained communications", IEEE Trans. Veh. Technol. 128 different transmission frameworks for an O F D M system. In the first transmission frame-work, a bit-loading algorithm, which minimizes the aggregate B E R of an O F D M system while maintaining a target buffering delay of the packets in the transmission buffer is pro-posed. In this framework, we assume a fixed total transmit power which is equally divided among the O F D M subcarriers. In the second transmission framework, we propose bit and power loading scheme with the objective to minimize the average total transmit power while maintaining a target buffering delay of the packets. Due to the system dynamics both loading frameworks are formulated as M D P and the optimal loading policies are obtained via equivalent linear programming (LP) methodology. The complexity of algorithms used to find the optimal loading policies and their implementation issues are described. Since finding optimal policies is complex and practically un-realizable for large number of car-riers in the system, we propose a sub-optimal loading algorithm using the results of the single carrier system's optimal loading policy and a greedy approach. Finally, in this chap-ter, we study the effect of correlation among the fading gains of subcarriers of a multicarrier modulation ( M C M ) system. Notation: Subscripts are reserved to denote a specific state of a state space, while su-perscripts are reserved to denote the subcarrier index. Subscript in brackets denotes the state at a certain transmission slot. 7.1 System Model A system model for buffer and channel adaptive transmission system is shown in Fig . 7.1 where we assume a single class of traffic is to be transmitted over fading channels using an O F D M system with L subcarriers. It is assumed that each subcarrier undergoes fre-quency flat fading. Data packets, which arrive from higher application layers, are stored in a finite size transmission buffer of length B in order to be transmitted later. In each trans-mission slot, the transmitter adaptively assigns a number of bits to different subcarriers jointly considering the state of buffer occupancy as well as different subcarriers' states. In what follows we provide detailed descriptions of the channel model for O F D M subcarriers as well as incoming traffic and rate (or both rate and power) adaptation models which are used in our adaptive transmission frameworks. It is important to mention that we propose two different transmission frameworks. The first transmission framework proposes a bit 129 Packets from higher layer Finite transmission buffer K-parallei streams K-fading subcarriers S/P Adaptive modulators IFFT Buffer state B i t l o a d i n g Sub-channels' con t ro l l e r state feedback Figure 7.1: Scheme of the O F D M system. loading algorithm which minimizes the aggregate B E R of an O F D M system while main-taining a target buffering delay of the packets in the transmission buffer. In this case, the transmit power, which is divided equally among the subcarriers is assumed to be fixed in each transmission slot. In the second transmission framework, we propose bit and power loading scheme which has the objective to minimize the average total transmit power while maintaining a target buffering delay of the packets. 7.1.1 Channel models Let the total bandwidth of the system be W[Hz]. We assume that the total bandwidth is equally divided among L O F D M subcarriers. Therefore, the bandwidth per carrier is Wsubcar = W/L[Hz]. Given the channel fading amplitude at i th carrier, a1 and a noise power spectral density of -/V 0[W/Hz], let us define the normalized fading gain at receiver for the ith carrier b} = (a1)2/N0Wsubcar. The fading gain channel estimation for each subcarrier is performed at the receiver and these estimates are sent back to the transmitter assuming no delay and no error in the transmission on the feedback channel. The received fading gain estimate on carrier i, h% corresponds to a discrete set C1 — {c\,..., clQ} of channel states where it is assumed that there are Q such discrete states. Let ith carrier be in the state c* i f hl is in the interval <j)j_i < hl < <f>j. Here it is assumed that fading gain thresholds satisfy the following inequality: 0 = (fio < ... < fa < . . . < 4>Q = oo. The channel is assumed to be block-fading as it is assumed that the received fading gain at the receiver stays in the given interval for the duration of the whole transmission slot. In each 130 transmission slot, a given number of O F D M symbols are transmitted. The duration of a transmission slot, T s , over which the fading gain remains roughly constant has to satisfy the following condition [74] 0.423 T s « — - , (7.1) Id where fd is the maximum Doppler frequency which depends on the signal carrier frequency and the velocity of the mobile terminal. The P D F of the fading gain of ith carrier in state p\{h) is considered to be known. Further, it is assumed that channel states of ith carrier form an ergodic Markov chain which is independent across the carriers. The composite channel state is defined as c = ( c ^ c 2 , . . . , c L ) , where cl € C \ defines the snapshot of carrier states in all parallel carriers. The number of composite channel states in state space C = C1 x C 2 x • • • x CL is QL. If the fading conditions among the subcarriers are independent, they can be obtained by simply taking the product of individual carrier's state transition probability. For example, we assume that the channel of ith carrier can be represented by F S M C [71]. For a given fading rate (i.e., Doppler frequency) the transition probabilities between the channel states of the F S M C can be found, for example, in [71]. 7.1.2 Incoming traffic model The incoming traffic i.e., the packet arrival process at the transmission buffer is assumed to be constant Fsec packets per second. If the duration of a slot is equal to T s [Sec], the packet arrival rate is F = FsecJs packets per slot. It is important to mention that for a given total bandwidth, the symbol duration of an O F D M system depends on the number of sub-carriers. For example, i f we assume a L carrier O F D M system and ideal Nyquist signalling, the duration of a symbol is Tsym = LTsscym, where Tsscym = 1/W is the duration of a symbol for the equivalent single carrier system. In our transmission frameworks we assume that Ns O F D M symbols are transmitted in each transmission slot irrespective of the number of carriers in the system. Therefore, the duration of a transmission slot, TJSec ] is also different for different number of carriers in the system for a given total bandwidth. We also assume a packet length of Np bits per packet. The number of packets that are transmitted in a slot depends on the total number of bits loaded in O F D M subcarriers in that given slot. 131 7.1.3 Adaptation model The adaptive modulator in carrier i is assigned an action a1 from the set of possible actions A1. It is assumed that the same rate actions are available in all carriers. Without loss of generality we assume that the set of available actions A1 = { a 0 , a i , a 2 , a 3 . . .au} , V i where action ao and au (u — 1,2, • • • ,U) correspond to transmitting no bit and u bits, respectively. The composite action space, A is the combination of all possible transmission rates in each subcarrier and is defined as a = (a 1 , a 2 . . . , aL), where a1 G A1 and a E A has total of A = UL actions. The role of the rate scheduler is to choose this composite action, a G A based on the current composite channel state c € C and the current buffer state, b G B, where B = {Zx Z 2 • • • ZB+i} is the buffer state space. Taking an action based on the buffer as well as the composite channel state is specified by a decision rule which we call the policy. More specifically, the stationary deterministic policy ip, which does not depend on time index, specifies action ain) at time step n as a function of the channel state c ( n ) and the buffer state 6 ( n ) . i.e., a{n) = <p(btn), c ( n ) ) . If a feasible action 1 9 a/n) = a G A is taken at time step n, the buffer dynamics can be expressed as where 6(n+i) and denote the buffer occupancy at time step n and (n + 1), respectively. tyl(a) returns the number of bits per symbol assigned to ith carrier i f composite action atn) is taken. This can be obtained by looking at the individual actions of ith carrier for that given composite action a( n). Without loss of generality, we use a normalized packet length i.e., the values of Np and iV s in Eq . (7.2) are chosen such that the ratio Ns/Np is equal to one. As a consequence we omit this ratio throughout the rest of the chapter. In practice, the packet length A^p can be thousands of bits per packet and the ratio can take any integer value. First transmission framework In the first transmission framework the total fixed transmit power, P T [W] is equally divided among the carriers. The fixed transmit power per carrier, therefore, is P = P T / L [ W ] . The 1 9 A feasible action does not lead to buffer overflow or negative buffer occupancy. Detailed description of feasible actions will be given in Section 7.2.1. L (7.2) 132 B E R of a given subcarrier is generally a function of the C N R as well as the number of bits v assigned to the subcarrier and can be written as BER(o ,u ) = f{g,v) (7.3) where g = hP is the C N R per carrier and / ( • , •) is the B E R function determined by specific modulation and coding scheme. For example, when uncoded M - Q A M is used in each sub-carrier, the exact expression of this function can be found in [72] and a good approximation is expressed as (e.g., see [75]) f(g,v) = 0.2 xeW(^^y (7.4) When binary-phase-shift (BPSK) modulation is used in each subcarrier, the B E R is given as B E R B p S K = ierfc(Vs). . (7.5) Since we use discrete channel state which is mapped to a unique range of C N R s rather than a unique instantaneous C N R value, using the expression of average B E R in a given channel state is appropriate. The average B E R of ith carrier, B E R over channel state c*, j = 1,2, - • • , L can be written as J^+1f(P*h\v)phi(hi)dhi B E R ( c » = T . (7.6) S e c o n d t r a n s m i s s i o n f r a m e w o r k In the second transmission framework, both the transmit power and bits are adaptively loaded in each subcarrier. A t first we assume that there exist an ideal coding scheme that allows information transmission without any transmission error. Therefore, the transmit power, P l corresponding to taking action a1 on ith carrier in channel state is connected via the Shannon capacity formula and is given by F ( c j , a i ) = i ( 2 a i - 1 ) (7.7) nj where hlj is the average received fading gain of ith carrier at channel state c*-. It is important to mention that in this case a1 represents the number of coded bits loaded on ith subcar-rier. It is important to mention that in this transmission framework Ns is the number of 133 coded symbols transmitted in each transmission slot. If the data packets can tolerate some transmission error instead of having an error free transmission, a practical modulation and coding scheme can be used. In this case the transmit power, P* rac corresponding to the rate action d1 can be approximated using the well known C N R gap approximation [76] 0 PUcj,a i) = x - ( 2 a ' - l ) (7.8) where 0 is a coding and modulation dependent parameter. For example, with uncoded M Q A M , 0 can be calculated as [76] 2 Q - i / B E R C V 4 (7.9) where Q x ( ) is the inverse standard Gaussian Q-function and BERn is the target B E R . 7.2 Scheduling Algorithms In this section we formulate our buffer and channel adaptive loading frameworks as the finite M D P . Then optimal bit-loading policies are obtained using equivalent L P methodol-ogy. Finally, a simple suboptimal algorithm which shows the performance very close to the optimal one is proposed. 7.2.1 Problem formulation A n unconstrained M D P is a model for deciding on how to act in a stochastic environment where outcomes are uncertain [73]. It is described through a set of decision epochs or time slots or stages T — 1,2, • • • , n, a set of states S = {sl, s2, • • • , sN}, a set of actions A = {a 1 , a 2 , • • • , au}, a set of state and action dependent immediate costs x: K, i—> R, and a set of state and action dependent transition probabilities. Set /C = {(s, a) : s G S, a G ,4 S} is the set of state-action pairs. While the system is in state S ( „ ) = sj G <S at decision epoch or time-slot n , the decision maker selects an action a(n) from the set of actions Asj available at state sj G S, where UsjesAsj = A. In the next time-slot, the system moves to a state sk G S according to the transition probability p ( s ( n + i ) = s f c |s( n) = sj, d(n)) and the decision maker incurs a one step immediate cost x(s(„), a( n)). 134 A policy as a mapping from state to actions specifies the decision rule to be used at all time slots. With a stationary deterministic policy ip, the expected long-term average cost per stage is l M ^ = J S 0 M £ E , ^ a ( B ) , ^ ( B ) ^ ' ( 7 ' 1 0 ) n = l where expectation, E s [ ] is over random evolution of the states of the M D P . A n optimal policy denoted by ip* is the one that incurs the minimum average cost per stage i.e., </?* = argmin Jv (7.11) where IT is a set of all stationary policies. The composite state space S of adaptive loading framework is composed of the buffer state space B and composite channel state C. The number of states in S = C x B is N = (B + 1) x QL. Since a finite size buffer is used at the transmitter, taking certain actions at specific buffer states leads to buffer overflow. This overflow can be avoided by taking an action ain) at time slot n such that L b{n) + F-J2^^(n))<B. (7.12) i=l On the other hand, the transmitter cannot transmit more packets than available at the buffer. So, the action a has to follow the inequality L J2^(a{n))<b{n). (7.13) i=i Using Eqs. (7.12) and (7.13) a feasible action space in state s, As, where, \Js&sAs = A can be found easily. Transition probabilities between states are based on transition probabilities of channel Markov chains and buffer dynamics Eq . (7.2) and can be expressed as follows: L p{s{n+l) = = s\a[n)) = P r o b . ( A ( ^ ) | A ( S i ) ) 5 ( V ( ^ ) - ( V ( S i ) - ^ * f e ( a H ) + F ) ) k=l (7.14) for certain a ( n ) = a G Asi, and s\ sj G S. Functions A(s) and V ( s ) return the composite channel state c and the buffer state b of composite state s, respectively. 5(x) returns 1 i f x = 0 and 0 otherwise. 135 Firs t transmission framework In our proposed bit-loading framework which minimizes the aggregate B E R with a fixed transmit power, we have two types of cost; delay cost and aggregate B E R cost. The aggregate B E R of the multicarrier system in state, S(„) = s G S for taking an action a(n) = a G ASn can be written as R F R U n i - ^ t i B E R ( ^ ( ^ ) ) , ^ ( a ( n ) ) ) ^ ( a ( n ) ) B b R a g g ( s ( n ) , a ( n ) ) - , (7.15) E i = l * ( a ( n ) ) where i1 returns ith carrier channel state of composite state s. The expected long-term average B E R cost under policy <p is ! M B E R . J p ) = Virn^ — E s [ B E R a g g ( s ( n ) , <p(s{n)))]. (7.16) n=l In order to avoid notational confusion, it should be mentioned that, in general, B E R a g g and B E R a g g denote the immediate and the long term average aggregate B E R , respectively. The delay cost is the average number of time slots that a packet has to wait at the transmission buffer before transmission. The immediate delay cost due to buffer occupancy under the policy ip is d(8(n)Ms(n))) = ^ ^ - C7.17) According to Little's formula, the time average delay in the buffer, D can be expressed as i M h 71=1 Since both the costs; B E R and delay costs are conflicting with each other, we can formu-late the problem as an unconstrained Markov decision process (TJMDP) with a trade-off factor or a constrained Markov decision process ( C M D P ) . When the problem is posed as an U M D P , the immediate cost function under a stationary deterministic policy ip is s ( S ( n ) , ¥ > ( S ( n ) ) ) = + / ? B E R a g g ( S { n ) , ^ ( S ( n ) ) ) (7.19) where (5 (> 0) is a trade-off factor and by changing its value we can obtain different trade-offs between average delay and aggregate B E R . For a given p, the stationary deterministic optimal policy (p* can be obtained using dynamic programming such as R V I or PI [73]. 136 Minimum aggregate B E R and average delay under the policy <p* are obtained from Eqs. (7.16) and (7.18). In C M D P , the objective cost is minimized while keeping the additional costs (called constrained costs) below some given bounds. In this proposed framework, our objective is to minimize the aggregate B E R while keeping delay cost below a target threshold, the problem thus can be formulated as follows: arg min BER a g g ((^) (7.20) subject to: D(tp) < Dt (7.21) where TlR is the set of all randomized stationary policies that are uniquely characterized with probabilities 0^(a) of applying action a G As in state s G S. Dt is an allowable maximum long-term average delay. The formulated C M D P can be solved using equivalent L P methodology [73]. A brief description on equivalent L P methodology to find optimal bit-loading policies is given in the next Section. S e c o n d t r a n s m i s s i o n f r a m e w o r k Similarly, in a bit and power loading framework which minimizes transmit power while achieving a target delay constraint, there are two types of costs. One is buffering delay cost as described in Eq . (7.17) and the other is power cost which can be expressed as L • Pr(s{n),ain)) =Y,Pi(£i(Hn)),Vi(cL(n))) (7-22) i=l where Pl(c%, a1), in general, is the required transmit power in ith carrier for taking an action a1 at state cl which can be obtained from Eq. (7.7) or (7.8). The expected long term average total power cost under policy <p is 1 M P T M = Yirn^ — Y, E , [ p T ( s ( n ) , ¥>(*(„)))]• C 7 - 2 3 ) n = l Again, in case of minimizing the total transmit power while meeting a given delay con-straint, we have two options to pose the optimization problem at hand. One is formulating the problem as an U M D P process and the other is formulating the problem as a C M D P . 137 When the problem is posed as an U M D P , the immediate cost function under a stationary deterministic policy <p is *(*(„), ¥>(*(»))) = ~^+PPMn)M*in)))- (7-24) With a C M D P the power optimization problem can be formulated as follows: arg min PT(</?) (7.25) <penR subject to: D(ip) < Dt. (7.26) 7.2.2 Optimal scheduling Although dynamic programming offers an elegant, unified treatment of a wide range of stochastic control problems, the curse of dimensionality gives rise to prohibitive computa-tional requirements of large-scale problems, such as this O F D M bit loading problem. A s we mentioned in previous section, there are number of algorithms, for example, R V I , PI, and L P that can be used to find the optimal solution for stochastic optimization problems formulated as a M D P . L P is studied in solving M D P models because of its elegant theory and the ease in which it allows inclusion of constraints [73]. To describe the dual L P 2 0 let us consider that z(s,a) represents the "steady-state" probability that the process is in state s and action a is applied. We seek to find the control policy which is represented in terms of probability distribution z over S x A. The optimal policy z* can be obtained as minimize ^ B E R a g g ( s , a)z(s, a) (7.27) seS, aeAs subject to : ^ d(s, a)z(s, a) < Dt (7.28) seS,aeAs £ > ( i , a ) = Y, z(s,a)p(j\s,a), WjeS (7.29) aeAj seS,aeAs Y z(s,a) = l (7.30) ses,aeAs z(s,a)>0,VseS,VaeAs. (7.31) 2 0 In order to describe the LP methodology, we consider the problem of minimizing aggregate B E R as an example. However, the transmit power minimization problem can be considered using the same methodology. 138 The inequality constraint in Eq . (7.28) is to keep the long-term average delay below the given threshold whereas the equality constraint in Eq. (7.29) satisfies the well known Chapman-Kolmogorov equation. The constraint in Eq . (7.30) ensures that the sum of the probabilities z(s,a) is equal to one while Eq. (7.31) is ensuring that the individual probability is greater than zero. If there exist an optimal solution z* to the LP, there exists an randomized stationary policy ip* that is optimal for the C M D P . In general, the optimal policy ip* for a C M D P is randomized. Now If Yla'eAs z*(s>a') = 0 f ° r some s G S, an action that drives the system to Sz* = {s G S : Yla'eAs z *( s > a ' ) > 0} i s chosen in each state [73]. The delay-BER trade-offs for different number of carriers are shown in Fig . 7.2. In order to make a fair comparison for different number of carriers, we used the same total transmit normalized (w.r.t. N0W) power, P T = 1. Due to the high complexity of finding optimal policies we had to restrict our simulations up to four carriers. We used three state Rayleigh channel model for each carrier. The states are partitioned such that probabilities of being in each state are equal. For example, this type of channel model can be found in [65], [66]. The channel variations across the subcarriers are assumed to be identically and independently distributed (i.i.d) with an average received power gain, h0 =15[dB]. The available rate set per carrier, .4* = [0 2 4]. A packet arrival rate of 2 packets per time slot for equivalent single carrier case is used and thus the packet arrival rate for k carrier system is 2 x k packets per time slot. As mentioned in Section 7.1.2 the slot duration of an O F D M system with k subcarriers is T£ = k x Tssc, where T f is the slot duration of an equiva-lent single carrier system. Therefore, in Fig . 7.2, the average delay for different number of carriers is normalized by the duration Tssc. In our proposed framework, the minimum achievable delay is one time slot. The normalized minimum achievable delay is, therefore, k times that of an equivalent single carrier system and consequently the minimum achiev-able delay starts from k time slots rather than starting from one time slot. This figure also shows that as the maximum tolerable delay increases, the aggregate B E R decreases. This is expected because of temporal diversity (TD) effects in time domain. The packet can wait at the transmission buffer until the channel condition is good enough to be transmitted. If (7.32) 139 -2.1 m Ui o -2.15p -2.35 -2.25 -2.45 -2.3 -2.4 -2.2 -2.5 Four carriers -2.55 -2.6 5 6 Normalized (by 1*°) delay in slots 8 9 2 3 4 Figure 7.2: Optimal delay and aggregate B E R trade-offs with different number of carriers (Doppler frequency, fd =300Hz). there is no delay constraint, the minimum achievable aggregate B E R , which corresponds to water filling case, can be achieved. It is interesting to see that as the number of carriers increases in the system, the delay limited aggregate B E R , in high delay tolerant region, decreases for the same traffic arrival rate (packets per second). This is owing to the spec-tral diversity (SD) effects in frequency domain. A s there are more carriers in the system, more SD is achieved. It is also interesting to observe that in low delay-constrained region, although the system has higher number of carriers, the aggregate B E R is higher (see cross-over points between the curves in Fig . 7.2). This is due to the fact that in that region, the T D takes over the SD. In other words, the T D is more dominant than SD. The delay-power tradeoffs for different number of carriers are shown in Fig . 7.3. In this case we assume ideal coding scheme with rate set per carrier, .A 1 = [0 2 4]. Therefore, the corresponding transmit normalized power levels were obtained using Eq . (7.7). F ig . 7.3 shows that as the maximum tolerable delay increases, the total transmit power decreases as expected due to T D as explained above. Another important remark from the figure is that as the number of carriers increases in the system, the SD gain becomes marginal. In other 140 Figure 7.3: Optimal delay and power tradeoffs with different number of carriers (Doppler frequency, f^ =100Hz). words, as we add more carriers in the system, the power saving that results from the extra additional carrier decreases. For example, when the system has two carriers instead of one, it saves a lot more power in order to meet the same target delay. However, adding the third carrier does not save that much power and the same scenario extends to the fourth carrier. 7.2.3 Suboptimal algorithm The complexity of finding the optimal bit-loading policy is enormous for large number of parallel carriers as it is often the case in O F D M systems. This phenomenon is commonly referred to as the curse of dimensionality. Even i f we could solve the problem using some advanced software which can handle L P with millions of variables, such a policy might not be realizable practically because of memory requirements of the lookup table to store the optimal policies. Therefore, we resort to the suboptimal solution. The principle is based on the divide and conquer approach. Optimal rate scheduling algorithm is produced for the equivalent single carrier system and then, using this solution, transmission rate for each 141 carrier is found considering a carrier's state and buffer state individually. The sum rate, i.e., the summation of these individual carrier rates is distributed among the carriers using a greedy approach in order to find the final suboptimal rate allocation policy. The suboptimal rate allocation algorithm is described below step-by-step • Step 1: Find the optimal transmission rate a1 for each carrier assuming that the carri-ers are independent • Step 2: Find the sum rate RSUm — J2i=ia* • Step 3: Divide the sum rate RSUm among the carriers using the greedy approach, according to the composite channel state c. In Step 1, the optimal transmission rate for each carrier is found from the optimal policy set of an equivalent single carrier system with a finite transmission buffer of size B and the system bandwidth of W[Hz] . The stationary optimal deterministic policy of the single carrier transmission system can be found formulating the problem as an U M D P (see, for example, [66]). It should be mentioned that as the total number of states is much less than in the multicarrier system, R V I can be used to find the optimum deterministic policy. Once the optimal policy for single carrier system for a fixed tradeoff factor f3 is available, the total sum rate is found adding the individual optimal rates as follows: • Initialize the set C to the set of all carriers. • Pick up the best carrier i from a set of all unassigned carriers C. Without loss of generality, consider that this carrier is in state c*, and the buffer being in state 6(n). The composite state for this carrier is ssc = (6(n), c*). The subscript "sc" is to mean the composite state of the equivalent single carrier case. • Find the optimal action a*(ssc) corresponding to the state ssc from the Table of equivalent single carrier case optimal policy. Update the buffer occupancy 6(n) = — a*(ssc) and remove the carrier i from the set of unassigned carriers £ . • Repeat the above procedure until all the carriers are assigned. • A d d the transmission rate in all subcarriers to find the sum rate RSUm in Step 2 of the suboptimal rate allocation algorithm. 142 -7.5 1 L f=100Hz i i Optimal * Sub-optimal " — — ? f=300Hz d It * * i i . * I I I I L 2 2.5 3 3.5 4 Normalized average delay Figure 7.4: Optimal and sub-optimal delay and aggregate B E R trade-offs for different fad-ing rates in two carrier case. In step 3, the greedy allocation, which has been used in literature for optimal resource allocation (see, for example, [69], [68]) improves the rate allocation among the carriers. The greedy rate allocation procedure wi l l be described in the next section. The delay-BER tradeoffs with the proposed suboptimal bit-loading algorithm with dif-ferent number of carriers are plotted in Figs. 7.4, 7.5 and 7.6, respectively by changing the tradeoff factor (5 of a single carrier policy. We have also plotted the optimal delay-BER tradeoffs in Figs. 7.4 and 7.5. In these examples, we have considered three channel states per carrier and a rate set per carrier is a1 — [0 1 2 3 4]. In suboptimal policy performance simulations, due to the M A T L A B software-based simulation time requirements we had to restrict ourselves up to a four carrier O F D M system. In a real system, there are two options to implement the suboptimal loading scheme. One way is to store the single carrier system optimal policies, which are obtained off-line, in a lookup table. These pre-stored single carrier optimal policies are then used to find the suboptimal policy for each carrier using the greedy allocation, in online fashion, as described above. Since one needs to store only single carrier system's policy, it requires less memory space but requires more online com-143 Normalized delay Figure 7.5: Optimal and sub-optimal delay and aggregate B E R trade-offs for different fad-ing rates in three carrier case. putation. The other option is to find the suboptimal policies for multicarrier system using the single carrier system optimal policies and the greedy allocation off-line. Then these suboptimal policies are stored in a lookup table. This strategy requires less on-line com-putation but requires more memory space. Figs. 7.4, 7.5 and 7.6, show that as the fading rate increases (i.e., the channel fading rate becomes faster), the aggregate B E R decreases in order to maintain the same delay constraint. This is due to the influence of the fading rate on T D . A s the channel becomes faster, the probability that the packets w i l l experience a better channel condition within a given number of transmission slots increases. In this regard, it is also worthy to mention that the minimum achievable aggregate B E R in order to maintain a hard delay constraint (a delay of one time slot), is not affected by the fading rate. In this hard delay-constrained case since the packets are to be transmitted within one time slot, T D is not achieved at all. The figures also show that the sub-optimal algorithm offers almost the same performance as the optimal one and as the number of carriers in the system increases, the performance of the suboptimal algorithm slightly degrades compared with the optimal algorithm. 144 6 4 2 0 100Hz ^ f„= 300Hz 4 4 . 5 5 5 . 5 6 6 . 5 Normalized delay Figure 7.6: Sub-optimal delay and aggregate B E R trade-offs for different fading rates in four carrier case. 1 4 5 0.175 0.145 Optimal * Sub-optimal 3 4 . 5 6 7 Normalized delay (normalized by the single carrier time slot) Figure 7.7: Optimal and sub-optimal delay and power trade-offs for different fading rates in two carrier case. Similarly we have plotted the suboptimal delay-power tradeoffs in Figs. 7.7, 7.8 and 7.9. As expected with the increase of the fading rate, the total average transmit power de-creases in order to maintain the same delay constraint. The power-delay trade-off curves for different fading rates start from the same point which is expected in the hard delay-constrained case. These figures also show that the proposed suboptimal policy attain delay-power tradeoffs which are very close to the optimal ones. One further effective method to reduce the complexity of O F D M loading problem is block wise loading (see, e.g. [68]). In this block loading method, it is assumed that the neighboring carriers undergo roughly the same fading gain. So, the neighboring carriers are grouped in a block and each block is loaded with the same rate (or both power and rate) which reduces the complexity of the loading algorithm compared with loading each carrier individually. For example, an O F D M system with 48 carries w i l l have 12 such blocks i f 4 neighboring carriers are grouped to-gether to form a block. If we use the block wise loading methodology, the number of composite states as well as total number of actions wi l l be reduced and eventually it w i l l lead to a simpler implementation. 146 0.16 0.155 h 4 5 6 7 8 Normalized delay (normalized by the single carrier time slot) Figure 7.8: Optimal and sub-optimal delay and power trade-offs for different fading rates in three carrier case. 0.15 0.148 0.146 0.144 ^ 0.142 a> S o I 0.14 (0 > < 0.138 0.136 0.134 0.132 0.13 —i r ~i r-0Hz f=300Hz 4.5 5 5.5 6 6.5 7 7.5 8 Normalized delay (normalized by the single carrier time slot) 8.5 Figure 7.9: Sub-optimal delay and power trade-offs for different fading rates in four carrier case. 147 7.3 Effect of Correlation among Subcarriers' Fading Gains In this section, we study and explore the effect of correlation between the subcarriers' fading gains of a M C M system on its bit and power loading for delay-constrained and no delay-constrained communication. We consider both continuous and discrete rate and channel gain variation cases. For continuous channel gain and rate variation, Lagrange for-mulation is used in order to find the optimal loading policy. For discrete rate adaptation and discrete channel gain variation, the Lagrangian formulation is not applicable. There-fore the optimal loading policies for both delay-constrained and no delay-constrained cases are obtained via a greedy allocation. 7.3.1 Channel and rate allocation model The composite channel gains of all subcarriers which are assumed to be known at the transmitter, are denoted by a vector, h — (ti1, ti2, • • • ,hL). For continuous channel model ti G = l,...,Q and the set of possible composite channel gains is h e H = (^R+)Q with joint P D F of the composite channel state denoted by Ph(h). For discrete channel model ti G {hi,..., HQ), i = 1,..., L and the composite channel gain h of all the carriers belongs to the set H = { h i , . . . , h ^ x } where hj, % = 1,..., HL, are all combinations of discrete channel states of all parallel carriers with probability of h G H denoted by P(h) . In each transmission slot, the transmitter adaptively assigns the transmission rate of A;th carrier, Rk and adjusts the transmit power level, Pfc by joint consideration of the different subcarriers' received power gains i.e., h . Therefore let us consider the transmission rate of A;th carrier is function of h and the transmission rates in the parallel subcarriers denoted by the vector, R = (i?x(h), i ? 2 (h ) , • • • , i?z,(h)). In continuous rate adaptation it is assumed that any positive rate is achievable i.e. Rl(h) G whereas in the discrete rate case it is assumed that Rl(h) G {0,1,2,...} for all i = 1,..., L. In order to adjust the transmit power we use the well known S N R gap approximation in (7.8). 148 7.3.2 Rate allocation with no delay constraints Water-filling power, P W F defined as the minimum required average transmit power of a M G M system with no delay constraint can be expressed as L P W F = min E Ri(h) s.t. 5>Wh), /0) ,t= i i=l > F (7.33) (7.34) where the operator E[-] is an expectation operator taken with respect to the joint PDFph(h) -In Eq. (7.34), the inequality constraint is to ensure that the average sum transmission rate in the parallel carriers is greater or equal to the data rate F. The problem of maximizing average transmission rate (i.e., water-filling capacity) with an average power constraint, which is the dual problem of our optimization problem in Eq . (7.33), has been solved earlier [75]. Continuous rate and channel variation: Using Eqs. (7.33) and (7.34), we form the following Lagrangian J ( R ( h ) , A ) = E i = i + AE E#(h) i=i (7.35) where A is the Lagrange multiplier. Finding the gradient of (7.35) with respect to R ( h ) and equating it to zero, we get L independent equations in Rk(h) that solve to iT (h ) = IV (ti) = W\og2 XWti 01n2 (7.36) The expression for the rate allocation in Eq . (7.36) is also optimal for the single carrier (L = 1) case for some A. Lagrangian constraint A can now be obtained from the constraint on the average sum rate in Eq . (7.34) L /•oo poo J2 •I i ? i ( h )p h ( h )d / i 1 •••dhL = F (7.37) i = i which employing i?*(h) = Rl(hl) simplifies to V / R\ti)p{ti)dti = F i = l Jh{=o (7.38) 149 where p{ti) is the marginal distribution of the received power gain ti, % = 1,..., L. Eqs. (7.36) and (7.38) show that the loading policy in no delay-constrained case with continuous rate adaptation decouples into L single carrier rate allocation problems that is dependent only on the marginal distributions of channel gains in each channel. In other words, the water-filling power P W F does not depend on the correlation among the subcarriers' fading gains. Intuitively, the result is also expected. In no delay-constrained case a data bit can wait theoretically infinite amount of time. Therefore, full diversity is achieved in both domains; SD and TD and it does not matter whether the channel fading gains are correlated or not. Discrete rate and channel variation: Let the discrete rates and discrete received power gains be defined as in Section 7.3.1. In this case the optimal rate allocation of problem defined in Eqs. (7.33) and (7.34) can be solved using the greedy allocation. It is impor-tant to mention that the Lagrangian formulation is not applicable to discrete rate variation case. The greedy allocation is performed both in time and spectral domain and is given as follows: • Step 1: Form a discrete rate allocation vector R with H = Q x HL elements R = {R\h1),...,R1(hHL),...,RL{h1)1...RL(hHL)} and s e t R = { 0 , 0 . . . , 0}. Let L HL *W = E E P W ( h ' ) ' h ' W ) (7-39) 1=1 1=1 be the average power needed for the discrete rate allocation vector R , where h;(z) is the normalized power gain of carrier i. of composite state h/. • Step 2: Let R z = {R(l),R(l) + 1,..., R(H)}, for 7 = 1,..., H. Find 1 such that I = arg min (p(R,) - P(R)) (7.40) and set R = Rr. • Step 3: If (7.34) is satisfied stop; else go to step 2. 150 As a numerical example we consider a two carrier M C M system whose subcarriers' gains are faded according to bivariate Rayleigh distribution. The bivariate Rayleigh distribution can be expressed as (see, for example, [77]) P(ai ,a2)(ai ,^i; "2,^21/5) 4a! a 2 0 ^ 2 ( 1 - p ) exp at — - I — -1 — p \Qi 0,2 2y/paicc2 (1 - / ) ) v W J (7.41) where ax,a2 > 0, Q f c = E[a|] , k = 1,2, and p = cov(a i , a 2 ) / ( v a r ( Q ; i ) v a r ( c * ; 2 ) ) is m e correlation coefficient and 0 < p < 1 and J 0(-) is the modified bessel function of first kind and zero order. In our numerical example we used the same channel gain variance of var( |a f c | 2 ) = 1 in each carrier, Wsubcar = l [KHz] and SN0 = 10~ 6 [W/Hz]. To simulate the discrete channel model, two dimensional space of bivariate Rayleigh distribution is quan-tized based on a uniform grid with 10 levels with step size 0.2. For discrete rate adaptation and discrete channel variations, the water-filling power P w for two carriers system is shown in F ig . 7.10. In this plot, we have used two different values of p; p — 0.1 and p = 0.8 and it shows that for a given average rate constraint there is an insignificant difference between the values of P W F for different values of p. This very small difference comes from the fact of discretization of the channel gains. For discrete rate adaptation, it still remains unsolved whether the optimization can be decoupled into L single carrier loading problems or not. However, numerically it is observed that for larger number of discrete channel states, the loading policy does not change with different values of p. 7.3.3 Rate allocation with hard delay constraints Delay-limited power, P D L , defined as the minimum required average total transmit power of a M C M system with hard delay constraint can be written as ' L J ] P ( i ? i ( h ) , ^ ) l , (7.42) P D L = min I R i (h), i=l, . . . ,L .i=l s.t. | ] ^ ( h ) > F , (7.43) i=i In Eq . (7.43) the inequality constraint means that the instantaneous sum-rate in all parallel carriers should be greater than or equal to the data rate in order to meet the hard delay constraint. Maximization of sum-capacity of M C M system with an instantaneous power 151 Q I — • 1 I I I I I I I I 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Rate [Kbits/sec] Figure 7.10: Power versus rate constraint for delay limited and non-delay limited rate allo-cation. constraint, which is a dual problem of the optimization in Eqs. (7.42) and (7.43), has been solved in [67]. For discrete rate adaptation, the optimal rate allocation for a given composite state hj e H can be obtained using the greedy allocation of Section 7.3.2 by using P(h) = 1 i f h - h i and P(h) = 0 i f h ^ h* (see also [68]). For the numerical settings of Section 7.3.2, the hard delay limited power, P D L is plotted in Fig. 7.10 for different values of p. This figure shows that as the correlation between subcarriers' fading gains increases, the value of P D L increases. This phenomenon can be explained as follows. In hard delay limited case since the data transmission rate is to be guaranteed at a fixed rate F in each time slot, a data bit cannot wait in order to achieve T D in time domain. However, due to having more than one carrier in the system, SD among the carriers in frequency domain can be achieved. If the fading gains among the carriers are correlated, less SD is achieved and consequently required transmit power increases in order to maintain the same instantaneous transmission rate. It is worthy to mention that full SD is achieved i f the subcarriers' fading gains are independently distributed and the 152 required power in this case is the lower bound of P D L . 7.4 Conclusions In this chapter, we have studied an optimal and suboptimal loading algorithms of an O F D M system for delay-constrained communication over correlated fading channels. Specifically, we have proposed two different transmission frameworks for delay-constrained O F D M communication. One is the bit-loading framework which minimizes aggregate B E R of a constant power O F D M system while meeting a delay constraint of the packets at the trans-mission buffer. The other is the bit and power loading algorithm which has the objective to minimize the total average transmit power while maintaining a target delay constraint. Op-timal loading policies in both cases are obtained using L P methodology formulating them as the M D R Since finding the optimal policies and implementing them in reality are highly complex, i f not impossible, we have also explored a suboptimal loading algorithm based on an equivalent single carrier optimal loading scheme and a greedy approach. Since the suboptimal loading algorithm requires only finding and storing the optimal policy of the equivalent single carrier case with fewer number of states, it is simple to realize it prac-tically. The selected numerical results have shown that the suboptimal loading scheme in both cases attains a very close tradeoff performance as the optimal one. Finally, we have explored the effect of correlation between the subcarriers' fading gains of a M C M system on its bit and power loading in two extreme cases: delay-constrained and no delay-constrained communications. For no delay-constrained case the correlation between subcarriers fading gains does not have any influence on the loading policy. There-fore, the average total transmit power is not influenced by the correlation between between the subcarriers fading. For discrete rate adaptation as well as discrete channel gain varia-tion, the optimal loading policies for both cases have been obtained via a greedy allocation. Assuming discrete rate adaptation and discrete channel gain variation, numerical examples have been demonstrated for different degrees of correlation. The results have showed that the required transmit power in hard delay-constrained case increases as the correlation in-creases. However, the degrees of correlation does not have any significant effect on the required transmit power in no delay-constrained case. Although we have considered only correlation among the carriers' fading gains, it is worthy to mention that time correlation 1 5 3 does not influence our conclusions. Bibliography [63] S. Shakkottai, T. S. Rappaport, and R C. Karlsson, "Cross-layer Design for Wireless Networks," Submitted for possible Journal publication, June 2003. Also available in http://www.ece.utexas.edu/ shakkott/Pubs/cross-layer.pdf. [64] R. Berry and R. Gallager, "Communication over fading channels with delay con-straints," IEEE Trans. Inform. Theory, vol. 48, pp.1135-1149, M a y 2002. [65] A . T. Hoang and M . Motani, "Buffer and channel adaptive modulation for transmis-sion over fading channels," in Proc. IEEE Int. Conf. Commun. (ICC03), Anchorage, A K , May 2003, pp. 2748-2752. [66] D . Djonin, A . K . Karmokar, and V. K . Bhargava, "Optimal and sub-optimal packet scheduling over correlated fading channels," in Proc. IEEE Int. Conf. Commun. (ICC04), Paris, France, Jun. 2004, pp. 906-910. [67] L . Goldfeld and V. Lyandres, 'Capacity of the multicarrier channel with frequency-selective Nakagami fading," IEICE Trans. Commun., vol. E83-B, pp. 697-702, Mar. 2000. [68] C. Y. Wong, R. S. Cheng, K . B . Letaief, and R. D . Murch, "Multiuser O F D M with adaptive subcarrier, bit, power, and power allocation," 1EEEJ. Select. Areas Commun., vol. 17, pp. 1747-1758, Oct. 1999. [69] D . N . C. Tse and S. V. Hanly, "Multiple access fading channels-Part I: Polymatriod structure, optimal resource allocation and throughput capacities", IEEE Trans. Inform. Theory, vol. 44 no. 7, pp. 2796-2815, November 1998. [70] L . Yang and M . - S . Alouini , "Cross layer analysis of buffered adaptive multicarrier transmission," in Proc. IEEE Veh. Technol. Conf. (VTC04 Fall), Los Angles, C A , September 2004. 155 [71] H . S. Wang and N . Moayeri, "Finite-state Markov channel-A useful model for radio communication channels," IEEE Trans. Veh. Technoi, vol.44, pp. 163-171, Feb. 1995. [72] P. K . Vitthaladevuni and M . - S . Alouini , " A recursive algorithm for the exact B E R computation of generalized hierarchical Q A M constellations," IEEE Trans. Inform. Theory, vol. 49 , no. 1 , pp. 297-307, January 2003. [73] M . L . Putterman, "Markov decision processes : discrete stochastic dynamic program-ming," New York : John Wiley & Sons, 1994. [74] T. S. Rappaport, "Wireless Communications Principles and Practice," Prentice Hal l , NJ,2002. [75] S: T. Chung and A . J. Goldsmith, "Adaptive multicarrier modulation for wireless systems," in Proc. The thirty-fourth Asilomar Conf. Signals, Systems and Comp., vol. 2, 29 Oct . - l Nov. 2000, pp. 1603-1607. [76] J. M . Cioffi, " A multicarrier premier," November 1991. Also available in http://www.stanford.edu/group/cioffi/pdf/multicarrier.pdf [77] M . K . Simon and M . - S . Alouini , " A Simple Single Integral Representation of the Bivariate Rayleigh Distribution," IEEE Commun. Letter, Vol . 2, No. 5, pp. 128-130, M a y 1998. 2004. 156 Chapter 8 Variance-Bounded Rate Allocation for Constant Rate Media Streaming 2 1 In order to take advantage of time-varying nature of wireless links, transmission rate, transmission power or both rate and power are varied according to the channel quality. These adaptive transmission techniques can lead to efficient use of the communication resources, see for example [78]. A s we mentioned in Chapter 1 that average transmission rate maximization algorithms for fading channels are suitable for services which have no delay constraint [79]. On the other hand fixed rate transmission with channel inversion power control for fading channel is suitable for services which have hard delay constraint. However, in order to satisfy some upper-layer QoS parameter, e.g., delay requirements, the transmission system should not only maintain an average transmission rate but also it may require to guarantee a bound on the variance of the transmission rate. For example, in case of high-quality media streaming over wireless links, there should be enough number of packets at the play-out buffer such as the video frames can be played in timely manner without any interruption (see for example [81]). In other words, in order to play out the entire video sequence smoothly, the buffer should not experience an underflow. As such the constant rate downloading from the server can avoid buffer underflow. But this constant rate downloading policy may not lead to a power efficient downloading scheme. On the other hand, from channel quality variation point of view, packet transmission should be scheduled at higher rate during relatively better channel qualities as suggested by the water-filling algorithm. This water-filling policy, which guarantees an average rate constraint, may cause too much play-out buffer outage due to unavailability of the video frames on time. Since the video frames are to be available at the buffer before their taken out time 2 1 The research work presented in this chapter is in preparation as D. V. Djonin, Md. J. Hossain, and V. K . Bhargava, "Variance-Bounded Rate Allocation for Constant Rate Media Streaming", to be submitted in IEEE Trans. Wireless Commun. 157 instants from the buffer, instead of having constant rate download some variance in the downloading rate can be tolerated. In this chapter, we study a packet scheduling scheme for on-demand constant rate me-dia streaming over time-varying wireless links. The objective of our proposed scheduling scheme is to minimize the average transmit power while maintaining a low receiver play-out buffer outage probability. Towards this objective, we formulate the scheduling scheme as a new rate allocation scheme namely V B R A scheme. The proposed V B R A scheme, in general, is useful to any application where the QoS parameters require not only an average transmission rate guarantee but also a certain guarantee on the variance of the transmission rate. For continuous rate adaptation and channel variation case, a closed-form solution for the optimal transmission rate is obtained in terms of the channel fading gain, average rate constraint and the variance of the transmission rate. Assuming a long size media frame for constant rate media streaming, a mathematical connection between the play-out buffer outage probability and the variance of the transmission rate is established. Specifically, we propose the joint probability density function (JPDF) method based on Gaussian approx-imation (GA) in order to find the variance of transmission rate for a given buffer outage probability. Due to the computational complexity of JPD method, we also introduce a sim-pler method namely diffusion approximation (DA) method, which was applied earlier in queueing networks performance analysis (e.g., see [82]), in order to approximate the play-out buffer outage probability. Using this expression, we explore the trade-offs between the average transmit power and the probability of buffer outage during the media play-out. 8.1 System Model In order to describe the general variance bounded rate allocation problem, let us consider a transmitter that transmits information bits to a receiver as shown in F ig . 8.1. The channel is a flat fading wireless link which is time-varying in nature. We assume that the channel fading gain h is an ergodic process with P D F of Ph(h). Transmission rate R and power P are adjusted according to the channel fading gain. Therefore, the transmission rate is a function of channel fading gain h and can be denoted as R(h). In continuous rate adaptation it is assumed that any positive rate is achievable i.e., R(h). In order to adjust the transmit power we assume that there exists an ideal coding scheme that allows information transmission 158 Prestored encoded Media I I I - Download Block length TB i r^ i L I •i i i-t Frame duration T/=LTB Frame Play-out (F bits) Play out F bits/frame Play-out buffer Frame Play-out (F bits) - Download and play-out phase -Phase of to [Sec] time index, / Figure 8.1: Scheme of the variance-bounded rate allocation. without any transmission error. Based on the channel capacity formula the power level, P corresponding to a transmission rate of R is given by P(R(h), h) = ^-(2R^'W - 1), (8.1) where W is the system bandwidth and ui2 = N0W is the additive white gaussian noise power. It is important to mention that R represents the number of coded bits. If the trans-mission system can tolerate some specified error rate, a practical modulation and coding scheme can be used. In this case the transmit power, P can be approximated using the well known S N R gap approximation [83] ?(R(h),h) = ~ - ( 2 R W w - 1 ) , (8.2) where 6 is a coding and modulation dependent parameter. For example, with uncoded M - Q A M , 6 can be calculated as [83] where Q _ 1 (•) is the inverse standard Gaussian Q-function and B E R 0 is the target B E R . For the time being let us consider the QoS parameters of the service, which has to be transmitted, are determined by two factors; one is the average transmission rate of R [Bits/Sec] and the other is the rate variance of a\. Later on we w i l l see that the average transmission rate and the transmission rate variance can be determined by some different QoS parameters in case of on-demand high-quality media streaming over wireless chan-nels. BERn (8.3) 159 8.2 Variance-Bounded Rate Allocation In order to minimize the transmit power while maintaining the average rate constraint of R and the variance of the transmission rate a\, we can formulate the following constrained optimization problem P a v = mmE[?(R{h),h))}, (8.4) R(h) s.t. E [R(h)] > R (8.5) E [(R(h) - R)2} < o\ (8.6) where the operator E[-] is an expectation operator taken with respect to the P D F Ph(h) and P a v is the average transmit power for the given average rate constraint and variance bound. The inequality constraint in Eq . (8.5) is to ensure that the average transmission rate is greater or equal to the data rate, R whereas the inequality constraint in Eq . (8.6) is to ensure that the variance of transmission rate should be kept below a given target requirement. It is important to mention that problem of maximizing average capacity of fading channel with an average power constraint has been studied earlier in [80]. It was shown that the power adaptation policy for fading channel which maximizes the average capacity with an average power constraint is the water-filling policy in time domain. Forming the Lagrangian of constrained optimization problem in Eqs. (8.4)-(8.6), we can write J(R(h),\l,\2) = E[P(R(h),h)}-X1(E[R(h)]-R) + X2(E[(R(h)-R)2]-a2R), (8.7) where Ai and A 2 are the Lagrange multipliers. Taking derivative of Eq . (8.7) with respect to the variable R(h) and equating the derivative to zero, we get the necessary condition to be satisfied by the solution of optimization problem (8.4)-(8.6) nR{h) x In 2 -- A i + 2X2(R{h) -R) = 0. (8.8) ti Eq. (8.8) is a non-linear equation in terms of R(h). The solution of Eq . (8.8) in R(h) is the optimal transmission rate Ro(h, A i , A 2 ) and can be obtained using M A T H E M A T I C A as R0(h,Xl,X2) = —~ ( A i l n 2 + 2 ^ A 2 l n 2 - 2 A 2 x P L 2A 2 In 2 ( ln2 ) 2 x 2 " " " ^ hXn (8.9) 160 where P L [2] is the "ProductLog" function that returns the principal solution for w in equa-tion z = wexp(w). The cut-off value for the channel fading gain, hc below which the transmission should be suspended can be obtained from Eq. (8.9) for Rn(h, A i , A 2 ) = 0. Then hc can be written as hc = . l n 2 _ . . (8.10) A i + 2RX2 Similarly taking the derivative of Eq . (8.7) with respect to A i and A 2 and equating them to zero, we get two equations as follows: Jhc Ro(h, A i , X2)ph(h)dh - R = 0, (8.11) l c / Roi^X^X^-R ph(h)dh-a2R = 0. (8.12) Using Eq . (8.10), Eqs. (8.11) and (8.12), can be solved for A\ and A 2 for a given R, o\ and Ph{h). Since these equations cannot be solved analytically, numerical method is used. A s soon as the values of A\ and A 2 are known, the optimal transmission rate RQ for a given channel gain, h can be obtained from Eq. (8.9). In order to explore the shape of the dependency of the optimal transmission rate, RQ on gain h, curves are plotted in F ig . 8.2 for different values of transmission rate variances o\ with an average rate constraint of 2[Mbits/Sec]. We assume total system bandwidth, W of l [ M H z ] , noise power, cu2 of l [mW]. We use Rayleigh fading channel model for channel fading power gain, h which leads to the exponential P D F for Ph{h) i.e., [84] ph(h) = ^-exp(-h/h0) (8.13) tin where h0 is the average channel fading power gain. We can make two observations from Fig . 8.2. First, for a given average rate constraint R, the optimal transmission rate becomes steeper as the variance of the transmission rate decreases. This is due to the fact that lower bound on transmission rate variance does not allow differentiation of transmission rates depending on the channel quality. Second, the channel gain cut-off value hc below which transmission is suspended, increases i f a higher variation of transmission rate is allowed. This is again expected, as with the higher transmission rate variance, data can be delayed until relatively better channel quality is achieved. Theoretically there are two extreme cases. One is the infinite bound on transmission variance. In this case the optimal transmission policy approaches the water-filling policy in time domain. The other is the 161 0.5 1 I 1 I 1 1 I > °H 0 8 i — * .... < / 1 * ^ - . ) » - Tfc * * j f r ' " l i l * 1 j X * * * *y* * • "" / : i • o;=o.ooooi / : / : : : : ; ! ; / / • • • • • • • / : ; : ; ; : : 1 / i i i i i i > i i —i—I 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 10 Channel fading gain, h Figure 8.2: Channel gain versus transmission rate (R = 2[Mbits/Sec], W = l [ M H z ] and ho = 10). zero variance-bounded case which leads to the fixed rate transmission policy. The optimal transmission rate curve is almost constant with respect to the channel gain h as shown in the Fig . 8.2 for a variance bound of 0.0001. Using the values of A x and A 2 , the average transmit power can be obtained as follows: f+oo 2 p . . P a v = / ^.{2R0(hMM)/w _ i ) p h t h ) d h . ( 8.14) A c h The plotting of power versus variance for different average transmission rate constraints is shown in Fig . 8.3. This figure shows that as the variance of transmission rate increases, the transmit power decreases. This is obvious and due to exploiting fading diversity in time domain. A s the variance of transmission rate increases, data bits can experience better channel quality and thus the required transmit power decreases. Similarly there are two extreme cases for the average transmit power. The one is the water-filling power allocation corresponding to the water-filling policy at theoretically infinite variance bound and the other is the power corresponding to the fixed rate transmission policy at zero variance bound. Obviously, the water-filling power is the lowest average transmit power for a given 162 20 E 5 0 \ f-— S-... — - — - , Averag e transmi; ,sion rate= 4[Bits/Se( •JHz] ' v ... ...„ ^ Average K-1 transmis sion rate= 2[Bits/Sec/Hz) 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.05 Variance of the transmission rate, &L Figure 8.3: Variance versus transmit power (h0 — 10). average transmission rate. 8.3 Constant Rate Play-Out under the Receiver Buffer Outage Probability Constraint In this section we consider the constant rate "on-demand" video play-out under the receiver buffer outage constraint as an example of the application of our proposed V B R A problem. In the sequel we wi l l describe the system model for constant rate on-demand play-out process and define the buffer outage probability. Then we introduce two models, namely the JPDF model and the D A model in order to find the variance of the transmission rate for a given buffer outage probability during media play-out. A t the end, a numerical example is presented in order to show the performance of the proposed rate allocation scheme. 163 8.3.1 Overall description Let us consider a distributed mobile media streaming application where a receiving node downloads and plays out media from a power-limited transmitting node. Example of this type of media can be small size pre-stored video files on video phones. We assume that the media frames are encoded independently and each media frame has a length of F bits. The link between the two communicating nodes is time-varying. A s shown in Fig . 8.1, time is slotted slot by slot and indexed a s n = 1,2,3 - ••. There are T such slots in a duration of a video frame Tj. Let the interval between two consecutive frame retrievals be Tf [Sec]. Each slot has the duration of T b[Sec] and has a fixed number of channel accesses i.e., a fixed number of symbol transmissions. We assume that the fading gain hn over a slot with index n remains roughly constant and while being identically and independently distributed from one slot to the next. In other words, we use so called block fading model [85] which is a well accepted fading model for slowly moving environment. Therefore, the transmission rate and the power remain the same over a slot but they may change from one slot to the next. In each transmission slot, according to the channel gain hn, the transmitter chooses the transmission rate and adjusts the transmit power based on (8.2). Let the transmission rate in the n-th slot interval (n = 1,2, • • •) be denoted with Rn[Bits/Sec]. Since we assume the sequence of channel states hn is i . i .d distributed, then the same can be stated for the sequence of rates Rn. The receiver actions have two phases; the initial download phase and the simultaneous play-out and download phase. The initial download phase is always at the start of a media session and during this phase the receiver downloads bits in order to accumulate data in the play-out buffer. In this phase the media is not played out. We assume that the initial download phase has a duration of to [Sec] which is equivalent to I = t0/Tb transmission slots. After the initial downloading period, the receiver enters into the simultaneous play-out and download phase as it starts to play-out the media frame by frame. Specifically, at the end of each T slots i.e., every 7 / — TT 6 [Sec], a video frame of F bits is taken out of the receiver buffer and played out as shown in Fig . 8.1. Therefore, the required average transmission rate, R is equal to the number of bits per frame divided by the frame duration i.e., R = - ^ [ B i t s / S e c ] . (8.15) 164 At the end of a frame duration of 7/[Sec], i f the play-out frame is not available at the buffer, the receiver declares a play-out outage and starts the session from the beginning. The viewer wants to view the entire media content played out as smoothly as possible with minimal freezes and outages. For notational convenience, we use different time index k to denote the A>th frame take out time as shown in Fig . 8.1. The number of bits downloaded during the fc-th frame is Yk = (RkT+i + RkT+2 + • • • + RkT+r) Tb (8.16) for k = 1,2, — If the number of slots per frame duration, T is sufficiently large, according to the central limit theorem distribution of Yk approaches Gaussian for i.i .d distributed sequence of rates R4. Since no frame is taken out of the buffer during the initial download phase of I slots and a frame of F bits is taken out every Tf [Sec] after that, the receiver buffer occupancy . ^ [ B i t s ] at the end of frame index k = 1 ,2 ,3 , . . . can be expressed as f 1 Yi i f k < I Xk = I ^ f 1 t ~ . (8.17) \ ZLYi + lti+iiYi-F) * k > L For sufficiently long frame length T , random variable Xk also follows the Gaussian distri-bution. The design goal we analyze is the minimization of the probability of receiver buffer out-age during the play-out phase. The receiver buffer outage occurs when the receiver buffer occupancy, Xk is less than zero in any frame index k (k > I). In view of the variance-bounded rate allocation proposed in Section 8.2 and the receiver buffer model described above, we next demonstrate how to find the outage probability for a given variance of the transmission rate. 8.3.2 Joint P D F methodology for calculation of the receiver buffer outage probability The probability of receiver buffer outage during the transmission of a file of length Z frames for buffer dynamics given in (8.17) can be analytically expressed as P0 = l- P r o b . [ X / + 1 > 0, XI+2 > 0 , . . . , Xz > 0]. (8.18) 165 This can be further expressed in terms of the joint P D F p{XI+x, X I + 2 , . . . , Xz) of random variables XI+i, XI+2,..., Xz as />00 poo Po = l- •• p ( X I + l , X w , X z ) d X I + 1 d X I + 2 • • • dXz. (8.19) Jo Jo Now, based on Eq . (8.17) it can be concluded that the sequence of receiver buffer occu-pancies constitutes a Markov chain, i.e. that the joint P D F p(XI+i,XI+2,..., Xz) can be expressed as p(XI+1, XI+2, ...,XZ)= p{XI+1)p(XI+2\XI+1) • • -piXzlXz^). (8.20) As we have discussed previously, for a sufficiently large frame length, the buffer occupancy follows a Gaussian distribution. Furthermore, conditional distributions p(Xk\Xk-i), for I < k < Z follow the Gaussian distribution as well . Namely, p(XI+1) = MXl+1(TITbR,(I + l)T<jR) (8.21) p ( X f c | X f c _ ! ) = AfXk(Xk^,TaR),Kk<Z (8.22) where Sfz(Z, aR) is a Gaussian distribution of random variable Z with expectation Z and variance o\. Substituting (8.21) into (8.20) and then into (8.19), we can get the expression for the outage probability given in terms of parameters I, T,oR,R as poo poo Po = l - / • • • / ^fxI+A^TbR,(I + l)Ta2R)x^fX[+2(XI+uTal)x... Jo Jo xtfXz(Xz-i,Ta2R)dXI+1 •••dXz. (8.23) For sufficiently large T this approach wi l l give the precise values for the probability of outage in the receiver buffer. However, from a computational point of view, using Eq . (8.23) is equivalent to computing the cumulative distribution function of a multivariate Gaussian distribution that is computationally intensive for large dimensional distributions. 8.3.3 Diffusion approximation for calculation of the receiver buffer outage probability When the number of frames Z becomes large, the calculation of receiver buffer outage probability using the JPDF methodology is practically impossible due to its computational complexity. In this section we, therefore, introduce D A model which offers an upper bound 166 and relatively simple approximative evaluation of the buffer outage probability. Since se-quence of transmission rates {Rn} are independent random variables, the play-out buffer occupancy at time Tfk, Xk can be modelled as a random walk (RW). The simplest defini-tion of a R W is a sum of a number of i.i .d. random variables [86]. When the number of frames Z becomes very large, a more physical approach is applicable and based on passage from discrete R W to a diffusion process that requires the following assumptions [86] • The slot length approaches zero, i.e. Tb —> 0, and the time axis is described with con-tinuous variable t. Keep the frame length of 7} [Sec] fixed. The average increments RTb in buffer occupancy during a slot approach zero, and the buffer occupancy is also represented with a continuous variable. • The data retrieval process from the buffer is performed evenly throughout the frame of length T — Tf/Tb —> oo slots. Therefore F/T - » 0 bits is retrieved from the buffer in each slot. Let the P D F of buffer occupancy, x at time t, be b(x, t)22. Then according to the D A , the dynamics of the buffer can be expressed by to the diffusion equation as follows: [86] - = D m T ^ - vm— (8.24) dt ox dx where the coefficient D d i f f is known as the diffusion constant and given as 'diff _ c2 'diff D„ = g (8.25) and vm is the average rate of diffusion. The detailed derivation of diffusion equation can be found in [86]. The solution of the diffusion equation subject to the initial condition that the buffer is at x' with probability 1 at time t' i.e., b(x', t') — 8{x - x') can be written as [86] b(x,t\x',t') = . n 1 v x exp 1 ' } ^2n(o2R/Tb)(t-t>) (x - x' - vm(t - t')) (2a2R/Tb)(t - V) (8.26) It is important to mention that the solution is Gaussian at all time times which can also be shown from central limit theorem. 2 2 In order to avoid notational confusion, we denote the continuous random variable buffer occupancy and the time as x and t, respectively. 167 According to our transmission framework and buffer dynamics equation, i f the buffer occupancy falls below zero, there is an outage and the session starts from the beginning. So, the buffer occupancy process X which is a diffusion process has an absorbing point, at x — 0 [86]. A n absorbing boundary is a surface with the property that it removes from the system any random walker that comes into contact with it. Therefore, the diffusion Eq . (8.24) is to solved subject to the boundary condition b(0, t0) = 0. Using this boundary condition the solution can be written as [86] b(x, t\x0, t0) = bF(x, t\x0, t0) - bF(x, t\ - x0,t0) (8.27) where bF(x, t\x0, t0) is the P D F in the absence of boundaries for the buffer occupancy at time t of the buffer which is at x0 at time t0: bF(x,t\x0,t0) = x exp (x - Xof 2(oR/Tb)(t - to) (8.28) ^/2n(aR/Tb)(t - to) Note that based on our second assumption, rate of diffusion in the play-out phase is vm = 0, as the average incoming traffic in the buffer is completely offset by the retrieval process. The survival probability of the buffer or the probability that its occupancy does not goes below zero by time t, is denoted by S(t\x0, tQ) and is given by POO S(t\x0,t0) = / b(x,t\x0,t0)dx. Jo Using Eqs. (8.27) and (8.28), Eq . (8.29) can be written as (8.29) S(t\x0,t0) = erf x0 y(2a'R/Tb)(t-t0) where erf(-) is the "error function" and defined as (8.30) erf(2) = —=. \ exp (~u2) du. Vn Jo (8.31) It is important to mention that the survival probability is conditional probability conditioned on that the buffer occupancy is x0 at time t0. Since no frames are taken out of the buffer during the initial download period t0, the buffer occupancy at the end of time t0 can be approximated as free-space (free space means without any boundaries) diffusion equation solution with vm = R, as follows: [86] bo(x0,t0) ^2ir(oR/Tb)to x exp (so - Rt0)2 ' 2 (4 /T 6 ) tb (8.32) 168 Then the probability that the buffer w i l l have no outage during play-out period of t = Z7)[Sec] with an initial download period of £ 0 [Sec], Smg can be obtained by averaging the conditional survival probability, S{t\x0,t0) over the P D F of x0, b0(x0,t0) and can be expressed as r+oo S^(t\to)= / S(t\x0,t0)b0(xo,to)dx0. (8.33) Jo Note the above equation can only be used for sufficiently large initial download period. Using Eqs. (8.30) and (8.32) in Eq. (8.33), finally the outage probability with an initial download phase of £ 0 [Sec] , P°A(t\t0) can be expressed as (8.34) From Eq. (8.34) it is possible to find the variance of transmission rate for a given outage probability. Then the value of variance can be used to find the optimal transmission rate as described in Section 8.2. In order to compare two different methods described above, we plot outage probability versus variance in F ig . 8.4. For this figure we assume that a frame length of 50 slots and frame rate of 25 frames per second (fps) is used. Therefore, the frame duration is Tf = 1/25[Sec]. We assume an initial download phase of 1 slot, while the play-out phase (due to computational complexity associated with Eq . 8.23) is chosen to be only 2 slots. Rather low average transmission rate of R = 1 [kbits/sec] is chosen only as an illustration and to ensure that outage probabilities are on the order of 1 0 - 6 — 1 0 _ 1 . This figure shows that D A model offers slightly higher outage probability than the JPDF method for a given variance bound. This is due to the fact that the D A model assumes that data retrieval process is performed evenly throughout the frame length instead of taking out frame at the end of a frame duration. So, the outage probability provided by the D A is more stringent and the D A model offers the upper bound on outage probability. In practice, the buffer w i l l experience lower outage probability than the calculated one from D A model. 8.3.4 Results In this section we show some numerical examples in order to show the performance of our proposed scheme. Specifically we plot the optimal trade-offs between the transmit (x0 - Rt0y ' 2(aVTb)t0 x erf XQ J2(al/Tb)(t-t0) dx0. 1 6 9 - • * - Diffusion approximation Joint PDF method '6 I I I I I I I I I I 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Variance of transmission rate, cr? Figure 8.4: Buffer outage probability versus transmission rate variance (W = l [ M H z ] , and ho = 10). Average transmit power, Pay[mW] Figure 8.5: Buffer outage probability versus transmit power (W = l [ M H z ] , and ho = 10). 170 power and the buffer outage probability using D A . In our setting we have used a video length of 10000 frames. Therefore total duration of the video is 400[Sec]. We assume an initial download phase of 0.2[Sec]. The optimal power-outage trade-offs plotted in F ig . 8.5 shows that as the outage probability increases the required transmit power decreases. This is obvious as the higher outage probability allows to have higher transmission rate variance and consequently more fading diversity is obtained. It is also remarkable that allowing a very low buffer outage can save lot more transmit power. 8.4 Conclusions In this chapter we have proposed and studied a V B R A scheme which is useful for de-lay constraint communications e.g., streaming media play-out over time-varying wireless channels. In our proposed transmission framework the transmission rate is adjusted ac-cording to the wireless channel quality. A s such, the transmit power is minimized and an average rate constraint is satisfied. Also, the proposed rate-allocation guarantees a trans-mission rate variance constraint that in turn controls the buffer underflow during play-out. Our transmission framework is optimal if the frame length is sufficiently large for Gaussian approximation to hold. 171 Bibliography [78] A . J. Goldsmith and S.-G. Chua "Variable-rate variable-power M Q A M for fading channels," IEEE Trans. Commun., vol. 45, pp.1218-1230, Oct. 1997. [79] D . N . C . Tse and S. V. Hanly, "Multiple access fading channels-Part I: Polymatriod structure, optimal resource allocation and throughput capacities", IEEE Trans. Inform. Theory, vol. 44 no. 7, pp. 2796-2815, Nov. 1998. [80] A . J. Goldsmith and P. P. Varaiya "Capacity of Fading Channels with Channel Side Information," IEEE Trans. Inform. Theory, vol. 43, pp. 1986-1992, Nov. 1997. [81] Y. L i , A . Markopoulou, N . Bambos, and A . J. Apostolopoulos, "Joint Power/Playout Control Schemes for Media Streaming over Wireless Links," in Proc. IEEE Packet Video 2004, Irvine, C A , Dec. 2004. Also available online http://www.stanford.edu/ amarko/PAPERS/p v04.pdf. [82] H . Kobayashi, "Application of the diffusion to queueing networks I: equilibrium queue distribution," Jour. Ass. Computing Mach., vol. 21, pp. 316-328, Apr. 1974. [83] J. M . Cioffi, " A multicarrier premier," Nov. 1991. Also available in http://www.stanford.edu/group/cioffi/pdf/multicarrier.pdf. [84] M . K . Simon and M . - S . Alouini , "Digital Communications over Fading Channels," 2nd Edition, New Jersey : John Wiley & Sons, 2005. [85] E . Biglieri , G . Caire, and G . Taricco, "Limiting performance of block-fading channels with multiple antennas," IEEE Trans. Inform. Theory, vol. 47, pp. 1273-1289, M a y 2001. [86] G . H . Weiss, "Aspects and Applications of the Random Walk," North-Holland, Else-vier Science, 1994. 172 Chapter 9 Conclusion In this dissertation, our contribution is the design of innovative scheduling schemes via a cross-layer design approach that jointly considers the time-varying nature of wireless channels as well as the required QoS parameters of different services. Specifically, this dissertation makes the following four major contributions. First, we have developed modulation-assisted two-user opportunistic scheduling schemes. Specifically, in Chapter 2, we have proposed a power-controlled hierarchical modulation-assisted T B S . The information access probability and some radio link layer performance of the proposed power-controlled T B S scheme have been analyzed in this chapter. Pre-sented numerical results show that the power-controlled hierarchical modulation-assisted T B S provides lower average buffer occupancy (i.e., queuing delay) and loss probability for the packets at the transmission buffer, at the expense of transmit power, compared with the classical SBS scheme. The required additional power decreases as the number of users increases in the system. We have compared our hierarchical scheme with a uni-form constellation-based mini-slotted scheme. This mini-slotted scheme provides simi-lar higher link layer performance as the hierarchical scheme but requires higher transmit power. Since the power-controlled modulation-assisted T B S includes the second best user in each transmission, it requires a certain amount of power compared with the classical SBS scheme. Therefore in Chapter 3, we have proposed a rate adaptive hierarchical modulation-assisted T B S scheme. The proposed rate adaptive modulation-assisted T B S scheme does not include the second best user in each transmission. Instead, it proposes to transmit in-formation to the second best user opportunistically by joint consideration of the channel qualities of the users. We have evaluated the information access probability and system S E in closed-form for an i.i.d fading environment in Chapter 3. Numerical results presented in this chapter show that the rate adaptive modulation-assisted T B S scheme almost dou-bles the frequency of information access for users without any degradation of overall SE , compared with the classical SBS . In Chapter 4, we have derived expressions for the SE of 173 the users for an i.n.d. fading environment. Using this expression, we have compares the fairness of the rate adaptive TBS scheme with that of the classical single user scheduling schemes. From a numerical example, we have observed that the rate adaptive TBS scheme increases the system's fairness without any degradation of system SE, compared with the classical SBS. In order to further improve system fairness we have proposed a rate adaptive HTS. The novelty of the HTS is that it significantly improves the system's fairness without any degradation of system SE compared with the SBS scheme; it cannot, however, achieve system fairness as good as the equivalent PFS, which suffers from a certain degradation of SE. In Chapter 5, we have analyzed some link layer performances; delay statistics and buffer distribution of the proposed rate adaptive TBS and HTS schemes via queuing analy-sis. Presented numerical results in this chapter show that TBS can significantly reduce the queuing delay of the packets at the transmission buffer. Interestingly, this improved delay performance is gained without any SE cost. For an i.n.d. fading environment, the HTS scheme significantly improves the delay performance of the far-end user, compared with that of the TBS and SBS schemes. It also achieves a delay performance that is close to that of the equivalent PFS (or NSS) scheme for the far-end user. However, the NSS scheme significantly increases the queuing delay of the packets for the near-end user. Second, we have developed, in Chapter 6, an adaptive scheduling protocol for multi-resolution image/video data transmission over time-varying channels. The proposed scheme not only takes advantage of hierarchical constellations but also uses an adaptive scheduling protocol to give different transmission priorities to different resolution levels. A Markov chain model of this protocol has led to closed-form expressions for the average packet loss rate and the average transmission rate. Numerical results show that the proposed scheme can control the relative transmission priorities in terms of transmission rate as well as loss rate of different resolution levels by varying the asymmetry of the constellation and the maximum number of allowed retransmissions. In Chapter 7, we have also proposed an integrated packet scheduling and unequal error protection strategy for real time packetized multi-resolution (layered) image/video data transmission over correlated channels. In or-der to the select transmit power level, a constellation priority parameter and the packets from different resolution levels, the proposed system considers the timeliness requirements and the importance levels of different packets as well as time-varying channel property. A joint optimization of the proposed transmission framework has been accomplished by for-174 mulating it as a M D P . The proposed hierarchical scheme has also been compared with an optimized scheme that uses uniform signal constellation. The latter scheme requires higher average transmit power than the hierarchical scheme in order to maintain the same average distortion of the received image/video data. Third, in Chapter 7 we have developed, link adaptation algorithms for a multicar-rier system for generalized delay constrained communications over time-varying chan-nels. Specifically, we have proposed two different transmission frameworks for delay-constrained O F D M communication. One is the bit-loading framework, which minimizes the aggregate B E R of a constant power O F D M system while meeting a delay constraint of the packets at the transmission buffer. The other is the bit- and power- loading algorithm, which seeks to minimize the total average transmit power while maintaining a target de-lay constraint. Optimal loading policies in both cases are obtained using L P methodology formulating them as the M D P . Since finding the optimal policies and implementing them are highly complex in reality, i f not impossible, we also explore a suboptimal loading algo-rithm based on an equivalent single carrier optimal loading scheme and a greedy approach. Since the suboptimal loading algorithm requires only finding and storing the optimal policy of the equivalent single carrier case with a fewer number of states, it is simple to realize it practically. The selected numerical results show that the suboptimal loading scheme in both cases attains a tradeoff performance very close to the optimal one. In Chapter 7, we have also explored the effect of correlation between the subcarriers' fading gains of a M C M system on its bit- and power-loading in delay-constrained and no delay-constrained communications. For the no delay-constrained case, the correlation between subcarrier fading gains does not have any influence on the loading policy. Therefore, the average total transmit power is not influenced by the correlation between the subcarriers' fading gains. For discrete rate adaptation as well as discrete channel gain variation, the optimal loading policies for both cases are obtained through a greedy allocation. Assuming discrete rate adaptation and discrete channel gain variation, numerical examples have been demon-strated for different degrees of correlation. The results show that the required transmit power in the hard delay-constrained case increases as the correlation increases. However, the degree of correlation does not have any significant effect on the required transmit power in the no delay-constrained case. Although we have considered only correlation among the carriers' fading gains, it is worthy to mention that time correlation does not influence our 175 conclusions. Fourth, in Chapter 8 we have devised a novel V B R A scheme for delay-constrained communications, e.g., media streaming over time-varying channels. In this chapter, we studied a V B R A problem that is useful for streaming media play-out over time-varying wireless channels. In our proposed transmission framework, the transmission rate is ad-justed according to the wireless channel quality; the transmit power is minimized and an average rate constraint is satisfied. Also, the proposed rate-allocation guarantees a trans-mission rate variance constraint that in turn controls the buffer underflow during play-out. Our transmission framework is optimal if the frame length is sufficiently large for Gaussian approximation to hold. 9.1 Future Research Challenges Our contributions in this dissertation, have not only provided innovative scheduling algo-rithms for time-varying wireless links, but also opened up exciting research avenues for future investigation. These research challenges are described below. 9.1.1 Opportunistic subcarrier allocation for OFDM-based system In our proposed T B S schemes, we considered a single-carrier system. However, next gen-eration, wireless networks, e.g., W i M A X , w i l l use O F D M A as a multiple access technique. With hierarchical modulation, one subcarrier of an O F D M A system can be shared among more than one user. Therefore, it is interesting to design and analyze the performance of an OFDMA-based system with opportunistic subcarrier allocations in conjunction with hierarchical transmission. We conjecture that since the hierarchical transmission scheme allows an O F D M subcarrier to be shared among more than one user it can achieve better system performance. 9.1.2 Designing multiple-best user scheduling scheme In our thesis, we have considered multiple best user scheduling scheme using power con-trolled hierarchical constellations. A s more users are included in the system, required aver-age transmit power increases. The rate adaptive modulation assisted T B S scheme does not 176 degrade overall SE but improves queuing delay performance. Further delay improvement can be obtained by including third best user in the system cleverly. However, design-ing such scheme with rate adaptive hierarchical modulations requires complicated design. Specifically, three dimensional joint P D F of C N R s of the first, second and best users needs to be considered. Further investigation in this direction can be interesting but challenging. 9.1.3 Rate adaptation for hybrid ARQ-based system for real-time multi-resolution data transmission Although we have used hierarchical modulation for unequal error protection for multi-resolution image/video data transmission over time-varying channels, our transmission frameworks in this regard can be generalized for any unequal error protection system. Specifically, it is interesting to design an adaptive and optimized scheme for real-time multi-resolution with a hybrid A R Q scheme. In this case, the scheme should change the coding rate for the current packets based on the timeliness of the packets from different resolution levels and the dynamics of time-varying channels. 9.1.4 Hybr id policy for media streaming over fading channels Our proposed V B R A allocation schemes for media streaming over time varying channels is optimal among a set of policies in which there is only knowledge of the channel infor-mation and no knowledge of the receiver buffer occupancy. Finding a policy with buffer knowledge is indeed a non-stationary policy. Implementation of a non-stationary policy is restricted by its complexity. Developing a hybrid policy based on our V B R A scheme and the partial receiver's buffer knowledge is challenging. Obviously, without full knowledge of the buffer, this policy would be suboptimal. However, having partial buffer knowledge can further improve system performance. 9.1.5 Effect of imperfect channel state and slow adaptation for time channels A l l of the adaptive schemes proposed in this dissertation assume that the channel infor-mation is perfectly known at the transmitter. However, in practice the channel state in-177 formation may be outdated or only known partially, e.g., in the form of acknowledgment signals for the ARQ system. Studying the performance of our proposed scheme with an imperfect channel state is another exciting future research direction. It is obvious that the performance of our proposed scheme will degrade with an imperfect channel state at the transmitter. Based on such future work, robust adaptive schemes can be designed in these contexts. Channel adaptive schemes also require a great amount of overhead, which in turn reduces the effective data transmission rate, especially for multiuser, multi-antenna, and multicarrier transmission systems. Therefore, researchers are attempting to develop adap-tive schemes with limited feedback. Examples of these recently developed schemes in-clude blind adaptive modulation schemes and binary feedback-based adaptive modulation schemes. Therefore, it is very important to design adaptive transmission schemes that adapt the transmission parameters according to channel statistics, e.g., average channel quality or amount of fading, instead of instantaneous channel quality. In future research, it would be very practical to extend our adaptive schemes for the more general multiuser, O F D M and MIMO systems. 178 Appendices Appendix A In this appendix, we derived the integral in Eq. (3.13). Using the expression of the joint 2 P D F in Eq. (3.3), the integral Pgwgm(9(i),9(2)) dg{2)dgm in Eq . (3.13) can be evaluated as follows: P9W9W(9{i),9{2))dg{2)dg{i) 7 r 2 , s + 1 K(K - 1) r%,s+i [9 J-y?. J-ti 9l exp (-g(\)lgo) exp (-g(2)/go) x [ l - exp (-g(2)/go)\ dg^)dgw Hr.s+l rs 7r%+1 gw K t K _ X) * 2 / K _ 2 fc=0 g 5 E( ; I t - ^ H W a O xexp (-(fc + l)g{2)/go) dg(2)dgm K(K-l)Kt(K:\^fu'^mM fc=0 V ^ / . 7r,« X K - 2 9(1) exp ( - ( f c + l)y(2)/^o) ^(2) - 1) - 2 N ( - l ) f c [exp(-(fc + l)7rV5o) ^ fc+i V fc / fc=0 x 7 x [exp ( - 7 r , s / p o ) - exp ( - 7 r , s + i M ) ] exp ( - ( f c + 2 ) 7 2 s / g 0 ) - exp ( - ( f c + 2 ) 7 2 s + 1 / g o ) fc + 2 (9.1) 179 Similarly using the expression of the joint P D F in Eq. (3.3), the integral hi. his p9W9(2) L72r , s + 1 flT,s Pg,1)gm(9(ih9(2)) dg(2)dg{i) in Eq . (3.18) can be evaluated as: s+1 f1r,s Psd)ff(2) (9m,9(2))dg(2)dg(i), Tr,s — Tr, $ = / + / ^ ^ N 2 ^ e x P (-9(1)/9o) e x P (-9(2)/9o) I 1 - exp (-£( 2)/tfo)] T r , s T r , s \i/0 / xexp (-(fc + 1)9(2)/go) dg{1)dg{2) Switching the order of the summation and the integrals, we can write Eq . nls+x nls his J-rL nls / P9W9(2)(9(i),g(2))dg(2)dg(i) < » ) 2 fed x / exp (-(k + l)g2/go)dg2 K-2 (9.2) = [exp (-llJgo) ~ exp ( - 7 r 2 s + i / 5 o ) ] x } ^ I x ( - l ) f c [exp (-(k + lhl/go) - exp ( - ( * + iKjgo)} • (9.3) 180 Appendix B /t2 rx P9j(x) j pg*m(z)dzdx. (9.4) For Rayleigh fading channel using Eqs. (4.1), (4.2) and (4.7), the integral in Eq . (9.4) can be evaluated as follows: [43] intuh) = f2 ^ exp (-JO f it p^z) n p ^ z ) d x Jh 9j V 9j/ JO fc=1)fc^j m=l,m#fc,j = 1 / -^exp ( — ^ - ) sign(r')exp (—rx) dx Jtl 9j V 9iJ f^K V 1 •>eT!< (9.5) sign(r') ^ ( r ' ^ + 1) 9 i ) V & where the notations r' has been adopted from the [43] and the references there in. More specifically, Tf- is the set obtained by expanding the product nn=i,n^j [}- e x P ( - £ ) ) then by taking the natural logarithm of each term, and sign(r) is the corresponding sign of each term in the expansion. 181 Integral:/|(ti,t2,*3) = / Pg , (*) / : Jo pg*w(z)dzdx. (9.6) Similarly for Rayleigh fading channel using Eqs. (4.1), (4.2) and (4.7) in Eq . (9.6), the integral can be evaluated in closed-form as follows: liMM) = £ l e x p ( - | ) j ( % s . , ( z ) ^ -cxp(-^-)dx) I ^ P9k(z) Yl Pgi(z)dz 9j \ 9iJ J \Jo k=lik^j i=i&kj J rt2 A 9j = l e x p l - ^ - e x p ^ - -ti\ f h — - e x p — -9jJ V 9j = exp K n ^ f c(*s) K f II ( l - e x p 9k Pt3 rx Integral:/^, i 2 , t 3 ) = / P9j{x) pg*{z)dzdx. Jti Jt3 Similarly, the integral in Eq . (9.8) can be evaluated as follows: • (9.7) (9.8) *2 Il(t\,h,h) = ^ pg.(x) pg-m(z)dzdx = P^(fQ Pa'w(z)dz ~ Jq P9'w(z)d^jdx = / p,M)( n = / r - e x p ( - - ) x s i g n ( r ) [^P {-rx) - exp {-rt3)} dx Jti 93 9j T(_TK sign(r) ft2 9i Jtl 1 - «p | - s ) ) - ( 1 - «p ( - s ) n ' f a - E T 6 T f J J = Y Si§n(T) f{r93 + V A _ exp(_^)exp(_rt3) V 9j J 9j dx 1 9j (rg, +1) ( e x p ( - ^ - ) - exp ( -^ - ) J e x p ( - r i 3 ) V 9j gj J 9j (9.9) 182 rt<l rx rz I n t e g r a l : / i ( t i , t 2 , * 3 ) = / / P9J(Z) Pgi)gfa(.x>y)dydzdx- 1 (9-10) For Rayleigh fading channel using Eqs. (4.1) and (4.14), the integral in Eq . (9.10) can be evaluated as: nx rz K K K PaM I 52 52 PM II P9m(y)dydzdx nx K „2 K K PQAz) 52 PM 52 PM n P9m(y)dydzdx m=l,m^j,k,l -TZ)dzdx -TZ) dzdx 52 sign(r)exp /*2 ^ /-X • ' ' i T e r * J t 3 V ^ y irngk + g~k + g~j) [ \ Mi ) -exp f _ ( ^ + ^ + ^ 2 \ l 183
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Some cross-layer design and performance issues in wireless...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Some cross-layer design and performance issues in wireless networks Hossain, Md. Jahangir 2007
pdf
Page Metadata
Item Metadata
Title | Some cross-layer design and performance issues in wireless networks |
Creator |
Hossain, Md. Jahangir |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | Present and future generation wireless systems are designed to support a wide variety of services, including video conferencing, media streaming, Internet access, email transfer, remote file access and web-browsing. Different applications have different traffic characteristics and quality of service (QoS) requirements. These QoS parameters include delay constraint, packet loss rate (PLR) and packet error rate (PER) requirement. For example, depending on the throughput or delay requirements of the services, wireless data services have already been classified as guaranteed or best-effort services. Mobile wireless links are time-varying in nature and error prone. In addition, communication resources, e.g., transmit power and bandwidth, are scarce. Through a cross-layer design approach, these inherent quality parameters of different services can facilitate efficient use of limited communication resources. In particular, the relative delay tolerance of data applications, in conjunction with the bursty activity patterns and time-varying nature of the wireless channels, opens up the possibility of scheduling transmissions to efficiently allocate limited wireless communication resources. The main contribution of this dissertation is the design of innovative scheduling schemes through cross-layer design approach that jointly considers the time-varying nature of wireless channels as well as the required QoS parameters of different services. This dissertation makes four major contributions, as follows. First, we develop modulation-assisted two-user opportunistic scheduling schemes. The novelty of the proposed schemes is improved delay performance and fairness for the serviced users in wireless networks without degradation of the system spectral efficiency (SE), compared with the classical single best user scheduling (SBS) scheme. Second, we develop an adaptive scheduling protocol for multi-resolution image/video data transmission over time-varying channels. The protocol is optimized for real-time multi-resolution data transmission in order to maintain a given quality of the received multi-resolution data. Third, we devise a novel variance-bounded rate adaptation (VBRA) scheme for delay-constrained communications. We explore an application of the proposed VBRA scheme for media streaming over time-varying channels in order to minimize the transmit power while maintaining a low play-out buffer outage probability. Fourth, we develop link adaptation algorithms for a multicarrier system for generalized delay-constrained communication over time-varying channels. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-02-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. |
DOI | 10.14288/1.0100568 |
URI | http://hdl.handle.net/2429/31332 |
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 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2007-317860.pdf [ 8.66MB ]
- Metadata
- JSON: 831-1.0100568.json
- JSON-LD: 831-1.0100568-ld.json
- RDF/XML (Pretty): 831-1.0100568-rdf.xml
- RDF/JSON: 831-1.0100568-rdf.json
- Turtle: 831-1.0100568-turtle.txt
- N-Triples: 831-1.0100568-rdf-ntriples.txt
- Original Record: 831-1.0100568-source.json
- Full Text
- 831-1.0100568-fulltext.txt
- Citation
- 831-1.0100568.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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100568/manifest