Julie Gaudin

Marcia Costa

Rafael Galvão

Erica Benvindo

Davide Tammaro

Sharon Cinquegrana

Rodrigo Soulé

Sidonie Garnier

Triston Lavergne

Roberta Previtera

Lorena Marchant

Enfin

a donné toutes les conditions pour parvenir au point de soutenir une thèse.

Résumé de la thèse

Chapitre 1 : Introduction Une baisse des prix et de la consommation énergétique ainsi que une miniaturisation des composants ont entrainé une forte augmentation de l'utilisation de réseaux de capteurs. De nouveaux outils mathématiques ont permis une nouvelle modélisation des réseaux de capteurs : deux de ces outils sont l'analyse stochastique et la topologie algébrique. En analyse stochastique, introduite dans les années 90 par Baccelli, le déploiement des réseaux de mobiles et de capteurs est considéré comme un processus ponctuel de Poisson, à la place du comportement déterministe utilisé auparavant. Dix ans plus tard, Ghrist a choisi de modéliser la couverture des réseaux de capteurs comme un complexe simplicial. Par conséquent, on pouvait appliquer des résultats de topologie algébrique à de tels réseaux. Ces résultats ont permis le calcul explicite de l'homologie du complexe simplicial. Donc, il a été possible de répondre à des questions pertinentes et non-triviales qui se posent dans les réseaux de capteurs, chaque acteur n'ayant aucune connaissance du réseau autre que son identifiant et ceux de ses voisins. De telles questions sont : "le réseau est-il connecté ?", "la région cible est-elle couverte ?", et "combien de composantes connexes et de trous y a-t-il dans le réseau ?".

Cette thèse est composée de deux parties. La première partie utilise l'analyse stochastique pour fournir des bornes pour la probabilité de surcharge de différents systèmes grâce aux inégalités de concentration. Bien qu'ils soient généraux, nous appliquons ces résultats à des réseaux sans-fil réels tels que le WiMax et le trafic utilisateur multi-classe dans un système OFDMA. Dans la seconde partie, nous trouvons des liens entre la topologie de la couverture dans un réseau de capteur et celle du complexe simplicial correspondant. Cette analogie met en valeur de nouvelles facettes des certains objets mathématiques comme les nombres de Betti, le nombre de k-simplexes, et la caractéristique d'Euler. Puis, nous utilisons conjointement la topologie algébrique et l'analyse stochastique, en considérant que les positions des capteurs sont une réalisation d'un processus ponctuel de Poisson. Nous en déduisons les statistiques du nombre de k-simplexe et de la caractéristique d'Euler, ainsi que des bornes supérieures pour la distribution des nombres de Betti, le tout en d dimensions. Nous démontrons aussi que le nombre de k-simplexes converge vers une distribution Gaussienne quand la densité de capteurs tend vers l'infini à une vitesse de convergence connue. Enfin, nous nous limitons au cas unidimensionnel. Dans ce cas, le problème devient équivalent à résoudre une file M/M/1/1 préemptive. Nous obtenons ainsi des résultats analytiques pour des quantités telles que la distribution du nombre de composantes connexes et la probabilité de couverture totale.

Les capteurs et les réseaux de capteurs

Un capteur est un outil capable de balayer un domaine spatial et de transmettre un signal permettant d'obtenir des informations. Les capteurs varient selon à leurs fonctions de telle sorte que nous pouvons les utiliser pour récuperer des donnés sismiques, thermiques, magnétiques, visuelles, acoustiques, etc. Un réseau de capteurs permet l'interpolation d'informations ponctuelles d'un phénomène, obtenues par les capteurs vers des dimensions plus grandes. La définition de la couverture d'un capteur dépend de sa fonction, mais elle est essentiellement donnée par tous les points qui sont à une distance (pour une norme quelconque) inférieure à une borne ǫ.

Les outils mathématiques

Les deux outils mathématiques principaux utilisés dans la thèse sont la topologie algébrique et le processus ponctuel de Poisson. La topologie algébrique permet d'évaluer la transition locale-globale : quelques informations globales telles quelles la connectivité, la couverture et la caractéristique d'Euler peuvent être obtenues tout simplement par l'échange d'informations parmi des capteurs proches les uns des autres, sans avoir besoin de connaître leurs positions, leurs orientations ou que l'information enregistrée par un capteur soit transmise plus loin qu'à ses voisins les plus proches.

Le processus ponctuel de Poisson, depuis les années 1990, est la base des modèles stochastiques pour les réseaux. Dans cette approche, la représentation physique du réseau est préservée, mais les positions géographiques des capteurs ne sont plus modélées comme s'elles étaient fixes, donc aucun déployment du réseau non-aléatoire ne nous est utile. Au lieu de cela, cette méthode nous permet de prendre quelques caractéristiques importantes pour le résau étant donné la densité de ces points. En outre, les processus ponctuels de Poisson possèdent le plus grand nombre de résultats parmi tous les processus ponctuels, ce qui motive son usage pour la modélisation des noeuds des réseaux de capteurs.

Chapitre 2 : Le modèle stochastique

Le principal modèle stochastique utilisé dans cette thèse est celui du processus ponctuel de Poisson. A une filtration juste, ce processus peut être vu comme une Martingale et ainsi tous les outils du calcul de Malliavin peuvent être directement utilisés. Les définitions et les résultats les plus importants en déduits sont décrits à la suite.

Le processus ponctuel de poisson

Pour caractériser l'aléa du système, nous considérons que l'ensemble de points est représenté par un processus de Poisson ω à intensité λ dans un espace Y . L'espace de configurations sur Y , est l'ensemble des mesures de points simples et localement finis :

Ω Y = ω = n k=0 δ(x k ) : (x k ) k=n k=0 ⊂ Y, n ∈ N ∪ {∞} ,
où δ(x) denote la mesure de Dirac en x ∈ Y . Localement fini veut dire que ω(K) < ∞ quelque soit le compact K dans Y . Normalement, il convient d'identifier un élément ω dans Ω Y avec l'ensemble qui correspond à son support, c'est-à-dire que n k=0 δ(x k ) est identifié avec l'ensemble non-ordonné {x 1 , • • • , x n }. Si A ∈ B(Y ), nous avons δ(x k )(A) = 1 [x k ∈A] , alors:

ω(A) = x k ∈ω 1 [x k ∈A] = A dω(x),
compte le nombre d'atomes contenus dans A.

Nous définissons E λ [F (ω)] comme l'espérance d'une fonction F qui ne dépend que de ω étant donné que l'intensité de ce processus est λ et P λ [ω ∈ Y ] = E λ 1 [ω∈Y ] . Par analogie, nous définissons V λ [F (ω)] et Cov λ [F (ω), G(ω)], de même que

∆ n = {(x 1 , • • • , x n ) ∈ Y n | x i = x j , ∀i = j}. Soit f (x 1 , • • • , x n ) une
fonction mesurable F (ω) est une variable aléatoire donnée par :

F (ω) = x i ∈ω∩A,1≤i≤n x i =x j if i =j f (x 1 , • • • , x n ) = A∩∆n f (x 1 , • • • , x n ) dω(x 1 ) • • • dω(x n ).
Une proprieté bien connue du processus ponctuel de Poisson, la formule de Campbell, établit que

E λ [F (ω)] = A f (x 1 , • • • , x n ) dλ(x 1 ) • • • dλ(x n ).
Un processus ponctuel de Poisson marqué ayant les marque dépendantes de la position tel quel la loi de probabilité de la marque Y n ne dépend que de la position X n à travers d'un noyau K:

P(Y n ∈ B | ω) = K(X n , B), for any B ⊂ X.
Si K est un noyau de probabilité, c'est-à-dire que K(x, X) = 1 pour quelque soit x ∈ R k , alors ω ′ est un processus de Poisson d'intensité K(x, dy) dλ(x) sur R k × R m . Si f : R k × R m → R est une fonction non-négative mesurable, soit

F = f dω ′ = Xn∈ω f (X n , Y n ).
Alors, nous pouvons utiliser un résultat équivalent à la formule de Campbell, pour les processus ponctuels marqués :

E λ,K [F ] = R k ×R m
f (x, y) K(x, dy) dλ(x).

Pour un large ensemble de fonctions symetriques f , l'intégrale stochastique de Poisson I n (f n ) est définie telle que :

I n (f n )(ω) = ∆n f n (x 1 , • • • , x n )( dω(x 1 ) -dλ(x 1 )) • • • ( dω(x n ) -dλ(x n )).
Cette définition nous permet de décomposer une fonction F ∈ L 2 (Ω Y , P) en une somme d'intégrales stochastiques :

F = E λ [F ] + ∞ n=1 I n (f n ).
Nous utilisons trois opérateurs à partir de cette décomposition : le gradient D t , l'opérateur de Ornstein-Uhlenbeck L et son inverse L -1 . Les définitions de ces opérateurs, dans des cadres où ils sont définis, sont les suivantes :

D t F = n≥1 nI n-1 (f n ( * , t)), LF = - ∞ n=1 nI n (f n ), L -1 F = - ∞ n=1 1 n I n (f n ).
Deux théorèmes importants utilisés dans cette thèse découlent des propriétés du calcul de Malliavin. Le premier établit que si la fonction F est telle que E λ [F ] = 0 et Var(F ) = 1, alors

d W (F, N (0, 1)) ≤ E λ 1 - Y [D t F × D t L -1 F ] dλ(t) + Y E λ |D t F | 2 D t L -1 F dλ(t).
L'autre, que si D t F < K pour tous les t, K ≥ 0 et DF L ∞ (Ω,L 2 (Y )) < ∞, alors

P(F -E λ [F ] ≥ x) ≤ exp - x 2K log 1 + xK DF L ∞ (Ω,L 2 (Y ))
.

Ce résultat est aussi valable pour les processus ponctuels de Poisson marqués.

Chapitre 3 : Modèle de température d'interférence dans des réseaux de radio cognitives

Dans ce chapitre nous nous proposons d'appliquer le modèle du Processus ponctuel de Poisson dans une approche de la température d'interférence (interference temperature, IT) pour l'usage du spectre de fréquence pour des réseaux de communication sans fil. Dans cette approche, les utilisateurs secondaires (USs) peuvent utiliser les bandes des utilisateurs primaires (UPs) tant que cela ne cause pas de dommages à la communication de ces derniers.

Le modèle physique

Dans l'approche de l'IT, les utilisateurs secondaires traitent les autres USs, les UPs, le bruit et déautres sources d'interférence comme dess interférence. Puis ils ajustent leur puissance de transmission de telle sorte qu'il n'y ait pas de dommage pour les UPs. La température d'interférence est donnée par :

T I (f c , B) = P I (f c , B) kB ,
où T I est estimée en Kelvin, P I en Watts, la bande considérée est centrée à f c avec une largeur de B, en Hertz et k est la constante de Boltzmann. Sont présentés deux modèles différents d'IT : le modèle idéal et le généralisé. Le premier limite l'interférence des signaux des UPs, et dès lors la connaissance de l'activité des UPs devient nécessaire. La relation suivante exprime ce modèle :

T I (f i , B i ) + M i P kB i ≤ T L (f i ) ∀ 1 ≤ i ≤ n,
où P est la puissance d'interférence moyenne des USs qui opèrent avec la fréquence centrale f c et avec largeur de bande B ; T L est la température limite établie et la constante M i représente l'atténuation entre l'émetteur secondaire et le récepteur primaire. Pour le modèle généralisé, l'activité des UPs n'est pas demandée, de telle sorte que le modèle peut être appliqué sur toute la largeur de bande, indépendament des positions des UPs. Nous avons donc :

T I (f c , B) + M P kB ≤ T L (f c ).
Le modèle utilisé pour l'atténuation de la puissance transmise est connu sous le nom de path loss, et établit une diminution polynommiale des signaux par rapport à la distance de la source. Ainsi, la puissance du signal dans une coordonnée y, compte tenu que le signal a été transmi dans la coordonnée x à une puissance µ j est donnée par : p j (x, y) = min µ j , µ j r 0 xy α , α étant le coefficient du path loss et r 0 une distance de référence.

La capacité moyenne des utilisateurs sécondaire

Les expressions pour l'approche de l'IT étant bien définies, nous pouvons appliquer le processus ponctuel de Poisson pour placer les utilisateurs. Dans cette section, nous calculons la capacité permise pour les utilisateurs secondaires lorsque la condition de ne pas dommager les UPs n'est respectée que pour des quantités moyennes. La densité moyenne des UPs est donnée par λ 1 , celle des USs par λ 2 et celle des interféreurs est donnée par λ 3 . Tout d'abord, nous obtenons la puissance maximale permise aux USs pour le cas idéal :

µ id 2 ≤ (α -2)T L kB i -λ 3 µ 3 πα λ 2 πα •
Pour le cas généralisé, nous avons :

µ gen 2 ≤ (α -2)T L kB -λ 3 µ 3 πα -B i B λ 1 µ 1 πα λ 2 πα •
Avec ces expressions, nous utilisons le théorème de Shannon-Hartley, qui détermine la limite de la capacité donné par :

C(x, y) = B log 2 1 + p 2 (x, y) E λ [I(x)] ,
pour avoir la capacité moyenne de communication des utilisateurs secondaires telle que si la puissance transmise est égale à la puissance moyenne, les USs ne causeront pas de dommage aux UPs :

C = 2BK 2 α R 2 2 ln(2) ln(1 + K) 2K 1 α + h R 2 K 1 α , α -h 2 K 1 α , α .
Dans ce résultat, nous avons :

K µ 2 E λ [I(x)] = µ 2 (α -2) πα B i B µ 1 λ 1 + µ 2 λ 2 + µ 3 λ 3
Pour le cas idéal, il suffit de remplacer µ 2 par µ id 2 et pour le cas généralisé, nous remplaçons µ 2 par µ gen 2 . La fonction h est définie ainsi :

h(r, t) r 0 ln 1 + 1 x t x dx.
Il est possible de trouver des expressions explicites pour h quand α est un entier positif. La capacité total du réseau est donnée à partir de l'expression suivante :

C total = D C(x, y) 1 [{ x-y ≤R 2 }] πR 2 2 dyλ 2 dx.
Cela nous permet de trouver les capacités totales dans les deux cas, puisque

C total = Cλ 2 πR 2 .
Une borne supérieure de la probabilité de dommage pour les UPs La section précédente considérait que les puissances transmises par les USs étaient tout le temps égales à leurs valeurs moyennes. Pourtant, si la distribution de la somme d'interférences est approximativement symétrique, la restriction ne sera pas respectée dans environ 50% des cas. Dans cette section, nous utilisons les inégalités de concentration pour trouver une relation explicite entre la probabilité de dommage pour les UPs et la puissance transmise par les USs.

En utilisant l'inégalité de concentration :

P(F ≥ t + m F ) ≤ exp - t 2s g 1 + ts v F .
Si l'interférence totale est donné par la somme des interférences, il nous faut maintenant utiliser la formule de Campbell afin de trouver m F and v F :

m F = E λ x i ∈ω 2 p 2 (x i , 0) + E λ x i ∈ω 3 p 3 (x i , 0) , v F = E λ x i ∈ω 2 p 2 2 (x i , 0) + E λ x i ∈ω 3 p 2 3 (x i , 0) ,
où ω 2 et ω 3 sont des processus ponctuels de Poisson : ω 3 représent le déploiment des interféreurs et ω 2 le déploiement des USs. Pour le cas idéal, nous obtenons alors :

m F = απ(µ 2 λ 2 + µ 3 λ 3 ) (α -2) , v F = 2απ(µ 2 2 λ 2 + µ 2 3 λ 3 ) (2α -2) et s = max(µ 2 , µ 3 ).
Pour le cas généralisé, nous avons :

m F = απ( B i B µ 1 λ 1 + µ 2 λ 2 + µ 3 λ 3 ) (α -2) , v F = 2απ( B i B µ 1 2 λ 1 + µ 2 2 λ 2 + µ 2 3 λ 3 ) (2α -2) et s = max B i B µ 1 , µ 2 , µ 3 .
La rélation entre la probabilité de dommage et la puissance transmise est donnée par

P(F ≥ T L (f i )kB i ) ≤ exp - T L (f i )kB i -m F 2s ln 1 + (T L (f i )kB i -m F )s v F = P sup .
Prenons le cas idéal quand µ 2 > µ 3 . Si nous définissons µ q 2 comme la puissance de transmission telle que la probabilité de dommage pour les UPs est plus petite que q et η est le rapport entre la puissance de transmission et la puissance de transmission pour le cas moyen qu'a été discuté auparavant, µ id 2 , alors nous avons, µ q 2 = ηµ id 2 . Rappelons aussi que η est une fonction de q. Donc q = exp λ 2 πα 2(α -2) η(q) -1 η(q) ln 1 + 2(α -1) (α -2) 1η(q) η(q) • Le résultat ci-dessus est le plus important de ce chapitre, car il signifie que dès que q(η) est une bijection, nous pouvons écrire η en fonction de q, et donc que nous pouvons obtenir la puissance de transmission des USs à partir de la probabilité de dommage maximale pour les UPs.

Chapitre 4 : Une borne supérieure de la probabilité de perte dans un système OFDMA

Nous présentons dans ce chapitre une autre application du processus ponctuel de Poisson afin de modéliser un système sans fil basé sur l'OFDMA (Orthogonal Frequency Division Multiple Access). Tandis que l'IT permet l'usage d'une même partie du spectre aussi par plusieurs utilisateurs, l'OFDMA ne le permet pas. Dans ce dernier cas, le système distribue le spectre dynamiquement, de façon à permettre le plus grand nombre d'utilisateurs possible dans le réseau.

Le modèle physique considère que :

• La position de chaque utilisateur est indépendente de celles des autres et leurs positions sont distribuées identiquement ;

• Le temps d'arrivée entre deux demandes pour service consecutives dans le système est distribué exponentialement ;

• Le temps de service pour chaque utilisateur est exponentialement distribué avec une moyenne de 1/ν ;

• La cellule C du réseau est circulaire, elle a une antenne placée en son centre et son rayon s'appelle R ;

• La densité superficielle de l'arrivée d'utilisateurs est constante.

Avec ces hypothèses, nous pouvons montrer que le processus ponctuel des utilisateurs actifs (ceux qui communiquent) est, en équilibre, un processus ponctuel de Poisson. Si le système possède N 0 sous-canaux, nous pouvons dire que la probabilité de perte est donnée par :

P loss = P λ N dω ≥ N 0 ,
de plus, N est le nombre de sous-canaux utilisés par un utilisateur placé à x, peut être exprimé ainsi :

N (x) =       C 0 W log 2 1 + P t KG (I + η) x γ      
• Dans cette expression, g est le gain de puissance dans le canal, C 0 est la capacité demandée par les utilisateurs, P t la puissance des signaux à la source, I l'interférence des autres cellules, γ le coefficient de path loss, η le bruit et W la largeur de bande de chaque souscanal.

Si, en plus, la perte de puissance d'un canal ne dépend que de la distance entre la source et le récepteur, nous obtenons :

P λ N dω ≥ αm N ≤ exp - v N N 2 max g (α -1)m N N max v N , où m N = πρ ν Nmax j=1 j(R 2 j -R 2 j-1 ) et v N = πρ ν Nmax j=1 j 2 (R 2 j -R 2 j-1 ).
Nous pouvons aussi considérer que G est aléatoire et si nous prenons S = 1/G, tel que p S (y) = ξ √ 2πσy exp -(10 log 10 yµ) 2 2σ 2 , où ξ = 10/ ln 10, nous avons le modèle d'interférence connu sous le nom de shadowing. Si un utilisateur ne peut communiquer que lorsque le rapport signal-interférence est supérieur à une constante β min , le nombre maximal de sous-canaux est limité par

N max = C 0 W log 2 (1 + β min ) •
Le nombre de sous-canaux demandé par un utilisateur placé à x qui a un gain y est donné par :

N (x, y) =       C 0 W log 2 1 + P t K ηy x γ       .
Par ailleurs, nous obtenons des résultats explicites en fonction des paramètres qui ont déjà été définis. Et, enfin, nous pouvons aussi considérer des différents besoins de capacité : par exemple, une classe d'utilisateurs qui souhaitent envoyer des données (et qui a besoin d'une capacité moins élevée) et une classe d'utilisateurs qui souhaitent télécharger des vidéos (et qui a ainsi besoin d'une capacité plus élevée). Dans ce cas là, une classe j a besoin de communiquer à une capacité C j . Si C max = max j C j , alors

N max = C max W log 2 (1 + β min )
.

En plus, le nombre de sous-canaux demandé par un utilisateur à x est aussi une fonction de j, et nous avons :

N (x, j, y) =       C j W log 2 1 + P t K ηy x γ       .
Le résultat le plus générique de ce chapitre (avec un gain aléatoire, et des classes d'utilisateurs différentes) est le suivant :

P λ N dω ≥ αm N ≤ exp - v N 2 max g (α -1)mN max v , où m = M j=1
N (x, j, y)λ j (x)p S (y) dx dy,

et v = M j=1
N (x, j, y) 2 λ j (x)p S (y) dx dy.

Soit N 0sup le nombre de sous-canaux utilisé pour avoir une probabilité de perte P sup et N 0 sim le nombre de sous-canaux utilisé pour avoir la probabilité de perte si nous simulons le réseau. Si nous utilisons le résultats de ce chapitre, nous observons qu'à partir de la table 4.3, N 0sup est approximativement 20% plus grand que N 0 sim , ce qui montre que l'usage de la borne supérieure pour le projet du système est réalisable.

Chapitre 5 : Topologie algébrique

La topologie algébrique est utilisée dans ce travail afin d'extraire certaines propriétés des réseaux à partir d'informations données par des éléments discrets qui créent ces réseaux. Les objects topologiques utilisés pour la modélisation des réseaux de capteurs sont les complexes simpliciaux. Tandis que les graphes représentent des relations binaires, les complexes simpliciaux représentent des relations d'ordre supérieur.

Étant donné un ensemble de points V , un k-simplexe est un sous-ensemble non-ordonné

{v 0 , v 1 , • • • , v k } où v i ∈ V et v i = v j pour tout i = j. Les faces du k-simplexe {v 0 , v 1 , • • • , v k } sont définies comme tous les (k -1)-simplexes de la forme {v 0 , • • • , v j-1 , v j+1 , • • • , v k } où 0 ≤ j ≤ k.
Un complexe simplicial est une collection de simplexes fermée par rapport à l'inclusion de faces, i.e., si {v 0 , v 1 , • • • , v k } est un k-simplexe, alors toutes leurs faces sont inclues dans l'ensemble de (k -1)-simplexes.

Étant donné U = (U v , v ∈ T) une collection d'ensembles ouverts le complexe de Cech de U appelé C(U) est le complexe simplicial abstrait où k-simplexes correspondent à

(k + 1)-tuples d'éléments distincts de U qui n'ont pas d'intersection vide, c'est-à-dire que {v 0 , v 1 , • • • , v k } est un k-simplexe si et seulement si k i=0 U v k = ∅.
On peut définir l'orientation d'un simplexe en définissant un ordre dans leurs sommets. Un changement d'orientation correspond à un changement de signe des coefficients tel que

[v 0 , • • • , v i , • • • , v j , • • • , v k ] = -[ v 0 , • • • , v j , • • • , v i , • • • , v k ].
Soit X un complexe simplicial. Pour chaque entier k, C k (X) est l'espace vectoriel engendré par l'ensemble de k-simplexes de X. L'opérateur appelé boundary map ∂ k est défini pour être une transformation linéaire

∂ k : C k → C k-1 qui a comme domaine les éléments de la base de C k , par exemple [v 0 , • • • , v k ], via ∂ k [v 0 , • • • , v k ] = k i=0 (-1) k [v 0 , • • • , v i-1 , v i+1 , • • • , v k ].
Cet opérateur permet la construction d'un complexe enchaîné : une suite d'espaces vectoriels et des transformations linéaires

• • • ∂ k+2 -→ C k+1 (X) ∂ k+1 -→ C k (X) ∂ k -→ C k-1 (X) • • • ∂ 2 -→ C 1 (X) ∂ 1 -→ C 0 (X).
Il est possible de montrer que pour quel que soit k entier positif, k,

∂ k • ∂ k+1 = 0.
Nous définissons ker ∂ k comme le noyau de ∂ k sur C k (i.e., tous les cycles qui sont fermés), im ∂ k comme l'image de ∂ k (i.e., les k -1-simplexes qui sont déjà des faces de k-simplexes).

Et si nous définissons

Z k = ker ∂ k and B k = im∂ k+1 , cela induit que B k ⊂ Z k . L'homologie k-dimensionelle de X, H k (X), est l'espace vectoriel quotient H k (X) = Z k (X) B k (X) •
et le k-ème nombre de Betti de X est sa dimension

β k = dim H k = dim Z k -dim B k .
L'invariant topologique nommé caractéristique d'Euler pour X, χ(X), est un entier défini par :

χ(X) = ∞ i=0 (-1) i β i .
Dans la thèse, s k représente le nombre de k-simplexes dans un complexe simplicial X et il est connu que :

χ(X) = ∞ i=0 (-1) i s i .
Nous appelons aussi T d a le tore d-dimensionel de coté a. Le complexe de Rips-Vietoris dans T d a est défini de la façon suivante : pour chaque ǫ > 0, le complexe de Rips-Vietoris de ω, R ǫ (ω) est le complexe simplicial abstrait où chaque k-simplexe correspond à (k + 1)-tuples non-ordonnés de points dans ω qui sont deux à deux plus proche que ǫ. Nous démontrons que pour un tore T d a et pour la norme produit d ∞ , R ǫ (ω) a le même type d'homotopie que le complexe de Cech C 2ǫ (ω). Nous définissons aussi la fonction

h(v 1 , • • • , v k ) comme étant : h(v 1 , • • • , v k ) = h k (v 1 , • • • , v k ) = 1≤i<j≤k 1 [ v i -v j <2ǫ] ,
qui détermine si un ensemble de k points distincts ordonnés forment un (k -1)-simplexe (h = 1) ou non (h = 0).

Soit ω ∈ T d a un ensemble de points qui forment le complexe simplicial C ǫ (ω). Les trois propositions sont démontrées dans la thèse :

• Si i > d, β i (ω) = 0 ;
• Il n'y a que deux valeurs possibles pour le d-ème nombre de Betti de C ǫ (ω) : sont égales pour quelque soit le

i) β d = 0, or ii) β d = 1. Si β d = 1, on a aussi χ(C ǫ (ω)) = 0. • Soit X un sous-ensemble compact de R d et τ : X → Y où x i = ky i pour x i ∈ X, y i ∈ Y et k une constante réelle positive. Appelons τ * ω la mesure image de ω par τ , i.e., τ * : Ω X → Ω Y est l'application ω = ∞ i=1 δ(x i ) vers τ * ∞ i=1 δ(kx i ). L'application τ * : Ω X → Ω Y établit
k si λ τ = λ/k d et ǫ τ = kǫ.

Applications aux réseaux de capteurs

Le but de ce chapitre est d'arriver à faire le lien entre la topologie et les réseaux de capteurs. Le nombre de k-simplexes montre par lui-même des tendances dans les réseaux : si deux réseaux ont les mêmes paramètres, il est plus probable que celui qui a plus de 1-simplexes soit connecté. De la même façon, il est plus probable que celui qui a plus de 2-simplexes ait une couverture plus large que l'autre. D'une façon plus sophistiquée, les nombres de Betti mesurent directement le nombre de composants connexes (par β 0 ), le nombre de trous en deux dimensions (par β 1 ), le nombre de vides en trois dimensions (par β 3 ), etc.

Nous avons aussi une interprétation de la caracteristique d'Euler : χ = 0 est une condition nécessaire pour que le tore soit couvert et β d = 1 est une condition nécessaire et suffisante. Cela nous permet aussi d'évaluer la couverture en [0, a] d (i.e., nous ne prenons plus le tore), si nous faisons attention aux effets de bord. Par exemple, β d = 1 est une condition suffisante pour la couverture de [ǫ, aǫ] d .

Chapitre 6 : Les moments des k-simplexes et de la caractéristique d'Euler

Les résultats des chapitres 2 et 5 sont appliqués dans le chapitre 6. Dans le modèle physique des réseaux de capteurs proposé, chaque capteur représente un point et possède un rayon de couverture ǫ. Nous considérons aussi que les points sont ceux d'un processus ponctuel de Poisson et que la norme utilisée pour vérifier si deux points sont proches l'un de l'autre est la norme produit. En construisant le complexe de Cech à partir des points et de ǫ, nous avons, par conséquent, une représentation de la couverture du réseau par un complexe simpliciel. Comme démontré dans le chapitre précédent, la couverture de ce complexe est la même que celle des unions des couvertures. Ce fait permet de substituer un problème algébrique à un problème combinatoire. Finalement, nous supposons que ces points tombent dans un tore de d dimensions, T d a , de coté a, ce qui nous permet d'éviter les effets de bord.

La méthode utilisée est la suivante : nous exprimons le nombre de k-simplexes (sommets, arrêtes, triangles, tétrahèdres, etc.) comme des intégrales itérées d'un processus de Poisson. Les calculs des moyennes se réduisent aux calculs des intégrales déterministes grâce à formule de Campbell. En utilisant la définition de la caractéristique d'Euler, nous pouvons également trouver son espérance. Pour les moments d'ordre supérieur, nous exprimons le nombre de simplexes par une somme de chaos et à partir de cela, nous utilisons la formule de multiplication de chaos. Nous avons aussi établi que la distribution du nombre de sous-complexes dans un complexe simpliciel tend vers la Gaussienne, avec une vitesse de convergence maximale de λ -1/2

Premiers moments

Nous considérons toujours que ǫ ≤ a/6. Nous démontrons que l'espérance du nombre de (k -1)-simplexes, N k (C ǫ (ω)) (où simplement N k ), est donnée par :

E λ [N k ] = λ k (ak(2ǫ) k-1 ) d k! •
Il est possible aussi de trouver des expressions fermées pour N 2 et N 3 quand nous utilisons la norme Euclidienne :

• E λ [N 2 ]
pour le complexe de Rips-Vietoris ou celui de Cech :

E λ [N 2 ] = πλ 2 ǫ 2 a 2 2 ;
• E λ [N 3 ] pour le complexe de Rips-Vietoris :

E λ [N 3 ] = π π - 3 √ 3 4 λ 3 a 2 ǫ 4 6 ;
• E λ [N 3 ] pour le complexe de Cech :

E λ [N 3 ] = 2λ k a 2 (πǫ 2 ) 2 3 •
Si nous utilisons la dépoissonisation, nous obtenons l'espérance du nombre de simplexes E λ [N k ] étant donné un nombre fixe de points N 1 = n (quand le nombre de points est fixé, nous appelons le processus ponctuel de processus ponctuel Binomial) :

E [N k |N 1 = n] = n k k d 2ǫ a d(k-1)

•

Considérons le polynomme de Bell, défini par :

B n (x) = n k=0 n k x k ,
E λ [χ] = a 2ǫ d e -λ(2ǫ) d (-B d (-λ(2ǫ) d )).
Si nous utilisons encore la dépoissonisation dans ce résultat, l'espérance de χ quand les points font partie d'un processus ponctuel Binomial est donnée par :

E [χ|N 1 = n] = n k=0 n k k d 2ǫ a d(k-1)
, Ensuite, nous démontrons deux théorèmes qui nous permettent d'avoir des intuitions par rapport au comportement des β k :

• La fonction (λ → E λ [χC ǫ (ω)]) a exactement d racines réelles non-négatives. De plus, entre deux racines consécutives et après la plus grande, il y a exactement un point critique.

• Les nombres de Betti de la couverture convergent en probabilité vers les nombres de Betti dans le tore quand λ tend vers l'infini :

P λ d i=0 β i (C ǫ ) = β i (T d [a] ) λ→∞ ---→ 1.
A partir des propriétés obtenues pour l'espérance de la caractéristique d'Euler et basées sur des simulations, nous conjecturons que, dans un complexe simpliciel aléatoire tel qu'il est décrit dans ce chapitre, il y a toujours deux types de trous dominants en fonction de λ, ǫ et a : β i et β i+1 . Les autres nombres de Betti sont très peu importants par rapport à ceux qui sont dominants. Nous appliquons aussi les inégalités de concentration afin de trouver un comportement pour la queue de la distribution du nombre de composants connexes. Ce comportement valable pour y > λa d :

P λ (β 0 ≥ y) ≤ exp - y -λa d 2 log 1 + y -λa d (2 d -1) 2 λ •

Les moments de deuxième ordre

Pour les moments d'ordre plus grand qu'un, nous utilisons les formules du calcul de Malliavin. Pour cela, nous représentons N k dans la façon suivante :

