Title: Multi-hop scatternet formation and routing for large scale Bluetooth networks

Authors: Wen-Zhan Song, Yu Wang, Chao Ren, Changhua Wu, Xiang-Yang Li

Addresses: School of Engineering and Computer Science, Washington State University, Vancouver, WA 98686, USA. ' Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA. ' School of Computer Science, Northwestern Polytechnical University, Xi'an, ShanXi 710072, China. ' Department of Computer Science, Kettering University, Flint, MI 48504, USA. ' Department of Computer Science, Illinois Institute of Technology, Chicago, IL 60616, USA

Abstract: This paper addresses the scatternet formation for large scale multi-hop Bluetooth networks. We first describe an efficient method to build a Connected Dominating Set (CDS) as the backbone of multi-hop Bluetooth network, then propose new algorithms to form the dBBlue scatternets (Song et al., 2005) in each cluster. The final scatternet, M-dBBlue, guarantees the connectivity. Our experiment shows our scatternet seldom parks any node. We then propose a complete set of hierarchical routing methods for M-dBBlue which enables the self-routing inside each cluster. Moreover, our scatternet formation and routing algorithm do not necessarily require position information of the node.

Keywords: Bluetooth networks; connected dominating set; dBBlue; multi-hop scatternet formation; connectivity guarantees; hierarchical routing; self-routing.

DOI: 10.1504/IJAHUC.2009.027476

International Journal of Ad Hoc and Ubiquitous Computing, 2009 Vol.4 No.5, pp.251 - 268

Published online: 26 Jul 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article