HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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

François Ingelrest 1 David Simplot-Ryl 1 Ivan Stojmenovic 1
1 POPS - System and Networking for Portable Objects Proved to be Safe
Inria Lille - Nord Europe, LIFL - Laboratoire d'Informatique Fondamentale de Lille
Abstract : 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.
Document type :
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 6:24:38 PM
Last modification on : Wednesday, February 23, 2022 - 11:58:02 AM
Long-term archiving on: : Tuesday, February 22, 2011 - 10:45:09 AM


  • HAL Id : inria-00069876, version 1



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⟩



Record views


Files downloads