Transcript Towards Efficient and Robust Multihop Wireless Networks

Towards Efficient and Robust
Multihop Wireless Networks with
Real-Time Media-Rich
Application Support
Ph.D. Dissertation Proposal
Kimaya Mittal
Department of Computer Science
University of California, Santa Barbara
Introduction
• Popularity of wireless networks
– Homes, offices, universities, airports, malls
– Largely access-point-based at present
Access point
Internet
Wireless user
devices
Wireline
connectivity
Kimaya Mittal, Ph.D. Dissertation Proposal
Introduction
• Multihop wireless networks gaining attention
Wireline
connectivity
Internet
Stand-alone (Ad hoc)
Extending Internet connectivity (Mesh)
Kimaya Mittal, Ph.D. Dissertation Proposal
Introduction
• Multihop wireless networks
– Benefits:
•
•
•
•
Easy to deploy/extend
Self-configuring
Adaptive
Cost-effective
– Tremendous potential to be technology of
choice for ubiquitous Internet access
Kimaya Mittal, Ph.D. Dissertation Proposal
Introduction
• Popularity of real-time media-rich applications
– VoIP, video streaming, gaming, videoconferencing, media-rich messaging
• Must be supported by Internet access
technology
• Strict requirements
– Minimum required throughput
– Maximum tolerable delay and jitter
Kimaya Mittal, Ph.D. Dissertation Proposal
Our Vision
Multihop wireless networks
provide
ubiquitous Internet connectivity
and support diverse applications,
including real-time media-rich
applications, in an efficient and
robust manner
Our focus is on 802.11 and IP-based networks
Kimaya Mittal, Ph.D. Dissertation Proposal
Challenges
• Differences between wireless and wired networks
– Shared medium
• Nodes sharing medium may be unable to communicate
–
–
–
–
–
High link error rates
Significantly lower capacity
Resource-constrained devices
Mobility and dynamic topology
Easily accessible to malicious attackers
• Wired network solutions not always applicable
Kimaya Mittal, Ph.D. Dissertation Proposal
Wireless Transmission
Characteristics
V
R
T
W
P
Q
U
S
X
Kimaya Mittal, Ph.D. Dissertation Proposal
Wireless Transmission
Characteristics
Transmission range of P
V
R
T
W
P
Q
U
S
X
Kimaya Mittal, Ph.D. Dissertation Proposal
Wireless Transmission
Characteristics
Transmission range of P
V
R
T
W
P
Q
U
S
X
Carrier-sense range of P
Kimaya Mittal, Ph.D. Dissertation Proposal
Wireless Transmission
Characteristics
V
R
T
W
P
Q
U
S
Carrier-sense range of P
X
Carrier-sense range of Q
Kimaya Mittal, Ph.D. Dissertation Proposal
Our Focus
• Focus on addressing three key challenges
– Shared medium
– Significantly lower capacity
– Easily accessible to malicious attackers
• Motivation
– Very important for realization of our vision
– Previously-proposed solutions lacking
– Significant scope for improvement
Kimaya Mittal, Ph.D. Dissertation Proposal
Shared Medium
•
•
•
•
•
Medium shared with carrier-sense neighbors (CSN)
Not all CSN can directly communicate
Potentially different view of medium at each CSN
Medium management challenging
Challenge for realization of vision: How can
requirements of real-time media-rich applications be
met?
V
R
T
Transmission range
Carrier-sense range
Q W
P
U
S
Kimaya Mittal, Ph.D. Dissertation Proposal
X
Low Capacity
• Wireless bandwidth limited and shared
• Multiple hops along path contend for medium
access
– Significant capacity drop
• Hidden terminal and exposed terminal
problems
• Challenge for realization of vision: How can
diverse applications be efficiently supported?
Kimaya Mittal, Ph.D. Dissertation Proposal
Accessibility to Malicious
Attackers
• Any device within range can gain access
– Can become part of routing infrastructure
• Security vulnerabilities in several protocols
– Popular routing protocols (AODV, DSR)
• Can be exploited for non-optimal
performance and denial of service
– Compromise of the routing protocol can have farreaching effects on entire network
• Challenge for realization of vision: How can
network be made robust?
Kimaya Mittal, Ph.D. Dissertation Proposal
Dissertation Goals
• To contribute to the realization of our
vision in the following areas:
– Real-time media-rich application support
– Efficient utilization of capacity
– Robustness to malicious behavior
Kimaya Mittal, Ph.D. Dissertation Proposal
Contributions
• Real-time media-rich application support
– Perceptive Communication [Tridentcom 06]
– PRP and RRT: Protocols for intra-flow contention
calculation [Broadnets 04, MONET 06]
• Efficient utilization of capacity
– Improvement of 802.11 capacity utilization
(Remaining work)
– Leveraging mobility [Mobiquitous 04, WCMC
Journal (submitted)]
• Robustness to malicious behavior
– Analysis of security vulnerabilities of popular
routing protocols + secure routing protocol (ARAN)
[ICNP 02, JSAC 05]
Kimaya Mittal, Ph.D. Dissertation Proposal
VISION
Multihop wireless networks provide
ubiquitous Internet connectivity and
support diverse applications,
including real-time media-rich
applications, in an efficient and
robust manner
GOALS
Real-time
media-rich
application
support
Efficient
utilization of
capacity
CONTRIBUTIONS
Intra-flow contention
calculation
Leveraging
user
mobility
Authenticated
routing
Network Layer
Perceptive
communication
Improvement of 802.11
capacity utilization
MAC Layer
Kimaya Mittal, Ph.D. Dissertation Proposal
Robustness
to malicious
behavior
VISION
Multihop wireless networks provide
ubiquitous Internet connectivity and
support diverse applications,
including real-time media-rich
applications, in an efficient and
robust manner
GOALS
Real-time
media-rich
application
support
Efficient
utilization of
capacity
Robustness
to malicious
behavior
CONTRIBUTIONS
Intra-flow contention
calculation
Leveraging
user
mobility
Authenticated
routing
Network Layer
Perceptive
communication
Improvement of 802.11
capacity utilization
MAC Layer
Kimaya Mittal, Ph.D. Dissertation Proposal
Remaining
Work
Perceptive Communication:
Motivation
• Medium-related operations at a node
depend on/affect medium state at CSN
• Need for communication among CSN
V
R
T
Transmission range
P
Carrier-sense range
Q
W
U
S
Kimaya Mittal, Ph.D. Dissertation Proposal
X
Examples of Need for
Communication Among CSN
• Support of real-time media-rich
applications requires
– Admission control
– Prioritized medium access
• Need to share information such as
bandwidth consumption and priorities of
existing flows with CSN
Kimaya Mittal, Ph.D. Dissertation Proposal
Potential Approaches to
Communicate Among CSN
• Direct communication
– Impossible (CS range > Tx range)
• High-power transmission [Yang 03]
– More energy, less spatial reuse
• Multihop forwarding [Yang 03]
– Requires relay node
• Lower rate transmission code
– May not be supported, may not reach all CSN
Kimaya Mittal, Ph.D. Dissertation Proposal
Potential Approaches to
Communicate Among CSN
• Direct communication
CS range
– Impossible (CS range > Tx range)
Tx range
• High-power transmission [Yang 03]
R
T
– More energy, less spatial reuse
Q
P
U
• Multihop forwarding [Yang 03]
– Requires relay node
S
• Lower rate transmission code
– May not be supported, may not reach all CSN
Kimaya Mittal, Ph.D. Dissertation Proposal
Potential Approaches to
Communicate Among CSN
• Direct communication
CS range
– Impossible (CS range > Tx range)
Tx range
• High-power transmission [Yang 03]
R
T
– More energy, less spatial reuse
Q
P
U
• Multihop forwarding [Yang 03]
– Requires relay node
S
High power
• Lower rate transmission code
Tx range
– May not be supported, may not reach all CSN
Kimaya Mittal, Ph.D. Dissertation Proposal
Potential Approaches to
Communicate Among CSN
• Direct communication
CS range
– Impossible (CS range > Tx range)
Tx range
• High-power transmission [Yang 03]
R
T
– More energy, less spatial reuse
Q
P
U
• Multihop forwarding [Yang 03]
– Requires relay node
S
• Lower rate transmission code
– May not be supported, may not reach all CSN
Kimaya Mittal, Ph.D. Dissertation Proposal
Potential Approaches to
Communicate Among CSN
• Direct communication
CS range
– Impossible (CS range > Tx range)
Tx range
• High-power transmission [Yang 03]
T
R
– More energy, less spatial reuse
Q
P
U
• Multihop forwarding [Yang 03]
– Requires relay node
S
Lower rate
• Lower rate transmission code
Tx range
– May not be supported, may not reach all CSN
Kimaya Mittal, Ph.D. Dissertation Proposal
Perceptive Communication
• During transmission, change in carrier signal
perceived by CSN
• Certain characteristics can be detected
– Duration of transmission
– Silence between transmissions
• Information encoded in perceivable
characteristics
– Can be inferred by CSN by monitoring carrier
signal, packet need not be decoded
Kimaya Mittal, Ph.D. Dissertation Proposal
Detection of Perceptive
Characteristics
• Node records received signal strength
(RSS) continuously (i.e. in every time
slot)
• Tracks signal strength over time
• Identifies transmissions and silences
from this information
• Measures their durations
Kimaya Mittal, Ph.D. Dissertation Proposal
Detection of Transmission
Duration
• Idealized graph of
signal strength vs.
time
• Packet Y sensed, not
decoded
• Duration of packet Y
(Ty) perceived
• Information encoded
in and inferred from
Ty
RSS
RxThresh
CSThresh
X
Kimaya Mittal, Ph.D. Dissertation Proposal
Y
Ty
time
Detection of Silence Duration
• Every transmission
RSS
preceded by preframe
• Inter-frame space
perceived, duration
RxThresh
(Ts) detected
• Ts < Tdifs (inter-packet CSThresh
space)
• Information encoded
in and inferred from
Ts
Pre-frame
Inter-frame space
Packet
Inter-packet space
Y
Ts
Kimaya Mittal, Ph.D. Dissertation Proposal
Tdifs
Time
Application of Perceptive
Communication
• Application-specific codebook
– Maps transmission durations or inter-frame
space durations to meanings
• Examples
– Communication of identity through size of
Hello messages
• Size modified by appending ‘tail’
– Communication of packet priority through
duration of inter-frame space
Kimaya Mittal, Ph.D. Dissertation Proposal
Testbed Evaluation
• Motivation
– Do actual graphs of signal strength vs. time
resemble ideal graphs?
– How accurately can perceptive characteristics be
measured on wireless hardware?
• Implementation
– Prototype implementation on Mica2 mote
• Only platform with API for per-slot RSS
– RSSI sampling in alternate time slots
Kimaya Mittal, Ph.D. Dissertation Proposal
Simple Test Scenario
• Single transmitter
– Placed within few inches of receiver
– Transmits 100 packets
• 10 packets per second
• 20 bytes payload
• Single receiver
– Samples RSS in every time slot
– Processes RSS readings to identify transmissions
• Simplistic algorithm
– Infers payload size from detected transmission
duration
Kimaya Mittal, Ph.D. Dissertation Proposal
Plot of RSSI vs. Time
Ack
Data
Noise
Kimaya Mittal, Ph.D. Dissertation Proposal
Payload Size Detection in Simple
Test Scenario
Kimaya Mittal, Ph.D. Dissertation Proposal
Analysis
• All packets detected within +/- 2 bytes
• 2-byte detection error unavoidable
– RSSI sampling in alternate slots
– Time slots of receiver and transmitter not
perfectly synchronized
• In remaining results, detection within +/2 bytes considered correct
• Silence detection results similar
Kimaya Mittal, Ph.D. Dissertation Proposal
Experiment: Effect of
Received Signal Strength
• Experiment setup similar to simple test
scenario
• Magnitude of RSS varied by changing
transmit power of sender
Kimaya Mittal, Ph.D. Dissertation Proposal
Effect of Received Signal Strength
Kimaya Mittal, Ph.D. Dissertation Proposal
Perceptive Communication:
Conclusions
• Perceptive communication among CSN
feasible and effective on wireless
hardware
• Some error in detection unavoidable
– Should be accounted for in protocol design
• More sophisticated detection algorithm
can further improve accuracy
Kimaya Mittal, Ph.D. Dissertation Proposal
Perceptive Communication:
Impact
• Powerful mechanism
• Creates new possibilities for managing
wireless medium
• Several potential applications in
prioritized MAC, admission control,
bandwidth estimation, channel
assignment, power control, etc.
Kimaya Mittal, Ph.D. Dissertation Proposal
Determination of Intra-Flow
Contention: Motivation
• Network capacity limited, may not be
able to support all flows requesting
access
• Admission control necessary
• Need to estimate bandwidth
consumption of new flow for admission
control decision
• Non-trivial due to intra-flow contention
Kimaya Mittal, Ph.D. Dissertation Proposal
What is Intra-Flow
Contention?
• Nodes along a multihop path may lie within
each other’s carrier-sense range
• This leads to intra-flow contention
Carrier-sensing range
of node Y
Z
Y
W
Packets of flow F contend for medium
access at nodes W, X and Y
X
Flow F
Kimaya Mittal, Ph.D. Dissertation Proposal
What is Intra-Flow
Contention?
• Due to intra-flow contention, bandwidth
consumption of a flow at a node becomes a
multiple of that requested by the application
Carrier-sensing range
of node Y
Z
Y
W
X
Bandwidth consumed by flow F at
nodes W, X, Y each is 3 times the
single-hop bandwidth
Flow F
Kimaya Mittal, Ph.D. Dissertation Proposal
Contention Count
• Contention Count (CC) at a node =
Intersection of (set of carrier-sensing
neighbors) with (set of nodes on multihop
path) + 1
• Bandwidth consumption of flow =
CC x (single-hop bandwidth consumption)
• To estimate bandwidth consumption, CC
must be calculated
Kimaya Mittal, Ph.D. Dissertation Proposal
Calculation of Contention
Count
• Previous approaches
– Contention-Aware Admission Control (CACP)
[Yang et al. 03]
• High power transmissions to communicate with CSN
• Our approaches
– Pre-Reply Probe (PRP) and Route Request Tail
(RRT)
– Use our perceptive communication techniques
to communicate with CSN
– Integrated with reactive route discovery
Kimaya Mittal, Ph.D. Dissertation Proposal
Comparison of PRP/RRT with
CACP
• Main benefits
– Reduced energy consumption
– Reduced network overhead
• Main drawback
– Error in CC calculation when collisions
occur (No more than +/- 1 in our
simulations)
Kimaya Mittal, Ph.D. Dissertation Proposal
Remaining Work: Improving
Capacity Utilization of 802.11
• Hidden terminal and exposed terminal
problems well-known artifacts of CSMA
protocols
• Result in wasted network capacity
Kimaya Mittal, Ph.D. Dissertation Proposal
What are Hidden Terminals?
Carrier-sense range
P
Q
S
R
Nodes P and R
cannot carrier
sense each other
and transmit
simultaneously,
causing collisions
at one or both
receivers
Kimaya Mittal, Ph.D. Dissertation Proposal
What are Exposed Terminals?
Carrier-sense range
Q
S
P
R
Nodes P and R
cannot transmit
simultaneously due
to carrier sensing,
even though their
transmissions do
not mutually
interfere
Kimaya Mittal, Ph.D. Dissertation Proposal
Hidden and Exposed Terminals
• Hidden terminals waste capacity through
collisions
• Exposed terminals waste capacity through
missed opportunities to transmit
• Prevalence of hidden and exposed terminals
depends on topology and carrier sense range
– Large CS range => More exposed terminals
– Small CS range => More hidden terminals
– Inherent tradeoff
Kimaya Mittal, Ph.D. Dissertation Proposal
Alleviation of Hidden and Exposed
Terminals: Previous Work
• RTS/CTS
– Does not address exposed terminals
• Adjusting CS range
– Eliminating hidden terminals [Chakeres 04,
Fuemmeler 04]
– Reducing exposed terminals [Vasan 05]
– Achieving optimal balance [Zhai 06, Zhu
06]
Kimaya Mittal, Ph.D. Dissertation Proposal
Proposed Contribution
• Can a solution be designed to eliminate both
hidden and exposed terminals
simultaneously?
– Adjustment of CS range clearly not enough
• Proposed Approach
– Set CS range to sufficiently large value to
eliminate hidden terminals
– Modify protocol to discover and alleviate exposed
terminals
Kimaya Mittal, Ph.D. Dissertation Proposal
Challenges
• Detection of exposed terminals
– Distance-based assumptions naïve
• Keeping information up-to-date
– Interference characteristics may vary with
time
• Coordination of simultaneous
transmissions
Kimaya Mittal, Ph.D. Dissertation Proposal
Potential benefit
• Qualnet simulation of random topology of 20
nodes in a 600m x 600m area shows 90 pairs
of mutually exposed links
– This is without increasing CS range to avoid
hidden terminals
– Hardware limitations currently prevent testbed
evaluation
• Indicates potential benefit of proposed
approach
Kimaya Mittal, Ph.D. Dissertation Proposal
VISION
Multihop wireless networks
provide
ubiquitous Internet
connectivity and support
diverse applications,
including real-time media-rich
applications, in an efficient
and robust manner
GOALS
Real-time
Efficient
Robustness
media-rich
utilization of to malicious
application
capacity
behavior
support
CONTRIBUTIONS
Intra-flow contention
calculation
Leveraging
user
mobility
Authenticated
routing
Network Layer
Perceptive
communication
MAC Layer
Improvement of 802.11
capacity utilization
Conclusions
• Dissertation
contributes
towards solving
important
problems
towards
realization of our
vision
• Significantly
advances stateof-the-art
• Creates new
avenues for
further research
Kimaya Mittal, Ph.D. Dissertation Proposal
Thank You!
Questions/Comments?