Distributed routing algorithms for multi-hop ad hoc networks using d-hop connected d-dominating sets

This paper describes a distributed algorithm (generalized d-CDS) for producing a variety of d-dominating sets of nodes that can be used to form the backbone of an ad hoc wireless network. In special cases (ordinary d-CDS), these sets are also d-hop connected and has a desirable “shortest path property”. Routing via the backbone created is also discussed. The algorithm has a “constant time” complexity in the limited sense that it is unaffected by expanding the size of the network as long as the maximal node degree is not allowed to increase too. The performances of this algorithm for various parameters are compared, and also compared with other algorithms.