Partial delaunay triangulation and degree limited localized bluetooth scatternet formation-

This paper addresses the problem of localized scatternet formation for multi-hop Bluetooth



based

personal area ad hoc networks. Nodes are assumed to know their positions and are able to



establish

connections with any of their neighboring nodes, located within their transmission radius,



in the neighbor

discovery phase. The next phase of the proposed formation algorithm is optional, and can be



applied

to construct a sparse geometric structure in a localized manner. We propose here a new



sparse planar

structure, namely, partial Delaunay triangulation (PDT), which can be constructed locally



and is denser

than other known localized structures. In the next mandatory phase, the degree of each node



is limited to 7

by applying the Yao structure, and the master-slave relations in piconets are formed in



created subgraphs.

This phase consists of several iterations. In each iteration, undecided nodes with higher



keys than any of

their undecided neighbo