"Distributed routing algorithms for multi-hop ad hoc networks using d-hop connected d-dominating sets"
Rieck, Michael Q.
MetadataShow full item record
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.
Michael Q. Rieck is Assistant Professor of Computer Science in the Department of Math and Computer Science at Drake University.
Showing items related by title, author, creator and subject.
Dhar, Subhankar; Rieck, Michael Q.; Pai, Sukesh; Kim, Eun Jik (Elsevier Science, 2004-10)In this paper, we propose several new distributed algorithms for producing sets of nodes that can be used to form backbones of an ad hoc wireless network. Our focus is on producing small sets that are d-hop connected and ...
Rieck, Michael Q.; Dhar, Subhankar (Springer-Verlag, 2005)For a connected graph, representing a sensor network, distributed algorithms for the Set Covering Problem can be employed to construct reasonably small subsets of the nodes, called k-SPR sets. Such a set can serve as a ...
Nesheim, Skyler; Smith, Matt (2007-05-31)The goal of our research is to create an improved routing protocol for Ad-Hoc Wireless networking. We began our research by studying a protocol developed by two Drake students, Tiffany Meredith and Jennifer Ehrlich, which ...