Weakly-connected dominating sets and sparse spanners in wireless ad hoc networks
Authors:
- 22 June 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 96-104
Abstract
A set S is dominating if each node in the graph G = (V, E) is either in S or adjacent to at least one of the nodes in S. The subgraph weakly induced by S is the graph G' = (V, E') such that each edge in E' has at least one end point in S. The set S is a weakly-connected dominating set (WCDS) of G if S is dominating and G' is connected G' is a sparse spanner if it has linear edges. In this paper, we present two distributed algorithms for finding a WCDS in O(n) time. The first algorithm has an approximation ratio of 5, and requires O(n log n) messages. The second algorithm has a larger approximation ratio, but it requires only O(n) messages. The graph G' generated by the second algorithm forms a sparse spanner with a topological dilation of 3, and a geometric dilation of 6.Keywords
This publication has 12 references indexed in Scilit:
- New distributed algorithm for connected dominating set in wireless ad hoc networks2003
- The clade vertebrata: spines and routing in ad hoc networks2002
- Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks2002
- Distributed heuristics for connected dominating sets in wireless ad hoc networksJournal of Communications and Networks, 2002
- RNG and internal node based broadcasting algorithms for wireless one-to-one networksACM SIGMOBILE Mobile Computing and Communications Review, 2001
- GPSR2000
- On calculating connected dominating set for efficient routing in ad hoc wireless networks1999
- On weakly connected domination in graphsDiscrete Mathematics, 1997
- Simple heuristics for unit disk graphsNetworks, 1995
- Unit disk graphsDiscrete Mathematics, 1990