An 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
`
`
`
`
`
`
`
`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.
`
`types of connections that can be
`two
`There are
`established between a master and a slave:
`the
`Synchronous Connection-Oriented
`(SCO), and
`the
`Asynchronous Connection-Less
`(ACL)
`link. SCO
`
`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.
`
`
`
`
`
`1
`
`One-E-Way Ex. 2004
`Sony Corporation v. One-E-Way, Inc.
`IPR2016-1639
`
`

`
`connections 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.
`
`[3] suggests that the Bluetooth polling mechanism should
`be as simple as possible in order to satisfy the low cost
`objective. [4] divides the slaves into active and inactive
`slaves. Active slaves are polled in a round robin manner
`and each inactive slave is polled in an inter-poll interval
`regularly to check whether it has become active or not.
`The polling scheme divides the bandwidth between
`slaves in an efficient way if the traffic demand of each
`slave is known in advance. [5] and [6] assume that a
`master knows whether a slave has data packets to send or
`not and are thus, ideal schemes. A slave is not polled only
`if both master and slave queues have no data packets. [1]
`presents another ideal scheme in which the master keeps
`polling the same slave until both the master and queues
`are empty. The next slave to be chosen is the one for
`which the sum of the master and slave queue lengths is
`the largest.
`
`[1] also proposes a practical polling scheme, called
`Limited and Weighted Round Robin (LWRR), which
`achieves a high efficiency by reducing the rate of visits to
`queues, which have been found empty in previous visits.
`LWRR sets a weight equal to Max_Priority (MP) to each
`slave at the beginning. Each time a slave is polled and no
`data is exchanged between the master and the slave, the
`weight of the slave is reduced by 1. The lowest value of
`the weight of a slave is 1, in which case the slave has to
`wait a maximum of MP-1 cycles to get a chance to be
`polled. LWRR has the following disadvantages which
`arise due to the number of slots of a polling cycle being
`variable: (a) an inactive slave needs to wait for a long
`time to get a chance to exchange data packets if the
`previous polling cycles have a large number of slots. This
`can lead to high delay for an idle slave; (b) an idle slave
`is polled frequently if the previous polling cycles have a
`small number of slots. This may reduce the efficiency of
`the system.
`
`The PLsWRR scheme presented in this paper builds on
`the LWRR scheme presented in [1] and removes the
`disadvantages of the scheme presented above. We discuss
`this in the next section.
`
`
`III. Pseudo-Random Cyclic Limited and slot-
`Weighted Round Robin (PLsWRR)
`
`
`
`2
`
`

`
`A simple method to avoid this kind of unfairness is to use
`a pseudo-random cyclic fashion at the master to poll
`slaves. We use a simple pseudo-random cycle, in which
`the master assigns a unique random number from 1 to 7
`to each slave at the beginning of each polling cycle and
`then polls the slaves in increasing order of these numbers.
`
`
`first flow
`second flow
`sum of the two flows
`
`160
`140
`120
`100
`80
`60
`40
`20
`0
`
`Throughput (kbps)
`
`PRR
`
`Pseudo-random RR
`Polling schemes
`
`Figure 2. Fairness and utilization comparison (two
`CBR connections)
`
`first flow
`second flow
`sum of the two flows
`
`160
`140
`120
`100
`80
`60
`40
`20
`0
`
`Throughput (kbps)
`
`PRR
`
`Pseudo-random RR
`Polling schemes
`
`Figure 3. Fairness and utilization comparison (two
`FTP connections)
`To show the increased fairness gained by using a pseudo-
`random ordering of slaves in a cycle we present
`simulation results of two experiment sets. The simulation
`environment used in this study was based on GloMoSim
`[7], a scalable simulation library, which was extended
`with a simulation model of the Bluetooth protocol. The
`Bluetooth baseband and L2CAP layers were implemented
`according to the specifications [3]. The simulated time
`for all experiments was 180 seconds.
`
`The PLsWRR scheme has the following two important
`properties: (1) the order in which slaves are polled in
`each cycle is determined in a pseudo-random manner. (2)
`the rate of polling to less active slaves is reduced by
`taking into account the traffic history.
`
`We first discuss why it is important for Bluetooth polling
`schemes to poll slaves in a pseudo-random cyclic fashion.
`
`
`Figure 1.Topology of the architecture showing 7
`slaves in a piconet
`Importance of Pseudo-Random Cycle of Polling:
`
`Consider the piconet shown in Figure 1, consisting of 7
`slaves. We note that data packets from one slave to
`another are first sent to the master, which stores them in a
`queue and then forwards them to the destination slave.
`Suppose slaves 2 and 4 generate heavy traffic to
`destination slave 6. We assume that slave 2, slave 4 and
`slave 6 get the same amount of polling since each of
`these master-slave links has the same queue status (one
`end has data packets, other has no data packets). Since
`packets from slave 2 and slave 4 share the master’s
`queue, the number of packets from slave 4 in the queue
`may depend not only on the slave 4-master link, but also
`on the slave 2-master link. For example, if the master
`polls the slaves in a fixed ordered polling cycle from
`slave 1 to slave 7, the master’s queue can be filled by
`packets from slave 2 if the master polls the slave 2
`always before slave 4. Thus, a fixed-ordered polling cycle
`may not be able to impart fairness to the slaves.
`
`
`
`
`
`
`3
`
`

`
`first flow
`third flow
`fifth flow
`sum of the flows
`
`second flow
`fourth flow
`sixth flow
`
`160
`140
`120
`100
`80
`60
`40
`20
`0
`
`Throughput (kbps)
`
`first flow
`third flow
`fifth flow
`sum of the flows
`
`second flow
`fourth flow
`sixth flow
`
`160
`140
`120
`100
`80
`60
`40
`20
`0
`
`Throughput (kbps)
`
`1
`
`2
`
`4
`3
`No. of active slaves
`
`Figure 4. Fairness and utilization comparison with
`Pure RR (FTP connections)
`
`5
`
`6
`
`1
`
`2
`
`4
`3
`No. of active slaves
`
`Figure 5. Fairness and utilization comparison with
`Pseudo-random RR (FTP connections)
`
`5
`
`6
`
`We add the pseudo-random cyclic feature to PRR in
`order to see the effects of this feature on fairness; we call
`this
`scheme Pseudo-Random PRR.
`In
`the
`first
`experiment, we compare the performance of the Pure
`Round Robin (PRR) and Pseudo-random Round Robin
`(Pseudo-random RR) schemes in a piconet consisting of 7
`slaves as shown in Fig 1. Both Slave 2 and slave 4 have
`either a CBR or a TCP connection with the destination
`being slave 6. Fig 2 shows the results when the
`connection is of type CBR, while Fig 3 shows the results
`when the connection is TCP. The “first flow” in the
`figures refers to the flow from slave 2, whereas the
`“second flow” refers to the flow from slave 4. We
`observe that the PRR polling scheme gives an unequal
`throughout to the two flows (both for CBR and TCP),
`while the pseudo-random PRR scheme divides the
`bandwidth equally between the flows.
`
`In the next experiment, we again consider the piconet of
`Fig 1. We now vary the number of connections in the
`piconet from 1 to 6, with each connection starting from a
`different slave and having the same slave as destination.
`The type of the connection is TCP. Fig 4 and Fig 5 show
`the results for PRR and Pseudo-Random RR respectively.
`Again, we see a much greater fairness in pseudo-random
`RR as compared to PRR.
`
`We now consider a polling scheme which has the second
`of the two features presented at the beginning of this
`section, i.e., the scheme reduces the rate of polling to less
`active slaves using the traffic history. We call this the
`LsWRR (Limited slot-weighted Round Robin) scheme.
`The LsWRR scheme extends the LWRR (Limited
`
`
`
`4
`
`
`Weighted Round Robin) scheme by adopting a weighted
`round robin algorithm where weights of slots are
`dynamically changed according to the observed previous
`polling cycle status. Each slave is assigned a slot-weight
`equal to Max-Slot-Priority (MSP) at the beginning. If a
`slave is polled and no data is exchanged, the slot-weight
`of the slave is reduced by the number of slots of the
`previous cycle (N). Each time it is the slave’s chance to
`get polled in the cyclic ordering, the master checks to see
`if the slave has skipped as many slots as is the difference
`between its current slot-weight with the MSP and polls
`the slave only if this condition is true. The lowest value
`that the slot-weight can take is equal to 1. Anytime there
`is a data exchange between the slave and the master, the
`slot-weight of the slave is increased to the MSP value.
`
`We see that LsWRR uses number of slots as opposed to
`number of cycles (as in LWRR) as a method to reduce
`the polling given to less active slaves. LsWRR guarantees
`that a slave waits up to a maximum of MSP slots to get a
`chance to be polled. This makes the behavior more
`reliable as compared with LWRR, in which the slave
`waits a bounded number of cycles, but the length of these
`cycles may be variable. Thus, unlike LWRR, LsWRR
`effectively works effectively irrespective of the length of
`the previous polling cycles. Thus, LsWRR removes the
`two disadvantages of LWRR that we pointed out earlier.
`
`We now add to LsWRR, the pseudo-random ordering of
`slaves, and call this scheme PLsWRR. A detailed
`PLsWRR specification through pseudo-code can be
`found in Figure 8.
`
`

`
`first flow
`third flow
`fifth flow
`sum of the flows
`
`second flow
`fourth flow
`sixth flow
`
`300
`
`250
`
`200
`
`150
`
`100
`
`50
`
`0
`
`Throughput (kbps)
`
`first flow
`third flow
`fifth flow
`sum of the flows
`
`second flow
`fourth flow
`sixth flow
`
`1
`
`2
`
`4
`3
`No. of active slaves
`
`Figure 7. Fairness and utilization comparison with
`Pseudo-random LsWRR (FTP connections)
`
`5
`
`6
`
`
`From the experiments in this section, we conclude that it
`is important for Bluetooth polling schemes to use a
`pseudo-random cyclic order of polling slaves. In the next
`section, we evaluate the performance of PLsWRR polling
`scheme through simulations and compare it with other
`polling schemes.
`
`
`IV. PERFORMACE EVALUATION
`
`
`In this section, we evaluate the performance of the
`PLsWRR polling scheme and show that it achieves high
`throughput and fairness. We simulate a piconet consisting
`of 7 slaves as shown in Figure 1 and vary the number of
`active slaves from 1 to 7. The simulated time for all
`experiments is 200 seconds; the routing protocol used is
`AODV. The value of L for LRR, LWRR and PLsWRR is
`taken to be 3; the value of MP for LWRR is taken to be 3.
`The value of MSP for PLsWRR is taken to be 160 slots,
`which gives the maximum waiting time for a slave to be
`polled as 100ms.
`
`In the experiments, we are interested in the throughput
`and delay behavior exhibited by the PLsWRR scheme
`and the four practical schemes, which do not require
`knowledge of slave queues. These practical schemes are:
`
` (cid:1)
`
` Round Robin (PRR): In this scheme, slaves are
`polled in a cyclic order and a master-slave queue pair
`is given a single chance to transmit in each cycle (i.e.,
`both the master and the slave can send once). The
`cyclic order is fixed.
`
`
`
`5
`
`300
`
`250
`
`200
`
`150
`
`100
`
`50
`
`0
`
`Throughput (kbps)
`
`1
`
`2
`
`4
`3
`No. of active slaves
`
`Figure 6. Fairness and utilization comparison with
`LsWRR (FTP connections)
`
`5
`
`6
`
`
`
`Nomenclature
`N:
`number of slots of previous cycle
`L:
`the max number of transmissions that can be performed
`by each pair per cycle
`MSP: Max Slot Priority
`SW: slot weight of the slave
`SS: number of slots has been skipped for the slave
`
`For each polling cycle
`Each slave is assigned a unique random number from 1 to 7
`Defined a dynamic polling cycle according to the random
`numbers permutation.
`For each slave in the polling cycle:
`If (MSP - SW < SS)
`Polls the slave until L times or no data packet is
`exchanged
`If (no data packet is exchanged)
`SW = max (SW – N, 1)
`else
` SW = MSP; SS = 0
`endif
`else
`SS = SS + N
`endif
`Figure 8. Pseudo code of PLsWRR algorithm
`
`
`We now repeat the previous experiment replacing RR
`with LsWRR and Pseudo-Random RR with PLsWRR.
`The value of L for LWRR is taken to be 3. The value of
`MSP for both LsWRR and PLsWRR is taken to be 160
`slots (160 * 0.625ms), which gives the maximum waiting
`time for a slave to be polled as 100ms. Fig 6 and Fig 7
`show the results. Again, we see that the PLsWRR is able
`to provide much greater fairness than LsWRR.
`
`
`
`

`
`PRR
`LWRR
`
`LRR
`PLsWRR
`
`0.25
`
`0.2
`
`0.15
`
`0.1
`
`0.05
`
`0
`
`Average Delay (s)
`
`1
`
`2
`
`5
`4
`3
`No. of active slaves
`Figure 10. Average End-to-End delays
`ON:OFF ratio 1:1
`
`6
`
`7
`
`
`for
`
`PRR
`LWRR
`
`LRR
`LsWRR
`
`700
`600
`500
`400
`300
`200
`100
`0
`
`Throughput (kbps)
`
`1
`
`2
`
`5
`4
`3
`No. of active slaves
`
`Figure 11. System Throughput of FTP connections
`for PRR, LRR, LWRR, and PLsWRR
`
`6
`
`7
`
`first flow
`second flow
`third flow
`fourth flow
`fifth flow
`sixth flow
`severnth flow
`sum of the flows
`
`700
`
`600
`
`500
`
`400
`
`300
`
`200
`
`100
`
`0
`
`Throughput (kbps)
`
`1
`
`2
`
`5
`4
`3
`No. of active slaves
`
`Figure 12. Fairness and utilization comparison
`with Pseudo-random LsWRR (FTP connections)
`
`6
`
`7
`
`1
`
`2
`
`800
`
`700
`
`600
`
`500
`
`400
`
`300
`
`200
`
`Throughput (kbps)
`
`100
`
`0
`
`PRR
`LWRR
`ERR
`5
`4
`3
`No. of active slaves
`
`Figure 9. System throughput for ON:OFF ratio
`1:1
`
`LRR
`PLsWRR
`
`6
`
`7
`
` (cid:1)
`
` Exhaustive Round Robin (ERR): This scheme
`defines a fixed cyclic order as in the case of PRR, but
`the master keeps polling the same slave until both the
`master and slave queues are empty.
`(cid:1) Limited Round Robin (LRR): In this scheme, slaves
`are polled in a fixed cyclic order and a master-slave
`queue pair is given a limited number of chances to
`transmit in each cycle.
`(cid:1) Limited and Weighted Round Robin (LWRR): This
`scheme adopts a cycle-weighted
`round
`robin
`algorithm with the weights dynamically changed
`according to the observed queue status ([1]).
`
`
`In the first experiment, we consider an ON:OFF CBR
`connection from each slave to the master. The CBR data
`rate is 250 packets/s and the packet size is 340 bytes.
`Each connection continually sends CBR packets for 30
`seconds and then idles for 30 seconds. Figure 9 shows
`that LsWRR and ERR give a higher throughput than the
`other schemes. However, using an ERR scheme may
`cause an unfair sharing of capacity between slaves [1].
`The PRR scheme gives the poorest performance, as it has
`to poll the idle slaves with as much frequency as the
`slaves that have data to exchange with the master.
`PLsWRR removes the inefficiency in LWRR caused by a
`variable polling cycle length (this was discussed earlier).
`It, thus, achieves a better performance than LWRR.
`Figure 10 shows that PLsWRR also gives a lower delay
`compared with the other schemes.
`
`
`
`6
`
`

`
`Environment," Technical report 990027, UCLA, Computer
`Science Department, 1999.
`
`In the next experiment, we consider active TCP traffic
`sources and run simulations with TCP connections from
`each slave to the master. Figure 11 shows that PLsWRR
`gives better performance than the other schemes and
`Figure 12 shows that all flows share the total capacity in
`a piconet equally with PLsWRR. The pseudo-random
`cyclic order in PLsWRR provides fairness to the flows.
`
`V. CONCLUSIONS
`
`
`In this paper, we proposed an efficient Bluetooth polling
`scheme called PLsWRR. This scheme builds on the
`LWRR scheme presented earlier by adopting a slot-
`weighted round robin algorithm. It improves performance
`in a piconet with few “active ” slaves by reducing the
`rate of visits to queues, which have been found empty
`during the last visit. Moreover, it polls slaves in a pseudo-
`random cyclic order and this enables flows to share the
`capacity equally. We also showed through simulations
`that this scheme is fair and capable of achieving high
`utilization of the piconet bandwidth. We also studied the
`performance of other related Bluetooth polling schemes
`by simulations and compared their performance with that
`of our scheme.
`
`
`REFERENCES
`
`
`[1] A. Capone, R. Kapoor and M. Gerla: “Efficient Polling
`Schemes for Bluetooth Picocells”, IEEE ICC 01, Finland,
`June, 2001.
`[2] J. Haartsen, “The Bluetooth Radio System”, IEEE
`Personal Communications Volume: 7 1, February 2000 ,
`Page(s): 28 –36.
`[3] Bluetooth Special Interest Group, “Specification of the
`Bluetooth System 1.0b, Volume 1: Core” December 1999.
`[4] N. Johansson, U. Korner, P. Johansson, “Performance
`Evaluation of Scheduling Algorithms for Bluetooth”, In
`Broadband Communications: Convergence of Network
`Technologies, Edited by Danny H. K. Tsang and Paul J.
`Kuhn.
`[5] S. Garg, M.Kalia, R. Shorey, “MAC Scheduling Policies
`and SAR Policies for Bluetooth: A Master Driven TDD
`Pico-Cellular Wireless System”, MoMuc 99, pp. 384-386
`[6] M. Kalia, D. Bansal, R. Shorey, “Data scheduling and
`SAR for Bluetooth MAC”, IEEE VTC 2000-Spring
`Tokyo, pp-716-720
`[7] M. Takai L, Bajaj, R, Ahuja, R. Bagrodia and M. Gerla,
`"GloMoSim: A
`Scalable Network
`Simulation
`
`
`
`7