<<

. 26
( 87 .)



>>

126 SCATTERNET FORMATION IN BLUETOOTH NETWORKS


4.4.2.2 Scatternet Formation. Among the solutions that apply to the more general
case of multihop topologies, the scatternet formation protocol described in [15] requires
that the protocol be initiated by a designated node (the blueroot) and generate a tree-like
scatternet. The blueroot starts the formation procedure by acquiring as slaves its one-hop
neighbors. These, in turn, start paging their own neighbors (those nodes that are at most
two hops from the root) and so on, in a “wave expansion” fashion, until the whole tree is
constructed. In order to limit the number of slaves, it is observed that if a node in a unit
disk graph has more than five neighbors, then at least two of them must be connected.
This observation is used to reconfigure the tree so that each master node has no more than
seven slaves. If a master v has more than seven slaves, it selects two of them that are nec-
essarily connected and instructs one of the two to be the master of the other, which is then
disconnected from v™s piconet. Such branch reorganization is carried throughout the net-
work, leading to a scatternet in which each piconet has no more than seven slaves. De-
pending on a selected node to start the formation procedure, this solution does not work in
the case of networks whose topology after the discovery phase is not connected. Further-
more, the implementation of the protocol requires the use of time-outs to solve possible
deadlocks in the piconet formation phase.
Solutions for scatternet formation in multihop BT networks that produce topologies
different from a tree are those presented in [14], [16], [17], [18], and [19].
The protocol presented in [13] and [14] proceeds from the device discovery phase as
described above into the BlueStars (i.e., piconet) formation phase, and the configuration
of the BlueStars into the connected scatternet. The phase of piconet formation deploys a
clustering-based approach for master selection [20]. Based on a locally and dynamically
computed weight (a number that expresses how suitable that node is for becoming a mas-
ter), each node decides whether it is going to be a master or a slave. This phase starts at
some dynamically selected nodes and terminates with the formation of disjoint piconets,
each with one master and possibly multiple slaves. The final phase concerns the selection
of gateway devices to connect multiple piconets so that the resulting scatternet is connect-
ed.
This solution has the following features. It works for general multihop BT networks.
The generated scatternet is a mesh with multiple paths between any pair of nodes. The se-
lection of the BT masters is driven by the suitability of a node to be the “best fit” for serv-
ing as a master. The generated scatternet is connected whenever the network resulting
from the device discovery phase is connected. Finally, even in case of a disconnected dis-
covered topology, the protocol generates a connected scatternet over each connected com-
ponent.
The scatternet formation scheme proposed in [16], BlueNet, produces a scatternet
whose piconets have a bounded number k of slaves. After the device discovery phase, each
node randomly enters the page or the page scan mode with probability p (phase 0). When
a node succeeds in getting at least one slave, it proceeds to phase 1 and tries to acquire up
to k neighboring nodes as slaves. Otherwise, it keeps randomly entering the page or page
scan mode and executing phase 0 until all neighboring nodes have communicated that
they joined some other node™s piconet. (The fact that a node in phase 0 can actually con-
tact all its neighbors can be guaranteed only statistically.) In case a phase 0 node remains
isolated, it enters phase 2, goes to page mode, and tries to interconnect to neighboring pi-
conets by acquiring as slaves one node from each such piconet (up to k). After having ac-
complished this task, a phase 2 node exits the protocol. A master in phase 1 that has con-
tacted all its neighbors and acquired at most k nodes in its piconet, proceeds to phase 3,
the piconet interconnection phase. In this phase, the slaves of the piconets formed in
127
4.5 GEOMETRIC TECHNIQUES AND SCATTERNET FORMATION