N k = 1 k! k i=0 k i λ k-i I i (T d a ) i h(x 1 , . . . , x k ) dx 1 . . . dx k-i .
Si ǫ ≤ a/6 et si nous utilisons la formule de produit des chaos, la covariance entre le nombre de (k -1)-simplexes, N k , et le nombre de (l -1)-simplexes, N l , pour l ≤ k est donnée par :

Cov λ [N k , N l ] = l-1 i=0 1 i!(k -l + i)!(l -i)! (λ(2ǫ) d ) k+i a 2ǫ d k + i + 2 i(k -l + i) l -i + 1 d .
Il est possible de trouver la variance de N 2 et N 3 en prenant la norme euclidienne :

• Pour le Rips-Vietoris complexe :

V λ [N 2 ] = a 2ǫ 2 π 2 (4λǫ 2 ) 2 + π 2 (4λǫ 2 ) 3 ,
• Pour le Rips-Vietoris complexe :

V λ [N 3 ] = a 2ǫ 2 (4λǫ) 3 π 6 π - 3 √ 3 4 + (4λǫ 2 ) 4 π π 2 2 - 5 12 - π √ 3 2 +(4λǫ 2 ) 5 π 2 4 π - 3 √ 3 4 2   •
Rappelons aussi que nous pouvons obtenir ce résultat avec un nombre fixe de points, en faisant la dépoissonisation.

Les variances et covariances des nombres de simplexes nous permettent aussi de trouver la variance de la caractéristique d'Euler :

V λ [χ] = a 2ǫ d ∞ n=1 c d n (λ(2ǫ) d ) n , où c d n = n j=⌈(n+1)/2⌉   2 j i=n-j+1 (-1) i+j (n -j)!(n -i)!(i + j -n)! n + 2(n -i)(n -j) 1 + i + j -n d - 1 (n -j)! 2 (2j -n)! n + 2(n -j) 2 1 + 2j -n d .
Nous avons trouvé l'expression simplifiée de la variance de la caractéristique d'Euler après beaucoup d'algébrisme :

V λ [χ] = a λe -2λǫ -4λ 2 ǫe -4λǫ ,
pourtant, nous n'arrivons pas à trouver des expressions de la variance de la caractéristique d'Euler pour des dimensions plus grandes. Enfin, nous appliquons des inégalités de concentration pour trouver une borne pour la queue de la distribution de χ :

P(χ -χ ≥ x) ≤ exp - x 4 log 1 + 2x V λ [χ] .
Les moments de n-ème ordre

Pour simplifier les calculs, mais sans perte en généralité, nous choisissons k = 1/2ǫ, alors λ τ = λ(2ǫ) d , ǫ τ = 1/2 et ak = a/2ǫ. Nous calculons les moments centraux, définis par Ñk = N k -Nk . De plus, nous disons que i j = 0 si i ≤ 0 où j ≤ 0 où ij ≤ 0 pour i et j des entiers positifs.

Avant de trouver le n-ème moment pour le cas le plus générique, nous montrons comment utiliser la méthode pour le troisième moment. Soient C 1 , C 2 et C 3 trois simplexes qui ont des sommets en commun. Pour L ∈ P({1, 2, 3}), nous appélons m L le nombre de sommets appartenant à la liste d'exactement L simplexes.

Alors M = m 123 + m 12 + m 13 + m 23 + m 1 + m 2 + m 3 est le nombre total de sommets et J 3 représente l'intégrale dans ces trois simplexes :

J 3 = ∆p 1 ∆p 2 ∆p 3 h p 1 h p 2 h p 3 dx 1 . . . dx M . p i étant le nombre de sommets du simplexe C i pour i = 1, • • • , 3, par exemple, p 1 = m 123 + m 12 + m 13 + m 1 , et x 1 , • • • , x M étant
les M sommets. De plus, J 3 (i, j, s, t) est l'intégrale définie ci-dessus telle que

• m 123 = 2t -i -j + s ∨ 0 • m 12 = i + j -s -t ∨ 0 • m 13 = i -t ∨ 0 • m 23 = j -t ∨ 0 • m 1 = k -i ∨ 0 • m 2 = k -j ∨ 0 • m 3 = k -s ∨ 0.
Avec ces définitions, nous pouvons obtenir le troisième moment centré du nombre de (k -1)-simplexes :

E λ N k 3 = i,j,s,t λ 3k-i-j t! k i k j k s i t j t t i + j -s -t J 3 (i, j, s, t).
Pour trouver une expression pour le n-ème moment, nous procédons de façon de la même manière. Soient C 1 , • • • , C n , n simplexes qui partagent quelques sommets. Pour L ∈ P({1, • • • , n}), nous appelons m L le nombre de sommets appartenant à la liste d'exactement L simplexes. Donc M = L∈P({1,••• ,n}) m L est le nombre total de sommets et J n représent l'intégrale dans ces n simplexes:

J n = ∆p 1 • • • ∆p n h p 1 . . . h pn dx 1 . . . dx M . p i étant le nombre de sommets du simplexe C i pour i = 1, • • • , n, et x 1 , • • • , x M les M sommets.
L'expression de la n-ème puissance en chaos des (k -1)-simplexes est donnée par :

N n k = i 1 ,••• ,in s 1 ,•••s n-2 t 1 ,•••t n-2   n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   I a (• j∈A f i j )I b (• j∈A f i j ), où, pour j ∈ {1, • • • , n -2}: • 1 ≤ i 1 , • • • , i n ≤ k, • s j ≥ |m j,1 -m j,2 |, • m j,1 = i 2j-1 si 1 ≤ j ≤ ⌊ n 2 ⌋ et s 2(j-⌊ n 2 ⌋)-1 sinon, • m j,2 = i 2j si 1 ≤ j ≤ ⌊ n 2 ⌋ et s 2(j-⌊ n 2 ⌋) sinon, • u j = m j,1 + m j,2 -s j , • A ⊂ {1, • • • , n}, • Si n si pair, alors a = s n-3 et b = s n-2 , • Si n si impair, alors a = s n-2 et b = i n .
Avec ce résultat, après l'application du calcul de Malliavin, nous trouvons l'expression du n-ème moment des (k -1)-simplexes :

E λ N k n = i 1 ,••• ,in s 1 ,••• ,s n-3 t 1 ,••• ,t n-2 λ nk+c   n j=1 λ -i j k i j     n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   J n (i 1 , • • • , i n , s 1 , • • • , s n-3 , t 1 , • • • , t n-2 ). Pour j ∈ {1, • • • , n -2}: • si j ≤ n -3, s j ≥ |m j,1 -m j,2 |, • m j,1 = i 2j-1 si 1 ≤ j ≤ ⌊ n 2 ⌋ et s 2(j-⌊ n 2 ⌋)-1 sinon, • m j,2 = i 2j si 1 ≤ j ≤ ⌊ n 2 ⌋ et s 2(j-⌊ n 2 ⌋) sinon, • m j,3 = s j si 1 ≤ j ≤ n -3 et s n-3 sinon, • u j = m j,1 + m j,2 -m j,3 , • si n est pair, alors c = s n-3 et s n-3 ≥ |m n-2,1 -m n-2,2 | ∨ |m n-3,1 -m n-3,2 |, • si n est impair, alors c = i n et i n ≥ |m n-2,1 -m n-2,2 |.

La convergence

Soient Γ un sous-complexe simplicial arbitraire qui contient n points et C ǫ (ω) le complexe simplicial aléatoire généré par le processus ponctuel de Poisson ω. Le nombre d'occurrences de Γ dans C ǫ (ω) est défini comme G Γ (ω). Rappelons qu'avec cette construction de complexe simplicial, un complexe simplicial Γ apparaît en C ǫ (ω) si les arrêtes de Γ sont dans C ǫ (ω). L'ensemble d'arrêtes de Γ, appelé par J Γ , est un sous-ensemble de

{1, • • • , n} × {1, • • • , n}. Soit aussi h(x 1 , • • • , x n ) = 1 c Γ (i,j)∈J Γ 1 [ x i -x j ≤ǫ] ,
où c Γ est le nombre de permutations de

{x 1 , • • • , x n } tel que h Γ (x 1 , • • • , x n ) = h Γ (x σ(1) , • • • , x σ(n) ), et f Γ (x 1 , • • • , x n ) la symétrisation de h Γ (x 1 , • • • , x n ).
Alors, nous avons :

G Γ = x 1 ,••• ,xn∈ω x i =x j if i =j f Γ (x 1 , • • • , x n ) = ∆n f Γ (x 1 , • • • , x n ) dω(x 1 ) • • • dω(x n ).
Avec cette définition, nous obtenons le théorème de convergence le plus important de cette section. Ce théorème établi qu'il y a une constante c Γ telle que, pour λ assez grand, la distance de Wasserstein entre

F = G Γ -E λ [G Γ ] √ V ar(G Γ )
et N (0, 1) est donnée par :

d W (F, N (0, 1)) ≤ c λ 1/2 •

Chapitre 7 : Le cas unidimensionnel

Le chapitre précédent traite du problème des réseaux de capteurs en d dimensions. Bien que nous ayons trouvé plusieurs résultats, il y a quelques questions qui n'ont pas été résolues, par exemple, celle de la moyenne du nombre de composants connexes. Nous avons réalisé que ces questions pourraient être résolues dans un cas plus restreint, quand les points tombent sur une droite ou sur un cercle. Dans ces cas-là, nous n'avons pas besoin d'utiliser les outils de la topologie algébrique.

Formulation du problème

Soit L > 0, nous supposons que le processus ponctuel de Poisson N d'intensité λ est sur [0, L]. Les atomes de N sont donnés par (X i , i ≥ 1). Donc, les variables aléatoires ∆X i = X i+1 -X i sont i.i.d. et exponnentialment distribuées. Nous fixons ǫ > 0. Nous disons que deux points placés respectivement sur x et y, sont directement connectés chaque fois que |x -y| ≤ ǫ. Pour i < j, deux points de N , nous disons que

X i et X j sont indirectement connectés si X l et X l+1 sont directement connectés pour quelque soit l = i, • • • , j -1.
Un ensemble de points connectés, directement où indirectement, est appelé un cluster, et cluster complet est celui qui commence et finit dans [0, L]. La connectivité du réseau est mesurée par le nombre de clusters.

Le nombre de points dans l'intervalle [0, x] est défini par

N x = ∞ n=0 1 [Xn≤x] . La variable aléatoire A i donnée par A i = X 1 si i = 1, inf{X j : X j > A i-1 , X j -X j-1 > ǫ} si i > 1,
représente le début du i-ème cluster, appelé par C i . De la même manière, la fin d'un cluster est définée par

E i = inf{X j + ǫ : X j > A i , X j+1 -X j > ǫ}.
Donc le i-ème cluster, C i , a un nombre de points donné par

N E i -N A i . Nous définissons aussi la longueur B i de C i comme E i -A i . La longueur intercluster, D i , est la distance entre la fin de C i et le début de C i+1 , c'est-à-dire, D i = A i+1 -E i , et ∆A i est la distance entre les deux premiers points de deux clusters consécutifs, C i et C i+1 , donnée par ∆A i = A i+1 -A i = B i + D i .
Le nombre de clusters complets est donné par β 0 , la distance entre le début du premier cluster et le début du (i + 1)-ème cluster est définie comme étant

U i = i k=1 ∆A k . Pour finir, nous définissons aussi ∆X 0 = D 0 = X 1 .
Nous avons trouvé les distributions de toutes les variables aléatoires présentées ci-dessus, tout d'abord avec les transformées de Laplace pour pouvoir après les inverser et ensuite trouver les expressions analytiques.

Les transformées de laplace

Les trois transformées de Laplace les plus importantes sont celles qui suivent :

• La longueur du i-ème cluster B i :

E e -sB i = 1 λ λ + s
L M m β 0 (•) (s) = a s (a + 1) Li -m 1 a + 1 , où Li t (z), z, t ∈ R, z < 1, est la fonction polylogarithmique qui a t comme paramètre, et qui esr définie par Li t (z) ∞ k=1 z k k t •

Les expressions analytiques

Dans cette section, nous inversons les tranformées de Laplace trouvées dans la dernière section. D'abord, nous obtenons l'expression pour les moments de β 0 :

M m β 0 (L) = m k=1 m k L ǫ -k k λǫe -ǫλ k 1 [L/ǫ>k] .
m k étant le nombre de Stirling du deuxième type. Nous utilisons donc ce résultat, donc, pour trouver l'expression de la distribution de β 0 , P(β 0 = n) :

P(β 0 = n) = 1 n! ⌊L/ǫ⌋-n i=0 (-1) i i! ((L -(n + i)ǫ)λe -λǫ ) n+i .
Cet inversion de la transformée de Laplace nous révèle un pair de transfomée entre les domaines x et s donnée par :

1 [x≥0] n! ⌊x/ǫ⌋-n i=0 (-1) i i! (x -(n + i)ǫ) 1 a n+i L ⇔ ae ǫs (ase ǫs + 1) n+1 .
Une fois que nous avons cette transformée, après l'usage de quelques proprietés fondamentales de la transformée de Laplace, nous pouvons obtenir les distributions de

B 1 et de U n , respectivement f B i (x) et f Un (x) : f B i (x) = λe -ǫλ p 0 (x -ǫ) + e -ǫλ d dx p 0 (x -ǫ) 1 [x>ǫ] , et f Un (x) = λe -ǫλ p n-1 (x -ǫ)1 [x>ǫ] , où p n (x) = P(β 0 = n|L = x).
Nous pouvons aussi obtenir la probabilité que [0, L] soit entièrement couvert par les capteurs. Soit R m,n (x) défini comme ci-dessous :

R m,n (x) = ⌊x/ǫ⌋-1 i=m   e -λǫ i+n i+n j=0 (λ[(1 -i)ǫ -x]) j j!   • Alors P([0, L] soit couvert) = R 0,1 (L) -e -λǫ R 0,1 (L -ǫ) -e -λǫ R 1,0 (L) + e -2λǫ R 1,0 (L -ǫ).
Le problème de connectivité des réseaux de capteurs aléatoires est donc entièrement résolu: nous avons trouvé des expressions analytiques simples pour représenter les distributions de β 0 , B i , U n de même que nous avon trouvé la probabilité que toute la région soit couverte, tout cela en fonction de L, ǫ, λ 0 , µ et t (nous rappelons que λ = λ 0 Le -t/µ ).

Cas particuliers

Nous avons résolu le problème de connectivité pour le cas où nous avions un nombre de clusters complets dans l'intervalle [0, L]. Nous pouvons aussi considérer deux cas légèrement différents. Dans le premier cas, nous comptons le nombre de clusters complets ou incomplets dans un intervalle, que nous appelons β ′ 0 . Nous obtenons l'expression suivante pour cette quantité :

P(β ′ 0 = n) = ⌊L/ǫ⌋+1 i=n (-1) i+n i n (G(i -1) + G(i)), for n ≥ 0, où G(k) = (-1) k   e -kλǫ k j=0 [λ(kǫ -L)] j j! -e -λL   1 [T >kǫ] .
Le deuxième cas particulier est celui où les points sont distribués sur un cercle de rayon L/2π et non plus sur une droite. Nous appelons χ le nombre de clusters dans ce cercle pour obtenir la distribution de χ :

P(χ = n) = e -λL 1 [n=0] + (1 -e -λL ) λe -ǫλ n! ⌊L/ǫ⌋-n i=0 (-1) i i! ([L -(n + i)ǫ]λe -ǫλ ) n+i-1 L + (n + i) 1 λ -ǫ .

Chapitre 8 : Conclusion

La contribution la plus importante de la thèse consiste en l'application simultanée de résultats de la topologie algébrique et de l'analyse stochastique aux réseaux de capteurs. Les outils du calcul de Malliavin ont été particulièrement utiles et la topologie a permis la création d'un lien entre le problème algébrique et le problème vu d'une façon combinatoire. Nous avons pu utiliser des outils de la mathématique moderne pour traiter quelques problèmes où l'usage des outils classiques a échoué. Nous remarquons aussi que nous avons obtenu des résultats qui ont des applications à la fin de chaque chapitre.

Abstract

Lower costs, lower power consumption, and hardware miniaturization have lead to a great increase in the use of sensor networks. New mathematical tools have enabled the conception of new models for sensor networks: two of these tools are stochastic analysis and algebraic topology. In stochastic analysis, as introduced by Baccelli in the 90s, deployment of mobiles and sensors in a nework is treated as a Poisson point process, instead of the deterministic behavior that was used before. Ten years later, Ghrist has started modelling the coverage of sensor networks as a simplicial complex. As a consequence, results of algebraic topology can be applied to such networks.These results have enabled the explicit computation of the homology of the simplicial complex. Therefore, it was possible to answer relevant and non-trivial questions related to sensor networks, each sensor having minimal information about the network (its identification number and the ones of his neighbors). Examples of such questions are: "is the network completely connected?", "is the target region covered?", and "how many connected components and holes are there in this network?".

This thesis has two main parts. Part I uses stochastic anlysis to provide bounds for the overload probability of different systems thanks to concentration inequalities. Although the results are general, we apply them to real wireless network systems such as WiMax and mutliclass user traffic in an OFDMA system. In part II, we find more connections between the topology of the coverage of a sensor network and the topology of its corresponding simplicial complex. These connections highlight new aspects of Betti numbers, the number of k-simplices, and Euler characteristic. Then, we use algebraic topology in conjunction with stochastic analysis, after assuming that the positions of the sensors are points of a Poisson point process. As a consequence we obtain, in d dimensions, the statistics of the number of k-simplices and of Euler characteristic, as well as upper bounds for the distribution of Betti numbers. We also prove that the number of k-simplices tends to a Gaussian distribution as the density of sensors grows, and we specify the convergence rate. Finally, we restrict ourselves to one dimension. In this case, the problem becomes equivalent to solving a M/M/1/1 preemptive queue. We obtain analytical results for quantites such as the distribution of the number of connected components and the probability of complete coverage. The importance of sensor networks grew tremendously in the last few decades in every field where observation of the physical world is useful. Those systems have already been inserted in a large range of sectors, and since the knowledge in electronics and communication technology is continuously expanding, it is expected that sensor networks will be an integral part of our lives, more than the present-day personal computers [START_REF] Akyildiz | Wireless sensor networs: a survey[END_REF][START_REF] Chong | Sensor networks: Evolution, opportunities, and challenges[END_REF].

Contents

The progressive miniaturization and the Moore law allow the development of low-cost, low-power, multifunctional sensor nodes. These features enable the practical usage of wireless sensor networks based on collaborative effort of a large number of nodes [START_REF] Akyildiz | Wireless sensor networs: a survey[END_REF][START_REF] Kahn | Mobile networking for smart dust[END_REF][START_REF] Lewis | Wireless Sensor Networks[END_REF]. As a consequence of this development, we have today a very wide range of domains of application, such as health monitoring, intelligent agriculture, environmental control, telematics, and space exploration. Overview of these and other applications are included in references [START_REF] Akyildiz | Wireless sensor networs: a survey[END_REF][START_REF] Estrin | Instrumenting the world with wireless sensor networks[END_REF][START_REF] Callaway | Wireless sensor networks: architectures and protocols[END_REF][START_REF] Karl | Protocols abd architectures for wireless sensors networks[END_REF][START_REF] Estrin | Connecting the physical world with persuasive networks[END_REF][START_REF] Pottie | Wireless integrated network sensors[END_REF][START_REF] Estrin | Next century challenges: scalable coordination in sensor networks[END_REF].

The conception of sensor networks requires, however, a multidisciplinary expertise that motivates the research that goes beyond only the improvement of the performances of the physical layer of the system. Dealing with sensor networks has to do with the integration between the physical dimension of transmission (signal, coding), to share properly the resources, to treat mechanisms that establish and maintain the connectivity and coverage (topology) of the network, to face the dynamics of the sensors (positioning, mobility and sensors default) and to model such systems. Moreover, these solutions must take into account the constraints of limited resources and low consummation [START_REF] Fleury | Réseaux de capteurs[END_REF].

In view of these particular features, sensor networks require new paradigms for communications: we need new tools (theories, heuristics, designs) conceived specifically for them. The topology of the networks is one important subject studied in this thesis, which includes connectivity and coverage. Loosely speaking, coverage describes how well sensors in the network can monitor a geographical region. The connectivity evaluates how much groups of sensors are disconnected among them.

Considering a variety of situations, it is possible to categorize three main scenarios: those where it is possible to choose the position of each sensor, perhaps best described as the 'computational geometry', e.g. in [START_REF] Li | Coverage in wireless ad hoc sensor networks[END_REF][START_REF] Meguerdichian | Coverage problems in wireless ad-hoc sensor networks[END_REF][START_REF] Tian | A coverage-preserving node scheduling scheme for large wireless sensor networks[END_REF][START_REF] Zhang | Maintaining Sensing Coverage and Connectivity in Large Sensor Networks[END_REF], those where sensors are arbitrarily deployed in the target region with the control of a central station (see [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] De | Coverage in sensor networks via persistent homology[END_REF][START_REF] Silva | Homological sensor networks[END_REF]), and those where the sensor locations are random in a decentralized system, which is analyzed, for example, in [START_REF] Koskinen | On the coverage of a random sensor network in a bounded domain[END_REF].

The problem of the first scenario is that, in many cases, placing the sensors is impossible.

Introduction

Sometimes this impossibility comes from the fact that the cost of placing each sensor is too high and sometimes the network has an inherent random behavior (like in the ad hoc case, where users move). In addition, this policy cannot take into account the configuration of the network in the case of failure of some sensor. The drawback of the second scenario is a higher unit cost per sensor, since each one has to communicate with the central station.

Besides, the central station itself increases the cost of the whole system. Moreover, if sensors are supposed to know their positions, an absolute positioning system has to be included in each sensor, making their hardware even more complex and as such, more expensive. This has motivated us to investigate the third scenario: randomly located sensors, no central station. Actually, if we can predict some characteristics of the topology of a random network, the number of sensors (or, as well, the power supply of them) can be a priori determined such that a given network may operate well with high probability. For instance, we can choose the mean number of sensors such that, if they are randomly deployed, there is more than 99% probability, for the network to be completely connected.

Topology of random geometric networks

The first studies concerning random points in a space with random pairwise relations have been elaborated by Erdös and Rényi [START_REF] Erdös | On random graphs, i[END_REF][START_REF] Erdös | On the evolution of random graphs[END_REF] and Gilbert [START_REF] Gilbert | Random graphs[END_REF] in the late 50s. While Erdös and Rényi assign an equal probability to all graphs with a specific number of edges, in the first model of Gilbert every possible edge between nodes occurs to have an independent probability p. Today, the model of Gilbert is called Bernoulli random graphs, or Erdös-Rényi graphs due to their research on the model of Gilbert. Although the models used by those authors are not equivalent, none of them considered the distance between nodes in order to determinate whether two points are connected or not. This observation led to name those graphs independent random graphs (IRG). The two different ways of approach have in common that they regard the connectivity between two points as a key element. By all means those models can be applied in telecommunications when the connexion does not depend on the distance, for instance, optical networks. Besides this model can also be applied to networks of power lines, computer networks, social links, business relations between companies, to name a few. Those random graphs and many of their properties were intensely studied [START_REF] Bollobás | Random Graphs[END_REF][START_REF] Alon | The Probabilistic Method[END_REF][START_REF] Janson | Random Graphs[END_REF].

The first model of random graphs where edges depend on the position of points, the dependent random graphs (DRG), can be traced back to the work of Gilbert in 1961 [START_REF] Gilbert | Random plane networks[END_REF]. In the model proposed by Gilbert, a pair of points is connected if this pair is separated by a distance smaller than some constant R. The resulting graph is called a random geometric graph (RGG). However, the dependence of points and edges of DRG's represents an important difficulty in comparison to IRG's: in the geometric setting, if the vertex V i is close to V j , and V j is close to V k , then V i will be fairly close to V k , that is, we do not have independence between edges any longer. On the other hand, the model of IRG's is too unrealistic to be used in wireless communication systems and the recent development of these systems has driven to intense researches of DRG's since the 90s. Some examples of DRG's that are not RGG's are the geometric Euclidean graphs [START_REF] Steele | Probability Theory and Combinatorial Optimization[END_REF][START_REF] Yukich | Probability Theory of Classical Euclidean Optimization Problems[END_REF] and the proximity graphs, where each point is connected to its k nearest neighbors [START_REF] Xue | The number of neighbors needed for connectivity of wireless networks[END_REF][START_REF] Balister | Connectivity of random knearest-neighbour graphs[END_REF][START_REF] Teng | k-nearest-neighbor clustering and percolation theory[END_REF]. However, these models do not capture basic properties of wireless systems: the conservation of energy imposes that the transmitted power decreases with the distance. Also the presence of noise imposes a maximum separation between source and receiver, which drove to the use of RGG's in recent works.

The cases of finite domains and infinite domains are treated differently. In the infinitespace case, the study of RGG's is known as percolation, where the object under study is the formation of giant connected components or complete connectivity. Indeed, the first RGG studied by Gilbert was about percolation (even if this name was not used, the term percolation was used for the first time in 1957 by Simon Broadbent and John Hammersley [START_REF] Broadbent | Percolation processes. i. crystals and mazes[END_REF]), where he proved that such giant components exist although. Percolation is an important branch of the modern probability theory and is intensively studied [START_REF] Grimmett | Percolation[END_REF][START_REF] Zuev | Continuous models of percolation theory[END_REF][START_REF] Zuev | Continuous models of percolation theory[END_REF][START_REF] Men | Estimation algorithms of infinite graphs percolation threshold[END_REF][START_REF] Meester | Continuum Percolation[END_REF].

In finite domain, RGG's are usually studied to derive asymptotic behavior for large finite graphs. The first work dates back to Hafner [START_REF] Hafner | The asymptotic distribution of random clumps[END_REF]. Since then, there were several works on this subject. In the 90s, applications of graph theory to probabilistic and statistical aspects of these graphs in one dimension were studied in the work of Godehardt et al. [START_REF] Godehardt | Graphs as Structural Models[END_REF][START_REF] Godehardt | On the connectivity of a random interval graph[END_REF][START_REF] Godehardt | The application of random coincidence graphs for testing the homogeneity of data[END_REF][START_REF] Harris | Probability models and limit theorems for random interval graphs with applications to cluster analysis[END_REF] and in the last decade we have [START_REF] Foh | A closed form network connectivity formula for onedimensional manets[END_REF][START_REF] Foh | Network connectivity of one-dimensional manets with random waypoint movement[END_REF][START_REF] Ghasemi | Exact probability of connectivity in onedimensional ad hoc wireless networks[END_REF][START_REF] Han | Connectivity Analysis of Wireless Ad-Hoc Networks[END_REF][START_REF] Han | One-dimensional geometric random graphs with nonvanishing densities: a very strong zero-one law for connectivity[END_REF], to cite a few. In higher dimensions, we have mathematical contributions from Appel and Russo [START_REF] Appel | The maximum vertex degree of a graph on uniform points in [0, 1] d[END_REF][START_REF] Appel | The minimum vertex degree of a graph on uniform points in [0, 1] d[END_REF][START_REF] Appel | The connectivity of a graph on uniform points in [0, 1] d[END_REF] and McDiarmid [START_REF] Mcdiarmid | Colouring proximity graphs in the plane[END_REF][START_REF] Mcdiarmid | Random channel assignment in the plane[END_REF]. The book of Penrose [START_REF] Penrose | Geometric Random Graphs[END_REF] is probably the most complete reference about the asymptotics for large finite graphs, compiling and complementing a series of works starting in 1995 [START_REF] Penrose | The longest edge of the random minimal spanning tree[END_REF][START_REF] Penrose | Extremes for the minimal spanning tree on normally distributed points[END_REF][START_REF] Penrose | A strong law for the largest nearest-neighbour link between points[END_REF][START_REF] Penrose | A strong law for the longest edge of the minimal spanning tree[END_REF][START_REF] Penrose | On k-connectivity for a geometric random graph[END_REF][START_REF] Penrose | Central limit theorem for k-nearest neighbour distances[END_REF][START_REF] Penrose | Vertex ordering and partitioning problems for random spatial graphs[END_REF][START_REF] Penrose | Focusing of the scan statistic and geometric clique number[END_REF][START_REF] Penrose | Weak laws of large numbers in geometric probability[END_REF].

Beyond the work of Gilbert, several other properties of RGG's have been explored. One of the most important property for wireless communications is the connectivity. There are efforts made in order to find out if a graph is completely connected, but also in order to count the number of components if there is more than one. This property was explored by means of geometric tools until Silva, Ghrist and Muhammad, in [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] Silva | Homological sensor networks[END_REF], introduced the use of algebraic topology for models of geometric graphs. Although the authors do not apply their idea at random realizations of points, their tools allow the local-to-global transition, because it is possible to calculate the number of connected components, called β 0 , with only on a list of edges and points. It means that, to apply algebraic topology to calculate β 0 , it is sufficient to label the points of the process. While a graph can be defined by a list of points and edges, a simplicial complex, used by Ghrist et al., is a list of points, edges, triangles, tetrahedrons and so on, which makes a graph to a particular case of a simplicial complex. As one can expect, this generalization gives much more information about the network. The first direct application is related to the coverage area in two or three dimensions.

Coverage is another widely studied subject of random realizations. In the beginning, it was not possible to point out the difference between the study of connectivity and coverage, because the research was done over circles. Many authors considered problems of covering a circle by a fixed number of arcs. In [START_REF] Whitworth | DCC Exercises on Choice and Chance[END_REF][START_REF] Fisher | On the similarity of the distributions found for the test of significance in harmonic analysis, and in stevens's problem in geometrical probability[END_REF][START_REF] Domb | The problem of random intervals on a line[END_REF][START_REF] Flatto | The random division of an interval and the random covering of a circle[END_REF][START_REF] Solomon | Geometric Probability[END_REF], the authors considered the covering when arcs have the same size. The works of Dvoretzki [START_REF] Dvoretzki | On covering a circle by randomly placed arcs[END_REF], Mandelbrot [START_REF] Mandelbrot | On dvoretski coverings for the circle[END_REF], Shepp [START_REF] Shepp | Covering the circle with random arcs[END_REF] and Siegel and Holst [START_REF] Siegel | Covering the circle with random arcs of random sizes[END_REF] regard this problem when arcs are not equal. The last one provides an exact formula for the probability of covering the circle, thereby extending Stevens [START_REF] Stevens | Solution to a geometrical problem in probability[END_REF]. Intuitively, one can say that the models of these works in one dimension are coverage problems, but in a point of view of topology, these papers deal with connectivity (counting the number of non-covered gaps is the same than counting the number of connected components). In more than one dimension, one of the early and now classical coverage problems is the coverage of a sphere, proposed by Moran in [START_REF] Moran | Random circles on a sphere[END_REF] and solved by Gilbert in [START_REF] Gilbert | The probability of covering a sphere with n circular caps[END_REF]. Extensions to k dimensions usually consider the asymptotics for models of fixed or Poisson distributed number of points like Hall in [START_REF] Hall | On the coverage of k-dimensional space by k-dimensional spheres[END_REF][START_REF] Hall | Introduction to the Theory of Coverage Processes[END_REF], Janson in [START_REF] Janson | Random coverings in several dimensions[END_REF] and Stoyan [START_REF] Stoyan | Stochastic Geometry and Its Applications[END_REF]. In the case of a Poisson process, when the individual covered domain 1. Introduction is of constant form with a Lebesgue measure A, the coverage is a simple problem, since the probability p of covering an arbitrary point is given by p = 1e -λA , where λ is the intensity of the process. A natural generalization of this case is to consider a fixed number of points i.i.d. in the target region, which was studied by Roy et al. in [START_REF] Athreya | On the coverage space by random sets[END_REF][START_REF] Roy | Coverage of space in booleans models[END_REF]. Other properties regarding the coverage were analyzed, for instance, the k-coverage [START_REF] Kumar | New technological vistas for systems and control: the example of wireless networks[END_REF] which studies the probability of a point being covered by k sensors, or the triangulation [START_REF] Li | Triangulation properties of the target area in wireless sensor networks[END_REF] which analyzes the probability of a point being inside some triangle formed by three points close from each other.

The use of topological algebraic on realizations seems to be an ideal tool to deal with the local-global transition, i.e. to obtain general aspects of coverage without knowing the exact positions of the points, such as the number of holes in two dimensions, called β 1 or voids in three dimensions, called β 2 , which are important questions for wireless networks that works using only geometry were not able to do. The main motivation to the study of random geometric simplicial complexes was their application to wireless networks given by the works [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] Silva | Coordinate-free coverage in sensor networks with controlled boundaries via homology[END_REF][START_REF] Muhammad | Control using higher order laplacians in network topologies[END_REF][START_REF] De | Coverage in sensor networks via persistent homology[END_REF][START_REF] Silva | Homological sensor networks[END_REF]. Other connected works with persistent homology [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF][START_REF] Zomorodian | Computing persistent homology[END_REF][START_REF] Edelsbrunner | Persistent homology -a survey[END_REF], which is a way of tracking how the homology of a sequence of spaces changes. At last, there are some works on random simplicial complexes that are not geometric, but the only ones that deal directly with geometric complexes are those from Kahle et al. [START_REF] Kahle | Limit theorems for betti numbers of random simplicial complexes[END_REF][START_REF] Kahle | Random geometric complexes. Discrete and Computational Geometry[END_REF], where the asymptotic behavior of the number of holes and voids, called Betti numbers, are found in some particular cases.

