138025390 Memoire Systeme de Navigation Par GPS

Mmoire de fin dtudes

Pour lobtention du diplme dIngnieur dEtat en Informatique

Option : Systmes Informatiques

Thme :

Systme de navigation automobile par GPS

Organisme daccueil : Eurequat-Algrie

Ralis par : Encadreur :

- ATTIG Asma - Mer

Souici Boualem

- BAKIRI kamelia Promoteur :

- Mer

Kazi Malik

Soutenu le 04/10/2012

Devant le jury compos de :

- Mer

AIT AOUDIA

-Mme MEZIANI

Promotion 2011/2012


ii

Remerciement

Nous prsentons nos remerciements les plus sincres nos deux Encadreurs

Monsieur Souici Brahim et Monsieur Kazi Malik, pour leur disponibilit et leur

encadrement, ainsi que pour leur soutien et leurs patiences tout au long de lanne.

Cest grce eux que nous avons pu mener bien ce travail.

Nous prsentons nos gratitudes aux membres du jury qui ont bien voulu

examiner et valuer notre travail et qui nous font lhonneur de participer la

soutenance.

Un grand MERCI tous les enseignants de lEcole nationale Suprieure

dInformatique ESI qui nous ont forms durant ces cinq dernires annes.

Nos remerciements vont aussi tous ceux qui ont contribu de prs ou de loin

la concrtisation de ce travail.

Merci tous


iii

Ddicace A mes chers parents,

A ma sur Yasmine,

A mon adorable frre Idir,

A ma chre cousine Nadia pour son soutien et son encouragement,

A toute ma famille,

A mon binme et amie Asma ,

A tous mes amis,

A tous ceux qui ont pu contribuer dune manire ou dune autre la ralisation

de ce modeste travail

Je vous le ddie .

Camlia


iv

Ddicace

Je remercie Dieu tout puissant de nous avoir permis dachever ce travail que je

ddie

Aux personnes les plus chres mon cur,

Les plus importantes dans ma vie,

Aux personnes qui mont faites ce que je suis,

Mes parents,

Mes surs et mes nices,

Mon cher binme Cami,

Mes amis.

Asma


v

Rsum ctuellement, nous vivons un trs grand progrs des nouvelles technologies et plus

prcisment les technologies de la communication qui connaissent un formidable

essor. Ces diffrents progrs ont conduit la cration du systme GPS Global

Positioning System qui est un systme servant dtecter tout moment la position

en latitude et longitude dun mobile se trouvant sur la surface de la terre et ce avec

une trs bonne prcision. Depuis sa cration le GPS a connu diffrentes applications

telles la scurit, la navigation maritime, laviation et la navigation routire (automobile).

Cette dernire se trouve tre son application la plus connue du grand public.

Les systmes de navigations automobiles sont des systmes axs sur la localisation de

lemplacement gographique dun mobile et la planification ditinraires allant de cette

position une destination prcise tout en indiquant lutilisateur les instructions suivre pour

atteindre sa destination. Litinraire propos doit tre optimal i.e. il doit reprsenter le chemin

le plus court ou le plus rapide existant entre les deux points. En outre, la navigation GPS en

temps rel est la solution pour naviguer dun point A un point B en prenant un chemin

optimis, qui est calcul grce aux cartes numriques.

Le prsent travail consiste en la conception et la ralisation dun systme de navigation

automobile temps rel pour appareils mobiles utilisant un algorithme amlior pour la

planification de litinraire optimal.

En utilisant la technologie GPS pour le positionnement et les cartes numriques fournies par

lorganisation OpenStreetMap (OSM), nous avons ralis un systme qui permet de naviguer

entre deux points se trouvant sur la surface de la terre. De plus, notre solution est

spcialement conue pour convenir la navigation en Algrie et offrir une bonne exprience

lutilisateur en retournant des rsultats exacts tout en ayant un temps de rponse acceptable.

Mots cls : GPS, Navigation routire, planification ditinraires, cartographie numrique,

OSM (OpenStreetMap), Windows mobile.

A


vi

Abstract

urrently, we live in a great progress of new technologies and more specifically

communication technology. These advances have led to the creation of GPS "Global

Positioning System" which is a system for detecting the position at any time (latitude,

longitude) of a mobile on the surface of the earth and with a good accuracy. Since its

inception, the GPS has undergone various applications such as security, maritime, aviation

and road navigation (automobile). The latter happens to be his best-known application of the

general public.

Car navigation systems are based on the geographic location of a mobile route planning from

this position to a specified destination while indicating to the user instructions on how to

reach its destination. The proposed route should be optimal (it must represent the shortest path

or the fastest between the two points). In addition, real-time GPS navigation solution is to

navigate from point A to point B by taking an optimized path, which is calculated using

digital maps.

This work involves the design and construction of a car navigation system for mobile real-

time using an improved algorithm for optimal route planning.

Using GPS technology for positioning and digital maps provided by the organization

OpenStreetMap (OSM), we developed a system that allows you to navigate between two

points on the surface of the earth. In addition, our solution is specifically designed to suit the

navigation Algeria and provide a good user experience by returning accurate results while

having an acceptable response time.

Keywords: GPS, Navigation Road, route planning, digital mapping, OSM (OpenStreetMap),

Windows Mobile.

C

SPG rap elibomotua noitagivan ed emtsyS

iiv

