Domaine de l'invention

Le domaine de l'invention est celui de la localisation de terminaux de télécommunications mobiles et plus généralement de dispositifs de télécommunications mobiles.

L'invention se rapporte plus particulièrement aux techniques de cartographie de mobiles.

L'invention trouve notamment des applications dans les domaines suivants :

- environnement : l'invention permet d'obtenir par exemple une cartographie de capteurs de polluants répartie sur une nappe de pétrole, cette carte renseignant sur la nappe elle-même,

- réalité virtuelle et interaction : l'invention permet d'obtenir une cartographie de capteurs répartis dans l'environnement qui va être utilisée pour interagir avec la réalité virtuelle,

- automobile : l'invention permet d'obtenir une cartographie de véhicules dans lesquels sont disposés des dispositifs de télécommunications mobiles.

Les capteurs, dispositifs et mobiles considérés pour la localisation et la cartographie sont dotés de moyens de télécommunications mobiles. Par la suite, le terme terminal couvre aussi bien un tel capteur, qu'un téléphone mobile, smartphone, i.e. tout dispositif apte à communiquer avec un réseau d'accès de télécommunications mobiles.

Art antérieur

[1] se rapporte à la localisation de nœuds sans fil dans un réseau distribué ad-hoc. L'évolution d'un tel réseau repose sur la capacité à établir des informations sur la localisation des nœuds. Les auteurs décrivent un algorithme basé sur les coordonnées a priori de quelques nœuds localisés dits ancrés et sur la mesure de distance entre paires de nœuds. Les auteurs supposent qu'il y a au moins quatre nœuds ancrés dont les coordonnées sont connues a priori. L'algorithme détermine les positions de nœuds voisins des nœuds ancrés et propage cette connaissance de positionnement à des nœuds distants des nœuds ancrés établissant ainsi une cartographie du réseau. Les distances sont estimées en mesurant la force du signal reçu (RSS: Received Signal Strength). Une telle estimation souffre d'une certaine inexactitude lorsque des obstacles entre l'émetteur et le récepteur affectent le signal transmis et diminuent la puissance reçue ; la distance estimée est alors plus grande qu'elle n'est en réalité. La puissance RSS est en outre très sensible aux effets multi- trajets (multi-path), aux phénomènes d'évanouissement (fading) et aux interférences. L'algorithme nécessite impérativement la connaissance des positions de quatre nœuds ancrés. Et à chaque fois qu'un nouveau nœud veut rejoindre le réseau, l'algorithme utilise tous les nœuds cartographiés pour déterminer la distance du nouveau nœud aux nœuds du réseau. Ce déroulement conduit à beaucoup d'estimations de distances et à beaucoup de signaux transmis pour estimer ces distances.

Exposé de l'invention

L'invention propose un procédé de cartographie flottante à partir des positions relatives de terminaux mobiles synchronisés appartenant à un groupe.

Plus particulièrement, l'invention a pour objet un procédé de cartographie flottante à partir des positions relatives de terminaux mobiles synchronisés appartenant à un groupe, les positions relatives des terminaux du groupe formant une carte flottante. Le procédé utilise uniquement des signaux de télécommunication de terminal à terminal dits signaux D2D pour déterminer les positions relatives des terminaux du groupe. Pour déterminer une carte flottante initiale par un terminal mobile créateur du groupe, le procédé comprend :

- diffusion par le terminal créateur du groupe d'un signal D2D d'information sur le groupe,

- diffusion par un terminal mobile candidat à appartenir au groupe d'un signal D2D de localisation,

- estimation par les terminaux du groupe de distances entre ces terminaux et le terminal candidat à partir du signal D2D de localisation reçu,

- transmission par chaque terminal du groupe au terminal créateur de la distance qu'il a estimée,

- diffusion par le terminal créateur d'un signal D2D d'appartenance au groupe du terminal candidat.

Les étapes de diffusion par le terminal candidat, d'estimation, de transmission et de diffusion d'appartenance au groupe sont itérées jusqu'à atteindre un nombre minimum de terminaux appartenant au groupe. Le nombre minimum est de quatre terminaux soit six distances estimées pour déterminer la carte flottante initiale en deux dimensions et de six terminaux soit quinze distances estimées pour déterminer la carte flottante initiale en trois dimensions. Le procédé comprend en outre pour déterminer la carte flottante initiale :

- détermination par le terminal créateur des positions relatives des terminaux du groupe formant la carte flottante initiale en résolvant un système d'équations correspondant aux distances estimées exprimées par des coordonnées relatives des terminaux du groupe dans un système de coordonnées orthogonales dont l'origine est la position d'un des terminaux du groupe,

- diffusion par le terminal créateur aux terminaux du groupe de la carte flottante initiale.

Dès que le groupe comprend au moins quatre terminaux, respectivement six, une carte flottante initiale en deux dimensions, respectivement en trois dimensions, peut être déterminée et ultérieurement enrichie de la localisation d'autres terminaux.

Contrairement à l'art antérieur, il n'y a aucune obligation que les quatre terminaux initiaux soient des terminaux ancrés ; le procédé s'affranchit de la nécessité de connaître la position de nœuds ancrés.