Overview of the Problem

A sensor is a device that scans a domain and returns a signal from which information may be extracted. Sensors vary in scope, resolution and types such as seismic, low sampling, rate magnetic, thermal, visual, infrared and acoustic, which are able to monitor a wide variety of ambient conditions such as temperature, pressure, light, humidity, vehicular movement, etc. Sensor nodes can be used for continuous sensing, event detection, event identification, location sensing and local control of actuators. In this section we present the way the functionality of the sensors is related to the interpretation of their coverage, and then, we show some practical applications to illustrate the potential of those networks.

Coverage

The miniaturization of the sensors justifies the fact that they can be represented as points in almost all applications in modern sensor networks. However, the concept of coverage is not as clear and usually not well explained. Then we consider three different situations to determinate coverage: one where sensors are supposed to communicate, one where sensors are supposed to perform a remote control and the third one where sensors monitor some conditions in their exact location. Depending on the function of the network, sensors can have more than one kind of coverage at the same time.

Sensors communicating

We first consider a sensor network where sensors upload/download data to/from other sensors. Sensors have a power supply allowing them to transmit a signal with a fixed power. It is well known that the transmitted power is attenuated over distance, an attenuation called path loss. Besides, power is affected by environmental conditions, a phenomenon modeled as shadowing. So the power received by a sensor is inferior to the one transmitted (except for rare events such as constructive interference due to multipath, for example). On the other hand, sensors have sensitivity, which means that they are able to identify correctly the signals with a desirable probability (with a low bit error rate) as long as the signal to noise ration is higher than some threshold, for instance, P s . In this case, the coverage of a sensor is defined as the whole region where others sensors can receive its signal with a power higher than P s . In Fig. 1.1 we illustrated the coverage radius ǫ in function of P s under the effect of path loss only.

Sensors monitoring conditions in their locations In this case, the sensor network is supposed to approximate the real profile of the measured quantity based on typical gradients of this one. This means that the coverage radius have to be chosen in order to warrant that sensors separated from each other at most by this radius are still able to fit or adjust with small errors. For instance, let us suppose that sensors measure temperature and that a sensor network is supposed to detect when the temperature exceeds some temperature T c . In Fig. 1.2, we see an example of a likely profile of the temperature gradient. In this case, we cannot choose a coverage radius ǫ 1 like the one in Fig. 1.2.a), since the sensor network could fail to detect the event of temperature higher than T c in the monitored region. However, a smaller coverage radius ǫ 2 , like in Fig. 1.2.b), would decrease considerably the probability of missing this event.

Sensors performing a remote control A large class of sensors is able to perform a remote control, such as light and movement sensors. In this case, coverage depends on the sensitivity of the receivers in the sensors, so, in order to be detected, the monitored event occurs closer than some distance.

Algebraic topology

The tools we present in this section have been developed in the 1930s, but it was only less than 10 years ago that they were applied to sensor networks, specifically in [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] Silva | Coordinate-free coverage in sensor networks with controlled boundaries via homology[END_REF][START_REF] Baryshnikov | Target enumeration via euler characteristic integrals i: sensor fields[END_REF][START_REF] De | Coverage in sensor networks via persistent homology[END_REF][START_REF] Silva | Homological sensor networks[END_REF]. The major contribution of algebraic topology is contemplating the local-to-global transition: global information of a sensor network such as connectivity, coverage and Euler characteristic can be obtained by using the information on the neighborhood of each node belonging to some sensor network. As a consequence, that global information is obtained without knowing the coordinates of the nodes, localization, orientation capabilities or any other information apart from their identities and the identities of close neighbors.

Roughly speaking, algebraic topology provides a way to associate to a given space X a collection of algebraic objects which gauge the global features of X. In our case, those global features are the called homology groups, H k (X), for k = 0, 1, . . . , and to determinate them, we use local objects built by simple oriented pieces, called simplices.

Given a set of points V , a k-simplex is an unordered subset {v 0 , v 1 , . . . , v k } where v i ∈ V and v i = v j for all i = j. The faces of the k-simplex {v 0 , v 1 , . . . , v k } are defined as all the (k -1)-simplices of the form {v 0 , . . . , v j-1 , v j+1 , . . . , v k } with 0 ≤ j ≤ k. In terms of coverage in a network, a 0-simplex represents a single sensor and a k-simplex represents that the k + 1 points of this simplex are covering the convex hull containing those points (see columns two and three in Fig. 1.3).

In the way that simplices were defined in this section, the Cech theorem establishes the link between a sensor network and a simplicial complex, showing that the union of the individual coverage of each sensor in the network and the simplicial complex obtained by these sensors and their coverages are topologically equivalent. This theorem is a consequence of the Nerve lemma [START_REF] Björner | Topological methods[END_REF]Theorem 10.7] and is seen in Chapter 5 of this thesis.

Poisson point processes

Since [START_REF] Baccelli | Stochastic geometry and architecture of communication networks[END_REF][START_REF] Baccelli | Stochastic geometry models of mobile communication networks[END_REF], Poisson point processes are the basis of stochastic-geometry modeling of communication networks. This modeling consists of treating the given architecture

Sensor network representation

Cech complex representation

Highest order simplices of the network as random and analyzing it in a statistical way. In this approach, the physical meaning of the network elements is preserved and reflected in the model, but their geographical locations are no longer fixed but modeled by random points. Consequently, any particular detailed pattern of locations is no longer of interest. Instead, the method allows catching the essential spatial characteristics of the network performance through the densities of these point processes.

S 1 v 1 A 0-simplex {v 1 } S 1 S 2 v 1 v 2 An 1-simplice {v 1 , v 2 } S 1 S 2 S 3 v 1 v 2 v 3 A 2-simplex {v 1 , v 2 , v 3 } S 1 S 2 S 2 v 1 v 2 v 3 Three 1-simplices {v 1 , v 2 }, {v 1 , v 3 } and {v 2 , v 3 }. S 1 S 2 S 3 S 4 ǫ ǫ ǫ ǫ v 1 v 2 v 3 v 4 A 3-simplex {v 1 , v 2 , v 3 , v 4 }
Poisson point processes can model both static and dynamic systems. In the first case, the communicating elements do not move although each one of them can be active or inactive (a sensor can be inactive due to a flaw or, intentionally, due to some protocol for instance) and it represents a network where there is no control over the deployment of each element in the target region, so the number of elements and their positions are random. In dynamic systems, the process represents a snapshot of the network. In some cases the random number of users is overdimensioned under this hypothesis, since this system would allow an arbitrarily large number of users in a system where resources, such as power or bandwidth, are limited.

Moreover, among all studied point processes, the Poisson one has the largest arsenal of results (see [START_REF] Daley | An introduction to the theory of point processes[END_REF][START_REF] Stoyan | Stochastic Geometry and Its Applications[END_REF]) and by using a proper filtration, the Poisson measure can be seen as a martingale. As consequence, as showed in Chapter 6 of [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings[END_REF], it is possible to use Malliavin calculus on such problems. The basic tools of Malliavin calculus consist in a gradient and a divergence operator that are linked by integration by parts formula. Along this thesis, the gradient operator D t will be used, and it can be defined by D y (F ) = F (ω ∪ y) -F (ω) of a given Poisson process ω, and an example of D y β 0 is given in Fig. 1.4. The stochastic analysis of a Poisson process warrants also the chaos representation of a large family of random variables F depending on ω ∈ A as

F = ∞ n=0 1 n! I n (f n ),
where the multiple Poisson stochastic integral I n (f n ), is defined in Chapter 2 as

I n (f n )(ω) = ∆n f n (x 1 , • • • , x n )( dω(x 1 ) -dλ(x 1 )) • • • ( dω(x n ) -dλ(x n )).
The gradient operator can compute the function f n as

f n (t 1 , . . . , t n ) = E λ [D t 1 . . . D tn F ] , a.e. t 1 , . . . , t n ∈ A.

Thesis Outline and Contributions

Let us turn to the contents of this thesis. Chapter 2 starts with an elementary exposition regarding the stochastic model of the positions of sensors/users. First some concepts of stochastic geometry are presented in order to define a Poisson point process and some properties such as the distribution of the number of point and the Campbell theorem. Then, we present some definitions and results of Malliavin calculus that are used in the thesis. Among the results of Malliavin calculus, we highlight the possibility of the decomposition if a large family of random variables depending on a Poisson point process as the sum of orthogonal chaos, each one being an Itô integral. If F is a random variable depending on the Poisson point process ω, the nth chaos represents the contribution of every set of n points on F . It also yields non-trivial results such as a concentration inequality used in Chapters 3, 4 and 6, allowing to find limits for the distribution of some random variables.

Chapter 3 uses the Poisson point process and concentration inequalities as analytical methods to apply to the interference temperature model. This model provides a way to reallocate spectrum bands more efficiently, giving some bandwidth at low power to opportunist users (the sensors) as long as they do not interfere the signal of licensed users (or primary users). We consider the position of the sensors in a given protocol (in this case WiMax) and we can use Campbell theorem to calculate how much power is available for those sensors such that, in the average, primary users ignore their presence in the system. However, the fact that this constraint is respected, on average, is not enough to design a system. The useful quantity is the probability of a primary user suffering an outage due to the fact that sensors use his bandwidth and it must be as low as possible. We are not able to calculate this probability but we can find an upper bound for the outage probability, so that we can design the transmitted power of the sensors such that the outage probability is lower than some threshold.

In Chapter 4 we study how an OFDMA system can be designed by using the tools presented in Chapter 2. An OFDMA system has a limited number of subchannels that distribute to the users in a cell and this system is overloaded if, at some instant, the demand of subchannels is larger than the number of available ones. Each user needs a different number of subchannels, which is a function of the channel fading and the type of service (data, voice, video, etc.). We aim to design the minimal number of subchannels a central station can provide as a function of the density of users and their needs such that the probability of overload of the system is low. This is done under reasonable assumptions, by considering that users positions at a given instant are given by the points of a Poisson process. This assumption overestimates the real number of users, since the number of available subchannels restricts the number of users in real cases. Then we use a the concentration inequality to obtain the main results.

In Chapter 5, we introduce the tools of topology. We make precise the idea of simplicial complexes, homology and Betti numbers. To determine those quantities we define a linear operator named boundary map and we use algebra. After defining these concepts, we show some other results that allow us to give even more concrete links between the model of simplicial complex in a torus and a sensor network.

It is mostly in Chapter 6 that we apply the tools of Chapters 5 and 2 and this is the first work with random geometric complexes not considering the asymptotics. We consider, as usual, that the deployment of the sensors is a Poisson point process in a d-torus. The coverage radius of the sensors is deterministic given by ǫ, which, as stated in Chapter 5, is enough to define a simplicial complex having the homotopy type and then, for our 1. Introduction purposes, we can only use the complex, allowing us to apply other tools from algebraic homology. Then we turn our attention to the number of simplices. We use the chaos decomposition and the Campbell theorem to find expressions for the n-th moments of ksimplices. The first three moments are explicitly found. We present a method to find the other moments, and although there are no new difficulties, the calculation is too tedious (we can have an idea comparing the complexity of the evaluation between the first and the second moments, and between the second and the third moments). This result can already tell information regarding the sensor network, but it is possible to go further and to calculate explicitly the two first moments of Euler characteristic. Moreover, all those results can be obtained for a fixed number of points by means of the Poisson transform (or de-poissonization). The results of the Euler characteristic and concentration inequalities allow us to infer some information related to the behavior of Betti numbers in d dimensions. It is also investigated the behavior of the number of k-simplices for a high density of sensors and we can show that this converges to a Gaussian distribution, which turns out to be an interesting result: since we have calculated the mean and variance of this quantity, we have a good approximation of its analytical distribution. Since we found also an upper bound of the distance between the distribution of k-simplices and the Gaussian, we can even estimate the error of this consideration.

Chapter 7 solves the problem of coverage and connectivity of sensor networks in one dimension. This can be applied to networks where sensors are deployed over a privileged dimension as well in queuing systems, since solving this problem is equivalent to evaluate a M/D/1/1 preemptive queue. We obtain all aforementioned results for this case: for a line segment or a circle, we find the distribution of the number of connected components (and we call each connected component a cluster), the distribution of the size of clusters, all the moments and the Laplace transform of those distributions. The mathematical tools used in this chapter are quite simple and the results could have been obtained at least fifty years ago. However, solving the problem in one dimension gives us hints and intuitions in order to solve the problem in d dimensions.

Part I

Stochastic Geometry

Chapter 2

Stochastic Model

Introduction

In this chapter, we review the main facts used in this thesis concerning the stochastic model. We give the definition of the Poisson measure on a space of configurations of a metric space X. This allows us to characterize the randomness of the system by considering that the set of points representing the sensors are modeled by a Poisson point process ω with intensity λ in a Polish space Y . This characterization is important due to the development of the theory of Poisson point process, giving us a large number of tools. From the definition of such a measure, it is possible to express a random variable depending on the random realization ω as a sum of stochastic integrals and then to obtain the probabilistic interpretation of the gradient D as a finite difference operator. Using this operator it is possible to derive other results, such as a concentration inequality on the Poisson space.

Poisson point process

To characterize the randomness of the system, we consider that the set of points is represented by a Poisson point process ω with intensity λ in a Polish space Y . The space of configurations on Y , is the set of locally finite simple point measures (cf [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings[END_REF]):

Ω Y = ω = n k=0 δ(x k ) : (x k ) k=n k=0 ⊂ Y, n ∈ N ∪ {∞} ,
where δ(x) denotes the Dirac measure at x ∈ Y . Simple measure means that ω({x}) ≤ 1 for any x ∈ Y . Locally finite means that ω(K) < ∞ for any compact K of Y . It is often convenient to identify an element ω of Ω Y with the set corresponding to its support, i.e.,

n k=0 δ(x k ) is identified with the unordered set {x 1 , • • • , x n }. For A ∈ B(Y ), we have δ(x k )(A) = 1 [x k ∈A] , so ω(A) = x k ∈ω 1 [x k ∈A] = A dω(x),
counts the number of atoms in A. The configuration space Ω Y is endowed with the vague topology and its associated σ-algebra denoted by F Y . Since ω is a Poisson point process of intensity λ: i) For any A with Lebesgue measure S(A), ω(A) is a random variable of parameter λS(A), i.e.,

P(ω(A) = k) = e -λS(A) (λS(A)) k k! • ii) For A ′ ∈ B(Y )
, for any disjoints A, A ′ , the random variables ω(A) and ω(A ′ ) are independent.

In the thesis, we refer E λ [F (ω)] as the mean of some function F depending on ω given that the intensity of this process is λ and

P λ [ω ∈ Y ] = E λ 1 [ω∈Y ] . The definitions of V λ [F (ω)] and Cov λ [F (ω), G(ω)] are straightforward. Define ∆ n = {(x 1 , • • • , x n ) ∈ Y n | x i = x j , ∀i = j}. Let f (x 1 , • • • , x n ) be
a measurable function and let F (ω) be a random variable given by

F (ω) = x i ∈ω∩A,1≤i≤n x i =x j if i =j f (x 1 , • • • , x n ) = A∩∆n f (x 1 , • • • , x n ) dω(x 1 ) • • • dω(x n ).
A well known property of the Poisson point processes [START_REF] Daley | An introduction to the theory of point processes[END_REF] states that

