Bluetooth scatternet formation protocol for wireless devices based on 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. Given a set of Bluetooth nodes that are positioned so that their unit disk graph is connected, the Bluetooth scatternet formation (BSF) problem is to select piconets, and the master and slave roles within each piconet, so that the obtained scatternet is connected, has some desirable properties, and shows good performance with respect to certain metrics. In this thesis, we propose a new Bluetooth scatternet formation protocol called BlueMis that is based on maximal independent set and guarantees connectivity and degree limitation. Three variations of the protocol are introduced with the basic idea of selecting slaves as the maximal independent set of each Bluetooth device. First, BlueMis as a simple unique iteration protocol is introduced, and then two iteration protocols called BlueMis1 and BlueMis2 are proposed. In the first iteration of BlueMis1 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 to the connectivity. A major advantage of this novel protocol is its simplicity. We implemented our proposed protocol and compared it to the well known protocol BlueMesh with respect to certain relevant metrics. Simulations show its advantage over the best competing protocol, especially for moderately dense networks