# Determining the Optimal Configuration of the Multi-Ring Tree for Bluetooth Multi-Hop Networks
## 2 Formation Algorithm
### Multi-Ring Tree Formation Algorithm
#### 2.2.2 Multi-Ring Tree Formation Algorithm  
After determining the local optimal configuration with suitable \(R\) and \(P\), the leader root connects its one-hop neighboring nodes to form the multi-ring tree scatternet. The neighboring nodes can then be regarded as the first-tier new roots, and the leader root connects them together into the first-tier ring subnet. The number of roots in the first-tier ring is \(P\). Once the first-tier ring subnet is formed, each root at the ring subnet connects to one neighboring node as the second-tier new root. The roots at the first-tier ring propagate their second-tier new roots' information and instruct them to connect with each other to form the second-tier ring subnet. In this way, the third-tier roots are discovered and connected until the desired R-tier ring subnet is achieved. As a result, a multi-ring subnet is constructed, and the bridge node can be a master/slave or a slave node. Using \(N=17\) and \(|P-R|\leq 2\) as an example in the dense scenario, a leader root R1 discovers 16 other neighboring nodes. The min-path algorithm is executed by the coordinator R1, and \(N\) is decreased by 1 into 16 since the initial \(N\) is a prime number. The leader root then computes all possible (\(R\), \(P\)) sets, including (1, 16), (2, 8), (4, 4), and compares them with the constraint. As a result, the (4, 4) set satisfies the constraint and the optimal configuration is determined. After determining the optimal configuration with \(R=4\) and \(P=4\), the leader root assigns the identification sequentially from R2 to R16 for all other roots and computes the connection information for each root. Here, R1 propagates the connection information for root candidates of the first-tier ring R2, R3, and R4, as shown in Figure 1(a). The first-tier ring is formed by connecting R1, R2, R3, and R4, as shown in Figure 1(b). Each root in the first-tier ring then connects with its downstream root and propagates the connection information for them to form the second-tier ring, as shown in Figure 1(c). In this way, the 4 by 4 multi-ring is generated until the outermost 4-ring is reached, as shown in Figure 1(d). Figure 2 illustrates the formation process of the optimal multi-ring subnet in the dense scenario. After the multi-ring subnet is generated, each new root in the multi-ring serves as a coordinator and begins to scan its neighboring advertising message and connects them to form their own piconets. The connected slaves then switch their roles to masters (called M/S nodes), and each M/S node repeats the same scan procedures as the root, while also connecting its advertisers to form its own piconet. This procedure is performed iteratively until the leaf nodes of the tree are reached. An illustrated example of the multi-ring tree scatternet with \(N=16\), \(R=4\), and \(P=4\) is shown in Figure 3. In addition, the pseudo code of the multi-ring tree scatternet formation algorithm is listed in Algorithm 1. Figure 2: Formation example of an optimal multi-ring subnet: (**a**) R1 propagates the connection information for R2, R3 and R4; (**b**) The first-tier ring is formed by connecting R1, R2, R3 and R4; (**c**) Each first-tier root connects with its downstream root to form the second-tier ring; (**d**) The 4 by 4 multi-ring is generated until the outermost 4-ring is reached. ```
// The algorithm design is for a topology formation method to construct the optimized multi-ring subnet. Input parameter \(N\): \(N\) is number of roots; Constraint:\(|P-R|\leq k\); Output parameter (\(R\), \(P\)): \(R\) is number of rings; \(P\) is number of nodes in each ring. // Init: A designated root discovers \(N\) neighboring roots including itself in a dense area. if\(N\) is not decomposable  decrease \(N\) until the value of \(N\) is decomposable else find all possible combination (\(R\), \(P\)) of \(N\) if\(|P-R|\leq k\), calculate the average path length for the corresponding sets and output the set (\(R\), \(P\)) with the minimum path length according to Equation (1).