bluetooth-topology2.pdf

Abstract– In recent years, wireless ad hoc networks have been
a growing area of research. While there has been considerable
research on the topic of routing in such networks, the topic of
topology creation has not received due attention. This is because
almost all ad hoc networks to date have been built on top of a
single channel, broadcast based wireless media, such as 802.11 or
IR LANs. For such networks the distance relationship between
the nodes implicitly (and uniquely) determines the topology of the
ad hoc network.

Bluetooth is a promising new wireless technology, which
enables portable devices to form short-range wireless ad hoc
networks and is based on a frequency hopping physical layer.
This fact implies that hosts are not able to communicate unless
they have previously discovered each other by synchronizing their
frequency hopping patterns. Thus, even if all nodes are within
direct communication range of each other, only those nodes which
are synchronized with the transmitter can hear the transmission.
To support any-to-any communication, nodes must be
synchronized so that the pairs of nodes (which can communicate
with each other) together form a connected graph.

Using Bluetooth as an example, this paper first provides deeper
insights into the issue to link establishment in frequency hopping
wireless systems. It then introduces the Bluetooth Topology
Costruction Protocol (BTCP), an asynchronous distributed
protocol for constructing scatternets which starts with nodes that
have no knowledge of their surroundings and terminates with the
formation of a connected network satisfying all connectivity
constraints posed by the Bluetooth technology. To the best of our
knowledge, the work presented in this paper is the first attempt at
building Bluetooth scatternets using distributed logic and is quite
“practical” in the sense that it can be implemented using the
communication primitives offered by the Bluetooth 1.0
specifications.

Index terms—Frequency hopping, Bluetooth, topology

construction, scatternet.

1. INTRODUCTION
An ad hoc network is a wireless network formed by nodes

that cooperate with each other to forward packets in the
network. Almost all experimental ad hoc networks to date have
been built on top of single channel, broadcast based 802.11
wireless LANs or IR LANs. In such networks, all nodes within
direct communication range of each other share a common
channel using a CSMA style MAC protocol. In addition,
multi-hop routing is used as a means for forwarding packets
beyond the communication range of the source’s transmitter.
Since a single channel is used throughout the network, the

This work is supported by an IBM University Partnership

Award.

topology of the ad hoc network is implicitly (and uniquely)
determined by distance relationship among the participating
nodes.

This paper is aimed at addressing a new problem which
arises when multiple channels are available for communication
in an ad hoc network. The problem is that of determining
which subgroup of nodes should share a common channel and
which nodes should act as relays and forward traffic from one
channel to another. The channel assignment should be done so
that all constraints posed by the underlying physical layer are
satisfied while ensuring that the resultant graph formed by all
nodes is connected.

We address an instance of the above problem which occurs
in Bluetooth based ad hoc networks, known as scatternets [9].
Bluetooth is a promising new technology which is aimed at
supporting wireless connectivity among cell phones, headsets,
PDAs, digital cameras, and laptop computers. Initially, the
technology will be used as a replacement for cables, but in due
course of time solutions for point-to-multipoint and multi-hop
networking over Bluetooth will evolve.

Bluetooth is a frequency hopping system which defines
multiple channels for communication (each channel defined by
a different frequency hopping sequence). A group of devices
sharing a common channel is called a piconet. Each piconet
has a master unit which selects a frequency hopping sequence
for the piconet and controls the access to the channel. Other
participants of the group known as slave units are
synchronized to the hopping sequence of the piconet master.
Within a piconet, the channel is shared using a slotted time
division duplex (TDD) protocol where a master uses a polling
style protocol to allocate time-slots to slave nodes. The
maximum number of slaves that can simultaneously be active
in a piconet is seven.

Multiple piconets can co-exist in a common area because
each piconet uses a different hopping sequence. Piconets can
also be interconnected via bridge nodes to form a bigger ad
hoc network known as a scatternet. Bridge nodes are capable
of timesharing between multiple piconets, receiving data from
one piconet and forwarding it to another. There is no
restriction on the role a bridge node can play in each piconet it
participates in. A bridge can be a master in one piconet and
slave in another (termed as M/S bridge) or a slave in all
piconets (termed as S/S bridge).