.

) ( " " SPG

.

( .

SPG )

.

.

)MSO( SPG

.

.

) MSO ( SPG :

.


viii

Table des matires Table des matires ........................................................................................... vi

Liste des figures ............................................................................................ xiii

Liste des tableaux ........................................................................................... xv

Introduction gnrale ....................................................................................... 1

Chapitre I:Gnralits sur les systmes de navigation automobile

I.1-Introduction ................................................................................................ 5

I.1.1-Dfinition de la navigation ............................................................................................. 5

I.1.2-Dfinition des systmes de navigation ........................................................................... 5

I.2-Dfinition dun systme de navigation automobile ..................................... 6

I.3-Historique ................................................................................................... 6

I.4-Navigation automobile en Algrie .............................................................. 6

I.4.1-Organisation OSM (Open Street Map) .......................................................................... 7

I.5-Types de systmes de navigation automobile ............................................. 7

I.5.1-Systme de navigation inertielle .................................................................................... 7

I.5.2- Systme de navigation radio ......................................................................................... 7

I.6-Fonctions et services ................................................................................. 10

1-Rapports de trafic en temps rel ........................................................................................ 10

2-Les points dintrts (POI) ................................................................................................ 10

3-Waypoints .......................................................................................................................... 10

I.7-Les composantes cls dun systme de navigation automobile.................. 11

I.7.1-Positionnement ............................................................................................................. 11

I.7.2-Planification d'itinraires ............................................................................................. 13

I.7.3-La base de donnes ...................................................................................................... 14

I.7.4-Interface utilisateur ...................................................................................................... 14

I.8-Evaluation des performances dun systme de navigation automobile ...... 14

1-La prcision (exactitude) ................................................................................................... 14

2-L'intgrit .......................................................................................................................... 14

3-Disponibilit ...................................................................................................................... 14

4-Continuit de service ......................................................................................................... 14

I.9-Conclusion ................................................................................................ 15

Chapitre II: Gnralits sur les techniques de positionnement et le GPS

II.1-Introduction ............................................................................................. 17


ix

II.2-Gnralits sur la golocalisation ........................................................... 17

II.2.1-Dfinition de la golocalisation .................................................................................. 17

II.2.2-Les composantes dun systme de golocalisation ..................................................... 17

II.2.3-Techniques de positionnement ................................................................................... 17

II.3-Prsentation du systme GPS .................................................................. 18

II.3.2-Structure physique ...................................................................................................... 18

a. Le segment espace ......................................................................................................... 19

b. Le segment de contrle ................................................................................................. 19

c. Le segment utilisateur ................................................................................................... 20

II.3.3-Les applications du GPS ............................................................................................. 20

a. Usages militaires ........................................................................................................ 20

b. Usages civils ................................................................................................................ 20

II.3.4-Dtermination d'une position par GPS ....................................................................... 21

a. Systme godsique ................................................................................................... 21

b. Les coordonnes gographiques ................................................................................ 21

c. La projection .............................................................................................................. 22

d. La triangulation .......................................................................................................... 23

e. La mesure de la distance ........................................................................................... 24

f. Le positionnement des satellites ................................................................................ 25

g. Les erreurs de positionnement ................................................................................... 25

II.3.5-Les rcepteurs GPS .................................................................................................... 25

II.4.1-Le DGPS ..................................................................................................................... 26

a. Dfinition du GPS diffrentiel .................................................................................. 26

b. Fonctionnement du DGPS ......................................................................................... 26

II.5-Les inconvnients de la navigation GPS .................................................. 26

II.6-Approches ............................................................................................... 27

II.7-Conclusion .............................................................................................. 28

Chapitre III : Etude sur les systmes de guidance

III.1-Introduction............................................................................................ 30

III.2-Formulation du problme ....................................................................... 30

III.3-Modlisation du problme ...................................................................... 31

III.3.1-Reprsentation graphique du rseau routier .............................................................. 31

a. Modle indpendant du temps ................................................................................... 31


x

b. Modle dpendant du temps ...................................................................................... 33

III.4-Approches et solutions ........................................................................... 33

III.4.1-Les diffrentes tudes menes cet effet .................................................................. 34

III.4.2-Algorithme de Dijkstra .............................................................................................. 35

a. Concept de lalgorithme de Dijkstra .......................................................................... 35

b. Description de lalgorithme ...................................................................................... 35

c. Complexit de lalgorithme (valuation) ................................................................... 36

III.4.3-Algorithme A* ........................................................................................................... 36

a. Concept de lalgorithme ............................................................................................ 36

b. Description de lalgorithme ...................................................................................... 37

c. Complexit de lalgorithme ....................................................................................... 38

III.4.4-Algorithmes Gntiques ............................................................................................ 38

a. Dfinition ................................................................................................................... 38

b. Concept de lalgorithme ............................................................................................ 38

c. Algorithme itratif utilisant un GA ........................................................................... 39

III.4.5-Algorithmes de planificateur d'itinraire standard .................................................... 39

a. Concept de lalgorithme ............................................................................................ 39

III.6-Comparaison .......................................................................................... 40

III.7-Amlioration .......................................................................................... 41

III.7.1-Variantes de Dijkstra ................................................................................................. 41

a. Algorithme de recherche restreinte ............................................................................ 41

b. Utilisation des tas de Fibonacci ................................................................................. 43

c. Algorithme de Dijkstra bidirectionnel ....................................................................... 45

III.7.2-Techniques dacclration ......................................................................................... 45

a. Les hirarchies des routes .......................................................................................... 45

b. Le partitionnement ..................................................................................................... 47

III.8-Choix dune technique ........................................................................... 48

III.9-Conclusion ............................................................................................. 50

chapitre IV: Conception et modlisation

IV.1-Introduction ........................................................................................... 52

IV.2-Architecture de lapplication .................................................................. 53

IV.2.1-Architecture gnrale ................................................................................................ 53

a. Partie Desktop ............................................................................................................ 54


xi

b. Partie mobile .............................................................................................................. 55

c. Utilit des prtraitements pour la partie mobile ........................................................ 55

IV.2.2-Architecture applicative ............................................................................................ 56

IV.3-Conception des modules ........................................................................ 60

IV.3.1- Module de Prtraitements ........................................................................................ 60

a. Format des donnes ................................................................................................... 60

b. Carte ........................................................................................................................... 62

c. Graphe de routage ...................................................................................................... 62

d. Rendu des tuiles ......................................................................................................... 63

IV.3.2 -Module de Positionnement ....................................................................................... 65

IV.3.3-Module de Routage ................................................................................................... 66

a. Calcul du chemin optimum ........................................................................................ 66

b. Instructions de routage ............................................................................................... 67

c. Calcul de la distance .................................................................................................. 67

IV.3.4 -Module de Rendu graphique .................................................................................... 68

IV.3.5 -Module de Recherche dadresse............................................................................... 69

IV.4-Modlisation UML ................................................................................ 69

IV.4.1-Diagramme des cas dutilisation ............................................................................... 69

a. Description textuelle .................................................................................................. 70

IV.4.2-Le diagramme des squences .................................................................................... 72

IV.5-Conclusion ............................................................................................. 76

Chapitre V:Ralisation

V.1-Introduction ............................................................................................. 78

V.2-Choix des technologies de dveloppement .............................................. 79

V.2.1-Partie Prtraitement (Module de prtraitement) ......................................................... 79

1. Environnement de dveloppement (Visual Studio 2010) ............................................. 79

2. Langage de programmation (C# 2010) ......................................................................... 80

V.2.2-Partie Mobile .............................................................................................................. 80

V.3-Base de Donnes ..................................................................................... 82

V.4-Prsentation de linterface et mode de fonctionnement ............................ 86

V.4.1 Prtraitement ............................................................................................................... 86

1. Authentification ............................................................................................................ 86

2. Gnration de la base de donnes ................................................................................. 86


xii

3. Mis jour ...................................................................................................................... 87

4. Gnration des tuiles ..................................................................................................... 88

V.4.2 Mobile client ............................................................................................................... 88

1. Navigation ..................................................................................................................... 89

2. Edition des POI ............................................................................................................. 91

V.5-Conclusion .............................................................................................. 93

Conclusion gnrale ....................................................................................... 94

Perspectives ................................................................................................... 96

Annexes .......................................................................................................... 97

Bibliographies .............................................................................................. 106

Webographies .............................................................................................. 110


xiii

Liste des figures Chapitre I: Gnralits sur les systmes de navigation automobile

Figure nI.1 : Systme de navigation automobile hybride ........................................................ 8

Figure nI.2 : Systmes de navigation automobiles (PNA, PDA, Smartphone) ....................... 9

Figure nI.4 : Rseau routier dcrit par le modle planaire .................................................... 12

Figure n I.5: Zone de recherche du map-matching ............................................................... 13

Chapitre II: Gnralits sur les techniques de positionnement et le GPS

Figure nII.1: la constellation GPS ......................................................................................... 18

Figure nII.2: Les trois segments du systme GPS ................................................................. 18

Figure nII.3 : Segment spatial ................................................................................................ 19

Figure n II.4: Rseau de contrle ........................................................................................... 20

Figure nII.5 : Coordonnes gographique ............................................................................. 21

Figure nII.6: Principales surfaces de projection, cne, cylindre, plan ................................... 23

Figure n II. 7: Diagramme de sphre ..................................................................................... 23

Figure nII.8: intersection de deux sphres ............................................................................. 23

Figure nII.9 : la triangulation ................................................................................................. 24


Figure n III.1 : Exemple de multi-graphe orient ................................................................... 32

Figure nIII.2 : Exemple de zones de recherche utilises par le RP-algorithme ..................... 40

Figure nIII.3 : Zone de recherche de lalgorithme restreint ................................................... 42

Figure nIII.4 : Zone de recherche restreinte laide dun hexagone dynamique ................... 43

Figure n III.5 : Tas de Fibonacci 5 arbres (Tas) et 14 nuds .............................................. 44

Figure nIII.6: Reprsentation des zones de recherche du bidirectionnel algorithme ............. 45

Figure nIII.7: Recherche dans un rseau utilisant la technique de hirarchisation 47

Figure nIII.8 : Graphe dun rseau routier ............................................................................. 47

Figure nIII.9 : Sur la gauche une reprsentation du rseau routier partitionn en cellule et sur

la droite la connexion de ces cellules ...................................................................................... 48

Chapitre IV : Conception et modlisation

Figure n IV.1: ARCHITECTURE GENERALES DE ALGPS ...................................................... 54

Figure nIV.2 : Schma illustratif de lutilit de chaque prtraitement pour les modules

mobiles ..................................................................................................................................... 55

Figure nIV.3 Schma simplifi dune application mobile .net multicouches . ....................... 57

Figure nIV.4 : Architecture applicative de ALGps .......................................................... 59

Figure nIV.5: OpenStreetMap Node ...................................................................................... 60

Figure nIV.6: Open Street Map way ...................................................................................... 61

Figure nIV.7 : OPEN STREET MAP RELATIONS ......................................................................... 61

Figure nIV.8 : Utilisation de Mapnik ..................................................................................... 64

Figure nIV.9 : Gnration des tuiles pour diffrents niveaux de zoom .................................. 65

Figure nIV.10 : Exemple du graphe de routage ...................................................................... 67

Figure nIV.11 : Diagramme des cas dutilisation ................................................................... 70

Figure nIV.12: Diagramme des squences de ldition des prfrences ................................ 73

Figure nIV.13 : Diagramme des squences de ldition des POIs ......................................... 74

Figure nIV.14 : Diagramme des squences de la navigation .................................................. 75


xiv

Chapitre V : Ralisation

Figure nV.1 : Logo de Visual Studio 2010 ............................................................................. 79

Figure n V.2 : Logo de Microsoft Expression Blend 4 ........................................................... 80

Figure n V.3 : Le Motorola MC65 ......................................................................................... 81

Figure n V.5 : Logo de Visual Studio 2008 ............................................................................ 82

Figure n V.6 : Extrait dun nouveau chemin .......................................................................... 83

Figure n V.7 : Reprsentation dune wilaya .......................................................................... 84

Figure n V.8 : Reprsentation dune ville ............................................................................... 84

Figure n V. 9 : Reprsentation dun village .......................................................................... 84

Figure n V.10 : Reprsentation dune srie de rue ................................................................ 84

Figure n V.11 : exemple de point dintrt [extrait de notre base de donnes ....................... 85

Figure n V.12 : Tuiles composant une carte de lAlgrie de zoom 12 ................................. 85

Figure n V.13 : Tuiles composant une carte de lAlgrie de zoom 8 .................................... 85

Figure n V.14 : authentification utilisateur ............................................................................. 86

Figure n V.15 : Interface gnration base de donnes ............................................................ 87

Figure n V.16 : Interface graphique de la mise jour ............................................................ 87

Figure n V.17 : Interface graphique du tlchargement des tuiles ......................................... 88

Figure n V.18 : Interface graphique de la page daccueil dAlGps ........................................ 89

Figure nV.19 : Recherche graphique de la recherche par POI ............................................... 90

Figure nV.20 : Recherche de POI dans la catgorie Restauration .......................................... 90

Figure nV.21 : Interface graphique de la recherche dadresse ............................................... 91

Figure n V.22 : Interface graphique de ldition dun POI ..................................................... 92

Figure n V.23 : Interface graphique de lajout dun POI ........................................................ 92


xv

Liste des tableaux


Tableau nIII.1 : Tableau reprsentant la complexit des oprations ................ 44

Chapitre IV : Conception et modlisation

Tableau nIV.1: Tableau rsumant les balises importantes ainsi que leurs

significations....71


Introduction gnrale

epuis sa venue sur terre, ltre humain a toujours cherch un moyen de se situer sur

sa plante. Au dbut il utilisa les astres pour se guider sur mer et sur terre. Ensuite

vinrent les progrs gographiques et mathmatiques qui ont apport le

dveloppement de cartes terrestres de plus en plus prcises.

Si on revenait dix ans en arrire, la cartographie routire et les itinraires imprims

dinternet semblaient tre notre seule solution, puis vint le temps des systmes de navigation

automobile souvent plus connus sous le nom de GPS, ce fut une norme rvolution dans le

domaine de la navigation. En grande partie cette rvolution est due aux normes progrs

quont connus les technologies de communications avec la cration du systme GPS et la

cartographie numrique. Depuis les systmes de navigation sont devenus des gadgets banals

quon utilise au quotidien grce la multitude davantage offerts par ces systmes tels le gain

de temps et dargent ainsi que lamlioration de la scurit et la gestion des situations

durgence.

Aujourdhui, la technologie GPS a rvolutionn plusieurs domaines grce la trs bonne

prcision quelle apporte lors de la dtermination de la position gographique dun mobile.

Daprs Jean-Luc Cosandier [COS 03], la prcision atteinte par cette technologie varie

dune centaine de mtres quelques mtres et cela dans 95% des cas. Ainsi elle permet de

go-localiser tout mobile se trouvant sur la surface de la terre et cela quelques soient le

moment et lendroit o il se trouve.

En quelques mots, les systmes de navigation automobile sont des systmes intelligents

permettant de localiser un vhicule avec une prcision phnomnale, en utilisant les

diffrentes techniques de localisation et de proposer litinraire le plus court ou le plus rapide

pour se rendre une destination prcise ainsi que diffrentes informations utiles la

navigation et cela en offrant une navigation en temps rel et une interface graphique

conviviale.

En dautres termes, les systmes de navigation automobile sont une combinaison entre

diffrents domaines allant de la go-localisation, la cartographie numrique et la

communication la recherche oprationnelle.

Notre projet consiste en la conception et le dveloppement dun systme de navigation routier

par GPS qui se prsente comme une application mobile destine tre dploye sur un PDA.

Notre application doit apporter une solution qui permet de naviguer dun point A un point B,

en indiquant le chemin optimal tout en effectuant un suivi en temps rel et continu du chemin

emprunt.

Notre systme se doit dtre performant et de garantir des rsultats exacts. En fait, le

dveloppement dapplications mobiles de ce type est confront plusieurs contraintes qui

sont relies la limitation de la vitesse de calcul de lappareil mobile et de la mmoire.

D


2

Gnralement, dans la plus part des systmes commercialiss ces contraintes sont pallis en

apportant des modifications lalgorithme utilis dans la planification ditinraire. Cependant

ces modifications ne garantissent pas un rsultat exacte ce pour quoi dans notre travail nous

allons prendre le soin de choisir le meilleur algorithme de calcul tout en amliorant sa vitesse

de calcul sans affecter lexactitude des rsultats.

En outre, le dveloppement de notre application est ax sur les points suivants :

Gestion des points dintrt (POI) par catgorie : Tous les points dintrts utiliss par

notre application doivent tre classs et stocks dans notre base de donnes selon leur

type.

Recherche dadresses, de point dintrts (POI) : Notre application doit mettre la

disposition de ses utilisateurs un outil qui permet deffectuer une recherche dadresse

ou de POI afin que celui-ci puisse indiquer sa destination sans avoir recours

introduire les coordonnes de sa destination.

Recherche du chemin le plus court, le plus rapide : le chemin qui sera indiqu

lutilisateur doit tre un chemin optimal.

Navigation en temps rel : Effectuer un suivi temps rel des positions prises par le

mobile et indiquer lutilisateur la prochaine manuvre suivre tout en lui donnant une

vision graphique de la position et de la trajectoire du vhicule et cela chaque

changement de position.

Recalcule du chemin en cas de dviation du chemin prdfini : Effectuer un suivi en

temps rel de la trajectoire du mobile et dtecter si le conducteur sest dvi du chemin

prdfini et ainsi recalculer le nouveau chemin qui doit tre pris par lutilisateur.

Nous avons divis notre mmoire en deux parties, une partie tat de lart qui est constitue de

trois chapitres et une partie conception et ralisation constitue de deux chapitres.

La Partie tat de lArt

Comme cit prcdemment cette partie est compose de trois chapitres et consiste en

une tude bibliographique sur les systmes de navigation en gnral. Le premier

chapitre stalera sur les gnralits relatives aux systmes de navigation automobile,

le deuxime portera sur la technique de positionnement savoir le GPS, le troisime

chapitre est une tude sur les systmes de guidance et au cours de celui-ci nous allons

dtailler les algorithmes de calcul du chemin optimal.

La Partie Ralisation et Conception

Au cours de cette partie nous allons aborder laspect technique de notre projet. Pour

dbuter nous prsenterons la conception de la solution que nous avons adopte pour le

dveloppement de notre application ainsi que sa modlisation en utilisant le modle

UML. Puis, nous prsenterons les diffrents outils choisis pour la ralisation de notre


3

projet et nous finirons par une conclusion gnrale des perspectives o nous

aborderons les objectifs atteints et les diffrentes amliorations possibles de notre

solution.

Gnralits sur les systmes de navigation automobile

Chapitre I



5

I.1-Introduction ctuellement, un nombre croissant de consommateurs a suscit un rel intrt pour les

quipements de navigation automobile. Effectivement les systmes de navigation

automobile se taillent une place importante sur le march et ne sont plus des gadgets

de luxe rservs pour les riches [FLI 04]. Daprs le centre de recherche japonais

Yano Reaserch Ltd en janvier 2011, La taille du march mondial des systmes de

navigation automobile tait de 9,8 million dunits, et devrait crotre de faon

constante de 2010 2015 avec une croissance annuelle dun taux de 10,7 %, pour atteindre

16.32 millions dunits en 2015 .

Tout cet intrt pour les systmes de navigations routiers est d leurs efficacits et aux

diffrents avantages quils apportent tels que le gain de temps et lconomie dargent. La suite

de ce chapitre est une introduction au domaine de la navigation automobile car il sera

consacr aux gnralits des notions de ce domaine.

Avant dentamer les gnralits sur les systmes de navigation automobile (Routiers) nous

expliquerons ce que lon veut dire par le mot navigation et cest quoi un systme de

navigation ? Afin de mieux introduire le sujet.

I.1.1-Dfinition de la navigation Naviguer consiste, au sens originel, se dplacer ou voyager sur l'eau. Par extension

logique, ce terme qualifie galement l'art et la science de conduire un navire. Ultrieurement,

la notion de navigation s'est tendue aux domaines arien, terrestre et spatial [1].

I.1.2-Dfinition des systmes de navigation En gnral, un systme de navigation est lensemble des techniques permettant de localiser la

position dun mobile par rapport un systme de rfrence et de fournir toute information

ncessaire au contrle et loptimisation des dplacements et du chemin du navigateur quil

soit arien, maritime ou terrestre ce qui nous amne distinguer trois systmes de

navigation [16]:

1) Arien : Ce premier est un systme destin au domaine de laviation autrement dit il

est spcialement conu pour fonctionner sur les avions, hlicoptres, aroplanes, et il

peut tre autonome et automatique.

2) Maritime : lune des premires utilisations des systmes de navigation tait bord des

bateaux. Cela tait d la complexit du processus dapprentissage et de lecture des

cartes marines.

Aujourdhui les systmes de navigation maritime sont devenus communs aux bateaux

de toutes tailles et sont utiliss mme par les pcheurs amateurs et professionnels.

3) Automobile (Routier) : Cest le systme de navigation le plus connu aux yeux du

