. 25
( 87 .)


conet interconnection). These operations require each node to be aware of its neighbors. A
phase of device discovery must, therefore, be performed before the actual scatternet for-
mation process takes place. For these operations, we describe here their desirable features
and the barriers to their implementation.
In what follows, given a set of BT nodes, we call a visibility graph the network topolo-
gy in which there is a link between any two nodes whose Euclidean distance is less than or
equal to the nodes™ transmission radius (for the sake of protocol description, we assume
that all nodes have the same transmission radius). These topologies are also often referred
to as unit disk graphs [3].

4.3.1 Device Discovery
The device discovery phase should lead each of the network nodes to become aware of all
its neighbors in the visibility graph. This neighbor knowledge should be “symmetric,”
which means that if node v knows node u, u must also know v. In general, unless simplify-
ing assumptions are made on the visibility graph (e.g., the visibility graph is a clique, as in
“single-hop” topologies), this is the least information required for performing the follow-

ing phases of piconet formation and interconnection. As described in Section 4.2, the
mechanisms provided by the BT specifications for device discovery (inquiry procedures)
do not lead to the needed symmetric neighbor knowledge and require nodes to be in oppo-
site inquiry modes in order to be able to communicate. Therefore, specifications-compli-
ant mechanisms must be defined to ensure that, for each pair of neighboring nodes v and
u, they are eventually in opposite modes and that, when node v discovers node u, u is also
made aware of v.
The implementation of the device-discovery mechanisms as outlined above is chal-
lenged by a number of BT standard features. We mentioned already the asymmetry intro-
duced by the inquiry procedures: since the inquirer does not transmit its unique BT ad-
dress, a node that receives an inquiry ID packet cannot discern if this packet comes from
an already discovered node. This leads to useless inquiry handshakes, and may compro-
mise the possibility of knowing the entire neighborhood. In addition, ensuring that two
nodes are in opposite modes (for instance, by having them alternating between inquiry
and inquiry scan mode) can be guaranteed only statistically, and it is a time-consuming
process. This is also exacerbated by the duration of the backoff interval, which makes the
inquiry handshake long.

4.3.2 Piconet Formation
The piconet formation phase concerns the assignment of roles”either master or slave”
to all the network nodes. As dictated by the specifications, if a node is a master, it is mas-
ter only in one piconet. In general, a slave can be enrolled in more than one piconet.
Desirable properties for piconet formation include:

Distributed operations. Networks of Bluetooth devices are characterized by high dy-
namics (e.g., because of mobility and nodes joining the network at different times),
and gathering complete information about the changing network topology can be
infeasible. Therefore, piconet formation should be executed at each node with limit-
ed knowledge of the node™s surrounding topology. One-hop or two-hop neighbor-
hood knowledge is what can be known at each node in reasonable time and with
limited resource consumption.
Piconet size limited to eight nodes. Since no more than seven slaves can be actively
communicating with a master, a master of a piconet with more than seven slaves is
forced to park and unpark its slaves in order for all of them to be able to communi-
cate. Parking and unparking have an associated overhead both in terms of induced
delay and bandwidth. The throughput available to the nodes is significantly reduced
in the case of large piconets, leading to inefficient operations.
Resource-based master selection. Being a master is more resource consuming than
being a slave, as masters have to handle and coordinate all the communications to
and from all the nodes in the piconet. Piconet formation should, therefore, be per-
formed, taking into account the different types of devices and their available re-
sources when assigning the role of master.

4.3.3 Piconet Interconnection
The final phase concerns the selection of gateway devices to interconnect multiple pi-
conets into a scatternet. There are three ways of interconnecting two piconets:

1. Master“master. In the case in which the masters of the two piconets are neighbors,
interconnection can be achieved by having one of the two masters join the other pi-
conet as a slave.
2. Gateway slaves. When a slave is neighbor of two masters, whether that slave be-
longs to only one of them or to both, it may be used to interconnect the two piconets
by joining the piconet to which it does not belong (if any). When this is the case,
that slave is called a gateway slave.
3. Intermediate gateways. This is the case in which two masters have two slaves that
are neighbors. The interconnection of the two piconets can be achieved by requiring
that one of the two gateways becomes the master of a new piconet that includes the
other intermediate gateway as slave.

Desirable characteristic of piconet interconnection (which are properties of the result-
ing scatternet) are:

Connected scatternet. If the topology resulting from the device discovery phase is
connected, the scatternet generated by a scatternet formation protocol should also
be connected.
Resilience to disconnections in the network. If the topology resulting from the de-
vice discovery phase is not connected, a scatternet formation protocol should be
able to correctly operate in the connected components of the network.
Routing robustness. The scatternet should have multiple routes between any pairs of
Limited route length. Scatternet routes are longer than the corresponding routes in
the topology resulting from the device discovery phase for two main reasons:
1. All intrapiconet communications pass through a master (two neighboring slaves
that belong to the same piconet cannot communicate directly).
2. The piconet-based network organization, which, for instance, may force nodes
that are one hop away but that do not belong to the same piconet to communicate
through a much longer interpiconet route.

