[attachment=3706]

DEMAND “ BASED BLUTOOTH SCHEDULING

---

Presented By:
D.NAGA HARSHAL K.KRISHNA PRASHANTH

CHAITANYA BHARATHI INSTITUTE OF TECHNOLOGY,GANDIPET,HYDERABAD-75.

---

Abstract
Bluetooth is a short-range wireless communication technology for ad-hoc communication between devices, each of which has a range of around 10m. The master typically employs strict round-robin mechanism to poll the slaves in a piconet consisting of a master and up to seven slaves. In this paper we propose a flexible polling mechanism for the master that begins with common polling periods for all slaves and subsequently increases the polling period for slaves with less traffic load. We compare our flexible polling mechanism with strict round-robin polling mechanism and conclude that flexible polling will improve the throughput of the piconet.
Introduction
Bluetooth is a wireless communication technology that permits communication between bluetooth enabled devices. Bluetooth operates in the ISM band. This band can be very noisy, so bluetooth employs a frequency hopping scheme for modulation. The range of a bluetooth device is around 10m. Bluetooth devices within range can set up an ad-hoc network called a piconet with one master that controls the piconet and a maximum of 7 slaves . The master and a slave communicate using Time Division Duplex (TDD) slots. Typically, though not necessarily, the master talks to the slave in a time-slot (625 s) and the slave replies to the master in the very next time-slot, the two consecutive slots where the master and one particular slave communicate with each other is called a bluetooth frame. We use the term metaframe to denote a number of consecutive bluetooth frames equal to that of the number of slaves in the piconet.
Bluetooth supports two types of channels: asynchronous and synchronous. For asynchronous communication the master polls a slave and the slave responds in the next slot. This communication is asynchronous in nature and is initiated by the master. For synchronous communication the master and slave talk to each other at regular intervals of time. The interval of time is set up before the synchronous communication starts. This is mainly used for voice traffic.
The total capacity for communication for a bluetooth piconet is about 1Mbps. Thus, it is highly undesirable to allocate two slots to (i.e., to poll) a master-slave connection only to have nothing to transmit in one or both slots, i.e., one or both slots are wasted. Bluetooth standards have two mechanisms in place to improve efficiency of usage of the available bandwidth:
a) An inactive slave can enter a dormant state for reduced power consumption. Bluetooth supports three such states: sniff, hold and park . We consider only the park state only for simplicity. Note the bluetooth device can communicate only in the active state.
b) The use of multi-slot packet formats (1:1), (1:3), (3:1), (1:5), (5:1). The notation (m) means that the master-to-slave packet is m time-slots long and the packet from slave-to-master is s time-slots long. Multislot packet formats improve throughput in situations where the master-slave connection has information flowing primarily in one direction, i.e., an asymmetric TDD connection. The use of multislot packets is mitigated by the condition that they cannot span slots reserved for synchronous (isochronous voice) traffic .
This paper proposes a flexible piconet scheduling mechanism which is not incompatible with a) and b) and involves variable-rate polling; the master-slave connections with little (but not dormant) activity are polled less frequently. The goal is to maximize the throughput of data traffic and to reduce the power consumption of the piconet. The proposed scheduling mechanism also realizes a graceful transition from the active to the park state and clearly stipulates when slaves are to be parked.
A bluetooth device can participate in either one or two piconets. When it participates in two piconets, it may act as a bridge between them. A system of interconnected piconets is called a scatternets. Inter-piconet communication within a scatternet is accomplished using the bridge nodes . We will describe certain restrictions on piconet scheduling in the presence of bridge nodes and other shared slaves.
Scheduling for Bluetooth Scatternets

A simple example of a bluetooth scatternet is depicted in Figure. Consider two piconets with a common node. One piconet has a total of three slaves and the other has a total of 7 (the maximum) slaves. Each slave has a single bluetooth transceiver so that it can only transmit once per bluetooth slot. We assume that adjacent piconets are synchronized so that transmission epochs for common slaves are aligned. Since 3 and 7 are co-prime, under strict round-robin scheduling both masters may occasionally poll the shared slave at the same time.

