# Determining the Optimal Configuration of the Multi-Ring Tree for Bluetooth Multi-Hop Networks
## 2 Formation Algorithm  
### Motivation of Multi-Ring Design  
It is assumed that a non-uniform environment is concentrated in a certain area with higher density, while the other extended areas are sparse areas. The high-density area belongs to the one-hop scenario and is designed as a multi-ring subnet. The other extended sparse areas belong to the multi-hop scene, which can be designed as a tree subnet. With the hybrid network design for the non-uniform scenario, the multi-ring tree benefits from both ring and tree network advantages.  
To generate a multi-ring subnet, a coordinator discovers and configures neighbor information \(N\) into the desired multi-ring subnet. The resulting multi-ring subnet can be the backbone network for the highly dense area. On the other hand, the discovered number of nodes \(N\) can be a random variable for various scenarios. Therefore, how to plan \(N\) into the optimal \(R\)-layer multi-ring architecture is an interesting research issue.  
Two main situations are considered in the design method: the first is how to form the desired multi-ring subnet, and the second is how to achieve the optimal configuration with the minimum multi-ring path length. Because \(N\) is a variable number, it can be divided into two general cases: prime number and composite number cases. When \(N\) is a prime number, \(N\) decreases by 1 until it is decomposable, since the prime case cannot form a multi-ring. When \(N\) is decomposable, \(N=R\times P\), where \(R\) is defined as the number of rings and \(P\) is defined as the number of nodes in each ring. In addition, to minimize the average path length of the multi-ring network, designing the symmetry multi-ring configuration to make the value of \(R\) and \(P\) as close as possible is intuitive.  
When \(N\) is decomposed into \(R\) and \(P\), it is found that some \(N\) have many combinations of \(R\) and \(P\). Therefore, all possibilities of combinations need to be calculated, and the corresponding average path lengths must be compared to determine the optimal configuration of \(N\). To make the multi-ring close to a symmetrical configuration, it is better to make \(R\) and \(P\) values closer in the multi-ring design. As a result, a constraint is proposed to limit the difference between the \(R\) and \(P\) to make the resulting network more symmetrical. At the same time, the constraint design also reduces the computational complexity of all possible combinations to more quickly determine the desired configuration.  
In the example of \(N=48\), there are eight decomposable multi-ring combinations except the cases (24, 2) and (48, 1) since at least three nodes are required to form a ring subnet. After calculating the various cases, the path length result of each combination is shown in Figure 1, which shows a minimum point when \(R=6\) with \(P=8\); this case achieves the minimum path length compared to all the other combinations. At the same time, the number of computations can be effectively reduced from eight to two if the constraint of \(R\)-\(P\) is set to four, thus improving the computation time required to determine the best configuration.  
Based on the above design points, we aim to develop a min-path algorithm to effectively determine the optimal multi-ring configuration. With an arbitrary given \(N\) and \(|P-R|\leq k\) constraint in the min-path algorithm, the system model can be formulated to quickly compute and search for the minimum point of the path length performance, and the most suitable \(R\) and \(P\) can be effectively determined.