It is possible to organize a given set of Bluetooth devices in
many different configurations. Figures 1b and 1c show two
example configurations in which nodes in a Bluetooth network
can be arranged. All nodes are assumed to be in radio
proximity of each other. Fig. 1b shows an example in which

Theodoros Salonidis1, Pravin Bhagwat2, Leandros Tassiulas1, and Richard LaMaire3

Distributed Topology Construction of Bluetooth Personal Area Networks

[email protected], [email protected], [email protected], [email protected]

1Electrical and Computer Engineering Department, University of Maryland at College Park.
2AT&T-Labs Research, Florham Park NJ.

3IBM T.J. Watson Research Center, Hawthorne NY.

all nodes are part of a single piconet1. Figure 1c illustrates
another configuration in which node A is master of piconet 1,
node E is master of piconet 3, node B is an M/S bridge (master
of piconet 2 and a slave of piconet 1), node D is a slave of
piconet 1 and node C is an S/S bridge (slave in piconets 2 and
3). In contrast to the above two configurations the node
interconnection topology in a single channel system will be a
complete graph (Fig. 1a) since all nodes will hear each other’s
transmission.

Figure 1: (a) Single channel model. (b),(c) Different
configurations according to the Bluetooth multiple channel

model.

Given a collection of Bluetooth devices, an explicit

topology construction protocol is needed for forming piconets,
assigning slaves to piconets, and interconnecting them via
bridges such that the resulting scatternet is connected. Such a
protocol should be asynchronous, totally distributed and nodes
should start with no information about their surroundings. The
problem of constructing distributed self-organizing networks
has been addressed in the past ([4][5][6][10]), but all the
efforts so far were aimed at solving the problem by assuming a
single broadcast channel and a CSMA style MAC protocol.
The problem is significantly harder for frequency hopping
based wireless systems as will be evident in the later
discussion.

This paper is a first attempt to address the topology
construction problem in the multiple FH channel setting
imposed by the Bluetooth technology. In to solve it, we
design our protocol in a bottom-up fashion: First, in section 2
we examine the wireless link provided by Bluetooth by
presenting the asymmetric “sender-receiver” point to point link
establishment protocol as defined in the Bluetooth
specifications. In section 3 we enhance this protocol by
proposing a symmetric variant of the link establishment
protocol where two devices alternate independently between
the “sender” and “receiver” state until they discover and
connect to each other. Such a protocol is necessary for
establishing a connection between a pair of identical devices
or in situations when any external means for selecting initial
device states are not available. Section 4 introduces the
Bluetooth Topology Construction Protocol (BTCP), which is
an asynchronous distributed connection establishment protocol
that extends the point to point symmetric protocol to the case
of many nodes. This protocol is based on a leader election

1 Note there is no edge among slave nodes since slaves

cannot hear each other’s transmission.

process where each node uses a timeout to independently
decide about the leader election termination. The timeout
delay factor introduces a correctness-delay tradeoff of the
network formation. By using the delay analysis of section 3 we
show in section 5 how to best choose the protocol parameters
in to maximize the probability of forming a connected
scatternet while minimizing delays. Finally, section 6 provides
a future work discussion and conclusions.

2. LINK ESTABLISHMENT IN BLUETOOTH : BACKGROUND

The Bluetooth Baseband Specification [1] defines the

Bluetooth point to point connection establishment as a two-
step procedure. First neighborhood information is collected
through the Inquiry Procedure. The Paging procedure is
subsequently used to establish the connections between
neighboring devices. Both the Inquiry and Paging procedures
are asymmetric processes; they involve two types of nodes
(which we call senders and receivers) each performing
different actions. During Inquiry, “senders” discover and
collect neighborhood information provided by “receivers”.
During Paging, “senders” connect to “receivers” discovered
during a previous inquiry procedure.

