SHAPER: a self-healing algorithm producing multi-hop Bluetooth scatternets

This paper deals with scatternet formation in Bluetooth. A scatternet is an ad hoc network of Bluetooth devices. Some works in the literature rely on the single-hop hypothesis, i.e., all devices are in radio visibility of each other. Other works refer to the more likely circumstance that devices are scattered in an area where some of them can not directly communicate. A challenging issue in this latter scenario (often referred to as multi-hop) is the design of a formation algorithm that: i) operates in a distributed way; ii) dynamically adapts the topology to the mobility of devices; iii) forms a scatternet with given topological properties. In this paper a distributed algorithm for scatternet formation that gives rise to a tree-like structure is introduced. The algorithm is shown to present three key properties that make it innovative with respect to the literature in the field: i) it is fully distributed and asynchronous; ii) it can be applied in a multi-hop environment; iii) it operates in order to dynamically adapt the topology to nodes´ mobility and failures. The key steps and rules of the algorithm are described and performance results obtained by simulation are discussed.