Simplified Bluetooth Scatternet Formation Using Maximal Independent Sets

Bluetooth standard allows the creation of piconets, with one node serving as its master and up to seven nodes serving as slaves. A Bluetooth ad hoc network can also be formed by interconnecting several piconets into a scatternet. Given a set of Bluetooth nodes which are positioned so that their unit disk graph is connected, the Bluetooth scatternet formation (BSF) problem is to select piconets, and master and slave roles in each piconet, so that the obtained scatternet is connected, has some desirable properties and good performance with respect to some metrics. In this article we propose BSF protocol based on maximal independent sets. It is a two iterations protocol. In the first iteration a piconet containing a maximal independent set is constructed for every device, while the second iteration attempts to simplify the scatternet structure and to delete piconets not essential for the connectivity. A major advantage of this novel protocol is its simplicity. Simulations show its advantage over the best competing protocol and especially for moderately dense networks.