E λ [F (ω)] = A f (x 1 , • • • , x n ) dλ(x 1 ) • • • dλ(x n ).
(

The notion of point process can be extended to configurations in R k × X where X is a subset of R m . A configuration is then typically of the form {(x n , y n ), n ≥ 1} where for each n ≥ 1, x n ∈ R k and y n ∈ X. We keep writing (x n , y n ) as a couple, though it could be thought as an element of R k+m , to stress the asymmetry between the spatial coordinate x n and the so-called mark, y n . For a marked point process, we denote by ω the set of locations, i.e., ω = {X n , n ≥ 1} and by ω ′ the set of both locations and marks, i.e., ω ′ = {(X n , Y n ), n ≥ 1}. A marked point process with position dependent mark is one for which the law of Y n , the mark associated to the atom located at X n , depends only on X n through a kernel K:

P(Y n ∈ B | ω) = K(X n , B), for any B ⊂ X. If K is a probability kernel, i.e., if K(x, X) = 1 for any x ∈ R k then it is well known that ω ′ is a Poisson process of intensity K(x, dy) dλ(x) on R k × R m . For f : R k × R m → R a measurable non-negative function, let F = f dω ′ = Xn∈ω f (X n , Y n ). (2.2)
We denote the mean of a function F of marked Poisson point process with kernel K as

E λ,K [F ].
The Laplace transform of F is given by [START_REF] Stoyan | Stochastic Geometry and Its Applications[END_REF]:

E λ,K e -sF = exp -(1 -e -sf (x,y) )K(x, dy)dλ(x) (2.3)
As consequence, the Campbell formula can be extended.

Theorem 2.1 Let ω ′ be a marked Poisson process on R k × R m . Let λ be the intensity of the underlying Poisson process and K the kernel of the position dependent marking. Then,

E λ,K [F ] = R k ×R m f (x, y) K(x, dy) dλ(x). A real function f : Y n → R is called symmetric if f (x σ(1) , • • • , x σ(n) ) = f (x 1 , • • • , x n )
for all permutations σ of S n .The space of symmetric square integrable random variables is denoted by

L 2 (λ) •n . For f ∈ L 2 (λ) •n , the multiple Poisson stochastic integral I n (f n ) is then defined as I n (f n )(ω) = ∆n f n (x 1 , • • • , x n )( dω(x 1 ) -dλ(x 1 )) • • • ( dω(x n ) -dλ(x n )). If f n ∈ L 2 (λ) •n and g m ∈ L 2 (λ) •m , the isometry formula E λ [I n (f n )I m (g m )] = n!1 [m=n] f n , g m L 2 (λ) •n (2.4)
holds true (see [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings[END_REF]). Furthermore, we have:

Theorem 2.2 Every random variable F ∈ L 2 (Ω Y , P) admits a (unique) Wiener-Poisson decomposition of the type F = E λ [F ] + ∞ n=1 I n (f n ),
where the series converges in L 2 (P) and, for each n ≥ 1, the kernel f n is an element of L 2 (λ) •n . Moreover, we have the isometry

F -E λ [F ] 2 L 2 (λ) •n = ∞ n=1 n! f n 2 L 2 (R + ) •n . (2.5) For f n ∈ L 2 (λ) •n and g m ∈ L 2 (λ) •m , we define f n ⊗ l k g m , 0 ≤ l ≤ k,
to be the function:

(y l+1 , • • • , y n , x k+1 , • • • , x m ) -→ Y l f n (y 1 , • • • , y n )g m (y 1 , • • • , y k , x k+1 , • • • , x m ) dλ(y 1 ) . . . dλ(y l ). (2.6)
We denote by

f n • l k g m the symmetrization in n + m -k -l variables of f n ⊗ l k g m , 0 ≤ l ≤ k.
This leads us to the next proposition, shown in [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings[END_REF]:

Proposition 2.3 For f n ∈ L 2 (λ) •n and g m ∈ L 2 (λ) •m , we have I n (f n )I m (g m ) = 2(n∧m) s=0 I n+m-s (h n,m,s ), where h n,m,s = s≤2i≤2(s∧n∧m) i! n i m i i s -i f n • s-i i g m belongs to L 2 (λ) •n+m-s , 0 ≤ s ≤ 2(m ∧ n).
In what follows, given f ∈ L 2 (λ) •q (q ≥ 2) and t ∈ Y , we denote by f ( * , t) the function on Y q-1 given by (

x 1 , • • • , x q-1 ) -→ f (x 1 , • • • , x q-1 , t).
Definition 2.1 Let Dom D be the set of random variables F ∈ L 2 (P ) admitting a chaotic decomposition such that

∞ n=1 qq! f n 2 < ∞.
Let D be defined by

D : Dom D → L 2 (Ω Y × Y, P × λ),
such that

F = E λ [F ] + n≥1 I n (f n ) -→ D t F = n≥1 nI n-1 (f n ( * , t)).
It is known, cf. [START_REF] Ito | Generalized poisson functionals[END_REF], that we also have

D t F (ω) = F (ω ∪ {t}) -F (ω), dP × dt a.e.. Remark 2.
1 It is possible to show that the expression of f n that appears in the chaos expansion

F = ∞ n=0 1 n! I n (f n )
can be expressed by using the gradient operator and we have:

f n (t 1 , . . . , t n ) = E λ [D t 1 . . . D tn F ] , a.e. t 1 , . . . , t n ∈ A.
This is analogous to the classical Taylor expansions for one or several variables, where we have

f (x) = ∞ n=0 a n x n n! ,
where the coefficients a n can be found:

a n = ∂ n f ∂x n (x) x=0 ,
and we have the correspondence:

calculus on R stochastic analysis f (x) F f (0) E λ [F ] ∂ n ∂x n D n ∂ n f ∂x n (0) E λ [D n F ] Definition 2.2 The Ornstein-Uhlenbeck operator L is given by LF = - ∞ n=1 nI n (f n ),
whenever F ∈ Dom L, given by those F ∈ L 2 P such that their chaotic expansion verifies

∞ n=1 q 2 q! f n 2 < ∞.
Note that E λ [LF ] = 0, by definition and (2.4).

Definition 2.3 For F ∈ L 2 (P) such that E λ [F ] = 0, we may define L -1 by L -1 F = - ∞ n=1 1 n I n (f n ).
Combining Stein's method and Malliavin calculus yields the following theorem, see [START_REF] Peccati | Stein's method and normal approximation of poisson functionals[END_REF]:

Theorem 2.4 Let F ∈ Dom D be such that E λ [F ] = 0 and Var(F ) = 1. Then, d W (F, N (0, 1)) ≤ E λ 1 - Y [D t F × D t L -1 F ] dλ(t) + Y E λ |D t F | 2 D t L -1 F dλ(t).
Another result from the Malliavin calculus used in this work is the following one, quoted from [99]:

Theorem 2.5 Let F ∈ Dom D be such that DF ≤ K, a.s., for some K ≥ 0 and

DF L ∞ (Ω,L 2 (Y )) < ∞. Then P(F -E λ [F ] ≥ x) ≤ exp - x 2K log 1 + xK DF L ∞ (Ω,L 2 (Y ))
.

(2.7)

We recall that if ω is a marked Poisson process on R k × R m of intensity λ and kernel K(x, y), then

m F = E λ,K [F ] = f (x) K(x, dy)λ( dx)
and

v F = |D x F (ω) K(x, dy)| 2 λ( dx).

Summary

In this chapter all the stochastic tools used throughout the thesis have been introduced. First, we have presented the Poisson point process in a formal fashion in order to present some properties and extend the definition to marked Poisson point processes. After, we have introduced the notion of Malliavin calculus, which allows us to describe a large family of the Poisson point process (those square-integrable ones) as the sum of chaos. As consequence, we can apply results from [START_REF] Peccati | Stein's method and normal approximation of poisson functionals[END_REF] and concentrations inequalities from [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings[END_REF] to find upper bounds for the distributions of random variables depending on a Poisson point process.

Chapter 3

Interference Temperature Model in Cognitive Radio Networks

Introduction

This chapter proposes the utilization of the Poisson point process as a new analytical method to be applied in the interference temperature (IT) approach. For this purpose, we firstly develop a model for the RF environment. Afterwards, by the use of the Poisson point process, we determine essential elements for the calculation of the achievable perlink capacity and the total capacity of a secondary network following the ideal and the generalized IT models.

As long as new radio access technologies continue to appear, there are few spectrum bands to be allocated due to inefficient fixed spectrum allocations. This phenomenon obstructs the development of new wireless technology and communication services [START_REF] Jia | Hardware-constrained multi-channel cognitive mac[END_REF]. Moreover, spectrum occupancy measurements [START_REF] Mchenry | Spectrum Occupancy Measurements[END_REF] evidence that fixed spectrum allocations also result in low efficiency in spectrum utilization because a large portion of the spectrum remains underutilized [33].

These observations have motivated the regulatory bodies to investigate different access methods to overcome the above problems. As result, the use of Cognitive Radio technology that allows Dynamic Spectrum Access (DSA) has emerged as a possible solution to solve the low efficiency in spectrum utilization by allowing spectrum sharing. In such an approach, Secondary Users (SUs) are allowed to dynamically access the unused spectrum in Primary Users' (PUs) bands, commonly referred as "spectrum holes".

In the last years, two different strategies of spectrum sharing have been identified. One is through opportunistic spectrum access, known as "Overlay" and the other is through the use of low power spread-spectrum, known as "Underlay" [START_REF] Cabric | Spectrum sharing radios[END_REF]. The Overlay approach is based on avoidance of PUs through the use of spectrum sensing and adaptive allocation. On the other hand in the Underlay approach, which is of interest in this chapter, the transmission of SUs is allowed in PUs bands, if the transmission power is low enough that it does not harm the PUs. As this approach imposes severe restrictions on transmitted power levels, it requires operating over "ultra" wide bandwidths. Under this framework, in November 2003, the concept of Interference Temperature (IT) was proposed by the Federal Communications Commission (FCC), as another way to dynamically manage and allocate spectrum resources [START_REF]Establishment of interference temperature metric to quantify and manage interference and to expand available unlicensed operation in certain fixed mobile and satellite frequency bands[END_REF]. The principal characteristic of the IT model, as an underlay approach, is the fact that in this model SUs attempt to coexist with PUs meanwhile, in other proposals for DSA (i.e. overlay approaches), SUs try to avoid PU's signals [START_REF] Clancy | Achievable capacity under the interference temperature model[END_REF].

After conclude the mathematical analysis enlightened by the Poisson point process model, we demonstrate the application of our model by a numerical example, in which we consider the primary user as a Universal Mobile Telecommunications Service (UMTS) network and the secondary user as an Ultra Wide Band (UWB) network. Finally, by the use of Concentration Inequalities we determine an upper bound on the outage probability of the primary network when the SUs transmit.

The rest of the chapter is organized as follows: Section 3.2 describes the ideal and the generalized interference temperature models and the physical features of the system; In Section 3.3, we present our model for the calculation of the SUs mean capacity and the numerical analysis; Bounds of the outage probability of PU using Concentration Inequalities are found in Section 3.4; Finally, in Section 3.5, we present our conclusions.

Physical Model

In the IT model, SUs equipped with cognitive radio technology must firstly sense the available spectrum band to compute the existing interference. In this approach, SUs treat PUs, other SUs, interference, and noise all as interference. Afterwards, they must adjust their transmission power to avoid raising the interference temperature above a predefined threshold, which is assumed to be established by the FCC. This threshold represents the maximum quantity of interference that a PU can tolerate. Therefore, SUs must guarantee that the existing interference temperature, added to the interference caused by their transmissions does not exceed the interference temperature limit (T L ) [START_REF] Clancy | Achievable capacity under the interference temperature model[END_REF].

The Interference Temperature T I (f c , B) is defined as:

T I (f c , B) = P I (f c , B) kB ,
where T I (f c , B) is estimated in Kelvin, the average interference power P I is measured in Watts, is centered at f c , covers a bandwidth B measured in Hertz and k is the Boltzmann's constant.

In [START_REF] Clancy | Achievable capacity under the interference temperature model[END_REF], two different interference temperature models were presented: the Ideal and the Generalized. The ideal model tries to limit interference specifically to PUs signals. Therefore, the priori knowledge of PUs activity is needed. This model can be written as:

T I (f i , B i ) + M i P kB i ≤ T L (f i ) ∀ 1 ≤ i ≤ n,
where P is the average power of SUs operating with the center frequency f c and bandwidth B. The band [f c -B/2, f c +B/2] overlaps n PUs signals, with respective frequencies f i and bandwidth B i , T L is the interference temperature limit. As the purpose of this model is to restrict the interference received by PUs, the constant M i (with fractional value between 0 and 1) represents the attenuation between the primary receiver and the secondary transmitter. This constant is assumed to be fixed by a regulatory body in [START_REF] Clancy | Achievable capacity under the interference temperature model[END_REF].

For the generalized model, the priori knowledge of PUs activity is not required. So this model can be applied in the entire bandwidth regardless the exact location of the PUs signals. The interference temperature limit in the generalized model can be expressed as following:

T I (f c , B) + M P kB ≤ T L (f c ).
Here B is the entire frequency range, and not just PUs frequency band. Since the parameters of the PUs receivers are unknown, the constraint is in terms of SUs transmitter's parameters [START_REF] Clancy | Achievable capacity under the interference temperature model[END_REF]. We consider a system in which the position of users are given by Poisson point processes. So the Poisson point process, ω j on R 2 , with intensity (i.e., the mean number of users per unity of area) λ j , represents the positions of user of kind j. Moreover, their individual transmission power is given by µ j . We associate primary users to the index j = 1, secondary users that are transmitting to j = 2 and interferers to j = 3. Besides, the marked Poisson point process ω ′ 2 on R 2 × R 2 associates, for each point X i from ω 2 another point Y i uniformly distributed over a disc D 2 (X i ) of radius R 2 centered at X i , in such way that Y i is the position of the SU receiving the signal of a SU placed at X i .

Let p j (x, y) be the received power experienced by a user located at y ∈ R 2 with respect to a transmitter of kind j at x ∈ R 2 . We use the propagation power loss as the simplified model for path loss being a function of distance, based on Hata's model:

p j (x, y) = min µ j , µ j r 0 x -y α , (3.1)
where r 0 and α are positive constants. In this approximation α is the path loss coefficient and we take r 0 = 1, where r 0 is a reference distance from the antenna far field. Due the strong attenuation as a function of distance, the existence of the noise and the sensibility of the SUs, we assume that SUs are only able to communicate with some other ones closer than a distance R 2 . The total interference power experienced by a point x with respect of all users of kind j is given by Q j (x). We illustrate a possible realization of the model in Fig. 3.1, representing all kinds of users. Note that, to each SU transmitting, it must exist a SU receiving, which does not cause interference. Along this work, since R 2 is considered enough small to consider that a pair of SU's (i.e. SU transmitter and SU receiver) causes the same interference in the other users, so, in terms of interference, SU's are considered as a single point.

Secondary User Mean Capacity

In this section, we consider that the constraint given by the temperature model holds for the mean of the quantities, and then, based on the physical model we analyze the mean capacity of the network. First, we proceed the calculations and then we present the numerical results.

Calculations of the mean capacity

The mean total network capacity of the SUs is based on the mean per-link capacity and the constraints of the IT model. Therefore, taking into account the IT model restrictions, we develop the necessary expressions to estimate the mean capacity for the ideal and the generalized IT models. In order to achieve this, we consider the following lemma. Lemma 3.1 Let ω j be a Poisson point process with intensity measure λ representing the positions of active users of kind j over R 2 transmitting with a power µ j . If Q j (x) is the total interference power received experienced by a point x ∈ R 2 , then

E λ [Q j (x)] = µ j λ j πα (α -2) . (3.2)
Proof: Given the invariance under translation of a stationary Poisson point process,

E λ [Q j (x)] = E λ [Q j (0)].
So, it suffices to use Eq. (2.1) for f (x) = p j (x, 0) as defined in Eq. (3.1):

E λ [Q j (0)] = E λ   X i ∈ω p j (X i , 0)   = R 2 p j (x, 0)λ j (x) dx = λ j 2π 0 ∞ 0 min µ j , µ j 1 r α r dr dθ = µ j λ j πα (α -2) ,
concluding the proof. For the ideal case, we must calculate the maximum allowed SUs Transmission Power µ id 2 . As imposed in the physical model, the ideal interference temperature model attempt to limit interference specifically to licensed signals. This means that the objective is to guarantee that

P I (f i , B i ) kB i + M i P kB i ≤ T L (f i ).
The left side of the equation represents the total temperature allowed to interferers with respect to a primary user using the center frequency f i , placed at x i , and we can rewrite it as

Q 2 (x) + Q 3 (x) ≤ T L (f i )kB i .
To guarantee that this inequality holds at least for the mean of interferences, we take the mean in both sides, use Lemma 3.1 and solve for µ id 2 , resulting in the maximum allowed transmission power to be used by secondary users:

µ id 2 ≤ (α -2)T L kB i -λ 3 µ 3 πα λ 2 πα • (3.3)
Now we calculate the maximum mean allowed SUs transmission power µ gen 2 following the generalized model. The main difference between the generalized and the ideal model is that in the generalized model the priori knowledge of PUs activity is not required. Thus, the generalized model is written as:

P I (f c , B) kB + M P kB ≤ T L (f c ).
As the parameters of the PUs receivers are unknown, the constraint is in terms of the SUs transmitter's parameters. Therefore, B is the entire frequency range, and not just PUs frequency band. Again, since SUs treat PUs, other SUs, interference, and noise all as interference, we notice that for the generalized model we take into account the power from the others PUs (averaging the PUs power over the SUs bandwidth) and evaluate the T L over the entire frequency range B. If the analyzed primary user is placed at x ∈ R 2 , then we rewrite this condition as a function of Q i 's:

B i B Q 1 (x) + Q 2 (x) + Q 3 (x) ≤ T L (f c )kB.
Assuring that, in average, this inequality holds, we take the mean, apply Lemma 3.1 and solving for µ gen 2 , we obtain:

µ gen 2 ≤ (α -2)T L kB -λ 3 µ 3 πα -B i B λ 1 µ 1 πα λ 2 πα • (3.4)
Since we are interested in the calculation of the capacity using the Shannon-Hartley theorem [START_REF] Proakis | Digital communications[END_REF] the per-link capacity C(x, y) of a user at x ∈ R 2 receiving a signal from a user at y ∈ R 2 such that xy ≤ R 2 , is given by:

C(x, y) = B log 2 1 + p 2 (x, y) E λ [I(x)] ,
Where I(x) is the interference power caused by the interferers, other SUs and PUs at x, given by

I(x) = B i B Q 1 (x) + Q 2 (x) + Q 3 (x).
Since y is uniformly distributed around x, then x is uniformly distributed over y and the mean capacity per link C(x) in the disc is:

C(x) = B log 2 1 + p 2 (x, y) E λ [I(x)] 1 [{ x-y ≤R 2 }] πR 2 2 dy By Lemma 3.1, E λ [Q j (x)]
does not depend on y, and p 2 (x, y) depends only on the distance between x and y, so

C(x) = C. Let us define K µ 2 E λ [I(x)] = µ 2 (α -2) πα B i B µ 1 λ 1 + µ 2 λ 2 + µ 3 λ 3 •
Then, we can rewrite C as follows:

C = R 2 0 2π 0 B πR 2 2 log 2 1 + K min(1, r -α )) r dθ dr. (3.5) Defining h : R + × (2, ∞) → R + as follows h(r, t) r 0 ln 1 + 1 x t x dx, (3.6)
we rewrite Eq. (3.5) as

C = 2BK 2 α R 2 2 ln(2) ln(1 + K) 2K 1 α + h R 2 K 1 α , α -h 2 K 1 α , α (3.7)
The capacity per-link in the ideal case, C id , is obtained taking µ 2 = µ id 2 , while the one in the generalized case, C gen , results of taking µ 2 = µ gen 2 . It is possible to find analytical expressions for h(r, t) when t is an integer. Lemma 3.2 Let β n = π(2n -1) for n integer. For t an odd integer, the expression of h(r, t) is given by:

h(r, t) = - 1 2 ⌊t/2⌋ n=1 cos 2β n t ln 1 r 2 + 2 r cos β n t + 1 +2 sin 2β n t arctan r sin( βn t ) 1 + r 2 cos( βn t ) + r 2 2 ln 1 + 1 r t - 1 2 ln 1 + 1 r •
If t/2 is odd, we obtain the following expression for h(r, t):

h(r, t) = - 1 2 ⌊t/4⌋ n=1 cos 2β n t ln 1 r 4 + 2 r 2 cos 2β n t + 1 -2 sin 2β n t arctan r 2 sin( 2βn t ) 1 + r 4 cos( 2βn t ) + r 2 2 ln 1 + 1 r t + 1 2 ln 1 + 1 r 2 ,
and if t/2 is even, then

h(r, t) = - 1 2 ⌊t/4⌋ n=1 cos 2β n t ln 1 r 4 + 2 r 2 cos 2β n t + 1 -2 sin 2β n t arctan r 2 sin( 2βn t ) 1 + r 4 cos( 2βn t ) + r 2 2 ln 1 + 1 r t •
Proof: First we differentiate the right-hand terms with respect to r and after several elementary but tedious manipulations we have:

∂h(r, t) ∂r = r ln 1 + 1 r t •
Then, it suffices to use the Fundamental Theorem of Calculus on the right-hand term of Eq. (3.6) to obtain that

∂ ∂r r 0 ln 1 + 1 x t x dx = r ln 1 + 1 r t •
So both sides of the equation differ at most by a constant. Since these two functions are analytical at r = 0, it suffices to see that

h(0, t) = 0 0 ln 1 + 1 x t x dx = 0,
thus the proof is concluded. We can use this lemma to obtain expressions for two typical values of α.

Lemma 3.3 The expression of h(r, 3) is given by:

h(r, 3) = 1 4 ln r 2 -r + 1 r 2 + 2r + 1 + √ 3π 12 + r 2 2 ln 1 + 1 r 3 + √ 3 2 arctan (2r -1) √ 3
and the expression of h(r, 4) is the following one

h(r, 4) = arctan r 2 + r 2 2 ln 1 + 1 r 4 .
Then, it is possible to calculate the mean total SUs capacity C total in a secondary cell of radius, R, defining a disc D. Using theorem 2.1 on the marked Poisson point process ω ′ 2 , we obtain:

C total = D C(x, y) 1 [{ x-y ≤R 2 }] πR 2 2 dyλ 2 dx.
However, Eq. 3.7 shows that the inner integral does not depend on x, so we can rewrite Eq. 3.8 as

C total = C D λdx = Cλ 2 D dx = Cλ 2 πR 2 . (3.8)
Applying the µ 2 obtained by the temperature model, we obtain the total capacity of a network, and we denote C id total for the ideal case, when µ 2 = µ id 2 , and C gen total when µ 2 = µ gen 2 .

Numerical Analysis for the Mean Capacity of the Secondary Network

In this section, we demonstrate the application of the equations developed previously. We examine the achievable per-link capacity (C) of a secondary network and the total capacity (C total ) of this network under some typical situations. For this analysis, we consider the primary user as a UMTS network and the secondary user as an UWB network, WiMedia. We develop this analysis following the ideal and the generalized IT models.

Concerning to UMTS or the primary network, we consider a primary user's intensity (λ 1 ) of 0.02 users per km 2 . This corresponds to 60 active mobile stations in a macro-cell with radius equal to 30 km. According to [START_REF] Su | The UMTS air-interface in RF engineering: design and operation of UMTS networksS[END_REF], the transmission power (µ 1 ) of the UMTS mobile stations is equal to 250 mW or 24dBm and the PUs bandwidth (B i ) is 5 MHz.

For the secondary network or WiMedia, the bandwidth (B) is 528 MHz [START_REF]Multiband ofdm physical layer specification[END_REF] and we consider R 2 = 10 m as the communication range of the secondary users (i.e. maximum distance between a secondary transmitter and a secondary receiver). This value corresponds approximately to the range of the IEEE 802.15.3a specification using UWB. Depending on the interference temperature model, the transmission power µ 2 is defined as µ id 2 or µ gen 2 and the secondary user's intensity (λ 2 ) is equal to 3 users per m 2 . The IT model includes not only power from primary and secondary transmitters but also the interference power of another source of interference which as been named as base interference. However, to provide an upper bound on the achievable capacity by the secondary network, we consider environments with no interference (i.e. µ 3 = 0). Finally, the last parameter to complete the system is Interference Temperature Limit (T L ). This parameter was set to 50000 K, same as other studies of the IT model developed to quantify the capacity achieved by the secondary network and the interference caused to the primary network such as [START_REF] Clancy | Achievable capacity under the interference temperature model[END_REF].

Considering these parameters for the ideal case we use Lemma 3.3 to obtain the SUs capacity for α = 3 and α = 4. In the first case we obtain an average SUs transmission power (µ id 2 ) of -99 dBm. With this SU power, the achievable per link capacity (C id ) using Eq. 3.7 is 5.8 Kbps. Therefore, the total achievable capacity (C id total ) of the secondary network present in a 100m radius secondary cell (R) is 545 Mbps. This value is obtained using Eq. 3.8. In the case of α = 4, the average SUs transmission power is -97.37 dBm and the achievable per-link capacity (C id ) is 9.22 Kbps. Thus, the total achievable capacity (C id total ) for the case α = 4 is 869 Mbps.

For the generalized model, in this scenario, the communication is not possible if we consider the same parameters. To allow the transmission of SUs we must increase the bandwidth (B) of the secondary network, which is in fact one of the characteristics of WiMedia's medium access control (MAC) layer [START_REF] Wimedia | The best choice for wireless pans[END_REF]. The WiMedia mobile station incorporates a MAC layer providing multimedia Quality of Service (QoS) and a physical layer based on multi-band orthogonal frequency-division multiplexing (MB-OFDM). This technology is well known to have robust link characteristics, meanwhile the multi-band aspect allows spectrum flexibility and support different channel modes. WiMedia's MAC layer uses a bandwidth reservation system called Distributed Reservation Protocol (DRP). The DRP provides a bandwidth reservation system that assures QoS support for multimedia traffic. This ensures that the streaming media will continue to have the bandwidth it needs once a reservation is established and without interference from other users [START_REF] Wimedia | The best choice for wireless pans[END_REF]. Therefore and in order to study the performance of the generalized model, the bandwidth (B) of the secondary network was increased of 57 MHz. So, we increase the SUs bandwidth from 528 MHz (i.e. minimum channel bandwidth of WiMedia systems) to 585 MHz.

Considering the same parameters used for the ideal case, but now with a SUs bandwidth (B) of 585 MHz, applying again Lemma 3.3 with a path loss exponent α = 3, we obtain analytically an average SUs transmission power (µ gen 2 ) of -104 dBm. With this SU power, the achievable per link capacity (C gen ) using Eq. 3.7 is 2.22 Kbps. Therefore, the total achievable capacity (C gen total ) using Eq. 3.8 of the secondary network present in a cell with 100 m radius (R) is 209 Mbps. In the case of α = 4, we obtain better performances compared to the case α = 3. The average SUs transmission power is -81.44 dBm and the achievable per-link capacity (C gen ) is 297 Kbps. Thus, the total achievable capacity (C gen total ) for the case α = 4 is 2.79 Gbps.

In Figure 3.2, we analyze the performance of the achievable capacity (C id ) as a function of the path loss exponent (α). This figure presents the behavior of C id for typical values of α. Therefore, we consider values from α = 3 to α = 6. These path loss exponents are used in relatively lossy environments (i.e. α = 3) and in indoor environments (i.e. from α = 4 to α = 6).

To understand the behavior of C id as a function of α plotted in Figure 3.2, we must take into account two different effects: the transmission effect and the reception one. In the transmission effect, with the increase of α, mobile users generate less interference and hence, the available transmission power of the SUs (µ id 2 ) and the value of K also increase. These results are justified by Lemma 3.1, Eq. 3.3 and Eq. 3.5. On the other hand, the reception effect occurs due to the attenuation of the radio signal as it propagates through space. Here, the received signal decreases with the increase of the path loss exponent. In this case, the reception effect appears for values of α higher than 6. With the SU total per-link capacity ranging from 5.8 Kbps to 12.31 Kbps, from Figure 3.2, we can observe that the ideal IT model is robust against the variation of path loss exponent (α). Now, using the parameters presented before, we analyze the behavior of the achievable capacity obtained by the secondary network when the secondary users' intensity (λ 2 ) is increased (i.e. when different load conditions are considered). following the ideal IT model. As we can see in this figure, with the increase of the secondary users' intensity (λ 2 ) the allowable SUs transmission power (µ id 2 ) decrease and hence, the achievable SUs capacity is diminished. These results can be verified in Eq. 3.5 and Eq. 3.5. We also notice in this figure that the achievable per-link capacity in the case of α = 4 is slightly higher compared to the case α = 3. In the case of the achieved mean total secondary network capacity (C id total ) as a function of the secondary users' intensity (λ 2 ), the total SUs capacity remains almost constant for the ideal case with α = 3 and α = 4. This behavior obey Eq. 3.8 presented in section 3.3.1.

Figure 3.4 and Figure 3.5 plot the achieved mean SU per-link capacity (C gen ) as a function of the secondary users' intensity (λ 2 ) for the generalized IT model. Here again, in order to analyze the performance of the generalized model the SUs bandwidth (B) was increased from 528 MHz to 585 MHz. In Figure 3.4 and Figure 3.5 we observe the same behavior occurred for the ideal case plotted in Figure 3.3. This is that the achieved mean SU per-link capacity is higher for the case α = 4 than for the case α = 3. These results are justified by Lemma 3.1, Eq. 3.3, Eq. 3.4 and Eq. 3.5. These expressions states that with the increase of α, MSs generate less interference and hence the available transmission power of the SUs µ id 2 or µ gen 2 and the value of K also increase. For the generalized approach, in Figure 3.5 we notice that the maximum achievable mean SU per-link capacity for α = 4 is 1.74 Mbps, meanwhile the maximum capacity for α = 3 in Figure 3.4 is only 13.5 Kbps. In the case of the achieved mean total secondary network capacity (C gen total ) as a function of the secondary users' intensity (λ 2 ), the total SUs capacity remains almost constant for the generalized case with α = 3 and α = 4.

In order to directly compare the performances in terms of mean SU per-link capacity of the ideal and the generalized IT models, we have set the SUs bandwidth B to 585 MHz 3.6 the ideal model outperforms the generalized approach for the case α = 3. However, for α = 4 the generalized case obtains better performance due to the higher allowable transmission power µ gen 2 . This behavior can be verified in Eq. 3.4.

Upper bound of PU Outage Probability

The latter section considers the constraint given by the Interference Temperature model with respect to the mean transmission power. However, if the distribution of the sum of the interferences is roughly symmetric, about 50% of PUs are not guarenteed the maximum allowed transmission power. This means that this averaged condition can only loosely gives an idea of the effect of interference, but cannot predict how probable is the occurrence of an outage of the PU network. Here, we use the concentration inequalities from Malliavin calculus to find an upper bound probability P sup of outage of a PU due the interference caused by the SUs as a function of µ 2 . Therefore, the system can be designed, such that the outage probability of the PUs is smaller than q = P sup .

Calculations: Upper bound of PU Outage Probability

Using the IT model and considering the ideal case, we want to find an upper bound for the probability of the following event:

T L (f i )kB i ≥ x i ∈ω 2 p 2 (x i , 0) + x i ∈ω 3 p 3 (x i , 0) F,
where the primary user to be analyzed is placed at the origin. Lemma 3.4 Let ω A and ω B be two independent Poisson point processes on R n with intensities λ A and λ B . Define G A and G B as follows:

G A (ω A ) = X i ∈ω A f A (X i ), G B (ω B ) = X i ∈ω B f B (X i ),
for f A and f B two non-negative measurable real-valued functions. Then, the random variable

G = G A (ω A ) + G B (ω B )
has the same distribution then the marked Poisson point process with intensity λ = λ A +λ B and kernel

K(x, y) = f A (x)δ y - λ A λ A + λ B + f B (x)δ y - λ B λ A + λ B .
Proof: We use Eq. 2.3 to obtain

E λ e -sG = E λ e -s(G A +G B ) = E λ e -sG A E λ e -sG B = exp -(1 -e -sf A (x) ) dλ A (x) × exp -(1 -e -sf B (x) ) dλ B (x) = exp -(1 -e -s )K(x, dy) d(λ A + λ B )(x) ,
which concludes the proof.

Lemma 3.5 Let ω be a marked Poisson point processes on R n × R m with intensity λ and kernel K(x, y) and define G as follows:

G(ω) = X i ∈ω f (X i , Y i ),
for f a non-negative measurable real-valued function. Then, for

t ∈ R n D t (G) = f (t, y)K(t, dy)
Proof: The proof follows straightforwardly from the application of Definition 2.1 on F (ω).

We set m F E λ [F ] and

v F |D x F (ω) K(x, dy)| 2 λ dx.
We obtain P sup via concentration inequalities, using Theorem 2.5

P(F ≥ t + m F ) ≤ exp - t 2s g 1 + ts v F .
where g(x) = (1 + x) ln(1 + x)x. Using Lemmas 3.4 and 3.5, we obtain that

m F = E λ x i ∈ω 2 p 2 (x i , 0) + E λ x i ∈ω 3 p 3 (x i , 0) , v F = E λ x i ∈ω 2 p 2 2 (x i , 0) + E λ x i ∈ω 3 p 2 3 (x i , 0) ,
and we use Lemma 3.1 to find m F :

m F = απ(µ 2 λ 2 + µ 3 λ 3 ) (α -2) • (3.9)
To find v F , it suffices to use the same lemma exchanging α by 2α and µ i by µ 2 i :

v F = 2απ(µ 2 2 λ 2 + µ 2 3 λ 3 ) (2α -2) • (3.10)
Since the function max(µ i , µ i r -α ) is decreasing with respect to r, s = max(µ 2 , µ 3 ).

Assuming µ 2 ≥ µ 3 and taking T L (f i )kB i = t + m F , then

P(F ≥ T L (f i )kB i ) ≤ exp - T L (f i )kB i -m F 2µ 2 ln 1 + (T L (f i )kB i -m F )µ 2 v F = P sup . (3.11)
This inequality holds for m F ≤ T L (f i )kB i . The generic case is similar and it suffices to define

F B i B x i ∈ω 1 p 1 (x i , 0) + x i ∈ω 2 p 2 (x i , 0) + x i ∈ω 3 p 3 (x i , 0), so m F = απ( B i B µ 1 λ 1 + µ 2 λ 2 + µ 3 λ 3 ) (α -2) ,
and

v F = 2απ( B i B µ 1 2 λ 1 + µ 2 2 λ 2 + µ 2 3 λ 3 ) (2α -2) •
In the generic case, s is given by

s = max B i B µ 1 , µ 2 , µ 3 ,
and from here we apply Theorem 2.5.

Results: Upper bound of PU Outage Probability

In this section, we take into account a specific outage probability of PUs to design the allowed transmission power for SUs following the ideal IT model. We use the same parameters considered in Section 3.3.2 to compare this power with the results of that section such that we can evaluate the trade-off of system reliability and capacity. Besides, we set λ 2 = 3 users/m 2 and analyze the results for α = 3 and α = 4.

We define µ q 2 as the transmission power such that the outage probability of PUs is smaller than q in the ideal case and η as the fraction of this transmission power with respect to µ id 2 calculated in the previous section, i.e. µ q 2 = η(q)µ id 2 . Since q(η) is a bijection on (0, 1), there exists a function η(q). We denote also C q as the mean capacity per link of a SU in function of q. Setting λ 3 = 0, we can rewrite Eq. 3.11 as a function of these variables to obtain:

q = exp λ 2 πα 2(α -2) η(q) -1 η(q) ln 1 + 2(α -1) (α -2) 1 -η(q) η(q) •
The function η(q) is presented in Figures 3.8 and 3.9 for α = 3 and α = 4 respectively. We can notice from Figure 3.8 and Figure 3.9, that in order to guarantee that the outage probability of PUs remains between 1% and 5%, we must reduce the SUs transmission power µ id 2 between a 26% and a 22% respectively for the case α = 3 and between a 34% and a 28% respectively for the case α = 4. Now, using Figure 3.10 and Figure 3.11, we evaluate the achieved performance in terms of mean SU per-link capacity for different values of the PUs outage probability following the ideal IT model. Figure 3.10 plots the mean SU per-link capacity as a function of the secondary users' intensity (λ 2 ) for the case α = 3 and Figure 3.11 for the case α = 4. Both figures show the achievable mean SU per-link capacity for 1%, 3% and 5% of the PUs outage probability and also plots the original case without restriction on the SUs transmission power µ id 2 . As we can see in Figure 3.10 and Figure 3.11 with the increase of λ 2 , the difference between the restricted cases and the non restricted case become shorter. This means that in order to guarantee that the outage probability of PUs remains between 1% and 5%, for a scenario with a large number of SUs, the restriction of the SUs transmission power µ id 2 does not lead to a significant reduction with respect to the mean SU per-link capacity.

Summary

This chapter has proposed the utilization of the Poisson Point Process and concentration inequalities as new analytical methods to be applied in the Interference Temperature model. These mathematical tools help us to evaluate, in a simple fashion, the achievable capacity by a secondary network, the interference caused to the primary network and the outage probability of the primary network when the secondary network transmits. For this purpose, we firstly developed the necessary expressions to estimate the mean base interference, the mean interference caused by other SUs and the mean interference caused by active PUs. As we have seen through this chapter the equations developed by our model remain quite simple. Using these results, we estimated the allowed SUs transmission power to guarantee that the PUs activity will not be affected by the SUs transmission. The later analysis was performed for the ideal and the generalized IT models. Afterwards, using the Shannon-Hartley theorem, we derived the expressions of the mean SU per-link capacity and the total secondary network capacity. Finally, by the use of Concentration Inequalities we determine an upper bound on the outage probability of the primary network.

In order to obtain numerical results using our expressions in a realistic scenario, we have examined the achievable capacity of an UWB system, WiMedia, as a secondary network and a UMTS network as the primary network. Our results show that for this scenario, the secondary network achieves a limited performance in terms of capacity, compared to the real capabilities of an UWB standard (e.g. IEEE 802.15.3a). However, these performances can easily be improved if the secondary network operates with a larger channel bandwidth, which is one of the characteristics of WiMedia's MAC layer. Furthermore, we have demonstrated that SUs communication is possible causing only minor damage to primary users following the ideal and the generalized interference temperature model. Moreover, by the use of Concentration Inequalities, we have established that in order to guarantee than only 1% of the PUs is affected by the SUs transmission, it will only cost approximately 25% of the mean allowable SUs transmission power and 20% for a PUs outage probability below 5%. In addition we have demonstrated that, for a scenario with a large number of secondary users, the restriction of the secondary users transmission power does not lead to a significant reduction of the achievable per-link capacity of the secondary network.

Chapter 4

Upper bound of loss probability of an OFDMA system

Introduction

In this chapter, we present another application of the Poisson point process modeling a wireless system based on Orthogonal Frequency Division Multiple Access (OFDMA), where future systems will widely rely. OFDMA can satisfy end user's demands in terms of throughput. It also fulfills operator's requirements in terms of capacity for high data rate services. Systems such as 802.16e and 3G-LTE (Third Generation Long Term Evolution) already use OFDMA on the downlink. For the uplink, 802.16e has also adopted OFDMA, while 3G-LTE uses SCFDMA (Single Carrier Frequency Division Multiple Access). OFDMA can also be possibly combined with multiple antenna technology to improve either quality or capacity of systems.

Dimensioning of OFDMA systems is then of the up-most importance for wireless telecommunications industry. As usual, the model introduced in this contribution takes into account the randomness of user locations and user traffic. It provides also an upper bound of loss probability in terms of sub-channels.

This chapter first provides a short introduction to OFDMA air interfaces, by providing some insights on sub-channel concepts and OFDMA jargon (see section 4.2). The dimensioning analytical model is first developed for a deterministic wireless channel, taking only into account the path-loss effect (cf. section 4.3). Section 4.4 analyses a more realistic situation, where wireless channel also encompasses shadowing effects. Section 4.5 extends the results to a multi class user traffic. The accuracy of analytical model is evaluated by comparing them with simulation.

Introduction to OFDMA air interfaces

OFDM (Orthogonal Frequency Division Multiplex) is a multi carrier technique especially designed for high data rate services. It divides the spectrum in a large number of frequency bands called sub-carriers that overlap partially in order to reduce spectrum occupation. Overlapping is made possible because the different sub-carriers are made orthogonal to each other by choosing a sub-carrier spacing multiple of the inverse of the OFDM symbol duration.

Each sub-carrier has a small bandwidth compared to the coherence bandwidth of the Systems such as ADSL (Asymmetric Digital Subscriber Line), digital audio broadcasting (DAB) and digital video broadcasting (DVB-T) rely on OFDM modulation. Most recently, power line systems (Home Plug) and WiMedia (short range communications) have also adopted OFDM.

In OFDM systems, all available sub-carriers are affected to one user at a given time for transmission. OFDMA extends OFDM by making it possible to share dynamically the available sub-carriers between different users (see figure 4.1). In that sense, it can then be seen as multiple access technique that both combines FDMA and TDMA features.

In practical systems, such as WiMAX or 3G-LTE, the sub-carriers are not allocated individually for implementation reasons mainly inherent to the scheduler design and physical layer signaling. Several sub-carriers are then grouped in sub-channels according to different strategies specific to each system. The unit of resource allocation is the sub-channel.

For example, in WiMAX, there are three modes available for building sub-channels: FUSC (Fully Partial Usage of Sub-channels), PUSC (Partial Usage of Sub-Channels) and AMC (Adaptive modulation and coding). In FUSC, sub-channels are made of sub-carriers spread over all the frequency band. In AMC, the sub-carriers of a sub-channel are adjacent instead of being uniformly distributed over the spectrum. FUSC provides an averaging effect on quality that makes it more suitable for mobile application, while AMC is more adapted for fixed users.

The sub-channel concept makes it easier to schedule radio resources. However, it becomes more difficult to assess channel quality as it is composed by different sub-carriers that can possibly span over several timeslots. An extensive literature has addressed that problem, and we will assume in the following, that whatever the sub-channelization scheme adopted, it is possible to consider an equivalent single channel gain for all the sub-carriers making part of a sub-channel (for example the average of channel gain computed on some sub-carrier pilots). We also assume that subcarrier allocation to different sub-channels is done slot by slot.

Upper Bound under a Deterministic Gain

We state the following assumptions: Assumption 1 The position of each user is independent of the position of all other. The users are indistinguishable, i.e., the positions are identically distributed.

Assumption 2

The time between two consecutive demands of users for service in the system (or inter arrival time) is exponentially distributed.

We define ρ(x) as the surface density of inter arrival time in s -1 m -2 , constant in time. Hence, for a region H ⊆ B, the mean inter arrival rate is h = H ρ(x)dx in s -1 .

Assumption 3

The service time for every user is exponentially distributed with mean 1/ν.

Assumption 4

The cell C is circular, with radius R and with the antenna in the center.

Assumption 5

The channel gain depends only on the distance from the transmitting antenna.

Assumption 6

The surface density of inter arrival time is constant.

These assumptions are commonly done to simplify the mathematical treatment and are quite reasonable. If we show that the point process given by the location of the users is a Poisson process, then it is sufficient to have the two first moments in order to apply theorem 2.5 and then calculate an upper bound P sup for the probability P loss of loosing communications due to a lack of sub-channels. To do this, we consider the following lemma: Lemma 4.1 Considering assumptions 1, 2 and 3, the point process ω of the active users positions is, in equilibrium, a Poisson process with intensity dλ(x) = ρ(x)ν -1 dx Proof: For a region H, in virtue of assumptions 2 and 3, the number of receiving (i.e., active) customers is the same as the number of customers in an M/M/∞ queue with input rate h and mean service time ν -1 . It is known [START_REF] Robert | Stochastic networks and queues[END_REF] that the distribution of the number of users U in equilibrium is then

P(U = u) = (h/ν) u u! e -h/ν . It follows that λ(H) λ(H) = h/ν = H ρ(x) ν dx.
Using assumption 1 concludes the proof. Without loss of generality, we consider the cell C has its antenna located at the origin. We are looking at evaluating

P loss = P λ N dω ≥ N 0 ,
where N (x) is defined by

N (x) =       C 0 W log 2 1 + P t K ḡ (I + η) x γ      
, and ḡ is the mean gain due to shadowing, C 0 is the throughput requested by users, I is the interference generated by outer cells and η the noise. We will not take into account interference generated by outer cells, so I = 0. Note that, with respect to x, N is increasing and piecewise constant. Let R j , j = 1, • • • , N max be the values such that N (x) = j for x ∈ [R j , R j+1 ). We can determine them by

R j = P t Kg η(2 C 0 /(jW ) -1) 1/γ .
According to Eq. (2.2) for a marked process, it is then clear that

E λ N dω = N dλ(x) = πρ ν Nmax j=1 j(R 2 j -R 2 j-1 ).
We denote by m N the last quantity. Moreover,

N 2 dλ(x) = πρ ν Nmax j=1 j 2 (R 2 j -R 2 j-1 ).
We denote by v N the last quantity. We take N 0 of the form αm N , so that according to Theorem 2.5:

P λ N dω ≥ αm N ≤ P sup (α)
where It is then natural to verify how far this bound is from the exact value of the loss probability in simple situations where simulation is available. We used here γ = 2.8, C 0 = 200 kb/s, W = 250 kHz and P t K/(η) = 1 × 10 6 . For the surface density of inter arrival time we use ρ = 0.0006 min -1 m -2 and the service time is 1/ν = 1 min, so, the mean number of users in the system is πR 2 ρ/ν = 18.85 users. If we consider the shadowing with σ = √ 10 dB and µ = 6 dB, we can use the mean gain g, giving g = 1/12. Thus, users in the cell boundary use 3 sub-channels, so N max = 3. For α varying from 1 to 2, which corresponds here to loss probabilities about 2% or 0.01%, we computed ∆ = log 10 P sup /P loss .

P sup (α) = exp - v N N 2 max g (α -1)m N N max v N . α 1.
Though concentration inequalities are usually thought as almost optimal, the results shown in Table 4.1 seem at first glance disappointing. Note though that the computation of the bound is immediate whereas the simulation on a fast PC took several hours to get a decent confidence interval. Note also that the error is about the same order of magnitude as the error made when using a usual trick, which consists in replacing infinite buffers by finite ones in Jackson networks (see [START_REF] Laurent Decreusefond | An error bound for infinite approximations of queueing networks with large finite stations[END_REF]). The margin provided by the bounds may be viewed as a protection against errors in the modeling or in the estimates of the parameters.

Upper Bound under a Random Gain

Let us determine now the upper bound probability P sup for P loss without assumption 5 but holding all other assumptions of the preceding section. Lemma 4.1 still holds, since it is a consequence of assumptions 1, 2 and 3. We also state two other natural assumptions: Assumption 7 The random gain is totally described by the log-normal shadowing, with mean µ and standard deviation σ, both in dB.

For a user at distance d from the origin, the gain is G = 1/S, where S follows a log-normal distribution:

p S (y) = ξ √ 2πσy exp - (10 log 10 y -µ) 2 2σ 2 ,
where ξ = 10/ ln 10.

Assumption 8 A user is able to receive the signal only if the signal-to-interference ratio is above some constant β min .

This means, in particular, that the number of sub-carriers needed by a transmitting user is surely bounded by

N max = C 0 W log 2 (1 + β min ) .
The situation is slightly different from that of Section 4.3, since the functional depends on two random factors: positions and gains. Consider now that our configurations are of the form (x, s) where x ∈ R 2 is still a position and s ∈ R is a gain. Since gain and positions are independent, we then have a Poisson process on R 3 of intensity measure dλ(x) ⊗ p S (y) dy. Thus we want to evaluate an upper bound of

P λ N dω ≥ N 0 where N (x, y) =       C 0 W log 2 1 + P t K ηy x γ       .
According to Theorem 2.5, we must compute m N = N (x, y)p S (y) dy dλ(x) and

v N = sup ω |D x,y F (ω)| 2 p S (y) dy dλ(x) = N 2 (x, y)p S (y) dy dλ(x). Let β 0 = ∞ and β j = 2 C 0 /(W j) -1 for j = 1, • • • , N max -1. For j = 1, • • • , N max -1, let A j = C×R +
1 {y x γ ≤PtK/ηβ j } p S (y) dy dx and A 0 = 0.

Lemma 4.2 For j = 1, • • • , N max -1, A j = πR 2 Q(α j -ζ ln R) + πe 2/ζ 2 +2α j /ζ Q(ζ ln R -2/ζ -α j ),
where α j = 1 σ (10 log 10 (P t K/ηβ j )µ) and ζ = 10γ σ ln 10 .

Proof: We can write

A j = C P(S x γ ≤ βj ) dx
where βj = P t K/ηβ j . Remind that S is equal in distribution to exp(N (µ, σ 2 )ξ) with ξ = ln(10)/10. Thus after a few manipulations, we get

A j = 2π R 0 r Q(α j -ζ ln r) dr,
where

Q(x) = 1 √ 2π x -∞ exp(- u 2 2 ) du.
The final result follows by a tedious but straightforward integration by parts. Now we see that

N (x, y) = j ⇐⇒ βj-1 < y x γ ≤ βj , for j = 1, • • • , N max -1 and N (x, y) = N max when y x γ > βNmax-1 .

Multi class user traffic

Upper bound of loss probability

We consider in this section, M classes of users. Class j users request a throughput of C j . The configurations associated to each class are of the form (x, y), where x ∈ R 2 is a position, y ∈ R is a gain. Since gain and positions are independent, we then have for each class of users a Poisson process on R 3 of intensity measure λ j (x) dx ⊗ p S (y) dy, where λ j (x) = ρ j (x)ν -1 j and j is the user class. For the sake of computational simplicity, we assume in the following, that ρ j (x) is constant with respect to x but the theory is still valid unaltered otherwise. Furthermore we consider that the random gain is totally described by the log-normal shadowing, with mean µ and standard deviation σ, both in dB. For a user at distance d from the origin, the gain is G = 1/S, where S follows a log-normal distribution as in section 4.4. We also assume that a user is able to receive the signal only if the signal-to-interference ratio is above some constant β min . This means, in particular, that the number of sub-channels needed by a transmitting user of class j is surely bounded by

N max j = C j W log 2 (1 + β min )
.

Without loss of generality, we consider the cell C has its antenna located at the origin. We are then looking at evaluating

P λ N dω ≥ N 0 ,
where

N (x, j, y) =       C j W log 2 1 + P t K ηy x γ       .
The functional depends on two aleas: positions and gains. It has also an additional parameter that describes the class of the user. Theorem 4.4 With the assumptions of this Section,

P λ N dω ≥ αm N ≤ P sup (α)
where

P sup (α) = exp - v N 2 max g (α -1)mN max v , with N max = max j N max j , m = M j=1
N (x, j, y)λ j (x)p S (y) dx dy, and

v = M j=1
N (x, j, y) 2 λ j (x)p S (y) dx dy.

Proof: Let λ j be the intensity of the Poisson process representing class j customers and λ = M j=1 λ j . Let ω be a Poisson process on R 2 of intensity λ. Consider the probability kernel

K(x, {j}) = λ j (x) λ(x) .
For a configuration ω = {x n , n ≥ 1}, there is thus a sequence of marks {u n , n ≥ 1}, u n ∈ {1, • • • , M } for all n ≥ 1, corresponding to the position dependent marking according to the kernel K. According to the properties of Poisson process, the process ω j = {x n , u n = j} is a Poisson process of intensity λ j . Now add to each point of ω, an independent mark y n , corresponding to the random gain, distributed according to a log-normal distribution. Denote by ω this point process which turns to be a Poisson process since the marks are independent from the positions. From section 2, we know that the process, the atoms of which are ω = (x n , u n , y n ), is a Poisson process of intensity j K(x, {j})λ(x)p S (y) dx dyδ j :

E λ   n≥1 f (X n , U n , Y n )   = M j=1 f (x, j, y) λ j (x) λ(x) λ(x)p S (y) dx dy = M j=1
f (x, j, y)λ j (x)p S (y) dx dy.

We are thus in position to apply the Theorem 2.5 to the Poisson process ω. The difference operator in Definition 2.1, is here equal to

D x,j,y F (ω) = F (ω ∪ {x, j, y}) -F (ω),
noting that max(D x,j,y F (ω)) = 4. That is to say, we look at the impact of adding a user at position x, with class j and gain y. For F = N dω, we obtain

D x,j,y F (ω) = N (x, j, y) ≤ N max j .
Thus, inequality (2.7) holds with s = max j N max j ,

m N = M j=1
N (x, j, y)λ j (x)p S (y) dx dy, and

v N = M j=1
N (x, j, y) 2 λ j (x)p S (y) dx dy.

Both m and v can be computed taking advantage of the fact that N is piecewise constant (see section 4.4). Let

β 0 = ∞ and β j,k = 2 C j /(W k) -1 for k = 1, • • • , N max j -1. For k = 1, • • • , N max j -1, let A j,k = C×R +
1 {y x γ ≤PtK/ηβ k } p S (y) dy dx and A 0 = 0. It can proved from results of section V that for k

= 1, • • • , N max j -1, A j,k = πR 2 Q(α j,k -ζ ln R) + πe 2/ζ 2 +2α j,k /ζ Q(ζ ln R -2/ζ -α j,k ),
where α j,k = 1 σ (10 log 10 (P t K/ηβ j,k )µ) and ζ = 10γ σ ln 10 .

We finally obtain the following formula.

Numerical application

In this section we will apply the upper bound calculated previously to the dimensioning of sub-channels in a OFDMA system. We consider here a cell, where two classes of users are competing to the access of available sub-channels. More precisely we consider here M = 2. The capacities required by each class of user is fixed to C 1 = 200 kb/s and C 2 = 100kb/s respectively. The path-loss exponent is fixed to γ = 3.8 and the sub-channel bandwidth is equal to W = 250 kHz. We also consider P t K/η = 1 × 10 12 . For the surface density of inter arrival time we use ρ 1 = 0.0006 min -1 m -2 and ρ 2 = 0.0006 min -1 m -2 . The service times are 1/ν 1 = 1 min and 1/ν 2 = 0.5 min, so the mean number of users in the system is πR 2 ρ 1 /ν 1 = 18.85 for class 1 users and πR 2 ρ 2 /ν 2 = 9.425 for class 2 users. We consider the shadowing with σ = √ 10 dB and µ = 6 dB. We have also considered β min = 0.2 We made α varying from 1.6 to 1.8, by steps of 0.05. This corresponds here to an upper bound of loss probability varying between 0.0068 and 0.045 As the analytical expression obtained in the previous section, is an upper bound of the real loss probability, applying it to dimension an OFDMA cell will lead to an over dimensioning in terms of sub-channels. We have computed the number of sub-channels N 0 with the analytical expression of upper bound of loss probability. We have computed by simulation the number of sub-channels required if the upper bound probability is used as the loss probability to dimension the system.

Results of table 4.3 show the over dimensioning is about 20% in terms of sub-channels. We should note that the computation of the upper bound and associated N 0 is immediate whereas the simulation on a fast PC is more tedious to get a decent confidence interval. The margin provided by the bounds may be viewed as a protection against errors in the modeling or in the estimates of the parameters. N 0sup is the number of sub-channels obtained with the analytical upper bound, whereas N 0 sim is the one obtained by simulation for the same loss probability value as P sup .

Summary

Using the concentration and deviation inequalities and the difference operator on Poisson space, we have calculated the upper bound probability of overloading the system by high demand of sub-carriers, over path loss and shadow fading. To do this we have found the first and second moment of the marked Poisson point process of users. It is possible to find an upper bound for the overloading probability, even in a relatively complex system, which is analytically computable in a very simple fashion. The method works for any functional of the configurations, possibly enriched by marks, which depends only on the positions of each user. It does not work for functionals involving relative distance between two or more users. Actually, for such a functional F , there is no bound on D x F (ω) valid for all x and ω.

Part II

Algebraic Topology with random Simplicial complexes

Chapter 5

Algebraic Topology

Introduction

The two most important advantages of the network presented throughout this work are that we do not need to have a central station nor to know the coordinates of the sensors. The first advantage is given by the randomness of the system, and its model was presented in Chapter 2. The second one comes from the topology of the network. The recent works of Ghrist and his collaborators [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF][START_REF] Silva | Coordinate-free coverage in sensor networks with controlled boundaries via homology[END_REF] show how, in any dimension, algebraic topology can be used to compute connectivity and coverage of a given configuration of sensors by finding the homology of the network.

In this chapter we introduce some basic tools from algebraic topology. For further reading on topology, see [START_REF] Hatcher | Algebraic Topology[END_REF][START_REF] Armstrong | Basic Topology[END_REF][START_REF] Munkres | Elements of Algebraic Topology[END_REF]. The main objective of this chapter is to create a link between the physical concepts of an arbitrary sensor network and the its topological representation.

Theory

Graphs can be generalized to more generic topological objects known as simplicial complexes. While graphs model binary relations, simplicial complexes represent higher order relations. Given a set of points V , a k-simplex is an unordered subset {v

0 , v 1 , • • • , v k } where v i ∈ V and v i = v j for all i = j. The faces of the k-simplex {v 0 , v 1 , • • • , v k } are defined as all the (k-1)-simplices of the form {v 0 , • • • , v j-1 , v j+1 , • • • , v k } with 0 ≤ j ≤ k.
A simplicial complex is a collection of simplices which is closed with respect to the inclusion of faces, i.e., if

{v 0 , v 1 , • • • , v k } is a k-simplex
then all its faces are in the set of (k -1)simplices.

Given U = (U v , v ∈ T) a collection of open sets, the Cech complex of U denoted by C(U), is the abstract simplicial complex whose k-simplices correspond to (k + 1)-tuples of distinct elements of U that have non empty intersection, so {v

0 , v 1 , • • • , v k } is a k-simplex if and only if k i=0 U v k = ∅.
One can define an orientation for a simplicial complex by defining an order on vertices. A change in the orientation corresponds to a change in the sign of the coefficient as

[v 0 , • • • , v i , • • • , v j , • • • , v k ] = -[ v 0 , • • • , v j , • • • , v i , • • • , v k ].
Let X be a simplicial complex. For each integer k, C k (X) is the vector space spanned by the set of oriented k-simplices of X. The boundary map ∂ k is defined to be the linear

v 0 v 1 v 2 v 0 + v 2 - [v 0 , v 1 ] + [v 1 , v 2 ] ∂ -→ [v 0 ] -[v 2 ] v 0 v 1 v 2 v 0 v 1 v 2 [v 0 , v 1 , v 2 ] ∂ -→ [v 1 , v 2 ] -[v 0 , v 2 ] +[v 0 , v 1 ] v 0 v 1 v 2 v 3 Filled Empty v 0 v 1 v 2 v 3 [v 0 , v 1 , v 2 , v 3 ] ∂ -→ +[v 1 , v 2 , v 3 ] -[v 0 , v 2 , v 3 ] +[v 0 , v 1 , v 3 ] -[v 0 , v 1 , v 2 ] a) b) c)
Figure 5.1: Examples of boundary maps. In a) an applications over 1-simplices, in b) we apply over a 2-simplex and in c) over a 3-simplex, turning a filled tetrahedron to an empty one

