La présente invention vise un traitement de données pour la communication de données dans un réseau informatique. En particulier, la présente invention vise un traitement de données pour la communication de données dans un réseau de capteurs.

Les capteurs actuels, par leur diversité, sont capables de mesurer différentes grandeurs physiques ou chimiques, par exemple une position d'un objet à la surface de la terre, une température, un niveau d'eau, un niveau de lumière, une présence de certains corps chimiques, etc. Certains capteurs sont en outre capables de fournir des images.

De manière générale, on appelle capteur un dispositif capable de réaliser une mesure d'un paramètre de son environnement, et de transmettre des données de mesure correspondantes.

On appelle réseau de capteurs un réseau informatique comportant un ensemble de capteurs et un ensemble de voies de communication permettant aux capteurs de transmettre des données de mesure. Un réseau de capteurs peut en outre comporter d'autres dispositifs, par exemple un ou plusieurs dispositifs) de collecte, configuré(s) pour collecter des données de mesure fournies par les capteurs, et /ou un ou plusieurs dispositifs) de routage, configuré(s) pour permettre le routage des données de mesure transmises. Les voies de communication sont par exemple des liaisons radioélectriques ou des liaisons filaires.

Actuellement, les capteurs sont généralement uniquement configurés pour mesurer un paramètre de l'environnement dans lequel ils sont implantés et pour transmettre les données de mesure correspondantes vers un point de collecte où l'information sera traitée. Les communications vers ce point de collecte se font par exemple suivant des chemins de communication définissant une topologie virtuelle arborescente. La sécurité des communications peut alors être assurée par le fait que l'arbre virtuel n'est pas unique.

Cependant, cette solution n'est pas applicable dans le cas d'un réseau de capteurs comportant des capteurs en outre configurés pour agir sur leur environnement, seul ou en association avec d'autres dispositifs. En effet, dans ce cas, le problème n'est plus d'assurer la sécurité des communications vers un point collecte, mais d'assurer la sécurité des communications entre les différents capteurs du réseau de capteurs.

La présente invention vient améliorer la situation.

A cet effet, l'invention propose un procédé de traitement de données pour la communication de données dans un réseau. Le réseau comprend un ensemble de dispositifs formant nœuds dudit réseau et un ensemble de liaisons, chaque liaison reliant deux desdits dispositifs. Le procédé comprend des étapes :

- déterminer un ensemble de chemins de communication entre les dispositifs, chaque chemin de communication comprenant une ou plusieurs liaison(s) de l'ensemble de liaisons,

- configurer les dispositifs pour que chaque communication entre deux dispositifs utilise un chemin de communication de l'ensemble de chemins de communication.

Les communications entre les dispositifs nécessitent la détermination préalable des chemins suivant lesquels ces communications pourront être acheminées : cela revient à contraindre les dispositifs à utiliser un chemin de cet ensemble. Cet ensemble de chemins représente donc les chemins « autorisés » à un instant donné.

Cette détermination préalable permet en outre de déterminer un nombre maximum de chemins susceptibles d'être utilisés à un instant donné, ce qui permet de maximiser la bande passante totale utilisable dans le réseau.

Avantageusement, les chemins de communication de l'ensemble de chemins de communication sont disjoints, c'est-à-dire que deux chemins quelconques de cet ensemble ne possèdent aucune liaison en commun (mais peuvent comporter un ou plusieurs nœuds en commun). L'utilisation de chemins disjoints permet d'augmenter la sécurité des communications entre les dispositifs du réseau. En effet, l'utilisation d'un ensemble de chemins disjoints améliore la robustesse aux pannes, puisque, en cas de panne affectant une liaison, un seul chemin sera affecté. En outre, cela permet d'éviter les risques de collision, donc les risques de non-transmission de données ou d'erreurs de transmission.

L'étape de détermination de l'ensemble de chemins de communication peut être mise en œuvre dans un des dispositifs. L'étape de configuration peut alors comporter une opération de transmission par le dispositif, à destination d'au moins un autre dispositif du réseau, d'un message contenant des informations relatives à l'ensemble de chemins de communication.

L'étape de détermination de l'ensemble de chemins de communication peut comporter une opération de sélection de deux dispositifs parmi les dispositifs du réseau, et une opération de détermination d'un nouveau chemin de communication entre les deux dispositifs sélectionnés.

L'opération de détermination d'un nouveau chemin de communication entre les deux dispositifs sélectionnés peut comprendre la sélection d'une liaison de l'ensemble de liaisons, et la construction d'un nouveau chemin de communication en utilisant la liaison sélectionnée, un plus court chemin entre un des deux dispositifs sélectionnés et une première extrémité de la liaison, et un plus court chemin entre la deuxième extrémité de la liaison et l'autre des deux dispositifs sélectionnés. Les liaisons peuvent être des liaisons radioélec triques. En variante, les liaisons peuvent être des liaisons filaires.

L'invention propose également un programme informatique comportant des instructions pour la mise en œuvre du procédé décrit ci-dessus lorsque ce programme est exécuté par un processeur.

L'invention propose également un dispositif, conçu pour être utilisé dans un réseau comprenant un ensemble de dispositifs et un ensemble de liaisons, chaque liaison reliant deux desdits dispositifs, ledit dispositif étant configuré pour :

