GPS, trames NMEA et itinéraires

Le principe de la géolocalisation par satellites

Le GPS (américain) et Galileo (européen) sont des constellations de satellites placés à environ 20 000 km d'altitude. Chaque satellite émet en continu un signal radio contenant deux informations : sa position et l'heure exacte d'émission, donnée par une horloge atomique embarquée.

Le récepteur (ton téléphone) ne fait qu'écouter. Il note l'heure à laquelle le signal arrive. La différence donne le temps de propagation $\Delta t$. Comme le signal voyage à la vitesse de la lumière $c = 300\,000\ \text{km·s}^{-1}$, on en déduit la distance :

Une seule distance ne suffit pas : elle place le récepteur sur une sphère. Avec deux satellites, on obtient un cercle. Avec trois, il reste deux points, dont un est absurde (loin dans l'espace) : on l'écarte. Il faut donc trois distances pour la position, et une quatrième mesure pour l'horloge du récepteur (voir plus bas). La figure est un schéma en deux dimensions : elle montre seulement les trois distances d1, d2 et d3 qui aboutissent au récepteur.

Mais il y a un piège. L'horloge du téléphone est une simple horloge à quartz, bien moins précise qu'une horloge atomique. Son erreur est une inconnue de plus à déterminer. On ajoute donc un quatrième satellite : avec quatre satellites, on obtient les trois coordonnées $(x ; y ; z)$ et la correction de l'horloge du récepteur.

Précision et sources d'erreur

Un téléphone est en général précis à quelques mètres en terrain dégagé. Cette précision se mesure en comparant la position affichée à une position connue : l'erreur moyenne est la moyenne des écarts relevés.

Plusieurs facteurs dégradent la précision :

• les bâtiments (en ville, les signaux rebondissent : on parle de trajets multiples) ;

• une faible couverture du ciel (tunnel, forêt dense, intérieur) ;

• la traversée de l'atmosphère, qui ralentit un peu le signal ;

• une mauvaise répartition des satellites dans le ciel.

Pour l'améliorer, on peut utiliser plusieurs constellations à la fois (GPS + Galileo), un récepteur double fréquence, ou un système de correction au sol.

Les trames NMEA 0183

Un récepteur GPS envoie ses résultats sous forme de trames de texte au protocole NMEA 0183. Chaque trame est une ligne dont les champs sont séparés par des virgules. Elle commence par $ et finit par * suivi d'une somme de contrôle (pour détecter les erreurs de transmission).

Le premier champ indique le type de trame. Par exemple GPGGA donne la position et la qualité du signal, GPRMC la position, la vitesse et la date.

Voici une trame fictive (sa somme de contrôle est donnée à titre d'illustration et n'a pas été vérifiée) :

$GPGGA,094530,4513.30,N,00506.20,E,1,07,1.1,230.0,M,48.0,M,,*5A

La vitesse dans une trame GPRMC est donnée en nœuds. Pour la convertir : $1\ \text{nœud} = 1{,}852\ \text{km/h}$. Par exemple, 10 nœuds valent $10 \times 1{,}852 = 18{,}52$ km/h.

Les cartes numériques

Une position GPS n'a de sens que posée sur une carte. Les cartes numériques sont organisées en couches d'informations superposées : fond de plan, routes, bâtiments, relief, limites administratives, etc. Tu peux afficher ou masquer ces couches.

Sur ton téléphone, tu peux aussi régler la confidentialité de ta position : dans les paramètres, chaque application reçoit l'autorisation d'accéder à ta position « jamais », « pendant l'utilisation » ou « toujours ». Tu choisis donc si tu la partages ou non.

Deux services à connaître :

• GéoPortail : le portail de l'Institut national de l'information géographique et forestière (IGN). Il propose des cartes, des photographies aériennes et de nombreuses couches (cadastre, risques, relief…). Il s'agit d'un service public.

• OpenStreetMap (OSM) : une carte du monde construite collaborativement par des contributeurs bénévoles, sous licence libre (ODbL). Tout le monde peut l'utiliser et la modifier.

Calculer un itinéraire : les graphes pondérés

Pour calculer un itinéraire, le logiciel représente le réseau routier par un graphe pondéré : les sommets sont les carrefours ou les villes, les arêtes sont les routes, et chaque arête porte un poids (durée en minutes, distance en km…).

Le poids d'un chemin est la somme des poids de ses arêtes. Chercher l'itinéraire le plus rapide, c'est chercher le chemin de poids minimal.

L'algorithme de Dijkstra trouve le plus court chemin depuis un sommet de départ. Principe :

1. Le départ a la distance 0, les autres sommets ont une distance provisoire infinie.

2. On choisit le sommet non encore définitif de plus petite distance provisoire : sa distance devient définitive.

3. Pour chacun de ses voisins, on teste si passer par lui raccourcit le chemin ; si oui, on met à jour la distance provisoire.

4. On recommence jusqu'à ce que l'arrivée soit définitive.

Retour au début : le téléphone de Lucas mesure les temps de propagation de signaux venus d'au moins quatre satellites, en déduit sa position, la place sur une carte, puis cherche sur un graphe pondéré le trajet le plus court jusqu'à la gare.

L'essentiel

• Un récepteur GPS ou Galileo calcule sa position à partir du temps de propagation de signaux émis par des satellites équipés d'horloges atomiques : $d = c \times \Delta t$.

• Il faut quatre satellites : trois pour $x$, $y$, $z$ et un pour corriger l'horloge du récepteur. 1 µs d'erreur donne environ 300 m.

• La précision est de quelques mètres ; elle est dégradée par les bâtiments, le manque de ciel visible et l'atmosphère.

• Une trame NMEA 0183 est une ligne de champs séparés par des virgules (heure UTC, latitude ddmm.mmm, hémisphère, nombre de satellites…). Degrés décimaux $=$ degrés $+$ minutes$/60$ ; 1 nœud $= 1{,}852$ km/h.

• GéoPortail (IGN, service public) et OpenStreetMap (collaboratif, licence libre) sont deux services de cartes numériques organisés en couches.

• Un itinéraire se calcule sur un graphe pondéré avec l'algorithme de Dijkstra ; le plus court en poids n'est pas forcément celui qui a le moins d'étapes.