Professor Philippe Godlewski

Professor Xavier Lagrange

Professor Martin Haenggi

Professor Brian Mark

Marc Lelarge Special

Dr Eduardo Ferraz

Dr Anaïs Vergne

Dr Ian Flint

Amine Benmosbah

Dr Tian Ban

Dr Zizhu Wang

tins. Before meeting him, I had never dreamed of pursuing my Ph.D. degree in France. It was Professor Philippe Martins who gave me such an opportunity. During the past four years, he gave me not only much invaluable guidance in

List of Figures

Motivations

Les récents progrès des communications sans fil et des micro-systèmes électro-mécaniques ont permis le développement des réseaux de capteurs [START_REF] Akyildiz | A survey on sensor networks[END_REF]. Un réseau de capteurs se compose d'un ensemble de noeuds disposant de capacités de calcul et de transmission réduites. Chacun capteur possède néanmoins des fonctionnalités de mesure et de communication avec des noeuds voisins. Ces capteurs sont déployés dans un domaine à superviser. Plusieurs types de mesures peuvent être effectuées : température, luminosité, intensité sonore, pression . . . . Les réseaux de capteurs ont beaucoup d'applications, qui peuvent être généralement classés en deux catégories: la supervision et la surveillance [START_REF] Yick | Wireless sensor network survey[END_REF]. Les applications de surveillance concernent essentiellement les personnes, les animaux et les véhicules [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF][START_REF] Oh | Instrumenting wireless sensor networks for real-time surveillance[END_REF][START_REF] Mikkel Baun Kjaergaard | Entracked: energy-efficient robust position tracking for mobile devices[END_REF][START_REF] Mikkel Baun Kjaergaard | Energy-efficient trajectory tracking for mobile devices[END_REF]. Les applications de supervision sont liées à la l'habitat, l'environnement. [START_REF] Juang | Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet[END_REF][START_REF] Mainwaring | Wireless sensor networks for habitat monitoring[END_REF][START_REF] Szewczyk | Habitat monitoring with sensor networks[END_REF][START_REF] Tolle | A macroscope in the redwoods[END_REF][START_REF] Werner-Allen | Deploying a wireless sensor net-work on an active volcano[END_REF][START_REF] Mo | Canopy closure estimates with greenorbs: sustainable sensing in the forest[END_REF][START_REF] Song | Design and deployment of sensor network for real-time high-fidelity volcano monitoring[END_REF][START_REF] Mao | Citysee: Urban CO 2 monitoring with sensors[END_REF], l'eSanté [START_REF] Xu | A wireless sensor network for structural monitoring[END_REF][START_REF] Chintalapudi | Monitoring civil structures with a wireless sensor network[END_REF][START_REF] Kim | Health monitoring of civil infrastructures using wireless sensor networks[END_REF][START_REF] Chebrolu | Brimon: a sensor network system for railway bridge monitoring[END_REF][START_REF] Stajano | Smart bridges, smart tunnels: Transforming wireless sensor networks from research prototypes into robust engineering infrastructure[END_REF], la télé-médecine [START_REF] Efstratiou | Experiences of designing and deploying intelligent sensor nodes to monitor hand-arm vibrations in the field[END_REF][START_REF] Baker | Wireless sensor networks for home health care[END_REF][START_REF] Lorincz | Mercury: a wearable sensor network platform for high-fidelity motion analysis[END_REF][START_REF] Shih | Sensor selection for energyefficient ambulatory medical monitoring[END_REF] et le contrôle de trafic [START_REF] Yoon | Surface street traffic estimation[END_REF][START_REF] Li | Performance evaluation of vehicle-based mobile sensor networks for traffic monitoring[END_REF][START_REF] Tubaishat | Wireless sensor networks in intelligent transportation systems[END_REF][START_REF] Semertzidis | Video sensor network for real-time traffic monitoring and surveillance[END_REF][START_REF] Pascale | Wireless sensor networks for traffic management and road safety[END_REF][START_REF] Bottero | Wireless sensor networks for traffic monitoring in a logistic centre[END_REF].

La couverture est un problème fondamental dans les réseaux de capteurs. Elle peut être considérée comme une mesure de la qualité de service d'un réseau de capteurs [START_REF] Meguerdichian | Coverage problems in wireless ad-hoc sensor networks[END_REF]. Basé sur les objectifs de couverture, les auteurs de [START_REF] Cardei | Coverage in Wireless Sensor Networks in Handbook of Sensor Networks[END_REF] ont classé la couverture en trois catégories: la couverture d'une zone géographique, la couverture d'un point spécifique et la couverture d'obstacle. Pour qui concerne le problème de la couverture de zone, l'objectif principal du réseau de capteurs est de couvrir l'intégralité des points de la zone. Dans le problème de couverture du point, l'objectif est de couvrir un ensemble de points spécifiques. Le but de la couverture d'obstacle est de minimiser la probabilité de pénétration non détectée à travers la barrière formée par des capteurs sans fil. Dans cette thèse, nous nous concentrons sur le problème de couverture de la zone.

Dans les applications liées à la couverture de zone, le domaine ciblé doit être être entièrement couvert. Cependant, les trous de couverture peuvent se former pour de nombreuses raisons, telles que le déploiement aléatoire des capteurs, l'épuisement de l'énergie de capteurs ou la destruction de capteurs. Par exemple, dans les applications de surveillance de volcan, le domaine ciblé est généralement hostile ou inaccessible pour les humains. Dans de telles situations, les capteurs doivent être déployées de façon aléatoire par des hélicoptères ou d'autres types de véhicules. Avec le déploiement aléatoire, noeuds de capteurs peuvent se regrouper à un endroit et laisser des trous de couverture à d'autres. En outre, même si dans le déploiement initial, le domaine ciblé est entièrement couvert par des noeuds de capteurs, des trous de couverture peuvent apparaître avec le temps: extinction, pannes, et destruction physique de capteurs. Par conséquent, il est d'une importance primordiale de disposer de mécanismes permettant de détecter et de localiser les trous de couverture. Certains noeuds mobiles peuvent alors être déployés pour rétablir la couverture [START_REF] Wang | Movement-assisted sensor deployment[END_REF][START_REF] Wang | Sensor relocation in mobile sensor networks[END_REF]. Par ailleurs, la connaissance des frontières des trous de couverture est également très utile dans la conception de fonctionnalités des réseaux, telles que le routage point à point et les mécanismes de collecte de données [START_REF] Wang | Boundary recognition in sensor networks by topological methods[END_REF].

De nombreuses approches ont été proposées pour la détection de trou de couverture dans les réseaux de capteurs sans fil. Elles peuvent généralement être classés en trois catégories: (i) les approches basées sur la localisation, (ii) les approches basées sur la distance, et (iii) les approches basées sur la connectivité. Les approches basées sur la localisation et la distance peuvent découvrir tous les trous de couverture avec une bonne précision mais nécessitent soit des informations de localisation précises soit des informations de distance précise, ce qui est difficile à obtenir dans de nombreux scénarios. Les approches basées sur la connectivité ont donc reçu une attention considérable ces dernières années. En particulier, les approches basées sur l'homologie ont attiré notre attention. Ghrist et ses collaborateurs ont introduit deux outils combinatoires : le complexe de Čech et le complexe de Rips-Vietoris (qu'on désignera par le terme complexe de Rips dans la suite de ce document). Ces deux objets sont utilisés pour détecter les trous de couverture [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF]. Une solution centralisée pour certains scénarios simples a été proposée par ses deux auteurs. Néanmoins, la conception d'un algorithme distribué efficace pour la détection de trous de couvertures, en se basant uniquement sur des informations de connectivité, demeure une question ouverte.

Conscients des limites du travail existant pour la détection de trous de couverture dans les réseaux de capteurs sans fil, nos travaux analysent plus en détail l'utilité de la théorie d'homologie. Nos travaux ont permis d'élaborer de nouveaux algorithmes distribués plus adaptés au problème de la detection des trous de couverture dans un réseau de capteurs sans fil.

Contributions

Nos contributions sont de deux ordres: (1) la précision de la détection de trous de couverture basée sur l'homologie et [START_REF] Yick | Wireless sensor network survey[END_REF] des algorithmes distribués pour la détection de trous de couverture. 0.1.2.1 La précision de la détection de trous de couverture basée sur l'homologie

Le complexe de Čech détecte l'intégralité des trous de couverture, mais il est difficile à construire. Le complexe de Rips est facile à construire, mais est imprécis dans certaines situations. Nous avons d'abord analysé la relation entre le complexe de Čech et le complexe de Rips en termes de trous de couverture pour les réseaux de capteurs sans fil sur un domaine ciblé plan. Nous choisissons la proportion de la surface de trous manqués par le complexe de Rips comme une mesure d'exactitude de la détection de trous de couverture basée sur l'homologie. Nous avons montré que cette proportion est liée au ratio entre les rayons de communication et de détection de chaque capteur (noté respectivement par R c et R s ). Nous avons ensuite analysé cette proportion dans trois cas et pour chaque cas, des expressions fermées pour les bornes inférieure et supérieure ont été dérivés. Les résultats de simulation sont 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 avons étendu l'analyse au cas de la sphère. Les résultats de simulation montrent que le rayon de la sphère a peu d'impact sur la proportion quand il est beaucoup plus grand que les rayons de communication et de détection de chaque capteur.

Algorithmes distribués pour la détection de trou de couverture

Nous avons proposé un algorithme distribué basé sur les graphes pour détecter les trous de couverture. L'algorithme se compose de quatre étapes: découverte des voisins, découverte des noeuds frontières, découverte des cycles frontières, sélection des cycles. Dans l'étape de la découverte des voisins, chaque noeud obtient des informations de tous ses 1-et 2-saut voisins. Dans l'étape de la découverte des noeuds frontières, chaque noeud détermine s'il s'agit d'un noeud frontière ou non en vérifiant l'existence d'un cycle Hamiltonien dans son graphe de voisinage. S'il existe, il est considéré comme un noeud non frontière. Dans le cas contraire, il est supposé être un noeud frontière. Après cela, certains noeuds frontières sont choisis au hasard pour lancer le processus de découverte des cycles frontières et de nombreux cycles seront trouvés. Mais ces cycles trouvés peuvent ne pas être minimum ou certains d'entre eux être liés aux mêmes trous de couverture. Donc, il est nécessaire de faire des choix parmi ces cycles, ce qui se fait dans l'étape finale.

L'algorithme proposé ci-dessus présente une grande complexité. Nous avons donc conçu un algorithme plus efficace basé sur l'homologie. L'idée de base de cet algorithme est la suivante: pour le complexe de Rips d'un réseau de capteurs, nous essayons de supprimer des sommets et des arêtes sans changer l'homologie tout en rendant le complexe de Rips moins dense. Ensuite, il devient plus facile de trouver des cycles frontières. La nouveauté de cet algorithme réside dans le critère de suppression d'un sommet ou d'une arête. A chaque tentative de suppression, l'algorithme vérifie si l'homologie change. Cet algorithme a la complexité O(n 3 ) où n est le nombre maximum de noeuds voisins à 1 saut et n est fini. Il est distribué et ne nécessite que des informations de 1-et 2-saut noeuds voisins. Il peut détecter avec précision les cycles frontières d'environ 99% des trous de couverture dans environ 99% des cas.

Contexte mathématique

La théorie de l'homologie fournit des solutions nouvelles et puissantes pour les problèmes d'identification des trous de couverture dans les réseaux de capteurs sans fil. Le principe de la théorie de l'homologie consiste à analyser les propriétés topologiques de certains domaines par des calculs algébriques. Les principaux objets sont connus comme des complexes simpliciaux, qui sont la généralisation du graphe. Le groupe d'homologie est un invariant topologique qui peut faire la distinction entre les espaces topologiques en mesurant le nombre de trous dans cet espace. Ces concepts étant relativement moins connus, il est donc nécessaire d'introduire un certain nombre de concepts fondamentaux. Pour une présentation détaillée, le lecteur pourra se reporter à [START_REF] Anthony | Basic Topology[END_REF][START_REF] Munkres | Elements of algebraic topology[END_REF][START_REF] Hatcher | Algebraic Topology[END_REF].

Définitions

Etant donné un ensemble de sommets V , un k-simplexe σ est un ensemble nonordonné {v 0 , v 1 , ..., v k } ⊆ V où v i = v j pour tout i = j, k est la dimension du simplexe. Un 0-simplexe est un sommet, un 1-simplexe est une arête, un 2-simplexe est un triangle avec son intérieur inclus et un 3-simplexe est un tétraèdre avec son intérieur inclus, voir la Figure 1. Tout sous-ensemble de {v 0 , v 1 , ..., v k } est appelé une face de σ. Un complexe simplicial X est un ensemble de simplexes qui satisfait à deux conditions: (1) toute la face d'un simplexe de X est aussi dans X, (2) l'intersection de deux simplexes σ 1 et σ 2 est une face de σ 1 et sigma 2 . Un complexe simplicial abstrait est la description purement combinatoire de la notion géométrique d'un complexe simplicial et n'a donc pas besoin de la seconde condition. La dimension d'un complexe simplicial X est la plus grande dimension de tout simplexe dans X. Un sous-complexe de X est un complexe simplicial X (k) ⊂ X, où k indique la dimension de X (k) . Par exemple, dans le complexe simplicial représenté sur la Figure 2, il contient six 0-simplexes {1}, {2}, . . . , {6}, huit 1-simplexes {1, 2}, {1, 6}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {4, 5}, {5, 6} et un 2-simplexe {1, 2, 6}.

v 0 v 0 v 1 v 0 v 1 v 2 0-simplex 2-simplex 1-simplex v 0 v 1 v 2 v 3 3-simplex
[v 0 , • • • , v i , • • • , v j , • • • , v k ] = -[v 0 , • • • , v j , • • • , v i , • • • , v k ]
Ensuite, on peut définir le groupe des chaînes, la différentielle de carré nul, le groupe des cycles et le groupe des bords. Definition 0.1. Pour un complexe simplicial abstrait X, pour chaque entier k > 0, le k-ième groupe des chaînes C k (X) est l'espace vectoriel formé par l'ensemble des k-simplexes orientés de X. Si k est plus grand que la dimension de X, C k (X) est 0. Definition 0.2. La différentielle de carré nul ∂ k est la transformation linéaire ∂ k : C k (X) → C (k-1) (X) qui agit sur les éléments de base de C k (X) via

∂ k [v 0 , • • • , v k ] = k i=0 (-1) i [v 0 , • • • , v i-1 , v i+1 , • • • , v k ]
où la somme est la somme algébrique.

Prenons l'exemple de la Figure 2, en tenant compte de l'orientation, nous supposons qu'il contient six 0-simplexes [START_REF] Akyildiz | A survey on sensor networks[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF], . . . , [START_REF] Simon | Sensor networkbased countersniper system[END_REF], huit 1-simplexes [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF], [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Li | Detection, classification, and tracking of targets[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF], [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF], [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF], [START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF], [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] et un 2-simplexe [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF]. Selon la définition 0.2, on peut voir que le bord du 2-simplexe [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] est la somme de trois 1-simplexes [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] et [START_REF] Simon | Sensor networkbased countersniper system[END_REF][START_REF] Akyildiz | A survey on sensor networks[END_REF], comme illustré sur la Figure 3(a). Mais le bord de la somme de trois 1-simplexes [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF], [START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF] et [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Li | Detection, classification, and tracking of targets[END_REF] est 0, sur la Figure 3(b). Definition 0.3. Le k-ième group des cycles de X est Z k (X) = ker ∂ k .

Definition 0.4. Le k-ième group des bords de X est B k (X) = im∂ k+1 .

Un calcul simple montre que ∂ k • ∂ k+1 = 0. Il s'ensuit que B k (X) ⊂ Z k (X). Les relations de C k (X), Z k (X), B k (X) sont montrées dans la Figure 4.

Ensuite, on peut bien définir le groupe d'homologie et sa dimension.

Definition 0.5. Le k-ième groupe d'homologie de X est l'espace vectoriel quotient

H k (X) = Z k (X) B k (X)
Definition 0.6. Le k-ième nombre de Betti de X est la dimension de H k (X):

β k = dim H k (X) = dim Z k (X) -dim B k (X).
∂ k+1 ∂ k C k+1 (X) C k (X) C k-1 (X) B k (X)
Z k (X)

Figure 4: Un exemple montrant les relations de C k (X), Z k (X), B k (X)

Les nombres de Betti sont utilisés pour compter le nombre de trous de différentes dimensions dans X. Par exemple, β 0 indique le nombre de trous de dimension 1, qui est le nombre de composantes connexes. Et β 1 compte le nombre de trous dans le plan.

On prend l'exemple dans la Figure 2, les différentielles associées à X sont faciles à obtenir sous forme matricielle:

∂ 1 =               [1, 2] [1, 6] [2, 3] [2, 6] [3, 4] [3, 5] [4, 5] [5, 6] [1] -1 -1 0 0 0 0 0 0 [2] 1 0 -1 -1 0 0 0 0 [3] 0 0 1 0 -1 -1 0 0 [4] 0 0 0 0 1 0 -1 0 [5] 0 0 0 0 0 1 1 -1 [6] 0 1 0 1 0 0 0 1      [1, 2, 6] [1, 2]
1 [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] -1

[2, 3] 0 [2, 6]
1 [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF] 0 [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF] 0 [START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF] 0 [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] 0

                   
Ensuite on peut obtenir β 0 = dim ker ∂ 0dim im∂ 1 = 6 -5 = 1

β 1 = dim ker ∂ 1 -dim im∂ 2 = 3 -1 = 2 0.2.

Complexes simpliciaux abstraits pour les réseaux

Pour le problème de la couverture dans les réseaux de capteurs sans fil, les deux complexes simpliciaux abstraits plus utiles sont le complexe de Čech et le complexe de Rips.

Le complexe de Čech est défini comme suit [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF].

Definition 0.7 (Complexe de Čech). Etant donné une collection d'ensembles U, le complexe de Čech de U, Č(U), est le complexe simplicial abstrait dont les k-simplexes correspondent aux intersections non-vides de k + 1 éléments distincts de U.

Le complexe de Čech capture la topologie de la collection d'ensembles, comme illustré par le théorème suivant. Theorem 0.1 (Théorème de Čech). Le complex de Čech complex d'une collection d'ensembles convexes a le type d'homotopie de l'union des ensembles.

Malheureusement, le complexe de Čech est très difficile à construire. Donc, un autre complexe plus facilement calculable nommé le complexe de Rips est introduit. Il est défini comme suit. Definition 0.8 (Complexe de Rips). Soient (M, d) un espace métrique, V un ensemble fini de points dans M et ǫ un réel positif, le complexe de Rips de V, R ǫ (V), est le complexe simplicial abstrait dont les k-simplexes sont les (k + 1)-tuples de points de V qui sont de distance inférieure à ǫ deux à deux.

Le complexe de Rips peut être construit avec la seule connaissance du graphe de connectivité du réseau et donne une approximation de la couverture par des calculs algébriques simples. Mais le complexe de Rips peut manquer des trous de couverture. En fait, il existe les relations suivantes entre le complexe de Čech et le complexe de Rips [START_REF] Vin De Silva | Blind swarms for coverage in 2-d[END_REF].

Theorem 0.2. Soit V un ensemble fini de points dans R d et Čǫ (V) le complexe de Čech de la couverture de V par des boules de rayon ǫ. Ensuit, il y a

R ǫ ′ (V) ⊂ Čǫ (V) ⊂ R 2ǫ (V) whenever ǫ ǫ ′ ≥ d 2(d + 1)
0.3 Précision de la détection de trou de couverture basée sur l'homologie dans le plan

Introduction

Le complexe de Čech et le complexe de Rips sont deux outils utiles pour la détection de trous de couverture. Le complexe de Čech est assez difficile à construire et le complexe de Rips est facile à construire. Les approches basées sur l'homologie utilisent généralement le complexe de Rips pour détecter les trous de couverture. Néanmoins, le complexe de Rips peut manquer quelques trous de couverture dans certaines situations. Dans ce qui suit, nous choisissons la proportion de la surface de trous manqués par le complexe de Rips comme une mesure de précision de la détection de trous de couverture basée sur l'homologie pour les réseaux de capteurs sans fil dans le plan.

Nous avons d'abord analysé la relation entre le complexe de Čech et le complexe de Rips en termes de trous de couverture. Nous trouvons que leur relation est liée au ratio entre les rayons de la communication et de détection. Les trous manqués par le complexe de Rips doivent être délimités par un triangle. Nous définissons ainsi le concept de trous triangulaires et de trous non-triangulaire.

Par la suite, nous obtenons des formes fermées pour les bornes inférieures et supérieures de la proportion de la surface de trous triangulaires.

Enfin, des simulations ont été menées et elles ont montré que les résultats de simulation sont bien compatibles avec les bornes analytiques inférieure et supérieure, avec des différences maximales de 0.5% et 3%.

Modèles et définitions

On considère un ensemble de capteurs fixes (appelé aussi noeuds) déployé sur un domaine ciblé plan modélisé par un processus de Poisson d'intensité λ. La propagation radio est supposé isotrope. Chaque capteur contrôle une région à l'intérieur d'un cercle de rayon R S et peut communiquer avec d'autres capteurs dans un cercle de rayon R c . Soit V l'ensemble de emplacements de capteurs dans un réseau de capteurs sans fil et S = {s v , v ∈ V} l'ensemble des disques de détection de ces capteurs: pour un emplacement v, s v = {x ∈ R 2 : xv ≤ R s }. Ensuite, selon la définition 0.7, le complexe de Čech du réseau de capteurs sans fil, noté ČRs (V), peut être construit comme suit: un k-simplexe

[v 0 , v 1 , • • • , v k ] appartient à ČRs (V) chaque fois que ∩ k l=0 s v l = ∅.
De même, selon la définition 0.8 et nous considérons ici l'espace métrique (R 2 , d), le complexe de Rips, noté R Rc (V), peut être construit comme suit:

un k-simplexe [v 0 , v 1 , • • • , v k ] appartient à R Rc (V) chaque fois que v l -v m ≤ R c pour tout 0 ≤ l < m ≤ k.
La figure 5 montre un réseau de capteurs, son complexe de Čech et deux complexes de Rips pour deux valeurs différentes de R c . En fonction du ratio de R c sur R s , le complexe de Rips et le complexe de Čech peuvent être proches ou plutôt différents. Dans cet exemple, pour R c = 2R s , le complexe de Rips voit le trou entouré par des noeuds 2, 3, 5, 6 comme dans le complexe de Čech tandis qu'il n'est pas visible dans le complexe de Rips pour R c = 2.5R s . Dans le même temps, le trou de couverture entouré par les noeuds 1, 2, 6 n'est pas présent dans les deux complexes de Rips.

En fait, le théorème de Čech (Theorem 0.1) indique que tout trou de couverture peut être trouvé dans le complexe de Čech. En outre, selon le Theorem 0.2, soit

d = 2, ǫ = R s et ǫ ′ = R c ,
il y a des relations suivantes entre le complexe de Čech et le complexe de Rips: Corollary 0.4. Quand γ ≥ 2, s'il y a un trou dans le complexe de Rips R Rc (V), il y aura un trou dans le complexe de Čech ČRs (V).

R Rc (V) ⊂ ČRs (V) ⊂ R 2Rs (V), whenever R c ≤ √ 3R s . (1)
Corollary 0.5. Quand √ 3 < γ < 2, il n'y a pas de relation garantie entre le complexe de Rips R Rc (V) et le complexe de Čech ČRs (V) en termes de trous. D'après ce qui précède, nous pouvons constater que pour qu'un trou dans un complexe de Čech ne soit pas vu dans un complexe de Rips, il faut et il suffit qu'il soit délimité par un triangle. Basé sur cette observation, une définition formelle de 'trou triangulaire' et de 'trou non-triangulaire' est donnée comme suit. Definition 0.9 (Trou triangulaire et non-triangulaire). Pour une paire de complexes ČRs (V) et R Rc (V) d'un réseau de capteurs, un trou triangulaire est une région non couverte délimitée par un triangle formé par les trois noeuds v 0 , v 1 , v 2 , où v 0 , v 1 , v 2 peuvent former un 2-simplexe qui apparaît dans R Rc (V) mais pas dans ČRs (V). Tous les autres trous sont non-triangulaires.

De la définition 0.9, nous pouvons voir dans la Figure 5 que quand R c = 2R s , il y a seulement un trou triangulaire délimitée par le triangle formé par les noeuds

< l ≤ R c / √ 3.
Un processus de Poisson homogène est stationnaire, donc sans tenir compte de l'effet frontière [START_REF] Bettstetter | How to achieve a connected ad hoc network with homogeneous range assignment: an analytical study with consideration of border effects[END_REF], tout point a la même probabilité d'être dans un trou triangulaire que l'origine O. Cette probabilité dans une configuration homogène est aussi égale à la proportion de la surface de trous triangulaires.

Nous considérons la probabilité que l'origine O soit à l'intérieur d'un trou triangulaire. Puisque la longueur de chaque arête dans le complexe de Rips doit être au plus R c , seuls les noeuds dans R c de l'origine peuvent contribuer au triangle qui délimite un trou triangulaire qui contient l'origine. Par conséquent, nous avons seulement besoin de considérer le processus de Poisson restreint à la la boule fermée B(O, R c ), qui est aussi un processus de Poisson homogène d'intensité λ. On note ce processus Φ. En outre, T (x, y, z) désigne la propriété que l'origine O est à l'intérieur du trou triangulaire délimitée par le triangle avec des points x, y, z en tant que sommets. Quand n 0 , n 1 , n 2 sont des points du processus Φ, T (n 0 , n 1 , n 2 ) est également utilisé pour désigner le cas où le triangle formé par les noeuds n 0 , n 1 , n 2 délimite un trou triangulaire qui contient l'origine. En outre, nous utilisons T ′ (n 0 , n 1 , n 2 ) pour désigner le cas où les noeuds n 0 , n 1 , n 2 ne peuvent pas former un triangle qui délimite un trou triangulaire qui contient l'origine.

Soit τ 0 = τ 0 (Φ) le noeud dans le processus Φ qui est plus proche de l'origine. Il y a deux cas à considérer lorsque l'origine à être à l'intérieur d'un trou triangulaire. Le premier cas est que le noeud τ 0 peut contribuer à un triangle qui délimite un trou triangulaire qui contient l'origine. Le deuxième cas est que le noeud τ 0 ne peut pas contribuer à un triangle qui délimite un trou triangulaire qui contient l'origine, mais trois autres noeuds peuvent former un triangle qui délimite un trou triangulaire qui contient l'origine. Ainsi, la probabilité que l'origine soit à l'intérieur d'un trou triangulaire peut être définie comme

p 2d (λ) = P{O is inside a triangular hole} = P{ {n 0 ,n 1 ,n 2 }⊆Φ T (n 0 , n 1 , n 2 )} = P{ {n 1 ,n 2 }⊆Φ\{τ 0 (Φ)} T (τ 0 , n 1 , n 2 )} + p sec 2d (λ) où p sec 2d (λ) = P{ {n i1 ,••• ,n i5 }⊆Φ\{τ 0 (Φ)} T (n i1 , n i2 , n i3 ) | T ′ (τ 0 , n i4 , n i5 )}
désigne la probabilité que le noeud τ 0 ne puisse contribuer à un triangle qui délimite un trou triangulaire qui contient l'origine, mais trois autres noeuds peuvent former un triangle qui délimite un trou triangulaire qui contient l'origine.

Dans les parties suivantes, nous allons analyser cette probabilité dans trois cas différents.

Theorem 0.9.

Quand 0 < γ ≤ √ 3, p 2d (λ) = 0. Theorem 0.10. Quand √ 3 < γ ≤ 2, on a p 2dl (λ) < p 2d (λ) < p 2du (λ), où p 2dl (λ) =2πλ 2 Rc/ √ 3 Rs r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 1 ,ϕ 1 )| )r 1 dr 1 (2) et p 2du (λ) =2πλ 2 Rc/ √ 3 Rs r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )r 1 dr 1 + p sec 2d (λ) et ϕ l (r 0 ) = 2 arccos(R c /(2r 0 )) ϕ u (r 0 ) = 2 arcsin(R c /(2r 0 )) -2 arccos(R c /(2r 0 )) R 1 (r 0 , ϕ 1 ) = min( » R 2 c -r 2 0 sin 2 ϕ 1 -r 0 cos ϕ 1 , » R 2 c -r 2 0 sin 2 (ϕ 1 + ϕ l (r 0 )) + r 0 cos(ϕ 1 + ϕ l (r 0 ))) |S + (r 0 , ϕ 1 )| = ϕ 1 ϕ l (r 0 ) R 1 (r 0 ,ϕ) r 0 rdrdϕ |S -(r 0 , r 1 , θ 1 )| = -ϕ l (r 0 ) θ 2l R 2 (r 0 ,r 1 ,θ 1 ,θ 2 ) r 0 rdrdθ 2 θ 2l = θ 1 -arccos cos(R c /R) -cos θ 1 cos θ 0 sin θ 1 sin θ 0 R 2 (r 0 , r 1 , θ 1 , θ 2 ) = min( » R 2 c -r 2 0 sin 2 θ 2 -r 0 cos θ 2 , » R 2 c -r 2 1 sin 2 (θ 2 -θ 1 ) + r 1 cos(θ 2 -θ 1 ))
p sec 2d (λ) est obtenu par des simulations.

Theorem 0.11. Quand γ > 2, on a p 2dl (λ) < p 2d (λ) < p 2du (λ), où

p 2dl (λ) =2πλ 2 ß Rc/2 Rs r 0 dr 0 π 0 dϕ 1 R ′ 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 1 ,ϕ 1 )| )r 1 dr 1 + Rc/ √ 3 Rc/2 r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 1 ,ϕ 1 )| )r 1 dr 1 ™ et p 2du (λ) =2πλ 2 ß Rc/2 Rs r 0 dr 0 π 0 dϕ 1 R ′ 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )r 1 dr 1 + Rc/ √ 3 Rc/2 r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )r 1 dr 1 ™ + p sec 2d (λ) et R ′ 1 (r 0 , ϕ 1 ) = min( » R 2 c -r 2 0 sin 2 ϕ 1 -r 0 cos ϕ 1 , » R 2 c -r 2 0 sin 2 ϕ 1 + r 0 cos ϕ 1 )
p sec 2d (λ) est obtenu par des simulations. La probabilité p 2d (λ) obtenue par des simulations est présentée avec la borne inférieure et la borne supérieure dans la Figure 6 On peut voir que pour une valeur de γ, p 2d (λ) présente un maximum à une valeur de seuil λ c de l'intensité. En fait, pour λ ≤ λ c , le nombre de noeuds est faible. Par conséquent, la probabilité que l'origine soit à l'intérieur d'un trou triangulaire est relativement faible aussi. Avec l'augmentation de λ, la connectivité entre les noeuds devient plus forte. Par conséquent, la probabilité que l'origine soit à l'intérieur d'un trou triangulaire augmente. Cependant, quand l'intensité atteint la valeur de seuil, l'origine est recouverte avec une probabilité maximale. p 2d (λ) diminue pour λ ≥ λ c . Les simulations montrent également que λ c diminue avec l'augmentation de γ. Dans cette section, nous étendons l'analyse sur la précision de la détection de trou de couverture basée sur l'homologie aux réseaux de capteurs sans fil sur la sphère. L'idée est la même que celle pour l'analyse de la précision dans le plan. La différence est que un trou dans un complexe de Čech manqué par un complexe de Rips doit être délimitée par un triangle sphérique. Nous définissons ainsi ces trous comme des trous triangulaires sphériques. On choisit la proportion de la surface de trous triangulaires sphériques comme une métrique pour évaluer la précision de la détection de trou de couverture basée sur l'homologie sur la sphère. Puisque le calcul est similaire, nous donnons simplement les résultats ici.

L'évaluation des performances

Supposons les capteurs déployés aléatoirement sur une sphère de rayon R selon un processus de Poisson homogène d'intensité λ. Tous les capteurs ont le même rayon de détection

R s et de communication R c , R s ≪ R, R c ≪ R.
Soit p s (λ) désigne la proportion de la surface de trous triangulaires sphériques, nous avons les résultats suivants. Theorem 0.12.

