Bluetooth scatternet scheduling with route breakage prediction

Download Full-Text PDF Cite this Publication

Text Only Version

Bluetooth scatternet scheduling with route breakage prediction



Department of Computer Science and Engineering Dr.Mahalingam College of Engineering and Technology


Assistant Professor (SS)

Department of Computer Science and Engineering Dr.Mahalingam College of Engineering and Technology


Bluetooth is a promising new technology for short range wireless connectivity between mobile devices. By constructing a piconet, Bluetooth device establishes link and communicates with other devices in a masterslave manner. The piconets are combined to form the Scatternet and communicate through the Relay /bridge node. So the performance of the Scatternet highly depends on the relays and its degree and mobility. The unnecessary relay causes scheduling overhead and inefficient use of limited resources. Thus, optimum number of relays should be maintained without any control overhead. The proposed method achieves this goal through relay reduction with load balancing and route breakage prediction. Therefore by implementing the proposed protocol the Scatternet performance will get improved due to reduced packet loss and route recovery time.

Keywords: Scatternet, Bridge/Relay node, Bridge Scheduling, Relay reduction, Load balancing, Route breakage, Signal Strength.


    The wireless technology can be classified as infrastructure and Infrastructure less (Adhoc) network. Bluetooth is an Adhoc networking technology aimed at Low-powered, short range applications. Bluetooth operates in the 2.4 GHz Industrial, Scientific, Medical (ISM) frequency band[9]. It works on the principle of frequency hop spread spectrum (FHSS). There are 79 hop carriers defined for Bluetooth, with 1 MHz spacing, in the ISM band. The basic network of Bluetooth is known as the Piconet. It contains maximum of eight nodes, one master and others are slaves. Each piconet master determines a frequency hopping spreading sequence that the slaves must follow in order to stay synchronized to the piconet channel. . The Time Division Duplex (TDD) frequency hopping (FH) channel is divided into 625µs time slots.

    A Bluetooth device identifies other devices through their Bluetooth Device Address (BD_Addr) and clock [9]. Initially, Blue- tooth device is in the standby mode and not associated to any device. The master of the piconet performs the inquiry operation to find the new devices within its range by broadcasting the ID packets. Each device enters to inquiry scan (listen to the master) mode to

    connect the master if it already exists in its range. In the second phase, the page and page scan procedure is used to get the Bluetooth address, clock and device class for synchronization. The master allocates the AM_Addr to slave; it range is from 1 to 7 [9]. As connection is then established allowing both the devices to start communication using a Time Division Duplex (TDD) mechanism.

    The Bluetooth uses the different types of packets like, control (ID, NULL, POLL, FHS), voice (HV1, HV2, HV3, DV), and data (DH1, DH3, DH5, DM1, DM3,

    DM5) packets. Bluetooth supports 1, 3 and 5 slots packets, each higher slot packet consumes more time as compared to lower slot packet. A master sends packets to slaves in an even-number of slots, while the slave responses to the master in subsequent slots (odd). If master has no data for slave it sends a POLL packet; and in response if slave also has no data to send to master, it sends a NULL packet to master. A master generally visits all its active slaves in a cycle fashion using a Round-robin scheduling technique [8].

    If many devices exist in a co-located area and exceed the limit of piconet, a larger network will be formed that has multiple piconet known as Scatternet. Bluetooth Scatternet has some special characteristics in comparison with general Adhoc networks [5]. In order to communicate between piconets there should be a bridge node that listen both piconet. This shared device is called as relay. The relay is synchronized to two piconets using the bridge scheduling algorithms [8]. The Scatternet performance highly depends on relay degree, mobility and the number of relays.

    A relay can only serve one piconet at one time; therefore other piconets communication is blocked. Once the relay has finished its service time in the current piconet, it switches to the next piconet, which causes delay and decreases network performance. This issue is known as an inter-piconet scheduling problem. There have been many protocols developed for inter-piconet communications, but only the two most significant related protocols are considered as basis for the proposed protocol. The relay reduction with disjoint route construction protocol (LORP) [4] reduces the relay without considering the traffic load. The dynamic relay management protocol

    (DRM) [2] does the relay reduction with load balancing. But DRM does not consider the node mobility, so the proposed protocol predicts the link disconnection due to mobility and the alternate path is selected before the link disconnection. The prediction is done using the signal strength measurement.


    A lot of researches have been done in Scatternet formation and inter piconet communication. The Bluetooth devices are connected through inquiry and paging procedures to form the piconet. Within a piconet the routing is controlled by the master node. The piconet combines together to form the Scatternet with one node as a bridge known as relay node. In case of inter piconet that is Scatternet scheduling the relay node plays the important role.

      1. Scatternet Formation and Bridge Scheduling

        The Bluetooth specification [9] includes the Radio layer- hooping sequences, baseband, device admission, link type and packet types etc. This paper explains clearly the fundamentals of piconet formation procedure .It also explain the communication within the piconet. But the Bluetooth specification does not define any Scatternet configuration. The proposed system adopts these concepts from this paper.

        There are different criteria for forming Scatternet and establish general models of Scatternet topologies [5].The different types of Scatternet topologies are: single piconet model, slave/slave mesh, master/slave mesh, tree hierarchy, Master/slave ring and slave/slave ring. The intra-piconet polling schemes and bridge scheduling algorithms are used for Bluetooth Scatternet [8]. The round robin polling scheme is used to poll the slave nodes and bridge scheduling algorithm uses rendezvous points to schedule the bridge device.

      2. Relay Reduction

        The relay reduction and disjoint routes construction, LORP protocol [4] present an effective protocol that can dynamically adjust the network topology by reducing the unnecessary relays. In a Scatternet, each relay r sends the Relay Information Collection (RIC) message to each of its masters. On receiving the RIC message, master mi collects information of relays belonging to piconet Pi and the connection information of neighboring masters. Once the relay r receives the information provided by the masters the relay connects to, each relay creates a Connection Table (CT). After the CT is constructed, each relay examines the CT and determines whether to change the role from a relay to a pure slave.

        Reducing the number of relays not only decreases the guard time cost for relay switching among piconets, but also reduces the probability of packet loss and improves

        the transmission efficiency. The relay nodes updte the CT in the following two situations. First, the relay nodes use the received polling messages from masters to check the link validity and update the CT. Second, the relay node updates the CT table when routes create new links. The relay reduction is done on higher degree relays, relays with same degree are not considered. The reduction is done without considering the traffic load so congestion occurs by reducing the high traffic relay. These drawbacks have been rectified in the proposed system.

      3. Signal Strength and Route Breakage Prediction

    The Route Breakage Prediction (RBP) Protocol [6] for Bluetooth network predicts the route breakage on the basis of signal strength before the link breaks .This protocol overcomes the problem of data packet loss and the problem of delay. But this protocol does not perform the Relay management on the basis of traffic load. To find the positions of the Bluetooth devices different metrics are used ,such as the RSSI (Received Signal Strength Indicator), time difference etc [7]. The Bluetooth Triangulator [1] explains an experiment combining hardware and software design to allow Bluetooth devices to communicate with each other and determine the position of other Bluetooth devices using signal strength readings. The proposed system adopts the threshold value and measuring methods from these papers.


