Transcript Why 802.15.3

Third-Party Handshake Protocol for
Efficient Peer Discovery
and Route Optimization in
IEEE 802.15.3 WPANs
Authors:
Zhanping Yin * Victor C. M. Leung
Published:
ACM/ MONET 2006
Presented by:
Gautam S. Thakur
Presentation Topics
1. Definitions and Terminologies
2. Knowing IEEE 802.15.3
3. Current Standards for Peer Discovery in IEEE
802.15.3
4. Issues and roadblocks
1.
2.
Peer Discovery and connectivity
Ad hoc routing vs. MAC Layer forwarding
5. Proposed Peer Discovery protocol with forwarding
route optimization (FRO)
6. Performance Evaluations
1.
2.
Intra-piconet no connection probability
Peer discovery delay analysis
7. Simulations and numerical results
8. Conclusion and future goals
WPAN
• A WPAN (wireless personal area network) is a
personal area network - a network for
interconnecting devices centered around an
individual person's workspace
• A very short range ~10 mtrs. E.g. Bluetooth
• Proposed operating frequencies are around
2.4 GHz in digital modes.
• The objective is to facilitate seamless
operation among home or business devices
and systems.
Ultra-Wideband
• A physical layer technology
• For, short distance communication with high
data rate and short transmission range.
• Lower power requirement and pulsed data
• UWB transmission over extremely wide
unlicensed radio spectrum  3.1 – 10.6 GHz.
• Over results in
– Less interference
– Wire-like performance for indoor wireless
environment.
Presentation Topics
1. Definitions and Terminologies
2. Knowing IEEE 802.15.3
3. Current Standards for Peer Discovery in IEEE
802.15.3
4. Issues and roadblocks
1.
2.
Peer Discovery and connectivity
Ad hoc routing vs. MAC Layer forwarding
5. Proposed Peer Discovery protocol with forwarding
route optimization (FRO)
6. Performance Evaluations
1.
2.
Intra-piconet no connection probability
Peer discovery delay analysis
7. Simulations and numerical results
8. Conclusion and future goals
Overview of 802.15.3
• Why 802.15.3 ?
• The 802.15.3 Wireless Space
• 802.15.3 Overview and Components
Overview of 802.15.3
[Why 802.15.3 ?]
• Motivated by the increasing demand of wireless
communications with
–
–
–
–
–
Ubiquitous network connectivity
Low cost and low power consumption -> WPAN
High data rate(HDR)
Quality of Service(QoS) support
Comparison with other short to medium range wireless
technologies
• Wireless LAN (WLAN)
– High cost and power consumption, no hard QoS guarantee
• WPANs-Bluetooth (802.15.1) and ZigBee(802.15.4)
– Data rate too low
• Applications of 802.15.3
– Virtual wireless multimedia connectivity
• Video/audio distribution
– High speed data transfer
Overview of 802.15.3
[ 802.15.3 = Wireless Multimedia ]
Overview of 802.15.3
[ The 802 Wireless Space ]
IEEE 802.15.3 Overview
• High date rate and low
power
• Mainly works within a
piconet with dynamic
DEV membership
• Ad hoc topology with
centralized control by
the PNC
• Connection oriented
peer-to-peer
communications
• Support for multimedia
quality of service(QoS)
• Multiple power
management modes
• Security
Formation of an 802.15.3 piconet
• The basic component
is the DEV
– One DEV is required to
assume the role of the
piconet coordinator
(PNC) of the piconet.
– The PNC provides the
basic timing sync for the
piconet with the beacon.
– Additionally, the PNC
manages the quality of
service (QoS)
requirements, power
save modes and access
control to the piconet.
Formation of an 802.15.3 piconet (2)
• PNC supports ad
hoc peer-to-peer
connections
• PNC provides
timing for
synchronization of
DEVs within the
piconet, performs
admission control,
allocates network
resources etc
Formation of a Piconet (3)
• All DEVs within radio coverage of the PNC
can then associate with it to form a piconet.
• Then starts the peer discovery.
• Some DEV pairs in the piconet may be out of
range of each other, and as a result, direct
peer-to-peer connection is unavailable
between them. This results in network layer
discovery methods
Superframe format
• Timing and data transmissions in the piconet
are based on the superframe
• The superframe has three parts
– Beacon: Control information, Allocates CTA,
Synchronization
– Contention Access Period (CAP): via CSMA/CA, file xfer
– Channel Time Allocation Period (CTAP)
Presentation Topics
1. Definitions and Terminologies
2. Knowing IEEE 802.15.3
3. Current Standards for Peer Discovery in IEEE
802.15.3
4. Issues and roadblocks
1.
2.
Peer Discovery and connectivity
Ad hoc routing vs. MAC Layer forwarding
5. Proposed Peer Discovery protocol with forwarding
route optimization (FRO)
6. Performance Evaluations
1.
2.
Intra-piconet no connection probability
Peer discovery delay analysis
7. Simulations and numerical results
8. Conclusion and future goals
Peer discovery and connectivity issue
• An 802.15.3 piconet supports ad hoc
communications between peer DEVs.
• Peer discovery is crucial to its operation.
• The DEVs shall be able to obtain information
about the services and capabilities of other
DEVs in the piconet at any time by
information discovery commands.
• Peer information is needed before a source
DEV can send any data to a destination DEV,
or generate channel time requests (CTRq) to
the PNC.
1
2
5
3
4
6
9
7
8
10
13
11
14
12
15
PNC
Src_DEV
Dest_DEV
PNC Info. Request command
SIFS
Imm-ACK
SIFS
PNC Information command
SIFS
Imm-ACK
SIFS
Probe Request Command
SIFS
Imm-ACK
SIFS
Probe Response Command
SIFS
Imm-ACK
RIFS
1. NOT receive the Imm-Ack
2. Cannot distinguish out-of-range
transmission and collision
3. Perform backoff retransmission
for collision repeatedly
DEV – 1
PNC
Dev 2 is outside the
range of Dev1 and
vise-versa
1. NOT receive Probe Request
command
DEV - 2
Existing Issues with IEEE 802.15.3
•
•
•
•
•
•
•
Peer discovery is crucial to piconet
operations.
Standard peer discovery is
unreliable and leads to substantial
delays for unreachable DEV pairs
Full piconet connectivity is not
guaranteed with only direct peerto-peer communications
The standard 802.15.3 MAC does
not take advantage of the unique
ranging capabilities enabled by
UWB
Connections are in peer-to-peer
manner without consider of
possible route optimizations
MAC modeling and performance
evaluation
Stream time scheduling methods
not defined in the standard
•
•
•
DEV_1 cannot communicate with
DEV_4 in peer-to-peer manner
For traffic between DEV_1 and
DEV_3, is it better to forward via
PNC than the direct connection?
What is the optimal path and data
rate between DEV_3 and DEV_5?
Using network layer routing
• Each hop request a
CTA slot seperately.
• PNC treat each hop as
independent traffic
stream
• Effect: Failure in an
intermediate hop
breaks the
connections, but PNC
assumes that an
independent stream is
terminated. Keeps
allocating CTAs for
other hops untill it is
eventually notified by
all participating DEV
Using MAC layer forwarding
• With explicit MAC
layer forwarding,
PNC knows that
these hops belongs
to one connection.
• Better adjusting
downstream and
upstream CTAs.
• Effect: reroute the
traffic is the
intermediate node
fails, and releasing
all CTAs if source
of destination
terminates.
Some Observations
• Peer discover is essential
to piconet operations
and communication
between DEVs
• Full piconet connectivity
cannot be guaranteed
• Some DEV pairs may be
out of range of each
other
• Mac layer routing fails
but is better then IP
routing.
• Remember, 802.15.3 has
centralized topology. So
what ??
• Using PNC, any devices
is two-hop count away
only.
• Can use the central
management capability
to discover simpler and
less costly MAC route
Proposed peer discovery protocol
with forwarding route optimization
• The PNC can always act as a first hop to
connect non-intersecting range DEVs
• However, a betterment can be done in the
frame forwarding by choosing another
DEV closer in distance to the source and
destination to forward the frame.
• All routes are limited to two hops only.
Algorithm
• If the Desti_DEV is reachable, sending PNC
Information Request and Response exchange is
redundant.
• So, Src_DEV send Probe Request command to the
Dest_DEV.
• If Dest_DEV receives the command, it returns an
Imm-ACK after a SIFS and then the Probe Response
command as in standard protocol operations.
• At the same time, the third party, i.e., the PNC, shall
actively monitor the frame exchange.
• Upon receiving a Probe Request, the PNC checks the
destination ID (Dest_ID) field in the MAC header.
Algorithm (2)
• If the Dest_ID is not associated in the piconet, the PNC
send an Imm-ACK to the Src_DEV after SIFS, followed
by a PNC Information command with an empty
Information Element (IE) to notify the source that
destination does not exist.
• Otherwise, instead of ignoring the Probe Request frame,
the PNC waits for the Imm-ACK from the destination
DEV.
• If no Imm-ACK arrives after a backoff inter-frame space
(BIFS), which is the sum of a SIFS and a clear channel
assessment detect time (CCADetectTime), the PNC
realizes that the destination DEV cannot hear the source.
• The PNC then immediately send an Imm-ACK to the
source, followed by a PNC Information command with
the route information. (an optimized route information in
sent)
SRC_DEV send Probe
Request command to
DEST_DEV & PNC listens
SIFS
Imm-ACK
Probe Response command
SIFS (Imm-ACK)
PNC also listen
DEST_DEV
hears?
YES
DEST_DEV
responds
No
No
DEST_DEV
ID
Present?
Yes, Timeout (BIFS)
Send Imm-ACK & route
information to source
Yes and
DEST_DEV sent Imm-ACK
Do Nothing, monitor if
DEST_DEV crash.
Forward the data to
the router node
Algorithm (3)
[Route calculation]
• Most wireless networks today employ a multirate PHY (e.g., UWB in 802.15.3a) that
supports a set of data rate dependent
modulation/coding parameters.
• Due to the extremely low power consumption
requirement of WPAN devices, the achievable
data rate drops dramatically when the
distance increases.
• The data rate can be modeled as a discrete
function of transmission distance d between
two DEVs:
Algorithm (3)
Rate(d )  Si;
Ri  1  d  Ri ;1  i  m
where, Rm  1  0, Ri is the transmiss ion range of rate Si;
and S 1 and Sm are the minimum and maximum data
rates, respective ly. If d is greater th an R1, then Rate(d)  0
and the DEVs have no connectivi ty
Algorithm (4)
• Since the PNC can monitor all commands exchanged
during the CAP, it can learn the data rates between
reachable DEV pairs and store them in an n x n rate
matrix (RM), where
• n is the total number of DEVs within the piconet. DEV
is assigned a unique DEV_ID in the piconet
RM ij is the link rate based on the current informatio n
obtained from the commands exchanged between
DEVi and DEVj. RM ij  0 if DEVi and DEVj
are out of range or the rate informatio n is
not available yet, and RM ij   if i  j.
Algorithm (5)
• All DEVs transmit with the maximum
allowable power when sending data. Since the
wireless links are symmetric in nature, clearly
RMij = RMji.
• Based on the current rate information stored
in RM, for an unreachable pair DEVi and
DEVj, the PNC can determine the optimal
(two-hop) route that has the minimum
transmission time, i.e., the best route employs
DEVk for MAC layer forwarding, where k
minimizes:
Algorithm (6)
1
1
min(

)
RM ik RMkj
k[ 0 , n 1]
• Alleviates the traffic load on the PNC
• Discovers a current optimal two-hop MAC layer
forwarding path given by existing rate information
without introducing any extra overhead
• If the connection is broken, the PNC can
immediately reroute the traffic to a current
optimal path, or terminate the connection by deallocating all corresponding CTAs.
Discussion
• Original case:
Causes
retransmission
• 3PHP: data sent via
2-hop route if
PNC_ID exists
Dest_ID
Dest_ID
• Normal Transmission (Imm_Ack)
• Normal Transmission (Imm_Ack)
XXX FRAME LOST XXXX
PNC_ID
• Causes retransmission
• Sent Via 2–hop route (Imm_Ack)
PNC
Src_DEV
PNC Info. Request command
Probe Request Command
BIFS
Imm-ACK
SIFS
PNC Information command with Route Info.
Imm-ACK
RIFS
Dest_DEV
SIFS
3PHP-Node
DEV – 1
DEV - 2
PNC
Observations
• With 3PHP, peer discovery requires only one
round of frame exchange.
• Fully utilized the broadcast nature,
centralized control, ad-hoc communication,
and efficient peer discovery.
• Save the futile back-off retransmission for
unreachable destination.
• Guaranteed full piconet connectivity. (no
network layer routing required)
• On demand routing
• More then BIFS waiting. (include RIFS) Conclusion
Performance Evaluations
[Intra-piconet no connection probability]
• Intra-piconet no
connection
probability
• Common Overlap
Area function
COLA(R, r, x):
Represent the
intersection of two
circles with radii R
and r (r e R),
respectively, which
centers are
separated by
distance x
Performance Evaluations (2)
[Intra-piconet no connection probability]
Performance Evaluations (3)
[Intra-piconet no connection probability]
• The probability of no direct connection
between two DEVs in a piconet is
Performance Evaluations (4)
[Peer Discovery delay analysis]
•
# of Frame Transmission
•
•
Expected
Contention Time
•
Expected Packet
Delay
Performance Evaluations (5)
[Peer Discovery delay analysis]
•
Expected routing
failure probability
• Expected successful peer discovery
delays are given by
Simulation and Numerical Results
• No connection probability as a function of
coverage range ratio
Simulation and Numerical Results (2)
• Peer discovery delay vs. conditional
collision probability
Simulation and Numerical Results (3)
• Piconet peer discovery time vs. coverage
range ratio
Simulation and Numerical Results (4)
• Piconet peer discovery failure probability
with standard method
Simulation and Numerical Results (5)
• Two-hop forwarding route optimization
ratio vs. piconet radius
Simulation and Numerical Results (6)
• Expected data between directly unreachable
pairs in piconets with 20 DEVs
Conclusion
• Underlying fact: peer-to-peer data delivery in
802.15.3 WPANs
• Existing MAC layer peer discovery methods
cannot guarantee full connectivity between
DEVs within a piconet through direct peerto-peer connections if the piconet operates
with a radius larger than half of the
maximum transmission distance. (~ 41.3%)
• If Mac fails, use the expensive network layer
routing.
Conclusion (2)
• Used the central control topology
• Routing in 2-hop with single round of
control frame exchange
• 3PHP achieves 25– 37% faster peer
discovery time over the standard MAC
• Route optimization algorithm in the PNC
to provide the best MAC layer forwarding
routes by self-learning the available rate
information between DEVs.
References
•
IEEE Standard 802.15.3, “Wireless medium access control (MAC) and physical
layer (PHY) specifications for high rate wireless personal area networks
(WPANs),”Sept. 2003.
•
Z. Yin and V.C.M. Leung, “Third-Party Handshake Protocol for Efficient Peer
Discovery in IEEE 802.15.3 WPANs,”in Proc. IEEE BroadNets2005, Boston, MA,
Oct. 2005.
•
Z. Yin and V.C.M. Leung, “Third-Party Handshake Protocol for Efficient Peer
Discovery and Route Optimization in IEEE 802.15.3WPANs,”accepted for
publication in ACM/KluwerJ. Mobile Networks and Applications, Nov. 2005.
•
Z. Yin and V.C.M. Leung, “Connection Data Rate Optimization of IEEE 802.15.3
Scatternetswith Multi-rate Carriers,”IEEE ICC’06, Istanbul, Turkey, June 2006.
•
Zhanping Yin and Victor C.M. Leung, “Introduction to IEEE 802.15.3 High Rate
Wireless Personal Area Network (WPAN)”, Electrical and Computer Engineering
University of British Columbia
Thank You