public. La plupart des cas il est destin une utilisation dans lautomobile cependant

il peut aussi tre utilis pour la navigation pdestre dans le cas de systme mobile.

A


6

I.2-Dfinition dun systme de navigation automobile Selon Myron Kayton : Un systme de navigation automobile est un systme capable de

dterminer la position et la vitesse du centre de masse d'un vhicule et doffrir une certaine

orientation au conducteur (pilote) .

En gnral, il utilise un utilitaire de localisation et une base de donnes contenant les cartes

numriques pour fournir des informations utiles la navigation [4].

Lutilitaire de localisation sert acqurir diffrentes informations concernant la

position de l'utilisateur sur le rseau routier.

la base de donnes contient diverses cartes numriques reprsentant le rseau routier

ainsi que les informations ncessaires la navigation.

Il offre aux conducteurs des itinraires en temps rel, et des annuaires des restaurants,

hpitaux, services de voitures, et autres points d'intrt (POI), et des alertes Vocales qui

aident le conducteur maintenir son attention sur la route. Cela est diffrent du tracking qui

est un processus destin au contrle (vitesse, trajectoire,..) et suivi des vhicules via un

terminal [NEB 06].

I.3-Historique Les systmes de navigation automobile ont fait l'objet d'exprimentation tendue y compris