La carte est dite flottante car elle n'est pas ancrée à une localisation géographique absolue, elle est uniquement formée des positions relatives entre les terminaux mobiles du groupe sans qu'aucun ancrage à une localisation géographique absolue ne soit nécessaire.

Selon le procédé proposé, les positions relatives des terminaux du groupe forment la carte flottante. Ce procédé permet ainsi d'obtenir une cartographie des terminaux du groupe. L'estimation de distance peut être effectuée par exemple en mettant en œuvre une technique « ToA » (Time of Arrivai) ou une technique « DToA » (Différence of Time of Arrivai). Les techniques ToA utilisent une mesure du temps de propagation Tj entre un terminal de référence et le terminal à localiser pour en déduire la distance correspondante CTj avec c la vitesse de propagation de l'onde. La répétition de la mesure pour plusieurs terminaux de référence synchronisés entre eux permet d'obtenir une localisation du terminal relative aux terminaux de référence.

Les techniques « DToA » mesurent des écarts de temps relatifs entre les terminaux, par rapport à un terminal de référence commun aux autres terminaux de référence. Il est en effet nécessaire que la référence de temps soit commune. Ainsi, la position relative des terminaux s'effectue par estimation des temps de propagation relatifs des ondes d'un terminal à localiser aux terminaux de référence et nécessite au moins trois terminaux de référence différents, synchronisés entre eux, pour procéder à une localisation à deux dimensions, correspondant à l'intersection du lieu des points associés à chaque temps de propagation.

Le procédé permet ainsi de déterminer une carte flottante en l'absence de connaissance de la localisation géographique absolue d'aucun des terminaux mobiles. Cette particularité permet une utilisation à l'intérieur de bâtiments dans des environnements où le positionnement GPS ou équivalent (par exemple Iridium) n'est pas toujours accessible. Son utilisation s'affranchit d'un système satellitaire dont l'accès peut être contrôlé, restreint, voire interdit. Le procédé peut s'utiliser en l'absence de couverture d'un réseau d'accès mobile car seul des signaux D2D sont nécessaires. Bien entendu, un réseau d'accès mobile peut être utile mais n'est pas nécessaire pour synchroniser en temps et en fréquence les terminaux. Si un réseau d'accès est présent et qu'il n'y a pas de terminal créateur, la station de base peut éventuellement jouer le rôle du mobile créateur de la carte flottante.

Le procédé ne nécessite pas de mesure d'angle d'arrivée d'un signal ni ne repose sur des signaux acoustiques.

- Selon un mode de réalisation particulier, le groupe comprenant au moins quatre terminaux, le procédé comprend pour l'obtention d'une carte en deux dimensions :diffusion par un terminal mobile candidat à appartenir au groupe d'un signal D2D de localisation,

- estimation par chacun d'au moins trois des terminaux du groupe d'une distance entre ce terminal du groupe et le terminal candidat à partir du signal D2D de localisation reçu, cette distance définissant un cercle de positions relatives possibles du terminal candidat autour du terminal du groupe,

- recherche d'une ou plusieurs intersections des cercles de positions relatives autour des au moins trois terminaux pour déterminer si le terminal candidat appartient au groupe et pour déterminer la position relative du terminal candidat sur la carte flottante.

Selon un mode de réalisation particulier, le groupe comprend en outre au moins deux autres terminaux, le nombre minimum étant de six terminaux pour initialiser une carte en trois dimensions. Le procédé est tel qu'au moins un quatrième terminal du groupe estime une distance entre ce terminal et le terminal candidat à partir du signal D2D de localisation reçu et est tel que la détermination d'une position relative du terminal candidat est effectuée par recherche d'intersections de sphères de positions relatives possibles du terminal candidat autour des au moins quatre terminaux, chaque sphère étant définie par la distance entre un des au moins quatre terminaux et le terminal candidat.

Ce mode permet de déterminer une carte flottante en trois dimensions. Une cartographie en trois dimensions présente particulièrement un intérêt pour une utilisation dans un contexte où les terminaux ne sont pas dans un même plan. Par exemple, les terminaux sont disposés dans un bâtiment à plusieurs niveaux.

Selon un mode de réalisation particulier, l'estimation d'une distance par un terminal du groupe nécessite que le signal D2D de localisation reçu par ce terminal dépasse un seuil dont la valeur courante est prise égale à une première valeur déterminée.

Ainsi, en-dessous du seuil, il est considéré selon ce mode que le signal de localisation reçu n'est pas fiable et qu'il ne peut pas permettre d'estimer une distance précise. Ce mode de réalisation permet d'éviter des calculs inutiles et donc de gérer efficacement l'énergie dépensée par les terminaux.

Selon un mode de réalisation particulier, le terminal créateur recevant de chaque terminal du groupe ayant pu estimer une distance cette distance estimée, le procédé est tel que si la recherche d'intersections permet de déterminer la position relative du terminal candidat et que le nombre de distances estimées reçues est supérieur à un nombre minimum de distances nécessaires alors le terminal créateur détermine une nouvelle valeur supérieure à la valeur courante du seuil et la valeur courante du seuil est prise égale à cette nouvelle valeur.

Ainsi, un des terminaux du groupe est dit créateur car à l'origine de la création du groupe.

