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.     

Distributed self-healing and variable topology optimization algorithms for QoS provisioning in scatternets

Bluetooth is an enabling technology for Personal Area Networks. A scatternet is an ad hoc network created by interconnecting several Bluetooth piconets, each with at most eight devices. Each piconet uses a different radio channel constituted by a frequency hopping code. The way the devices are grouped in different piconets and the way the piconets are interconnected greatly affect the performance of the scatternet in terms of capacity, data transfer delay, and energy consumption. There is a need to develop distributed scatternet formation algorithms, which guarantee full connectivity of the devices, reconfigure the network due to mobility and failure of devices, and interconnect them such a way to create an optimal topology to achieve gainful performance. The contribution of this paper is to provide an integrated approach for scatternet formation and quality-of-service support (called SHAPER-OPT). To this aim, two main procedures are proposed. First, a new scatternet formation algorithm called self-healing algorithm producing multihop Bluetooth scatternets (SHAPER) is developed which forms tree-shaped scatternets. A procedure that produces a meshed topology applying a distributed scatternet optimization algorithm (DSOA) on the network built by SHAPER is then defined. Performance evaluation of the proposed algorithms, and of the accordingly created scatternets, is carried out by using ns2 simulation. Devices are shown to be able to join or leave the scatternet at any time, without compromising the long term connectivity. Delay for network setup and reconfiguration in dynamic environments is shown to be within acceptable bounds. DSOA is also shown to be easy to implement and to improve the overall network performance.     

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.     

Comparative Performance Evaluation of Scatternet Formation Protocols for Networks of Bluetooth Devices

This paper describes the results of the first ns2-based comparative performance evaluation among four major solutions presented in the literature for forming multi-hop networks of Bluetooth devices (scatternet formation). The four protocols considered in this paper are BlueTrees [1], BlueStars [2], BlueNet [3] and the protocol presented in [4] which proposes geometric techniques for topology reduction combined with cluster-based scatternet formation. We implemented the operations of the four protocols from device discovery to scatternet formation. By means of a thorough performance evaluation we have identified protocol parameters and Bluetooth technology features that affect the duration of the formation process and the properties of the produced scatternet. We have investigated how possible modifications of the BT technology (e.g., backoff duration, possibility for a BT inquirer to identify itself) make device discovery more efficient for scatternet formation in multi-hop networks. We have then discussed implementation concerns for each of the selected protocols. Finally, we have analyzed the protocols overhead as well as the effect of the different protocols operations on key metrics of the generated scatternets, which includes the time needed for forming a scatternet, the number of its piconets, the number of slaves per piconet, the number of roles assumed by each node and the scatternet route lengths.     

一种基于Bluetooth的路由技术

Bluetooth是一种用于短距离无线通信的新技术,该文首先描述Bluetooth通信技术中Piconet网络和Scatternet网络的特征,并针对这些特征,分析了路由方法设计的基本原则,然后提出了一种IPover Bluetooth的路由方法,重点分析了在Piconet中,Scatternet中、跨Scatternet几种情况下的路由发现和数据传递的方法,并提出Bluetooth单元的跨Scatternet漫游方法。     

Scalable and QoS-Aware Dynamic Slot Assignment and Piconet Partitioning to Enhance the Performance of Bluetooth Ad Hoc Networks

