# A Reconfigurable Formation and Disjoint Hierarchical Routing for Reshapeable Bluetooth Networks
## 2 Related Work  
Many scatternet formation algorithms have been developed for the construction of multi-hop sensor networks. These algorithms can be divided into two categories. The first [13; 14; 15; 16; 17] deals with situations in which all nodes are within radio range. The second category [18; 19; 20; 21; 22; 23] deals with situations in which all nodes are not necessarily within radio range. Depending on the purpose of a scatternet, a number of different topology models [24] can be generated. These scatternet topology models can be generally categorized as tree-based, ring-based or mesh-based topologies, although bus and star topologies have also been studied. Tree scattenet formation (TSF) [13] is a simple algorithm used to generate a tree topology. Initially, each node alternately switches between inquiry and inquiry-scan mode to find its neighbor nodes. Then the root node connects with neighbor nodes in the piconet formation phase. In addition, two sub-trees can be merged via the roots, and the master node becomes the new root of the merged tree topology. In [14], all Bluetooth devices are classified as components. A component can be a node, a piconet or a scatternet. Initially, all nodes are leader nodes, connecting with other nodes. When a link is established, the master node will become the leader of this component. This leader will then try to connect with other components. Finally, all components will be connected, and a large tree-shaped scatternet is generated. In [15], a node which has complete knowledge of all other nodes is elected as the leader of the scatternet. This leader then partitions the entire scatternet topology by optimizing the number of piconets according to a predefined formula. In [16], a super master collects all nodes' information, distributes the role for each node, and controls the topology shapes into line, bus, star or mesh by their corresponding parameters. A Bluetooth hybrid ring tree topology called BlueHRT (bluetooth hybrid ring tree) [17] has been proposed for operation with a non-uniform distribution of Bluetooth devices. The protocol forms a ring topology in densely covered areas, which is connected with multiple tree subnets around sparsely covered areas. BlueHRT aims to mitigate the bottleneck problem in dense areas for high traffic loads, while reducing the path length in terms of delays among devices in the surrounding areas. Three-phase algorithms are designed to form a hybrid ring-tree scatternet, including discovery, role assignment and connection algorithms. During the inquiry phase, a discovery algorithm compares the addresses of all Bluetooth devices and selects the root with the largest number of addresses as a leader. In the role-assignment algorithm, the root assigns master nodes and slave/slave bridges in the ring area, as well as master/slave nodes for the tree topology. In the connection phase, all master and master/slave nodes start to page their slaves and connect the scatternet to a hybrid ring-tree topology. Bluetree [18] is the first scatternet formation protocol to build a tree hierarchy (TH) for Bluetooth _ad hoc_ networks. It adopts one or several root nodes to start the formation of a scatternet. The resulting topology is tree-shaped, and uses master/slave nodes to serve as relays throughout the entire scatternet. Although its spanning tree architecture achieves a minimum number of connection links between any two nodes, its tree-shaped topology is not reliable under dynamic topological changes [19]. In addition, while the algorithm is easily implemented, the root node is likely to become a bottleneck. Bluenet [20] and Bluestar [21; 22] are good examples of master/slave mesh (MSM) topology. Bluenet sets up a scatternet in a distributed manner, and the mesh-like architecture is able to achieve higher information-carrying capacity than can a tree-shaped architecture.