"Distributed routing schemes for ad hoc networks using d-SPR sets"
Rieck, Michael Q.
Kim, Eun Jik
MetadataShow full item record
SubjectAd hoc wireless networks; Dominating set; Routing algorithm; Set covering problem; Shortest path routing
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 d-dominating and have a desirable ‘d-shortest path property’ which we call d-SPR sets. These algorithms produce sets that are considerably smaller than those produced by an algorithm previously introduced by the authors. Our proposed algorithms, except the greedy ones, have constant time complexity in the restricted sense that the time required is unaffected by the size of the network, assuming however that the node degrees are bounded by a constant. The performance of the new algorithms are compared, and also compared with the authors' earlier algorithm, and with an adaptation of an algorithm of Wu and Li.
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.
Manley, Eric D.; Deogun, Jitender S.; Xu, Lisong; Alexander, Dennis R. (2010-04)In this paper, we investigate the application of network coding to all-optical networks from both the algorithmic and infrastructural perspectives. We study the effectiveness of using network coding for optical-layer ...
Manley, Eric D. (ICNC, 2014-02)Network coding, a networking paradigm in which different pieces of data are coded together at various points along a transmission, has been proposed for providing a number of benefits to networks including increased ...
Manley, Eric D.; Saha, Shivashis; Deogun, Jitender S. (PDCS, 2010-11)In this paper, we consider the problem of topology design for both unprotected and one-link protected all-optical networks. We investigate the problem of selecting switching sites to minimize total cost of the network. The ...