transformations ∂ k : C k → C k-1 which acts on basis elements [v 0 , • • • , v k ] via ∂ k [v 0 , • • • , v k ] = k i=0 (-1) k [v 0 , • • • , v i-1 , v i+1 , • • • , v k ].
Examples of such operations are given in Fig. 5.1. This map gives rise to a chain complex: a sequence of vector spaces and linear transformations

• • • ∂ k+2 -→ C k+1 (X) ∂ k+1 -→ C k (X) ∂ k -→ C k-1 (X) • • • ∂ 2 -→ C 1 (X) ∂ 1 -→ C 0 (X).
A simple lemma then asserts that for any integer k,

∂ k • ∂ k+1 = 0.
The demonstration of this lemma follows straightfowardly from the definition of ∂ k . We define ker ∂ k as the kernel of ∂ k on C k (i.e., all closed cycles), im ∂ k as the image of ∂ k (i.e., the k -1-simplices that are faces of k-simplices) and if we define The k-dimensional homology of X, denoted H k (X) is the quotient vector space,

Z k = ker ∂ k and B k = im∂ k+1 , this induces that B k ⊂ Z k . 0 0 0 C k Z k B k C k+1 C k-1 ∂ -→ ∂ -→
H k (X) = Z k (X) B k (X) •
and the k-th Betti number of X is its dimension:

β k = dim H k = dim Z k -dim B k .
The well known topological invariant named Euler characteristic for X, denoted by χ(X), is an integer defined by:

χ(X) = ∞ i=0 (-1) i β i .
Denoting s k as the number of k-simplices in a simplicial complex X, a well known theorem states that the Euler characteristic is also given by:

χ(X) = ∞ i=0 (-1) i s i .
The simplicial complexes we consider are of a special type. They can be considered as a generalization of geometric random graphs.

Definition 5.1 The d-dimensional torus with with sides a is denoted by T d a . Definition 5.2 Given ω a finite set of points on the torus. For ǫ > 0, we define

U ǫ (ω) = {B d∞ (v, ǫ), v ∈ ω} and C ǫ (ω) = C(U ǫ (ω)), where B d∞ (x, r) = {y ∈ T d a , x -y ∞ < r}.
Theorem 5.1 Suppose ǫ < a/4. Then C ǫ (ω) has the same homotopy type as U ǫ (ω). In particular they have the same Betti numbers.

Proof: This will follow from the so-called nerve lemma of Leray, as stated in [START_REF] Rotman | An Introduction to Algebraic Topology[END_REF]Theorem 7.26] or [START_REF] Björner | Topological methods[END_REF]Theorem 10.7]. One only needs to check that any non-empty intersection of sets B d∞ (v, ǫ) is contractible.

Consider such a non-empty intersection, and let x be a point contained in it. Then, since ǫ < a/4, the ball B d∞ (x, 4ǫ) can be identified with a cube in the Euclidean space. Then each B d∞ (v, ǫ) containing x is contained in B d∞ (x, 4ǫ), hence also becomes a cube with this identification, hence convex. Then the intersection of these convex sets is convex, hence contractible. Definition 5.3 Let ω be a finite set of points in T d a . For any ǫ > 0, the Rips-Vietoris complex of ω, R ǫ (ω), is the abstract complex whose k-simplices correspond to unordered (k + 1)-tuples of points in ω which are pairwise within distance less than ǫ of each other. The proof is given in [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF] in a slightly different context, but it is easy to check that it works here as well. It must be pointed out that Cech and Rips-Vietoris simplicial complexes can be defined similarly for any distance on T d a but it is only for the product distance that the homotopy type of both complexes coincides.

By Lemma 5.2, k points are forming a (k -1)-simplex whenever they are two-by-two closer than 2ǫ from each other. We define along the thesis h

(v 1 , • • • , v k ) as h(v 1 , • • • , v k ) = h k (v 1 , • • • , v k ) = 1≤i<j≤k 1 [ v i -v j <2ǫ] , (5.1)
which determines if a set of k distinct ordered points generates a (k -1)-simplex.

Proposition 5.3 Let ω ∈ T d a be a set of points, generating the simplicial complex C ǫ (ω). Then, if i > d, β i (ω) = 0. Proof: By Theorem 5.1, C ǫ (ω) has the same homology as U ǫ (ω). But U ǫ (ω) is an open manifold of dimension d, so its Betti numbers β i (ω) vanish for i > d, see for example [START_REF] Greenberg | Algebraic Topology: a First Course[END_REF]Theorem 22.24]. Proposition 5.4 Let ω ∈ T d a be a set of points, generating the simplicial complex C ǫ (ω). There are only two possible values for the d-th Betti number of C ǫ (ω):

i) β d = 0, or ii) β d = 1.
If the second holds, then we also have χ(C ǫ (ω)) = 0.

Proof: By Theorem 5.1, C ǫ (ω) has the same homology as U ǫ (ω). Now, U ǫ (ω) is an open submanifold of the torus, so there are only two possibilities:

i) U ǫ (ω) is a strict open submanifold, hence non-compact ii) U ǫ (ω) = T d a .
In the first case, β d (ω) = 0 by [START_REF] Greenberg | Algebraic Topology: a First Course[END_REF]Corollary 22.25]. In the second case C ǫ (ω) has same homology as the torus, hence β d (ω) = 1 and χ(ω) = 0. Proposition 5.5 Let X a compact subset of R d and consider the map τ : X → Y as x i = ky i for x i ∈ X, y i ∈ Y and k a positive real constant. Denote by τ * ω the image measure of ω by τ , i.e., τ * :

Ω X → Ω Y maps ω = ∞ i=1 δ(x i ) to τ * ∞ i=1 δ(kx i ).
The application τ * : Ω X → Ω Y maps the Poisson measure λ on Ω X to the Poisson measure λ τ = λ/k d on Ω Y . Moreover, if ǫ τ is the distance in Y such that two points will be connected, the homology of the two simplicial complexes C ǫ (ω) ω∈T d Proof: A slightly changing on Propositions 6.1.7 and 6.1.8 of [START_REF] Privault | Stochastic Analysis in Discrete and Continuous Settings[END_REF] is enough to show that τ * maps the Poisson measure λ on Ω X to the Poisson measure λ τ = λ/k d on Ω Y . Then, it suffices to realize that for x i ∈ X and for y i ∈ Y :

h(x 1 , • • • , x k ) = 1≤i<j≤k 1 [ x i -x j <2ǫ] = 1≤i<j≤k 1 [ kx i -kx j <2kǫ] , hence h(y 1 , • • • , y k ) = 1≤i<j≤k 1 [ y i -y j <2ǫτ ] ,
which concludes the proof.

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 1 x 2 x 3 x 4 x 5 x 6 x 7 a) b) c)
Figure 5.3: The relation between the coverage of a sensor network and its Cech complex.

In a) the individual coverages, in b) the network coverage and in c) the correspondent simplicial complex

Applications to sensor networks

We aim to apply the definitions (k-simplexes, Euller's characteristic and Betti's numbers) and topological properties of the simplicial complexes to the connectivity and coverage problems. In a very intuitive fashion, the number of k-simplices itself shows some tendency in the network: if in two networks with identical number of sensors, one of them has more 1-simplices than the other, this first one has a tendency to be more connected; by the same reason, if a network has more 2-simplices than another one, the region on the first case tends to be well covered.

In a more sofisticated way, Theorem 5.1 formalizes that, in order to determine coverage of sensors, it suffices interpret them as Cech complexes, which is enough to applications that need to determine only connectivity and coverage. In Fig. 5.3 we see an example a sensor network seen as a simplicial complex: in a) we have the individual coverages, in b) we see the network coverage and in c) we have the correspondent simplicial complex. Nonetheless, sensors cannot provide it precisely in applications where they need to communicate with a central station or data have to be passed through them, since communication amoung them is always pairwise. The complex that represent this constraint is the Vietoris-Rips one.

An intepretation to Euller's characteristic is given by Proposition 5.4, where we see that χ = 0 is a necessary condition to have a complete coverage of the torus, and β d = 1 is a necessary and sufficient condition. This could in turn translate into conditions for coverage in [0, a] d when considered as embedded in Euclidean space (i.e. not as a torus), but then one needs to be careful about border effects. For example, one can say that

β d = 1 is a sufficient condition for coverage of [ǫ, a -ǫ] d .

Summary

We have summarized in the chapter some concepts of algebraic topology to be used in the next two chapters. First, we have defined the concept of simplicial complex, Betti's numbers and Euler characteristic. Then, seeing the space of k-simplices as a linear space, it has been shown that the proper use of the linear operator named boundary map makes it possible to calculate any of those Betti numbers. Moreover, we have stated and proved some propositions that provide interpretations of sensor networks as a simplicial complex, establishing a relation between the simplices, Betti numbers and Euler characteristic to sensors, connectivity and coverage.

Chapter 6

Moments of k-Simplices and Euler Characteristic

Introduction

We apply in this chapter, at the same time, the results of Chapters 2 and 5 to characterize a sensor network. The physical features are less in evidence with respect to Chapters 3 and 4 and, although these features are used to justify the mathematical model, we focus almost absolutely in the application of tools of modern mathematics.

Each sensor is represented by its location point with a coverage radius constant given by ǫ. The homology of the coverage of this sensor network, as shown in [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF], can be represented by a simplicial complex. This distance ǫ, represents the distance that each sensor can control some environmental information (such as temperature, pressure, presence of an intruder, etc.) around them, but a different interpretation can be done if the sensors are communicating among them. In this case, we suppose that sensors have a power supply allowing them to transmit theirs ID's and, at the same time, sensors have receivers that can identify the transmitted ID's of other sensors above a threshold power. The sensors, knowing mutually the ID's of the close neighbors, are considered connected, creating an information network. The problem remains analogous as the previous one, except that we substitute the coverage radius ǫ by a communication one of ǫ/2. We can see examples of simplicial complexes representations given by sensors communicating among them or monitoring a region in Fig. 6.1.

We consider also that sensors are points of a Poisson point processes. As usual, this assumption reflects the fact that, due the lack of control of the sensors positioning, only a random fraction of the available sensors will actually lie in the target region or some sensors may shut down by running out of energy, moreover, the position of each sensor, a priori, does not interact with the positions other sensors. Instead of using the Euclidean norm, we use the maximum norm along this chapter. We consider this for three reasons: this norm represents a superior and an inferior limits for the Euclidean norm (we can inscribe and circumscribe a circle with two squares); due to the random interactions with the environment (causing shadowing and fading), even the Euclidean norm cannot capture with precision the real behavior of this kind of sensor networks, so we choose the norm that allows us to simplify the calculations; as shown in Lemma 5.2, using the maximum norm, the Cech complex become equal to the Rips-Vietoris complexes. Finally, we assume that sensors lie over d-torus with sides a, T d a . This choice was motivated by three factors: it avoids the border effects; using Proposition 5.4, it helps to determine weather or not a sensor network in the d-box is completely covered; if ǫ is small compared to a, the calculations for all parameters in the d-torus are a good approximation for the [0, a] d box.

The coverage of a point and the region where points can lie in are illustrated in Fig. 6.1, representing the case where a point is deployed over a plan. A very few papers deal with the properties of some random simplicial complexes. The most interesting one is [START_REF] Kahle | Random geometric complexes. Discrete and Computational Geometry[END_REF] which has been followed by [START_REF] Kahle | Limit theorems for betti numbers of random simplicial complexes[END_REF]. Though there are certain similarities between the work presented in this chapter and that of Kahle, we would like to point out the differences. In [START_REF] Kahle | Random geometric complexes. Discrete and Computational Geometry[END_REF], the number of points is fixed and the positions are i.i.d. random variables in the plane. It differs from a Poisson point process by the randomness of the number of points. However, for our initial motivation, Poisson process fits better since due to failures or movements, we don't know at each time the number of sensors. Moreover, Kahle is concerned with asymptotic regimes of the mean value of the Betti numbers. We do give exact formulas for any moment of the number of simplices. In addition, by using Malliavin calculus, we go further since we can evaluate the speed of convergence in the CLT and give a concentration inequality to bound the distribution tail of the first Betti number. On the other hand, [START_REF] Kahle | Limit theorems for betti numbers of random simplicial complexes[END_REF] obtains results for some ranges of ǫ, and particularly for the subcritical range asymptotic behaviors are found for β k , including the mean, the variance and the distribution.

Our method goes as follows: We write the numbers of k-simplices (i.e. points, edges, triangles, tetrahedron, etc.) as iterated integrals with respect to the underlying Poisson process. Then, the computation of the means simply reduces to the computation of deterministic iterated integrals thanks to Campbell formula. By using the definition of the Euler characteristic as an alternating sum of the numbers of simplices, we find its expectation. The point is that even if the summing index goes to infinity, there are so many cancellations that the expectation of χ depends only on the d-th power of the intensity of the Poisson process where d is the dimension of the underlying space. Using the multiplication formula of iterated integrals, one can reproduce the same line of thought for higher order moments to the price of an increased complexity in the computations. We obtain closed form formulas for the variance of the number of k-simplices and of the Euler characteristic and series expansions for higher order moments. Using Stein's method mixed with Malliavin calculus, we generalize the results of [START_REF] Penrose | Geometric Random Graphs[END_REF] by proving a precise (i.e. with speed of convergence) CLT for sub-complexes count. As it turns out, the speed of convergence is of the order of λ -1/2 .

The chapter is organized in the following way: the calculations and analytical results for the mean of simplices and Euler characteristics are presented in the Section 6.2; Section 6.3 presents the calculations for the variance and covariance of the number of simplices which leads to an expression of the Euler characteristic; next, in Section 6.4, we use the strategies calculations of the previous sections to find the third moment of k-simplices and then a method to express the n-th moment is presented; in Section 6.5, a theorem showing the convergence in law of the number of connected simplicial complex is proved.

First Moment

Consider that a Poisson point process ω generates a Cech complex C ǫ (ω), and, even though the number of k-simplices, the Betti's number and the Euler characteristic are functions of C ǫ (ω), we denote them, respectively,

N k+1 (C ǫ (ω)) = N k+1 , β k (C ǫ (ω)) = β k and χ(C ǫ (ω)) = χ.
In this section, we evaluate the mean of the number of k -1-simplices, E λ [N k ] and the mean Euler characteristic, E λ [χ]. Theorem 6.1 Let ǫ ≤ a/6. Then, the mean number of (k -1)-simplices N k (C ǫ (ω)) is given by

E λ [N k ] = λ k (ak(2ǫ) k-1 ) d k! • Proof: If (u i,1 , • • • , u i,d
) represents the coordinates of a point v i , we can separate the indicator function as follows:

1 [ v i -v j <2ǫ] = d l=1 1 [{|ui,l-uj,l|<2ǫ}∪{|ui,l-uj,l|>a-2ǫ}] .
According to 5.1, the number of (k -1)-simplices can be counted by the expression:

N k = 1 k! v 1 ,••• ,v k ∈ω v i =v j if i =j h(v 1 , • • • , v k ).
Since ω is a Poisson point process of intensity λ, for a Borel sets A i , i integer we have:

E λ     v 1 ,•••v k ∈ω v i =v j if i =j h(v 1 , • • • , v k )     = λ k A 1 • • • A k h(v 1 , • • • , v k ) dv 1 . . . dv k . Taking 1 k! h = f , A i = T d a and defining {|x i -x j | < 2ǫ} ∪ {|x i -x j | > a -2ǫ} = d ǫ (x i , x j ),
we have:

E λ [N k ] = λ k k! T d a • • • T d a h(v 1 , • • • , v k ) dv 1 . . . dv k = λ k k! d l=1 a 0 • • • a 0 1≤i<j≤k 1 [dǫ(ui,l,uj,l)] du 1,l . . . du k,l = λ k k!   a 0 . . . a 0 1≤i<j≤k 1 [dǫ(x i ,x j )] dx 1 . . . dx k   d (6.1) = λ k k!      a 0 a 0 1 [dǫ(x k ,x k-1 )] . . . a 0 m integrals k i=k-m+1 1 [dǫ(x i ,x k-m )] . . . a 0 k i=2 1 [dǫ(x i ,x 1 )] dx 1 . . . dx k d . (6.2)
Since 6ǫ ≤ a, the integration region is convex (see Fig. 6.3). Then, we can rewrite the

v 0 v 1 v 2 v 0 v 1 v 2 a) b)
Figure 6.3: a) Maximum cover in T a and ǫ = a/6. The red region shows the cover of a point v 0 , the blue region is the cover of v 1 and the green region is the cover of v 2 . b) Maximum cover in the same conditions of a) when ǫ = a/5. In this case, we the three covers intersect each other pairwise, but there is no intersection of the three covers.

integral in Eq. ( 6.2) as

a 0 a 0 1 [dǫ(x k ,x k-1 )] • • • a 0 k i=2 1 [dǫ(x i ,x 1 )] dx 1 . . . dx k = a 0 x k +2ǫ x k -2ǫ min(x k ,x k-1 )+2ǫ max(x k ,x k-1 )-2ǫ . . . min(x k ,••• ,x 2 )+2ǫ max(x k ,••• ,x 2 )-2ǫ dx 1 . . . dx k . (6.3)
Then, consider a subset of the integration region [0, a] d of Eq. ( 6.3), defined as

A 1, 2, ••• , k , such that x 1 ≥ x 1 ≥ . . . ≥ x k .
In this case, we can write the integral over A 1, 2, ••• , k as:

a 0 x k +2ǫ x k -2ǫ . . . min(x k ,••• ,x 2 )+2ǫ max(x k , ••• ,x 2 )-2ǫ 1 [x i ≥x j if i≤j] dx 1 . . . dx k = a 0 x k +2ǫ
x k

x k +2ǫ

x k-1

. . .

x k +2ǫ x 2 dx 1 . . . dx k .
For σ ∈ S k , we denote by

A σ the set A σ(1), ••• , σ(k) . Then, σ∈S k A σ = [0, a] d . Moreover, since the function h(x 1 , • • • , x k
) is symmetric, we can exchange the integration variables in the integral of Eq. (6.1) without changing its result. As a consequence, if

σ ∈ S k , • • • Aσ 1≤i<j≤k 1 [dǫ(x i , x j )] dx 1 . . . dx k = • • • Aσ 1≤i<j≤k 1 [dǫ(x i , x j )] dx i 1 . . . dx i k .
Thus, we have

a 0 • • • a 0 1≤i<j≤k 1 [dǫ(x i , x j )] dx 1 . . . dx k = σ∈S k • • • Aσ 1≤i<j≤k 1 [dǫ(x i , x j )] dx i 1 . . . dx i k = k! • • • A Id 1≤i<j≤k 1 [dǫ(x i , x j )] dx 1 . . . dx k = k! a 0 x k +2ǫ x k x k +2ǫ x k-1
. . .

x k +2ǫ x 2 dx 1 . . . dx k .
Then, by the change of variables

y k-i = (x k-i -x k )/2ǫ for i = 1, k, we get: k! a 0 x k +2ǫ
x k

x k +2ǫ

x k-1 . . .

x k +2ǫ x 2 dx 1 . . . dx k = (2ǫ) k-1 k! a 0 1 0 1 y k-1 . . . 1 y 2 dy 1 . . . dy k-1 dx k .

Moments of k-Simplices and Euler Characteristic

The integral in the right-handed term is evaluated substituting all y i for y ′ i -1, so

(2ǫ) k-1 k! a 0 0 -1 0 y ′ k-1 . . . 0 y ′ 2 dy ′ 1 . . . dy ′ k-1 dx k = (2ǫ) k-1 k!a 1 (k -1)! = a(2ǫ) k-1 k. (6.4)
Finally, plug Eq. ( 6.4) into Eq. ( 6.2) to obtain:

E λ [N k ] = λ k (ak(2ǫ) k-1 ) d k! ,
and thus the proof is complete.

Remark 6.1 The possibility of writing E λ [N k ] as Eq. (6.1) is due the fact that we use the maximum norm. This simplifies the calculations since we can treat each component individually. However, considering the Euclidean norm it is still possible to find a closedform expression for E λ [N 2 ] and E λ [N 3 ] for the Rips-Vietoris and the Cech complexes in

T 2 a . For E λ [N 2 ],
we have:

E λ [N 2 ] = 1 2 E x 1 ,x 2 ∈ ω x 1 =x 2 h(x 1 , x 2 ) = λ 2 2 T 2 a T 2 a h(x 1 , x 2 )dx 2 dx 1 .
Then, if b(x, r) is the ball centered at x and radius r. Then

E λ [N 2 ] = λ 2 2 T 2 a b(x 1 ,ǫ) dx 2 dx 1 = λ 2 2 T 2 a πǫ 2 dx 1 , so E λ [N 2 ] = πλ 2 ǫ 2 a 2 2 • We write E λ [N 3 ], as E λ [N 3 ] = 1 3! E x 1 ,x 2 ,x 3 ∈ ω x 1 =x 2 ,x 2 =x 3 h(x 1 , x 2 , x 3 ) = λ 3 6 T 2 a T 2 a T 2 a h(x 1 , x 2 , x 3 )dx 3 dx 2 dx 1
Let R 3 be the region where x 3 can lie to form a two simplex. Figure 6.4 presents this region. The surface of this region S(R 3 ) in polar coordinates (r, θ) is given by

S(R 3 ) = 2ǫ 2 arccos(r/(2ǫ)) -r ǫ 2 -r 2 /4
hence: If we substitute u = r/(2ǫ), then:

E λ [N 3 ] = λ 3 6 T 2 a b(x 1 ,ǫ) R 3 dx 1 dx 2 dx 3 = 2πλ 3 S(B) 6 ǫ 0 2rǫ 2 arccos r 2ǫ -r 2 ǫ 1 - r 2ǫ
E λ [N 3 ] = 2πλ 3 S(B) 6 8ǫ 4
1 2 0 u arccos(u) -u 2 1 -u 2 du = 2πλ 3 S(B) 6 8ǫ 4 (I 1 -I 2 )
where I 1 and I 2 are well known integrals and after solving them we find:

E λ [N 3 ] = π π - 3 √ 3 4 λ 3 a 2 ǫ 4 6
for the Rips complex•

We can proceed do the same calculations to obtain the mean of the mean number of 2-simplices on a Cech complex, defining carefully the region of integration.

E λ [N 3 ] = 2λ k a 2 (πǫ 2 ) 2 3
for the Cech complex, Corollary 6.2 Let ǫ ≤ a/6. Then, the mean number of (k -1)-simplices N k given that N 1 = n is given by

E [N k |N 1 = n] = n k k d 2ǫ a d(k-1)
• Proof: We use the depoissonization to obtain the mean of simplexes for a Binomial process with n points, E [N k |N 1 = n], by means of the pair of Poisson transform:

z k = ∞ n=0 α n z n e -z n! ⇔ α n = n! (n-k)! , if n ≥ k, 0 , otherwise.
Consider now the Bell's polynomial B d (x), defined as (see [START_REF] Bell | Exponential polynomials[END_REF])

B n (x) = n k=0 n k x k ,
where n is an positive integer and n k is the Stirling number of the second kind. An equivalent definition of B n can be:

