Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 01 avril 2011 à 11h00 en B311, Hichem Kenniche nous parlera de : Réseaux de capteurs sans fil de grande taille : quelques contributions à la modélisation et à l'algorithmique

Résumé : Date: Wed, 16 Mar 2011 10:29:36
From: Hichem.Kenniche
j'ai le plaisir de vous inviter à la soutenance de ma thèse intitulée « Réseaux de capteurs sans fil de grande taille: quelques contributions à la modélisation et à l'algorithmique » ainsi qu'au pot qui suivra. La soutenance aura lieu le vendredi 1 avril à 11h00 dans la salle B311. Le jury sera constitué de :
M. Jean Frédéric Myoupo, professeur, Université de Picardie Jules Verne, Président.
M. Yves Métivier, professeur, Université Bordeaux 1, Rapporteur.
M. Vincent Villain, professeur, Université de Picardie Jules Verne, Rapporteur.
Mme. Frédérique Bassino, professeur, Université Paris 13, Examinatrice.
M. Gérard Duchamp, professeur, Université Paris 13, Examinateur.
M. Christian Lavault , professeur, Université Paris 13, Directeur de thèse.
M. Vlady Ravelomanana, professeur, Université Paris 7, Co-encadrant.

-------------------------------------------------------------------
Résumé de la thèse :
Cette thèse est consacrée d'abord aux problèmes de modélisation des réseaux de capteurs sans fil, à 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 les modèles de graphes classiques obsolètes. Nous montrons que la stratégie aléatoire est la seule façon 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éfinie 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é 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 valeur 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 normale. Dans le second cas, nous étudions le même algorithme sur les graphes d'Erdös-Rényi et montrerons que la distribution limite n'existe pas. Enfin, nous présenterons et analyserons un algorithme distribué probabiliste optimal (en temps et en bits).


Dernière modification : mercredi 06 juillet 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr