. 27
( 87 .)




Figure 4.4. The scatternet produced by combining the Yao construction with BlueStars.

25), it instructs it to wait for a page from node 7. Node 7 also knows that nodes 6, 13, and
25 are the nodes through which the two piconets can be interconnected, and it adopts the
same gateway selection rule of node 36. Therefore, it pages node 25 to enroll it as its
slave. The same thing happens between masters 7 and 30, which select as intermediate
slave node 22 (the sole node that can fulfill this purpose). The piconets of nodes 36 and 21
must interconnect via intermediate slaves. To this purpose, since both masters know each
other and which of their slaves are neighbors of the slaves of the other, they can consis-
tently choose two neighboring slaves and instruct them to page each other in order to form
the needed new piconet. In the case depicted in Fig. 4.4, for instance, node 36 instructs
node 15 (the biggest of its slaves that are neighbors of slaves of node 21) to page node 20,
which is its neighbor that is a slave of node 21. Consistently, node 21 instructs its slave 20
to go into page scan mode and waits for a page from node 15. Similarly, the piconets of
masters 36 and 30 are joined by the new piconet formed by node 13 and 22, which act as
intermediate slaves. (The details of the rule adopted for consistent gateway selection and
for piconet interconnection can be found in [14].)


In this section, we describe BlueMesh, a protocol for forming connected scatternets
whose piconets have a bounded number of slaves. As with BlueStars, scatternet connec-
tivity is guaranteed by establishing an interpiconet route between any two masters that are
at most three hops away [22, Theorem 1]. Unlike the protocol presented in the previous
section, BlueMesh does not need location information.
BlueMesh proceeds in successive iterations. Each iteration is executed by the network
nodes that have not yet exited the execution of the protocol at some previous iteration.
Let us call Gi = (Vi, Ei) the network topology graph at iteration i, i 1. G1 is simply the
topology after the device discovery phase (as before, we assume that this topology is a
UDG). Each of the Gi, i > 1, is the subgraph of G1 that spans the nodes of V1 that did
not exit the execution of BlueMesh in one of the previous iterations. In each iteration i,
piconets are formed from the nodes in the topology graph Gi. The interconnection of
two piconets is achieved either via a gateway slave or via a pair of intermediate gate-
ways, one of which belongs to one piconet and the other to the other piconet. Gateway
slaves are selected in the current iteration so that the piconets they belong to are joined.
Masters then proceed to select the intermediate gateways between adjacent piconets not
yet interconnected.
The intermediate gateways are the nodes that proceed onto the next iteration. All mas-
ters, slaves that have not been selected as gateways, and the gateway slaves exit the execu-
tion of BlueMesh at this time. BlueMesh terminates when all nodes have exited the execu-
tion of the protocol.
The functioning of BlueMesh is illustrated by the following example. We assume that
BT devices know their identity, their weight, and the identities and weights of all their
one-hop and two-hop neighbors. Two-hop neighbor knowledge can be achieved after the
device discovery by executing the “pecking order” protocol described in Section 4.5,
where the information exchanged via the temporary piconet between the nodes v and u are
the lists of neighbors N(v) and N(u).
Each iteration of the protocol is performed locally at each node v and is made up of two
parts: role selection (for piconet formation) and gateway selection.

Role selection is executed by every node at the very beginning of each iteration i (in
the case of the first iteration role selection is performed as soon as the two-hop neighbor
discovery process has been completed). Based on its weight and the weight of its one-hop
neighbors, a node determines whether it is an init node in Gi. Only init nodes go into page
mode. All the other nodes go into page scan mode.
Let us consider again the network of Fig. 4.2. Being the nodes with the biggest
weight in their neighborhood, devices 30 and 36 are init nodes. They are masters and
switch to page mode. All the other nodes go into page scan mode. Device 30, which has
less than seven neighbors, selects all of them (nodes 11 and 22) as its slaves and pages
them to communicate its decision. “Piconet 30” is then formed by nodes 11, 22 and 30.
Device 36 has eight neighbors. Since we want to form piconets each with a number of
slaves k = 7, node 36 must select only seven of its eight slaves. Slave selection is per-
formed at a master node v by executing the following procedure, where S(v) is the set of
selected neighbors and C(v) denotes the set of v™s bigger neighbors that are slaves and
v™s smaller neighbors.

1 S(v) 0 /
2 U C(v)
3 while U 0 /
4 do x bigger in U(v)
5 S(v) S(v) {x}
6 U U \ N(x)
7 S(v) S(v) GET(7 “ |S(v)|, C(v) \ S(v))