Il réceptionne les distances estimées par les autres terminaux du groupe et recherche une interception des cercles ou sphères des positions relatives possibles du terminal candidat autour des terminaux. Lorsque les distances reçues sont en nombre suffisant et permettent de résoudre un système d'équations définissant une intersection ou plusieurs intersections des cercles ou sphères, la carte est enrichie avec la position relative du terminal candidat.

Le terminal créateur compare alors le nombre de distances reçues avec le nombre minimum de distances nécessaire. Si le nombre de distances reçues est supérieur au nombre minimum, l'augmentation du seuil va permettre de faire varier le nombre de distances estimées reçues. Ceci permet de gérer efficacement l'énergie totale dépensée par les terminaux. Si au contraire le nombre de distances reçues est inférieur au nombre minimum ou si une application utilisant la carte flottante a besoin d'une plus grande précision dans la localisation, la diminution du seuil va permettre d'augmenter le nombre de distances estimées reçues. Plus le nombre de distances estimées reçues est important, plus la précision peut être augmentée car la redondance des données va compenser les éventuelles erreurs de mesure.

L'invention a en outre pour objet un terminal mobile dit créateur comprenant :

- un émetteur pour diffuser un signal D2D d'information sur un groupe de terminaux comprenant le terminal créateur dont les positions relatives déterminent une carte flottante,

- un récepteur pour recevoir un signal D2D de localisation diffusé par un terminal mobile candidat à appartenir au groupe et pour recevoir une distance estimée entre un terminal du groupe autre que le terminal créateur et le terminal candidat à partir du signal D2D de localisation,

- un processeur pour estimer une distance entre le terminal créateur et le terminal candidat à partir du signal D2D de localisation reçu, cette distance définissant un cercle ou une sphère de positions relatives possibles du terminal candidat,

- un processeur pour déterminer les positions relatives des terminaux du groupe qui forment une carte flottante initiale en résolvant un système d'équations lorsqu'un nombre minimum de terminaux appartenant au groupe est atteint respectivement de quatre terminaux soit six distances estimées pour une carte en deux dimensions et de six terminaux soit quinze distances estimées pour une carte en trois dimensions, le système d'équations correspondant aux distances estimées exprimées par des coordonnées relatives des terminaux du groupe dans un système de coordonnées orthogonales dont l'origine est le terminal créateur.

Pour déterminer la carte flottante en deux dimensions respectivement en trois dimensions lorsque le groupe comprend au moins quatre terminaux respectivement au moins six terminaux, le processeur est apte à :

- rechercher une ou des intersections des cercles et des sphères de positions relatives autour d'au moins respectivement trois terminaux et quatre terminaux du groupe, déterminer si le terminal candidat appartient au groupe et déterminer la position relative du terminal sur la carte flottante.

Un tel terminal peut bien sûr comporter différentes caractéristiques relatives au procédé de cartographie flottante selon l'invention qui peuvent être combinées ou prises isolément. Ainsi, les caractéristiques et avantages de ce terminal sont les mêmes que ceux du procédé de cartographie flottante et ne sont donc pas détaillés plus amplement.

L'invention a en outre pour objet un système de terminaux mobiles synchronisés formant un groupe mettant en œuvre un procédé de cartographie flottante à partir des positions relatives des terminaux mobiles du groupe, les positions relatives des terminaux du groupe formant une carte flottante, le procédé utilisant uniquement des signaux de télécommunication de terminal à terminal dits signaux D2D pour déterminer les positions relatives des terminaux du groupe. Le système comprend :

- un terminal dit créateur pour diffuser un signal D2D d'information sur le groupe et pour diffuser aux terminaux du groupe une carte flottante initiale,

- des terminaux mobiles candidats à appartenir au groupe aptes à diffuser un signal D2D de localisation à réception du signal d'information sur le groupe.

Le terminal créateur est apte à recevoir le signal D2D de localisation diffusé par un terminal mobile candidat à appartenir au groupe et pour recevoir une distance estimée entre un terminal du groupe autre que le terminal créateur et le terminal candidat à partir du signal D2D de localisation. Le terminal créateur est apte à estimer une distance entre lui-même et le terminal candidat à partir du signal D2D de localisation et apte à déterminer les positions relatives des terminaux du groupe qui forment la carte flottante initiale en résolvant un système d'équations lorsqu'un nombre minimum de terminaux appartenant au groupe est atteint respectivement de quatre terminaux soit six distances estimées pour une carte en deux dimensions et de six terminaux soit quinze distances estimées pour une carte en trois dimensions. Le système d'équations correspond aux distances estimées exprimées par des coordonnées relatives des terminaux du groupe dans un système de coordonnées orthogonales dont l'origine est le terminal créateur.

Pour déterminer la carte flottante en deux dimensions respectivement en trois dimensions lorsque le groupe comprend au moins quatre terminaux respectivement au moins six terminaux, le système est tel que :

- un terminal mobile candidat à appartenir au groupe est apte à diffuser un signal D2D de localisation à réception du signal d'information sur le groupe,

- au moins trois terminaux respectivement quatre du groupe sont aptes à estimer chacun une distance entre ce terminal et le terminal candidat à partir du signal D2D de localisation reçu, cette distance définissant un cercle respectivement une sphère de positions relatives possibles autour du terminal du groupe et

