Transcript 20100518_Downlink Sc..

Bader Al-Manthari, Nidal Nasser, and Hossam
Hassanein,“Downlink Scheduling With Economic
Considerations for Future Wireless Networks,” IEEE
TRANSACTIONS ON VEHICULAR TECHNOLOGY, Vol. 58,
No. 2, FEBRUARY 2009.
Advisor：Yeong-Sung Lin
Student：Chiu-Han Hsiao
Department of Information Management
National Taiwan University
Taipei, Taiwan, R. O. C.
Outline
 Introduction
 Background Study
Problem Description and System Model
Centralized Downlink Packet Scheduler (CDPS)
Performance Evaluation
Experiment Result
Conclusion
2010/05/18
OPLAB
2
Introduction(1/2)
 3G Universal Mobile Telecommunication System
(UMTS)(2Mbps)
 High-Speed Downlink Packet Access (HSDPA) (3.5G) can
theoretically support up to 14.4 Mbps, which is seven
times higher than the data rate offered by UMTS
 A key component of radio-resource management (RRM) is
packet scheduling, which is responsible for distributing the
shared radio resources among the mobile users
 we propose a novel centralized downlink packet scheduler
(CDPS) scheme to be implemented at the base stations of
future wireless cellular systems
2010/05/18
OPLAB
3
Introduction(2/2)
CDPS utilizes an opportunity cost function that
allows service providers to control its degree of
fairness and hence control the system capacity
CDPS is designed to balance between the
requirements of connections (e.g., throughput,
fairness, etc.) and the requirements of service
providers (e.g., revenues)
CDPS can be configured to reduce to the
maximum carrier-to-interference ratio (Max CIR)
and proportional fairness (PF) schemes
2010/05/18
OPLAB
4
Background Study
2010/05/18
OPLAB
5
Multiple Access Methods
Multiple users share the available spectrum
2010/05/18
OPLAB
6
What is “IMT-2000”
IMT-2000 (Internet Mobile Telecommunications2000) is the personalized global multi-media
service, which unifies all the various mobile
telephone system specs
Services
– global roaming service
– multimedia communications
This is “ 3rd Generation Mobile Communication
System”
2010/05/18
OPLAB
7
IMT-2000
ITU (International Telecommunication Union)
IMT-2000
• Year 2000 Ready
• Operate at 2000 MHz
• Provide 2000K bps Data Rate
3G Data Rate Requirement
• Vehicular -- 144 Kbps
• Pedestrian --- 384 Kbps
• Indoor --- 2Mbps
2010/05/18
OPLAB
8
IMT-2000 Evolution
2010/05/18
OPLAB
9
IMT-2000 Evolution
W-CDMA
(FDD)
ARIB (W-CDMA)
PDC
UTRA (W-CDMA)
GSM
Wideband
CDMA
Multicarrier
Multicode
TD-CDMA
(TDD)
GPRS
EDGE
136 HS
AMPS
IS-54
UWC-136
IS-136
136+
cdmaOne
(IS-95)
cdma2000
IS-95B
• IEEE Spectrum, Aug. 1999 (Modified)
2010/05/18
OPLAB
• AMPS: Advanced Mobile Phone System
• GSM: Global Systems for Mobile Comm.
• GPRS: General Packet Radio Service
• PDC: Personal (or Pacific) Digital Comm.
• EDGE: Enhanced Data rates for GSM
(or global) Evolution
• UTRA: UMTS Terrestrial Radio Access
10
IMT-2000 Terrestrial RTT Standardization
 CDMA2000 (North America)
– Based on Qualcom cdmaOne
– Support multi-carrier (MC)
– Use IS-41 to accomplish the core network compatibility
 TD-SCDMA (Mainland)
–
–
–
–
大唐電信 and Siemens
TDD-based
Requirement : time synchronization
Limit coverage area of BS
 WCDMA/UMTS (Japan and Europe)
