Transcript Scheduling Algorithms for Wireless Networks

Opportunistic Scheduling
Algorithms for Wireless Networks
Vegard Hassel
CUBAN Seminar 22. April 2004
Agenda
•
•
•
•
•
What is scheduling/opportunistic scheduling?
Cross-layer design
Different types of channel models
Fairness
Algorithms that only consider the channel
conditions
• Algorithms that consider QoS
• Algorithms that consider power consumption
• Current & future research
What Is Scheduling?
Scheduling policy:
-a rule that specifies which user is allowed
to transmit and which user is allowed to
receive at each timeslot
Uplink (user transmits) and downlink (user
receives) at different frequencies.
What Is Opportunistic
Scheduling?
Opportunistic: Scheduler tries to exploit channel
conditions to achieve higher network performance
SCHEDULER
USER 1
USER 2
BUFFERS
The base station serves as a scheduling agent
USER 3
Qualcomm Example (1)
• The channel conditions for each user is independent
• The channel is GOOD 50% of the time and BAD 50% of
the time
• Two users with bitrates:
– User 1: 200Mbit/s or 400Mbit/s
– User 2: 400Mbit/s or 800Mbit/s
• The users cannot be active at the same time
• Round robin algorithm without opportunistic scheduling:
– R1=0.5*(0.5*200Mbit/s+0.5*400Mbit/s)=150Mbit/s
– R2=0.5*(0.5*400Mbit/s+0.5*800Mbit/s)=300Mbit/s
Qualcomm Example (2)
• With opportunistic scheduling, the user that has the GOOD
channel condition is chosen:
– 25% of the time both users have BAD channel
– 50% of the time one user has GOOD channel
– 25% of the time both users have GOOD channel
• The user with the relatively best channel is chosen
• Round robin with opportunistic scheduling:
– R1=0.5*(0.25*200Mbit/s+0.75*400Mbit/s)=175Mbit/s
– R2=0.5*(0.25*400Mbit/s+0.75*800Mbit/s)=350Mbit/s
• Opportunistic scheduling gives a 17% capacity gain
But what if both users need 200Mbit/s?
Cross-Layer Design
TCP/IP-layers:
•
•
•
•
•
Application
Transport (TCP, UDP)
Internet (IP)
Network access (MAC, LLC)
Physical
Today: Some adaptation between neighbouring layers
Tomorrow: Network stack that take advantage of the
interdependencies between the layers
Cross-Layer Design
Variations follow different time scales:
• SNR variations ~ microseconds
• Congestion of packets ~ seconds?
• Cumulative user traffic ~ 10-100 seconds
Goldsmith: Because of the different
timescales, adaptation between layers is
reasonable only if problems cannot be fixed
locally within a layer.
What Influences Scheduling?
QoS requirements
Delay
Throughput
SCHEDULING
Fast fading
Slow fading
Instantaneous channel conditions
Restrictions From Other Layers
Physical layer:
• Adaptive coding and modulation (MQAM)
• TDMA or CDMA
• TDMA: The channel should be constant
within a time-slot
Higher layers:
• Throughput requirements
• Delay requirements
Channel Models
• Two-state Markov: GOOD/BAD
• Slow fading: log-normal distribution
• Fast fading:
– Rice (LOS)
– Rayleigh (LOS blocked)
– Nakagami (general)
• The average SNR,  , for the fast fading models is
influenced by slow fading
• Slow scheduling: parameters changes slowly
• Fast scheduling: parameters changes fast

Fairness
• Choosing the best user with regard to the
channel can lead to starvation of some users
• Fair algorithms assign a guaranteed time or
throughput to the users (Robin Hood)
• Fairness not so important in a fast fading
environment
Algorithms That Only Consider
The Channel Conditions
1. Proportional fair algorithm
2. Max SNR scheduling
3. Max SNR scheduling with a threshold
4. Opportunistic beamforming
Proportional Fair Algorithm
• Proportional fair if:
– increasing the current throughput by x% for one
user leads to a cumulative throughput decrease
for the other users of more than x%
• Maximises the product of the throughputs
• The user with the relatively best channel is
chosen
• Starvation is avoided
• Used by Qualcomm/HDR (IS-856)
Proportional Fair Algorithm
Algorithm:
STEP 1:
At time t choose the user with the highest Ri(t)/ Ci(t):
Ri (t) 
i (t)  argmax

