Eighth IEEE Symposium on Computers and Communications Connected Dominating Set and its Induced Position-less Sparse Spanner For Mobile Ad Hoc Networks Kemer-Antalya, Turkey June 30-July 03 ISBN: 0-7695-1961-X
A set S is a dominating set (DS) if each node in the graph is either in S or a neighbor to at least one of the nodes in S. A connected dominating set (CDS) is a DS that induces a connected subgraph. A t-spanner of a graph G = (V,E) is a spanning subgraph G' = (V, E'), such that the shortest-hop path between any two nodes in G', is at most t times their shortest path in G. A sparse spanner (spanner with linear edges) is of fundamental importance to distributed networking operations.In this paper, we present a new algorithm for constructing and maintaining a CDS-Based sparse spanner for mobile ad hoc networks without using geographic positions. This CDS has a constant approximation factor. Consequently, the number of nodes responsible for routing is also within a constant factor of the minimum. Our distributed algorithm runs in linear time and uses linear messages. Furthermore, the spanner has a constant topological and geometric dilation.
Index Terms:
connected dominating set, sparse spanner, topological dilation, geometric dilation
Citation:
Khaled M. Alzoubi, "Connected Dominating Set and its Induced Position-less Sparse Spanner For Mobile Ad Hoc Networks," iscc, pp.209, Eighth IEEE Symposium on Computers and Communications, 2003 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||