tel que le terminal créateur est apte à rechercher une ou plusieurs intersections des cercles respectivement des sphères de positions relatives autour des au moins trois terminaux pour déterminer si le terminal candidat fait partie du groupe et pour déterminer une position relative du terminal candidat sur la carte flottante.

L'invention a en outre pour avantage qu'un terminal ne peut pas mentir sur sa localisation puisque cette dernière est déterminée à partir de mesures effectuées par d'autres terminaux et non pas déterminées à partir de coordonnées fournies par ce terminal. L'invention bénéficie donc d'une sécurité distribuée qui renforce l'exactitude de la carte flottante.

Un procédé de cartographie flottante selon l'invention peut être implémenté sous la forme d'un ou plusieurs circuits intégrés numériques ou analogiques, ou dans un ou plusieurs composants électroniques de type processeur par exemple un microprocesseur, un FPGA. Ainsi, l'algorithme de cartographie flottante selon l'invention peut être mis en œuvre de diverses manières, notamment sous forme câblée ou sous forme logicielle.

L'invention propose ainsi une nouvelle technique de cartographie flottante pour obtenir simplement une carte des positions relatives de terminaux mobiles appartenant à un groupe.

Dans encore un autre mode de réalisation, l'invention concerne un ou plusieurs programmes d'ordinateur comportant des instructions pour la mise en œuvre d'un procédé de cartographie flottante tels que décrits précédemment, lorsque le ou les programmes sont exécutés par un processeur d'un ou plusieurs terminaux mobiles appartenant au groupe ou voulant appartenir au groupe. De tels programmes peuvent être stockés sur un support d'information.

Liste des figures

D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante de modes de réalisation particuliers, donnés à titre de simples exemples illustratifs et non limitatifs, et des dessins annexés, parmi lesquels :

- la figure 1 est un schéma illustrant une méthode ToA d'estimation de distances entre des terminaux du groupe et un terminal candidat et illustrant une méthode de triangulation,

- la figure 2 est un schéma représentant des étapes d'une phase d'initialisation d'un procédé selon l'invention,

- la figure 3 est un schéma illustrant une zone d'incertitude de la position relative d'un terminal candidat à appartenir au groupe,

- la figure 4 un schéma représentant les étapes principales d'un mode de réalisation d'un procédé selon l'invention,

- la figure 5 est un schéma simplifié d'un terminal créateur selon l'invention.

Description de modes de réalisation de l'invention

Le procédé de cartographie flottante selon l'invention détermine une carte qui comprend les positions relatives des terminaux qui appartiennent à un groupe. Ces positions relatives sont déterminées en exploitant une estimation des distances entre ces terminaux. L'estimation d'une distance entre deux terminaux illustrée par la figure 1 peut être effectuée selon différentes méthodes, par exemple une technique ToA.

Le principe d'estimation d'une distance entre un premier terminal et un second terminal à partir d'une technique ToA (Time of Arrivai) consiste à mesurer l'intervalle de temps δτ entre le signal émis sous la forme d'un Dirac par le premier terminal et le signal correspondant reçu par le second terminal. L'intervalle de temps 5TJ correspond au délai de propagation du signal entre l'émetteur Ti et le récepteur M ou entre l'émetteur M et le récepteur Ti. La vitesse de propagation étant celle de la lumière, la mesure de permet de calculer la distance d _j = c5T _j séparant les terminaux M et Ti.

La précision de la mesure de δτ est liée à la capacité du terminal récepteur à estimer avec précision l'instant d'arrivée du signal en ligne directe (LOS: line-of-sight). La présence de bruit additif au signal reçu et de trajets multiples peuvent rendre l'estimation ardue. Pour améliorer la précision de l'estimation, un moyen consiste à utiliser un signal ultra large bande (UWB : Ultra Wide Band) comme décrit par [2]. Un signal est considéré ultra large bande UWB si le rapport entre sa bande et sa fréquence centrale est plus grand que 0,2 ou si c'est un signal multi bandes avec une largeur totale de bande supérieure à 500MHz.

Lors d'une phase d'initialisation illustrée par l'organigramme de la figure 2, le procédé détermine une carte flottante initiale. Cette carte initiale nécessite un groupe d'au moins quatre terminaux pour une cartographie selon deux dimensions (carte 2D) et d'au moins six terminaux pour une cartographie selon trois dimensions (carte 3D).

Un terminal est dit créateur en ce qu'il initialise la création du groupe Localized cluster de terminaux dont les positions relatives forment la carte initiale.

A l'initialisation, le terminal créateur CH est le seul terminal du groupe. Le terminal CH diffuse un message d'information Group information broadcast (id group, radio resources for Tx/Rx of localization signal, P ) sur le groupe. Cette diffusion se fait au moyen d'un signal de télécommunication de terminal à terminal dit D2D c'est-à-dire sans être relayé par une station de base. Le message Group information broadcast comprend un identifiant id group du groupe Localized cluster, une identification radio resources for Tx/Rx of localization signal des ressources radio pour l'émission et la réception d'un signal de localisation et une valeur seuil P pour une puissance reçue d'un signal de localisation provenant d'un terminal extérieur au groupe, le seuil étant destiné à être utilisé par les terminaux du groupe.

Si un terminal UE qui n'appartient pas au groupe Localized cluster reçoit le message

