Transcript PowerPoint Slides

Heterogeneity in
Multi-Hop Wireless Networks
Nitin H. Vaidya
University of Illinois at Urbana-Champaign
www.crhc.uiuc.edu/~nhv
© 2003 Vaidya
1
Summary


Heterogeneity is essential
Heterogeneity is beneficial
Research Agenda
 Develop protocols that exploit the heterogeneity
 Develop mechanisms to better evaluate wireless systems
Proof by example …
2
Heterogeneity

Many dimensions of heterogeneity:
Architecture
Physical capability of hosts
Higher layers
3
Architecture
Multi-hop wireless networks

Pure ad hoc networks

Hybrid networks
4
Pure Ad Hoc Networks


No “infrastructure”
All communication over (one or more) wireless hops
B
C
A
D
E
Z
Ad hoc connectivity
X
Y
5
Hybrid Networks

Infrastructure + Ad hoc connectivity
infrastructure
AP1
AP2
B
C
A
D
E
Z
Ad hoc connectivity
X
Y
6
Hybrid Networks

Infrastructure may include wireless relays
infrastructure
AP1
P
AP2
R
B
C
A
D
E
Z
Ad hoc connectivity
X
Y
7
Hybrid Networks

Heterogeneity
Some hosts connected to a backbone, most are not
Access points may have more processing capacity, energy
infrastructure
AP1
AP2
B
C
A
D
E
Z
Ad hoc connectivity
X
Y
8
Hybrid Networks

Heterogeneous wireless technologies
infrastructure
AP1
AP2
Type 1
(3G)
B
A
Type 2
(802.11)
X
C
D
E
Z
Y
9
Hybrid Networks

Heterogeneity is essential
Pure ad hoc or pure infrastructure networks inadequate for
many environments

Heterogeneity is beneficial …
10
Benefit over Pure Ad Hoc Networks

Infrastructure provides a frame of reference
Can assign approximate locations to the mobiles
– Provide location-aware services
– Reduce route discovery overhead
AP0
AP1
B
R1
A
AP2
AP3
D
R2
R3
A
11
Benefit over Pure Ad Hoc Networks

Infrastructure can reduce diameter of the network
Lower delay
Potentially greater per-flow throughput
infrastructure
AP1
P
AP2
R
B
C
A
D
E
Z
Ad hoc connectivity
X
Y
12
Infrastructure Facilitates New Trade-Offs
(hypothetical curves)
Poor Man’s Ad Hoc Network
Ad hoc-ness = K
User density distribution
affects the trade-off
13
Infrastructure Helps in Resource Allocation
Address Assignment

Unique IP addresses need to be assigned to hosts in
a network

DHCP used in traditional networks

Difficult to use DHCP in pure ad hoc networks

But Can also be deployed on the infrastructure in a
hybrid network
14
Infrastructure Helps in Resource Allocation
Address Assignment

Impossible to detect address duplication in networks
that can get partitioned
• Unbounded delays cause difficulty

Clusters of hosts may partition from the
infrastructure, rejoin, over time

Need a mechanism to assign unique addresses
despite partitions
• Impossible with unbounded message delays
15
If a problem cannot be solved
Change the problem
16
Weak Duplicate Address Detection
Packets from a given host to a given address
should be routed to the same destination,
despite duplication of the address

Achievable despite unbounded delay, but incurs
overhead

Infrastructure to the rescue: Use weak DAD only for
nodes partitioned from the infrastructure
 Can this extend to other resource allocation problems?
17
Benefit over Pure Infrastructure Networks

Ad hoc routing increases the “reach” of the
infrastructure

Connectivity can be traded with overhead
Example: Limit “ad hoc-ness” to K hops
18
Hybrid Networks: Research Issues
How to implement infrastructure?

How to deploy relays/access points?

What functionality should be given to relays and access
points?
• Density, distribution
• Should they cooperate? With each other? With mobiles?

Are relays an optimization or necessary components?

Should the spectrum be divided between the infrastructure
and ad hoc components?
19
Hybrid Networks: Research Issues
How to design protocols?

How to trade “complexity” with “performance” ?

How to design protocols that maximize “performance” for a
given complexity?
• Parameterize ad hoc-ness ?
• Power control: How should the heterogeneity affect power
control?
• MAC: Should the infrastructure do more work?
• Routing: Reduce overhead using infrastructure
• Transport: How to approach theoretical capacity bounds?
• How to deal with potentially unbounded delays?

The answers to the above questions are inter-dependent
• Power control, MAC, routing, transport protocols affect each
other’s behavior
• Cross-layer design needed
20
Heterogeneity

Many dimensions of heterogeneity:
Architecture
Physical capability of hosts
–
–
–
–
Antennas
Topology control mechanisms
Processing capability
Energy availability
Higher layers
21
Antenna Capabilities

“Fixed beam” antennas prevalent on mobile devices
Omnidirectional antennas

“Movable beam” antennas likely to become more
prevalent over time
Switched, steered, adaptive, smart …
– Can form narrow beamforms, which may be changed over time
Re-configurable antennas
– Beamforms can be changed over time by reconfiguring the
antenna

Different devices may incorporate different antennas
22
Antenna Heterogeneity
All antennas are not made equal

Beamforms: Only directional, or omni too?

Timescale: Can beams be “moved” at packet
timescales?

Single beam or multiple beams?

Variations with time?
23
Antenna Capabilities

Protocols designed for omnidirectional (fixed beam)
antennas inadequate with movable beam antennas

State of the art: MAC Protocols designed for specific
antenna capabilities

Need “antenna-adaptive” MAC and routing protocols
that allow for antenna heterogeneity
24
Antenna Heterogeneity

Heterogeneity is essential
Enforcing homogeneity will limit benefits from antenna
improvements

Heterogeneity is beneficial
Devices can employ best antennas that they can “afford”
– Device constraints: energy, processing, size, weight, $$
– Access points may use more capable antenna than mobiles
Antenna-adaptive protocols allow separation of the antenna
as a “layer” in the protocol stack
25
Antenna Heterogeneity: Research Challenge
How to design “antenna-adaptive” protocols ?

Need to develop suitable antenna abstractions that
span a range of antenna designs

Forces us to think about essential characteristics of
antennas
– Example: Variability of beam patterns a more
fundamental property than directionality
26
Evaluation of Wireless Networks
27
Capacity

Capacity analysis:
• Capacity results useful to determine the gap between
actual performance and the best case scenario
• Significant progress in recent years
• Need further work to model heterogeneous environments
28
Evaluation of Wireless Protocols

Benchmarks: Need benchmarks for comparison of
different protocols
• State of the art: Toy benchmarks, almost no real data (for
evaluating multi-hop wireless networks)

Simulations
• Commonly used simulation models are poor
• Need better physical layer models accessible to protocol
community
29
Evaluation of Wireless Protocols

Experimentation:
“Full scale” experiments not always practical
Need mechanisms to build and experimentally evaluate
“scaled models” of the network
–
–
–
–
Physical dimensions
Mobility
Number of hosts
Traffic density
How to “scale down” the network, and still maintain
essential behaviors?
30
Conclusions
31
Conclusions

Heterogeneity essential, and beneficial

Heterogeneity  Complexity ?
Not necessarily
Thinking about heterogeneity useful in arriving at better abstractions

Need protocols that can exploit heterogeneity

Need approaches for realistic comparative evaluation of
protocols
32
Thanks!
33