Smaller Connected Dominating Sets in Ad Hoc and Sensor Networks based on Coverage by Two-Hop Neighbors - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

Smaller Connected Dominating Sets in Ad Hoc and Sensor Networks based on Coverage by Two-Hop Neighbors

Résumé

In this paper, we focus on the construction of an efficient dominating set in ad hoc and sensor networks. A set of nodes is said to be dominating if each node is either itself dominant or neighbor of a dominant node. This set can for example be used for broadcasting, so the smaller the set is, the more efficient it is. As a basis for our work, we use a heuristics given by Dai and Wu for constructing such a set and propose an enhanced definition to obtain smaller sets. This approach, in conjunction with the elimination of message overhead by Stojmenovic, has been shown (in recent studies) to be an excellent compromise with respect to a wide range of metrics considered. In our new definition, a node u is not dominant if there exists in its 2-hop neighborhood a connected set of nodes with higher priorities that covers u and its 1-hop neighbors. This new rule uses the exact same level of information required by the original heuristics, only neighbors of nodes and neighbors of neighbors must be known to apply it, but it takes advantage of some knowledge originally not taken into account: 1-hop neighbors can be covered by some 2-hop neighbors. We give the proof that the set obtained with this new definition is a subset of the one obtained with Dai and Wu's heuristics. We also give the proof that our set is always dominating for any graph, and connected for any connected graph. Two versions were considered: with topological and positional information, which differ in whether or not nodes are aware of links between their 2-hop neighbors that are not 1-hop neighbors. An algorithm for applying the concept at each node is described. We finally provide experimental data that demonstrates the superiority of our rule in obtaining smaller dominating sets. A centralized algorithm was used as a benchmark in the comparison. The overhead of the size of connected dominating set was reduced by about 15% with the topological variant and by about 30% with the positional variant of our new definition.
Fichier principal
Vignette du fichier
RT-0304.pdf (206.49 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00069876 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00069876 , version 1

Citer

François Ingelrest, David Simplot-Ryl, Ivan Stojmenovic. Smaller Connected Dominating Sets in Ad Hoc and Sensor Networks based on Coverage by Two-Hop Neighbors. [Research Report] RT-0304, INRIA. 2005, pp.12. ⟨inria-00069876⟩
86 Consultations
218 Téléchargements

Partager

Gmail Facebook X LinkedIn More