B n (x) = e -x ∞ k=0 x k k d k! • Theorem 6.3 Let ǫ ≤ a/6.
The mean of the Euler characteristic mean of the simplicial complex C ǫ (ω) is given by

E λ [χ] = a 2ǫ d e -λ(2ǫ) d (-B d (-λ(2ǫ) d )). Proof: Since N k ≤ 1 k! k-1 j=0 (N 1 -j) ≤ N k 1 k! , then ∞ k=1 N k ≤ ∞ k=1 N k 1 k! = e N 1 .
As

E λ e N 1 < ∞, we have E λ -∞ k=1 (-1) k N k = -∞ k=1 (-1) k E λ [N k ] and E λ [χ] = E λ - ∞ k=1 (-1) k N k = - ∞ k=1 (-1) k E λ [N k ] = - ∞ k=1 (-1) k λ k (ak(2ǫ) k-1 ) d k! = a d -(2ǫ) d ∞ k=0 (-λ(2ǫ) d ) k+1 (k + 1) d (k + 1)! = a d e -λ(2ǫ) d -(2ǫ) d e λ(2ǫ) d ∞ k=0 (-λ(2ǫ) d ) k k d k! = a 2ǫ d e -λ(2ǫ) d (-B d (-λ(2ǫ) d )).
The proof is thus complete. If we take d = 1, d = 2 and d = 3, we obtain:

E λ [χ] (C ǫ (ω)) ω∈T [a] = aλe -λ2ǫ , E λ [χ] (C ǫ (ω)) ω∈T 2 [a 2 ] = a 2 λe -λ(2ǫ) 2 1 -λ(2ǫ) 2 , E λ [χ] (C ǫ (ω)) ω∈T 3 [a 3 ] = a 3 λe -λ(2ǫ) 3 1 -3λ(2ǫ) 3 + (λ(2ǫ) 3 ) 2 .
Remark 6.2 For c a positive real, E λ [χ] is invariant under the transformation λ ′ = λ/c, ǫ ′ = cǫ and a ′ = ca. Taking c = 1/2ǫ, we obtain:

E λ [χ] = a ′d e -λ ′ (-B d (-λ ′ )).
Hence, the mean depends actually only on a ′ and λ ′ .

Corollary 6.4 The mean of χ in a Binomial process homogeneous with n points is given by:

E [χ|N 1 = n] = n k=0 n k k d 2ǫ a d(k-1)
, Proof: This is a consequence of Corollary 6.2. If we take d = 1, d = 2 and d = 3 and calling ǫ = 2ǫ a , we have:

E [χ|N 1 = n, d = 1] = -n (1 -ǫ) n-1 , E [χ|N 1 = n, d = 2] = n 1 -ǫ2 n-2 (nǫ 3 -1), E [χ|N 1 = n, d = 3] = -n 1 -ǫ3 n-3 (n 2 ǫ6 -3nǫ 3 + ǫ3 + 1).
The following result is well known.

Lemma 6.5 If B d (x)
is the Bell's polynomial and for d ≥ 1, the following relations are valid:

d dx B d (x) = B d+1 (x) x -B d (x), d dx (e x B d (x)) = e x x B d+1 (x).
According to these relations, it is routine to prove the following theorem.

Theorem 6. [START_REF] Armstrong | Basic Topology[END_REF] The function (λ → E λ [χC ǫ (ω)]) has exactly d non-negative real roots. Moreover, between each consecutive roots and after the last one, there is exactly one critical point.

We can see by the expression of E λ [χ] that this quantity tends to 0 as λ tends to infinity. This convergence is due the fact that the Euler characteristic of the Cech complex of the cover tends to the Euler characteristic of the d-Torus where the points are deployed. This is shown in the following theorem. Theorem 6.7 The Betti numbers of C(U ǫ ) converge in probability to the Betti number of the torus as λ goes to infinity:

P λ d i=0 β i (C ǫ ) = β i (T d [a] ) λ→∞ ---→ 1.
Proof: Let η < ǫ/2, by compactness of the torus, there exists a finite collection of balls B of radius

η covering T d [a] . Since η < ǫ/2, if x belongs to some ball B ∈ B then B ⊂ B(x, ǫ), hence B∈B (ω(B) = 0) ⊂ U ǫ (ω) = T d [a] .
Thus,

P λ U ǫ (ω) = T d [a] ≤ P λ B∈B (ω(B) = 0) ≤ K exp(-λ(2η) d ) λ→∞ ---→ 0.
Moreover, by the nerve lemma, as stated on [14, Theorem 10.7]:

U ǫ (ω) = T d [a] ⊂ d i=0 β i (C ǫ ) = β i (T d [a] ) ,
and the result follows.

Remark 6.3 From the properties obtained of the Euler characteristic mean and based in some simulations, we conjuncture that, in a random simplicial complex as defined in this chapter, there is always two main kinds of holes in this complex, β i and β i+1 . So, for instance, consider Fig. 6.5 where points are placed in 5 dimensions. When λ is small, in average, the components are isolated from the others, so β 0 > 0 and we do not have other kinds of holes, so β 0 is the dominating Betti number. If λ is increased (which means, in average, to increase the number of points), the components connect with each other, decreasing β 0 and some cycles appears, so β 0 and β 1 are the dominating Betti numbers. Increasing λ even more, the complex becomes completely connected and we have a large number of cycles. For λ even larger, those cycles begin to vanish and we have the first voids. Then, we follow this reasoning until all the region is completely covered, so β 5 = 1 and χ = 0. The following lemma is straightforward. Lemma 6.8 Let k 1 , k 2 and k 3 be real positive constants and f : R 2 + → R defined as

f (x, y) = exp - k 1 -x 2k 2 log 1 + (k 1 -x)k 2 k 3 y •
Then, for k 1x > 0, the function is strictly increasing with respect to x and with respect to y. Theorem 6.9 For y > λa d , we have

P λ (β 0 ≥ y) ≤ exp - y -λa d 2 log 1 + y -λa d (2 d -1) 2 λ • Proof:
To apply Theorem 2.5, we need to evaluate max(Dβ 0 ) and Dβ 0 L ∞ (Ω,L 2 (Y )) . Since there are more points than connected components, E λ [β 0 ] ≤ E λ [N 0 ] = λa d . According to the definition of D, max(Dβ 0 ) is the maximum variation of β 0 induced by the addition of an arbitrary point. If this point is at a distance smaller than ǫ from ω, then Dβ 0 ≤ 0, otherwise, Dβ 0 = 1, so max(Dβ 0 ) = 1. Besides, this added point can join at most two connected components in each dimension, so in d dimensions it can join at most 2 d connected component, which means that Dβ 0 ranges from -(2 d -1) to 1, and then

Dβ 0 L ∞ (Ω,L 2 (Y )) ≤ λ max |Dβ 0 | 2 = λ(2 d -1) 2 .
Using Lemma 6.8 and Theorem 2.5, we get:

P λ (β 0 ≥ y) ≤ exp - y -λa d 2 log 1 + y -λa d (2 d -1) 2 λ , for y > λa d ≥ E λ [β 0 ].

Second order moments

We use all the definitions of the previous section.

Lemma 6.10 We can rewrite N k as

N k = 1 k! k i=0 k i λ k-i I i (T d a ) i h(x 1 , . . . , x k ) dx 1 . . . dx k-i .
Proof: We have that

∆ k h(x 1 , • • • , x k )( dω(x 1 ) -λ dx 1 ) . . . ( dω(x i ) -λ dx i )λ dx i+1 . . . λ dx k = i j=0 (-1) j i j ∆ k h(x 1 , • • • , x k ) dω(x 1 ) . . . dω(x j )λ dx j+1 . . . λ dx k .
Thus, after some algebrism with the binomial factors, we have

1 k! k i=0 k i i j=0 (-1) j i j ∆ k h(x 1 , • • • , x k ) dω(x 1 ) . . . dω(x j )λ dx j+1 . . . λ dx k = 1 k! ∆ k h(x 1 , • • • , x k ) dω(x 1 ) . . . dω(x k ) = N k ,
concluding the proof. Definition 6.1 Let C 1 and C 2 be two simplices with common vertices. For L ∈ P({1, 2}), let us denote m L the number of vertices belonging exactly to the list L of simplices. Then M = m 12 + m 1 + m 2 is the total number of vertices and J 2 represents the integral on these two simplices:

J 2 (m 12 , m 1 , m 2 ) = ∆ m 12 +m 1 ∆ m 12 +m 2 h m 12 +m 1 h m 12 +m 2 dx 1 . . . dx M . with x 1 , • • • , x M being the M vertices. -1 0 1 x 2 x m 12 . . . 1 x m 12 +1
x m 12 +m 1 . . .

J 2 (m 12 , m 1 , m 2 ) = m 12 + m 1 + m 2 + 2m 1 m 2 m 12 + 1 . (6.5)
Proof: Let us split the integration domain of J 2 in two domains S 1 and S 2 corresponding to the cases:

1. All the vertices are connected with each other, thus there is only one simplex. The integral on S 1 is simply the number of points in the simplex:

M = m 12 + m 1 + m 2 .
2. There are at least two vertices at distance d > 1, which leads to two simplices. By symmetry we can choose to order the m L vertices for each L ∈ P({1, 2}) from lowest to greatest or the opposite and choose which simplex is on which side of the axis.

Thus we have the integral on S 2 equal to 2m 12 !m 1 !m 2 !A, with A an integral whose calculation is detailed below.

We choose to enumerate the vertices of the simplexes such that:

• x 1 , • • • , x m 12 are the m 12 common vertices. • x m 12 +1 , • • • , x m 12 +m 1 are the m 1 vertices of only C 1 . • x m 12 +m 1 +1 , • • • , x M are the m 2 vertices of only C 2 .
Without loss of generality we can choose the origin to be x 1 . The vertices are now order as described in Fig. 6.6:

0 ≤ x m 12 ≤ x m 12 -1 ≤ • • • ≤ x 2 ≤ 1, -1 ≤ x 2 -1 ≤ x m 12 +1 ≤ x m 12 +2 ≤ • • • ≤ x m 12 +m 1 ≤ x m 12 +1 + 1 , and
x m 12 +1 ≤ x m 12 +m 1 +1 -1 ≤ x M ≤ x M -1 ≤ • • • ≤ x m 12 +m 1 +1 ≤ 1.
Let us denote J a (f )(x) =

x a f (u) du then we write the composition J

(2)

a (f )(x) =
x a u a f (v) dv du. We also denote m = m 12 + 1 and n = m 12 + m 1 + 1, then we have:

A = 1 0 J (m 12 -2) 0 (1)(x 2 ) 0 x 2 -1 -J (m 1 -1) xm+1 (1)(x m ) 1 xm+1 J (m 2 -1) xn-1 (1)(x n ) dx n dx m dx 2 .
We find that:

J (m 12 -2) 0 (1)(x 2 ) = x m 12 -2 2 (m 12 -2)! , -J (m 1 -1) xm+1 (1)(x m ) = 1 (m 1 -1)! , J (m 2 -1) xn-1 (1)(x n ) = 1 (m 2 -1)! .
Thus we have:

A = 1 (m 12 -2)!(m 1 -1)!(m 2 -1)! 1 0 x m 12 -2 2 0 x 2 -1 -x m dx m dx 2 = 1 (m 1 -1)!(m 2 -1)!(m 12 + 1)! ,
concluding the proof.

Theorem 6.12 Let ǫ ≤ a/6. Then, the covariance between the number of (k-1)-simplices, N k , and the number of (l -1)-simplices, N l , for l ≤ k is given by

Cov λ [N k , N l ] = l-1 i=0 1 i!(k -l + i)!(l -i)! (λ(2ǫ) d ) k+i a 2ǫ d k + i + 2 i(k -l + i) l -i + 1 d . (6.6)
Proof: We want to evaluate E λ [(N k -E λ [N k ])(N l -E λ [N l ])]
. By Lemma 6.10, this can be written as

E λ 1 k! k i=1 k i λ k-i I i f k i 1 l! l i=1 l i λ l-i I i f l i ,
where

f n j = (T d a ) j h(v 1 , • • • , v n ) dv 1 . . . dv n-j .
Using the isometry formula, given by Eq. (2.4), we have

Cov λ [N k , N l ] = 1 k!l! l i=1 k i l i λ k+l-2i E λ I i f k i I i f l i = 1 k!l! l i=1 k i l i λ k+l-2i i! f k i f l i L 2 (λ) •i = l-1 i=0 1 i!(k -l + i)!(l -i)! λ k-l+2i f k l-i f l l-i L 2 (λ) •(l-i) . (6.7)
Hence, we are reduced to compute

f k j f l j L 2 (λ) •(j) = (T d a ) j (T d a ) l-j h(v 1 , • • • , v l ) dv j+1 . . . dv l (T d a ) k-j h(v 1 , • • • , v k ) dv j+1 . . . dv k λ dv 1 . . . λ dv j .
Since a > ǫ/6, we have

f k j f l j L 2 (λ) •(j) = [0,a] d λ dv 1 ([0,a] d ) k-1 h(0, v 2 , • • • , v k ) × h(0, v 2 , • • • , v j , v ′ 1 , • • • , v ′ l-j ) dv ′ l-j . . . dv ′ 1 dv k . . . dv j+1 λ dv j . . . λ dv 2 . Moreover, if v i = (u i,1 , • • • , u i,d ) and v ′ i = (u ′ i,1 , • • • , u ′ i,d
) and we proceed to the following substitutions:

u i,1 = 2ǫx i if 2 ≤ i ≤ j, u i,1 = 2ǫy k-j if j + 1 ≤ i ≤ k, u ′ i,1 = 2ǫz i if 1 ≤ i ≤ l -j,
This results in a Jacobian (2ǫ) k+l-2i-1 and we recognize the integral to be exactly J 2 (j, kj, lj) as defined in Definition 6.1. Thus, we have:

f k j f l j L 2 (λ) •(j) = λ i a d (2ǫ) k+l-2i-1 (J 2 (j, k -j, l -j)) d .
Finally, using Eq. (6.5) and Eq. (6.7) gives the result.

Remark 6.4 It is possible to write Var(N k ) as Eq. (6.6) due the fact that we use the maximum norm. This simplifies the calculations since we can treat each component individually. However, considering the Euclidean norm it is still possible to find analytically a closed-form expression for Var(N k ), but its calculation involves nasty integrals and a generic term cannot be found. When we consider the Rips-Vietoris complex in T 2 a , the variance of the number of 1-simplices and 2-simplices are given by:

V λ [N 2 ] = a 2ǫ 2 π 2 (4λǫ 2 ) 2 + π 2 (4λǫ 2 ) 3 ,
and

V λ [N 3 ] = a 2ǫ 2 (4λǫ) 3 π 6 π - 3 √ 3 4 + (4λǫ 2 ) 4 π π 2 2 - 5 12 - π √ 3 2 +(4λǫ 2 ) 5 π 2 4 π - 3 √ 3 4 2   • Remark 6.5
In the same way that we explicit the mean of k simplexes in corollary 6.2 for a binomial point process with n points, variances, covariances, and N th moments can all be found since they can be written as a polynomial on λ.

Since we have an expression for the variance of the number of k-simplices, it is possible to calculate one for the Euler characteristic. Theorem 6.13 Let ǫ ≤ a/6. Then, the variance of the Euler characteristic in a d torus is:

V λ [χ] = a 2ǫ d ∞ n=1 c d n (λ(2ǫ) d ) n ,
where

c d n = n j=⌈(n+1)/2⌉   2 j i=n-j+1 (-1) i+j (n -j)!(n -i)!(i + j -n)! n + 2(n -i)(n -j) 1 + i + j -n d - 1 (n -j)! 2 (2j -n)! n + 2(n -j) 2 1 + 2j -n d .
Proof: The variance of χ is given by:

V λ [χ] = E λ (χ -E λ [χ]) 2 = E λ   ∞ k=1 (-1) k N k - ∞ k=1 (-1) k E λ [N k ] 2   = E λ   ∞ k=1 (-1) k (N k -E λ [N k ] 2   = E λ   ∞ i=1 ∞ j=1 (-1) i+j (N i -E λ [N i ])(N j -E λ [N j ])   .
We remark that N i ≤

N i 1 i! , so there is a constant c such that E λ   ∞ i=1 ∞ j=1 |(N i -E λ [N i ])(N j -E λ [N j ])|   ≤ ∞ i=1 ∞ j=1 N i 1 i! N j 1 j! ≤ cE λ [e n 1 ] 2 < ∞.
Thus the alternating series converges absolutely allowing us to exchange the mean with the sums and we can write

V λ [χ] = ∞ i=1 (-1) i ∞ j=1 (-1) j Cov λ [N i , N j ] .
The result follows by Eq. (6.6) and some tedious but straightforward algebra.

Lemma 6.14 Let n be a positive integer, then

n j=1 n j j -1 n -j -1 - j -1 n -j = (-1) n .
Proof: We first simplify the expression:

n j=1 n j j -1 n -j -1 - j -1 n -j = n j=1 2n -3j j n j j n -j ,
Then, applying hypergeometric functions, we solve the sum:

n j=1 2n -3j j n j j n -j = (-1) n .
Theorem 6.15 In one dimension, the expression of the variance of the Euler characteristic is:

V λ [χ] = a λe -2λǫ -4λ 2 ǫe -4λǫ .
Proof: If d = 1, according to Theorem 6.13:

V λ [χ] = a 2ǫ ∞ n=1 c 1 n (2λǫ) n , (6.8)
and we define

α n = n j=⌈ n+1 2 ⌉   2 j i=n-j+1 (-1) i+j n (n -j)!(n -i)!(i + j -n)! - n (n -j)! 2 (2j -n)!   . and β n = c 1 n -α. It is well known that 2j-n i=0 (-1) i j i = (-1) 2j-n-1 j -1 2j -n ,
using Stiffel's relation, we obtain:

α n = (-1) n n n! n j=⌈ n+1 2 ⌉ n j 2 2j-n i=0 (-1) i j i + 2(-1) n n j = 1 (n -1)! n j=⌈ n+1 2 ⌉ 2 n j j -1 n -j -1 - n j j n -j -2(-1) n n j = 1 (n -1)! n j=⌈ n+1 2 ⌉ n j j -1 n -j - j -1 n -j -1 -2(-1) n n j . (6.9)
The identity n j = n n-j allows us to write that

n j=⌈(n+1)/2⌉ (-2(-1) n ) n j = n j=0 n j = 2 n , n odd, n j=⌈(n+1)/2⌉ (-2(-1) n ) n j = n n/2 + n j=0 - n j = -2 n + n n/2 , n even. Since j-1 n-j = 0 for j < n+1 2 , we have n j=⌈ n+1 2 ⌉ n j j -1 n -j - j -1 n -j -1 = n j=1 n j j -1 n -j - j -1 n -j -1 for n odd and n j=⌈ n+1 2 ⌉ n j j -1 n -j - j -1 n -j -1 = - n n/2 + n j=1 n j j -1 n -j - j -1 n -j -1 .
for n even. According to Lemma 6.14, we get:

n j=⌈(n+1)/2⌉ n j j -1 n -j -1 - j -1 n -j = -1, n odd, n j=⌈(n+1)/2⌉ n j j -1 n -j -1 - j -1 n -j = 1 - n n/2 , n even.
Then, we substitute these two last expressions in Eq. (6.9) to obtain

α n = (-1) n (1 -2 n )1 [n≥1] (n -1)! ,
and thus

∞ i=0 α n x n = -xe -x + 2xe -2x .
Proceeding along the same line, β n is given by

β n = n j=⌈ n+1 2 ⌉   2 j i=n-j+1 (-1) i+j 2(n -i)(n -j) (n -j)!(n -i)!(i + j -n + 1)! - 2(n -j) 2 (n -j)! 2 (2j -n + 1)! = (-1) n (-2 + 2 n )1 [n≥1] (n -1)! - 21 [i≥2] (i -2)! ,
and again we can simplify the power series ∞ i=0 β n x n :

∞ i=0 β n x n = 2xe -x -2(x + x 2 )e -2x .
Then, substituting α n and β n in Eq. (6.8) yields the result. Theorem 6. [START_REF] Broadbent | Percolation processes. i. crystals and mazes[END_REF] We have Dχ ≤ 2 and Dχ L ∞ (Ω,L 2 (T d a )) < ∞ and

P(χ -χ ≥ x) ≤ exp - x 4 log 1 + 2x V λ [χ] .
Proof: In two dimensions, the Euler characteristic is:

χ = β 0 -β 1 + β 2 .
Therefore we can bound Dχ by the variation of β 0β 1 added to the variation of β 2 when we add a vertex to a simplicial complex.

If we add a vertex on the torus, either the vertex is isolated or not. In the first case, it forms a new connected component incrementing β 0 by 1, and the number of holes that is β 1 is the same. Otherwise, as there is no new connected component, β 0 is the same, but the new vertex can at most fill a hole incrementing β 1 by 1. Therefore, the variation of β 0β 1 is at most 1. Now, let us look at the variation of β 2 when we add a vertex to a simplicial complex. According to Proposition 5.3 is at most 1, showing that Dχ ≤ 2. Then, we use Eq. (2.7) to complete the proof.

N th order moments

For this section, without loss of generality, using Proposition 5.5, we can choose k = 1/2ǫ, so λ τ = λ(2ǫ) d , ǫ τ = 1/2 and ak = a/2ǫ.

We are interested in the central moment, so we introduce the following notation for the centralized number of (k -1)-simplices: Ñk = N k -Nk .

Finally, let us denote that i j = 0 as soon as i ≤ 0 or j ≤ 0 or ij ≤ 0 for i and j integers.

We extend the Definition 6.1 used in the second order moments calculations. Then M = m 123 + m 12 + m 13 + m 23 + m 1 + m 2 + m 3 is the total number of vertices and J 3 represents the integral on these three simplices:

J 3 = ∆p 1 ∆p 2 ∆p 3 h p 1 h p 2 h p 3 dx 1 . . . dx M .
with p i being the number of vertices of simplex C i for i = 1, • • • , 3, for instance p 1 = m 123 + m 12 + m 13 + m 1 , and x 1 , • • • , x M being the M vertices. Definition 6.3 We denote J 3 (i, j, s, t) the integral defined above such that

• m 123 = 2t -i -j + s ∨ 0 • m 12 = i + j -s -t ∨ 0 • m 13 = i -t ∨ 0 • m 23 = j -t ∨ 0 • m 1 = k -i ∨ 0 • m 2 = k -j ∨ 0 • m 3 = k -s ∨ 0.
Theorem 6.17 The third moment of the number of (k -1)-simplices is given by:

E λ N k 3 = i,j,s,t λ 3k-i-j t! k i k j k s i t j t t i + j -s -t J 3 (i, j, s, t),
with s ≥ |i -j|.

Proof: From Lemma 6.10 , we know that the chaos decomposition of the number of (k -1)-simplices is given by

N k = I 1 (f 1 ) + • • • + I k (f k ) = k i=1 I i (f i ), with f i (x 1 , • • • , x i ) = k i h(x 1 , • • • , x k )λ k-i dx k . . . dx i+1 , and
I i (f i ) = f i ( dω(x 1 ) -dλ(x 1 )) . . . ( dω(x i ) -dλ(x i )).
Then, we define

g i,j,i+j-s = i+j-s∧i∧j t=⌈ i+j-s 2 ⌉ t! i t j t t i + j -s -t f i • u-t t f j
and using the chaos expansion (cf Proposition 2.3), we get

N k 3 = (I 1 (f 1 ) + • • • + I k (f k )) 3 =   k i=1 k j=1 I i (f i )I j (f j )   (I 1 (f 1 ) + • • • + I k (f k )) = k i,j=1 i+j s=|i-j| I s (g i,j,i+j-s )(I 1 (f 1 ) + • • • + I k (f k )) = k i,j,l=1 i+j s=|i-j| I s (g i,j,i+j-s )I l (f l ).
According to (2.4), denoting u = i + js, we obtain:

E λ N k 3 = E λ   k i,j=1 i+j∧k s=|i-j|∨1 I s (g i,j,u )I s (f s )   = k i,j=1 i+j∧k s=|i-j|∨1 g i,j,u f s λ s dx 1 . . . dx s = k i,j=1 i+j∧k s=|i-j|∨1 u∧i∧j t=⌈ u 2 ⌉ λ s t! i t j t t u -t (f i • u-t t f j )f s dx 1 . . . dx s .
Then we recognize the integral defined in Definition 6.3:

E λ N k 3 = k i,j,=1 i+j∧k s=|i-j|∨1 u∧i∧j t=⌈ u 2 ⌉ λ 3k-i-j t! k i k j k s i t j t t u -t J 3 (i, j, s, t).
Finally, relaxing the boundaries on the sums conclude the proof. Then M = L∈P({1,••• ,n}) m L is the total number of vertices and J n represents the integral on these n simplices:

J n = ∆p 1 • • • ∆p n h p 1 . . . h pn dx 1 . . . dx M .
with p i being the number of vertices of simplex C i for i = 1, • • • , n, and x 1 , • • • , x M being the M vertices. Theorem 6. [START_REF] Chong | Sensor networks: Evolution, opportunities, and challenges[END_REF] The expression of the n-th power of the number of (k -1)-simplices is given by: (6.10) where for j ∈ {1, • • • , n -2}:

N n k = i 1 ,••• ,in s 1 ,•••s n-2 t 1 ,•••t n-2   n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   I a (• j∈A f i j )I b (• j∈A f i j ),
• 1 ≤ i 1 , • • • , i n ≤ k, • s j ≥ |m j,1 -m j,2 |, • m j,1 = i 2j-1 if 1 ≤ j ≤ ⌊ n 2 ⌋ and s 2(j-⌊ n 2 ⌋)-1 otherwise, • m j,2 = i 2j if 1 ≤ j ≤ ⌊ n 2 ⌋ and s 2(j-⌊ n 2 ⌋) otherwise, • u j = m j,1 + m j,2 -s j , • A ⊂ {1, • • • , n}, • If n is even, then a = s n-3 and b = s n-2 ,
• If n is odd, then a = s n-2 and b = i n .

Proof: The decomposition of the centralized number of (k -1)-simplices is:

N k = I 1 (f 1 ) + • • • + I k (f k ) = k i=1 I i (f i ).
Now, we raise N k to the n-th power:

N k n = k i=1 I i (f i ) n .
First, we consider the case where n is even, we can group the factors two by two:

N n k = k i 1 =1 I i 1 (f i 1 ) k i 2 =1 I i 2 (f i 2 ) . . .   k i n-1 =1 I i n-1 (f i n-1 ) k in=1 I in (f in )   .
We then use the chaos expansion of Proposition 2.3:

I i (f i )I j (f j ) = 2(i∧j) s=0 I i+j-s   s≤2t≤2(s∧i∧j) t! i t j t t s -t f i • s-t t f j   = i+j s=|i-j| I s   i+j-s≤2t≤2(i+j-s)∧i∧j) t! i t j t t i + j -s -t f i • i+j-s-t t f j   .
Let us denote

g s = t! i t j t t i + j -s -t f i • i+j-s-t t f j ,
so we can re-write, relaxing the boundaries on the sums:

I i (f i )I j (f j ) = s≥|i-j| t I s (g s ).
Thus, we have:

N n k = k i 1 ,i 2 =1 s 1 ≥|i 1 -i 2 | t 1 I s 1 (g s 1 ) • • • k i n-1 ,in=1 s n/2 ≥|i n-1 -in| t n/2 I s n/2 (g s n/2 ).
We go on grouping terms by 2 until we only have a product of 2 chaos left: First we made n/2 chaos expansions, leading to n/2 sums with indexes s j , j = 1, • • • , n/2. To reduce the number of chaos to 2, we have to make other chaos expansions. For j ≥ n 2 + 1, the sum indexed by s j represents the expansion of the chaos indexed s 2(j-n

2 )-1 and s 2(j-n 2 )-1 . We have 2 chaos remaining when j = 2(j -n 2 ) + 2, i.e. when j = n -2. Moreover, there are as much sums indexed with t j as with s j , that is n -2. Thus we can write:

N n k = k i 1 ,••• ,in=1 s 1 ,•••s n-2 t 1 ,•••t n-2 I s n-3 (φ s n-3 )I s n-2 (φ s n-2 ), With s j ≥ |m j,1 -m j,2 | for j ∈ {1, • • • , n -2} if we denote: • m j,1 = i 2j-1 if 1 ≤ j ≤ n 2 and s 2(j-n 2 )-1 otherwise, • m j,2 = i 2j if 1 ≤ j ≤ n
2 and s 2(j-n 2 ) otherwise. Then, denoting u j = m j,1 + m j,2s j and A the subset of {1, • • • , n} such that if j ∈ A then the chaos i j is expanded in the chaos s n-3 , we have:

I s n-3 (φ s n-3 )I s n-2 (φ s n-2 ) =   n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   I s n-3 (• j∈A f i j )I s n-2 (• j∈A f i j ).
The notation • j∈A f i j represents the product defined in Eq. (2.6) of the functions f i j for j ∈ A, but whom variables depend on all the i 1 ,

• • • , i n , s 1 , • • • , s n-2 , and t 1 , • • • , t n-2 .
Now, if n is odd, we consider n -1 which is even, therefore we have:

N n k = k i 1 ,••• ,i n-1 =1 s 1 ,••• ,s n-3 t 1 ,••• ,t n-3 I s n-4 (φ s n-4 )I s n-3 (φ s n-3 ) k in=1 I in (f in ) = k i 1 ,••• ,in=1 s 1 ,••• ,s n-2 t 1 ,••• ,t n-2 I s n-2 (φ s n-2 )I in (f in ),
with s j ≥ |m j,1m j,2 | for j ∈ {1, • • • , n -2} using the same notations for n -1 instead of n:

• m j,1 = i 2j-1 if 1 ≤ j ≤ n-1 2 and s 2(j-n-1 2 )-1 otherwise, • m j,2 = i 2j if 1 ≤ j ≤ n-1
2 and s 2(j-n-1 2 ) otherwise. And with u j = m j,1 + m j,2s j ,

I s n-2 (φ s n-2 ) =   n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   I s n-2 (• j∈{1,••• ,n-1} f i j ),
concluding the proof. Theorem 6. [START_REF] Cooper | Introduction to queueing theory[END_REF] The expression of the n-th moment of the number of (k -1)-simplices is given by:

E λ N k n = i 1 ,••• ,in s 1 ,••• ,s n-3 t 1 ,••• ,t n-2 λ nk+c   n j=1 λ -i j k i j     n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   J n (i 1 , • • • , i n , s 1 , • • • , s n-3 , t 1 , • • • , t n-2 ). With for j ∈ {1, • • • , n -2}: • if j ≤ n -3, s j ≥ |m j,1 -m j,2 |, • m j,1 = i 2j-1 if 1 ≤ j ≤ ⌊ n 2 ⌋ and s 2(j-⌊ n 2 ⌋)-1 otherwise, • m j,2 = i 2j if 1 ≤ j ≤ ⌊ n 2 ⌋ and s 2(j-⌊ n 2 ⌋) otherwise, • m j,3 = s j if 1 ≤ j ≤ n -3 and s n-3 otherwise, • u j = m j,1 + m j,2 -m j,3 , • If n is even, then c = s n-3 and s n-3 ≥ |m n-2,1 -m n-2,2 | ∨ |m n-3,1 -m n-3,2 |, • If n is odd, then c = i n and i n ≥ |m n-2,1 -m n-2,2 |.
Proof: The expression of the n-th power of the number of (k -1)-simplices is given in Eq. (6.10):

N n k = k i 1 ,••• ,in=1 s 1 ,••• ,s n-2 t 1 ,••• ,t n-2   n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   I a (• j∈A f i j )I b (• j∈A f i j ).
If n is even, we have:

N n k = k i 1 ,••• ,in=1 s 1 ,••• ,s n-2 t 1 ,••• ,t n-2   n-2 j=1 t j ! m j,1 t j m j,2 t j t j u j -t j   I s n-3 (• j∈A f i j )I s n-2 (• j∈A f i j ).
So let us focus on the only part of the equation that is likely to change when we take the expected value, which we will denote:

K = s n-3 s n-2 I s n-3 (• j∈A f i j )I s n-2 (• j∈A f i j ).
We then use the property of Eq. (2.4) and recognize the integral from Definition 6.4:

E λ [K] = s n-3   n j=1 λ k-i j k i j   λ s n-3 J n (i 1 , • • • , i n , s 1 , • • • , s n-3 , t 1 , • • • , t n-2 ) = s n-3 λ nk+s n-3   n j=1 λ -i j k i j   J n (i 1 , • • • , i n , s 1 , • • • , s n-3 , t 1 , • • • , t n-2 ), with s n-3 ≥ |m n-2,1 -m n-2,2 | ∨ |m n-3,1 -m n-3,2 |.
Then for n odd we directly write:

