Efficient Policies for Increasing Capacity in
`Bluetooth: An Indoor Pico-Cellular Wireless
`System
`
`Manish Kalia, Sumit Garg, Rajeev Shorey
`IBM India Research Laboratory,
`Block 1, Indian Institute of Technology,
`Hauz Khas, New Delhi 110016, India.
`Email: srajeev@in.ibm.com, Phone: 91-11-6861100, Fax: 91-11-6861555
`
`Abstract—In indoor pico-cellular wireless systems, such as Bluetooth ,
`a pico-cell has a Master-Slave configuration. Bluetooth is a Centralized
`Master driven system that supports Time Division Duplex Medium Access
`Control. A pico-cell has a limit on the maximum number of active Slaves.
`In Bluetooth, a pico-cell can have a maximum of seven Slaves in active state
`(capable of transmitting and receiving data). The remaining Slaves in a
`pico-cell remain in an inactive state. Having more than seven slaves con-
`nected to the Master can be advantageous in many situations. Having a
`large number of Slaves in one pico-cell as compared to forming new pico-
`cells can lead to lower power consumption and a relatively simple network
`architecture. In this paper we investigate different methods of increasing
`the capacity of Bluetooth pico-cells. We propose new policies using the
`Park mode to increase the number of Slaves virtually connected to a Mas-
`ter. These policies can have a significant impact on system parameters such
`as the throughput, packet delays and dropping probability of packets.
`
`I. INTRODUCTION
`As we see an explosion of activities in the area of wire-
`less networks, it is desirable to see a wireless solution that
`brings all the multiple technologies/standards in different
`sectors together and at the same time provide a universal
`and ubiquitous connectivity solution between computing,
`communication and supporting devices. Bluetooth is an
`effort to realize this vision [1], [2].
`The physical constraints of the wireless medium often
`lead naturally to a Master-Slave configuration [4], [1]. In a
`Master-Slave configuration, one of the stations in a cell is
`the Master (this could be the fixed Access Point or the Base
`Station) and the other remote stations are Slaves (e.g., the
`handheld devices such as palmtop computers, cell phones,
`pagers). The need for simplicity and low complexity has
`made Time Division Duplex (TDD) one of the promising
`candidates for medium access control (MAC) in wireless
`systems having a Master-Slave configuration. In TDD, the
`forward (i.e., Master to Slave) and the reverse (i.e., Slave
`to Master) links occur in pairs, i.e., after data is sent by
`the Master over the forward link, the subsequent slot is re-
`served for the Slave to transmit data in the reverse link.
`This mode of operation makes multiple access straight-
`forward, since the Master provides a single point of co-
`ordination. Proposed standards for low-power, low-cost
`wireless mobile communication systems, such as the Blue-
`
` http://www.bluetooth.com, http://www.bluetooth.net
`
`tooth, have adopted centralized TDD scheduling (i.e., at
`the Master) as the MAC protocol for scheduling access to
`the wireless medium.
`A Bluetooth pico-cell has a range of the order of 10
`meters. However, even in that area there can be multi-
`ple Bluetooth (BT) devices. In the current BT standard,
`a maximum of seven active devices (referred to as Slaves
`in Bluetooth) can be supported in a pico-cell. Increasing
`the capacity of BT pico-cells is therefore an area worth
`investigating. In this paper, we have proposed new poli-
`cies that efficiently increase the capacity of a pico-cell by
`swapping active and inactive (parked) Slaves. The algo-
`rithms show significant performance gains as compared to
`the naive policies.
`In Section II, we
`The paper is organized as follows.
`describe in brief the MAC in Bluetooth and the types of
`links supported in the standard. We discuss the capacity
`restrictions in Bluetooth in Section III. The four opera-
`tional modes of Bluetooth devices are described in detail
`in Section IV with emphasis on the park mode. The vari-
`ous unparking methods in Bluetooth are proposed and de-
`scribed in Section V. The simulation assumptions and re-
`sults are presented in Section VI. Finally, in Section VII,
`we present the conclusion.
`
`II. MEDIA ACCESS CONTROL IN BLUETOOTH
`Bluetooth uses a TDD slot structure for resolving con-
`tention over the wireless links. There is a strict alternation
`of slots between the Master and the Slaves. The Master can
`only send packets to a Slave in even slots while the slave
`can send packets to the Master in an odd slot [1]. This
`implies that the scheduling occurs in pairs of slots (i.e.,
`the Master-Slave pair). Further, the task of scheduling is
`vested with the Master. Note that from the above descrip-
`tion, it is not difficult to infer that there could be a wastage
`of slots in the TDD scheme, since if only one of the Mas-
`ter or the Slave has data to send, a slot gets wasted. Blue-
`tooth supports both voice and data traffic [1]. Two types
`of links are supported between any two members of the
`
`Zepp Labs, Inc.
`ZEPP 1046
`Page 1
`
`