Quand 0 < R c ≤ R arccos([3 cos 2 (R s /R) -1]/2), p s (λ) = 0. Theorem 0.13. Quand R arccos([3 cos 2 (R s /R) -1]/2) < R c ≤ 2R s , on a p sl (λ) < p s (λ) < p su (λ), où p sl (λ) = 2πλ 2 R 4 θ 0u Rs/R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )dθ 1 (3) et p su (λ) = 2πλ 2 R 4 θ 0u Rs/R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )dθ 1 + p sec s (λ) et θ 0u = arccos » [1 + 2 cos(R c /R)]/3 ϕ m (θ 0 ) = arccos[(cos(R c /R) -cos 2 θ 0 )/ sin 2 θ 0 ] θ 1u (θ 0 , ϕ s1 ) = min{θ 1u1 (θ 0 , ϕ s1 ), θ 1u2 (θ 0 , ϕ s1 )} θ 1u1 (θ 0 , ϕ s1 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 ϕ s1 ò + arctan(cos ϕ s1 tan θ 0 ) θ 1u2 (θ 0 , ϕ s1 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 (ϕ s1 -ϕ m (θ 0 )) ò + arctan(cos(ϕ s1 -ϕ m (θ 0 )) tan θ 0 ) |C(N, Rθ 0 )| = 2πR 2 (1 -cos θ 0 ) |S + (θ 0 , ϕ s1 )| = ϕ s1 2π-ϕm(θ 0 ) θ 1u (θ 0 ,ϕ) θ 0 R 2 sin θdθdϕ |S -(θ 0 , θ 1 , ϕ s1 )| = ϕm(θ 0 ) ϕ 2l (θ 0 ,θ 1 ,ϕ s1 ) θ 2u (θ 0 ,θ 1 ,ϕ s1 ,ϕ 2 ) θ 0 R 2 sin θ 2 dθ 2 dϕ 2 ϕ 2l (θ 0 , θ 1 , ϕ s1 ) = ϕ s1 -arccos cos(R c /R) -cos θ 1 cos θ 0 sin θ 1 sin θ 0 θ 2u (θ 0 , θ 1 , ϕ s1 , ϕ 2 ) = min{θ 1u1 (θ 0 , ϕ 2 ), θ 2u2 (θ 0 , θ 1 , ϕ s1 , ϕ 2 )} θ 2u2 (θ 0 , θ 1 , ϕ s1 , ϕ 2 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 (ϕ 2 -ϕ s1 ) ò + arctan(cos(ϕ 2 -ϕ s1 ) tan θ 1 )
p sec s (λ) est obtenu par des simulations.

Theorem 0.14. Quand R c > 2R s , on a p sl (λ) < p s (λ) < p su (λ), où

p l (λ) = 2πλ 2 R 4 ß Rc 2R Rs R sin θ 0 dθ 0 2π π dϕ s1 θ ′ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )dθ 1 + θ 0u Rc/2R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 e -λ|C(N,Rθ 0 )| × e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )dθ 1 ™ et p u (λ) = 2πλ 2 R 4 ß Rc 2R Rs R sin θ 0 dθ 0 2π π dϕ s1 θ ′ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )dθ 1 + θ 0u Rc/2R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 e -λ|C(N,Rθ 0 )| × e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )dθ 1 ™ + p sec s (λ) et θ ′ 1u (θ 0 , ϕ s1 ) = min{θ 1u1 (θ 0 , ϕ s1 ), θ ′ 1u2 (θ 0 , ϕ s1 )} θ ′ 1u2 (θ 0 , ϕ s1 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 ϕ s1 ò -arctan(cos ϕ s1 tan θ 0 ) p sec s (λ)

L'évaluation des performances

Une sphère centrée à l'origine de rayon R est considérée dans les simulations. La probabilité que le point de coordonnées sphériques (R, 0, 0) soit à l'intérieur d'un trou triangulaire sphérique est calculée. Les capteurs sont déployés aléatoirement sur la sphère selon un processus de Poisson homogène d'intensité λ. Le rayon de détection R s de chaque noeud est 10 mètres et le rayon de communication R c est choisi de 20 à 30 mètres avec un intervalle de 2 mètres. Soit γ = R c /R s , alors γ varie de 2 à 3 avec un intervalle de 0.2. En outre, λ est sélectionnée de 0.001 à 0.020 avec un intervalle de 0.001. Pour chaque paire de (λ, γ), 10 7 simulations sont exécutées pour vérifier si le point de coordonnées sphériques (R, 0, 0) est à l'intérieur d'un trou triangulaire sphérique. A partir sur ces hypothèses, nous pouvons utiliser un graphe G(V, E) pour représenter le réseau de capteurs sans fil, où V représente tous les noeuds du réseau de capteurs sans fil. Pour deux noeuds, si ils peuvent communiquer avec l'autre, une arête les connecte sur le graphe. Pour tout noeud v i ∈ V , son graphe de voisinage est le sous-graphe de G(V, E) induit par tous ses voisins.

0.4.1.1 Impact de R s et R c Puisque l'on suppose R s ≪ R et R c ≪ R, on choisit R = 10R s pour analyser l'impact de R s et R c

Un algorithme distribué basé sur les graphes

Le processus de notre algorithme peut être résumé comme suit.

Modèles et définitions

Nous utilisons les mêmes modèles pour les noeuds comme dans la Section 0.5. En outre, nous avons besoin de donner quelques définitions qui seront utilisés dans le processus de cet algorithme.

On dit que un i-simplexe

[v i0 , v i1 , ..., v ii ] fait partie d'un j-simplexe [v j0 , v j1 , ..., v jj ] si [v i0 , v i1 , ..., v ii ] ⊂ [v j0 , v j1 , ..., v jj ]. Ainsi, le sommet [v 0 ] ou [v 1 ] fait partie de l'arête [v 0 , v 1 ]. L'arête [v 0 , v 1 ] fait partie du 2-simplexe [v 0 , v 1 , v 2 ].
T (v), c'est-à-dire w v = min △∈T (v) I △ .
Le poids d'un noeud interne est un indicateur de la densité de ses noeuds voisins. Si le poids d'un noeud interne est 0, le noeud doit être sur le bord d'un trou de couverture. Plus le poids est élevé, plus la probabilité que le noeud ne soit pas sur le bord d'un trou de couverture est grande.

On utilise également la définition de graphe simplement connecté comme dans [START_REF] Dong | Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods[END_REF]. Soit G un graphe simple avec ensemble de sommets V (G) et d'arêtes E(G). Un cycle C est un sous-graphe de G s'il est connectée et chaque sommet de C est de degré deux. Le longueur d'un cycle C est le nombre de ses arêtes, noté |E(C)|. L'espace de cycle C(G) d'un graphe G contient tous les cycles de G. L'ajout de deux cycles

C 1 et C 2 est défini comme C 1 ⊕ C 2 = (E(C 1 ) ∪ E(C 2 )) \ (E(C 1 ) ∩ E(C 2 )).
Le sous-espace de cycle du triangle C T (G) de G est l'ensemble de tous les cycles 3-longueur dans C(G).

G[N G (u) ∩ N G (v) ∪ {u, v}] -e. L'ensemble de voisins d'un k-simplexe [v 0 , v 1 , ..., v k ] est défini comme k i=0 N G (v i ).
Definition 0.13 (Suppression d'un k-simplexe dans un complexe de Rips).

Un k- simplexe [v 0 , v 1 , • • • , v k ] est
w v = 0 else if ∃t ∈ T (v), n(t) est vide then w v = 2 else w v = 3 end if END 0.6.2.

Suppression de sommet et arête

Dans ce composant, on effectue un nombre maximal de suppressions de sommets sans changer le nombre de trous de couverture dans le réseau de capteurs original et on supprime également des arêtes spéciales si ces arêtes existent. Pour la suppression de sommets, on ne considère que les noeuds internes, les noeuds de clôture ne seront jamais supprimés. Dans la partie suivante, on utilise sommet et noeud de manière interchangeable.

(1) Suppression de sommet Si le poids d'un sommet est inférieur à 3, il ne doit jamais être supprimé. Sinon, le sommet continue à vérifier s'il est supprimable ou non en fonction de la transformation HP. Après la vérification, le sommet diffuse un message indiquant qu'il peut être supprimé ou non. Après avoir reçu le statut de tous ses voisins, chaque sommet supprimable continue à vérifier s'il doit être supprimé. On peut trouver que le poids de chaque sommet supprimable doit être 3. On suppose que le sommet avec une identité inférieure a la priorité doit être supprimé en premier. Donc, chaque sommet supprimable a juste besoin de vérifier si son identité est la plus basse parmi tous ses voisins supprimables. Si c'est le cas, il devrait être supprimé. Sinon, il ne doit pas être supprimé. L'algorithme 2 donne la procédure détaillée pour la suppression de sommet. La procédure de suppression de sommet se termine jusqu'à ce que aucun sommet ne puisse être supprimé dans le complexe de Rips. La Figure 12(b Après la suppression de sommets, on trouve une chose intéressante. Les Arêtes n'ayant pas de voisins doivent être sur le bord de trous, comme l'arête commune de trous de couverture 7 et 8 dans la Figure 12(b). L'arête ayant un seul voisin se trouve sur le bord d'un trou de couverture avec une grande probabilité, comme les arêtes rouges sur la Figure 12(b). Mais il est possible qu'il existe certaines de ces arêtes spéciales qui ne se trouvent pas sur le bord, comme l'arête bleu entre les trous de couverture 1 et 2 dans la Figure 12(b). Nous essayons de supprimer ces arêtes spéciales. Puisque l'arête a un seul voisin, la suppression de l'arête ne créera pas un nouveau trou.

On appelle arêtes frontière des arêtes ayant au plus un voisin. Ensuite, nous concevons une règle pour suppresser les arêtes frontières spéciales. Si un sommet v n'a qu'une seul arête frontière vx et vx a un seul voisin y et la suppression de vx ne fera pas v avoir une nouvelle arête frontière, alors vx peut être supprimé. Cela peut être facilement réalisé en vérifiant si vy a plus de deux voisins. La Figure 12(d) montre le résultat après la suppression d'arête.

Détection d'arête frontière

Après la suppression de sommets et d'arêtes, nous pouvons trouver que presque toutes les arêtes frontières se situent sur le bord de trous. On peut également voir que certaines arêtes situées sur le bord n'ont pas été trouvés. Dans ce composant, nous essayons de trouver les arêtes autant que possible. Dans tous les cas, ces arêtes ont deux ou plusieurs voisins. Si on définit les noeuds ayant une ou plusieurs arêtes frontières comme noeuds frontières et d'autres noeuds comme noeuds non-frontières, puis on essaie de supprimer certaines arêtes reliant les noeuds non-frontières et les noeuds frontières en fonction de la transformation HP, telles que les arêtes vertes illustrées sur la Figure 12(e). Après cela, il est possible que certaines nouvelles arêtes frontières soient reconnues et des arêtes spéciales illustrées dans la Section 0.6.2.2 sont également identifiés, comme les arêtes bleues présentées dans la Figure 12(f). Dans ce cas, on peut toujours utiliser la règle dans la Section 0.6.2.2 pour les supprimer. Il est encore possible que certaines arêtes se trouvant sur le bord n'aient pas été découvertes. Ce cas se produit généralement lorsque certains noeuds frontières sont des voisins et les arêtes qui les relient ont plus d'un voisin. Dans ce cas, on supprime aléatoirement certaines de ces arêtes en fonction de la transformation HP, comme les arêtes vertes sur la Figure 12(g). De cette façon, presque toutes les arêtes frontières peuvent être trouvées.

Découverte de cycles frontières élémentaires

Après la détection des arêtes frontières , il est facile de découvrir les cycles frontières élémentaires. Nous pouvons choisir au hasard des noeuds qui ont deux arêtes frontières comme initiateurs. Chaque noeud lance un processus pour trouver le cycle frontière élémentaire en envoyant un message le long de l'un de ses arêtes frontières. Quand il reçoit le message en retour le long de l'autre arête frontière, il découvre un cycle frontière élémentaire. De cette façon, tous les cycles frontières élémentaires peuvent être trouvés, comme les cycles indiqués par des couleurs différentes sur la Figure 12(k).

Minimisation de cycles frontières

Il est possible que certains cycles frontières élémentaires trouvés ne soient pas minimum, nous avons donc besoin de minimiser ces cycles. Ceci peut être réalisé en vérifiant s'il existe un chemin plus court entre deux noeuds quelconques dans le cycle. De cette façon, nous pouvons obtenir presque la plupart des cycles minimum entourant les trous de couverture.

L'évaluation des performances

On choisit une région carrée de 100 × 100 m 2 comme le domaine ciblé. Le rayon de détection R s de chaque noeud est 10 mètres. Le rayon de communication R c est 20 mètres et ainsi γ = 2. Il y a des capteurs de frontière le long des arêtes du carré avec 20 mètres de distance entre voisins. D'autres capteurs internes sont déployés de façon aléatoire dans la région basée sur un processus Poisson homogène d'intensité λ.

Complexité

La complexité de calcul de chaque étape de l'algorithme est illustré dans Table 1. Chapter 1 Introduction

Motivations

Recent advancements in wireless communications and Micro-Electro-Mechanical System (MEMS) have enabled the development of wireless sensor networks (WSNs) [START_REF] Akyildiz | A survey on sensor networks[END_REF]. A WSN consists of a number of tiny sensor nodes each capable of sensing, data processing and communicating with neighbouring nodes. These sensor nodes are deployed in the target field to collectively monitor physical phenomena, such as heat, light, sound, pressure, motion. WSNs have lots of applications, which can be generally classified into two categories: tracking and monitoring [START_REF] Yick | Wireless sensor network survey[END_REF]. Tracking applications include tracking humans, animals and vehicles [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF][START_REF] Oh | Instrumenting wireless sensor networks for real-time surveillance[END_REF][START_REF] Mikkel Baun Kjaergaard | Entracked: energy-efficient robust position tracking for mobile devices[END_REF][START_REF] Mikkel Baun Kjaergaard | Energy-efficient trajectory tracking for mobile devices[END_REF]. Monitoring applications include habitat and environmental monitoring [START_REF] Juang | Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet[END_REF][START_REF] Mainwaring | Wireless sensor networks for habitat monitoring[END_REF][START_REF] Szewczyk | Habitat monitoring with sensor networks[END_REF][START_REF] Tolle | A macroscope in the redwoods[END_REF][START_REF] Werner-Allen | Deploying a wireless sensor net-work on an active volcano[END_REF][START_REF] Mo | Canopy closure estimates with greenorbs: sustainable sensing in the forest[END_REF][START_REF] Song | Design and deployment of sensor network for real-time high-fidelity volcano monitoring[END_REF][START_REF] Mao | Citysee: Urban CO 2 monitoring with sensors[END_REF], structural health monitoring [START_REF] Xu | A wireless sensor network for structural monitoring[END_REF][START_REF] Chintalapudi | Monitoring civil structures with a wireless sensor network[END_REF][START_REF] Kim | Health monitoring of civil infrastructures using wireless sensor networks[END_REF][START_REF] Chebrolu | Brimon: a sensor network system for railway bridge monitoring[END_REF][START_REF] Stajano | Smart bridges, smart tunnels: Transforming wireless sensor networks from research prototypes into robust engineering infrastructure[END_REF], health-care monitoring [START_REF] Efstratiou | Experiences of designing and deploying intelligent sensor nodes to monitor hand-arm vibrations in the field[END_REF][START_REF] Baker | Wireless sensor networks for home health care[END_REF][START_REF] Lorincz | Mercury: a wearable sensor network platform for high-fidelity motion analysis[END_REF][START_REF] Shih | Sensor selection for energyefficient ambulatory medical monitoring[END_REF] and traffic monitoring [START_REF] Yoon | Surface street traffic estimation[END_REF][START_REF] Li | Performance evaluation of vehicle-based mobile sensor networks for traffic monitoring[END_REF][START_REF] Tubaishat | Wireless sensor networks in intelligent transportation systems[END_REF][START_REF] Semertzidis | Video sensor network for real-time traffic monitoring and surveillance[END_REF][START_REF] Pascale | Wireless sensor networks for traffic management and road safety[END_REF][START_REF] Bottero | Wireless sensor networks for traffic monitoring in a logistic centre[END_REF].

Coverage is a fundamental problem in WSNs. It can be considered as the measure of quality of service of a sensor network [START_REF] Meguerdichian | Coverage problems in wireless ad-hoc sensor networks[END_REF]. Based on the coverage objectives, the authors in [START_REF] Cardei | Coverage in Wireless Sensor Networks in Handbook of Sensor Networks[END_REF] classified coverage into three types: area coverage, point coverage and barrier coverage. As for the area coverage problem, the main objective of the sensor network is to cover an area. While in the point coverage problem, the objective is to cover a set of points. The aim of barrier coverage is to minimize the probability of undetected penetration through the barrier formed by wireless sensor networks. In this thesis, we focus on area coverage problem.

In applications related to area coverage, the target field is usually required to be fully covered. However, coverage holes may be formed due to many reasons, such as random deployment, energy depletion or destruction of sensors. For example, in the volcano monitoring applications, the target field is usually hostile or unapproachable for human beings, under such situations, sensor nodes have to be deployed randomly by helicopters or other kinds of vehicles. With random deployment, sensor nodes may cluster at some place while leaving coverage holes at some other places. Furthermore, even if in the initial deployment, the target field is fully covered by sensor nodes. With time goes by, some nodes may deplete their battery power more quickly than others, which may cause a coverage hole. In addition, some nodes may be destroyed by a natural disaster. Therefore, it is of paramount importance to detect and localize coverage holes. On one hand, it can facilitate the full coverage of target field. After coverage holes are localized, some moving nodes can de deployed in the coverage hole areas to patch them [START_REF] Wang | Movement-assisted sensor deployment[END_REF][START_REF] Wang | Sensor relocation in mobile sensor networks[END_REF]. On the other hand, knowing coverage hole boundaries is also very helpful in the design of basic networking functionalities, such as point-to-point routing and data gathering mechanisms [START_REF] Wang | Boundary recognition in sensor networks by topological methods[END_REF].

Many approaches have been proposed for coverage hole detection in WSNs. They can be generally classified into three categories: (i) location based approaches, (ii) range based approaches, and (iii) connectivity based approaches. Location based and range based approaches can discover all coverage holes with good accuracy but require either precise location information or accurate distance information, which is difficult to obtain in many scenarios. So connectivity based approaches received considerable attention in recent years. Particularly, homology based approaches attracted our attention. Ghrist and his collaborators introduced two combinatorial tools, Čech complex and Vietoris-Rips complex (we abbreviate it to Rips complex in this thesis), to detect coverage holes [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF]. They proposed a centralized solution for some simple scenarios, but designing an efficient distributed algorithm for coverage hole detection with only connectivity information is still an open issue.

Realizing the limitations of existing work for coverage hole detection in WSNs, we try to further analyse the usefulness of homology theory for coverage hole detection and design some distributed algorithms to detect coverage holes in WSNs.

Objectives and contributions

Objectives

The main objectives are to design algorithms for coverage hole detection in WSNs, which have the following properties.

• Connectivity based. Location based and range based approaches require either precise location information of nodes or accurate distance information between neighbouring nodes. Such requirement is either expensive or impractical in many scenarios, which substantially limits their applicability. So we aim to design connectivity based approaches.

• Distributed. Usually, there is no central unit in a WSN to control all the nodes. So it is required to design distributed algorithms, especially for large scale sensor networks.

• Efficient. Since sensor nodes have only limited capabilities, the complexity of the proposed algorithms should be low as much as possible so that sensor nodes can implement them efficiently, which can extend the lifetime of the sensor networks.

• Can discover boundary cycles. A boundary cycle of a coverage hole is a cycle connecting all the nodes surrounding the coverage hole. After discovering boundary cycles of coverage holes, we can deploy more nodes in these regions to cover them. It is thus important to detect boundary cycles. Many of the above presented approaches only detect boundary nodes, which may be not sufficient to discover the boundary cycles of coverage holes. For location based approaches, it is possible to find exact boundary cycles after detecting boundary nodes, as presented in [START_REF] Tong | On discovering sensing coverage holes in large-scale sensor networks[END_REF]. But for range based approaches, detecting boundary nodes is not sufficient to discover the exact boundary cycles in some cases, which will be illustrated in Section 2.1.4. Therefore, we aim to design algorithms which can discover boundary cycles.

Contributions

Our contributions are twofold: (1) accuracy of homology based coverage hole detection and (2) distributed algorithms for coverage hole detection. These works have been published in some conferences or submitted to some journals, as summarized in Table 1.1.

Accuracy of homology based coverage hole detection

Čech complex can fully capture coverage holes but it is difficult to construct. Rips complex is easy to construct but may miss some holes. We first analysed the relationship between Čech complex and Rips complex in terms of coverage holes for WSNs on a planar target field. Then we chose the proportion of the area of holes missed by Rips complex as a metric to evaluate the accuracy of homology based coverage hole detection. We showed that such proportion is related to the ratio between communication and sensing radii of each sensor (denoted respectively by R c and R s ). We then analysed this proportion in three cases and for each case, closed form expressions for lower and upper bounds were derived. Simulations results are well consistent with the analytical lower and upper bounds, with maximum differences of 0.5% and 3%. This part of work has been published in ICC 2012 [START_REF] Yan | Accuracy of homology based approaches for coverage hole detection in wireless sensor networks[END_REF].

In addition, we extended the analysis to the sphere case. Simulation results show that the radius of sphere has little impact on the proportion when it is much larger than communication and sensing radii of each sensor. This part of work has been submitted to IEEE Transactions on Wireless Communications [START_REF] Yan | Accuracy of homology based coverage hole detection for wireless sensor networks on sphere[END_REF].

Distributed algorithms for coverage hole detection

We first proposed a graph based distributed algorithm to detect coverage holes. The algorithm consists of four steps: neighbour discovery, boundary nodes discovery, boundary cycles discovery, cycles selection. In the step of neighbour discovery, each node obtains all its 1-and 2-hop neighbours information. In boundary nodes discovery step, each node determines whether it is a boundary node or not by checking the existence of a Hamiltonian cycle in its neighbour graph. If there exists, it is considered to be a non-boundary node. Otherwise, it is assumed to be a boundary node. After that, some boundary nodes are randomly selected to initiate the boundary cycles discovery process and many cycles will be found. But these found cycles may not be minimum or some of them bound the same coverage holes. So it is required to make choices among these cycles, which is done in the final step. This part of work has been published in GLOBECOM 2011 [START_REF] Yan | Connectivity-based distributed coverage hole detection in wireless sensor networks[END_REF].

The above proposed algorithm exhibits high complexity. So we designed a more efficient homology based algorithm. The basic idea of this algorithm is that for the Rips complex of a WSN, we try to delete some vertices and edges without changing the homology while making the Rips complex more sparse and nearly planar. Then it is easier to find boundary cycles. The novelty of this algorithm lies in the rule we proposed to decide for each vertex or edge whether its deletion can change the homology or not. This algorithm has the worst case complexity O(n 3 ) where n is the maximum number of 1-hop neighbour nodes and n is finite. It is distributed and requires only 1-and 2-hop neighbour nodes information. It can accurately detect the boundary cycles of about 99% coverage holes in about 99% cases. This part of work has been submitted to IEEE/ACM transactions on networking [START_REF] Yan | Homology-based distributed coverage hole detection in wireless sensor networks[END_REF].

Organization

The rest of this thesis is organised as follows. Chapter 2 gives a survey about the coverage hole detection approaches and introduces homology theory briefly. Chapter 3 analyses the accuracy of homology based coverage hole detection for WSNs on a planar target field. It first identifies the relation between Čech complex and Rips complex on plane in terms of coverage holes. Then the lower and upper bounds of the accuracy are derived. Chapter 4 extends the ideas in Chapter 3 to WSNs on the sphere. Chapter 5 introduces a graph based distributed coverage hole detection algorithm. Chapter 6 further presents an efficient homology based distributed algorithm for coverage hole detection. Finally, Chapter 7 provides concluding remarks and some possible future research directions.

Chapter 2 Related Work and Mathematical Background

Many approaches have been proposed for coverage hole detection in WSNs. They can be generally classified into three categories: (1)location based approaches; (2) range based approaches and (3) connectivity based approaches. The connectivity based approaches can be further classified into graph based and homology based according to the tools they adopt. The former two types of approaches attract less attention since they require either precise location information of nodes or accurate distance information between neighbouring nodes which is very difficult to obtain in many scenarios. Connectivity based approaches attract a great deal of attention as they only need connectivity information which is easy to obtain. In this category, homology based approaches attract particular attention due to its powerful tools for coverage hole detection, which is also our interest.

In this chapter, we consider location based, range based and graph based approaches as traditional approaches and first give a survey about them and describe their pros and cons in Section 2.1. Then we give a brief introduction to homology theory before presenting homology based approaches in Section 2.2.

Traditional approaches

Location based approaches

The location based approaches can further be classified into two cases according to the boundary node detection methods they adopted.

Polygon based approaches

In [START_REF] Wang | Movement-assisted sensor deployment[END_REF][START_REF] Fang | Locating and bypassing routing holes in sensor networks[END_REF][START_REF] Ghosh | Estimating coverage holes and enhancing coverage in mixed sensor networks[END_REF][START_REF] Cărbunar | Redundancy and coverage detection in sensor networks[END_REF], the Voronoi diagram was used to detect boundary nodes. The Voronoi diagram of a collection of nodes partitions the space into polygons called Voronoi polygons. Every point in a given polygon is closer to the node in this polygon than to any other node. So if some portion of a Voronoi polygon is not covered by the node inside this polygon, it will not be covered by any other node, which implies a coverage hole. However, it is known from computational geometry that the Voronoi polygon of boundary nodes can not be locally computed in general [START_REF] Okabe | Spatial Tessellations: Concepts and Applications of Voronoi Diagrams[END_REF]. Realising such a problem, the authors in [START_REF] Zhang | Localized algorithms for coverage boundary detection in wireless sensor networks[END_REF][START_REF] Zhang | A coverage inference protocol for wireless sensor networks[END_REF] proposed to use localized Voronoi polygons for boundary node detection. In the scheme, each node constructs its localized Voronoi polygon. If its localized Voronoi polygon is infinite or it is finite but with some vertices uncovered by the node, then the node must be a boundary node.

Perimeter based approaches

Different from polygon based approaches, perimeter based approaches detect boundary nodes by checking whether the perimeter of the node's sensing disk is covered by its neighbours or not. In [START_REF] Huang | The coverage problem in a wireless sensor network[END_REF], it is proved that a sensor node does not border a coverage hole if its sensing border is entirely covered by the sensing ranges of its neighbours. Another boundary node detection approach proposed in [START_REF] Wang | Integrated coverage and connectivity configuration in wireless sensor networks[END_REF][START_REF] Zhang | Maintaining sensing coverage and connectivity in large sensor networks[END_REF] simplifies the previous border checking approach by only checking intersection points on the sensing border. A point is called an intersection point between nodes u and v if it is an intersection point of the sensing borders of u and v. A node is a boundary node if and only if there exists at least one intersection point which is not covered by any other neighbours. Based on that criterion, some other algorithms were proposed in [START_REF] Tong | On discovering sensing coverage holes in large-scale sensor networks[END_REF][START_REF] Watfa | Energy-efficient approaches to coverage holes detection in wireless sensor networks[END_REF] to discover boundary nodes. Furthermore, the authors also proposed a distributed algorithm to discover the exact boundary cycles of coverage holes in [START_REF] Tong | On discovering sensing coverage holes in large-scale sensor networks[END_REF].

Range based approaches

The range based approaches attempt to identify boundary nodes based on relative distance between neighbouring nodes. They also follow the ideas of either polygon based or perimeter based approaches. In [START_REF] Zhang | Detecting coverage boundary nodes in wireless sensor networks[END_REF][START_REF] Zhang | Localized coverage boundary detection for wireless sensor networks[END_REF], a localized Voronoi polygon based boundary node detection algorithm was proposed, which is similar as that in [START_REF] Zhang | Localized algorithms for coverage boundary detection in wireless sensor networks[END_REF][START_REF] Zhang | A coverage inference protocol for wireless sensor networks[END_REF]. The difference lies in that the localized Voronoi polygon is constructed using location information of nodes in [START_REF] Zhang | Localized algorithms for coverage boundary detection in wireless sensor networks[END_REF][START_REF] Zhang | A coverage inference protocol for wireless sensor networks[END_REF] while it is constructed based on directional and distance information between neighbouring nodes in [START_REF] Zhang | Detecting coverage boundary nodes in wireless sensor networks[END_REF][START_REF] Zhang | Localized coverage boundary detection for wireless sensor networks[END_REF].

In [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF], the author followed the idea of perimeter based approaches. He proposed a coverage verification algorithm based on distances between neighbouring nodes. In the algorithm, each node first calculates a set of segments. Each segment is a part of its sensing border that is covered by one of its intersecting neighbours. After that, the node verifies whether its entire sensing border is covered by the set of segments. If yes, it implies the node is not a boundary node. Otherwise, it is a boundary node. Recently, in [START_REF] Bejerano | Coverage verification without location information[END_REF], the same author proposed another simpler algorithm for coverage verification. He assumed that the transmission radius of each sensor is at least four times larger than its sensing radius. The assumption implies that for any node, every pair of its intersecting neighbours are also neighbours of each other. The algorithm uses this property to determine the relative locations of all the intersecting neighbours of any node and uses it to verify coverage. But if the assumption is not satisfied, the algorithm will not work. In addition, a more general scheme was proposed in [START_REF] Gaurav | Generic coverage verification without location information using dimension reduction[END_REF] for verifying k-coverage of a d-dimensional target field for an arbitrary positive integer k and d ∈ {1, 2, 3}. The scheme transforms the k-coverage verification problem in d dimension to a number of coverage verification problems in (d -1) dimension by dimension reduction technique. It then uses the same ideas as that in [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF][START_REF] Bejerano | Coverage verification without location information[END_REF] to verify k-coverage in one dimension.

Graph based approaches

Graph based approaches usually detect coverage holes based on graph theory. In [START_REF] Li | Distributed coordinate-free hole detection and recovery[END_REF][START_REF] Li | Distributed coordinate-free algorithm for full sensing coverage[END_REF], a set of active nodes is selected using some distance information. Then for each active node, it checks whether there exists a 3MeSH ring in its neighbour graph. A 3MeSH ring is defined as a closed polygon formed by nodes in neighbour graph, which can not be triangulated by these nodes. If there exists a 3MeSH ring, then the node is a non-boundary node, otherwise, it is a boundary node. After all boundary nodes are detected, boundary cycles are then discovered through signaling protocols. This approach is not purely based on connectivity information, it needs some distance information. In addition, it can detect holes with up to ten edges with proper complexity, but for holes with more than ten edges, the complexity will be higher.

More recently, some distributed algorithms were proposed to detect topological hole [START_REF] Funke | Topological hole detection in wireless sensor networks and its applications[END_REF][START_REF] Funke | Hole detection or: "how much geometry hides in connectivity?[END_REF] or to recognise boundary in sensor networks by using only connectivity information [START_REF] Wang | Boundary recognition in sensor networks by topological methods[END_REF][START_REF] Dong | Distributed coverage in wireless ad hoc and sensor networks by topological graph approaches[END_REF][START_REF] Dong | Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods[END_REF][START_REF] Kröller | Deterministic boundary recognition and topology extraction for large sensor networks[END_REF][START_REF] Zhou | Localized algorithm for precise boundary detection in 3d wireless networks[END_REF]. These algorithms may be useful for coverage hole detection. In [START_REF] Funke | Topological hole detection in wireless sensor networks and its applications[END_REF][START_REF] Funke | Hole detection or: "how much geometry hides in connectivity?[END_REF], Funke et al proposed a simple distributed algorithm to identify nodes near the boundary of the target field and holes. The basic idea is to construct iso-contours based on hop count from a root node and identify where the contours are broken. Following their ideas, two boundary detection algorithms were proposed in [START_REF] Le | Topological boundary detection in wireless sensor networks[END_REF] and [START_REF] Chu | Decentralized boundary detection without location information in wireless sensor networks[END_REF]. In [START_REF] Kröller | Deterministic boundary recognition and topology extraction for large sensor networks[END_REF], Kröller et al proposed to recognise boundary by searching for some specific structures called flower and augmenting cycle. The success of their algorithm critically depends on the identification of at least one flower structure, which may not always be the case especially in a sparse network [START_REF] Wang | Boundary recognition in sensor networks by topological methods[END_REF]. In [START_REF] Saukh | On boundary recognition without location information in wireless sensor networks[END_REF], Saukh et al introduced the concept of patterns and proposed a fully distributed algorithm for boundary recognition based on that concepts. Their approach is applicable for both dense and sparse deployments. In [START_REF] Schieferdecker | Efficient algorithms for distributed detection of holes and boundaries in wireless networks[END_REF], a distributed algorithm based solely on connectivity information was proposed to detect holes and boundaries. The basic idea is to use multidimensional scaling (MDS) [START_REF] Torgerson | Multidimensional scaling: I. theory and method[END_REF] to compute virtual coordinates of nodes, and then use a geometrical method to detect boundary nodes. But the running time of MDS is high. In [START_REF] Wang | Boundary recognition in sensor networks by topological methods[END_REF], Wang et al exploited a special structure called "cut" in the shortest path tree to detect boundary nodes and connect them to boundary cycles. As their basic objective is to identify the global topology of the underlying environment where sensors are deployed, some holes may be neglected by their algorithm. In order to identify holes with any size, Dong et al [START_REF] Dong | Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods[END_REF] proposed a fine grained boundary recognition approach. The basic idea is to first extract the skeleton of the sensor network, and then to identify primary boundary cycles, finally to minimize these boundary cycles. As their algorithm involves many communications in the whole network, the control overhead is significant.

Fekete et al [START_REF] Sándor | Neighborhood-based topology recognition in sensor networks[END_REF] proposed a statistical method to detect boundary nodes based on the assumption that nodes on the boundaries have much less average degrees than nodes in the interior of the network. Another statistical approach was proposed in [START_REF] Sándor | A new approach for boundary recognition in geometric sensor networks[END_REF] by computing the restricted stress centrality of a node. Nodes in the interior tend to have a higher centrality than nodes on the boundary. Similarly, Li et al [START_REF] Li | Coordinate-free distributed algorithm for boundary detection in wireless sensor networks[END_REF] exploited two centrality measures in graph theory, called betweenness and closeness, to identify boundary nodes. It is observed that boundary nodes usually have lower betweenness or higher closeness than their neighbouring nodes. These statistical approaches usually require very high node density.

In summary, these boundary recognition approaches suffer from one or more following disadvantages if used for coverage hole detection. (1) They only detect coarse boundary nodes and do not consider boundary cycles. ( 2) They can only detect large coverage holes. (3) The complexity is high. (4) High density of nodes is required.

Remarks on these approaches

To summarize, Table 2.1 gives some typical traditional approaches and their characteristics and Table 2.2 presents the pros and cons of the traditional coverage hole detection approaches. [START_REF] Zhang | Detecting coverage boundary nodes in wireless sensor networks[END_REF] Range based Distributed NA No Bejerano [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF] Range based Distributed O(n 3 ) No Li et al [START_REF] Li | Distributed coordinate-free hole detection and recovery[END_REF] Graph based Distributed O(n 3 ) Yes Wang et al [START_REF] Wang | Boundary recognition in sensor networks by topological methods[END_REF] Graph based Distributed NA Yes Dong et al [START_REF] Dong | Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods[END_REF] Graph based Distributed NA Yes

Graph based only need connectivity information may miss coverage holes

Generally speaking, the performance of location based approaches and range based approaches is highly dependent on the accuracy of location or distance information. When accurate location information is available, location based approaches can not only detect all boundary nodes but also discover all boundary cycles. But Some graph based approaches may not be directly used to detect coverage holes, but they can really provide some helpful insights for distributed algorithm design.

Homology based approaches

Homology based approaches attempt to detect coverage holes based on homology theory. The principle of homology theory consists in analysing topological properties of some domain by algebraic computations. The main objects are known as simplicial complexes, which are generalization of graphs. Homology group is a topological invariant that can distinguish between topological spaces by measuring the number of holes in a topological space. These concepts may be relatively less known, so it is necessary to give a basic introduction first.

Mathematical background

In this section, we give a brief introduction to homology theory, see [START_REF] Anthony | Basic Topology[END_REF][START_REF] Munkres | Elements of algebraic topology[END_REF][START_REF] Hatcher | Algebraic Topology[END_REF] for a thorough introduction to this subject. We first give the definitions of simplex and simplicial complex. After that, homology group is defined following definitions of chain group, cycle group and boundary group. Finally, the two most useful simplicial complexes of networks are introduced and their relations are presented.

Simplicial complex

Given a set of points V , a k -simplex σ is an unordered set {v 0 , v 1 , ..., v k } ⊆ V where v i = v j for all i = j, k is the dimension of the simplex. In geometric realisation, a 0-simplex is a vertex, a 1-simplex is an edge, a 2-simplex is a triangle with its interior included and a 3-simplex is a tetrahedron including its interior, see Figure 2.2. Any subset of {v 0 , v 1 , ..., v k } is called a face of σ. A simplicial complex X is a collection of simplices which satisfies two conditions: (1) any face of a simplex from X is also in X; (2) the intersection of any two simplices σ 1 and σ 2 is a face of both σ 1 and σ 2 . An abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex and therefore does not need the second condition. The dimension of a simplicial complex X is the largest dimension of any simplex in X. A subcomplex of X is a simplicial complex X (k) ⊂ X, where k indicates the dimension of X (k) . For example, in the simplicial complex shown in Figure 2.3, it contains six 0simplices {1}, {2}, . . . , {6}, eight 1-simplices {1, 2}, {1, 6}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {4, 5}, {5, 6} and one 2-simplex {1, 2, 6}.

v 0 v 0 v 1 v 0 v 1 v 2 0-simplex 2-simplex 1-simplex v 0 v 1 v 2 v 3 3-simplex
k-simplex in X. Denote the k-simplex {v 0 , v 1 , • • • , v k } with an ordering by [v 0 , v 1 , • • • , v k ],
and a change in the orientation corresponds to a change in the sign of the coefficient like

[v 0 , • • • , v i , • • • , v j , • • • , v k ] = -[v 0 , • • • , v j , • • • , v i , • • • , v k ]
Then we can define chain group, boundary map, cycle group, boundary group and finally homology group. Definition 2.1. Given an abstract simplicial complex X, for each k > 0, the kchain group C k (X) is the vector space spanned by the set of oriented k-simplices of X. If k is larger than the dimension of X, C k (X) is defined to be 0. Definition 2.2. The boundary map ∂ k is defined to be the linear transformation

∂ k : C k (X) → C (k-1) (X) which acts on the basis elements of C k (X) via ∂ k [v 0 , • • • , v k ] = k i=0 (-1) i [v 0 , • • • , v i-1 , v i+1 , • • • , v k ]
where the sum is algebraic summation.

Still consider the example shown in Figure 2.3, taking into account the orientation, we assume that it contains six 0-simplices [START_REF] Akyildiz | A survey on sensor networks[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF], . . . , [START_REF] Simon | Sensor networkbased countersniper system[END_REF], eight 1-simplices [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF], [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Li | Detection, classification, and tracking of targets[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF], [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF], [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF], [START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF], [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] and one 2-simplex [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF]. According to Definition 2.2, we can see that the boundary of the 2-simplex [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] is the sum of three 1-simplices [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF], [START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] and [START_REF] Simon | Sensor networkbased countersniper system[END_REF][START_REF] Akyildiz | A survey on sensor networks[END_REF], as illustrated in Figure 2.4(a). While the boundary of the sum of three 1-simplices [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF], [START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF] and [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Li | Detection, classification, and tracking of targets[END_REF] is 0, shown in Figure 2.4(b).

k-cycle group of X is Z k (X) = ker ∂ k . Definition 2.4. The k-boundary group of X is B k (X) = im∂ k+1 .
From Definition 2.3 and 2.4, we can see that Z k (X) contains all the k-chains with no boundary and B k (X) contains all the k-chains which are a boundary of one

(k + 1)-chain. A simple calculation demonstrates that ∂ k • ∂ k+1 = 0, which means that a boundary has no boundary. It follows that B k (X) ⊂ Z k (X). The relations of C k (X), Z k (X), B k (X) are shown in Figure 2.5.
Then we can well define the homology group.

Definition 2.5. The k-th homology group of X is the quotient vector space

H k (X) = Z k (X) B k (X)
Definition 2.6. The k-th Betti number of X is the dimension of H k (X):

β k = dim H k (X) = dim Z k (X) -dim B k (X). 0 0 0 ∂ k+1 ∂ k C k+1 (X) C k (X) C k-1 (X) B k (X) Z k (X)
C k (X), Z k (X), B k (X)
From Definition 2.5, we can see that the k-th homology group H k (X) is a set of equivalence classes of k-cycles. For any two k-cycles z and z ′ , they are in the same equivalence class if and only if zz ′ ∈ B k (X), that is their difference is a boundary of one (k + 1)-chain. The Betti numbers are used to count the number of different dimensional holes in X. For example, β 0 indicates the number of 1-dimensional holes, that is the number of connected components. And β 1 counts the number of holes on the plane.

Consider the example in Figure 2.3, we use matrices to describe boundary maps, then we can get that ∂ 0 is the null function on the set of 1-simplices, ∂ 1 and ∂ 2 are given as follows.

∂ 1 =               [1, 2] [1, 6] [2, 3] [2, 6] [3, 4] [3, 5] [4, 5] [5, 6] [1] -1 -1 0 0 0 0 0 0 [2] 1 0 -1 -1 0 0 0 0 [3] 0 0 1 0 -1 -1 0 0 [4] 0 0 0 0 1 0 -1 0 [5] 0 0 0 0 0 1 1 -1 [6] 0 1 0 1 0 0 0 1               ∂ 2 =                     [1, 2, 6] [1, 2] 1 [1, 6] -1 [2, 3] 0 [2, 6] 1 [3, 4] 0 [3, 5] 0 [4, 5] 0 [5, 6] 0                    
Then we can obtain

β 0 = dim ker ∂ 0 -dim im∂ 1 = 6 -5 = 1 β 1 = dim ker ∂ 1 -dim im∂ 2 = 3 -1 = 2
β 0 denotes the number of connect components and β 1 denotes the number of holes.

It can be seen from Figure 2.3 that there are two holes surrounded by nodes 2, 3, 5, 6 and 3, 4, 5 respectively.

In above discussions, we only consider computation of the number of holes, without considering the localization of holes. Actually, it is possible to localize holes by computing non-trivial generators of the homology groups. But the standard computation usually exhibits high complexity, which is of quintic order in the number of simplices [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF]. In [START_REF] Muhammad | Control using higher order laplacians in network topologies[END_REF], the authors proposed to use the Laplacian operators on chain complexes to detect and localize holes. The Laplacian operator L k is defined from the boundary operators and their transposes:

L k = ∂ k+1 ∂ * k+1 + ∂ * k ∂ k (2.1)
Then it is shown that the k-th Betti number is the dimension of the null space of L k and the eigenvectors corresponding to the zero eigenvalues represent homology classes of the k-th homology group. For any k-simplex, it corresponds to a norm of its corresponding eigenvector component, by sequentially select the k-simplices with the highest norm, we may find the boundary cycles. But the found boundary cycles may not be true when two holes close to each other. We still use the example in Figure 2.3 to explain it.

According to (2.1), we can obtain

L 0 =               2 -1 0 0 0 -1 -1 3 -1 0 0 -1 0 -1 3 -1 -1 0 0 0 -1 2 -1 0 0 0 -1 -1 3 -1 -1 -1 0 0 -1 3               L 1 =                     3 0 -1 0 0 0 0 0 0 3 0 0 0 0 0 1 -1 0 2 1 -1 -1 0 0 0 0 1 3 0 0 0 1 0 0 -1 0 2 1 -1 0 0 0 -1 0 1 2 1 -1 0 0 0 0 -1 1 2 -1 0 1 0 1 0 -1 -1 2                     L 2 = 3
It is easy to compute that L 0 has one zero eigenvalue and the corresponding eigenvector is

V 0 =               0.4082 0.4082 0.4082 0.4082 0.4082 0.4082              
It can be seen that all vertices have the same norms in their corresponding eigenvector components, which means any vertex can be a generator of the homology group.

Similarly, we can find that L 1 has two zero eigenvalues and the corresponding eigenvectors are

V 1 =                     0.0306 -0.0306 0.0918 -0.0612 -0.5386 0.6304 -0.5386 0.0918                     and V 2 =                     -0.1800 0.1800 -0.5400 0.3600 -0.2768 -0.2632 -0.2768 -0.5400                    
We choose the three edges which have the highest norms in V 1 . Then we can find that they represent the hole bounded by three edges [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF], [START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF] and [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Li | Detection, classification, and tracking of targets[END_REF] in Figure 2.3. But from V 2 , if we sequentially choose the edge with the highest norm, we may find the cycle formed by edges [START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Li | Detection, classification, and tracking of targets[END_REF], [START_REF] Li | Detection, classification, and tracking of targets[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF], [START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF], [START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF][START_REF] Simon | Sensor networkbased countersniper system[END_REF] and [START_REF] Simon | Sensor networkbased countersniper system[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF] in Figure 2.3. The cycle bounds two holes in Figure 2.3. It means that the cycle found is not accurate. In addition, we can see that L 2 has no zero eigenvalue, which means that there is no 3-dimensional hole in Figure 2.3.

Abstract simplicial complexes for networks

For the coverage problem in WSNs, the two most useful abstract simplicial complexes are Čech complex and Rips complex. The Čech complex is defined as follows [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF].

Definition 2.7 ( Čech complex). Given a collection of sets U, Čech complex of U, Č(U), is the abstract simplicial complex whose k-simplices correspond to nonempty intersections of k + 1 distinct elements of U.

The Čech complex captures the topology of the collection of sets as illustrated by the following theorem.

Theorem 2.1 ( Čech theorem). The Čech complex of a collection of convex sets has the homotopy type of the union of the sets.

Unfortunately, it is very difficult to compute Čech complex even if the precise information about the relative locations of sensors is provided because of its high complexity. So another more easily computable complex named Rips complex is introduced. It is defined as follows.

Definition 2.8 (Rips complex). Given a metric space (M, d), a finite set of points V on M and a fixed radius ǫ, the Rips complex of V, R ǫ (V), is the abstract simplicial complex whose k-simplices correspond to unordered (k + 1)-tuples of points in V which are pairwise within distance ǫ of each other.

The Rips complex can be constructed with the sole knowledge of the connectivity graph of the network and gives an approximate coverage by simple algebraic calculations. But Rips complex may miss some coverage hole. In fact, there exist following relations between Čech complex and Rips complex [START_REF] Vin De Silva | Blind swarms for coverage in 2-d[END_REF].

Theorem 2.2. Let V be a set of points in R d and Čǫ (V) be the Čech complex of the cover of V by balls of radius ǫ. Then there is

R ǫ ′ (V) ⊂ Čǫ (V) ⊂ R 2ǫ (V) whenever ǫ ǫ ′ ≥ d 2(d + 1)
According to Theorem 2.2, the relation between Čech complex and Rips complex in terms of coverage holes can be derived, which will be presented in Chapter 3.

Homology based approaches

As a pioneer work, in [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF], Ghrist and his collaborators introduced homology to detect coverage holes. They first introduced a combinatorial object, Čech complex, which fully characterizes coverage properties of a WSN (existence and location of holes). Unfortunately, this object is very difficult to construct even if the precise information about the relative locations of sensors is available. Thus, they introduced another more easily computable complex, Rips complex. This complex can be constructed with the sole knowledge of the connectivity graph of the network and gives an approximate coverage by simple algebraic calculations. Then their work is followed by [START_REF] Vin De Silva | Blind swarms for coverage in 2-d[END_REF][START_REF] De | Coordinate-free coverage in sensor networks with controlled boundaries via homology[END_REF][START_REF] De | Coverage in sensor networks via persistent homology[END_REF][START_REF] De | Homological sensor networks[END_REF], where a relative homological criterion for coverage is presented. As regards implementation in real WSNs, these homology based approaches are necessarily centralized, which makes them impractical in large scale sensor networks.

The first steps of implementing the above ideas in a distributed way were taken in [START_REF] Muhammad | Control using higher order laplacians in network topologies[END_REF]. It is shown that combinatorial Laplacians are the right tools for distributed computation of homology groups, and thus can be used for decentralized coverage verification. The combinatorial Laplacians can be used to detect absence of holes or a single hole. But when there are multiple holes close to each other in WSNs, it is not clear how to distinguish them, as shown in Section 2.2.1.2. To address such limitations, a gossip like decentralized algorithm was proposed in [START_REF] Muhammad | Decentralized computation of homology groups in networks by gossip[END_REF] to compute homology groups, but its convergence is slow.

In [START_REF] Tahbaz | Distributed coverage verification in sensor networks without location information[END_REF][START_REF] Tahbaz | Distributed coverage verification in sensor networks without location information[END_REF], the authors first presented a decentralized scheme based on combinatorial Laplacians to verify whether there is a coverage hole or not in a WSN. For the case when there are coverage holes, they further formulated the problem of localizing coverage holes as an optimization problem for computing a sparse generator of the first homology group of the Rips complex corresponding to the sensor network. But it is possible that some cycle found by their algorithm contains multiple holes next to each other. For the purpose of coverage verification, a distributed algorithm for homology computation was proposed in [START_REF] Dlotko | Distributed computation of coverage in sensor networks by homological methods[END_REF] based on reduction and co-reduction of simplicial complex. But they did not consider the problem of localising coverage holes.

Following the ideas of homology based approaches, two divide and conquer based algorithms were proposed in [START_REF] Kanno | Detecting coverage holes in wireless sensor networks[END_REF] and [START_REF] Chintakunta | Divide and conquer: Localizing coverage holes in sensor networks[END_REF] respectively. In [START_REF] Kanno | Detecting coverage holes in wireless sensor networks[END_REF], the Rips complex of a sensor network is first planarized by eliminating some crossing edges using the scheme proposed in [START_REF] Muhammad | Connectivity graphs as models of local interactions[END_REF][START_REF] Muhammad | Connectivity graphs as models of local interactions[END_REF]. Then the planar simplicial complex is divided into subcomplexes. In each subcomplex, it is recursively divided until the holes are found. But the process of planarization needs location information of nodes. In [START_REF] Chintakunta | Divide and conquer: Localizing coverage holes in sensor networks[END_REF], the network is iteratively divided into small partitions. And in each partition, it verifies whether there are coverage holes by checking the first homology group of the Rips complex corresponding to this partition. If it is non-trivial, this partition is divided again. Otherwise, it means there is no coverage hole in this partition. As they used the algorithm in [START_REF] Muhammad | Decentralized computation of homology groups in networks by gossip[END_REF] to check the first homology group of Rips complex, the scheme also suffers from the same problem as that in [START_REF] Muhammad | Decentralized computation of homology groups in networks by gossip[END_REF].

Table 2.3 gives some typical homology based approaches and their characteristics. All these homology based approaches assume that the communication radius of each sensor R c is no larger than √ 3 times the sensing radius of the sensor R s . For this point, there are two aspects to be illustrated: (1) if this assumption is satisfied, Rips complex can be used for coverage verification. According to Theorem 2.2, let d = 2, ǫ = R s and ǫ ′ = R c , we can see if there is no coverage hole in Rips complex R ǫ ′ (V), there must be no coverage hole in the corresponding WSN. But as pointed out in [START_REF] De | Homological sensor networks[END_REF], it is also possible that some coverage holes are detected in Rips complex while there is in fact no holes in corresponding WSN, as shown in Figure 2.6. (2) If this assumption is not satisfied, Rips complex may miss some coverage holes, see Figure 2.7. Therefore, although homology theory has the great potential to solve coverage hole problem in WSNs, much work is needed for further research.

Introduction

As discussed in Chapter 2, Čech complex and Rips complex are two useful tools for coverage hole detection. But Čech complex is rather difficult to construct while Rips complex is easy to construct, so homology based approaches usually use Rips complex to detect coverage holes. In addition, these homology based approaches always assume that the communication radius R c of a sensor is no larger than √ 3 times the sensing radius R s of the sensor. But if this assumption is not satisfied, Rips complex may miss some special coverage holes (these holes are defined as triangular holes). It is thus of paramount importance to determine the proportion of the area of such triangular holes to evaluate the accuracy of homology based coverage hole detection. There is not much work on the proportion of the area of triangular holes. Some recent work [START_REF] Liu | A study of the coverage of large-scale sensor networks[END_REF][START_REF] Lazos | Stochastic coverage in heterogeneous sensor networks[END_REF][START_REF] Wan | Coverage by randomly deployed wireless sensor networks[END_REF][START_REF] Li | Coverage properties of the target area in wireless sensor networks[END_REF] provided some results on coverage probability but with a different point of view. In [START_REF] Liu | A study of the coverage of large-scale sensor networks[END_REF][START_REF] Lazos | Stochastic coverage in heterogeneous sensor networks[END_REF], the fraction of the area covered by sensors was analysed. In [START_REF] Wan | Coverage by randomly deployed wireless sensor networks[END_REF], the authors studied how the probability of coverage changes with the sensing radius or the number of sensors. In [START_REF] Li | Coverage properties of the target area in wireless sensor networks[END_REF], a point on a plane is defined to be tri-covered if it lies inside a triangle formed by three nodes, and the probability of tri-coverage is analysed. None of them considered triangular holes.

In this chapter, we focus on homology based coverage hole detection for WSNs on plane. Firstly, we identify the relationship between Čech complex and Rips complex in terms of coverage holes. We find that their relationship depends on the ratio between communication and sensing radii and the holes missed by Rips complex must be bounded by a triangle, we thus define them to be triangular holes and other holes to be non-triangular.

Secondly, we use the proportion of the area of triangular holes as a metric to evaluate the accuracy of homology based coverage hole detection. Such proportion is also related to the ratio between communication and sensing radii of each sensor. So for different ratios, we derive the closed form expressions for lower and upper bounds of the proportion.

Finally, extensive simulations have been run and it is shown that simulation results are well consistent with our analytical lower and upper bounds, with maximum differences of 0.5% and 3%.

Models and definitions

Consider a collection of stationary sensors (also called nodes) deployed on a planar target field according to a homogeneous Poisson point process with intensity λ. The Poisson point process is defined as follows.

Definition 3.1. A Poisson point process Φ with intensity λ on a Borel set B(X) is characterized by two fundamental properties: 1) For any subset A of B(X), the number of nodes in A, n(A), is a random variable following Poisson distribution with parameter λ|A|: P(n(A) = k) = e -λ|A| (λ|A|) k k! , where |A| is the area of A.

2) For any disjoint sets A 1 , A 2 of B(X), the random variables n(A 1 ) and n(A 2 ) are independent.

As usual, isotropic radio propagation is assumed. Each sensor monitors a region within a circle of radius R s and may communicate with other sensors within a circle of radius R c . Let V denote the set of sensor locations in a WSN and S = {s v , v ∈ V} be the collection of sensing disks of these sensors: for a location v, s v = {x ∈ R 2 :

xv ≤ R s }. Then, according to Definition 2.7, the Čech complex of the WSN, denoted by ČRs (V), can be constructed as follows:

a k -simplex [v 0 , v 1 , • • • , v k ] belongs to ČRs (V) whenever ∩ k l=0 s v l = ∅.
Similarly, according to Definition 2.8, we consider here the metric space (R 2 , d), then the Rips complex, denoted by R Rc (V), can be constructed as follows:

a k -simplex [v 0 , v 1 , • • • , v k ] belongs to R Rc (V) whenever v l - v m ≤ R c for all 0 ≤ l < m ≤ k.
Figure 3.1 shows a WSN, its Čech complex and two Rips complexes for two different values of R c . Depending on the ratio R c over R s , the Rips complex and the Čech complex may be close or rather different. In this example, for R c = 2R s , the Rips complex sees the hole surrounded by nodes 2, 3, 5, 6 as in the Čech complex whereas it is missed in the Rips complex for R c = 2.5R s . At the same time, the true coverage hole surrounded by nodes 1, 2, 6 is missed in both Rips complexes. In fact, the Čech theorem (Theorem 2.1) indicates that any coverage hole can be found in Čech complex. Furthermore, according to Theorem 2.2, let d = 2, ǫ = R s and ǫ ′ = R c , there are following relations between Čech complex and Rips complex:

R Rc (V) ⊂ ČRs (V) ⊂ R 2Rs (V), whenever R c ≤ √ 3R s . (3.1)
According to (3.1), some relationships between Čech complex and Rips complex in terms of coverage holes can be derived as illustrated in the following corollaries. For convenience, define γ = R c /R s .

Corollary 3.1. When γ ≤ √ 3, if there is no hole in Rips complex R Rc (V), there must be no hole in Čech complex ČRs (V).

Proof. If there is no hole in R Rc (V), it means that R Rc (V) can be triangulated. Since γ ≤ √ 3 means R c ≤ √ 3R s , according to the first inclusion in (3.1), we have R Rc (V) ⊂ ČRs (V). Consequently, Čech complex ČRs (V) can also be triangulated.

And when R c ≤ √ 3R s , each triangle must be covered by the sensing ranges of its vertex nodes [START_REF] Vin De Silva | Blind swarms for coverage in 2-d[END_REF]. So there is no hole in ČRs (V). Corollary 3.2. When γ ≥ 2, if there is a hole in Rips complex R Rc (V), there must be a hole in Čech complex ČRs (V).

Proof. If there is a hole in R Rc (V), there must be a cycle with more than three edges in R Rc (V) that can not be triangulated, as the cycle formed by nodes 2, 3, 5, 6 in Figure 3.1(c). Since γ ≥ 2 means R c ≥ 2R s , according to the second inclusion in (3.1), we can see that ČRs (V) ⊂ R 2Rs (V) ⊂ R Rc (V). Consequently, there must also be a cycle in ČRs (V) which can not be triangulated. And there is a coverage hole in the cycle.

Corollary 3.3. When √ 3 < γ < 2,
there is no guarantee relation between Rips complex R Rc (V) and Čech complex ČRs (V) in terms of holes.

From Corollary 3.1, a sufficient condition for coverage verification can be derived, which has been figured out in [START_REF] Tahbaz | Distributed coverage verification in sensor networks without location information[END_REF]. But it is not a necessary condition. It is possible that there is no hole in ČRs (V), while there is a hole in R Rc (V). From Corollary 3.2, we can find a necessary condition for the existence of a hole in ČRs (V). Corollary 3.3 indicates that when there is no hole in R Rc (V), it is possible that there is a hole in ČRs (V). When there is a hole in R Rc (V), it is also possible that ČRs (V) contains no hole.

From the discussions above, we can find that a hole in a Čech complex not seen in a Rips complex must be bounded by a triangle. Based on this observation, a formal definition of 'triangular hole' and 'non-triangular hole' is given as follows.

Definition 3.2 (Triangular and non-triangular hole). For a pair of complexes ČRs (V) and R Rc (V) of a WSN, a triangular hole is an uncovered region bounded by a triangle formed by three nodes v 0 , v 1 , v 2 , where v 0 , v 1 , v 2 can form a 2-simplex which appears in R Rc (V) but not in ČRs (V). Any other holes are non-triangular.

From Definition 3.2, we can see from Figure 3.1 that when R c = 2R s , there is only one triangular hole that bounded by the triangle formed by nodes 1, 2 and 6. When R c = 2.5R s , there are two additional triangular holes, bounded by triangles formed by nodes 2, 3, 6 and 3, 5, 6 respectively.

Bounds on proportion of triangular holes

In this section, the conditions under which any point on the target field is inside a triangular hole are first given. From the discussion in Section 3.2, it is found that the proportion of the area of triangular holes is related to the ratio γ. Three different cases are considered for the proportion computation. For each case, the upper and lower bounds of the proportion are derived.

Preliminary

Lemma 3.4. For any point on the target field, it is inside a triangular hole if and only if the following two conditions are satisfied:

1. the distance between the point and its nearest node is larger than R s .

2. the point is inside a triangle formed by three nodes with pairwise distance less than or equal to R c .

Lemma 3.5. If there exists a point O which is inside a triangular hole, then

R s < R c / √ 3.
Proof. According to the definition of triangular holes, if there exists a triangular hole, then there must be a 2-simplex which is in

R Rc (V) but not in ČRs (V). If R s ≥ R c / √ 3
, then according to the first inclusion in (1), we have R Rc (V) ⊂ ČRs (V), it means that there are no 2-simplices which are in R Rc (V) but not in ČRs (V), there is a contradiction, so R s < R c / √ 3.

Lemma 3.6. If O is inside a triangular hole and l denotes the distance between O and its closest neighbour, we have

R s < l ≤ R c / √ 3.
Proof. R s < l is a direct corollary from Lemma 3.4. We only need to prove l ≤ R c / √ 3. If point O is inside a triangular hole, it must be surrounded by a triangle formed by sensors with pairwise distance less than or equal to R c . Assume it is surrounded by a triangle N 0 N 1 N 2 , as in Figure 3

.2. The closest neighbour of O is not necessarily in the set {N 0 , N 1 , N 2 }. If l > R c / √ 3, then d 0 ≥ l > R c / √ 3, d 1 ≥ l > R c / √ 3 and d 2 ≥ l > R c / √ 3.
In addition, since α + β + ϕ = 2π, there must be one angle no smaller than 2π/3. Without loss of generality, assume α ≥ 2π/3, then according to the law of cosines,

d 2 02 = d 2 0 + d 2 2 -2d 0 d 2 cos α > R 2 c /3 + R 2 c /3 -2/3R c R c cos(2π/3) = R 2 c . So d 02 > R c . Since N 0 and N 2 are neighbours, d 02 ≤ R c . There is a contradiction. Therefore l ≤ R c / √ 3.
A homogeneous Poisson point process is stationary, thus without considering border effect [START_REF] Bettstetter | How to achieve a connected ad hoc network with homogeneous range assignment: an analytical study with consideration of border effects[END_REF], any point has the same probability to be inside a triangular hole as the origin O. This probability in a homogeneous setting is also equal to the proportion of the area of triangular holes. We borrow part of the line of proof from [START_REF] Li | Coverage properties of the target area in wireless sensor networks[END_REF] where a similar problem was analysed.

We consider the probability that the origin O is inside a triangular hole. Since the length of each edge in the Rips complex must be at most R c , only the nodes within R c from the origin can contribute to the triangle which bounds a triangular hole containing the origin. Therefore, we only need to consider the Poisson point process constrained in the closed ball B(O, R c ), which is also a homogeneous Poisson point process with intensity λ. We denote this process as Φ. In addition, T (x, y, z) denotes the property that the origin O is inside the triangular hole bounded by the triangle with points x, y, z as vertices. When n 0 , n 1 , n 2 are points of the process Φ, T (n 0 , n 1 , n 2 ) is also used to denote the event that the triangle formed by the nodes n 0 , n 1 , n 2 bounds a triangular hole containing the origin. In addition, we use T ′ (n 0 , n 1 , n 2 ) to denote the event that the nodes n 0 , n 1 , n 2 can not form a triangle which bounds a triangular hole containing the origin.

Let τ 0 = τ 0 (Φ) be the node in the process Φ which is closest to the origin. There are two cases for the origin to be inside a triangular hole. The first case is that the node τ 0 can contribute to a triangle which bounds a triangular hole containing the origin. The second case is that the node τ 0 can not contribute to any triangle which bounds a triangular hole containing the origin but other three nodes can form a triangle which bounds a triangular hole containing the origin. So the probability that the origin is inside a triangular hole can be defined as

p 2d (λ) = P{O is inside a triangular hole} = P{ {n 0 ,n 1 ,n 2 }⊆Φ T (n 0 , n 1 , n 2 )} = P{ {n 1 ,n 2 }⊆Φ\{τ 0 (Φ)} T (τ 0 , n 1 , n 2 )} + p sec 2d (λ) (3.2)
where

p sec 2d (λ) = P{ {n i1 ,••• ,n i5 }⊆Φ\{τ 0 (Φ)} T (n i1 , n i2 , n i3 ) | T ′ (τ 0 , n i4 , n i5 )}
denotes the probability that τ 0 can not contribute to any triangle which bounds a triangular hole containing the origin but other three nodes can form a triangle which bounds a triangular hole containing the origin.

In the following parts, we will analyse this probability in three different cases.

Case

0 < γ ≤ √ 3 Theorem 3.7. When 0 < γ ≤ √ 3, p 2d (λ) = 0.
Proof. It is a direct corollary from Lemma 3.5.

Case

√ 3 < γ ≤ 2 Theorem 3.8. When √ 3 < γ ≤ 2, we have p 2dl (λ) < p 2d (λ) < p 2du (λ), where p 2dl (λ) =2πλ 2 Rc/ √ 3 Rs r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 1 ,ϕ 1 )| )r 1 dr 1 (3.3)
and

p 2du (λ) =2πλ 2 Rc/ √ 3 Rs r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )r 1 dr 1 + p sec 2d (λ) (3.4)
and

ϕ l (r 0 ) = 2 arccos(R c /(2r 0 )) (3.5) ϕ u (r 0 ) = 2 arcsin(R c /(2r 0 )) -2 arccos(R c /(2r 0 )) (3.6) R 1 (r 0 , ϕ 1 ) = min( » R 2 c -r 2 0 sin 2 ϕ 1 -r 0 cos ϕ 1 , » R 2 c -r 2 0 sin 2 (ϕ 1 + ϕ l (r 0 )) + r 0 cos(ϕ 1 + ϕ l (r 0 ))) (3.7) |S + (r 0 , ϕ 1 )| = ϕ 1 ϕ l (r 0 ) R 1 (r 0 ,ϕ) r 0 rdrdϕ |S -(r 0 , r 1 , θ 1 )| = -ϕ l (r 0 ) θ 2l R 2 (r 0 ,r 1 ,θ 1 ,θ 2 ) r 0 rdrdθ 2 θ 2l = θ 1 -arccos cos(R c /R) -cos θ 1 cos θ 0 sin θ 1 sin θ 0 R 2 (r 0 , r 1 , θ 1 , θ 2 ) = min( » R 2 c -r 2 0 sin 2 θ 2 -r 0 cos θ 2 , » R 2 c -r 2 1 sin 2 (θ 2 -θ 1 ) + r 1 cos(θ 2 -θ 1 ))
p sec 2d (λ) is obtained by simulations.

Proof. We first prove the lower bound. It can be obtained from (3.2) that

p 2d (λ) > P{ {n 1 ,n 2 }⊆Φ\{τ 0 (Φ)} T (τ 0 , n 1 , n 2 )}
So for the lower bound, we only consider the case that the closest node τ 0 must contribute to a triangle which bounds a triangular hole containing the origin.

Using polar coordinates, we assume the closest node τ 0 lies on (d 0 , π). It is well known that the distance d 0 is a random variable with distribution

F d 0 (r 0 ) = P{d 0 ≤ r 0 } = 1 -e -λπr 2 0
Then the probability density function of d 0 can be found as

f d 0 (r 0 ) = 2πλr 0 e -λπr 2 0 (3.8) From Lemma 3.6, we can obtain R c < d 0 ≤ R c / √ 3
, then the above probability can be written as

P{ {n 1 ,n 2 }⊆Φ\{τ 0 (Φ)} T (τ 0 , n 1 , n 2 )} = Rc/ √ 3 Rs P{ {n 1 ,n 2 }⊆Φ ′ r 0 T ((r 0 , π), n 1 , n 2 )}f d 0 (r 0 )dr 0 (3.9)
where Φ ′ r 0 is the restriction of Φ in B(O, R c )\B(O, r 0 ). Once the node τ 0 is determined, the other two nodes must lie in the different half spaces: one in H + = R + ×(0, π) and the other in H -= R + ×(-π, 0). Assume n 1 lies in H + and n 2 lies in H -. Since the distance to τ 0 is at most R c , n 1 and n 2 must also lie in the ball B(τ 0 , R c ). Furthermore, the distance to the origin is at most R c and larger than d 0 , they should also lie in the region A = B(O, R c )\B(O, d 0 ). Therefore,

n 1 must lie in G + = H + B(τ 0 , R c ) A and n 2 must lie in G -= H -B(τ 0 , R c ) A.
In addition, considering the distance between n 1 and n 2 should be at most R c and the origin should be inside the triangle formed by τ 0 , n 1 and n 2 , n 1 must lie in the shadow region

A + = G + B(M 2 , R c ),
R c = γR s ≤ 2R s < 2d 0 . O τ 0 A + R c R c H + H - (d 0 , π) M 2 M 1 R c ϕ l ϕ u Figure 3.3: Illustration of region A + in the case √ 3 < γ ≤ 2
Ordering the nodes in A + by increasing polar angle so that τ 1 = (d 1 , ϕ 1 ) has the smallest angle ϕ 1 . And assume the nodes τ 0 , τ 1 and another node τ 2 ∈ G -can form a triangle which bounds a triangular hole containing the origin, then τ 2 must lie to the right of the line passing through τ 1 and O, denoted by H + (ϕ 1 ) which contains all points with polar angle ϕ ∈ (ϕ 1π, ϕ 1 ). In addition, the distance to τ 1 is at most R c , so the node τ 2 must lie in the region S -, as illustrated in Figure 3.4.

S -(τ 0 , τ 1 ) = S -(d 0 , d 1 , ϕ 1 ) = G -H + (ϕ 1 ) B(τ 1 , R c )
Here we need to obtain the density of node τ 1 . Considering the way τ 1 was defined, there should be no nodes with a polar angle less than ϕ 1 , that is to say no

O τ 0 A + R c H + H - (d 0 , π) M 2 M 1 ϕ 1 τ 1 (d 1 , ϕ 1 ) S + S -
S + (τ 0 , τ 1 ) = S + (d 0 , ϕ 1 ) = A + H + (ϕ 1 )
Since the intensity measure of the Poisson point process in polar coordinates is λrdrdϕ, the density F τ 1 of τ 1 can be expressed as

F τ 1 (dr 1 , dϕ 1 ) = λr 1 e -λ|S + (d 0 ,ϕ 1 )| dr 1 dϕ 1 (3.10)
The integration domain D(d 0 ) with respect to parameters (d 1 , ϕ 1 ) can be easily obtained. From the construction of the region A + , we can get ϕ l (r 0 ) = 2 arccos(R c /(2d 0 ))

and ϕ u (r 0 ) = 2 arcsin(R c /(2d 0 )) -2 arccos(R c /(2d 0 )). So ϕ l (r 0 ) ≤ ϕ 1 ≤ ϕ u (r 0 ) and d 0 < d 1 ≤ R 1 (d 0 , ϕ 1 ), where R 1 (d 0 , ϕ 1 ) = min( » R 2 c -d 2 0 sin 2 ϕ 1 -d 0 cos ϕ 1 , » R 2 c -d 2 0 sin 2 (ϕ 1 + ϕ l (r 0 )) + d 0 cos(ϕ 1 + ϕ l (r 0 )))
Assume only τ 0 , τ 1 and nodes in S -(τ 0 , τ 1 ) can contribute to the triangle which bounds a triangular hole containing the origin, we can get a lower bound of the probability that the origin is inside a triangular hole. It is a lower bound because it is possible that τ 1 can not contribute to any triangle which bounds a triangular hole containing the origin, but some other nodes with higher polar angles in the region A + can contribute to such a triangle. For example, in Figure 3.5, if there is no node in S -but there are some nodes in S ′-, then τ 1 can not contribute to any triangle which bounds a triangular hole containing the origin, but τ ′ 1 can form such a triangle with τ 0 and another node in S ′-. Based on the assumption, we have Next we will prove the upper bound. As discussed in Section 3.3.1, there are two cases for the origin being inside a triangular hole. As for the second case that the closest node τ 0 can not but some other nodes can contribute to a triangle which bounds a triangular hole containing the origin, it is not easy to obtain a closed form expression for such probability, so we can get it by simulations. Simulation results show that this probability is less than 0.0025 % at any intensity λ when √ 3 < γ ≤ 2. So we still focus on the probability of the first case.

P{ {n 1 ,n 2 }⊆Φ ′ r 0 T ((r 0 , π), n 1 , n 2 )} > P{ n 2 ⊆Φ ′ r 0 S -(τ 0 ,τ 1 ) T ((r 0 , π), τ 1 , n 2 )} = D(r 0 ) P{ n 2 ⊆Φ ′ r 0 S -(r 0 ,r 1 ,ϕ 1 ) T ((r 0 , π), (r 1 , ϕ 1 ), n 2 )}F τ 1 (dr 1 , dϕ 1 ) = D(r 0 ) P{Φ ′ r 0 (S -(r 0 , r 1 , ϕ 1 )) > 0}F τ 1 (dr 1 , dϕ 1 ) (3.11) O τ 0 A + R c H + H - (d 0 , π) M 2 M 1 ϕ 1 τ 1 S + S - τ′ 1 R c R c S′ - S′ +
For the lower bound, we only considered the case that τ 1 contributes to a triangle which bounds a triangular hole containing the origin. For the upper bound, we need to further consider the case that τ 1 can not but some other nodes in A + can contribute to such a triangle, shown in Figure 3.5. Assume the node τ ′ 1 = (d ′ 1 , ϕ ′ 1 ) with the second smallest polar angle in A + can contribute to such a triangle, it means that there is no node in S -(d 0 , d 1 , ϕ 1 ) but there is at lease one node in the region

S ′-(d 0 , d 1 , ϕ 1 , d ′ 1 , ϕ ′ 1 ) = S -(d 0 , d ′ 1 , ϕ ′ 1 )\S -(d 0 , d 1 , ϕ 1 ).
Then the density of the pair (τ 1 , τ ′ 1 ) is given as

F τ 1 ,τ ′ 1 (dr 1 , dϕ 1 , dr ′ 1 , dϕ ′ 1 ) = λ 2 r 1 r ′ 1 e -λ|S + (d 0 ,ϕ ′ 1 )| dr 1 dϕ 1 dr ′ 1 dϕ ′ 1 (3.
12)

The probability that τ 1 can not but τ ′ 1 can form a triangle which bounds a triangular hole containing the origin with τ 0 and another node in

S ′-(d 0 , d 1 , ϕ 1 , d ′ 1 , ϕ ′ 1 ) can be expressed as P{ {n 2 ,n 3 }⊆Φ ′ r 0 S -(τ 0 ,τ 1 ) T ((r 0 , π), τ ′ 1 , n 2 ) | T ′ ((r 0 , π), τ 1 , n 3 )} = P{Φ ′ r 0 (S -(r 0 , r 1 , ϕ 1 )) = 0} × P{Φ ′ r 0 (S ′-(r 0 , r 1 , ϕ 1 , r ′ 1 , ϕ ′ 1 )) > 0}F τ 1 ,τ ′ 1 (dr 1 , dϕ 1 , dr ′ 1 , dϕ ′ 1 ) = e -λ|S -(r 0 ,r 1 ,ϕ 1 )| × (1 -e -λ|S ′-(r 0 ,r 1 ,ϕ 1 ,r ′ 1 ,ϕ ′ 1 )| )F τ 1 ,τ ′ 1 (dr 1 , dϕ 1 , dr ′ 1 , dϕ ′ 1 ) (3.13)
As we can see from Figure 3.5, as long as τ ′ 1 has a higher polar angle than τ 1 has, the sum of

|S -(r 0 , r ′ 1 , ϕ ′ 1 )| and |S ′-(r 0 , r 1 , ϕ 1 , r ′ 1 , ϕ ′ 1 )
| will be always smaller than |S -(r 0 , r 0 , ϕ 1 )|.

Therefore we can get from (3.13)

P{ {n 2 ,n 3 }⊆Φ ′ r 0 S -(τ 0 ,τ 1 ) T ((r 0 , π), τ ′ 1 , n 2 ) | T ′ ((r 0 , π), τ 1 , n 3 )} < (e -λ|S -(r 0 ,r 1 ,ϕ 1 )| -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )F τ 1 ,τ ′ 1 (dr 1 , dϕ 1 , dr ′ 1 , dϕ ′ 1 ) (3.14) Furthermore, let S ′+ (d 0 , ϕ 1 , ϕ ′ 1 ) = S + (d 0 , ϕ ′ 1 )\S + (d 0 , ϕ 1 ), then λr ′ 1 e -λ|S ′+ (d 0 ,ϕ 1 ,ϕ ′ 1 )| dr ′ 1 dϕ ′ 1 = 1 -e -λ|A + \S + (d 0 ,ϕ 1 )| < 1 (3.15)
It is the complement of the probability that no node is in the region A + \S + (d 0 , ϕ 1 ).

From (3.11), (3.12), (3.14) and (3.15), we can obtain

P{ n 2 ⊆Φ ′ r 0 S -(τ 0 ,τ 1 ) T ((r 0 , π), τ 1 , n 2 )} + P{ {n 2 ,n 3 }⊆Φ ′ r 0 S -(τ 0 ,τ 1 ) T ((r 0 , π), τ ′ 1 , n 2 ) | T ′ ((r 0 , π), τ 1 , n 3 )} < D(r 0 ) (1 -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )F τ 1 (dr 1 , dϕ 1 ) (3.16)
Similarly, we can further consider the case that neither of τ 1 and τ ′ 1 can contribute to a triangle which bounds a triangular hole containing the origin, but other nodes with even higher polar angle can contribute to such a triangle. In this way, we can get the same result as (3.16).

Therefore, it can be derived that

P{ {n 1 ,n 2 }⊆Φ ′ r 0 T ((r 0 , π), n 1 , n 2 )} < D(r 0 ) (1 -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )F τ 1 (dr 1 , dϕ 1 ) (3.17)
From (3.2), (3.8), (3.9), (3.10) and (3.17), we can get the upper bound shown in (3.4).

Here we need to compute the areas of S + (r 0 , ϕ 1 ), S -(r 0 , r 1 , ϕ 1 ) and S -(r 0 , r 0 , ϕ 1 ). In fact, the areas |S + (r 0 , ϕ 1 )|, |S -(r 0 , r 1 , ϕ 1 )| and |S -(r 0 , r 0 , ϕ 1 )| have very similar expressions. For example, the area |S + (r 0 , ϕ 1 )| can be expressed as

|S + (r 0 , ϕ 1 )| = ϕ 1 ϕ l (r 0 ) R 1 (r 0 ,ϕ) r 0 rdrdϕ = 1 2 ϕ 1 ϕ l (r 0 ) [R 2 1 (r 0 , ϕ) -r 2 0 ]dϕ (3.18) When ϕ 1 ≤ π/2 -arccos(R c /(2r 0 )), |S + (r 0 , ϕ 1 )| = I(r 0 , ϕ 1 ) -I(r 0 , ϕ l (r 0 ))
where

I(r 0 , ϕ) = r 2 0 sin 2ϕ 4 + R 2 c ϕ 2 - R 2 c 2 arcsin r 0 sin ϕ R c - r 0 sin ϕ 2 » R 2 c -r 2 0 sin 2 ϕ - r 2 0 ϕ 2 When π/2 -arccos(R c /(2r 0 )) < ϕ 1 ≤ ϕ u (r 0 ), |S + (r 0 , ϕ 1 )| = 2|S + (r 0 , π/2 -arccos( R c 2r 0 )| -|S + (r 0 , π -2 arccos( R c 2r 0 ) -ϕ 1 |
Similarly, |S -(r 0 , r 1 , ϕ 1 )| and |S -(r 0 , r 0 , ϕ 1 )| can be obtained. The detailed com-putation is presented in Section A.1 of Appendix A.

Case γ > 2

Theorem 3.9. When γ > 2, we have p 2dl (λ) < p 2d (λ) < p 2du (λ), where

p 2dl (λ) =2πλ 2 ß Rc/2 Rs r 0 dr 0 π 0 dϕ 1 R ′ 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 1 ,ϕ 1 )| )r 1 dr 1 + Rc/ √ 3 Rc/2 r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 1 ,ϕ 1 )| )r 1 dr 1 ™ (3.19)
and

