ACADÉMIE D'AIX MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE

-

Documents
147 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Doctorat, Bac+8
ACADÉMIE D'AIX-MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE THÈSE présentée à l'Université d'Avignon et des Pays de Vaucluse pour obtenir le diplôme de DOCTORAT SPÉCIALITÉ : Informatique École Doctorale 166 « I2S Mathématiques et Informatique» Laboratoire d'Informatique (EA 4128) Quelques contributions dans les réseaux de capteurs sans fil : Localisation et Routage par Clément SAAD Soutenue publiquement le 10 juillet 2008 devant un jury composé de : M. Philippe MICHELON Professeur, LIA, Avignon Président M. Eric FLEURY Professeur, LIP - ENS, Lyon Rapporteur M. Jean-Frédéric MYOUPO Professeur, LaRIA, Amiens Rapporteur M. Jacques BLANC-TALON DGA, Paris Examinateur M. Jean-Claude KÖNIG Professeur, LIRMM, Montpellier Examinateur M. Abderrahim BENSLIMANE Professeur, LIA, Avignon Directeur de thèse M. Marcelo DIAS DE AMORIM Chargé de Recherche, LIP6, Paris Invité Laboratoire d'Informatique Université d'Avignon Laboratoire d'Informatique d'Avignon te l-0 03 64 91 4, v er sio n 1 - 2 7 Fe b 20 09

  • directeur de thèse abderrahim

  • université d'avignon et des pays de vaucluse

  • marcelo dias de amorim

  • mur en étape préliminaire

  • amorim chargé de recherche

  • localisation dans les réseaux statiques


Sujets

Informations

Publié par
Publié le 01 juillet 2008
Nombre de visites sur la page 73
Langue Français
Signaler un problème