– NTT DoCoMo develops WCDMA
– Core network is based on GSM system
– UTRA (UMTS Terrestrial Radio) proposed by Europe is similar as
WCDMA
2010/05/18
OPLAB
11
Network Upgrade Comparison: CDMA2000 1x vs.
GPRS / W-CDMA
SGSN: Serving GPRS Support Node
GGSN: Gateway GPRS Support Node
2010/05/18
MSC: Mobile Switching Center
OPLAB
12
New Terms
WCDMA/UMTS Terms
– BTS → Node B (NB)
– BSC → RNC (Radio Network Controller)
• New job : RRM (Radio Resource Management)
Radio Bearers
Channels
– Logical Channel
– Transport Channel
– Physical Channel
Data forwarding direction
– Uplink (reverse link)
– Downlink (forward link)
2010/05/18
OPLAB
13
3G Frequency Allocation in Taiwan
MHz
890
1885MHz
2025MHz
2110MHz
ITU IMT-2000
ITU IMT-2000
2165
50
2110
1975
25
A BC D
BCD
2010
15
20
2025
D
60
C
45
B
35
1915
20
A A
2200MHz
35
825
870
E
845
E
MHz
3G 執照
頻寬
頻帶 (MHz)
A
2 x 15 MHz + 5 MHz
1920 ~ 1935, 2110 ~2125, 1915 ~ 1920
B
2 x 10 MHz + 5 MHz
1935 ~ 1945, 2125 ~ 2135, 2010 ~ 2015
C
2 x 15 MHz + 5 MHz
1945 ~ 1960, 2135 ~ 2150, 2015 ~ 2020
D
2 x 15 MHz + 5 MHz
1960 ~ 1975, 2150 ~ 2165, 2020 ~ 2025
E
2 x 20 MHz
825 ~ 845, 870 ~ 890
Apple - iPhone - 技術規格.htm
2010/05/18
OPLAB
14
WCDMA Standards
3GPP
– www.3gpp.org
WCDMA
– FDD mode
– TDD mode
Release
–
–
–
–
–
–
–
–
–
R98 (1998)
R99 (200003 freeze) --- WCDMA
R4 (200103 freeze)
R5 (2002 freeze) --- HSDPA
R6 (2003 freeze) --- HSUPA
R7 (2007 freeze)
R8 (2008 freeze) --- LTE
R9 (ongoing)
R10 (ongoing)
2010/05/18
OPLAB
LTE: Long Term Evolution
15
History (1/2)
Release 98 (1998)
– This and earlier releases specify pre-3G GSM networks
Release 99 (2000 Q1)
– Specified the first UMTS 3G networks, incorporating a CDMA
air interface
– USIM : mutual authentication (AKA)
Release 4 (2001 Q2)
– Originally called the Release 2000 - added features including an
All-IP Core Network
Release 5 (2002 Q1)
– Introduced IMS and HSDPA
Release 6 (2004 Q4 )
– Integrated operation with WLAN networks and adds HSUPA,
MBMS, enhancements to IMS such as Push to Talk over
Cellular (PoC)
2010/05/18
OPLAB
16
History (2/2)
Release 7 (2007 Q4)
– Focuses on decreasing latency, improvements to QoS and realtime applications such as VoIP
– also focus on HSPA+ (High Speed Packet Access Evolution),
MIMO, SIM high-speed protocol and contactless front-end
interface (Near Field Communication enabling operators to
deliver contactless services like mobile payments), EDGE
Evolution.
Release 8 (In progress, not ready before Mar 2009)
– LTE, All-IP Network (SAE). It constitutes UMTS as an entirely
IP based fourth-generation network.
Release 9 (In progress, expected to be frozen in Dec
2009 )
– SAES Enhancements, WiMAX and LTE/UMTS Interoperability
Release 10 (In progress)
– LTE-Advanced
2010/05/18
OPLAB
17
3GPP Development Progress
Functionality
UTRA FDD/TDD
modes, USIM,
AMR speech
codec, MMS,
LCS,
CAMEL etc.
LCR TDD,
UTRA FDD
repeater function,
700MHz support
for GERAN
IMS phase 1,
HSDPA,
Wideband AMR,
IP transport
in UTRAN
Release
Releasenn
Release
Release66
Release
Release55
Release
Release44
HSUPA,
MBMS,
WLAN/UMTS
Interworking ,
IMS phase 2
OFDM?
MIMO?
EDCH?
IMS further
Phase?
Release
Release1999
1999
1999 - 12
2010/05/18
2001 - 03
2002 - 03/06
OPLAB
2003/12
Time
18
3GPP’s Evolution/Revolution Towards
4G
Enchanced
IMT - 2000
IMT - 2000
New
Mobile
Access
2001/11/04
2002/06/24
2003/09/26
2005/01/04
3GPP R4
(WCDMA)
3GPP
3GPPR5
R5
(+HSDPA
(+HSDPA)
)
3GPP
3GPPR6
R6
(+HSUPA)
3GPP
3GPPR7
R7
(+MIMO)
(+MIMO)
R8
LTE
OFDMA
Systems
3GPP R4
3GPP R5
3GPP R6
3GPP R7
3GPP R8
Data Rate
(peak)
2010/05/18
Forward
Link
2 Mbps
Reverse
Link
384 Kbps
> 10 Mbps > 10 Mbps > 20 Mbps
384 Kbps > 2 Mbps
OPLAB
> 5 Mbps
100 Mbps
20 Mbps
19
Radio Resource Management
CDPS is proposed
2010/05/18
OPLAB
20
Channel quality condition for scheduling
decisions
2010/05/18
OPLAB
21
Packet Scheduler Model
2010/05/18
OPLAB
22
System Formulation
we emphasize recent scheduling schemes
for data (non–real-time) services in future
wireless cellular networks
the base station simultaneously serves n
connections n ≥ 1 and selects one or more
connections for transmission in a frame of
some fixed time duration
These PDUs are stored in the transmission
queue of the corresponding connection in a
first-in–first-out fashion
2010/05/18
OPLAB
23
Utility Function
The user’s i (1 ≤ i ≤ n) preferences at time t as
perceived by the service provider can be expressed
by a utility function Ui(Xi1(t),Xi2(t), . . . , Xim(t)),
– where n is the total number of users’ connections in the
system,
– Xi1(t), . . . , Xim−1(t) are the chosen quantitative
measures of the user connection’s preferences in this
system such as the average throughput, current data rate,
average delay, etc.,
– Xim(t) is a fairness measure that represents how fair the
scheduling scheme is to the user connection, and m is
the maximum number of chosen quantitative measures.
We assume that the utility function is additive
2010/05/18
OPLAB
24
Objective Function
OCi(t) is the opportunity cost of serving connection i
at time t, and K is a predefined constant value
2010/05/18
OPLAB
25
Cobb–Douglas Utility Function for Downlink
Scheduling
Cobb-Douglas生產函數：簡稱C-D生產函
數
最簡單之形式如：Q = AKαLβ
式中Q：產出量，K：資本使用量，L勞
動使用量，A、α 及β表固定常數，其數
值可由實際統計資料估計出
2010/05/18
OPLAB
26
Cobb–Douglas生產函數
1.若α +β>1，則此生產為遞增的規模報酬；即
若所有生產要素按相同比例增加，則產量增
加的比例大於生產因素增加的比例。如：Q
= 20K0.7L0.6
2.若α +β=1，則此生產為固定的規模報酬；即
產量增加的比例等於生產因素增加的比例。
例：Q = 50K0.4L0.6
3.若α +β<1，則此生產為遞減的規模報酬；即
產量增加的比例小於生產因素增加的比例。
例：Q = 100K0.5L0.3
2010/05/18
OPLAB
27
Definitions of Xi1(t) and Xi2(t)
Assuming m = 2 in our formulation of CDPS, the
Cobb–Douglas utility function is expressed as
Ui(X1,X2) = X1c ·X2d
– where c, d ≥ 0. Let X1 be any performance metric that
the service provider wants to optimize, such as the
average connection throughput or average delay. Let X2
be a fairness measure that increases as the connection’s
or system’s perception of fairness increases, which
results in an increase in U
2010/05/18
OPLAB
28
Definitions of Xi1(t) and Xi2(t)
To maximize the system’s overall utility, we
need to achieve the highest possible values
of Xi1(t) and Xi2(t) for all connections.
However, it is not possible to achieve high
values of both Xi1(t) and Xi2(t) for all
connections because of the tradeoff between
capacity and fairness
2010/05/18
OPLAB
29
Definitions of Xi1(t) and Xi2(t)
Given these two definitions, the fairness measure
for connection i at time t, αi(t) can be defined
Si(t) is the average throughput for connection i up
to time t
maxj Sj(t) is the maximum average throughput
achieved among all connections up to time t.
the fairness measure for connection i is the ratio of
its average throughput to the maximum throughput
achieved among all the connections in the system.
We call this measure the “relative fairness.”
2010/05/18
OPLAB
30
Definitions of Xi1(t) and Xi2(t)
The opportunity cost of serving connection i
at time t (i.e., the opportunity cost of
fairness) is defined as
where Ri(t) is the current data rate for
connection i at time t, which depends on its
channel condition,
maxj Rj(t) is the maximum current data rate
of all connections at time t
2010/05/18
OPLAB
31
Definitions of Xi1(t) and Xi2(t)
 c: the Cobb–Douglas utility function’s constant, where c ≥
