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