Queueing (TDQ), Adaptive Master-Slave Switching
Ef?cient Multi-Hop Communications in Bluetooth
Scatternets
Liza Lai-Yee Shek and Yu-Kwong Kwok
Department of Electrical and Electronic Engineering
The University of Hong Kong,Pokfulam Road,Hong Kong
Abstract—This study proposes an integrated ad hoc rout-ing and time-slot scheduling(IARTSS)scheme to address the problem of ad hoc routing in Bluetooth networks.Our proposed scheme contains four main mechanisms to address the different facets of the problem,namely Compensation-Based Time-Slot Assignment(CTSA),Traf?c Differenti-ation Queueing(TDQ),Adaptive Master-Slave Switching (AMSS),and an Enhanced AODV algorithm for ad hoc rout-ing.CTSA judiciously allocates time slots to slaves based on elapsed time,utilization,and queue lengths,helping the bridge nodes to catch up with the lagging of services in pi-conets.TDQ differentiates traf?c into self-originated and forwarded messages,and serves them in a dynamically ad-justed adaptive ratio.AMSS calculates the time for a bridge node to stay in a piconet in a more effective way,based on utilization fraction and queue lengths.Enhanced AODV for ad hoc Routing is implemented as a routing protocol for Bluetooth scatternet.We have built a comprehensive Bluetooth simulator and performed extensive simulations to evaluate the proposed IARTSS.We?nd that our proposed scheme can perform well under a wide variety of practical circumstances,and provides ef?cient and high performance intra-piconet and inter-piconet communications. Keywords:Bluetooth,scatternets,ad hoc routing,time-slots scheduling.
I.I NTRODUCTION
Bluetooth[3]is an important and increasingly popu-lar wireless communication standard,and in recent years a large number of Bluetooth products have been intro-duced commercially.Its chief advantages are small and low power consumption,which make the technology an attractive choice when setting up short-range wireless ad hoc networks.A typical Bluetooth network,known as a piconet,consists of one master and seven slaves.When several Bluetooth networks interconnect through a number of bridge nodes,they form a scatternet.However,no rout-ing protocol has yet been de?ned for Bluetooth scatternets. Meanwhile,because of its small size and low cost,Blue-tooth is widely“pervasive”,in the sense that even cheap electrical appliances will be expected to become Bluetooth enabled.If so,scatternets consisting of several piconets will exist even in a home environment.Thus,there is a pressing need to develop an ef?cient ad hoc routing algo-rithm[4]to make communication possible between distant devices.
This study proposes an integrated ad hoc routing and time-slot scheduling(IARTSS)scheme to address the problem of ad hoc routing in Bluetooth networks.We have built a comprehensive Bluetooth simulator and performed extensive simulations to evaluate the proposed IARTSS. We?nd that our proposed scheme can perform well un-der a wide variety of practical circumstances,and provides ef?cient and high performance intra-piconet and inter-piconet communications.
II.O VERVIEW OF THE P ROPOSED I NTEGRATED
S CHEME
Our proposed scheme contains four main mecha-nisms to address the different facets of the prob-lem,namely Compensation-Based Time-Slot Assignment (CTSA),Traf?c Differentiation Queueing(TDQ),Adap-tive Master-Slave Switching(AMSS),and an Enhanced AODV algorithm[1]for ad hoc routing.Due to space lim-itations,it is not possible for us to describe in detail the four mechanisms.The reader is referred to the on-line full report[2]for the detailed information.We only provide highlights in the following.
Compensation-Based Time-Slot Assignment(CTSA)is a scheduling algorithm tailor-made for Bluetooth.With the formation of scatternet,some nodes have to take up the role of routers or bridges to interconnect different piconets together.As Bluetooth uses a frequency hopping scheme, a node cannot listen to two piconets simultaneously.As a result,it can only synchronize and participate in one pi-conet at a time.This implies that these bridge nodes have to multiplex their time among different piconets.How-ever,as Bluetooth adopts a centralized polling scheme for time slots allocations,these nodes have to compete for time slots with all the other nodes when they switch back to another piconet.Consequently,the resources acquired by these nodes from the piconet are fewer.In a scatter-net environment,traf?c routing across the network can be abundant.The bridge nodes play an important role in rout-
ing packets across different piconets and they become the bottlenecks of the system.Most of the existing schedul-ing algorithms allocate time slots according to the loads of the queues,and if we apply them to Bluetooth directly,we may have ignored the bridging and uplink traf?c problems. CTSA is an advanced scheduling scheme for Bluetooth.It exploits the properties of the absence of bridge nodes to calculate the time slots allocation for each nodes more ef-fectively.
Traf?c Differentiation Queueing(TDQ)is a technique to separate different traf?c to different queues in Blue-tooth’s link layer.Traf?c is differentiated as“self traf?c”and“forward traf?c”in this scheme and they are put into two different queues.Those being generated by the Blue-tooth host itself are classi?ed as“self traf?c”while those being forwarded to it are classi?ed as“forward traf?c”. The Bluetooth link layer serves these queues based on an adaptive ratio manner.This scheme helps routing pack-ets across scatternet more ef?ciently and can improve the throughput and delay in a large extent.
Adaptive Master-Slave Switching(AMSS)is a hold time calculation scheme between bridge nodes,which de-cides the duration for a node to stay in a piconet.As bridge nodes in Bluetooth network need to multiplex their time to different piconets in a scatternet,the time spent on a piconet greatly affects the overall system performances. Hence,an adaptive calculation of the hold time is re-quired.AMSS addresses this problem and uses an adaptive method based on queue lengths and utilization ratio to de-termine the hold time for a piconet.This scheme allocates time between piconets in a more effective way. Enhanced AODV for Ad Hoc Routing is a routing pro-tocol developed to facilitate ad hoc routing in Bluetooth network.AODV is used because it is one of the most rep-resentative ad hoc routing protocols and it performs well in most of the wireless network environment.In our en-hanced AODV routing protocol,we have modi?ed AODV for Bluetooth so that it becomes suitable for Bluetooth’s narrow bandwidth and small packet size features.Our modi?cations are mainly about reducing the overheads in the AODV protocol,making the modi?ed version more suitable for the Bluetooth environments.
III.S IMULATION R ESULTS
In our performance study,Bluetooth networks with a variable number of nodes are examined.The Bluetooth topology used is a Bluetooth scatternet with a maximum of three masters and two bridge nodes,and thus,restrict-ing the number of piconets to be a maximum of three in our simulation environment.We also focus on the worst case scenario—seven slaves are in each piconet.For traf-?c load,we make use of the Constant Bit Rate(CBR)traf-?c and the Exponential(EXP)traf?c source.The CBR source generates160bits regularly in20msec time in-tervals,making the data rate8kbps.The EXP source is based on Poisson arrivals and has a data rate of56kbps. We vary the traf?c load also by using different number of traf?c sources in the scatternet:light load—2CBR and2 EXP,medium load—4CBR and4EXP,and heavy load—8CBR and8EXP.To compare our IARTSS scheme with other practical approaches,we also simulate three other different schemes:round-robin(RR)time-slot scheduling with original AODV,de?cit round-robin(DRR)time-slot scheduling with original AODV with two different de?cit counter calculations[2].The results are shown in Fig-ures1to5.
IV.R EMARKS ON THE R ESULTS
We have studied the performance of IARTSS and com-pared the results with two major scheduling schemes, which are the round robin algorithm and the de?cit round robin algorithm,respectively.Results show that IARTSS can perform well in many situations and improve the per-formances in scatternet environment.These results are promising and suggest that Bluetooth,despite of its com-plication in network structure and polling scheme,can sup-port communications in a wider network.
IARTSS generally works better than the other algo-rithms.It is because with the proposed time-slot schedul-ing and routing mechanisms,the overheads involved in getting packets through different piconets are much re-duced.DRR1and DRR2generally works poorly because they tend to favor downlink traf?c and discriminate the low volume uplink traf?c.
Bluetooth technology is a new technology which just starts to emerge.There are still many rooms for further study and insightful development.Our research is just one of the beginnings,and more research problems could be addressed and studied in the future.If the proposed meth-ods are applied in the real Bluetooth networks,interfer-ence will be an important problem.It is because when many Bluetooth devices exist together,they may experi-ence a large interference.Therefore,the major limitation will be the maximum number of Bluetooth devices that can exist together.The study of interference in Bluetooth network is thus an urgent need.Also IARTSS calculates time slot assignments and hold time in simple mathematics only.More stringent calculations can actually be applied to them for more accurate approximations of the problem. In this research,we enhance the AODV for Bluetooth as the routing protocol.However,research in developing a completely novel ad hoc routing for Bluetooth may be a
E n d -t o -e n d l a t e n c y (s )
Number of hops
(a)end-to-end delay of scatternet
traf?c
D e l i v e r y r a t e (%)
Number of hops
(b)delivery rate of scatternet traf?c
T h r o u g h p u t (b p s )
Numbe r of hop s
(c)throughput of scatternet traf?c
https://www.wendangku.net/doc/d93692960.html,parison of different approaches using the DM3
packet type under
the light load conditions.
E n d -t o -e n d l a t e n c y (s )
Number of hops
(a)end-to-end delay
of scatternet traf?c
D e l i v e r y r a t e (%)
Number of hops
(b)delivery
rate of scatternet traf?c
T h r o u g h p u t (b p s )
Number of hop s
(c)throughput of scatternet traf?c
https://www.wendangku.net/doc/d93692960.html,parison of different approaches using the DM3
packet type under the medium load conditions.
E n d -t o -e n d l a t e n c y (s )
Number of hop s
(a)end-to-end delay of scatternet
traf?c
D e l i v e r y r a t e (%)
Number of hops
(b)delivery rate of
scatternet traf?c
T h r o u g h p u t (b p s )
Number of hops
(c)throughput of scatternet traf?c
https://www.wendangku.net/doc/d93692960.html,parison of different approaches using the DM3
packet type under the heavy load conditions.
E n d -t o
-e n d l a t e n c y (s )
Number of node s
(a)end-to-end delay of scatternet traf?c
D e l i v e r y r a t e (%)
Number of node s
(b)delivery rate of scatternet traf?c
T h r o u g h p u t (b p s )
Numbe r of Node s
(c)throughput of scatternet traf?c
https://www.wendangku.net/doc/d93692960.html,parison of different approaches using the DM3
packet type with various number of nodes in the scatternet.
E n d -t o -e n d l a t e n c y (s )
Number of node s
(a)end-to-end delay of scatternet traf?c
D e l i v e r y r a t e (%)
Number of node s
(b)delivery rate of
scatternet traf?c
T h r o u g h p u t (b p s )
Numbe r of Node s
(c)throughput of scatternet traf?c
https://www.wendangku.net/doc/d93692960.html,parison of different approaches using the DM5
packet type with various number of nodes in the scatternet.
predominant factor to total success in this topic area.
A CKNOWLEDGMENTS
This research was supported by the Hong Kong Research Grants Council under project number HKU 7024/00E.
R EFERENCES
[1]
E.M.Royer and C.E.Perkins,“An Implementation Study of the AODV Routing Protocol,”Proc.WCNC 2000,vol.3,pp.1003–1008,September 2000.
[2]
L.L.-Y .Shek,Ad Hoc Routing and Time-Slot Scheduling in Blue-tooth Networks ,M.Phil.Thesis,The University of Hong Kong,December 2002(http://www.eee.hku.hk/?ykwok/students/thesis-mphil-ShekLiza.pdf).[3]The Of?cial Bluetooth Web Site,https://www.wendangku.net/doc/d93692960.html,/dev/speci?cations.asp,2002.
[4]
C.K.Toh,Ad Hoc Mobile Wireless Networks:Protocols and Sys-tems ,Prentice Hall,2002.