K ′ = in s n-2 I in (• j∈I f i j )I s n-2 (• j∈I f i j ), E λ K ′ = in λ nk+in   n j=1 λ -i j k i j   J n (i 1 , • • • , i n , s 1 , • • • , s n-3 , t 1 , • • • , t n-2 ), with i n ∈ {|m n-2,1 -m n-2,2 | ∨ 1, k}.
The binomials with the i j allow us to relax the boundaries on the sums on i j , concluding the proof.

Convergence

Let Γ be an arbitrary connected simplicial complex containing n points and C ǫ (ω) be the random simplicial complex by the Poisson point process ω. The number of occurrences of Γ in C ǫ (ω) is denoted as G Γ (ω). It must be noted that with our construction of the simplicial complex, a complex Γ appears in C ǫ (ω) as soon as its edges are in C ǫ (ω). The set of edges of Γ, denoted by

J Γ is a subset of {1, • • • , n} × {1, • • • , n}. Let h(x 1 , • • • , x n ) = 1 c Γ (i,j)∈J Γ 1 [ x i -x j ≤ǫ] ,
where c Γ is the number of permutations of {x 1 ,

• • • , x n } such that h Γ (x 1 , • • • , x n ) = h Γ (x σ(1) , • • • , x σ(n) ),
and let

f Γ (x 1 , • • • , x n ) be the symmetrization of h Γ (x 1 , • • • , x n ).
Then, we have:

G Γ = x 1 ,••• ,xn∈ω x i =x j if i =j f Γ (x 1 , • • • , x n ) = ∆n f Γ (x 1 , • • • , x n ) dω(x 1 ) • • • dω(x n ). ( 6
G Γ = n i=0 I i (f Γ i ),
where f Γ i is a bounded symmetric function given by

f Γ i (x i+1 , • • • , x n ) = n i λ n-i B n-i f Γ (x 1 , • • • , x n ) dx 1 . . . dx n-i , (6.12)
for any i ∈ {1, • • • , n}.

Proof: From (6.11), using the binomial expansion and some algebra, we obtain

G Γ = n i=0 ∆ i    n i ∆ n-i f Γ (x 1 , • • • , x n )λ dx 1 . . . λ dx n-i    ( dω(x n-i+1 ) -λ dx n-i+1 ) . . . ( dω(x n ) -λ dx n ).
To conclude the proof, we note that, since the torus is a compact set and h Γ is bounded, f Γ i is bounded. Lemma 6.21 For any Γ connected simplicial complex containing n points, for λ large enough,

E λ [G Γ ] ≤ cλ n and V λ [G Γ ] ≤ P 2n-1 Γ (λ).
where P 2n-1 Γ (λ) is a polynomial on λ of degree 2n -1 depending on Γ.

Proof: Using Lemma 6.20 and the chaos properties, we obtain

E λ [G Γ ] = λ n ∆n f Γ (x 1 , • • • , x n ) dx 1 . . . dx n ≤ cλ n , since f Γ is bounded. Furthermore, V λ [G Γ ] = n i=1 i! f Γ i 2 L 2 (B,λ) = n i=1 i! ∆ i   λ n-i n i B n-i f Γ (x 1 , • • • , x n ) dx 1 . . . dx n-i   2 λ dx 1 . . . λ dx i = n i=1 i! λ 2n-i ∆ i   n i B n-i f Γ (x 1 , • • • , x n ) dx 1 . . . dx n-i   2 dx 1 . . . dx i . and since f Γ is bounded, V λ [G Γ ] is a polynomial of degree 2n -1. Lemma 6.22 For λ large enough, if k > 1, E λ (I k (1)) 2 < cλ 2k-1 ,
and

E λ (I k (1)) 2 is constant if k = 0.
Proof: The proof is trivial for the case k = 0. If k ≥ 1, for i ≤ k we have

∆ i dω(x 1 ) . . . dω(x i ) = i-1 j=0
(ω(B)j), so we can rewrite I k (1) as follows:

I k (1) = k i=0   k i (-λS(B)) i k-i-1 j=0 (ω(B) -j)   .
Thus, E λ (I k (1)) 2 can be written as

E λ (I k (1)) 2 = E λ   (ω(B) -λS(B)) 2k + 2≤i+j≤2k-1 c i,j ω(B) i (λS(B)) j   ,
where the c i,j are integer constants.

If we differentiate the k-th central moment

E[(N -λ ′ ) k ] = ∞ i=0 (r -λ ′ ) k e -λ ′ (λ ′ ) i i!
of a random variable N distributed as Poisson with mean λ ′ , with respect to λ ′ we find the following recurrence:

E[(N -λ ′ ) k+1 ] = λ ′ dE[(N -λ ′ ) k ] dλ ′ + kE[(N -λ ′ ) k-1 ] .
Hence, using induction we can show that E[(Nλ ′ ) k ] is a polynomial on λ with maximum degree ⌊k/2⌋, for k > 1. Since E λ ω(B) i is the Bell Polynomial of degree i on λ, it follows straightforwardly that the polynomial

E λ   2≤i+j≤2k-1 c i,j ω(B) i (λS(B)) j  
has degree at most 2k -1, and the proof is thus complete. Definition 6.5 Let f i , g j and h k be, respectively, functions of i-th, j-th and k-th chaos of the Wiener-Poisson decomposition of some square integrable function of ω. For 0 ≤ s ≤ 2(n ∧ m), we define

f i ⋆ s g j = s≤2n≤2(s∧i∧j) n! i n j n f i • s-n n g j .
For 0 ≤ r ≤ 2((i + js) ∧ k), we abuse of the notation to write

h k ⋆ r (f n ⋆ s g m ) = h k ⋆ r f n ⋆ s g m . Lemma 6.23 If |f n (x 1 , • • • , x n )| is bounded by a positive real c, then E λ I n (f n ) 2 ≤ c 2 E λ I n (1) 2 .
Proof: We use the isometry formula given by Eq. (2.5), so

E λ I n (f n ) 2 = n! f n L 2 (λ) •n = n! B n f 2 n (x 1 , • • • , x n )λ dx 1 . . . λ dx n ≤ n! B n c 2 λ dx 1 . . . λ dx n = c 2 E λ I n (1) 2 ,
and the proof is complete.

Theorem 6.24 Let F = G Γ -E λ [G Γ ] √ V λ [G Γ ]
, then, for λ large enough,

B E λ |D t F | 2 |D t L -1 F | λ dt ≤ c λ 1/2 • Proof: Provided that G Γ has n points, Lemma 6.20 shows that G Γ = n i=0 I n (f Γ n ), so D t F = 1 V λ [G Γ ] n i=1 iI i-1 (f Γ i ( * , t)), D t L -1 F = 1 V λ [G Γ ] n i=1 I i-1 (f Γ i ( * , t)).
Let us define

g i-1 = f Γ i ( * , t) λ n-i •
According to Eq. (6.12), we note that g i does not depend on λ. Using the triangular inequality, we have

|D t F | 2 |D t L -1 F | ≤ n-1 i,j,k=0 λ 3n-3-i-j-k (i + 1)(j + 1) V λ [G Γ ] 3 2 |I i (g i )I j (g j )I k (g k )|.
Then, we apply twice the chaos expansion and use again the triangular inequality to obtain:

|D t F | 2 |D t L -1 F | ≤ n-1 i,j,k=0 2(i∧j) s=0
2((i+j-s)∧k) r=0 λ 3n-3-i-j-k (i + 1)(j + 1)

V λ [G Γ ] 3 2 × |I i+j+k-s-r (g i ⋆ r g j ⋆ s g k )|,
Since f i is bounded, g i is bounded as so g i ⋆ r g j ⋆ s g k for i, j, k, r, s in the range of their indexes above. We define c(i, j, k, r, s) = sup{g i ⋆ r g j ⋆ s g k }(i + 1)(j + 1), and we use Jensen's inequality and Lemma 6.23 to write

E λ |D t F | 2 |D t L -1 F | ≤ n-1 i,j,k=0 2(i∧j) s=0 2((i+j-s)∧k) r=0 λ 3n-3-i-j-k V λ [G Γ ] 3 2 E λ (I i+j+k-s-r (g i ⋆ r g j ⋆ s g k )) 2 ≤ n-1 i,j,k=0 2(i∧j) s=0
2((i+j-s)∧k) r=0 λ 3n-3-i-j-k c(i, j, k, r, s)

V λ [G Γ ] 3 2
E λ (I i+j+k-s-r (1)) 2 .

Using Lemmas 6.21 and 6.22 we obtain:

B E λ |D t F | 2 |D t L -1 F | λ dt ≤ n-1 i,j,k=0 2(i∧j) s=0 2((i+j-s)∧k) r=0 c(i, j, k, r, s) × λ 3n-3-i-j-k V λ [G Γ ] 3 2 E λ (I i+j+k-s-r (1)) 2 1/2 B λ dt ≤ cλ 3n-3 V λ [G Γ ] 3 2 B λ dt ≤ c λ 1/2 , concluding the proof. Theorem 6.25 Let F = G Γ -E λ [G Γ ] V ar(G Γ ) •
Then, when λ is large enough

E λ |1 -DF, DL -1 F L 2 (λ) | ≤ c λ 1/2 ,
for some constant c.

Proof: The expressions of D t F and D t L -1 F are given by

D t F = 1 V λ [G Γ ] n i=1 iI i-1 (f i ( * , t)), and
D t L -1 Z = 1 V λ [G Γ ] n i=1 I i-1 (f i ( * , t)).
The inner product D t L -1 F, D t F L 2 (λ) is expressed by:

D t L -1 F, D t F L 2 (λ) = 1 V λ [G Γ ] B n i,j=1 iI i-1 (f i ( * , t))I j-1 (f j ( * , t))λ dt.
Then,

D t L -1 Z, D t Z L 2 (λ) = 1 V λ [G Γ ] n i,j=1 i B I i-1 (f i ( * , t))I j-1 (f j ( * , t))λ dt = 1 V λ [G Γ ] B I 0 (f 1 (t) 2 λ dt + 1 V λ [G Γ ] n i,j=1 (i,j) =(1,1) i B I i-1 (f i ( * , t))I j-1 (f j ( * , t))λ dt.
Defining g i-1 as in Theorem 6.24 and using the chaos expansion, we get:

D t L -1 F, D t F L 2 (λ) = f 1 2 L 2 (λ) V λ [G Γ ] + 1 V λ [G Γ ] n i=2 i(i -1)! B f n ( * , t) 2 L 2 (λ) λ dt + n-1 i=1 (i + 1) λ 2n-2i-2 V λ [G Γ ] B 2(i-1) s=0 I 2i-s (g i ⋆ s g i )λ dt + n-1 i,j=0 (i + 1) λ 2n-i-j-2 V λ [G Γ ] B 2(i∧j) s=0 I i+j-s (g i ⋆ s g j )λ dt. Since B f i ( * , t) 2 L 2 (λ) λ dt = B B i-1 f 2 i (t 1 , • • • , t i-1 , t)λ dt 1 . . . λ dt i-1 λ dt = B i f 2 i (t 1 , • • • , t i-1 , t)λ dt 1 . . . λ dt i-1 λ dt = f i L 2 (λ) ,
and given the isometry formula

V λ [G Γ ] = G Γ L 2 Ω -E λ [G Γ ] 2 = i=0 n! f i 2 L 2 (B i ) -f 0 2 = i=1 n! f i 2 L 2 (λ) ,
we have

f 1 2 L 2 (λ) V λ [G Γ ] + 1 V λ [G Γ ] n i=2 i(i -1)! B f i ( * , t) 2 L 2 (λ) λ dt = 1.
Hence

D t L -1 Z, D t Z L 2 (λ) = 1 + n-1 i,j=0 (i,j) =(1,1) 2(i∧j) s=0 s =2i if i=j (i + 1) λ 2n-i-j-2 V λ [G Γ ] B I i+j-s (g i ⋆ s g j )λ dt.
Let c(i, j, s) be defined as c(i, j, s) = sup{g i ⋆ s g j }(i + 1).

Then, we use the triangular inequality, Jensen's inequality and Lemma 6.23 to obtain:

E λ |1 -DF, DL -1 F L 2 (λ) | ≤ E λ n-1 i,j=0 (i,j) =(1,1) 2(i∧j) s=0 s =2i if i=j (i + 1) λ 2n-i-j-2 V λ [G Γ ] B |I i+j-s (g i ⋆ s g j )| λ dt ≤ n-1 i,j=0 (i,j) =(1,1) 2(i∧j) s=0 s =2i if i=j (i + 1)λ 2n-i-j-2 V λ [G Γ ] B E λ (I i+j-s (g i ⋆ s g j )) 2 1 2 λ dt ≤ n-1 i,j=0 (i,j) =(1,1) 2(i∧j) s=0 s =2i if i=j c(i, j, s) λ 2n-i-j-2 V λ [G Γ ] E λ (I i+j-s (1)) 2 1/2 B λ dt.
Finally, using Lemmas 6.22 and 6.21, there is a constant c such that:

E λ |1 -DF, DL -1 F L 2 (λ) | ≤ c λ 1/2
for λ large enough. Theorem 6.26 There exists a constant c such that, for λ large enough, the Wasserstein distance between

F = G Γ -E λ [G Γ ] √ V ar(G Γ )
and N (0, 1) is given by:

d W (F, N (0, 1)) ≤ c λ 1/2 • Proof:
The proof comes straightforwardly from Theorem 3.1 as stated in [START_REF] Peccati | Stein's method and normal approximation of poisson functionals[END_REF]:

d W (F, N (0, 1)) ≤ E λ |1 -DF, DL -1 F L 2 (λ) | + B E λ |D t F | 2 |D t L -1 F | λ dt,
which we can use since f n is bounded, so F ∈ Dom D. We use theorems 6.24 and 6.25 in the first and second terms, respectively. Remark 6. [START_REF] Armstrong | Basic Topology[END_REF] We note that for any definition of h

(x 1 , • • • , x n ) such that h(x 1 , • • • , x n ) ≥ 1,
this theorem will hold. This means that, as long as the formation of simplices depends only on the positions of the points, the law of the number of connected components will converge to a Gaussian law. For example, this cover the cases on R d , on d-torus, for Cech complexes or Rips complexes.

Summary

In this chapter, we have obtained a way to find the n-th moment of the k-simplices in a random simplicial complex from points of a Poisson and Binomial point process as vertices in d dimensions. This is done by using the chaos expansion and evaluating some integrals. We have seen that the expressions of such moments are very complex for moments of order superior or equal to three, but the mean is expressed in a very simplified fashion and the variance is given by the sum of k terms. The same method used to find the variance can be applied to find the covariance between the number of k-simplices and l-simplices and its expression is given by a sum of the minimum of k and l terms.

With respect to the Euler characteristic, we have calculated also a closed-form expression for its mean using the alternating sum of the mean of k-simplices, resulting in a Bell polynomial over as a function of λ(2ǫ) d . Moreover, we have found an infinite power series to express its variance by using the covariance result. Then, we have simplified the variance of the Euler characteristic for d = 1 and we have simplified two terms over d + 1 of the variance in d dimensions. A concentration inequality has been used to find an upper bound to the tail of the Euler characteristic distribution. We have also conjectured that at most two kinds of holes are predominant.

Although we determine a way to find the n-th moment of N k , their expressions are too complex for n ≥ 3 and so it is not possible to find their distributions. However, in Section 6.5, we have used Theorem 3.1 as stated in [START_REF] Peccati | Stein's method and normal approximation of poisson functionals[END_REF] to determined an upper bound for the distance between the distribution of N k and the Gaussian one with mean E λ [N k ] and variance Var(N k ). This result holds in any dimension for points deployed over any compact set and actually the result holds not just for k-simplices, but for any kind of connected graph.

Chapter 7

One-dimensional Case

Introduction

The previous chapter considers sensors represented by a random configuration on d dimensions. Although we can obtain important results concerning the moments and distributions of quantities such as the number of k-simplices and Euler characteristic, there are some unanswered questions regarding the number of connected components and coverage. Trying to answer those questions, we quickly realized that the dimension of the ambient space played a key role. We then first began by the analysis of dimension 1, which appeared to be the simplest situation. In this case, there is no need of algebraic topology so we will not go further in the description of this line of thought even if it was our first motivation.

In dimension 1, the only question of interest is that of the connexity but it can take different forms. Imagine we are given [0, 1] as a domain in which n points {x 1 , • • • , x n } are drawn. For a radius r, one can wonder whether

[0, 1] ⊂ ∪ i=1, ••• , n [x i -r, x i + r] or one can investigate whether [x i -r, x i + r] ∩ [x i+1 -r, x i+1 + r] = ∅ for all i = 1, • • • , n -1.
The second situation is less restrictive since we do not impose that the frontier of the interval to be covered. Depending on the application we have in mind, both questions are sensible. A slightly different but somehow close problem is that of the circle: Consider now that the points are dispatched along a circle of unit perimeter C 1 and ask again whether C 1 ⊂ ∪ i=1, ••• , n B(x i , r) where B(x, r) is the 2-dimensional ball of center x and radius r. Several years ago, this problem has been thoroughly analyzed [START_REF] Siegel | Covering the circle with random arcs of random sizes[END_REF] and references therein) for a fixed number of i.i.d. arcs over the circle. A closed form formula can be given for the probability of coverage as a function of the number and of the common law of the arcs length. Some variations of this problem have been investigated since, see for instance [START_REF] Holst | On multiple covering of a circle with random arcs[END_REF]. More recently, in [START_REF] Kumar | New technological vistas for systems and control: the example of wireless networks[END_REF], algorithms are devised to determine whether a domain can be protected from intrusion by a "belt" of sensors (namely a ring or the border of a rectangle). There is no performance analysis in this work which is focused on algorithmic solutions for this special problem of coverage. Still motivated by applications to sensor networks, the paper [START_REF] Manohar | Path coverage by a sensor field: the nonhomogeneous case[END_REF] considers the situation where sensors are actually placed in a plan, have a fixed radius of observation and analyses the connectivity of the trace of the covered region over a line. The works of Kahle [START_REF] Kahle | Limit theorems for betti numbers of random simplicial complexes[END_REF][START_REF] Kahle | Random geometric complexes. Discrete and Computational Geometry[END_REF] are actually hardly linked to our results: the motivation is the same, studying the Betti numbers of some random simplicial complexes but the results are only asymptotic and valid in dimension greater than 2.

Our main result is the distribution of the number of connected components for a Poisson distribution of sensors in a bounded interval. We could not use the method of [START_REF] Siegel | Covering the circle with random arcs of random sizes[END_REF] since the number of gaps does not determine the connectivity of the domain. For instance, one may have only one gap at the "beginning" which means that all the points are pairwise within the threshold distance and thus that the network is connected or one may have only one gap in the "middle" which means that there is a true hole of connectivity.

Actually, our method is very much related to queueing theory. Indeed, clusters, i.e. sequence of neighboring points, are the strict analogous of busy periods -see Section 7.2. As will appear below, our analysis turns down to be that of an M/D/1/1 queue with preemption: When a customer arrives during a service, it preempts the server and, since there is no buffer, the customer who was in service is removed from the queuing system. This analogy led us to use standard tools of queueing theory: Laplace transform and renewal processes -see for instance [START_REF] Asmussen | Applied probability and queues[END_REF][START_REF] Cooper | Introduction to queueing theory[END_REF]. This works perfectly and with a bit of calculus, we can compute all the characteristics we are interested in. It is worthwhile to note that a queueing model (namely the M/G/∞) also appears in [START_REF] Manohar | Path coverage by a sensor field: the nonhomogeneous case[END_REF].

The paper is organized as follows: Section 2 presents the model and defines the relevant quantities to be calculated. The calculations and analytical results are presented in Section 3. For our situation, we find results analogous to that of [START_REF] Siegel | Covering the circle with random arcs of random sizes[END_REF]. In section 4, two other scenarios are presented, considering the number of incomplete clusters and clusters placed in a circle. In Section 5, numerical examples are presented and analyzed.

Problem Formulation

Let L > 0, we assume that we are given a Poisson process, denoted by N , of intensity λ on [0, L]. Let (X i , i ≥ 1) be the atoms of N . We thus know that the random variables, ∆X i = X i+1 -X i are i.i.d. and exponentially distributed. We fix ǫ > 0. Two points, located respectively at x and y, are said to be directly connected whenever |x -y| ≤ ǫ. For i < j, two points of N , say X i and X j , are indirectly connected if X l and X l+1 are directly connected for any l = i, • • • , j -1. A set of points directly or indirectly connected is called a cluster, a complete cluster is a cluster which begins and ends within [0, L]. The connectivity of the whole network is measured by the number of clusters.

The number of points in the interval [0, x] is denoted by

N x = ∞ n=0 1 [Xn≤x] . The random variable A i given by A i = X 1 if i = 1, inf{X j : X j > A i-1 , X j -X j-1 > ǫ} if i > 1,
represents the beginning of the i-th cluster, denoted by C i . In the same way, the end of this same cluster, E i , is defined by

E i = inf{X j + ǫ : X j > A i , X j+1 -X j > ǫ}.
So, the i-th cluster, C i , has a number of points given by N E i -N A i . We define the length B i of C i as E i -A i . The intercluster size, D i , is the distance between the end of C i and the beginning of C i+1 , which means that D i = A i+1 -E i and ∆A i is the distance between the first points of two consecutive clusters C i , given by ∆A

i = A i+1 -A i = B i + D i .
Remark 7.1 With this set of assumptions and definitions, we can see our problem as an M/D/1/1 preemptive queue, see Fig. 7.1. In this non-conservative system, the service time is deterministic and given by ǫ. When a customer arrives during a service, the served customer is removed from the system and replaced by the arriving customer. Within this

ǫ Remaining service time Time • • • X 1 A 1 1↓ X 2 2↓ 1↑ X 3 3↓ 2↑ X 4 A 2 3⇑ E 1 4↓ X 5 5↓ 4↑ 5⇑ X 6 A 3 E 2 6↓ X 7 7↓ 6↑ Figure 7
.1: Queueing representation of the proposed problem. A down arrow denotes that user i starts to be served. An up arrow indicates that user i leaves the system without have finished the service. A double up arrow ilustrates that the service of user i finishes. It is also shown the beginning and the end of the ith busy period, respectively, A i and E i . framework, a cluster corresponds to what is called a busy period, the intercluster size is an idle time and A i + D i is the length of the i-th cycle.

D 2 ǫ ǫ C 2 C 1 0 C n A 1 A 2 A 3 A n B 1 B 2 B n U 2 ∆X 1 ∆X 2 E 1 E n-1 E n E 2 ∆X NA 2 ∆X NE 1 ∆X 0 D 1 ∆A 2 ǫ ǫ ∆A 1 = U 1
The number of complete clusters in [0, L] corresponds to the number of connected components β 0 (L) (since in dimension 1, it coincides with the Euler characteristics of the union of intervals, see [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF]) of the network. The distance between the beginning of the first cluster and the beginning of the (i + 1)-th one is defined as U i = i k=1 ∆A k . We also define ∆X 0 = D 0 = X 1 . Figure 7.2 illustrates these definitions.

For the sake of completeness, we recall the essentials of Markov process theory needed to go along, for further details we refer for instance to [START_REF] Cooper | Introduction to queueing theory[END_REF] and [START_REF] Asmussen | Applied probability and queues[END_REF]. In what follows, for a process X, (F X t , t ≥ 0) is the filtration generated by the sample-paths of X:

F X t = σ{X(s), s ≥ t}.
Definition 7.1 A process (X(t), t ≥ 0) with values in a denumerable space E is said to be Markov whenever

E λ [F ] (X(t + s))F X t = E λ [F ] (X(t + s))X(t),
for any bounded function F from E to R, any t ≥ 0 and s ≥ 0.

Equivalently, a process X is Markov if and only if given the present (i.e. given X(t)), the past (i.e. the sample-path of X before time t) and the future (i.e. the sample-path of X after time t) of the process are independent. Definition 7.2 A random variable τ with values in R + ∪ {+∞} is an F X -stopping time whenever for any t ≥ 0, the event {τ ≤ t} belongs to F X t .

The point is that (7.1) still holds when t is replaced by a stopping time τ : Given X(τ ), the past and the future of X are independent. X is then said to be strong Markov. This property always holds for Markov processes with values in a denumerable space but is not necessarily true for Markov processes with values in an arbitrary space.

From now on, the Markov process under consideration is N , the Poisson process of intensity λ over [0, L]. Lemma 7.1 For any i ≥ 1, A i and E i are stopping times.

Proof: Let us consider the filtration F N t = σ{N a , a ≤ t}. For i = 1, we have

{A 1 ≤ t} ⇔ {X 1 ≤ t} ⇔ {N t ≥ 1} ∈ F N t .
Thus, A 1 is a stopping time. For A 2 , we have

{A 2 > t} ⇔ n≥1    N t = n, n j=1    ∆X j ≥ ǫ, n k=j+1 {∆X k ≤ ǫ}       ∈ F N t ,
so A 2 is also a stopping time. We proceed along the same line for others A i and as well for E i to prove that they are stopping times.

Since N is a (strong) Markov process, the next corollary is immediate.

Corollary 7.2

The set {B i , D i , i ≥ 1} is a set of independent random variables. Moreover, D i is distributed as an exponential random variable with mean 1/λ and the random variables {B i , i ≥ 1} are i.i.d.

Calculations

Throughout this section, we find first the Laplace transforms of B i , ∆A i , U i and the probability that there are n clusters in the interval. Then, we find the analytical expression of those quantities by inverting their Laplace transform.

Laplace transforms

We find first the Laplace transform of the distribution of B i , the size of a cluster. and E e -s∆X j 1 [∆X j >ǫ] = e -λǫ . By Corollary 7.2, since the B i 's are i.i.d, it suffices to calculate E e -sB 1 . Hence, the Laplace transform of the distribution of B i is given by

E e -sB i = ∞ n=1 E e -sB 1 , N E 1 = n = ∞ n=1 E   e -s( P n-1 j=1 ∆X j +ǫ) 1 [∆Xn>ǫ] n-1 j=1 1 [∆X j ≤ǫ]   = ∞ n=1 E e -s∆X 1 1 [∆X 1 ≤ǫ] n-1 E e -s∆Xn 1 [∆Xn>ǫ] e -sǫ = ∞ n=0 λ s + λ (1 -e -(s+λ)ǫ ) n e -sλ e -sǫ = 1 λ λ + s se λǫ λ e sǫ + 1 , (7.2)
which concludes the proof.

From this result, we can immediately calculate the Laplace transform of the distribution of ∆A i . Since ∆A i = B i + D i , we have E e -s∆A i = E e -s(B i +D i ) and using Corollary 7.2:

E e -s∆A i = E e -sB i E e -sD i = 1 se λǫ λ e sǫ + 1 • (7.3)
If we turn our attention to the system seen as a queue, as a remark, this last result can lead us to calculate the probability of the server is busy, or, equivalently, the loss probability, since the interarrival time is exponentially distributed. Due to the fact that A i and E i are stopping times, this probability is given by E

[B i ] /E [∆A i ],
which can be obtained by:

P(Server is busy) = E [B i ] E [∆A i ] = -d ds E e -sB i s=0 -d ds E [e -s∆A i ] s=0 = 1 -e -λǫ .
The Laplace transform of another r.v., U n , is found in the next corollary.

{β 0 ≥ n} ⇔ {∆X 0 + U n-1 + B n ≤ L} if n ≥ 1, {∆X 0 < ∞} if n = 0,
because the events in each side of the relation represent that there are more than β 0 clusters in the interval [0, L]. We can see this condition illustrated in Fig. 7.3 for n ≥ 1. For n = 0, the additional case, {∆X 0 ≥ ∞}, is trivial. Since {β 0 = n} and {β 0 ≥ n + 1} are disjoint events:

U n-1 0 L ∆X 0 D 1 D n B 1 B 2 B n B n+1
P(β 0 ≥ n) = P((β 0 ≥ n + 1) ∪ (β 0 = n)) = P(β 0 ≥ n + 1) + P(β 0 = n). 123
Thus

P(β 0 = 0) = 1 -P(∆X 0 + B 1 ≤ L), and
P(β 0 = n) = P(∆X 0 + U n-1 + B n ≤ L) -P(∆X 0 + U n + B n+1 ≤ L). (7.6) Let Y n ∆X 0 + U n-1 + B n if n ≥ 1 0 if n = 0 ,
the Laplace transform with respect to x, P(Y n ≤ x) can be calculated:

L{P(Y n ≤ •)}(s) = ∞ 0 P(Y n ≤ x)e -sx dx = ∞ 0 x 0 dP Yn (y)e -sx dx = ∞ 0 ∞ y e -sx dx dP Yn (y) = 1 s ∞ 0 e -sy dP Yn (y) = 1 s E e -sYn = 1 s E e -s∆X 0 E e -sU n-1 E e -sBn = 1 s 1 e λǫ λ se sǫ + 1 n (7.7)
for n ≥ 1, where we used Corollary 7.2 in the third line. For n = 0, the Laplace transform is trivial and given by L{P(y 0 ≤ •)}(s) = 1/s. Substituting Eq. (7.7) in the Laplace transform of both sides of Eq. (7.6) yields:

L{p n (•)}(s) = L{P(Y n ≤ •)}(s) -L{P(Y n+1 ≤ •)}(s) = e ǫλ λ e ǫs e ǫλ λ se ǫs + 1 n+1 , n ≥ 0.
The proof is thus complete.

Lemma 7.6 Let m be an positive integer. When

ǫ → 0, E [β m 0 ] → E [N m L ].
Proof: Since lim x→0 P(∆X i < x) = 0, for almost all N , for any non-negative integer j, if X j ≥ η, there exists η such that ∆X j ≥ η. If ǫ < η, then β 0 (ǫ) a.s.

= N L . Besides, since β 0 ≤ N L , it is well known that all the m-th moments of a random variable distributed as Poisson converge. This means that, for any positive integer m, E [β m 0 ] also exists and that when

ǫ → 0, E [β m 0 ] = E [N m L ]. Let Li t (z), z, t ∈ R, z < 1, be the polylogarithm function with parameter t, defined by Li t (z) ∞ k=1 z k k t • For m a positive integer, consider the function of x M m β 0 x → E [β m 0 (x)] = ∞ i=0 i m p i (x) (7.8)
and its Laplace transform given by:

L M m β 0 (•) (s) = ∞ 0 + E [β 0 (x) m ] e -sL p n (x)dx.
Corollary 7.7 Let a be defined as follows: a e ǫλ λ se ǫs .

The Laplace transform of the m-th moment of β 0 (L) is:

L M m β 0 (•) (s) = a s (a + 1) Li -m 1 a + 1 , (7.9)
which converges, provided that 1 a+1 < 1. Proof: Applying the Laplace transform of both sides of Eq. (7.8) and using its linearity:

L M m β 0 (•) (s) = L ∞ i=1 i m p i (•) (s) = ∞ i=1 (i m L{p i (•)}(s)), (7.10)
where we can interchange the sum and the Laplace transform due to Lemma 7.6. Thus, it is possible to find the Laplace transform of E [β 0 (L) m ]: Li -m 1 a + 1 , concluding the proof.

L M m β 0 (•) (s) = ∞ i=1 (i m L{p i (•)}(s))

Analytical expressions

Until this point, we have all the results we are interested in, but in a Laplace transform form. In this section, we find a way to inverse every one of those transforms. We start finding the moments of β 0 and we define m k as the Stirling number of the second kind [START_REF] Graham | Concrete Mathematics: A Foudation for Computer Science[END_REF].

Corollary 7.8 The m-th moment of the number of clusters on the interval [0, L] is given by: .11) Proof: Using the following identity [START_REF] Wood | [END_REF] valid for a positive integer m