We now describe a way to prevent simultaneous polling of shared slaves. Recall that a piconet with 7 slaves has a metaframe of 2x7=14 time-slots. We propose that each piconet has a metaframe of 14 slots (7 consecutive polling epochs (bluetooth frames)) irrespective of the number of slaves. So, if a piconet has 3 slaves, each slave could be polled at least twice in a metaframe because, of course, 2x3<7<3x3. Consider the single (7-2x3) pad slot in this situation. Pad slots are never assigned to shared slaves. Pad slots can be assigned to dedicated slaves in a round-robin fashion. Thus, we create a two-layer hierarchical round-robin polling mechanism where the first layer has 7 polling opportunities and only dedicated slaves are polled in the second layer. See Figure 2 for an example in which slave 1 is assumed to be shared and slaves 0 and 2 are dedicated. In this figure, each square represents a two-slot bluetooth frame (a polling epoch); the slave labeled 1 is shared and, consequently, does not participate in the layer-two slots. In this example, the HRR mechanism works so that slaves 0 and 2 are served in the pad slot of alternate metaframes, i.e., they take turns using the pad slot.
Figure 1 - A bluetooth Scatternet.

In Figure 3, we consider a piconet with four slaves: slave 3 is a synchronous (isochronous voice) slave, slave 1 is an asynchronous (data) slave shared with another master, and slaves 0 and 2 are dedicated asynchronous slaves. Note that neither the synchronous slave nor the shared slave participate in the pad slots and that the synchronous slave is polled only once per metaframe.


Figure 2 - An example of a two-layer HRR structure


Figure 3 “ An alternative two-level HRR scheduler

When a slave that already belongs to a piconet joins a new piconet, it communicates to the new master the slots at which it is polled by its other existing master. Therefore, the new master can poll the slave (i.e., assign it to slots in its metaframe) so as to avoid the situation where the slave is polled simultaneously by two masters.
Methods of setting up (at once) a conflict-free group polling schedule for a bluetooth scatternet of M piconets with a total of L shared slaves have been explored in the context of bandwidth arbitration for switch fabrics. For example, let L=M and consider the MxM matrix whose entry in the ith column jth row is the number of layer-one slots of the ith piconet that are dedicated to the jth shared slave of the scatternet. So, this is a doubly sub-stochastic matrix all of whose entries are multiples of 1/7. Note that, to determine this matrix, whether to poll a shared slave once or twice per metaframe (a choice illustrated in Figure 3) must be previously determined. Given the doubly stochastic matrix, the Slepian-Duguid or Birkoff-von Neumann-Konig approaches can be used to find a conflict-free scatternet schedule, i.e., to find a Mx7 matrix whose ith row is the layer-one frame of the ith piconet and the index of any shared slave appears at most once in any column (this latter condition is implies that no (shared) slave is simultaneously polled by two or more masters). For the case where L>M (resp., L<M), one can pad the MxL matrix with L-M all-zero row vectors (resp., M-L column vectors) to create an LxL (resp., MxM) doubly sub-stochastic matrix and proceed as above. Once the schedule for the shared slaves has been determined, the slot assignments for the dedicated slaves are added to the Mx7 matrix as described above. The following table is a complete, conflict-free schedule for the scatternet of Figure 1 wherein M=5, L=4 and the circled labels are those of the shared slaves. For that example, device no. 8 is a slave of device no. 6 and both are masters. Thus, device no. 8 cannot poll its slaves during the bluetooth frame in which it is polled by device no. 6.


A Flexible Piconet Scheduling Mechanism
In a bluetooth piconet, each slave has a FIFO queue for transmission to the master and the master has a FIFO queues for transmission to each of the slaves. Recall that, a TDD connection is associated with each slave; hereafter, the term connection will connote the two associated queues depicted in Figure 4. Note that, within a single connection, the two arrival processes to the queues will be dependent.


Figure 4 - The nth TDD connection of a bluetooth piconet

Figure 5 - Example of flexible polling mechanism

