L'invention se rapporte au domaine des réseaux de capteurs sans fil (WSN pour "Wireless Sensor Network" en anglais), c'est-à-dire de capteurs aptes à communiquer entre eux par liaison radio.

L'invention se rapporte plus particulièrement à la localisation de capteurs d'un réseau de capteurs.

Un réseau de capteurs est composé d'une pluralité de capteurs répartis sur une zone géographique. La fonction d'un capteur est de collecter et de transmettre des données relatives à un phénomène que l'on souhaite étudier dans la zone géographique.

11 est important de pouvoir localiser les capteurs dans la zone géographique d'une part pour des raisons de maintenance et d'autre part pour situer où les données sont collectées.

Cette localisation est d'autant plus importante lorsque les capteurs sont mobiles à l'intérieur de la zone géographique.

Le document US2009/0128412 décrit une méthode de localisation de capteurs d'un réseau de capteurs. A cet effet, chaque capteur est équipé d'un module de communication sans fil pour communiquer avec les capteurs du réseau et comporte un module de mesure de distance. Le module de mesure de distance est apte à mesurer la distance séparant le capteur des autres capteurs du réseau ou d'une partie des autres capteurs du Téseau. Les distances mesurées sont ensuite transmises à un serveur de localisation qui détermine, à partir de ces mesures, la localisation absolue des capteurs du réseau.

Cette méthode nécessite la connaissance de la position absolue de plusieurs capteurs, généralement trois. Ces capteurs, appelés "capteurs ancre" permettent au serveur de localisation de déterminer la position absolue des autres capteurs en fonction des mesures de distance reçues.

Un capteur ancre est par exemple un capteur fixe dont la position est connue ou un capteur comportant un module de type GPS (pour "Global Positioning System") ou encore un capteur comportant un module de localisation d'un autre type apte à déterminer 3a position du capteur.

Pour différentes raisons, il n'est pas toujours possible d'avoir un nombre suffisant de capteurs ancre pour localiser les autres capteurs du réseau.

Ces raisons sont par exemple des contraintes d'installations liées au site ou encore des problèmes de consommation d'énergie.

Par exemple, dans le cas d'une application de localisation d'un ensemble de pompiers évoluant sur un site d'intervention pour laquelle chaque pompier est équipé d'un capteur, les capteurs sont tous mobiles. H n'existe pas de capteur Fixe. L'installation, sur les capteurs, d'un module de localisation capable de déterminer leur position et de renvoyer les coordonnées déterminées, est coûteuse.

Il existe donc un besoin d'une solution simple et peu coûteuse pour localiser la position de capteurs d'un réseau de capteurs ne nécessitant pas l'utilisation de capteurs ancre.

L'invention vient améliorer la situation.

A cet effet, l'invention se rapporte à un procédé de localisation de capteurs d'un réseau de capteurs aptes à communiquer entre eux par liaison radio, caractérisé en ce qu'il comprend les étapes suivantes :

- réception, en provenance de capteurs du réseau de capteurs, de mesures de distances relatives entre des capteurs du réseau;

- calcul d'une géométrie du réseau de capteurs à partir des mesures de distance reçues; ladite géométrie comprenant des noeuds représentatifs de capteurs du réseau de capteurs;

- détermination d'une position absolue d'au moins un capteur par ancrage de la géométrie calculée dans un référentiel absolu à partir de contraintes liées à un plan d'environnement du réseau de capteurs.

La position absolue est ainsi obtenue par déplacement de la géométrie dans le plan d'environnement pour qu'elle s'insère dans ce plan en tenant compte des contraintes du plan. Les contraintes liées au plan d'environnement telles que des positions autorisées ou interdites, des trajectoires autorisées pour les capteurs permettent d'obtenir une localisation de la géométrie sur le plan d'environnement. Ainsi, il n'est pas nécessaire d'utiliser des capteurs ancre.

Selon un mode de réalisation particulier du procédé de localisation, les contraintes sont spécifiées dans un graphe d'environnement comprenant un ensemble de positions absolues possibles pour un capteur dans le plan d'environnement. Le graphe d'environnement caractérise les contraintes du plan d'environnement.

Les contraintes sont par exemple des positions autorisées pour les capteurs. Le graphe d'environnement permet une représentation simple et complète de l'ensemble des contraintes.