phase 1, by alternating between page and page scan mode, attempt to set up links with
neighboring slaves of other phase 1 piconets as instructed by their masters. The connectiv-
ity of the resulting scatternet is not guaranteed (i.e., not all the BlueNets are connected,
even when the topologies resulting from the discovery phase are).
The main aim of the protocol proposed in [17] and [18] is to build up a connected scat-
ternet in which each piconet has no more than seven slaves. To this purpose, degree reduc-
tion techniques are initially applied to the network topology graph to reduce the number of
wireless links at each node to less than seven without disconnecting the network. Any (mul-
tihop) scatternet formation protocol can then be executed on the resulting topology, yield-
ing to a scatternet whose piconet size is at most eight (one master and at most seven slaves).
These techniques require each node to be equipped with additional hardware that provides
the node with its current (geographic) location (e.g., a GPS receiver). Details of this solu-
tion, combined with the BlueStars protocol outlined above, are given in Section 4.5.
The idea behind BlueMesh, the scatternet formation protocol presented in [19] and
[21], is to generate a connected scatternet by selecting some masters among the network
nodes, and allowing each master to select at most seven slaves. The selection of the slaves
is performed in such a way that if a master has more than seven neighbors, it chooses sev-
en slaves among them so that via them it can reach all the others. Once masters and slaves
are selected, i.e., piconets are formed throughout the network, gateways are chosen so that
there is an interpiconet route between all masters that are at most tree hops away (i.e., all
adjacent piconets are interconnected). This condition ensures the connectivity of the
BlueMesh scatternet [22]. Further details about BlueMesh are given in Section 4.6.
BlueMesh improves previous solutions in that: a) as opposed to BlueTrees, the generated
scatternet is a more robust mesh and it also works in connected components of a possibly
disconnected network; b) all generated scatternets are connected, which is not the case
with BlueNet; c) as opposed to BlueStars, no piconet in a BlueMesh scatternet has more
than seven slaves; and finally, d) no extra hardware is required as in the geometric-based
solutions of [18].
Thorough performance evaluation of BlueStars has been presented in [23]. A perfor-
mance comparison of the solutions for multihop scatternet formation presented in [14],
[16], and [18] is given in [24].


4.5 GEOMETRIC TECHNIQUES AND SCATTERNET FORMATION

In this section, we describe the details of a scatternet formation protocol that produces
scatternets that are connected and whose piconets have a bounded number k of slaves
(usually it will be k = 7).
The protocol assumes that each node knows its own identity, a dynamically computed
weight that indicates how much that node is suitable for serving as a master, and its own lo-
cation in the plane (usually provided by an on-board GPS device, or by any suitable inertial
positioning system device). It is also assumed that, as the outcome of the device discovery
phase, a node also knows the identity of its neighbors, their weight, and their location.
For the sake of clarity, in the description of the algorithm we assume that nodes are
randomly and uniformly scattered in the plane and that the network graph resulting from
the device discovery phase is a connected unit disk graph (UDG).
The knowledge of the location is exploited for applying to the UDG geometric-based
techniques to reduce the degree of the network to at most k. Once a connected topology
with such a bounded degree has been obtained, the BlueStars algorithm for scatternet for-
128 SCATTERNET FORMATION IN BLUETOOTH NETWORKS


mation outlined above uses the nodes™ weight for selecting the masters, the slaves, and the
gateways necessary to form a degree-bounded connected scatternet.
In [18], several degree reduction techniques are described, and it is proven that the re-
sulting degree-bounded topologies are connected. Here we describe only one of those
techniques, namely the one that [18] deems the most promising for the Bluetooth technol-
ogy, termed Yao construction. This technique was first proposed by Yao to construct the
minimum spanning tree of the graph originated by a set of points in high dimension effi-
ciently [25]. The reader is referred to [18] for a description of other geometric techniques
for degree reduction in wireless networks modeled by UDGs.
The Yao construction is executed at each node v and proceeds as follows. Node v di-
vides the plane that surrounds it into k equal angles. In each angle, node v chooses the
closest neighbor u, if any. (Ties are broken arbitrarily.) A link between nodes v and u sur-
vives the Yao contruction phase if and only if v has chosen u and vice versa. All other links
are deleted. To make such decision, nodes need to exchange with their neighbors the in-
formation on the nodes they selected. The mechanism we use for information exchange is
the temporary setup of a piconet between every pair of neighboring nodes. For this to be
possible, we have to guarantee that every pair of nodes are in opposite page modes. This is
obtained by having the nodes execute the following protocol. Upon completing the local
selection of links, a node v checks whether it has the biggest weight among its neighbors
N(v). If this is the case, that node, called in the rest of the chapter an init node, executes
the following procedure:

PECKODER(v)
1 PAGEMODE
2 for each smaller u in N(v)
3 do PAGE(u, v)
4 EXIT

An init node goes into page mode and starts paging all its neighbors (which, by defini-
tion, are “smaller neighbors,” i.e., nodes with a smaller weight) setting up temporary pi-
conets with each one of them. The information exchanged in the temporary piconet con-
cerns whether the two nodes have chosen each other or not.
Symmetrically, a noninit node u executes the following procedure:

SUBNODE(u)
1 PAGESCANMODE
2 for each bigger u in N(u)
3 do WAITPAGE(u, v)
4 PECKORDER(u)

Node u goes into page scan mode and waits for a page from all its neighbors with big-
ger weights (“bigger neighbors”). As soon as node u has decided about all the links with
the bigger neighbors (i.e., it has been paged by all of them), it goes to the “bottom of the
pecking order”; that is, being now the biggest node among those with which it has to ex-
change the link information, it switches to page mode, and starts setting up temporary pi-
conets with all its smaller neighbors (if any).
The topology resulting from the Yao construction, as described, is connected and has
the property that no node has more than k neighbors [18].
129
4.5 GEOMETRIC TECHNIQUES AND SCATTERNET FORMATION