The existing system implements the Dynamic Relay management (DRM) protocol. The DRM protocol adjusts optimally the number of relays according to the traffic load. It contains two basic procedures: First, it changes the role of unnecessary relays, including relays of the same degree, with less control overheads. Second, the DRM monitors the traffic load on each relay, and if a relay creates a bottleneck, a master shares its traffic load through the creation and activation of backup relays, i.e. a load balancing process [2].

3.4. Relay Reduction

The unnecessary relays are reduced on the basis of the relay degree and remaining battery power [2]. The relay node which is high in degree will remain as active relay and the low degree relays will change to backup relay and if same degree relay, the node with minimum battery power will designate as backup relay. The relays are selected without disconnecting the existing Scatternet. The Scatternet after the application of Relay Reduction is illustrated in Fig 2.

Fig 1: Illustration of

Scatternet [9]

    1. Scatternet Formation

      The Scatternet is formed through inquiry and paging procedures [1][2]. Initially all Bluetooth devices will be in the standby mode. The nodes enter into the inquiry and inquiry scan mode, in which some node send ID packets and others listens and replys.The node will send inquiry messages. The nodes receiving the inquiry message will send reply to node. After this the nodes will enter to paging procedure. The paging procedure is done for getting the BD-Addr. The node starts the procedure will designate as Master others as slaves. After forming piconets the Scatternet is formed by connecting the piconets through relay nodes. The relay nodes are those

      applying DRM [9]

      Fig.2: Scatternet after

      nodes which listen to more than one Master. The Fig 1 shows the Scatternet used for the DRM protocol.

    2. Relay Connection Table Construction

      After the connection establishment each relay sends its information including battery power, number of connection etc to connected masters [2]. The master constructs the relay connection table using this information. This RCT table is used to find the degree and the remaining battery power for Relay Reduction.

    3. Inter Piconet Routing

      In this, the node wants to send data will communicate to its Master .The Master will send route request packet and the route reply will come in the reverse path of the request [4]. Then the data packets are send between nodes through the discovered path using the relay nodes.

      Algorithm: Relay reduction procedure[2]

      Input: Relay Connection table Output: Defines Relay Role

      1. for each relay i in row do

      2. if subset (row i ,row i+1 ) then

      3. if degree(row i )<degree(row i+1) or (degree(row i )= degree(row i+1)) and R_power(row i )<R_power(row i+1 ) then

      4. chang_role_RCT(row i )=BR

      5. if Ri (P_Id)!=M(P_Id) then

      6. disconnect (Ri )

      7. endif