p 2du (λ) =2πλ 2 ß Rc/2 Rs r 0 dr 0 π 0 dϕ 1 R ′ 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )r 1 dr 1 + Rc/ √ 3 Rc/2 r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 )
r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1e -λ|S -(r 0 ,r 0 ,ϕ 1 )| )r 1 dr 1

™ + p sec 2d (λ) (3.20)
and

R ′ 1 (r 0 , ϕ 1 ) = min( » R 2 c -r 2 0 sin 2 ϕ 1 -r 0 cos ϕ 1 , » R 2 c -r 2 0 sin 2 ϕ 1 + r 0 cos ϕ 1 )
p sec 2d (λ) is obtained by simulations.

In this case, we can use the same method as in Section 3.3.3 to get the lower and upper bounds, shown in (3.19) and (3.20) respectively. But we need to consider two situations

R s < d 0 ≤ R c /2 and R c /2 < d 0 ≤ R c / √ 3.
In the first situation, d 0 ≤ R c /2 means that the ball B(O, d 0 ) is included in the ball B(τ 0 , R c ). The illustrations for the regions A + , S + , S -, S ′+ and S ′-in this situation are shown in Figure 3.6(a) and 3.6(b) respectively. In addition, the lower limit of integration for ϕ 1 is 0 and the upper limit is π. The computation of the area |S + (r 0 , ϕ 1 )| is the same as that in Section 3.3.3, but the computation of the area |S -(r 0 , r 1 , ϕ 1 )| is a little different, which is shown in Section A.2 of Appendix A. The second situation is the same as that in Section 3.3.3. Furthermore, simulation results show that p sec 2d (λ) is less than 0.16% at any intensity when 2 < γ ≤ 3.

