An Efficient Scatternet Formation Algorithm for Dynamic Environments

Godfrey Tan and John Guttag
IASTED International Conference on Communications and Computer Networks, November, 2002.

There is increasing interest in wireless ad hoc networks built from portable devices equipped with short-range wireless network interfaces such as Bluetooth. This paper addresses issues related to internetworking such networks to form larger ``scatternets.'' Within the constraints imposed by the emerging standard Bluetooth link layer and MAC protocol, we describe an efficient online scatternet topology formation 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.

[PostScript (180KB)] [PDF (108KB)]

Bibtex Entry:

@inproceedings{tan02ccn,
  author =       "Godfrey Tan and Allen Miu and Hari Balakrishnan and John Guttag",
  title =        "{An Efficient Scatternet Formation Algorithm for Dynamic Environments}",
  booktitle =    "{IASTED International Conference on Communications and Computer Networks (CCN02)}",
  year =         2002,
  month =        Nov,
  address =      {Cambridge, MA},
}