8 else

  1. chang_role_RCT(row i+1 )=BR

  2. if Ri+1 (P_Id)!=M(P_Id) then

  3. disconnect (Ri+1 )

  4. endif

  5. endif

  1. endif

  2. end for each

    1. Load Balancing



      After relay reduction if any congestion occurs then the master will go for load balancing. The threshold delay is set. If the delay is increased beyond the threshold value the backup relays are switched to active relay to share the load through role_switch operation [2]. The total link load TLL, which is the sum of incoming and outing traffic, can be calculated through the equation [3].

      1. end for each

      2. if BR!=Null then 9Connection(role_switch_req(BR),role_switch_r eqNeighbor_Master))

      10 while Transmission() 11Disconnect(role_switch_req(BR),role_switch_ req(Neighbor_Master))

      12 end if

    2. Drawbacks of Existing System

Analytically, the DRM has reduced relay-reduction overhead [9]. But this system was not addressed the relay node mobility that will cause frequent link disconnection. So in order to avoid this prediction method is proposed.



j 1

a 1 j

i 1

a 1 i


The proposed system considers the relay node mobility as

for i& j=1,2,n where n<8 (1)

Delay in a Scatternet highly depends on the relay degree (RD) and traffic load. The relay activation time depends on the bridging algorithm that is further divided into two times, synchronization time and service time. Therefore, the total link delay (TLD) can be calculated through Equation [3]:

TLD=RD*(Synchronization_Time+Service_Time) +TLL (2)

The master checks the traffic load of each relay in the piconet through the Decision Maker function (DM). The DM compares the TLD with , the threshold value .The value is fixed and it is analyzed that = 1.5 s gives optimum results [8]. If the TLD is greater than the master searches for a backup relay. The below given algorithm is used for the backup relay.

Algorithm: Dynamic load balancing[2] Input: Relay Connection table

Output: Find backup relay to share load

  1. for each relay i in row do

  2. if subset(rowi, R) and BR=Null then

  3. BR=Idi

  4. else if subset(rowi, BR) and

    RD(BR)<RD(rowi ) then

  5. BR=Idi

  6. end if

well as the link disconnection due to this. The proposed system predicts the route breakage using the signal strength measurement.

    1. Dynamic Relay Management

      The Dynamic relay management in proposed system is done through the DRM protocol. The Scatternet is formed through Inquiry and Paging procedure. After connection establishment the Relay Connection table is formed. Then by monitoring the traffic load the Master node will go for Relay reduction or load balancing.

    2. Route Breakage Prediction

The link disconnection occurs in Scatternet mainly due the relay node mobility. This will degrade the performance of the Scatternet through packet loss and delay for Route recovery. So in order to avoid this prediction approach is employed [6]. The signal strength between the relay node and the connected master node is measured. If the signal strength is reducing beyond the threshold value, then the particular relay is replced with a backup or a slave node within the rage of the master nodes through role switching operation. Thus the route recovery time will reduce and the packet loss will also get reduced due to this method.