0. The value of this constant determines the weight on Xi1(t)
in the Cobb–Douglas utility function
 d: the Cobb–Douglas utility function’s constant, where d ≥
1. The value of this constant determines the weight on Xi2(t)
in the Cobb–Douglas utility function.
 We restrict the value of this constant to an odd integer
because our defined Xi2(t) in the adopted Cobb–Douglas
utility function is a negative function
 d must be odd
2010/05/18
OPLAB
32
Definitions of Xi1(t) and Xi2(t)
Xi1(t) = Ri(t): the current data rate of
connection i at time t
The utility of connection i being served
increases as Ri(t) increases. It should be
noted that other performance metrics could
be used. However, we use the current data
rate as the first component in the Cobb–
Douglas utility function to increase the
system capacity and, hence, achieve the
efficiency objective
2010/05/18
OPLAB
33
Definitions of Xi1(t) and Xi2(t)
Xi2(t) = f(αi(t), γi(t)) = 1 − γi −ln(αi(t))
γi > 1: the fairness measure, which is a
function of the relative fairness that we
defined to increase fairness in the system
2010/05/18
OPLAB
34
Definitions of Xi1(t) and Xi2(t)
The parameter γi is used to control the shape
of Xi2(t) and , hence, the level of fairness in
the system
γi can be set to different values for different
connections to allow the service provider to
maintain different levels of fairness for
different connections depending on the type
of traffic they have, the amount of money
they are expected to pay, their loyalty, etc.
2010/05/18
OPLAB
35
Definitions of Xi1(t) and Xi2(t)
Objective
function
Connection
Selection
2010/05/18
OPLAB
36
Experiment Environment Setting
Simulation Model
2010/05/18
OPLAB
37
Simulation Parameters
2010/05/18
OPLAB
38
Test Environments
Case I: Ped A (Fig 5~12)
– The mobile users in the Ped A environment move at a
fixed speed of 3 km/h, which is the recommended value
by the 3GPP
Case II: fixed differentiated channel conditions
(Fig 13, 14)
– The fixed channel environment is created to evaluate
the performance of the CDPS under different fixed
channel conditions (as opposed to Ped A in which the
channel conditions of users vary with time, according to
the models specified by the 3GPP)
2010/05/18
OPLAB
39
Fig.2010/05/18
5. Cell throughput.
OPLAB
40
Fig. 6. Cell throughput with different values of K.
Fig. 7. Distribution of connection average throughputs.
2010/05/18
OPLAB
41
Fig. 8. Distribution of connection average throughputs with different values of K.
2010/05/18
OPLAB
42
Fig. 9. User satisfaction with minimum throughput of 128 Kbps
2010/05/18
OPLAB
43
Fig. 10. User satisfaction with minimum throughput of 128 Kbps with
different values of K.
2010/05/18
OPLAB
44
Fig. 11. User satisfaction with minimum throughput of 356 Kbps
2010/05/18
OPLAB
45
Fig. 12. User satisfaction with minimum throughput of 356 Kbps
with different values of K.
2010/05/18
OPLAB
46
Fixed Differentiated Channel Conditions
Seven values are used for the SNR: −7, −4,
−1, 2, 5, 8, and 11 dB
For each SNR value, there are ten
connections (a total of 70 connections in the
cell)
2010/05/18
OPLAB
47
Fig. 13. Average connection throughput for connections with different
OPLAB
48
SNR2010/05/18
values.
Fig. 14. Percentage of packet loss for connections with different SNR
values.
OPLAB
49
2010/05/18
Conclusions
we have proposed a CDPS scheme for future
wireless cellular systems that is based on a utility
function to represent the satisfactions of the
mobile users as perceived by the service provider
Our scheme also utilizes an opportunity cost
function to represent the satisfactions of the
service provider
CDPS can simultaneously meet four design
objectives, that is, efficiency, fairness, users’
satisfactions, and flexibility
2010/05/18
OPLAB
50
Comments
How does it work on real-time traffic or
another service types?
– X1c may be delay or delay jitter.
– Objective function have to be modified.
How is the uplink data flow?
What is the business model for a operator to
get maximum revenues? Strategy?
2010/05/18
OPLAB
51
Thank you