In this paper we introduce a novel and unified approach to the problems of device discovery and scatternet formation for the
Bluetooth standard. We introduce a stochastic model for Bluetooth device discovery and prove that a protocol based on very
simple local rules generates a topology that, with high probability, is connected and, crucially, has constant maximum degree.
Based on this, we develop a new protocol for device discovery and scatternet formation for multi-hop BlueTooth networks. By
means of extensive ns2 simulations we show that our solution is simple to implement, fast and requires low overhead, both
for the device discovery and the scatternet formation phases, and leads to better performance when compared to the major approaches
so far proposed in the literature.
Keywords Scatternet formation - Bluetooth - Personal area networks - Ad hoc networks
Research supported by EC projects MAGELLAN and DELIS.
Devdatt Dubhashi received his B.Tech. degree in Computer Science and Engineering from the Indian Institute of Technology, Delhi and his Masters
and Ph.D. degrees from Cornell University, Ithaca, NY. He spent two years at the Max-Planck-Institut fur Informatik in Saarbrucken,
Germany and two and a half years at BRICS (Basic Research in Computer Science) University of Aarhus, Denmark. Thereafter he
was an Assistant Professor at the Indian Institute of Technology, Delhi. His random walk finally reached its current position
as Associate Professor, Department of Computer Science and Engineering at Chalmers and Gothenburg University, Sweden. His
main research interests are in exploring the unusual effectiveness of probability (and other discrete Mathematics) in Computer
Science.
Olle Häggström is a professor of mathematical statistics at Chalmers University of Technology, Sweden. His research interests are mainly
in probability theory and statistical mechanics. He is vice chairman of the Swedish Mathematical Society, and in 2004 he was
elected fellow of the Nobel Prize awarding Royal Swedish Academy of Sciences.
Gabriele Mambrini received the laurea degree in Computer Science from the University of Rome, “La Sapienza,” Italy, in March 2003. He is currently
with the Italian Interuniversities Consortium for Supercomputing Applications (CASPUR), in Rome. His current research interests
include wireless networking, automatic text categorization and indexing, computer security.
Alessandro Panconesi is professor of Computer Science at the University “La Sapienza” of Rome. He has a PhD in Computer Science from Cornell University.
He was awarded the ACM Danny Lewin Award in 1992. His main research interest is the design and analysis of probabilistic and
distributed algorithms. He is the Director of BICI (Bertinoro International Center for Informatics).
Chiara Petrioli received the Laurea degree with honors in computer science in 1993, and the Ph.D. degree in computer engineering in 1998,
both from Rome University “La Sapienza,” Italy. She is currently Assistant Professor at the Computer Science Department at
Rome University “La Sapienza”. Her current work focuses on ad hoc and sensor networks, Bluetooth, energy-conserving protocols,
QoS in IP networks and Content Delivery Networks. Prior to Rome University she was research associate at Politecnico di Milano
and was working with the Italian Space agency (ASI) and Alenia Spazio. Dr. Petrioli is an area editor of the ACM/Kluwer Wireless
Networks journal, the Wiley InterScience Wireless Communications & Mobile Computing journal and the Elsevier Ad Hoc Networks
journal. She has served in the organizing committee and technical program committee of several leading conferences in the
area of networking and mobile computing including ACM Mobicom, ACM Mobihoc, IEEE ICC. Dr. Petrioli was a Fulbright scholar,
and is a member of ACM and IEEE.