# A Reconfigurable Formation and Disjoint Hierarchical Routing for Reshapeable Bluetooth Networks
## 3 Mesh-Tree Topology Design
### Scatternet Formation  
With a new root selection process, the designated root sets constant \(k\) and \(c\) as parameters. Where \(k\) is the number of layers and \(c\) is designed as a counter of the hop length from each downstream master to the designated root. With \(k=I=2\) and \(c=0\), the first root initially propagates these two parameters in the downstream direction and pages up to seven neighboring slaves to form a piconet. Each slave then switches its role to master (called an M/S node) and pages additional slaves. These new masters increase \(c\) by one, decrease \(k\) by one and continue to propagate the \(k\) parameter in the downstream direction. After this, the new masters begin to page up to seven neighboring slaves and connect their slaves to form their own piconets. Finally, each new master will switch to return mode and wait for the return signal notification. In this method, when the \(k\)th master is reached, \(k=0\). The master becomes a new root, and the \(k\) propagation process stops. The root selection process continues until all new roots are selected. The tree-shaped subnet of the designated root is thus created. At the same time, each new root repeats the same procedure as the designated root to build its own tree-shaped subnet, until the whole scatternet is formed. After each new root is determined, it notifies its upstream masters to start a return connection procedure. During the return connection phase, a new parameter, \(r\), is also added to represent the number of return links of each M/S node. When each returning master alternately switches its state between page and page-scan activities to connect with additional M/S nodes, the parameter \(r\) can be increased by one. Finally, each return master will pass its node ID (identification), \(c\) and \(r\) to the designated root when each master finishes the return connection phase. This procedure is run iteratively until the designated root is reached. As a result, the tree-shaped subnet of the designated root is converted into a mesh-shaped subnet. In addition, the root node collects sufficient information to calculate the average query path length, the total number of nodes, and the total number of return links for the optimum peak-search method decision. The peak-search method is described in detail in Section 4.1. When the optimum, \(I\), is not located, the root node propagates these two parameters with \(k=I+1\) and \(c=0\) in the downstream direction to increase the tree-shaped subnet by one more layer, as well as to generate new masters. During the return connection, only the new masters can connect with their neighboring M/S nodes and increase the return link parameter \(r\). This procedure is repeated until the optimum \(I\) is determined. When the M/S node cannot connect with its downstream master, it will reset parameter \(r=0\) and send its ID to the root node to cancel the return connection. In the topology maintenance phase, the optimum layer \(I\) can be increased or decreased by executing the reconfigurable method again when the size of the network becomes larger or smaller than a predefined threshold value. Figure 1: Scatternet formation process of a reconfigurable mesh-tree. (**a**) The designated root R1 connects with the first tier masters. (**b**) When the second tier masters R2 are reached and the counter limit \(k=0\), these masters become new roots. (**c**) These new roots request their upstream masters to start the return connection procedure until R1 is reached. (**d**) The mesh-shaped topology of the designated root is formed and each new root manages its own tree-shaped subnet. R1, the designated root; R2, the second tier masters. Here, \(k=2\) is used in Figure 1 as an example to describe the reconfigurable mesh-tree scatternet formation process. Initially, the designated root R1 connects with the first tier masters, as shown in Figure 1a. Then, the first tier masters decrease \(k\) by one, and continue to connect with their downstream masters.