Scatternet formation protocols should carefully select gateways so that the increase in the
route length is limited.

Selection of gateway slaves. Whenever possible, gateway slaves are to be preferred
for piconet interconnection. This is due to the fact that when a master is also a slave
for interconnection purposes, when it acts as a slave, all the communications to and
from all the nodes in its own piconet are “frozen,” which clearly detrimentally af-
fects throughput performance.
Small number of roles per node. A node should have the minimum number of roles.
If a node has x roles, then it belongs to x different piconets. Switching between two
piconets has an overhead due to synchronization to the frequency hopping sequence
of the current master.
Self-healing. When the network topology varies dynamically (due to nodes mobili-
ty, arrival of new nodes, failures of links/nodes, etc.), a scatternet formation proto-
col should be able to converge to a scatternet that retains all the properties of the ini-
tial scatternet.

Papers that have addressed desirable properties of scatternet formation protocols along
with the identification of key metrics for their performance evaluation are [4], [5], [6],
and [7].


The BT specifications describe methods for device discovery and for the participation of
a node in multiple piconets. However, solutions for scatternet formation are not provided.
A first broader classification of the solutions proposed so far in the literature distin-
guishes between scatternet formation protocols that require the radio vicinity of all nodes
(single-hop topologies) and protocols that work in the more general multihop scenario.
The solutions are usually distributed and localized, in the sense that the protocols are exe-
cuted at each node with limited knowledge of the surrounding topology.

4.4.1 Single-Hop Solutions: Device Discovery and Scatternet Formation
In some of the scatternet formation protocols for single-hop topologies, the device-dis-
covery phase takes place concurrently with the phases of piconet formation and inter-
connection. Therefore, in this section the three phases are described together. In all
cases, the nodes involved in the device discovery process keep switching between the in-
quiry and inquiry scan modes. This mechanism allows two nodes to eventually be in op-
posite modes at the same time, which is the needed condition for them to meet each
Among the solutions that work only in single-hop topologies with n nodes, the first al-
gorithm for scatternet formation has been presented in [8]. The Bluetooth Topology Con-
struction Protocol (BTCP) described in that paper is based on a distributed leader-election
process. The leader election is performed by means of the inquiry and inquiry scan proce-
dures so that when two neighboring nodes discover each other, one of the two nodes
“wins,” that is, it keeps participating in the discovery of other nodes, while the loser quits
this phase, letting the winner know about its identity, its clock, and the identities and the
clocks of all the nodes it was made aware of via previous confrontations. The elected
leader (final winner) will eventually know the number, identities, and clocks of all the
nodes in the network, based on which it decides the role that each node performs in the fi-
nal scatternet. The computed roles are then communicated by the leader to all nodes. Des-
ignated masters are informed of the list of their designated slaves. The specific centralized
algorithm, performed locally by the leader aims at minimizing the number of piconets
while generating a mesh-like connected scatternet whose piconets have no more than sev-
en slaves and are interconnected by gateways of degree two. The centralized algorithm ex-
ecuted by the leader generate a connected scatternet that satisfies the required properties
only when the number of nodes in the network is 36. When n > 36, other centralized
schemes could be used such as the one proposed in [9], which also takes traffic into ac-
count. The problem of scatternet formation is formulated as an integer linear program-
ming problem where the objective function to be minimized is the traffic load at the most
congested node (bottleneck node). Another centralized scheme has been presented in [10],
which works for networks with any number of nodes. The aim of the protocol is to design
a scatternet topology for which optimal interpiconet scheduling can be defined and that
obtains max“min fairness. Once it has gathered all the information about all the network