During the inquiry or paging procedure, although senders
and receivers use the same (inquiry or paging) frequency
hopping sequence2, it is likely that they will be out of phase
since each unit starts at a different hop frequency derived from
its local clock value. This (unavoidable) phase difference
introduces a phase uncertainty among the devices
participating in the procedure. To overcome this phase
uncertainty, senders and receivers hop at different speeds. A
receiver hops at a slow rate over the common frequency
pattern listening on each hop for sender messages and the
sender transmits at a much higher rate listening in between
transmissions for an answer, in hope of discovering the
frequency a receiver is currently listening to. Given two units,
one operating as a sender and the other as a receiver, the term
Frequency Synchronization delay (or FS delay) refers to the
time until the sender transmits at the frequency the receiver is
currently listening on3.

Even if the two procedures have the same synchronization
mechanism, a difference is that during the paging procedure
the sender tries to bypass the FS delay by estimating the phase
of the receiver. If paging is performed directly after the Inquiry
procedure, the sender has acquired the clock value of the
receiver unit and can use it to determine its phase and connect
to it instantaneously.

The functional difference between the Inquiry and Paging
Procedures lies in the use of a universal FH sequence in the
first and a common point to point FH sequence in the second.

2 Nf, the number of frequencies in the inquiry or page

hopping set, is equal to 32 for systems operating in Europe and
US and 16 for systems operating in Japan, Spain and France.

3 The sender can cover the entire inquiry hopping frequency set in
time Tcoverage = Nf x 625us which is 10ms (20ms) for the 16 (32) hop
system.

A

B

C D

E

A

B

C D

E

A

B

C D

E

Piconet 3

Piconet 1

Piconet 2

(a) (b) (c)

Using a universal inquiry hopping sequence, a sender node
effectively “broadcasts” an Inquiry Access Code (IAC) packet
that can be heard only by receiver nodes that listen for such a
packet. During the paging procedure, by using the receiver’s
page hopping sequence a sender node initiates connection
establishment by effectively “unicasting” a Device Access
Code (DAC) packet that can be heard only by the
corresponding receiver device. Thus the Inquiry Procedure
involves many units, where a sender can discover more than
one receivers while the paging procedure involves only two
units, where a sender pages and connects to a specific receiver.

2.1. The Bluetooth Asymmetric protocol for link formation

According to the Bluetooth Baseband specification the

protocol starts by the sender starting in the INQUIRY state and
the receiver in the INQUIRY SCAN state. As was described in
the previous section there is an initial FS delay until the sender
hits the frequency the receiver is listening to. Upon receiving
the IAC packet, the receiver backs off for an amount of time
that is uniformly distributed between 0 and 639.375ms. This
happens in to prevent the contention problem that would
arise if there were two receivers listening on the same hop
frequency. If both of them responded immediately, the
response message would get garbled and the sender would not
receive it. We call the time while the receiver backs off the
Random Backoff delay (or RB delay). When the receiver
unit wakes up, it starts listening again at the hop it was
listening to before backing off. After a second FS delay (same
as the first one), a second IAC packet is received from the
sender. Then the receiver sends back to the sender an FHS
packet that contains:

1. The receiver’s address: This is used by the sender to

derive the DAC of the receiver and the page hopping
sequence it will use later in to page the receiver.

2. The receiver’s clock value: This is used to estimate the
phase of the receiver and thus eliminate the FS delay
during the paging procedure that follows.

The timing diagram in Figure 2, summarizes the point to

point connection establishment procedure between the two
units. The dashed arrows denote events on each unit’s
timeline and each event is numbered in the it happens
during the connection establishment procedure. The timing
diagram shows that the receiver enters the PAGE SCAN state
after sending the inquiry response FHS packet to the sender.
When the sender receives the FHS packet, it enters the PAGE
state and uses the clock information in the FHS packet to send
a DAC packet on the frequency the receiver is listening to in
the PAGE SCAN state. Then the receiver responds
immediately with a DAC packet and the sender sends an FHS
packet to the receiver. The receiver uses the FHS information
to determine the channel hopping sequence and the phase of
the sender and becomes the slave of the point to point
connection. It then acknowledges the FHS packet with another
DAC packet. As soon as the sender receives the
acknowledgment, it becomes the master of the connection and