Selon une caractéristique particulière du procédé de localisation, l'étape de détermination par ancrage comprend :

- une étape de sélection d'un nœud de référence parmi les nœuds de la géométrie;

- une étape de sélection de points d'ancrage parmi les positions absolues du graphe d'environnement;

- une étape de détermination d'un premier vecteur de déplacement et d'un deuxième vecteur de déplacement associé, par point d'ancrage, le premier vecteur de déplacement étant calculé en fonction de la distance entre ledit nœud de référence et le point d'ancrage considéré; - une étape de choix d'un premier vecteur de déplacement et d'un deuxième vecteur de déplacement associé en fonction des premier et deuxième vecteurs déterminés et en fonction d'un premier critère;

- une étape d'application du premier vecteur de déplacement à l'ensemble des nœuds et d'application du deuxième vecteur de déplacement aux nœuds de la géométrie autres que le nœud de référence.

Le premier vecteur de déplacement permet de déterminer la position absolue du nœud de référence. Le deuxième vecteur de référence permet de déterminer la position des autres nœuds tout en conservant la géométrie.

Le nombre de points d'ancrage sélectionnés est un paramètre qui permet de déterminer un compromis entre la précision souhaitée et le nombre de calculs effectués. Le choix de ce paramètre permet une adaptation simple et rapide du procédé au réseau de capteurs utilisé.

Ce type de filtrage, appelé filtrage particulaire, permet une localisation précise.

L'utilisation d'un graphe d'environnement permet de déterminer ia position attendue des capteurs et de limiter ainsi le nombre de points d'ancrage à utiliser.

Selon un mode de réalisation particulier du procédé de localisation, un premier vecteur de déplacement et d'un deuxième vecteur de déplacement associé sont choisis parmi les premiers et deuxièmes vecteurs déterminés.

Les différentes configurations possibles sont évaluées et une des configurations est retenue. Selon un mode de réalisation particulier du procédé de localisation, le premier critère est un score de concordance entre une position absolue des nœuds obtenue par application d'un premier et d'un deuxième vecteurs déterminés et le graphe d'environnement, ledit score de concordance correspondant à la somme de distances entre les nœuds et des points du graphe d'environnement.

Ce critère permet d'obtenir une localisation précise.

Selon un autre mode de réalisation particulier du procédé de localisation, le premier vecteur de déplacement choisi est déterminé en fonction de la distance entre le nœud de référence et un barycentre associé aux premiers vecteurs de déplacement déterminés et le deuxième vecteur de déplacement associé choisi est choisi en fonction d'un angle de rotation moyen.

Le moyennage entre plusieurs positions considérées comme vraisemblables permet d'augmenter la stabilité de la position absolue.

Selon un autre mode de réalisation particulier du procédé de localisation, des valeurs de pondération étant associées aux points d'ancrage, les premier et second vecteurs de déplacement sont choisis en fonction des valeurs de pondération.

Selon un autre mode de réalisation particulier du procédé de localisation, le procédé comporte en outre une étape de mise à jour d'au moins une valeur de pondération des points d'ancrage. Selon un autre mode de réalisation particulier du procédé de localisation, les étapes de réception, de calcul d'une géométrie et de détermination absolue sont réitérées avec les valeurs de pondération mises à jour.

Ainsi, lorsque plusieurs itérations du procédé sont réalisées, la précision de l'estimation de la position absolue est augmentée.

La réitération permet une réévaluation de la position des capteurs et permet ainsi une localisation en temps réel des capteurs.

Selon un autre mode de réalisation particulier du procédé de localisation, le premier vecteur de déplacement est un vecteur de translation et le deuxième vecteur de déplacement est un vecteur de rotation et/ou de symétrie orthogonale

Selon un autre mode de réalisation particulier du procédé de localisation, la détermination du second vecteur de déplacement pour un point d'ancrage comprend:

- une étape de positionnement du nœud de référence sur ledit point d'ancrage ;

- une étape de calcul d'un score d'ancrage représentatif d'une distance entre ies nœuds et le graphe d'environnement pour plusieurs angles de rotation des nœuds autour du nœud de référence et/ou par symétrie ;

