| Abstract |
|
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.
|
 Additional Information
|
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,
p. 209,
Eighth IEEE Symposium on Computers and Communications,
2003
|