des efforts pour atteindre des marchs grand public.

Selon la propre chronologie historique de la socit (chronologie historique alpin 1981),

Alpin rclame avoir cr en collaboration avec HONDA le premier systme de navigation

pour voiture en 1983 [10].

Avec le dveloppement des technologies de la tlcommunication plusieurs systmes ont vu

le jour comme le systme cr par Steven Lobbezoo base de navigation par satellite en

1986, les systmes de navigation par GPS qui sont conus par Mitsubishi Electric et Pioneer

en 1990 et ceux conus par Oldsmobile et Magellan en 1995 [17].

Cependant, il fallait attendre jusqu'en 2000 pour que les Etats-Unis ddient un signal GPS

pour des fins uniquement civiles ce qui a contribu en les expansions du domaine de la

navigation et la cration de diffrents utilitaires ddis cet usage. En effet, de nos jours,

pratiquement tous les constructeurs automobiles proposent un systme de navigation comme

option sur leurs vhicules. Nanmoins ce domaine n'est plus exclusif aux constructeurs

automobiles car plusieurs socits spcialises dans les systmes de navigation par GPS

mobiles ont vu le jour comme Garmin en 1998, TomTom en 2001 etc.

I.4-Navigation automobile en Algrie A notre connaissance, jusquau moment de la rdaction de ces lignes les systmes de

navigation routier restent quasiment inexistants en Algrie, cela est d plusieurs facteurs

cependant l'Absence d'une carte dtaille du territoire national est lun des problmes majeurs.


7

En effet, les seules cartes disponibles sont dtenues par l'INC (Institut National de la

Cartographie) et ne sont utilises que dans le domaine de la golocalisation. Mais avec la

venue de l'organisation OSM (Open street MAP) la cartographie ne devrait plus poser de

problmes car cette dernire met la disposition des utilisateurs des cartes numriques

utilisation libre. Ce qui devait tre une trs bonne opportunit pour les ralisateurs des

systmes de navigation car l'Algrie reprsente un grand march (vu le nombre de

consommateur) et sans oublier l'absence de la concurrence qui est un facteur trs important.

I.4.1-Organisation OSM (Open Street Map) OpenStreetMap est une organisation internationale qui cre et fournit des donnes

gographiques libres et sous une licence libre, telles que des cartes routires ou cyclables,

toute personne qui en aura besoin. Cet outil est initi en juillet 2004 par Steve Coast au

College University de Londres dans le but de rendre la cartographie accessible tout le

monde car la plupart des cartes ont des restrictions lgales ou techniques qui empchent de

les utiliser de faon crative, productive ou innovante [15].

Note : Pour plus dinformation sur lorganisation OpenStreetMap consultez rfrence [15].

I.5-Types de systmes de navigation automobile Les systmes de navigation automobile peuvent tre classifis selon la technologie utilise

lors de la localisation du vhicule. Daprs Myron Kayton (Navigation systems, 2001) les

systmes peuvent tre classs comme suit :

I.5.1-Systme de navigation inertielle Les systmes de navigation inertielle sont les systmes les plus prcis utilisant le principe du

Dead-rocking. Ils ont t dvelopps pour une large gamme de vhicules et sont les

premiers systmes commercialiss dans le domaine de la navigation automobile [MYR 01].

a. Dead-rocking

C'est le calcul de la position gographique du vhicule partir des informations du

capteur talonn, et cela en prenant une srie continue de mesures commenant avec

une valeur initiale connue. Ces systmes doivent tre rinitialiss quand les erreurs

s'accumulent et si il y a eu une perte dnergie [MYR 01].

b. Les mesures inertielles

Dans la navigation inertielle un acclromtre est utilis pour mesurer les

acclrations du vhicule tandis quun gyroscope mesure lorientation des

acclromtres ; ensuite un ordinateur de bord utilise ces donnes dans ses calculs

afin de dterminer la position et la vitesse du vhicule [MYR 01].

I.5.2- Systme de navigation radio Un systme radio est constitu dun rseau dmetteurs (parfois aussi des rcepteurs) sur le

sol ou dans les satellites. Gnralement les GNSS (Global Navigation Satellite System) sont

les plus utiliss dans ce type de navigation, en particulier le systme Amricain GPS Navstar

[MYR 01].


8

Un vhicule dtecte la transmission radio et calcule sa position par rapport aux positions

connues des stations mettrices. La vitesse est calcule partir du dcalage Doppler de la

transmission ou dune squence de positions. Le dcalage Doppler est la diffrence entre la

frquence du signal reu et celle du signal mis et cela lorsque le rcepteur et lmetteur sont

en mouvement lun par rapport lautre [22].

Contrairement aux systmes de navigation inertielle, les systmes radio peuvent tre intgrs

dans le tableau de bord du vhicule ou mobile grce aux PDA et Smartphone.

a. Systmes intgrs (embarqus)

Rservs quelques privilgis il y a de cela quelques annes en effet daprs J. D.

Power en 2002 la moyenne du taux d'adoption des systmes de navigation

embarqus, sur le march amricain, est simplement rest moins de 2% et cela

est d en premier lieu aux cots onreux de celui-ci. Dsormais les systmes de

navigation font partie des plus importantes options intgres un vhicule.

Gnralement constitus dun cran LCD et dun microprocesseur assez

performant afin deffectuer les diffrents calculs, ces derniers sont intgrs au

tableau de bord du vhicule et utilisent aussi le systme radio du vhicule pour la

lecture des cartes numriques stockes sur CD ou DVD ainsi que des rcepteurs

radios [FLI 04].

Un avantage cl des systmes de navigation embarqus, cest leur capacit relier

plusieurs services diffrents ainsi que la possibilit dintgr les techniques de

navigation inertielle et en faire un seul systme hybride (radio et inertiel) la figure

nI.1 donne un aperu des principaux lments d'un systme de ce type. Sur la

