In recent years, wireless ad hoc networks have been a growing area of research. While there has been considerable research on the topic of routing in such networks, the topic of topology creation has not received due attention. This is because almost all ad hoc networks to date have been built on top of a single channel, broadcast-based wireless media, suchas 802.11 or IR LANs. For such networks the distance relationship between the nodes implicitly (and uniquely) determines the topology of the ad hoc network.

Bluetooth is a promising new wireless technology that enables portable devices to form short-range wireless ad hoc networks and is based on a frequency hopping physical layer. This fact implies that hosts are not able to communicate unless they have previously discovered each other by synchronizing their frequency hopping patterns. Thus, even if all nodes are within direct communication range of each other, only those nodes which are synchronized with the transmitter can hear the transmission.

To support any-to-any communication, nodes must be synchronized so that the pairs of nodes (which can communicate with each other) together form a connected graph.

Using Bluetooth as an example, this paper first provides deeper insights into the issue to link establishment in frequency hopping wireless systems. It then introduces the Bluetooth Topology Costruction Protocol (BTCP), an asynchronous distributed protocol for constructing scatternets which starts with nodes that have no knowledge of their surroundings and terminates with the formation of a connected network satisfying all connectivity constraints posed by the Bluetooth technology.

To the best of our knowledge, the work presented in this paper is the first attempt at building Bluetooth scatternets using distributed logic and is quite "practical" in the sense that it can be implemented using the communication primitives offered by the Bluetooth 1.0 specifications.