Date Added: Jan 2010
This paper describes a distributed algorithm for producing a variety of sets of nodes that can be used to form the backbone of an ad hoc wireless network. The backbone produced is a d-hop dominating set, and in special cases is also d-hop connected and has a desirable shortest path property". D-hop dominating means that every node is within a graph distance d of some node in the set. Routing via the backbone created is also discussed. The algorithm has a constant time complexity in the sense that it is unaffected by the size of the network as long as the node degrees aren't growing. The performances of this algorithm for various parameters are compared, and also compared with other algorithms.