# Determining the Optimal Configuration of the Multi-Ring Tree for Bluetooth Multi-Hop Networks
## 3 Routing Protocol  
### A Self-Routing Algorithm  
In order to effectively deliver a packet in the multi-ring tree scatternet, this work also presents a self-routing protocol with a shortest path criterion. The self-routing algorithm for one single-hop with multi-hop scenarios can achieve the least overhead route discovery compared to the other traditional routing protocols. Figure 4 shows a packet address field of the multi-ring tree. The routing protocol designs three types of scatternet address field: the Ring-ID, Root-ID, and Tree-ID in the packet header to achieve the self-routing capability. The packet field of Ring-ID with \(\left\lceil\log_{2}^{R}\right\rceil\) bits serves to specify the number of rings in the multi-ring subnet. The packet field of Root-ID with \(\left\lceil\log_{2}^{P}\right\rceil\) bits addresses the number of roots in each ring. The Tree-ID defines all the downstream nodes in each root. In addition, the slave node is addressed by the Bluetooth AM_ADDR in a piconet. With these three types of address, each node can deliver packets to the desired destination node in a multi-ring tree network. During the scatternet formation, a two-stage addressing method for the multi-ring tree is proposed. The first stage is to define the address for the multi-ring, and the second stage is to define the spanning tree address for the self-routing protocol. In the first stage, the Ring-ID is set to 1 for the roots in the first-tier ring, and the Root-ID is set to 1 for the leader root. In this way, the Ring-ID is set to 2 for the roots in the second-tier ring, the Ring-ID is set to 3 for the roots in the third-tier ring, and finally the outermost ring Ring-ID is set as \(R\). At the same time, the Root-ID of roots in each ring is set by a constant counter \(r\), where \(1\leq r\leq P\). The second stage presents a tree-addressing criterion specifically to all nodes in each spanning tree for the multi-hop scenario. Each root with Tree-ID = 0 connects with its downstream nodes with Tree-ID = 1, and the Tree-ID sequentially increases by 1 until 7 for the most connected nodes in the first-tier tree. The master in the first-tier with Tree-ID = 1 then connects with its downstream layer nodes with Tree-ID from 8 to 14, and the master Tree-ID = 2 assigns its connected nodes with Tree-ID from 15 to 21. In this way, the master with Tree-ID = 8 connects with its downstream nodes and assigns the third-tier nodes Tree-ID from 57 to 63, so that each upstream master can forward the packet to the destination node according to the Tree-ID. In summary, the address range of Tree-ID in the each-tier tree is assigned with the tree-addressing criterion by its parent with pTree-ID from (7 \(\times\) pTree-ID) + 1 to 7 \(\times\) (pTree-ID + 1). With the destination Tree-ID = 24 as an example, the root of the destination receives the packet and computes the ID = 24 by the tree-addressing criterion. The destination is located at the address range of its third connected master, and the packet will be forwarded to the parent master of the destination. The parent master in the first-tier then forwards the packet to the destination node, since ID = 24 is the directly connected node of this master. Figure 4: Multi-ring tree scatternet address field of a packet. To reduce the packet length of a larger ring subnet and efficiently deliver packets, a shortest path criterion is defined as Equation (3) to minimize the hop distance between root \(i\) as \(r_{i}\) and root \(j\) as \(r_{j}\). When a root in the ring subnet receives a new packet either from the tree subnet or the ring subnet, the Root-ID of the destination root will be checked with its own Root-ID by Equation (3). If \(j\) is greater than or equal to \(i\) and Equation (3) is satisfied, then the packet will be forwarded in a clockwise direction in the ring subnet; otherwise, the packet is forwarded in a counterclockwise direction.