Godfrey Tan, John Guttag
IASTED International Conference on Communications and Computer Networks, Cambridge, MA, 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.
[PDF (105KB)] [PostScript (176KB)]
Bibtex Entry:
@inproceedings{tan2002efficient,
author = "Godfrey Tan and John Guttag",
title = "{An Efficient Scatternet Formation Algorithm for Dynamic Environments}",
booktitle = {IASTED International Conference on Communications and Computer Networks},
year = {2002},
month = {November},
address = {Cambridge, MA}
}