- déterminer un ensemble de chemins de communication à utiliser entre les dispositifs du réseau, chaque chemin de communication comprenant une ou plusieurs liaison(s) de l'ensemble de liaisons,

- configurer les dispositifs du réseau pour que chaque communication entre deux desdits dispositifs utilise un chemin de communication dudit ensemble de chemins de communication.

Le dispositif peut être un capteur configuré pour transmettre des données de mesure, correspondant à une mesure réalisée par le capteur, à au moins un autre capteur du réseau, le capteur étant en outre configuré pour que chaque communication entre ledit capteur et un autre capteur du réseau utilise au moins un chemin de communication de l'ensemble de chemins de communication.

L'invention propose également un réseau comprenant un ensemble de dispositifs et un ensemble de liaisons, chaque liaison reliant deux desdits dispositifs. Au moins un des dispositifs est configuré pour déterminer un ensemble de chemins de communication entre les dispositifs, chaque chemin de communication comprenant une ou plusieurs liaison(s) de l'ensemble de liaisons. Les dispositifs sont en outre configurés pour que chaque communication entre deux des dispositifs utilise un chemin de communication de l'ensemble de chemins de communication.

L'ensemble de dispositifs peut comprendre des capteurs et des dispositifs de routage.

Le dispositif réalisant la détermination peut être un capteur en outre configuré pour transmettre, à destination d'au moins un dispositif de routage, un message contenant des informations relatives à l'ensemble de chemins de communication.

Le capteur réalisant la détermination peut en outre être configuré pour sélectionner deux capteurs parmi les capteurs du réseau de capteurs, et pour déterminer un nouveau chemin de communication entre les deux capteurs sélectionnés.

Le capteur réalisant la détermination peut en outre être configuré pour sélectionner une liaison de l'ensemble de liaisons, et pour construire un nouveau chemin de communication à partir de la liaison sélectionnée, d'un plus court chemin entre un des deux capteurs sélectionnés et une première extrémité de la liaison, et d'un plus court chemin entre la deuxième extrémité de la liaison et l'autre des deux capteurs sélectionnés.

D'autres caractéristiques et avantages de l'invention apparaîtront encore à la lecture de la description qui va suivre. Celle-ci est purement illustrative et doit être lue en regard des dessins annexés sur lesquels : la Figure 1 est un graphe représentant un réseau de capteurs ;

la Figure 2 est un organigramme illustrant les étapes d'un procédé de communication de données dans le réseau de capteurs selon un mode de réalisation de l'invention, cet organigramme pouvant représenter l'algorithme général du programme informatique au sens de l'invention ;

les Figures 3 à 10 sont des vues similaires à la figure 1 illustrant le déroulement de différentes étapes du procédé de la figure 2 ; et

la Figure 11 est un schéma fonctionnel montrant un capteur du réseau de capteurs, selon un mode de réalisation de l'invention.

L'invention concerne un procédé de traitement de données pour la communication de données dans un réseau d'entités communicantes. Elle est décrite dans le cas de son application à un réseau de capteurs.

La figure 1 montre un réseau de capteurs G représenté sous la forme d'un graphe G.

Le réseau de capteurs G est par exemple utilisé dans le domaine de la sécurité, notamment pour détecter une situation anormale (intrusion d'une personne, dégradation d'une installation, alerte météorologique, détection précoce de séismes).

En variante, le réseau de capteurs G peut être utilisé dans le domaine de la surveillance de l'environnement, notamment pour fournir des informations sur l'environnement (analyse de l'air en des points particuliers, analyse de l'eau, détection des incendies de forêt) ou pour déterminer des assolements optimaux pour différentes cultures.

En variante, le réseau de capteurs G peut être utilisé dans le domaine des applications relatives à la chaîne support logistique, notamment pour délivrer la position d'un véhicule, ou de marchandises, afin de suivre les acheminements et/ou de déterminer le niveau des stocks.

En variante, le réseau de capteurs G peut être utilisés dans le domaine militaire, notamment pour surveiller un champ d'opérations et des actions logistiques devant subvenir aux besoins des opérations, ainsi que dans le domaine de la productique et la domotique. Le réseau de capteurs G comprend un ensemble de dispositifs représentés respectivement par des nœuds (ou sommets) du graphe. On appelle ensemble V l'ensemble des nœuds du graphe G.

L'ensemble de dispositifs comporte trois capteurs ti, t ₂ et t ₃ . Les capteurs ti, t ₂ et t ₃ sont configurés pour mesurer un paramètre de l'environnement dans lequel ils sont implantés et pour transmettre des données de mesure correspondantes à destination d'un autre dispositif du réseau de capteurs G. Chaque capteur t _l5 1 ₂ , t ₃ est en outre configuré pour agir sur son environnement, seul ou en association avec un autre dispositif, en fonction de données de mesure mesurées par le capteur t _l5 t ₂ , t ₃ ou reçues d'un autre capteur t _l5 1 ₂ , t ₃ .

En se référant à la figure 11 , le capteur ^ comporte un module de mesure 1 configuré pour mesurer un paramètre de son environnement, et un module d'émission-réception 2 configuré pour transmettre des données de mesure correspondant à une mesure réalisée par le module de mesure 1 et pour recevoir des données, notamment des données de mesure, provenant des capteurs t ₂ et t ₃ . Le capteur ^ comporte en outre un module de traitement 3 configuré pour mettre en œuvre un procédé de communication de données dans le réseau de capteurs G, décrit en détails plus loin. Les capteurs t ₂ et t ₃ sont réalisés de manière similaire.

