Skip to Main content Skip to Navigation
Reports

Dominating sets-based Self* Minimum Connected Covers of Query Regions in Sensor Networks

Ajoy Datta 1 Maria Gradinariu 2 Rajesh Patel 1
2 ADEPT - Algorithms for Dynamic Dependable Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : Sensor networks are mainly used to gather strategic information in various monitored area. Sensors may be deployed in zones where their internal memory or the sensors themselves can be corrupted. Moreover, once deployed sensors cannot be easily replaced, therefore the persistence and the robustness of the network are two main issues that have to be addressed while efficiently deploying large scale sensor networks. Minimum*** Connected Covers of a query region in sensor networks aims at selecting a subset of nodes that entirely covers the monitored area, is strongly connected (i.e. between any two sensors in the selected set there is a communication path) and the final set does not contain a subset with the same properties. Interestingly, the connected query region cover cannot be solved by trivially applying algorithms that compute minimum connected dominating sets designed for adhoc or sensor networks, since these algorithms aim at selecting a connected cover of existing nodes in the network irrespectively of the relationship between their sensing region and the monitored zone. Nevertheless, these algorithms define an efficient connected tilling of the monitored zone that can be further completed to a fully cover. In this paper we propose two novel, fully localized, robust solutions to the minimum connected cover of query regions that can cope with both transient faults (corruptions of the internal memory of sensors) and sensors crash/join. Our algorithms use only 2 bits of memory and follow two different strategies: a greedy strategy (sensors are chosen such that the overlap with sensors already chosen is minimal) and pruning-based approach (sensors are removed from the cover set till the final set of nodes contains only non redundant sensors). We prove the self* (self-configuration, self-stabilization and self-healing) properties of our solutions. Via extended simulations we conclude that our solutions provide better performances in terms of coverage than pre-existing self-stabilizing solutions. Moreover, we observe that the greedy approach performs better than the pruning strategy. \\ Nous proposons deux infrastructures efficaces pour la couverture d'une zone de surveillance dans les réseaux de capteurs. La construction des infrastructures proposées utilise comme stratégie de construction les ensembles dominants. Les algorithmes proposés sont tolérant aux fautes transitoires ainsi qu'à l'insertion et au départ des noeuds.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/inria-00069842
Contributor : Anne Jaigu <>
Submitted on : Friday, May 19, 2006 - 4:35:00 PM
Last modification on : Thursday, February 11, 2021 - 2:48:03 PM
Long-term archiving on: : Saturday, April 3, 2010 - 10:35:16 PM

Identifiers

  • HAL Id : inria-00069842, version 1

Citation

Ajoy Datta, Maria Gradinariu, Rajesh Patel. Dominating sets-based Self* Minimum Connected Covers of Query Regions in Sensor Networks. [Research Report] PI 1803, 2006, pp.22. ⟨inria-00069842⟩

Share

Metrics

Record views

540

Files downloads

144