A self-routing topology for Bluetooth scatternets

The emerging Bluetooth standard is considered to be the most promising technology to construct ad-hoc networks. It contains specifications of how to build a piconet but left out details of how to automatically construct a scatternet from the piconets. Existing solutions only discussed the scatternet formation issue without considering the ease of routing in such a scatternet. We present algorithms to embed b-trees into a scatternet which enables such a network to become self-routing. It requires only a fixed-size message header and no routing table at each node regardless of the size of the scatternet. These properties make our solution scalable to deal with networks of large sizes. Our solutions are of distributed control and asynchronous. We prove that our algorithm preserves the b-tree property when devices join or leave the scatternet and when one scatternet is merged with another