L'ensemble de dispositifs comporte également sept dispositifs de routage Ui à u ₇ . Les dispositifs de routage Ui à u ₇ sont configurés pour router les communications entre les capteurs ti, t ₂ et t ₃ .

Ainsi, les capteurs ^ à t ₃ sont des dispositifs émetteurs et/ou destinataires d'un paquet de données, tandis que les dispositifs de routage Ui à u ₇ sont des dispositifs servant d'intermédiaires pour l'acheminement d'u tel paquet de données d'un capteur à un autre. Les capteurs du réseau G sont reliés entre eux par un ensemble de voies de communication (appelées ici également chemins de communication), comprenant des liaisons, chaque liaison (a,b) entre deux dispositifs a et b étant représentée par un lien (ou arêtes) du graphe G. On appelle ensemble E l'ensemble des liens / arêtes du graphe G.

Sur l'exemple représenté à la figure 1, l'ensemble de voies de communication comporte : une liaison (t^Ui) entre le capteur ^ et le dispositif de routage u _l5

une liaison (ti,u ₃ ) entre le capteur ti et le dispositif de routage u ₃ ,

une liaison (ti,t ₂ ) entre le capteur ti et le capteur t ₂ ,

- une liaison (t ₂ ,u ₅ ) entre le capteur t ₂ et le dispositif de routage u ₅ ,

une liaison (t ₂ ,u ₇ ) entre le capteur t ₂ et le dispositif de routage u ₇ ,

une liaison (t ₃ ,Ui) entre le capteur t ₃ et le dispositif de routage Ui,

une liaison (t ₃ ,u ₄ ) entre le capteur t ₃ et le dispositif de routage u ₄ , une liaison (t ₃ ,u ₇ ) entre le capteur t ₃ et le dispositif de routage u ₇ ,

une liaison (ui,u ₂ ) entre le dispositif de routage Ui et le dispositif de routage u ₂ , une liaison (u ₂ ,u ₅ ) entre le dispositif de routage u ₂ et le dispositif de routage u ₅ , une liaison (u ₂ ,u ₆ ) entre le dispositif de routage u ₂ et le dispositif de routage u ₆ ,

- une liaison (u ₃ ,u ₄ ) entre le dispositif de routage u ₃ et le dispositif de routage u ₄ ,

une liaison (u ₃ ,u ₆ ) entre le dispositif de routage u ₃ et le dispositif de routage u ₆ , une liaison (u ₄ ,u ₅ ) entre le dispositif de routage u ₄ et le dispositif de routage u ₅ , et une liaison (u ₆ ,u ₇ ) entre le dispositif de routage u ₆ et le dispositif de routage u ₇ .

Les liaisons sont des liaisons radioélectriques, par exemple des liaisons de type Wifi. En variante, les liaisons pourraient être des liaisons filaires. Une liaison (a,b) est considérée sans orientation, c'est-à-dire qu'elle sert à la communication d'un dispositif a vers un dispositif b, et à la communication du dispositif b vers le dispositif a.

On appelle sous-ensemble T de l'ensemble V ( Γ ç V ) le sous-ensemble des nœuds du graphe G représentant des dispositifs configurés pour pouvoir communiquer entre eux, qui sont émetteurs et/ou destinataires d'un paquet de données, et non pas simples intermédiaires dans l'acheminement de paquets. En d'autres termes, le sous-ensemble T comporte uniquement les capteurs ti, t ₂ , t ₃ , mais pas les dispositifs de routage.

On appelle sous-ensemble (V-T) de l'ensemble V le sous-ensemble des nœuds du graphe G qui n'appartiennent pas au sous-ensemble T. Le sous-ensemble (V-T) comporte donc les dispositifs de routage Ui à u ₇ .

Une communication entre deux capteurs t peut passer par un ou plusieurs dispositifs de routage u, mais ne peut pas passer par un troisième capteur t. Ainsi, on fait l'hypothèse ici qu'un chemin de communication joignant un premier capteur t et un deuxième capteur t' du sous- ensemble T ne peut pas contenir un autre capteur du sous-ensemble T. Ainsi, les chemins de communication entre deux capteurs t et t' du sous-ensemble T ne comprendront aucun capteur en commun, si ce n'est les capteurs t et t' .

On considère par exemple que les liaisons radioélectriques présentent une capacité unitaire donnée et tous les dispositifs émettent sur une même fréquence. En conséquence, une seule communication peut être acheminée à un instant donné sur une liaison.

Les dispositifs n'ont pas nécessairement connaissance de l'ensemble de la topologie du réseau de capteurs. Selon des modes de réalisation de l'invention, les dispositifs t, u ont connaissance de leurs voisins, c'est-à-dire des dispositifs qui leurs sont directement reliés par une liaison.

Selon des modes de réalisation de l'invention, les dispositifs de routage Ui à u ₇ ont en outre connaissance de leur appartenance au domaine réseau d'un capteur ti , t ₂ , t ₃ .

