Bridges of Bluetooth county: topologies, scheduling, and performance

The performance of two Bluetooth piconets linked through a shared device is analyzed using the tools of queueing theory. We analyze both possible topologies: the master/slave (MS) bridge, in which the shared device is the master in one of the piconets and a slave in the other, and the slave/slave (SS) bridge, where the shared device is the slave in both piconets. Two scheduling policies, limited service and exhaustive service, are considered. Analytical results are derived for the probability distribution of access delay (i.e., the time that a packet has to wait before being serviced) and end-to-end delay for both intrapiconet and interpiconet bursty traffic. The SS bridge has been found to offer lower access delays and local end-to-end delay than its MS counterpart, which provides lower end-to-end delay for nonlocal traffic due to the smaller number of hops (three, instead of four) for such traffic. In both topologies, exhaustive service scheduling was found to provide lower delays than the limited service one. All analytical results have been confirmed through simulations.     

Efficient Scheduling Algorithms for Bluetooth Scatternets

When more than seven devices are connected in a Bluetooth scatternet, bridge devices are used to connect two piconets to the scatternet. To deal with possible data transmissions between different piconets, the bridge device must frequently switch to different masters. Suppose, however, that a bridge is serving a piconet and the master in another piconet is calling it at the same time, the calling master has to wait until the bridge completes the previous service. Such transmission delay may accumulate over a long period and the performance of the whole Bluetooth network will degrade significantly. In this work, two new scheduling protocols, namely the static schedule and the hybrid schedule were implemented in an effort to smooth this kind of transmission delay in Bluetooth networks. In this static schedule the rendezvous points between piconets are coordinated by distributing them by using a graph edge coloring technique. In case of a heavy traffic load, the static schedule is expected to perform well. On the other hand, in case of a light traffic load, the static schedule may cause long and unavoidable routing delays even when there is no transmission between piconets; in this case a naive random round-robin (RR) schedule in each piconet is more appropriate. Thus, in the hybrid schedule, each master initially runs a RR scheme in its piconet. When the traffic load is heavier than a predefined threshold value, it runs the static schedule. Finally, simulations were conducted by using an ns-2 simulator and Bluehoc to demonstrate the efficiency and effectiveness of the proposed scheduling protocols.

On the Analysis of the Bluetooth Time Division Duplex Mechanism

Efficient communication in Bluetooth networks requires design of intra and inter-piconet scheduling algorithms, and therefore, numerous algorithms have been proposed. However, due to complexities of the Bluetooth MAC, the performance of these algorithms has been analyzed mostly via simulation. We present analytic results regarding the exhaustive, gated, and limited (pure round robin) scheduling algorithms in piconets with bidirectional and unidirectional traffic. We show that a piconet operated according to the limited scheduling algorithm is equivalent to a 1-limited polling system and present exact results regarding symmetric piconets with bidirectional traffic. Then, the difficulties in analyzing the performance of the exhaustive and gated algorithms in a piconet with bidirectional traffic are demonstrated. In addition, we present exact analytic results for piconets with unidirectional traffic. We show that, surprisingly, in symmetrical piconets with only uplink traffic, the mean waiting time is the same for the exhaustive and limited algorithms. This observation results from the differences between piconets and traditional polling systems and can be extended for time-division-duplex systems with arbitrary packet lengths. Furthermore, we show that the mean waiting time in a piconet with only uplink traffic is significantly higher than its corresponding value in a piconet with only downlink traffic. Finally, we numerically compare the exact results to approximate results, presented in the past.     

Adaptive interpiconet scheduling for multipurpose scatternet scenarios

Bluetooth specification still has open issues, including the intra and interpiconet scheduling topics. This article proposes an interpiconet scheduling algorithm, referred to as AISA (Adaptive Interpiconet Scheduling Algorithm). AISA is characterized by its adaptability to varying network traffic conditions; and its ability to optimize specific performance metrics via parameterization. Both features enable it to be employed in a variety of scenarios with improved performance shown by the simulation results.     

