# A Reconfigurable Formation and Disjoint Hierarchical Routing for Reshapeable Bluetooth Networks
## 5 Disjoint Hierarchical Routing  
In the reconfigurable mesh-tree network, the designated root can be regarded as the sink node, and all other nodes are sensors. During packet transmission, the sensor data will forward from each  
Figure 5: Average query hop in the mesh-shaped topology. Figure 6: The link performance ratio of peak-search examples. sensor to the sink node. Therefore, the main traffic congestion is located at the mesh subnet, since most of the traffic load will pass through this area to its destinations. From the energy consumption point of view, the nodes nearer the sink forward most of the packets and deplete their batteries more rapidly than other nodes and become energy holes or hot spot nodes in the network. To balance the traffic load and address the energy hole problem in the mesh-subnet, two equal disjoint paths are designed for each node forwarding packets to the sink. In the routing algorithm, each node generates two equal and disjoint paths to forward sensor data to the sink in the mesh subnet. The design goal of the routing algorithm is to balance the energy consumption for the hot-spot nodes and to deliver the packets from one subnet to all the other subnets effectively. Furthermore, each node with energy harvesting technology acquires additional energy from solar power, which eliminates the major battery capacity constraint. In the scatternet formation period, some routing information can be exchanged among masters. In the first phase of scatternet formation, each master in the mesh-subnet or the tree-subnet keeps a record of its directly connected master. As a result, a one-hop neighboring path can be easily formed by connecting all the masters. In the second phase of scatternet formation, each returning master in the mesh-subnet will exchange its own piconet information together with a list of its directly connected masters to its neighboring masters. At the same time, each returning master, including the root, will pass its own piconet information to its directly connected masters. Here, the directly connected neighboring piconets within their neighboring \(k\) hops of a master are defined as the \(k\)-tier piconets of the master. The associated \(k\)-tier piconet information will be stored in the master's \(k\)-tier piconet table. In addition, those masters affected by the return connection mechanism will update their \(k\)-tier piconet tables via relays. As a result, each master will keep its own piconet information and its \(k\)-tier piconet information. This information is used locally when a node requests a master for a path to deliver packets. After completing the second phase of scatternet formation, each master in the mesh-subnet will have the routing information of all master nodes and store it in a piconet list table. This table contains a list of all masters. Meanwhile, each master uses the all-pairs Dijkstra's shortest algorithm to compute two disjoint shortest paths for any two-piconet pair. This disjoint shortest paths information is stored in a scatternet routing table, and is used when any slave node asks its master for routing information to deliver packets and alleviate load balance. In the tree-subnet of the new root, a routing table is formed by each master node in the following way: When a leaf node perceives that it is at the end of the tree, it reverts back and informs its upstream master about itself. Likewise, every informed master then forwards its descendant information to its upstream master via the tree path established in the first phase, until the new root is reached. In this way, every master has its descendant routing information, and the new root node collects all node information. Finally, a simple table-driven routing protocol is used to forward packets on the tree-subnet. Based on the routing information collected by all the masters in the mesh-subnet and the new roots in the tree-subnet, a disjoint hierarchical routing protocol is developed. This is a proactive routing protocol, and operates in two types of packet transmissions.