Algebraic topology of random simplicial complexes and applications to sensor networks
Topologie algébrique de complexes simpliciaux aléatoires et applications aux réseaux de capteurs
Résumé
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 I I, 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 Point 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.
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 traffic 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 dimen- sions. 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.
Origine : Version validée par le jury (STAR)
Loading...