O M R c R c τ 0 (d 0 , π) A + S + S - τ 1 ϕ 1 R c R c (a) O M R c τ 0 (d 0 , π) A + S + S - τ 1 ϕ 1 S′ - R c τ′ 1 S′ + (b)

Performance evaluation

This section first introduces simulation settings. Simulation results are then presented and compared with analytical lower and upper bounds.

Simulation settings

A disk centered at the origin with radius R c is considered in the simulations. The probability that the origin is inside a triangular hole is computed. Sensors are randomly distributed in the disk according to a homogeneous Poisson process with intensity λ. The sensing radius R s of each node is set to be 10 meters and γ is chosen from 2 to 3 with interval of 0.2. So the communication radius R c ranges from 20 to 30 meters with interval of 2 meters. λ is selected from 0.001 to 0.020 with interval of 0.001. For each γ, 10 7 simulations are run under each λ to check whether the origin is inside a triangular hole.

Performance evaluation

The probability p 2d (λ) obtained by simulations is presented with the lower bound and upper bound in It can be seen that for any value of γ, p 2d (λ) has a maximum at a threshold value λ c of the intensity. As a matter of fact, for λ ≤ λ c , the number of nodes is small. Consequently the probability of the origin being inside a triangular hole is relatively small too. With the increase of λ, the connectivity between nodes becomes stronger. As a result, the probability of the origin being inside a triangular hole increases. However, when the intensity reaches the threshold value, the origin is covered with maximum probability. p 2d (λ) decreases for λ ≥ λ c . The simulations also show that λ c decreases with the increase of γ.

On the other hand, it can be seen from Figure 3.7(a) and 3.7(b) that for a fixed intensity λ, p 2d (λ) increases with the increases of γ. That is because R s is fixed. Then the larger R c is, the higher is the probability of each triangle containing a coverage hole. Furthermore, the maximum probability increases quickly with γ ranging from 2.0 to 3.0. These results can be used for planning of WSNs, which will be discussed in Section 3.4.3.

Finally, it can be found in Figure 3.7(a) that the probability obtained by simulations is very well consistent with the lower bound. The maximum difference between them is about 0.5% according to Table 3.3. Figure 3.7(b) shows that probability obtained by simulations is also consistent with the upper bound. The maximum difference between them is about 3% according to Table 3.3. 3.0 0.001 0 0.0001 0.0004 0.0012 0.0024 0.0051 0.002 0.0001 0.0008 0.0037 0.0100 0.0208 0.0377 0.003 0.0002 0.0025 0.0116 0.0277 0.0556 0.0884 0.004 0.0004 0.0059 0.0219 0.0512 0.0899 0.1323 0.005 0.0008 0.0090 0.0321 0.0702 0.1121 0.1501 0.006 0.0012 0.0117 0.0409 0.0808 0.1172 0.1454 0.007 0.0015 0.0156 0.0474 0.0830 0.1109 0.1229 0.008 0.0017 0.0170 0.0490 0.0803 0.0995 0.0977 0.009 0.0021 0.0181 0.0475 0.0723 0.0809 0.0714 0.010 0.0023 0.0185 0.0436 0.0615 0.0621 0.0512 0.011 0.0022 0.0180 0.0399 0.0502 0.0455 0.0346 0.012 0.0025 0.0165 0.0344 0.0410 0.0339 0.0218 0.013 0.0020 0.0140 0.0285 0.0309 0.0232 0.0145 0.014 0.0020 0.0134 0.0238 0.0233 0.0158 0.0086 0.015 0.0016 0.0118 0.0192 0.0171 0.0116 0.0056 0.016 0.0019 0.0098 0.0148 0.0130 0.0069 0.0034 0.017 0.0016 0.0087 0.0118 0.0090 0.0047 0.0020 0.018 0.0015 0.0066 0.0091 0.0064 0.0034 0.0010 0.019 0.0010 0.0057 0.0070 0.0046 0.0020 0.0006 0.020 0.0010 0.0043 0.0050 0.0028 0.0010 0.0003

Discussions on applications

In this chapter, we only consider triangular holes. For non-triangular holes, we assume they can be detected and covered by additional nodes. Under this assumption, our analytical results can be used for planning of WSNs. For example, a WSN is used to monitor a planar target field and the ratio γ = 2, according to the analytical upper bounds, we can see that the maximum proportion of the area of triangular holes under γ = 2 is about 0.05%, which can be neglected. It means that as long as the planar target field can be triangulated by nodes, we can say the target field is covered. But if γ = 3 and at least 95% of the target field should be covered, then it means that the proportion of the area of triangular holes can be at most 5%. From the analytical upper bounds of γ = 3, it can be seen that when the intensity λ = 0.009, the upper bound is about 5%, so in order to cover at least 95% of the target field, the intensity of nodes should be larger than 0.009. Although in our simulations, we only consider γ between 2.0 and 3.0, similar results can be obtained for any other values of γ.

Chapter summary

In this chapter, we have considered the accuracy of homology based coverage hole detection on plane. We first derive the relationship between Čech complex and Rips complex in terms of coverage holes, which shows that their relationship is related to the ratio between communication and sensing radii of each sensor. Based on the relationship, the situations when Rips complex may miss coverage holes are identified. We find that the holes missed by Rips complex are always bounded by a triangle, so define them to be triangular holes. Furthermore, we use the proportion of the area of triangular holes to evaluate the accuracy of homology based coverage hole detection on plane. Sensors are assumed to be randomly deployed on a planar target field according to a homogeneous Poisson point process. Under such homogeneous configuration, without considering border effect, the proportion of the area of triangular holes is equivalent to the probability of any point in the target field being inside a triangular hole. Then we consider the probability in three different cases of the ratio between communication and sensing radii. For each case, the closed form expressions for the lower and upper bounds of the probability are derived. Simulation results are well consistent with the analytical lower and upper bounds, with maximum differences of 0.5% and 3%.

Chapter 4

Accuracy of Homology based Coverage Hole Detection on Sphere

Introduction

In Chapter 3, the accuracy of homology based coverage hole detection on plane has been analysed. But in some real applications, such as volcano monitoring [START_REF] Werner-Allen | Deploying a wireless sensor net-work on an active volcano[END_REF] and forest monitoring [START_REF] Mo | Canopy closure estimates with greenorbs: sustainable sensing in the forest[END_REF], the target fields are complex surfaces. So it is also important to consider the coverage hole detection problem of WSNs on surfaces. On the other hand, from theoretical point of view, the coverage on 3D surfaces is quite a different problem from its counterpart in 2D plane. As sphere is the simplest case of 3D surfaces, we choose it as the first step for the accuracy analysis of homology based coverage hole detection in this chapter. The relationship between Čech complex and Rips complex on sphere is different from that on plane. Similar as on plane, the holes missed by Rips complex on sphere are always bounded by a spherical triangle and are thus defined to be spherical triangular holes. We also use the proportion of the area of spherical triangular holes to evaluate the accuracy of homology based coverage hole detection on sphere. There is not much work on the proportion of the area of spherical triangular holes. In [START_REF] Zhao | Surface coverage in wireless sensor networks[END_REF], the authors proposed the surface coverage model and derived the expected coverage ratio under stochastic deployment on 3D surface. In [START_REF] Liu | On coverage of wireless sensor networks for rolling terrains[END_REF], the expected coverage ratio under stochastic deployment on 3D rolling terrains was derived. Nevertheless, none of these research considered spherical triangular holes.

In this chapter, we first analyse the relationship between Čech complex and Rips complex in terms of coverage holes on sphere. we find that a hole in a Čech complex missed by a Rips complex must be bounded by a spherical triangle. Based on that, a formal definition of spherical triangular hole is given.

Second, we choose the proportion of the area of spherical triangular holes as a metric to evaluate the accuracy of homology based coverage hole detection on sphere. Such proportion is analysed under a homogeneous setting and it is related to the communication and sensing radii of each sensor. Three cases are considered for the computation of such proportion. For each case, closed form expressions for lower and upper bounds of the proportion are derived.

Third, extensive simulations are performed to evaluate impacts of communication and sensing radii, radius of sphere on proportion of the area of spherical triangular holes. It is shown that simulation results are well consistent with the analytical lower bound, with a maximum difference of 0.5%, and consistent with the analytical upper bound, with a maximum difference of 3%. Furthermore, simulation results show that the radius of sphere has little impact on the proportion when it is much larger than communication and sensing radii.

Models and definitions

Consider a collection of stationary sensors (also called nodes) deployed randomly on a sphere S 2 with radius R according to a homogeneous Poisson point process with intensity λ. For any two points p 1 and p 2 on S 2 , the distance between them d(p 1 , p 2 ) is defined to be the great circle distance, which is the shortest distance between any two points on the surface of a sphere measured along a path on the surface of the sphere. As usual, isotropic radio propagation is assumed. All sensors have the same sensing radius R s and communication radius R c on S 2 . It means for any sensor located at v on S 2 , any point p on S 2 with d(v, p) ≤ R s is within the sensing range of the sensor; and for any two sensors located at v i , v j on S 2 , they can communicate with each other if d(v i , v j ) ≤ R c . In addition, we assume R s ≪ R, R c ≪ R.

On sphere, we also use Čech complex and Rips complex to capture coverage holes. Before constructing them, we need to point out that the realisation of k-simplex on sphere is different from that in Euclidean space R d . The realisation of 0-, 1-, 2-and 3-simplex in R d has been shown in Figure 2.2, here we give the realisation of 0-, 1-and 2-simplex on a sphere S 2 in Figure 4.1. We can see that on a sphere S 2 , a 0-simplex Then we can construct Čech complex and Rips complex. Let V denote the set of sensor locations in a WSN on S 2 with radius R and S = {s v , v ∈ V} denote the collection of sensing ranges of these sensors: for a location v,

[v 0 ] is a vertex , a 1-simplex [v 0 , v 1 ] is the shorter arc of the great circle passing through v 0 and v 1 , a 2-simplex [v 0 , v 1 , v 2 ] is a spherical triangle v 0 v 1 v 2 with its interior included. v 0 v 0 v 1 v 0 v 1 v 2 0-simplex 2-simplex 1-simplex
s v = {x ∈ S 2 : d(x, v) ≤ R s }.
According to Definition 2.7, the Čech complex of the WSN on sphere, denoted by ČRs (V), can be constructed as follows:

a k -simplex [v 0 , v 1 , • • • , v k ] belongs to ČRs (V) whenever ∩ k l=0 s v l = ∅.
Similarly, according to Definition 2.8, we consider here the metric space (S 2 , d), then the Rips complex, denoted by R Rc (V), can be constructed as follows:

a k -simplex [v 0 , v 1 , • • • , v k ] belongs to R Rc (V) whenever d(v l , v m ) ≤ R c for all 0 ≤ l < m ≤ k.
In addition, since we consider only coverage holes on the sphere S 2 , it is sufficient to construct 2-dimensional Čech complex and 2-dimensional Rips complex of the WSN, denoted as Č(2) Rs (V) and R

Rc (V) respectively. Figure 4.2 shows a WSN, its Čech complex and two Rips complexes for two different values of R c . Depending on the relation of R c and R s , the Rips complex and the Čech complex may be close or rather different. In this example, for R c = 2R s , the Rips complex sees the hole surrounded by 2, 3, 5, 6 as in the Čech complex whereas it is missed in the Rips complex for R c = 2.5R s . At the same time, the true coverage hole surrounded by 1, 2, 6 is missed in both Rips complexes. Theorem 2.2 in Chapter 2 presents the relationship between Čech complex and Rips complex in Euclidean space, but that is not true for sphere. So we derive the relationship between Č(2) Rs (V) and R

Rc (V) on sphere as follows.

Lemma 4.1. Let V denote the set of node locations in a WSN on S 2 with radius R, all nodes have the same sensing radius R s and communication radius

R c , R s ≪ R, R c ≪ R, then R (2)
Rc (V) ⊂ Č(2) Rs (V) ⊂ R (2) 2Rs (V), whenever R c ≤ R arccos([3 cos 2 (R s /R) -1]/2) (4.1)
Proof. The second inclusion is trivial because for any k-simplex

[v 0 , v 1 , • • • , v k ] ∈ Č(2)
Rs (V), it means the sensing ranges of these nodes have a common intersection, so the pairwise distance d(v i , v j ) ≤ 2R s for all 0 ≤ i < j ≤ k, which means

[v 0 , v 1 , • • • , v k ] ∈ R (2)
2Rs (V). As for the first inclusion, it is clear that R Rc (V) must also be in Č( 2)

Rs (V) since for any 1-simplex [v i , v j ] with distance d(v i , v j ) ≤ R c ≤ R arccos([3 cos 2 (R s /R)- 1]/2) < R arccos(2 cos 2 (R s /R) -1) = 2R s ,
it means that the sensing ranges of the two nodes have a common intersection. So we only need to prove that all 2-simplices in R

(2)

Rc (V) must be in Č(2) Rs (V).
It is equivalent to say that for any three nodes with pairwise great circle distance no larger than R c , their sensing ranges must have a common intersection.

Assume a 2-simplex

[v 0 , v 1 , v 2 ] ∈ R (2)
Rc (V), then the three nodes v 0 , v 1 and v 2 must determine a plane α. We consider the spherical cap on S2 cut off by the plane α. Since R c < R, the spherical cap must be on a hemisphere. It is easy to see that the intersection of the plane α and sphere S 2 is a circle c. Let O 1 be the center of circle c, O be the center of S 2 , P be the intersection of line OO 1 and S 2 .

Using spherical coordinates, we assume the point P has a spherical coordinate (R, 0, 0). P may be inside1 or outside the spherical triangle v 0 v 1 v 2 , which is shown in

v 0 , v 1 and v 2 , so [v 0 , v 1 , v 2 ] ∈ Č(2) Rs (V).
If P is outside the spherical triangle v 0 v 1 v 2 , as shown in Figure 4.3(a), it indicates that the spherical triangle v 0 v 1 v 2 must be contained in half of the spherical cap. Assume v 0 , v 1 and v 2 have spherical coordinates (R, θ, ϕ 0 ), (R, θ, ϕ 1 ) and (R, θ, ϕ 2 ), where θ ∈ (0, π/2), ϕ 0 < ϕ 1 < ϕ 2 , then we have ϕ 1ϕ 0 , ϕ 2ϕ 1 , ϕ 2ϕ 0 ∈ (0, π). Using d 01 , d 12 , d 02 to denote the pairwise great circle distances between v 0 , v 1 , v 2 , then according to the spherical law of consines, we have

cos(d 01 /R) = cos 2 θ + sin 2 θ cos(ϕ 1 -ϕ 0 ) (4.2) cos(d 12 /R) = cos 2 θ + sin 2 θ cos(ϕ 2 -ϕ 1 ) (4.3) cos(d 02 /R) = cos 2 θ + sin 2 θ cos(ϕ 2 -ϕ 0 ) (4.4)
In addition, we use σ to denote the angle between two arcs v0 v 1 and v0 v 2 , M to denote the middle point of the arc v0 v 2 and d 0M , d 1M to denote great circle distances between v 0 , v 1 and M . It can be seen Consequently

d 0M = d 02 /2.
cos d 1M R -cos d 0M R = cos d 01 R + cos d 12 R -cos d 02 R -1 2 cos(d 02 /(2R)) (4.8)
From (4.2), (4.3), (4.4) and (4.8), we get

cos d 1M R -cos d 0M R = sin 2 θ cos ϕ 2 -ϕ 0 2 sin ϕ 1 -ϕ 0 2 sin ϕ 2 -ϕ 1 2 cos d 02 2R (4.9) Since 0 < ϕ 1 -ϕ 0 , ϕ 2 -ϕ 1 , ϕ 2 -ϕ 0 < π and 0 < d 1M /R, d 0M /R, d 02 /R < π/2
, it can be obtained from (4.9) d 1M < d 0M ≤ R c /2 < R s , which means the point M is a common intersection of the sensing ranges of v 0 , v 1 and v 2 , so

[v 0 , v 1 , v 2 ] ∈ Č(2) Rs (V). It means all 2-simplices in R (2) Rc (V) must be in Č(2) Rs (V).
Consequently the first inclusion is proved.

According to (4.1), some relationships between Čech complex and Rips complex in terms of coverage holes can be derived as illustrated in the following corollaries.

Corollary 4.2. When R c ≤ R arccos([3 cos 2 (R s /R) -1]/2), if there is no hole in R (2)
Rc (V), there must be no hole in Č( 2)

Rs (V). Corollary 4.3. When R c ≥ 2R s , if there is a hole in R (2)
Rc (V), there must be a hole in Č( 2)

Rs (V). Corollary 4.4. When R arccos([3 cos 2 (R s /R) -1]/2) < R c < 2R s , there is no guarantee relation between R (2)
Rc (V) and Č(2) Rs (V) in terms of holes.

From the discussions above, a hole in a Č( 2)

Rs (V) not seen in a R (2)
Rc (V) must be bounded by a spherical triangle. Based on this observation, a formal definition of spherical triangular hole is given as follows.

Lemma 4.7. Let O be a point inside a spherical triangular hole and l denote the great circle distance between O and its closest neighbour, then

R s < l ≤ R arccos » [1 + 2 cos(R c /R)]/3.
The proof is similar as that of Lemma 4.1.

Since we assume nodes are distributed on S 2 according to a homogeneous Poisson point process with intensity λ, any point has the same probability to be inside a spherical triangular hole without considering border effect [START_REF] Bettstetter | How to achieve a connected ad hoc network with homogeneous range assignment: an analytical study with consideration of border effects[END_REF]. This probability in a homogeneous setting is also equal to the proportion of the area of spherical triangular holes.

We use spherical coordinates (R, θ, ϕ) to denote points on S 2 with radius R, where θ is polar angle and ϕ is azimuth angle. We consider the probability of the point N with spherical coordinates (R, 0, 0) being inside a spherical triangular hole. Since the communication radius of each sensor is at most R c , only the nodes within R c from the point N can contribute to the spherical triangle which bounds a spherical triangular hole containing N . Therefore, we only need to consider the Poisson point process constrained on the spherical cap C(N, R c ) which is also a homogeneous Poisson point process with intensity λ, where C(N, R c ) denotes the spherical cap centered at point N and the maximum great circle distance between N and points on the spherical cap is R c . We denote this process as Φ. In addition, T s (x, y, z) denotes the property that the point N is inside the spherical triangular hole bounded by the spherical triangle with points x, y, z as vertices. When n 0 , n 1 , n 2 are points of the process Φ, T s (n 0 , n 1 , n 2 ) is also used to denote the event that the spherical triangle formed by the nodes n 0 , n 1 , n 2 bounds a spherical triangular hole containing the point N . In addition, we use T ′ s (n 0 , n 1 , n 2 ) to denote the event that the nodes n 0 , n 1 , n 2 can not form a spherical triangle which bounds a spherical triangular hole containing the point N .

Let τ 0 = τ 0 (Φ) be the node in the process Φ which is closest to the point N . There are two cases for the point N to be inside a spherical triangular hole. The first case is that the node τ 0 can contribute to a spherical triangle which bounds a spherical triangular hole containing the point N . The second case is that the node τ 0 can not contribute to any spherical triangle which bounds a spherical triangular hole containing the point N but other three nodes can form a spherical triangle which bounds a spherical triangular hole containing the point N . So the probability that the point N is inside a spherical triangular hole can be defined as

p s (λ) = P{N is inside a spherical triangular hole} = P{ {n 0 ,n 1 ,n 2 }⊆Φ T s (n 0 , n 1 , n 2 )} = P{ {n 1 ,n 2 }⊆Φ\{τ 0 (Φ)} T s (τ 0 , n 1 , n 2 )} + p sec s (λ) (4.10)
where

p sec s (λ) = P{ {n i1 ,••• ,n i5 }⊆Φ\{τ 0 (Φ)} T s (n i1 , n i2 , n i3 ) | T ′ s (τ 0 , n i4 , n i5 )}
denotes the probability that the node τ 0 can not contribute to any spherical triangle which bounds a spherical triangular hole containing the point N but other three nodes can form a spherical triangle which bounds a spherical triangular hole containing the point N .

Case

0 < R c ≤ R arccos([3 cos 2 (R s /R) -1]/2) Theorem 4.8. When 0 < R c ≤ R arccos([3 cos 2 (R s /R) -1]/2), p s (λ) = 0.
Proof. According to (4.1), when

0 < R c ≤ R arccos([3 cos 2 (R s /R) -1]/2), R (2)
Rc (V) ⊂ Č(2)
Rs (V), it means that every 2-simplex in R

Rc (V) must be in Č( 2) Rs (V), so there is no spherical triangular holes which means p s (λ) = 0.

Case R arccos([3 cos

2 (R s /R) -1]/2) < R c ≤ 2R s Theorem 4.9. When R arccos([3 cos 2 (R s /R) -1]/2) < R c ≤ 2R s , we have p sl (λ) < p s (λ) < p su (λ), where p sl (λ) = 2πλ 2 R 4 θ 0u Rs/R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )dθ 1 (4.11) and p su (λ) = 2πλ 2 R 4 θ 0u Rs/R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )dθ 1 + p sec s (λ) (4.12)
and

