147
pages
Français
Documents
2008
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
147
pages
Français
Ebook
2008
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié par
Publié le
01 juillet 2008
Nombre de lectures
73
Langue
Français
Poids de l'ouvrage
4 Mo
Publié par
Publié le
01 juillet 2008
Nombre de lectures
73
Langue
Français
Poids de l'ouvrage
4 Mo
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