Each master v chooses as slaves those neighbors in C(v) that “cover” all the other
neighbors in the sense that if a neighbor u is not selected as v™s slave, then at least one of
u™s neighbors has been selected by v. Such coverage is always possible by selecting at
most five slaves [19].
Procedure COMPUTES implements a greedy approach for computing S(v). One of v™s
neighbors in C(v) (e.g., the one with the biggest weight) is selected as its slave, say node x.
The procedure is then executed again on the set of all nodes in C(v) \ {x}, which are not
covered by x. This rule allows node v to select up to five of its neighbors in C(v) through
which all other neighbors can be reached.
The function GET(m, W) returns a set of m nodes from the set W (for instance, the m
smaller ones, or randomly chosen ones, or the bigger ones, etc.). It is used by COMPUTES
for selecting additional slaves to a maximum of seven (|S(v)| 7).
By executing COMPUTES(36), node 36 first selects five nodes”devices 8, 13, 15, 21,
and 25”through which 36 can reach all its remaining neighbors. Then, by selecting nodes
17 and 20 it reaches the limit of seven slaves (procedure GET, line 7). At this point, node
36 pages all its neighbors. It will communicate to node 6 that it is not invited to join its pi-
conet, and it will invite all the other selected nodes. As opposed to what happens in
BlueStars, when a node is invited to join a piconet, it always accepts the invitation even if
it already belongs to other piconets. Piconet 36 is made up of eight devices: master 36 and
the seven slaves 8, 13, 15, 17, 20, 21, and 25. In piconet 30, slave 22 has been paged by all
its bigger neighbors. It switches to page mode and starts paging the nodes in C(22), name-
ly, devices 7 and 13, communicating its role. Similarly, device 25, which has received the
page from node 36, pages nodes 6 and 7, which are in C(25). Device 13 received the

pages from all its bigger neighbors, and it is now ready to communicate its role (slave of
master 36) to its smaller neighbors 6 and 7. Device 7, which now knows that all its bigger
neighbors (nodes 13, 22, and 25) are slaves, becomes master and pages all of its four
neighbors, inviting them to join its piconet, which they do. Piconet 7 is thus formed by its
master and the slaves 6, 13, 22, and 25. At this point, the network has been divided into
three piconets that need to be interconnected. This marks the start of the gateway selection
part of the current iteration. In this part, all slaves communicate to their master(s) infor-
mation about the roles of their neighbors, their neighbors™ list of masters, and whether
some of their neighboring masters selected them as slaves. The information is obtained
with an extra network-wide “wave” of messages exchanged in a pecking-like fashion dur-
ing the role selection phase. Based on this information, each master decides which slaves
to select as gateways to which piconet in order to obtain a connected scatternet. If a pair of
masters have selected common slaves, they choose the bigger one among them as the
gateway slave. This is the preferred way to interconnect adjacent piconets. Whenever no
gateway slave can be selected to interconnect adjacent piconets, intermediate gateways are
selected, again based on their weight (e.g., so that the sum of their weights is maximized,
or the minimum weight is maximized, or any other unambiguous selection rule). Upon
completion of these operations, the gateway slaves, together with the masters and the non-
gateway slaves, exit the execution of the BlueMesh protocol. The intermediate gateways
proceed to iteration i + 1 to form new piconets that interconnect them, hence providing
connectivity between the piconets they affiliated with in iteration i. Going back to our ex-
ample, devices 22 and 25, common slaves of piconet 7 and 36, and 7 and 30, respectively,
are selected as gateway slaves to interconnect such piconets. Piconets 30 and 36 can be in-
terconnected only through the pair of intermediate gateways 13 and 22. These two nodes
are the only two nodes that move to the next iteration of the protocol. All the other nodes
quit the execution of BlueMesh at this time. Some of these nodes are masters (of a single
piconet), some are just slaves in one piconet (as is node 6), and some have multiple roles
(e.g., gateway slaves 13, 22, and 25). Realizing that it is now an init node, node 22 goes
into page mode and pages its smaller neighbor 13, which is waiting for its page. The two-
node piconet 22 is thus formed, which implements the interconnection between masters
36 and 30. The scatternet resulting from the execution of BlueMesh on the network of Fig.
4.2 is displayed in Fig. 4.5. Masters are depicted as pentagons, the piconets generated in
the first iteration are star shaped, and the piconet generated in the second iteration has an
oval shape.


