Soft real-time communications over Bluetooth under interferences from ISM devices

Soft real-time communications over Bluetooth under interferences from ISM devices J. L. Sevillano, D. Cascado, F. Dı´ az del Rı´ o, S. Vicente, G. Jimenez and A. Civit-Balcells ETSII, Universidad de Sevilla, Av. Reina Mercedes, s/n. 41012, Sevilla, Spain SUMMARY Bluetooth is a suitable technology to support soft real-time applications like multimedia streams at the personal area network level. In this paper, we analytically evaluate the worst-case deadline failure probability of Bluetooth packets under co-channel interference as a way to provide statistical guarantees when transmitting soft real-time traffic using ACL links. We consider the interference from independent Bluetooth devices, as well as from other devices operating in the ISM band like 802.11b/g and Zigbee. Finally, we show as an example how to use our model to obtain some results for the transmission of a voice stream. KEY WORDS: Bluetooth; co-channel interference; soft real-time; worst-case deadline failure probability 1. INTRODUCTION Bluetooth is currently one of the most successful standards for low-power, short-range wireless personal area networks (WPAN). A wide range of devices are being introduced, with applications supporting asynchronous and/or isochronous data transfers. The motivation of this work is that more and more wireless devices are also introduced that operate in the same frequency bands than Bluetooth devices (the so-called ISM-Industrial, Scientific & Medical bands), including IEEE 802.11, IEEE 802.15.4, WirelessUSB, etc. Depending on the level of sensitivity to the interference from other devices, some types of traffic may suffer from unpredictable delays or packet losses due to these interferences. In this paper, we evaluate the real-time behaviour of Bluetooth communications, and show how interferences from other ISM devices can be taken into account. A typical Bluetooth system is composed of a small number of devices that form a wireless network called a piconet. Connections are established ad hoc by a Bluetooth unit that becomes a Contract/grant sponsor: Spanish Ministry of Science and Technology; contract/grant number: Heterorred: TIC20011868-C03-02 Correspondence to: Jose´ Luis Sevillano, ETSII, Universidad de Sevilla, Av. Reina Mercedes, s/n. 41012, Sevilla, Spain. E-mail: [email protected] master so that the other units (slaves) synchronize with it. The Bluetooth channel is then divided into slots of length 625 ms so that time slots are alternatively used by master and slaves (time division duplex). Any unit may function as a master or as a slave (this role is maintained only for the duration of the piconet), but although it may participate as slave in multiple piconets, it can only be a master in one piconet. Two types of connections can be established in Bluetooth [1]: synchronous connectionoriented (SCO) and asynchronous connectionless links (ACL). In ACL links, the master of the piconet performs a polling among all the slaves, although the polling policy is not specified by the current Bluetooth specification because the best policy depends on the application. Slave devices can only transmit if the master has requested them in the preceding slot. ACL packets require acknowledgement and they are retransmitted in case of errors using a fast automatic repeat request (ARQ) scheme until they are successfully delivered. Several types of ACL packets are defined depending on whether they use forward error correction (FEC) or not. Also, multislot packet transmissions are allowed (three or five slots packets). On the other hand, SCO links are based on a fixed and periodic pre-allocation of slots (every two, four or six slots) for guaranteed transmission of continuous (audio–video) streams. SCO packets are always one slot length and they are never retransmitted. If errors occur during transmission (not corrected by FEC) they are ignored and the packet is delivered as it is received. Finally, the master does not have to poll the slaves in SCO links, so a slave may transmit an SCO packet without a previous request. A typical use of Bluetooth would be the support of soft real-time applications like multimedia streams. In these applications, the use of SCO links monopolizes bandwidth and leaves very little room for other ACL links. Several authors [2, 3] have proposed that ACL links could be used to carry voice and other isochronous traffic. These applications require QoS guarantees in terms of delay, delay variation and loss rate [4], so several attempts have been made to provide these guarantees in ACL links [5, 6]. However, these works ignore the possibility of interferences from other devices. When using wireless connections we should always keep in mind that a system with several interfering devices is probabilistic in nature. In the case of ACL links, 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 operating in the ISM band: WLANs like IEEE 802.11, IEEE 802.15.4 networks [7], WirelessUSB [8], microwave ovens, etc. The problem of coexistence with other devices has received considerable attention in the literature [9–14]. However, these studies are limited to the computation of parameters like bit error rates (BER) or the probability that a given packet suffers a collision. To the best of our knowledge, they have not been used to provide real-time guarantees for Bluetooth connections taking into account co-channel interferences. Maybe the only exception is [15] where the authors compute the probability that a packet does not meet its deadline for two-way transactions under interferences from other Bluetooth devices. However, they do not take into account the effect of the polling algorithm or the interference between SCO and ACL packets. Furthermore, their sources of interference are only other independent Bluetooth devices. In this paper, we present an analysis that allows us to obtain the probability that a Bluetooth packet exceeds its deadline, taking into account the effect of the polling within the piconet, the presence of SCO links and the interferences from other ISM devices, including 802.11b/g, Bluetooth and Zigbee. Our approach was outlined in a previous paper [16], where we proposed the use of schedulability tests like those that have been used to provide guarantees on message delays in distributed real-time systems [17]. These analyses use the worst-case transmission times to bound message response times, and to assess the schedulability of the system. When packet transmission times cannot be upper-bounded, as is the case with Bluetooth piconets under cochannel interferences, then a probabilistic analysis is needed. One possibility is statistical rate monotonic scheduling (SRMS) [18]. A simpler approach is the probabilistic time-demand analysis used for single-processor systems with semi-periodic tasks (tasks released periodically but with random computation times) in Reference [19]. However, any of these approaches are difficult and computationally expensive. In this paper, we would rather evaluate the worst-case deadline failure probability (WCDFP), considering collisions from other ISM devices in a similar fashion to that used to take into account transmission errors in controller area network (CAN)-based systems in Reference [20]. To illustrate our methodology, we show some results for the transmission of a voice stream, ‘...one of the most sought-after applications for IEEE 802.15.1 [i.e. Bluetooth] devices, and they are most susceptible to interference’ [9]. However, our approach is useful in any time-critical application. The paper is organized as follows. In the next section, we first compute the worst-case response times ignoring interferences. Then in Section 3 we discuss how to include the effect of interferences, and in Section 4 we propose an unified model to include interferences from different ISM devices, particularly 802.11b/g, Bluetooth and Zigbee. In Section 5, we evaluate as an example the transmission of a voice stream through an ACL link under interferences. Finally, we present our conclusions. 2. WORST-CASE RESPONSE TIME Consider a piconet composed of a master and up to seven slaves, with several SCO and ACL links. SCO packets have pre-assigned slots and always pre-empt ACL packets. Furthermore, they are never delayed, so their response times remain constant regardless of possible interferences. That is, the packet may be corrupted or not, but its response time is not affected by possible interferences. Although the behaviour of SCO links could also be evaluated using the probability that the packet is corrupted as a measure of performance, several reasons make ACL links more interesting. In coexistence scenarios, that is, situations where the main reason for packet drop is due to the interference from other devices and not due to noise or range, FEC protection will cause the Bluetooth unit to send more packets for a given amount of data, and this results in higher interferences [9]. DHx (Data High rate) ACL packets are therefore preferred since they are not FEC encoded. On the other hand, it has been shown that if ACL links are used for isochronous traffic (like voice) instead of SCO links, other ACL links like TCP behave better, with the voice quality only slightly affected [3]. For these reasons, in this paper we consider the use of ACL links to support real-time transmissions, and as a result we focus only on the computation of worst-case response times of ACL packets, while SCO packets are considered simply as a source of interference. Therefore, consider N(N47) slaves with active ACL links. In this paper, we assume for simplicity that each ACL packet occupies a single slot. Only a single ACL link can exist between the master and every slave [21], and the polling is performed only with slaves with ACL links. Outgoing ACL packets are queued whenever they suffer delays from three possible sources: *The polling mechanism. An ACL packet has to wait for the poll when it is the other nodes’ turn. *Pre-emption from SCO packets. *Interferences from other ISM devices. These interferences may destroy the packets so they introduce additional delays. In this section, we present an analysis to compute worst-case response times of ACL packets including the delays due to the first two sources of interferences, while in the following section we extend this analysis to include interferences from other ISM devices. In our model, an SCO packet jis characterized by its period (T SCOj ) and its constant transmission time (C SCO ). Although the Bluetooth channel is divided into slots of length 625 ms, due to the time division duplex mechanism we should count two slots per transmission. In other words, every transmission includes one slot for the packet and another one for the acknowledgement. Therefore, we consider for our discrete-time model a time unit dslot ¼2n625 ms;so that CSCO ¼1d slot. On the other hand, an ACL packet iis characterized by its period (T i ), z deadline (D i )and transmission time (C i ). In what follows, we assume that ACL packets transmission times do not depend on the priority level (the Bluetooth MAC layer does not support priorities except for the priority of SCO over ACL packets). As a result, we write Ci¼C;for all i. We also assume that packets must be received before the end of the period of the sending task (that is, D i 5T i ), to avoid packets from successive invocations of the sending task to delay each other. Several intra-piconet polling algorithms have been proposed [22]. In this paper, we consider a pure round-robin (one packet per visit), because it is the most used in current Bluetooth connections [5]. Furthermore, it has been shown that PRR has a good performance at high loads [22]. Anyway, other polling schemes could also be considered in our model. We are interested in the computation of the worst-case response time of an ACL packet that may be delayed by other ACL/SCO packets. With the PRR algorithm, we can distinguish between two cases: *Packets queued at a given node. Since only a single ACL link can exist between the master and every slave, there is no interference on a given ACL packet mdue to local (within the node) higher priority packets except for SCO packets. *Packets queued at other nodes (ACL links between the master and the other slaves). While our reference ACL packet mis waiting for the poll, these packets are being transmitted. They can be modelled as a single ‘high priority packet’ with periodicity equal to the polling period T POLL [17]. The interference due to packets in other nodes is given by the number of times this ‘higher priority packet’ with period equal to T POLL is scheduled for transmission during the worst-case packet response time: Qm TPOLL  ðTPOLL CÞ where Q m is the queuing time of our reference ACL packet m, that is, the time packet mspends in the queue (time from being queued to the time transmission begins). In the PRR case, nodes are only allowed to transmit a single packet per visit. Therefore, TPOLL ¼NnC:Every time this z If the traffic in the ACL link is not isochronous, then the period should be interpreted as the minimum time between successive packets. ‘packet’ interfere a given packet m, we have to wait TPOLL C¼ðN1ÞnC:Therefore, the total interference on a given packet mis Qm NnC  ðN1ÞC We also have to add the periodic and fixed interference from SCO packets, which does not depend on the node they may be generated. The master can support up to three simultaneous SCO links while slaves can support two or three SCO links. Therefore, the interference from these packets can be found by calculating the number of times successive instances of SCO packets could be scheduled for transmission in front of a given ACL packet m: X 8j2SCOS Qm TSCOj  CSCO where SCO S is the set of SCO links in the piconet. We assume that the jitter (the maximum time variability between subsequent packets of an SCO link) is null. The queuing time can now be found iteratively [17]: Qnþ1 m¼Qn m NnC  ðN1ÞCþX 8j2SCOS Qn m TSCOj  CSCO ð1Þ The total response time of a given ACL packet min the worst case is then: Rm¼QmþCð2Þ If interferences from other ISM devices are ignored, then whatever polling scheme is used collisions do not occur within a piconet. Therefore, the packet transmission time is a constant. Since we are considering single-slot packets, then C¼1d slot of 2n625 ms (time division duplex). 3. CONSIDERING INTERFERENCES If interferences are considered, we say that a collision occurs when the packet is received incorrectly due to these interferences. The sender is notified of this error in the slot directly following the unsuccessful transmission using a fast-ARQ scheme [1]. The packet is then retransmitted at the next opportunity (in alternate slots) until it is successfully received. Therefore, the transmission time Ccannot be considered a constant anymore. Instead, it becomes a (discrete) random variable, so Cand Q m are random variables. Therefore, a probabilistic time-demand analysis should be used analogous to that used for single-processor systems with semi-periodic tasks (tasks released periodically but with random computation times) in Reference [19]. However, this approach is very difficult and computationally expensive because we have to compute the probability density function of Q m from the probability density function of random variable C. Instead, since we are only interested in determining the probability that a packet meets its deadline, we will use a different approach. Let us denote by P S the probability of successful transmission. In a piconet with ACL links, the wasted time units due to collisions correspond to a sequence of Bernoulli trials with probability of success P S . The overhead for every collision is just a packet retransmission C. Therefore, the effect of interferences can be included in our model of Section 2 by adding a collision overhead E(X) that is a function of the number of collisions during a time period X.If SCO packets are ignored, EðXÞ¼knC;with kbeing the number of collisions during any time period X. However, we have to take into account that SCO packets are not retransmitted in case of collisions (in that case, the packet is simply corrupted but delivered ‘as is’). Therefore, k should be computed as the number of collisions occurring in any time period X excluding the transmission period of SCO packets. We will take this into account in due course. Anyway, considering co-channel interferences, Equation (1) becomes Qnþ1 m¼EðQn mþCÞþ Qn m NnC  ðN1ÞCþX 8j2SCOS Qn m TSCOj  CSCO ¼knCþQn m NnC  ðN1ÞCþX 8j2SCOS Qn m TSCOj  CSCO ð3Þ Note that Cis again a constant C¼1d slot ¼2n625 ms (for single slot packets) because all the effects of collisions are included in function E(). The response time of packet mwith kcollisions can now be computed iteratively. First we iterate Equation (3) with k¼0;obtaining a first result for Q m , and through Equation (2) for R m . Then we increment kand repeat the iterative computation to obtain new results for Q m and R m . We repeat this algorithm until R m >D m (or the iteration does not converge). In this way we obtain K m , which we define to be the maximum number of collisions for which R m 4D m (since the final value k f makes R m exceed the packet deadline, we have Km¼kf1). Let Q MAX be the last obtained value of Q m , that is, the queuing time obtained through the following iteration: Qnþ1 m¼KmnCþQn m NnC  ðN1ÞCþX 8j2SCOS Qn m TSCOj  CSCO ð4Þ and also let R MAX be the last obtained value of R m : RMAX ¼QMAX þCð5Þ so it represents the worst-case response time when the maximum tolerable number of collisions K m occur. Once K m and R MAX are obtained, we are now able to calculate the worst-case deadline failure probability (WCDFP) simply as the probability that more than K m collisions occur during R MAX . Since we assume that time is slotted, with a time unit d slot ¼2n625 ms;then the probability that a collision occurs in a given time unit is 1P S (i.e. the probability that the transmission is not successful). Therefore, we have that the probability that kcollisions occur during a time period Xis X k ! ð1PSÞkPXk Sð6Þ In our case, the time period is R MAX but transmission of SCO packets should be excluded. Therefore, X¼RMAX X 8j2SCOS QMAX TSCOj  CSCO ð7Þ Now, the WCDFP for an ACL packet mis given by WCDFPm¼1X Km k¼0 X k ! ð1PSÞkPXk Sð8Þ with Xgiven by Equation (7). 4. PROBABILITY OF SUCCESSFUL TRANSMISSION The analysis developed in Section 3 provides the WCDFP for an ACL packet as a function of the probability of successful transmission. In this section, we show how this probability can be obtained when there are different ISM devices interfering with our reference ACL packet. We begin with the case of interferences due to other independent Bluetooth devices. In order to reduce interferences (among other reasons), Bluetooth uses Frequency Hopping, with a pseudo-random hopping sequence. We can then assume that a Bluetooth device transmits using randomly chosen frequencies. Therefore, there is a possibility that several independent (but interfering) Bluetooth devices coexist in the same area and that they choose the same hop carrier. We can assume that hops are evenly distributed over 79 different frequency bands [23]. It can be shown that if M B is the number of interfering piconets (including the reference piconet) and ris the normalized load over every piconet (assuming a homogeneous traffic, so ris the same for all the piconets) then the probability of successful transmission is [15] PSjBB¼2ð1sÞ1r 79  þð2s1Þ1r 79  2  2ðMB1Þ ð9Þ where s¼366=625 ¼0:5856 is the ratio between the actual transmission time of a single slot packet and the Bluetooth slot duration. Recall that this expression is based on the fact that a successful transmission occurs 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 in the packet itself. This expression can be simplified if we neglect the term (r/79) 2 50.00016: PSjBBffi12sr 79  2ðMB1Þð10Þ Since we are concerned with the worst-case behaviour (in order to provide QoS or real-time guarantees), then this pessimistic approximation can be considered a lower bound on the probability of successful transmission, and also the case of fully loaded piconets should be used, that is, r¼1:Furthermore, although a time and frequency coincidence does not always destroy the packet, depending on the strength of the interference signal arriving to the receiver [24, 25], we also assume the worst-case: interference of just one bit is enough to destroy the whole packet. This previous model can be easily interpreted as the probability that none of the other M B 1 piconets transmit with the same carrier than our reference piconet in two consecutive slots. The facts that the actual packet transmission time is only of duration sslots and that independent piconets are not synchronized are taken into account through the factor 2s. We will use this model to show how to include interferences from other independent Bluetooth devices in the computation of the worst-case response time of ACL packets. However, many other more complex (and not so pessimistic) interference models could also be used [25], including the multislot case discussed in Reference [11]. Other non-Bluetooth devices may also produce interferences. The most important source of interference are 802.11 devices, and their effect on Bluetooth transmissions are well studied in the literature [10,12–14]. In this paper, we use the model described in Reference [14] which assumes the worst case that a time and frequency coincidence always destroys the packet. Let H and Wbe the transmission times of a single slot Bluetooth packet (H¼366 ms) and of an IEEE 802.11 packet, respectively, and also let Lbe the dwell period of an IEEE 802.11 packet. Finally, if we define Gas G¼dH=Le*LWH then it can be shown that the probability of a successful Bluetooth transmission under interferences from 802.11 devices is [14] } PSjBW¼1jGj L  1B 79  dH=Le þjGj L 1B 79  dH=LeG=jGj "# 2MW ð11Þ M W is the number of interfering 802.11 devices, and Bis the channel width of the 802.11 system, that is, B¼22 MHz for 802.11b and B¼16:5 MHz for 802.11g (we only consider direct sequence spread spectrum}DSSS systems). Different from Reference [14], we take again into account that a successful transmission occurs if there are no collisions in two consecutive (and independent) Bluetooth slots. Also note that we ignore coexistence mechanisms like adaptive frequency hopping (AFH), alternating wireless medium access (AWMA), etc. [10]. An interesting observation is that Equations (9) and (11) are essentially based on the same reasoning. Particularly, although Equation (11) was obtained in Reference [14] only for the case of interferences from 802.11 devices, in fact Equation (9) can be obtained as a particular case of Equation (11). Indeed, if we take W¼H(the interfering device is also a Bluetooth packet) and s¼H=L51 in Equation (11), we have G¼ðL2HÞ50:Finally, since for a Frequency Hopping system like Bluetooth B¼1;we obtain Equation (9) for the case r¼1: The same approach could also be used for other ISM devices. For instance, an IEEE 802.15.4 (Zigbee) transmission using the ISM band will interfere with Bluetooth in approximately 3 out of the 79 hops [7, Annex E]. Usually, in a sensor network the probability of activity of every node is very low, and also the transmission time of an 802.15.4 packet is much larger than the duration of a Bluetooth slot, so we could use Equation (11) with B¼3 and L4W4H:In this case, G¼ðLWHÞ>0:Therefore, the probability of a successful Bluetooth transmission under interferences from 802.15.4 devices could be expressed as PSjBZ¼13 79 u  2MZ ð12Þ where M Z is the number of interfering 802.15.4 devices and u¼ðWþHÞ=LffiW=Lcan be interpreted as the probability of activity of an IEEE 802.15.4 node. Recall that in a typical sensor network MZ4and u5: } In case the M W 802.11 devices have different values for W and L, that is, the traffic is not homogeneous, then obviously Equation (11) becomes a product of M W terms. To sum up, we have shown that Equation (11), originally developed only for the case of interferences from 802.11 devices, provides us with a generic model that can be used to model interferences from other ISM devices. Redefining parameters like B,H,Lor W, we can obtain the probability of a successful Bluetooth transmission under interferences from different ISM devices. In the general case, the product of the PSjBXterms should be used. For instance, if 802.11, Zigbee, and independent Bluetooth devices are present, then: PS¼Y X¼fB;W;Zg ðPSjBXÞ An important consideration is that these models assume the worst case that a time and frequency coincidence always destroys the packet. Although we think they are still useful for the computation of worst-case, real-time guarantees, we should be careful because many of their results may be too pessimistic. For instance, IEEE 802.15.4 networks are tailored for applications with low power, so the probability of interferences due to these devices is relatively low even in case of time and frequency coincidence. In other words, parameters M X should not be interpreted as nodes operating in the same area, but as nodes that have sufficient power to cause a collision. 5. EXAMPLE: VOICE OVER ACL LINKS UNDER CO-CHANNEL INTERFERENCE The analysis developed in this paper is useful for any time-critical application. Only for illustration purposes, let us consider as an example the transmission of a voice stream in several configurations. First, consider a configuration composed of a piconet of 3 slaves, where 2 slaves use ACL links. We also assume that the other node is using an SCO link in order to show how our model is able to include this additional source of interference. However, in order not to monopolize the bandwidth we assume that this SCO link uses HV3 packets, that is, one-slot packets that are sent every six slots. We assume that one of the ACL links is used to carry a voice stream. Voice can be implemented as 8 kbps coded speech, with voice packets of 20 bytes every 20 ms [3]. DH1 packets (28 bytes maximum) can be used when carrying this traffic over ACL links. We assume that the deadline of these packets is equal to the time gap between arrival of two packets, that is, Ti¼Di¼20 ms: Now, let us apply the model described in Sections 2–4 to compute the WCDFP of these voice packets in the presence of interferences from the other ACL and SCO links of the piconet, as well as from other independent Bluetooth devices. In this configuration, 2 slaves use ACL links so N¼2:Also, C¼CSCO ¼1d slot because only DH1 and HV3 packets are used. Finally, TSCO ¼3d slots for HV3 packets, so Equation (3) becomes: Qnþ1 m¼kþQn m 2  þQn m 3  We now iterate with k¼0;and obtain a final value Qm¼2d slots, and using Equation (2) Rm¼3d slots ¼3:75 ms;which is less than the deadline Dm¼20 ms:We then increase k,and repeat the process. This way, we obtain a final value for Km¼2;QMAX ¼12 d slots and RMAX ¼13 d slots ¼16:25 ms;which meets the deadline Dm¼20 ms:If more than two collisions occur then this timing requirement is not met.