Transcript PhD Dissertation Slides

Towards Viable Large Scale
Heterogeneous Wireless Networks
Ph.D. Dissertation Defense
by
Rahul Amin
Electrical and Computer Engineering
Research Advisor: Dr. Jim Martin
Committee Members:
Dr. Harlan B. Russell
Dr. Daniel Noneaker
Dr. Brian Dean
Dr. Melissa Smith
Outline
• Introduction
• Motivation and Background
• Thesis Statement
• System Model
• Research Phase I Summary – Resource Allocation Problem
• Research Phase II Study – Practical Implementation Issues
• Conclusions
2
Introduction
• The demand for wireless data traffic is outgrowing current
supply capabilities
– Proliferation of mobile
devices in the last decade has
created an exponential
growth in traffic demand
– FCC projects a 275 MHz
spectrum deficit by 2014 if no
new spectrum is made
available for broadband usage
– Utilizing available spectrum in
the most efficient manner
becomes paramount
Source: Opennetsummit April 2012
3
Introduction (Contd.)
• While there are areas of spectrum that are over-utilized, there
are other areas of spectrum that are underutilized
• This has renewed interest in techniques that attempt to improve
spectral efficiency through co-operation at the radio/network
level
– Bottom-up Approaches
• Examples: Cognitive networks, Dynamic Spectrum Access networks
– Top-down Approaches
• Examples: Heterogeneous wireless networks, Wi-Fi Offloading, Femtocells/Picocells
• Heterogeneous wireless networks (hetnets) made up of several
cellular (LTE, WiMAX, HSPA) and WLAN (Wi-Fi) Radio Access
Technologies (RATs) is the focus of our study
4
Motivation and Background
• Due to the widespread deployment of several wireless RATs, it is quite
common for any geographical location to be covered by more than
one wireless network
• Current practices lead to sub-optimal spectrum usage
– Wireless networks are built independently
– Individual networks attempt to achieve best performance within its own
network, generally ignoring impact of co-located networks
– Users are required to select the active access network
• A fundamental motivation for our research is that enhancing access
and use of spectrum requires a combination of cognitive device
capabilities AND a component of resource allocation that operates at
the global level [VT ’11]
Source:
[VT ’11] J. Martin, R. Amin, A. Eltawil, A. Hussien, “Limitations of 4G Wireless Systems,” Proceedings of Virginia Tech Wireless Symposium, June
2011.
5
Motivation and Background (Contd.)
• Frameworks have been defined by both IEEE and 3GPP groups
to allow a hierarchical/centralized control of resources
managed by multiple RATs
– IEEE Heterogeneous Wireless Frameworks:
• 802.21 – Seamless mobility through networks based on different radio
access technologies
• 1900.4 – Co-ordinated network-device decision making to aid in the
optimization of radio resource usage, including spectrum access control
– 3GPP Heterogeneous Wireless Frameworks:
• Common Radio Resource Management, Joint Radio Resource Management,
Multi-access Radio Resource Management
– Local resource managers of different wireless technologies interact with a
centralized entity to jointly optimize the process of resource allocation
6
Motivation and Background (Contd.)
• From a user device perspective, numerous reconfigurable architectures
have been proposed that consist of flexible computing structure that
can be reconfigured to connect to various RATs
– Energy-efficient reconfigurable device architectures (MPSoC) are being
investigated based on various hardware components such as ASICs, FPGAs
and DSPs [ICCD ’11]
• A common design metric among all platforms is reducing energy
consumption that restricts both the capabilities of the device and the
design choices that are available
• Enough progress has been made at both the system architecture level
and at the user device level to make the implementation of a real
hetnet system feasible in the near future
Source:
[ICCD ’11] A. Hussien, A. Eltawil, R. Amin, J. Martin, “Energy Aware Task Mapping Algorithm for Heterogeneous MPSoC based Architectures,” Poster
Proceedings of IEEE International Conference on Computer Design, October 2011.
7
Thesis Statement
• Our research addresses the resource allocation problem and
practical implementation issues related to the creation of a hetnet
system, where multiple RATs collectively provide a unified wireless
network to a diverse set of users through co-ordination managed by a
centralized Global Resource Controller (GRC) to improve the efficiency
with which spectrum is utilized
– Characterize network efficiency in terms of four conflicting objectives:
(i) spectral efficiency (ii) instantaneous fairness (iii) long-term fairness (iv)
overall energy consumption
– Analyze spectral efficiency and energy consumption trade-offs involved with
different user device choices and operating assumptions (Phase I – Study 1)
– Analyze achievable trade-offs between all four conflicting network
performance objectives from a scheduling perspective (Phase I – Study 2)
– Analyze performance gains of a centralized solution compared to a
distributed solution while taking RAT-specific implementation details and
centralized control overhead into account (Phase II Study)
8
System Model
cUE
TCP/IP
Local Resource
Controller (LRC)
Radio Link
Aggregation
Battery
Bandwidth
Controller Controller
Location
Controller
Heterogeneous
Wireless
Network
AWS #1
Filters, modems, coding logic
Radio
Link 1
AWS #2
Radio
Link 1
FPGA resources
Radio
Link i
AWS #i
Radio
Link i
LTE
eNodeB
LTE
eNodeB
WiMax
BS
LTE
eNodeB
WiMAX
BS
S1-MME
Carrier’s
Backend
Global Resource
Controller (GRC)
WVLINK
Ingress/Egress
S1-U
Location
Services
S101
MME
S11
PDG
Mapping to 3GPP
Internet
9
WiMAX
BS
Network Efficiency Metrics
• Spectral Efficiency
– represented as the ratio of (data) rate allocated to each user
in the system to the total spectrum used:
•
Long-Term Fairness
– relates to the difference in rates allocated to each user over
long time-scales
– computed using Jain’s Fairness Index as follows:
10
Network Efficiency Metrics (Contd.)
• Instantaneous Fairness
– If support for real-time traffic is assumed, this metric is
computed using the proportion of users whose minimum data
rate requirements per scheduling interval are satisfied:
– If support for only best-effort traffic is assumed, this metric is
computed using Jain’s Fairness Index for each scheduling
interval:
11
Network Efficiency Metrics (Contd.)
• Overall Energy Consumption
– Hardware-based model: Assumes fixed energy consumption as
long as a radio is connected to a RAT
– Data Transfer-based model: Assumes radio can be operated in
‘deep sleep’ mode, where there is no energy consumption, when there
is no active transmission/reception
12
Research Phase I Summary Resource Allocation Problem
13
Research Overview
• Performed using high-level system modeling approach via MATLAB/AMPL
simulations
• Heuristic Algorithm Simulation Study
– Analyze achievable tradeoffs in terms of network efficiency measures of spectral
efficiency and energy consumption due to the benefits of network co-operation
based on different user device assumptions, network topologies and network
outages
– Algorithm accounts for spectral efficiency, instantaneous fairness and long-term
fairness measures by following a two-step scheduling approach
• Optimization-based Algorithm Simulation Study
– Analyze achievable tradeoffs in terms of all four network efficiency measures
using a utility function-based and a weighted sum approach for a limited set of
user device assumptions, network topologies and network outages
– Algorithm accounts for instantaneous fairness using admission control procedure;
the weights of the other three attributes computed using Analytic Hierarchy
Process
14
Results Summary
• A linear increase in spectral efficiency due to benefits of network co-operation
(multi-access network diversity) has an order of magnitude higher increase in
energy consumption based on current FPGA-based reconfigurable hardware
[ICCCN ’11]
• Network topology and various user device hardware assumptions (ASIC, FPGA)
have a significant impact on the spectral efficiency and energy consumption
tradeoffs [WCNC ’12]
– Exponential tradeoff for balanced network topology
– Linear tradeoff for unbalanced network topology
– ASIC-based hardware reduces energy consumption increase by almost 5x
• We show an increase of up to 56.7% in the multi-attribute utility measure for our
algorithm compared to other widely used algorithms such as Max-Sum Rate,
Max-Min Fairness, Proportional Fairness and Min Power [JSAC ’13]
Source:
[ICCCN ’11] J. Martin, R. Amin, A. Eltawil, A. Hussien, “Using Reconfigurable Devices to Maximize Spectral Efficiency in Future Heterogeneous Wireless
Systems,” Proceedings of IEEE International Conference on Computer Communications and Networks, Aug 2011.
[WCNC ’12] R. Amin, J. Martin, A. Eltawil, A. Hussien, “Spectral Efficiency and Energy Consumption Tradeoffs for Reconfigurable Devices in
Heterogeneous Wireless Systems,” Proceedings of IEEE Wireless Communications and Networking Conference, April 2012.
[JSAC ’13] R. Amin, J. Martin, J. Deaton, L. DaSilva, A. Hussien, A. Eltawil, “Balancing Spectral Efficiency, Energy Consumption, and Fairness in Future
15 on Selected Areas in Communications, May 2013.
Heterogeneous Wireless Systems with Reconfigurable Devices,” IEEE Journal
Research Phase II Study Practical Implementation Issues
16
Research Overview
• Performed using detailed protocol level simulator, ns-2,
to model each RAT and the management overhead
required for a hetnet system
• Greedy Sort-based Algorithm Simulation Study
– Analyze the performance gains for a centralized GRC solution
compared to a distributed solution using our four network
efficiency metrics
– Identify technical challenges associated with the
management/operation of a hetnet system
– Analyze the overhead caused by the centralized GRC solution
relative to the overall system (data) throughput
17
Simulation Description
• 2 WiMAX (802.16e) BSs, 6 Wi-Fi (802.11g) APs in 2 * 2 km2 area
• 100 users
- Each user can use any available RAT
- Three user movement patterns: (i) Linear Movement (ii) Random
Waypoint (Speed: 2 mph) (iii) Random Waypoint (Speed: [2, 20 mph])
18
System Assumptions
• Each RAT (Wi-Fi and WiMAX) uses an adaptive Modulation and Coding
Scheme (MCS)
• Wi-Fi MAC independently achieves max-min fairness scheduling objective
via DCF which employs CSMA/CA with binary exponential backoff algorithm
• WiMAX MAC independently achieves proportional fairness scheduling
objective via Deficit Weighted Round Robin scheduler
• The GRC operates on a five-second scheduling interval
• Each user device has an ASIC-based Wi-Fi and WiMAX radio; only one radio
can be used for a data connection at any given time (integral association)
• Infinitely backlogged downlink data traffic for each user device (Constant Bit
Rate traffic sent at 25 Mbps over TCP transport layer)
• Network re-association management implemented using IEEE 802.21’s
Media Independent Handover Function (MIHF)
19
Extended System Model
• MIHF implemented at the 2.5 Layer of the OSI stack
• cUE periodically sends link parameter report to the GRC
• Using link parameter report, GRC periodically computes cUE-to-RAT
association mapping
• Link Parameter Report Generation: (i) Periodic scanning (5-second basis)
(ii) Location-based
20
Greedy Sort-based Algorithms
• For each RAT, sort each user in descending order based on the user’s
maximum achievable data rate via the corresponding RAT
– In case of ties, put user with lowest achievable data rate via all connectivity options
first
• Greedily associate best unassociated user to a RAT in each association
decision round based on two metrics: achievable total system throughput
and lowest user throughput
• Use scheduling objective (Proportional Fairness or Max-Min Fairness) of
each RAT in each round to determine achievable total system throughput
and lowest user throughput metrics via following two propositions:
21
Greedy Sort-based Algorithms (Contd.)
• Max Throughput Algorithm
– Make decisions based on maximum achievable total system throughput
metric
– In case of ties, use maximum lowest user throughput metric
• Max Fairness Algorithm
– Make decisions based on maximum lowest user throughput
– In case of ties, use maximum achievable total system throughput metric
• Each of the two algorithms terminates when each user is
assigned to a RAT
22
Example (Max Throughput Algorithm)
Achievable Data
Rate
12
6
a
1
2
3
Sorted users for each BS
b
2
6
4
3
User
4
BS
4
1
BS a
Max-Min
Fair
BS b
Proportional
Fair
User 1
User 1
User 3
User 2
User 2
User 3
User 4
User 4
Round
#
Total System
Throughput
(Next assoc.
BS a)
Lowest User
Throughput
through BS a
Total System
Throughput
(Next assoc.
BS b)
Lowest User
Throughput
through BS b
Association
Decision
1
12
12
4
4
User 1 – BS a
2
8
4
15
3
User 2 – BS b
3
11
4
14.5
1
User 3 – BS b
4
8.5
3
14
0.333
User 4 – BS b
23
Example (Max Fairness Algorithm)
1
12
6
a
2
3
Sorted users for each BS
b
2
6
4
4
3
1
4
BS a
Max-Min
Fair
BS b
Proportional
Fair
User 1
User 1
User 3
User 2
User 2
User 3
User 4
User 4
Round
#
Total System
Throughput
(Next assoc.
BS a)
Lowest User
Throughput
through BS a
Total System
Throughput
(Next assoc.
BS b)
Lowest User
Throughput
through BS b
Association
Decision
1
12
12
4
4
User 1 – BS a
2
8
4
15
3
User 3 – BS a
3
7.2
2.4
11
3
User 2 – BS b
4
9
2
10
2
User 4 – BS b
24
Spectral Efficiency Results
• Both centralized algorithms (location based) outperform distributed solution
- Up to 99.2% increase in spectral efficiency (Linear movement pattern)
• Scan based solutions lead to unpredictable performance due to disruption of
active TCP data connections
25
Fairness Results
• Both instantaneous and long-term fairness metrics for Centralized Max Fairness
algorithm improve compared to distributed solution
- Up to 28.5% increase in instantaneous fairness metric (Random Waypoint
Same Speed)
• Both metrics deteriorate for Max Throughput algorithm compared to distributed
solution
26
Overall Energy Consumption Results
• Based on two components: (i) energy consumption per bit transmitted/received
and (ii) the number of handovers
- Dominated by the first component as handover costs of low energy
consuming ASIC-based hardware assumed
27
Energy Consumption Due to Handovers
• More accurate representation of increase in energy consumption that implements
periodic association computations via the use of a centralized controller
• Number of horizontal handovers (WiMAX-to-WiMAX) lead to a drastic increase in
energy consumption for centralized solutions
- Up to 794% increase (Linear movement pattern)
28
Spectral Efficiency vs. Energy
Consumption Trade-off
• Increase in energy consumption due to handovers outgrows increase in spectral
efficiency by a factor of approximately 5 to 14 for various movement patterns!!!
29
Overhead Results
• The overhead required by centralized solution based on IEEE 802.21 framework is
very manageable
- Lower than 4.7% of overall throughput for random movement patterns
- Up to 18.3% of overall throughput for linear topology which does not use
resources of all available RATs (rare case)
30
Conclusions
• Analyzed achievable tradeoffs in terms of network efficiency measures of
spectral efficiency and energy consumption due to the benefits of network
co-operation based on different user device assumptions, network
topologies and network outages
• Analyzed achievable tradeoffs in terms of all four network efficiency
measures using a utility function-based and a weighted sum approach for
a limited set of user device assumptions, network topologies and network
outages
• Analyzed performance gains for a centralized GRC solution compared to a
distributed solution using a detailed protocol-level simulator and IEEE
802.21 standards-based solution
• General trend in each study showed a higher increase in energy
consumption compared to the increase in spectral efficiency
-
Advanced power management schemes for user devices operating in a hetnet
system required
Resource allocation algorithms implemented at the GRC need to account for
energy consumption increase due to frequent re-associations
31
Thank You!
32