In the following, we propose a new scheme with a flexible polling rate per slave. Our mechanism will be described using the example in Figure 5. The following table depicts the polling epochs of this example; those of the asynchronous dedicated slaves (ADSs), numbers 0 and 2, are checked with an x in the third row. In this table, discrete time is measured in multiples bluetooth frames (2 x 625 s). The focus of the rest of this paper is on the polling decisions for the ADS slots; those of the standard policy are indicated in middle (second) row of the following table for the example under consideration. Our flexible polling policy will give alternative polling decisions for the ADS slots. The flexible polling mechanism does not make any polling decision for the shared or synchronous slaves.


In general, suppose that there are D asynchronous dedicated slaves. At any given time, the dth ADS is assigned a time-stamp td and a polling period nd by the master. Our flexible polling policy works as follows. For an ADS slot, the master polls the ADS slave with the smallest (current) time-stamp; ties are broken arbitrarily. When an ADS is polled, its time-stamp is increased by its polling period. More precisely, if the dth ADS is polled, the result is that td td + nd. The following statement is easy to prove :

Statement: The ADS polling decisions are periodic with period mp equal to the least common multiple of the current polling periods n1,n2,...,nD-1. Moreover, in every period of mp ADS slots, the dth ADS is polled mp/np times, for all d {0,1,...,D-1}.

Note that if all the polling periods are identical, the result is standard round-robin polling. Under flexible polling, the polling periods are periodically adjusted according to the following rule. Initially, all polling periods of the asynchronous dedicated slaves are set to D. At any given time, the polling period of an ADS belongs to the set of integers:
N0 D N1 N2¦.... NK-1 < NK
We assume that the increase in the polling period, hereafter called the step size, is constant and denoted it by m = N k+1 - N k, i.e.,
Nk = D + km.
Suppose that the dth ADS is polled at a point where nd = Nk for some k {1,...,K}. One or both queues associated with this ADS connection (Figure 4) could be prompted to transmit during the two-slot frame. There are two cases:
1. If, as a result of this polling decision, there was nothing to transmit in the frame (no packet was transmitted by the ADS connection), the master would increase the polling period of this ADS; i.e., set nd = Nk+1 if k < K or, if k=K, the master would consider parking the ADS.
2. If a packet is transmitted by the ADS connection, the polling period of the ADS is reset to D.
The quantities K and NK are chosen so that if the polling period is NK, the slave is inactive enough to be parked. Parking the slave not only saves valuable bandwidth but also helps in reducing the power consumption of the bluetooth device. More details on parking can be found in [15].
Performance Evaluation of a Flexible Polling Strategy
One simply stated objective of our flexible polling policy is to maximize the throughput of the bluetooth piconet over the ADS frames. A second issue is the access latency (or response time) of the piconet. By access latency we mean the delay experienced by the first packet of an arriving data burst to a master-slave connection.
The simulation scenarios we considered assume all (ADS) slaves were active (slaves in a parked state neither transmit nor receive data and, hence, are not affected by the choice of polling strategy). Under the strict round-robin polling mechanism, the master polls each slave in turn and the polling period for each slave is simply the number of slaves in the piconet. Under a flexible polling policy, a range of access latencies for a data burst is possible depending on the current polling period of the master-slave connection. If a data burst arrives just after a polling epoch of a slave and the current polling period of that slave is large, the access latency of the burst will be large. The polling step size (m = N k+1 - N k) can be adapted to significant changes in the traffic conditions in order to reduce access latency. For example, if overflow of the transmit buffers is too frequent, the step size could be reduced accordingly.
A simulation study was performed for the example given in Figure 5. Though not a comprehensive simulation of an actual piconet, our study was detailed enough the show the affect of our flexible polling algorithm on the throughput and access latency. Various traffic profiles were selected for the two ADS slaves from the ones shown below in Figure 6. The resolution in Figure 6 is at the level of a bluetooth frame (polling epoch), i.e., each arrival represents an entire bluetooth frame (two time-slots). We chose different combinations of two traffic profiles from those depicted. The access latency was calculated as the delay experienced by the first packet of a traffic burst, i.e., the shaded packet(s) in Figure 6.