- une étape de sélection d'un score d'ancrage parmi les scores obtenus et de l'angle de rotation associé.

Selon un autre mode de réalisation particulier, le procédé de localisation comprend en outre une étape de sélection d'une information relative à la position absolue déterminée pour un capteur et une étape d'émission vers ledit capteur de ladite information

L'invention concerne également un dispositif de localisation de capteurs d'un réseau de capteurs aptes à communiquer entre eux par liaison radio caractérisé en ce qu'il comprend :

- des moyens de réception, en provenance de capteurs du réseau de capteurs, de mesures de distances relatives entre des capteurs du réseau;

- un module de calcul d'une géométrie relative du réseau de capteurs à partir des mesures de distance reçues; ladite géométrie comprenant des nœuds représentatifs de capteurs du réseau de capteurs;

- un module de détermination d'une position absolue d'au moins un capteur par ancrage de la géométrie calculée dans un référentiel absolu à partir de contraintes liées à un plan d'environnement du réseau de capteurs.

L'invention concerne encore un système comprenant un ensemble de capteurs aptes à communiquer entre eux par liaison radio et un dispositif tel que décrit précédemment.

L'invention concerne enfin un produit programme d'ordinateur comprenant des instructions pour mettre en œuvre les étapes du procédé de localisation tel que décrit précédemment, lorsqu'il est chargé et exécuté par un processeur. D'autres particularités et avantages de la présente invention apparaîtront dans la description suivante de modes de réalisation donnés à titre d'exemples non limitatifs, en référence aux dessins annexés, dans lesquels :

- la figure 1 est un schéma illustrant un système de localisation selon un mode de réalisation de l'invention,

- la figure 2 illustre un exemple de graphe d'environnement selon un mode de réalisation de l'invention,

- la figure 3 est un organigramme illustrant les principales étapes d'un procédé de localisation;

- la figure 4 illustre un exemple de graphe de positionnement selon un mode de réalisation de l'invention,

- la figure 4 est un organigramme illustrant les principales étapes d'un procédé de localisation;

- la figure 5 illustre un exemple de table contenant les mesures de distances en provenance des capteurs, selon un mode de réalisation de l'invention,

- la figure 6 est un organigramme illustrant de façon détaillée les différentes étapes d'un procédé de localisation mis en œuvre dans un système de localisation selon un mode de réalisation de l'invention,

- la figure 7 est un schéma bloc représentant un dispositif apte à réaliser les étapes d'un procédé de localisation selon un mode de réalisation de l'invention.

Un mode de réalisation de l'invention va maintenant être décrit en référence aux figures 1 à

5.

En référence à la figure 1, un système SYS comprend N capteurs Cl, C2, C3...Cn et un dispositif de localisation LOC.

Les N capteurs forment un réseau de capteurs.

Les capteurs Cl, C2, C3... comportent un module de mesure MES apte à mesurer la distance le séparant des capteurs voisins et un module d'émission/réception COM apte à transmettre les distances mesurées soit à un capteur voisin, soit au dispositif de localisation LOC au moyen d'une liaison sans fil, par exemple une liaison de type WIFI ou une liaison de type Zigbee ou Wavenis.

De façon connue, les technologies Zigbee ou Wavenis sont des technologies basse consommation.

Les mesures réalisées par un capteur sont transmises au module de LOC soit directement, soit par l'intermédiaire d'un ou plusieurs capteurs. A titre d'alternative, les mesures réalisées par un capteur sont transmises à un module de transmission (non représenté), appelé généralement "puits", par l'intermédiaire d'un ou plusieurs capteurs. Le module de transmission est apte à retransmettre les données reçues au module de localisation LOC par une liaison filaire ou non filaire.

Les capteurs Cl, C2, C3...Cn sont également aptes à retransmettre une mesure de distance reçue d'un autre capteur.

A titre d'alternative, les capteurs Cl, C2, C3...Cn sont également aptes à effectuer des mesures telles que des mesures de relevage de compteur et à les retransmettre.

Le dispositif de localisation LOC comporte un module de communication MCO apte à recevoir des mesures de distances relatives en provenance des capteurs, un module de géométrie TOP et un module de détermination DET de la position absolue d'un capteur.

Le dispositif de localisation LOC comporte également une mémoire MEM dans laquelle est enregistré un plan d'environnement PE.