Les capteurs t _l5 t ₂ , t ₃ sont en outre conçus pour exécuter une version distribuée de l'algorithme de Ford-Belman au moyen duquel, à partir d'un ensemble de chemins utilisables, chaque capteur calcule le plus court chemin existant entre lui et un autre capteur destinataire de données à transmettre. Cet algorithme est décrit par exemple dans l'ouvrage intitulé « Graphes et algorithmes », des auteurs M. Gondran et M. Minoux, publié aux Editions Eyrolles.

En référence à la figure 2, on décrit ci-dessous un mode de réalisation du procédé communication de données, qui permet d'améliorer la gestion de la bande passante du réseau de capteurs G. Le procédé est mis en œuvre dans chacun des capteurs t _{l 5} 1 ₂ , t ₃ . En variante, le procédé peut être mis en œuvre dans un seul des capteurs t _l5 1 ₂ , t ₃ , ou bien dans une partie des capteurs t _l5 1 ₂ , t ₃ - Le procédé est mis en œuvre par un capteur t et fait appel, pour un nœud t donné, à des informations topologiques représentatives de la topologie du réseau dans l'environnement de ce nœud t, ces informations topologiques comprend notamment l'ensemble des voisins du nœud t, le domaine réseau X _t du nœud t et la frontière de ce domaine réseau. Ces notions sont définies plus en détail ci-dessous.

On appelle ensemble X _t un ensemble représentant le domaine du nœud t du sous-ensemble

T. L'ensemble X _t comprend des dispositifs du réseau de capteurs G considérés comme appartenant au domaine réseau du capteur t. Le domaine réseau du capteur t peut comprendre, outre le capteur t, un ou plusieurs dispositifs) de routage u, mais pas d'autre capteur t. Aussi, l'intersection entre l'ensemble X _t et le sous-ensemble T contient uniquement le nœud t

On appelle ensemble B(t) un ensemble de dispositifs (capteurs t et/ou dispositifs de routage u) considérés comme voisins du domaine X _t et n'appartenant à aucun domaine. L'ensemble B(t) comprend des dispositifs t, u directement reliés à un dispositif du domaine réseau X _t par une liaison, et qui sont considérés comme n'appartenant pas à un autre domaine réseau X _t -.

On appelle ensemble B'(t) une frontière du domaine X _t . L'ensemble B'(t) comprend des dispositifs t, u considérés comme directement reliés par une liaison à un dispositif n'appartenant pas au domaine X _t . L'intersection entre l'ensemble B'(t) et l'ensemble B'(t') est en outre égale à l'ensemble vide

On appelle variable X" une variable indicatrice du fait qu'un dispositif de routage u du sous-ensemble (V-T) appartient ou non au domaine X _t du capteur t. La variable X" vaut Ί ' si le dispositif de routage u appartient au domaine X _t , et vaut '0' sinon.

On appelle ensemble L(X) un ensemble de dispositifs t, u voisins d'au moins un nœud d'un sous-ensemble X de l'ensemble qui n'appartiennent pas au sous-ensemble X.

L'ensemble L(X) comprend des dispositifs t, u du réseau de capteur G qui n'appartiennent pas au sous-ensemble X mais qui sont directement reliés par une liaison à un dispositif t, u du sous- ensemble X.

On appelle ensemble E(u - v) un ensemble de liaisons formant un chemin de communication d'un premier dispositif u à un deuxième dispositif v du réseau de capteurs G. Un chemin de communication du dispositif u au dispositif v peut comprendre une unique liaison lorsque les dispositifs u et v sont directement reliés par une liaison, ou plusieurs liaisons lorsqu'une communication entre les dispositifs u et v doit être routée via un ou plusieurs dispositifs) de routage du réseau de capteurs G.

On appelle ensemble E(X : Y) un ensemble de liaisons ayant une extrémité dans le sous- ensemble X de l'ensemble V et l'autre extrémité dans le sous-ensemble Y de l'ensemble V.

On appelle ensemble pcch(u - v) un ensemble de liaisons constituant le plus court chemin (du point de vue du nombre de liaisons) du dispositif u au dispositif v.

