An Efficient Scatternet Formation Algorithm for Dynamic Environments

G. Tan, A. Miu, J. Guttag, and H. Balakrishnan (USA)


Bluetooth Scatternet, Dynamic Topology Contruction


There is increasing interest in wireless ad hoc networks built from portable devices equipped with short-range wire less network interfaces such as Bluetooth. This paper ad dresses issues related to internetworking such networks to form larger “scatternets.” Within the constraints imposed by the emerging standard Bluetooth link layer and MAC proto col, we describe an efficient online scatternet topology for mation algorithm, called TSF (Tree Scatternet Formation). TSF connects nodes in a tree structure that simplifies packet routing and scheduling. Unlike earlier work, our protocol is designed to work well with dynamic environments where nodes arrive and leave arbitrarily. TSF incrementally builds the topology and healing partitions when they occur. We have developed a Bluetooth simulator in ns that includes most aspects of the entire Bluetooth protocol stack. Using this, we derive simulation results that show that TSF has low latencies in link establishment, tree formation and partition healing, all of which grow logarithmically with the number of nodes in the scatternet. Furthermore, TSF generates tree topologies where the average path length between any node pair grows logarithmically with the size of the scatternet.

Important Links:

Go Back