Performance of Bluetooth Bridges in Scatternets with Limited Service Scheduling

The performance of two Bluetooth piconets linked through a bridge device is analyzed using the tools of queueing theory. We analyze both possible cases, i.e., when the bridge device is the master in one of the piconets and a slave in the other (MS bridge), as well as when the bridge device is the slave in both of the piconets (SS bridge). Analytical results are derived for the probability distribution of access delay (i.e., the time that a packet has to wait before being serviced) and end-to-end delay, for both intra- and inter-piconet bursty traffic. The scatternet with an SS bridge was found to provide lower end-to-end delay for local traffic as well as lower access delay, while the scatternet with an MS bridge offers lower end-to-end delay for non-local traffic. The scatternet with an SS bridge was also found to be less sensitive to increased probability of non-local traffic and low values of time interval between bridge exchanges, than its counterpart with an MS bridge. All analytical results have been confirmed through simulations.     

A Fair and Traffic Dependent Scheduling Algorithm for Bluetooth Scatternets

The Bluetooth specification defines the notion of interconnected piconets, called scatternets, but does not define the actual mechanisms and algorithms necessary to set up and maintain them. The operation of a scatternet requires some Bluetooth units to be inter-piconet units (gateways), which need to time-division multiplex their presence among their piconets. This requires a scatternet-scheduling algorithm that can schedule the presence of these units in an efficient manner. In this paper, we propose a distributed scatternet-scheduling scheme that is implemented using the HOLD mode of Bluetooth and adapts to non-uniform and changing traffic. Another attribute of the scheme is that it results in fair allocation of bandwidth to each Bluetooth unit. This scheme provides an integrated solution for both intra- and inter-piconet scheduling, i.e., for polling of slaves and scheduling of gateways.     

A Bluetooth scatternet-route structure for multihop ad hoc networks

Bluetooth scatternets, integrating polling, and frequency hopping spread-sprectrum in their medium access control protocol, provide a contention-free environment for Bluetooth devices to access the medium and communicate over multihop links. Currently, most available scatternet formation protocols tend to interconnect all Bluetooth devices at the initial network startup stage and maintain all Bluetooth links thereafter. Instead of this "big scatternet" approach, we propose a scatternet-route structure to combine the scatternet formation with on-demand routing, thus eliminating unnecessary link and route maintenances. To the best of our knowledge, this is the first effort to address on-demand scatternet formation with every detail. We introduce an extended ID (EID) connectionless broadcast scheme, which, compared with original Bluetooth broadcast mechanism, achieves very much shortened route discovery delay. We also propose to synchronize the piconets along each scatternet route to remove piconet switch overhead and obtain even better channel utilization. Furthermore, we present a route-based scatternet scheduling scheme to enable fair and efficient packet transmissions over scatternet routes. Network performance analysis and simulations show that scatternet routes can provide multihop wireless channels with high network utilization and extremely stable throughput, being especially useful in the transmission of large batches of packets and real time data in wireless environment.     

Analysis of packet interference and aggregated throughput in a cluster of Bluetooth piconets under different traffic conditions

In a Bluetooth piconet, the Master essentially controls the channel. Due to an absence of coordination between independent Masters while accessing the wireless medium, devices will encounter high packet interference if several piconets are simultaneously operating in the same area. Since even a headset and a mobile phone can be connected with a Bluetooth link forming a piconet, it may not be unusual to find tens of independent piconets in crowded places like airports, international conferences, shopping malls, and so on. Study of packet interference is important because interference affects the throughput of a piconet. Motivated by the fact that applications will benefit, in terms of higher available data rate in one direction, by using multiple-slot packets in an asymmetric manner, in this paper, we present an analytical model of packet interference in a cluster of piconets using multiple-slot packets. Also, considering that all the portable devices can have a Bluetooth interface and people are highly mobile these days, it will not be uncommon to find a cluster of piconets of both the 79-hop and the 23-hop types in the same area. We then present an analytical model of interference of multiple-slot packets in a heterogeneous cluster of Bluetooth piconets. By a heterogeneous cluster we mean some piconets are of the 23-hop type and the rest are of 79-hop type. We show how the aggregate throughput in a cluster of piconets degrade under various traffic scenarios, such as 1-slot, 3-slot, and 5-slot packets in symmetric and asymmetric modes in synchronous and asynchronous conditions of Master clocks. Our analytic model is based on the idea of probabilistic graphs, where a node denotes a piconet and an edge denotes the probability of interference between two nodes. Though the 23-hop system has been phased out, our work gives a general approach to model packet interference in multiple, frequency-hopping systems that need not be Bluetooth systems.     