may start exchanging data with the synchronized receiver-
slave.

Figure 2: The Bluetooth asymmetric link formation

protocol.

By observing Figure 2, we can easily identify the link

formation delay components. The inquiry procedure delay
consists of a first FS delay, the RB delay and a second FS
delay that is taking place when the receiver waits for the
second IAC packet after it wakes up. The paging procedure
delay is negligible since it immediately follows the inquiry
procedure. (As soon as the first DAC packet is received by the
receiver the rest of the steps are happening in consecutive
625µs slots). Thus we can approximate the link formation
delay R using the following equation:

RBFSR += 2 (1)

where FS and RB are uniform random variables in

[ ]erageTcov,0 and [ ]max,0 r respectively. According to equation
(1), the link formation delay can be at most

msmsmsrT erage 375.659375.639202 maxcov =+=+ for the 32-
hop system and 649.375ms for the 16-hop system.

3. A SYMMETRIC PROTOCOL FOR LINK FORMATION

The asymmetric protocol provided by the Bluetooth

specification, yields a very short connection establishment
delay provided that the sender and receiver roles are pre-
assigned.

When two or more users are trying to establish links
between their Bluetooth devices in an ad hoc fashion, they will
not be able to explicitly assign sender and receiver roles. They
will just press a button and expect to connect with their peers.
Thus there should be a symmetric mechanism that forms
connections in an ad hoc fashion without any explicit sender or
receiver role pre-assignment. A way to do this, is by forcing
the two nodes to alternate independently between the sender
(INQUIRY state) and receiver (INQUIRY SCAN state) roles

(6) Enter the
PAGE state

(5) Respon d an d enter
PAGE SC AN state

(4) Wake u p

(3) Go to sleep

(2) Start in INQUIRY
SCAN state

(1) Start in the
INQ UIRY s tate IAC

…
….

FS

de
la

y
R

B

de
la

y

FHS
DAC

IAC

DAC

(7) Connection
Es tablishe d

Li
nk

F
or

m
at

io
n

D
el

ay

Sender Receiver

FS

de
la

y

(7) Connection
Establishe d

Pa
gi

ng

de
la

y

(7) Connection
Es tablishe d

FHS
DAC

0
-6

39
. 3

75
m

s
0

-2
0

m
s

0
-2

0
m

s
4

x
0.

6
25

m
s(6) Enter the

PAGE state
(5) Respon d an d enter

PAGE SC AN state

(4) Wake u p

(3) Go to sleep

(2) Start in INQUIRY
SCAN state

(1) Start in the
INQ UIRY s tate IAC

…
….

FS

de
la

y
R

B

de
la

y

FHS
DAC

IAC

DAC

(7) Connection
Es tablishe d

Li
nk

F
or

m
at

io
n

D
el

ay

Sender Receiver

FS

de
la

y

(7) Connection
Establishe d

Pa
gi

ng

de
la

y

(7) Connection
Es tablishe d

FHS
DAC

0
-6

39
. 3

75
m

s
0

-2
0

m
s

0
-2

0
m

s
4

x
0.

6
25

m
s

and try to connect according to the asymmetric protocol during
an overlap interval where they meet in opposite states.

In Figure 3, Unit A has already started alternating, and Unit
B starts alternating at some arbitrary time

0t . The merged
schedule is produced by merging the state switching times of
the two units into a single one, which can be seen as an “on-
off” process.

By using state alteration, a connection will be established
after a random delay, which in principle will be larger than the
one of the asymmetric protocol. The reason is that starting at
each “on” interval of the merged process, the two units will
connect after a random interval RBFSR += 2 , given that they
both remain fixed at their (complementary) states for an
amount of time greater than R. Otherwise, they have to wait for
the next “on” interval. The time Tc from time 0t up to the point
where the two units come to a complementary state for a
sufficient amount of time is essentially the link formation delay
between the two units.

Figure 3: A symmetric link formation protocol: Nodes

