"Distributed routing schemes for ad hoc networks using d-SPR sets"
Loading...
Authors
Dhar, Subhankar
Rieck, Michael Q.
Pai, Sukesh
Kim, Eun Jik
Issue Date
2004-10
Type
Article
Language
en_US
Keywords
Ad hoc wireless networks , Dominating set , Routing algorithm , Set covering problem , Shortest path routing
Alternative Title
Abstract
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.
Description
Michael Q. Rieck is an associate professor at Drake University in Des Moines, Iowa, USA. He holds a Ph. D. in mathematics from the University of South Florida. His primary research interests are in the areas of camera tracking and ad hoc wireless networks. He has also published results in the areas of triangle geometry, discrete mathematics, linear algebra, finite fields and association schemes.
Citation
MICROPROCESSORS AND MICROSYSTEMS, 2004. 28 (8): 427-437.
Publisher
Elsevier Science
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
0141-9331