Dans le mode de réalisation décrit, le plan PE est un plan d'un bâtiment.

A titre d'alternative, le plan P est par exemple une carte routière ou un plan de ville.

La mémoire MEM comporte également un graphe d'environnement GP représentant les positions possibles des capteurs dans le plan PE.

Le graphe d'environnement GP comporte un ensemble de points reliés par des arcs.

La figure 2 illustre un exemple de graphe d'environnement GP pour un plan d'environnement PE.

Dans le mode de réalisation décrit, les capteurs sont mobiles dans le plan d'environnement

PE.

A titre d'alternative, certains capteurs sont fixes. Un premier mode de réalisation du procédé de gestion de l'invention mis en œuvre dans le système SYS va maintenant être décrit en référence aux figures 3 à 5.

En référence à la figure 3, lors d'une étape E2, le module de communication MCO du dispositif de localisation LOC reçoit des mesures de distances en provenance des N capteurs Cl,

C2, C3...Cn. Ces mesures constituent un premier ensemble de mesures.

Les distances mesurées sont enregistrées au fur et à mesure de leur réception dans une table T de la mémoire MEM du dispositif de localisation. Comme illustré sur la figure 4, la table T comporte N lignes et N colonnes. Un élément de la table T, se situant à la ligne i et à la colonne

], correspond à la distance relative entre le capteur i et le capteur j mesurée par le capteur Ci.

L'étape E2 est suivie d'une étape E4 lors de laquelle le module de géométrie TOP du dispositif de localisation LOC calcule une géométrie relative du réseau de capteurs à partir des mesures de distance reçues et enregistrées dans la table T. Par exemple, la géométrie est calculée par utilisation de l'algorithme MDS (pour

"Multidimensional Scaling").

À titre d'alternative, l'algorithme MDS-MAP est utilisé.

Les algorithmes MDS et MDS-MAP sont par exemple décrits dans le document "Sensor Network Localization from local Connectiviry : performance analysis for the MDS-MAP Algorith", August 2009 de S. Oh, A. Karbasi, A. Montanari.

La géométrie obtenue lors de l'étape E4 se présente sous la forme d'un graphe de positionnement GR.

La figure 5 illustre un exemple de graphe de positionnement GR pour un système SYS comprenant 5 capteurs. Les nœuds NI, N2 ...N5 représentent la position relative des capteurs les uns par rapport aux autres.

L'étape E4 est suivie d'une étape E6 lors de laquelle le module de détermination DET du dispositif de localisation LOC détermine une position absolue d'un ou plusieurs capteurs par ancrage de la géométrie calculée dans un référentiel absolu à partir de contraintes liées au plan d'environnement PE du réseau de capteurs.

L'étape de détermination E6 est par exemple réalisée par une technique de filtrage particulaire à M particules.

A titre d'alternative, l'étape de détermination E6 est réalisée par filtrage de Kalman.

Dans un mode de réalisation particulier, les étapes El à E6 sont réitérées. La réitération permet de prendre en compte le déplacement des capteurs dans le réseau et de les faire correspondre avec la structure de l'environnement.

Un mode détaillé de réalisation du procédé de localisation dans lequel l'ancrage est réalisé par filtrage particulaire va maintenant être décrit en référence à la figure 6

Lors d'une étape préalable E0, des particules Pi sont localisées sur le graphe d'environnement GP. Le nombre M de ces particules est choisi en fonction de l'application, de la précision souhaitée pour la localisation et des contraintes de temps de calcul. La position des particules est déterminée de façon à ce que les particules Pi soient réparties sur le graphe d'environnement GP. Chaque particule Pi est représentée par sa position Xpi sur le graphe d'environnement GP. Une valeur de pondération Ai est également associée à chaque particule Pi. Comme il est décrit dans la suite de la description, la valeur de pondération Ai représente la probabilité que la particule Pi représente un nœud de référence déterminé du réseau de capteurs. Lors de cette étape E0, les probabilités Ai sont équiprobables.

Les particules Pi représentent des points d'ancrage.