The alternate path is selected for backup relays, if there exists backup relays to replace the weak link. If more than one backup relays exists the master will select the relay with higher degree and higher remaining battery power. If there are no backup relays, the master will perform the

role switch operation among its slaves. The slave which is within the communication range of the corresponding piconets, which is within 30m, that node is selected as the relay. So the further communication is done through the new relay. Thus the route breakage can be predicted using this method.


    The proposed system is simulated on UCBT (University of Cincinnati BlueTooth) a Bluetooth extension to NS2.This simulator implements Bluetooth in great details. The connected Scatternet with 25 Bluetooth nodes are created. Nodes are randomly deployed in an area of 100m*100m and the radio range for the Bluetooth node is taken as 30 m.The Scatternet contains five piconets. The Fig 3 shows the Scatternet formed. The Nodes are in the initial state. Then the Master is selected and then it will send request to the other nodes. If a node receives request from more than one Master then it will act as bridge between the piconets. The constant bit rate traffic model is used. To evaluate the performance the packet loss and route recovery time is considered.

    Fig 4: Relay

    Connection Table Entries


    In Adhoc networks, the link disconnection occurs due to node mobility. In Bluetooth Scatternet the relay node degree and mobility affects the Scatternet performance. The relay node mobility causes link disconnection. The existing system does relay management without considering the relay node mobility. The proposed system overcomes the drawback by predicting the route breakage. Thus the proposed system will improve the Scatternet efficiency through reducing the packet loss and route rediscovery time.



Fig 3: Scatternet

I would like to express my deep sense of gratitude with sincerity to my guide Mrs. J.Bhavithra, M.E., Assistant Professor (SS), Department of Computer Science and Engineering, who provided her valuable suggestions and precious time in accomplishing this paper. I thank all those who had contributed directly and indirectly towards the success of this project.


  1. Almaula, V. ;Cheng, D.(2006):Bluetooth triangulator.Technical report: Department of

    The Fig 4 shows the RCT entries for the Node 3, which is

    a Master node. The entries are the bridge node listening to the Master, its remaining battery power and the total number of connections for each relay node. From this we are estimating the degree of relays and this information is used in Relay Reduction. The same table is used for selecting the backup relay whenever congestion occurs. The Relay table will be modified by adding the signal strength measure of Realy nodes in order to predict the Route Breakage.

    Computer Science and Engineering, University of California, San Diego.

  2. Bakhsh, S.T.;Hasbullah,H. ; Tahir,S.(2012) :Dynamic relay management protocol for efficient inter- piconet scheduling in Bluetooth scatternet.Journal of Computer and Electrical Engineering,Vol.38,pp. 626 642.

  3. Bakhsh,S.T.;Hasbullah,H. ;Tahir,S.(2011): Dynamic Congestion Control through backup relay in Bluetooth Scatternet .Journal of Network and Computer Applications,Vol.34,pp.12521262.

  4. Jong, Y.G.; Yung, C.C.;Ping, S.K. ; Chieh, L.S. (2007): Relay reduction and disjoint routes construction for scatternet over Bluetooth radio system.J Network Comput Appl, Vol.30, pp.728 749.

  5. Persson, K.E.; Manivannan,D.; Singhal, M. (2005): Bluetooth Scatternets: criteria, models and classification. Ad Hoc Networks, Vol.3, pp.777- 794.

  6. Tahir, S. ; Said, A.M. (2012): Route Breakage Prediction Protocol for Bluetooth Network Recovery.Latest Advances in Information Science and Applications, Vol.3, pp: 242-247.

  7. Thapa, K.; Case, S. (2003): An Indoor Positioning Service for Bluetooth Ad Hoc Networks.Midwest Instruction and Computing, Duluth, MN, USA.

  8. Vojislav, B.;Misic, J. (2003):Polling and bridge scheduling algorithms in Bluetooth. Technical report TR 03/04, Manitoba, Canada R3T 2N2: Department of Computer Science, University of Manitoba Winnipeg.

  9. Whitaker, R.M.; Hodge, L.;Chlamtac, I. (2005)

:Bluetooth Scatternet formation: a survey.Ad hoc Networks, Vol.3, pp.403450.

Leave a Reply

Your email address will not be published. Required fields are marked *