Group information broadcast du terminal créateur CH et veut intégrer le groupe, il diffuse en retour vers le terminal CH du groupe un signal de localisation Localization signal broadcast.

Le terminal CH du groupe qui reçoit le signal de localisation Localization signal broadcast émit par le terminal UE estime la distance d avec ce terminal UE si la puissance reçue Ps dépasse le seuil P. Si la puissance reçue Ps ne dépasse pas le seuil P alors aucun traitement F n'est possible. Après avoir estimé la distance d, le terminal CH envoie un message d'intégration Intégration message au groupe au terminal UE en lui attribuant un identifiant UEl (UE dedicated number). Après intégration au groupe et pour les besoins d'illustration, la distance entre le terminal CH et le terminal UEl est notée d ₁ . Le groupe est ainsi constitué des terminaux CH et UEl et le terminal CH a connaissance de la distance d ₁ .

Un terminal qui appartient au groupe écoute les signaux de localisation Localization signal broadcast destinés au groupe.

Le terminal créateur CH peut éventuellement diffuser de nouveau un message d'information sur le groupe.

Si un terminal UE qui n'appartient pas encore au groupe reçoit ce message ou le précédent message du terminal créateur CH et veut intégrer le groupe, il diffuse en retour vers les terminaux CH, UEl du groupe un signal de localisation. Si la puissance reçue par le terminal UEl dépasse le seuil alors ce terminal estime la distance au terminal UE et la transmet au terminal créateur CH. Si la puissance reçue par le terminal CH dépasse le seuil alors ce terminal estime la distance d au terminal UE. Après avoir estimé la distance au terminal UE et avoir reçu la distance transmise par le terminal UEl, le terminal CH envoie un message d'intégration au groupe au terminal UE en lui attribuant un identifiant, UE2. Après intégration au groupe et pour les besoins d'illustration, la distance entre le terminal CH et le terminal UE2 est notée d ₂ et la distance entre le terminal UEl et le terminal UE2 est notée d ₁₂ Le groupe est ainsi constitué des terminaux CH, UEl et UE2 et le terminal CH a connaissance des distances d ₁ , d ₂ et d ₁₂ .

Le terminal CH tente de créer la carte initiale à partir des distances d ₁ , d ₂ et d ₁₂ qu'il connaît. Compte tenu qu'aucune position absolue n'est déterminée ou connue, la carte flottante ne peut pas être initialisée à partir de seulement trois terminaux.

Le terminal créateur CH peut éventuellement diffuser de nouveau un message d'information sur le groupe. Si un terminal UE qui n'appartient pas encore au groupe reçoit ce message ou un précédent message du terminal créateur CH et veut intégrer le groupe, il diffuse en retour vers les terminaux CH, UEl, UE2 du groupe un signal de localisation. Si la puissance reçue par le terminal UEl, UE2 dépasse le seuil alors ce terminal estime la distance au terminal UE et la transmet au terminal créateur CH. Si la puissance reçue par le terminal créateur CH dépasse le seuil alors ce terminal estime la distance d au terminal UE. Après avoir estimé la distance au terminal UE et avoir reçu les distances transmises respectivement par les terminaux UEl et UE2, le terminal créateur CH envoie un message d'intégration au groupe au terminal UE en lui attribuant un identifiant, UE3. Après intégration au groupe et pour les besoins d'illustration, la distance entre le terminal CH et le terminal UE3 est notée d ₃ , la distance entre le terminal UEl et le terminal UE3 est notée d ₁₃ et la distance entre le terminal UE2 et le terminal UE3 est notée d ₂₃ . Le groupe est ainsi constitué des terminaux CH, UEl, UE2 et UE3 et le terminal créateur CH a connaissance des distances d , d ₂ , d ₁₂ , d ₃ , d ₁₃ , d ₂₃ .

Le terminal créateur CH tente de créer MAP la carte flottante initiale à partir des distances d ₁ , d ₂ , d ₁₂ , d ₃ , d ₁₃ , d ₂₃ qu'il connaît. La carte flottante initiale est formée des positions relatives des terminaux CH, UEl, UE2 et UE3 du groupe que le terminal créateur CH a pu déterminer à partir de ces distances d ₁ , d ₂ , d ₁₂ , d ₃ , d ₁₃ , d ₂₃ .

En effet, à partir d'un groupe de seulement quatre terminaux et de la connaissance de six distances entre ces terminaux, le procédé peut déterminer la carte flottante initiale dans un système de coordonnées (x, y) orthogonales dont l'origine est prise identique à la position d'un des quatre terminaux du groupe. Ceci peut être considéré comme un théorème (théorème 1), sa preuve est donnée en annexe A.

Chaque distance entre deux terminaux UEi et UEj est associée à une équation de la forme : ^d ij = ^ (yj - yi) ^■

Avec six distances, on a donc six équations pour quatre terminaux avec huit inconnues ; les coordonnées (x;, yi) de chaque terminal UEi. En considérant que le système de coordonnées a pour origine le terminal CH créateur du groupe de coordonnées (0,0) alors le système de six équations ne contient plus que six inconnues, il peut donc théoriquement être résolu et la carte peut être créée.

