Scatternet Formation in Bluetooth

Bluetooth is an emerging Technology for pervasive computing, which is expected to become a ubiquitous solution for providing short range, low power, low cost, pico- cellular wireless connectivity. Bluetooth employs a Master- slave model, where a master device communicates directly with several Slave devices.Efficient clustering or topology construction algorithms play a very important role for forming a connected set of piconets, namely, a scatternet. In this paper, we address the problem of oganization of a set of devices into a minimum set of star- shaped clusters of limited size, with the connection between stars through non- centre nodes, under the assumption that not all nodes are within radio range of each other. We show that the feasibility and optimisation of scatternet formation are algorithmically hard. For this problem , a greedy centralised algorithm which assumes that a central entity has complete knowledge of the underlying topology is proposed. This is shown to be 1+ [k1 min(s,n)/n]-approximation algorithm, which is in terms of size of a s-clique-cover, s, the maximum bound on the number of slaves that any master can have , k1, and the number of nodes in the network, n. We then present a distributed heuristic which assumes that each node has 2-hop information of its neighbourhood. The performance of thes algorithms are also analysed using simulation experiments.
Keywords - Bluetooth , Scatternet, Piconet, Clustering, Ad-hoc networks.