θ 0u = arccos » [1 + 2 cos(R c /R)]/3 ϕ m (θ 0 ) = arccos[(cos(R c /R) -cos 2 θ 0 )/ sin 2 θ 0 ] θ 1u (θ 0 , ϕ s1 ) = min{θ 1u1 (θ 0 , ϕ s1 ), θ 1u2 (θ 0 , ϕ s1 )} θ 1u1 (θ 0 , ϕ s1 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 ϕ s1 ò + arctan(cos ϕ s1 tan θ 0 ) θ 1u2 (θ 0 , ϕ s1 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 (ϕ s1 -ϕ m (θ 0 )) ò + arctan(cos(ϕ s1 -ϕ m (θ 0 )) tan θ 0 ) |C(N, Rθ 0 )| = 2πR 2 (1 -cos θ 0 ) |S + (θ 0 , ϕ s1 )| = ϕ s1 2π-ϕm(θ 0 ) θ 1u (θ 0 ,ϕ) θ 0 R 2 sin θdθdϕ |S -(θ 0 , θ 1 , ϕ s1 )| = ϕm(θ 0 ) ϕ 2l (θ 0 ,θ 1 ,ϕ s1 ) θ 2u (θ 0 ,θ 1 ,ϕ s1 ,ϕ 2 ) θ 0 R 2 sin θ 2 dθ 2 dϕ 2 ϕ 2l (θ 0 , θ 1 , ϕ s1 ) = ϕ s1 -arccos cos(R c /R) -cos θ 1 cos θ 0 sin θ 1 sin θ 0 θ 2u (θ 0 , θ 1 , ϕ s1 , ϕ 2 ) = min{θ 1u1 (θ 0 , ϕ 2 ), θ 2u2 (θ 0 , θ 1 , ϕ s1 , ϕ 2 )} θ 2u2 (θ 0 , θ 1 , ϕ s1 , ϕ 2 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 (ϕ 2 -ϕ s1 ) ò + arctan(cos(ϕ 2 -ϕ s1 ) tan θ 1 )
p sec s (λ) is obtained by simulations.

Proof. We first prove the lower bound. It can be obtained from (4.10) that

p s (λ) > P{ {n 1 ,n 2 }⊆Φ\{τ 0 (Φ)} T s (τ 0 , n 1 , n 2 )}
So for the lower bound, we only consider the first case that the closest node τ 0 must contribute to a spherical triangle which bounds a spherical triangular hole containing the point N .

Using spherical coordinates, we assume the closest node τ 0 lies on (R, α 0 , 0) and use |S| to denote the area of the set S, then we can get the distribution of α 0 as

F α 0 (θ 0 ) = P (α 0 ≤ θ 0 ) = 1 -e -λ|C(N,Rθ 0 )| (4.13)
since the event α 0 > θ 0 means that the spherical cap C(N, Rθ 0 ) does not contain any nodes from the process, which is given by the Poisson probability e -λ|C(N,Rθ 0 )| .

Furthermore, |C(N, Rθ 0 )| can be given as

|C(N, Rθ 0 )| = θ 0 0 2π 0 R 2 sin θdϕdθ = 2πR 2 (1 -cos θ 0 ) (4.14)
From (4.13) and (4.14), we can get the density of τ 0

F α 0 (dθ 0 ) = 2πλR 2 sin θ 0 e -λ|C(N,Rθ 0 )| dθ 0 (4.15)
The integration range for θ 0 can be easily obtained. According to Lemma 4.7, we have

R s < Rθ 0 ≤ R arccos » [1 + 2 cos(R c /R)]/3, so R s /R < θ 0 ≤ θ 0u = arccos » [1 + 2 cos(R c /R)]/3.
Therefore the probability of the first case can be given as

P{ {n 1 ,n 2 }⊆Φ\{τ 0 (Φ)} T s (τ 0 , n 1 , n 2 )} = θ 0u Rs/R P{ {n 1 ,n 2 }⊆Φ ′ θ 0 T s ((R, θ 0 , 0), n 1 , n 2 )}F α 0 (dθ 0 ) (4.16)
where Φ ′ θ 0 is the restriction of Φ in C(N, R c )\C(N, Rθ 0 ). Once the node τ 0 is determined, the other two nodes must lie in the different half spaces: one in H + = R + × (0, π/2) × (π, 2π) and the other in H -= R + × (0, π/2) × (0, π). Assume n 1 lies in H + and n 2 lies in H -. Since the great circle distance to τ 0 is at most R c , n 1 and n 2 must also lie in the spherical cap C(τ 0 , R c ). Furthermore, the great circle distance to the point N is at most R c and larger than Rα 0 , they should also lie in the region A = C(N, R c )\C(N, Rα 0 ). Therefore, n 1 must lie in

G + = H + C(τ 0 , R c ) A and n 2 must lie in G -= H -C(τ 0 , R c ) A.
In addition, considering the great circle distance between n 1 and n 2 should be at most R c and the point N should be inside the spherical triangle formed by τ 0 , n 1 and n 2 , n 1 must lie in the shadow region Ordering the nodes in A + by increasing azimuth angle so that τ 1 = (R, θ 1 , ϕ s1 ) has the smallest azimuth angle ϕ s1 . And assume the nodes τ 0 , τ 1 and another node τ 2 ∈ G -can form a spherical triangle which bounds a spherical triangular hole containing the point N , then τ 2 must lie to the right of the great circle passing through τ 1 and N , denoted by H + (ϕ s1 ) which contains all points with azimuth angle ϕ ∈ (ϕ s1π, ϕ s1 ). In addition, the great circle distance to τ 1 is no larger than R c ,

A + = G + C(M 2 , R c ), shown in
S -(τ 0 , τ 1 ) = S -(α 0 , θ 1 , ϕ s1 ) = G -H + (ϕ s1 ) C(τ 1 , R c )
Here we need to obtain the density of node τ 1 . Considering the way τ 1 was defined, there should be no nodes with an azimuth angle less than ϕ s1 in A + , that is to say no nodes are in the region

S + (τ 0 , τ 1 ) = S + (α 0 , ϕ s1 ) = A + H + (ϕ s1 )
Since the intensity measure of the Poisson point process in spherical coordinates is λR 2 sin θdθdϕ, the density F τ 1 of τ 1 can be given as

F τ 1 (dθ 1 , dϕ s1 ) = λR 2 sin θ 1 e -λ|S + (α 0 ,ϕ s1 )| dθ 1 dϕ s1 (4.17)
Then we derive the integration domain D(α 0 ) with respect to parameters (θ 1 , ϕ s1 ). Assume the point M 2 has the spherical coordinate (R, α 0 , ϕ m ), ϕ m ∈ (0, π). Since the great circle distance between τ 0 and M 2 is R c , then according to the spherical law of consines, we have cos Rc R = cos 2 α 0 + sin 2 α 0 cos ϕ m ⇒ ϕ m (α 0 ) = arccos[(cos Rc Rcos 2 α 0 )/(sin 2 α 0 )]. It can be seen that points M 1 and Q have the spherical coordinates (R, α 0 , 2π-ϕ m (α 0 )) and (R, α 0 , 2ϕ m (α 0 )) respectively, where Q is one intersec- ] + arctan(cos ϕ t tan α 0 ). Similarly, assume any point with great circle distance R c to M 2 has the spherical coordinate (R,

θ ′ t , ϕ ′ t ), we have θ ′ t (α 0 , ϕ ′ t ) = arccos[ cos(Rc/R) √ 1-sin 2 α 0 sin 2 (ϕ ′ t -ϕm(α 0 )) ] + arctan(cos(ϕ ′ t -ϕ m (α 0 )) tan α 0 ). Then the integration range for θ 1 is [θ 0 , θ 1u (α 0 , ϕ s1 )], where θ 1u (α 0 , ϕ s1 ) = min {θ 1u1 (α 0 , ϕ s1 ), θ 1u2 (α 0 , ϕ s1 )}, θ 1u1 (α 0 , ϕ s1 ) = θ t (α 0 , ϕ s1 ) and θ 1u2 (α 0 , ϕ s1 ) = θ ′ t (α 0 , ϕ s1 ). Furthermore, |S + (α 0 , ϕ s1 )| can be expressed as |S + (α 0 , ϕ s1 )| = ϕ s1 2π-ϕm(α 0 ) θ 1u (α 0 ,ϕ) α 0 R 2 sin θdθdϕ (4.18)
Assume only τ 0 , τ 1 and nodes in S -(τ 0 , τ 1 ) can contribute to the spherical triangle which bounds a spherical triangular hole containing the point N , we can get a lower bound of the probability that the point N is inside a spherical triangular hole. It is a lower bound because it is possible that τ 1 can not contribute to a spherical triangle which bounds a spherical triangular hole containing point N , but some other nodes with higher azimuth angles in the region A + can contribute to such a spherical triangle. For example, in Figure 4.6, if there is no node in S -but there are some nodes in S ′-, then τ 1 can not contribute to any spherical triangle which bounds a spherical triangular hole containing point N , but τ ′ 1 can form such a spherical triangle with τ 0 and another node in S ′-.

Based on the assumption, we have

P{ {n 1 ,n 2 }⊆Φ ′ θ 0 T s ((R, θ 0 , 0), n 1 , n 2 )} >P{ n 2 ⊆Φ ′ θ 0 S -(τ 0 ,τ 1 ) T s ((R, θ 0 , 0), τ 1 , n 2 )} = D(θ 0 ) P{ n 2 ⊆Φ ′ θ 0 S -(θ 0 ,θ 1 ,ϕ s1 ) T s ((R, θ 0 , 0), (R, θ 1 , ϕ s1 ), n 2 )}F τ 1 (dθ 1 , dϕ s1 ) = D(θ 0 ) P{Φ ′ θ 0 (S -(θ 0 , θ 1 , ϕ s1 )) > 0}F τ 1 (dθ 1 , dϕ s1 ) = D(θ 0 ) (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )F τ 1 (dθ 1 , dϕ s1 ) (4.19)
where |S -(θ 0 , θ 1 , ϕ s1 )| can be expressed as

|S -(θ 0 , θ 1 , ϕ s1 )| = ϕm(θ 0 ) ϕ 2l (θ 0 ,θ 1 ,ϕ s1 ) θ 2u (θ 0 ,θ 1 ,ϕ s1 ,ϕ 2 ) θ 0 R 2 sin θ 2 dθ 2 dϕ 2 (4.20)
and

ϕ 2l (θ 0 , θ 1 , ϕ s1 ) = ϕ s1 -arccos cos(R c /R) -cos θ 1 cos θ 0 sin θ 1 sin θ 0 θ 2u (θ 0 , θ 1 , ϕ s1 , ϕ 2 ) = min{θ 1u1 (θ 0 , ϕ 2 ), θ 2u2 (θ 0 , θ 1 , ϕ s1 , ϕ 2 )} θ 2u2 (θ 0 , θ 1 , ϕ s1 , ϕ 2 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 (ϕ 2 -ϕ s1 ) ò + arctan(cos(ϕ 2 -ϕ s1 ) tan θ 1 )
Therefore, from (4.15), (4.16), (4.17) and (4.19), the lower bound shown in (4.11) can be derived.

Next we will prove the upper bound. As discussed in Section 4.3.1, there are two cases for the point N being inside a spherical triangular hole. As for the second case that the closest node τ 0 can not but some other nodes can contribute to a spherical triangle which bounds a spherical triangular hole containing the point N , we also get it by simulations as the case on plane. Simulation results show that this probability is less than 0.003% at any intensity λ when R arccos([3 cos 2 (R s /R)-1]/2) < R c ≤ 2R s . So we still focus on the probability of the first case.

(R s /R) - 1]/2) < R c ≤ 2R s
For the lower bound, we only considered the case that τ 1 contributes to a spherical triangle which bounds a spherical triangular hole containing point N . For the upper bound, we need to further consider the case that τ 1 can not but some other nodes in A + can contribute to such a spherical triangle, shown in Figure 4.6. Assume the node

τ ′ 1 = (R, θ ′ 1 , ϕ ′ s1
) with the second smallest azimuth angle in A + can contribute to such a spherical triangle, it means that there is no node in S -(α 0 , θ 1 , ϕ s1 ) but there is at least one node in the region

S ′-(α 0 , θ 1 , ϕ s1 , θ ′ 1 , ϕ ′ s1 ) = S -(α 0 , θ ′ 1 , ϕ ′ s1 )\S -(α 0 , θ 1 , ϕ s1 ).
Then the density of the pair (τ 1 , τ ′ 1 ) is given as

F τ 1 ,τ ′ 1 (dθ 1 , dϕ s1 , dθ ′ 1 , dϕ ′ s1 ) = λ 2 R 4 sin θ 1 sin θ ′ 1 e -λ|S + (α 0 ,ϕ ′ s1 )| dθ 1 dϕ s1 dθ ′ 1 dϕ ′ s1 (4.21)
The probability that τ 1 can not but τ ′ 1 can form a spherical triangle which bounds a spherical triangular hole containing point N with τ 0 and another node in S ′-(α 0 , θ 1 , ϕ s1 , θ ′ 1 , ϕ ′ s1 ) can be given as

P{ {n 3 ,n 4 }⊆Φ ′ θ 0 S -(τ 0 ,τ ′ 1 ) T s ((R, θ 0 , 0), τ ′ 1 , n 4 ) | T ′ s ((R, θ 0 , 0), τ 1 , n 3 )} = P{Φ ′ θ 0 (S -(θ 0 , θ 1 , ϕ s1 )) = 0} × P{Φ ′ θ 0 (S ′-(θ 0 , θ 1 , ϕ s1 , θ ′ 1 , ϕ ′ s1 )) > 0}F τ 1 ,τ ′ 1 (dθ 1 , dϕ s1 , dθ ′ 1 , dϕ ′ s1 ) = e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| × (1 -e -λ|S ′-(θ 0 ,θ 1 ,ϕ s1 ,θ ′ 1 ,ϕ ′ s1 )| )F τ 1 ,τ ′ 1 (dθ 1 , dϕ s1 , dθ ′ 1 , dϕ ′ s1 ) (4.22)
As we can see from Figure 4.6, as long as τ ′ 1 has a higher polar angle than τ 1 has, the sum of

|S -(α 0 , θ 1 , ϕ s1 )| and |S ′-(α 0 , θ 1 , ϕ s1 , θ ′ 1 , ϕ ′ s1 )| will be always smaller than |S -(α 0 , α 0 , ϕ s1 )|.
Therefore we can get from (4.22)

P{ {n 3 ,n 4 }⊆Φ ′ θ 0 S -(τ 0 ,τ ′ 1 ) T s ((R, θ 0 , 0), τ ′ 1 , n 4 ) | T ′ s ((R, θ 0 , 0), τ 1 , n 3 )} < (e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )F τ 1 ,τ ′ 1 (dθ 1 , dϕ s1 , dθ ′ 1 , dϕ ′ s1 ) (4.23)
Let S ′+ (θ 0 , ϕ s1 , ϕ ′ s1 ) = S + (θ 0 , ϕ ′ s1 )\S + (θ 0 , ϕ s1 ), then

λR 2 sin θ ′ 1 e -λ|S ′+ (θ 0 ,ϕ s1 ,ϕ ′ s1 )| dθ ′ 1 dϕ ′ s1 = 1 -e -λ|A + \S + (θ 0 ,ϕ s1 )| < 1 (4.24)
It is the complement of the probability that no node is in the region A + \S + (θ 0 , ϕ s1 ).

From (4.19), (4.21), (4.23) and (4.24), we can obtain

P{ n 2 ⊆Φ ′ θ 0 S -(τ 0 ,τ 1 ) T s ((R, θ 0 , 0), τ 1 , n 2 )} + P{ {n 3 ,n 4 }⊆Φ ′ θ 0 S -(τ 0 ,τ ′ 1 ) T s ((R, θ 0 , 0), τ ′ 1 , n 4 ) | T ′ s ((R, θ 0 , 0), τ 1 , n 3 )} < D(θ 0 ) (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )F τ 1 (dθ 1 , dϕ s1 ) (4.25)
where |S -(θ 0 , θ 0 , ϕ s1 )| has the similar expression as (4.20).

Similarly, we can further consider the case that neither of τ 1 and τ ′ 1 can contribute to a spherical triangle which bounds a spherical triangular hole containing point N , but other nodes with even higher azimuth angle can contribute to such a spherical triangle. In this way, we can get the same result as (4.25).

Therefore, it can be derived that

P{ {n 1 ,n 2 }⊆Φ ′ θ 0 T s ((R, θ 0 , 0), n 1 , n 2 )} < D(θ 0 ) (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )F τ 1 (dθ 1 , dϕ s1 ) (4.
p l (λ) = 2πλ 2 R 4 ß Rc 2R Rs R sin θ 0 dθ 0 2π π dϕ s1 θ ′ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )dθ 1 + θ 0u Rc/2R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 e -λ|C(N,Rθ 0 )| × e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )dθ 1 ™ (4.27) and p u (λ) = 2πλ 2 R 4 ß Rc 2R Rs R sin θ 0 dθ 0 2π π dϕ s1 θ ′ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 × e -λ|C(N,Rθ 0 )| e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )dθ 1 + θ 0u Rc/2R sin θ 0 dθ 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 θ 1u (θ 0 ,ϕ s1 ) θ 0 sin θ 1 e -λ|C(N,Rθ 0 )| × e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 0 ,ϕ s1 )| )dθ 1 ™ + p sec s (λ) (4.28)
and

θ ′ 1u (θ 0 , ϕ s1 ) = min{θ 1u1 (θ 0 , ϕ s1 ), θ ′ 1u2 (θ 0 , ϕ s1 )} θ ′ 1u2 (θ 0 , ϕ s1 ) = arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 ϕ s1 ò -arctan(cos ϕ s1 tan θ 0 )
p sec s (λ) is obtained by simulations.

We can use the same method as in Section 4.3.3 to get the lower and upper bounds, shown in (4.27) and (4.28) respectively. But we need to consider two situations

R s /R < θ 0 ≤ R c /(2R) and R c /(2R) < θ 0 ≤ θ 0u = arccos » [1 + 2 cos(R c /R)]/3.

Case R → ∞

Intuitively, when R → ∞, the cases on sphere should be the same as those on plane, which will be proved in this section. We choose the case R arccos([3 cos 2 (R s /R) -1]/2) < R c ≤ 2R s on sphere and the case √ 3 < γ = R c /R s ≤ 2 on plane for proof. For other cases, the proof is similar. For convenience, let

θ 0 = r 0 /R, θ 1 = r 1 /R, ϕ s1 = π + ϕ 1 . Lemma 4.11. lim R→∞ R arccos([3 cos 2 (R s /R) -1]/2) = √ 3R s
Proof. According to l'Hôpital's rule, we have

lim R→∞ R arccos([3 cos 2 (R s /R) -1]/2) =R s lim x→0 arccos([3 cos 2 (x) -1]/2) x (let x = R s /R) =R s lim x→0 3 cos x sin x » 1 -([3 cos 2 (x) -1]/2) 2 =R s lim x→0 6 cos x sin x » (3 -3 cos 2 x)(1 + 3 cos 2 x) = √ 3R s Lemma 4.11 means that when R → ∞, the condition R arccos([3 cos 2 (R s /R) - 1]/2) < R c ≤ 2R s is equivalent to the condition √ 3 < γ = R c /R s ≤ 2.
Lemma 4.12.

lim R→∞ Rθ 0u = lim R→∞ R arccos » [1 + 2 cos(R c /R)]/3 = R c / √ 3
Proof. According to l'Hôpital's rule, we have

lim R→∞ R arccos » [1 + 2 cos(R c /R)]/3 =R c lim x→0 arccos » [1 + 2 cos(x)]/3 x (let x = R c /R) =R c lim x→0 1 » 3 -[1 + 2 cos(x)] sin x » 1 + 2 cos(x) =R c / √ 3 lim x→0 sin x √ 2 -2 cos x = R c / √ 3 Lemma 4.13. Let θ 0 = r 0 /R, then we have lim R→∞ ϕ m (θ 0 ) = lim R→∞ arccos[(cos(R c /R) -cos 2 θ 0 )/ sin 2 θ 0 ] = π -2 arccos(R c /(2r 0 )) = π -ϕ l (r 0 )
where ϕ l (r 0 ) is shown in (3.5).

Proof. According to l'Hôpital's rule, we have