The main concerns about the implementation of most of the described protocols for scat-
ternet formation in multihop networks are due to the discovery phase as we have de-
scribed it in Section In particular, we observed the following two problems:
First, it is extremely time consuming, and therefore impractical, to discover all the
neighbors of a given node. We have simulated the device discovery phase by using a BT
extension to the ns2 network simulator, which implements all the details of the BT proto-
col stack. The device discovery was run for a predefined time Tdisc over each visibility
graph generated by distributing uniformly and randomly n = 30, 50, 70, 90, 110 nodes
over a square area of side L = 30 meters. The transmission range of each node was that of
Power Class 3 BT nodes (10 m). Nodes alternate between inquiry and inquiry scan mode,


22 30


Figure 4.5. A BlueMesh scatternet.

spending a variable time, uniformly and randomly selected in the interval (0.02s, 2s), in
each mode. The resulting topology, which we call a BT topology, has links only between
those pairs of BT nodes that were able to discover each other during the device discovery
We observe that it may take a long time to discover all the neighbors of a node (e.g.,
only 47% of a node™s neighbors have been discovered after 10 s of device discovery in net-
works with 110 nodes). However, a shorter time suffices for discovering enough neigh-
bors so that the resulting BT topologies are connected, which is the needed requirement
for obtaining connected scatternets. This is shown by Figure 4.6. We can provide statisti-
cal guarantees that the BT topologies are connected in case of moderately dense to heavi-
ly dense visibility graphs provided that the device discovery runs for at least 6 s.
Three are the features of the Bluetooth technology that we have identified as having a
strong impact on the device discovery duration: a) The need to adopt (stochastic) mecha-
nisms to have neighboring nodes in opposite inquiry modes, so they can discover each
other; b) the impossibility of identifying the inquirer, which demands the construction of a
temporary piconet between neighbors that have discovered each other already; and c) the
overly long duration of the backoff interval as stipulated in the BT specifications (2048
clock ticks). In our performance evaluation, we have quantified the impact of each of
these features on the performance of device discovery [24]. We observe that, by just de-
creasing the backoff duration to one-fourth of the value specified by the standard, a signif-
icant increase in the number of discovered neighbors is achieved that leads to connected
topologies in less than 2 seconds. For instance, in networks with 110 nodes”by far the
worst case in the simulated scenarios”over 80% of a node™s neighbors are discovered
within 10 seconds.
Second, the topology resulting from the device discovery phase may not be a UDG
graph. This violates the assumption on which all protocols that provide connected scatter-
nets with piconets with less than k = 7 slaves rely. For instance, it might no longer be true
that given a node v with more than five neighbors, it is possible to find two among v™s
neighbors that are physically neighbors and have discovered each other. For the protocol
to work correctly, after the device discovery phase, it is, therefore, necessary to perform
an extra phase leading to a consistent knowledge of each node™s neighborhood. Basically,
we want two nodes that have discovered a common neighbor and are neighbors them-
selves to discover each other. This can be obtained in the following way. At the end of the

% of connected topologies

n = 30
n = 50
n = 70
n = 90
n = 110
2 3 4 5 6 7 8 9 10
Time (seconds)
Figure 4.6. Percentage of connected BT topologies versus Tdisc.

discovery phase, all neighboring nodes that have discovered each other exchange the list
of the nodes they just discovered. This list exchange can be performed by executing the
“pecking order” protocol as described above (Section 4.5) and leads to the construction at
each node v of a set Av of all nodes discovered by all v™s neighbors that v did not discover.
Once the list exchange is finished, node v starts contacting the nodes in Av to see whether
they are nodes within its transmission range (i.e., undiscovered neighbors). To this purpose,
a node v alternates for a predefined amount of time between page and page scan modes, at-
tempting to discover the nodes in its Av. More specifically, when in page mode, v attempts
to page one after another (in round-robin fashion) of the nodes in Av. Each time two nodes
u and v discover each other, they remove each other from their sets Au and Av and exchange
their lists of neighbors. This may lead to new nodes for u and v to be added to their sets Au
and Av, that is, to new nodes to page. The length of this phase has to be carefully chosen so
as to discover all the nodes in Av that are actually in v™s transmission range.


This chapter described solutions to the problem of scatternet formation, namely, to the
problem of setting up multihop networks of Bluetooth devices. Solutions for the two ma-


. 27
( 87 .)