ABSTRACT1An Efficient and Fair Polling Scheme for Bluetooth Yeng-Zhong Lee Rohit Kapoor Mario Gerla UCLA Computer Science WAM Lab Los Angeles CA, 90095 (yenglee, rohitk, gerla)@cs.ucla.edu ABSTRACT Bluetooth is a universal radio interface in the 2.45Ghz frequency band, which will enable users to connect a range of small electronic devices. Any two or more Bluetooth-enabled devices that come within range of each other can set up an ad hoc connection, called a piconet. Within a piconet, the unit that establishes the piconet becomes the master and the rest of the units act as slaves. The master sends a data or POLL packet to poll a slave and the slave responds with a packet in the next time slot. The manner in which the master polls the slaves has a significant impact on the system performance. In this paper, we first discuss previously proposed polling schemes for Bluetooth. We then propose a new polling scheme called Pseudo-Random Cyclic Limited slot-Weighted Round Robin (PLsWRR) that builds on the Limited Weighted Round Robin (LWRR) scheme presented in [1]. The PLsWRR scheme has the following two important properties: (i) As in LWRR, it tries to distinguish between slaves on the basis of their “activeness”, i.e., according to the traffic history. LsWRR reduces the rate of polling to less active slaves by not polling them for a certain number of slots (as opposed to cycles). This keeps the maximum time that a slave may not be polled bounded. (ii) The order in which slaves are polled in each cycle is determined in a pseudo-random manner. We show that it is very important to use a pseudo-random ordering of slaves in a cycle and that a polling scheme that does not employ a pseudo-random ordering can easily lead to unfairness among TCP connections. We also show by means of simulations that the PLsWRR scheme performs consistently well on scenarios with different traffic sources like TCP and CBR and achieves high throughput and fairness. I. INTRODUCTION Bluetooth is a universal radio interface in the 2.45Ghz frequency band, which will enable users to connect a range of small electronic devices such as notebook computers, cellular phones and other portable handheld devices easily and quickly, without the need for cables. The key features of Bluetooth that distinguish it from other wireless standards are its minimal hardware dimensions, low complexity, low price and low power consumption [2]. These hardware characteristics imply that Bluetooth may be used in a variety of avenues to form short-range wireless ad hoc networks. Any two or more Bluetooth-enabled products that come within range of each other can set up an ad hoc connection, called a piconet. Within a piconet, a Bluetooth unit can be either a master or a slave. Each piconet has one master and up to seven active slaves. Any unit can be the master, but usually the unit that establishes the piconet becomes the master. Bluetooth provides full-duplex transmission using a Time-Division Duplex (TDD) scheme to divide the channel into 625us time slots. Master and slave transmit alternately. Master-to-slave transmissions always start in an even-numbered time slot, while the slave-to-master transmissions always start in an odd numbered time slot. Each piconet is characterized by a particular fast frequency-hopping pattern, the hopping rate being 1600 hops/s; the frequency is uniquely determined by the master’s address and followed by all the devices participating in the piconet. The frequency hopping mechanism allows the overlapping of different piconets in the same space without a significant increase in interference. There are two types of connections that can be established between a master and a slave: the Synchronous Connection-Oriented (SCO), and the Asynchronous Connection-Less (ACL) link. SCO2connections provide a circuit-oriented service with constant bandwidth based on a fixed and periodic allocation of slots. ACL connections provide a packet-oriented service and span over 1,3 or 5 slots [2]. For ACL links, Bluetooth uses a fast acknowledgment and retransmission scheme to ensure reliable transfer of data. The master polls each slave, controlling the traffic within a piconet. A slave is only allowed to transmit after the master has polled it. The problem of finding an efficient polling algorithm for piconets is quite similar to the problem of centrally controlled polling schemes. However, the constraints added by the four key characteristics of Bluetooth: (i) lack of information of the slave queue at the master, (ii) only a slave unit that has been directly addressed by the master in the previous time slot is allowed to transmit data, (iii) a slot gets wasted if the master uses a no payload (POLL) packet to poll a slave, or a slave is polled and the slave has no data to send (NULL), (iv) the polling mechanism must be kept as simple as possible in order to satisfy the low cost objective, will significantly impact the performance of data traffic over Bluetooth. In this paper, we propose a new polling scheme called Pseudo-Random cyclic Limited slot-Weighted Round Robin (PLsWRR) that builds on the Limited Weighted Round Robin (LWRR) scheme presented in [1]. The LsWRR scheme has the following two important properties: (i) It tries to distinguish between slaves on the basis of their “activeness”, i.e., according to the traffic history. (ii) The order in which slaves are polled in each cycle is determined in a pseudo-random manner. We show that it is very important to use a pseudo-random ordering of slaves in a cycle and that a polling scheme that does not employ a pseudo-random ordering can easily lead to unfairness among TCP connections. The rest of the paper is organized as follows. Section II discusses related work and the motivation for this paper. Section III presents the PLsWRR polling scheme and discusses its important features. Section IV compares the performance of the PLsWRR polling scheme with other previously proposed polling schemes. Finally, Section V concludes the paper. II. RELATED POLLING SCHEMES In this section, we first review related polling schemes for Bluetooth. These schemes broadly fall under two categories: ideal and practical. The ideal schemes assume that the master has complete and updated knowledge of the queue status of the slaves. The practical schemes do not make any such assumption and are practically realizable; the ideal schemes serve as good performance benchmarks.
View Full Document
Unlocking...