lim R→∞ arccos[(cos(R c /R) -cos 2 θ 0 )/ sin 2 θ 0 ] = arccos( lim R→∞ (cos(R c /R) -cos 2 (r 0 /R))/ sin 2 (r 0 /R)) = arccos( lim R→∞ R c /R 2 sin(R c /R) -2r 0 /R 2 sin(r 0 /R) cos(r 0 /R) -2r 0 /R 2 sin(r 0 /R) cos(r 0 /R) ) = arccos( lim R→∞ 1 - R c sin(R c /R 2r 0 sin(r 0 /R) ) = arccos(1 -R 2 c /(2r 2 0 )) Meanwhile, we have cos(π -2 arccos(R c /(2r 0 ))) = 1 -R 2 c /(2r 2 0 ) and 0 ≤ π - 2 arccos(R c /(2r 0 )) ≤ π, so π -2 arccos(R c /(2r 0 )) = arccos(1 -R 2 c /(2r 2 0 )).
As from (3.5), we know ϕ l (r 0 ) = 2 arccos(R c /(2r 0 )), Consequently

lim R→∞ arccos[(cos(R c /R) -cos 2 θ 0 )/ sin 2 θ 0 ] = π -2 arccos(R c /(2r 0 )) = π -ϕ l (r 0 ) Lemma 4.14. Let θ 0 = r 0 /R, ϕ s1 = π + ϕ 1 , we have lim R→∞ Rθ 1u1 (θ 0 , ϕ s1 ) = lim R→∞ R(arccos ï cos(R c /R) » 1 -sin 2 θ 0 sin 2 ϕ s1 ò + arctan(cos ϕ s1 tan θ 0 )) = » R 2 c -r 2 0 sin 2 ϕ 1 -r 0 cos ϕ 1
Proof. Still using l'Hôpital's rule, we have

lim R→∞ R(arccos ï cos(R c /R)/ » 1 -sin 2 θ 0 sin 2 ϕ s1 ò + arctan(cos ϕ s1 tan θ 0 )) = lim R→∞ arccos ï cos(R c /R)/ » 1 -sin 2 (r 0 /R) sin 2 ϕ s1 ò 1/R + r 0 cos ϕ s1 = lim R→∞ R 2 … 1 - cos 2 (Rc/R) 1-sin 2 (r 0 /R) sin 2 ϕ s1 ( R c R 2 sin R c R - r 0 R 2 cos R c R sin r 0 R cos r 0 R sin 2 ϕ s1 ) + r 0 cos ϕ s1 = lim R→∞ R c sin(R c /R) -r 0 sin(r 0 /R) sin 2 ϕ s1 » sin 2 (R c /R) -sin 2 (r 0 /R) sin 2 ϕ s1 + r 0 cos ϕ s1 = lim R→∞ R 2 c -r 2 0 sin 2 ϕ s1 R » sin 2 (R c /R) -sin 2 (r 0 /R) sin 2 ϕ s1 + r 0 cos ϕ s1 = » R 2 c -r 2 0 sin 2 ϕ s1 + r 0 cos ϕ s1 = » R 2 c -r 2 0 sin 2 ϕ 1 -r 0 cos ϕ 1
According to Lemma 4.13 and 4.14, we can get the following lemma.

Lemma 4.15. Let θ 0 = r 0 /R, ϕ s1 = π + ϕ 1 , we have

lim R→∞ Rθ 1u2 (θ 0 , ϕ s1 ) = lim R→∞ R(arccos ï cos(R c /R) » 1 -sin 2 θ 0 sin 2 (ϕ s1 -ϕ m (θ 0 )) ò + arctan(cos(ϕ s1 -ϕ m (θ 0 )) tan θ 0 )) = » R 2 c -r 2 0 sin 2 (ϕ 1 + ϕ l (r 0 )) + r 0 cos(ϕ 1 + ϕ l (r 0 ))
According to Lemma 4.14 and 4.15, we obtain the lemma as follows.

Lemma 4.16.

Let θ 0 = r 0 /R, ϕ s1 = π + ϕ 1 , we have lim R→∞ Rθ 1u (θ 0 , ϕ s1 ) = lim R→∞ R min{θ 1u1 (θ 0 , ϕ s1 ), θ 1u2 (θ 0 , ϕ s1 )} = R 1 (r 0 , ϕ 1 )
where R 1 (r 0 , ϕ 1 ) is shown in (3.7). Proof. From (4.18), we have

|S + (θ 0 , ϕ s1 )| = ϕ s1 2π-ϕm(θ 0 ) θ 1u (θ 0 ,ϕ) θ 0 R 2 sin θdθdϕ
Let θ = r/R and ϕ = π + ϕ ′ , then use Lemma 4.13 and 4.16, we get

lim R→∞ |S + (θ 0 , ϕ s1 )| = lim R→∞ ϕ s1 -π π-ϕm(θ 0 ) Rθ 1u (θ 0 ,π+ϕ ′ ) Rθ 0 R sin(r/R)drdϕ ′ = ϕ 1 ϕ l (r 0 ) R 1 (r 0 ,ϕ ′ ) r 0 rdrdϕ ′ = |S + (r 0 , ϕ 1 )|
Similarly, we can get the following lemma. From the lemmas above, we can get the theorem as follows. Proof.

Let θ 0 = r 0 /R, θ 1 = r 1 /R, ϕ s1 = π + ϕ 1 .
First, from (4.14), it is easy to check

lim R→∞ |C(N, Rθ 0 )| = lim R→∞ 2πR 2 (1 -cos(r 0 /R)) = πr 2 0
From (3.5) and (3.6), we can get ϕ u (r 0 ) = π -2ϕ l (r 0 ).

Then, using the lemmas above, we can obtain from (4.11)

lim R→∞ p sl (λ) = lim R→∞ 2πλ 2 Rθ 0u Rs R sin r 0 R dr 0 2ϕm(θ 0 ) 2π-ϕm(θ 0 ) dϕ s1 Rθ 1u (θ 0 ,ϕ s1 ) Rθ 0 R sin r 1 R × e -λπr 2 0 e -λ|S + (θ 0 ,ϕ s1 )| (1 -e -λ|S -(θ 0 ,θ 1 ,ϕ s1 )| )dr 1 = 2πλ 2 Rc/ √ 3 Rs r 0 dr 0 ϕu(r 0 ) ϕ l (r 0 ) dϕ 1 R 1 (r 0 ,ϕ 1 ) r 0 e -λπr 2 0 × e -λ|S + (r 0 ,ϕ 1 )| (1 -e -λ|S -(r 0 ,r 1 ,ϕ 1 )| )r 1 dr 1 = p 2dl (λ)
The upper bound can be proved similarly.

Performance evaluation

In this section, simulation settings are first given. Then simulation results are compared with analytical lower and upper bounds under different settings of R s , R c , R.

Simulation settings

A sphere centered at the origin with radius R is considered in the simulations. The probability of the point with spherical coordinate (R, 0, 0) being inside a spherical triangular hole is computed. Sensors are randomly distributed on the sphere according to a homogeneous Poisson point process with intensity λ. The sensing radius R s of each node is set to be 10 meters and communication radius R c is chosen from 20 to 30 meters with interval of 2 meters. Let γ = R c /R s , then γ ranges from 2 to 3 with interval of 0.2. In addition, λ is selected from 0.001 to 0.020 with interval of 0.001. For each pair of (λ, γ), 10 7 simulations are run to check whether the point with spherical coordinate (R, 0, 0) is inside a spherical triangular hole.

Impact of R s and R c

As illustrated in Section 4.2, R s ≪ R and R c ≪ R, here we choose R = 10R s to analyse the impact of R s and R c on the probability of any point being inside a spherical triangular hole. Under this configuration, the probability p s (λ) obtained by simulations is presented with the lower and upper bounds in It can be seen that for any value of γ, p s (λ) has a maximum at a threshold value λ c of the intensity. As a matter of fact, for λ ≤ λ c , the number of nodes is small. Consequently the probability of any point being inside a spherical triangular hole is relatively small too. With the increase of λ, the connectivity between nodes becomes stronger. As a result, the probability of any point being inside a spherical triangular hole increases. However, when the intensity reaches the threshold value, the probability is up to its maximum. p s (λ) decreases for λ ≥ λ c . The simulations also show that λ c decreases with the increase of γ.

On the other hand, it can be seen from Figure 4.8(a) and 4.8(b) that for a fixed intensity λ, p s (λ) increases with the increases of γ. That is because when R s is fixed, the larger R c is, the higher is the probability of each spherical triangle containing a coverage hole. Furthermore, the maximum probability increases quickly with γ ranging from 2.0 to 3.0. These results can also provide some insights for planning of WSNs, which will be discussed in Section 4.4.4.

Finally, it can be found in Figure 4.8(a) that the probability obtained by simulations is very well consistent with the lower bound. The maximum difference between them is about 0.5%. Figure 4.8(b) shows that probability obtained by simulations is also consistent with the upper bound. The maximum difference between them is about 3%.

Impact of R

Although we assume R s ≪ R and R c ≪ R, to better understand the impact of R on the probability of any point being inside a spherical triangular hole, we choose R to be 5R s , 10R s and 100R s . In addition, we also want to know the difference of the probability under spherical and 2D planar cases. Therefore, simulation results, lower and upper bounds of the probability under spheres with radii 5R s , 10R s , 100R s and 2D plane are shown in Figure 4.9(a), 4.9(b) and 4.9(c) respectively. Simulation results for p sec s (λ) under spheres with radii 5R s , 10R s , 100R s and 2D plane are shown in Figure 4.10. The detailed values are presented in Appendix B.

It can be seen from Figure 4.9 that simulations results, lower and upper bounds under spheres with radii 5R s , 10R s , 100R s and 2D plane are very close with each other. More precisely, the maximum difference of simulations results under spheres with radii 5R s and 10R s is about 0.045%, which is about 0.06% under spheres with radii 5R s and 100R s and is about 0.03% under spheres with radii 10R s and 100R s . In addition, the maximum differences of simulation results between 2D planar case and spherical cases with radii 5R s , 10R s , 100R s are 0.05%, 0.03% and 0.02% respectively. It means the larger the radius of sphere is, the more closer are the simulation results under sphere and 2D plane, it is because the larger the radius of sphere is, the more likely of the local of each node on the sphere to be planar.

With respect to lower and upper bounds, it is found that under any two spheres with radii 5R s , 10R s , 100R s , the maximum difference of lower and upper bounds are 0.06% and 0.12% respectively. Furthermore, under spheres with radii 5R s , 10R s , 100R s and 2D plane, the maximum difference of lower bounds is also 0.06%, and that of upper bounds is also 0.12%. More importantly, under sphere with radius 100R s and 2D plane, the maximum difference of lower bounds is 5 × 10 -6 and that of upper bounds is 2.5 × 10 -5 . It means the probabilities under cases of sphere with radius 100R s and 2D plane are nearly the same, which is quite logical since when the radius of sphere is much more larger than the sensing radius of any node, the local of any node can be considered to be planar.

It can be further found that under above cases, the maximum differences of simulation results, lower and upper bounds are all so small that they can be neglected. Consequently, it also means that the radius of sphere has little impact on the probability of any point on the sphere to be inside a spherical triangular hole.

Discussions on applications

Similar to the case on plane, our analytical results can also be used for planning of WSNs. For example, a WSN is used to monitor a mountain and the ratio γ = 2, according to the analytical upper bounds, we can see that the maximum proportion of the area of spherical triangular holes under γ = 2 is about 0.06 %, which can be neglected. It means that as long as the surface of mountain can be spherically triangulated by nodes, we can say the mountain is covered. But if γ = 3 and at least 95% of the surface of the mountain should be covered, then it means that the proportion of the area of spherical triangular holes can be at most 5%. From the analytical upper bounds of γ = 3, it can be seen that when the intensity λ = 0.009, the upper bound is about 5%, so in order to cover at least 95% of the mountain, the intensity of nodes should be larger than 0.009. Furthermore, our results can also be used in the scenarios when using satellite to cover the whole earth.

Chapter summary

In this chapter, we consider the accuracy of homology based coverage hole detection on sphere. First, the relationship between Čech complex and Rips complex on sphere is derived, which is different from that on plane. After that, the situations when Rips complex may miss coverage holes are identified and we find that the holes missed by Rips complex are always bounded by a spherical triangle. So we define them to be spherical triangular holes and use the proportion of the area of spherical triangular holes to evaluate the accuracy of homology based coverage hole detection on sphere. We consider a homogeneous case that nodes are randomly distributed on a sphere according to a homogeneous Poisson point process. Under such a setting and without considering border effect, the proportion of the area of spherical triangular holes is equivalent to the probability of any point on the sphere being inside a spherical triangular hole. Based on that, three different cases are considered and for each case, the closed form expressions for the lower and upper bounds of the probability are derived. Simulation results are well consistent with the analytical bounds. More importantly, it is shown that the radius of sphere has little impact on the probability as long as it is much larger than communication and sensing radii of each sensor.

Chapter 5

Graph based Distributed Coverage Hole Detection

Introduction

For triangular holes, we have computed the proportion of their area to evaluate the accuracy of homology based coverage hole detection approaches in Chapter 3. For non-triangular holes, we aim to design algorithms to detect them. As discussed in Section 2.1.3, graph based approaches usually only detect boundary nodes without discovering boundary cycles. In this chapter, we aim to design a graph based algorithm to find boundary cycles of non-triangular coverage holes in a WSN. In this algorithm, we design a method to detect boundary nodes by checking whether there exists a Hamiltonian cycle in their neighbour graphs. After that, some nodes are randomly selected to initiate the process to find boundary cycles. It is possible that some of the found cycles are not minimum or bound the same coverage holes, so it is necessary to make some choices among these cycles. Comparing our algorithm with a location based approach, we find that our algorithm can accurately discover the boundary cycles of more than 95% coverage holes when the intensity is low.

Models and assumptions

Consider a collection of stationary sensors deployed randomly on a planar target field. As usual, isotropic radio propagation is assumed. Each sensor monitors a region within a circle of radius R s and may communicate with other sensors within a circle of radius R c .

In addition, some other assumptions are as follows.

1. There are sensors located on the external boundary of the target field. They are known as fence sensors and other sensors are referred to as internal sensors. Each fence sensor has two fence neighbours. This is also the general assumption in many homology based algorithms [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] Vin De Silva | Blind swarms for coverage in 2-d[END_REF][START_REF] De | Coverage in sensor networks via persistent homology[END_REF][START_REF] Tahbaz | Distributed coverage verification in sensor networks without location information[END_REF].

2. Although sensors are not aware of their locations, every sensor can know whether it is a fence or an internal node by using the mechanisms presented in [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF] or other methods as in [START_REF] Dong | Distributed coverage in wireless ad hoc and sensor networks by topological graph approaches[END_REF]. In fact, it is a conventional assumption adopted by many existing range based methods [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF][START_REF] Gaurav | Lifetime and coverage guarantees through distributed coordinate-free sensor activation[END_REF] or connectivity based methods [START_REF] Dong | Distributed coverage in wireless ad hoc and sensor networks by topological graph approaches[END_REF][START_REF] Tahbaz | Distributed coverage verification in sensor networks without location information[END_REF].

3. Internal sensors are distributed on the planar target field according to a homogeneous Poisson point process with intensity λ.

4. Each sensor has an unique ID.

The network has only one connected component.

Base on these assumptions, we can use a graph G(V, E) to represent the WSN, where V denotes all the nodes of WSN, for any two nodes, if they can communicate with each other, an edge connects them in the graph. For any node v i ∈ V , its neighbour graph is the sub-graph of G(V, E) induced by all its neighbours. In addition, we give the definition of equivalent transformation which will be used in the algorithm and the performance evaluation part. Definition 5.1 (Equivalent transformation). An equivalent transformation is a sequential combination of vertex insertion, deletion or replacement as follows:

• vertex insertion. For a cycle < v 1 , v 2 , . . . , v i , v i+1 , . . . , v k >, a vertex v ′ can be inserted in the cycle if v ′ is a neighbour of v i and v i+1 in the cycle.
• vertex deletion. For a cycle < v 1 , v 2 , . . . , v k >, a vertex v i in the cycle can be deleted if its two neighbouring vertices in the cycle are neighbours.

• vertex replacement. For a cycle < v 1 , v 2 , . . . , v k >, a vertex v i in the cycle can be replaced by v ′ if v ′ is a neighbour of v i and its two neighbours or v ′ , v i and two neighbours of v i have at least one common neighbour.

v' v' v' v' v' v' v i v i+1 v i v i+1

Graph based distributed algorithm

In this section, we will propose a graph based distributed algorithm to find boundary cycles of coverage holes in WSNs. The general steps of the algorithm are given first and the details of each step are presented in the following parts.

The entire process of our algorithm can be summarized as follows.

1. Each sensor gets its 1-and 2-hop neighbours information and constructs a neighbour graph. Then the Rips complex of the WSN can be constructed, as shown in Figure 5.2(a).

2. Based on the neighbour graph, each node can determine whether it can be a boundary node or not by checking whether there exists a Hamiltonian cycle in its neighbour graph. If there exists, the node is assumed to be a non-boundary node. Otherwise, it is assumed to be a boundary node. The results are shown in Figure 5.2(b∼c).

3. When each node has determined whether it is a boundary node or not, it can broadcast this information to its neighbours. Then each node knows the status of its neighbours. After that, some nodes can initiate boundary cycles discovery process to find cycles bounding holes, such as the nodes denoted by green diamond in Figure 5.2(d∼e). It is possible that some cycles found in step 3 are not minimum or some cycles bound the same hole. So it is necessary to minimize and make choices among all cycles found. The result is shown in Figure 5.2(f).

Each step is described in more detail in the following parts.

Neighbour discovery

In this step, each node needs to obtain all its 1-and 2-hop neighbours information. This can be easily achieved by two broadcasts of hello message. In the first one, each node broadcasts its id. When it gets all the ids of its 1-hop neighbours, each node continues to broadcast a hello message containing the ids of its 1-hop neighbours.

After receiving the neighbour list of its neighbours, each node can construct its neighbour graph. Assume ID i denotes the id of i-th node, G i (V i , E i ) is the neighbour graph of node ID i , where V i denotes the set containing ids of its 1-hop neighbours and E i is the set containing all the edges between its 1-hop neighbours. Notice that ID i is not included in V i . After that, the Rips complex corresponding to the WSN can be constructed. As the WSN is on a planar target field, it is sufficient to construct a 2-dimensional Rips complex of the WSN in order to find coverage holes. All 0-and 1-simplices can be easily obtained. As for 2-simplices, any three nodes which are neighbours of each other can form a 2-simplex. A Rips complex can be built according to this rule, shown in Figure 5.2(a). In addition, the 1-and 2-hop neighbours information will also be used in the step of cycles selection.

Boundary nodes discovery

After each node knows its 1-and 2-hop neighbours, it needs to determine whether it is a boundary node or not. we propose a method based on Hamiltonian cycle for the verification. For each internal node ID i , if it has less than three neighbours or there exist no Hamiltonian cycles in its neighbour graph G i (V i , E i ), this node is considered to be a boundary node. Otherwise, it is considered as a non-boundary node. For fence nodes, the node itself should be added to its neighbour graph and verify whether there exists a Hamiltonian cycle in the new graph. So the problem here is to find a method to search a Hamiltonian cycle in a graph. In general, it is a NP-complete problem. However, considering the graph in our problem is the neighbour graph of a node, it usually contains a small number of nodes, so it is possible to use an exhaustive search method to check the existence of a Hamiltonian cycle in a graph. Figure 5.2(b) shows the result of boundary nodes detection, nodes denoted by red stars are boundary nodes. We call the method as Hamiltonian cycle based boundary node detection (denoted by HC). We can see from the figure that some nodes lying on the boundary of a hole are not recognized. It is also possible that some boundary nodes found by the algorithm are not lying on the boundary of a hole (such case does not happen in this example). In order to find more boundary nodes, we aim to use the boundary nodes detected by the method HC. After some boundary nodes have been found, each boundary node broadcasts a message indicating its status (boundary) to its neighbours. So each node gets the status of its neighbours. Considering that any boundary node should have at least two boundary neighbours and the two neighbours should not be neighbours, we select the boundary nodes that have only one boundary neighbour or have more boundary neighbours but these neighbours are neighbours of each other. Each such node v chooses one of its non-fence neighbours which has the minimum degree and is not a neighbour of any boundary neighbour of v, and set the neighbour to be a boundary node. The process of adding boundary nodes is repeated for the new added nodes and until no nodes can be added. We call the method as improved Hamiltonian cycle based boundary node detection (denoted by IHC). According to this rule, more true boundary nodes can be found, such as the nodes denoted by blue stars in Figure 5.2(c). It is also possible that some nodes are wrongly detected as boundary nodes, such as the nodes denoted by magenta stars in Figure 5.2(c). This case is usually due to the fact that nodes near the external boundary of the target field have a relatively lower number of neighbours.

Boundary cycles discovery

After determining the status (boundary), each boundary node broadcasts a message indicating its status to its neighbours. Then, each node knows the status of its 1-hop neighbours. The next step is to find the cycles bounding holes. Since the algorithm is distributed, there is no central unit to select some nodes to initiate the process. Considering the fact that any internal node whose neighbour graph has more than one connected components must lie on the boundary of at least two coverage holes, we choose such nodes with higher priority to initiate the process. In addition, any other node which has no boundary neighbours or has the minimum id among all its boundary neighbours can also initiate the process. Each selected node initiates the process by broadcasting a message. As seen from Figure 5.2(c), some nodes lying on the boundary are not recognized as boundary nodes. Given that only boundary nodes continue broadcasting when they receive a broadcast message, it is possible that some holes can not be discovered. But if all nodes, no matter boundary nodes or not, broadcast the message, the message complexity will be high. So the structure of the message is designed as in Table 5.1. The element node_seq contains the ids of nodes that have received and forwarded the message. The element type indicates the type of message. We define three types of messages, denoted by 0, 1 and 2. 0 indicates that the last node in node_seq is a boundary node. 1 indicates that the last node is a non-boundary node and 2 indicates that the last two nodes are non-boundary nodes. Furthermore, we set a probability p(0 < p < 1) for non-boundary nodes. When a non-boundary node receives a broadcast message with type 0, it will broadcast the message with probability p and set the message type as 1. When a non-boundary node receives a type 1 message, it will broadcast with probability p 2 and set the message type as 2. If a non-boundary node receives a type 2 message, it will neglect it. Any boundary node will set the message type as 0 when it broadcasts a message. In addition, for any fence node, if it is not a boundary node, it will not forward any message. When broadcasting a message, each node attaches its id to the node_seq of the message sequentially. In this way, the message contains all the ids of nodes from an initiating node to the current one. In addition, the node also keeps the message, showing that it has been visited by the path initiated by the initiator.

Whenever a node receives a message, it needs to first verify whether its id has been in the node_seq of the message. If so, the nodes deletes the message. Otherwise, it continues to check whether the message has the same initiator as some message kept by the node. If not, it means that the message is new and the node will broadcast the message as illustrated in the last paragraph. If yes, the node needs to verify whether the two messages can form a cycle. We use m n and m o to denote the new message and the message kept by the node. If the first ids in node_seqs of m n and m o are the same and node_seqs of m n and m o have no other common ids, the last id in the node_seq of m n and the second last id in the node_seq of m o 1 are not neighbours, then a cycle can be formed and the node keeps the cycle. It is possible that the cycle found is not minimum, this can be processed by the next step illustrated in Section 5.3.4. Furthermore, if the length of node_seq in m n plus one is less than the length of node_seq in m o , it means their exists a shorter path between the initiator of the message and the node, so the node replaces m o by m n and broadcasts m n as illustrated in the last paragraph. In addition, in order to reduce the message complexity, when any initiating node receives a message initiated by another node, it will delete the message if the other initiator has higher id than itself.

After the above process, some boundary cycles can be found and it is also possible some cycles have not been discovered because there is no initiator selected in those cycles. In this case, some node can further be randomly selected to initiate the boundary cycles discovery process, such as the node denoted by green diamond in coverage hole 1 in Figure 5.2(e).

To better understand the process of the algorithm, we use an example in Figure 5.3 to explain it. The Rips complex of a WSN is shown in Figure 5. 3(a). According to the rule defined in the step of boundary nodes discovery, we can see that nodes 1, 2, 4, 5, 13, 14 and 16 are boundary nodes based on Hamiltonian cycle verification, shown in Figure 5.3(b). Then node 16 has only one boundary neighbour, so it chooses one node from its non-fence neighbours which has the minimum degree and is not connected with node 1. In this way, node 7 is set to be a boundary node, shown in Figure 5.3(c). Then nodes 1 and 5 are selected as initiators, shown in Figure 5. 3(d), since the id of node 1 is smaller than its boundary neighbours and node 5 has two connected components in its neighbour graph. They broadcast a message containing their ids respectively and set the message type as 0 because they are both boundary nodes. When their neighbours receive the messages, they can decide whether to transmit the message or not. For example, neighbours of node 5 (nodes 2, 4, 6, 7, 8, 14) receive the message. As nodes 6 and 8 are non-boundary internal nodes, they can choose to broadcast the message with probability p, assume node 8 chooses to transmit the message but node 6 not. Since the other neighbours of node 5 are boundary nodes, they will broadcast the message. This process is shown in Figure 5.3(e) (the message type is not shown in the figure). The node sequence in a red bracket indicates that a node receives a message but has not transmitted the message. Then in the next round, nodes 2, 4, 7, 8, 14 and 16 will broadcast (any nonboundary fence node does not broadcast any message). We assume they broadcast sequentially. The result of this round is shown in Figure 5.3(f), assuming nodes 6 and 8 choose to not transmit any message. The node sequence in a black bracket indicates the message kept by the node. Node 1 will not transmit any message since it is an initiator and its id is smaller than any other initiators. After that, nodes 3, 5, 7 and 13 will continue broadcasting. And in this process, node 7 can find a cycle <1, 16, 7, 5, 2> and node 13 can find another cycle <5, 4, 13, 14>, shown in Figure 5.3(g). Similarly, node 5 will find the cycle <1, 2, 5, 7, 16> and node 14 will find the cycle <5, 14, 13, 4> in the next round, shown in Figure 5.3(h). Since the two sequences [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF] and [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Brooks | Distributed target classification and tracking in sensor networks[END_REF][START_REF] Tolle | A macroscope in the redwoods[END_REF] have two common nodes, node 14 will not form a cycle and just broadcast the message containing the sequence [START_REF] Akyildiz | A survey on sensor networks[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF][START_REF] Arora | A line in the sand: a wireless sensor network for target detection, classification, and tracking[END_REF]. After that, no node will continue broadcasting messages. Until now, four cycles have been found. We can see that some of them actually bound the same coverage holes. So cycles selection should be performed, which will be illustrated in next section.

Cycles selection

After last step, many boundary cycles have been found. But it is possible that some cycles are not minimum or bound the same holes or even are not really bounding a hole. So it is necessary to analyse these cycles and make choices. This can be realized distributively by each node in the cycle. For any node in a cycle, it first checks whether there exists a shorter path between itself and other nodes in the cycle by using its 1-and 2-hop neighbours information. If there exists, the node can shorten the cycle. After that, it continues to check whether the cycle bounds the same hole as another cycle found before. For any two cycles, if one cycle can be converted to another one by the equivalent transformation presented in Definition 5.1, they are considered to bound the same hole. In addition, it is possible that some non-minimum cycle can not be minimized since each node has only its 1and 2-hop neighbours information. It is also possible that some cycle bounds more than one holes. To this end, for any two cycles c 1 , c 2 with length larger than 7, if

|c 1 ∩ c 2 | ≥ 1/2|c 1 | or |c 1 ∩ c 2 | ≥ 1/2|c 2 |,
we delete the cycle with larger length since it is highly possible that the cycle with larger length bounds more than one holes in this case. It is also possible that a false cycle can not be deleted. We investigate such error probability in Section 5.4.3. Consider the example in Figure 5.3, four cycles have been found in the last step. In this step, the cycles found by nodes are transmitted to the nodes in the cycles and each node checks whether there exists a shorter path or whether two cycles are the same. After doing this, nodes can find the two cycles <5, 4, 13, 14> and <5, 14, 13, 4> are the same, the two cycles <1, 16, 7, 5, 2> and <1, 2, 5, 7, 16> are also the same. So only one of them is kept. The result is shown in Figure 5.3(i). (e)

Simulations and performance evaluation

In this section, simulation settings are first given and probabilities of boundary nodes detection and boundary cycles detection are then presented.

Simulation settings

The target field is assumed to be a 100 × 100 m 2 square area. The sensing radius R s of each node is 10 meters. The communication radius R c is set to be 20 meters. There are fence sensors located along the edges of the square with 20 meters distance between neighbours. Other internal sensors are randomly distributed in the area according to a homogeneous Poisson point process with intensity λ. Under such settings, we approximately obtain that λ should be at least 0.006 for the WSN to be connected with high probability according to the results in [START_REF] Bettstetter | On the minimum node degree and connectivity of a wireless multihop network[END_REF] based on percolation theory. So we set λ to be 0.006, 0.008 and 0.01 in our simulations.

Probability of boundary nodes detection

A key step of our algorithm is boundary nodes detection and we propose two methods (denoted by HC and IHC respectively) to detect them. Here we want to have an idea about how many boundary nodes detected by our methods are true or false. First, we use the location based approach in [START_REF] Tong | On discovering sensing coverage holes in large-scale sensor networks[END_REF] to find all boundary nodes. Then we delete those nodes which only bound a triangular hole since our algorithm only detect non-triangular holes. We use success probability p succ b to denote the ratio between the number of true boundary nodes detected by our methods and the number of boundary nodes detected by the location based approach. Similarly, error probability p err b is used to denote the ratio between the number of false boundary nodes detected by our methods and the number of boundary nodes detected by the location based approach. Simulation results for success and error probabilities are shown in Figure 5.4(a) and (b) respectively, which are the average of 1000 simulations. It can be seen from Figure 5.4(a) that when λ is lower, p succ b of the two methods are relatively higher. That is because when λ is lower, there are fewer number of nodes in neighbour graphs and it is more accurate to detect boundary nodes by checking the existence of a Hamiltonian cycle in neighbour graphs. From Figure 5.4(b), we can see that when using improved Hamiltonian cycle based boundary nodes detection, p err b increases largely. The larger the density is, the larger is the increase.

Probability of boundary cycles detection

In order to evaluate the accuracy of our algorithm, we compare it with the location based algorithm (denoted as LBA) proposed in [START_REF] Tong | On discovering sensing coverage holes in large-scale sensor networks[END_REF]. Since the location based algorithm can discover both triangular and non-triangular coverage holes, but our algorithm can only detect non-triangular coverage holes, we do not consider those triangular coverage holes in the comparison. As it is possible that there exist shorter paths in boundary cycles found by LBA, we first shrink them using 1-hop neighbour information of boundary nodes. After that, we compare those boundary cycles with what our algorithm finds. Two boundary cycles are considered to surround the same coverage hole if one cycle can be converted to another one by equivalent transformations presented in Definition 5.1. We can see from Definition 5.1 that equivalent transformations only need 1-hop neighbours information. We emphasize that only 1-hop neighbours information can be used in the comparison in order to evaluate the accuracy of boundary cycles found by our algorithm. For example, if one cycle c 1 found by our algorithm can not be converted to another cycle c 2 found by LBA using only 1-hop neighbours information but can be converted by using 2-hop neighbours information, we consider the cycle c 1 is not accurate and the corresponding coverage

Chapter summary

In this chapter, we have proposed a graph based algorithm to detect boundary cycles of coverage holes in a WSN. The algorithm includes four steps. In the first step, each node obtains its 1-and 2-hop neighbours information. After that, each node determines that it is a boundary node or not by checking whether there exists a Hamiltonian cycle in its neighbour graph. Then some boundary nodes are randomly selected to initiate the process to discover boundary cycles. The cycles found may not be minimum or bound the same coverage holes, so cycles selection is performed in the final step. We compare our algorithm with a location based approach, which shows that our algorithm can accurately find boundary cycles of more than 95% coverage holes when the intensity is low. But the algorithm has high complexity since each node needs to check the existence of a Hamiltonian cycle in its neighbour graph by exhaustive search, and the error probability of boundary cycle detection is high when the intensity is high, so we aim to design an efficient and accurate algorithm for coverage hole detection in WSNs, which will be presented in Chapter 6.

Chapter 6

Homology based Distributed Coverage Hole Detection

Introduction

In last chapter, we have proposed a graph based coverage hole detection algorithm, but that algorithm has high complexity. In this chapter, we aim to design an efficient distributed coverage hole detection algorithm. We design such an algorithm based on homology theory. The basic idea of this algorithm is that for the Rips complex of a WSN, we try to delete some vertices and edges without changing the homology while making the Rips complex more sparse and nearly planar. Then it is easy to find boundary edges, each of which is part of at most one triangle1 . Finally such edges are connected in some order to form the boundary cycles.

The main contributions of this chapter are in three aspects. First, we define a rule for each vertex or edge to decide whether its deletion will change the homology of the Rips complex of the original WSN or not. Each vertex or edge can make such decision independently and only needs its 1-hop neighbour information.

Second, we propose a homology based algorithm to discover boundary cycles of coverage holes. In the algorithm, each node computes its weight independently. The weight of a node is a density indicator of its surrounding nodes. The larger the weight is, the higher is the probability that the node is not on the boundary of a coverage hole. Then some vertices and edges are deleted without changing the homology of Rips complex. After this process, the Rips complex becomes much sparser and nearly all boundary edges can be found by just checking whether the edge is part of at most one triangle or not. Then coarse boundary cycles are discovered by connecting boundary edges in some order and exact boundary cycles are further found by minimizing coarse boundary cycles.

Third, extensive simulations are performed to evaluate the performance of our algorithm. Analysis shows that the worst case complexity of our algorithm is O(n 3 ), where n is the maximum number of neighbours of each node. Comparisons with a boundary recognition algorithm show that our algorithm is more efficient and easy to implement in a distributed way. Comparisons with a location based algorithm further show that our algorithm can accurately detect the boundary cycles of about 99% coverage holes in about 99% cases.

Models and definitions

We use the same models for nodes as last chapter. In addition, we need to give some definitions that will be used in the process of this algorithm.

We say that a i-simplex

[v i0 , v i1 , ..., v ii ] is part of a j-simplex [v j0 , v j1 , ..., v jj ] if [v i0 , v i1 , ..., v ii ] ⊂ [v j0 , v j1 , ..., v jj ]. So the vertex [v 0 ] or [v 1 ] is part of the edge [v 0 , v 1 ]. The edge [v 0 , v 1 ] is part of the triangle [v 0 , v 1 , v 2 ].
In addition, we use E(v) to denote all the edges that the node v is part of and T (v) to denote all the triangles that the node v is part of. Definition 6.1 (Index of a triangle). The index of a triangle △ is the highest dimension of the simplex that the triangle is part of, denoted by I △ . Definition 6.2 (Weight of a node). The weight of a fence node is defined to be 0. For any internal node v, if there exists one edge in E(v) which is not part of any triangle, the weight w v of node v is set to be 0; if not, the weight is the minimum index of all the triangles in T (v), that is

w v = min △∈T (v) I △ .
The weight of an internal node is an indicator of the density of its surrounding nodes. If the weight of an internal node is 0, the node must be on the boundary of a coverage hole. The larger the weight is, the higher is the probability that the node is not on the boundary of a coverage hole.

We also use the definition of simple-connectedness graph as in [START_REF] Dong | Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods[END_REF]. Let G be a simple graph with vertex set V (G) and edge set E(G). An example is used to illustrate the procedures of this algorithm in Figure 6.2. For a WSN with some coverage holes, the Rips complex of the WSN is first constructed, shown in Figure 6.2(a), then the algorithm aims to discover minimum boundary cycles of all holes. In weight computation component, each node computes its weight independently according to Definition 6.2. After obtaining the weight, each node continues to determine whether it can be deleted or not according to some rules defined hereafter. Figure 6.2(b) shows the result of vertex deletion. Furthermore, some special node will decide whether some edge can be deleted or not. Figure 6.2(b∼c) shows the process of such special edge deletion. After the second component, many boundary edges can be found, as the red line shown in Figure 6.2(d). But it is possible that some other boundary edges have not been found. Then in the third component, all or nearly all boundary edges will be found after deleting some edges, see Figure 6.2(e∼j). Then coarse boundary cycles can be easily discovered, as shown in Figure 6.2(k). It is possible that the found boundary cycles are not minimum. In this case, coarse boundary cycles will be minimized in the final component as shown in Figure 6.2(l).

Weight computation

In this component, each node computes its weight. For any fence node, its weight is 0. For any internal node, theoretically it needs to construct all the simplices it is part of. As we consider WSNs on a planar target field, each internal node only needs to construct all its 1-simplices and 2-simplices and their neighbours. This can also reduce the computation complexity. In order to do this, the node needs to obtain all its 1-and 2-hop neighbours information. This can be easily achieved by two broadcasts of hello message. In the first one, each node broadcasts its id. When it gets all the ids of its 1-hop neighbours, each node continues to broadcast a hello message containing the ids of its 1-hop neighbours. After receiving the neighbour list of its neighbours, the node can obtain its E(v), the set of edges (1-simplices) and T (v), the set of triangles. It can also get the neighbours of each simplex. For any e ∈ E(v), let n(e) denote the neighbour set of e. For any t ∈ T (v), let n(t) denote the neighbour set of t. Then the weight of node v can be computed as in Algorithm 3.

Algorithm 3 Weight computation (for internal node

v) Begin if ∃e ∈ E(v), n(e) is empty then w v = 0 else if ∃t ∈ T (v), n(t) is empty then w v = 2 else w v = 3 end if END 6.3.

Vertex and edge deletion

In this component, we conduct maximal vertex deletion without changing the number of coverage holes in the original WSN and also delete some special edges if such edges exist. For vertex deletion, we only consider internal nodes, fence nodes will never be deleted. In the following part, we use vertex and node interchangeably.

(1) vertex deletion From the definition of weight, we can see that the higher the weight is, the higher is the probability that the sensing range of the node is fully covered by its neighbours, consequently the probability that the node does not lie on the boundary is higher. Meanwhile, if the deletion of a vertex may create a new coverage hole, it must not be deleted no matter how high the weight is. So we have such a rule for vertex deletion. If the weight of a vertex is smaller than 3, it should never be deleted. Otherwise, the vertex continues to check whether it is deletable or not according to the HP transformation. After the verification, the vertex broadcasts a message indicating that it can be deleted or not. After receiving the status of all its neighbours, each deletable vertex continues to check whether it should be deleted. It can be found that the weight of any deletable vertex must be 3. We assume that the vertex with lower ID has the priority to be deleted first. So each deletable vertex just needs to check whether its ID is the lowest among all its deletable neighbours. If so, it should be deleted. Otherwise, it should not be deleted. Algorithm 4 gives the detailed process for vertex deletion. According to the rule, it can be seen that two neighbouring vertices will not be deleted simultaneously, so each vertex can make the decision independently. When a vertex is deleted, it broadcasts a message to its neighbours. All its neighbours will modify their simplices according to Definition 6.4 and compute their weights again. The procedure of vertex deletion terminates until no vertex can be deleted in the Rips complex. Figure 6.2(b) gives the initial result after vertex deletion.

Algorithm 4 Vertex deletion (for internal node v) Begin if w v < 3 then node v can not be deleted else if node v is not deletable according to HP transformation then node v can not be deleted else if the ID of node v is the smallest among all its deletable neighbours then node v is deleted end if END (2) edge deletion After vertex deletion, we find one interesting thing. Edges having no neighbours must be on the boundary of holes, such as the common edge of coverage holes 7 and 8 in Figure 6.2(b). The edge having only one neighbour lies on the boundary of a coverage hole with high probability, such as the red edges shown in Figure 6.2(b). But it is possible that there exist some special such edges not lying on the boundary, such as the blue edge between coverage holes 1 and 2 in Figure 6.2(b). We try to delete such special edges. Since the edge has only one neighbour, deleting the edge will not create a new hole.

We call edges having at most one neighbour as boundary edges. Then we design a rule for deleting special boundary edges. If a vertex v has only one boundary edge vx and vx has only one neighbour y and deletion of vx will not make v have a new boundary edge, then vx can be deleted. This can be easily achieved by checking whether vy has more than two neighbours, shown in Algorithm 5. After vx is deleted, the nodes v, x and y need to update their simplices according to Definition 6.4 and recompute their weights. According to this rule, nearly all boundary edges which does not lie on the boundary of any holes can be deleted. But it is also possible that some edges lying on the boundary are also deleted, such as the blue edges in coverage holes 3, 4, 5 and 6 in Figure 6.2(b). This is not a big issue, because deletion of such edges will not create new holes and just enlarge the current coverage holes. It can be solved in the boundary cycles minimization component. In addition, after edge deletion, it is possible that some vertices can be deleted again, such as the vertex denoted by red square in Figure 6.2(b∼c). If such a case happens, we can continue to do vertex deletion until no more vertex or edge can be deleted.

Boundary edge detection

After deleting some vertices and edges, we can find that nearly all boundary edges lie on the boundary of holes. It can also be found that some edges lying on the boundary have not been found. In this component, we try to find such edges as many as possible. In all cases, such edges have two or more neighbours. If we consider the nodes having one or more boundary edges as boundary nodes and other nodes as non-boundary nodes, then we try to delete some edges connecting non-boundary nodes and boundary nodes according to the HP transformation, such as the green edges shown in Figure 6.2(e). After that, it is possible that some new boundary edges are recognized and some special edges illustrated in Section 6.3.2 are also identified, as the blue edges shown in Figure 6.2(f). In this case, we can still use the rule to delete them. It is still possible that some edges lying on the boundary have not been discovered. Such case usually occurs when some boundary nodes are neighbours and edges connecting them have more than one neighbours. In this case, we randomly delete some of such edges according to the HP transformation, such as the green edges in Figure 6.2(g). After that, some new boundary edges can be recognized, as shown in Figure 6.2(h).

But it is possible that the new found boundary edges can not construct a correct cycle with other boundary edges, as the magenta edges in coverage holes 2 and 4 in Figure 6.2(h). Such case is often due to the fact that two boundary edges cross with each other. It is found from numerous simulations that there are mainly three cases of crossing boundary edges, as shown in Figure 6.3, red lines denote boundary edges and black ones denote non-boundary edges. Similarly, we define some rules to delete such edges. We take node v as an example, in the top part of Figure 6.3(a), the two red lines connecting v and its neighbours are deleted, as shown in the bottom part of Figure 6.3(a). For the cases in Figure 6.3(b) and (c), the red line connecting v and its neighbour is deleted, as shown in the bottom part of Figure 6.3(b) and (c). According to such rules, some boundary edges can be deleted, such as the black bold edges in coverage hole 2 in Figure 6.2(i). It is also possible that certain boundary edges are deleted incorrectly. It is not a big issue as explained in last section. In addition, there exists also another case that a false boundary edge is found, as the blue edge in Figure 6.4. To this end, we can define a similar rule to delete them. For any internal node v, if it has two boundary neighbour nodes u and w, the edge vu and vw are not boundary edges and wu is a boundary edge, if the deletion of the edge wu can make at least one of the two edges vu and vw be a boundary edge, then wu can be deleted. According to such rule, the false boundary edge can be deleted and some correct boundary edge may also be deleted, as the black bold edge in coverage hole 3 in Figure 6.2(i). Similarly, it is not a big issue.

In general, after the process above, nearly all boundary edges can be found, as shown in Figure 6.2(j). But there exists one special case as in Figure 6.5. In this For two coarse boundary cycles with a common boundary edge uv, we can choose one node from u and v having three boundary edges as an initiator, for example, u is selected and u has three boundary edges uv, ux and uy. Then, u initiates the coarse boundary cycles discovery process by sending a message to v. The message contains the ID of u. When v receives this message, it records the ID of the initiator and sets u as its father node. After that, v continues to send the message along its other boundary edges. Each node receiving the message makes the same process until node u receives the message along its two other boundary edges ux and uy. Then node u sends a message to x and y respectively noticing them to form coarse boundary cycles. Then node x sends a message containing its ID to its father node, its father node does the same thing until the message arrives at node u. Then a coarse boundary cycle is formed. Similarly, node y does the same thing and another cycle can be formed. After forming coarse boundary cycles, node u informs the sequence to the nodes in the cycles. For two coarse boundary cycles with common nodes or separated, we just need to randomly choose one node which has two boundary edges as an initiator. Then the node initiates the process to find the coarse boundary cycle by sending a message along one of its boundary edges. When it receives the message coming back along the other boundary edge, it discovers one coarse boundary cycle. In this way, all coarse boundary cycles can be found, as the cycles indicated by different colours in Figure 6.2(k).

As for the special case shown in Figure 6.5, when the node v receives a message from its boundary neighbour node, it broadcasts the message to all its neighbours except its father node. If its neighbour node is a boundary node, then the message can be sent along the boundary edges. If its neighbour node is not a boundary node but it has boundary neighbour nodes, then it can send the message to its boundary neighbour nodes. Else, it will not transmit the message again. In this way, the message goes along boundary edges most of the time and can return to the original node sending the message.

Boundary cycles minimization

It is possible that some coarse boundary cycles found are not minimum, so we need to minimize such cycles. This can be achieved by checking whether there exists a shorter path between any two nodes in the cycle. Since each node has its 1-and 2-hop neighbours information, it can locally check the existence of a shorter path in the cycle. If there exists, we shorten the cycle and continue to do the same verification until no such case exists. After that, it is still possible some cycle has not been minimized, such as the coverage hole 2 in Figure 6.2(k). So we use the following 2-hop shrinking process to make the cycle as shorter as possible. For any four adjacent nodes in the cycle, say a, b, c, d, if there exists one node x which is one common neighbour of nodes a, b, c, d, then the cycle can be shortened by using x to replace nodes b and c.

In this way, we can nearly obtain most minimum cycles surrounding coverage holes. It is also possible that in some cases, we can not get the minimum cycles since each node only has its 1-and 2-hop neighbours information.

Performance evaluation

In this section, we first give simulation settings and then analyse the complexity of our algorithm. After that, we compare our algorithm with one boundary recognition algorithm and another location based coverage hole detection algorithm.

Simulation settings

For performance evaluation of the algorithm, we choose a 100 × 100 m 2 square area as the target field. The sensing radius R s of each node is 10 meters. The communication radius R c is set to be 20 meters and so γ = 2. There are fence sensors locating along the edges of the square with 20 meters distance between neighbours. Other internal sensors are randomly distributed in the area according to a homogeneous Poisson point process with intensity λ.

Complexity

The computation complexity of each step in the algorithm is shown in Table 6.1. In the weight computation component, each node only needs to check all its 2simplices, so the computation complexity is O(n 2 ), where n is the number of its 1-hop neighbours.

In vertex deletion part, each node needs to check whether it is deletable or not according to HP transformation. This can be done by checking all its cycles in its neighbour graph. It can build a spanning tree in its neighbour graph and check all fundamental cycles in the spanning tree. There are En + 1 fundamental cycles, where E is the number of edges in its neighbour graph, so the worst case computation complexity is O(n 2 ). Since the node needs to recompute its weight and recheck whether it is deletable when any one of its neighbour is deleted, so the total worst case computation complexity is O(n 3 ). As for the edge deletion, the node only needs to do simple verification as shown in Algorithm 5, the complexity is O(1).

In the boundary edge detection component, the non-boundary nodes need to check whether the edge connecting itself with its boundary neighbours can be deleted or not according to HP transformation. So the worst case computation complexity is O(n 3 ), the actual complexity is much less than that since for one edge, there are usually very few nodes in its neighbour graph. The boundary nodes also need to check whether the edges connecting itself and its boundary neighbours can be deleted or not, so the complexity is also O(n 3 ). In addition, the boundary nodes need to check whether there exist special cases as illustrated in Section V.D. The worst case computation complexity for such process is O(n 2 ). So the complexity of this step is O(n 3 ).

As for the final two components, each node only needs to broadcast some messages and do some local computations, the complexity is O(1). So the total worst case computation complexity for our algorithm is O(n 3 ).

Comparison with boundary recognition algorithm

As discussed in Chapter 2, many boundary recognition algorithms have been proposed. Among them, the algorithm proposed in [START_REF] Dong | Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods[END_REF] is the most promising for coverage hole detection. So we want to compare it with our algorithm. We use BR (Boundary Recognition algorithm) and HBA (Homology Based Algorithm) to denote their algorithm and our algorithm respectively.

We first introduce the algorithm BR briefly. In BR, a FGP (Fundamental Group Preserving) transformation is defined. The algorithm includes four components: skeleton extraction, primary boundary cycles and refined inner boundary cycles and refined outer boundary cycle. In skeleton extraction, maximal vertex and edge deletion are performed according to FGP transformation and a skeleton graph is obtained. In this component, each node needs its k-hop neighbour information (k ≥ 2). After that, the skeleton graph is separated into primary boundary cycles. Each primary boundary cycle contains one hole. Then primary boundary cycles are refined into tightest inner boundaries. For each boundary cycle C, it is extended in the graph of the WSN according to FGP transformation and a maximal graph

G C which is topologically equivalent to C is obtained. Then one vertex v in G C is selected and v is extended in G C to obtain a subgraph G v of G C . The edges in G C but not in G v
are considered as gap edges and they found that any cycle in G C surrounding the hole must contain at least one gap edge. So for each gap edge, a shortest cycle containing the gap edge is obtained. Among all these cycles, the shortest cycle is considered as the tightest inner boundary cycle. As we only consider the inner boundary, the component refined outer boundary cycle is not discussed here.

Comparing the two algorithms BR and HBA, we can find that they have the same worst case computation complexity. But our algorithm is more easy to implement in a distributed way for the following reasons. First, for the vertex deletion part, in our algorithm HBA, each node can independently decide whether it can be deleted or not. But in BR, it is possible that two nodes with k-hop distance can not be deleted simultaneously, so they need to interact with each other. Second, in order to find the minimum boundary cycles, the node in our algorithm HBA only needs to do some local verifications. But in BR, nearly all nodes in the whole WSN may be involved, which is neither efficient nor scalable for large scale WSNs.

In addition, for the WSNs which have largely separated coverage holes, our algorithm is more efficient. This is because in BR, the skeleton graph is required to be connected in the process of skeleton extraction. If the coverage holes are largely separated, they have to be enlarged much in order to keep the connectivity of skeleton graph. There is no such requirement in our algorithm. Figure 6.6 gives an example to show this.

Comparison with location based algorithm

In order to evaluate the accuracy of our algorithm HBA, we compare it with the location based algorithm LBA proposed in [START_REF] Tong | On discovering sensing coverage holes in large-scale sensor networks[END_REF]. We use the same way as discussed in Section 5.4.3 to do the evaluation. We set λ to be 0.008, 0.010 and 0.012 respectively. For each intensity, 1000 simulations are performed. Simulation results show that when λ is 0.008, there are nine times among the 1000 times when our algorithm can not find all non-triangular coverage holes. In each of the nine times, only one coverage hole is missed. There are 7363 non-triangular holes in total and 7354 ones found by our algorithm. When λ is 0.010 and 0.012, only one time among the 1000 times when our algorithm can not find all coverage holes. And in that time, only one coverage hole is missed. When λ is 0.010, there are 6114 non-triangular holes in total and 6113 ones found by our algorithm. When λ is 0.012, there are 4613 non-triangular holes in total, of which 4612 ones are found. The results are shown in Table 6.2. All these results show that our algorithm can find about 99% coverage holes in about 99% cases.

Chapter summary

In this chapter, we have proposed a homology based distributed algorithm to detect boundary cycles of coverage holes in WSNs. The algorithm includes five components: weight computation, vertex and edge deletion, boundary edge detection, coarse boundary cycles discovery and boundary cycles minimization. The Rips complex of the WSN is first constructed. Then in weight computation, and each node computes its weight independently. The weight of a node is a density indicator of its surrounding nodes. The larger the weight is, the higher is the probability that the node is not on the boundary of a coverage hole. In vertex and edge deletion part, we define a rule for each vertex or edge to decide whether its deletion will change the homology or not and some vertices and edges are deleted without changing the homology of Rips complex. After this process, the Rips complex becomes much sparser. In boundary edge detection part, nearly all boundary edges can be found by just checking whether the edge is part of at most one triangle or not. Then coarse boundary cycles are discovered by connecting boundary edges in some order and exact boundary cycles are further found by minimizing coarse boundary cycles. Our algorithm is with the worst case computation complexity O(n 3 ), where n is the maximum number of neighbours of each node. We also compare our algorithm with a boundary recognition algorithm and a location based algorithm, which shows that our algorithm is efficient and accurate to discover boundary cycles of coverage holes.

show that the radius of sphere has little impact on the proportion when it is much larger than communication and sensing radii of each sensor. More importantly, our analytical results can be used for planning of WSNs.

• Distributed algorithms for coverage hole detection

For non-triangular holes, we proposed two algorithms to detect them. The first algorithm detects boundary nodes by checking whether there exists a Hamiltonian cycle in the neighbour graph of each node. Since it is a NPcomplete problem to check the existence of a Hamiltonian cycle, the complexity of the algorithm is very high.

The second algorithm we proposed is more efficient and can work in both sparse and dense WSNs. The basic idea is that for the Rips complex of a WSN, we try to delete some vertices and edges without changing the homology while making the Rips complex more sparse and nearly planar, then it is easy to find boundary cycles of coverage holes. Comparisons with a boundary recognition algorithm and a location based algorithm show that our algorithm is efficient and can accurately detect 99% coverage holes in 99% cases. Although in some special cases, our algorithm can not detect the accurate coverage hole boundary, it can still provide some useful information for repairing coverage holes.

In addition, there also exist some limitations in our work. First, for sensing and communication models of sensor nodes, we consider only the boolean model. Second, in the algorithms we proposed, we always assume nodes can receive messages correctly, without considering packet error or loss. These problems need further consideration in our future work.

Future research directions

This work mainly focuses on the applications of homology theory for coverage hole detection in WSNs on 2D plane and sphere. Homology theory can also be applied in 3D WSNs. In addition, it has also potential applications in cellular networks.

• Coverage hole detection in 3D WSNs

For 2D WSNs, we only need to consider 2-dimensional Rips complex for coverage hole detection. For 3D WSNs, we will need to consider 3-dimensional Rips complex for coverage hole detection. According to the relationship between Čech complex and Rips complex, we know that Rips complex may also miss coverage holes for 3D WSNs. The holes missed by Rips complex must be surrounded by tetrahedrons. So it is also essential to analyse the accuracy of Rips complex for coverage hole detection in 3D WSNs. Furthermore, we can also design distributed algorithms to detect boundaries of coverage holes. The difference lies in that the boundary of a coverage hole in 2D WSNs is a cycle formed by edges, while it is a polyhedron formed by triangles in 3D WSNs. It is more challenging since we need to define a new rule for any vertex, edge or triangle to determine whether its deletion will change the homology of the Rips complex.

• Coverage preserving node scheduling for WSNs For WSNs with very high density, the target field is often over covered. In order to extend the lifetime of WSNs, it is usually required to turn off some redundant nodes while preserving coverage. Although the homology based algorithm proposed in this thesis is mainly for coverage hole detection, it can also be used for node scheduling. It can be seen that when the WSN contains no coverage holes, some nodes can be switched off without changing the coverage according to the rule defined in the algorithm. This is because our algorithm does not change the homology in the process. This problem has been investigated in a centralized way by our group [START_REF] Vergne | Reduction algorithm for simplicial complexes[END_REF]. But the energy constraint of each node has not been considered in the investigation, which can be our future work.

• Auto-planning in heterogeneous networks Future heterogeneous networks will have more and more small cells overlaid by macro cells. The massive deployment of small cells faces a number of challenges, among which interference management is of utmost importance. The theory of algebraic topology can be both used to analyse the expected characteristics of network where spatial features are important but also to devise some new operating algorithms. One problem we have in mind of that is the automatic frequency planning in heterogeneous network. The problem is to allocate frequency bands dynamically so that the interferences are the least possible while guaranteeing a maximum coverage. We expect the algebraic topology can be useful for such a task. Indeed, one can construct two simplicial complexes: one representing coverage as before, the other representing exclusion regions in the sense of cognitive radio, the exclusion region of a given BS means that any other BSs within this region can not use the same frequency sub-bands simultaneously. Using our previously defined algorithms [START_REF] Yan | Homology-based distributed coverage hole detection in wireless sensor networks[END_REF][START_REF] Vergne | Reduction algorithm for simplicial complexes[END_REF], we think that we can define frequency allocations satisfying as much as possible the two criteria.

where β 0 = ϕ 1arccos where |S -(r 0 , r 1 , ϕ 1 )| = I ′ (r 1 , β 1ϕ 1 ) -I ′ (r 1 , β 0ϕ 1 ) + I(r 0 , 0) -I(r 0 , β 1 ) = I ′ (r 1 , β 1ϕ 1 ) -I ′ (r 1 , β 0ϕ 1 ) -I(r 0 , β 1 )

I ′ (r 1 , ϕ) = r 2 1 sin 2ϕ 4 + R 2 c ϕ 2 + R 2 c 2 arcsin r 1 sin ϕ R c + r 1 sin ϕ 2 » R 2 c -r 2 1 sin 2 ϕ -
where 3.0 0.001 0 0.0001 0.0004 0.0014 0.0026 0.0051 0.002 0.0001 0.0008 0.0036 0.0103 0.0220 0.0391 0.003 0.0002 0.0028 0.0114 0.0297 0.0583 0.0924 0.004 0.0004 0.0055 0.0218 0.0518 0.0931 0.1382 0.005 0.0008 0.0098 0.0317 0.0715 0.1175 0.1544 0.006 0.0010 0.0124 0.0425 0.0832 0.1216 0.1491 0.007 0.0015 0.0153 0.0481 0.0880 0.1169 0.1292 0.008 0.0018 0.0184 0.0491 0.0833 0.1018 0.1022 0.009 0.0021 0.0181 0.0482 0.0762 0.0861 0.0756 0.010 0.0022 0.0177 0.0460 0.0641 0.0660 0.0544 0.011 0.0023 0.0184 0.0406 0.0530 0.0492 0.0367 0.012 0.0026 0.0174 0.0349 0.0424 0.0359 0.0236 0.013 0.0024 0.0158 0.0297 0.0327 0.0257 0.0153 0.014 0.0022 0.0138 0.0244 0.0238 0.0170 0.0092 0.015 0.0022 0.0115 0.0197 0.0183 0.0117 0.0065 0.016 0.0019 0.0099 0.0146 0.0136 0.0078 0.0034 0.017 0.0016 0.0083 0.0124 0.0099 0.0048 0.0020 0.018 0.0014 0.0069 0.0092 0.0065 0.0034 0.0013 0.019 0.0013 0.0056 0.0071 0.0044 0.0021 0.0007 0.020 0.0010 0.0047 0.0055 0.0033 0.0013 0.0004 Table B.5: p sl (λ), p su (λ) and p s (λ) under R = 10R s , γ = 2.0, 2.2 (%) λ γ = 2.0 γ = 2.2 p sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.0005 0.0006 0.0011 0.0126 0.0127 0.0239 0.002 0.0031 0.0031 0.0061 0.0677 0.0689 0.1265 0.003 0.0074 0.0081 0.0145 0.1535 0.1571 0.2829 0.004 0.0125 0.0134 0.0245 0.2445 0.2519 0.4454 0.005 0.0173 0.0183 0.0337 0.3213 0.3331 0.5782 0.006 0.0211 0.0224 0.0412 0.3739 0.3895 0.6652 0.007 0.0238 0.0251 0.0465 0.4001 0.4232 0.7034 0.008 0.0252 0.0279 0.0492 0.4030 0.4318 0.6990 0.009 0.0254 0.0278 0.0498 0.3874 0.4138 0.6649 0.010 0.0247 0.0273 0.0483 0.3591 0.3900 0.6089 0.011 0.0233 0.0255 0.0456 0.3233 0.3524 0.5424 0.012 0.0214 0.0241 0.0419 0.2841 0.3122 0.4708 0.013 0.0193 0.0221 0.0378 0.2448 0.2680 0.4008 0.014 0.0171 0.0196 0.0332 0.2073 0.2293 0.3355 0.015 0.0149 0.0174 0.0291 0.1730 0.1899 0.2775 0.016 0.0129 0.0148 0.0250 0.1426 0.1587 0.2259 0.017 0.0110 0.0127 0.0213 0.1163 0.1294 0.1820 0.018 0.0092 0.0109 0.0178 0.0939 0.1056 0.1453 0.019 0.0077 0.0091 0.0150 0.0752 0.0813 0.1151 0.020 0.0064 0.0069 0.0123 0.0598 0.0664 0.0902 3.0 0.001 0 0.0001 0.0003 0.0011 0.0024 0.0048 0.002 0.0001 0.0009 0.0034 0.0106 0.0210 0.0386 0.003 0.0002 0.0025 0.0115 0.0286 0.0538 0.0901 0.004 0.0005 0.0055 0.0227 0.0513 0.0905 0.1335 0.005 0.0007 0.0088 0.0316 0.0696 0.1109 0.1503 0.006 0.0010 0.0126 0.0414 0.0808 0.1207 0.1455 0.007 0.0015 0.0153 0.0469 0.0870 0.1150 0.1245 0.008 0.0018 0.0162 0.0475 0.0805 0.0995 0.0988 0.009 0.0022 0.0181 0.0471 0.0732 0.0811 0.0720 0.010 0.0023 0.0179 0.0448 0.0633 0.0645 0.0512 0.011 0.0024 0.0180 0.0397 0.0505 0.0478 0.0349 0.012 0.0023 0.0164 0.0340 0.0411 0.0350 0.0230 0.013 0.0023 0.0148 0.0297 0.0322 0.0248 0.0151 0.014 0.0019 0.0131 0.0236 0.0237 0.0173 0.0091 0.015 0.0019 0.0120 0.0193 0.0177 0.0113 0.0053 0.016 0.0017 0.0100 0.0149 0.0127 0.0077 0.0031 0.017 0.0016 0.0082 0.0112 0.0091 0.0049 0.0019 0.018 0.0013 0.0068 0.0087 0.0065 0.0032 0.0013 0.019 0.0013 0.0056 0.0063 0.0047 0.0020 0.0005 0.020 0.0010 0.0043 0.0049 0.0032 0.0012 0.0005 Table B.9: p sl (λ), p su (λ) and p s (λ) under R = 100R s , γ = 2.0, 2.2 (%) λ γ = 2.0 γ = 2.2 p sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.0006 0.0006 0.0011 0.0126 0.0130 0.0239 0.002 0.0031 0.0031 0.0061 0.0677 0.0698 0.1264 0.003 0.0078 0.0078 0.0144 0.1534 0.1578 0.2828 0.004 0.0129 0.0129 0.0243 0.2443 0.2547 0.4451 0.005 0.0187 0.0187 0.0334 0.3209 0.3385 0.5778 0.006 0.0226 0.0226 0.0408 0.3733 0.3920 0.6644 0.007 0.0247 0.0247 0.0461 0.3995 0.4243 0.7028 0.008 0.0273 0.0273 0.0487 0.4022 0.4281 0.6985 0.009 0.0278 0.0278 0.0492 0.3865 0.4168 0.6645 0.010 0.0271 0.0271 0.0477 0.3582 0.3864 0.6079 0.011 0.0257 0.0257 0.0451 0.3224 0.3477 0.5405 0.012 0.0238 0.0238 0.0414 0.2833 0.3099 0.4701 0.013 0.0218 0.0218 0.0373 0.2440 0.2659 0.4001 0.014 0.0193 0.0193 0.0330 0.2066 0.2272 0.3350 0.015 0.0172 0.0172 0.0289 0.1724 0.1900 0.2758 0.016 0.0149 0.0149 0.0249 0.1421 0.1572 0.2250 0.017 0.0127 0.0127 0.0211 0.1158 0.1297 0.1817 0.018 0.0108 0.0108 0.0177 0.0935 0.1054 0.1447 0.019 0.0086 0.0086 0.0148 0.0748 0.0838 0.1151 0.020 0.0074 0.0074 0.0122 0.0595 0.0672 0.0903 3.0 0.001 0 0.0001 0.0003 0.0014 0.0028 0.0054 0.002 0.0001 0.0008 0.0037 0.0101 0.0208 0.0374 0.003 0.0002 0.0026 0.0112 0.0297 0.0556 0.0916 0.004 0.0005 0.0055 0.0224 0.0511 0.0908 0.1327 0.005 0.0007 0.0090 0.0325 0.0705 0.1127 0.1508 0.006 0.0010 0.0126 0.0424 0.0817 0.1197 0.1436 0.007 0.0015 0.0157 0.0465 0.0847 0.1142 0.1256 0.008 0.0018 0.0170 0.0481 0.0818 0.0992 0.0996 0.009 0.0021 0.0190 0.0481 0.0743 0.0811 0.0731 0.010 0.0021 0.0183 0.0443 0.0622 0.0639 0.0520 0.011 0.0023 0.0174 0.0396 0.0525 0.0478 0.0362 0.012 0.0022 0.0170 0.0346 0.0411 0.0352 0.0235 0.013 0.0021 0.0153 0.0294 0.0316 0.0244 0.0143 0.014 0.0020 0.0137 0.0234 0.0239 0.0165 0.0088 0.015 0.0020 0.0113 0.0187 0.0180 0.0118 0.0053 0.016 0.0018 0.0099 0.0153 0.0129 0.0072 0.0035 0.017 0.0016 0.0087 0.0117 0.0090 0.0048 0.0020 0.018 0.0013 0.0068 0.0092 0.0061 0.0032 0.0011 0.019 0.0012 0.0061 0.0071 0.0046 0.0021 0.0008 0.020 0.0010 0.0048 0.0053 0.0032 0.0012 0.0004

I(r 0 , ϕ) = r 2 0 sin 2ϕ 4 + R 2 c ϕ 2 - R 2 c 2 arcsin r 0 sin ϕ R c - r 0 sin ϕ 2 » R 2 c -r 2 0 sin 2 ϕ - r 2 0 ϕ 2

1 2 . 1 2 4. 4 4 . 8

 212448 Un exemple de simplexes . . . . . . . . . . . . . . . . . . . . . . . . . 2 Un exemple de complexe simplicial . . . . . . . . . . . . . . . . . . . 3 Illustrations de bord . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Un exemple montrant les relations de C k (X), Z k (X), B k (X) . . . . . 5 (a) Un réseau de capteurs sans fil, (b) le complexe de Čech, (c) le complexe de Rips pour R c = 2R s , (d) le complexe de Rips pour R c = 2.5R s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 La proportion de la superface de trous triangulaires (a) les résultats de simulation et des bornes inférieures, (b) les résultats de simulation et des borne supérieures, (c) les résultats de simulation pour p sec 2d (λ) . 7 La proportion de la surface de trous triangulaires sphériques sous R = 10R s (a) les résultats de simulation et des bornes inférieures, (b) les résultats de simulation et des bornes supérieures . . . . . . . . . . 8 La comparaison de la proportion de la surface de trous triangulaires sphériques (a) la comparaison des résultats de simulation, (b) la comparaison des bornes inférieures, (c) la comparaison des bornes supérieures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Les résultats de simulation pour p sec s (λ) . . . . . . . . . . . . . . . . 10 Les procédures du algorithme distribué basé sur les graphes. (a) le complexe de Rips d'un réseau de capteurs sans fil, (b∼c) découverte des noeuds limites, (d∼e) découverte des cycles limites, (f) sélection des cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Diagramme de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . 12 Les procédures de l'algorithme. (a) le complexe de Rips d'un réseau de capteurs, (b) après suppression de sommet, (c∼d) suppression d'arête, (e∼j) détection d'arête frontière, (k) découverte de cycles frontières élémentaires, (l) minimisation de cycles frontières . . . . . . . . . . . xv Examples illustrating that it is not sufficient to only detect boundary nodes in order to discover boundary cycles . . . . . . . . . . . . . . . 2.2 An example of simplices . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 An example of simplicial complex . . . . . . . . . . . . . . . . . . . . 2.4 Illustrations of boundary . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 An example showing the relations of C k (X), Z k (X), B k (X) . . . . . . 2.6 An example of Rips complex falsely detects a coverage hole, assume R c = R s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 An example of Rips complex missing a coverage hole, assume R c = 2R s 3.1 (a) A WSN, (b) Čech complex, (c) Rips Complex under R c = 2R s , (d) Rips Complex under R c = 2.5R s . . . . . . . . . . . . . . . . . . . 3.2 Illustration of O being inside a triangular hole . . . . . . . . . . . . . 3.3 Illustration of region A + in the case √ 3 < γ ≤ 2 . . . . . . . . . . . 3.4 Illustration of regions S + and S -in the case √ 3 < γ ≤ 2 . . . . . . 3.5 Illustration of regions S ′+ and S ′-in the case √ 3 < γ ≤ 2 . . . . . . 3.6 Illustrations of regions in case γ > 2. (a) the regions A + , S + and S -, (b) the regions S ′+ and S ′-. . . . . . . . . . . . . . . . . . . . . . . 3.7 Proportion of the area of triangular holes (a) simulation results and lower bounds, (b) simulation results and upper bounds, (c) simulation results for p sec 2d (λ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 0-, 1-and 2-simplex on sphere . . . . . . . . . . . . . . . . . . . . . . 4.2 (a) A WSN, (b) Čech complex, (c) Rips Complex under R c = 2R s , (d) Rips Complex under R c = 2.5R s . . . . . . . . . . . . . . . . . . .4.3 Illustrations of P and spherical trianglev 0 v 1 v 2 : (a) P is inside the spherical triangle v 0 v 1 v 2 , (b) P is outside the spherical triangle v 0 v 1 v Illustration of region A + in the case R arccos([3 cos 2 (R s /R) -1]/2) < R c ≤2R s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Illustration of regions S + and S -in the case R arccos([3 cos 2 (R s /R)-1]/2) < R c ≤ 2R s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Illustration of regions S ′ + and S ′in the case R arccos([3 cos 2 (R s /R)-1]/2) < R c ≤ 2R s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Illustrations of regions in case R c > 2R s . (a) the regions A + , S + and S -, (b) the regions S ′+ and S ′-. . . . . . . . . . . . . . . . . . . . . xvi Proportion of the area of spherical triangular holes under R = 10R s (a) simulation results and lower bounds, (b) simulation results and upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Comparison of the proportion of the area of spherical triangular holes (a) comparison of simulation results, (b) comparison of lower bounds, (c) comparison of upper bounds . . . . . . . . . . . . . . . . . . . . . 4.10 Simulation results for p sec s (λ) . . . . . . . . . . . . . . . . . . . . . . 5.1 Examples of equivalent transformations . . . . . . . . . . . . . . . . . 5.2 Procedures of graph based distributed algorithm. (a) Rips complex of a WSN, (b∼c) boundary nodes discovery, (d∼e) boundary cycles discovery, (f) cycles selection . . . . . . . . . . . . . . . . . . . . . . . 5.3 An example illustrating the process of this algorithm. (a) Rips complex of a WSN, (b∼c) boundary nodes discovery, (d∼h) boundary cycles discovery, (i) cycles selection . . . . . . . . . . . . . . . . . . . 5.4 (a) Success probability of boundary nodes detection p succ

Figure 1 :

 1 Figure 1: Un exemple de simplexes

Figure 2 :

 2 Figure 2: Un exemple de complexe simplicial

Figure 3 :

 3 Figure 3: Illustrations de bord

Figure 5 :

 5 Figure 5: (a) Un réseau de capteurs sans fil, (b) le complexe de Čech, (c) le complexe de Rips pour R c = 2R s , (d) le complexe de Rips pour R c = 2.5R s

  (a) et 6(b) respectivement. Les résultats de simulation pour p sec 2d (λ) sont présentés dans la Figure 6(c).

DFigure 6 :

 6 Figure 6: La proportion de la superface de trous triangulaires (a) les résultats de simulation et des bornes inférieures, (b) les résultats de simulation et des borne supérieures, (c) les résultats de simulation pour p sec 2d (λ)

  sur la probabilité que n'importe quel point soit à l'intérieur d'un trou triangulaire sphérique. Dans cette configuration, la probabilité p s (λ) obtenue par des simulations est présentée avec les bornes inférieure et supérieure dans la Figure7(a) et 7(b) respectivement. On peut voir que ces résultats sont similaires à ceux de la section 0.3.4.0.4.1.2 Impact de RPour mieux comprendre l'impact de R sur la probabilité que n'importe quel point est à l'intérieur d'un trou triangulaire sphérique, on choisit R à 5R s , 10R s et 100R s . En outre, nous voulons aussi connaître la différence de la probabilité sous les cas

Figure 7 :

 7 Figure 7: La proportion de la surface de trous triangulaires sphériques sous R = 10R s (a) les résultats de simulation et des bornes inférieures, (b) les résultats de simulation et des bornes supérieures

Figure 8 :Figure 9 :

 89 Figure 8: La comparaison de la proportion de la surface de trous triangulaires sphériques (a) la comparaison des résultats de simulation, (b) la comparaison des bornes inférieures, (c) la comparaison des bornes supérieures

Definition 0. 12 (

 12 Graphe simple connectivité). Un graphe connexe G est simplement connecté si son espace de cycle C(G) est vide, ou pour chaque cycle C dans C(G), il existe un ensemble de cycles 3-longueur T 0 ⊆ C T (G) afin que C = T ∈T 0 T . Soit X un ensemble de sommets (ou d'arêtes) dans un graphe G, on utilise G[X] pour désigner le sous-graphe induit de sommet (ou d'arête) par X. Les voisins d'un sommet v dans G est noté N G (v). Le graphe des voisins Γ G (v) d'un sommet v est noté G[N G (v)]. Le graphe des voisins Γ G (e) d'une arête e = (u, v) est défini comme

0. 6 . 2 FinFigure 11 :

 6211 Figure 11: Diagramme de l'algorithme

Figure 2 . 1 :

 21 Figure 2.1: Examples illustrating that it is not sufficient to only detect boundary nodes in order to discover boundary cycles

Figure 2 . 2 :

 22 Figure 2.2: An example of simplices

Figure 2 . 3 :

 23 Figure 2.3: An example of simplicial complex

Figure 2 . 4 :

 24 Figure 2.4: Illustrations of boundary

Figure 2 . 5 :

 25 Figure 2.5: An example showing the relations of C k (X), Z k (X), B k (X)

Figure 2 . 6 :

 26 Figure 2.6: An example of Rips complex falsely detects a coverage hole, assume R c = R s

Figure 2 . 7 :

 27 Figure 2.7: An example of Rips complex missing a coverage hole, assume R c = 2R s

Figure 3 . 1 :

 31 Figure 3.1: (a) A WSN, (b) Čech complex, (c) Rips Complex under R c = 2R s , (d) Rips Complex under R c = 2.5R s

Figure 3 . 2 :

 32 Figure 3.2: Illustration of O being inside a triangular hole

  shown in Figure 3.3. M 2 is one intersection point between the circle C(O, d 0 ) and the circle C(τ 0 , R c ), such intersection point must exist in this case since

Figure 3 . 4 :

 34 Figure 3.4: Illustration of regions S + and S -in the case √ 3 < γ ≤ 2

Figure 3 . 5 :

 35 Figure 3.5: Illustration of regions S ′+ and S ′-in the case √ 3 < γ ≤ 2 Therefore, from (3.8), (3.9), (3.10) and (3.11), the lower bound shown in (3.3) can be derived.Next we will prove the upper bound. As discussed in Section 3.3.1, there are two cases for the origin being inside a triangular hole. As for the second case that the closest node τ 0 can not but some other nodes can contribute to a triangle which bounds a triangular hole containing the origin, it is not easy to obtain a closed form expression for such probability, so we can get it by simulations. Simulation results show that this probability is less than 0.0025 % at any intensity λ when √ 3 < γ ≤ 2. So we still focus on the probability of the first case.For the lower bound, we only considered the case that τ 1 contributes to a triangle which bounds a triangular hole containing the origin. For the upper bound, we

Figure 3 . 6 :

 36 Figure 3.6: Illustrations of regions in case γ > 2. (a) the regions A + , S + and S -, (b) the regions S ′+ and S ′-

Figure 3 .

 3 7(a) and 3.7(b) respectively. Simulation results for p sec 2d (λ) are shown in Figure 3.7(c). The detailed values are given in Table 3.1, 3.2 3.3 and 3.4 respectively.

Figure 3 . 7 :

 37 Figure 3.7: Proportion of the area of triangular holes (a) simulation results and lower bounds, (b) simulation results and upper bounds, (c) simulation results for p sec 2d (λ)

Figure 4 .

 4 Figure 4.1: 0-, 1-and 2-simplex on sphere

Figure 4 . 2 :

 42 Figure 4.2: (a) A WSN, (b) Čech complex, (c) Rips Complex under R c = 2R s , (d) Rips Complex under R c = 2.5R s

( 2 )

 2 Rc (V) and Č(2)Rs (V) contain the same 0simplices. It is also easy to see that all 1-simplices in R[START_REF] Yick | Wireless sensor network survey[END_REF]

Figure 4 .

 4 3(a) and 4.3(b) respectively. It can be seen that P has the same great circle distance to v 0 , v 1 and v 2 , denoted

Figure 4 . 3 :

 43 Figure 4.3: Illustrations of P and spherical triangle v 0 v 1 v 2 : (a) P is inside the spherical triangle v 0 v 1 v 2 , (b) P is outside the spherical triangle v 0 v 1 v 2

Figure 4 . 4 .

 44 M 1 and M 2 are two intersection points between bases of spherical caps C(N, Rα 0 ) and C(τ 0 , R c ), such intersection points must exist in this case since R c ≤ 2R s < 2Rα 0 .

Figure 4 . 4 :

 44 Figure 4.4: Illustration of region A + in the case R arccos([3 cos 2(R s /R) -1]/2) < R c ≤ 2R s

Figure 4 . 5 :

 45 Figure 4.5: Illustration of regions S + and S -in the case R arccos([3 cos 2(R s /R) -1]/2) < R c ≤ 2R s

Figure 4 . 6 :

 46 Figure 4.6: Illustration of regions S ′ + and S ′in the case R arccos([3 cos 2(R s /R) -1]/2) < R c ≤ 2R s

26 )From ( 4 .

 264 10), (4.15), (4.16), (4.21) and (4.26), the upper bound shown in (4.12) can be derived.

4. 3 . 4

 34 Case R c > 2R s Theorem 4.10. When R c > 2R s , we have p sl (λ) < p s (λ) < p su (λ), where

Figure 4 . 7 :

 47 Figure 4.7: Illustrations of regions in case R c > 2R s . (a) the regions A + , S + and S -, (b) the regions S ′+ and S ′-

Lemma 4 . 17 .

 417 Let θ 0 = r 0 /R, ϕ s1 = π + ϕ 1 , we have lim R→∞ |S + (θ 0 , ϕ s1 )| = |S + (r 0 , ϕ 1 )| where |S + (θ 0 , ϕ s1 )| and |S + (r 0 , ϕ 1 )| are shown in (4.18) and (3.18).

Lemma 4 . 18 .

 418 Let θ 0 = r 0 /R, θ 1 = r 1 /R, ϕ s1 = π + ϕ 1 , we have lim R→∞ |S -(θ 0 , θ 1 , ϕ s1 )| = |S -(r 0 ,r 1 , ϕ 1 )| where |S -(θ 0 , θ 1 , ϕ s1 )| and |S -(r 0 , r 1 , ϕ 1 )| are shown in (4.20) and (A.1).

Theorem 4 .

 4 [START_REF] Chintalapudi | Monitoring civil structures with a wireless sensor network[END_REF].lim R→∞ p sl (λ) = p 2dl (λ)where p sl (λ) and p 2dl (λ) are shown in (3.3) and (4.11).

Figure 4 .

 4 8(a) and 4.8(b) respectively.

Figure 4 . 8 :

 48 Figure 4.8: Proportion of the area of spherical triangular holes under R = 10R s (a) simulation results and lower bounds, (b) simulation results and upper bounds

Figure 4 . 9 :Figure 4 . 10 :

 49410 Figure 4.9: Comparison of the proportion of the area of spherical triangular holes (a) comparison of simulation results, (b) comparison of lower bounds, (c) comparison of upper bounds

Figure 5 .

 5 Figure 5.1 presents an example showing vertex insertion, deletion and replacement.

Figure 5 . 1 :

 51 Figure 5.1: Examples of equivalent transformations

Figure 5 . 2 :

 52 Figure 5.2: Procedures of graph based distributed algorithm. (a) Rips complex of a WSN, (b∼c) boundary nodes discovery, (d∼e) boundary cycles discovery, (f) cycles selection

  Figure 5.2(d) shows the result of selection. Nodes denoted by green diamonds are initiators.

Figure 5 . 3 :

 53 Figure 5.3: An example illustrating the process of this algorithm. (a) Rips complex of a WSN, (b∼c) boundary nodes discovery, (d∼h) boundary cycles discovery, (i) cycles selection

Figure 5 . 4 :

 54 Figure 5.4: (a) Success probability of boundary nodes detection p succ b , (b) error probability of boundary nodes detection p err b

Figure 6 . 1 :

 61 Figure 6.1: Flow chart of the algorithm

Figure 6 .Algorithm 5

 65 2(d) shows the result after edge deletion. Edge deletion (for internal node v) Begin if v has only one boundary edge vx and vx has one neighbour y then N (vy) = neighbour set of vy if |N (vy)| > 2 then vx can be deleted end if end if END

Figure 6 . 3 :

 63 Figure 6.3: Illustration of crossing boundary edges

Figure 6 . 4 :Figure 6 . 5 :

 6465 Figure 6.4: Illustration of false boundary edges

Figure 6 . 6 :

 66 Figure 6.6: (a) Rips complex of a WSN, (b) coarse boundary cycles found by HBA, (c) primary boundary cycles found by BR

2 c 2r 0 r 1 , β 2 = 2 c -r 2 0 2 c -r 2 1 Figure A. 2 : 1 Firstr 2 1 + 2r 0 r 1 cos ϕ 1 then α 1 = arccos r 2 0 + d 2 -r 2 1 2r 0 d As α 1 + α 2 R 2 cFigure A. 4 :

 212222121111221224 Figure A.2: For the computation of β 1

r 2 0 ϕ 2 If R 2

 22 (r 0 , r 1 , ϕ 1 , 0) = R cr 0 , which is the case in Figure A.3, then we can obtain β 1 as in Section A.1 and the area |S -(r 0 , r 1 , ϕ 1 )| as follows.

  1, 2 et 6. Lorsque R c = 2.5R s , il existe deux trous triangulaires supplémentaires, délimitées par des triangles formés par des noeuds 2, 3, 6 et 3, 5, 6 respectivement. 0.3.3 Des bornes sur la proportion de la surface de trous triangulaires Dans cette section, les conditions dans lesquelles n'importe quel point sur le domaine ciblé est dans un trou triangulaire sont d'abord donnés. Trois cas différents sont pris en compte pour le calcul de la proportion. Pour chaque cas, les bornes supérieures et inférieures de la proportion sont dérivées. Lemma 0.6. Pour tout point sur le domaine ciblé, il est à l'intérieur d'un trou triangulaire si et seulement si les deux conditions suivantes sont satisfaites: 1. la distance entre le point et son noeud le plus proche est plus grande que R s .

2. le point est à l'intérieur d'un triangle formé par trois noeuds avec la distance par paire inférieure ou égale à R c . Lemma 0.7. S'il existe un point O qui est à l'intérieur d'un trou triangulaire, alors R s < R c / √ 3. Lemma 0.8. Si O est à l'intérieur d'un trou triangulaire et l désigne la distance entre O et son voisin le plus proche, nous avons R s

  Dans les simulations, un disque centré à l'origine de rayon R c est considéré. La probabilité que l'origine soit à l'intérieur d'un trou triangulaire est calculée. Les capteurs sont déployés de façon aléatoire dans le disque selon un processus de Poisson homogène d'intensité λ. Le rayon de détection R

s de chaque noeud est 10 mètres et γ est choisi entre 2 et 3 avec un intervalle de 0.2. Ainsi, le rayon de communication R c varie de 20 à 30 mètres avec un intervalle de 2 mètres. λ est sélectionnée de 0.001 à 0.020 avec un intervalle de 0.001. Pour chaque γ, 10 7 simulations sont exécutés sous chaque λ pour vérifier si l'origine est à l'intérieur d'un trou triangulaire.

  est obtenu par des simulations.

	Theorem 0.15.
	lim

R→∞ p sl (λ) = p 2dl (λ) où p sl (λ) et p 2dl (λ) sont présentés dans (2) et (3).

  )

	Figure 10: Les procédures du algorithme distribué basé sur les graphes. (a) le
	complexe de Rips d'un réseau de capteurs sans fil, (b∼c) découverte des noeuds
	limites, (d∼e) découverte des cycles limites, (f) sélection des cycles
	0.6 La détection de trou de couverture basée sur
	l'homologie
	Dans cette section, on présente un algorithme distribué efficace basé sur l'homologie
	pour détecter le trou de couverture. L'idée de base de cet algorithme est le suivant:
	pour le complexe de Rips d'un réseau de capteurs, on essaie de supprimer des som-
	mets et des arêtes sans changer l'homologie tout en rendant le complexe de Rips
	moins dense et presque plan. Ensuite, il est facile de trouver les cycles frontières.

  En outre, E(v) désigne tous les arêtes dont le noeud [v] est une partie et T (v) désigne tous les 2-simplexes dont le noeud [v] est une partie. Definition 0.11 (Poids d'un noeud). Le poids d'un noeud de clôture est 0. Pour chaque noeud interne v, s'il existe une arête dans E(v) qui ne fait pas partie d'un 2-simplexe, Le poids w v du noeud v est 0; sinon, le poids est l'indice minimum de tous les 2-simplexes dans

	Definition 0.10 (Indice d'un 2-simplexe). L'indice d'un 2-simplexe △ est la plus grande dimension du simplexe dont le 2-simplexe fait partie, noté I △ .

) donne le résultat initial après la suppression de sommet.

	Algorithm 2 Suppression de sommet (pour noeud interne v)
	Begin
	if w v < 3 then
	noeud v ne peut pas supprimé
	else if noeud v n'est pas supprimable en fonction de la transformation HP then
	noeud v ne peut pas supprimé
	else if l'identité de noeud v est la plus bas parmi tous ses voisins supprimables.
	then
	noeud v est supprimé
	end if
	END
	(2) Suppression d'arête

Table 1 :

 1

	La complexité de chaque étape de l'algorithme
	Etape	Complexité
	Le calcul de poids	O(n 2 )
	Suppression de sommet et arête	O(n 3 )
	Détection d'arête frontière	O(n 3 )
	Découverte de cycles frontières élémentaires	O(1)
	Minimisation de cycles frontières	O(1)

Table 1 .

 1

	1: Summary of publications
	Titles	Contributions
	IEEE GLOBECOM 2011	Graph based algorithm, see Chapter 5
	IEEE ICC 2012	Accuracy of homology based coverage hole detection on plane, see Chapter 3
	IEEE Transactions on	Accuracy of homology based coverage
	Wireless Communications	hole detection on sphere, see Chapter 4
	IEEE/ACM Transactions on Networking	Accuracy of homology based coverage hole detection on plane and homology based algorithm, see Chapter 3 and 6

Table 2 .

 2 1: Characteristics of typical traditional approaches for coverage hole detection

	References	Category	Centralized /Distributed	Complexity	Discover boundary cycles
	Fang et al [52] Location based	Centralized	NA	No
	Zhang et al [57] Location based	Distributed	NA	No
	Huang et al [58] Location based	Distributed	O(n log n)	No
	Tong et al [47] Location based	Distributed	NA	Yes
	Zhang et al

Table 2 .

 2

	Approaches	pros		cons
	Location based	accurately boundary nodes and detect boundary cycles	need precise location information
		accurately	detect	need accurate dis-
	Range based	boundary nodes, dis-cover most boundary	tance may falsely detect information,
		cycles		boundary cycles

2: Summary of traditional coverage hole detection approaches in WSNs

Table 2 .

 2 3: Characteristics of homology based approaches for coverage hole detection

	References	Category	Centralized /Distributed	Complexity	Discover boundary cycles
	Ghrist et al [38] Homology based	Centralized	NA	Yes
	Muhammad et al [84]	Homology based	Distributed	NA	Yes
	Tahbaz-Salehi et al[86]	Homology based	Distributed	NA	Yes
	Kanno et al [88] Homology based	Distributed	NA	Yes
	Chintakunta et al[89]	Homology based	Distributed	NA	Yes

Table 3 .

 3 1: p 2dl (λ), p 2du (λ) and simulation results for p 2d (λ) under γ = 2.0, 2.2 (%)

	λ	γ = 2.0 p 2dl (λ) p 2d (λ) p 2du (λ) p 2dl (λ) p 2d (λ) p 2du (λ) γ = 2.2
	0.001 0.0005 0.0006 0.0011 0.0126 0.0126 0.0239
	0.002 0.0031 0.0035 0.0061 0.0677 0.0694 0.1264
	0.003 0.0074 0.0075 0.0144 0.1534 0.1553 0.2828
	0.004 0.0124 0.0127 0.0242 0.2443 0.2545 0.4456
	0.005 0.0171 0.0184 0.0335 0.3210 0.3335 0.5779
	0.006 0.0210 0.0228 0.0411 0.3734 0.3921 0.6636
	0.007 0.0236 0.0245 0.0462 0.3996 0.4222 0.7028
	0.008 0.0250 0.0262 0.0487 0.4023 0.4267 0.6987
	0.009 0.0252 0.0280 0.0493 0.3866 0.4139 0.6637
	0.010 0.0245 0.0269 0.0479 0.3583 0.3886 0.6082
	0.011 0.0231 0.0265 0.0451 0.3225 0.3512 0.5412
	0.012 0.0213 0.0239 0.0418 0.2834 0.3080 0.4697
	0.013 0.0192 0.0219 0.0372 0.2440 0.2673 0.3989
	0.014 0.0170 0.0200 0.0330 0.2066 0.2275 0.3348
	0.015 0.0148 0.0166 0.0285 0.1724 0.1902 0.2764
	0.016 0.0127 0.0145 0.0250 0.1421 0.1591 0.2249
	0.017 0.0108 0.0124 0.0211 0.1158 0.1284 0.1817
	0.018 0.0091 0.0109 0.0179 0.0935 0.1042 0.1445
	0.019 0.0076 0.0087 0.0146 0.0749 0.0836 0.1147
	0.020 0.0063 0.0076 0.0122 0.0595 0.0654 0.0898

Table 3 .

 3 2: p 2dl (λ), p 2du (λ) and simulation results for p 2d (λ) under γ = 2.4, 2.6 (%)

	λ	γ = 2.4 p 2dl (λ) p 2d (λ) p 2du (λ) p 2dl (λ) p 2d (λ) p 2du (λ) γ = 2.6
	0.001 0.0622 0.0629 0.1130 0.1820 0.1848 0.3241
	0.002 0.3147 0.3211 0.5597 0.8661 0.8917 1.4929
	0.003 0.6739 0.6994 1.1729 1.7466 1.8157 2.9153
	0.004 1.0157 1.0610 1.7301 2.4854 2.6147 4.0217
	0.005 1.2643 1.3270 2.1078 2.9277 3.0995 4.5933
	0.006 1.3957 1.4734 2.2785 3.0654 3.2670 4.6651
	0.007 1.4192 1.5096 2.2701 2.9631 3.1675 4.3771
	0.008 1.3596 1.4508 2.1301 2.7047 2.9082 3.8832
	0.009 1.2451 1.3417 1.9113 2.3655 2.5394 3.3036
	0.010 1.1011 1.1887 1.6561 2.0021 2.1450 2.7223
	0.011 0.9469 1.0256 1.3974 1.6515 1.7763 2.1887
	0.012 0.7960 0.8616 1.1523 1.3345 1.4309 1.7273
	0.013 0.6567 0.7089 0.9325 1.0607 1.1363 1.3408
	0.014 0.5334 0.5776 0.7440 0.8316 0.8874 1.0286
	0.015 0.4275 0.4660 0.5859 0.6448 0.6862 0.7813
	0.016 0.3389 0.3674 0.4559 0.4953 0.5253 0.5894
	0.017 0.2660 0.2880 0.3522 0.3775 0.3979 0.4411
	0.018 0.2070 0.2228 0.2697 0.2859 0.2985 0.3288
	0.019 0.1600 0.1733 0.2054 0.2153 0.2246 0.2440
	0.020 0.1229 0.1329 0.1551 0.1614 0.1680 0.1800

Table 3 .

 3 3: p 2dl (λ), p 2du (λ) and simulation results for p 2d (λ) under γ = 2.8, 3.0 (%)

	λ	γ = 2.8 p 2dl (λ) p 2d (λ) p 2du (λ) p 2dl (λ) p 2d (λ) p 2du (λ) γ = 3.0
	0.001 0.4110 0.4194 0.7212 0.7912 0.8105 1.3722
	0.002 1.8301 1.8947 3.0740 3.2854 3.4145 5.3836
	0.003 3.4664 3.6261 5.5778 5.8312 6.1158 9.0434
	0.004 4.6489 4.9111 7.1727 7.3642 7.7864 10.8372
	0.005 5.1793 5.5055 7.6722 7.7633 8.2559 10.8698
	0.006 5.1464 5.4880 7.3298 7.3343 7.8099 9.8046
	0.007 4.7371 5.0501 6.5004 6.4488 6.8510 8.2590
	0.008 4.1314 4.4196 5.4764 5.3967 5.7198 6.6504
	0.009 3.4638 3.6929 4.4427 4.3604 4.5967 5.1905
	0.010 2.8193 2.9963 3.5068 3.4344 3.6102 3.9673
	0.011 2.2434 2.3763 2.7126 2.6547 2.7753 2.9872
	0.012 1.7540 1.8577 2.0687 2.0235 2.1000 2.2259
	0.013 1.3527 1.4175 1.5586 1.5263 1.5781 1.6483
	0.014 1.0319 1.0866 1.1647 1.1422 1.1734 1.2141
	0.015 0.7804 0.8102 0.8662 0.8497 0.8744 0.8920
	0.016 0.5862 0.6093 0.6395 0.6293 0.6417 0.6538
	0.017 0.4378 0.4527 0.4713 0.4645 0.4706 0.4785
	0.018 0.3256 0.3343 0.3467 0.3419 0.3479 0.3498
	0.019 0.2413 0.2450 0.2541 0.2512 0.2541 0.2557
	0.020 0.1783 0.1836 0.1858 0.1843 0.1862 0.1868
	λ	Table 3.4: Simulation results for p sec 2d (λ) Simulation results for p sec 2d (λ) under different γ (%) 2.0 2.2 2.4 2.6 2.8

  Similarly, we have

		cos σ =	cos(d 12 /R) -cos(d 01 /R) cos(d 02 /R) sin(d 01 /R) sin(d 02 /R)	(4.5)
	cos	d 1M R	= cos	d 01 R	cos	d 0M 2R	+ sin	d 01 R	cos	d 0M 2R	cos σ	(4.6)
	From (4.5) and (4.6), we can obtain
			cos	d 1M R	=	cos(d 01 /R) + cos(d 12 /R) 2 cos(d 02 /(2R))	(4.7)

Table 5 .

 5

	1: Message structure
	node_seq	type
	ids	0, 1 or 2

Table 5 .

 5 number of correct cycles found by our algorithm b number of false cycles found by our algorithm c number of cycles missed by our algorithm d number of cycles found by LBA

			2: Number of boundary cycles
	λ	p	n c	a	n f	b	n m	c	p succ c	p err c	n L	d
	0.006	0.5 7213 347 216 0.9709 0.0467 7429 0.8 7322 399 107 0.9856 0.0537
	0.008	0.5 6994 421 330 0.9549 0.0575 7324 0.8 7202 507 122 0.9833 0.0692
	0.010	0.5 5690 362 514 0.9172 0.0583 6204 0.8 5977 471 227 0.9634 0.0759

a

Table 6 .

 6

	1: Complexity of each step in the algorithm
	Step	Complexity
	Weight computation	O(n 2 )
	Vertex and edge deletion	O(n 3 )
	Boundary edge detection	O(n 3 )
	Coarse boundary cycles discovery	O(1)
	Boundary cycles minimization	O

Table 6 .

 6 2: Number of non-triangular holes

		number of	number of	number of
	λ	non-triangular holes found by	non-triangular holes missed by	non-triangular holes found by
		HBA	HBA	LBA
	0.008	7354	9	7363
	0.010	6113	1	6114
	0.012	4612	1	4613

  Table B.2: p sl (λ), p su (λ) and p s (λ) under R = 5R s , γ = 2.4, 2.6 (%) sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.0617 0.0621 0.1120 0.1800 0.1810 0.3198 0.002 0.3130 0.3227 0.5556 0.8582 0.8779 1.4759 0.003 0.6710 0.6972 1.1663 1.7340 1.8110 2.8902 0.004 1.0128 1.0594 1.7231 2.4720 2.6030 3.9935 0.005 1.2626 1.3281 2.1023 2.9173 3.0835 4.5714 0.006 1.3957 1.4748 2.2780 3.0599 3.2596 4.6534 0.007 1.4211 1.5142 2.2720 2.9628 3.1745 4.3775 0.008 1.3632 1.4612 2.1344 2.7089 2.9099 3.8895 0.009 1.2502 1.3520 1.9185 2.3731 2.5526 3.3164 0.010 1.1070 1.1988 1.6665 2.0117 2.1574 2.7370 0.011 0.9532 1.0349 1.4068 1.6620 1.7819 2.2050 0.012 0.8024 0.8729 1.1615 1.3451 1.4413 1.7422 0.013 0.6629 0.7189 0.9421 1.0706 1.1447 1.3552 0.014 0.5391 0.5847 0.7523 0.8407 0.9024 1.0404 0.015 0.4327 0.4723 0.5932 0.6527 0.6998 0.7922 0.016 0.3434 0.3673 0.4616 0.5020 0.5313 0.5982 0.017 0.2698 0.2929 0.3578 0.3832 0.4079 0.4488 0.018 0.2103 0.2276 0.2740 0.2905 0.3057 0.3342 0.019 0.1627 0.1753 0.2088 0.2191 0.2300 0.2481 0.020 0.1251 0.1371 0.1583 0.1645 0.1726 0.1840 Table B.3: p sl (λ), p su (λ) and p s (λ) under R = 5R s , γ = 2.8, 3.0 (%) sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.4052 0.4128 0.7082 0.7780 0.7935 1.3416 0.002 1.8091 1.8711 3.0291 3.2417 3.3616 5.2894 0.003 3.4351 3.5920 5.5143 5.7720 6.0728 8.9249 0.004 4.6179 4.8769 7.1119 7.3111 7.7338 10.7383 0.005 5.1564 5.4688 7.6306 7.7284 8.2208 10.8076 0.006 5.1347 5.4757 7.3086 7.3200 7.7953 9.7798 0.007 4.7361 5.0693 6.4998 6.4513 6.8566 8.2651 0.008 4.1386 4.4233 5.4859 5.4106 5.7332 6.6721 0.009 3.4763 3.7200 4.4633 4.3806 4.6133 5.2202 0.010 2.8346 3.0127 3.5300 3.4568 3.6285 3.9983 0.011 2.2594 2.4024 2.7364 2.6767 2.8028 3.0159 0.012 1.7695 1.8684 2.0897 2.0436 2.1208 2.2512 0.013 1.3667 1.4476 1.5780 1.5438 1.5944 1.6691 0.014 1.0442 1.0911 1.1804 1.1570 1.1919 1.2311 0.015 0.7908 0.8212 0.8782 0.8619 0.8807 0.9062 0.016 0.5948 0.6169 0.6501 0.6392 0.6463 0.6644 0.017 0.4449 0.4592 0.4792 0.4723 0.4838 0.4868 0.018 0.3313 0.3397 0.3529 0.3481 0.3535 0.3565 0.019 0.2458 0.2544 0.2590 0.2561 0.2565 0.2608 0.020 0.1819 0.1832 0.1899 0.1881 0.1899 0.1908 Table B.4: Simulation results for p sec s (λ) when R = 5R s

	λ p λ p λ	γ = 2.4 γ = 2.8 Simulation results for p sec (λ) under different γ (%) γ = 2.6 γ = 3.0 2.0 2.2 2.4 2.6 2.8

Table B .

 B 6: p sl (λ), p su (λ) and p s (λ) under R = 10R s , γ = 2.4, 2.6 (%) sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.0621 0.0633 0.1126 0.1815 0.1844 0.3229 0.002 0.3143 0.3233 0.5584 0.8640 0.8882 1.4891 0.003 0.6731 0.6924 1.1711 1.7433 1.8151 2.9093 0.004 1.0149 1.0584 1.7291 2.4819 2.6077 4.0144 0.005 1.2638 1.3277 2.1059 2.9249 3.0912 4.5867 0.006 1.3957 1.4768 2.2784 3.0639 3.2581 4.6614 0.007 1.4196 1.5107 2.2698 2.9629 3.1699 4.3798 0.008 1.3604 1.4585 2.1296 2.7056 2.9030 3.8841 0.009 1.2463 1.3429 1.9124 2.3673 2.5450 3.3067 0.010 1.1025 1.1897 1.6593 2.0044 2.1548 2.7270 0.011 0.9484 1.0268 1.3993 1.6540 1.7771 2.1923 0.012 0.7975 0.8690 1.1540 1.3371 1.4297 1.7307 0.013 0.6582 0.7169 0.9358 1.0631 1.1390 1.3452 0.014 0.5348 0.5824 0.7457 0.8338 0.8946 1.0318 0.015 0.4288 0.4649 0.5876 0.6467 0.6926 0.7843 0.016 0.3400 0.3706 0.4575 0.4969 0.5281 0.5911 0.017 0.2669 0.2874 0.3528 0.3789 0.3971 0.4428 0.018 0.2078 0.2266 0.2704 0.2870 0.3027 0.3301 0.019 0.1607 0.1715 0.2054 0.2162 0.2276 0.2451 0.020 0.1234 0.1331 0.1556 0.1621 0.1693 0.1812 Table B.7: p sl (λ), p su (λ) and p s (λ) under R = 10R s , γ = 2.8, 3.0 (%) sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.4095 0.4171 0.7178 0.7878 0.7988 1.3641 0.002 1.8247 1.8936 3.0625 3.2742 3.4057 5.3602 0.003 3.4583 3.6133 5.5592 5.8160 6.1184 9.0140 0.004 4.6408 4.8961 7.1570 7.3505 7.7578 10.8118 0.005 5.1732 5.5014 7.6589 7.7541 8.2506 10.8531 0.006 5.1432 5.4654 7.3267 7.3304 7.8045 9.7974 0.007 4.7367 5.0489 6.5027 6.4492 6.8548 8.2604 0.008 4.1330 4.4019 5.4781 5.4000 5.7205 6.6557 0.009 3.4668 3.6944 4.4466 4.3653 4.6061 5.1974 0.010 2.8230 2.9974 3.5140 3.4399 3.6109 3.9742 0.011 2.2473 2.3838 2.7199 2.6601 2.7777 2.9941 0.012 1.7578 1.8524 2.0745 2.0285 2.1101 2.2329 0.013 1.3561 1.4223 1.5644 1.5306 1.5815 1.6539 0.014 1.0349 1.0834 1.1698 1.1458 1.1735 1.2186 0.015 0.7830 0.8180 0.8687 0.8527 0.8779 0.8950 0.016 0.5883 0.6091 0.6427 0.6317 0.6456 0.6561 0.017 0.4396 0.4597 0.4734 0.4664 0.4736 0.4804 0.018 0.3270 0.3373 0.3480 0.3434 0.3487 0.3516 0.019 0.2424 0.2491 0.2553 0.2524 0.2560 0.2568 0.020 0.1792 0.1815 0.1870 0.1852 0.1870 0.1879 Table B.8: Simulation results for p sec s (λ) when R = 10R s

	λ p λ p λ	γ = 2.4 γ = 2.8 Simulation results for p sec (λ) under different γ (%) γ = 2.6 γ = 3.0 2.0 2.2 2.4 2.6 2.8

Table B .

 B 10: p sl (λ), p su (λ) and p s (λ) under R = 100R s , γ = 2.4, 2.6 (%) sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.1847 0.0634 0.1129 0.1847 0.1847 0.3243 0.002 0.8858 0.3206 0.5596 0.8858 0.8858 1.4928 0.003 1.8142 0.6908 1.1724 1.8142 1.8142 2.9170 0.004 2.6096 1.0587 1.7303 2.6096 2.6096 4.0212 0.005 3.0924 1.3243 2.1080 3.0924 3.0924 4.5932 0.006 3.2566 1.4775 2.2798 3.2566 3.2566 4.6655 0.007 3.1608 1.5086 2.2689 3.1608 3.1608 4.3784 0.008 2.8923 1.4484 2.1290 2.8923 2.8923 3.8844 0.009 2.5444 1.3401 1.9116 2.5444 2.5444 3.3054 0.010 2.1512 1.1832 1.6566 2.1512 2.1512 2.7228 0.011 1.7772 1.0236 1.3970 1.7772 1.7772 2.1908 0.012 1.4286 0.8615 1.1524 1.4286 1.4286 1.7273 0.013 1.1334 0.7100 0.9333 1.1334 1.1334 1.3414 0.014 0.8922 0.5779 0.7435 0.8922 0.8922 1.0291 0.015 0.6854 0.4626 0.5853 0.6854 0.6854 0.7821 0.016 0.5240 0.3705 0.4564 0.5240 0.5240 0.5892 0.017 0.4017 0.2894 0.3520 0.4017 0.4017 0.4410 0.018 0.2998 0.2256 0.2698 0.2998 0.2998 0.3283 0.019 0.2279 0.1749 0.2054 0.2279 0.2279 0.2439 0.020 0.1689 0.1334 0.1553 0.1689 0.1689 0.1803 Table B.11: p sl (λ), p su (λ) and p s (λ) under R = 100R s , γ = 2.8, 3.0 (%) sl (λ) p s (λ) p su (λ) p sl (λ) p s (λ) p su (λ) 0.001 0.4109 0.4188 0.7215 0.7911 0.8086 1.3723 0.002 1.8300 1.8796 3.0737 3.2851 3.4049 5.3829 0.003 3.4661 3.6178 5.5773 5.8308 6.1097 9.0459 0.004 4.6485 4.9135 7.1730 7.3637 7.7923 10.8368 0.005 5.1789 5.4868 7.6722 7.7628 8.2563 10.8698 0.006 5.1460 5.4754 7.3318 7.3339 7.7878 9.8022 0.007 4.7368 5.0488 6.5032 6.4484 6.8581 8.2612 0.008 4.1311 4.4128 5.4758 5.3964 5.7122 6.6519 0.009 3.4635 3.6919 4.4426 4.3602 4.5862 5.1919 0.010 2.8191 2.9994 3.5084 3.4342 3.6076 3.9679 0.011 2.2432 2.3784 2.7148 2.6545 2.7726 2.9887 0.012 1.7539 1.8533 2.0699 2.0234 2.1079 2.2273 0.013 1.3526 1.4219 1.5597 1.5262 1.5761 1.6480 0.014 1.0318 1.0794 1.1654 1.1421 1.1773 1.2141 0.015 0.7803 0.8173 0.8662 0.8496 0.8703 0.8916 0.016 0.5861 0.6069 0.6396 0.6292 0.6436 0.6538 0.017 0.4378 0.4551 0.4713 0.4644 0.4714 0.4784 0.018 0.3255 0.3356 0.3464 0.3418 0.3490 0.3498 0.019 0.2412 0.2498 0.2541 0.2512 0.2555 0.2558 0.020 0.1783 0.1832 0.1860 0.1843 0.1848 0.1868 Table B.12: Simulation results for p sec s (λ) when R = 100R s

	λ p λ p λ	γ = 2.4 γ = 2.8 Simulation results for p sec (λ) under different γ (%) γ = 2.6 γ = 3.0 2.0 2.2 2.4 2.6 2.8

It also includes the case that P is on one arc of the spherical triangle v 0 v 1 v

.

the id of current node has been in m 0

In this chapter, a triangle means a

2-simplex

Acknowledgements

I would like to express my deepest gratitude to my advisor Professor Philippe Mar-

Definition 4.1 (Spherical triangular hole). For a pair of complexes Č [START_REF] Yick | Wireless sensor network survey[END_REF] Rs (V) and R

(2) Rc (V) of a WSN, a spherical triangular hole is an uncovered region bounded by a spherical triangle formed by three nodes v 0 , v 1 , v 2 , where v 0 , v 1 , v 2 can form a 2simplex which appears in R [START_REF] Yick | Wireless sensor network survey[END_REF] Rc (V) but not in Č(2) Rs (V).

From Definition 4.1, we can see from Figure 4.2 that when R c = 2R s , there is one spherical triangular hole bounded by the spherical triangle formed by nodes 1, 2 and 6. And when R c = 2.5R s , there are two additional spherical triangular holes, bounded by spherical triangles formed by nodes 2,3,6 and 3, 5, 6 respectively.

Bounds on proportion of spherical triangular holes

In this section, the conditions under which any point on S 2 with radius R is inside a spherical triangular hole are first given. From the discussions in Section 4.2, it is found that the proportion of the area of spherical triangular holes is related to the relation of R c and R s . Three different cases are considered for the proportion computation. For each case, closed form expressions for lower and upper bounds of the proportion are derived.

Preliminary

Lemma 4.5. For any point on S 2 , it is inside a spherical triangular hole if and only if the following two conditions are satisfied:

1. the great circle distance between the point and its closest node is larger than R s .

2. the point is inside a spherical triangle formed by three nodes with pairwise great circle distance less than or equal to R c .

Lemma 4.6. If there exists a point O which is inside a spherical triangular hole, then R s < R arccos

Proof. According to Definition 4.1, if there is a point O inside a spherical triangular hole, then there exists a 2-simplex σ ∈ R

(2)

Rs (V). According to (4.1), we have

hole is not found.

Based on the method presented above, we choose p to be 0.5 and 0.8. For each λ, we run 1000 simulations. We also use success and error probabilities, denoted by p succ c and p err c , to evaluate the accuracy of our algorithm for boundary cycles detection, which are shown in Figure 5.5(a) and (b) respectively. The detailed values are presented in Table 5.2. increases when p increases from 0.5 to 0.8. That is because when p is larger, there are more non-boundary nodes broadcasting messages, which can increase the number of boundary cycles detected. In addition, we can see that p has a larger impact on the probability when λ is higher. It is because when λ is higher, more nodes lying on the boundary are not recognized, these nodes may broadcast messages when p is higher.

). The triangle cycle subspace C T (G) of G is the set of all 3-length cycles in C(G). Definition 6.3 (Simple-Connectedness Graph). A connected graph G is of simple connectedness if its cycle space C(G) is empty, or for any cycle C in C(G), there exists a set of 3-length cycles