nodes, the leader computes a k-regular topology (i.e., a topology in which all nodes have k
links). The final topology is obtained by selecting and combining k different disjoint sets
of edges that are (near-) perfect matchings (also called 1-factors), 2 k 2n “ 1. The au-
thors describe a selection of the 1-factors that leads to a connected topology.
A randomized distributed algorithm for single-hop topologies is described in [11]. The
protocol proceeds in rounds (i.e., it is a synchronous protocol). The devices are grouped
into components (that may be either a single device, a piconet, or a connected scatternet),
each of which has a leader. They are progressively joined to form the final connected scat-
ternet. In every round, leaders of different components attempt to discover each other.
This is performed by having each leader randomly enter either the inquiry or inquiry scan
mode for that round. Leaders in opposite modes that discover each other decide which of
the nodes in their components they can be interconnected with, thus forming a larger
component. The protocol terminates when all the nodes belong to the same component.
The resulting scatternet has the following properties: Each piconet has no more than sev-
en slaves, and every gateway has degree two. The number of generated piconets is close to
the theoretical minimum ®n/7. The scatternet, which is a tree, is formed in O(log n)
rounds with high probability.
A tree-like scatternet is also produced in the Tree Scatternet Formation (TSF) proto-
col described in [12]. The idea behind the protocol is very similar to the one presented
in [11], although TSF is an asynchronous protocol. At any point in time, the scatternet
being generated by TSF is a forest of connected trees. As the protocol proceeds, trees
are joined by their roots that, by periodically alternating between inquiry and inquiry
scan mode, try to discover each other. Since the trees™ interconnection happens only via
the roots, and since any node could be a root, all nodes must be in the transmission
range of each other for the generated scatternet to be connected (single-hop solution).
Newly arriving nodes can be included in already formed trees, which render this solu-
tion self-healing, that is, able to cope with changes in the network topology. The solu-
tion aims at minimizing the number of piconets, and at keeping the number of nodes per
piconet below seven. However, this cannot be always guaranteed. In general, generating
a tree-like scatternet topology simplifies routing but introduces limits in terms of ro-
bustness and efficiency.

4.4.4 Multihop Solutions
Protocols for general multihop topologies rely on the assumption that each node is aware
of its neighbors and this knowledge is symmetric. This knowledge is provided by the de-
vice discovery phase, which is, therefore, performed before the actual piconet formation
and interconnection phases. Device discovery. The solution for device discovery in multihop networks
uses a mechanism introduced in [13] and [14] that is similar to that described in [8]. Each
device alternates between inquiry mode and inquiry scan mode, remaining in each mode
for a time selected randomly and uniformly in a predefined time range. The operations
while in each of the two modes are those described in the specifications. When two nodes
in opposite inquiry modes handshake, they set up a temporary piconet that lasts only the
time necessary to exchange their ID and possibly other information necessary for the fol-
lowing phases of the protocol. The formation of temporary piconets and the exchange of
information achieves the required mutual knowledge.

The following procedure describes the operations performed at each device v as it en-
ters the topology discovery phase of the protocol:

1 Tdisc td
2 while Tdisc > 0
3 do if RAND(0. 1) < 0.5
6 INQUIRY(min(Tinq, Tdisc))
8 COMPUTE(Tscan)
9 INQUIRYSCAN(min(Tscan, Tdisc))
11 COMPUTE (Tscan)
12 INQUIRYSCAN(min(Tscan, Tdisc))
14 COMPUTE(Tscan)
15 INQUIRY(min(Tinq, Tdisc))

The generic device v that executes the discovery procedure sets a timer Tdisc to a prede-
fined time length of the discovery phase td. This timer is decremented at each clock tick
(Tdisc keeps track of the remaining time until the end of this phase).
Device v then randomly enters either the inquiry or inquiry scan mode, and computes
the length of the selected phase (Tinq or Tscan). This computation is performed by ran-
domly and uniformly selecting the phase duration in a predefined interval. While in a
given mode, device v performs the inquiry procedures as described by the BT specifi-
cations. The procedures that implement the inquiry mode (procedure INQUIRY) or the in-
quiry scan mode (procedure INQUIRYSCAN) are executed for the computed time (Tinq and
Tscan, respectively), not to exceed Tdisc. Upon completion of an inquiry (inquiry scan)
phase, a device switches to the inquiry scan (inquiry) mode. A node keeps alternating
between the two opposite modes until Tdisc > 0. As mentioned, to allow each pair of
neighboring devices to achieve a mutual knowledge of each other, our scheme requires
that whenever a device in inquiry (inquiry scan) mode receives (sends) an FHS packet,
a temporary piconet is set up by means of a page phase, and devices exchange their ID
and possibly other information. As soon as this information has been successfully com-
municated, the piconet is disrupted.
The effectiveness of the described mechanism in providing the needed mutual knowl-
edge to pairs of neighboring devices relies on the idea that by alternating between inquiry
and inquiry scan mode, and randomly selecting the length of each inquiry (inquiry scan)
phase, we have high probability that any pair of neighboring devices will be in opposite
mode for a sufficiently long time, thus allowing the devices to discover each other.
The duration of the discovery phase should be chosen so that each node is made aware
of enough of its neighbors to guarantee network connectivity. This implies that, as op-
posed to single-hop solutions, in multihop topologies when two nodes discover each other
they both have to keep performing device discovery as there might be other nodes that
need to discover them to be connected to the rest of the network (and vice versa).


. 25
( 87 .)