FR 2926142 A1 20090710 FR 0800093 A 20080108 -1- La présente invention concerne un dispositif permettant d'hybrider des informations de localisation en tenant compte de la statistique de ces informations. Celle-ci procède d'un processus itératif permettant d'affiner les mesures de distances par rapport aux différents amers en utilisant la redondance des informations disponibles tant dans le domaine spatial que temporel. Jusqu'à ce jour la combinaison des différentes mesures permettant d'obtenir un positionnement dans l'espace est basé sur l'utilisation d'outils tels que la recherche du moindre carré. La position obtenue représente le meilleur � compromis � par rapport aux informations obtenues sans chercher à les affiner. De plus, la redondance dans le domaine temporel n'est pas prise en compte. Le dispositif selon l'invention permet d'utiliser de façon optimale toutes les informations redondantes disponibles autant dans le domaine spatial que temporel à travers six caractéristiques innovantes. Selon une première caractéristique, il comporte une recherche itérative de la solution 15 optimale. Chaque itération se décompose en passes successives dans le domaine spatial ou temporel. Selon une deuxième caractéristique, chaque passe, spatiale ou temporelle, se base sur des entrées et des sorties pondérées et requiert en entrée des informations sur la vraisemblance de la solution en cours de construction et produit en sortie de nouvelles informations sur la 20 vraisemblance de cette même solution. Selon une troisième caractéristique, les informations d'entrée comportant les mesures prises avec les différents amers sont associées à une estimation de la vraisemblance a priori. Selon une quatrième caractéristique, le dispositif prend une décision ferme sur la localisation du mobile en se basant sur des entrées pondérées représentant des informations de 25 vraisemblance. Selon une cinquième caractéristique, le procédé utilisé lors de chaque passe se base sur des entrées et des sorties pondérées et requiert en entrée des informations sur la vraisemblance de la solution en cours de construction et produit en sortie de nouvelles informations sur la -2- vraisemblance de cette même solution en utilisant l'information extrinsèque extraite des données d'entrée. Selon une sixième caractéristique, la prise de décision finale se base sur des entrées pondérées et requiert en entrée des informations sur la vraisemblance de la solution en cours de 5 construction et produit en sortie des coordonnées de localisation. L'invention est illustrée par les dessins annexes suivants: • La figure 1 présente un dessin schématisant la problématique de localisation, • La figure 2 présente les étapes nécessaires au fonctionnement du dispositif, • La figure 3 présente un schéma d'un mode de réalisation du dispositif. 10 Le but est de pouvoir hybrider de façon optimale un ensemble d'informations de localisation. Les informations utilisées pour la localisation sont de trois types: • des mesures de distance (à partir d'un NMR, un délai de propagation, une carte topographiques...), • des mesures de différences de distances (principalement des différences de délais de 15 propagation entre deux sources synchronisées ou re-synchronisées), • des mesures d'angles (uniquement par triangulation ou en cas d'antennes sectorielles). Ces différentes mesures nous permettent de définir des surfaces dont la nature dépend du type de mesure (sphère dans le premier cas, hyperboloïde dans le deuxième et secteur dans le troisième). 20 Le problème de localisation se résume donc à trouver les points d'intersection entre ces différentes surfaces et à disposer de suffisamment de mesures pour que l'ensemble des points d'intersection se réduise idéalement à un seul point ou de façon plus pragmatique à un ensemble de points dont la distance entre eux est en dessous de la précision recherchée. A chaque instant où nous souhaitons recalculer une position, nous disposons d'un ensemble de 25 mesures. Supposons que nous disposions pour chaque mesure, d'une indication de fiabilité qui n'est autre qu'une indication d'erreur sur la distance sous forme d'une vraisemblance. Nous pouvons donc appliquer un algorithme récursif de correction d'erreur afin de faire converger notre localisation. -3- Pour ce faire, nous devons disposer de différents outils innovants. Nous allons commencer par décrire un procédé de décodage à entrée pondérée et sortie ferme (Décodage de type SIHO (Soft Input Hard Output)). Lors de la réception des mesures, nous avons: [RI= [7-1+[B1 Avec [R]= Ro R1 R n [T]= To T1 Tn Bä Bo B1 [B]= où [R] sont les mesures reçues, [T] les distances exactes et [B] le bruit sur les mesures. Pour n mesures: [Ri , [Tl et [B1 sont de taille n . R. (13) est la distance mesurée entre le mobile M (12) et l'amer A. (11). Le décodage de [R] , selon le critère du Maximum de Vraisemblance a Posteriori (MVP), 10 conduit à prendre la décision: [D]=[T'] si Pr([T]/[R ])> Pr([T']l[R ]), V j ≠i où [T'] est le jème ensemble de distances possibles. [T'] peut être assimilé à un � mot de code � dans le sens où [T' ] doit vérifier que el , A1Mf =T1 . Nous allons nous attacher à présenter une forme discrète de la recherche du MVP. 15 Sur l'ensemble des réels, le nombre de [T'] est infini. Nous allons discrétiser les positions possibles de M sur un maillage de l'espace à pas fixe et constant. Dans le cas où les membres de [T'] sont indépendants entre eux, nous avons: n Pr([T']1[R])=11 Pr(T;IR1) 1=1 Dans le cas d'un bruit blanc gaussien, nous avons: (Ti-R,)2 20 Pr(T;/R1)= 1 .e 2Q' .N/2 rr . rr1 La variance du bruit gaussien n'est pas forcément la même pour tous les R1 car les canaux de propagation ne sont pas systématiquement identiques. Si nous passons en logarithme, nous obtenons: n ln(Pr ([T']/[R]))=I ln(Pr(T'/R1)) 1=1 soit, 1n(Pr([T']/[R]))=E ln( 1 )- z .E (T--R1)2 1-1 2 rr .Q1 1__1 Q1 Maximiser Pr([T']/[R]) revient à maximiser ln(Pr([T n (T/ -R1)2 Ceci revient à minimiser 2 1=1 Q Nous avons donc: [D]-=[T'] si n (T R1)2 Ti).ù R1)2 b' j≠i 2 1=1 O'1 1=1 tT Nous allons nous attacher à rechercher le MVP sur l'ensemble des réels le nombre de [T'] est infini. Pour trouver le maximum nous utiliserons la dérivée pour trouver en quelle point elle s'annule et chercherons donc à annuler la dérivée de 1n(Pr([T']/[R])) . En repartant des équations précédentes, nous avons: d d [Ti] (ln(Pr ([T ]/[R])))=ù12 •n d dT' ( (Tluù2R1)2 ) 1 T'ùR Soit: d[Ti] (ln(Pr([T']/[R])))=ù1 c2 - 4 ]/[R])) d (1n(Pr([T']/[R]))) Annuler d[Ti] n T'ùR1 , revient à: 2 = 0 1=1 Q1 Une approche calculatoire de ce problème consiste à utiliser la forme discrète de façon convergente. Pour cela, nous procédons selon les étapes suivantes: • déterminer une première position grossière (notamment grâce au Cell-Id). On applique un premier maillage pour pouvoir utiliser la forme discrète; • redéfinir un maillage plus fin autour de l'extremum trouvé lors de l'étape précédente 20 tant que la précision sur les valeurs des coordonnées n'est pas suffisante. Il est à noter toutefois que les passes ne renforcent pas la précision par rapport à l'erreur de localisation mais � juste � la précision au sens numérique du terme car ce procédé n'extrait pas d'information supplémentaire. Le deuxième outil est un procédé de décodage à entrée pondérée et sortie pondérée (Décodage de type SISO (Soft Input Soft Output)). Pour pouvoir exploiter ce procédé dans un temps raisonnable, nous allons discrétiser les [T'] . Pour ce faire, nous partons de la valeur initiale de [R] et nous échantillonnons autour de cette valeur par un pas suffisamment fin pour obtenir la précision souhaitée. Le nombre de valeurs discrètes est appelé 5 Dans un cas multivalué, nous définissons le LLR (Logarithm of Likelihood Ratio) de la façon P(T =TII[R]) suivante: LLR (T')= In ' P(T1≠T//[R]) Nous avons: Pr(Ti=T//[R])= f Pr([T]/[R]) [T]oùT =T Pr(Ti≠Tt/[R])=E f Pr([T]/[R]) 141[T]oùT;=T f Pr([T]/[R]) Soit: LLR (Ti )-=- ln J Pr([T]/[R]) 141 [T]oùT;=T Dans une hypothèse d'indépendance des mesures, nous obtenons: n f fJ Pr(Tp/Rp) LLR (Thù In [T]oùT,=T p=1 n f fl Pr(Tp/Rp) I41 [T]oùT;=Tp=1 Pr(Rp/Tp).Pr(Tp) D'après le théorème de Bayes: Pr (Tp/Rp)= Pr(Rp) n Pr(R1/T1=TI).Pr(Ti=T;). f [T Pr(Tp/Rp) [T]oT;=T P=1.p41 LLR (T; )= In n Pr(R1/T; T).Pr(T1 ri). E f [T Pr(Tp/Rp) 1$1 [T]où7 =T; p=1.p4i Soit: n f i i J H Pr(Tp/Rp) i _ IPr(Ri/Ti=Ti) Pr(Ti=Ti) [T]oùT=T P=1,P≠i LLR(T;)ùnPr(Ri/Ti Ti)+InPr(Ti T)+In n Nous pouvons décomposer le LLR en trois composantes. Une partie � conditionnelle �, une partie � a priori � et enfin la partie � extrinsèque �. LLR(T)=Lc(T)+La(T )+Le(T ) Pr(Ti i =T1) La partie � a priori � vaut: La (T;) = I n Pr(T;≠ T;) Nous l'initialiserons à 0 pour la première itération si les informations sont équiprobables mais elle peut aussi être initialisée avec des estimations de la probabilité a priori si elles sont disponibles. Pr (R /T =T') La partie � conditionnelle � vaut: Lc (T;) = I n Pr(Ri/Ti≠T;) Nous allons chercher à l'évaluer. _(R;-T�2 Dans un canal gaussien nous avons: Pr(Ri/Ti)= l 1 .e 2. r V 2 *Tr*Cri Soit: Lc(T;)=In e 2.o- le 2.o lei La partie � extrinsèque � vaut quant à elle: n f fl Pr(Tp/Rp) Le(Ti)=In [T]oùT;=T7 P=1,p≠i n 1 f 1J Pr(Tp/Rp) 141 [T ]oùT;=T; P=1,P≠ i n f fl Pr(T,IRp) Soit: L/ ) [T ]oùT,=TP=1, p≠i Le ( T'=I n n f fl Pr(Tp/Rp) 141 [T ]oùT;=T;P=1,pi Nous allons enfin combiner ces différents outils et nous intéresser au processus itératif lui- f Pr(Tp/ R J ~ p) [T]oùT,≠T; P=1,P≠i -7 même. L'optimisation de la précision des mesures de distances provient de l'utilisation itérative de décodeurs à entrée et sortie pondérées qui travaillent sur des données indépendantes et qui permettent d'extraire des informations extrinsèques grâce à une redondance des informations. Lors de la phase d'initialisation (21), les informations recueillies sont placées dans la matrice [R] dont la dimension k dépend du nombre de passes par itération. Ces informations sont constituées des mesures de distances opérées entre les différents amers. Chaque dimension représente une relation de redondance entre les mesures d'une même ligne. Cette relation doit être indépendante des autres dimensions. Le procédé commence par une phase d'initialisation, dont l'objet est de constituer les matrices [R] et [La] . Ces matrices peuvent comporter une nombre variable de dimensions. Dans le cadre de nos explications, nous nous cantonnerons au cas bidimensionnel ( k=2 ) mais ce procédé peut être étendu de façon non limitative à un nombre quelconque de dimensions. La matrice [R] a alors la forme suivante: Rô Rô ... Rô R° R1 Ri R° m m m La matrice [La] , qui a une dimension supplémentaire qui correspond aux valeurs discrétisées des T; , a la forme suivante: 5 Lao La 5l o o La° Lao o Lal Lafl o o o L 0 L° L o Lap al al al m Laô La° La° m m m La J est la vraisemblance a priori correspondant à la valeur reçue T . Dans ce procédé, la vraisemblance est exprimée par le logarithme du rapport de vraisemblance. [La] est 20 initialisée à 0 si l'on a aucune information a priori à insérer dans le processus de convergence La5gj -8- sinon elle est initialisée avec une estimation du logarithme du rapport de la vraisemblance a priori. Définissons [La(0)] comme la valeur initiale de [La] et [R(0)] comme la valeur initiale de [R ] . Durant une itération, une passe est opérée dans chaque dimension (22 et 23), la passe exploite 5 la relation de redondance de la dimension en question pour générer des informations extrinsèques [Le(r)] à la passe numéro r . A l'issue de la passe r nous aurons: [La(r)]=a(r)•[Le(r)]+[La(rù1)] où a(r) est un coefficient compris entre 0 et 1 permettant de minimiser l'apport des 10 premières informations extrinsèques si il est considéré comme peu fiable. nous évaluons aussi [LLR (r)] . Nous aurons: [LLR(r)]=[La(r)]+[Lc(r)]+[Le(r)] Nous générons alors un nouvelle matrice [R (r) ] qui est constitué des T qui maximisent le LLR (r)? o pour un couple (io, 1) donné. 15 Toutes les k passes constituent une itération. Lors de chaque itération toutes les dimensions ont eu droit à une passe. A la fin de chaque itération, un critère de convergence est appliqué (24). Ce critère est souvent lié à la fois au nombre d'itérations maximum que l'on s'autorise (pour des problèmes de temps de calcul) et à la variation du résultat d'une itération à l'autre (si nous 20 avons convergé sur une position, il est inutile de continuer). Dans le cas où la convergence est jugée insuffisante, une nouvelle itération démarre sinon une décision ferme est prise pour décider de la position finale du mobile à localiser. La décision ferme est prise en utilisant un décodeur à entrée pondérée et sortie ferme. Attachons nous maintenant à décrire un mode de réalisation de ce procédé. Plaçons-nous dans 25 un espace à 2 dimensions. Un mobile est en visibilité de 4 stations que nous considérerons isochrones. Il mesure la distance qui le sépare de ces 4 stations en trois instants consécutifs. Nous supposons que le mobile reste à une position fixe, bien que les principes évoqués dans -9- cet exemple peuvent tout aussi bien être adaptés à un mobile en mouvement. Chaque colonne de la matrice [R] est constituée des mesures avec les 4 stations à un instant donné, et chaque ligne est constituée des différentes mesures par rapport à la même station à chaque instant. Pour plus de facilité, les colonnes seront ordonnées dans l'ordre croissant de temps. Nous avons donc [R ] qui vaut: Ro0 R R R 1 1 R R 2 2 R R 3 3 R; est la mesure de distance par rapport à la ième station au jen~e instant de mesure. Nous commençons par initialiser [R(0)] et [La(0)] (31). Sans connaissance préalable de la position du mobile toutes les mesures seront considérées comme équiprobables. [La(0)] sera donc initialisé à 0. Chaque itération va se dérouler à travers deux passes: une sur le domaine spatial (32), colonne par colonne, et une sur le domaine temporel (33), ligne par ligne. Nous avons une première passe spatiale (32). Reprenons l'équation décrivant l'information 15 extrinsèque: n f Pr(TpIR [T]où p) io iop=1,p#i Ti=T, 1 n f fl Pr(TPIRP) I# j io io p=l,p#i [T ]oùT i,=T i, Dans notre exemple: n R2 0 R2 1 R2 2 R2 3 )= Le(T f II io io P=1, P [T]oùT, =Ti Pr(TpIRp) se décline, dans le sens des colonnes, en une intégrale circulaire sur un cercle de centre la station Si et de rayon que nous appellerons 'o - 10 - n n Pr(Tp/Rp)= o ioP=1,p4i ioP=l,p≠i [T ]oùT il=T i Ci j j Cette intégrale est évaluée pour tous les discrétisés pour permettre le calcul de [Le(r)] . D'un point de vue calculatoire, cette intégration peut se révéler relativement 5 coûteuse. Une très bonne approximation peut être réalisé en utilisant le maximum au lieu de l'intégral. n n io op=l,p≠i ci, p=1,p≠i V2. 7T .O'p [T]oùTi =Ti j Nous avons une seconde passe temporelle (33). Reprenons l'équation décrivant l'information extrinsèque. n f [T Pr(Tp/Rp) io =1, [T]oùT1 =TiioP p#i n f H Pr(Tp/R p) 1#1 o oP=1, P#i [T ]oùT i,=T i, (T oùRp)x Dans le cas d'un bruit blanc gaussien: Pr (T /R )= 1 .e 2'Qp p P VN/2*TT*tep ù(RpùTp)x . e 2.o-P f Soit: 1 \/2.TT.Qp Nous avons alors: 1 e 2.Q' ) H Pr(Tp/Rp),-Max i°( ù(RpùT p)x 10 Repartons de l'équation: Le (T )= ln n Pr(Tp/Rp) [T]oùTii= o i0P=1,P#i Ti se décline, dans le sens des lignes, de la façon suivante: f n n Pr(Tp/Rp)= [T Pr(T;°IRp) f io ioP=l,p≠i p=1,P#i j [T ]oùT i =T i Dans le cas d'un bruit blanc gaussien: i z (T i,ù Rp) Pr(T'f/R )_ .e 1 2.~P P v ^'2*n-*tep i° (T i,ùRp) e 2.Qp n n D'où: f [T Pr(Tp/Rp)= H io iop=1,P#i [T ]oùT i,=T i, 1 - 11 - Nous avons donc les deux passes de définies, il ne nous reste plus qu'à fixer un critère de convergence pour le détecteur de convergence (34). Dans cet exemple de mode d'application, il serait judicieux d'arrêter au bout de 20 itérations ou si toutes les colonnes sont identiques entre elles. Ce procédé novateur peut être la source de beaucoup d'applications industrielles aussi bien de façon centralisée afin d'hybrider un certain nombre d'informations de localisation provenant de sources diverses, que dans un processus de finger printing (recherche de la localisation d'un amer) ou dans un dispositif embarqué et autonome (téléphone mobile, dispositif de navigation automobile...).10 REVENDICATIONS 1. Procédé basé sur des entrées pondérées caractérisé par: • l'utilisation en entrée d'un vecteur de mesures [R ] , entre un mobile M à localiser et différents amers A . aux positions connues, ainsi que d'une indication de leur vraisemblance pour chaque mesure; • l'établissement d'un ensemble de vecteurs de mesures [Ti] satisfaisant une contrainte entre les différentes mesures; • la recherche parmi les vecteurs [Ti] possibles du vecteur [D] qui maximise la vraisemblance � a posteriori �. 2. Procédé, selon la revendication 1, caractérisé par: • le fait que la contrainte utilisée est pour tous les vecteurs de mesure [Ti] `d 1,I AIM =Tr , les mesures convergeant en un point unique de l'espace; • la détermination du point de l'espace localisant M comme le point ayant servi à construire le vecteur [D] 3. Procédé, selon la revendication 2, caractérisé par: • une recherche itérative de la position de M en resserrant à chaque étape la distance entre les points de l'espace associés aux [Ti] autour de la position de M déterminée à l'étape précédente; • l'arrêt de la recherche quand la distance entre les points de l'espace associés aux [Ti] devient inférieure à la précision de positionnement recherchée. 4. Procédé basé sur des entrées pondérées et fournissant des sorties pondérées caractérisé par: • l'utilisation d'un LLR (Logarithm Likelyhood Ratio) dans un cas multivalué; • l'utilisation en entrée d'un vecteur de mesures [R] , entre un mobile M à localiser et différents amers Ai aux positions connues, ainsi que d'une contrainte liant les différentes valeurs de [R ] ; • l'élaboration d'un ensemble de vecteurs de mesures [Ti] de la façon suivante: o pour chaque valeur de [R] est établi un ensemble de valeurs discrètes autour de cette valeur;- 13- o les combinaisons des valeurs discrètes pour chaque valeur de [R] déterminent l'ensemble des vecteurs de mesures [Ti] ; • l'établissement pour chaque vecteur de mesures [T] d'une indication de leur vraisemblance à travers un vecteur [La] représentant la partie � a priori � du LLR; • la détermination du LLR pour les vecteurs de mesures [Ti] en prenant en compte la vraisemblance des mesures à travers la partie � a priori � du LLR [La] ainsi que le type de canal pour déterminer la partie � conditionnelle � et la partie � extrinsèque � du LLR; • la recherche du vecteur de mesures [Td] dans l'ensemble des [Ti] qui maximise le LLR; • l'utilisation du vecteur de mesures [T M ainsi que de la partie � extrinsèque � [Le] de son LLR comme sorties pondérées. 5. Procédé de recherche itérative caractérisé par: • l'établissement d'une matrice de mesures [R] , entre un mobile M à localiser et différents amers Ai aux positions connues, ainsi que pour chaque mesure une indication de leur vraisemblance, chaque dimension de la matrice formant un vecteur de mesures liées par une contrainte; • l'élaboration d'un ensemble de matrices [Ti] de la façon suivante: o pour chaque valeur de [R] est établi un ensemble de valeurs discrètes autour de cette valeur; o les combinaisons des valeurs discrètes pour chaque valeur de [R] déterminent l'ensemble des matrices de mesures [Ti] • l'initialisation d'une matrice [La] présentant pour chaque valeur de [Ti] une valeur d'initialisation de la partie � a priori � du LLR; • l'enchaînement d'itérations décomposées en passes successives, chaque passe successive représentant une utilisation du procédé de la revendication 4 pour chaque dimension de [R] avec pour entrée: o les vecteurs de mesures [T'] correspondant à cette dimension; o les vecteurs [La] , partie � a priori � du LLR, correspondant à cette dimension;- 14- o la contrainte associée à cette dimension; • la recherche de la matrice de mesures [T d] dans l'ensemble des [T'] qui maximise le LLR et la mise à jour de [R] avec les valeurs de [T 'id] ; • la mise à jour de la matrice [La] après chaque passe en lui additionnant la 5 matrice [Le] , sortie souple de la passe courante représentant la partie � extrinsèque � du LLR qui correspond à [T M ] , multipliée par un coefficient compris entre 0 et 1 et pouvant varier entre chaque passe afin de doser l'apport d'informations � extrinsèques �; • la vérification d'un critère de convergence à la fin de chaque itération; 10 . le fait qu'une nouvelle itération commence si le critère n'est pas vérifié. 6. Système de recherche itérative, selon les revendications 2 et 5, caractérisé par: • l'utilisation du procédé 5 avec, pour au moins une dimension de [R] , la contrainte utilisée qui est, pour tous les vecteurs de mesures [Ti] de cette dimension, V1,IAIM=T1 , les mesures convergeant en un point unique de 15 l'espace; • le fait que lorsque le critère de convergence est respecté, la position de M est déterminée à partir de la matrice [R] en utilisant le procédé de la revendication 2.