On appelle ensemble P(t - t') un ensemble de chemins de communication d'un capteur t à un capteur t'.

L'approche proposée ici consiste à déterminer l'ensemble X _t pour les différents capteurs t du réseau, au moyen d'un processus itératif, comprenant les étapes S21 à S23 décrites ci-dessous, processus au cours duquel chaque capteur détermine son domaine réseau X _t . Le processus est donc mis en œuvre de manière répartie entre les différents capteurs du réseau.

A l'initialisation du processus, chaque ensemble X _t comprenant uniquement le capteur t.

Puis, à chaque itération, on ajoute à l'ensemble X _t les voisins de t qui n'appartiennent pas à l'ensemble T et qui n'appartiennent pas déjà à un autre domaine X _t -, c'est-à-dire qu'on ajoute à l'ensemble X _t le contenu de l'ensemble B(t). Ainsi, à chaque itération, l'étendue de l'ensemble X _t est modifiée à partir de la connaissance de la frontière B'(t) de l'ensemble X _t , à la manière d'un front d'onde qui se propagerait à partir de la frontière de l'ensemble X _t .

Chacun des capteurs t du réseau met en œuvre ce même processus. La variable X" , qui caractérise l'appartenance d'un dispositif de routage u au domaine X _t d'un capteur t, varie ainsi au fur et à mesure des modifications des ensembles X _t déterminés par les capteurs t. A l'issu du procédé, on aboutit alors à une répartition des entités t, u du réseau dans des domaines réseaux X _t disjoints.

L'algorithme mathématique correspondant est décrit en détail ci-dessous : il fait ressortir les principes énoncés ci-dessus.

L'étape SI est une étape d'initialisation. Pour chaque capteur t du sous-ensemble T, c'est- à-dire dans l'exemple pour chaque capteur t _l , t ₂ et t ₃ :

l'ensemble X _t est défini comme comprenant uniquement le capteur t,

l'ensemble B(t) est défini comme étant égal à l'ensemble vide, et

l'ensemble B'(t) est défini comme étant égal à l'ensemble vide.

C'est-à-dire que :

De plus, pour chaque couple de capteurs t, t' du sous-ensemble T, l'ensemble P(t-t') est défini comme étant égal à l'ensemble vide.

C'est-à-dire que :

De plus, pour chaque dispositif de routage u du sous-ensemble (V-T) la variable est fixée égale à Ό' , c'est-à-dire que les dispositifs de routage u ₁ à u ₇ sont initialement considérés comme n'appartenant à aucun domaine réseau.

En d' autres termes :

L'étape S2 est une étape de traitement itérative visant à établir le plus grand nombre de chemins entre les capteurs t du sous-ensemble T, c'est-à-dire entre les capteurs t _l , 1 ₂ et t ₃ .

L'étape S2 comprend des opérations S21 à S25.

A l'opération S21, un capteur t du sous-ensemble T est sélectionné.

Puis, un ensemble U _t est déterminé comme contenant les dispositifs de routage u du sous- ensemble (V-T) dont la variable est égale à T . L'ensemble U _t contient donc les dispositifs de routage u considérés comme appartenant au domaine réseau X _t du capteur t sélectionné. A l'initialisation du procédé, cet ensemble U _t est donc vide.

L'opération S21 est répétée pour chaque capteur t du sous-ensemble T, c'est-à-dire pour chaque capteur ti, t ₂ , t ₃ , comme symbolisé par la flèche F ₂ i. Lorsque tous les capteurs t ont été sélectionnés, le procédé passe à l'opération S22.

A l'opération S22, un ensemble U est déterminé comme étant égal à l'union des ensembles U _t . L'ensemble U contient donc les dispositifs de routage u considérés comme appartenant au domaine réseau d'un des capteurs t.

A l'opération S23, un capteur t du sous-ensemble T est sélectionné.

Puis, l'ensemble B(t) est déterminé comme étant égal à l'intersection de l'ensemble des voisins F(X _t ) et du sous-ensemble (V-T), moins l'union de l'ensemble U et des ensembles X _t associés respectivement à chaque capteur t. L'ensemble B(t) contient donc les dispositifs de routage u, considérés comme voisins du domaine réseau du capteur t, et n'appartenant pas déjà à un domaine réseau d'un autre capteur .

Puis, l'ensemble B'(t) est déterminé comme étant égal à l'ensemble B(t), moins l'union des intersections des ensembles B(t) et B'(t) respectivement associés à chaque nœud t du sous- ensemble T. L'ensemble B'(t) contient donc les dispositifs de routage u considérés comme voisins du domaine réseau du capteur t, n'appartenant pas déjà au domaine réseau d'un des capteurs t, et n'appartenant pas à la fois à l'ensemble des voisins d'un des nœuds t et à la frontière du domaine réseau de ce nœud t. La détermination de l'ensemble B'(t) permet de décroiser les frontières des différents domaines réseau.

Puis, l'ensemble B(t) est défini comme étant égal à l'ensemble B'(t).

Puis, le domaine X _t est déterminé comme étant égal à l'union du domaine X _t et de l'ensemble B(t). Le domaine X _t contient donc à ce stade les dispositifs de routage u appartenant déjà au domaine réseau du capteur t, ainsi que les dispositifs de routage u considérés comme voisins du domaine réseau du capteur t et n'appartenant pas déjà à un domaine réseau.

Puis, pour tout dispositif appartenant à l'intersection du domaine X _t et du sous-ensemble

(V-T), la variable ^" est fixée égale à T . Ainsi, la variable ^" de chaque dispositif de routage u appartenant au domaine réseau du capteur t est fixée égale à Ί ' , pour indiquer que le dispositif de routage u appartient au domaine réseau du capteur t.

L'opération S23 est répétée pour chaque capteur t du sous-ensemble T, c'est-à-dire pour chaque capteur t _l5 t ₂ , t ₃ , comme symbolisé par la flèche F23. Lorsque tous les capteurs t du sous- ensemble T ont été sélectionnés, le procédé passe à l'opération S24. A ce stade, les ensembles X _t obtenus sont des ensembles disjoints, dans lesquels sont réparties les entités t, u du réseau : chaque capteur t appartient à un ensemble X _t et un seul, et chaque dispositif u appartient à au plus un ensemble X _t .

Les étapes S24 à S25 décrites ci-dessous définissent un processus itératif pour la détermination de chemins disjoints à partir de ces domaines réseaux disjoints. Dans ce processus de détermination des chemins, comme il s'agit de chemins pour la transmission de données d'un capteur à un autre, chaque chemin aura nécessairement une extrémité dans un domaine réseau d'un capteur et l'autre extrémité dans le domaine réseau d'un autre capteur. En outre, chaque chemin aura une première portion dans un premier domaine réseau et une deuxième portion dans un deuxième domaine réseau. On peut donc construire un chemin complet à partir de portions de chemin déterminées domaine par domaine.

L'algorithme mathématique correspondant est décrit en détail ci-dessous et fait ressortir les principes énoncés ci-dessus. A l'opération S24, un ensemble est déterminé comme étant égal au sous-ensemble T.

A l'opération S25, un capteur t du sous-ensemble T est sélectionné. L'opération S25 comprend une sous-opération S251 comportant la sélection d'un capteur t' appartenant à l'ensemble

Puis, une liaison (u,v) appartenant à l'ensemble E(X _t : X _t ) est sélectionnée. Une liaison (u,v) est donc sélectionnée parmi les liaisons ayant une extrémité dans le domaine réseau du capteur t et une extrémité dans le domaine réseau du capteur t' .

Puis, si les ensembles pcch(t-u) et pcch(v-t') sont non vides, l'ensemble des chemins P(t-t') est déterminé comme étant égal à l'union de l'ensemble P(t-t') et de l'ensemble formé par pcch(t-u), (u,v) et pcch(v-t'). Cette opération de détermination est donc réalisée à condition qu'il existe des liaisons permettant de construire un ensemble (pcch(t-u), (u,v), pcch(v-t')), c'est-à-dire à condition qu'il existe, dans l'ensemble E, des liaisons permettant de construire un nouveau chemin de communication entre les capteurs t et t' . Le nouveau chemin de communication est alors formé par le plus court chemin entre le capteur t et le dispositif de routage u, la liaison (u-v) entre le dispositif u et le dispositif v, et le plus court chemin entre le dispositif v et le capteur t' .

