Date post: | 16-Apr-2018 |
Category: |
Documents |
Upload: | trinhkhuong |
View: | 219 times |
Download: | 5 times |
Scheduling and HARQScheduling and HARQSeminar LTE: Der Mobilfunk der ZukunftSeminar LTE: Der Mobilfunk der Zukunft
Tobias Schrage
University Erlangen-NürnbergChair of Mobile Communications
January 13, 2010
OutlineOutline
1 Scheduling
2 HARQ
3 Literature
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ1 / 311 / 31
SchedulingScheduling
Why Scheduling?Why Scheduling?
SituationIn a LTE cell several UEs are logged in and each one wants toaccess the channel for data transfer. How can the eNodeBdetermine which one should be served?
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ2 / 312 / 31
SchedulingScheduling BasicsBasics
Scheduling BasicsScheduling Basics
What can be scheduled?
Space
Bandwidth
Code
Transmit Power
What has to be considered?
Maximum Delay
Fairness
Problem of “User Starvation”
Efficiency (overall throughput)
Overhead
Some of these aspects are contradictory
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ3 / 313 / 31
SchedulingScheduling BasicsBasics
Scheduling BasicsScheduling Basics
What can be scheduled?
Space
Bandwidth
Code
Transmit Power
What has to be considered?
Maximum Delay
Fairness
Problem of “User Starvation”
Efficiency (overall throughput)
Overhead
Some of these aspects are contradictory
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ3 / 313 / 31
SchedulingScheduling AlgorithmsAlgorithms
AlgorithmsAlgorithms
The following scheduling algorithms will be discussed:
Round Robin
Maximum Rate
Proportional Fair Scheduling
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ4 / 314 / 31
SchedulingScheduling Round Robin AlgorithmRound Robin Algorithm
Round Robin IRound Robin I
Round Robin is the simplest known scheduling algorithm. Itallocates each UE equally spaced timeslots, completelyignoring channel quality or data rate.
t
Channel quality
UE #1
UE #2
UE #3 (selected)
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ5 / 315 / 31
SchedulingScheduling Round Robin AlgorithmRound Robin Algorithm
Round Robin IIRound Robin II
As we can see in the diagram, the Round Robin Algorithm hassome serious drawbacks:
It is not efficient
It is not fair in the sense of service quality
Therefore we need better scheduling algorithms.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ6 / 316 / 31
SchedulingScheduling Maximum Rate AlgorithmMaximum Rate Algorithm
Maximum Rate IMaximum Rate I
The Maximum Rate Scheduler always selects the UE with thebest data rate for transfer. Therefore it needs informationabout the expected data rate (which can be derived from theSNR) of each UE.
t
Channel quality
UE #1
UE #2
UE #3 (selected)
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ7 / 317 / 31
SchedulingScheduling Maximum Rate AlgorithmMaximum Rate Algorithm
Maximum Rate IIMaximum Rate II
Advantages
Very efficient in the sense of overall datarate
Easy implementation, only information about signalquality is needed.
Disadvantages
User starvation is very probable
Impossible to calculate maximum delay, very high delaytime possible
→ Practical application is pointless
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ8 / 318 / 31
SchedulingScheduling Maximum Rate AlgorithmMaximum Rate Algorithm
Maximum Rate IIIMaximum Rate III
Improvements
To avoid “User Starvation” it is possible to add a minimal datarate rmin each user needs to receive. This data rate can beassigned to the users in a manner similar to the Round Robinalgorithm and thus we obtain a combination of bothalgorithms.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ9 / 319 / 31
SchedulingScheduling Proportional Fair AlgorithmProportional Fair Algorithm
Proportional Fair Algorithm IProportional Fair Algorithm I
Basic IdeaMeasure the link quality of each UE over a defined timeinterval and select the UE with the best quality with respect toits average
i = argmaxi{ri ,n+1
θi ,n
}
t
Channel quality
UE #1
UE #2
UE #3 (selected)
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ10 / 3110 / 31
SchedulingScheduling Proportional Fair AlgorithmProportional Fair Algorithm
Proportional Fair Algorithm IIProportional Fair Algorithm II
Advantages
“User Starvation” not very likely
Better overall throughput than the Round Robin Scheduler
Disadvantages
Information about the channel quality needed
Higher complexity
Lower throughput than Max Rate Scheduler
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ11 / 3111 / 31
SchedulingScheduling Proportional Fair AlgorithmProportional Fair Algorithm
ComparisonComparison
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ12 / 3112 / 31
SchedulingScheduling General RemarksGeneral Remarks
Remarks IRemarks I
Multiple Carriers
In LTE, these algorithms have to be extended to the amount ofavailable resource blocks (OFDM-Subcarriers).
Not part of the specification
Scheduling algorithms are not part of any specification. Thenecessary interfaces have to be specified (e.g. how to obtaininformation about channel quality) but not the scheduler itself.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ13 / 3113 / 31
SchedulingScheduling General RemarksGeneral Remarks
Remarks IIRemarks II
Quality of Service
Another important point the scheduler has to consider is QoS:Different services should have different priorities and maybesome users should be served preferential.
HARQRequested repetition of a packet should be able to prioritiseother scheduled packets.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ14 / 3114 / 31
SchedulingScheduling Uplink ChannelUplink Channel
Uplink ChannelUplink Channel
In principle, the same algorithms can be used for the uplinkchannel. However, some problems have to be considered:
Limited power of the UEs, hence it is unlikely that a singleterminal can use the whole link capacity
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ15 / 3115 / 31
SchedulingScheduling Uplink ChannelUplink Channel
OutlineOutline
1 Scheduling
2 HARQ
3 Literature
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ16 / 3116 / 31
HARQHARQ Error CorrectionError Correction
HARQHARQ
Error CorrectionLike every communication channel, the LTE channel is alsosubject to errors.These might occur due to:
Variations in channel quality (relatively slow varying)
Intracell interference and receiver noise (fast varying andunpredictable)
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ17 / 3117 / 31
HARQHARQ FEC & ARQFEC & ARQ
FEC & ARQ IFEC & ARQ I
There are two different approaches to error correction:
FEC - Forward Error CorrectionIntroduces redundancy in the transmitted signal by addingparity bits.
Can only correct a certain number of errors
ARQ - Automated Repeat reQuest
Receiver performs Cyclic Redundancy Check check of thereceived data. If the received packet is error-free, thereception will be acknowledged and the packet accepted,otherwise a retransmission will be requested.
Adds delay for every erroneusly received bit
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ18 / 3118 / 31
HARQHARQ FEC & ARQFEC & ARQ
FEC & ARQ IIFEC & ARQ II
Combination of FEC & ARQThe best of both worlds
1 FEC: Corrects a certain maximum of errors in the packet
2 ARQ: Performs CRC check on the possibly alreadycorrected packet and requests retransmission onerroneous reception.
→ HARQ (Hybrid-ARQ)
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ19 / 3119 / 31
HARQHARQ HARQ with Chase CombiningHARQ with Chase Combining
HARQ with Chase Combining IHARQ with Chase Combining I
R = 3/4
1st Transmission 1st Retransmission 2nd Retransmission 3rd Retransmission
Input to Decoder
Accumulated Energy E 2E 3E 4E
Resulting Code Rate R = 3/4 R = 3/4 R = 3/4 R = 3/4
Info.
R = 1/4
Puncturing
Coded Bits
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ20 / 3120 / 31
HARQHARQ HARQ with Chase CombiningHARQ with Chase Combining
HARQ with Chase Combining IIHARQ with Chase Combining II
Same Symbols
If the reception fails, the same symbols will be send again→ Accumulated Energy increases (and thus SNR improves)
Code RateCode Rate is untouched, only determined by the FEC Code
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ21 / 3121 / 31
HARQHARQ HARQ with Soft CombiningHARQ with Soft Combining
HARQ with Soft Combining IHARQ with Soft Combining I
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ22 / 3122 / 31
HARQHARQ HARQ with Soft CombiningHARQ with Soft Combining
HARQ with Soft Combining IIHARQ with Soft Combining II
1 The information bits are encoded with a Mother Code,typically a low-rate code (R=1/4 in the example).
2 The encoded bits are either punctured or repeated to fitthe desired code rate.
3 The receiver decodes the bits and upon error-freedecoding accepts the block and notifies the sender,otherwise the next version is requested from the sender.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ23 / 3123 / 31
HARQHARQ HARQ with Soft CombiningHARQ with Soft Combining
HARQ with Soft Combining IIHARQ with Soft Combining II
1 The information bits are encoded with a Mother Code,typically a low-rate code (R=1/4 in the example).
2 The encoded bits are either punctured or repeated to fitthe desired code rate.
3 The receiver decodes the bits and upon error-freedecoding accepts the block and notifies the sender,otherwise the next version is requested from the sender.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ23 / 3123 / 31
HARQHARQ HARQ with Soft CombiningHARQ with Soft Combining
HARQ with Soft Combining IIHARQ with Soft Combining II
1 The information bits are encoded with a Mother Code,typically a low-rate code (R=1/4 in the example).
2 The encoded bits are either punctured or repeated to fitthe desired code rate.
3 The receiver decodes the bits and upon error-freedecoding accepts the block and notifies the sender,otherwise the next version is requested from the sender.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ23 / 3123 / 31
HARQHARQ HARQ with Soft CombiningHARQ with Soft Combining
HARQ with Soft Combining IIIHARQ with Soft Combining III
4 The sender will transmit the next version with redundancybits and the receiver will try to decode the block, usingthe information from the old and the new block.
5 If the decoding fails again, in the example it would bepossible to request a third block.
6 If the decoding is still impossible, repetition will start. Thefirst block will be send again, thus the accumulatedenergy will be increased and hopefully allow decoding.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ24 / 3124 / 31
HARQHARQ HARQ with Soft CombiningHARQ with Soft Combining
HARQ with Soft Combining IIIHARQ with Soft Combining III
4 The sender will transmit the next version with redundancybits and the receiver will try to decode the block, usingthe information from the old and the new block.
5 If the decoding fails again, in the example it would bepossible to request a third block.
6 If the decoding is still impossible, repetition will start. Thefirst block will be send again, thus the accumulatedenergy will be increased and hopefully allow decoding.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ24 / 3124 / 31
HARQHARQ HARQ with Soft CombiningHARQ with Soft Combining
HARQ with Soft Combining IIIHARQ with Soft Combining III
4 The sender will transmit the next version with redundancybits and the receiver will try to decode the block, usingthe information from the old and the new block.
5 If the decoding fails again, in the example it would bepossible to request a third block.
6 If the decoding is still impossible, repetition will start. Thefirst block will be send again, thus the accumulatedenergy will be increased and hopefully allow decoding.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ24 / 3124 / 31
HARQHARQ Benefits of HARQBenefits of HARQ
Benefits of HARQBenefits of HARQ
FEC can correct a small amount of errors
ARQ can rely on FEC for packets with few errors and onlyhas to treat packets with many errors
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ25 / 3125 / 31
HARQHARQ Benefits of HARQBenefits of HARQ
Comparison of ARQ and Link AdaptationComparison of ARQ and Link Adaptation
ARQCan automaticallyadapt code rate
Reacts immediatelyupon occurrence of anerror
Increases delay timewhile correcting
Link Adaptation
Adapts code rateexplicitly
Reacts relatively slow
Does not affect delay
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ26 / 3126 / 31
HARQHARQ Implementation in LTEImplementation in LTE
Implementation in LTEImplementation in LTE
Multiple parallel HARQ processes run in the UE and theeNodeB.
How do receiver and sender know when to perform SoftCombining and when to clear their buffers for a newblock?→ new-data indicator has to be send
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ27 / 3127 / 31
HARQHARQ Implementation in LTEImplementation in LTE
Downlink ChannelDownlink Channel
Asynchronous, adaptive HARQ
Asynchronous: No strict timing, retransmission packetis scheduled like any other packet, normally with higherpriority.
Adaptive: The retransmission can use other resources(frequency, modulation) than the original packet.
For each block, the HARQ process-id and the redundanyversion number has to be send via the PDCCH (PhysicalDownlink Control Channel). The ACK/NAK message is sentthrough the uplink channel.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ28 / 3128 / 31
HARQHARQ Implementation in LTEImplementation in LTE
Uplink Channel IUplink Channel I
Synchronous, non-adaptive HARQ
Synchronous: Retransmission after a fixed interval(8 packets)
non-adaptive: Same resources have to be used again.
The only necessary feedback to the sender is a single bit,with information whether to resend the packet or not.
There is also a possibility to explicitly define theretransmission for another frequency block, but this is notthe usual behaviour.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ29 / 3129 / 31
HARQHARQ Implementation in LTEImplementation in LTE
Uplink Channel IIUplink Channel II
How to support both modes?
There are two ways to request a retransmission:
PHICH (Physical Hybrid-ARQ Indicator Channel): Thereceiver can request the retransmission using the sameresources.
PDCCH: The eNodeB can use the PDCCH to allocateanother frequency for the retransmission or to request acertain redundancy version of the packet.
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ30 / 3130 / 31
LiteratureLiterature
LiteratureLiterature
[Dah08] E. Dahlman et al.: 3G Evolution – HSPA and LTE forMobile Broadband , 2nd Edition, 2008.
[Kon09] M. Konrad: Scheduling Algorithms and theirApplication in Wireless Communications , 2009.
[Kwa08] R. Kwan et al.: Multiuser Scheduling on the Downlinkof an LTE Cellular System, 2008
Tobias SchrageTobias Schrage – Scheduling and HARQ– Scheduling and HARQ31 / 3131 / 31
Scheduling and HARQScheduling and HARQSeminar LTE: Der Mobilfunk der ZukunftSeminar LTE: Der Mobilfunk der Zukunft
Tobias Schrage
University Erlangen-NürnbergChair of Mobile Communications
January 13, 2010