Let X be a vertex (or edge) set in a graph G, we use G[X] to denote the vertexinduced (or edge-induced) sub-graph by X. The neighbours of a vertex v in G is denoted by

is deleted in a Rips complex R(V) means that the simplex and all simplices which the simplex is part of are deleted from R(V).

Based on definitions above, we can give the definition of HP (Homology Preserving) transformation.

Definition 6.5 (HP Transformation).

A HP transformation is a sequential combination of vertex (or edge) deletion as follows: a vertex (or edge) x of G is deletable if neighbour graph Γ G (x) (1) has two or more vertices; (2) is connected and ( 3) is a simple-connectedness graph. Theorem 6.1. HP transformations do not change the number of coverage holes in Rips complex of a WSN.

Proof. In order to prove HP transformations do not change the number of coverage holes in Rips complex of a WSN, we only need to prove that in the process of HP transformations, there is no new coverage holes created and no two coverage holes merged. If a new coverage hole is created when a vertex v (or edge e) is deleted, then the boundary cycle of the new coverage hole must be a cycle in Γ G (v) (or Γ G (e)), which means Γ G (v) is not a simple-connectedness graph. It is contrary to the third condition in HP transformation, so there is no new coverage hole created. On the other hand, if two coverage holes are merged when a vertex v (or edge e) is deleted, then the neighbour graph Γ G (v) (Γ G (e)) must not be connected, which is contrary to the second condition in HP transformation. So there are no two coverage holes merged. Consequently, the number of coverage holes will not be changed in the process of HP transformation.