alternate between sender and receiver state until they connect.

There are some interesting questions arising from the

proposed “alternating states” technique. First of all what
should the alternating schedule be? Should the states alternate
in a periodic or random fashion? It can be analytically proven
that the mean connection time is infinite when each unit
changes states deterministically. A formal proof is omitted due
to lack of space and can be found in [3]. Intuitively, if the state
residence intervals are fixed, the intervals of the merged
process in Figure 3 will be fixed as well. Then the connection
time will depend on the fixed phase difference of the two
devices. If this phase is very small, then the “on” intervals in
the merged process will be very small and the link formation
delay very large since the units will use arbitrarily many “on”
intervals until they finally connect.

Alternatively, a random schedule can be imposed on the
state residence times. In [3] we provide an ad hoc link
formation delay model, and show that when each unit
alternates independently between INQUIRY and INQUIRY
SCAN with the state residence times following a common
random distribution, we can analytically calculate the mean
and variance of the link formation delay.

The way to calculate the connection set up delay is to
determine the cdf and pdf of the merged schedule process X
given that the two nodes alternate independently according to
an identical distribution Z. In [3] we show that the mean and

variance of the link formation delay of the symmetric protocol
are given by:

[ ] [ ] [ ] [ ]( )( ) [ ]RE
p

pXEXRXEXE
TE c +

−+>
+=

1|
2

(2.1)

[ ] [ ] [ ] [ ]( )( ) [ ]RVar
p

pXVarXRXVarXVar
TVar c +

−+>
+=

1|
2

(2.2)

where [ ]XRPp ≤= . (2.3)

The “alternating states” technique is a mechanism that
guarantees an ad hoc point to point connection between two
Bluetooth devices. When more than two devices exist and wish
to form a scatternet “on the fly”, a protocol should be devised
on top of this mechanism, that ensures that the resulting
network will fulfill the requirements and structure of a
Bluetooth scatternet. This protocol should also be efficient in
terms of network establishment delay. We will use the
symmetric link formation delay model derived in [3] in
to achieve this.

4. BTCP: A DISTRIBUTED SCATTERNET FORMATION

PROTOCOL

Our motivation for the scatternet formation problem arises

from a “conference-scenario” of an ad hoc network
establishment. Suppose that there are many users in a room
that wish to form an ad hoc network using their Bluetooth
enabled devices. Each user presses a “start” button and waits
for the device to show on the screen a “network connection
established” message after a short period of time. After this
message appears, the user will be able to exchange information
with any other user in the room. The description of this
application actually contains the elements of a successful
connection establishment protocol:

• Network connection establishment should be performed in

a totally distributed fashion. This means that each device
starts operating asynchronously on its own and it initially
does not have any knowledge about the identities or
number of nodes in the room.

• After completion, the protocol must guarantee a connected
scatternet. “Connected” means that there should be at least
one path between any two nodes in the network.

• The network set up delay should be minimized such that it
is tolerable by the end user.

In general there are no restrictions regarding the final form

of the scatternet. The only requirements are that:

• There should be piconets that have one master and less
than seven slaves and that piconets are interconnected
through S/S or M/S bridge nodes.

• Every node must be able to reach every other node in the
resulting network i.e. the network must be connected.

R

S

I

S S S

I I

I II

S S

X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11

0t

…

cT

Merged
Schedule

Unit 1

Unit 2

R

S

I

S S S

I I

I II

S S

X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11

0t

…

cT

Merged
Schedule

Unit 1

Unit 2

In addition to satisfying connectivity, a desirable feature of
the protocol would be to be able to shape the network topology
according to scatternet formation criteria imposed by specific
applications. For example the same node may need to have
different roles in different applications. Also it may be
possible for a node to have more restrictive degree constraints
than seven due to its own nature as a device; for example a
palm pilot would not have the processing power to be a master
of a seven slave piconet. Scatternet formation criteria could
also be in the form of traffic demands that need to be satisfied
by the nodes participating in the network construction process.
These criteria should be taken into account during the
topology construction process if they exist. The problem of
defining scatternet forrmation criteria is itself an open research
issue that is heavily dependent on the envisioned applications.
Although we do not address it in this paper, our approach takes
it into account by collecting information about all nodes
participating in the process at a single point before actual
connection happens.