M m β 0 (L) = m k=1 m k L ǫ -k k λǫe -ǫλ k 1 [L/ǫ>k] . ( 7
Li -m (z) = m k=0 (-1) m+k k! m + 1 k + 1 (1 -z) k+1 ,
in the result of Corollary 7.7, we find that

L M m β 0 (•) (s) = a s m k=0 (-1) m+k k! m + 1 k + 1 (1 + a) k a k+1 (a + 1) = 1 s m k=0 c k,m 1 a k ,
where the coeficients c k,m are integers given by:

c k,m = m j=k (-1) j j! m + 1 j + 1 j k .
Using the following identity of Stirling numbers [START_REF] Roman | The Umbral of Calculus[END_REF],

m j=0 (-1) j j! m + 1 j + 1 = 0,
we find that c 0,m = 0 for m a positive integer. So we can write the Laplace transform of the moments as

L M m β 0 (•) (s) = m k=1 c k,m λe -ǫλ k s k+1 e ksǫ (7.12)
and apply the inverse of the Laplace transform in both size of Eq. (7.12) to obtain:

M m β 0 (L) = L -1 m k=1 c k,m λe -ǫλ k s k+1 e ksǫ (L) = m k=1 c k,m λe -ǫλ k L -1 1 s k+1 e ksǫ (L) = m k=1 c k,m k! (L -kǫ) k λe -ǫλ k 1 [L>kǫ] (7.13)
According to Lemma 7.6, when ǫ → 0, we obtain

M m β 0 (L) = E [N m L ] = m k=1 c k,m k! (Lλ) k 1 [L>0] .
Hence, for any λ > 0,

m k=1 c k,m k! (Lλ) k 1 [L>0] = m k=1 m k (Lλ) k 1 [L>0] ,
which shows that

c k,m = m k k! .
Thus, we have proved (7.11) for any positive integer m.

Once we have an expression of the moments, we can find the Laplace transform of the distribution of β 0 . Theorem 7.9 The expression of P(β 0 = n) with respect of n, L, λ and ǫ is given by:

P(β 0 = n) = 1 n! ⌊L/ǫ⌋-n i=0 (-1) i i! ((L -(n + i)ǫ)λe -λǫ ) n+i . ( 7

.14)

Proof: With the expression of the moments of β 0 found in Corollary 7.8, we can find the Laplace transform of its distribution, given by

E e -sβ 0 = 1 -sE [β 0 ] + s 2 2! E β 2 0 - s 3 3! E β 3 0 + ...
Rearranging the terms of the right-side hand and substituting M m β 0 (L) by the result of Eq. (7.11), we obtain:

E e -sβ 0 = ∞ k=0   (L -kǫ) k λe -λǫ k 1 [L>kǫ] ∞ j=k (-s) j j! j k   •
But we can simplify this expression, since [START_REF] Roman | The Umbral of Calculus[END_REF] gives

∞ j=k x j j! j k = 1 k! (e x -1) k , (7.15)
and we have

E e -sβ 0 = ∞ k=0 (L -kǫ) k λe -λǫ k 1 [L>kǫ] (e -s -1) k k! •
We can then apply the inverse of Laplace to find the distribution of β 0 :

∞ k=0 ∞ i=k (-1) i i! i n δ(k -n)(kǫ -L) k λe -λǫ k 1 [L>kǫ] .
After some simple algebra, we find the expression of the probability of an interval containing n complete clusters:

P(β 0 = n) = 1 n! ⌊L/ǫ⌋-n i=0 (-1) i i! ([L -(n + i)ǫ]λe -λǫ ) n+i , concluding the proof.
With the explicit expression of P(β(x) = n) = p n (x), we can show a simple lemma.

Lemma 7.10 For x ≥ 0, p n (x) has the three following properties:

i) p n (x) is derivable; ii) lim x→∞ p n (x) = 0; iii) lim x→∞ dpn(x) dx = 0.
Proof: Let j be a non-negative integer. The function is obviously derivable when x/ǫ = j. Besides, we have

lim x→ǫj + p n (x) -lim x→ǫj - p n (x) = lim x→ǫj + (-1) j j! (x -(n + j)ǫ) 1 a n+j •
Since the right-hand term function of x is zero as well as its derivative for all j, the function is also derivable when x/ǫ = j, which proves i). Using the Final Value theorem in the Laplace transform of p n (x) and its derivative, we show items ii) and iii). The expression of p n (x) gives us, indeed, a transform Laplace pair between the x and s domains:

1 [x≥0]
n! = λe -ǫλ e -ǫs L {p 0 (•)} (s) + e -ǫλ e -ǫs sL {p 0 (•)} (s).

Here, using the inverse Laplace transform established in Eq. (7.16) and remembering that p 0 (x -) = 0, we get an analytical expression for f B i (x), proving Eq. (7.17 Inverting this Laplace transform we prove Eq. (7.18).

Number of incomplete clusters

The major difference with Sec. 7.3 is that a cluster is counted as soon as one of the point of the cluster is inside the interval [0, L]. So, for instance, in Fig. 7.3, we count actually n + 1 incomplete clusters. We define β ′ 0 as the number of incomplete clusters on an interval [0, L]. Proof: The condition of β ′ 0 ≥ n is slightly changed:

{β ′ 0 ≥ n} ⇔ {∆X 0 + U n-1 ≤ L} if n ≥ 1, {∆X 0 < ∞} if n = 0.
We define Y n as

Y n ∆X 0 + U n-1 if n ≥ 1 0 if n = 0.
Repeating the same calculations, we find the Laplace transform of P(β ′ 0 (L) = n): With this expression, following the lines of Lemma 7.6, we obtain:

L{P(β ′ 0 (•) = n)}(s) =          λ s + λ
L E β ′ 0 (•) m (s) = m+1 k=1 m + 1 k (k -1)! 1 s k λ λ + s λe -λǫ e sǫ k-1
.

Then, we write:

λ λ + s 1 s k = (-1) k λ k-1 1 λ + s + k i=1 1 s i -1 λ k-i
, to find an expression with a well known Laplace transform inverse, and after inverting it, we obtain: Inverting this expression for an non-negative integer n, we have the searched distribution.

E β ′m 0 = m k=0 m + 1 k + 1 k!G(k). ( 7

Number of clusters in a circle

We investigate now the case where the points of the process are deployed over a circumference and we want to count the number of complete clusters, which corresponds to calculate the Euler Characteristic of the total coverage, so we call this quantity χ. Due to the symmetry of the circumference , we can choose an arbitrary point to be the origin. If it is given that there is at least one point on it, we can choose the origin to be at some point of the process. Theorem 7.14 The distribution of the Euler Characteristic, χ, when the points are deployed over a cirumference of length L is given by

P(χ = n) = e -λL 1 [n=0] + (1 -e -λL ) λe -ǫλ n! ⌊L/ǫ⌋-n i=0 (-1) i i! ([L -(n + i)ǫ]λe -ǫλ ) n+i-1 L + (n + i) 1 λ -ǫ , (7.24)
for n ≥ 0.

Proof: It is possible to establish a relation between the case in the line and the case in the circle. If there are no points in the circle, of course χ = 0. Otherwise, if there is at least one point, we choose the origin at this point and we have the equivalence between the events:

{χ ≥ n} ⇔ {U n-1 + B n ≤ L} ∩ {N L > 0} if n ≥ 1, {∆X 0 < ∞} if n = 0. B n L D 1 D n B 1 B 2 B n B n+1 U n-1 0 N L B 1 D n D 1 0 N L ǫ U n-1 B 2
L + k 1 λ -ǫ 1 [L>kǫ] .
Expanding the Laplace transform in a Taylor serie and rearranging terms, as we did previously, yields we can directly invert this Laplace transform, add the case where there are no points for χ = 0, and the theorem is proved.

Examples

We consider some examples to illustrate the results of the paper. Here, the behavior of the mean and the variance of β 0 as well as P r(β 0 = n) are presented.

From Eq. (7.11), we have that E [β 0 ] is given by:

E [β 0 ] = (L -ǫ)λe -ǫλ 1 [L>ǫ] .
This expression agrees with the intuition that there are three typical regions given a fixed ǫ. When λ is much smaller than 1/ǫ, the number of clusters is approximatively the number of sensors, since the connections with few sensors will unlikely happen, which can be seen from the fact that β 0 → Lλ when λ → 0. As we increase λ, the mean number of direct connections overcomes the mean number of sensors and, at some value of λ, we expect that β 0 decreases, when adding a point is likely to connect disconnected clusters. We remark that the maximum occurs exactely for ǫ = 1/λ, i.e., when the mean distance between two sensors equals the threshold distance for them to be connected. In this maximum, β 0 takes the value of (L/ǫ-1)e -1 . Finally, when λ is too large, all sensors tend to be connected and there is only one cluster which even goes boyond L, so there are no complete clusters into the interval [0, L]. This is trivial when we make λ → ∞ in the last equation. and under the condition that L > 2ǫ:

Var(β 0 ) = (Lǫ)λe -ǫλ + ǫ(3ǫ -2L)λ 2 e -2ǫλ . when λ is small compared to ǫ, the plot should be approximatively linear, since there would not be too much connections in the network and the variance of the number of clusters should be close to the variance of the number of sensors given by λL. Since β 0 tends almost surely to 0 when λ goes to infinity, Var(β 0 ) should also tend to 0 in this case. Those two properties are observed in the plot. Besides, we find the critical points of this function, and again, λ = 1/ǫ is one of them and at this value Var(β 0 ) = (L/ǫ)e -1 + (3 -2L/ǫ)e -1 . The other two are the ones satisfiy the transcendant equation:

λe -λǫ = Lǫ 2ǫ(2L -3ǫ)

• By using the second derivative, we realize that 1/ǫ is actually a minimum. Besides, if L ≤ 2ǫ, there is just one critical point, a maximum, at λ = 1/ǫ. The last example in the section is performed with the result obtained in Theorem 7.9. We consider again L = 4 and ǫ = 1 to obtain the following distributions: P(χ = 0) = 1 -3λe -λ + 2λ 2 e -2λ -1/6λ 3 e -3λ , P(χ = 1) = 3λe -λ -4λ 2 e -2λ + 1/2λ 3 e -3λ , P(χ = 2) = 2λ 2 e -2λ -1/2λ 3 e -3λ , P(χ = 3) = 1/6λ 3 e -3λ , P(χ > 3) = 0.

Those expressions are simple and they have at most four terms, since L = 4ǫ. We plot these functions in Fig. 7.7. The critical points on those plots at λ = 1/ǫ are confirmed for the fact that, as a function of λ, for every n, P(χ = n) can be represented as a sum j i=0 q i,j (λe -λǫ ) i where the coeficients q i,j are constant in relation to λ. However, (λe -λǫ ) i has a critical point at λ = 1/ǫ for all i > 0, so this should be also a critical point of P(χ = n). If λ is small, we should expect that P(χ = 0) is close to one, since it is likely to N have no points. For this reason, in this region, P(χ = n) for n > 0 is small. When λ is large, we expect to have very large clusters, likely to be larger than L, so it is unlikely to have a complete cluster in the interval and, again, P(χ = 0) approaches to the unity, while P(χ = n) for n > 0 become again small.

Summary

In this chapter, we have obtained expressions that model a random sensor network in a line. We have evaluated both the analytical expression and its Laplace transform of the following quantities: the length of a cluster, the length of a sequence of consecutive clusters, the distribution of the number of complete clusters, incomplete clusters and clusters on a circumference, all the moments of those distributions and the probability of complete coverage. The analytical solutions are simple since they involve only polynomial and exponential functions; they are exact; and they take into account a large number of realistic variables such as density of the network, lifetime of the sensors, power transmission and reception sensitivity, all of this with a random deployment of sensors. Moreover, these calculations solve also the queueing problem of the busy period of an M/D/∞ and find many parameters of a M/G/1/1 when the service time is distributed as c.

Chapter 8

Concluding Discussion and Future Works

In this thesis, we explored tools of stochastic analysis and algebraic topology applied to sensor networks. We considered the usual modeling of the positions in a network as a Poisson point process. Furthermore, we used stochastic analysis under the Poisson measures to characterize random variables as the sum of stochastic integrals and we applied the gradient operator D, as well as the Ornstein-Uhlenbeck generator L and its inverse. As regards algebraic topology, we took advantage of the fact that the topology of a sensor network coverage is the same as that of its simplicial complex.

Stochastic analysis enabled us to find upper bound probabilities for various situations, and we presented two of them throughout the thesis: the probability of opportunist users in a cognitive system to damage licensed users and the probability for losing a user in an OFDMA system because all subcarriers of the central station are already in use. In both cases, the results can be used to design a system, since they are function of parameters that can be found or controlled by the operator.

In the first case we consider the power constraint to be respected in order to avoid outages of the licensed users. Then we found the maximum power allowed to opportunist users in a WiMax network such that this the mean interference caused by them respects this constraint. Then, we found out that the power allowed to these secondary users in order to have low outage probabilities for primary ones is not much weaker than the averaged one. So, for instance, the operator can control capacity of secondary users according to the outage probability, or the opposite, the intensity of users can be controlled in a region to ensure that users (primary and secondary ones) have a minimum QoS in their communication. It is worth mentioning that the secondary users capacity is improved and damage to primary ones is lessened when their intensity and bandwidth are increased, which is a tendency of the next generation wireless networks.

In the second application, we found a relationship between the probability of overloading the system, the density of active users and the number of available subchannels, thus providing a large number of possibilities to design OFDMA systems. We also compare the numerical results with simulations and note that the calculated number of subchannels leads to an overload probability overestimated by about 20% of the simulated one. The margin provided by the bounds may be viewed as a protection against errors in the modeling or in the estimations of parameters. We should remark that, in both cases, we found new analytical results for the very complex mathematical problems.

Conclusion

The most important results from algebraic topology came from the interpretation of a sensor network as a simplicial complex, which enables us to compute the Betti numbers of the coverage of a sensor network. We showed that Betti numbers do not allow us to determine if a region is completely covered, but we solved this problem if points lay on a torus. In this case, the Euler characteristic also can provide valuable information on coverage: if this quantity equals zero, probably the network is covered. We obtained statistics on the number of k-simplices, such as its mean, variance, covariance and third moment, and we provided a method to calculate the n-th moment. The results already show some tendencies for the network, for instance if a network has a number of 1-simplices much larger than the number of points, then probably this network is connected. We can think about similar intuitive interpretations, but these statistics lead to more interesting results: we can use them to determinate the mean and variance of the Euler characteristic and to find bounds for the distribution of connectivity. We also proved that the distribution of the number of k-simplices converges to a Gaussian distribution when the intensity of points λ tends to infinity, with a convergence rate of O(1/ √ λ). If we combine this convergence with the statistics of first and second order, we have a good approximation for the distribution of the number of k-simplices. With this result, a random Gaussian vector can represent the joint distribution of the number of different simplices, since we have the correlation between the number of any k-simplices and l-simplices.

In Chapter 7 we did not use a particular new method, but classical ones to solve the M/M/1/1 preemptive queue which was not solved in the literature. This result corresponds to the solution of the major problem of the thesis in one dimension: the arrival time corresponds to the beginning of a cluster of sensors, the busy period corresponds to the size of a cluster and the number of served users after a certain time corresponds to the number of clusters in a line segment. We found all relevant parameters and we believe that this example can give insights to cases in two or more dimensions.

The most important contribution of the thesis is to apply simultaneously results from algebraic topology and from stochastic analysis on sensor networks. Although tools of Malliavin calculus were more often used, topology has played a fundamental role since the random variables and their relations came from concepts of topology. One of the main purposes of this thesis was the use of modern mathematical tools in networks, which was fulfilled. By using these tools, we could obtain results for problems with very hard analytical treatment where classical tools have failed to solve. We remark that it was also important to present concrete and applicable results in each chapter.

Future Works

Although the use of topology has been essential to the work, we used but a superficial layer of it. There are a lot of works in this domain and we believe that they soon will be used in random networks (see, for instance [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF][START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF][START_REF] Muhammad | Control using higher order laplacians in network topologies[END_REF]), especially the works of persistent homology. We remember that we were not able to find relevant results for the Betti numbers: we know how to compute them, but not how to treat them statistically. A particularly intriguing question would be to find a closed-form expression for the Euler characteristic (instead of the infinite power series representing it) in two dimensions, at least. With respect to the deployment of the points, there are various different point processes that could be used to represent the behavior of users, ranging from the randomness of the density of user (as in a Cox process) to processes where the position of each user depends on the position of other users (as in determinantal processes).

List of Figures

se λǫ λ e sǫ + 1 ;• 1 se λǫ λ e sǫ + 1 ;•e ǫλ λ e ǫs e ǫλ λ se ǫs + 1 n+1•

 1111 La distance ∆A i entre les deux premiers points de deux clusters consécutifs C i et C i+1 : E e -s∆A i = E e -sB i E e -sD i = La distance entre le début du premier cluster et le début du (i + 1)-ème cluster E e -sUn = 1 e λǫ λ se sǫ + 1 n ; Maintenant, nous définissons p n (L) = P(β 0 = x), ce qui signifie que, p n (L) est la probabilité de l'existence d'exactement n cluster dans l'intervalle [0, L]. Compte tenu que pour tout L ∈ R + , 0 ≤ p n (L) ≤ 1, la transformée de Laplace par rapport à L L{p n (•)}(s) = ∞ 0 e -st p n (t)dt, est bien définie, nous pouvons la calculer en utilisant l'expression de E e -sUn : L{p n (•)}(s) = Nous avons aussi trouvé la transformée de Laplace du m-ème moment de β 0 , M m β 0 (L), qui sera utilisée pour trouver la transformée inverse de L{p n (•)}(s) :

Figure 1 . 1 :

 11 Figure 1.1: The black circles represent the positions of the sensors. The coverage radius ǫ in function of P s under the effect of path loss only. Sensors cannot send data to their sensors further than ǫ.

Figure 1 . 2 :

 12 Figure 1.2: In both figures, the black circles represent the positions of the sensors. a) A choice of a coverage radius ǫ 1 may not capture an undesirable event; b) A choice of a smaller radius ǫ 2 increases the probability of capturing the event

Figure 1 . 3 :∪ y) = 1 Dy β 0 = - 1 +yFigure 1 . 4 :

 131114 Figure 1.3: Topological interpretations of sensor networks. Each node v i represents a sensor S i . We can see that the topology of the coverage is the same as for the simplicial complex

Figure 3 . 1 :

 31 Figure 3.1: Example of a configuration with primary users, secondary users (transmitters and receivers) and interferers.

Figure 3 . 2 :

 32 Figure 3.2: Mean SU Per-link Capacity (Kbps) as a function of the path loss exponent (α) for the Ideal case with a secondary user's intensity λ 2 equal to 3 users per m 2 .

Figure 3 .Figure 3 . 3 :

 333 Figure 3.3: Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the ideal IT model with B = 528 MHz for the cases α=3 and α=4.

Figure 3 . 4 :Figure 3 . 5 :

 3435 Figure 3.4: Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the generalized IT model with B = 585 MHz for the case α = 3

Figure 3 . 6 :

 36 Figure 3.6: Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the ideal and generalized IT models with B = 585 MHz for the case α = 3.

  link Capacity Generalized case for = 4 and B = 585MHz Mean SU Per link Capacity Ideal case for = 4 and B = 585MHz

Figure 3 . 7 :

 37 Figure 3.7: Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the ideal and generalized IT models with B = 585 MHz for the case α = 4.

3 Figure 3 . 8 : 4 Figure 3 . 9 : 3 Figure 3 . 10 :

 3384393310 Figure 3.8: Fraction of the transmission power (η) as a function of the outage probability of the PUs (q) for the ideal case with α = 3.

4 Figure 3 . 11 :

 4311 Figure 3.11: Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for different values of the PUs outage probability following the ideal IT model with B = 528 MHz for the case α = 4.

Figure 4 . 1 :

 41 Figure 4.1: OFDMA sub-carrier allocation principle

Figure 4 . 2 :

 42 Figure 4.2: OFDMA sub-channel principle

Theorem 4 . 3 1 {

 431 For any function θ : R → R,θ(N (x, y))p S (y) dy dλ(x) = Nmax-1 j=1 θ(j)(A j -A j-1 ) + θ(N max )(πR 2 -A Nmax-1 ).Proof: Since N can take only a finite number of values, we have θ(N (x, y))p S (y) dy dλ(x) (x, y), N (x, y)=j} p S (y) dy dx.

Theorem 4 . 5 )(πR 2 -

 452 For any function θ : R → R, θ(N (x, j y))p S (y) dy dλ(x) = )(A l -A l-1 ) + θ(N max j

  α

Figure 5 . 2 :

 52 Figure 5.2: A chain complex showing the sets C k , Z k and B k .

Lemma 5 . 2

 52 For the torus T d a equipped with the product distance d ∞ , R ǫ (ω) has the homotopy type of the Cech complex C 2ǫ (ω)

  [a] andC ǫτ (τ * ω) τ * ω∈T d [ak]are the same for any k if λ τ = λ/k d and ǫ τ = kǫ.

Figure 6 . 1 :

 61 Figure 6.1: a) Sensors and their coverage; b) simplicial complex representation when sensors are monitoring the region; c) simplicial complex representation when sensors are communicating among them.

2 aFigure 6 . 2 :

 262 Figure 6.2: Illustration of the coverage of a point and the region where points can lie, in the 2 dimensional case

Figure 6

 6 Figure 6.4: a) Region R 3 b) Limit of the region R 3

Domination regions of β k when d = 5 in function of λ Dominating β k β 0 β 0 and β 1 β 1 β 2 β 3 β 4 β 1 and β 2 β 2 and β 3 β 3 and β 4 - 12 Figure 6 . 5 :

 12342341265 Figure 6.5: Behavior of χ related to the regions of dominance of β i . There are at most two dominating Betti numbers

1 Figure 6 . 6 :

 166 Figure 6.6: Example of relative positions of the points

Definition 6 . 2

 62 Let C 1 , C 2 and C 3 be three simplices with common vertices. For L ∈ P({1, 2, 3}), let us denote m L the number of vertices belonging exactly to the list L of simplices.

Definition 6 . 4

 64 Let C 1 , • • • , C n be n simplices with some common vertices. For L ∈ P({1, • • • , n}), let us denote m L the number of vertices belonging exactly to the list L of simplices.

Figure 7 . 2 :

 72 Figure 7.2: Definitions of the relevant quantities of the network: distance between points, distance between clusters, the size of clusters, the size interclusters, the beginning of clusters and the end of clusters.

Corollary 7 . 3 λ λ + s se λǫ λ e sǫ + 1 • ( 7 . 1 ) 0 e

 731710 The Laplace transform of the distribution of B i , is given by E e -sB i = 1Proof: Since ∆X j is an exponentially distributed random variable,E e -s∆X j 1 [∆X j ≤ǫ] = ǫ -st λe -λt dt = λ s + λ 1e -(s+λ)ǫ

Corollary 7 . 4 E 1 e λǫ λ se sǫ + 1 ne ǫλ λ e ǫs e ǫλ λ se ǫs + 1 n+1 • ( 7 . 5 )

 7411175 The Laplace transform of the distribution of U n , for n ≥ 0 is given by E e -sUn = 1 e λǫ λ se sǫ + 1 n • (7.4) Proof: We use Corollaries 7.2 and 7.3 to calculate the Laplace transform of the distribution of U n , since Un = n i=1 (B i + D i ):E e -sUn = E e -sUn = E e -s(P i=n i=1 (B i +D i )) e -sB i E e -sD i = ,for n ≥ 0.Let us define p n (L) P(β 0 = x), i.e., p n (L) is the probability of having n clusters on the interval [0, L]. Since for all L ∈ R + , 0 ≤ p n (L) ≤ 1, the Laplace transform with respect to L,L{p n (•)}(s) = ∞ 0 e -st p n (t)dt,is well defined, and we are able to compute it with the expression of E e -sUn : Theorem 7.5 For n ≥ 0, the Laplace transform of the function p n (L) is given by L{p n (•)}(s) = Proof: Let β 0 = β 0 (L) be the number of complete clusters on [0, L]. To calculate the probability of {β 0 (L) = n}, we have to note that

Figure 7 . 3 :

 73 Figure 7.3: Illustration of the condition equivalent to β 0 ≥ n.

) andf 1 = λe -ǫλ e ǫλ λ e ǫs e ǫλ λ se ǫs + 1 e

 11 Un (x) = λe -ǫλ p n-1 (xǫ)1 [x>ǫ] ,(7.18)where the expressions of p 0 (xǫ) and d dx p 0 (xǫ) are straightforwardly obtained from Eq. (7.14).Proof: According to Corollary 7.3:E e -sB i = 1 λ (λ + s)e λǫ λ se sǫ + -ǫs + e -ǫλ s e ǫλ λ e ǫs e ǫλ λ se ǫs + 1 e -ǫs

1 e λǫ λ se sǫ + 1 n= λe -ǫλ e ǫλ λ e ǫs e ǫλ λ se ǫs + 1 n

 111 ). Proceeding in a similar fashion, we can find the distribution of U n by inverting its Laplace transform given by Corollary 7.4: E e -sUn = e -ǫs = λe -ǫλ e -ǫs L {p n-1 (•)} (s).

Theorem 7 .

 7 [START_REF] Bell | Exponential polynomials[END_REF] Let G(k) be defined asG(k) = (-1) k   e -kλǫ k j=0 [λ(kǫ -L)] j j! e -λL   1 [T >kǫ]for k ∈ N + and G(-1) = e -λL . ThenP(β ′ 0 = n) = ⌊L/ǫ⌋+1 i=n (-1) i+n i n (G(i -1) + G(i)), for n ≥ 0. (7.20)

. 22 )= 1

 221 Expanding the Laplace transform of the distribution of β ′ 0 in a Taylor serie and rearranging terms, we get E e -sβ ′ 0 use the recurrence that Stirling numbers obey[START_REF] Roman | The Umbral of Calculus[END_REF], k -1) + G(k))(e -s -1) k .

Figure 7 . 4 :

 74 Figure 7.4: Illustration of the condition equivalent to χ ≥ n. Since the coverage of the last point on [0, L] overlaps the cluster with a point in zero, they are actually contained in the same cluster

E

  e -sχ = (1e -λL )λe -ǫλ ∞ k=0 [Lkǫ]λe -ǫλ k-1

Figure 7 . 5 E[β 0 ] in function of λ 0 Figure 7 . 5 : 1 .

 750751 Figure 7.5: Variation of the mean number of clusters as a function of λ when L = 4 and ǫ = 1.The variance can be obtained also by Eq.(7.11):Var(β 0 ) = (Lǫ)λe -ǫλ 1 [L>ǫ] + (L -2ǫ)λ 2 e -2ǫλ 1 [L>2ǫ] -(Lǫ) 2 λ 2 e -2ǫλ 1 [L>ǫ] ,

Fig. 7 .Figure 7 . 6 :

 776 Fig. 7.6 shows a plot of Var(β 0 ) as function of λ for L = 4 and ǫ = 1. We can expect that, Var(β 0 )

Figure 7 . 7 :

 77 Figure 7.7: Probabilities of connectivity, P(β 0 = n), for n = 0, 1, 2, 3, as a function of λ when L = 4 and ǫ = 1.

1. 1

 1 The black circles represent the positions of the sensors. The coverage radius ǫ in function of P s under the effect of path loss only. Sensors cannot send data to their sensors further than ǫ. . . . . . . . . . . . . . . . . . . . . . . . 1.2 In both figures, the black circles represent the positions of the sensors. a) A choice of a coverage radius ǫ 1 may not capture an undesirable event; b) A choice of a smaller radius ǫ 2 increases the probability of capturing the event 1.3 Topological interpretations of sensor networks. Each node v i represents a sensor S i . We can see that the topology of the coverage is the same as for the simplicial complex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Gradient operator D y in a Poisson process ω. . . . . . . . . . . . . . . . . . 3.1 Example of a configuration with primary users, secondary users (transmitters and receivers) and interferers. . . . . . . . . . . . . . . . . . . . . . . . 3.2 Mean SU Per-link Capacity (Kbps) as a function of the path loss exponent (α) for the Ideal case with a secondary user's intensity λ 2 equal to 3 users per m 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the ideal IT model with B = 528 MHz for the cases α=3 and α=4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the generalized IT model with B = 585 MHz for the case α = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the generalized IT model with B = 585 MHz for the case α = 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the ideal and generalized IT models with B = 585 MHz for the case α = 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for the ideal and generalized IT models with B = 585 MHz for the case α = 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Fraction of the transmission power (η) as a function of the outage probability of the PUs (q) for the ideal case with α = 3. . . . . . . . . . . . . . . . . . . 3.9 Fraction of the transmission power (η) as a function of the outage probability of the PUs (q) for the ideal case with α = 4. . . . . . . . . . . . . . . . . . . 3.10 Mean SU Per-link Capacity (Kbps) as a function of the secondary users' intensity (λ 2 ) for different values of the PUs outage probability following the ideal IT model with B = 528 MHz for the case α = 3. . . . . . . . . . .

  Overview of the Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Mathematical Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Algebraic topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Poisson point processes . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Thesis Outline and Contributions . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Multi class user traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Upper bound of loss probability . . . . . . . . . . . . . . . . . . . . . 4.5.2 Numerical application . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.3 Applications to sensor networks . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Moments of k-Simplices and Euler Characteristic 87 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2 First Moment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.3 Second order moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.4 N th order moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.5 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 7.3 Calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7.3.1 Laplace transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7.3.2 Analytical expressions . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7.4 Other Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.4.1 Number of incomplete clusters . . . . . . . . . . . . . . . . . . . .

	1 Introduction 1.1 Motivation: sensor networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Topology of random geometric networks . . . . . . . . . . . . . . . . . . . . 1.3 I Stochastic Geometry 2 Stochastic Model 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Poisson point process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Interference Temperature Model in Cognitive Radio Networks 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Physical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Secondary User Mean Capacity . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Calculations of the mean capacity . . . . . . . . . . . . . . . . . . . 3.3.2 Numerical Analysis for the Mean Capacity of the Secondary Network 3.4 Upper bound of PU Outage Probability . . . . . . . . . . . . . . . . . . . . 3.4.1 Calculations: Upper bound of PU Outage Probability . . . . . . . . 3.4.2 Results: Upper bound of PU Outage Probability . . . . . . . . . . . 3.5 4 Upper bound of loss probability of an OFDMA system 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Introduction to OFDMA air interfaces . . . . . . . . . . . . . . . . . . . . . 4.3 Upper Bound under a Deterministic Gain . . . . . . . . . . . . . . . . . . . 4.4 Upper Bound under a Random Gain . . . . . . . . . . . . . . . . . . . . . . Algebraic Topology 7.1 . 129 79 81 7.4.2 Number of clusters in a circle . . . . . . . . . . . . . . . . . . . . . . 130 7.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Conclusion 134 Concluding Discussion and Future Works 135 8.1 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Bibliographie 146 4.5 II Algebraic Topology with random Simplicial complexes 117 Chapter 1 Introduction 5.1 One-dimensional Case 1.1 Motivation: sensor networks

Table 4 .

 4 1: Comparison between P sup and P loss for deterministic gain.

		5 1.6 1.7	1.8	1.9	2
	P sup 0.18 0.1 0.04 0.02 0.008 0.003
	∆	0.98 1.1 1.15 1.3	1.3	1.4

Table 4 .

 4 The proof is thus complete. We used the same set of values as for the simulation of Section 4.3 together with assumptions 8 and 7 with β min = 0.2. Results of Table4.2 show that the theoretical bound is rather stable when gains become stochastic.

	α	1.5 1.6 1.7	1.8	1.9	2
	P sup 0.2 0.1 0.05 0.02 0.01 0.004
	∆	1.7 1.8 2.1	2.3	2.4	2.6

2: Comparison between P sup and P loss for random gain.

Table 4 .

 4

		1.6	1.65	1.7	1.75	1.8
	P sup	0.0445 0.0286 0.0180 0.0111 0.0068
	N 0sup	45.2	46.7	48	49.5	50.9
	N 0 sim	38	39	40.4	41.6	42.8

3: Difference in terms of sub-channels obtained by simulation and analytically.

  .11)6. Moments of k-Simplices and Euler CharacteristicLemma 6.[START_REF] Daley | An introduction to the theory of point processes[END_REF] The random variable G Γ has a chaos representation given by:

  We can use this relation to find the distributions of B i and U n .Theorem 7.11 The distributions of B i and U n , respectively f B i (x) and f Un (x) are f B

	⌊x/ǫ⌋-n i=0	(-1) i i!	(x -(n + i)ǫ)	1 a	n+i	L ⇔	ae ǫs (ase ǫs + 1) n+1 .	(7.16)

i (x) = λe -ǫλ p 0 (xǫ) + e -ǫλ d dx p 0 (xǫ) 1 [x>ǫ] ,

Interference Temperature Model in Cognitive Radio Networks

Acknoledgements

We can also obtain the probability that the segment [0, L] is completely covered by the sensors. To do this, we remember that the first point (if there is one) is capable to cover the interval [X 1ǫ, X 1 + ǫ]. This motivates the Theorem 7.12. Theorem 7.12 Let R m,n (x) be defined as follows:

Then,

Proof: The condition of total coverage is the same as

which means that:

Hence,

and since B 1 and X 1 are independent:

From this point we use Lemma 7.10 to solve some analytical integrals and to do some algebra to obtain Eq. (7.19). Hence, we have explicit expressions, which are quite simple, to represent the distributions of β 0 , B i , U n and the probability of total coverage as a function of L, ǫ, λ 0 , µ and t (we remember that λ = λ 0 Le -t/µ ), so the problem of a random sensor network in one dimension is completely solved.

Other Scenarios

Although we consider the problem of finding the number of complete clusters until this point of the paper, the method can be used to calculate p n to other definitions for the number of clusters. In this We consider particularly two other definitions: the number of incomplete clusters and the number of clusters in a circle.

LIST OF FIGURES