# Determining the Optimal Configuration of the Multi-Ring Tree for Bluetooth Multi-Hop Networks
## 2 Formation Algorithm
### Multi-Ring Tree Formation Algorithm  
#### 2.2.1 Min-Path Algorithm  
In order to improve the topology's reliability, other than the conventional single-ring network, this work proposes a multi-ring tree scatternet formation algorithm. The multi-ring subnet as a core network design effectively improves network reliability. To effectively form the desired topology, the algorithm discovers the topology only in the dense area instead of the global area as the conventional single-ring network does, in order to reduce the computation and communication complexity. In the dense area, a min-path algorithm is also presented to determine the optimal configuration of the multi-ring subnet. During the node discovery phase (NDP) [30], each node alternatively operates as a scanner or an advertiser by a scan probability \(p\). In the multi-ring tree, a node plays a scanner if its probability \(p\) is greater than 0.5, or as an advertiser otherwise. In a time interval \(T\), each scanner increases its neighbor count by one when receiving an advertising message from a new neighbor. After the completion of NDP, a leader election phase (LEP) is started afterward. When two nodes meet, the node with the higher neighbor count value wins the role as a master and the other one plays a slave. During the connection, each slave sends its collected neighbor information to the master and stops to advertise message. When two nodes have the same neighbor count value, the node with the lower ID becomes the master. In this way, the masters continue to scan neighbor information and compare their neighbor count values by exchanging advertising messages. At the completion of LEP, the last master is elected as a leader root with the maximum neighbor count value in the dense area. At the end of LEP, a leader root discovers the local topology with \(N\) roots' information in the dense area. The min-path algorithm is introduced here to determine the local optimal topology of the multi-ring subnet. In the algorithm, the input parameter is \(N\), and the output parameters are the number of rings \(R\) and the number of nodes in each ring \(P\), where \(N\) can be factorized into the \(R\)-ring  
Figure 1: The average path length of \(N=48\) example. and \(P\)-node in each ring. The minimum value of \(R\) and \(P\) is 1, and the maximum value of \(R\) and \(P\) is \(N\). The decision criterion is compared by the average hop length \(H\), where \(H_{i}\) is a function of \(R\) and \(P\) for a given combination \(i\), where \(m\) is the maximum value of \(i\). When many decomposable combinations \(i\) exist for any given \(N\), the minimum point needs to be discovered by comparing the average hop length \(H_{i}\). To minimize the computation complexity of \(H(R,P)\), the constraint criterion \(|P-R|\leq k\) is also introduced, where \(k\) is a constant; the smaller \(k\) reduces the computation complexity of the min-path algorithm. The min-path and the constraint criteria can be expressed as Equations (1) and (2), respectively. \[\underset{i=1...m}{\text{Min}}\left(H_{i}(R_{i},P_{i})\right) \tag{1}\]  
Subject to:  
\[|P_{i}-R_{i}|\leq k \tag{2}\]  
The smaller \(k\) for each \(N\) intuitively brings the \(R\) closer to the \(P\). The resulting topology is more approximate to the symmetry deployment. However, when \(N\) is not decomposable, \(N\) decreases by 1 until the value can be factorized and the \(|P-R|\leq k\) constraint is satisfied. On the other hand, when \(N\) is decomposed into \(R\) and \(P\), if \(|P-R|\) does not satisfy the constraint, then \(N\) decreases by 1 until it can be decomposed into \(R\) and \(P\). Finally, the optimal configuration with the least hop length can be decided, and the suitable combination of \(R\) and \(P\) can be found. In addition, the closer \(R\) and \(P\) can satisfy the \(|P-R|\) constraint, the better is the formation of a more symmetrical multi-ring configuration.