Motivation

The ubiquitous use of information intensive consumer devices such as cell phones, personal digital assistants (PDAs), and laptop computers have called for a new networking paradigm for interconnecting them. The goal is to create a personal area network (PAN) that accommodates seamless information transfer between different devices with varying capacity in an ad hoc manner without the need for manual configuration, cables, or wired infrastructure. In December, 1999, an industry consortium known as the Bluetooth Special Interest Group standardized Version 1 of a short-range, low-power, RF technology called Bluetooth motivated in part by the need for suitable link-layer PAN technologies. The Bluetooth communication substrate, consisting of Radio, Baseband, Link Controller and Link Manager, specifies mechanisms for establishing connection with nearby devices in an ad hoc manner. Unlike traditional wireless LANs which rely on distributed contention resolution mechanisms, Bluetooth is based on a centralized master-slave polling scheme known as Time Division Duplex (TDD). Furthermore, Bluetooth achieves robustness against interference from nearby devices by employing a Frequency Hopping Code Division Multiple Access (FH-CDMA) technique. 

Because frequency-hopping facilitates high densities of communicating devices, it is possible for dozens of piconets to co-exist and independently communicate in close proximity without significant performance degradation. The Bluetooth specification alludes to this concept of internetworking multiple piconets, calling it a scatternet, but does not specify how it is to be done. Before this concept becomes a reality, we need to solve a number of challenging problems. 

Blueware is an effort to identify these challenges clearly and solve them so that self-organizing Bluetooth scatternets can be realized. We identify the three main challenges as: i) topology formation, ii) link scheduling, and iii) packet routing. In broadcast based wireless LANs such as 802.11, the network topology is determined by the physical distance between nodes. In Bluetooth, an explicit topology formation process is required since nearby devices need to discover each other and explicitly establish a point-to-point link. During the link formation process, the two Bluetooth nodes synchronize the frequency hopping sequence and gather necessary clock information. The essential ad hoc discovery process could be lengthy and clever solutions are required to quickly form a network topology that spans across all nodes within the transmission proximity.

A link scheduling mechanism is necessary since relay nodes need to communicate in multiple channels or links. This is because Bluetooth devices, each with a single radio chip, can only be active on a particular channel at a time and thus, nodes must communicate in different channels on a time division basis. Hence, a link scheduling mechanism is required for neighboring nodes to carry out successful packet transfers. In fact, the overall performance of the scatternet-wide communication critically depends on the scheduling mechanism which dictates the bandwidth utilization, end-to-end latency and the energy usage.

A routing mechanism is also essential to route packets over a multi-hop scatternet. Small Bluetooth packet size and low memory and energy requirements dictate the design of ad hoc scatternet routing protocols.

Approach

Scatternet Formation

Our approach attempts to form a scatternet topology which simplifies both scheduling and routing problems while minimizing the number of piconets which a relay node participates in (as opposed to the total number of piconets). We have developed an efficient topology formation algorithm, called TSF (for Tree Scatternet Formation), which assigns master/slave roles to nodes while connecting them in a tree structure. Our algorithm is both decentralized and self-healing, in that nodes can join and leave at any time without causing long disruptions in connectivity. It also decides dynamically and in a distributed fashion which nodes act as masters and which as slaves, thus avoiding manual configuration of roles to nodes or centralized decision making. Furthermore, our scheme does not require any communication between nodes already in the scatternet, using only Bluetooth's lower-layer primitives for detecting potential nodes to form links with and establish communication links.

People

Hari Balakrishnan
John Guttag
Allen Miu
Godfrey Tan

Publications

Godfrey Tan and John Guttag. A Locally Coordinated Scatternet Scheduling Algorithm. In the 27th Annual IEEE Conference on Local Computer Networks (LCN), Tampa, FL, Novemeber, 2002. [ps, pdf]

Godfrey Tan, Allen Miu, John Guttag, and Hari Balakrishnan. An Efficient Scatternet Formation Algorithm for Dynamic Environments. In IASTED Communications and Computer Networks (CCN), Cambridge, MA, November, 2002. [ps, pdf]

Godfrey Tan. Blueware: Bluetooth Simulator for ns. MIT Technical Report, MIT-LCS-TR-866, Cambridge, MA, October, 2002. [ps, pdf]

Godfrey Tan. Self-organizing Bluetooth Scatternets. SM Thesis, Massachusetts Institute of Technology, January, 2002. [ps, pdf]

Godfrey Tan. Interconnecting Bluetooth-like Personal Area Networks. In 1st Annual Oxygen Workshop, Gloucester, MA, 2001. [ps, pdf]

Godfrey Tan, Allen Miu, John Guttag and Hari Balakrishnan. Forming Scatternets from Bluetooth Personal Area Networks. MIT Technical Report, MIT-LCS-TR-826, Cambridge, MA, October, 2001. [ps, pdf]

Software

Blueware simulator 1.0 is implemented as an extension module to ns-2 and availabe for download.