Brevet FR3055503A1 — publié le 20180302

PROCEDE DE GEOLOCALISATION COLLABORATIVE SUR UN VOISINAGE L'invention concerne un procédé de géolocalisation collaborative en groupe, mettant en jeu plusieurs noeuds dans un réseau de communication. Dans le procédé selon l'invention, les noeuds échangent entre eux des informations de distance et/ou de position, par exemple, ou d'autres paramètres utiles pour la géolocalisation, afin de disposer d'un système de navigation plus performant. Les noeuds peuvent être des noeuds mobiles qui changent de 10 position dans le réseau de radiocommunication (par exemple des piétons ou des véhicules en réseau). La gestion des échanges d'informations dans le cas de la navigation collaborative devient un problème lorsque le nombre de noeuds présents dans un réseau de communication est important, typiquement au- 15 delà de quelques dizaines de noeuds. Dans ce cas, certains noeuds peuvent se trouver distants les uns des autres de plus d'une dizaine de bonds, ce qui pose à la fois des problèmes de congestion et de délai d'acheminement des informations, lorsque chaque noeud doit diffuser les informations dont il dispose à tous les autres noeuds du réseau. Les solutions de calcul global de 20 la géolocalisation connues de l'art antérieur se heurtent à la fois à un problème de forte combinatoire (nombre d'informations à prendre en compte important dans le calcul) induite par les réseaux de grande taille et à la difficulté de récupérer en temps limité des informations venant de tous les noeuds (limitation des protocoles d'échange, comme évoqué ci-dessus, pour 25 rapatrier sur chaque noeud toutes les informations des autres noeuds dans des délais contraints). Ceci rend généralement très difficile, voire impossible, le calcul d'une solution globale en temps contraint et, in fine, d'une solution pouvant être actualisée facilement et remise à jour en fonction du temps de cycle de géolocalisation. Le cycle de géolocalisation est, par exemple, défini 30 par des instants déclencheurs du procédé de géolocalisation. Les mesures de distance entre voisins peuvent être obtenues par des mesures sur la forme d'onde du réseau de radiocommunication ou par 3055503 2 un équipement complémentaire. Dans ce dernier cas, on définit le graphe orienté de télémétrie inter-noeuds en formant une arête (i,j) si le noeud i délivre une mesure de distance du noeud j. Par la suite, sauf mention contraire, les termes graphe ou réseau ne feront référence qu'au graphe de 5 télémétrie, qui coïncide avec le graphe du réseau de communication dans le cas où les mesures de télémétrie sont réalisées sur les liens radio. L'art antérieur décrit également des méthodes de géolocalisation locale qui comportent un calcul de positionnement d'un noeud à géolocaliser en exploitant les voisins directs du noeud (du graphe de télémetrie) qui disposent eux-mêmes d'une estimation de leur position. Cette solution ne fonctionne que si au moins trois noeuds voisins disposent d'une estimation de position pour eux-mêmes. De plus, elle est peu précise lorsque le nombre de voisins est faible. Dans le cas où l'on ne dispose pas d'au moins trois noeuds ayant une estimation de position, une extension de cette solution consiste, par exemple, à itérer le processus de géolocalisation à partir des voisins, i.e., en essayant à nouveau d'obtenir une géolocalisation du noeud courant au prochain cycle, ce qui sera possible si au moins trois noeuds voisins parviennent à se géolocaliser. Cependant, une telle solution ne permet pas toujours de trouver des solutions de géolocalisation dans des situations pourtant observables, notamment si aucun noeud du réseau ne dispose d'au moins trois voisins géolocalisés. Ceci reste vrai dans le cas où des solutions de géolocalisation sont obtenues, celles-ci étant généralement peu précises et insuffisamment actualisées en présence de noeuds mobiles. La figure 1 illustre un réseau avec un noeud à géolocaliser A, plusieurs noeuds 2 disposant d'une estimation de position, plusieurs noeuds 3 sans estimation de position. Tous les noeuds communiquent entre eux par des moyens de communication et un protocole de communication connus de l'homme du métier. Cette solution est valide si tous les noeuds sont observables. Toutefois, elle présente comme inconvénient de requérir un temps de calcul important pour estimer une position. Un noeud est dit « observable », si ce dernier est capable d'estimer ses données de position 3055503 3 au sein du réseau. On définit également le degré d'observabilité Dn d'un noeud n comme étant le nombre de bonds requis pour qu'il puisse se géolocaliser au sein du sous-réseau de voisinage à Dn bonds du noeud n, avec par convention un degré d'observabilité nul, si le noeud dispose déjà 5 d'une propre estimation de position. Cette estimation de position peut être obtenue, par exemple à l'aide d'un capteur GPS en poursuite. La figure 2 illustre le cas où la géolocalisation du noeud courant A est impossible avec une approche classique sur voisinage direct, car le procédé ne dispose pas d'au moins trois noeuds voisins ayant une estimation 10 de position. La figure 2 schématise un périmètre 20 contenant le noeud à géolocaliser A, deux noeuds voisins 21, 22 disposant d'une estimation de position et d'un noeud voisin 23 ne disposant pas d'estimation de position et qui ne contribue pas à la géolocalisation du noeud A. Ce cas ne permet donc pas de géolocaliser le noeud A. 15 Le document intitulé « Localisation collaborative pour réseaux de capteurs » de Karel Heurtefeux et Fabrice Valois, HAL Id: hal-00250241, https://hal.archives-ouvertes.fr/hal-00250241, divulgue un algorithme de localisation locale qui utilise uniquement la connaissance de la topologie radio et ne fait pas appel à des mesures de ranging ou des mesures de GPS. 20 Le procédé selon l'invention repose sur une nouvelle approche qui consiste, notamment, à déterminer un voisinage observable et ensuite à dérouler des étapes de géolocalisation en exploitant les mesures disponibles de ranging et de positions. Le voisinage observable pour un noeud à géolocaliser est défini 25 comme un ensemble de noeuds contenant le noeud à géolocaliser, ces noeuds étant eux-mêmes observables, c'est-à-dire : que ces noeuds sont capables d'estimer leur propre position ou qu'ils disposent déjà d'une géolocalisation, que ces noeuds communiquent avec le noeud à géolocaliser en 30 diffusant des informations de position et/ou de ranging qui peuvent être utilisées pour géolocaliser le noeud A. La géolocalisation du noeud A est d'autant plus précise que le 3055503 4 nombre de mesures et de noeuds de ce voisinage est important. Notons que la géolocalisation du noeud A implique au niveau du traitement du noeud A, la géolocalisation de l'ensemble des noeuds du 5 voisinage. L'invention concerne un procédé de géolocalisation collaborative d'un ou de plusieurs noeuds Mi dans un réseau de communication, les noeuds échangeant entre eux au moins des informations de distance et/ou de positions comportant au moins les étapes suivantes : 10 - Déterminer un premier sous-graphe V1 de noeuds voisins d'un noeud courant A à géolocaliser, à N bonds, - Sélectionner dans ledit premier sous-graphe V1, le plus grand sous-graphe observable V3, - Exécuter un algorithme de géolocalisation sur les noeuds du plus 15 grand sous-graphe observable V3 et déterminer au moins la position du noeud courant A. Selon une variante, le procédé de géolocalisation est caractérisé en ce qu'il comporte au moins les étapes suivantes : - Déterminer un premier sous-graphe V1 des noeuds voisins du noeud 20 courant A en considérant les noeuds à N bonds maximum avec N supérieur ou égal à zéro, puis - Déterminer le plus grand sous-graphe observable V3 à partir du premier sous-graphe des voisins V1 contenant le noeud A, en exécutant les étapes suivantes : 25 - Déterminer s'il existe au moins trois noeuds appartenant au premier sous-graphe V1 et disposant d'une estimation de position, - S'il n'existe pas au moins trois noeuds appartenant au premier sous-graphe V1 et disposant d'une estimation de position alors, il n'y a pas de voisinage observable du noeud A inclus dans le 30 premier sous-graphe V1 et le noeud A n'est pas localisable, 3055503 5 - S'il y a au moins trois noeuds appartenant au premier sous-graphe V1 avec estimation de position, alors, construire un deuxième sous-graphe V2, en éliminant du premier sous-graphe V1 les noeuds qui sont différents du noeud A, qui ne contiennent 5 pas d'estimation de position et qui ont un nombre d'arêtes partant du noeud inférieur ou égal à 2, - Tester si le deuxième sous-graphe V2 est observable, si c'est le cas on définit le plus grand sous-graphe V3 comme étant le deuxième sous-graphe V2, 10 - Sinon, parcourir les sous-graphes de V2 contenant le noeud A, - Exécuter un algorithme de géolocalisation sur les noeuds contenus dans le plus grand sous-graphe V3 existant, afin de déterminer la position du noeud courant A. Le test d'observabilité d'un sous-graphe peut mettre en oeuvre un 15 test de rigidité globale. Le test de rigidité globale peut comporter les étapes suivantes : - Vérifier qu'un sous-graphe reste connexe lorsqu'on enlève deux sommets quelconques, - Vérifier qu'un sous-graphe reste rigide en enlevant une arête 20 quelconque. Le procédé s'applique, par exemple, dans un réseau de communication décentralisé pour déterminer la position des noeuds dudit réseau. L'invention concerne aussi un dispositif de géolocalisation d'un ou 25 de plusieurs noeuds dans un réseau, les noeuds étant équipés d'émetteurs-récepteurs et de moyens de communication caractérisé en ce que chacun des noeuds comporte au moins les éléments suivants : - Un processeur adapté à exécuter les étapes du procédé selon l'invention, 30 - Un dispositif permettant à un noeud de se géolocaliser, 3055503 6 - Une table mémorisant les informations de topologie des autres noeuds. L'invention s'applique dans un réseau de communication ad-hoc. D'autres caractéristiques et avantages de la présente invention 5 apparaîtront mieux à la lecture de la description qui suit, d'exemples de réalisation donnés à titre illustratif et nullement limitatif, annexée des figures qui représentent : - Figure 1, un premier exemple d'architecture réseau de télémetrie selon l'art antérieur et Figure 2, un deuxième exemple d'architecture 10 selon l'art antérieur, - Figure 3, une illustration de la définition d'un noeud observable dans un réseau, - Figure 4, une illustration des éléments et des modules équipant les noeuds d'un réseau pour la mise en oeuvre du procédé selon 15 l'invention, - Figure 5, une illustration des sous-ensembles de noeuds obtenus par le procédé selon l'invention, et - Figure 6, un organigramme décrivant un exemple d'étapes mises en oeuvre par le procédé. 20 La figure 3 illustre ce que l'on entend par noeud observable ou non observable. Un noeud est dit k-observable (i.e. degré d'observabilité k) s'il existe un sous-réseau de noeuds observables le contenant et inclus dans le sous-réseau du voisinage de n à k bonds. - Le noeud sera dit 0-observable, avec k=0, si et seulement si le noeud 25 est une ancre, c'est-à-dire que le noeud dispose de sa propre estimation de position, par exemple à l'aide d'un capteur GPS, - Le noeud sera dit 1-observable, avec k=1, si et seulement si le noeud peut être géolocalisé à partir de ses voisins directs (noeud positionné à un bond du noeud courant) et des éventuelles mesures de ranging 30 entre les voisins eux-mêmes, 3055503 7 - Le noeud sera dit k-observable, avec k>1, si et seulement si le noeud est observable (i.e. géolocalisable) au sein de son voisinage à k bonds, en exploitant les mesures de positions et de ranging des noeuds de ce voisinage. 5 Afin de mieux faire comprendre le procédé selon l'invention, l'exemple qui suit est donné dans le cas d'un système de communication comprenant plusieurs noeuds Mi. La figure 4 schématise une partie du réseau de communication comprenant les Mi noeuds et les modules équipant ces noeuds. Le procédé dans cet exemple est mis en oeuvre de manière 10 décentralisée, c'est-à-dire que chaque noeud est autonome et équipé de moyens de mesure pour la géolocalisation, et de moyens de communication pour échanger des informations avec les autres noeuds du réseau, connus de l'homme du métier. Un noeud comporte, par exemple, un dispositif de communication 15 40, un processeur 41 adapté à exécuter les étapes du procédé selon l'invention et une batterie 42 ou dispositif d'alimentation. Les noeuds Mi communiquent entre eux, par exemple, au moyen d'une liaison radiofréquence sans fil ou par d'autres moyens connus de l'homme du métier. Chaque noeud comporte aussi une mémoire ou table de voisins 43 20 permettant de stocker les informations de position des autres noeuds et d'avoir une image de la topologie des noeuds du réseau. Le réseau de communication comporte aussi un dispositif pour déterminer la position absolue de tout ou partie des noeuds. Ainsi, tous les noeuds ou une partie des noeuds peuvent, par exemple, être équipés d'un 25 récepteur 44 qui, couplé avec un dispositif satellitaire 50, permet au noeud équipé du récepteur 44 de se géolocaliser. Ce dispositif de mesures de position peut être un système de géolocalisation GPS (Global Positioning System), un système de navigation satellitaire GNSS (Global Navigation Satellite System), un moyen de topographie, etc. Sur la figure 4, le noeud M2 30 est équipé d'un récepteur, alors que le noeud M3 ne l'est pas. Il comporte aussi un dispositif de mesures de distance de ses voisins directs ou dispositif de ranging, qui est colocalisé. Le dispositif de 3055503 8 ranging peut se présenter sous la forme d'une carte électronique portée par le noeud. Selon une autre variante de réalisation, ce pourrait être une fonctionnalité du système de communication au niveau d'un noeud mesurant le temps mis par l'onde radio pour transiter entre les noeuds. 5 La figure 5 illustre les deux étapes du procédé selon l'invention qui permettent de définir un sous-ensemble de noeuds à partir duquel un procédé de géolocalisation sera exécuté. Le procédé fait appel à la notion de graphe orienté G connu de l'homme du métier. Le graphe est défini par un ensemble de couples (S, B) avec S un ensemble fini de sommets et B un 10 ensemble de couple de sommets correspondant aux noeuds du réseau. Le noeud A est un noeud à géolocaliser et comporte les différents équipements d'un noeud décrit à la figure 4. Les noeuds 51i sont des noeuds qui comportent une estimation de position, représentés en traits pointillés sur la figure. Les noeuds 52j sont des noeuds qui ne comportent pas d'estimation 15 de position, représentés en traits pleins sur la figure. Chaque noeud connaît la topologie de ranging du réseau. Il s'agit ici de la topologie de télémétrie pour laquelle deux noeuds i et j sont reliés par une arête orientée (i,j), si i dispose d'une mesure relative de la distance de j. Lorsque le système de télémétrie est intégré à un réseau de 20 radiocommunication de type MANET (Mobile ad hoc networks), la topologie est la topologie d'un réseau de radiocommunication. Un cycle de géolocalisation est par exemple déclenché au niveau de chacun des noeuds selon une période T, toutes les T secondes ou minutes en fonction de l'application. 25 L'exemple qui suit va être donné dans le cadre d'une architecture décentralisée dans laquelle chaque noeud va essayer de se géolocaliser en mettant en oeuvre le procédé sur son voisinage, i.e., les noeuds dans son voisinage. Les étapes exécutées sont alors les suivantes : Première étape, Etape 1 : à un instant donné to, on détermine le voisinage du 30 noeud courant A à N bonds, avec N supérieur ou égal à 0, le nombre N est par exemple défini en tenant compte de la durée T du cycle de géolocalisation, afin que le procédé ait le temps d'utiliser les informations 3055503 9 transmises par les noeuds voisins distants d'au plus N bonds ; le voisinage constitue un premier sous-graphe V1, Deuxième étape, Etape 2 : à partir de l'ensemble des voisins à N bonds défini à la première étape, le procédé détermine le plus grand sous-graphe 5 V2 observable du voisinage à N bonds : - contenant au moins le noeud A, - dans lequel au moins trois noeuds (sommets) M1, M2, M3 du sous-graphe V2 disposent d'une estimation de position, - qui vérifie la propriété d'être globalement rigide selon la définition 10 connue de l'homme du métier, i.e., sous-graphe 3-connexe et rigide- redondant, Troisième étape, Etape 3 : le procédé met en oeuvre un procédé classique de géolocalisation sur l'ensemble des noeuds contenus dans le plus grand sous-graphe. 15 La figure 6 illustre de manière détaillée un organigramme des étapes mises en oeuvre par le procédé selon l'invention : 601 - on détermine un ensemble V1 ou premier sous-graphe des noeuds voisins du noeud courant A à N bonds maximum (N>=0), en utilisant des procédés connus de l'homme du métier basés, par exemple, sur des 20 protocoles d'échanges de tables de voisins, 602 - On teste s'il existe au moins trois noeuds appartenant au premier sous-graphe V1 et disposant d'une estimation de position, - S'il n'existe pas au moins trois noeuds appartenant au premier sous-graphe V1 et disposant d'une estimation de position alors, il 25 n'y a pas de voisinage observable du noeud A inclus dans le sous- graphe V1 et le procédé s'arrête, il n'est pas possible de localiser le noeud A, 603, - S'il y a au moins trois noeuds appartenant au sous-graphe Vi avec estimation de position, alors on passe à l'étape suivante pour 30 trouver un sous-graphe observable, 3055503 10 On détermine le plus grand sous-graphe observable V3 à partir du sous-ensemble des voisins V1 contenant le noeud A, en exécutant par exemple les étapes suivantes : 604 - On construit un deuxième sous-graphe V2, en éliminant du premier 5 sous-graphe V1 les noeuds différents du noeud A, qui ne contiennent pas d'estimation de position et qui sont de degré inférieur ou égal à 2 (correspondant au nombre d'arrêtes qui partent d'un noeud), ce qui permet de conserver uniquement les noeuds qui vont servir à l'algorithme de localisation, 10 605 - On teste si le deuxième sous-graphe V2 est observable, en utilisant par exemple un test de rigidité globale connu de l'homme du métier, - Si le deuxième sous-graphe V2 est observable, alors le plus grand sous-graphe V3 est égal au sous-graphe V2, 606, et l'on passe à l'étape de géolocalisation, 15 - Sinon, 607, le procédé parcourt tous les sous-graphes de V2 en recherchant le plus grand sous-graphe V3 observable contenant le noeud A, c'est-à-dire le sous-graphe contenant le plus de noeuds. Ce parcours peut être exhaustif, mais il peut être optimisé pour éviter de parcourir la totalité des sous-graphes de V2, par exemple en 20 parcourant les sous-graphes par taille (i.e. nombre de sommets) décroissante et en s'arrêtant dès qu'un sous-graphe observable et contenant le noeud A est observé. Si on ne trouve pas de sous-graphe observable contenant le noeud A, il n'y a pas de voisinage observable du noeud A inclus 25 dans le premier sous-graphe V1 et le procédé se termine, 608, Si un sous-graphe est observable alors V3 existe, et on passe à l'étape de géolocalisation, 609, 609 - On exécute un algorithme de géolocalisation sur les noeuds contenus dans le plus grand sous-graphe V3, afin de déterminer la position du noeud 30 courant A. 3055503 11 Le test de rigidité globale peut être réalisé en exécutant les étapes suivantes connues de l'homme du métier : Vérifier que le sous-graphe est 3-connexe, i.e., le graphe reste connexe en enlevant deux sommets quelconques, 5 Vérifier que le sous-graphe présente une redondance rigide (le sous-graphe reste rigide en enlevant une arête quelconque ; la rigidité peut être par exemple vérifiée en utilisant le théorème de Laman). Le procédé décrit ci-dessus peut être utilisé dans un réseau de 10 communication mobile de type ad-hoc. Le procédé offre un procédé de géolocalisation collaborative en temps contraint dans des grands réseaux, pour un nombre de noeuds de communication au moins égal à dix. Ceci permet notamment d'obtenir une solution en temps contraint et avec une meilleure précision de 15 géolocalisation que la précision obtenue par les procédés de l'art antérieur. REVENDICATIONS1 - Procédé de géolocalisation collaborative d'un ou de plusieurs noeuds Mi dans un réseau de communication, les noeuds échangeant entre eux des 5 informations de distance et/ou de positions, comportant au moins les étapes suivantes : - Déterminer un premier sous-graphe V1 de noeuds voisins d'un noeud courant A à géolocaliser, à N bonds, - Sélectionner dans ledit premier sous-graphe V1, le plus grand sous- 10 graphe observable V3, - Exécuter un algorithme de géolocalisation sur les noeuds du plus grand sous-graphe observable V3 et déterminer au moins la position du noeud courant A. 15 2 - Procédé de géolocalisation selon la revendication 1 caractérisé en ce qu'il comporte au moins les étapes suivantes : - Déterminer un premier sous-graphe V1 des noeuds voisins du noeud courant A en considérant les noeuds à N bonds maximum avec N supérieur ou égal à zéro, (601), puis 20 - Déterminer le plus grand sous-graphe observable V3 à partir du premier sous-graphe des voisins V1 contenant le noeud A, en exécutant les étapes suivantes : - Déterminer s'il existe au moins trois noeuds appartenant au premier sous-graphe V1 et disposant d'une estimation de position, (602), 25 - S'il n'existe pas au moins trois noeuds appartenant au premier sous-graphe V1 et disposant d'une estimation de position alors, il n'y a pas de voisinage observable du noeud A inclus dans le premier sous-graphe V1 et le noeud A n'est pas localisable, (603), - S'il y a au moins trois noeuds appartenant au premier sous-graphe 30 V1 avec estimation de position, alors, (604) on construit un deuxième sous-graphe V2, en éliminant du premier sous-graphe 3055503 13 V1 les noeuds qui sont différents du noeud A, qui ne contiennent pas d'estimation de position et qui ont un nombre d'arêtes partant du noeud inférieur ou égal à 2, - (605) - Tester si le deuxième sous-graphe V2 est observable, si c'est le cas définir le plus grand sous-graphe V3 comme étant le deuxième sous-graphe V2, (606), - Sinon, parcourir les sous-graphes de V2 contenant le noeud A (607), - Exécuter (609) un algorithme de géolocalisation sur les noeuds contenus dans le plus grand sous-graphe V3 existant, afin de déterminer la position du noeud courant A. 3 - Procédé selon la revendication 2 caractérisé en ce que le test d'observabilité d'un sous-graphe met en oeuvre un test de rigidité globale. 4 - Procédé selon la revendication 3 caractérisé en ce que le test de rigidité globale comporte les étapes suivantes : - Vérifier qu'un sous-graphe reste connexe lorsqu'on enlève deux sommets quelconques, - Vérifier qu'un sous-graphe reste rigide en enlevant une arrête quelconque. 5 - Procédé selon l'une des revendications précédentes caractérisé en ce que le réseau est un réseau de communication décentralisé et on détermine la position des noeuds dudit réseau. 6 - Dispositif de géolocalisation d'un ou de plusieurs noeuds dans un réseau, les noeuds étant équipés d'émetteurs-récepteurs et de moyens de communication caractérisé en ce que chacun des noeuds comporte au moins les éléments suivants : 3055503 14 - Un processeur (41) adapté à exécuter les étapes du procédé selon l'une des revendications 1 à 5, - Un dispositif (44) permettant à un noeud de se géolocaliser, - Une table (43) mémorisant les informations de topologie des autres 5 noeuds. 7 - Dispositif selon la revendication 6 caractérisé en ce que le réseau est un réseau de communication ad-hoc. 10