Affordable Access

Publisher Website

Distributed routing schemes for ad hoc networks usingd-SPR sets

Authors
Journal
Microprocessors and Microsystems
0141-9331
Publisher
Elsevier
Publication Date
Volume
28
Issue
8
Identifiers
DOI: 10.1016/j.micpro.2004.03.016
Keywords
  • Dominating Set
  • Ad Hoc Wireless Networks
  • Routing Algorithm
  • Set Covering Problem
  • Shortest Path Routing
Disciplines
  • Computer Science

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.