The Device Discovery in Bluetooth Scatternet Formation Algorithm

Abstract

The Bluetooth Scatternet Formation (BSF) problem can be defined as the problem of forming wireless networks of Bluetooth devices in an efficient manner. A number of restrictions imposed by the Bluetooth specifications make the BSF problem challenging and unique. Many interesting solution algorithms have been proposed in the literature to solve this problem. In this thesis, we investigate the BSF problem. We concentrate on problems introduced by the procedures of device discovery of the Bluetooth specifications and on the different solutions used by BSF algorithms to deal with these problems. We study also in this thesis problems introduced by the specifications of link establishment in Bluetooth due to their close interaction with the device discovery specifications. We survey and categorize the different device discovery techniques used by BSF algorithms. This categorization is then used as a basis to identify the different theoretical computational models used to study BSF algorithms. We argue, in this thesis, that the currently available models for Bluetooth wireless networks do not model adequately, in most cases, the complexities of the Bluetooth specifications and we show that these models were oversimplified in many cases. A general computational model will be useful as a starting point to design BSF algorithms and to compare the different and numerous BSF algorithms – especially in term of the execution time efficiency. In this thesis, we provide a set of suggestions that will help in the creation of such model. We survey a number of studies that examined in more depth the specifications of device discovery in Bluetooth. We survey also other studies that attempted to simplify the Bluetooth network model, either by suggesting modifications on the Bluetooth specifications or by the use of communication technologies other than Bluetooth. Finally, we present some experiments accompanied with analyzes to show the complexities of the Bluetooth specifications and their sensitivity to minor changes (whether in the specifications or in their implementation).