Brevet FR2770712A1 — publié le 19990430

La présente invention concerne la diffusion de communications entre les stations d'un réseau de type distribué. Le réseau est par exemple un réseau local sans fil dont les stations communiquent entre elles en se partageant un canal radio. Un réseau de type distribué ne possède pas de station de base pour gérer les communications entre les stations. Selon un mécanisme de diffusion connu utilisé dans un protocole d'accès MAC contrôle d'accès au support (Medium Access Control) pour un réseau local sans fil de type distribué, chaque station du réseau rediffuse les messages qu'elle reçoit. Les messages ont par exemple une durée de vie limitée, qui peut être exprimée par un nombre maximal de rediffusions. Tant qu'un message n'a pas atteint son nombre maximal de rediffusion, il est rediffusé. La rediffusion des messages fait qu'une station peut recevoir des messages dupliqués, c'est-à-dire contenant les mêmes données utiles, depuis plusieurs stations différentes. La station considérée va rediffuser chacun de ces messages. En d'autres termes, la station considérée reçoit plusieurs fois le "même" message, et le rediffuse à chaque fois. Les données dupliquées sont ensuite triées et éliminées par des couches supérieures à la couche MAC. Ce système génère un trafic important, et donc une occupation du canal radio, au détriment de nouveaux messages de données. En outre, cela augmente le risque de collision de messages, et par conséquent le risque de perte de message. Pour améliorer la diffusion de message, il est possible de sélectionner un sous-ensemble de stations réparties dans le réseau qui seules seront autorisées à rediffuser les messages reçus en diffusion. Le nombre de rediffusions est ainsi limité. Cependant, une station rediffuse toujours au moins une fois un message. En outre, il est possible qu'elle rediffuse plusieurs fois le "même" message. La présente invention vise à remédier aux inconvénients de la technique antérieure, en fournissant un procédé de diffusion de messages qui contrôle les messages au niveau de la couche MAC, avant de les rediffuser. A cette fin, I'invention propose un procédé de diffusion de message entre des stations d'un réseau, chaque station ayant en mémoire une première table respective contenant des identificateurs de stations destinataires finales de message associés à des identificateurs de stations destinataires intermédiaires de message, caractérisé en ce qu'une station considérée quelconque effectue les opérations suivantes lorsqu'elle reçoit un message: - mémorisation dans une seconde table de données concernant ledit message et comportant au moins un identificateur de message et un identificateur de station émettrice dudit message, - comparaison de l'identificateur de message avec les identificateurs de message précédemment mémorisés dans la seconde table, - recherche dans la première table de la station considérée d'un groupe de stations qui sont à la fois station destinataire finale et station destinataire intermédiaire, et - diffusion d'un second message si et seulement si l'identificateur dudit message est différent des identificateurs précédemment mémorisés dans la seconde table et si ledit groupe comporte au moins une station différente de la station ayant émis ledit message. Le procédé selon l'invention résout le problème énoncé ci-dessus, en exploitant le trafic de données au niveau MAC (Medium Access Control). L'invention utilise d'une part les messages de données acheminés dans le réseau et d'autre part la table de routage des stations, pour déterminer si un message doit être rediffusé. Les rediffusions de message sont moins nombreuses, ce qui diminue le risque de collision et donc de perte de message. Les données diffusées peuvent être des données utilisateur ou des informations de routage, par exemple. Selon une caractéristique préférée, le second message a un identificateur de message qui est celui dudit message et une adresse de station émettrice intermédiaire qui est celle de la station considérée. La diffusion du second message est équivalente à la rediffusion du message en cours de traitement. Selon une autre caractéristique préférée, I'identificateur de message comporte l'adresse de la station émettrice initiale du premier d'un ensemble de messages précédents ayant le même identificateur de message que ledit message. Les messages sont ainsi identifiés de manière simple et fiable. Corrélativement, I'invention concerne une station de communication d'un réseau, ayant en mémoire une première table respective contenant des identificateurs de stations destinataires finales de message associés à des identificateurs de stations destinataires intermédiaires de message, caractérisée en ce qu'elle comporte, ou en ce qu'elle est adaptée à coopérer avec: - des moyens de mémorisation dans une seconde table de données concernant un message qu'elle reçoit et comportant au moins un identificateur de message et un identificateur de station émettrice dudit message, - des moyens de comparaison de l'identificateur de message avec les identificateurs de message précédemment mémorisés dans la seconde table, - des moyens de recherche dans la première table de la station considérée d'un groupe de stations qui sont à la fois station destinataire finale et station destinataire intermédiaire, et - des moyens de diffusion d'un second message si et seulement si l'identificateur dudit message est différent des identificateurs précédemment mémorisés dans la seconde table et si ledit groupe comporte au moins une station différente de la station ayant émis ledit message. La station de communication selon l'invention présente les mêmes avantages que ceux du procédé précédemment exposés. Les caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture d'un mode préféré de réalisation illustré par les dessins ci-joints, dans lesquels - la figure 1 représente un réseau distribué de stations, - la figure 2 représente une station mobile du réseau de la figure 1, - la figure 3 représente une table de routage de l'une des stations mobiles du réseau de la figure 1, - la figure 4 représente un message de données transmis d'une station mobile à une autre, - la figure 5 représente un extrait d'une table de messages entendus par l'une des stations mobiles du réseau, selon l'invention, - la figure 6 est un algorithme de traitement de message de données, selon l'invention. Selon le mode de réalisation choisi et représenté à la figure 1, un réseau local sans fil comporte des stations, dont cinq, référencée SMa à SMe sont représentées. Les stations sont ici mobiles. La connectivité des stations mobiles évolue en permanence, en fonction des déplacements des stations et des modifications de leur environnement. De plus, il est possible que le nombre de stations mobiles effectivement connectées au réseau évolue également. Les stations communiquent entre elles par transmission radio ou en variante par transmission infrarouge. Chaque station, ou noeud du réseau, est repérée par une adresse unique. Le réseau est de type distribué, c'est-à-dire qu'il ne comporte pas de station de base pour gérer les communications entre stations. On s'intéresse ici aux communications entre stations qui sont effectuées selon un mode de diffusion, au niveau MAC (Medium Access Control). Un mode de réalisation de l'une quelconque des stations, par exemple la station SMC, est représenté à la figure 2. Les moyens de mise en oeuvre de l'invention sont intégrés dans un ordinateur, qui comporte des interfaces utilisateurs classiques, non décrits ici. En variante, les moyens de mise en oeuvre de l'invention ne sont pas intégrés à une station mobile proprement dite, mais ces moyens et la station mobile sont adaptés à communiquer et coopérer ensemble. La station SMC intègre une unité centrale de traitement sous la forme d'un processeur 10 relié par un bus d'une part à une mémoire morte (ROM) 30 dans laquelle sont enregistrés les programmes exécutés par le processeur et d'autre part à une mémoire vive (RAM) 20 comportant une zone de travail, des registres de données et une zone réservée au stockage des messages reçus ou en attente d'émission. La mémoire vive 20 stocke entre autres, un journal, exposé dans la suite, correspondant à la table des derniers messages reçus et entendus par la station mobile SMC. La station mobile SMC comporte un module de communication radiofréquences 50, connu en soi, permettant à la station mobile SMC d'émettre et de recevoir des données vers et depuis d'autres stations mobiles. L'interface entre le module de communication radiofréquences 50 et le processeur 10 se fait par: - le port de contrôle 15, dont la valeur binaire représente l'état d'occupation du support de transmission sans fil à un instant donné, - le port de lecture 16, dans lequel le processeur 10 lit les données reçues par la station mobile SMC, - le port d'écriture 17, où la station mobile SMC peut aller écrire les données qu'elle souhaite émettre via le support de transmission radiofréquences. Une horloge 40, reliée au processeur 10, permet à ce dernier de réaliser des opérations à intervalles réguliers, telles que par exemple, les opérations de lecture I écriture dans les ports 15, 16, 17. Chaque station mobile a en mémoire une table de routage représentée à la figure 3. La table de routage TRC de la station SMC comporte une liste de chacune des stations accessibles (station destinataire finale) à partir de la station considérée, la prochaine station (station destinataire intermédiaire) à atteindre pour atteindre chacune des stations accessibles et le coût pour atteindre chacune des stations accessibles. Le coût est par exemple le nombre de sauts nécessaires, c'est-à-dire le nombre de segments à parcourir, pour atteindre chacune des stations accessibles. Selon des variantes de réalisation, le coût peut tenir compte par exemple du rapport signal à bruit, du niveau de réception des messages, des délais d'acheminement, ou du nombre de stations voisines de la station considérée, ou encore être une combinaison de ces paramètres. Ainsi, par exemple, il est possible d'atteindre la station SMe depuis la station SMC, la prochaine station étant SMd, et le coût, c'est-à-dire ici le nombre de sauts, étant de deux. La table de routage d'une station est valable à un instant donné, et est susceptible d'évoluer dans le temps. D'autre part, la table de routage d'une station peut comporter d'autres informations, telles que numéro de séquence, drapeau, par exemple, qui ne sont pas utiles pour la présente invention. Comme représenté à la figure 4, les données sont échangées entre stations sous la forme de message 60 comportant au moins les champs suivants: - le champ 61 contenant l'adresse SEI de la station émettrice initiale du message, - le champ 62 contenant l'adresse SDF de la station destinataire finale du message (diffusion), - le champ 63 contenant l'adresse SET de la station émettrice intermédiaire, - le champ 64 contenant l'adresse SDT de la station destinataire intermédiaire (diffusion), - le champ 65 contenant un identificateur ID de message créé par la station émettrice initiale, - le champ 66 contenant le coût CT du message, mis à jour par chaque station intermédiaire et par la station destinataire finale, - le champ 67 de données proprement dites, - le champ 68 contenant le type IT du message, par exemple message de données. Dans le cas général, les stations émettrice initiale et destinataire finale sont les extrémités du chemin à parcourir par le message. Les stations émettrice intermédiaire et destinataire intermédiaire sont les extrémités d'un segment du chemin. Dans le cas particulier de la diffusion de message que l'on considère ici, toutes les stations du réseau, sauf celle ayant émis le message, sont destinataires du message. Pour indiquer que le message est transmis en mode diffusion, les adresses de station destinataire intermédiaire et finale sont à une valeur spécifique DIF. Le coût CT peut être utilisé pour limiter le nombre de saut, et par conséquent la durée de vie des messages. Chacune des stations mémorise des données sur chacun des messages qu'elle reçoit. Ces données sont mémorisées dans une table spécifique, ou journal, dont la taille prédéterminée, correspondant à une fenêtre temporelle, est choisie en fonction d'un délai d'acheminement maximal de message dans le réseau. Comme représenté à la figure 5, pour chaque message reçu, la station SMd mémorise les données suivantes: - le champ 71 contenant l'adresse SEI de la station émettrice initiale du message, - le champ 72 contenant l'adresse SDF de la station destinataire finale du message, - le champ 73 contenant l'adresse SET de la station émettrice intermédiaire, - le champ 74 contenant l'adresse SDT de la station destinataire intermédiaire, - le champ 75 contenant l'identificateur ID de message créé par la station émettrice initiale, - le champ 76 contenant le coût CT du message, mis à jour par chaque station qui reçoit le message, - le champ 77 contenant la date DT d'audition du message. Les valeurs des six premiers champs sont déduites du message reçu et la dernière est mise à jour par la station SMd. La date d'audition DT n'est pas utilisée par la présente invention et peut servir notamment à contrôler les délais d'acheminement ou à limiter la durée de vie des messages. La figure 6 représente un algorithme mis en oeuvre dans chacune des stations mobiles du réseau, lorsqu'un message est reçu, pour traiter ce message. L'algorithme comporte des étapes E600 à E607 qui sont mémorisées en mémoire morte 30. L'étape E600 est la réception par la station mobile d'un message qui a été émis en diffusion par une autre station mobile. Pour cela, le processeur 10 lit régulièrement le port 16 pour vérifier si le module radio 50 a reçu des données. Lorsqu'un message de données a été reçu, le processeur 10 lit le champ 64 du message pour chercher s'il contient l'adresse DIF de diffusion, et le type de message dans le champ 68. Après la réception d'un message diffusé, L'étape E600 est suivie de l'étape E601, qui est un test pour vérifier si l'adresse SEI de la station émettrice initiale contenue dans le champ 61 du message en cours de traitement est égale à l'adresse de la station considérée. Si la réponse est positive, cela signifie que le message en cours de traitement a été initialement émis par la station considérée. Cette dernière ne mémorise pas ce message dans son journal, et n'effectue aucun autre traitement sur le message. L'exécution de l'algorithme est terminée. Si la réponse à l'étape E601 est négative, cela signifie que le message en cours de traitement a été initialement émis par une autre station mobile. L'étape E601 est alors suivie de l'étape E602 à laquelle le journal de la station est mis à jour. La mise à jour consiste à introduire les données relatives au message en cours de traitement dans le journal de la station, comme représenté à la figure 5. L'étape E602 comporte la mise à jour du coût. Dans le cas où le coût est le nombre de sauts, ou de segments parcourus, le coût mémorisé est égal au coût lu dans le champ 66 du message, incrémenté de une unité. L'étape E602 est suivie de l'étape E603 qui est un test pour vérifier si le message correspond à un message déjà mémorisé dans le journal de la station. Le test consiste à comparer le couple formé de l'identificateur ID du message et de l'adresse SEI de la station émettrice initiale du message avec les couples formés d'identificateur de message et d'adresse de station émettrice initiale de message qui sont mémorisés dans le journal de la station considérée. Si la réponse est positive, cela signifie qu'il y a correspondance entre le message en cours de traitement et un message précédemment reçu et mémorisé. Le message n'est pas diffusé par la station considérée, car le message correspondant a déjà été diffusé, ce qui évite des diffusions multiples de messages contenant les mêmes données. L'exécution de l'algorithme est terminée. Si la réponse à l'étape E603 est négative, cette étape est suivie de l'étape E604, qui est la transmission du message vers la couche applicative de la station pour traiter les informations reçues, c'est-à-dire les informations qui étaient contenues dans le champ de données 67 du message. L'étape suivante E605 est une consultation de la table de routage pour déterminer quelles sont les stations voisines de la station considérée. Une station voisine de la station considérée est une station capable de communiquer de façon bidirectionnelle avec la station considérée. En d'autres termes, les stations voisines peuvent être atteintes en un saut. Les stations voisines sont les stations qui sont à la fois stations destinataires finales et stations destinataires intermédiaires dans la table de routage de la station considérée. L'étape E605 est suivie de l'étape E606 qui est un test pour déterminer si la station considérée a d'autres stations voisines que la station émettrice intermédiaire du message en cours de traitement. Le test consiste à comparer l'adresse des stations voisines avec l'adresse SET contenue dans le champ 63 du message en cours de traitement. Si la réponse est négative, il est inutile que la station considérée diffuse un message contenant les données du message en cours de traitement, puisque seule la station émettrice du message en cours de traitement recevrait ce nouveau message. l'exécution de l'algorithme est terminée. Si la réponse est positive à l'étape E606, cette dernière est suivie de l'étape E607 à laquelle un message est formé et diffusé. Cette étape est la "rediffusion" du message en cours de traitement, c'est-à-dire que le nouveau message correspond au message en cours de traitement et est formé de la manière suivante. Le champ de données 67 de ce message contient les informations présentes dans le champ de données du message en cours de traitement. L'adresse SEI de la station émettrice initiale, L'adresse SDF de station destinataire finale (ici à la valeur DIF), I'identificateur ID de message sont recopiés dans les champs correspondants du message en cours de traitement. Le coût CT de ce nouveau message est mis à jour par la station considérée. L'adresse SET de la station émettrice intermédiaire de ce nouveau message est celle de la station considérée. En référence à nouveau à la figure 1, on suppose que la station SM a émet un message en diffusion. Ce message est entendu par la station SMb, qui met à jour son journal en mémorisant les données concernant ce message. Après avoir vérifié que ce message ne correspond pas à un autre message déjà mémorisé dans le journal de la station SMb, et que la station SMb a d'autres stations voisines que la station SMa, en l'occurrence les stations SMC et SMd, la station SMb émet un second message en diffusion, ce nouveau message ayant le même identificateur de message et la même adresse de station émettrice initiale que le premier message. Ce message est entendu par les stations SMa, SMC et SMd. La station SMa constate qu'elle est station émettrice initiale de ce second message. Elle n'effectue aucun traitement supplémentaire sur ce message. Les stations SMC et SMd mémorisent les données concernant le second message dans leur journal respectif. La station SMC vérifie que le second message ne correspond pas à un autre message déjà mémorisé dans le journal et qu'elle a d'autres stations voisines que la station SMb, ici la station SMd. La station SMC forme un troisième message et l'émet en diffusion. Ce troisième message est entendu par les stations SMb et SMd, qui mémorisent les données concernant le troisième message dans leur journal respectif et constatent que le troisième message correspond à un message déjà mémorisé dans leur journal respectif. Elles ne rediffusent pas de message en conséquence. Concernant de nouveau le second message, la station SMd vérifie que le second message ne correspond pas à un autre message déjà mémorisé dans le journal et qu'elle a d'autres stations voisines que la station SMb, ici les stations SMC et SMe. La station SMd forme un quatrième message et l'émet en diffusion. Ce quatrième message est entendu par les stations SMC et SMe qui mémorisent les données concernant le quatrième message dans leur journal respectif. La station SMC constate qu'il correspond à un message déjà mémorisé dans son journal, et ne rediffuse pas de message en conséquence. La station SMe constate en consultant sa table de routage qu'elle a pour seule station voisine la station SMd, qui est la station émettrice intermédiaire du quatrième message. Elle ne rediffuse pas de message en conséquence. Le message a ainsi été diffusé à toutes les stations du réseau, avec un nombre limité de rediffusion. Bien entendu, la présente invention n'est nullement limitée aux modes de réalisation décrits et représentés, mais englobe, bien au contraire, toute variante à la portée de l'homme du métier. REVENDICATIONS 1. Procédé de diffusion de message entre des stations d'un réseau, chaque station ayant en mémoire une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisé en ce qu'une station considérée quelconque effectue les opérations suivantes lorsqu'elle reçoit un message: - mémorisation (E602) dans une seconde table de données concernant ledit message et comportant au moins un identificateur (ID, SEI) de message et un identificateur (SET) de station émettrice dudit message, - comparaison (E603) de l'identificateur (ID, SEI) de message avec les identificateurs de message précédemment mémorisés dans la seconde table, - recherche (E605) dans la première table de la station considérée d'un groupe de stations qui sont à la fois station destinataire finale et station destinataire intermédiaire, et - diffusion (E607) d'un second message si et seulement si (E603) I'identificateur dudit message est différent des identificateurs précédemment mémorisés dans la seconde table et si (E606) ledit groupe comporte au moins une station différente de la station ayant émis ledit message. 2. Procédé selon la revendication 1, caractérisé en ce que le second message a un identificateur (ID, SEI) de message qui est celui dudit message et une adresse (SET) de station émettrice intermédiaire qui est celle de la station considérée. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que l'identificateur de message comporte l'adresse (SEI) de la station émettrice initiale du premier d'un ensemble de messages précédents ayant le même identificateur de message que ledit message. 4. Station de communication d'un réseau, ayant en mémoire (20) une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisée en ce qu'elle comporte: - des moyens de mémorisation (20) dans une seconde table de données concernant un message qu'elle reçoit et comportant au moins un identificateur (ID, SEI) de message et un identificateur (SET) de station émettrice dudit message, - des moyens (10) de comparaison de l'identificateur (ID, SEI) de message avec les identificateurs de message précédemment mémorisés dans la seconde table, - des moyens (10) de recherche dans la première table de la station considérée d'un groupe de stations qui sont à la fois station destinataire finale et station destinataire intermédiaire, et - des moyens (10, 50) de diffusion d'un second message si et seulement si l'identificateur dudit message est différent des identificateurs précédemment mémorisés dans la seconde table et si ledit groupe comporte au moins une station différente de la station ayant émis ledit message. 5. Station de communication d'un réseau, ayant en mémoire une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisée en ce qu'elle est adaptée à coopérer avec: - des moyens (10) de mémorisation dans une seconde table de données concernant un message qu'elle reçoit et comportant au moins un identificateur (ID, SEI) de message et un identificateur (SET) de station émettrice dudit message, - des moyens (10) de comparaison de l'identificateur (ID, SEI) de message avec les identificateurs de message précédemment mémorisés dans la seconde table, - des moyens (10) de recherche dans la première table de la station considérée d'un groupe de stations qui sont à la fois station destinataire finale et station destinataire intermédiaire, et - des moyens (10, 50) de diffusion d'un second message si et seulement si l'identificateur dudit message est différent des identificateurs précédemment mémorisés dans la seconde table et si ledit groupe comporte au moins une station différente de la station ayant émis ledit message. 6. Station selon la revendication 4 ou 5, caractérisée en ce qu'elle est adaptée à former le second message de sorte qu'il ait un identificateur (ID, SEI) de message qui est celui dudit message et une adresse (SET) de station émettrice intermédiaire qui est celle de la station considérée.