Si la carte flottante initiale est selon trois dimensions (carte 3D), sa formation nécessite six terminaux dans le groupe et la connaissance par le terminal créateur CH de quinze distances. Avec quinze distances, on a donc quinze équations pour six terminaux avec dix-huit inconnues, les coordonnées (Χι, γι, Ζι) de chaque terminal UEi. En considérant que le système de coordonnées a pour origine le terminal créateur CH du groupe de coordonnées (0,0,0) alors le système de quinze équations ne contient plus que quinze inconnues, il peut donc théoriquement être résolu et la carte peut être créée.

Une fois que la carte initiale map est déterminée, le terminal créateur CH la diffuse dans un message Broadcast map aux terminaux du groupe Localized cluster.

L'intégration d'un nouveau terminal UE dans le groupe nécessite alors uniquement l'implication de trois terminaux CH, UEI, UE2 (carte 2D) ou de quatre terminaux (carte 3D) du groupe pour obtenir la position relative du nouveau terminal. Et la position relative d'un nouveau terminal UE peut être déterminée par triangulation. Le principe de triangulation est illustré par la figure 1.

Dans un plan à deux dimensions, un terminal M est localisé en considérant l'intersection de trois cercles de rayon : d _t = C5TJ . La localisation du terminal M nécessite l'émission de trois signaux issus de trois terminaux Tl, T2, T3 différents synchronisés entre eux ou de manière réciproque la réception par les trois terminaux Tl, T2, T3 du même signal émis par le terminal M. A chaque intervalle de temps 5tj correspondant au délai de propagation du signal entre l'émetteur Tj et le récepteur M est associé un rayon dj = CSTJ de Cercle Cj centré sur le terminal Tj.

Comme illustré par la figure 3 dans le cas 2D, le procédé peut tenir compte d'une marge e d'incertitude sur l'estimation des distances. La marge d'incertitude sur chaque estimation de distance se traduit par une zone d'incertitude dans laquelle peut se trouver la position relative du terminal.

Le déroulement du procédé est illustré par l'organigramme de la figure 4.

Le terminal créateur CH diffuse un message d'information Group information broadcast sur le groupe Localized cluster. Cette diffusion se fait au moyen d'un signal direct dit D2D c'est-à- dire sans être relayé par une station de base. Le message comprend un identifiant id group du groupe, une identification radio resources for Tx/Rx of localization signal des ressources radio pour l'émission et la réception d'un signal de localisation et une valeur seuil P sur une puissance reçue d'un signal de localisation provenant d'un terminal. Les terminaux UEl, UE2 appartenant déjà au groupe et les terminaux UE n'appartenant pas encore au groupe peuvent exploiter le signal reçu.

Si un terminal UE qui n'appartient pas encore au groupe Localized cluster reçoit le message du terminal créateur CH et veut intégrer le groupe, il diffuse en retour vers les terminaux CH, UEl, UE2, UE3 du groupe un signal de localisation Localization signal broadcast.

Un terminal CH, UEl, UE2 du groupe qui reçoit ce signal estime la distance d ₄ , d ₁₄ , d ₂₄ avec ce terminal UE si la puissance reçue Ps dépasse le seuil P. En dessous du seuil P, le signal reçu est considéré comme non fiable, aucun traitement F n'est possible et le terminal du groupe n'effectue pas d'estimation de distance. Si un terminal UEl, UE2 du groupe estime la distance d ₁₄ , d ₂₄ au terminal f/£ ^" , il la communique au terminal créateur CH.

Le principe d'estimation de distance par triangulation appliqué au procédé selon l'invention revient donc dans le cas d'une carte 2D à résoudre un système de trois équations à trois inconnu les coordonnées relatives connues de chacun

des trois terminaux du groupe et (X _j , _j ) les coordonnées relatives du terminal UE h localiser. Pour une carte 2D, l'ajout du nouveau terminal UE nécessite donc uniquement d'estimer trois distances par trois terminaux CH, UEl, UE2 du groupe.

Ainsi, pour n > 4, l'obtention de la carte flottante 2D nécessite uniquement la connaissance de :

6 + 3(n - )(< c£ = 2 -Zl-.) distances avec n le nombre de terminaux dans le groupe, cette relation est démontrée par récurrence en annexe A (corollaire 1).

Pour une carte 3D, l'ajout d'un nouveau terminal nécessite uniquement d'estimer quatre distances par quatre terminaux du groupe. Ainsi, pour n > 6, l'obtention de la carte flottante 3D nécessite la connaissance de :

15 + 4(n - 6)(< C¾ = !li!izl2) distances avec n le nombre de terminaux dans le groupe.

Un avantage du procédé est que l'ajout d'un nouveau terminal UE à la carte flottante ne nécessite pas d'estimer toutes les distances avec tous les terminaux du groupe. En effet, le seuil P est un moyen pour limiter le nombre de distances estimées et éviter ainsi des calculs inutiles. Ce seuil permet d'estimer les distances associées aux signaux les plus forts donc les moins perturbés.

Après avoir estimé la distance au terminal UE et avoir reçu les distances transmises respectivement par les terminaux UEl et UE2 du groupe, le terminal créateur CH vérifie la cohérence des distances entre elles i.e. s'il peut résoudre le système d'équations.

