An analytical model of inter-channel interference in Bluetooth-based systems

An Analytical Model Of Inter-Channel Interference In Bluetooth-Based Systems J.L. Sevillano, F. Diaz del Rio, G. Jimenez, D. Cascado, A. Civit-Balcells ETS Ingenieria Informatica. Avda. Reina Mercedes s/n. 41012 Sevilla. SPAIN e-mail: (sevi,fdiaz,gagi,danic,civit)@atc.us.es. Abstract - One of the main advantages of the Bluetooth standard is that it provides a way to support ad-hoc connedivity between a variable number of devices at low cost. However, in situations with many Bluetooth devices that coexist in the same area the problem of channel interference may become of high importance. In this paper, we present an analysis that prorids some expressions for the channel throughput and the delay that packets suffer due to possible collisions with other Bluetooth devices. The model includes the different effects of new and retransmitted packets. Both synchronized and unsynchronized systems are considered. Furthermore, although the effect of propagation losses are not explicitly considered, we show how they could be included in our model. Keywords: Bluetooth, performance analysis, channel interference, throughput, packet delay. 1. INTRODUCTION Bluetooth is a global standard for a low-power, short-range Wireless Personal Area Network (WAN). Its aim is to provide connectivity to a very wide range of devices. Currently, Bluetooth connections are being embedded in notebook computers, digital cameras, Personal Digital Assistants (PDAs), mobile phones, and it is also used in non portable devices with wireless connections such as desktop PCs, printers, etc. A typical Bluetooth system is composed of a small numher of devices that form a wireless network called a piconet. Since connections are established ad-hoc (a piconet can he automatically established when units arrive within range), a variable number of piconets may coexist in the same area. These piconets may be independent or may become a system of linked piconets called a scatternet [I]. In the latter case, a Bluetooth unit is a member of more than one piconet, on a time-division multiplex (TDM) basis (a unit can only transmitheceive in one piconet at a time). These interpiconet nodes [2] may either forward traffic between two overlapping piconets or operate independently in the piconets. Also, more than one bluetooth channel may co-exist in a single device such as Internet Access Points [3]. The idea is to share the available bandwidth among different and independent users and/or devices. With WPANs, a typical scenario consist of a number of people with portable (and moving) devices entering a common area and connecting to fixed networks and maybe to other portable terminals (for instance to share documents in a meeting) [Z]. Therefore, a situation where several people in proximity have open Bluetooth connections is very common: airports, conference halls, office, etc. in these cases, channel interference is not negligible and in this paper we try to model its effect on performance. Bluetooth operates in the ISM (Industrial, Scientific & Medical) band, from 2.402GHz to 2.480GHz. This is a crowded band, and its use is only going to increase [4]. However, we only focus on the interference generated by Bluetooth devices, although there are many possible sources of interference (microwave ovens, 802.1 1 LANs, etc.),. When a piconet is established by a bluetooth unit, it becomes a master so that the other units (slaves) synchronize with it. Any unit may function as a master or as a slave (this role is maintained only for the duration of the piconet), hut although it may participate as slave in multiple piconets it may only be a master in one piconet. The Bluetooth channel is divided into slots of length 625p so that the time slots are alternatively used by the master and the slaves. Although multi-slot packet transmissions are allowed (e.g., DH3 and DH5 packets), in this paper we assume that each packet occupies a single slot. For a given piconet (with a master and up to 7 slaves) communication is Time Division Duplex: transmitter and receiver alternate their transmissions in separate slots. The master of the piconet performs a polling among all the slaves, so that within a piconet collisions do not occur. Therefore, interference may only occur among devices connected to different logical channels (independent piconets or scanernets). In order to reduce this interference, and also to serve other purposes like reducing multipath effects, Bluetooth uses Frequency Hopping. The main hopping sequence, called Connected Mode, used in all usual transmissions, distributes the hops evenly over all carriers. There are 79 different liequency bands at IMHz spacing defined in the Bluetooth specification, although in some countries a reduced set of carriers may be used [I]. In order to include these possible differences in our model, we denote the number of bop carriers as M. The slot 0-7803-7605-6/02/$17.00 02002 IEEE. 384 length of 625w comes from a hop rate of 1600 hops per second (there are no frequency hops within a slot). When several independent (but interfering) Bluetooth devices coexist in thc same area, we can assume that they transmit using randomly chosen frequencies. Note that this mechanism is a form of Code Division Multiple Access (CDMA). Of come, there is a possibility that several devices happen to choose the same hop carrier. In that case, we say that a collision occurs and the packet will he received incorrectly. The sender is notified of this error in the slot directly following the unsuccessful transmission using a fast-ARQ scheme [I]. The packet is retransmitted at the next opportunity (in alternate slots) until the packet is successhlly received. 2. PREVIOUS WORKS Several recent studies have addressed the problem of the analysis of channel interference in Bluetooth systems. El- Hoiydi [5] studies the worst case, that is, he considers 100% traffic. As a result, his model provides upper bounds on the packet error rate (probability of collisions) as well as lower bounds on the throughput. On the other hand, Lim et al. [3] do not limit their study to the worst case, but they provide an approximate throughput vs. offered load analysis. In both references the different cases of synchronized and unsynchronized piconets are considered. Of come, in the Bluetooth specification piconets are not synchronized, hut equations for the synchronous case are much simpler and they may provide acceptable predictions in some cases. Lim et al. also consider multislot packet transmissions. These two references ignore the mitigation effects of propagation losses of radio waves, that is, they assume that the interference ofjust 1 bit is enough to destroy the packets. It is not easy to take into account the effects of propagation of radio waves in a building, including capture effects, position of terminals/obstacles, environment geometry, etc. For instance, Karnik and Kumar [6] present analytical results only for up to 3 piconets, because it is very complicated to obtain even approximate results for a higher number. However, Mazzenga et al. [7] provides a very interesting way to include these effects in the analysis of channel interference, and we will use their approach in our model. The main contribution of the present paper is that it provides expressions for the throughput that include the different effects of new and retransmitted packets. This allows us to obtain expressions for the throughput not only as a function of the offered load, but also as a function of the probability of new packet generation at every node. A very interesting advantage of this approach is that the model is also able to give an estimation of the delay suffered by packets due to collisions. In the following sections, we first present our model for the synchronous case, and then for the more general case of asynchronous piconets. Finally, although the effect of propagation losses are not explicitly considered, we show how they could be included in our model following Mavenga et al. [7]. 3. ANALYSIS Let N be the number of interfering piconets. First, we assume that all the piconets are synchronized among them. We begin with a brief summary of the results obtained by Lim et al. [3]. Let r be the normalized load over every piconet, including both new and retransmitted packets. For a given piconet, which is transmitting in a slot in a particular carrier, the probability of a collision with another piconet is r/M, that is, the probability that a transmission attempt occurs in the other piconet and that the same particular carrier is also chosen. A collision does not occur with probability I-r/M. Therefore, the probability of a successful transmission is . Y.1 P- 1-- s-[ L) that is, the probability that none of the other N-l piconets transmit with the same carrier than our reference piconet. Differently from the model of Lim et al., in this paper we are interested in including the different effects of new and retransmitted packets. Therefore, we define p as the probability of a new transmission attempt in a slot. We assume a homogeneous traffic so that p is a constant for all the piconets. Note the difference betweenp and r. With our definitioqp does not include packet retransmissions due to collisions, while r as ueed in eq. (I) is the probability that a transmission attempt occurs in a slot, both due to new packet generation and retransmissions. Since access is contention-free (the master pelforms a polling with all the slaves), only one of the devices generates new messages in every slot, sop could also be referred to the probability that a single device generates new packets. 385 - N=Z tN40 -A-N=50 -a- N=100 -ir- N=I50 -0- N=Z00 I N=Z +N=IO tN=50 IZN=lOO +N=l50 tN=Z00 04 I I I., , , , I O,I o,z 0,s 0,4 0,5 0,6 0,7 o,a 0,9 I (p) prob. of new packet generation Figure 2. Channel load including new and retransmined packets Then, a known result from multiprocessor systems can he used (see for instance [8]). If we consider the interval between two successful transmissions in a piconet, we can divide it into tbree parts: a number of slots with no transmission attempts, X; a number of wasted slots due to collisions, W; and finally, a single slot with the successful transmission (Fig. I). Note that any device (master or slave) transmit only in alternate slots, one after the other. In order to use the same reasoning of [8], we ignore the slots that do not correspond to the transmitting device. Therefore, the actual load carried over the channel is r=(W+I)/(X+ W+I). The wasted slots due to collisions correspond to a sequence of Bernoulli trials with probability of success Ps. The number of wasted slots is therefore geometrically distributed, so its mean is: 1 - Ps W=~i(l-P,)iP, =- i=J ps Analogously, the slots with no packets are also geometrically distributed, so X=(f-p)(u. Note that we assume that the probability of new packet generation is the same for all the slots. As a result, we get (3) Since Ps depends on r as shown in eq. (I), we can use a simple iteration algorithm beginning with r=p. - o,a a ?0,6 2 0.4 Gi -0,z m r 0 oi I, I,, , , ,-I o,i o,z 0,s 0,4 0,s 0,6 0,7 o,a 0,9 I (p) prob. of new packet generation Figure 3. Throughput characteristics Figure 2 shows the results obtained from this iteration. As expected, the actual channel load is always greater than p. due to the retransmission attempts of previously collided packets. If the number of interfering piconets N is large, the channel load go% very rapidly withp. This result may have important practical consequences since p represents the actual load due to the higher level protocols for every single device. Anyway, this mechanism allows us to obtain the probability of a successful transmission Ps as a function of N (the number of piconets) and p (the probability that a new packet is generated in a slot). Another important parameter is the throughput (the rate of successfully transmitted packets): with r being the channel load r obtained from the iterative process performed over eq. (3). Results are shown in Fig. 3. Note that when the number of interfering piconets is large, the throughput has a maximum at medium loads and then decreases for higher values ofp. The reason is that in the presence of collisions the system is not work conserving, that is, the channel is wasted while there are packets in the system waiting to be transmitted. This is also the case for other protocols like ALOHA [9]. Since we have obtained the probability of a successful transmission as a function of the probability of new transmission attempts, we are now able to estimate the mean delay that a 386 tN=2 tN=50 +N=l00 + N=l50 -0- N=200 25 m a - i; 20 2 15 8 10 E - - C as 0 0,l 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,s 1 (p) prob. of new packet generation Figure 4. Delay eharacterjrties packet suffers due to possible collisions with other Bluetooth devices. From eq. (2), and considering that any device transmit in alternate slots, the mean delay including the successful slot is T = 2( y ) + 1 expressed in slots of length 625p [I] (see Fig. 4). Note that this expression does nof include the delay due to the polling performed by the master of the piconet. It is apparent from fig. 4 and eqs. (I) and (5) that the mean delay is upper bounded for a given number of piconets. Therefore, it may seem that the Bluetooth protocol is well suited for real-time applications. Of course, soft real-time applications like multimedia are one of the more typical uses of Bluetooth (voice, video, etc.). But when the system presents strict temporal requirements, we should always keep in mind that a system with several interfering piconets is probabilistic in nature. Although the polling performed by the master provides determinism within a piconet, there is always the possibility of a collision with other bluetooth devices connected to different logical channels, as well as with other interfering devices (WLANs like IEEE 802.11, microwave ovens, etc). These intuitive conclusions could also be drawn from our model if we take into account not only the mean delay but also the delay variance. For the geometric distribution of the number of wasted slots W, the variance is: Since Psis a decreasing function of r, then the delay variance grows with p much more rapidly than the mean delay when the number of piconets is large. For instance, for N=200 and rl we have W=l1.6 and d=146.6. Note that retransmitted packets have the same opporlunities than new packets, so it may occur that some unlucky packets suffer very large delays. This is not acceptable in real-time control applications, and even in applications like continuous voice or video streams delay variance may be at least as important as average delay. 4. ASYNCHRONOUS PlCONETS So far, we have considered the case of synchronous piconets. However, in the Bluetooth specification the piconets are not synchronized, so a slot in our reference piconet overlaps with two slots in every interfering piconet. As a matter of fact, in the Bluetooth standard a single slot packet is only of duration 366p, while the time-slot length is 625p. This difference is needed for the electronics to stabilize with every frequency hop. The ratio R=366/625=0.5856 must be taken into account because two piconets may interfere in one or two slots depending on the time offset. If we assume that time offsets of the rest of piconets with respect to the reference piconet are uniformly distributed in time, the probability to interfere with two slots of another piconet is 2*R-l=0.1712, and with only one slot 2*(1- R)=0.8288 [5]. It seems that the assumption of synchronized piconets is not so had, although we can easily include this term in our model by changing eq. (1) as follows: Ps = [ 2(1-R) [ 1-- :I +(2R-1) [ 1-- :,’I” (7) The second term is due to the fact that if our slot overlaps with two slots, then a successful transmission occurs if there are no collisions in two consecutive (and independent) slots. We let eq. (7) depend on R in order to have a more general expression. The protocol imposes that the minimum switching time between frequency hops is 200ps so K0.68 [I]. Equation (7) differs fiom that of [5], because this author instead of (1) uses ulat is, it is assumed that the probability to successfully hansmit is the probability that all the other piconets hansmit and they choose a different kquency, therefore excluding the possibility that simply some piconets do not hansmit at all. The reawn is prohably that the author of [5] is actually interested in the worst case, when all piconets have lOO%traffic(r+I),and~s isnotourcase. 387 A simpler expression for (7) could be used if we fake into account N-l that r/M<<I. Ifwe neglect the term (r/@, we obtain )(I-R)'RN-l-" Pn (14) (9) with B bemg the probability that no collision occm, given by (see eq. (7)): which is similar to eq. (1) with the factor 2R reflecting the effect of considering asynchronous piconets. 5. INCLUDING PROPAGATION LOSSES As we discussed in section 2, it would be very interesting to include in OUT model the effect of the propagation characteristics of radio waves. This is a complex issue that goes beyond the aims of this paper. However, we will use a recent result from Mazzenga et al. [7] that allows ns to include these effects. In order to do this, we first present an alternative way to obtain eq. (1). Note that the probability that n out of the interfering piconets produce a collision is Then, the probability that a collision occurs is We now obtain (1) since Ps=I-Pc=q(0). We are now able to use the result in [7], which states that propagation losses and capture effects could he considered if we change eq. (IO) as where fin are coefficients that include these effects. Their computation is difficult because they depend on the geometry and propagation characteristics of the environment, the position of the Bluetooth devices for every interfering piconet, etc. Anyway a more general expression for Ps is therefore B= 2(1-R) 1-- +(2R-1) 1-- . (15) [ ( J ( 4 Using the same approximation than eq. (9), we get Note that again this simple expression coincides with eq. (12) except for using 2Rr instead of r reflecting the effect of considexing qnchronous piconets. ACKNOWLEDGMENTS This work was supported by the Spanish Minishy of Science and Technology under contracts TIC2001-1868-C03-02 and TIC2000-0087-P4-01. REFERENCES [I] J.C. Haartsen, "The Bluetwth Radio System". IEEE Penanal Cammicalions, pp. 28-36. Feb. 2000. [2] P. Johansson, M. heidis, R. Kapoor, M. Gerla, "Bluetwth: AD Enabler foi Penanal Area Networking". IEEE Newark, pp. 28-37. SepVOct. 2001. [3] Y. Lim, J. Kim, S.L. Min, J.S. Ma, "Performance Evaluation of the Bluetooth-based Public Internet Access Point". Pmc. IS" Int Conf Informalion Networking, pp. 643-648. Beppu, Japan. 2001 [4] "Wireless New Technologies". Agilent Technolodes, 2002. [51 A. El-Hoiydi, %terference Between BlUefOOfh Networks-Upper Bound on the Packet Ermr Rate". IEEE Comm. Lellers, vol. 5, no. 6, June 2001. [6] A. Kamik and A. Kumar, "Performance of fhe Bluetooth Physical Layer". IEEE Inl. Conf Personal Wireles$ Comm., pp. 70-74. Hyderabad, India. 2000. [7] F. M-nga, D. Cassiali, P. Loreti, F. Vatalaro "Evaluation of Packet Loss Probability in Bluetooth Networks". Proc. IEEE far CO& Comm., pp. 313-317. NYC, 2002. 181 M.H. MacDaugall, Sirnulofig Compufer Sysremr Techniques and Toolr. TheMIT Press, 1987. [Y] A.S. Tanenbarn, Compuler Network. S4 ed. Prentice-Hall. 1996. which reduces to (1) iffin=l for all n. write eq. (12) as follows: Finally, for the case of unsynchronized piconets, we can re- 388