A pseudo random coordinated scheduling algorithm for Bluetooth scatternets

ABSTRACT

The emergence of Bluetooth as a default radio interface allows handheld devices to be rapidly interconnected into ad hoc networks. Bluetooth allows large numbers of piconets to form a scatternet using designated nodes that participate in multiple piconets. A unit that participates in multiple piconets can serve as a bridge and forwards traffic between neighbouring piconets. Since a Bluetooth unit can transmit or receive in only one piconet at a time, a bridging unit has to share its time among the different piconets. To schedule communication with bridging nodes one must take into account their availability in the different piconets, which represents a difficult, scatternet wide coordination problem and can be an important performance bottleneck in buillding scatternets. In this paper we propose the Pseudo-Random Coordinated Scatternet Scheduling (PCSS) algorithm to perform the scheduling of both intra- and inter-piconet communication. In this algorithm Bluetooth nodes assign meeting points with their peers such that the sequence of meeting points follows a pseudo random process that is different for each pair of nodes. The uniqueness of the pseudo random sequence guarantees that the meeting points with different peers the node will collide only occasionally. This removes the need for explicit information exchange between peer devices, which is a major advantage of the algorithm. The lack of explicit signaling between Bluetooth nodes makes it easy to deploy the PCSS algorithm in Bluetooth devices, while conformance to the current Bluetooth specification is also maintained. To assess the performance of the algorithm we define two reference case schedulers and perform simulations in a number of scenarios where we compare the performance of PCSS to the performance of the reference schedulers

REFERENCES

• 1: Bluetooth Special Interest Group. Bluetooth Baseband Specification Version 1.0 B. http://www.bluetooth.com/.
• 2: Bluetooth Special Interest Group. http://www.bluetooth.com/.
• 3: J. Haartsen. BLUETOOTH- the universal radio interface for ad-hoc, wireless connectivity. Ericsson Review, (3), 1998.
• 4: Z. Haraszti, I. Dahlquist, A. Farago, and T. Henk. Plasma - an integrated tool for ATM network operation. In Proc. International Switching Symposium, 1995.
• 5: N. Johansson, U. Korner, and P. Johansson. Performance evaluation of scheduling algorithms for Bluetooth. In IFIP TC6 WG6.2 Fifth International Conference on Broadband Communications (BC'99), Hong Kong, November 1999.
• 6: N. Johansson, U. Korner, and L. Tassiulas. A distributed scheduling algorithm for a Bluetooth scatternet. In Proc. of The Seventeenth International Teletraffic Congress, ITC'17, Salvador da Bahia, Brazil, September 2001.
• 7: P. Johansson, N. Johansson, U. Korner, J. Elgg, and G. Svennarp. Short range radio based ad hoc networking: Performance and properties. In Proc. of ICC'99, Vancouver, 1999.
• 8: M. Kalia, D. Bansal, and R. Shorey. MAC scheduling and SAR policies for Bluetooth: A master driven TDD pico-cellular wireless system. In IEEE Mobile Multimedia Communications Conference MOMUC'99, San Diego, November 1999.
• 9: M. Kalia, D. Bansal, and R. Shorey. MAC scheduling policies for power optimization in Bluetooth: A master driven TDD wireless system. In IEEE Vehicular Technology Conference 2000, Tokyo, 2000.
• 10: M. Kalia, S. Garg, and R. Shorey. Efficient policies for increasing capacity in Bluetooth: An indoor pico-cellular wireless system. In IEEE Vehicular Technology Conference 2000, Tokyo, 2000.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms

Keywords:
Bluetooth, inter-piconet communication, scatternet, scheduling