Dynamic construction of Bluetooth scatternets of fixed degree and low diameter

ABSTRACT

Bluetooth is a promising recent radio technology for ad hoc networking. Bluetooth networks are based on connecting together piconets, to form a scatternet. The structure of the scatternet, and the way the scatternet is built and maintained, are not part of the Bluetooth specifications, but have a tremendous impact on the performance of the network. We present an efficient distributed algorithm for Bluetooth scatternet construction. The resulting scatternet is scalable and our construction is dynamic in the sense that nodes can join and leave the network at their convenience. For fixed constant degree of nodes, the resulting diameter is polylogarithmic in the size of the network, and the connectivity of the masters is high. We also give a routing protocol adapted to the specific scatternet topology returned by our algorithm. This protocol does not require complicated path-discovery methods, but is based on a simple virtual labeling of the devices participating in the scatternet.

REFERENCES

• 1: P. Bhagwat and A. Segall, A routing vector method (RVM) for routing in Bluetooth scatternets. In 6th IEEE Int. Workshop on Mobile Multimedia Communications (MOMUC '99), 1999.
• 2: P. Bhagwat and S. Rao, On the characterization of Bluetooth scatternet topologies. Tech. Report, Dept. of CS, Univ. of Maryland, USA. 2001. http://www.cs.umd.edu/~pravin/.
• 3: Bluetooth Special Interest Group. http://www.bluetooth.com.
• 4: Jennifer Bray , Charles Sturman, Bluetooth: Connect Without Cables, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 5: K. Fleming, R. Hunter, J. Inouye, and J. Schiffer, Enabling Always On, Always Connected (AOAC) Computing with Bluetooth Technology. Intel Technology Journal, Number Q2, 7--14, 2000.
• 6: C. Law and K.-Y. Siu, A Bluctooth Scatternet Formation Algorithm. To appear in the 1st IEEE Symp. on Ad-Hoc Wireless Networks (SAWN '01), San Antonio, Texas, USA, Nov. 2001.
• 7: Gy. Miklós , A. Rácz , Z. Turányi , A. Valkó , P. Johansson, Performance aspects of Bluetooth scatternet formation, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 8: Brent A. Miller , Chatschik Bisdikian, Bluetooth revealed: the insider's guide to an open specification for global wireless communication, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 9: C. Perkins, Ad hoc networking. Addison Wesley, 2000.
• 10: Lakshmi Ramachandran , Manika Kapoor , Abhinanda Sarkar , Alok Aggarwal, Clustering algorithms for wireless ad hoc networks, Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.54-63, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345848.345860]
• 11: T. Salonidis, P. Bhagwat, L. Tassiulas, and R. LaMaire, Distributed topology construction of Bluetooth personal area networks. Proceedings of of IEEE INFOCOM, April 2001.
• 12: G. Tan, A. Miu, J. Guttag, and H. Balakrishnan. Forming scatternets from Bluetooth personal area networks. MIT Technical Report MIT-LCS-TR-826, October 2001.
• 13: W. Wallis, Combinatorial Design. Marcel Dekker, New York, 1988.
• 14: Z. Wang, R. J. Thomas, and Z. Haas, Bluenet - A new scatternet formation algorithm. Proceedings of the 35th Hawaii International Conference on System Sceiences, 2002.
• 15: G. V. Zaruba, S. Basagni, and I. Chlamatac, Bluetrees - Scatternet formation to enable Bluetooth-based ad hoc networks. Proceedings of IEEE ICC, vol. 1, pp. 273--277, June 2001.
• 16: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 17: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 18: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 19: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory