loading...
Connected Dominating Set and its Induced Position-less Sparse Spanner For Mobile Ad Hoc Networks
Kemer-Antalya, Turkey June 30-July 03
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISCC.2003.1214124Eighth IEEE Symposium on Computers an ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Khaled M. Alzoubi, Robert Morris College
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.


Suggestions