Bluetooth is a radio technology for Wireless Personal Area Networks in the 2.4 GHz ISM frequency band and allows short-range devices to be connected in the form of ad hoc networks. The Bluetooth medium access control protocol is based on a strict master/slave concept wherein any communication between slave devices has to go through the master. While this model is simple, the use of such a nonoptimal packet forwarding scheme incurs much longer delays between any two slave-devices as double the bandwidth is used by the master. In addition, if two or more devices want to communicate as a group, this can only be achieved by either multiple unicast transmissions or a piconet-wide broadcast from the master. To handle these issues efficiently, we propose a novel combination of Dynamic Slot Assignment (DSA) and piconet partitioning. With DSA, the piconet master dynamically assigns slots to slaves so as to allow them to communicate directly with each other without any intervention from the master. Our proposed communication architecture provides for enhanced Quality of Service (QoS), better admission control, and multidevice conversation, which make a multicast-like communication feasible within the piconet. To widen the scope of DSA, we propose a QoS-aware Enhanced DSA (EDSA) version where dynamic piconet partitioning and scatternet support are exploited by grouping devices into piconets as per their connection endpoints, enabling it to be employed over a scatternet. We have performed extensive simulations and observe that these schemes drastically enhance Bluetooth performance in terms of the delay and the throughput, while significantly reducing the network power consumption.     

Hop count based optimization of Bluetooth scatternets

In the past five years Bluetooth scatternets were one of the most promising wireless networking technologies for ad hoc networking. In such networks, mobility together with the fact that wireless network nodes may change their communication peers in time, generate permanently changing traffic flows. Thus, forming an optimal scatternet for a given traffic pattern may be not enough, rather a scatternet that best supports traffic flows as they vary in time is required.In this paper we study the optimization of scatternets through the reduction of communication path lengths. After demonstrating analytically that there is a strong relationship between the communication path length on one hand and throughput and power consumption on the other hand, we propose a novel heuristic algorithm suite capable of dynamically adapting the network topology to the existing traffic connections between the scatternet nodes. The periodic adaptation of the scatternet topology to the traffic connections enables the routing algorithms to identify shorter paths between communicating network nodes, thus allowing for more efficient communications. We evaluate our approach through simulations, in the presence of dynamic traffic flows and mobility.     

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).     

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.

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.     

Bluetooth scatternet formation from a time-efficiency perspective

The Bluetooth Scatternet Formation (BSF) problem consists of interconnecting piconets in order to form a multi-hop topology. While a large number of BSF algorithms have been proposed, only few address time as a key parameter, and when doing so, virtually none of the solutions were tested under realistic settings. In particular, the baseband and link layers of Bluetooth are highly specific and known to have crucial impacts on performance. In this paper, we revisit performance studies for a number of time-efficient BSF algorithms, focusing on BlueStars, BlueMesh, and BlueMIS. We also introduce a novel time-efficient BSF algorithm called BSF-UED (for BSF based on Unnecessary-Edges Deletion), which forms connected scatternets deterministically and limits the outdegree of nodes to 7 heuristically. The performance of the algorithm is evaluated through detailed simulation experiments that take into account the low-level specificities of Bluetooth. We show that BSF-UED compares favorably against BlueMesh while requiring only 1/3 of its execution time. Only BlueStars is faster than BSF-UED, but at the cost of a very large number of slaves per master (much more than 7), which makes it impractical in many scenarios.     

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.     

Bluegon: a polygon-shaped scatternet formation algorithm for Bluetooth

Bluetooth is one of the cable-replacement technologies. It uses short-range radio links to replace connecting cables. Bluetooth enables portable devices to form short-range wireless ad hoc networks. A set of Bluetooth devices sharing a common channel can form a personal area network called a piconet. Several piconets can also be interconnected to establish a scatternet. Zaruba, Basaghi and Chlamtac proposed a mechanism for forming a distributed scatternet called the Bluetree. The algorithm is based on selecting an arbitrary node serving as the Blueroot. The Blueroot initiates the construction of the Bluetree. Though the algorithm is very simple, there are some weak points. For example, being a tree limits its routing choices. There are also the problems of overloading on the Blueroot and the many master/slave bridges on any routing path. In this paper, we will improve the weaknesses of Bluetree by eliminating the bottleneck in the Blueroot and by reducing the number of bridges to half for almost any path. We call the new algorithm Bluegon since polygons (cycles) will be formed in the scatternet. Simulation results indicate the efficiencies of our algorithm. Copyright © 2006 John Wiley & Sons, Ltd.     

A Location-Aware Routing Protocol for the Bluetooth Scatternet

