Performance of a new Bluetooth scatternet formation protocol

ABSTRACT

A Bluetooth ad hoc network can be formed by interconnecting piconets into scatternets. The constraints and properties of Bluetooth scatternets present special challegnes in forming an ad hoc network efficiently. In this paper, we evaluate the performance of a new randomized distributed Bluetooth scatternet formation protocol. Our simulations validate the theoretical results that our scatternet formation protocol runs in O(log n) time and sends O(n) messages. The scatternets formed have the following properties: 1) any device is a member of at most two piconets, and 2) the number of piconets is close to be optimal. These properties can avoid overloading of any single device and lead to low interference between piconets. In addition, the simulations show that the scatternets formed have O(log n) diameter. As an essential part of the scatternet formation protocol, we study the problem of device discovery: establishing multiple connecitons with many masters and slaves in parallel. We investigate the collision rate and time requirement of the inquiry and page processes. Deducing from the simulation results of scatternet formation and device discovery, we can verify that the total number of packets sent is O(n) and demonstrate that the maximum number of packets sent by any single device is O(log n). At last, we give estimates of the total time requirement of the protocol and suggest further improvements

REFERENCES

• 1: The Bluetooth Special Interest Group. http://www.bluetooth.com.
• 2: simjava. http://www.dcs.ed.ac.uk/home/hase/simjava/.
• 3: 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]
• 4: MIT Auto-ID Center. http://auto-id.mit.edu.
• 5: BlueHoc: Bluetooth performance evaluation tool. http://oss.software.ibm.com/developerworks/ opensource/bluehoc/.
• 6: Jennifer Bray , Charles Sturman, Bluetooth: Connect Without Cables, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 7: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 8: Samir R. Das , Robert Castañeda , Jiangtao Yan, Simulation-based performance evaluation of routing protocols for mobile ad hoc networks, Mobile Networks and Applications, v.5 n.3, p.179-189, Sept. 2000 [doi>10.1023/A:1019108612308]
• 9: Jaap Haartsen. Bluetooth - the universal radio interface for ad hoc, wireless connectivity. Ericsson Review, (3):110-117, 1998.
• 10: P. Johansson, N. Johansson, U. Korner, and G. Elg, J.and Svennarp. Short range radio based ad-hoc networking: performance and properties. In Proceedings of the IEEE International Conference on Communications 1999, volume 3, pages 1414-1420, 1999.
• 11: Ching Law , Amar K. Mehta , Kai-Yeung Siu, Performance of a new Bluetooth scatternet formation protocol, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501441.501442]
• 12: Ching Law and Kai-Yeung Siu. An O(log n) randomized resource discovery algorithm. In Brief Announcements of the 14th International Symposium on Distributed Computing, Technical Report, Technical University of Madrid, number FIM/110.1/DLSIIS/2000, pages 5-8, October 2000. Available at http://list.mit.edu/~ching/.
• 13: Ching Law and Kai-Yeung Siu. A Bluetooth scatternet formation algorithm. In Proceedings of the IEEE Symposium on Ad Hoc Wireless Networks 2001, San Antonio, Texas, USA, November 2001.
• 14: Amar Mehta. Ad-hoc network formation using Bluetooth scatternets. Master's thesis, June 2001.
• 15: 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
• 16: 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
• 17: Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 18: Bhaskaran Raman , Pravin Bhagwat , Srinivasan Seshan, Arguments for Cross-Layer Optimizations in Bluetooth Scatternets, Proceedings of the 2001 Symposium on Applications and the Internet (SAINT 2001), p.176, January 08-12, 2001
• 19: Theodoros Salonidis , Pravin Bhagwat , Leandros Tassiulas, Proximity awareness and fast connection establishment in Bluetooth, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 20: Theodoros Salonidis, Pravin Bhagwat, Leandros Tassiulas, and Richard LaMaire. Distributed topology construction of Bluetooth personal area networks. In Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 2001.
• 21: Stefan Zurbes. Considerations on link and system throughput of Bluetooth networks. In Proceedings of the 11th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, volume 2, pages 1315-1319, 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Performance, Theory, Verification

Keywords:
Bluetooth, ad hoc networks, resource discovery, topology construction