FR2923971A1 - Determination des coordonnees d'un noeud dans un reseau de noeuds. - Google Patents
Determination des coordonnees d'un noeud dans un reseau de noeuds. Download PDFInfo
- Publication number
- FR2923971A1 FR2923971A1 FR0759160A FR0759160A FR2923971A1 FR 2923971 A1 FR2923971 A1 FR 2923971A1 FR 0759160 A FR0759160 A FR 0759160A FR 0759160 A FR0759160 A FR 0759160A FR 2923971 A1 FR2923971 A1 FR 2923971A1
- Authority
- FR
- France
- Prior art keywords
- node
- nodes
- coordinates
- network
- current node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 claims abstract description 34
- 230000005540 biological transmission Effects 0.000 claims description 6
- 238000004590 computer program Methods 0.000 claims description 4
- 238000011084 recovery Methods 0.000 claims description 4
- 238000001514 detection method Methods 0.000 description 4
- 238000012360 testing method Methods 0.000 description 3
- 235000008694 Humulus lupulus Nutrition 0.000 description 2
- 238000004891 communication Methods 0.000 description 2
- 238000010276 construction Methods 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000008034 disappearance Effects 0.000 description 1
- 238000006073 displacement reaction Methods 0.000 description 1
- 230000005484 gravity Effects 0.000 description 1
- 238000005259 measurement Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 239000000779 smoke Substances 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
- H04W40/04—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources
- H04W40/10—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources based on available power or energy
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
- H04L45/122—Shortest path evaluation by minimising distances, e.g. by selecting a route with minimum of number of hops
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W64/00—Locating users or terminals or network equipment for network management purposes, e.g. mobility management
- H04W64/003—Locating users or terminals or network equipment for network management purposes, e.g. mobility management locating network equipment
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
- H04W40/20—Communication route or path selection, e.g. power-based or shortest path routing based on geographic position or location
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
L'invention concerne 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, comportant 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.
Description
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.
Claims (7)
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
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0759160A FR2923971A1 (fr) | 2007-11-19 | 2007-11-19 | Determination des coordonnees d'un noeud dans un reseau de noeuds. |
| PCT/FR2008/052063 WO2009071783A1 (fr) | 2007-11-19 | 2008-11-17 | Determination des coordonnees d'un noeud dans un reseau de noeuds |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0759160A FR2923971A1 (fr) | 2007-11-19 | 2007-11-19 | Determination des coordonnees d'un noeud dans un reseau de noeuds. |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| FR2923971A1 true FR2923971A1 (fr) | 2009-05-22 |
Family
ID=39832674
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| FR0759160A Pending FR2923971A1 (fr) | 2007-11-19 | 2007-11-19 | Determination des coordonnees d'un noeud dans un reseau de noeuds. |
Country Status (2)
| Country | Link |
|---|---|
| FR (1) | FR2923971A1 (fr) |
| WO (1) | WO2009071783A1 (fr) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113640845A (zh) * | 2021-08-09 | 2021-11-12 | 上海西虹桥导航技术有限公司 | 位置数据延迟改正优化的方法、装置、设备及存储介质 |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111291138B (zh) * | 2020-02-21 | 2023-07-18 | 支付宝(杭州)信息技术有限公司 | 更新关系网络的方法及装置 |
-
2007
- 2007-11-19 FR FR0759160A patent/FR2923971A1/fr active Pending
-
2008
- 2008-11-17 WO PCT/FR2008/052063 patent/WO2009071783A1/fr not_active Ceased
Non-Patent Citations (6)
| Title |
|---|
| FONSECA R ET AL: "Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets", PROCEEDINGS OF THE SYMPOSIUM ON NETWORKED SYSTEMS DESIGN ANDIMPLEMENTATION, USENIX ASSOCIATION, BERKELEY, CA, US, 2 May 2005 (2005-05-02), pages 329 - 342, XP002408361 * |
| MOSCIBRODA T ET AL: "VIRTUAL COORDINATES FOR AD HOC AND SENSOR NETWORKS", DIALM-POMC'04. PROCEEDINGS OF THE 2004 JOINT WORKSHOP ON FOUNDATIONS OF MOBILE COMPUTING. PHILADELPHIA, PA, OCT. 1, 2004; [PROCEEDINGS OF THE WORKSHOP ON FOUNDATIONS OF MOBILE COMPUTING], NEW YORK, NY : ACM, US, 1 October 2004 (2004-10-01), pages 8 - 16, XP001235046, ISBN: 978-1-58113-921-1 * |
| RAO A ET AL: "GEOGRAPHIC ROUTING WITHOUT LOCATION INFORMATION", PROCEEDINGS OF THE 9TH. ANNUAL INTERNATIONAL CONFERENCE ON MOBILE COMPUTING AND NETWORKING. MOBICOM 2003. SAN DIEGO, CA, SEPT. 14 - 19, 2003; [ANNUAL INTERNATIONAL CONFERENCE ON MOBILE COMPUTING AND NETWORKING], NEW YORK, NY : ACM, US, vol. CONF. 9, 14 September 2003 (2003-09-14), pages 96 - 108, XP001186711, ISBN: 978-1-58113-753-8 * |
| ROSSI M ET AL: "Cost efficient routing strategies over virtual coordinates for wireless sensor networks", GLOBAL TELECOMMUNICATIONS CONFERENCE, 2005. GLOBECOM '05. IEEE ST. LOIUS, MO, USA 28 NOV.-2 DEC. 2005, PISCATAWAY, NJ, USA,IEEE, vol. 5, 28 November 2005 (2005-11-28), pages 2975 - 2980, XP010879366, ISBN: 978-0-7803-9414-8 * |
| THOMAS WATTEYNE ET AL: "On using Virtual Coordinates for Routing in the Context of Wireless Sensor Networks", IEEE INTERNATIONAL SYMPOSIUM ON PERSONAL, INDOOR AND MOBILE RADIO COMMUNICATIONS. PIMRC, IEEE; PI, XX, 1 September 2007 (2007-09-01), pages 1 - 5, XP031168614, ISBN: 978-1-4244-1143-6 * |
| YAO ZHAO ET AL: "Hop ID: A Virtual Coordinate based Routing for Sparse Mobile Ad Hoc Networks", IEEE TRANSACTIONS ON MOBILE COMPUTING, IEEE SERVICE CENTER, LOS ALAMITOS, CA, US, vol. 6, no. 9, 1 September 2007 (2007-09-01), pages 1075 - 1089, XP011189125, ISSN: 1536-1233 * |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113640845A (zh) * | 2021-08-09 | 2021-11-12 | 上海西虹桥导航技术有限公司 | 位置数据延迟改正优化的方法、装置、设备及存储介质 |
| CN113640845B (zh) * | 2021-08-09 | 2024-06-07 | 上海西虹桥导航技术有限公司 | 位置数据延迟改正优化的方法、装置、设备及存储介质 |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2009071783A1 (fr) | 2009-06-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP3957045B1 (fr) | Procédé et dispositif de traitement d'un message d'alerte notifiant une anomalie détectée dans un trafic émis via un réseau | |
| EP3167572B1 (fr) | Passerelle résidentielle relais entre un dispositif terminal et un serveur | |
| EP3804408A1 (fr) | Procédé de sélection d'une route dans un réseau ad hoc | |
| FR2878674A1 (fr) | Procede et systeme d'adaptation dynamique de metrique de qualite de service dans un reseau ad hoc | |
| FR3046324A1 (fr) | Procede pour determiner une reference temporelle et/ou au moins une reference spatiale dans un systeme de communication | |
| EP2163071A2 (fr) | Procédé de détermination automatique d'un groupe de pairs situés dans le voisinage d'un autre pair au sein d'un réseau de communication, et serveur, dispositif d'analyse et équipement de communication associés | |
| FR2923971A1 (fr) | Determination des coordonnees d'un noeud dans un reseau de noeuds. | |
| CA3103089A1 (fr) | Procede d'extinction d'un reseau de communication | |
| WO2013000996A1 (fr) | Procede pour l'extension de routeurs dans un reseau de communications et routeur mettant en oeuvre ce procede | |
| WO2012131280A1 (fr) | Communication de données dans un réseau de capteurs | |
| EP2591588B1 (fr) | Accès à un réseau de noeuds répartis sur une architecture de communication a l'aide d'un serveur de topologie avec sélection multicritères | |
| EP3675463B1 (fr) | Procédé d'identification d'un objet connecté dans une infrastructure réseau | |
| FR3073109A1 (fr) | Procede de communication | |
| WO2017215970A1 (fr) | Procede de dissemination de donnees dans un reseau maille | |
| EP1652346B1 (fr) | Procede de localisation d'objets mobiles communicants au sein d'un reseau de communications | |
| FR2939267A1 (fr) | Procede de gestion de routage de communications dans un reseau de communication sans-fil, produit programme d'ordinateur, moyen de stockage et dispositif de gestion correspondant | |
| Kim et al. | Dynamic anchors based void avoidance scheme for real-time application in wsns | |
| FR2938718A1 (fr) | Procede de communication et reseau mettant en oeuvre ce procede | |
| FR3091101A1 (fr) | Procédé de gestion d’un dispositif de communication de données et dispositif pour la mise en œuvre du procédé | |
| FR3139964A1 (fr) | Procédé de gestion d’un réseau de communication, réseau de communication et entité associés | |
| EP3331293B1 (fr) | Reseau informatique sans fil et procede pour localiser un noeud dans ledit reseau | |
| EP3046368B1 (fr) | Procede de collecte d'informations de routage dans un reseau ad-hoc et procede de selection de route a partir des informations collectees | |
| EP4544817A1 (fr) | Procédés de fourniture et de collecte, station de base, dispositif de collecte et d'analyse de données et système | |
| FR3105680A1 (fr) | Procédé et dispositif de routage de flux de données | |
| EP4264840A1 (fr) | Décodage collaboratif d'une trame corrompue détectée par plusieurs stations de base avec optimisation de la charge du réseau d'accès |