Interference modeling and performance of Bluetooth MAC protocol

The emergence of Bluetooth as a default radio interface has allowed handheld electronic devices to be instantly interconnected as ad hoc networks. These short-range ad hoc wireless networks, called piconets, operate in the unlicensed 2.4-GHz ISM (Industrial-Scientific-Medical) band where devices may be used to configure single or overlapping piconets, known as scatternet. As all piconets operate in the same frequency band, the presence of multiple piconets in the vicinity may create interference on signal reception. This paper employs a signal capture model to study the piconet MAC performance, taking inter-piconet interference into consideration. This model leads to several important mathematical relationships for Bluetooth networks, including successful packet transmission probability. Furthermore, our model and anticipated throughput are validated using extensive simulation. These results indicate that Bluetooth throughput is affected by multiple piconet interference. Definitely, our model can be considered to provide a solid foundation for future interference aware Bluetooth protocols.     

A New Bluetooth Scatternet Formation Protocol

A Bluetooth ad hoc network can be formed by interconnecting piconets into scatternets. The constraints and properties of Bluetooth scatternets present special challenges in forming an ad hoc network efficiently. In this paper, we present and analyze a new randomized distributed protocol for Bluetooth scatternet formation. We prove that our protocol achieves O(logn) time complexity and O(n) message complexity. The scatternets formed by our protocol have the following properties: (1) any device is a member of at most two piconets, and (2) the number of piconets is close to be optimal. These properties can help prevent overloading of any single device and lead to low interference between piconets. We validate the theoretical results by simulations, which also show that the scatternets formed have O(logn) diameter. As an essential part of the scatternet formation protocol, we study the problem of device discovery: establishing multiple connections simultaneously with many Bluetooth devices. We investigate the collision rate and time requirement of the inquiry and page processes. Our simulation results indicate that the total number of packets sent is O(n) and that the maximum number of packets sent by any single device is O(logn).     

Bottom-Up Construction of Bluetooth Topology under a Traffic-Aware Scheduling Scheme

We propose a Bluetooth topology construction protocol that works in conjunction with a priority-based polling scheme. A master assigns a priority to its slaves including bridges for each polling cycle and then polls them as many times as the assigned priority. The slaves can spend their idle time either in a power-saving mode or perform new node discovery. The topology construction algorithm works in a bottom-up manner in which isolated nodes join to form small piconets. These small piconets can combine to form larger piconets. Larger piconets can start sharing bridge nodes to form a scatternet. Individual piconets can also discover new nodes while participating in the master-driven polling process. The shutting down of master and slave nodes is detected for dynamic restructuring of the scatternet. The protocol can handle situations when all the Bluetooth nodes are not within radio range of each other     

Energy-aware on-demand scatternet formation and routing for Bluetooth-based wireless sensor networks

Bluetooth is a promising short-range wireless communication technology with the characteristics of interference resilience and power efficiency, both desirable for wireless sensor networks. The new Intel Mote sensor devices have Bluetooth technology incorporated as the standard wireless communications interface. When using Bluetooth in applications where multihop routing is required, groups of Bluetooth piconets combine together to form a scatternet. However, most of the existing scatternet formation protocols are designed to facilitate communications between any two pairs of devices, regardless of the actual traffic demand pattern. For wireless sensor network applications with low-duty-cycle traffic patterns, an on-demand scatternet formation protocol can achieve significant power saving by avoiding unnecessary network connectivity. To that end, we introduce an on-demand scatternet and route formation protocol designed specifically for Bluetooth-based wireless sensor networks. Our protocol builds a scatternet on demand, and is able to cope with multiple sources initiating traffic simultaneously. In addition, our energy-aware forwarding nodes selection scheme is based on local information only, and results in more uniform network resource utilization and improved network lifetime. Simulation results show that our protocol can provide scatternet formation with reasonable delay and good load balance, which results in prolonged network lifetime for Bluetooth-based wireless sensor networks.     

