Performance analysis of single-slave Bluetooth piconets under cochannel interference

PERFORMANCE ANALYSIS OF SINGLE-SLAVE BLUETOOTH PICONETS UNDER COCHANNEL INTERFERENCE D. Cascado, J. L. Sevillann, S. Vicente, F. Diaz del Rio, G. Jimhez, A. Linares, A. Civit-Balcells. ETS lngenieria lnformatica. Universidad de Sevilla. Avda. Reina Mercedes sin. 41012, Sevilla (Spain). Abstract In this paper, we present an analytical model for single-slave Bluetooth piconets when the coexistence of multiple interfering devices produces collisions. Closedform expressions for the channel throughput and the mean packet delay are obtained, including the time spent waiting on the node's queue. The effect of propagation losses and asynchronous piconets are also discussed. The results of the analysis are validated through simulation. Keywords Bluetooth, co-channel interference, performance analysis, piconet, WGil systems. I. INTRODUCTION Bluetooth is a global standard for a low-power, short-range Wireless Personal Area Network (WPAN). A typical Bluetooth system is composed of a small number of devices that form a wireless network called a piconet. Since connections are established ad-hoc, a variable number of piconets may coexist in the same area. A typical scenario may consist of a number of people with portable (and moving) devices entering a common area and connecting to fixed networks and mayhe to other portable terminals (for instance to share documents in a meeting) [l]. 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 currently a very popular band for wireless short-range devices [2]. However, we only focus on the interference generated by Bluetooth devices, although there are many possible sources of intefierence (microwave ovens, 802.1 1 LANs, etc.). When a Bluetooth unit establishes a piconet, it becomes a musfer so that the other units (slaves) synchronize with it. Any unit may hnction 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 he a master in one piconet. The Bluetooth channel is divided into slots of length 625~s so, 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 0-7803-8523-3/04/$20.00 02004 IEEE. and up to I 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. The scheduling policy is not specified by the current Bluetooth specification because the best policy depends on the application. Several alternatives have been studied in the literature mainly through simulation [3], with very scarce analytical studies [4]. The actual scheduling should be implemented at the middleware level. However, a common use of current Bluetooth devices is simply a point-to-point link between the master and a single slave, that is, a "single slave piconet". In this paper, we are especially concerned with this simple case. Whatever polling scheme is used, within a piconet collisions do not occur. Therefore, interference may only occur among devices connected to different logical channels (independent piconets or scatternets). 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 Connecfed Mode, used in all usual transmissions, distributes the hops evenly over all carriers. We denote the number of hop camers as M, although the Bluetooth specification defines 79 different frequency hands at IMHz spacing [SI. The slot length of 625ps 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 the same area, we can assume that they transmit using randomly chosen frequencies. Of course, there is a possibility that several devices choose the same hop carrier. In that case. 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 [SI. The packet is retransmitted at the next opportunity (in alternate slots) until the packet is successfully received. 11. PREVIOUS WORKS Several recent studies have addressed the problem of the analysis of channel interference in Bluetooth systems. El- Hoiydi [6] studies the worst case, that is, he considers 100% traffic. As a result, his model provides upper hounds on the packet error rate (probability of collisions) as well as lower hounds on the throughput. On the other hand, Lim et al. [7] 954 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 course, in the Bluetooth specification piconets are not synchronized, but equations for the synchronous case are much simpler and they may provide acceptable predictions in some cases. Lim et al. also consider multi-slot packet transmissions. Packets delays are also an important performance parameter. El-Hoiydi and Decotignie [SI present delay hounds for twoway (DATA-ACK) transactions under co-channel interference. Also in a previous work [9], we obtained simple expressions for the mean delay that packets suffer due to possible collisions with other Bluetooth devices. We modelled the different effects of new and retransmitted packets, and also discussed the differences between the synchronous and asynchronous cases. However none of these works include the effect of the waiting time in the device buffer. This delay can be modelled using queuing theory. For instance, a recent work models several polling policies in Bluetooth piconets using MIGII queues with vacations [4], but ignoring the effects of interferences with other devices. However, in this paper we are interested in modelling these interferences. Since the scheduling policy is not specified by the Bluetooth specification, we will only consider the case of single-slave piconets in order to exclude the polling delay from our analysis. It is clear that a single-slave piconet can be modelled as an WGil system, with the Bluetooth channel considered as a single-server system with an arbitrary service time distribution. In all of these references the mitigation effects of propagation losses of radio waves are ignored, that is, it is assumed that the interference of just one 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 terminalslobstacles, environment geometry, etc. For instance, Kamik and Kumar [IO] present an analytical model for the packet loss probability, obtained by limiting the number of interfering piconets to three because it is very complicated to obtain even approximate results for a higher number. Probably, one of the most interesting approaches for our purposes is given by Mazzenga et al. [ll]. They provide a simple way to include these effects in the analysis of channel interference, and we will use their approach in our model. In the following sections, we first present our model assuming synchronised interfering piconets, beginning with the computation of the probability of a successful transmission and then deriving important parameters like channel throughput. Also, although the effect of propagation losses are not explicitly considered, we show how they could be included in our model following [ll]. Then, in order to model the Bluetooth device as an WG/I queue we fust derive the mean and variance of the “service time”, which in a single-slave piconet is just the delay due to collisions, and derive an expression for the waiting time in the queue. In the subsequent section we present some simulation results in order to validate the model, and finally we present ow conclusions. 111. ANALYSIS Let N be the number of interfering piconets. We first assume that all the piconets are synchronized among them (later in this section we discuss this issue further). Let r he the normalized load over every piconet. We assume a homogeneous traffic, so r is the same for all the piconets. Collisions may occw if devices in different independent piconets use the same camer. In that case, packets are retransmitted in alternate slots. For a given piconet, which is transmitting in a slot in a particular camer, 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 1-r/M. Therefore, the probability that n out of the interfering piconets produce a collision in a slot is where ,l% are coefficients that include propagation losses and capture effects [I I]. Their computation is not easy because they depend on the geometry and propagation characteristics of the environment, the position of obstacles and Bluetooth devices for every interfering piconet, etc. A possible solution to this issue is proposed in [ 141. Anyway, a successful transmission occurs only if there are no collisions in two consecutive (and independent) slots: one for the packet and the other one for the acknowledgement (ACK). If the ACK is not received, the packet is retransmitted as if a collision had occurred. Therefore, the probability of a successful transmission is given by with q(n) given by eq. (1). Note that we assume that all piconets devices (master or slave) produce the same load over the piconet. If we ignore propagation effects (that is, /3,,=1 for all n), then eq. (2) becomes: which coincides with the result in [7]. This result can be easily interpreted as the probability that none of the other N- 1 piconets transmit with the same carrier than ow reference 955 piconet in two consecutive slots. Now we are able to obtain the thruughpirt (the rate of successfully transmitted packets) simply as S=rPs, that is, the probability that a transmission attempt occurs and that this attempt is successful. Equation (2) was obtained assuming synchronized piconets. The effmt of consideing asynchronous piconets is always small because in the Bluetooth standard a single slot packet is only of duration 366ps, while the time-slot length is 625~s. In a previous work [9], we showed that a simple expression for Ps for the asynchronous rase is .-( = - (2Rr) Ay-'' , which is similar to eq. (3) except for the factor 2R. Here we take into account that r/M<<1(#79 in most cases, andr4) so we neglect the term (r/h.02. In other words, the equations for the synchronous case provide an acceptable approximation to the asynchronous case just assuming in our equations an increase of ZR (17%) in the offered load. As discussed in section I. in this paper we are also interested in the estimation of message response times. Let us first compute the mean delay that a packet suffers due to possible collisions with other Bluetooth devices, ignoring the waiting time in the queues. The wasted slots due to collisions correspond to a sequence of Bernoulli trials with probability of success Ps [9]. The number of wasted slots is therefore geometrically distributed, so its mean is: (4) Considering that any device transmit in alternate slots, the mean delay including the successful slot is expressed in slots of length 625p. Note that this expression represents the mean delay that packets suffer due to possible collisions with other Bluetooth devices, excluding waiting times in the queues. Also note that we add one slot for the successful transmission while a single slot packet is only of duration R=366/625=0.5856 slots. This difference should be taken into account mainly for small loads (W<<). A. Considering the time spent in the queue. So far, we have only considered the delay that the packet suffers due to collisions with other Bluetooth devices. In single-slave piconets, the other source of delay is the time spent waiting on the node's queue. We model the device queue as an M/G/I system. We assume that messages arrive following a Poisson distribution, with mean h messages per second. The Bluetooth channel is considered a single-server system with an arbitrary service time distribution. For such a WGII system, the average number of customers in the queue is given by the Pollaczek-Kinchin mean value formula [12] where var[q and T are the variance and the mean of the service time distribution, respectively, and p is the utilimlionfucfor. Now using Little's law, we get the mean waiting time in the queue The second expression comes from the fact that p=hT. In order lo relate this expression with the model developed above, we use r (the offered load) instead of p, as a measure of the probability that the system is busy. If interference from other Bluetooth devices is ignored, then service time is a constant (var[q=O) and the system becomes an M/D/I system. With several interfering piconets the mean service time should include the slots wasted due to collisions, and therefore is given by 2W+2, with Wgiven by eq. (4). Note that the queue is emptied only in alternate slots and therefore the service time for the WG/I queue includes two slots per transmission attempt. The variance can be obtained since the variance for the geometric distribution of the number of wasted slots Wis: By definition V~I[T]=T~-(T~, so from eq. (5) we get that the variance of the service time distribution is var[T]=4var[W]. As a final result, the total time that a packet spends in the system can be obtained as the sum of the time in the queue and the packet service time itself [eq. (5)]: This equation is expressed in slots of length .r=625ps. A final observation is that the mean queuing delay of a normal WG/1 queue and that of an WG/I queue with clocked service differs by half the clock interval [ 131. Therefore, due to the slotted time assumption, we should modify eq. (9) by increasing the mean delay by one slot of 625~s, since the clock interval of OUT M/G/l system is 2.r (two slots per transmission attempt). IV. VALIDATION In order to validate the above model we performed several simulations with a detailed Bluetooth simulator developed using Matlab 6.1. For the comparison between analysis and simulation, we considered a variable number of interfering single-slave piconets, ignoring propagation losses of radio waves and other effects like forward error correction. That is, we assume that a cochannel interference will always 956 destroy all packets. Piconets are synchronized and packets are generated with exponential inter-arrival times. Finally, since we are only interested in the comparison between the models, we assume single-slot packets. Figure 1. Channel throughput vs. Offered load for a variable number of interfering piconets. In Figure 1 we show the throughput-offered load characteristics for 2, 5 and 10 interfering piconets, from both the simulation and the analytical model [using eq. (3)]. It can be observed that the estimation using the analysis is very close to the simulation results. Note that as the number of interfering piconets grows, the maximum throughput decreases because of the slots wasted due to collisions. Although not shown in Figure 1, a hump can he observed with very large N, that is, maximum throughput is achieved at medium loads and then throughput decreases for higher values of the offered load [7]. The reason is that in this situation the channel is almost “idle” (because of the wasted slots due to collisions) while there are packets in the system waiting to he transmitted. However this very high number of interfering piconets (N>40 [7]) is not common in a real scenario. Furthermore, when N becomes larger, a higher distance separates Bluetooth devices. As a result, the effect on the probability of collision of devices situated far away becomes almost negligible. That is, in eq. (I) the assumption of ,&=I for all n is no longer valid. This intuitive reasoning is confirmed through simulation in [SI, where it is shown that the packet error probability remains almost constant as N increases. Our model would he able to include this effect if we could estimate adequate values for p,,. This is the matter of further research. However, in this paper we maintain the assumption that co-channel interference always destroy the packets and for this reason we only consider relatively low values for N. Figure 2a, 3b and 3c show the mean delay versus offered load characteristics for N=2, N=5 and N=10 respectively, using a logarithmic scale because of the very high values of the mean delay at high loads. The simulator counts 366p for the transmission time of one slot packet, while eq. (9) includes one full slot of 625ps for the successful transmission. This difference between the models would produce small deviations limited to the zone of small loads. Instead, we prefer to modify eq. (9) by using the actual transmission time of R=366/625=0.5856 slots instead of one (successful) slot. With this change, the comparison between the models confirms the accuracy of the analysis. Note that the mean delay increases very rapidly with the offered load. If queuing delay is not considered, the mean delay increases slowly with the offered load as expected from eq. (5) (see [9]). On the other hand, it is a known result that waiting times in a queue depend on the first and second moment of the service time distribution [12]. Therefore, the higher the variance of the service time, the worse the performance. In our case the mean waiting time in the queue increases with the variance of the number of wasted slots [eq. (7)]. This variance is given by eq. (S), where it can he seen that it grows with r much more rapidly than the delay due to collisions itself, since Ps is a decreasing function of r. This result is intuitive since retransmitted packets have the same opportunities than new packets, so it may occur that some unlucky packets suffer very large delays. As a result of this high variability of the service times, the queue size (and thus the time spent in the queue) grows very rapidly with r, especially when the number of interfering piconets is large. This is the reason of the high values for the mean delay in Figure 2. Finally, an important observation is that the offered load includes both new packets as well as the retransmission attempts of previously collided packets. Therefore, the actual offered load over the channel may he much higher than the “original” load due to the higher-level protocols (see [9] for numerical results). As a result, the values of the offered load for which the mean delay suddenly increases may be relatively not unusual. V. CONCLUSIONS When many Bluetooth devices coexist in the same area, the problem of channel interference may become of high importance. In this paper we have presented an analysis that adequately models the effect of this interference in performance. Particularly, we obtain simple expressions for the channel throughput and the mean packet delay. The analysis has been validated through simulation. We have also discussed how to include the effect of propagation losses and the fact that in general piconets are not synchronised. Although the delay due to the polling policy in multi-slave piconets is not considered, our results could he useful for any Bluetooth connection under co-channel interference. 957 : 18' I . ", Figure 2. Mean packet delay vs. Offered load. Differently from other models in the literature, the analysis also includes the waiting times in the queues. This is especially important in this case because although collisions produce an increase in the mean service time of a packet, it is the variance of this time that tends to grow very rapidly with the offered load and the number of interfering piconets. As a result, the waiting time in the queues increases rapidly and becomes the most important component in the packet delay. This effect may become a serious drawback in applications like continuous voice or video streams, realtime control, etc. even in situations where the number of interfering Bluetooth devices is relatively low. VI. ACKNOWLEDGEMENTS The Spanish Ministry of Science and Technology supported this work under contracts TIC2001-1868-'203-02 and TIC2000-0087-P4-0 1. REFERENCES [I] P. lahamsan, M. Kazantzidis, R. Kapoor, M. Gerla, Bluetooth: An Enablcr for Personal Area Networking, IEEE Nctwork, 15 (2001) 28- 37. [2] M. HBnnikZinen, T. D. HZmBlainen, M. Niemi, J. Saarinen, Trends in personal wireless data communications, Computer Communications, [3] A. Capone, M. Gerla, R. Kapoor, Efficient plling schemes for Bluetooth picacells Communications, Proc. IEEE Int. Conf. Comm., pp. 1990-1994,2001, 141 1. Misic, V.B. Misic, Modeling Bluetooth piconet performance, IEEE Communications Lctters 7(2003) I8 -20. [5] J.C. Haartsen, The Bluetooth Radio System,. IEEE Pcrsonal Communications 7(2noo) 28-36. [6] A. El-Hoiydi, Interference Between Bluetooth Networks-Upper Bound on thc Packet Error Rate, IEEE Comm. Lettcrs 5(2001) 245-247. [7] Y. Lim, J. Kim, S.L. Min, J.S. Ma, Performance Evaluation of the Bluetooth-based Public Internet ACCCSS Point. Proc. 15' Int. Conf. Information Nctwarking, pp. 643-648. Beppu, Japan. 2001 [8] A. El-Hoiydi, J.D. Decotignie. SoR-Dcadline Bounds for Two-way Transactions in Bluetooth Picanets under co-channel Interference, 25 (1) (2002) pp. 84-99, IEEE Int. Conf. Emerging Technologies and Factory Automation, pp. 143-150. Oct. 2001. [9] J.L.Sevillano ct al., An analytical model of Inter-channel Interference in Bluctwth-Bascd Syslems. Proc. IEEE MWCN'02, pp. 384-388. [IO] A. Kamik and A. Kumar, "Performance of the Bluctoath Physical Layer". IEEE hf Conf Personal Wireless Comm., pp. 70-74. Hyderabad, India. 2000. [I I] F. Mazzenga, D. Cassioli, P. Loreti, F. Vatalaro "Evaluation of Packet Loss Probability in Bluetooth Networks". Proc. IEEE In/. Conf Comm.,pp. 313-317.NVC, 2002. [I21 B.R. Haverkort, "Performance of Computer Communication Systems". Wiley, 1998. [I31 W. Bun. "Local Area Subnctworks: A Performance Comparison", IEEE ~rans. Comm. COM-~~ (1981) 1465-1473. [I41 D. Cascado, S. Vicente, A. Linares, J. L. Sevillano, G. Jimhez, A. Civil. "Inclusion of propagation effects on packet error rate of Bluetwth networks", IEEE Workhop on Wireless Circuits and Systems. Vancouver, Canada. 2004. stockholm, swede". 20n2. 958