Si le terminal créateur peut déterminer la localisation du terminal UE et enrichir la carte flottante avec cette localisation alors il envoie un message d'intégration au groupe au terminal UE en lui attribuant un identifiant, UE . Le terminal créateur CH ajoute MAJ à la carte flottante la position relative du terminal UE à partir des distances d ₄ , d ₁₄ , d ₂₄ qu'il connaît. La carte flottante est formée des positions relatives des terminaux du groupe, soit selon l'illustration la carte flottante initiale, auxquelles est ajoutée la position relative du terminal UE que le terminal créateur CH a pu déterminer à partir des distancesd ₄ , d ₁₄ , d ₂₄ .

Le groupe est ainsi constitué des terminaux CH, UE1, UE2, UE3 et UE et le terminal créateur CH a connaissance des distances d ₁ , d ₂ , d ₁₂ , d ₃ , d ₁₃ , d ₂₃ , d , d ₁ et d ₂ .

Une fois que la carte map est déterminée, le terminal créateur CH la diffuse dans un message Broadcast map aux terminaux du groupe Localized cluster.

Si une estimation de distance est erronée ou bien lorsque la marge e d'incertitude n'est pas suffisante, le système d'équations peut ne pas être résolu. Compte tenu que la détermination de la position relative du terminal UE ne, nécessite l'intervention que de trois terminaux du groupe, toute autre distance estimée par un autre terminal du groupe est étiquetée comme redondante et ignorée dans un premier temps. Mais lorsque le système d'équations ne peut pas être résolu alors le terminal créateur CH peut prendre en compte une distance redondante, par exemple estimée par le terminal UE3 pour déterminer un nouveau système d'équations. Le terminal créateur CH peut ainsi exploiter les différentes distances redondantes jusqu'à obtenir un nouveau système d'équations pouvant être résolu.

Comme démontré en Annexe A (corollaire 2), dans le cas où le système d'équations ne peut être résolu, le procédé dispose de n— 4 distances redondantes pour déterminer la position relative du terminal UE. Dans le cas d'une cartographie 3D, le procédé dispose de n— 6 distances redondantes pour déterminer la position relative du terminal UE.

Si aucun nouveau système d'équations ne peut être résolu, le procédé peut alors diminuer P i le seuil P de comparaison de la puissance reçue avant une nouvelle émission d'un message d'information Group information broadcast (id group, radio resources for Tx Rx of localization signal, P) sur le groupe pour tenter d'obtenir d'autres signaux exploitables et ainsi obtenir des estimations de distances plus fiables.

La figure 5 illustre la structure simplifiée d'un terminal créateur selon l'invention.

Un terminal créateur CH d'une cartographie flottante d'un groupe de terminaux selon l'invention comprend un processeur μΡ, une mémoire de masse MEM, une mémoire rapide pour le chargement d'un programme Pg, un émetteur/récepteur EM/RE piloté par le processeur, une antenne ANT d'émission et de réception d'un signal. L'activation du procédé de cartographie selon l'invention déclenche le chargement des instructions de code du programme d'ordinateur Pg dans la mémoire rapide depuis la mémoire de masse MEM, puis l'exécution par le processeur μΡ des instructions du programme pour la mise en œuvre du procédé de cartographie selon l'invention.

Selon les instructions du programme : - le processeur détermine un signal D2D d'information sur un groupe de terminaux dont les positions relatives déterminent une carte flottante,

- le processeur pilote l'émetteur pour diffuser le signal D2D d'information,

- le processeur pilote le récepteur pour recevoir un signal D2D de localisation diffusé par un terminal mobile candidat à faire partie du groupe,

- le processeur estime une distance entre le terminal CH et le terminal candidat à partir du signal D2D de localisation reçu, cette distance définissant un cercle ou une sphère de positions relatives possibles du terminal candidat autour de ce terminal CH,

- le processeur pilote le récepteur pour recevoir des distances estimées entre d' autres terminaux du groupe et le terminal candidat à partir du signal D2D de localisation reçu, ces distances définissant d'autres cercles ou sphères de positions relatives possibles du terminal candidat autour de ces autres terminaux du groupe,

- le processeur recherche une ou plusieurs intersections des cercles ou sphères de positions relatives autour d'au moins trois (cercles) ou quatre (sphères) terminaux du groupe pour déterminer une position relative du terminal candidat sur la carte flottante, le terminal candidat devenant un terminal appartenant au groupe si la zone permet de déterminer la position relative du terminal candidat.

Selon des instructions d'initialisation du programme exécutées par exemple lors d'une première activation de application de cartographie :

- le processeur détermine un signal D2D d'information sur un groupe de terminaux dont les positions relatives déterminent une carte flottante,

- le processeur pilote l'émetteur pour diffuser le signal D2D d'information,

- le processeur pilote le récepteur pour recevoir un signal D2D de localisation diffusé par un terminal mobile candidat à faire partie du groupe,

- le processeur estime une distance entre le terminal CH et le terminal candidat à partir du signal D2D de localisation reçu, la distance définissant un cercle ou une sphère de positions relatives possibles du terminal candidat autour de ce terminal CH,

- le processeur pilote le récepteur pour recevoir des distances estimées par d'autres terminaux du groupe à partir du signal D2D de localisation reçu, chaque distance définissant un cercle ou une sphère de positions relatives possibles du terminal candidat autour d'un terminal du groupe,

- le processeur recherche une ou plusieurs intersections des cercles ou sphères préalablement définis de positions relatives pour déterminer une position relative du terminal candidat sur la carte flottante,