Interference Evaluation of Bluetooth and IEEE 802.11b Systems

The emergence of several radio technologies, such as Bluetooth and IEEE 802.11, operating in the 2.4 GHz unlicensed ISM frequency band, may lead to signal interference and result in significant performance degradation when devices are colocated in the same environment. The main goal of this paper is to evaluate the effect of mutual interference on the performance of Bluetooth and IEEE 802.11b systems. We develop a simulation framework for modeling interference based on detailed MAC and PHY models. First, we use a simple simulation scenario to highlight the effects of parameters, such as transmission power, offered load, and traffic type. We then turn to more complex scenarios involving multiple Bluetooth piconets and WLAN devices.     

Bluetooth scatternets: criteria, models and classification

Bluetooth ad hoc networks are constrained by a master/slave configuration, in which one device is the master and controls the communication with the slave devices. The master and up to seven active slave devices can form a small Bluetooth network called a piconet. In order to build larger network topologies, called scatternets, the piconets must be interconnected. Scatternets are formed by allowing certain piconet members to participate in several piconets by periodically switching between them. Due to the fact that there is no scatternet formation procedure in the Bluetooth specification, numerous different approaches have been proposed. We discuss criteria for different types of scatternets and establish general models of scatternet topologies. Then we review the state-of-the-art approaches with respect to Bluetooth scatternet formation and compare and contrast them.     

Load-adaptive inter-piconet scheduling in small-scale Bluetooth scatternets

Bluetooth enables wireless communication via ad hoc networks. The basic topology (piconet) is a collection of slaves controlled by a master. A scatternet is a multihop network of piconets. We anticipate that most scatternets will be composed of only a few piconets. However, even in small scatternets, efficient data flow requires the design of inter-piconet scheduling algorithms. Thus, this article presents and evaluates a load adaptive scheduling algorithm tailored for small-scale scatternets. The main advantage of this algorithm is the use of the Bluetooth low-power hold mode, which allows greater flexibility than other low-power modes. A simulation model has been developed in order to evaluate the performance of the algorithm. We show that the results obtained by the model are very close to the analytic results. Then we evaluate the performance of various intra-piconet scheduling algorithms. Finally, we present simulation results regarding inter-piconet scheduling, and compare the proposed algorithm to algorithms using the sniff mode.     

A Secure Protocol for Bluetooth Piconets Using Elliptic Curve Cryptography

In this article, the authors shall propose a new method for the implementation of secure Bluetooth piconets. Two requirements for the systems must be considered, i.e., privacy and authentication. Privacy ensures that an eavesdropper cannot intercept conversations between two slaves in piconets. Authentication ensures that service is not obtained fraudulently in order to avoid charge for usage. Additionally, a new key distribution scheme is designed for practical implementation in low-cost and low-power Bluetooth piconets. The proposed method employs elliptic curve cryptography for the use in the Bluetooth network. We have proper solutions to Bluetooth devices registration and Bluetooth piconets establishment. Furthermore, compared with Seo and Lee’s protocol, the proposed scheme has a lower computation cost.This research was partially supported by the National Science Council, Taiwan, R.O.C., under contract no.: NSC91-2213-E-324-003.     

A new insight into Bluetooth piconets coexistence

This paper discusses Bluetooth piconets coexistence. We use an approach which is totally different from those used traditionally with Bluetooth (probabilistic collision models). We show how it is possible to obtain an interference‐free Bluetooth environment in some conditions, for certain kinds of Bluetooth devices, using the properties of the Bluetooth frequency hopping system. Copyright © 2008 John Wiley & Sons, Ltd.     

