Performance issues of Bluetooth scatternets and other asynchronous TDMA ad hoc networks

Loading...
Thumbnail Image

Files

TR_2002-52.pdf (213.53 KB)
No. of downloads: 793

Publication or External Link

Date

2002

Citation

DRUM DOI

Abstract

In this paper we address a practical performance issue arising inwireless ad hoc networks using time division multiple access(TDMA). This issue relates to the degradation of the networkability to allocate bandwidth when the usual assumption ofsystem-wide slot synchronicity does not hold.

The problem is investigated for the case of Bluetooth, a newpromising TDMA wireless technology that enables the formation ofad hoc networks called scatternets. A scatternet does not supporta global slot synchronization mechanism. Instead, nodes aregrouped in multiple channels called piconets and each piconet usesa different time slot reference provided by a node designated asmaster. Traffic forwarding between piconets is performed in a timedivision fashion by bridge nodes that are aware of the timereferences of the piconets they participate in. Due to theinherent lack of global synchronicity, slots are wasted whenbridges switch piconet time references. This translates to abandwidth loss compared to an ideally synchronized scatternet.While the existence of this asynchronicity overhead has beenreported in previous work, there has been no effort to minimize itor even evaluate its possible extent. Nevertheless, these issuesare very important for the deployment of practical TDMA-based adhoc networks.

We consider a scatternet that allocates bandwidth to its linksusing an asynchronous periodic conflict-free TDMA schedule. Inthis setting the asynchronicity overhead is manifested as anincrease in the minimum period required to realize a demandallocation when compared to a perfectly synchronized system.

We first derive a general upper bound on the overhead of anyscatternet and demand allocation. Then we consider the problem ofminimizing the overhead given a scatternet configuration anddemand allocation on its links. We cast this as a combinatorialoptimization problem and propose two algorithms for its solution.The first algorithm reaches the optimal solution using exhaustivesearch. However this approach can be computationally prohibitivefor large problem sizes. To this end, we introduce a secondpractical heuristic algorithm of polynomial complexity. Usingsimulations, the heuristic is shown to perform very well forproblem sizes where the optimal can be computed. For large problemsizes we use the heuristic to investigate the effect of thevarious system parameters on the generated overhead and evaluateits performance with respect to the derived general upper bound.

Notes

Rights