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

Clément Saad

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

• Fleury
• Marcelo
• Académie d'Aix-Marseille
• Ben Slimane
• Université d'Avignon et des Pays de Vaucluse

Informations

• Publié par: profil-feym-2012
• Publié le: 01 juillet 2008
• Nombre de lectures: 73
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

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