Once a connected topology with such a bounded degree has been obtained, the BlueS-
tars algorithm for scatternet formation outlined in Section 4.4 uses the nodes™ weight for
selecting the masters, the slaves and the gateways necessary to form a degree-bounded
connected scatternet.
Let us consider the network of Fig. 4.2 as the network resulting from the device discov-
ery phase. The only node with more than seven neighbors is node 36. Therefore, node 36
executes the Yao construction procedure to discard one of its eight neighbors. Assuming
that nodes 20 and 21 fall in the same seven angles in which node 36 has partitioned the
plane around itself, the result of the Yao construction phase is the cancellation of the link
between node 36 and node 21. At this point, a connected scatternet is obtained by execut-
ing BlueStars over the “Yao topology” just obtained (where now nodes 36 and 21 are no
longer neighbors). BlueStars, described in [13] and [14], proceeds from the Yao topology
to the following two phases of piconet formation and interconnection of the piconets into
a connected scatternet. Based on a locally and dynamically computed weight (a number
that expresses how suitable that node is for becoming a master) and on the knowledge of
the weight of its neighbors (obtained during the discovery phase and the Yao construction
phase), each node decides whether it is going to be a master or a slave. This decision is
taken at a node depending on the decision of the bigger neighbors, and is then communi-
cated to the smaller neighbors. The mechanism through which this is implemented is sim-
ilar to the pecking order protocol described above. In particular, a node that decided to be
master is either an init node or a node whose bigger neighbors all decided to be slaves. A
node that has been told (via paging) by one or more of its bigger neighbors that they are
masters, becomes the slave of the first master that paged it. This phase of the protocol
leads to the partition of the topology resulting from the discovery phase and the Yao con-
struction into piconets. BlueStars does not guarantee a bounded number of slaves per pi-
conet. However, its combination with the Yao contraction (which limits the nodal degree
to k) also obtains this desirable property. The execution of the piconet formation phase of
BlueStars over the Yao topology obtained from the topology depicted in Fig. 4.2 is shown
in Fig. 4.3.
Nodes 21, 30, and 36, being init nodes, start paging their neighbors, which are all in
page scan mode. As depicted in Figure 4.3, node 21 is successful in paging nodes 17
and 20, which become part of its piconet. Node 30 has no competitors in having nodes
11 and 22 join its piconet. Node 36 forms the largest piconet by acquiring nodes 6, 8,
13, 15, and 25 as slaves. Once nodes 13, 22, and 25 have communicated their decision
to become slaves, node 7, whose bigger neighbors are all slaves, decides to be a master,


22
8
13
17 30
11
36
21
7
6


25
20
15

Figure 4.2. A Bluetooth network after the discovery phase.
130 SCATTERNET FORMATION IN BLUETOOTH NETWORKS



22
8 13
17 30

11
36
7
21
6

15
25
20



Figure 4.3. BlueStars™ piconet formation.



and since node 6 is already affiliated to node 36, it will be a master of a piconet with
one node.
After the piconet formation phase, each master proceeds to the selection of gateway
devices to connect multiple piconets so that the resulting scatternet is connected. In order
to achieve connectivity, it is necessary (and sufficient) that each master establishes a path
with (i.e., chooses gateways to) all the masters that are at most three hops away [22]. The
knowledge about which nodes are the masters two and three hops apart is achieved during
the piconet formation phase. Specifically, each node v communicates its role (and possi-
bly the identity and weight of its master) to all its smaller neighbors and to the bigger
neighbors that became slaves. If a node is a slave, it waits for the smaller neighbors to
communicate the same information. In this way, at the end of the piconet formation phase
each node is aware of the identity of all its neighbors, and of the identity and weight of its
masters, which is the information needed in the piconet interconnection phase. The
process of piconet interconnection is based again on a mechanism similar to the pecking
order protocol, this time executed only among the masters. The result of the BlueStars pi-
conet interconnection phase over the network of piconets of Figure 4.3 is depicted in Fig-
ure 4.4.
By the end of the piconet formation phase, node 36 knows the identity and the weight
of all the master at most three hops away, and the slaves through which it can reach them.
For instance, one (or more) among nodes 6, 13, and 25 could be used as gateway slaves to
interconnect to node 7. Once it has chosen one of these nodes (say, the biggest one: node




22
8 13
17 30

11
36
7
21

<<

. 26
( 87 .)



>>