1iN Ci (t) 
*
STEP 2:
Update average rate:
Ci (t  1)  (11/tC )  Ci (t)  1/tC  Ri (t)  I(i)

Max SNR Scheduling
Proportional Fair algorithm with:
• large values of tc
• same  for all users: Ri(t) ~ i(t) and Ci(t) ~ 
i (t)  arg max ( i (t))
*
1iN
 The user with the largest SNRis chosen
Also called greedy algorithm

Not fair if  is different for different users
Max SNR Scheduling With
Threshold
The user with the largest SNR above a
threshold is chosen:

argmax( i (t)) if   i (t)   th (t)

*
i (t)   1iN
rand
(

(t))
if


(t)


(t)

i
i
th
1iN
Reduces the amount of feedback from the
users. Channel state information is only fed
back if SNR is above the threshold.
Opportunistic Beamforming
Induce channel fluctuations in a slow fading
environment:
• MS’s with multiple antennas
• Antennas are fed with random phase and
amplitude
• The overall induced SNR of a user is fed
back to the BS
• The BS schedules proportionally fair
according to the different SNR values
Algorithms That Consider QoS
• FUNDAMENT: Revenue-based algorithm
• This algorithm maximizes the throughput
with regard to QoS requirements:
i (t)  arg max w i (t)Ri (t)
*
1iN

wi(t): weight assigned to a user to include the
QoS requirements
Algorithms That Consider QoS
Examples of QoS-requirements:
•
Minimum delay requirement
•
Minimum throughput requirement
M-LWDF
Modified Largest Weighted Delay First
i* (t)  arg max  iW i (t)Ri (t)
1iN
i: constant for controlling delay distributions

Wi(t): head-of-the-line packet delays
This simple algorithm is throughput optimal!
M-LWDF: Throughput Guarantees
Guarantees minimum throughput Ri:
i (t)  arg max iW i (t)Ri 
*
1iN
Ri: constant token arrival rate in bucket i
Wi(t): delay of the longest delay token in bucket

i: constant for controlling time-scale on which
throughput guarantees are provided
Lazy Scheduler
A scheduler that trades off delay for energy
QuickTime™ og en
TIFF (LZW)-dekomprimerer
kreves for å se dette bildet.
M-LWDF: Delay vs. Power?


W
(t)
i* (t)  argmaxi i Ri (t)
Pi (t)
1iN 

i: constant for controlling trade-off between
power and delay
 Wi(t): head-of-the-line packet delays
Pi(t): power that has to be provided to user i
System Model
Buffering on both uplink and downlink
SCHEDULER
USER 1
USER 2
BUFFERS
USER 3
BUFFERS
Current Research
Have investigated buffering between wired
and wireless (Rayleigh) networks using
optimal SNR scheduling.
New expression for overflow probability
when the rate into the memoryless buffer is
constant.
The corresponding expression has been found
for a queue with Poisson distributed traffic
from the wired network (M/G/1-queue)
What Will I Do Next?
• Investigate max SNR Scheduling with both
power and rate adaptation for M-QAM
• Investigate the effects of Dopplerspread,
coherence time and avg fade duration
• Spectral efficiency and BER for a
scheduling algorithm using a -threshold
• Max SNR scheduling with delayed CSI
• SNR scheduling with different 
Future Research
1) Physical layer issues:
• Optimising adaptive coding/modulation to the
scheduling algorithm in use
• Scheduling for slow fading channels (fairness!)
• Evaluating channel information inaccuracy
• Analysing interference/multicell issues
• Combining MIMO with scheduling
• Combining OFDM with scheduling
• Energy efficient scheduling (with Sébastien)
Future Research
2) QoS issues:
Must look at algorithms that:
• Provide QoS differentiation between users
• Maximise the number of users that can be
supported with the desired QoS
• Provide minimum flow guarantees?
• Gives minimum buffer overflow
Future Research
3) Other issues:
•
•
•
•
Ad Hoc networks
Multi-hop networks
MAC and ARQ protocols
CAC: Connection Admission Control