An efficient algorithm for scheduling in bluetooth piconets and scatternets

Bluetooth is a short-range radio technology operating in the unlicensed industrial-scientific-medical (ISM) band at 2.45 GHz. A piconet is basically a collection of slaves controlled by a master. A scatternet, on the other hand, is established by linking several piconets together in an ad hoc fashion to yield a global wireless ad hoc network. This paper proposes a scheduling policy that aims to achieve increased system throughput and reduced packet delays while providing reasonably good fairness among all traffic flows in bluetooth piconets and scatternets. We propose a novel algorithm for scheduling slots to slaves for both piconets and scatternets using multi-layered parameterized policies. Our scheduling scheme works with real data and obtains an optimal feedback policy within prescribed parameterized classes of these by using an efficient two-timescale simultaneous perturbation stochastic approximation (SPSA) algorithm. We show the convergence of our algorithm to an optimal multi-layered policy. We also propose novel polling schemes for intra- and inter-piconet scheduling that are seen to perform well. We present an extensive set of simulation results and performance comparisons with existing scheduling algorithms. Our results indicate that our proposed scheduling algorithm performs better overall on a wide range of experiments over the existing algorithms for both piconets (Das et al. in INFOCOM, pp. 591–600, 2001; Lapeyrie and Turletti in INFOCOM conference proceedings, San Francisco, US, 2003; Shreedhar and Varghese in SIGCOMM, pp. 231–242, 1995) and scatternets (Har-Shai et al. in OPNETWORK, 2002; Saha and Matsumot in AICT/ICIW, 2006; Tan and Guttag in The 27th annual IEEE conference on local computer networks(LCN). Tampa, 2002). Our studies also confirm that our proposed scheme achieves a high throughput and low packet delays with reasonable fairness among all the connections.     

Impact of Interfering Bluetooth Piconets on a Collocated $p$-Persistent CSMA-Based WLAN

In this paper, the effect of cochanneled Bluetooth (BT) piconets on a carrier-sense multiple-access (CSMA)-based wireless local area network (WLAN) is investigated. Specifically, the $p$-persistent CSMA protocol is considered for WLANs, and the probability of error of a WLAN packet is calculated in the presence of interfering BT packets of different lengths and variable piconet traffic loads and as a function of the BT's frequency-hopping guard time. The probability derivation is then used in conjunction with the $p$-persistent CSMA throughput and delay formulations to examine its net performance in the presence of BT interference. Simulations have been used to corroborate the analytical results, which indicate that the presence of just one fully loaded interfering BT piconet reduces the peak CSMA throughput by 42%. Furthermore, we show that under fully loaded BT traffic conditions, the effect of more shorter BT packet transmissions on the CSMA delay performance can outweigh the interference impact of a higher number of BT piconets with longer packet transmissions.      

Mutual interference between independent Bluetooth piconets

The Bluetooth wireless communication technology provides wireless solutions applicable for a number of communications needs. In addition, multiple independent piconets are possible and likely to occur within the same location, either intentionally or by chance. Bluetooth devices utilize frequency hopping and independent piconets operate on different hopping sequences. Although the use of independently selected hopping sequences reduces the likelihood of mutual interference, as the number of colocated piconets increases, mutual interference becomes more likely. Mutual interference is also dependent on the performance requirements dictated by the application utilizing Bluetooth technology as well as the environment in which the piconet is operating. A method for analytically evaluating mutual interference for Bluetooth technology is presented. Models were developed for a single Bluetooth interferer as well as multiple interfering Bluetooth piconets operating in an arbitrary environment. The analytical models are based on two sets of parameters: Bluetooth interference and radio propagation. Empirical tests have been conducted to both support the derivation of the analytical models as well as to substantiate the analytical model results. The analytical results fall within the 95% confidence bounds of the empirical test results. Mutual interference analysis is presented based on evaluating the analytical model over a wide range of the multidimensional parameter space. The analytical model presented is a general approach well suited for evaluating mutual interference for applications using Bluetooth for data communications.