Large Wireless Sensor Networks : Some Contributions to Modeling and Algorithms
Institution:
Paris 13Disciplines:
Directors:
Abstract EN:
Le concept des réseaux de capteurs sans fil , issu de la fusion des progrès en radiocommunication et en micro-électronique est apparu assez récemment et offre un nouveau paradigme pour la définition de l’intelligence ambiante. Les réseaux de capteurs sont constitués d’un ensemble de noeuds qui sont déployés en grand nombre et qui interagissent avec l’environnement (mesure ou action sur des paramètres), dont le large spectre applicatif s’étend de la surveillance environnementale à la détection de vie sur d’autres planètes. Cependant, la conception de tels réseaux de grande taille se heurte à un certain nombre de difficultés techniques provenant des contraintes imposés par les capacités réduites des capteurs (individuels): basse puissance, énergie limité, capacité de stockage et communication réduite. Cette thèse est consacrée d’abord aux problèmes de modélisation des réseaux de capteurs sans fil. A savoir, comment trouver un modèle de communication réaliste. Un réseau de communication se modélise par un graphe. Le cadre de réseaux de capteurs sans fil ne va pas déroger à la règle et les capteurs, les noeuds de communication seront modélisés par les sommets du graphe tandis que les arêtes représenteront les liens physiques de communication entre ces éléments communicants. La notion de graphe est importante car un grand nombre de paramètres employés en théorie des graphes permettent de quantifier des propriétés physique, topologiques ou des performances des réseaux modélisés. Toutefois, dans l’avenir les applications impliqueront un très grand nombre de capteurs à déployer sur de grande zones souvent inaccessibles, ce qui conduirait à un déploiement aléatoire rendant le les modèles de graphe classique obsolète. Nous montrons que la stratégie aléatoire est la seule facon de déployer les réseaux de capteurs et par conséquent la modélisation par les graphes aléatoires géométriques et les graphe de Poisson est la plus appropriée. Nous développons ensuite nos travaux concernant la k-couverture, définit comme tout point physique de la zone de d´ ploiement doit être couvert par au moins k noeuds actifs. Une notion très importante car nécessaire au bon fonctionnement du réseau car impliquant le connexion. Pour étudier les réseaux de capteurs aléatoires et pour pouvoir mettre à profit leurs densités afin de concevoir des protocoles qui permettent de maintenir un haut degré de couverture tout en prolongeant la durée de vie du réseau, nous étudions les limites fondamentales de la durée vie d’un réseau de capteurs que tout algorithme peut atteindre. Pour un ensemble de n points suivants un processus ponctuels de Poissons d’intensité lambda dans une région de taille S avec chaque point couvrant un disque unité, nous donnerons des résultats concernant les valeurs requise pour garantir la k-couverture pour toute valeurs de k. Nous terminons enfin par l’étude en moyenne d’algorithmes pour la recherche de stable maximal dans les graphes aléatoires. Nous examinons d’abord la performance du plus simple des algorithmes séquentiel sur deux types de graphes aléatoires. Dans le premier cas, nous considérons des graphes de Poisson, on établira que l’algorithme glouton trouve un ensemble indépendant maximal dont la loi limite est asymptotiquement normal. Dans le second cas, nous étudions le même algorithme sur les graphes d’Erd˝ os-Rényi et montreront que la distribution limite n’existe pas. Enfin, nous présenterons et analyserons un algorithmes distribués probabilistes optimal (en temps et en bits).
Abstract FR:
Recent advances in sensor and wireless communication technologies in conjunction with developments in microelectronics have made available a new type of communication network. Wireless Sensor Networks (WSNs) are self-configured and infrastructure less wireless networks made of small devices equipped with specialized sensors and wireless transceivers. The main goal of a WSN is to collect data from the environment and send it to a reporting site where the data can be observed and analyzed. While many fundamental ideas existed about twenty to thirty years ago, recent years we see tremendous research activity in wireless networks due to their applications in various situations. Potential applications of sensor networks abound; they can be used to monitor remote and/or hostile geographical regions, to trace animals movement, to improve weather forecast, and so on. However, the development of working large scale WSNs still requires solutions to a number of technical and theoretical challenges, due mainly to the constraints imposed by the wireless sensor devices. This thesis is concerned first with problems in modeling wireless sensor networks. Namely, we address the problems of finding a realistic model. Communication network have their origin in classic areas of theoretical computer science and applied mathematics, the framework for wireless sensor networks will not depart from the rule, regardless of the radio technology used, from the topology point of view, at any instant in time a WSN can be represented as a graph with a set of vertices consisting of the nodes of the network and a set of edges consisting of the links between the nodes. The notion of a graph is important because a large number of parameters used in graph theory can quantify properties physical, or topological network performance modeled. However, WSNs applications involve a large number of sensors to deploy on inaccessible areas, leading to a random deployment which makes the classical graph models obsolete. We show that the modeling with Random Geometric Graphs and Poisson Graphs is the most appropriate. Another important issue is network coverage. It means how well an area of interest is being monitored by a network. To study dense random sensor networks and to show how to profit their densities in order to design protocols that can maintain high degrees of coverage while prolonging the lifetime of the network, we investigate the fundamental limits of sensor network lifetime that any algorithm can achieve. In our settings, n nodes are deployed as a Poisson point process with density # in a region of size S and each sensor node can cover a unit-area disk. We investigate the required value of lenda congruent à lambda(k), i. E. In terms of k, to guarantee the k-coverage of the region R (with absolute value of R = l2 = S) by the nodes for unbounded values of k, while all previous work dealt only with constant values. In the second part of this thesis, we consider the Maximal Independent Set problem. We consider first the performance of the simplest of the maximal independent set algorithms on two types of random graphs. In the first case, we consider Poisson graphs and establish that the greedy algorithm finds a maximal independent set whose size is asymptotically normal. In the second case, we study the same algorithm whenever the inputs are Erd˝ os-Rényi random graphs and show that the limit distribution does not exist. Finally, we present and analyze a fast randomized distributed algorithm for the Maximal Independent Set problem. The average running time of the algorithm is E(Tn) = O(logn) and the running time is O(logn) with high probability, n being the number of nodes. Each message is containing one bit.