Dans l'exemple de réalisation décrit ici, le nombre M de particules est de 300 et la valeur de pondération ou probabilité Ai est de 1/300. Egalement lors de l'étape E0, on choisit un capteur parmi l'ensemble de capteurs comme étant un capteur de référence. Ce capteur est par exemple choisi aléatoirement.

Pour l'application considérée ici de localisation de capteurs dans un bâtiment, le nombre 300 permet d'obtenir une bonne précision. Un nombre M trop petit diminue la précision. Un nombre M plus grand augmente le nombre de calculs à effectuer.

Un premier ensemble de mesures de distances relatives est enregistré dans la table T lors de l'étape E2 et un graphe de positionnement GR représentant la géométrie du réseau de capteurs est calculée lors de l'étape E4.

Le nœud NI du graphe de positionnement GR et correspondant au capteur de référence du graphe de positionnement GR est considéré comme étant le nœud de référence.

L'étape E6 de détermination, consécutive à l'étape E4, comporte des sous étapes E604 à

E618.

Lors de la sous étape E604, le graphe de positionnement GR est positionné sur le graphe d'environnement GP de façon à ce que le nœud de référence NI soit positionné sur la particule Pl. En d'autres termes, la position du nœud de référence NI est la position XI de la particule PI et la position des autres nœuds du réseau est recalculée en fonction de la position du nœud NI.

Cette opération consiste en une translation du graphe de positionnement GR. Elle consiste à appliquer un vecteur de déplacement qui est un vecteur de translation, aux nœuds Ni du réseau de capteur. Ce vecteur de déplacement représente un premier vecteur de déplacement.

Lors d'une sous étape E606, la configuration obtenue est testée.

Si, suite à ce déplacement, des nœuds du graphe de positionnement GR se situent en dehors du plan d'environnement PE, la configuration est rejetée.

Sinon, c'est-à-dire si l'ensemble des nœuds du graphe de positionnement GR se situe à l'intérieur du plan d'environnement PE, une distance globale entre le graphe de positionnement GR et le graphe d'environnement GP est calculée (sous étape 608).

Par exemple, la distance globale calculée est la somme des distances entre chaque nœud Ni du graphe de positionnement GR et le graphe d'environnement GP.

La distance entre un nœud Ni et le graphe d'environnement GP est par exemple la distance entre le nœud Ni et le point du graphe d'environnement GP le plus proche.

A titre d'alternative, cette distance prend en compte des caractéristiques du plan d'environnement (contournement de murs du bâtiment par exemple).

Lors d'une étape E610, une rotation d'un angle θ du graphe de positionnement GR autour du nœud NI , c'est-à-dire de la particule PI, est ensuite effectuée.

Par exemple, l'angle θ est de 5 degrés. Ceci revient à appliquer un deuxième vecteur de déplacement aux nœuds de la géométrie qui ne sont pas le nœud de référence. Ce deuxième vecteur de déplacement est un vecteur de rotation d'angle θ,

Les sous étapes E606 à E610 sont alors réitérées avec ce nouveau positionnement du graphe de positionnement GR.

L'étape E610 est réitérée pour tous les angles θ entré 0 et 360°.

On obtient ainsi des distances D(P1,0) correspondant à des deuxièmes vecteurs de déplacement V(P1, θ).

Lors d'une sous étape E612, une symétrie orthogonale du graphe de positionnement GR est effectuée par rapport à un axe, par exemple vertical, passant par le nœud NI .

Les sous étapes E606 à E610 sont réitérées pour l'ensemble des valeurs d'angle θ comprises entre 0 et 360°.

On obtient ainsi des distances DS(P1 ,0) correspondant à des deuxièmes vecteurs de déplacement VS(P1, θ). VS représente ici un vecteur de déplacement qui est la somme d'un vecteur de symétrie orthogonale et d'un vecteur de rotation d'angle θ.

Lors d'une étape E614, une distance Dmin(Pl) est déterminée. La distance Dmin(Pl) est la plus petite parmi l'ensemble des distances calculées pour la particule PI, c'est-à-dire parmi les distances D(P1, θ) et les distances DS(P1, θ).

La distance Dmin(Pl) est la distance déterminée pour la particule PI et est associée au vecteur de déplacement V(P1, θ) ou VS(P1, θ). Le vecteur V(P1, θ) ou VS(P1, θ) représente un deuxième vecteur de déplacement.

