Question? Leave a message!




Multi-User Capacity and Opportunistic Communication

Multi-User Capacity and Opportunistic Communication 40
MultiUser Capacity and Opportunistic Communication Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 1Outline  Reference: Chapter 6 (and 5): Tse/Viswanath  Multiple access (or multiuser) channels are different from pt pt channels  New concepts/techniques: successive interference cancellation (SIC), superposition coding, multiuser diversity.  AWGN multiuser uplink: CDMA + SIC  AWGN multiuser downlink: superpositioncoding (CDMA like) + SIC  Fast Fading: ability to track channel at sender (CSI) + opportunistic more important due to multiuser diversity  Gains over CSIR for full range of SNR (not just low SNR)  Opportunistic beamforming, IS856 (1x EVDO) etc… Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 2Ptpt channel Capacity  A slow fading channel is a source of unreliability: very poor outage capacity. Diversity is needed.  A fast fading channel with only receiver CSI has a capacity close to that of the AWGN channel. Delay is long compared to channel coherence time.  A fast fading channel with full CSI can have a capacity greater than that of the AWGN channel: fading now provides more opportunities for performance boost.  The idea of opportunistic communication is even more powerful in multiuser situations. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 3Fundamental Feature of Wireless Channels: Time Variation  multipath fading  largescale channel variations  timevarying interference Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 4Traditional Approach to (Multiuser) Wireless System Design Compensates for channel fluctuations. I.e. treats a multiuser channel like a set of disjoint singleuser (or ptpt) channels. Examples: interference averaging; nearfar power control, fixed coding/modulation rates Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 5Example: CDMA Systems Two main compensating mechanisms: 1. Channel diversity:  frequency diversity via Rake combining  macrodiversity via soft handoff  transmit/receive antenna diversity 2. Interference management:  power control  interference averaging Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 6What Drives this Approach Main application is voice, with very tight latency requirements. Needs a consistent channel. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 7Opportunistic Communication: A Different View Transmit more when and where the channel is good. Exploits fading to achieve higher longterm throughput, but no guarantee that the "channel is always there". Appropriate for data with nonrealtime latency requirements (file downloads, video streaming). Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 8Recall: PointtoPoint Fading Channels Capacityachieving strategy is waterfilling over time. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 9Variable rate over time: Target BER  In the fixedrate scheme, there is only one code spanning across many coherence periods.  In the variablerate scheme, different codes (distinguished by difference shades) are used depending on the channel quality at that time.  For example, the code in white is a lowrate code used only when the channel is weak. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 10Adaptive Modln/Coding vs Shannon Limit  Optionally turbocodes or LDPC codes can be used instead of simple block/convolutional codes in these schemes Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 11Performance over PtPt Rayleigh Channel Not much bangforbuck for going to CSI from CSIR high SNR Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 12Performance: Low SNR At low SNR, capacity can be greater (w/ CSI) when there is fading. Flip side: harder to get CSI at low SNR  Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 13Hitting the Peaks Low SNR: Hard in Practice (High SNR) Fixed power almost as good as waterfilling (Low SNR) Waterfilling helps, But CSI harder users pay delay penalties At low SNR, one can transmit only when the channel is at its peak. Primarily a power gain. In practice, hard to realize such gains due to difficulty in tracking the channel when transmitting so infrequently. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 14Multiuser Opportunistic Communication Multiple users offer new diversity modes, just like time or frequency or MIMO channels Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 15Performance AWGN Increase in spectral efficiency with number of user at all SNR’s, not just low SNR Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 16Multiuser w/ CSI: Low SNR case Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 17Multiuser Diversity Total average SNR = 0 dB.  In a large system with users fading independently, there is likely to be a user with a very good channel at any time.  Longterm total throughput can be maximized by always serving the user with the strongest channel. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 18Sum Capacity: AWGN vs Ricean vs Rayleigh  Multiuser diversity gain for Rayleigh and Ricean channels ( = 5); KP/N0 = 0 dB.  Note: Ricean is less random than Rayleigh and has lesser sum capacity Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 19Multiuser Diversity: A More Insightful Look  Independent fading makes it likely that users peak at different times.  In a wideband system with many users, each user operates at low average SNR, effectively accessing the channel only when it is near its peak.  In the downlink, channel tracking can be done via a strong pilot amortized between all users. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 20Theory Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 212user uplink AWGN: Capacity Region  Capacity region C: is the set of all pairs (R1,R2) such that simultaneously user 1 and 2 can reliably communicate at rate R1 and R2.  Tradeoff: if user 1 wants to communicate at higher rate: user 2 may need to lower rate  Eg: OFDM: vary allocation of sub carriers or slots per user  Capacity region: optimal tradeoff for any MAC scheme  Performance measures:  Symmetric capacity: User k has an average power  Sum capacity: constraint of P Joules/symbol (with k k = 1, 2) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 22Uplink AWGN Channel Capacity Region  Satisfies three constraints: R1, R2, and (R1+R2)  Without the third constraint, the capacity region would have been a rectangle, …  … and both users could simultaneously transmit at the pointto point capacity as if the other user did not exist. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 23Uplink AWGN Capacity successive cancellation: cancel 1 before 2 optimal conventional cancel 2 before 1 decoding Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 24AWGN Multiuser Capacity SIC Decoder  User 1 can achieve its singleuser bound while at the same time user 2 can get a non zero rate:  Each user encodes its data using a capacityachieving AWGN channel code.  2stage decoding:  1. Decodes the data of user 2, treating the signal from user 1 as Gaussian interference.  2. Once the receiver decodes the data of user 2, it can reconstruct user 2’s signal and subtract it from the aggregate received signal.  Then decode the data of user 1.  Only the background Gaussian noise left in the system, the maximum rate user 1 can transmit at is its singleuser bound log (1 + P /N ). 1 0  This receiver is called a successive interference cancellation (SIC) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 25SIC vs Conventional CDMA/Orthogonal Schemes  Minimizes transmit power to achieve target rates of two users  In interference limited scenarios, increases system capacity  Conventional CDMA is suboptimal because it controls power of strong users downwards to handle the nearfar problem  = such high SNR users cannot transmit at high rates  They have to depress their SNRs and transmit at lower rates  With SIC: nearfar is not a problem, but an advantage  Less apparent for voice, but definitely for data  Orthogonal: allocates a fraction α of the degrees of freedom to user 1 and the rest (1 − α) to user 2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 26Conventional CDMA vs Capacity 20 dB power difference between 2 users Successive cancellation allows the weak user to have a good rate without lowering the power of the strong user. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 27Waterfilling vs Channel Inversion  Waterfilling and rate adaptation (across users) maximize long term throughput but incur significant delay.  Channel inversion in downlink (“perfect” power control in CDMA jargon) is powerinefficient but maintains the same data rate (received SNR) at all channel states. Huge power penalty during deep fades. Peak power constraints = method cannot work.  Channel inversion achieves a delaylimited capacity. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 28Orthogonal vs Capacity 20 dB power difference between 2 users orthogonal Orthogonal achieves maximum throughput (intersection point above) but may not be fair. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 29General Kuser Uplink AWGN Capacity K  Kuser capacity region is described by 2 − 1 constraints, one for each possible nonempty subset S of users:  SumCapacity:  Equal power case:  Symmetric capacity:  Eg: OFDMA w/ allocation of 1/K degrees of freedom per user better than CDMA w/ conventional receivers. (see CDMA limits next slide)  Sum capacity is unbounded as the number of users grow. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 30Example: CDMA Uplink Capacity (I/f limited)  Single cell with K users (conventional, i.e. nonSIC receiver):  Treat interference as additive noise  Capacity per user  Cell capacity (interferencelimited) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 31CDMA Uplink Capacity Example (continued)  If outofcell interference is a fraction f of incell interference: Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 32Downlink AWGN Channel: 2users  The transmit signal x m has an average power constraint of P Joules/symbol.  Difference from the uplink of this overall constraint: there the power restrictions are separate for the signals of each user.  The users separately decode their data using the signals they receive.  Single user bounds: Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 33Symmetric 2user downlink AWGN case  The capacity region of the downlink with two users having symmetric AWGN channels, i.e., h1 = h2.  This upper bound on R can be attained by using all the power k and degrees of freedom to communicate to user k (with the other user getting zero rate).  No SIC here… Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 34Superposition Coding: facilitating SIC Base station superposes the signals of users, like CDMA SIC receiver R2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 35Superposition Decoding  Superposition decoding example. The transmitted constellation point of user 1 is decoded first, followed by decoding of the constellation point of user 2. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 36Downlink Capacity: w/ superposition coding superposition coding 20 dB gain difference between 2 users orthogonal The boundary of rate pairs (in bits/s/Hz) achievable by superposition coding (solid line) and orthogonal schemes (dashed line) for the two user asymmetric downlink 2 AWGN channel with the user SNRs equal to 0 and 20 dB (i.e., Ph /N = 1 1 0 2 and Ph /N = 100). Eg: at R1 = 0.9 b/s/Hz, superposition coding gives R2 = 3b/s/Hz 2 0 vs orthogonal of 1 b/s/Hz. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 37Uplink AWGN Capacity: Summary Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 38Downlink AWGN: Summary Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 39SIC Implementation Issues  Complexity scaling with the number of users:  At mobile node complexity scales if more users  Can group users by SNR bands and do superposition coding within the group  Error propagation: degrades error prob by at most K ( users). Compensate w/ stronger code.  Imperfect channel estimates:  Stronger user: better channel estimates. Effect does not grow…  Analogtodigital quantization error:  Implementation constraint with asymmetric signals Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 40Uplink Fading Channel: Summary Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 41Reference: Uplink Fading Channel  K users:  Outage Probability:  Individual outage: ε = overall outage prob (orthogonal):  In general: Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 42Reference: Multiuser SlowFading Outage Capacity (2user example, contd) Note: worse than ptpt  Plot of the symmetric outage capacity of the 2user Rayleigh slow fading uplink as compared to C, the corresponding performance of a pointtopoint Rayleigh slow fading channel. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 43Reference: Uplink: Fast Fading, CSIR  Without CSI (i.e channel state information at Tx) , fading always hurts as in point topoint case…  With large number of users, the penalty vanishes, but no improvement over ptpt Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 44Reference: Fast Fading uplink, Orthogonal  … which is strictly less than the sum capacity of the uplink fading channel for K ≥ 2.  In particular, the penalty due to fading persists even when there is a large number of users. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 45Multiuser FastFading w/ CSI  Central interest case  Dynamically allocate powers to users as a function of CSI  To achieve the maximum sum rate, we can use orthogonal multiple access…  this means that the codes designed for the pointtopoint AWGN channel can be used w/ variable rate coding…  Contrast this with the case when only the receiver has CSI (i.e. CSIR), where orthogonal multiple access is strictly suboptimal for fading channels. (see previous slide)  Note that, this argument on the optimality of orthogonal multiple access holds regardless of whether the users have symmetric fading statistics. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 46Multiusers: diversity gain, not d.f gain  Having multiple users does not provide additional degrees of freedom in the system:  the users are just sharing the time/frequency degrees of freedom already existing in the channel.  Thus, the optimal power allocation problem should really be thought of as how to partition the total resource (power) across the time/frequency degrees of freedom …  … and how to share the resource across the users in each of those degrees of freedom.  The above solution says that from the point of view of maximizing the sum capacity, ..  … the optimal sharing is just to allocate all the power to the user with the strongest channel on that degree of freedom. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 47Applications Fairness/Scheduling Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 48Application to 1x EVDO’s DownLink  Multiuser diversity provides a systemwide benefit.  Challenge is to share the benefit among the users in a fair way. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 49Symmetric Users Serving the best user at each time is also fair in terms of long term throughputs. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 50Asymmetric Users: Hitting the Peaks Want to serve each user when it is at its peak. A peak should be defined with respect to the latency timescale t of the application to provide shortterm fairness. c Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 51Proportional Fair Scheduler Schedule the user with the highest ratio R = current requested rate of user k k T = average thruput of user k in the past t time slots. k c Like a dynamic priority scheme Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 52Performance Fixed environment: 2Hz Rician fading with E /E =5. fixed scattered Low mobility environment: 3 km/hr, Rayleigh fading High mobility environment: 120 km/hr, Rayleigh fading Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 53Channel Dynamics Channel varies faster and has more dynamic range in mobile environments. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 54Why No Gain with High Mobility 3 km/hr 30 km/hr 120 km/hr Can only predict the average of the channel fluctuations, not the instantaneous values. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 55Throughput of Scheduler: Asymmetric Users (Jalali, Padovani and Pankaj 2000) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 56Inducing Randomness  Scheduling algorithm exploits the naturegiven channel fluctuations by hitting the peaks.  If there are not enough fluctuations, why not purposely induce them (eg: in fixed situation) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 57Dumb Antennas The information bearing signal at each of the transmit antenna is multiplied by a random complex gains. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 58Slow Fading Environment: Before Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 59After Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 60Slow Fading: Opportunistic Beamforming  Dumb antennas create a beam in random timevarying direction.  In a large system, there is likely to be a user near the beam at any one time.  By transmitting to that user, close to true beamforming performance is achieved. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 61Opportunistic Beamforming: Slow Fading Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 62Opportunistic Beamforming: Fast Fading Improves performance in fast fading Rician environments by spreading the fading distribution. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 63Overall Performance Improvement Mobile environment: 3 km/hr, Rayleigh fading Fixed environment: 2Hz Rician fading with E /E =5. fixed scattered Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 64Smart vs Dumb Antennas  Spacetime codes improve reliability of pointtopoint links but reduce multiuser diversity gain.  Dumb (random beamforming) antennas add fluctuations to pointtopoint links but increases multiuser diversity gains. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 65Cellular System: Opportunistic Nulling  In a cellular systems, users are scheduled when their channel is strong and the interference from adjacent basestations is weak.  Multiuser diversity allows interference avoidance.  Dumb antennas provides opportunistic nulling for users in other cells (a.k.a interference diversity).  Particularly important in interferencelimited systems with no soft handoff. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 66Conventional vs Opportunistic Communication Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 67Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 68Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 69Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 70Extra Slides: not covered… Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 71Uplink and Downlink Capacity  CDMA and OFDM are specific multiple access schemes.  But information theory tells us what is the capacity of the uplink and downlink channels and the optimal multiple access schemes. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 72Example of Rate Adaptation: 1xEVDO Downlink Multiple access is TDMA via scheduling. Each user is ratecontrolled rather than powercontrolled. (But no waterfilling: fixed transmit power, different code/modulation rates.) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 73Rate Control: Adaptive Modulation/Coding Mobile measures the channel based on the pilot and predicts the SINR to request a rate. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 74SINR Prediction Uncertainty 30 km/hr 120 km/hr 3 km/hr accurate prediction conservative accurate prediction of instantaneous prediction of of average SINR for SINR. SINR. a fast fading channel Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 75Incremental ARQ  A conservative prediction leads to a lower requested rate.  At such rates, data is repeated over multiple slots.  If channel is better than predicted, the number of repeated slots may be an overkill.  This inefficiency can be reduced by an incremental ARQ protocol.  The receiver can stop transmission when it has enough information to decode.  Incremental ARQ also reduces the power control accuracy requirement in the reverse link in Rev A. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 76