gauche on a les capteurs (gyroscope et tachymtre) et un satellite GPS pour la

dtermination de la position. Un cran LCD pour laffichage, Un lecteur de CD ou

de DVD. Sur la droite, une connexion GSM et diffusions de RDS-TMC utilises

pour les informations concernant le trafic.

Figure nI.1 : Systme de navigation automobile hybride [FLI 04]

b. Systmes mobiles

Daprs le TCS (Tourning Club Suisse) Les systmes de navigation mobiles sont

aussi fiables que les systmes embarqus et sont dune utilisation moins complexe.

En effet, le TCS affirme que les systmes mobiles sont faciles utiliser grce au


9

fait quils runissent dans le mme botier le logiciel de navigation, le matriel

cartographique numris et enregistr sur un priphrique de stockage ainsi que le

rcepteur GPS. Si les systmes mobiles ont autant progress cest bien grce aux

nouvelles crations comme les PNA (Personnel Navigation Assistant) dvelopps

par les socits spcialises dans la navigation ainsi que les PDA et Smartphones

[TCS05].

Figure nI.2 : Systmes de navigation automobiles (PNA, PDA, Smartphone) [TCS 09]

i. La navigation avec les PNA Les PNA sont les premiers systmes de navigation mobiles qui ont t

commercialiss. Leur invention a permis dtendre lexploitation des navigateurs GPS

au grand public. Ces navigateurs sont aussi performants que les navigateurs

embarqus, faciles et simple manier [TCS 09].

ii. La navigation avec PDA Ce type de navigation consiste utiliser un ordinateur de poche type PDA (Personal

Digital Assistent).Ces appareils peuvent tre quips peu de frais dun rcepteur

radio (GNSS) et dun logiciel de navigation. Lutilisateur doit cependant avoir

quelques connaissances en informatique pour faire fonctionner le systme de

navigation [TCS 05].

Logiciel de navigation: Le logiciel de navigation contient des algorithmes et