Bluetooth is a most promising technology for the wireless personal area networks and its specification describes how to build a piconet. Though the construction of scatternet from the piconets is left out in the specification, some of the existing solutions discuss the scatternet formation issues and routing schemes. Routing in a scatternet, that has more number of hops and relay nodes increases the difficulties of scheduling and consumes the bandwidth and power resources and thereby impacts on the performance of the entire network. In this paper, a novel routing protocol (LARP) for the Bluetooth scatternet is proposed, which reduces the hop counts between the source and the destination and reconstructs the routes dynamically using the location information of the Bluetooth devices. Besides, a hybrid location-aware routing protocol (HLARP) is proposed to construct the shortest routes among the devices with or without having the location information and degenerate the routing schemes without having any location information. Experimental results show that our protocols are efficient enough to construct the shortest routing paths and to minimize the transmission delay, bandwidth and power consumption as compared to the other protocols that we have considered. Chih-Yung Chang received the Ph.D. degree in Computer Science and Information Engineering from National Central University, Taiwan, in 1995. He joined the faculty of the Department of Computer and Information Science at Aletheia University, Taiwan, as an Assistant Professor in 1997. He was the Chair of the Department of Computer and Information Science, Aletheia University, from August 2000 to July 2002. He is currently an Associate Professor of Department of Computer Science and Information Engineering at Tamkang University, Taiwan. Dr. Chang served as an Associate Guest Editor of Journal of Internet Technology (JIT, 2004), Journal of Mobile Multimedia (JMM, 2005), and a member of Editorial Board of Tamsui Oxford Journal of Mathematical Sciences (2001--2005). He was an Area Chair of IEEE AINA'2005, Vice Chair of IEEE WisCom 2005 and EUC 2005, Track Chair (Learning Technology in Education Track) of IEEE ITRE'2005, Program Co-Chair of MNSA'2005, Workshop Co-Chair of INA'2005, MSEAT'2003, MSEAT'2004, Publication Chair of MSEAT'2005, and the Program Committee Member of USW'2005, WASN'2005, and the 11th Mobile Computing Workshop. Dr. Chang is a member of the IEEE Computer Society, Communication Society and IEICE society. His current research interests include wireless sensor networks, mobile learning, Bluetooth radio systems, Ad Hoc wireless networks, and mobile computing. Prasan Kumar Sahoo got his Master degree in Mathematics from Utkal University, India. He did his M.Tech. degree in Computer Science from Indian Institute of Technology (IIT), Kharagpur, India and received his Ph.D in Mathematics from Utkal University, India in April, 2002. He joined in the Software Research Center, National Central University, Taiwan and currently working as an Assistant Professor, in the department of Information Management, Vanung University, Taiwan, since 2003. He was the Program Committee Member of MSEAT'2004, MSEAT'2005, WASA'2006, and IEEE AHUC'2006. His research interests include the coverage problems, modeling and performance analysis of wireless sensor network and Bluetooth technology. Shih-Chieh Lee received the B.S. degree in Computer Science and Information Engineering from Tamkang University, Taiwan, in 1997. Since 2003 he has been a Ph.D. Students in Department of Computer Science and Information Engineering, Tamkang University. His research interests are wireless sensor networks, Ad Hoc wireless networks, and mobile/wireless computing.     

Ad hoc networking with Bluetooth: key metrics and distributed protocols for scatternet formation

Bluetooth is a promising technology for personal/local area wireless communications. A Bluetooth scatternet is composed of simple overlapping piconets, each with a low number of devices sharing the same radio channel. A scatternet may have different topological configurations, depending on the number of composing piconets, the role of the devices involved and the configuration of the links. This paper discusses the scatternet formation issue by analyzing topological characteristics of the scatternet formed. A matrix-based representation of the network topology is used to define metrics that are applied to evaluate the key cost parameters and the scatternet performance. Numerical examples are presented and discussed, highlighting the impact of metric selection on scatternet performance. Then, a distributed algorithm for scatternet topology optimization is introduced, that supports the formation of a “locally optimal” scatternet based on a selected metric. Numerical results obtained by adopting this distributed approach to “optimize” the network topology are shown to be close to the global optimum.     