`
`slots for packets. If an active slave is not addressed,
`it may sleep until the next new master transmission.
`From the type indication in the packet, the number
`of slots the master has reserved for its transmission
`can be derived; during this time, the non-addressed
`slaves do not have to listen on the master-to-slave
`slots. A periodic master transmission is required to
`keep the slaves synchronized to the channel. Since
`the slaves only need the channel access code to syn-
`chronize with, any packet type can be used for this
`purpose.
`2. Sniff: In the sniff mode, the duty cycle of the slave’s
`listen activity can be reduced. If a slave participates
`on an ACL link, it has to listen in every ACL slot
`to the master traffic. With the sniff mode, the time
`slots where the master can start transmission to a spe-
`cific slave is reduced; that is, the master can only
`start transmission in specified time slots. These so-
`called sniff slots are spaced regularly with an inter-
`val of Tsni. The slave has to listen at Dsni slot
`every sniff period, Tsni for a Nsniattempt number
`of times. If the slave receives a packet in one of the
`Nsniattempt RX slots, it should continue listening as
`long as it receives packets to its own AM ADDR.
`Once it stops receiving packets, it should continue
`listening for Nsnitimeout RX slots or remaining of
`the Nsniattempt number of RX slots, whichever is
`greater.
`3. Hold: During the CONNECTION state, the ACL
`link to a slave can be put in a hold mode. This means
`that the slave temporarily does not support ACL pack-
`ets on the channel any more (note however that possi-
`ble SCO links will still be supported). With the hold
`mode, capacity can be made free to do other things
`like scanning, paging, inquiring, or attending another
`piconet. The unit in hold mode can also enter a low-
`power sleep mode. During the hold mode, the slave
`unit keeps its active member address (AM ADDR).
`4. Park: When a slave does not need to participate
`on the piconet channel, but still wants to remain
`synchronized to the channel, it can enter the park
`mode which is a low-power mode with very little
`activity in the slave.
`In the park mode, the slave
`gives up its active member address AM ADDR. In-
`stead, it receives two new addresses to be used in
`the park mode: PM ADDR (8-bit Parked Member
`Address) and AR ADDR (8-bit Access Request Ad-
`dress). The PM ADDR distinguishes a parked slave
`from the other parked slaves. This address is used
`in the master-initiated unpark procedure.
`In ad-
`dition to the PM ADDR, a parked slave can also
`be unparked by its 48-bit BD ADDR. The all-zero
`PM ADDR is a reserved address:
`if a parked unit
`
`piconet (i.e., a cell in Bluetooth) forming a Master-Slave
`pair. These are the (i) Synchronous Connection Oriented
`(SCO) links for voice, and the (ii) Asynchronous Connec-
`tionless (ACL) links for data. Voice traffic occupies fixed
`slots that are assigned a priori by the Master. When there
`is one SCO (i.e., voice) link, we can have four TDD slots
`available for the data traffic between every two voice slots
`[1]. Figure 1 illustrates the Bluetooth slot structure and
`shows the TDD slots that are being shared by the SCO and
`ACL links. In Bluetooth only three data packet sizes are
`allowed : one slot, three slot and five slot length. An im-
`portant constraint is that a data packet transmission from a
`Master or Slave cannot span across different voice slots.
`
`III. CAPACITY RESTRICTIONS IN BLUETOOTH
`A Bluetooth device has a 3-bit Active Member address
`(referred to as the AM ADDR); zero address is used for
`broadcast packets, hence only seven active Slaves are pos-
`sible in a pico-cell. In Bluetooth, a pico-cell can therefore
`have a maximum of seven active slaves that are capable of
`transmitting and receiving data.
`In many scenarios, an increased pico-cell capacity
`would we very useful. Often there may be just one BT
`device which can act as an Access Point (connected to the
`wired network). Such a device would most appropriately
`act as the Master of all other devices in the vicinity. Form-
`ing different pico-cells would need inter pico-cell commu-
`nication that would lead to communication overheads as
`well as complex network architecture. Considerable power
`savings can be achieved by reducing the number of pico-
`cells (and hence the number of Masters).
`
`IV. DIFFERENT SLAVE MODES IN BLUETOOTH
`A Bluetooth (BT) Slave can be in one of the four oper-
`ational modes: Active, Sniff, Hold and Park. A brief de-
`scription of each of the above modes is given in this sec-
`tion.
`1. Active: In the active mode, the Bluetooth unit ac-
`tively participates on the channel. The master sched-
`ules the transmission based on traffic demands to and
`from the different slaves. In addition, it supports reg-
`ular transmissions to keep slaves synchronized to the
`channel. Active slaves listen in the master-to-slave
`
`MASTER
`
`SLAVE 1
`
`ACL
`
`SLAVE 2
`
`SLAVE 3
`
`ACL
`
`SCO
`
`
`
`
`
`
`
`ACL
`
`ACL
`
`SCO
`
`
`
`
`
`
`
`SCO
`
`
`
`ACL
`
`SCO
`
`
`
`SCO
`
`
`
`
`
`
`
`SCO
`
`
`
`ACL
`
`SCO
`
`
`
`SCO
`
`
`
`ACL
`
`ACL
`
`Fig. 1. Variable size data (ACL) in presence of reserved voice channels (SCO)
`
`Zepp Labs, Inc.
`ZEPP 1046
`Page 2
`
`

`
`transmission present. If there is no information to be sent,
`NULL packets can be transmitted by the master. If there
`is indeed broadcast information to be sent to the parked
`slaves, the first packet of the broadcast message shall be re-
`peated in every beacon slot of the beacon train. However,
`synchronous traffic like on the SCO link, may interrupt the
`beacon transmission.
`In addition to the beacon slots, an access window is de-
`fined where the parked slaves can send requests to be un-
`parked. To increase reliability, the access window can be
`repeated Maccess times (Maccess ). The access window
`starts a fixed delay Daccess after the beacon instant. The
`width of the access window is Taccess.
`The access window may support different slave access
`techniques, like polling, random access, or other forms of
`access. At this stage, only the polling technique has been
`defined. The same TDD structure is used as on the piconet
`channel, i.e. master-to-slave transmission is alternated by
`slave-to-master transmission. The slave-to-master slot is
`divided into two half slots of 312.5 s each. The half slot
`a parked slave is allowed to respond in corresponds to its
`access request address (AR ADDR). For counting the half
`slots to determine the access request slot, the start of the
`access window is used. The slave is only allowed to send
`an access request in the proper slave-to-master half slot
`if in the preceding master-to-slave slot a broadcast packet
`has been received. In this way, the master polls the parked
`slaves.
`However, the slots of the access window can also be
`used for traffic on the piconet if required. For example, if
`an SCO connection has to be supported, the slots reserved
`for the SCO link may carry SCO information instead of
`being used for access requests, i.e., if the master-to-slave
`slot in the access window contains a packet different from
`a broadcast packet, the following slave-to-master slot can-
`not be used for slave access requests.
`
`ACCESS WINDOW
`
`Slave 4
`Parked
`
`Slave 3
`Parked
`
`Slave 2
`Parked
`
`Slave 1
`Parked
`
`Broadcast
`Packet
`
`Broadcast
`Packet
`
`Beacon Train
`
`2
`
`3
`
`Nb
`
`1
`
`
`
`
`Daccess
`
`Master
`Transmission
`
`Master
`Transmission
`
`Beacon Instant
`
`Taccess
`
`Fig. 2. Beacon Train and Access Window in Bluetooth
`
`V. UNPARKING METHODS IN BLUETOOTH
`Slaves can be unparked (i.e., come out of Park mode)
`in two ways: Master-activated unparking and Slave-
`activated unparking. In Master-activated unparking, Mas-
`ter broadcasts unparking commands in the beacon slots.
`Multiple Slaves can be unparked by one broadcast packet.
`
`has the all-zero PM ADDR it can only be unparked
`by the BD ADDR. In that case, the PM ADDR has
`no meaning. The AR ADDR is used by the slave in
`the slave-initiated unpark procedure. All messages
`sent to the parked slaves have to be carried by broad-
`cast packets (the all-zero AM ADDR) because of the
`missing AM ADDR. The parked slave wakes up at
`regular intervals to listen to the channel in order to re-
`synchronize and to check for broadcast messages. To
`support the synchronization and channel access of the
`parked slaves, the master supports a beacon channel
`described in the next section. The beacon structure
`is communicated to the slave when it is being parked.
`When the beacon structure changes, the parked slaves
`are updated through broadcast messages.
`In addi-
`tion for using it for low power consumption, the park
`mode is used to connect more than seven slaves to a
`single master. At any one time, only seven slaves can
`be active. However, by swapping active and parked
`slaves out respectively in the piconet, the number of
`slaves virtually connected can be much larger (255 if
`the PM ADDR is used, and even a larger number if
`the BD ADDR is used). There is no limitation to the
`number of slaves that can be parked.
`To support parked slaves, the master establishes a bea-
`con channel when one or more slaves are parked. The
`beacon channel consists of one beacon slot or a train of
`equidistant beacon slots which is transmitted periodically
`with a constant time interval. The beacon channel is illus-
`trated in Figure 2. A train of NB (NB ) beacon slots is
`defined with an interval of TB slots.
`The beacon slots in the train are separated by DB. The
`start of the first beacon slot is referred to as the beacon in-
`stant and serves as the beacon timing reference. The bea-
`con parameters NB and TB are chosen such that there are
`sufficient beacon slots for a parked slave to synchronize to
`during a certain time window in an error-prone environ-
`ment.
`The beacon channel serves four purposes:
`1. Transmission of master-to-slave packets which the
`parked slaves can use for re-synchronization
`2. Carrying messages to the parked slaves to change the
`beacon parameters
`3. Carrying general broadcast messages to the parked
`slaves
`4. Unparking of one or more parked slaves
`Since a slave can synchronize to any packet which is
`preceded by the proper channel access code, the packets
`carried on the beacon slots do not have to contain spe-
`cific broadcast packets for parked slaves to be able to syn-
`chronize; any packet can be used. The only requirement
`placed on the beacon slots is that there is master-to-slave
`
`Zepp Labs, Inc.
`ZEPP 1046
`Page 3
`
`

`
`In Slave-activated unparking, Slaves send unparking re-
`quest to the Master through the access window. Master
`sends an unpark command to the parked Slaves through
`a broadcast packet. After the unpark command, two slots
`are used for a Poll packet exchange between the Master
`and the unparked Slave (overhead of unparking). If we use
`only the Master-activated unparking, no data can be sent in
`the beacon slots (broadcast packets are present). However,
`no access window is needed. If only Slave-activated un-
`parking is used, no data can be sent in the access window.
`However, data can be sent in the beacon slots.
`
`A. Constant Interval Policy
`To begin with, we propose a simple policy, the Constant
`Interval Policy (CIP) that uses the Master-activated un-
`parking. We maintain a list of time-stamped Slaves. When
`a Slave is parked or unparked, it is time-stamped. A parked
`Slave with the oldest time-stamp is periodically unparked
`and an active Slave with oldest timestamp is parked.
`In CIP, each Slave remains unparked for the same time
`interval. However, some Slaves may have less data to send
`and can be parked for longer times. This will reduce slot
`wastage. Slaves that have more data to send can be parked
`for a lesser time. This may reduce packet drops and delays
`in the system. Motivated by this, we propose Unparked
`Queue based Policy (UQP) and Parked-Unparked Queue
`based Policy (PUQP).
`
`B. UQP and PUQP
`In these policies we use the queue size information at
`the Master-Slave buffers. We reduce the park time (and in-
`crease the unpark time) for Slaves that have high backlog
`in Master and Slave queues. Similarly we increase the park
`time for Slaves having a small backlog at the Master and
`Slave queues. Each Slave (parked or unparked) is given a
`priority. The priority depends on the sum of queue back-
`logs at the Master and Slave queues (Qbacklog) and time
`Tdelay, defined as the time elapsed since the Slave has been
`in a state (Parked or Unparked). To avoid random fluc-
`tuations, Qbacklog is averaged. For an unparked connec-
`tion, priority P (cid:0)
` Qbacklog
`Tmax ,
`Qmax  (cid:2)  (cid:0) 
` (cid:0)
`Tdelay
`(  ). Here Qmax is the sum of maximum queue size
`at Master and Slave and Tmax is the maximum time a
`Slave is allowed to stay in a state (parked or unparked).
`An unparked Slave with the least priority is parked pe-
`riodically. Hence a Slave can get parked if it has small
`backlog at the queue or has been unparked for time com-
`parable to Tmax. Similarly for a parked connection, pri-
`
`Qmax  (cid:2)  (cid:0) 
` TdelayTmax , (  ). A
`ority P (cid:0)
` Qbacklog
`parked Slave with the highest priority is unparked period-
`ically. Thus a parked Slave will get unparked if it has a
`high backlog or has remained parked for a long time. The
`
`parameter determines the weights given to Qbacklog and
`Tdelay, in determining the priority for a Slave.
`
`B.1 Unparked Queue based policy (UQP)
`Unparked Queue based policy (UQP) uses Master-
`activated unparking. As mentioned above, the queue size
`information is used to prioritize different Slaves.
`Infor-
`mation about the Master queues is already available at the
`Master. Queue size information about the Slaves can be
`piggy-backed along with data packets from the Slave to
`Master. In active (unparked) Slaves, this is easily possi-
`ble as every Master to Slave transmission is followed by a
`Slave to Master transmission. However we cannot obtain
`the queue sizes of the parked slaves in this manner. When
`a Slave is parked, Master records queue size information
`of that Slave. This is used in computing Qbacklog through-
`out the period when the Slave remains parked. Since in
`our policies we have used average queue size information,
`we can use it as a good approximation to the actual value.
`
`B.2 Parked-Unparked Queue based policy (PUQP)
`The Parked-Unparked Queue based policy (PUQP) uses
`Slave-activated unparking. This policy improves upon
`(UQP) by utilizing the current queue size information of
`the Parked Slaves (rather than using old information). We
`use the access window to communicate queue size infor-
`mation from the parked slaves to the Master. In Slave acti-
`vated unparking, the access window is used for all Slaves
`to send unparking requests to the Master. Queue size in-
`formation is passed along with the packets to the Master.
`The Master then computes priorities (as mentioned above)
`and selects the connection to unpark. The selected con-
`nection is sent an unpark command in any of the following
`broadcast slot.
`
`VI. SIMULATION RESULTS
`We simulate a piconet consisting of five active Slaves
`and a Master. For each Slave, there is a corresponding
`queue at the Master. The TDD slot length in Bluetooth is
`equal to 625  secs [1]. The data arrival process at the
`Master and Slave queues is assumed to be one of the fol-
`lowing (i) Poisson (MP) or (ii) a two-state Markov Mod-
`ulated Poisson Process (MMPP) [5]. For the MMPP pro-
`cess, the transition probability from one state to another is
`equal to 0.01 and the probability of remaining in a state is
`0.99. The first and fourth M-S pair have MP arrival pro-
`cess at both Master and Slave queue with an arrival rate of
`0.1. The second and third M-S pairs also have MP arrival
`processes. In second pair Master has a arrival rate 0.19 and
`Slave 0.01 while it is the opposite in third pair. The fifth
`pair has MMPP arrivals with rate varying between 0.19
`and 0.01. The arrival rate is in units of packets per TDD
`slot. The buffer size at the Slaves and the Master queues
`
`Zepp Labs, Inc.
`ZEPP 1046
`Page 4
`
`

`
`CIP
`UQP
`PUQP
`
`20
`
`40
`
`60
`
`120
`100
`80
`Period of Beacon Instant in slots (Tb)
`
`140
`
`160
`
`180
`
`200
`
`Fig. 4. Average Delay vs. TB for CIP, UQP, PUQP
`
`CIP
`UQP
`PUQP
`
`1600
`
`1400
`
`1200
`
`1000
`
`800
`
`600
`
`400
`
`200
`
`Average Delay (in slots)
`
`0
`
`0
`
`260
`
`240
`
`220
`
`200
`
`180
`
`160
`
`140
`
`Power Packet Ratio (PPR)
`
`120
`
`0
`
`20
`
`40
`
`140
`120
`100
`80
`60
`Period of Beacon Instant in slots (Tb)
`
`160
`
`180
`
`200
`
`Fig. 5. Power Consumed (in slot units) vs. TB for CIP, UQP, PUQP
`
`significant performance gains as compared to the naive
`policies. We observe improvements in throughput, delays
`as well as power consumption in the proposed policies.
`This can have a significant impact on the performance of
`Bluetooth systems.
`
`REFERENCES
`[1] Bluetooth special interest group. http://www.bluetooth.com/
`[2]
`http://www.bluetooth.net/
`S. Keshav, An engineering approach to computer networking: ATM net-
`[3]
`works, the Internet, and the Telephone network, Addison-Wesley, 1999.
`[4] R. W. Wolff, Stochastic modelling and the theory of queues, Prentice Hall
`Inc, Englewood Cliffs, NJ, 1989.
`
`is 20 packets. Discrete Event Simulation was run for 5000
`TDD slots and the statistics were collected after the first
`100 slots to remove any initialization bias in the simula-
`tions, if any.
`We study the performance of the three policies for dif-
`ferent values of TB (interval between two beacon instants).
`For UQP and PUQP we take (cid:0) (cid:3). In Figure 3 we ob-
`serve the system throughput for the three policies. UQP
`performs much better than CIP in terms of throughput
`(10% increase). For higher values of TB, the PUQP per-
`forms the best. It gives a throughput of 75% as compared
`to UQP which has a throughput of 67% and CIP which
`has a throughput of 54%. In Figure 4 we observe UQP and
`PUQP lead to lower average delays. The performance of
`CIP and UQP declines for higher values of TB. PUQP per-
`forms better for higher values of TB. In PUQP, during the
`access window no data can be transferred. Length of the
`access window is equal to number of parked slaves. Thus
`wastage becomes small for large values of TB. However
`for UQP and CIP, the slot wastage is due to the beacon
`train. Since the length of the beacon train is proportional
`to TB, the wastage remains the same.
`To measure the power consumption we introduce a new
`parameter, Power Packet Ratio (PPR). PPR is defined
`as the average power consumed in transmitting thousand
`packets of slot length one. This parameter allows us to re-
`alistically compare the performance of different protocols.
`In Figure 5 we observe the power consumption of different
`policies. PUQP and UQP perform much better than CIP in
`terms of power consumption. The UQP policy performs
`the best. The reason is that it avoids unnecessary listening
`of the radio channel by slaves (absence of access window).
`The beacon train is effectively used to transmit data.
`
`CIP
`UQP
`PUQP
`
`20
`
`40
`
`60
`
`120
`100
`80
`Period of Beacon Instant in slots (Tb)
`
`140
`
`160
`
`180
`
`200
`
`Fig. 3. System Throughput vs. TB for CIP, UQP, PUQP
`
`80
`
`70
`
`60
`
`50
`
`40
`
`30
`
`20
`
`10
`
`0
`
`0
`
`System Throughput (% of total slots)
`
`VII. CONCLUSION
`In this paper, we have proposed new policies that ef-
`ficiently increase the capacity of a pico-cell by swapping
`active and inactive (parked) Slaves. The algorithms show
`
`Zepp Labs, Inc.
`ZEPP 1046
`Page 5