Les sous étapes E604 à E614 sont ensuite réitérées avec les (M-l) autres particules.

On obtient ainsi M distances Dmin(Pi), M premiers vecteurs de déplacement et M deuxièmes vecteurs de déplacement associés.

Lors d'une sous étape E616, la valeur de probabilité Ai associée à chaque particule Pi est recalculée, La valeur de probabilité Ai calculée est par exemple obtenue par la formule :

Ai = Ai exp( -Drain (Ρϊ)/2σ ² )

dans laquelle σ est un seuil prédéterminé.

A titre d'alternative, une autre loi associant une probabilité en fonction de la distance entre le graphe de l'environnement et la géométrie du réseau de capteurs est utilisée.

Lors d'une étape E618, la position X la plus probable pour le nœud de référence NI est déterminée.

Dans le mode de réalisation décrit, la position X la plus probable pour le nœud de référence NI est le barycentre de l'ensemble des particules pondérées. A titre d'alternative, la position la plus probable pour le nœud de référence NI est le barycentre de l'ensemble des particules ayant une probabilité Ai supérieure à un seuil prédéterminé.

Egalement à titre d'alternative, la position X la plus probable pour le nœud de référence NI est la position Xi pour laquelle la probabilité Ai est la plus importante parmi les probabilités Ai(Pi).

Encore à titre d'alternative, il n'est pas tenu compte des valeurs de pondération. Les valeurs, de pondération Ai servent dans ce cas uniquement à la sélection des particules pour les itérations suivantes.

Egalement lors de l'étape E618, un premier vecteur de déplacement VDl et une deuxième vecteur de déplacement VD2 sont estimés. Le premier vecteur de déplacement VDl correspond à la translation du nœud de référence NI entre sa position initiale et la position X. Le deuxième vecteur de déplacement VD2 correspond à la rotation du graphe de positionnement GR et éventuellement à une symétrie orthogonale appliquée.

L'étape E6 est suivie d'une étape E8 lors de laquelle on vérifie qu'il n'y a pas dégénérescence du filtre. Lors de cette étape on vérifie que l'inverse de la somme des Ai au carré reste supérieure à un seuil prédéterminé.

Si cette condition n'est pas respectée, une étape E10 d'échantillonnage est déclenchée afin de ramener les particules de probabilité Ai les plus faibles sur celles de probabilité les plus fortes.

Lors de l'étape E12, une nouvelle position Xi est calculée pour chacune des particules Pi

(position tirée aléatoirement, fonction de la précédente position, et contrainte à rester sur le graphe de positionnement GR).

Dans le mode de réalisation décrit, Les étapes E2 à E12 sont ensuite réitérées avec un nouvel ensemble de mesures et en utilisant les particules restantes.

Selon un mode de réalisation choisi et représenté à la figure 7, un dispositif de localisation mettant en œuvre un procédé de localisation selon l'invention est par exemple un ordinateur de type PC 100 qui comporte de façon connue, notamment une unité de traitement 102 équipée d'un microprocesseur, une mémoire morte de type ROM ou EEPROM 103, une mémoire vive de type RAM 104, une interface de communication 105 avec des capteurs par une liaison sans fil.

La mémoire morte 103 comporte des registres mémorisant un programme d'ordinateur PG comportant des instructions de programme adaptées à réaliser les étapes d'un procédé de localisation selon l'invention.

Lors de la mise sous tension, le programme PG stocké dans la mémoire de type EEPROM 103 est transféré dans la mémoire vive qui contiendra alors un code exécutable ainsi que des registres pour mémoriser les variables nécessaires à la mise en œuvre d'une étape de réception, en provenance de capteurs du réseau de capteurs, de mesures de distances relatives entre des capteurs du réseau; d'une étape de calcul d'une géométrie du réseau de capteurs à partir des mesures de distance reçues, ladite géométrie comprenant des nœuds représentatifs de capteurs du réseau de capteurs; et d'une étape de détermination d'une position absolue du capteur par ancrage de la géométrie calculée dans un référentiel absolu à partir de contraintes liées à un plan d'environnement du réseau de capteurs,

De manière plus générale un moyen de stockage, lisible par un ordinateur ou par un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en œuvre les étapes d'un procédé de gestion selon l'invention.