Conclusions and Future Work

In this chapter, we summarize our major contributions and discuss future research directions.

Major contributions

This work aims at studying the applications of homology theory for coverage hole detection in WSNs. Two main aspects have been studied, namely accuracy of homology based coverage hole detection and distributed algorithms for coverage hole detection. Specifically, the main contributions can be summarized as follows.

• Accuracy of homology based coverage hole detection

We first analysed the relationship between Čech complex and Rips complex in terms of coverage holes for WSNs on a planar target field. Their relation depends on the ratio γ between communication radius and sensing radius of each sensor. When γ ≤ √ 3, Rips complex does not miss any coverage holes. While γ > √ 3, Rips complex may miss coverage holes and the holes missed by Rips complex are always bounded by triangles. Thus we defined them to be triangular holes and other holes to be non-triangular. Furthermore, we chose the proportion of the area of triangular holes as the metric to evaluate the accuracy of homology based coverage hole detection. Such proportion is related to γ. Then we analysed the proportion in three cases and for each case, closed form expressions for lower and upper bounds of the proportion are derived. Simulations results are well consistent with the analytical lower and upper bounds, with maximum differences of 0.5% and 3%. In addition, we extended the analysis to the sphere case. Simulation results

Appendix

Here we give the detailed computation of the area

The region S -(r 0 , r 1 , ϕ 1 ) is shown in Figure

Consequently, we can get β 1 as follows

and when

where

Replace r 1 by r 0 in (A.3), we can get the area of S -(r 0 , r 0 , ϕ 1 ).

A.2 Area |S -(r 0 , r 1 , ϕ 1 )| in case γ > 2

As illustrated in Section 3.3.4, two situations should be considered in case γ > 2.

The area |S -(r 0 , r 1 , ϕ 1 )| can also be expressed as

2) and Furthermore, since the upper limit of integral for ϕ is 0, we need to check the value of R 2 (r 0 , r 1 , ϕ 1 , 0).

Then we can get the area |S -(r 0 , r 1 , ϕ 1 )| as

Appendix B

Detailed Values of Simulation

Results and Bounds on Sphere RESUME : 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 Čech et complexe de Rips. Le complexe de Čech 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 d'analyse, 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 noeuds voisins et a la complexité O(n 3 ) où n est le nombre maximum de noeuds 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-CLEFS :

Homologie simpliciale, trou de couverture, réseaux de capteurs sans fil ABSTRACT : Homology theory provides new and powerful solutions to address the coverage hole problem in wireless sensor networks (WSNs). They are based on two combinatorial objects named Čech complex and Rips complex. Čech complex can detect all coverage holes, but it is very difficult to construct. Rips complex is easy to construct but it may be not accurate in some situations.

In the first part of this thesis, we choose the proportion of the area of holes missed by Rips complex as a metric to evaluate the accuracy of homology based coverage hole detection. Closed form expressions for lower and upper bounds of the proportion are derived. Simulation results are well consistent with the analytical lower and upper bounds, with maximum differences of 0.5% and 3%. In addition, we extend the analysis to the sphere case.

In the second part, we first propose a graph based distributed algorithm to detect non-triangular holes. This algorithm exhibits high complexity. We thus propose another efficient homology based distributed algorithm. This algorithm only requires 1-and 2-hop neighbour nodes information and has the worst case complexity O(n 3 ) where n is the maximum number of 1-hop neighbour nodes. It can accurately detect the boundary cycles of about 99% coverage holes in about 99% cases.

KEY-WORDS : Homology theory, coverage hole, wireless sensor networks