ACADÉMIED’AIX-MARSEILLE
UNIVERSITÉD’AVIGNONETDESPAYSDEVAUCLUSE
THÈSE
présentée à l’Université d’Avignon et des Pays de Vaucluse
pour obtenir le diplôme de DOCTORAT
SPÉCIALITÉ : Informatique
École Doctorale 166 « I2S Mathématiques et Informatique»
Laboratoire d’Informatique (EA 4128)
Quelques contributions dans les réseaux de
capteurs sans fil : Localisation et Routage
par
Clément SAAD
Soutenue publiquement le 10 juillet 2008 devant un jury composé de :
M. Philippe MICHELON Professeur, LIA, Avignon Président
M. Eric FLEURY Pr, LIP - ENS, Lyon Rapporteur
M. Jean-Frédéric MYOUPO Professeur, LaRIA, Amiens
M. Jacques BLANC-TALON DGA, Paris Examinateur
M. Jean-Claude KÖNIG Professeur, LIRMM, Montpellier
M. Abderrahim BENSLIMANE Pr, LIA, Avignon Directeur de thèse
M. Marcelo DIAS DE AMORIM Chargé de Recherche, LIP6, Paris Invité
Laboratoire d'Informatique
Laboratoire d’Informatique d’Avignon
Université d'Avignon
tel-00364914, version 1 - 27 Feb 2009tel-00364914, version 1 - 27 Feb 2009Remerciements
Je tiens à remercier les personnes qui, dans leurs rôles, ont contribué à cette aventure
scientifique et humaine qu’a représenté cette thèse.
Pour réaliser une thèse il faut, au-delà de la motivation, le goût d’apprendre et de
faire apprendre avec toute la rigueur que cela exige. Cette vision que je me suis faite, je
la dois à deux personnes qui, depuis mon stage de DEA, n’ont cessé de me transmettre
leur passion pour leur métier : Ehoud Ahronovitz et Jean-Claude König. Tout au long
de ces années, des liens d’amitié se sont tissés et même si, contrairement à Jean-Claude,
Ehoud n’a pas été encadrant de ma thèse, il a toujours été un soutien.
Cette thèse fut encadrée également par mon directeur de thèse Abderrahim Bensli-
mane que je remercie pour m’avoir proposé ce sujet.
Je remercie chaleureusement les membres du jury, Philippe Michelon en qualité de
président du jury, Eric Fleury et Jean-Frédéric Myoupo qui ont eu la tâche d’évaluer
mes travaux en tant que rapporteurs, et enfin Jacques Blanc-Talon et Marcelo Dias de
Amorim.
Pour le cadre et l’ambiance qu’ils m’ont offert au cours de ces années, je remercie les
membres de l’équipe APR et en particulier Julien avec qui j’ai étroitement collaboré sur
la fin de ma thèse.
Je n’oublie pas l’ensemble des personnes qui m’ont rendu cette thèse agréable : Yol-
lande, Nicolas, Maxime, Rémi, Gilles, et tous les autres.
Enfin, je remercie mes compagnons de route de la première heure Franck, Clément,
Sabine, Romain, ma famille sans qui je ne serais pas arrivé jusque là et plus particuliè-
rement Caroline qui pendant ma thèse m’a offert le plus beau des cadeaux.
iii
tel-00364914, version 1 - 27 Feb 2009iv
tel-00364914, version 1 - 27 Feb 2009Table des matières
1 Introduction 1
I La localisation dans les réseaux de capteurs 5
2 Présentation générale 9
2.1 Les systèmes de localisation . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Les technologies de mesure . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Temps d’arrivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Différence des temps d’arrivée . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Puissance du signal . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.4 Angle d’arrivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 La localisation dans les réseaux statiques . . . . . . . . . . . . . . . . . . 12
2.3.1 Les méthodes libres de mesure . . . . . . . . . . . . . . . . . . . . 13
2.3.2 Les basées mesures . . . . . . . . . . . . . . . . . . . . . 15
2.4 La localisation dans les réseaux mobiles . . . . . . . . . . . . . . . . . . . 19
3 AT-Family : une famille de méthodes de localisation dans les réseaux statiques 21
3.1 Pré-requis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 AT-Free : une méthode libre de mesure . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Technique d’approximation . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Gestion des diffusions . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.3 AT-Free en étape préliminaire . . . . . . . . . . . . . . . . . . . . . 26
3.3 AT-Dist : une méthode basée mesures de distance . . . . . . . . . . . . . 27
3.3.1 Technique d’approximation . . . . . . . . . . . . . . . . . . . . . . 27
3.3.2 Règles de localisation (MuR - Method using Rules) . . . . . . . . 29
3.3.3 MuR en étape préliminaire . . . . . . . . . . . . . . . . . . . . . . 34
3.4 AT-Angle : une méthode basée mesures d’angle . . . . . . . . . . . . . . 35
3.4.1 Localisation exacte . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Technique d’approximation . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Propriétés d’AT-Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.7 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.7.1 Cercle parfait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
v
tel-00364914, version 1 - 27 Feb 20093.7.2 Erreurs de mesure . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.8 Extension à la troisième dimension . . . . . . . . . . . . . . . . . . . . . . 43
3.9 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.9.1 Environnement des simulations . . . . . . . . . . . . . . . . . . . 44
3.9.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.9.3 Discussion sur les simulations . . . . . . . . . . . . . . . . . . . . 52
3.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 ATM-Family : une extension vers la mobilité 55
4.1 Stratégie d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.1 SFR (Static Fixed Rate) . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.2 DVM (Dynamic Velocity Monotonic) . . . . . . . . . . . . . . . . . 57
4.1.3 MADRD (Mobility Aware Dead Reckoning Driven) . . . . . . . . 57
4.1.4 Conclusion sur ces stratégies . . . . . . . . . . . . . . . . . . . . . 58
4.2 ATM-Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.2.1 ATM-Free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2.2 ATM-Dist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.3 ATM-Angle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2.4 Propriétés et implémentation . . . . . . . . . . . . . . . . . . . . . 62
4.2.5 Adaptation des stratégies d’ordonnancement . . . . . . . . . . . . 63
4.3 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.1 Environnement des simulations . . . . . . . . . . . . . . . . . . . 65
4.3.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
II Le routage dans les réseaux de capteurs 75
5 Présentation générale 79
5.1 Le routage géographique dans les réseaux statiques . . . . . . . . . . . . 81
5.1.1 Les algorithmes Greedy . . . . . . . . . . . . . . . . . . . . . . . . 82
5.1.2 Routage par faces (Face routing) . . . . . . . . . . . . . . . . . . . 83
5.1.3 GFG (Greedy-Face-Greedy) . . . . . . . . . . . . . . . . . . . . . . 84
5.1.4 Power Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2 Le routage géographique dans les réseaux mobiles . . . . . . . . . . . . . 84
6 EEG-Routing : Routage Géographique Efficace en Energie 87
6.1 Pré-requis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.2 Modèle énergétique et rayon d’émission optimal . . . . . . . . . . . . . . 88
6.3 Définition de la métrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.3.1 Calcul de la probabilité de communication . . . . . . . . . . . . . 90
6.3.2 Ratio entre la consommation d’énergie et le progrès . . . . . . . . 93
6.3.3 Calcul du coût d’un arc . . . . . . . . . . . . . . . . . . . . . . . . 94
6.4 EEG-Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.1 Avant le déploiement . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2 Après le . . . . . . . . . . . . . . . . . . . . . . . . . 95
vi
tel-00364914, version 1 - 27 Feb 20096.4.3 Elimination des boucles . . . . . . . . . . . . . . . . . . . . . . . . 98
6.4.4 Tolérance aux pannes et aux apparitions de capteurs . . . . . . . 98
6.5 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.5.1 Environnement des simulations . . . . . . . . . . . . . . . . . . . 99
6.5.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7 Ellipse-Routing : Une technique de routage dans les réseaux mobiles 103
7.1 Routage probabiliste dans une ellipse . . . . . . . . . . . . . . . . . . . . 103
7.1.1 Principe de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.1.2 Résultats des simulations . . . . . . . . . . . . . . . . . . . . . . . 105
7.1.3 Analyse de ces . . . . . . . . . . . . . . . . . . . . . . 106
7.2 Calcul du couple rayon d’émission - facteur de l’ellipse . . . . . . . . . . . . 107
7.2.1 Calcul analytique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.2.2 Résultats des simulations . . . . . . . . . . . . . . . . . . . . . . . 108
7.3 Gestion des erreurs de position . . . . . . . . . . . . . . . . . . . . . . . . 112
7.3.1 Erreur de position de la source . . . . . . . . . . . . . . . . . . . . 112
7.3.2 Erreurs de des nœuds restants . . . . . . . . . . . . . . . 113
7.3.3 Résultats des simulations . . . . . . . . . . . . . . . . . . . . . . . 117
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8 Conclusion et perspectives 121
8.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Liste des illustrations 125
Liste des tableaux 129
Bibliographie 131
vii
tel-00364914, version 1 - 27 Feb 2009viii
tel-00364914, version 1 - 27 Feb 2009Chapitre 1
Introduction
Dans les premiers âges de l’informatique, la difficulté pour les chercheurs était
d’adapter les différents algorithmes aux contraintes matérielles imposées par les or-
dinateurs (puissance de calcul, mémoire limitée, ...). Même si ces difficultés n’ont pas
disparu, leurs impacts tendent à diminuer tant la puissance des ordinateurs s’accroît
à une vitesse surprenante. Il faut des applications telles que la cryptographie, les ana-
lyses ADN en bio-informatique, la fouille de données, ... pour redonner vie à ces limites
imposées par le matériel. Toutefois, les avancées technologiques conduisent à une nou-
velle évolution du paradigme.
Incontestablement, ce début de vingt et unième siècle est placé sous le signe de
la communication. Après le phénomène Internet, la démocratisation des technologies
sans fil révolutionne les moyens de communication avec notamment l’apparition de
réseaux spontanés ou réseaux ad hoc. L’hétérogénéité de ces réseaux et l’absence d’in-
frastructure accroissent leurs intérêts et ouvrent de nouvelles perspectives avec, par
exemple, l’émergence de réseaux mobiles.
Autre événement majeur de l’informatique, la décomposition et la répartition des
calculs sur plusieurs machines a permis d’outrepasser les limites des processeurs. En
effet, pourquoi se limiter à une seule et même unité de calcul ? Dès lors qu’un calcul
peut se décomposer, sa résolution sera d’autant plus rapide que le nombre d’unités de
calcul sera élevé.
Enfin, indépendamment de ces avancées technologiques et algorithmiques, il existe
une tendance dans le domaine des micro-systèmes électroniques qui s’est accentuée ces
dernières années : il s’agit de la miniaturisation.
C’est dans ce contexte qu’apparaît une nouvelle génération d’appareils : les cap-
teurs communiquants. Ils sont généralement de petite taille, dotés d’une unité de cal-
cul et capables de communiquer entre eux. On parlera alors de réseaux de capteurs. Les
fonctionnalités des capteurs étant limitées de par leurs faibles ressources, les applica-
tions doivent être adaptées à leurs caractéristiques. L’émergence de ce nouveau champ
d’étude va pousser les informaticiens à retourner aux sources de leur histoire ...
1
tel-00364914, version 1 - 27 Feb 2009Chapitre 1. Introduction
Module de traitement de 
données
Module de mesure de 
distances ou d'angles
Module de localisation  Module de Capture d'évènements
(GPS, Galileo, ...) communication
Batterie
FIG.1.1: Architecture d’un capteur
La tâche première d’un capteur est de détecter un événement (par exemple, un chan-
gement de température, des mouvements, des vibrations, ...). Il est donc capable de ré-
colter des données relatives à son environnement, de les traiter, puis, si nécessaire, de
les communiquer à des capteurs voisins via un médium sans fil.
S’il existe différents types de capteurs, leur fonctionnement reste le même. L’archi-
tecture d’un capteur, représentée en figure 1.1, se résume ainsi :
– un module de capture : il détecte les événements ayant lieu dans son rayon de
perception ;
– un module de traitement : doté d’un processeur et d’une mémoire, il traite les
données détectées et éventuellement les communique ;
– un module de communication : il se charge de la transmission et de la réception
des données via un médium sans fil ;
– un module de localisation (optionnel) : il peut s’agir d’un système GPS (Parkin-
son et al, 1996), Galileo (CNES et ESA) ou d’un autre système de localisation qui
donne au capteur sa position exacte ;
– un module de mesure (optionnel) : il mesure la distance ou l’angle avec un capteur
voisin ;
– une batterie : elle alimente tous les autres modules.
Les interactions entre ces modules sont illustrées en figure 1.1. Chacun d’entre eux
est alimenté par la batterie. La consommation d’énergie est essentiellement due aux
modules de communication sans fil et de traitement des données. Le module optionnel
de localisation est également une source de consommation d’énergie non négligeable.
Pour prolonger la durée de vie des réseaux de capteurs, il est donc indispensable de mi-
nimiser les calculs et les communications. Ces contraintes majeures doivent être prises
en compte par les méthodes proposées pour ce type de réseau. La figure 1.2 est un
exemple de capteur alimenté par deux piles.
2
tel-00364914, version 1 - 27 Feb 2009