Puis, l'ensemble E est déterminé comme étant égal à l'ensemble E courant moins l'ensemble formé par pcch(t-u), (u,v), et pcch(v-t'). En d'autres termes, les liaisons formant le nouveau chemin de communication sont retirées de l'ensemble des liaisons E, et ne pourront donc plus être utilisées pour construire un nouveau chemin de communication. Cela permet de construire un ensemble de chemins de communication disjoints. La sous-opération S251 est répétée pour chaque capteur t' de l'ensemble T , c'est-à-dire pour chaque capteur ti, t ₂ , t ₃ , comme symbolisé par la flèche F251. Lorsque tous les capteurs t' de l'ensemble T ont été sélectionnés, le procédé sort de la boucle F251.

L'opération S25 est répétée pour chaque capteur t du sous-ensemble T, comme symbolisé par la flèche F25. Lorsque tous les capteurs t du sous-ensemble T ont été sélectionnés, le procédé sort de la boucle F25.

Comme symbolisé par la flèche F2, l'étape S2 est répétée tant qu'il reste un dispositif de routage u du sous-ensemble (V-T) qui n'appartient à aucun domaine X _t . Lorsqu'il ne reste plus de dispositif de routage u du sous-ensemble (V-T) n' appartenant à aucun domaine X _t , le procédé passe à l'étape S3.

L'étape S2 peut être réalisée par l'algorithme ci-dessous :

(suite page suivante)

A l'étape S3, l'ensemble des chemins de communication disjoints déterminé à l'étape S2 est utilisé pour configurer les dispositifs t, u du réseau de capteurs G. En particulier, l'ensemble de chemins de communication est mémorisé dans le capteur t ayant mis en œuvre le procédé.

Puis, un message contenant des informations relatives à l'ensemble des chemins disjoints est transmis, via le module d'émission-réception 2, aux dispositifs de routage u du réseau de capteurs G. Ainsi, les dispositifs de routage u ont connaissance des chemins qui peuvent être utilisés pour la communication entre les capteurs t, ce qui leur permet de router les messages transmis à travers le réseau de capteurs G.

Dans le cas où tous les capteurs t du réseau de capteurs mettent en œuvre le procédé, il n'est pas nécessaire de transmettre le message d'information aux autres capteurs t du réseau de capteurs, puisque ceux-ci ont déjà connaissance des chemins de communication qui peuvent être utilisés entre les capteurs t. Dans le cas où seul un capteur ti du réseau de capteurs G met en œuvre le procédé, l'étape S3 comprend également une opération de transmission du message d'information depuis le capteur ti à destination des capteurs t ₂ et t ₃ .

Le procédé décrit ci-dessus permet de maximiser le nombre total de chemins disjoints qui relient les capteurs t _l5 t ₂ , t ₃ entre eux, c'est-à-dire de déterminer le plus grand nombre de chemins disjoints reliant les capteurs.

Le problème qui consiste à déterminer le nombre maximum de chemins disjoints (arêtes disjointes) entre des terminaux formant un sous-ensemble des nœuds d'un réseau est connu sous le nom de problème de Mader. L'invention propose une solution distribuée au problème de Mader.

Le procédé permet en outre, avec un algorithme de faible complexité, de donner un résultat approché au problème de Mader , qui est par exemple décrit dans le document de A.Frank « On a theorem of mader. Discrète Mathematics, 101 :49-57, 1992 ». L'utilisation d'un algorithme de faible complexité permet de mettre ce procédé en œuvre dans des capteurs classiques d'un réseau de capteurs.