- le processeur pilote l'émetteur pour diffuser un signal D2D d'appartenance au groupe du terminal candidat uniquement si la zone permet de déterminer la position relative du terminal candidat. Références :

[1] : C. Savarese, J. Rabaey, J. Beutel, "Locationing In Distributed Ad-Hoc Wireless Sensor Networks", ICASSP 2001

[2] : S. Gezici, Z. Tian, G.B. Giannakis, H. Kobayashi, A.F. Molisch, H.V. Poor, and Z. Sahinoglu, "Localization via ultra-wideband radios," IEEE Signal Processing Mag., vol. 22, no. 4, pp. 70-84, July 2005

Annexe A

Théorème 1 : à partir d'un groupe de seulement n = 4 terminaux et de la connaissance de = 6 distances £ M entre les terminaux UEi et UEj le procédé peut déterminer la carte flottante initiale dans un système de coordonnées (x, y) orthogonales dont l'origine est prise identique à la position d'un des quatre terminaux du groupe. M est l'ensemble des réels.

Preuve :

On considère n terminaux UEs connectés entre eux :

UEl de coordonnées (x , y ) est connecté aux n— 1 autres terminaux avec n— 1 distances dy avec j > 1

UE2 est aussi connecté à n— 1 UEs avec n— 2 nouvelles distances d ₂ j avec j > 1 puisque d ₁₂ = d _2i ,

UEn— 1 est aussi connecté à n— 1 UEs avec 1 nouvelle distance d _n _ _ln . Ainsi, nous av — i) = n(n— l)/2 valeurs de distances qui correspondent à combinaisons de distances.

La localisation de tous les terminaux n'est pas connue sauf celle du terminal UEl qui est choisi comme étant l'origine du système de coordonnées orthogonales (donc de la carte flottante) i.e. (x , y ) = (0, 0). Il reste donc 2(n— 1) coordonnées d' UEs inconnues.

Les distances peuvent être exprimées en fonction des coordonnées sous la forme suivante :

Il s'agit d'un système non linéaire de n(n— l)/2 équations avec 2(n— 1) variables inconnues.

Pour résoudre ce système il faut au moins que ⁿ ^ ⁿ ^ > 2(n— 1) soit n > 4.

On peut observer que le système d'équations précédent n'a pas une unique solution. Ceci est démontré sur la base de l'exemple suivant : n = 4 UEs, on dispose de entre les terminaux UE1, UE2, UE3 et UE4. Choisissons :

UE1 de coordonnées ( i, yi) = (0, 0) et tel que d ₁₂ = 1, di3 = 2, d ₁₄ = -J5

i/£2 tel que d ₂₃ = 1, d ₂ 4 ⁼ 2

i/£3 tel que d ₃₄ = 1

En remplaçant ces valeurs dans le système d'équations, il vient :

Il y a donc un nombre infini de solutions qui dépendent de la coordonnée x ₂ . Mais toutes les solutions fournissent la même carte flottante à une rotation près prise entre 0° et 360°. L'unicité de la carte dépend de la valeur de x ₂ . La connaissance de x ₂ permet de déterminer chaque coordonnées des terminaux du groupe donc de déterminer la carte flottante.

Fin de la preuve.

Corollaire 1

Pour n > 4, l'obtention de la carte flottante 2D nécessite uniquement la connaissance de :

6 + 3(n - 4)(< = Z-i- -il) distances avec n le nombre de terminaux dans le groupe.

Preuve par récurrence :

initialisation : ί = 5

Compte tenu du théorème 1 pour ί = 4 UEs il faut = 6 valeurs de distances.

Si on ajoute un terminal UE à cette carte, on a seulement besoin de trois distances supplémentaires d _5fe pour 1 < k≤ 4 en appliquant une méthode de triangulation. Le nombre maximum de distances pouvant être obtenu pour construire cette carte est = 10. On a ainsi besoin en tout de 6 + 3 = 6 + 3(5 - 4) = 9 < 10 distances,

étape ί = 6 :

Pour une carte de cinq terminaux UEs il faut neuf distances. Pour ajouter un terminal à cette carte, il faut trois distances supplémentaires d _ek pour 1 < k≤ 5 en appliquant une méthode de triangulation. Soit en tout (6 + 3) + 3 = 6 + 3 (6— 4) = 12 < C ² , = 15 distances,

étape i = n :

On a besoin en tout de 6 + 3(n - 4) < = n(n - l)/2. étape ί = n + 1 :

On a besoin en tout de :

+ n = + n = = C* ₊₁ , soit :

Fin de la preuve

Corollaire 2 :

dans le cas où le système d'équations ne peut être résolu à cause d'une erreur d'estimation d'une distance, le procédé dispose de n— 4 distances redondantes pour déterminer la position relative du terminal pour n > 4.

Preuve :

Pour ajouter un terminal n à la carte flottante, il faut [6 + 3(n— 4)]— [6 + 3 (n— 1— 4)] = 3 distances supplémentaires (corollaire 1). Mais on dispose au total de n— 1 nouvelles distances d _nk pour 1 < < n— 1. On dispose donc de n— 1— 3 = n— 4 distances additionnelles dites redondantes.

Fin de la preuve