7/23/2019 2009CLF21979.pdf
1/195
Reseau de capteurs sans fil : etude en vue de la
realisation dun recepteur GPS differentiel a faible cout
Messaoud Kara
To cite this version:
Messaoud Kara. Reseau de capteurs sans fil : etude en vue de la realisation dun recepteurGPS differentiel a faible cout. Networking and Internet Architecture. Universite Blaise Pascal- Clermont-Ferrand II, 2009. French. .
HAL Id: tel-00724810
https://tel.archives-ouvertes.fr/tel-00724810
Submitted on 22 Aug 2012
HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.
Larchive ouverte pluridisciplinaire HAL, est
destinee au depot et a la diffusion de documents
scientifiques de niveau recherche, publies ou non,
emanant des etablissements denseignement et de
recherche francais ou etrangers, des laboratoires
publics ou prives.
https://tel.archives-ouvertes.fr/tel-00724810https://tel.archives-ouvertes.fr/tel-00724810https://hal.archives-ouvertes.fr/7/23/2019 2009CLF21979.pdf
2/195
Nd'ordre D.U : 1979EDSPIC : 457
Universit Blaise PascalClermont-Ferrand II
COLE DOCTORALESCIENCES POUR L'INGENIEUR DE CLERMONT-FERRAND
THSEPrsente Par
Messaoud KARAIngnieur en Informatique
Pour obtenir le grade de
DOCTEUR DUNIVERSITSpcialit : INFORMATIQUE
Rseau de capteurs sans fil : Etude en vue de la ralisation
dun rcepteurGPS diffrentiel faible cot
Soutenue publiquement le 25 novembre 2009 devant le jury :
M. Farouk Toumani Prsident (Universit Blaise Pascal)
M. Mahmoud Meribout Rapporteur (The Petroleum Institute, Abu Dhabi, United
Arab Emirates)
Mme. Edwige Pissaloux Rapporteur (Universit Pierre et Marie Curie)
M. Jean-Pierre Chanet Invit (CEMAGREF de Clermont-Ferrand)
M. Kun Mean Hou Directeur de thse (Universit Blaise Pascal)
7/23/2019 2009CLF21979.pdf
3/195
7/23/2019 2009CLF21979.pdf
4/195
A ma famille.
7/23/2019 2009CLF21979.pdf
5/195
7/23/2019 2009CLF21979.pdf
6/195
Remerciements
Mes travaux de thse se sont drouls au sein du laboratoire LIMOS (Laboratoire d'Informatique,
de Modlisation et d'Optimisation des Systmes, UMR 6158 CNRS), et, en partie, en collaboration
avec le SMTC (Syndicat Mixte des Transports en Commun de lagglomration clermontoise) et deux
socits prives GT Aquitaine (Garczynski Traploir Aquitaine, filiale du groupe VINCI) et i2S.
Je tiens remercier ceux qui mont aid de prs ou de loin dans la ralisation de mes travaux.
Je tiens tout dabord remercier mon directeur de thse, Monsieur Kun Mean HOU, pour mavoir
accueilli au sein de son quipe (SMIR, Systmes Multi-sensoriels Intgrs Intelligents Rpartis). Son
expertise, sa disponibilit, sa confiance, son soutien et ses conseils mont t prcieux.
Mes remerciements vont, tout naturellement, aussi Monsieur Alain Quilliot Directeur dulaboratoire LIMOS. Il na jamais pargn ses efforts pour encourager les partenariats avec des
acteurs industriels et pour fournir des moyens dencadrement de bonnes qualits.
Je tmoigne normment de gratitude envers tous les membres du jury et je remercie vivement
Monsieur Mahmoud Meribout et Madame Edwige Pissaloux davoir accept d'tre rapporteur de mes
travaux, et Monsieur Farouk Toumani davoir prsid mon jury de thse. Je remercie galement
Monsieur Jean-Pierre Chanet pour sa participation ce jury et son engagement trs fort dans de
nombreuses collaborations entre le Cemagref de Clermont-Ferrand (UR TSCF quipe COPAIN) et
lquipe SMIR du laboratoire LIMOS. Ce fut un vrai plaisir de collaborer avec son quipe.
Je remercie le SMTC davoir financ en partie mes travaux dans le cadre de deux projets de
recherche et dveloppement (Projets SUAB et MobiPlus). Je remercie aussi les entreprises et les
organismes avec lesquels jai collabor lors de mes travaux de recherche dont GT Aquitaine, i2S,
TMS et le laboratoire LASMEA. Dans ce cadre l, je remercie Messieurs Serge Godard (Prsident du
SMTC) et Patrice Charlat (Chef de projet du tramway clermontois), Jean-Rmy Gad et Jean Dumesnil
(respectivement chef dentreprise et charg daffaires de lentreprise GT Aquitaine Talence), et
Jean-Louis Blouin et Christophe Geindre (respectivement directeur gnral et responsable de la
division Solutions de la socit i2S Pessac).
Mes remerciements vont galement tous les membres de l'quipe SMIR qui sont devenus plus
que des collgues ; pour leur accueil, leur aide et pour les moments que nous avons partags et les
discussions enrichissantes que nous avons eues. Je remercie particulirement Messieurs Hai-Ying
ZHOU et Christophe de Vaulx dont leur aide ma t trs prcieuse lors de mon arrive dans lquipe.
Je remercie galement M. Mohamad Badra et Mme Jian-Jin LI ainsi que mes autres collgues :
Abdelaziz Amamra, Gil De Sousa, Aurlien Jacquot, Xunxing Diao et Hao Ding. Je suis donc trs
reconnaissant envers eux tous. Sans eux, la ralisation de cette thse n'aurait pas t possible.
7/23/2019 2009CLF21979.pdf
7/195
Je veux bien videmment remercier toutes les personnes que j'ai ctoyes de prs ou de loin -
simplement avec un bonjour un matin - durant ces annes de thse, au laboratoire LIMOS, au SMTC,
chez i2S et GT Aquitaine. Merci eux tous.
Je suis galement reconnaissant envers Alexandre Guitton avec qui jai travaill le pl us pendant
mes deux annes dATER (Attach Temporaire dEnseignement et de Recherche).
Merci ceux qui ont contribu ce que cette thse se passe bien : collaborateurs, personnes
administratives, aides techniques, Merci donc Batrice Bourdieu, Daniel Breugnot, Martine
Closset, Nathalie Fonty, Frdric Meignan et Rose Seguy.
Jai une norme pense pour tous les membres de ma famille, mme loigns, pour leurs
encouragements incessants et, en particulier, pour mon pouse pour son soutien indfectible et sa
patience inpuisable.
Enfin, je remercie tous mes amis, dont la liste serait trop longue numrer. Si j encite quelques
uns, je risque denoublier, Je les remercie donc pour leur soutien tout au long de ces annes de thse
et pour leurs encouragements et conseils notamment dans les moments difficiles.
7/23/2019 2009CLF21979.pdf
8/195
Rsum
Un Rseau de Capteurs Sans Fil (RCSF) est compos dun ensemble de capteurs/nudsdont le
nombre peut tre trs grand. Le RCSF est utilis pour raliser une tche spcifique dune application.
Les RCSF sont devenus de plus en plus populaires grce leur large champ dapplicationsciviles et
militaires : environnement, agriculture, mtorologie, sant, domotique
Le but final dunRCSF est de surveiller une zone dintrt, mais pour y parvenir plusieurs sous
objectifs (services) doivent tre raliss. Parmi ces services : la synchronisation entre nuds, la
localisation, la gestion de la topologie, lagrgation des donnes, le stockage de donnes, etc.
La localisation des nuds est lun des services les plus importants. Elle consiste associer
chaque nud les coordonnes de sa position. Plusieurs mthodes sont utilises pour raliser cette
fonctionnalit. Un ensemble de systmes (technologies) ont t dvelopps pour assurer ce service.
Le systme le plus utilis lextrieur, lchelle mondiale, est de loin le GPS ( Global Positioning
System). Il a lavantage de fournir la position (ainsi que lheure) en continu et dans toutes les
conditions mtorologiques.
Cependant, la prcision du GPS nest pas suffisante pour toutes les applications, do la ncessit
de lamliorer. Pour cela, le mode diffrentiel (DGPS, Differential GPS) est introduit. Il consiste
utiliser une station de base qui surveille les erreurs du GPS, calcule des corrections et les transmet
via un mdium daccs sans fil. Mais linstallation dune station diffrentielle (RTK, Real -Time
Kinematic) est difficile et surtout trs onreuse.
Le mode diffrentiel inspire les travaux de cette thse mais linverse de la solution RTK qui utilise
une grande station de base, la solution originale propose dans cette thse (LCDGPS, Low Cost
Differential GPS, Local Cooperative DGPS) est base sur lutilisation dun RCSF quips de
rcepteurs GPS standards faible cot.
Les travaux mens pour amliorer la prcision du GPS incluent lutilisation de carte numrique
(Map Matching), la diffrence simple, la diffrence intelligente, le filtrage, la correction globale,
Afin dvaluer cette solution, une plateforme matrielle et logicielle a t dveloppe, elle consis te
en un rseau de capteurs appels LiveNodes (LIMOS Versatile Embedded Node). La partie logicielleest compose notamment dun systme dexploitation embarqu appel LIMOS ( LIghtweight Multi-
threading Operating System) et dun protocole de communication sans fil appel CIVIC
(Communication Inter Vhicule Intelligente et Cooprative) et enfin les traitements propres la
solution LCD-GPS.
Les rsultats obtenus montrent que le LCD-GPS peut tre utilis pour diverses applications mais
quil est trs sensible lenvironnement (multi-trajet). Cependant, il est noter que, le RCSF permet
en gnral la ralisation dun capteur robuste et sr.
Mots-cls: Localisation, Rseaux de Capteurs Sans Fil, RCSF, GPS, DGPS, GPS Diffrentiel, MapMatching
7/23/2019 2009CLF21979.pdf
9/195
7/23/2019 2009CLF21979.pdf
10/195
Wireless Sensor Networks: Study for developing a LowCost Differential GPS receiver.
Abstract
A Wireless Sensor Network (WSN) consists of a set of wireless nodes where their number can be
very large. The WSN is used to perform a specific task for an application. The WSN has become
increasingly popular due to their wide range of civil and military applications: smart planet, smart
home, smart care, M2M (Machine to Machine)...
The ultimate goal of a WSN is to monitor an area of interest, but to achieve that, several objectives
(services) must be implemented. These services include: synchronization between nodes, localization,
topology management, data aggregation, data storage, etc.
The nodes localization is one of the most important services. It associates to each node the
coordinates of its position. Several methods are used to achieve this function. A set of systems
(technologies) have been developed to provide this service.
The most commonly used outdoors, worldwide, by far is the GPS (Global Positioning System). It
has the advantage of providing the position (and time) continuously and in all weather conditions.
However, the accuracy of GPS does not meet the requirements of all applications, thus it is
necessary to improve GPS accuracy. For this, the differential mode (DGPS, Differential GPS) is
introduced. It uses a base station that monitors the GPS errors, calculates corrections and transmits
them through a wireless access medium; but the installation of a differential station (RTK, Real-Time
Kinematic) is difficult and very expensive.
The differential mode inspires this thesis, but in contrast to the RTK solution that uses a large base
station, the original solution proposed in this thesis (LCD-GPS, Low Cost Differential GPS, Local
Cooperative DGPS) is based on using a WSN equipped with low cost standard GPS receivers.
Works conducted to improve the GPS accuracy include the use of a digital map (Map Matching),
the simple difference, the intelligent difference, the filtering and a global correction.
To evaluate this solution, a hardware and software platform has been developed; it consists of a
network of wireless nodes called LiveNodes (LIMOS Versatile Embedded Node). The software part iscomposed particularly of an embedded operating system called LIMOS (Lightweight Multi-Threaded
Operating System) and a wireless communication protocol called CIVIC (Inter Vehicle Communication
and Intelligent Cooperative) and finally the specific processing of LCD-GPS solution.
The results show that the LCD-GPS can be used for various applications but it is very sensitive to
the environment (multipath). However, it is noted that the WSN can generally achieve a robust and
reliable location sensor.
Keywords: Localization, Wireless Sensor Networks, WSN, GPS, DGPS, Differential GPS, Map
Matching
7/23/2019 2009CLF21979.pdf
11/195
7/23/2019 2009CLF21979.pdf
12/195
xi
Table des matires
Remerciements ................................................................................................................. v
Rsum............................................................................................................................ vii
Abstract ............................................................................................................................ ix
Table des figures .............................................................................................................. xv
Liste des tableaux ........................................................................................................... xix
Liste des acronymes ........................................................................................................ xxi
INTRODUCTION GNRALE ............................................................................................... 1
Organisation du mmoire .......................................................................................................... 2
I SYSTEMES DE LOCALISATION ...................................................................................... 5
1 Introduction ....................................................................................................................... 5
1.1 Importance des systmes de localisation ........................................................................................... 51.2 Contraintes pour un systme de localisation ...................................................................................... 61.3 Proprits dun systme de localisation ............................................................................................. 71.4 Composition dun systme de localisation........................................................ .................................. 9
2 Estimation de distance/angle ........................................................................................... 10
2.1 Indicateur de puissance du signal reu RSSI .............................................................. ..................... 112.2 Le nombre de sautsRHC (Radio Hop Count) .................................................................................. 112.3 Le temps de parcoursToA/ToF ...................................................................................................... 12
2.4 La diffrence du temps darrive TDoA .......................................................... ................................ 122.5 Langle darrive AoA/DoA ............................................................................................................. 132.6 La reconnaissance de motifs ............................................................................................................. 142.7 Autres approches .............................................................................................................................. 142.8 Commentaires sur lestimation de distance/angle........................................................................... 18
3 Calcul de la position (auto-localisation) ............................................................................. 18
3.1 Trilatration et multilatration ......................................................................................................... 193.2 Triangulation ..................................................................................................................................... 203.3 Approche probabiliste ....................................................................................................................... 213.4 Cadre englobantBB ........................................................................................................................ 223.5 Position centrale ............................................................................................................................... 23
3.6 Bilan et synthse sur les techniques de calcul de la position ............................................................ 234 Algorithme de localisation ................................................................................................ 24
4.1 Le systme GPS ................................................................................................................................. 254.2 Systme de localisation ad hoc (APS) ................................................................ ................................ 274.3 Estimation rcursive de la position (RPE) .......................................................................................... 294.4 Estimation dirige/oriente de la position (DPE) .............................................................................. 294.5 Localisation avec balise mobile (LMB) .............................................................................................. 30
5 Exemples de systmes de localisation (technologies) ........................................................ 31
5.1 Active Badge ...................................................................................................................................... 315.2 Active Bat .......................................................................................................................................... 325.3 Cricket ............................................................................................................................................... 33
5.4 RADAR ............................................................................................................................................... 346 Amlioration de la prcision ............................................................................................. 35
7/23/2019 2009CLF21979.pdf
13/195
Table des matires
xii
6.1 Le lissage (filtre passe bas) ................................................................................................................ 356.2 La limitation (SNAPPING) .................................................................................................................. 366.3 La fusion et le suivi (fusion and tracking) .......................................................................................... 36
7 Conclusion ....................................................................................................................... 36
II POSITIONNEMENT PAR SATELLITES ........................................................................... 39
1 Introduction ..................................................................................................................... 39
2 Le systme GPS ................................................................................................................ 40
2.1 La composition du systme ............................................................................................................... 402.2 Lhistorique du GPS ........................................................................................................................... 442.3 Services offerts par le GPS ................................................................................................................ 452.4 Le principe du positionnement ......................................................................................................... 46
3 Les sources derreurs ........................................................................................................ 52
3.1 Introduction ...................................................................................................................................... 523.2 Quantification des erreurs ................................................................................................................ 533.3 Erreurs du secteur de contrle.......................................................................................................... 54
3.4 Erreurs atmosphriques (propagation) ............................................................................................. 563.5 Erreurs dues au rcepteur ................................................................................................................. 583.6 Performances du GPS ........................................................................................................................ 59
4 Le GPS diffrentiel (DGPS) ................................................................................................ 60
4.1 Principe du DGPS ............................................................................................................................... 604.2 Analyse des erreurs du DGPS ............................................................................................................ 614.3 Performance du DGPS ....................................................................................................................... 624.4 Techniques du GPS Diffrentiel .............................................................. ........................................... 63
5 Systmes daugmentation de la prcision par satellites..................................................... 65
5.1 WAAS ................................................................................................................................................. 655.2 EGNOS ............................................................................................................................................... 66
5.3 MSAS ................................................................................................................................................. 665.4 GAGAN .............................................................................................................................................. 66
6 Modernisation du systme GPS ........................................................................................ 67
7 Les autres systmes de localisation par satellites .............................................................. 67
7.1 GLONASS ........................................................................................................................................... 687.2 GALILEO ............................................................................................................................................. 697.3 BEIDOU (BEIDOU -2, COMPASS) ........................................................................................................ 72
8 La transformation des coordonnes WGS-84 vers Lambert II ............................................. 73
8.1 Dfinition........................................................................................................................................... 738.2 Gomtrie de lellipsode.................................................................................................................. 73
8.3 Transformation des coordonnes gographiques vers cartsiennes ............................................... 748.4 Paramtres de la similitude entre WGS-84 et NTF ........................................................................... 748.5 Transformation des coordonnes cartsiennes vers gographiques ............................................... 748.6 Transformation des coordonnes gographiques vers planes ......................................................... 75
9 Conclusion ....................................................................................................................... 77
III LCD-GPS (LOW-COST DIFFERENTIAL GPS)................................................................ 79
1 Introduction ..................................................................................................................... 79
2 Principe du LCD-GPS ......................................................................................................... 79
3 Analyse de la solution....................................................................................................... 80Correction et fonction de transfert ............................................................................................................... 81
4 Caractrisation des positions dun point........................................................................... 82
7/23/2019 2009CLF21979.pdf
14/195
Table des matires
xiii
5 Corrections diffrentielles en tapes ................................................................................. 86
5.1 Utilisation dune carte numrique (Map Matching)......................................................................... 865.2 Une correction locale ........................................................................................................................ 895.3 Une correction globale ...................................................................................................................... 96
6 Exprimentations LISIMA: ............................................................................................ 96
6.1 Scnario I : Espace ouvert ................................................................................................................. 976.2 Scnario 2 : Effet du multi-trajet sur la prcision ......................................................... ................... 105
7 La correction globale ....................................................................................................... 110
8 Exprimentations sur la plateforme PAVIN ...................................................................... 116
8.1 Prsentation de la plateforme PAVIN ............................................................................................. 1168.2 Scnario I : Correction globale ........................................................................................................ 1178.3 Scnario II : La moyenne de plusieurs rcepteurs GPS ................................................................... 121
9 Conclusion ...................................................................................................................... 122
IV La plateforme matrielle et logicielle et ses applications ....................................... 123
1 Introduction .................................................................................................................... 1232 Architecture Matrielle ................................................................................................... 123
2.1 Les plateformes existantes ........................................................... ................................................... 1242.2 Le LiveNode ..................................................................................................................................... 1252.3 La station de base (ZigBee/Wi-Fi).................................................................................................... 128
3 Architecture Logicielle ..................................................................................................... 128
3.1 Les systmes dexploitation embarqus ddis aux RCSF .............................................................. 1283.2 Le systme LIMOS ........................................................................................................................... 1293.3 Les algorithmes de routages existants (MANET)............................................................................. 1303.4 Le protocole CIVIC ........................................................................................................................... 1313.5 Le LCD-GPSTraitements GPS ............................................................... ......................................... 136
4 Cas dutilisation du capteur LiveNode .............................................................................. 1394.1 Projet Net-ADDED ........................................................................................................................... 1394.2 Projet MobiPlus ............................................................................................................................... 1414.3 Autre projets et collaborations ....................................................................................................... 143
5 Conclusion ...................................................................................................................... 145
CONCLUSION GENERALE ................................................................................................ 147
Bibliographie ................................................................................................................. 151
ANNEXE I ALMANACH ................................................................................................. 159
1 Paramtres dune orbite de satellite ................................................................................ 159
2 Extrait dun almanch ....................................................................................................... 159
3 Logiciel Planning de Trimble ....................................................................................... 161
ANNEXE II MESSAGE DE NAVIGATION .......................................................................... 163
1 Format du message de navigation .................................................................................... 163
2 Contenu du message de navigation .................................................................................. 163
ANNEXE III Calcul des valeurs DOP ............................................................................... 165
ANNEXE IV Description du protocole NMEA 0183 ...................................................... 167
1 Message GGA - Global positioning system fixed data ........................................................ 168
7/23/2019 2009CLF21979.pdf
15/195
Table des matires
xiv
2 Message GGL - Geographic positionLatitude/Longitude ................................................ 169
3 Message GSA - GNSS DOP and active satellites ................................................................. 169
4 Message GSV - GNSS satellites in view ............................................................................. 169
5 Message RMC - Recommended minimum specific GNSS data ........................................... 170
6 Message VTG - Course over ground and ground speed ..................................................... 170
7/23/2019 2009CLF21979.pdf
16/195
xv
Table des figures
Figure I-1 Composition dun systme de localisation [1] ....................................................................... 10Figure I-2 Principe du TDoA .................................................................................................................. 13
Figure I-3 Principe de la trilatration ..................................................................................................... 19
Figure I-4 Principe de la triangulation [1] ............................................................................................... 21
Figure I-5 Principe de la triangulation [7] ............................................................................................... 21
Figure I-6 Exemple approche probabiliste [1]........................................................................................ 22
Figure I-7 Principe du cadre englobant ................................................................................................. 23Figure I-8 Principe du DPEDirected Position Estimation.................................................................. 30
Figure I-9 Active Badge....................................................................................................................... 32
Figure I-10 principe du Active Bat........................................................................................................ 33
Figure I-11 Emetteur/Rcepteur Cricket ................................................................................................ 34
Figure II- 1 Segments du systme GPS [60] ......................................................................................... 40Figure II- 2 La constellation GPS .......................................................................................................... 41
Figure II- 3 Des satellites GPS des blocs II/IIA, IIR-M, IIF et III ............................................................ 41
Figure II- 4 Carte des stations du segment de contrle ........................................................................ 43
Figure II- 5 Positionnement 3D avec une seule mesure connue (R) .................................................... 46
Figure II- 6 Positionnement 3D avec deux mesures connues............................................................... 47
Figure II- 7 Positionnement 3D avec trois mesures connues................................................................ 47
Figure II- 8 Rfrentiel ECEF ................................................................................................................ 48
Figure II- 9 Mesure du temps par un rcepteur GPS ............................................................................ 50
Figure II- 10 Construction des signaux GPS transmis sur L1 et L2 [49] ............................................... 52
Figure II- 11 Erreurs de position du satellite [49] .................................................................................. 54
Figure II- 12 DOP - Mauvaise gomtrie des satellites [50] .................................................................. 56Figure II- 13 DOP - Bonne gomtrie des satellites [50] ....................................................................... 56
Figure II- 14 Traverse des couches atmosphriques .......................................................................... 56
Figure II- 15 Le multi-trajet .................................................................................................................... 58
Figure II- 16 Architecture d'un systme GPS diffrentiel ...................................................................... 61
Figure II- 17 Principe daugmentation de la prcision par satellites WAAS ....................................... 65
Figure II- 18 Prcision GPS avec la correction WAAS .......................................................................... 66
Figure II- 19 La constellation GLONASS ............................................................................................... 68
Figure II- 20 La constellation GALILEO ................................................................................................. 70
Figure II- 21 Un satellite GALILEO (GIOVE-A, vue dartiste)................................................................ 72Figure II- 22 Processus de changement de systme godsique [47] ................................................. 74
Figure II- 23 Zones de projection Lambert ............................................................................................ 76
Figure III- 1 Principe du LCD-GPS ........................................................................................................ 80
Figure III- 2 Schma de principe de la correction diffrentielle ............................................................. 82
Figure III- 3 Relevs GPS dun point sur le toit de lISIMA pendant 7 heures le 24/07/2008 ............... 83
Figure III- 4 Satellites utiliss pour le positionnement dun point sur le toit de lISIMA......................... 84
Figure III- 5 Variations des carts en X, Y et Z pour un mme point (7 Heures) .................................. 84
Figure III- 6 Variations des carts en X, Y et Z pour un mme point (5 minutes) ................................. 85
Figure III- 7 Histogramme des erreurs en X, Y et Z respectivement ..................................................... 86
Figure III- 8 Correction laide dune carte numrique (MAP MATCHING) ......................................... 87
Figure III- 9 Trois trajectoires de trois rcepteurs GPS ......................................................................... 87
Figure III- 10 Projection dune trajectoire sur les bords de la route (Map Matching) ............................ 88Figure III- 11 Carte du campus des Czeaux (Universit Blaise Pascal) ............................................. 89
7/23/2019 2009CLF21979.pdf
17/195
Table des figures
xvi
Figure III- 12 Principe de la diffrence simple (une seule station) ........................................................ 90
Figure III- 13 Le placement des 3 capteurs ........................................................................................... 90
Figure III- 14 Format des donnes GPS au format NMEA .................................................................... 91
Figure III- 15 Format des donnes GPS aprs conversion en LAMBER II ........................................... 91
Figure III- 16 Les positions instantanes des 3 capteurs (exprimentation du 04/01/2007) ................ 92
Figure III- 17 Les positions instantanes du 2me
capteur (exprimentation du 04/01/2007) ............... 92Figure III- 18 Facteurs de corrlation entre les coordonnes des 3 capteurs ....................................... 93
Figure III- 19 Les positions corriges du 3mecapteur .......................................................................... 94
Figure III- 20 Les positions estimes des 3capteurs ............................................................................ 95
Figure III- 21 Un relev GPS pour les mmes 3 points fixes ................................................................ 95
Figure III- 22 Le placement des 3 capteurs (Exprimentation 22-23-24/07/2008)................................ 97
Figure III- 23 Les positions instantanes des 3 capteurs ...................................................................... 98Figure III- 24 Variations des carts en X, Y et Z pour le 1iercapteur22/08/2008 .............................. 99
Figure III- 25 Extrait des variations dX, dY et dZ................................................................................... 99
Figure III- 26 Erreurs simultanes des 3 capteurs, variations en X .................................................... 100
Figure III- 27 Erreurs simultanes des 3 capteurs, variations en Y .................................................... 100
Figure III- 28 Erreurs simultanes des 3 capteurs, variations en Z..................................................... 101Figure III- 29 Nuages de points des 3 capteurs22/07/2008 ............................................................ 102
Figure III- 30 Traitements sur les donnes du 1ercapteur .................................................................. 103
Figure III- 31 Traitements sur les donnes du 2mecapteur ................................................................ 103
Figure III- 32 Traitements sur les donnes du 3mecapteur ................................................................ 104
Figure III- 33 Lieu des exprimentations (parking ISIMA) ................................................................... 105
Figure III- 34 La disposition des 5 capteurs ........................................................................................ 106
Figure III- 35 Les nuages de points des 5 capteurs ............................................................................ 107
Figure III- 36 Comparaison des prcisions des 5 capteurs ................................................................. 107
Figure III- 37 Un Cycab avec un LiveNode ......................................................................................... 117
Figure III- 38 La plateforme PAVINCircuit urbain ............................................................................ 117
Figure III- 39 PAVIN- Positions des capteurs fixes (rouge) et mobile (cyan) ...................................... 118
Figure III- 40 Pavin - Correction pour un mobile avec 6 stations de rfrence ................................... 119
Figure III- 41 Pavin - Correction pour un mobile avec 5 stations de rfrence ................................... 120
Figure III- 42 Pavin - Correction pour un mobile avec 4 stations de rfrence ................................... 120
Figure III- 43 PAVIN- trace dun mobile avec 3 rcepteur GPS.......................................................... 121
Figure IV- 1 Architecture matrielle et logicielle dun LiveNode ddi au LCD-GPS .......................... 123
Figure IV- 2 Le LiveNode (deux gnrations) ..................................................................................... 125
Figure IV- 3 Un ensemble de LiveNodes ............................................................................................ 126Figure IV- 4 Le multi-support WiFi-ZigBee (2 LiveNodes connects ensemble) ................................ 127
Figure IV- 5 La station ZigBee ............................................................................................................. 128
Figure IV-6 Larchitecture de LIMOS
.................................................................................................. 130
Figure IV- 7 CIVIC - Architecture mixte Ad-hoc et infrastructure ........................................................ 132
Figure IV- 8 Le concept de DANKAB .................................................................................................. 133
Figure IV- 9 La structure du protocole CIVIC avec LCD-GPS ............................................................ 134
Figure IV- 10 La topologie du routage avec le SF ............................................................................... 134
Figure IV- 11 La topologie du routage avec DANKAB ........................................................................ 135
Figure IV- 12 Test de CIVIC sur PAVIN (disposition des nuds)....................................................... 136
Figure IV- 13 Test de CIVIC sur PAVIN avec un mobile (vhicule cycab) .......................................... 136
Figure IV- 14 LCD-GPS pour une station de rfrencePhase I ...................................................... 137
Figure IV- 15 LCD-GPS pour une station de rfrencePhase II ..................................................... 138
Figure IV- 16 LCD-GPS Utilisation dune carte numrique ................................................................. 138
Figure IV- 17 LCD-GPS Correction diffrentielle................................................................................. 139Figure IV- 18 Net-ADDEDUtilisation du LiveNode dans lagriculture.............................................. 140
7/23/2019 2009CLF21979.pdf
18/195
Table des figures
xvii
Figure IV- 19 Net-ADDEDLiveNode utilis pour la collecte de lhumidit au sol............................ 141
Figure IV- 20 MobiPlusLe sous-systme quai (SSQ) ...................................................................... 142
Figure IV- 21 MobiPlusLe sous-systme bus (SSB) ....................................................................... 143
Figure IV- 22 MobiPlusLa plateforme exprimentale Aubire ..................................................... 143
Figure IV- 23 Projet STARCapteur biomdical ............................................................................... 144
Figure IV- 24 Projet STARPrincipe gnral..................................................................................... 144Figure i1- 1 Les diffrents paramtres dune orbite de satellite.......................................................... 159Figure i1- 2 Visibilit des satellites GPS sur Clermont-Ferrand .......................................................... 161Figure i1- 3 Nombre de satellites visibles ............................................................................................ 162Figure i1- 4 Carte du ciel : Azimut & Elvation durant 24 heures ....................................................... 162Figure i1- 5 Les diffrentes valeurs de DOP ....................................................................................... 162Figure i2- 1 Structure du message de navigation ............................................................................... 163Figure i2- 2 Contenu du message de navigation ................................................................................ 164
7/23/2019 2009CLF21979.pdf
19/195
7/23/2019 2009CLF21979.pdf
20/195
xix
Liste des tableaux
Tableau I-1 : Comparaison des mthodes destimation des distances/angles..................................... 18Tableau I-2 : Comparaison des mthodes de calcul de la position [1] ................................................. 24
Tableau II-1 Bilan des erreurs du GPS [49] .......................................................................................... 60Tableau II-2 Bilan des erreurs du DGPS ............................................................................................... 62Tableau II-3 Performances prvues des diffrents services de GALILEO [41][45] .............................. 72Tableau II-4 Constantes de la projection Lambert pour la France [47] ................................................. 75
Tableau III1 Statistique sur les positions instantanes dun point sur le toit de lISIMA.................... 83
Tableau III2 Statistique sur les changements des positions GPS - Temps ....................................... 85
Tableau III3 Statistique sur les changements des positions GPS - Distance.................................... 85
Tableau III4 Rsum des rsultats de deux exprimentations.......................................................... 96
Tableau III5 Diffrence simple applique aux donnes du 1ierjour (22/07/2008) ........................... 101
Tableau III6 Diffrence intelligente applique aux donnes du 1ier
jour (22/07/2008) .................... 102Tableau III7 Rsum des carts types des 5 capteurs (25/11/2008) .............................................. 107
Tableau III8 Rsultats de la diffrence simple ................................................................................. 108
Tableau III9 Rsultats de la diffrence simple avec les donnes filtres ........................................ 109
Tableau III10 Rsultats de la diffrence intelligente ........................................................................ 109
Tableau III11 Rsultats de la diffrence intelligente avec les donnes filtres ............................... 110
Tableau III12 Rsultats de la diffrence simple globale (2 stations) ............................................... 111
Tableau III13 Rsultats de la diffrence simple globale (3 stations) ............................................... 111
Tableau III14 Rsultats de la diffrence simple globale (4 stations) ............................................... 112
Tableau III15 Rsultats du filtrage+la diffrence simple globale (2 stations) .................................. 112
Tableau III16 Rsultats du filtrage+la diffrence simple globale (3 stations) .................................. 113
Tableau III17 Rsultats du filtrage+la diffrence simple globale (4 stations) .................................. 113Tableau III18 Rsultats de la diffrence intelligente globale (2 stations) ........................................ 114
Tableau III19 Rsultats de la diffrence intelligente globale (3 stations) ........................................ 114
Tableau III20 Rsultats de la diffrence intelligente globale (4 stations) ........................................ 115
Tableau III21 Rsultats du filtrage+la diffrence intelligente globale (2 stations) ........................... 115Tableau III22 Rsultats du filtrage+la diffrence intelligente globale (3 stations) ........................... 116
Tableau III23 Rsultats du filtrage+la diffrence intelligente globale (4 stations) ........................... 116
Tableau IV1 Comparaison entre les CSF existants [65] .................................................................. 124
7/23/2019 2009CLF21979.pdf
21/195
7/23/2019 2009CLF21979.pdf
22/195
xxi
Liste des acronymes
AS AntiSpoofing
CEP Circular Error Probable
CDMA Code Division Multiple Access
DOP Dilution Of Precision
GDOP Geometric DOP
HDOP Horizontal DOP
PDOP Position DOP
VDOP Vertical DOP
DGPS Differential GPS
ECEF Earth Centered, Earth Fixed
EGNOS European Geostationary Navigation Overlay Service
GNSS Global Navigation Satellite System
GPS Global Positioning System
INS Inertial Navigation System
LAN Local Area Network
MSAS MTSAT Based Augmentation System
NAVSTAR Navigation System with Time and Ranging
PPS Precise Positioning Service
PRN Pseudo Random Noise or Pseudo Random Number
RHC Radio Hop Count
RMS Root Mean Square
HRMS Horizontal Root Mean Square
RSSI Received Signal-Strength Indicator
RTLS Real Time Locating System
SA Selective Availability
SEP Spherical Error Probable
SBAS Satellite-Based Augmentation System
7/23/2019 2009CLF21979.pdf
23/195
Liste des acronymes
xxii
SPS Standard Positioning Service
SV Space Vehicle (Satellite)
SVN Space Vehicle Number
ToA Time of Arrival
TDoA Time Difference of Arrival
UERE User Equivalent Range Error
UTC Universal Coordinated Time
UTM Universal Transverse Mercator
WLAN Wireless Local Area Network
WAAS Wide Area Augmentation System
WGS World Geodetic System
7/23/2019 2009CLF21979.pdf
24/195
1
INTRODUCTION GNRALE
Ces dernires annes ont vu natre un nouveau type de rseaux appels Rseaux de Capteurs
Sans Fil (RCSF), grce notamment aux progrs rcents dans la microlectronique et les technologies
de transmission sans fil.
Un RCSF est compos dun ensemble de nuds/capteurs dont le nombre peut tre trs grand. Le
RCSF est utilis pour raliser une tche spcifique dune application. Chaque nud intgre une
sonde (capteur) qui mesure une grandeur physique (temprature, humidit, luminosit, ), un module
de communication sans fil et un microcontrleur pour traiter les informations et ventuellement les
stocker dans une unit de mmoire.
Les RCSF sont devenus de plus en plus populaires en raison de leur large champ dapplications
civiles et militaires : environnement, agriculture, mtorologie, sant, domotique
Afin que le RCSF parvienne raliser son objectif principal, il est ncessaire que plusieurs sous-
objectifs soient atteints. Parmi ces sous-objectifs : la synchronisation entre nuds, la localisation, la
gestion de la topologie du rseau, lagrgation des donnescollectes, le stockage de donnes, etc.
La localisation des nuds est lun des services les plus importants. Elle consiste dterminer la
position physique (par exemple latitude, longitude et altitude pour le GPS) de chaque nud.
Les systmes de localisation sont identifis comme une technologie cl pour le dveloppement et
lutilisation des RCSF. Cependant, leur utilisation nest pas rserve aux RCSF. Ils sont utiliss dans
plusieurs autres domaines : la robotique, les rseaux ad hoc, la tlphonie mobile,
Le systme GPS est le systme de localisation le plus utilis au monde. Il prsente un certains
nombre davantages: Il est disponible dans le monde entier, il fonctionne jour et nuit (24h/24 et 7j/7)
et dans toutes les conditions mtorologiques (avec dgradation de ses performances dans les cas
extrmes).
Cependant, il nest pas utilisable partout. En effet, il nest utilisable qu lextrieur et lorsquil ny a
pas dobstacle. De plus, sa prcision nest pas suffisante pour toutes les applications du fait que les
signaux GPS sont perturbs par plusieurs phnomnes lis notamment la traverse des couches
atmosphriques (ionosphre et troposphre) et lendroit o se trouve le rcepteur GPS.
Pour amliorer la prcision du GPS, le mode diffrentiel est adopt. Il consiste utiliser une station
de base (fixe) quipe dun rcepteur GPS et dun dispositif de communication radio. Cette station
surveille en permanence les erreurs du GPS, calcule des corrections et les transmet par radio. Un
rcepteur GPS (dot de la fonction diffrentielle) qui reoit ces corrections, les applique ses
mesures de distances (RcepteurSatellites) puis calcule sa position corrige. Cette position est plus
prcise que la position calcule par le rcepteur GPS sans correction (mode absolu).
Nos travaux de thse sinspirent du mode diffrentiel du GPS, mais linverse des solutions
diffrentielles existantes (trs onreuses, taille imposante, installation complique), la solution que
nous proposons est base sur lutilisation dun RCSF compos de nuds quips de rcepteurs GPS
7/23/2019 2009CLF21979.pdf
25/195
INTRODUCTION GNRALE
2
standard (civil) faible cot. Ils cooprent pour fournir un service de positionnement GPS diffrentiel
amliorant ainsi la prcision du positionnement sans pour autant augmenter les cots dune manire
significative.
Notre travail au dpart tait de concevoir et mettre en uvre la localisation par GPS au sein du
protocole de communication CIVIC (Communication Inter Vhicule Intelligente et Cooprative) qui
tait en cours de dveloppement. La localisation par GPS permettra alors dutiliser des antennes
directives (asservies), deffectuer du routage gographique, de synchroniser les nuds pour la
datation des donnes.
Ces travaux se sont tendus par la suite pour proposer une solution GPS diffrentielle base sur
un RCSF appele LCD-GPS (Low Cost Differential GPS, Local Cooperative DGPS) qui vise
amliorer la prcision du GPS.
Afin dvaluer cette solution, une plateforme matrielle et logicielle a t dveloppe, elle consiste
en un rseau de capteurs appels LiveNodes (LIMOS Versatile Embedded Node). La partie logicielle
est compose notamment dun systme embarqu appel LIMOS (LIghtweight Multi-threading
Operating System), dun protocole de communication appel CIVIC et des traitements lis la
solution LCD-GPS.
Org an isatio n du mmoi re
Ce mmoire est compos de quatre chapitres organiss comme suit :
Le premier chapitre est consacr ltat de lart de la localisation en gnral et plus
particulirement dans les rseaux de capteurs sans fil. Il commence par montrer limportance de lalocalisation, ses contraintes ainsi que les caractristiques dun systme de localisation. Ce dernier est
considr comme compos de trois sous systmes : un systme destimation des distances/angles
entre les nuds, un systme pour calculer la position relative des noeuds et un algorithme de
localisation qui dfinit la faon dont les informations de localisation sont manipules dans le rseau
afin que la grande partie des nuds puisse se localiser. Ces trois sous systmes sont tudis et
analyss sparment. Par la suite un ensemble de systmes (technologies) de localisation raliss
sont prsents. Le chapitre se termine par la prsentation des mthodes utilises pour amliorer la
prcision car les positions fournies par un systme de localisation sont toujours exposes des
imprcisions.
Le systme de localisation le plus utilis au monde est le GPS en raison de ses multiples
potentialits : localisation mondiale, disponible 24h/24 et 7j/7, position et lheure fournies,
Nos travaux de thse sont bass sur lutilisation du systme GPS civil standard, pour cela le
deuxime chapitre est consacr aux systmes de positionnement par satellites notamment le systme
GPS (amricain). Il prsente entre autres la composition du systme, le principe de positionnement,
les services offerts, les sources derreurs et dimprcisions, les mthodes de correction pour y
remdier : le mode diffrentiel (DGPS, Differential GPS), les systmes daugmentation de la prcision
par satellites et la modernisation du systme GPS. Le chapitre se termine par la prsentation des
7/23/2019 2009CLF21979.pdf
26/195
INTRODUCTION GNRALE
3
systmes (dj raliss ou en cours de ralisation) similaires au systme GPS : GLONASS (russe),
GALILEO (europen) et BEIDOU (chinois).
Le but de notre travail de thse est dexplorer une solution GPS diffrentielle de faible cot visant
amliorer sa prcision notamment en ville. Cette solution est prsente dans le troisime chapitre.
Elle est base sur lutilisation dun rseau de capteurs sans fil quips de rcepteurs GPS civils
faible cot. Le troisime chapitre prsente les fondements thoriques de notre technique appele
LCD-GPS (Low-Cost Differential GPS, Local Cooperatif DGPS). Il expose le principe de la mthode,
les tapes de sa mise en uvre, les exprimentations menes et les rsultats obtenus.
Le quatrime chapitre est consacr la prsentation de la plateforme matrielle et logicielle
utilises dans nos travaux de thse pour valuer les mthodes tudies. Cette plateforme utilise un
rseau de capteurs appels LiveNodes (LIMOS Versatile Embedded Node) raliss localement par
notre quipe de recherche. La partie logicielle est compose notamment dun systme embarqu
appel LIMOS (LIghtweight Multi-threading Operating System) et dun protocole de communicationappel CIVIC (Communication Inter Vhicule Intelligente et Cooprative). Les traitements propres la
solution LCD-GPS prsents dans le troisime chapitre sont intgrs au sein du protocole CIVIC.
Par la suite, les projets qui ont t raliss en se basant sur cette plateforme sont prsents.
Le mmoire se termine par une conclusion et des perspectives sur les travaux raliss au cours de
cette thse.
7/23/2019 2009CLF21979.pdf
27/195
7/23/2019 2009CLF21979.pdf
28/195
5
I SYSTEMES DE LOCALISATION
Ce premier chapitre est consacr aux mthodes et technologies de localisations dune manire
gnrale et plus particulirement la localisation de nuds dans les rseaux ad hoc et les Rseaux
de Capteurs Sans Fil (RCSF). Il aborde la localisation lextrieur ainsi qu lintrieur.
1 Int roduct ion
Un Rseau de Capteurs Sans Fil (RCSF) est compos dun ensemble de capteurs/nudsdont le
nombre peut tre trs grand. Le RCSF est utilis pour raliser une tche spcifique dune application.
Les RCSF sont devenus de plus en plus populaires grce leur large champ dapplicationsciviles et
militaires : environnement, agriculture, mtorologie, sant, domotique
Le but final dun RCSF est de surveiller ou contrler une zone dintrt, mais pour y parvenirplusieurs sous objectifs (services) doivent tre raliss. Parmi ces services : la synchronisation entre
nuds, la localisation, la gestion de la topologie, lagrgation des donnes, le stockage de donnes,
etc.
La localisation des nudsest lun des services les plus importants. Elle consiste dterminer la
position physique (par exemple latitude, longitude et altitude pour le GPS) pour chaque capteur.
Plusieurs domaines ont besoin de la localisation : la robotique, les rseaux ad hoc, les RCSF,
tlphonie mobile, applications militaires, aviation et astronomie.
Ce chapitre prsente les techniques utilises pour la localisation en gnral. Il commence parmontrer limportance de la localisation, ses contraintes, ses proprits et passe ensuite aux
algorithmes utiliss et se termine par donner des exemples de systmes dj raliss.
1.1 Importance des systmes de localisation
Les positions des capteurs peuvent tre prdtermines et prconfigures. Mais, en gnral, les
capteurs ont un dploiement alatoire, car ils sont utiliss sur des terrains inaccessibles, embarqus
sur des engins mobiles ou sur le lieu dun dsastre ou leur nombre (trs grand) ne permet pas de
prconfigurer la position. Pour cela, un systme de localisation est ncessaire afin de fournir auxnudsleurs positions.
Les systmes de localisation sont identifis comme une cl technologique pour le dveloppement
et lutilisation des RCSF. Cependant, leur utilisation nest pas exclusive aux RCSF.
La localisation est importante pour plusieurs aspects, parmi lesquels :
1. Lidentification des donnes collectes:
Cela consiste projeter les donnes/vnements sur la position de collecte/occurrence. Lun
des objectifs majeurs des RCSF est de surveiller une zone dintrt. Cependant, aprs que
les donnes soient collectes, il est important didentifier la rgion do viennent ces donnes.
7/23/2019 2009CLF21979.pdf
29/195
CHAPITRE I SYSTEMES DE LOCALISATION
6
2. Lagrgation des donnes collectes :
Cela permet aux nuds intermdiaires de corrler et de fusionner les donnes qui
proviennent de la mme rgion quand ces donnes sont transmises via le rseau.
3. Ladressage des nuds:
Cela permet dutiliser la position des nuds comme identifiant unique dans le rseau.4. Ladministration du rseau:
Cela permet dadministrer et dinterroger les nuds localiss dans une rgion, valuer la
couverture des nuds, et de gnrer une carte dnergie disponible dans chaque nud [33].
5. Les algorithmes gographiques :
Ce sont des algorithmes qui utilisent linformation de localisation des nuds pour optimiser
lutilisation desressources du RCSF. Parmi ces algorithmes : le routage, le contrle de la
topologie, le contrle de la densit des nuds et le suivi dobjets mobiles (object tracking).
1.2 Contraintes pour un systme de localisation
Un systme de localisation doit respecter un ensemble de contraintes imposes par les spcificits
des RCSF d leurs limitations (ressources matrielles : puissance du processeur, mmoire, nergie)
et applications. Parmi ces contraintes :
1. Auto-organisation:
Les RCSF sont utiliss dans des applications diverses. Dans plusieurs applications (si ce
nest pas la majorit des cas) le RCSF est indpendant de toute infrastructure ce qui implique
que lalgorithme de localisation doit tre distribu. Dans le reste des cas, lalgorithme de
localisation peut tre centralis.2. Evolutivit(extensibilit, chelle) :
Lalgorithme de localisation peut tre appliqu aussi bien un RCSF dense qu un RCSF
avec un nombre rduit de nuds. La plupart des algorithmes de localisation sont sensibles
la densit des nuds; sil ny a pas assez de nuds lalgorithme donne des rsultats
imprcis [5].
3. Robustesse:
Lalgorithme de localisation doit tre tolrant aux problmes de communication ainsi quaux
imprcisions des distances et des positions (des amers
1
) dues notamment aux faits suivants :o Les liens de communications entre deux nuds sont asymtriques. En effet, la
communication entre deux nuds peut passer dans un sens, sans pour autant passer
dans lautre sens.
o Les ondes radio ne se propagent pas de la mme faon dans tous les milieux. Elles
se propagent diffremment sur lherbe (gazon), sable ou sur lasphalte(rflexion et
absorption).
o Les obstacles (environnants) et les irrgularits du terrain : Les obstacles peuvent
cacher les nuds ce qui donne de mauvaises mesures et par consquent une
mauvaise localisation.1Dans la suite, Les mots balise, ancre, amer, station de base et station de rfrence sont utiliss indiffremment.
7/23/2019 2009CLF21979.pdf
30/195
CHAPITRE I SYSTEMES DE LOCALISATION
7
o Topologie non convexe : Les coordonnes des nudsqui se trouvent dans les
extrmits dun RCSF sont souvent moins prcises cause du manque de mesure de
distances. En effet, il ny a pas assez de nuds dans le voisinage et de plus tous les
nuds accessibles sont dans le mme ct [5]. Exemple : Si les capteurs sont
distribus sur un champ rectangulaire, les capteurs qui se trouvent prs des quatrecoins (angles) du rectangle seront mal localiss.
4. Efficacit dans lutilisation des ressources du RCSF:
Mme si le systme de localisation est indispensable pour le bon fonctionnement du RCSF, il
nest pas le but principal du rseau. Il doit utiliser les ressources du capteur dune manire
efficace pour ne pas les puiser. Les concepteurs des algorithmes de localisation doivent
minimiser les cots en termes dnergie, matriel et dploiement de leurs algorithmes de
localisation.
1.3 Proprits dun systme de localisation
Un ensemble de caractristiques (critres) permettent de comparer les systmes de localisation
[1][5][6][27]. Les caractristiques plus importantes sont les suivantes :
1. Position physique et/ou symbolique
Cette proprit dfinit le fait que le systme de localisation fournit aux nuds des positions
physiques (valeurs numriques) par exemple 5m ou des positions symboliques comme une personne
se trouve dans la cuisine, au salon,
Il est possible aussi de combiner des positions physiques avec des positions symboliques.
2. Coordonnes absolues ou relatives
Dans un systme de coordonnes absolues, les positions sont dfinies dans le cadre dune
rfrence globale et commune toutes les positions. Par exemple le systme GPS utilise le systme
de coordonnes WGS842 qui associe chaque position sur terre des coordonnes absolues en
termes de longitude, latitude et altitude.
Les coordonnes relatives sont dfinies par rapport une rfrence commune, mais cette
rfrence nest pas la mme pour tous les nuds ; elle nest donc pas globale. Par exemple, en
France, les positions des villes sont dfinies par rapport Paris et aux Etats-Unis elles sont dfinies
par rapport Washington.
Pour passer des coordonnes relatives aux coordonnes absolues, un ensemble damers est
ncessaires (au moins trois en 2D). Ces amers doivent connatre leurs coordonnes absolues dans
un repre global. Un ensemble de transformations gomtriques (rotation, translation et
ventuellement homothtie) sont ncessaires pour obtenir les coordonnes absolues de tous les
nuds.
2World Geodetic System 1984
7/23/2019 2009CLF21979.pdf
31/195
CHAPITRE I SYSTEMES DE LOCALISATION
8
3. Calcul centralis ou distribu
Cette caractristique fait rfrence lendroit o les positionssont calcules. Est-ce que le calcul
de la position se fait localement par un participant (nud) en se basant sur des mesures effectues
localement ou au contraire les mesures sont envoyes vers une station centrale qui calcule les
positions et les renvoie vers les nudsconcerns.
En outre les aspects de mise lchelle (extensibilit) et defficacit (cot de communication et de
calcul), le respect de la vie prive (lthique) est trs important, il nest pas toujours souhaitable quun
nud rvle sa position un serveur central.
4. Exactitude et prcision
Les deux proprits les plus importantes dun systme de localisation sont lexactitude et la
prcision de ses positions.
Lexactitude est dfinie comme la distance maximale entre la position estime et la position relle
dunobjet (un nud). Une grande exactitude indique un cart maximal rduit.
La prcision est dfinie comme le pourcentage avec lequel lexactitude est obtenue, moyenne sur
un ensemble dexpriencespour dterminer la position.
Les valeurs de lexactitude et de la prcision nont un sens que si elles sont donnes ensemble
formant ainsi la caractristique exactitude/prcision du systme de localisation3.
Par exemple, le Service Standard du GPS a une exactitude de 13m en horizontale (prcision
95%) et 22m en vertical (prcision 95%) [32].
5. Echelle
Un systme de localisation peut tre utilis sur diffrentes chelles. Par exemple pour un
dploiement intrieur lchelle peut tre une pice ou dun immeuble. Pour le dploiement extrieur,
lchelle peut tre un parking ou une couverture mondiale.
Deux mtriques importantes sont :
1- La zone couverte par le systme par unit dinfrastructure. Par exemple, le systme couvre
deux pices.2- Nombre dobjets localisables par unit dinfrastructure et par unit de temps. Par exemple, le
nombre de badges localiss dans une pice chaque seconde.
6. Limites
Certains systmes ont des limites (inhrentes) de dploiement. Par exemple, ils ne fonctionnent
qu lextrieur (GPS) ou lintrieur (systme Active Badge [28][29]). Dautres systmes ont des
portes limites de quelques mtres pour fonctionner correctement (systme MotionStar [3]).
3Par abus de langage, le mot prcision est utilis la place de lexactitude, ce qui signifie que laprcision est 100% et la mesure donne est lexactitude.
7/23/2019 2009CLF21979.pdf
32/195
CHAPITRE I SYSTEMES DE LOCALISATION
9
7. Cot
Les cots dun systme de localisations peuvent tre exprims en termes de :
1- Temps : installation de linfrastructure, administration et maintenance.
2- Espace : la taille de chaque capteur de localisation ainsi que la taille de linfrastructure.
3- Energie : consommation lectrique pour chaque capteur et pour linfrastructure.
4- Budget : cot de chaque capteur, frais dinstallationet de maintenance.
En outre des proprits prcdentes, un systme de localisation peut tre utilis pour des fins
didentification ou de classification dobjets (ou de personnes). Cette information est moins importante
dans le cadre des RCSF ou, si elle est utilise, elle nest pas considre habituellement comme partie
du systme de localisation.
1.4 Composition dun systme de localisation
Un systme de localisation peut tre dcompos en trois parties distinctes. Chaque partie a son
propre objectif et mthodes de rsolution. Elles seront tudies sparment. Ces trois parties (sous-
systmes) sont :
1. Lestimation de distance/angle: Cette partie permet destimer la distance et/ou langle entre
deux nuds. Cette information est utilise par la suite par les deux autres parties (estimation
locale).
2. Le calcul de la position: Cette partie permet destimer la position dun nud en se basant
sur les mesures de distances et/ou dangles disponibles et sur les positions des nuds de
rfrences (ancres, amers) en utilisant la triangulation par exemple.3. Algorithme de localisation: Cest la partie la plus importante du systme de localisation.
Elle dfinit la manire avec laquelle les informations disponibles (distances, angles, positions
des nuds dj localiss) sont manipules afin que la grande partie ou la totalit des nuds
puissent estimer leurs positions.
Les performances du systme de localisation sont directement lies aux performances de chaque
partie. La Figure I-1 illustre la dcomposition du systme de localisation en sous systmes. Les
nuds reprsents par des cercles gris sont des amers, les autres nuds (en blanc) sont des nuds
qui ne sont pas encore localiss. Cette convention restera valable tout au long de ce chapitre.
La suite de ce chapitre traite chacune des trois composantes du systme de localisation en
prsentant, analysant et comparant les mthodes utilises.
La premire partie est consacre lestimation des distances/angles. La deuxime partie prsente
les mthodes de calcul de la position. La dernire partie est consacre aux algorithmes de
localisation. Le chapitre se termine par une discussion gnrale.
7/23/2019 2009CLF21979.pdf
33/195
7/23/2019 2009CLF21979.pdf
34/195
CHAPITRE I SYSTEMES DE LOCALISATION
11
2.1 Indicateur de puissance du signal reuRSSI
La technique de localisation base sur le RSSI utilise la puissance du signal reu pour estimer la
distance entre un nud metteur et un nud rcepteur. La distance est estime en utilisant un
modle de propagation des ondes radio. Plusieurs modles existent ; le plus simple [6] utilise la
formule suivante : : la distance entre les deux nuds. , : la puissance du signal transmis et reu respectivement. : deux constantes connues du modle.
: Le coefficient daffaiblissement du signal radio( par exemple).
: Le rapport entre la puissance du signal reu une distance dun mtre de lmetteuret lapuissance du signal mis.Dautres modles plus complexes existent [2]. En gnral, chaque modle est conu pour un
environnement et un scnario bien dfini.
En pratique, les mesures RSSI sont bruites (de lordre de plusieurs mtres). Ce bruit est d la
propagation donde radio qui nest pas uniforme en environnement rel. Par exemple, les ondes radio
ne se propagent pas de la mme faon dans toutes les directions, ni de la mme faon sur lherbe
que sur lasphalte ou sur dautre matriaux. Les obstacles comme les murs, les meubles et autres
refltent et absorbent les ondes radio. Par consquent, les mesures de distance avec RSSI nont pas
dmontr une bonne prcision par rapport aux autres mthodes de localisation.
Le grand avantage de la mthode est son faible cot car tous les nuds sont dj quips de
dispositif de communication sans fil ; de plus elle ne rajoute aucun surcot de communication. Son
inconvnient est sa sensibilit aux bruits, interfrences, asymtrie du lien de communication (RSSI
non uniforme), obstacles et types dantenne.
Cette mthode peut avoir des erreurs de mesure dpassant 50% de la porte du dispositif de
communication [7]. Plusieurs travaux ont t mens pour amliorer la prcision du RSSI en utilisant
notamment le filtrage pour minimiser les fluctuations des valeurs du RSSI [11][14].
2.2 Le nombre de sautsRHC (Radio Hop Count)
La mthode RHC est base sur le constat suivant : si deux nuds peuvent se communiquer, alors
la distance entre eux est infrieure la porte maximale du dispositif de communication (R, Range)
avec une grande probabilit [5]. Pour la localisation, seulement linformation de connectivit est
utilise, lindicateur depuissance du signal reu nest pas pris en compte.
7/23/2019 2009CLF21979.pdf
35/195
CHAPITRE I SYSTEMES DE LOCALISATION
12
Linformation de connectivit dfinit un graphe non orient dont les sommets sont les nuds du
rseau et les artes reprsentent les liens directs de communication. Le nombre de sauts entredeux nuds et est dfini comme la longueur du plus court chemin entre ces deux nuds.
Si est la distance entre et alors : Si le nombre de voisins est connu, la longueur dun saut peut tre estime(). La distance entre
les nuds i et jdevient :
La prcision de la mthode est la moiti de la porte du dispositif de communication ( R). Nagbal
et al [20] dmontrent par simulation quune prcision de 0.2xR peut tre obtenue si le nombre de
voisins est suprieur ou gal 15.
Dans le cas dexistence dobstructions la mthode donne des rsultats encore moins prcises. En
effet, le nombre de sauts entre deux nuds peut tre grand, mme s ils sont proches lun de lautre
mais un obstacle les spare et qui ne leur permet pas de communiquer directement [5].
2.3 Le temps de parcoursToA/ToF
La technique ToA (Time of Arrival, ToF Time of Flight) exploite la relation entre la distance parcourue
par un signal et le temps de parcours. En effet, la distance entre lmetteur et le rcepteur est la
multiplication du temps pris par le signal avec la vitesse des ondes radio
La vitesse de propagation du signal radio est 3x108m/s.
La technique ToA ncessite la synchronisation parfaite entre lmetteur et le rcepteur [1]. Si lercepteur connat lheure dmission du signal, il peut alors calculer la distance le sparant de
lmetteur en dterminant le temps pris par le signal pour arriver au niveau du rcepteur.
Selon le type du signal utilis, la mthode ToA ncessite, en gnral, des horloges trs grande
rsolution du temps pour obtenir des prcisions acceptables.
Pour les ondes radio, la rsolution du temps doit tre trs leve. Cependant, pour les ondes
sonores, les besoins en rsolution du temps sont modestes, mais leur inconvnient est que leur
vitesse de propagation dpende des conditions extrieures comme la temprature et lhumidit. Un
talonnage rigoureux est donc ncessaire [6].
2.4 La diffrence du temps darriveTDoA
La mthode TDoA (Time Difference of Arrival) a deux variantes :
1. La diffrence du temps pris par un signal envoy par un nud pour arriver au niveau de trois
nuds ou plus. Cette variante est bien connue dans les r seaux cellulaires. Elle ncessite une
synchronisation parfaite des stations de base [1].
2. La diffrence de temps pris par deux signaux envoys par un mme nud pour arriver au
niveau dun autre nud.Chaque nud doit tre quip de deux dispositifs mission/rception.
En gnral, le premier dispositif utilise les ondes radio (vitesse 3x108m/s) et le deuxime
7/23/2019 2009CLF21979.pdf
36/195
CHAPITRE I SYSTEMES DE LOCALISATION
13
utilise les ondes sonores (vitesse 340 m/s la temprature de lair de 15C) ou ultrasonores.
Le premier nud met les deux signaux simultanment. Pour chaque signal reu, le deuxime
nud note son temps darrive et ainsi il peut calculer la diffrence. En gnral, le premier
signal est utilis pour dclencher un compteur et ds larrive du deuxime signal, le nud
aura directement la diffrence de temps darrive. En connaissant les vitesses de propagationdes deux signaux et lcart de temps entre les deux rceptions, le nud rcepteur peut
facilement calculer sa distance par rapport lmetteur.
Pour que la technique soit prcise, les deux nuds doivent tre en visibilit directe. De plus,
lenvironnement ne doit pas favoriser lcho.La Figure I-2 illustre le principe du TDoA.
Figure I-2 Principe du TDoA
Trest le temps darrive du signal radio.
Tsest le temps darrive du signal sonore (ou ultrasonore).
Vsest la vitesse du signal sonore (ou ultrasonore).Cette technique est limite par la distance mesurer (infrieure une centaine de mtres), car on
suppose que le temps de propagation du signal radio est quasiment nul par rapport au temps de
propagation du signal ultrasonore.
2.5 Langle darrive AoA/DoA
A la place des distances, il est possible de localiser un nud en utilisant des angles.
La mthode AoA (Angle of Arrival, DoA Direction of Arrival) permet de mesurer langle darrive dun
signal. Pour cela le nud qui mesure langle doit tre quip soit par un ensemble de petitesdantennes ou plusieurs rcepteurs ultrason [19]. Lorsque un nud reoit un signal, il utilise la
phase ou le temps darrive du signal au niveau de chaque antenne (ou rcepteur ultrason) pour
dduire langle darrive du signal.
La ncessit davoir du matriel supplmentaire ainsi que des distances minimales entre les
diffrents rcepteurs ( ultrason) reprsentent les inconvnients de la mthode en termes de cot et
dencombrement (taille).
La prcision de la mthode est de quelques degrs (environ 5 [20][19]).
T0
Tr Ts
SonRadio
metteur
Rcepteur
7/23/2019 2009CLF21979.pdf
37/195
CHAPITRE I SYSTEMES DE LOCALISATION
14
2.6 La reconnaissance de motifs
Une alternative aux mesures de distances et dangles est lutilisation dune carte prtablie (base
de donnes) de la couverture dun signal aux diffrentes positions de lenvironnement et dutiliser
cette carte pour dterminer la position dun nud particulier en effectuant une reconnaissance de
motif (pattern matching, Location Fingerprinting) sur ses mesures.
Cette mthode ncessite la collecte de mesures empiriques (ou un modle de simulation trs
fidle) de la puissance du signal (moyenne, cart-type, mdiane) des diffrentes stations de rfrence
aux divers endroits o les autres nuds seront par la suite lo caliss. Il est important aussi de prendre
en compte lorientation des nuds car cette dernire peut entraner des variations significatives. Une
fois ces informations collectes, chaque nud dans la zone dintrt est localis (positionn) en
comparant le motif rsultant des signaux reus avec celui qui correspond le mieux sur la carte
prtablie. Cette mthode est trs connue, notamment dans le domaine du traitement dimage.
Pour les signaux radio, cette mthode donne des rsultats meilleurs que les mthodes RSSI etAoA [4].
Linconvnient majeur de cette mthode est quelle est dpendante de lendroit o elle est utilise
et elle ncessite une collecte intensive dinformations avant quelle soit utilisable. De plus elle ne peut
pas tre utilise si les caractristiques radios de lenvironnement sont trs dynamiques.La ncessit
de construire la base de donnes des signatures rend la mthode difficilement ralisable pour la
plupart des scnarios des RCSF.
Le system RADAR [21], dvelopp par un groupe de recherche de Microsoft, utilise cette mthode
de localisation pour lune de ses deux ralisations.
2.7 Autres approches
Certains systmes localisent les personnes (ou les objets) indirectement, sans avoir besoin quils
portent un dispositif de localisation (amers ou rcepteur). Ils utilisent la place limage (apparence
dune personne, vhicule,..), profile de bruit, plateforme de force pour localiser des personnes et/ou
des objets dans leur environnement. Parmi ces systmes on trouve les surfaces instrumentes, la
vision, LIDAR,
2.7.1 Les surfaces instrumentesLinconvnient majeur des mthodes prsentes jusquici est quelles ne localisent que les nuds
(objet, personne quip) qui participe au protocole du systme de localisation et que le systme ne
peut pas localiser dautre objets externes au systme.
Une alternative est dquiper le sol de capteurs (instrumenter la surface) pour localiser des
personnes partir de leurs poids, par exemple.
Schmidt et al [22] utilisent une plateforme de test (240x180 cm) quipe de quatre capteurs de
force installs aux quatre coins de la surface. Ils montrent quen comparant les changements des
forces au niveau des quatre capteurs, ils peuvent estimer la position dun objet avec 10cm deprcision. Mme si le systme est prcis et ne ncessite pas dquiper les usagersde dispositifs de
7/23/2019 2009CLF21979.pdf
38/195
7/23/2019 2009CLF21979.pdf
39/195
CHAPITRE I SYSTEMES DE LOCALISATION
16
plus lev. Ces systmes utilisent un metteur fixe qui envoie des impulsions magntiques et de
plusieurs petits rcepteurs (ports par une personne) qui envoient par radio leurs observations. A
partir de ces observations une position 3D et une orientation (le tangage, le lacet et le roulis) sont
estimes avec une grande prcision et une frquence de mise--jour allant jusqu 120Hz. Le
systme MotionStar4
par exemple estime les positions en 3D avec une prcision de 7.6 mm et de 0.5pour lorientation.
En installant plusieurs rcepteurs (vingt par exemple) sur les diffrents membres et articulations
dune personne, ces systmes permettent de capturer les mouvements en temps rel et avec une
frquence de mise--jour trs leve. Ces systmes sont les plus utiliss pour capturer les
mouvements des personnages (une rplique dune personne relle) utiliss en dessins anims et
dans les jeux vido.
Les inconvnients de ce type de systmes sont les suivants : la limitation de la couverture et le
cot trs lev. En effet, ces systme fonctionnent seulement quand les rcepteurs sont dans un
rayon de 3 mtres de lmetteur; leurs prix minimal est de 50 000$ [3].
2.7.5 LIDAR
Le LIDAR (Light Detection And Ranging, Dtection et tlmtrie par la lumire) est un instrument de
mesure relativement rcent qui a rvolutionn la navigation robotise ces dernires annes [3]. Le
Lidar reprsente une technique de tldtection ou de mesure optique base sur l'analyse des
proprits d'une lumire laser renvoye vers son metteur.
Le LIDAR utilise un systme de balayage avec un laser infrarouge. Le rsultat est une image 2D
prcise sur 180 des distances des objets (obstacles) les plus proches au capteur LIDAR. Parce que
le systme est prcis et quil est indpendant des conditions dclairage, les systmes LIDARs
permettent des robots de se localiser avec une prcision centimtrique dans des environnements
typiquement intrieures.
A cause du prix, de la taille, du poids et du mode de fonctionnement du systme, il ny a pas eu de
systmes personnels portatifs utilisant un LIDAR pour se localiser.
2.7.6 Identification par radio frquenceRFID
La radio-identification5(Radio Frequency IDentifcation)est une technique qui permet d'identifier des
objets, des vhicules, des animaux ou des personnes au moyen d'un dispositif lectronique (Une
tiquette radio (RFID Tag)) transmettant par radiofrquence des informations prenregistres un
lecteur qui l'interroge faible distance.
Les tiquettes RFID sont trs varies mais, gnralement, elles sont conues pour deux
utilisations diffrentes [3] :
1. Sur une courte distance avec un champ dutilisation de quelques centimtres, elles
fonctionnent avec le courant dinduction gnr par le passage devant un lecteur RFID.
4Site web : www.ascension-tech.com5Dfinition donne par le site www.franceterme.culture.fr
7/23/2019 2009CLF21979.pdf
40/195
CHAPITRE I SYSTEMES DE LOCALISATION
17
2. Sur une longue distance, elles fonctionnent habituellement distance suprieure six mtres.
Les deux types dtiquettes sont de petite taille, de faible cot, durables, et comme elles nont pas
de batterie ( changer ou recharger), elles peuvent tre embarques ou mme enfouies dans un
objet.
2.7.7 Ultralarge bandeUWB
UWB6 (UltraWide Band) est un mode de transmission consistant mettre et recevoir des
impulsions extrmement courtes de radiofrquences qui constituent des signaux dont le rapport de la
largeur de bande la frquence centrale est beaucoup plus grand que dans les modulations
employes habituellement.
UWB (IEEE 802.15.4a) est la technologie la plus prometteuse pour la localisation dintrieur. Les
impulsions mises permettent de mesurer le temps de parcours entre lmetteur et le rcepteur et par
consquent pouvoir localiser un badge par exemple.
Les transmetteurs UWB peuvent coexister avec les autres dispositifs sans-fil.
Avec leur cot et consommation faibles, ils reprsentent un bon candidat pour la localisation
courte et moyenne distance. La technologie UWB promet de saffranchir des contraintes nergtique
(consommation lectrique) et les limites de