Lorsque le procédé a été exécuté, chaque communication entre deux capteurs ti, t ₂ , t ₃ du réseau de capteurs est réalisée en utilisant un chemin de communication de l'ensemble de chemins de communication. Ce procédé itératif permet ainsi de maximiser la bande passante totale que pourront utiliser les capteurs ti, t ₂ , t ₃ pour communiquer, car l'ensemble des chemins maximise le nombre de chemins disjoints et qu'en conséquence le nombre de chemins utilisables à un instant donné est maximal.

L'utilisation de chemins disjoints permet en outre d'augmenter la sûreté de fonctionnement du réseau de capteurs G. En effet, l'utilisation de chemins disjoints permet d'éviter les risques de collision, donc les risques de non-transmission de données.

On décrit ci-dessous un exemple de réalisation des étapes SI et S2 du procédé, appliqué au réseau de capteurs de la figure 1.

La figure 3 représente les ensembles X _tl , X _t2 , X _t3 après l'étape SI. L'ensemble X _tl , qui représente le domaine réseau du capteur t _{l 5} contient uniquement le capteur t^ De manière similaire, l'ensemble X _t2 , qui représente le domaine réseau du capteur t ₂ , contient uniquement le capteur t ₂ , et l'ensemble X _t3 , qui représente le domaine réseau du capteur t ₃ , contient uniquement le capteur t ₃ .

La figure 3 représente également les ensembles B(ti), B(t ₂ ) et B(t ₃ ) après une itération de l'opération S23 pour chaque capteur t _l5 t ₂ , t ₃ . L'ensemble B(t ), des dispositifs de routage voisins du capteur t _{l 5} contient les dispositifs de routage Ui et u ₃ , qui sont directement reliés au capteur t _l5 respectivement par les liaisons (ti,Ui) et (ti,u ₃ ). De manière similaire, l'ensemble B(t ₂ ), des dispositifs de routage voisins du capteur t ₂ , contient les dispositifs de routage u ₅ et u ₇ , qui sont directement reliés au capteur t ₂ , respectivement par les liaisons (t ₂ ,u ₅ ) et (t ₂ ,u ₇ ), et l'ensemble B(t ₃ ), des dispositifs de routage voisins du capteur t ₃ , contient les dispositifs de routage u _l5 u ₄ et u ₇ , qui sont directement reliés au capteur t ₃ , respectivement par les liaisons (t ₃ ,Ui), (t ₃ ,u ₄ ) et (t ₃ ,u ₇ ).

La figure 4 représente les ensembles B' (ti), B'(t ₂ ) et B'(t ₃ ) après une itération de l'opération S23 pour chaque capteur ti, t ₂ , t ₃ . Dans l'exemple représenté, le capteur t ₃ a été sélectionné en premier. Ainsi, l'ensemble B'(t ₃ ) est égal à l'ensemble B(t ₃ ) de la figure 3.

Le capteur t ₂ a été sélectionné en deuxième. L'ensemble B'(t ₂ ) a donc été déterminé comme étant égal à l'ensemble B(t ₂ ) moins l'ensemble B(t ₃ ). En conséquence, le dispositif de routage u ₇ , qui appartenait à l'ensemble B(t ₃ ) au moment de la détermination, a été retiré de l'ensemble B(t ₂ ) pour obtenir l'ensemble B'(t ₂ ).

Le capteur ti a été sélectionné en troisième. De manière similaire, l'ensemble B'(ti) a donc été déterminé comme étant égal à l'ensemble B(ti) moins l'ensemble B(t ₃ ) et moins l'ensemble B(t ₂ ). En conséquence, le dispositif de routage u _{l 5} qui appartenait à l'ensemble B(t ₃ ) au moment de la détermination, a été retiré de l'ensemble B(ti) pour obtenir l'ensemble B' _d ).

La figure 5 représente les ensembles X _u , X _t2 et X _t3 après une itération de l'opération S23 pour chaque capteur ti, t ₂ , t ₃ . L'ensemble X _u est déterminé comme étant égal à l'union des ensembles X _u et B(ti), après que l'ensemble B(ti) ait été défini comme étant égal à l'ensemble B' (ti). Ainsi, à ce stade, l'ensemble X(ti) contient le capteur ti qu'il contenait initialement, ainsi que le dispositif de routage u ₃ contenu dans l'ensemble B(ti). De manière similaire, l'ensemble X _t2 contient le capteur t ₂ et le dispositif de routage u ₅ , et l'ensemble X _t3 contient le capteur t ₃ et les dispositifs de routage u _l5 u ₄ et u ₇ .

Les figures 5 à 7 représentent le déroulement de deux itérations de l'opération S25.

On considère que le capteur t ₃ est sélectionné à l'opération S25, puis que le capteur t ₂ et la liaison (u ₄ , u ₅ ) sont sélectionnés à la sous-opération S251. La sélection de la liaison (u ₄ ,u ₅ ) est symbolisée sur la figure 5 par la mise en gras de cette liaison.

