Skip to Main content Skip to Navigation
Theses

Homology theory for coverage hole detection in wireless sensor networks

Résumé : La théorie de l'homologie fournit des solutions nouvelles et efficaces pour régler le problème de trou de couverture dans les réseaux de capteurs sans fil. Ils sont basés sur deux objets combinatoires nommés complexe de Cech et complexe de Rips. Le complexe de Cech peut détecter l'intégralité des trous de couverture, mais il est très difficile à construire. Le complexe de Rips est facile à construire, mais il est imprécis dans certaines situations. Dans la première partie de cette thèse, nous choisissons la proportion de la surface de trous manqués par le complexe de Rips comme une mesure d'évaluer l'exactitude de la détection de trou de couverture basée sur l'homologie. Des expressions fermées pour les bornes inférieures et supérieures de la proportion sont dérivés. Les résultats de simulation sont bien compatibles avec les bornes inférieure et supérieure calculés analytiquement, avec des différences maximales de 0.5% et 3%. En outre, nous étendons l'analyse au cas de la sphère. Dans la deuxième partie, nous proposons d'abord un algorithme distribué basé sur les graphes pour détecter les trous non triangulaires. Cet algorithme présente une grande complexité. Nous proposons donc un autre algorithme distribué plus efficace basé sur l'homologie. Cet algorithme ne nécessite que des informations de 1- et 2-saut nœuds voisins et a la complexité O(n3) où n est le nombre maximum de nœuds voisins à 1 saut. Il peut détecter avec précision les cycles frontières d'environ 99% des trous de couverture dans environ 99% des cas.
Mots-clés : Homologie simpliciale
Complete list of metadatas

Cited literature [104 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01234691
Contributor : Abes Star :  Contact
Submitted on : Friday, November 27, 2015 - 11:52:14 AM
Last modification on : Wednesday, June 24, 2020 - 4:19:00 PM
Document(s) archivé(s) le : Sunday, February 28, 2016 - 11:41:13 AM

File

theseYanV2.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01234691, version 1

Collections

Citation

Feng Yan. Homology theory for coverage hole detection in wireless sensor networks. Networking and Internet Architecture [cs.NI]. Télécom ParisTech, 2013. English. ⟨NNT : 2013ENST0049⟩. ⟨tel-01234691⟩

Share

Metrics

Record views

198

Files downloads

172