Figure 6 - The different traffic profiles of example slaves

Note that Slaves 2 and 3 have high traffic load while Slaves 1 and 4 have low traffic load. The simulation results can be classified in two basic groups.
Results when the slaves had similar traffic load:
Here we chose the combination of Slave 2 and Slave 3 or Slave 1 and Slave 4. Clearly, in these cases, a flexible polling policy will make scheduling decisions similar to those of round-robin polling and this is reflected in the simulation results:
¢ The results for round-robin polling for Slave 2 and Slave 3:
o Percentage of wasted frames: 0
o The throughput of the piconet: 100%
¢ The results for flexible polling for Slave 2 and Slave 3:
o Percentage of wasted slots: 0
o The throughput of the piconet: 100%
¢ The results for round-robin polling for Slave 1 and Slave 4:
o Percentage of wasted slots: 39%
o The throughput of the piconet: 61%
o The average access latency: 3
¢ The results for the flexible polling for Slave 1 and Slave 4:
o Percentage of wasted Slots: 39%
o The throughput of the piconet: 61%
o The average access latency: 3
Note that the low throughput of Slave 1 and Slave 4 is due to the fact that their queues are under-loaded; thus, there are many unused slots because there is simply nothing to send.
Results when the Slaves had different traffic load:
In this scenario, we choose the two slaves such that they had different traffic load. We shall display the result for Slaves 2 and 4, a representative combination. Slave 2 has significantly higher traffic load compared to Slave 4. We noticed a clear improvement in the throughput for these selected traffic profiles for flexible polling. The advantage of flexible polling was clearly visible here. Flexible polling allocated more slots to the slave with greater traffic load, i.e., to Slave 2.
¢ The results for the round-robin polling for Slave 2 and Slave 4
o Percentage of wasted slots: 20%
o The throughput of the piconet: 80.0%
o Average access latency: 3
¢ The results for the flexible polling for Slave 2 and Slave 4
o Percentage of wasted slots: 8.75%
o The throughput of the piconet: 91.25%
o Average access latency: 4
We varied the step size (m = Nk+1 “ Nk) for different simulation cycles to find its affect on the access latency. The results for different values of step size m are graphically shown in Figure 7 below. In this graph, the percentage of wasted slots, throughput and burst access latency are plotted. Clearly, throughput of the piconet is an increasing function of m. However, burst access latency is also an increasing function of m.

Figure 7 - Changes due to variation of polling step size
Conclusion
In this paper, a strategy was described for scheduling of shared slaves in a bluetooth scatternet. Also, we compared strict round-robin polling to a proposed flexible demand-based polling mechanism for a bluetooth piconet. We are assuming here that the master can do a small amount of integer computation. The flexible polling mechanism resulted in greater throughput when the traffic load was unevenly distributed among the (dedicated) slaves. Also, there would be a corresponding improvement in overall power consumption as the slaves that have less traffic load were polled less frequently. Finally, the flexible polling mechanism gives a well-defined rule to determine when to park a slave. The drawback of flexible polling is a potential increase in the access latency of an arriving burst of data to be transmitted. This tradeoff can be made tolerable by adapting the polling period step-size to the traffic.
References:
[1] M. Albrecht, M. Frank, P. Martini, M. Schetelig, A. Vilavaara, and A. Wenzel.
IP services over Bluetooth: leading the way to a new mobility. Proc. Conf. on Local Computer Networks (LCN '99), pages 2 --11, 1999.

[2] T.E. Anderson, S.S. Owicki, J.B. Saxe, and C.P. Thacker. High speed switch scheduling for local area networks. ACM Trans. Comp. Sys., pages 319--352, Nov. 1993.

[3] J.C.R. Bennett and H.~Zhang. Hierarchical packet fair queueing algorithms. IEEE/ACM Trans. Networking, Vol. 5, No. 5:pages 675--689, Oct. 1997.