Transcript Distributed Topology Construction of Bluetooth Personal Area

Distributed Topology
Construction of Bluetooth
Personal Area Networks
Theodoros Salonidis, Pravin Bhagwat,
Leandros Tassiulas and Richard LaMaire
Objective of Study

Multiple channels in an ad-hoc network
Which subgroup of nodes share a common
channel and which act as forwarding nodes
 Bluetooth Topology Construction Protocol
Asynchronous distributed protocol for
constructing scatternets
Introduction to Bluetooth

Cable replacement technology
 Range is 10 meters so is targeted for
personal area networks
 Based on a frequency hopping physical
layer
Bluetooth Piconet

A group of devices
sharing a common
channel
 Piconet consists of
a Master and up to
7 slave devices
Bluetooth Piconet (contd.)

Within a piconet channel is shared using
TDD protocol
 Multiple piconets can co-exist using
different hopping sequences
 Piconets interconnected via bridge nodes to
form scatternets
 Bridge nodes are capable of timesharing
between multiple piconets
Scatternet
Scatternet with a shared Bridge node
Bluetooth Protocol Stack
Applications
IP
SDP
RFCOMM
Data
Audio
L2CAP
Link Manager
Baseband
RF
Functional Overview

Standby
Waiting to join a piconet
 Inquire
Ask about radios
to connect to
 Page
Connect to a specific radio
Transit
 Connected
Data
Device is active on a piconet
(master or slave)
 Park/Hold
Low power connected states
Standby
Inquiry
Page
Connected
Park
Hold
Sniff
Connection Setup
Inquiry - scan protocol
To learn about the
clock offset and
device address of
other nodes in
proximity
Addressing

Bluetooth device address (BD_ADDR)
– 48 bit IEEE MAC address
 Active Member address (AM_ADDR)
– 3 bits active slave address
– assigned by Master

Parked Member address (PM_ADDR)
– 8 bit parked slave address
Link Establishment in
Bluetooth

Inquiry procedure
“senders” discover and collect
neighborhood information
 Paging procedure
“senders” connect to receivers
 Frequency Synchronization delay
Time until sender transmits at the frequency
receiver is listening to
Asymmetric Protocol for Link
Formation

Random Backoff Delay
Receiver backs off for an amount of time
between 0 – 639.375 ms on receiving IAC packet
 Link formation delay
2FS + RB
Initial FS delay until the sender hits frequency
receiver is listening to and second FS delay after a
second IAC packet is received from sender
Bluetooth Asymmetric Link
Formation Protocol
Target
Initiator
1.Start
Inquiry state
IAC
2.Start
Inquiry state
3.Go to Sleep
IAC
6.Enter
Page state
4.Wake up
FHS
DAC
5.Respond and enter
Page Scan state
DAC
7.Connection
Established
FHS
DAC
7.Connection
Established
A Symmetric Protocol for Link
Formation

S
I
I
S
S
I
I
S
Forms connections in
an ad hoc manner
without any explicit
sender or receiver role
pre-assignment
 Nodes alternate
between the sender
(INQUIRY state) and
receiver (INQUIRY
SCAN state)
Connection Establishment
Protocol

Node has no initial knowledge about the
other devices in the room
 Protocol must guarantee a connected
scatternet
 Network setup delay should be minimized
to the end user
BTCP: A Distributed
Scatternet Formation Protocol

BTCP is based on a leader election process
 A bridge node may connect only two
piconets
 The resulting scatternet should consist of
minimum number of piconets
 Scatternet should be fully connected
 Two piconets share only one bridge
Phase I: Coordinator Election





Election of a coordinator node
Two nodes that discover each other compare their
VOTES variable
Node with larger VOTES variable is selected
winner
Loser tears down connection and enters PAGE
SCAN state
Winner node increases its VOTES by VOTES
(loser)
Phase II: Role Determination

Coordinator elected during Phase I has FHS
packets of all the nodes
 Coordinator decides role that each node
performs in scatternet
 Coordinator has a connectivity list set
(SLAVESLIST(x), BRIDGELIST(x))
 Temporary piconet is formed with the
coordinator as the Master
Phase III: Connection
Establishment

Each Master pages and connects to the
slaves and bridges
 Bridge node waits to be paged by a second
master and then sends a CONNECTED
notification
State Alternation Timeout
ALT_TIMEOUT

ALT_TIMEOUT expires
Node assumes it is the elected coordinator
 Large ALT_TIMEOUT
Node having won the competition continues to
alternate
 Small ALT_TIMEOUT
More than one nodes assume they are the
coordinator and result in a disconnected scatternet
Protocol Performance

Network connection setup delay and the
probability of protocol correctness
 A large ALT_TIMEOUT period will satisfy
the “correctness” condition with higher
probability but will cause a larger overhead
 A small ALT_TIMEOUT period will result
in more than one coordinators
Conclusions and Discussion

Nodes which are not within communication
range of each other
 Separate topology maintenance and
optimization protocol in order to take into
account mobility and nodes entering and
leaving the network
Meet King Harald Bluetooth
10th Century Viking
King
 King Harald united
Denmark and Norway.
Bluetooth of today
will unite the world of
computers and
telecom