les donnes qui traitent les mesures effectues par chaque capteur (p. ex., par

inertie ou les donnes de l'air). Il contient les constantes dtalonnage,

squences d'initialisation, algorithmes autotest et algorithmes de rechange pour

priodes lorsque les capteurs n'ont pas ou ne reoivent pas d'information

[MYR 01].


10

iii. Smartphone

Les tlphones portables se transforment aussi en systmes de navigation condition

quils soient quips de Bluetooth et de GPRS afin de pouvoir rcuprer les cartes

numriques se trouvant sur un serveur distant .Cependant ce type de navigation parfois

peut gnrer des frais de connexion [TCS 10].

I.6-Fonctions et services La fonction la plus fondamentale d'un systme de navigation routier est de donner la meilleure

route possible vers une destination particulire. Il doit tre capable de recalculer votre

itinraire si vous manquez une instruction ou un itinraire particulier.

La plupart des systmes de navigation routire remplissent trois fonctions fondamentales: le

positionnement, la recherche dadresse et la cration de routes et de suivi. Comme ils

permettent aussi de choisir les prfrences de routage, y compris la plus courte distance, le

temps le plus rapide, ou mme les routes sans page. Cependant les nouveaux systmes

proposent dautres services supplmentaires destins apporter plus daide au conducteur et

minimiser le temps et les frais de transport, cela est dune grande importance pour lconomie

de nimporte quel pays [FLI 04] [16]. Ces options diffrent dun systme un autre mais les

plus importantes sont :

1-Rapports de trafic en temps rel

Certains logiciels de navigation ont la capacit de recevoir des informations concernant le

trafic et ainsi viter les retards dus aux embouteillages. Cependant ces informations ne sont

disponibles que dans certains pays.

2-Les points dintrts (POI)

Cette fonction est une base de donnes de tous les sites et services susceptibles dintresser les

utilisateurs comme les htels, gares et stations-services etc.

3-Waypoints

Les waypoints sont des emplacements gographiques, dcrits par la longitude et la latitude,

que lon enregistre dans le systme. Les waypoints sont rarement utiliss avec les systmes

automobiles embarqus, mais ils sont essentiels pour les modles portables (mobiles).


11

I.7-Les composantes cls dun systme de

navigation automobile

Figure nI.3 : Les composantes cls dun systme de navigation automobile [FLI 04]

Comme reprsent dans la figure nI.3 les composantes principales d'un systme de

navigation automobile sont la base de donnes contenant la feuille de route (La carte)

numrique ainsi que des informations sur chaque destination possible ,le positionnement

c'est- dire la dtermination de la position actuelle du vhicule sur le rseau routier,

proposition d'itinraire et orientation c'est--dire la planification d'un itinraire allant de la

position actuelle du mobile jusqu' la destination choisie tout en orientant le conducteur, en

lui donnant des instructions audio ou visuelles, et une interface utilisateur pour faire

fonctionner le systme. Les travaux respectifs de Schlott [SCH 97] et zhao [ZHA 97] en

1997 nous donnent plus de dtail et dfinissent ces composantes comme suit :

I.7.1-Positionnement

Afin de dterminer la position actuelle du vhicule le systme doit d'abord dterminer la

position gographique (golocaliser le vhicule), comme on la cit prcdemment cela se

fait en gnral par dead-rocking ou en utilisant les GNSS, ensuite, cette position est utilise

pour dterminer la position sur le rseau routier disponible et cela se fait en utilisant le

processus du map-matching (correspondance de carte).

a. Le map-matching

Le map-matching est une mthode qui peut tre utilise pour amliorer la prcision

lors de l'affichage de la position du vhicule sur une carte lectronique. Le principe de

cette mthode est La correspondance entre la sortie du systme de navigation et le

rseau routier reprsent sur la carte numrique afin de s'assurer que la position est

cass ou correspond la plus proche rue [SKO et HAN 08]. Gnralement la

correspondance se fait en trois tapes:

Lors de la premire tape un ensemble d'arcs candidats ou segments sont

slectionns.


12

Deuximement la probabilit d'arcs candidats / segments est value

l'aide d'informations gomtriques et topologiques.

Enfin, l'emplacement du vhicule sur le segment de route le plus probable

est dtermin.

Informations gomtriques

Les informations gomtriques incluent des mesures comme la proximit entre la

position value et la route la plus proche dans la carte.

Informations topologiques

Le critre topologique de l'information dtermine la connectivit des routes

candidates (Des arcs), par exemple, le vhicule ne peut pas soudainement se

dplacer d'un segment de route un autre s'il n'y a aucun point d'intersection au

milieu des segments.

Si aucune rue ne satisfait aux conditions de recherche, on peut conclure que le

vhicule est l'extrieur de la rue donc il n'est pas ncessaire de correspondre la

position du vhicule cette rue.

Cette correspondance est ralise grce au modle planaire.

b. Le modle planaire

Figure nI.4 : Rseau routier dcrit par le modle planaire [SKO et HAN 08]

Gnralement le rseau routier est reprsent dans les cartes numriques sous forme

d'une planaire ou le systme des rues est reprsent par un ensemble d'arcs (c'est

dire, des courbes dans R2). Chaque arc reprsente une route dans le rseau et est

suppos tre linaire par morceaux, de sorte qu'elle puisse tre dcrite par un ensemble

de points. Les derniers points dans l'ensemble sont appels nuds et le reste comme

point de forme.


13

Les nuds dcrivent le commencement, ou la fin d'un arc indiquant un dbut, une

impasse ou une intersection (i.e. le point de passage d'un arc un autre).

c. Algorithme

Toutefois, un rseau routier peut tre assez compliqu surtout quand il ya plusieurs

croises de chemins (carrefours, intersections) par consquent la dtermination de la

rue correcte n'est pas entirement claire. Afin de facilit ce procd plusieurs

algorithmes et approches ont t proposs tel que lalgorithme propos par Yi et al en

1998 [YI et al 98].

Figure n I.5: Zone de recherche du map-matching [YI et al 98]

La figure n I.5 prsente une section d'un rseau et un point (P(X, Y)) reprsentant la

position gographique du vhicule. Pour trouver quelle rue correspond la position

sur le rseau routier, un cercle de rayon de rechercher est dessin. Par exprience, une

valeur approprie pour r sera utilise. Dans ce domaine, l'objectif est de trouver toutes

les rues qui satisfont les conditions suivantes :

Distance (D) entre la rue et le point P est plus courte que r. Ils existent deux cas

possibles :

Si le vhicule est statique, slectionnez la rue dont d est la plus courte ;

Si le vhicule est en mouvement, choisissez la rue qui a le plus petit

angle avec la direction du mouvement du vhicule.

I.7.2-Planification d'itinraires

Une fois la position de la voiture sur le rseau routier dtermine, une route peut tre planifie

de cette position-l. Cet itinraire est prvu l'aide des routes disponibles sur le rseau et puis

parmi ces itinraires le systme choisit le plus rapide ou le plus court selon le choix du

conducteur l'aide des algorithmes utiliss pour la dtermination d'itinraire optimis (voir

chapitre III), puis des instructions sont donnes au conducteur.

Cependant ces instructions doivent tre donnes temps au conducteur afin qu'il puisse en

prendre compte. Si la voiture n'est pas positionne sur litinraire courant pour un certain laps


14

de temps, alors le systme conclut que le conducteur a dvi de sa route, et une nouvelle route

doit tre prvue partir de la nouvelle position de la voiture [FLI 04].

I.7.3-La base de donnes

La base de donnes est stocke sur un support disque. Elle contient la carte numrique utilise

pour la planification d'itinraire, positionnement ainsi que des informations sur toutes les

destinations possibles [FLI 04].

I.7.4-Interface utilisateur

En gnral, l'interface est constitue de la carte montrant la position actuelle du vhicule et le

Rseau routier environnant est affich avec la prochaine manuvre. Le pilote normalement

reoit un avertissement sonore qui le prpare pour la prochaine manuvre, par exemple

chang de voie ou ralentir. Une fois l'emplacement de la manuvre atteint, le conseil actuel

est donn [FLI 04].

I.8-Evaluation des performances dun systme de

navigation automobile

De nos jours il existe plusieurs critres d'valuation des performances d'un systme de

navigation automobile mais seulement quatre d'entre eux, sont les plus significatifs; cependant

il faut se rappeler que la prcision est considr comme le critre le plus caractrisant des

performances d'un systme de navigation [SKO et HAN 08].

1-La prcision (exactitude)

C'est le degr de conformit des informations fournies par le systme des valeurs relles

concernant la position, vitesse, etc.

2-L'intgrit

C'est la mesure de la confiance qui peut tre mise dans les informations provenant du systme

de navigation en d'autres termes c'est la probabilit des dfaillances non dtectes dans la

prcision spcifie prcdemment.

3-Disponibilit

C'est la mesure du pourcentage de couverture de la zone destine et dans laquelle le systme

de navigation fonctionne.

4-Continuit de service

C'est la probabilit que le systme fournit continuellement des informations sans interruption

en dehors des services rguliers pendant la priode de travail prvue.


15

I.9-Conclusion

u cours de ce chapitre, nous avons tudi les diffrents systmes de navigation

par GPS. Allant de leurs proprits et les services proposs aux critres

dvaluation. De plus, nous avons introduit les diffrentes notions relies au

domaine de la navigation, ncessaires et utiles la suite de notre tude.

Etant donn que le positionnement est une partie importante dans la conception

des systmes de navigation, alors dans le chapitre suivant nous aborderons les

techniques de positionnement ainsi que les systmes de coordonnes.

A

Gnralits sur les techniques de positionnement et le GPS

Chapitre II



17

II.1-Introduction omme on a pu le constater prcdemment une partie importante du fonctionnement

dun systme de navigation automobile repose principalement sur la localisation de la

position du vhicule, ce qui est ralis laide de diverse techniques de

positionnement et ces dernires relvent du domaine de la golocalisation, alors pour

tre plus explicatif dans ce chapitre on introduira quelques notions cls de ce domaine

ainsi que la technologie GPS.

II.2-Gnralits sur la golocalisation [FAL 04]

II.2.1-Dfinition de la golocalisation La localisation dune personne ou dun mobile (vhicules, tlphones,) la surface de la

terre est dite : go-positionnement. Pour obtenir des informations plus prcises sur un

positionnement, la localisation trouve est mise en corrlation avec des systmes

dinformation.

Le go-positionnement est un rel besoin dans le monde de mobilit o nous vivons.

II.2.2-Les composantes dun systme de golocalisation Un systme de go localisation est compos de quatre composantes principales :

a. Terminal communicant : C'est llment qui reoit les coordonnes gographiques

de lobjet.

b. Logiciel de localisation : Toutes les informations relatives une golocalisation sont

stockes, analyses et affiches grce aux outils et fonctions offerts par le logiciel.

Le stockage et lanalyse se font par des serveurs informatiques qui hbergent

l'infrastructure et qui reoivent et traitent les donnes envoyes par les terminaux.

Et pour faciliter lusage lutilisateur on ajoute une interface graphique.

c. Donnes : les donnes reprsentent la partie la plus importante car elle constitue une

Liaison entre les autres composantes. Pour tre plus explicatif, la donne gnre par

un terminal qui se trouve sur le terrain doit tre transmise une plateforme logicielle

qui va la traiter, la prsenter graphiquement l'utilisateur et l'associer d'autres

donnes afin d'enrichir les informations relatives l'tat du terminal ou de la flotte de

terminaux.

d. Les utilisateurs : Un systme de golocalisation tant avant tout un outil, c'est son

utilisation (ou ses utilisateurs) qui permet d'en exploiter toutes ses fonctionnalits.

II.2.3-Techniques de positionnement Pour effectuer une localisation on peut utiliser plusieurs techniques dont : les systmes de

positionnement par satellites tels le GPS et GONASS, le positionnement cellulaire (GSM,

WIFI), le RFID et la localisation par adresse IP (Voir annexe A).

C


18

Le GPS est le systme le plus utilis dans le domaine de la navigation automobile vu la

prcision et la simplicit quil apporte. Dans la suite de ce chapitre on stalera sur ses

diffrents aspects.

II.3-Prsentation du systme GPS

Figure nII.1: la constellation GPS [10]

Le GPS est une constellation de 24 satellites, il permet de calculer la position gographique

(les coordonns) de n'importe quel point situ sur la surface du globe, en mesurant la distance

entre un rcepteur et les satellites qu'il capte. Sa prcision peut atteindre 1 mtre [ELR 04].

II.3.2-Structure physique [ELR 04] Le systme est compos de trois parties fondamentales :

Figure nII.2: Les trois segments du systme GPS [10]


19

a. Le segment espace [ELR 04]

Le segment spatial est le cur du systme, il est compos denviron 24 satellites rpartis

sur six orbites (quatre satellites par orbite) pour assurer une couverture mondiale continue.

Ces orbites sont quasi-circulaires, avec une inclinaison de 55 par rapport l'quateur et

une altitude denviron 11.000 miles pour viter les problmes associs aux systmes

terrestre. Ce qui leur permet galement de faire le tour de la terre toutes les 12 heures.

Ainsi o que ce soit sur la terre, 4 10 satellites sont visibles simultanment (en

considrant une lvation suprieure 10).

Figure nII.3 : Segment spatial [11]

Frquences de communication : Chaque satellite met des signaux radio

uniques dans la bande UHF, il existe deux frquences :

la premire destine l'usage civil est dsigne par "signal L1" et

sa valeur est de 1575,42 MHz.

la deuxime destine lusage militaire dsigne par "signal L2"

et sa la valeur est de 1227 MHz.

Ce signal est constitu de 3 messages : le code protg (code P), le code d'acquisition

(C/A pour Coarse/Acquisition) et un message de navigation.

b. Le segment de contrle

Dans le Monde, il existe cinq stations de contrle au sol qui sont situes tout autour de la terre

(Hawaii, Colorado Springs, le de l'Ascension, Diego Garcia et Kwajalein).

Dont quatre stations automatiques de surveillance et une seule station principale de

contrle Colorado Springs . Les stations automatiques reoivent constamment des donnes

provenant des satellites et renvoient ces informations la station principale de contrle. Cette

dernire corrige et met jour (phmrides, paramtres dhorloge..) les donnes reues puis

renvoie les informations aux satellites via deux antennes situes sur deux autres sites

diffrents [ELR 04].


20

Figure n II.4: Rseau de contrle [ELR 04]

c. Le segment utilisateur

Compos des rcepteurs GPS, appareils qui permet de calculer la position, la vitesse et

l'heure d'un observateur, partout et tout moment sur Terre et dans ses environs,

quelles que soient les conditions climatiques.

Le segment utilisateur regroupe les utilisateurs militaires (marine, arme de terre et

arme de lair), la police ou la gendarmerie dans le domaine civil, il regroupe les

navigateurs maritimes, les pilotes, les chasseurs, pcheurs, randonneurs, les sportifs,

les conducteurs dengin etc... [ELR 04].

II.3.3-Les applications du GPS

a. Usages militaires

Bien que le systme GPS a t achev seulement en 1994, il a dj prouv tre

dune aide prcieuse pour les forces militaires amricaines. Il est principalement

utilis pour le guidage des missiles de croisire ou des munitions tactiques (bombes

et roquettes) [12].

b. Usages civils

Un signal a t ddi uniquement pour lusage civil depuis 2000. Grce sa prcision

et son faible cot, le positionnement par GPS a trouv de nombreuses applications.

Parmi ces applications on distingue les suivantes : Cartographie et reprage de

points dintrt (POI), gestion des ressources naturelles (Agriculture), op

gnie civil, Gophysique, Cartographie arienne et navigation routire.

Cette dernire est l'application du GPS la plus connue du grand public et le sujet de

notre tude. Effectivement, l'utilisation du systme de navigation GPS et trs rpandu

et quipe maintenant un bon nombre de vhicules [ELR 04].


21

II.3.4-Dtermination d'une position par GPS

a. Systme godsique [ELR 04]

Afin de localiser mathmatiquement un point sur la terre dune faon univoque, il

faut dfinir un rfrentiel godsique.

Dfinition

Cest la ralisation concrte et numrique dun repre tridimensionnel dont le centre

est proche du centre de masse de la terre, ses deux premiers axes sont dans le plan

de lquateur et le troisime est proche de laxe de rotation des ples.

Un systme godsique est la combinaison d'un ellipsode qui prcise les

dimensions et la forme de la terre et d'un point de base partir duquel on dtermine

les coordonnes gographiques. Gnralement dans un ellipsode normal les trois

axes ont des longueurs diffrentes, mais dans cette modlisation ils ont des

longueurs gales, ce qui donne une sphre aplatie.

Il existe des centaines de systmes godsiques utiliss dans le monde. Mais avec

l'avnement du GPS, un systme valable mondialement a t mis au point : Cest

l'ellipsode WGS 84 (World Geodesic System of 1984).

b. Les coordonnes gographiques [ELR 04]

La position dun point M est reprsente par trois paramtres qui sont :

LONGITUDE, LATITUDE et ALTITUDE. Ces trois valeurs constituent les

coordonnes gographiques de ce point.

Figure nII.5 : Coordonnes gographique [ELR 04]


22

La longitude : angle orient entre le plan mridien origine et le plan mridien

contenant le point M. Le mridien dorigine est celui de Greenwich. La longitude est

gnralement exprime en degrs (marqus d') allant de 0 au mridien de

Greenwich 180 Est et l'Ouest

La latitude : angle orient entre le plan de l'quateur et la normale l'ellipsode

passant par le point M.Elle est gnralement exprime en degrs (marqus d') allant

de 0 l' quateur 90 aux ples Nord et Sud.

La hauteur h : distance algbrique entre le point M et l'ellipsode.

Ces coordonnes nont aucun sens si elles ne sont pas accompagnes avec les informations

concernant leur systme godsique. Sans information on pourrait obtenir des diffrences de

plusieurs dizaines de mtres, une fois celles-ci projetes [LAV 04].

c. La projection

Le GPS est utilis en association avec une carte pour se reprer et se positionner

i. La cartographie : Daprs le comit Franais de cartographie Cest lArt de dresser les

cartes gographiques. Une reprsentation gomtrique conventionnelle, gnralement

plane, en positions relatives, de phnomnes concrets ou abstraits, localisables dans

lespace ; cest aussi un document portant cette reprsentation ou une partie de cette

reprsentation sous forme dune figure manuscrite, imprime ou ralise par tout autre

moyen [13].

ii. La carte

La carte est toute reprsentation partielle ou complte mathmatiquement prcise de la

surface terrestre sur un plan montrant la situation, la distribution et les rapports de

divers phnomnes naturels et sociaux, choisis et dfinis en fonction du but de chaque

carte.

Les cartes gographiques servent reprsenter des phnomnes gographiques, c'est-

-dire des phnomnes dont la configuration spatiale produit du sens .Elles mettent en

valeur l'tendue dun espace, sa localisation relative par rapport aux espaces voisins,

ainsi que la localisation des lments qu'il contient [13].

iii. La projection cartographique [ELR 04]

Pour reprsenter la surface du globe sur une carte plane, et pour avoir des positions en

fonction de coordonnes plus simples utiliser que les donnes angulaires

(latitude/longitude) il faut passer par une projection. Une carte est donc toujours une

prsentation dforme de la ralit car la carte ainsi obtenue reprsente la surface de la

Terre dans une grille rectangulaire, les coordonnes sont appele easting (x) et

northing (y). Cette transformation n'est pas triviale puisque la sphre n'est pas une

surface dveloppable. En d'autres termes on ne peut pas transformer une surface

sphrique en un plan sans tirer et/ou contracter certaines rgions.

Il existe de trs nombreuses projections, que l'on peut classer en trois catgories (voir


23

annexe B) :

Projection conique.

Projection cylindrique.

Projection plane

Figure nII.6: Principales surfaces de projection, cne, cylindre, plan [20]

d. La triangulation [MEJ et VAN 10]

Son principe repose sur la mesure de la distance entre le satellite et le rcepteur. Sachant

que le satellite a une position bien dfinie dans un espace trois dimensions, lensemble

des points possibles o pourrait se situer lutilisateur du GPS est la sphre imaginaire

avec un rayon gal la distance du rayon de satellites.

Figure n II. 7: Diagramme de sphre [14]

Lintervention dun deuxime satellite qui connait la distance qui le spare du rcepteur

GPS cre un cercle qui reprsente lintersection des deux sphres et regroupe toutes les

positions que peut avoir le rcepteur GPS.

Figure nII.8: intersection de deux sphres [14]


24

Deux satellites ne suffisent pas pour obtenir une bonne prcision, alors on se sert dun

troisime. Lintersection des trois sphres dfinit deux points possibles. Dans le cas o

lutilisateur se situe sur la surface de la Terre seul un des deux points est cohrent.

L'un deux se dplace trs rapidement donc il est limin au profit du second qui est li

la vitesse de dplacement du rcepteur. Ainsi on peut dduire sa position exacte.

Figure nII.9 : la triangulation [14]

Donc : en thorie trois satellites suffisent pour connatre la position exacte dun point sur

Terre. Pourtant, nous verrons quen pratique il en faut quatre, ce quatrime servira pour

lobtention dune meilleure prcision du temps.

e. La mesure de la distance

Connaitre exactement la distance sparant le satellite du rcepteur est l'hypothse sur

laquelle reposait toute la dmonstration prcdente, son calcul se fait grce la

formule suivante :

Distance = vitesse * temps

i. Calcul du temps [MEJ et VAN 10]

Cela ncessite une manipulation : le satellite et le rcepteur mettent tous deux au

mme instant le code pseudo alatoire. Le rcepteur retarde le dbut de son

mission jusqu' ce que son signal soit en phase avec celui provenant du satellite.

La valeur de ce retard est ainsi le temps mis par le signal pour se propager du

satellite jusqu' l'utilisateur.

ii. Calcul de la vitesse [MEJ et VAN 10]

La vitesse de la transmission du signal est proche de la vitesse de la lumire, ce qui

est de 300 000 km / s.

Nous avons, le temps et la vitesse, donc on peut calculer la distance avec la formule

prcdente.


25

f. Le positionnement des satellites [MEJ et VAN 10]

Pour calculer prcisment la distance sparant un satellite du point dterminer, il faut que

ce dernier connaisse parfaitement sa position dans lespace. Donc afin dobtenir un

positionnement exact et parfait, il faut rgler ce dtail (la position des satellites). Ce

rglage est pris en charge par les stations de contrle. En effet, le satellite renvoie sa

position thorique la station qui calcule alors lerreur de positionnement commise par ce

dernier et la lui renvoie pour quil la prenne en compte lors de ses calculs.

g. Les erreurs de positionnement [ELR 04]

Lun des facteurs importants quon doit prendre en compte lors du choix dune

technique de positionnement est la prcision qui peut tre atteinte par celle-ci.

Certes le GPS nous donne une trs bonne prcision qui peut aller jusqu un mtre.

Cependant, des erreurs peuvent introduire des inexactitudes dans la position finale.

Effectivement, la mesure de la distances entre le rcepteur et les satellites est entache

d'erreurs (systmatiques et alatoires), leur origine est de trois types : erreurs dues aux

satellites (trajectoire, horloge) erreurs dues au rcepteur (horloge, bruit lectronique,

chemins multiples, variation du centre de phase de l'antenne) et finalement les erreurs

engendres par la transmission du signal (ionosphre, troposphre). Un certain nombre

de ces erreurs peut tre compens ou modlis afin de les corriger, ceci dpend du type

de rcepteur et du mode de mesure.

II.3.5-Les rcepteurs GPS [21] Un rcepteur GPS doit dtecter et convertir en mesures utiles les signaux transmis de tous les

satellites. Pendant la propagation des signaux, une perte dans la force de signal se produit et

c'est pour cette raison que les proprits de spectre et de corrlation de diffusion des signaux

sont exiges.

Les rcepteurs GPS peuvent, selon leur architecture, tre sous diviss en trois catgories

(voir annexe C) :

Les rcepteurs multicanaux.

Les rcepteurs squentiels.

Les rcepteurs multiplex.

Les rcepteurs multiplex et les rcepteurs squentiels tlchargent le message de navigation

dune manire asynchrone pour chaque satellite. Cest pourquoi le calcul de position demande

plus de temps.


26

II.4-Prcision On peut accrotre la prcision du GPS, en faisant intervenir les techniques damlioration :

CARRIER PHASE, WAAS (Wide Area Augmentation System) et DGPS cette dernire est la

plus utilise.

II.4.1-Le DGPS [ELR 04]

a. Dfinition du GPS diffrentiel

Le GPS diffrentiel en anglais Differential Global Positioning System : DGPS

permet damliorer considrablement la prcision des positions quobtiennent les

exploitants de petits btiments partir de leurs rcepteurs GPS. Sa prcision peut

atteindre les 10 mtres en nutilisant que les signaux du service de positionnement

standard.

b. Fonctionnement du DGPS

Le rcepteur GPS de la station de rfrence DGPS mesure les signaux de tous les

satellites en vue. Comme cette dernire est installe le long dune voie navigable

ctire dans une position fixe dont on connat avec prcision les coordonnes, elle est

capable de rsoudre lquation du temps de parcours rel et du temps de parcours

thorique de chaque signal des satellites. Alors elle peut dterminer nimporte quelle

erreur temporelle puis elle transmet les corrections effectuer tous les satellites en

vue. Le rcepteur embarqu ne prend en compte que les corrections applicables aux

satellites quil utilise pour la solution de navigation

II.5-Les inconvnients de la navigation GPS Il y'a beaucoup de facteurs qui limiteront et influenceront les rsultats d'un systme de

navigation automobile bas seulement sur la technologie GPS, les plus importants sont :

En raison des difices et des gratte-ciel denses, rues btisses se trouvant dans le

centre-ville, font en sorte que les signaux du GPS deviennent si faibles ce qui

gnre des erreurs lors du calcul de la position trop grandes pour tre tolres.

Les effets multi-trajet des signaux GPS sont trs graves dans les zones urbaines

cites ci-dessus, et peuvent provoquer une erreur computative lors du

positionnement parfois, ces erreurs peuvent tre extrmement large.

Sur les carrefours, les tunnels et passages souterrains, les signaux GPS sont trop

faibles pour tre reus ou mme aucun signal ne peut tre reu.

Les facteurs ci-dessus rendent le systme GPS du vhicule incapable de fournir en continu

des informations de positionnement [Qin et al 04].


27

II.6-Approches Afin de mettre fin la mauvaise rception GPS en milieu urbain plusieurs approches ont t

proposes et voici les plus pertinentes [Qin et al 04] :

Le GPS peut tre amlior en augmentant le nombre de satellites visibles. Pour

se faire le Russe Global Navigation Satellite System (GLONASS) est utilis en

offrant plus de satellites en vue et donc, augmenter la disponibilit des satellites.

Ceci est ralisable grce aux rcepteurs GPS avance qui peuvent recevoir plus

de 8 satellites diffrents au mme temps et ainsi amliorer la rception GPS en

milieu urbain.

En trouvant une solution limite (contrainte). Par exemple dans la navigation

automobile l'altitude change lentement donc elle est considre comme tant

une constante et est suppose tre connue.

En intgrant le GPS avec des capteurs (utilisation du dead-rocking) tels que les

systmes de navigation inertielle (INS) et des codeurs qui peuvent fournir des

informations en continu mais cela nest possible que dans le cas o le systme

de navigation est embarqu.

L'utilisation du filtre de Kalman apporte aussi une solution ce problme

l'aide de la modlisation dynamique du systme. En effet l'utilisation du filtre

exige une mise jour continue dans le temps et permis ainsi de dterminer la

position du vhicule mme si aucune mesure de pseudo-position n'est

disponible. (Voir annexe D)

Une nouvelle approche a t ajoute par Youjing Cui et Shuzhi Sam dans leurs

travaux en 2003 [SHU et CUI 03]. Cette approche est une autre solution

restreinte. Plus prcisment elle propose de modliser approximativement le

chemin du vhicule en des pices de courbes comme des lignes droites, des

arcs, polynmes et ainsi de suite. comme le vhicule se dplace dans un milieu

urbain, son chemin est toujours limit un certain segment de la route.

En modlisant approximativement le chemin du vhicule en une ligne

ressemblant la route connue par consquent moins de satellites GPS sont

ncessaires pour obtenir les informations concernant le positionnement. En

effet, le nombre minimum de satellites ncessaires diminue deux au lieu de

quatre.


28

II.7-Conclusion

travers ce chapitre, on a tent de comprendre les diffrentes techniques utilises dans

le positionnement et plus prcisment le GPS qui daprs notre tude se trouve tre la

technique la plus approprie pour un systme de navigation routier mobile.

Comme nous avons abord aussi les diffrentes notions relies au positionnement

telle que les systmes de coordonnes, les erreurs de positionnement et les approches

utilise pour lamlioration des ces erreurs etc.

Aprs le positionnement vient la deuxime composante principale dun systme de

navigation routier par GPS, et qui est la guidance en dautre termes la planification

ditinraires et celle-ci sera tudie en dtail dans le chapitre qui suit.

A

Etude sur les systmes de guidance

Chapitre III



30

III.1-Introduction prs avoir dtermin la position du vhicule sur le rseau routier, reste la

dtermination de litinraire le plus optimis et lorientation du conducteur. En

gnral, ces tches sont remplies par le systme de guidance. Ce dernier est lune des

composantes les plus importantes dun systme de navigation [FLI 04], On lui

consacrera la suite de notre tude.

Dans la suite de ce chapitre nous nous concentrerons sur la fonction de base des systmes de

guidance savoir la planification ditinraire et le calcul du chemin optimal. Effectivement,

ce chapitre portera sur la modlisation du problme et la recherche du chemin optimal, le

critre doptimisation est dtermin selon le choix de lutilisateur.

En gnral, les systmes de navigation automobile fournissent la possibilit de choisir parmi

diffrents critres d'optimisation ou diffrentes fonctions de cot. En effet, le conducteur peut

choisir entre la planification de litinraire le plus rapide ou le plus court, litinraire le plus

rapide en donnant la prfrence aux autoroutes et litinraire le plus rapide en ngligeant les

autoroutes. De plus, des options pour viter les routes page ou les ferries peuvent tre

disponibles. Un autre aspect de la vie relle qui influence la qualit d'un itinraire prvu, est la

prsence de bouchons de circulation sur l'itinraire prsent. Les informations du trafic,

savoir sur les embouteillages, travaux routiers et les conditions routires par exemple, sont

reus par RDS-TMC (Radio Data System - Traffic Message Channel), ou par un tlphone

GSM connect.

III.2-Formulation du problme Un systme de navigation automobile utilise des cartes contenant des milliers de rseaux

routiers (une reprsentation graphique ventuellement tiquete pondre de toutes les rues et

passages). Cela signifie quun systme de navigation automobile doit tre capable de planifier

des itinraires sur les rseaux routiers qui contiennent des millions de segments de route et

cette planification ne doit prendre que quelques secondes.

Une fois que le conducteur a introduit sa destination et le systme a dtermin la position de

la voiture, un itinraire est planifi de cette position-l la destination souhaite. Lors de la

planification de cette route, des donnes doivent tre rcupres de la base de donnes

plusieurs reprises, en raison de la capacit limite de la mmoire interne, qui est

Documents

138025390 Memoire Systeme de Navigation Par GPS