BTCP is based on a leader election process. Leader election
is generally an important tool for breaking symmetry in a
distributed system. Since the nodes start asynchronously and
without any knowledge of the total number of participating
nodes in the network construction process, an elected
coordinator will be able to control the network formation and
ensure that the resulting topology will satisfy the connectivity
requirements of a Bluetooth scatternet.

In the absence of any scatternet formation criteria, and in
to design a simpler and faster protocol, we propose and
justify the following default properties that the resulting
network will satisfy:

1. A bridge node may connect only two piconets. (Bridge

degree constraint): A bridge node forwards data from
one piconet to another by switching between them in a
time division manner. Given that each portable device
may have limited processing capabilities, a maximum
bridge degree of two relieves a node of being an
overloaded crossroad of multiply originated data transfers.

2. Given the number of nodes N, the resulting scatternet
should consist of the minimum number of piconets
possible. The impact of this is similar to the motivation of
solving the problem in [6] of finding the minimum number
of routers in an ad hoc network. A minimum number of
piconets yields an easier network to control.

3. The resulting scatternet should be fully connected.
This means that every master will be connected to all
other masters through bridge nodes. Scatternets are
expected to change and be reformed over time. A fully
connected scatternet in its initial state provides higher
robustness against topology changes. Also no routing is
needed in this original state since every master can reach
every other master through a bridge node and every slave
can reach everybody else through its own master.

4. Two piconets share only one bridge (Piconet overlap
constraint). This condition is used in to provide a
means of terminating easily the connection establishment
protocol and calculating the minimum number of piconets.

If two masters later wish to share another bridge between
them they can do so by means of a bridge negotiation
protocol.

The protocol consists of three phases:

Phase I: Coordinator Election

During this phase, there is an asynchronous, distributed

election of a coordinator node that will eventually know the
count, identities and clocks of all the nodes participating in the
network construction process.

Each node x has a variable called VOTES which is set to 1
as soon as the node is powered up. After initialization, the
node starts alternating between the INQUIRY and INQUIRY
SCAN state.

Any two nodes x and y that discover each other will form a
point to point connection, enter a “one-to-one confrontation”
and compare their VOTES variables. The node with the larger
variable is the winner of the confrontation. If the two nodes
have equal VOTES variables the winner is the node with the
larger Bluetooth address.

Without loss of generality, suppose that x is the winner and
y is the loser. The loser y sends all the device FHS packets of
the nodes it has won so far to the winner x, it tears down the
connection and enters the PAGE SCAN state. In this way it
will not be able to hear inquiry messages any more but only
page messages from nodes that will page it in the future. This
action has the effect of eliminating the loser from the
coordinator election process and preparing it for the next
phases of the protocol.

The winner x increases its VOTES variable by VOTES(y)
and continues on the leader election process by resuming
alternating between INQUIRY and INQUIRY SCAN.

If there are N nodes participating in the scatternet formation,
there will be N-1 one-to-one confrontations. The winner of the
N-1st confrontation will be the coordinator node and the rest of
the nodes will be in the PAGE SCAN state waiting to be paged
by a node that has information about them.

Phase II: Role Determination

The coordinator that was elected during phase I, has the

FHS packets (i.e. identities+clocks) of all the nodes and hence
knows the total number of nodes N that participate in the
network connection establishment.

At the start of phase II, the coordinator checks if the number
of nodes that it has discovered during phase I is less than eight.
If this is the case, it pages and connects to all of the nodes in
PAGE SCAN and one piconet is formed with the coordinator
as the master and all the other nodes as its slaves. In this
special case the protocol terminates at this point.

If the number of nodes is greater than seven then more than
one piconet must be formed and interconnected via bridge
nodes. Given the global view of the network the coordinator
can decide on the role that each node will perform in the final
scatternet. If the participating …