An enhanced and energy efficient communication architecture for Bluetooth wireless PANs

Bluetooth is a radio technology for Wireless Personal Area Networking (WPAN) operating in the 2.4 GHz ISM frequency band, and allows devices to be connected into short-range ad hoc networks. The Bluetooth medium access control protocol is based on the Master/Slave paradigm wherein any communication between slave devices has to go through the Master. While this model provides for simplicity, it incurs a longer delay between any two slave devices due to far from optimal packet forwarding, the use of double the bandwidth, and also additional energy wastage at the Master. Moreover, if more than two devices want to communicate as a group, this can only be achieved by either multiple unicast transmissions or a piconet-wide broadcast, clearly resulting in inefficiency. In this paper, we propose a novel Dynamic Slot Assignment (DSA) scheme whereby the Master device dynamically assigns slots to Slaves so as to allow them to communicate directly with each other without any Master intervention. This proposed communication architecture also provides for Quality of Service (QoS) requests, admission control, and multi-device conversation by which a multicast-like communication is implemented within a piconet. Through extensive simulation, we observe that DSA drastically enhances Bluetooth performance in terms of delay and throughput, while significantly reducing power consumption at the master and the overall piconet.     

A traffic-aware scheduling for bluetooth scatternets

Bluetooth is a low cost, low power, short-range radio technology used for wireless personal area networks (PANS). Bluetooth scatternet is a set of piconets interconnected via bridge devices. Good interpiconet schedulings are necessary for bridge devices to switch among piconets they participate in. This paper proposes an interpiconet scheduling algorithm named "Traffic-Aware Scatternet Scheduling" (TASS), for bridges in Bluetooth scatternets. According to masters' traffic information, TASS can adaptively switch the bridge to high traffic load masters, and increase the usage of the bridge. In addition, TASS can reduce the number of failed "unsniffs" and the overhead of "bridge switch wastes" to further increase overall system performance. Simulation results show that TASS outperforms existing interpiconet scheduling in both network throughput and adaptability for various traffic loads.     

BlueStar: Enabling Efficient Integration Between Bluetooth WPANs and IEEE 802.11 WLANs

Bluetooth is a radio technology for Wireless Personal Area Networking (WPAN) operating in the 2.4 GHz ISM frequency band. So far, there has been little research on how Bluetooth-enabled devices can effectively and efficiently have uninterrupted access to wide area networks (WAN) such as the Internet. We introduce a novel architecture (BlueStar) whereby selected Bluetooth devices, called Bluetooth Wireless Gateways (BWGs), are also IEEE 802.11 enabled so that these BWGs could serve as egress/ingress points to/from the IEEE 802.11 wireless network. We propose mitigating interference between Bluetooth and IEEE 802.11, by employing a hybrid approach of adaptive frequency hopping (AFH) and Bluetooth carrier sense (BCS) of the channels. AFH labels channels as bad or good, and Bluetooth devices only access those channels in the good state, whereas BCS is used to avoid collision by sensing the channel prior to any transmission. By combining AFH and BCS, we drastically minimize the effect of the worst-case interference scenario wherein both a Bluetooth and an IEEE 802.11 interface are co-located in a single device. BlueStar enables Bluetooth devices, belonging to either a piconet or a scatternet, to access the WAN through the BWG without the need for any fixed Bluetooth access points, while utilizing widely deployed base of IEEE 802.11 networks. Moreover, we define the protocol stack employed by BlueStar as well as indicate how BWGs efficiently manage their capacity allocation through the different systems. We also mathematically derive an upper bound on the number BWGs needed in a Bluetooth scatternet so that uninterrupted access to all Bluetooth devices could be provided.     

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.