L'ensemble P(t ₃ -t ₂ ) est alors déterminé comme étant égal à l'union des ensembles P(t ₃ - t ₂ )= 0 et ((pcch(t ₃ -u ₄ )=(t ₃ ,u ₄ ), (u ₄ ,u ₅ ), pcch(u ₅ -t ₂ )=(t ₂ ,u ₅ )). L'ajout du chemin ((t ₃ ,u ₄ ) , (u ₄ ,u ₅ ), (t ₂ ,u ₅ )) dans l'ensemble P(t ₃ -t ₂ ) est symbolisé sur la figure 6 par la représentation des liaisons (t ₃ ,u ₄ ) et (t ₂ ,u ₅ ) en pointillés. Puis, les liaisons (t ₃ ,u ₄ ) , (u ₄ ,u ₅ ), et (t ₂ ,u ₅ ) sont supprimées de l'ensemble E, comme représenté sur la figure 7, pour ne pas être réutilisées.

Lors de l'itération suivante de la sous-opération S251, on considère que le capteur ti et la liaison (ti, Ui) sont sélectionnés. La sélection de la liaison (ti,Ui) est symbolisée sur la figure 5 par la mise en gras de cette liaison. L'ensemble P(t ₃ ,ti) est alors déterminé comme étant égal à l'ensemble ((t ₃ ,Ui), (t^Ui)). L'ajout du chemin ((t ₃ ,Ui), (t^Ui)) dans P(t ₃ -ti) est symbolisé sur la figure 6 par la représentation de la liaison (t ₃ , ) en pointillés. Puis, les liaisons (t ₃ ,uù et (t _{l 5} Ui) sont supprimées de l'ensemble E, comme représenté sur la figure 7.

Lors de l'itération suivante de l'opération S25, le capteur t ₂ est sélectionné. Puis le capteur ti et la liaison (ti , t ₂ ) sont sélectionnés à la sous-opération S251. La sélection de la liaison (ti,t ₂ ) est symbolisée sur la figure 5 par la mise en gras de cette liaison. L'ensemble Pfe-ti) est alors déterminé comme étant égal à l'union de l'ensemble P(t ₂ -ti)= 0 et de l'ensemble (pcch(t ₂ - t ₁ )=(t ₂ ,t ₁ )). Puis, la liaison (t ₂ , ti) est supprimée de l'ensemble E, comme représenté sur la figure 7.

Le procédé continu ensuite de manière similaire, par itération. Les figures 8 à 10 représentent le déroulement de la dernière itération de l'étape S2.

La figure 8 montre que, à ce stade, le domaine X _tl comprend le capteur ^ et le dispositif de routage u ₃ , le domaine Χ _β comprend uniquement le capteur t ₂ , et le domaine X _t3 comprend le capteur t ₃ et le dispositif de routage u ₇ . En outre, la frontière B(ti) est égale à l'ensemble vide, la frontière B(t ₂ ) comprend le dispositif de routage u ₇ , et la frontière B(t ₃ ) comprend les dispositifs de routage u ₄ et u ₆ .

La figure 9 montre que, lors d'une itération de l'opération S25, le capteur t ₃ a été sélectionné. Puis, le capteur ti et la liaison (u ₃ ,u ₄ ) ont été sélectionnés à S251. A ce stade, il n'y a plus, dans l'ensemble E, de liaison entre le capteur t ₃ et le dispositif de routage u ₄ . Un nouveau chemin entre les capteurs t ₃ et ^ ne peut donc pas être construit.

A l'itération suivante de la sous-opération S251, le capteur t ₂ et la liaison (t ₂ ,u ₇ ) sont sélectionnés. Le chemin ((t ₃ ,u ₇ ), (u ₇ ,t ₂ )) est alors ajouté dans l'ensemble P(t ₃ , t ₂ ) des chemins entre les capteurs t ₃ et t ₂ .

La figure 10 représente l'ensemble final des chemins disjoints. Cet ensemble comprend le chemin (ti,t ₂ ) entre les capteurs ti et t ₂ , le chemin ((ti,Ui), (ui,t ₃ )) entre les capteurs ti et t ₃ , et les chemins ((t ₂ , u ₅ ), (u ₅ ,u ₄ ), (u ₄ ,t ₃ )) et ((t ₂ ,u ₇ ), (u ₇ ,t ₃ )) entre les capteurs t ₂ et t ₃ .

Ces quatre chemins de communication sont alors mémorisés dans les différents dispositifs t, u du réseau de capteurs G et seront les seuls chemins de communication utilisés pour les communications entre les capteurs ti, t ₂ et t ₃ . La bande passante du réseau de capteurs G est ainsi optimisée, et la sécurité de la transmission est assurée par l'utilisation de chemins de communication disjoints.

Bien entendu, la présente invention ne se limite pas aux formes de réalisation décrites ci- avant à titre d'exemples ; elle s'étend à d'autres variantes.

Par exemple, le procédé peut être mis en œuvre dans des entités autres que des capteurs, par exemple dans des actionneurs, ou autres types de terminaux. Le réseau informatique n'est donc pas nécessairement un réseau de capteurs, mais peut être, par exemple, un réseau IP utilisant un protocole de type Multiprotocol Label Switching (MPLS), ou encore un réseau ad-hoc, un réseau véhiculaire, un réseau wifi maillé, un réseau de pairs, etc.

En outre, le calcul des chemins peut être réalisé dans une entité physiquement distincte de l'entité communicante qui utilise ce chemin.