Brevet FR2923971A1 — publié le 20090522

La présente invention se situe dans le domaine des réseaux de capteurs sans fil (WSN pour Wireless Sensor Network en anglais). Un réseau de capteurs sans fil est composé d'un grand nombre (jusqu'à plusieurs dizaines de milliers) de capteurs ou noeuds de taille réduite. Ces noeuds sont positionnés aléatoirement dans une zone géographique d'observation. La fonction d'un noeud est de collecter et de transmettre des données relativement à un phénomène que l'on souhaite étudier dans la zone d'observation considérée. Les données ainsi collectées au niveau d'un noeud source sont intégrées dans un message. Ce message est transmis à un noeud destination ou encore noeud puits (pour sink node en anglais) grâce à l'utilisation d'un protocole de routage dans le réseau de noeuds. Un protocole de routage sert à trouver une succession de noeuds à atteindre pour transmettre un message d'un noeud source à un noeud puits, en consommant le moins d'énergie possible. La succession de noeuds constitue un chemin et le passage d'un noeud à un autre se fait par saut. On parle alors de chemin multi-sauts. Les techniques de routage les plus anciennes reposent sur la création d'une structure organisée entre les différents noeuds constitutifs du réseau, comme par exemple le regroupement de noeuds en grappes (pour clusters en anglais). Ensuite, un protocole de routage hiérarchique est appliqué à la structure. Ces techniques nécessitent une détection régulière par les noeuds des changements au sein de la structure, ce qui consomme beaucoup d'énergie. D'autres techniques proposent des protocoles de routage géographique. L'utilisation d'un tel protocole implique que chaque noeud connaisse parfaitement sa localisation. Pour des réseaux comportant peu de noeuds, ceci peut être réalisé en plaçant les noeuds en des points préalablement connus et en programmant manuellement leur localisation. Pour des réseaux de plus grande ampleur, les noeuds peuvent être équipés d'un système de géolocalisation par satellite (GPS pour Global Positioning System en anglais). Quelle que soit la taille du réseau, il n'est pas facile de connaître parfaitement la localisation d'un noeud et la mise en oeuvre d'un tel protocole est coûteuse. Pour résoudre cette difficulté, certaines techniques proposent des protocoles de routage géographique pour lesquels la localisation d'un noeud se déduit de la position d'un ensemble de noeuds "ancres" (pour anchor nodes en anglais). Seuls les noeuds "ancres", dont le nombre est limité, ont besoin de connaître parfaitement leur localisation. Comme il n'en demeure pas moins difficile de connaître parfaitement la localisation d'un noeud "ancre", les techniques de routage les plus récentes proposent d'utiliser des coordonnées relatives d'un noeud par rapport à ces noeuds "ancre", ceux-ci ne connaissant pas aussi eux-mêmes leurs coordonnées réelles. De telles techniques sont exposées dans l'article de Q. Cao et de T. Abdelzaher, intitulé "A scalable logical coordinates framework for routing in wireless sensor networks", dans 25th IEEE International Real-Time Systems Symposium (RTSS), IEEE, 2004 et dans l'article de R. Fonseca et al., intitulé "Beacon vector routing: Scalable point-to-point routing in wireless sensornets", dans Networked Systems Design & Implementation (NSDI), 2005. Dans ces deux articles, les coordonnées relatives d'un noeud sont définies comme un vecteur de nombre de sauts nécessaires pour atteindre chacun des noeuds "ancres". Un inconvénient de ces techniques est que plusieurs noeuds peuvent avoir les mêmes coordonnées. De plus, les chemins trouvés par les protocoles de routage géographique utilisés sont longs, ce qui représente un autre inconvénient. Les techniques utilisant des coordonnées relatives d'un noeud par rapport à un ensemble de noeuds "ancres" nécessitent également une phase d'initialisation pour mesurer la distance entre un noeud et les différents noeuds "ancres". Or, une telle phase consomme du temps et de l'énergie. De plus, comme des noeuds apparaissent ou disparaissent dans le réseau, la représentation de celui-ci évolue et une mise à jour est nécessaire. Il existe donc un réel besoin de disposer d'une méthode de détermination des coordonnées d'un noeud dans un réseau qui ne présente pas les inconvénients précités des techniques connues. Ainsi, la présente invention concerne, selon un premier aspect, un procédé de détermination des coordonnées d'un noeud courant dans un réseau de noeuds dans lequel un message est transmis du noeud courant à un noeud suivant, qui comporte des étapes de : - initialisation aléatoire de coordonnées virtuelles pour chacun des noeuds du réseau, - mise à jour des coordonnées virtuelles du noeud courant à chaque transmission d'un message au noeud suivant. La détermination des coordonnées des noeuds d'un réseau selon l'invention s'affranchit de l'identification de noeuds "ancres" et de la connaissance de leurs coordonnées des techniques connues. Les noeuds ayant des coordonnées virtuelles, initialisées aléatoirement, celles-ci sont indépendantes de la localisation géographique des noeuds dans le réseau. La phase d'initialisation n'est pas coûteuse à réaliser puisqu'il n'est plus nécessaire de connaître parfaitement la localisation géographique des noeuds. Comme la mise à jour des coordonnées virtuelles d'un noeud courant ne se fait que lorsque celui-ci transmet un message, cette mise à jour ne requiert aucun moyen supplémentaire (en particulier, aucune communication) par rapport à ceux mis en oeuvre par le protocole de routage. De plus, il n'est pas nécessaire de mettre à jour les coordonnées virtuelles des noeuds courants lorsqu'aucun message ne circule. Cette technique permet donc d'économiser de l'énergie. Selon une caractéristique préférée, le procédé selon l'invention comporte, en outre, des étapes de : - identification de noeuds voisins du noeud courant, - récupération des coordonnées virtuelles des noeuds voisins par le noeud courant. Selon une caractéristique préférée, la mise à jour des coordonnées virtuelles du noeud courant s'effectue en leur affectant la moyenne des coordonnées virtuelles respectives des noeuds voisins. La configuration du réseau peut évoluer facilement et cette évolution est prise en compte par le procédé de détermination des coordonnées virtuelles d'un noeud de l'invention. En particulier, de nouveaux noeuds peuvent apparaître et certains noeuds du réseau peuvent disparaître tout au long de la vie du réseau. Ces apparitions et disparitions sont prises en compte lors de la mise à jour des coordonnées virtuelles d'un noeud, en fonction des coordonnées virtuelles des noeuds voisins. Par ailleurs, la mise à jour des coordonnées virtuelles permet de déterminer des chemins ayant un nombre de sauts très faible. Le faible nombre de sauts se traduit par une dépense en énergie réduite lors de la transmission d'un message d'un noeud source à un noeud puits le long d'un chemin et donc par un allongement de la durée de vie du réseau. Selon une caractéristique préférée, le procédé selon l'invention comporte une étape facultative de mise à jour des coordonnées virtuelles d'au moins un noeud voisin du noeud courant lorsque la distance virtuelle entre le au moins noeud voisin et le noeud courant est inférieure à un seuil donné. Ainsi, l'actualisation des coordonnées virtuelles des noeuds voisins, lorsque la distance avec le noeud courant tombe en dessous d'un certain seuil, permet de déterminer plus rapidement des chemins ayant un nombre de sauts très faible. L'invention concerne aussi un dispositif de détermination des coordonnées d'un noeud courant dans un réseau de noeuds dans lequel un message est transmis du noeud courant à un noeud suivant, comportant : - un module d'initialisation aléatoire de coordonnées virtuelles pour chacun des noeuds du réseau, - un module de mise à jour des coordonnées virtuelles du noeud courant à chaque transmission d'un message au noeud suivant. L'invention concerne également un objet communicant apte à recevoir un dispositif ci-dessus. L'invention porte aussi sur un produit programme d'ordinateur comportant des instructions de programme pour l'exécution du procédé de détermination des coordonnées d'un noeud courant dans un réseau de noeuds, dans lequel un message est transmis du noeud courant à un noeud suivant, tel que décrit ci-dessus. L'invention sera mieux comprise à la lumière de la description qui suit d'un mode particulier de réalisation du procédé, selon l'invention, de détermination des coordonnées d'un noeud dans un réseau de noeuds en référence aux dessins annexés sur lesquels : la figure 1 représente un exemple d'un réseau de noeuds, - la figure 2 représente le procédé selon l'invention, - la figure 3 représente un dispositif apte à mettre en oeuvre le procédé de la figure 2, - la figure 4 représente les résultats d'un test de mise en oeuvre du procédé de la figure 2. L'invention est décrite ci-dessous pour un mode particulier de réalisation dans lequel un message est transmis, à travers un réseau de noeuds, d'un noeud source vers un noeud destination ou puits. La transmission du message du noeud source vers le noeud puits s'effectue par sauts successifs d'un noeud à l'autre. A chaque saut, le message est transmis d'un noeud courant à un noeud suivant. La figure 1 représente un exemple d'un réseau de noeuds. Ces noeuds, qui peuvent, à titre d'exemple, être des capteurs, sont répartis dans une zone d'observation Z. Le réseau de noeuds de la figure 1 comporte un noeud source S, un noeud puits P et un ensemble de noeuds M, N, V, W, X, Y. V représente un noeud courant, c'est-à-dire un noeud en possession d'un message à transmettre. La figure 2 représente le procédé selon l'invention de détermination des coordonnées d'un noeud dans un réseau de noeuds. Ce procédé comporte une étape 21 d'initialisation des coordonnées de chacun des noeuds du réseau. On considère, par exemple, que la zone d'observation est un espace à deux dimensions. Les coordonnées des noeuds du réseau sont alors représentées par un vecteur à deux dimensions du type (I,J), où I et J sont des réels définis aléatoirement entre 0 et une valeur maximale positive DimMax, elle aussi définie aléatoirement. Tous les noeuds du réseau connaissent a priori la même valeur maximale DimMax. Au cours de cette étape 21, chacun des noeuds N du réseau de coordonnées (N1, N2) choisit aléatoirement chacune de ses coordonnées N1 et N2 entre 0 et DimMax. Le noeud puits P a pour coordonnées (P1, P2). Les coordonnées (P1, P2) sont définies arbitrairement, par exemple (0,0). Tous les noeuds du réseau connaissent et utilisent les mêmes coordonnées (P1, P2) pour le puits. Les coordonnées initiales des noeuds du réseau ainsi définies sont virtuelles, aléatoires et indépendantes de la position géographique de ces différents noeuds dans l'espace d'observation. On appelle distance virtuelle d(M,N) entre deux noeuds M et N, de coordonnées virtuelles respectives (M1, M2) et (N1, N2), la distance euclidienne séparant leurs coordonnées virtuelles. La distance d(V,W) se définit de la façon suivante : d(M,N)=V(M1 ùN1)2 +(M2 ùN2)2 Chaque noeud choisit chacune de ses deux coordonnées virtuelles étant choisies aléatoirement entre 0 et DimMax lorsqu'il est mis en route (ou allumé) dans le réseau. La distance virtuelle étant calculée à partir de ces coordonnées virtuelles, deux noeuds voisins ne sont pas forcément séparés par une distance virtuelle faible. En référence à la figure 2, l'étape 22 est une étape d'identification des noeuds voisins du noeud courant. Le noeud courant V de coordonnées virtuelles (V1, V2) est le noeud en possession du message et qui doit le transmettre à un de ses voisins. On désigne par noeud suivant, le noeud voisin du noeud courant destinataire du message. On dit que deux noeuds sont voisins lorsqu'ils peuvent communiquer ensemble directement. L'identification des noeuds voisins du noeud courant V se fait à l'aide du protocole de routage utilisé dans le réseau de noeuds considéré, comme par exemple un protocole de routage géographique. Par construction, le protocole de routage sert à trouver une succession de noeuds à atteindre pour transmettre le message du noeud source au noeud puits, à partir de la position de ces noeuds, définie par leurs coordonnées. Pour cela, le protocole de routage comporte la création d'une table de voisinage comportant pour chaque noeud du réseau, la liste de ses voisins ainsi que leurs coordonnées. L'identification des noeuds voisins du noeud courant s'effectue donc directement à partir de la table de voisinage. En référence à la figure 2, l'étape 23 est une étape de récupération par le noeud courant des coordonnées virtuelles de ses noeuds voisins. Ces informations sont obtenues à partir la table de voisinage créée par le protocole de routage. Ainsi, en référence à la figure 1, à l'issue des étapes 22 et 23, le noeud courant V de coordonnées virtuelles (V1, V2) sait qu'il a trois voisins W, X, Y et que leurs coordonnées virtuelles respectives, obtenues à partir de la table de voisinage, sont (W1, W2), (X1, X2), (Y1, Y2). En référence à la figure 2, l'étape 24 est une étape de mise à jour des coordonnées virtuelles du noeud courant. Après avoir identifié ses noeuds voisins et récupéré leurs coordonnées virtuelles, le noeud courant met à jour ses coordonnées virtuelles. La mise à jour des coordonnées virtuelles du noeud courant à chaque 20 transmission d'un message au noeud suivant en fonction des coordonnées virtuelles des noeuds voisins du noeud courant. Pour cela, il leur affecte la valeur des coordonnées du barycentre de ses voisins. Les coordonnées du barycentre, pour chacune des deux dimensions de l'espace d'observation, correspondent à la moyenne des 25 coordonnées virtuelles des noeuds voisins pour chacune des deux dimensions respectives. Ainsi, en référence à la figure 1, le noeud courant V met à jour ses coordonnées virtuelles (V1, V2) en leur affectant la moyenne des coordonnées virtuelles respectives de ses trois voisins W, X, Y, soit : 30 V1 = (W1+X1+Y1)/3 V2 = (W2+X2+Y2)/3 Lorsqu'à l'issue de l'étape 24, le noeud courant a mis à jour ses coordonnées virtuelles, il envoie le message à destination du noeud suivant en utilisant le protocole de routage. Même si le message est à destination du noeud suivant, tous les autres voisins du noeud courant reçoivent également ce message. Outre les données à transmettre au noeud puits, le message comporte également, dans une partie d'un en-tête de ce message, les coordonnées virtuelles actualisées du noeud courant. Les noeuds courants, ainsi que certains de leurs noeuds voisins tel que décrit ci-après, mettent à jour leurs coordonnées virtuelles à chaque saut sur le chemin multi-sauts séparant le noeud source du noeud puits, et ce, pour tous les messages envoyés tout au long de la vie du réseau de noeuds considéré. L'étape 25 représentée sur la figure 2 est une étape facultative d'actualisation des coordonnées virtuelles d'un ou plusieurs noeuds voisins du noeud courant. A la réception du message envoyé par le noeud courant à l'issue de l'étape 24, les noeuds voisins du noeud courant vérifient à quelle distance virtuelle ils se trouvent du noeud courant. Si la distance virtuelle entre le noeud courant et un noeud voisin est inférieure à un seuil MinVirtuel, alors ce noeud voisin fait varier ses coordonnées virtuelles en se déplaçant virtuellement sur la demi-droite reliant le noeud courant à ce noeud voisin de telle sorte que la distance entre ces deux noeuds devienne égale au seuil MinVirtuel. La valeur de MinVirtuel est positive et définie arbitrairement. Tous les noeuds du réseau connaissent et utilisent la même valeur de MinVirtuel. Par exemple, en référence à la figure 1, le noeud X qui est à une distance d(X,V) du noeud courant V inférieure à MinVirtuel, va modifier ses coordonnées virtuelles. Cette modification correspond à un déplacement virtuel sur l'axe V,X, représenté par une flèche sur la figure 1. A l'issue de ce déplacement, la distance d(X,V) entre le noeud X et le noeud courant V est alors égale à MinVirtuel. Cette étape contribue à une détermination plus rapide de chemins multisauts ayant un nombre de sauts très faible. La figure 3 illustre un dispositif 30 apte à mettre en oeuvre le procédé de détermination des coordonnées d'un noeud dans un réseau de noeud selon l'invention. Ce dispositif comprend un module 31 d'initialisation de coordonnées 10 virtuelles pour chacun des noeuds du réseau. En référence à l'étape 21, le module 31 d'initialisation, choisit aléatoirement chacune des coordonnées virtuelles des noeuds du réseau. Le dispositif 30 comprend un module 32 d'identification des noeuds voisins d'un noeud courant. 15 Le module 32 identifie les noeuds voisins d'un noeud courant à partir de la table de voisinage créée par le protocole de routage tel que décrit à l'étape 22. Le dispositif 30 comprend un module 33 de récupération par le noeud courant des coordonnées virtuelles des noeuds voisins. 20 En référence à l'étape 23, les coordonnées virtuelles des noeuds voisins du noeud courant sont obtenues à partir de la table de voisinage créée par le protocole de routage. Le dispositif 30 comporte également un module 34 de mise à jour des coordonnées virtuelles du noeud courant. 25 Tel que décrit à l'étape 24, le module 34 met à jour les coordonnées virtuelles du noeud courant en leur affectant la moyenne des coordonnées virtuelles respectives des noeuds voisins. Le dispositif 30 comporte en outre un module 35 d'actualisation des coordonnées virtuelles d'un ou plusieurs noeuds voisins du noeud courant tel 30 que décrit précédemment à l'étape 25. Les modules 31 à 35 peuvent être des modules logiciels formant un programme d'ordinateur. L'invention concerne donc également un programme d'ordinateur pour un dispositif de détermination des coordonnées d'un noeud dans un réseau de noeuds comprenant des instructions logicielles pour faire exécuter par le dispositif le procédé précédemment décrit. Le module logiciel peut être stocké dans ou transmis par un support de données. Celui-ci peut être un support matériel de stockage, par exemple un CD-ROM, une disquette magnétique ou un disque dur, ou bien un support transmissible tel qu'un signal électrique, optique ou radio. Le dispositif 30 de détermination des coordonnées d'un noeud dans un réseau de noeuds peut être intégré dans un objet communicant apte à capter des informations sur son environnement à les transmettre, par exemple par radiocommunication, à un autre objet communicant du réseau. Le procédé selon l'invention est utilisable dans des applications de domotique, comme par exemple pour de la détection d'intrusion ou d'incendie. Les noeuds du réseau correspondent alors à des capteurs placés en différents endroits d'une habitation. Une autre application du procédé selon l'invention est la détection de feux de forêt. Des capteurs de fumée ou de chaleur sont dispersés dans une forêt, par exemple à partir d'un hélicoptère. Les données recueillies par ces capteurs sont transmises à un centre de supervision d'incendie. Cet exemple illustre avantageusement l'intérêt de l'invention puisque dans ce cas les coordonnées des capteurs, ainsi dispersés, ne sont pas connues. De plus, le nombre de ces capteurs peut varier soit parce que certains sont détruits soit parce que de nouveaux capteurs sont ajoutés.30 La figure 4 représente les résultats d'un test de mise en oeuvre du procédé selon l'invention. Dans cet exemple, la valeur de DimMax, correspondant à la valeur maximale des coordonnées N, et N2 d'un noeud N, a été fixée arbitrairement égale à 1000. En référence à la figure 4, le graphe G représente l'ensemble des noeuds du réseau. Les points correspondent aux noeuds positionnés à leurs coordonnées réelles. Les noeuds voisins sont reliés deux à deux par un segment de droite représenté par un trait plein sur le graphe G. Les deux séries de graphes G11 à G14 et G21 à G24 de la figure 4 illustrent l'évolution au cours du temps des coordonnées virtuelles, pour deux valeurs de MinVirtuel différentes. Pour la série de graphes G11 à G14, MinVirtuel a été choisi arbitrairement égal à 50. Pour la série de graphes G21 à G24, MinVirtuel a été choisi arbitrairement égal à 100. Initialement (graphes G11 et G21), les coordonnées virtuelles des noeuds du réseau sont initialisées aléatoirement. Les graphes G12 à G14 et G22 à G24 illustrent l'évolution de ces coordonnées virtuelles au fur et à mesure que les messages traversent le réseau de noeuds. Les tests et les mesures effectués permettent de mettre en évidence un phénomène d'alignement des noeuds. Les noeuds les plus éloignés du puits en coordonnées réelles le sont également en coordonnées virtuelles. Ce phénomène d'alignement représente un avantage important de l'invention. En effet, c'est ce phénomène qui permet au protocole de routage, par exemple un protocole de routage géographique, utilisant les coordonnées virtuelles des noeuds selon l'invention, de déterminer des chemins ayant un nombre de sauts très faible. REVENDICATIONS 1. Procédé de détermination des coordonnées d'un noeud courant dans un réseau de noeuds dans lequel un message est transmis du noeud courant à un noeud suivant, caractérisé en ce qu'il comporte des étapes de : -initialisation aléatoire de coordonnées virtuelles pour chacun des noeuds du réseau, - mise à jour des coordonnées virtuelles du noeud courant à chaque transmission d'un message au noeud suivant. 2. Procédé selon la revendication 1, caractérisé en ce qu'il comporte en outre des étapes de : - identification de noeuds voisins du noeud courant, - récupération des coordonnées virtuelles des noeuds voisins par le noeud courant. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que la mise à jour des coordonnées virtuelles du noeud courant s'effectue en leur affectant la moyenne des coordonnées virtuelles respectives des noeuds voisins. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce qu'il comporte une étape facultative de mise à jour des coordonnées virtuelles d'au moins un noeud voisin du noeud courant lorsque la distance virtuelle entre le au moins noeud voisin et le noeud courant est inférieure à un seuil donné. 5. Dispositif de détermination des coordonnées d'un noeud courant dans un réseau de noeuds dans lequel un message est transmis du noeud courant à un noeud suivant, caractérisé en ce qu'il comporte :- un module d'initialisation aléatoire de coordonnées virtuelles pour chacun des noeuds du réseau, - un module de mise à jour des coordonnées virtuelles du noeud courant à chaque transmission d'un message au noeud suivant. 6. Objet communicant apte à recevoir un dispositif selon la revendication 5. 7. Produit programme d'ordinateur comportant des instructions de 10 programme pour l'exécution du procédé de détermination des coordonnées d'un noeud courant dans un réseau de noeuds, dans lequel un message est transmis du noeud courant à un noeud suivant, selon l'une quelconque des revendications 1 à 4.5