Brevet FR2987216A1 — publié le 20130823

MÉTHODE DE CARTOGRAPHIE DE SIGNATURES WI-FI PAR COLLECTE AVEUGLE DE MESURES RSS DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne le domaine du positionnement, notamment à l'intérieur de bâtiments (indoor positioning), au moyen de signatures Wi-Fi. Elle a plus particulièrement trait à une méthode de 10 cartographie de telles signatures grâce à une collecte aveugle de mesures RSS (Received Signal Strength). ÉTAT DE LA TECHNIQUE ANTÉRIEURE La méthode de positionnement au moyen de 15 signatures Wi-Fi (Wi-Fi fingerprints) a fait l'objet de nombreuses recherches ces dernières années. Elle s'avère en effet particulièrement prometteuse pour le positionnement dans un environnement où les signaux GPS ne sont que peu, voire pas disponibles, comme les zones 20 situées à l'intérieur de bâtiments (environnement indoor). Le principe d'une telle méthode de positionnement repose sur l'hypothèse que chaque point de la zone considérée peut être caractérisé de manière univoque 25 par les niveaux de puissance (RSS) des signaux Wi-Fi émis par les points d'accès ou APs (Access Points) dans cette zone. Le vecteur constitué par les niveaux de puissance des signaux Wi-Fi reçus en un point est encore dénommé signature Wi-Fi de ce point. 30 Un récepteur (terminal, smartphone) peut alors obtenir sa position en effectuant une mesure des niveaux de puissance des signaux Wi-Fi présents. Cette mesure est comparée avec les signatures Wi-Fi stockées dans une base de données représentant la cartographie RSS de la zone considérée et la position du récepteur est donnée par celle du point possédant la signature Wi-Fi la plus proche de la mesure, au sens d'une certaine métrique. La méthode de positionnement précitée présente toutefois l'inconvénient de nécessiter la constitution préalable d'une base de données contenant la cartographie RSS de la zone considérée. La constitution de la base de données nécessite généralement d'effectuer une campagne de mesures en parcourant systématiquement la zone et en relevant les niveaux RSS avec les coordonnées de chaque point de mesure. Cette contrainte rend la mise en oeuvre d'une telle méthode de positionnement par signature RSS complexe et coûteuse. Il a été récemment proposé une méthode de 20 positionnement, dite WiFi-SLAM (Simultaneous Localization And Mapping), permettant de s'affranchir de la constitution préalable d'une base de données. On pourra en trouver une description dans l'article de B. Ferris et al. intitulé « Wi-Fi SLAM using gaussian 25 process latent variable models » publié dans Proc. of the International Joint Conf. on Artificial Intelligence, 2007, pages 2480-2485. Toutefois, cette méthode repose sur des hypothèses restrictives sur un modèle probabiliste (GP-LVM) entre les niveaux RSS et 30 les positions de mesure qui n'est pas souvent réalisé en pratique. De surcroît, elle ne permet pas d'obtenir un positionnement précis dans un environnement complexe. Un premier but de la présente invention est de proposer une méthode de cartographie de mesures RSS, 5 sans relevé des coordonnées des points de mesure (collecte aveugle de mesures RSS), qui se prête bien à une approche collaborative et puisse être utilisable dans un environnement quelconque. Un second but de la présente invention est de permettre un positionnement 10 qui ne requiert pas de campagne préalable de mesure. EXPOSÉ DE L'INVENTION La présente invention est définie comme une méthode de cartographie de signatures Wi-Fi dans une 15 zone géographique prédéterminée, comprenant : - une étape de collecte de mesures de puissance de signaux Wi-Fi, chaque mesure étant représentée par un vecteur constitué par les niveaux de puissance respectifs de signaux émis par une pluralité de points 20 d'accès Wi-Fi, la collecte desdites mesures étant effectuée séquentiellement le long d'au moins une trajectoire d'un utilisateur au sein de ladite zone géographique, pour fournir au moins une séquence de mesures ; 25 - une étape de détermination d'un graphe représentatif de la trajectoire, chaque mesure de ladite séquence correspondant à un noeud ou à un point unique d'une arête de ce graphe ; - une étape de caractérisation topographique de 30 ladite trajectoire à partir au moins dudit graphe représentatif de la trajectoire et d'un modèle géométrique de la zone géographique, la caractérisation topographique associant à chaque mesure un point du modèle géométrique ; - une étape de stockage de la séquence de mesures 5 dans une base de données, chaque mesure étant stockée en relation avec le point du modèle géométrique qui lui a été associé à l'étape précédente. L'étape de détermination du graphe représentatif de la trajectoire comprend avantageusement le calcul 10 d'une matrice de distances constituée par des distances entre les mesures de ladite séquence, prises deux à deux, les mesures de ladite séquence étant rangées selon un ordre chronologique prédéterminé. L'étape de détermination du graphe représentatif 15 de la trajectoire comprend typiquement les étapes suivantes : - construction d'un premier graphe, dit graphe de voisinage, dont chaque noeud correspond à une mesure de ladite séquence de mesures, deux noeuds du premier 20 graphe étant reliés par une arête si les mesures correspondant à ces noeuds satisfont à un critère de voisinage, ladite arête étant alors affectée d'un poids égal à la distance entre ces mesures ; - construction d'un second graphe, dont les noeuds 25 sont identiques aux noeuds du premier graphe, dit graphe géodésique, deux noeuds du graphe géodésique étant reliés par une arête dont le poids est égal à la longueur du plus court chemin entre ces noeuds dans le graphe de voisinage. 30 Selon une variante, le graphe géodésique est soumis à une réduction de dimension à l'aide d'un algorithme MDS-MAP. Le graphe représentatif de la trajectoire est ensuite obtenu par simplification du graphe géodésique. La simplification du graphe géodésique peut être 5 réalisée notamment au moyen d'une découpe par communautés de ce graphe, après réduction de dimension ou non, les noeuds du graphe représentatif de la trajectoire étant des représentants respectifs des communautés ainsi obtenues. 10 Dans ce cas, la découpe par communautés du graphe géodésique peut être réalisée en - effectuant une analyse par composantes principales des mesures correspondant aux noeuds du graphe géodésique situés dans un voisinage de ce noeud ; 15 - classant par ordre décroissant les valeurs propres obtenues par ladite analyse ; - comparant le rapport de la première à la seconde valeur propre par rapport à un seuil prédéterminé, le noeud étant classé comme étant de premier type, si le 20 rapport est supérieur à ce seuil, et comme étant de second type, dans le cas inverse ; - regroupant dans une même communauté les noeuds du second type satisfaisant à un critère de connectivité prédéterminé. 25 Le critère de connectivité d'un noeud du graphe géodésique peut être le nombre d'arêtes reliées à ce noeud dans le graphe de voisinage. A chaque mesure, on associe un point du graphe 30 représentatif de la trajectoire, ledit point étant défini soit comme un noeud soit comme un point d'une arête de ce graphe. Si le noeud du graphe géodésique représentant ladite mesure fait également partie du graphe représentatif de la trajectoire, la mesure est associée à ce noeud, et, à défaut, le noeud du graphe géodésique, représentant ladite mesure, est projeté sur une arête reliant des premier et second noeuds, la mesure étant alors associée au point obtenu par projection, défini par le couple desdits premier et second noeuds et par un coefficient d'interpolation entre ces noeuds. L'étape de caractérisation topographique de la trajectoire peut comprendre un appariement des noeuds du graphe représentatif de la trajectoire avec les noeuds d'un graphe extrait du modèle géométrique, dit graphe géométrique, et une recherche des arêtes communes au graphe représentatif de la trajectoire et au graphe géométrique. On attribue ensuite à chaque mesure associée à un noeud du graphe représentatif de la trajectoire, la position du noeud du graphe géométrique qui lui est apparié, et l'on attribue à chaque mesure associée à un point d'une arête du graphe représentatif de la trajectoire une position obtenue par interpolation entre les positions des noeuds du graphe géométrique respectivement appariés aux noeuds reliés par cette arête dans ledit graphe représentatif. Pour une mesure donnée, l'interpolation entre les positions des noeuds du graphe géométrique utilise de préférence le même coefficient d'interpolation que celui entre noeuds du graphe représentatif de la trajectoire. Une mesure au moins de la séquence peut être labellisée par un label donnant une information de position. Si la mesure labellisée est associée à un noeud du graphe représentatif de la trajectoire, ce noeud est apparié au noeud du graphe géométrique ayant la position la plus proche de celle donnée par le label de la mesure. 10 BRÈVE DESCRIPTION DES DESSINS La Fig. 1 représente de manière schématique un ordinogramme de la méthode de cartographie de signatures Wi-Fi selon un mode de réalisation de la présente invention ; 15 La Fig. 2 représente un exemple de matrice de distances utilisée dans l'étape de détermination du graphe représentatif de la trajectoire de la Fig. 1 ; La Fig. 3 représente sous forme d'ordinogramme un exemple de réalisation de l'étape de détermination du 20 graphe représentatif de la trajectoire de la Fig. 1 ; La Fig. 4 représente un exemple de matrice d'adjacence calculée à l'étape 320 de la Fig.3 La Fig. 5A représente un graphe géodésique dans lequel ont été identifiés des noeuds du premier type et 25 des noeuds du second type à l'étape 340 de la Fig. 3 ; La Fig. 5B représente un graphe géodésique dans lequel des noeuds singuliers ont été identifiés ; La Fig. 5C représente un graphe représentatif de la trajectoire de l'utilisateur ; 30 La Fig. 5D représente une manière d'associer un noeud du graphe géodésique à un point d'une arête du graphe représentatif de la trajectoire en Fig. 5C ; La Fig. 6 représente sous forme d'ordinogramme un exemple de réalisation de l'étape de caractérisation topographique de la Fig. 1. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS Le principe de base de l'invention est d'utiliser la séquence de mesures d'un utilisateur parcourant la zone pour déterminer un graphe représentatif de sa trajectoire, et effectuer une caractérisation topographique de cette trajectoire à l'aide d'un modèle géométrique de la zone en question. Plus précisément, nous considérons par la suite un utilisateur muni d'un récepteur et parcourant la zone selon une trajectoire quelconque, non connue a priori. L'utilisateur est équipé d'un récepteur de signaux WiFi par exemple un terminal Wi-Fi ou un téléphone intelligent (smartphone) capable de mesurer, et soit d'enregistrer localement soit de transmettre à un serveur distant les niveaux RSS des différents points d'accès. Nous désignerons dans la suite par vecteur de mesure RSS, ou plus simplement par mesure RSS ou encore mesure, un vecteur dont les éléments sont les niveaux de puissance des signaux Wi-Fi reçus des différents points d'accès (AP) de la zone géographique considérée. On suppose que les différents points d'accès sont indexés par leurs identifiants de réseau (BSSID) respectifs et que les éléments du vecteur de mesure RSS sont classés de manière univoque à partir de leurs identifiants. Le récepteur effectue séquentiellement des mesures RSS le long de la trajectoire de l'utilisateur dans ladite zone géographique. Ces mesures peuvent être faites à intervalles réguliers ou non. Si celles-ci ne sont pas effectuées à intervalles réguliers, elles sont avantageusement, mais non nécessairement, horodatées. La séquence chronologique des mesures RSS le long de la trajectoire de l'utilisateur peut être représentée par une matrice : 1 2n N--1 /1 P l 1 - - - P1n - - - PI 2 N-1 /12 P2 P2n /12 P.:2 I 2N-1 N "- Pp Pp ) - - - - - - - - - - - (1) où l'élément ji désigne la ni(i'me mesure de puissance du signal reçu du pième point d'accès. Dans la suite, la matrice M sera également dénommée séquence de mesures RSS ou plus simplement séquence de mesures. La nième mesure de l'utilisateur le long de sa trajectoire sera notée Fin =( )T En règle générale, les mesures RSS obtenues par le récepteur ne sont pas labellisées. Par mesure labellisée, on entend une mesure à laquelle est associée une information de position. Cette information de position permet de situer le lieu de la mesure avec un degré de précision plus ou moins élevé. Certaines mesures RSS d'une séquence peuvent être toutefois labellisées. Ce sera notamment le cas, si des signaux GPS sont disponibles en certains points de mesure (notamment en périphérie de zone indoor) ou bien encore si le récepteur est équipé d'un ou de plusieurs capteur(s) permettant de faire un pointage en certains lieux de la zone considérée. En outre, les mesures RSS peuvent être complétées, le cas échéant, par des mesures physiques de capteurs additionnels (par exemple équipant le téléphone intelligent de l'utilisateur), tels que magnétomètre, accéléromètre, baromètre etc., réalisés de préférence en technologie MEMS. Par souci de simplification, mais sans préjudice de généralisation, l'invention sera exposée pour des mesures RSS seules. L'invention s'applique avantageusement à un contexte collaboratif, c'est-à-dire au cas où plusieurs utilisateurs effectuent des séquences de mesures. On comprendra aussi qu'un même utilisateur peut effectuer des séquences distinctes en parcourant successivement des trajectoires différentes. Les situations précédentes sont susceptibles de relever du même formalisme dès lors que l'on considère une trajectoire composite constituée de K trajectoires d'un ou de plusieurs utilisateur(s). La séquence de mesures à considérer n'est autre que la concaténation des matrices m(K) 1 relatives aux différentes 25 trajectoires considérées. On peut donc se ramener sans perte de généralité à la trajectoire d'un utilisateur, celle-ci pouvant ne pas être connexe. La Fig. 1 représente schématiquement un 30 ordinogramme de la méthode de cartographie RSS selon un mode de réalisation de l'invention. Dans une première étape, 110, on collecte au moins une séquence de mesures RSS d'un utilisateur. Les mesures RSS peuvent être collectées localement au niveau du récepteur avant d'être transmises par bloc à un serveur distant. Alternativement, les mesures peuvent être transmises une par une au serveur. Comme on l'a indiqué plus haut, l'étape de collecte peut concerner plusieurs utilisateurs et donc plusieurs trajectoires, chaque trajectoire d'un utilisateur donnant lieu à une séquence élémentaire de mesures RSS représentée par une matrice MW, la séquence de mesures étant alors représentée par la concaténation de ces matrices. Dans une seconde étape, 120, on détermine à partir de la séquence de mesures collectées un graphe représentatif de la trajectoire considérée, chaque mesure de ladite séquence correspondant à un point (noeud ou point d'une arête) de ce graphe. L'étape 130, dite étape de caractérisation 20 topographique, utilise le graphe représentatif obtenu à l'étape précédente et un modèle géométrique de la zone considérée pour associer à chaque mesure RSS un point correspondant du modèle géométrique. Par modèle géométrique, on entend une représentation simplifiée de 25 la zone considérée, par exemple une représentation filaire de cette zone. Le modèle géométrique peut être un graphe classique de navigation permettant le calcul d'itinéraires entre différents points d'intérêt de cette zone. Le modèle géométrique peut être 30 bidimensionnel ou tridimensionnel selon le type de zone. Dans le cas d'un modèle tridimensionnel, les transitions entre différents niveaux (étages d'un bâtiment par exemple) font partie du modèle géométrique. Enfin, à l'étape 140, on stocke dans une base de 5 données les mesures RSS, chaque mesure étant stockée en relation avec le point du modèle géométrique qui lui a été associé à l'étape précédente. Plus précisément, chaque enregistrement de la base de données comprend une information de position (les coordonnées du point 10 du modèle géométrique) ainsi que les niveaux RSS de la mesure. La base de données contient ainsi une cartographie de signatures Wi-Fi de la zone. Les étapes 110 à 140 peuvent être exécutées selon un processus collaboratif. Autrement dit, la base de 15 données peut être constituée et/ou complétée par des utilisateurs parcourant successivement la zone géographique. L'homme du métier comprendra que la base de données de signatures Wi-Fi peut ensuite être utilisée 20 de manière conventionnelle pour déterminer la position d'un utilisateur. Pour ce faire, le récepteur (terminal équipé d'une carte Wi-Fi, smartphone) de l'utilisateur mesure les niveaux de puissance des différents points d'accès, recherche dans la base de données la signature 25 Wi-Fi la plus proche de cette mesure au sens d'une métrique prédéterminée et récupère les coordonnées du point associé à la signature ainsi obtenue. Le cas échéant, la méthode de positionnement détermine un ensemble de signatures les plus proches de la mesure et 30 effectue un calcul barycentrique à partir des positions associées à ces signatures. Avantageusement, l'utilisateur enrichit la base de données en effectuant une nouvelle séquence de mesures et en la transmettant au serveur, tout en utilisant celles déjà stockées dans la base de données pour son propre positionnement. Les différentes étapes de la méthode de cartographie de signatures Wi-Fi selon l'invention sont détaillées ci-après. La détermination du graphe représentatif de la trajectoire opère sur au moins une séquence de mesures d'un utilisateur ou de plusieurs utilisateurs. Lorsque la base de données est obtenue à partir d'une seule séquence de mesures, la trajectoire de l'utilisateur couvre de préférence l'ensemble de la zone dont on souhaite réaliser la cartographie RSS. Le cas échéant, les séquences de mesure peuvent être regroupées par sous-zones (la zone géographique peut être par exemple divisée en zones élémentaires ou en zones distantes). Le classement par sous-zone peut être réalisé à partir des identifiants (BSSID) des points d'accès. Pour un ensemble de points d'accès donnés, on ne considérera alors que les séquences dont les mesures présentent un niveau RSS non nul (en pratique inférieur à un seuil de bruit) pour au moins l'un des points d'accès de cet ensemble. La détermination du graphe représentatif de la trajectoire fait appel à la notion de matrice de distances (ou matrice de dissimilarité) de deux séquence de mesures, ces séquences de mesures pouvant être distinctes ou non. On introduit tout d'abord un opérateur mathématique D de distance (distance euclidienne, distance de Minkowski, distance de Manhattan, distance de Mahalanobis) entre deux mesures RSS. Cette distance n'est autre que celle entre les vecteurs de taille P représentant ces mesures. Pour estimer la similarité/ dissimilarité entre une première séquence de mesures NI, et une seconde séquence de mesures M2, on calcule la distance entre chaque mesure de M1 et chaque mesure de M2. Si la première séquence est de longueur NI et la seconde séquence de longueur N2, on obtient alors une matrice de distances D(M1,M2) de taille Ai-1> Dans la matrice de distances, les mesures RSS sont rangées selon un ordre chronologique, autrement dit, dans l'ordre de la séquence à laquelle elles appartiennent. Ainsi deux lignes consécutives ou deux colonnes consécutives correspondent à des mesures consécutives. Un bloc rectangulaire dans la matrice de similarité, délimité par les lignes 4 et i2, et les colonnes f et j2 mesure la similarité entre une portion (il à i2) de la première séquence et une portion (j1 à 12) de la seconde séquence. Si un bloc carré de la matrice présente de faibles valeurs (inférieures à un seuil prédéterminé) sur sa diagonale, cela signifie que les deux portions des séquences de mesure sont sensiblement alignées, et correspondent par conséquent à une portion de trajectoire commune, parcourue dans le même sens. De même, si ce même bloc présente de faibles valeurs sur son anti-diagonale, cela signifie que les deux portions des séquences de mesures correspondent à une portion de trajectoire commune, parcourue en sens inverse. Lorsque l'on groupe plusieurs séquences élémentaires MI,M2,...,MQ collectées par un ou plusieurs utilisateurs en une séquence composite M obtenue par 20 concaténation de ces séquences, la matrice de distances de la séquence composite NI, notée D(M,M), donne les matrices de distances des séquences élémentaires qui la composent, soit D(NI,I,N10, q,,l,""Q ainsi que les matrices de distances entre ces séquences, 25 D(1V1q,Mq,) =D(Mq,,Mq) , . En effet, D(M,M) s'exprime comme suit: D(M,M [D(NI'NQ D(M,,1V12) - D(Mi,IVIQ) DO/1[2,NQ D(M2,M2) - D(M2,1VIQ) . . D(VIQ,Mt) D(NIQ,M2) --- D(MQ,MQ)) (2) La Fig. 3 représente un exemple de réalisation de l'étape de détermination du graphe représentatif de la trajectoire dans la Fig. 1. Dans une première étape, 310, on calcule la matrice de distances D(M,M) de la séquence de mesures. Lorsqu'une séquence de mesures Ma, est déjà disponible 10 dans la base de données, la matrice de distances peut être calculée par rapport à cette dernière séquence D(MUML), le reste du traitement étant identique. Pour des raisons de simplification, mais sans perte de généralité, seul le premier sera décrit ci-après. 15 A l'étape 320, on construit un premier graphe, dit graphe de voisinage, V, à partir de la matrice de distances calculée à l'étape précédente. Pour ce faire, on attribue à chaque mesure un noeud du graphe et l'on calcule une matrice d'adjacence Mad de taille NxN (où 20 N est la longueur de la séquence), dont les éléments sont des valeurs binaires telles que a=l si les mesures (correspondant respectivement aux noeuds i,j du graphe) satisfont à un critère de voisinage, et au=0 sinon. 25 Le critère de voisinage est un critère de proximité temporelle et, éventuellement, de similarité. Plus précisément, deux mesures de rangs i,j de la séquence seront considérées comme temporellement proches (et donc voisines) si i-e0. De préférence, on choisit 0=1, autrement dît deux mesures sont considérées comme temporellement proches si elles sont successives et les noeuds qui les représentent sont reliés par une arête. Dans ce cas, pour une séquence de mesures continue temporellement, la diagonale principale de la matrice d'adjacence ainsi que les diagonales secondaires au dessus et au dessous de la diagonale principale sont constituées d'éléments égaux à 1. Alternativement, lorsque les mesures sont horodatées, le critère de proximité temporelle peut porter sur les instants des mesures, deux mesures étant considérée comme proches si ces instants de mesure sont séparés de moins d'un écart temporel T prédéterminé. La matrice d'adjacence comportera alors une bande diagonale de largeur variable d'éléments égaux à 1. A titre d'exemple, on a représenté en Fig. 4 la matrice d'adjacence correspondant à la matrice de distances de la Fig. 2. Les points de cette figure aux indices i,j correspondent à aii=1. Les autres éléments sont nuls. En sus du critère de proximité temporelle, un critère de similarité peut être utilisé. Par exemple deux mesures p. seront considérées comme similaires si leur distance où s est un seuil de distance prédéterminé. Alternativement ou cumulativement, deux mesures seront considérées comme similaires si elles « voient » le même ensemble de points seront {p=1,..,P exemple encore, d' accès. Plus précisément, deux mesures considérées comme voisines si /If > {p . On pourra prendre par pn O. Alternativement ou cumulativement deux mesures seront considérées comme similaires si elles correspondent à un minimum local de la puissance mesurée d'un point d'accès p. Dans tous les cas, si deux mesures gi,pi sont considérées comme temporellement proches ou similaires au sens précédent, au=1, et les noeuds d'indices i,j du graphe de voisinage sont reliés par une arête. On comprendra que le graphe de voisinage comporte un relativement faible nombre d'arêtes. Le poids d'une arête entre noeuds du graphe de voisinage est donné par la distance entre les mesures correspondantes, à savoir D(itiduj. A l'étape 330, on construit un second graphe, dit 20 graphe géodésique, G, à partir du graphe de voisinage, /. Le graphe géodésique, à la différence du graphe de voisinage, est complet. Autrement dit, chaque noeud de G est relié par une arête à chacun des autres noeuds de G. 25 Les poids des arêtes du graphe géodésique sont obtenus à l'aide des plus courts chemins au sein du graphe de voisinage. Plus précisément, si l'on considère l'arête joignant les noeuds i,j du graphe G, le poids c17 de cette arête est donné par la longueur du 9 plus court chemin entre les noeuds i,j du graphe V. Il est important de noter que les poids du, au contraire des distances D(tAti), ont une signification géodésique dans la mesure où ils fournissent une estimation de la distance entre les points de la zone géographique où ont été effectuées ces mesures. Ces distances sont dénommées par la suite distances géodésiques pour bien les distinguer des distances entre mesures J9(gi,110. Le graphe géodésique G relie des points dans un espace de dimension P (espace des mesures). Etant donné que ces mesures ont été prises en des points de dimension 2 ou 3 (espace de la zone géographique), on comprend intuitivement que la matrice M représentant la séquence des mesures soit dégénérée et celles-ci puissent donc être représentées dans un espace de dimension réduite (à savoir 2 ou 3 au lieu de P). Optionnellement, le graphe géodésique fait l'objet d'une réduction de dimension, par exemple grâce à l'algorithme MDS-MAP dont on trouvera par exemple une description dans l'article de C. Ellis et al. intitulé « A comparison of MDS-MAP and non-linear regression » publié dans Proc. of 2010 International Conference on Indoor Positioning and Indoor Navigation (IPIN), 15-17 Sept. 2010, Zurich. Quelle que soit la dimension du graphe géodésique (réduite ou non), celui-ci fait ensuite l'objet d'une simplification à l'étape 340, avantageusement au moyen d'une découpe par communautés (ou clustering). Le but de cette étape est de regrouper les noeuds en agrégats (ou communautés) significatifs. Un exemple préférentiel de réalisation de la découpe par communautés est donné ci-après. Dans un premier temps, pour chaque point du graphe 5 géodésique, on détermine l'ensemble des points situés dans un voisinage de ce point, à moins d'une distance géodésique prédéterminée, 8, de celui-ci. Cette distance géodésique peut être fixée en fonction de la distance géodésique moyenne entre noeuds représentant 10 des mesures successives. Par exemple, si la distance moyenne entre mesures successives est notée ï, le voisinage peut être défini par une boule de rayon ici où K est un facteur strictement supérieur à 1 (par exemple . 15 Le voisinage du noeud ainsi défini, on considère la distribution des noeuds contenus dans ce voisinage et l'on effectue une analyse en composantes principales de cette distribution. L'analyse en composantes principales se fait dans l'espace des mesures ou dans 20 l'espace de dimension réduite selon que l'on a procédé préalablement ou non à la réduction de dimension. L'analyse en composantes principales consiste à calculer les valeurs propres de la matrice de corrélation des coordonnées des noeuds dans l'espace 25 considéré. On classe alors les valeurs propres par ordre décroissant. Si l'on note /1. et '2 respectivement la première et la seconde valeurs propres de la liste, on classe le noeud comme étant d'un premier type si ÂI/À2>>1 et d'un second type dans le cas inverse, c'est- 30 à-dire À, . Plus précisément, le noeud est considéré comme un noeud du premier type si 2122 où p est un seuil d'ellipticité, et du second type dans le cas inverse. Le voisinage d'un noeud du premier type est situé essentiellement le long d'une droite. Un tel noeud sera associé à une arête du graphe représentatif de la trajectoire. En revanche, le voisinage d'un noeud du second type est réparti sans direction privilégiée. Un tel noeud est un candidat au regroupement au sein d'une communauté, comme décrit plus loin. La Fig. 5A représente un exemple de graphe géodésique (dont la dimension a été réduite à 2) dans lequel on a classé les noeuds du premier type (représentés sous forme de croix) et les noeuds du 15 second type (représentés sous forme de carrés). Les noeuds du second type sont regroupés en communautés représentées par les cercles 510. Des noeuds du second type sont regroupés au sein 20 d'une même communauté s'ils satisfont à un critère de connectivité prédéterminé. Par exemple, le critère de connectivité peut être que ces noeuds soient reliés entre eux dans le graphe de voisinage. On peut choisir un critère plus sélectif en ajoutant une condition 25 supplémentaire selon laquelle un noeud ne fait partie d'une communauté donnée que dans la mesure où est relié, dans le graphe de voisinage, à plus de la moitié des noeuds de cette communauté. De nombreux algorithmes de découpe de graphe par 30 communautés (graph clustering) peuvent être utilisés pour déterminer les noeuds de premier et second types, et pour regrouper ces noeuds par type. On pourra notamment se référer à ceux passés en revue dans l'article de S.E. Schaeffer intitulé « Graph clustering » publié dans Computer Science Review I (2007), pages 27-64. On choisit ensuite un représentant par communauté, par exemple le noeud de degré le plus élevé dans le graphe de voisinage ou celui présentant le rapport 21/i2 le plus faible, c'est-à-dire le plus proche de 1. Selon une variante, des noeuds singuliers sont identifiés en sus au sein du graphe géodésique. La Fig. 5B représente le même exemple de graphe géodésique que la Fig. 5A, dans lequel des noeuds singuliers ont été entourés par des cercles 520. Ces noeuds singuliers présentent une configuration locale particulière : ils sont par exemple des extrémités de branches (degré égal à 1 dans le graphe de voisinage) ou des noeuds correspondant à des discontinuités de direction. Ils sont avantageusement caractérisés en considérant le voisinage d'un noeud y et en déterminant pour chaque couple de noeuds (/1,v2) appartenant à ce voisinage, l' angle / I =--(_ vvi,vv2 Si la distribution de l' angle p sur / le voisinage est comprise dans une plage [fimi',8,',] d' étendue inférieure à 360°, le noeud en question peut être identifié comme singulier. Revenant à la Fig. 3, on détermine en 350 le graphe représentatif de la trajectoire, 1-2, à partir du 30 graphe géodésique, G, simplifié à l'étape précédente, comme expliqué plus haut. Dans le cas d'une découpe par communautés, on comprendra que les représentants de ces communautés et, le cas échéant, les noeuds singuliers, constituent les noeuds du graphe Q On a représenté en Fig. 5C un exemple de graphe représentatif de la trajectoire, obtenu à partir du graphe géodésique de la Fig. 5B. Les noeuds 530 sont les noeuds du graphe simplifié obtenu à l'étape 340. Les arêtes du graphe Q sont obtenues de la manière suivante. On considère successivement tous les noeuds y du graphe géodésique hormis ceux qui ont déjà été sélectionnés comme noeuds du graphe Q (par exemple représentants de communautés, noeuds singuliers). Pour chacun de ces noeuds, y, on détermine, au moyen du graphe géodésique, le couple de noeuds (71,72) du graphe O les plus proches de y (au sens de la plus faible distance géodésique). Si une arête E n'est pas présente entre les noeuds h et 72 dans 0, on fait l'hypothèse qu'une telle arête existe. On projette ensuite le noeud y sur l'arête E, la projection étant calculée dans l'espace de mesures ou dans l'espace de dimension réduite selon le cas. Soit yo le point projeté sur cette arête comme indiqué en Fig. 5D. Il 25 est alors possible de déterminer le cosinus de l'angle a formé par 70/ et 7172 au moyen des distances géodésiques d' d et d2 d2 d2 hv YVV I r2 Y2V d soit cosa= et 2d7 d2, dhvo =d /cosa. On vérifie ensuite si cosa>pT (où Pr est un seuil prédéterminé) et si dy0, Lorsque le traitement de tous les points du graphe géodésique est achevé, on a obtenu toutes les arêtes du graphe 1-2, comme représenté en Fig. 5C. A l'étape 360, on associe à chaque mesure un point du graphe 0. Par point du graphe 1-2, on entend soit un noeud y, soit un point d'une arête de Q. Plus précisément, si ladite mesure est représentée par un noeud y de G, deux situations peuvent se présenter : a) lé noeud y de G est également un noeud du graphe 1-2 (par exemple si y est le représentant d'une communauté de G), la mesure est alors associée au noeud y de 1-2 ; b) le noeud y de G n'est pas un noeud du graphe .(-2, la mesure est alors associée au noeud vo, projection de y sur l'arête E reliant le couple des noeuds (71,72) de 1-2 tel que A est le plus proche de y (au sens de la plus faible distance géodésique) et 72 est le noeud o de 1-2 maximisant le cosinus de l'angle a formé par y1v et ho-. La mesure en question est alors associée au couple de noeuds (714 et à un coefficient d'interpolation x entre A et 72. Comme décrit plus haut, la méthode de cartographie de signatures Wi-Fi se poursuit par une caractérisation topographique de la trajectoire, et plus précisément du graphe représentatif Q. Cette caractérisation topographique fait appel à 5 un modèle géométrique de la zone considérée (représentation filaire, graphe de navigation). De préférence, le modèle géométrique se présente sous la forme d'un graphe, dénommé ci-après graphe géométrique F de cette zone. Si le modèle géométrique ne se 10 présente pas sous la forme d'un graphe, il est toujours possible de se ramener au cas précédent en extrayant un graphe du modèle en question. Le cas échéant, plusieurs graphes géométriques peuvent être extraits du modèle géométrique, chaque graphe géométrique correspondant à 15 un degré de résolution différent. Le graphe F comprend des arêtes représentant des axes de déplacement dans la zone (par exemple des couloirs), ces arêtes reliant des noeuds représentant généralement soit des intersections entre axes de 20 déplacement (croisements, changements de direction), soit, pour les noeuds extrémaux, des accès à la zone en question (entrées/sorties). En tout état de cause, les coordonnées (2D ou 3D) de chaque noeud de F sont connues. La position d'un point situé sur une arête de 25 F se déduit simplement par interpolation des coordonnées des noeuds reliés par cette arête. La Fig. 6 représente un exemple de réalisation de la caractérisation topographique du graphe Q. 30 Dans une première étape, 610, on apparie les noeuds du graphe Q à des noeuds du graphe géométrique, F. A cette fin, on peut utiliser des méthodes d'appariement de graphes (graph matching) connues de l'état de la technique, par exemple celle décrite dans l'article de M. Zaslavskiy et al. intitulé « A path following algorithm for the graph matching problem publié dans IEEE Trans. on pattern analysis and machine intelligence, Vol. 31, No. 12, Dec. 2009, pages 2227- 2242. Lorsque la séquence de mesures de départ comprend une mesure labellisée, l'appariement exploite avantageusement cette labellisation pour faciliter l'appariement entre noeuds. Plus précisément, si la mesure labellisée correspond à un noeud du graphe 1-2, ce noeud est apparié au noeud de F ayant la position la plus proche de celle du label. Si la mesure labellisée correspond à un point vo d'une arête E entre deux noeuds A et y2 (avec un rapport d'interpolation x) de 12, les noeuds 7/ et y2 seront respectivement appariés à des noeuds y'1 et 7'2 de F tels que le point -1» obtenu par interpolation entre 7'1 et 7'2 (avec le même rapport d'interpolation) soit le plus proche possible de celle donnée par le label. De manière générale, lorsqu'une mesure est labellisée, l'appariement des noeuds devra respecter au mieux la contrainte de position donnée par le label, par exemple en minimisant une fonction de coût. Enfin, si l'utilisateur est équipé d'un capteur adapté à fournir une information de distance parcourue (podomètre par exemple) ou de direction (gyromètre, 30 magnétomètre, etc.) et que des mesures sont labellisées par cette information (en pratique un enregistrement de la base de données comprend alors, outre les P niveaux RSS, une indication fournie par le capteur), les informations en question peuvent également être exploitées pour faciliter l'appariement. Une fois cet appariement de noeuds réalisé, on détermine en 620, les arêtes communes aux graphes 1-2 et F. Une arête du graphe F peut correspondre (autrement 10 dit être équivalente) à plusieurs arêtes du graphe 1-2. A l'étape 630, on attribue à chaque mesure une position de la manière suivante : Si la mesure correspond à un noeud y du graphe S2 (situation (a) ci-dessus), la position attribuée à la 15 mesure est celle du noeud y' de F apparié avec y. Si la mesure correspond à un point vo d'une arête 72 de G, la position attribuée à la mesure est obtenue par interpolation (avec le même coefficient d'interpolation x caractérisant vo) entre les positions 20 des noeuds et 7'2 de F respectivement appariés avec ri et 2/2. Lorsqu'une mesure est labellisée, celle-ci conserve l'information de position donnée par le label et la position fournie à l'étape 640 peut ne pas lui 25 être associée. Après qu'une position a été attribuée à chaque mesure, les mesures ainsi que leurs positions attribuées respectives sont stockées dans la base de données. On obtient ainsi une cartographie de 30 signatures Wi-Fi. Cette cartographie peut être utilisée par l'utilisateur pour déterminer directement sa trajectoire et a fortiori sa position courante. On remarquera que ce positionnement ne requiert pas de disposer au préalable d'une cartographie de mesures RSS mais qu'au contraire cette cartographie peut être élaborée à partir des mesures effectuées. Dans un mode préférentiel de réalisation, la cartographie de signatures Wi-Fi est élaborée de manière collaborative, chaque utilisateur fournissant simultanément ou successivement une séquence de mesures lors du déplacement le long de sa trajectoire respective. La cartographie de signatures Wi-Fi peut ensuite être utilisée de manière conventionnelle pour permettre à un utilisateur quelconque de se positionner dans la zone à l'aide de la signature Wi-Fi mesurée par son terminal. REVENDICATIONS1. Méthode de cartographie de signatures Wi-Fi dans une zone géographique prédéterminée, caractérisée 5 en ce qu'elle comprend - une étape de collecte de mesures de puissance de signaux Wi-Fi (110), chaque mesure étant représentée par un vecteur constitué par les niveaux de puissance respectifs de signaux émis par une pluralité de points 10 d'accès Wi-Fi, la collecte desdites mesures étant effectuée séquentiellement le long d'au moins une trajectoire d'un utilisateur au sein de ladite zone géographique, pour fournir au moins une séquence de mesures ; 15 -- une étape de détermination d'un graphe représentatif de la trajectoire (120), chaque mesure de ladite séquence correspondant à un noeud ou à un point unique d'une arête de ce graphe ; - une étape de caractérisation topographique de 20 ladite trajectoire (130) à partir au moins dudit graphe représentatif de la trajectoire et d'un modèle géométrique de la zone géographique, la caractérisation topographique associant à chaque mesure un point du modèle géométrique ; 25 - une étape de stockage de la séquence de mesures dans une base de données (140), chaque mesure étant stockée en relation avec le point du modèle géométrique qui lui a été associé à l'étape précédente. 30 2. Méthode de cartographie de signatures Wi-Fi selon la revendication 1, caractérisée en ce quel'étape de détermination du graphe représentatif de la trajectoire (Q) comprend le calcul (310) d'une matrice de distances constituée par des distances entre les mesures de ladite séquence, prises deux à deux, les mesures de ladite séquence étant rangées selon un ordre chronologique prédéterminé. 3. Méthode de cartographie de signatures Wi-Fi selon la revendication 2, caractérisée en ce que la 10 détermination du graphe représentatif de la trajectoire (12) comprend en outre les étapes suivantes : - construction d'un premier graphe (320), dit graphe de voisinage (V), dont chaque noeud correspond à une mesure de ladite séquence de mesures, deux noeuds du 15 premier graphe étant reliés par une arête si les mesures correspondant à ces noeuds satisfont à un critère de voisinage, ladite arête étant alors affectée d'un poids égal à la distance entre ces mesures ; - construction d'un second graphe (330), dont les 20 noeuds sont identiques aux noeuds du premier graphe, dit graphe géodésique (G), deux noeuds du graphe géodésique étant reliés par une arête dont le poids est égal à la longueur du plus court chemin entre ces noeuds dans le graphe de voisinage. 25 4. Méthode de cartographie de signatures Wi-Fi selon la revendication 3, caractérisée en ce que le graphe géodésique est soumis à une réduction de dimension à l'aide d'un algorithme MDS-MAP. 30 5. Méthode de cartographie de signatures Wi-Fiselon la revendication 3 ou 4, caractérisée en ce que le graphe représentatif de la trajectoire est obtenu par simplification (340) du graphe géodésique. 6. Méthode de cartographie de signatures Wi-Fi selon la revendication 5, caractérisée en ce que la simplification du graphe géodésique est réalisée au moyen d'une découpe par communautés de ce graphe, après réduction de dimension ou non, les noeuds du graphe représentatif de la trajectoire étant des représentants respectifs des communautés ainsi obtenues. 7. Méthode de cartographie de signatures Wi-Fi selon la revendication 6, caractérisée en ce que la 15 découpe par communautés du graphe géodésique est réalisée en : - effectuant une analyse par composantes principales des mesures correspondant aux noeuds du graphe géodésique situés dans un voisinage de ce noeud 20 - classant par ordre décroissant les valeurs propres obtenues par ladite analyse ; - comparant le rapport de la première à la seconde valeur propre par rapport à un seuil prédéterminé, le noeud étant classé comme étant de premier type, si le 25 rapport est supérieur à ce seuil, et comme étant de second type, dans le cas inverse ; - regroupant dans une même communauté les noeuds du second type satisfaisant à un critère de connectivité prédéterminé. 30 8. Méthode de cartographie de signatures Wi-Fi selon la revendication 7, caractérisée en ce que lecritère de connectivité d'un noeud du graphe géodésique est le nombre d'arêtes reliées à ce noeud dans le graphe de voisinage. 9. Méthode de cartographie de signatures Wi-Fi selon l'une des revendications 5 à 8, caractérisée en ce qu'a chaque mesure on associe (360) un point du graphe représentatif de la trajectoire, ledit point étant défini soit comme un noeud soit comme un point d'une arête de ce graphe. 10. Méthode de cartographie de signatures Wi-Fi selon la revendication 9, caractérisée en ce que si le noeud du graphe géodésique représentant ladite mesure fait également partie du graphe représentatif de la trajectoire, la mesure est associée à ce noeud, et qu'a défaut, le noeud du graphe géodésique, représentant ladite mesure, est projeté sur une arête reliant des premier et second noeuds, la mesure étant alors associée au point obtenu par projection, défini par le couple desdits premier et second noeuds et par un coefficient d'interpolation entre ces noeuds. 11. Méthode de cartographie de signatures Wi-Fi selon la revendication 10, caractérisée en ce que l'étape de caractérisation topographique (130) de la trajectoire comprend un appariement (610) des noeuds du graphe représentatif de la trajectoire avec les noeuds d'un graphe extrait du modèle géométrique, dit graphe 30 géométrique, et une recherche (620) des arêtes communes au graphe représentatif de la trajectoire et au graphe géométrique. 12. Méthode de cartographie de signatures Wi-Fi selon la revendication 11, caractérisée en ce que l'on attribue à chaque mesure associée à un noeud du graphe 5 représentatif de la trajectoire, la position du noeud du graphe géométrique qui lui est apparié, et que IL' on attribue à chaque mesure associée à un point d' une arête du graphe représentatif de la trajectoire une position obtenue par interpolation entre les positions 10 des noeuds du graphe géométrique respectivement appariés aux noeuds reliés par cette arête dans ledit graphe représentatif. 13. Méthode de cartographie selon la revendication 15 12, caractérisée en ce que, pour une mesure donnée, l'interpolation entre les positions des noeuds du graphe géométrique utilise le même coefficient d'interpolation (x) que celui entre noeuds du graphe représentatif de la trajectoire. 20 14. Méthode de cartographie de signatures Wi-Fi selon l'une des revendications précédentes, caractérisée en ce qu'au moins une mesure est labellisée par un label donnant une information de 25 position. 15. Méthode de cartographie selon l'une des revendications 11 à 14, caractérisée que si la mesure labellisée est associée à un noeud du graphe 30 représentatif de la trajectoire, ce noeud est apparié au noeud du graphe géométrique ayant la position la plus proche de celle donnée par le label de la mesure.