La présente invention concerne un procédé de maximisation d'une quantité de transmissions actives dans un réseau mobile sans fïl.

L'invention se situe dans le domaine des communications sur réseaux sans fïls. L'invention est notamment adaptée pour des réseaux de type réseau ad-hoc sans infrastructure comportant des nœuds mobiles comme les réseaux de type MANET (réseau Ad-Hoc mobile: « Mobile Ad-hoc NETwork » en terminologie anglo-saxonne). Chaque nœud est mis en œuvre sous la forme d'un dispositif de communication sans fïl. Dans un réseau ad-hoc mobile, chaque nœud du réseau est relié à d'autres nœuds du réseau par un ensemble de liens inter-nœuds, cet ensemble pouvant varier dans le temps. Les liens sont établis automatiquement grâce à un protocole de communication pour réseaux mobiles, par exemple de type LSR (routage par état de liens : « Link State Routing » en terminologie anglo-saxonne). La présente invention s'applique donc à des dérivés des réseaux LSR, c'est-à-dire des réseaux utilisant le standard OSPF (ouverture du chemin de transmission le plus court en premier : « Open Shortest Path First » en terminologie anglo-saxonne, et des versions optimisées du standard OSPF, comme OLSR (Routage par état de liens optimisé : « Optimised Link State Routing » en terminologie anglo-saxonne) ou MARP (Protocole de routage prenant en compte la mobilité : « Mobility Aware Routing Protocol » en terminologie anglo-saxonne). Chaque lien possède des capacités limitées, elles aussi variables dans le temps, comme par exemple une bande passante ou une latence de transmission. Les liens et nœuds forment un graphe de communication (aussi dénommé topologie) variable dans le temps. On parlera dans la suite du document de capacités du réseau pour englober les capacités de l'ensemble des liens constituant un réseau.

Un réseau ad-hoc mobile peut supporter bon nombre d'applications. Dans une application d'échange de données envisagée dans le cadre de l'invention, chaque nœud est aussi un capteur optronique capable d'acquérir des données et notamment des données de type image, vidéo et/ou audio. Les données ainsi acquises sont échangées entre des nœuds du réseau suite à des demandes de transmission émises soit par un nœud source, soit par un ou plusieurs nœuds destinataires. En fonction du nombre de destinataires, les transmissions pourront se faire en mode point-à-point (« unicast » en terminologie anglo-saxonne), ou en mode point-multipoint (« multicast » en terminologie anglo-saxonne).

Pour éviter des phénomènes de congestion ou de perte de données dans le réseau, il faut en général s'assurer de la compatibilité des caractéristiques d'un trafic de données induit par une transmission avec les capacités d'un réseau. Parmi les caractéristiques les plus souvent considérées, on trouve un débit du trafic, une latence requise pour ce trafic et parfois un niveau de priorité relatif de ce trafic par rapport à d'autres trafics concurrents. Le niveau de priorité d'un trafic, aussi appelé niveau de criticité, est le plus souvent représentatif du niveau d'importance de ce trafic. On considérera par la suite que les trafics les plus critiques doivent impérativement être transmis.

La mise en œuvre d'une application d'échange de données dans un réseau ad- hoc mobile pose un certain nombre de problèmes et notamment un problème de gestion des demandes de transmission. En effet, le caractère mobile des nœuds du réseau entraîne des variations constantes de sa topologie. Les capacités des liens reliant deux nœuds peuvent, par conséquent, varier au cours du temps. De plus, de nouveaux nœuds peuvent apparaître alors que d'autres peuvent disparaître, ce qui induit des créations et des disparitions de liens. Il semble ainsi nécessaire de prendre constamment en compte ces modifications de topologie dans la gestion des demandes de transmission, mais aussi dans la gestion des transmissions en cours. L'invention a pour but de maximiser un nombre de transmissions actives dans le réseau ad-hoc mobile considéré à un instant donné. Une transmission active est ici définie comme une transmission en cours, ayant fait préalablement l'objet d'une demande de transmission, cette demande ayant été autorisée par un système de gestion des demandes de transmission. Une demande de transmission autorisée se concrétise donc par une transmission active. Par opposition, une demande de transmission en attente est une demande n'ayant pas été autorisée par le système de gestion des demandes de transmission, cette demande ayant été mise en attente pour pouvoir être considérée plus tard par le système. Elle peut se révéler caduque si elle ne peut être honorée par le réseau. Cela peut être le cas suite à une intervention d'un opérateur ou après expiration d'un temps maximal (« time-out » en terminologie anglo-saxonne) d'admission. Nous verrons par la suite que la résolution de ce problème global revient à résoudre des problèmes plus ciblés dépendant du contexte, comme par exemple la vérification de la compatibilité du trafic associé à une demande de transmission avec les capacités du réseau, ou la mise à jour des transmissions en cours en cas de modification de topologie.

L'invention concerne un procédé de maximisation d'une quantité de demandes de transmission autorisées parmi un ensemble de demandes de transmission dans un réseau sans fil mobile comprenant une pluralité de nœuds mobiles reliés par des liens, chaque lien étant associé à des capacités comprenant une bande passante et une latence, chaque transmission devant s'opérer sur un chemin de transmission et étant associée à des caractéristiques comprenant un débit et une latence maximale admissibles, ledit procédé étant mis en œuvre par un nœud maître et étant caractérisé en ce qu'il est activé sur réception par le nœud maître d'un événement appartenant à un ensemble prédéfini d'événements, l'ensemble prédéfini d'événements comprenant un premier type d'événement impliquant une modification de topologie du réseau, et en ce qu'il comprend les étapes suivantes: obtenir un ensemble de demandes de transmission ; si l'événement est du premier type, mettre en œuvre une procédure d'optimisation sous contrainte comprenant les étapes suivantes : définir des contraintes comprenant des contraintes de débit et de latence en fonction des capacités de chaque lien impliqué dans chaque chemin de transmission retenu pour chaque demande de transmission de l'ensemble de demandes de transmission ; définir au moins un sous-ensemble de l'ensemble de demandes de transmission ; associer chaque sous-ensemble défini avec une fonction de coût, la fonction de coût associée à un sous-ensemble prenant en compte les chemins de transmission retenus pour les demandes de transmission respectives comprises dans le sous-ensemble ; déterminer un sous-ensemble de cardinalité maximale compatible avec les contraintes définies et minimisant la fonction de coût, le sous-ensemble déterminé représentant les demandes de transmission à autoriser.

De cette manière, le procédé assure que le nombre de demandes de transmission est maximisé et utilise au maximum les capacités du réseau sans fil mobile.

Selon un mode de réalisation, l'ensemble prédéfini comprend un second type d'événement n'impliquant aucune modification de topologie du réseau, la détermination du sous-ensemble de cardinalité maximum compatible avec les contraintes définies dans le cadre d'un événement du deuxième type utilise une procédure de détermination des demandes de transmission à autoriser simplifiée, la mise en œuvre de la procédure d'optimisation sous contrainte dépendant du résultat de la procédure de détermination des demandes de transmission à autoriser simplifiée.

De cette manière, le choix des demandes de transmission à autoriser est simplifié. Selon un mode de réalisation, les caractéristiques d'une demande de transmission comprennent de plus un niveau de criticité permettant d'ordonner le traitement des demandes de transmission entre elles, les niveaux de criticité respectifs des demandes de transmission d'un sous-ensemble donné étant pris en compte par le procédé sous forme d'une contrainte supplémentaire permettant d'assurer que le sous-ensemble déterminé comprend les demandes de transmission de l'ensemble des demandes de transmission associées à des niveaux de criticité les plus élevés.

De cette manière, les demandes de communication les plus importantes sont privilégiées.

Selon un mode de réalisation, chaque chemin de transmission retenu pour une demande de transmission appartenant à un sous-ensemble de demandes de transmission donné est associé à un coût dépendant d'une quantité de nœuds traversés par le chemin de transmission, la fonction de coût d'un sous-ensemble de demandes de transmission donné étant la somme des coûts associés aux chemins de transmission retenus pour chaque demande de transmission comprise dans le sous-ensemble de demandes de transmission donné.

Selon un mode de réalisation, la procédure d'optimisation sous contrainte comprend une recherche de chemins de transmission optimaux pour chaque demande de transmission. Selon un mode de réalisation, l'ensemble des demandes de transmission comprend des demandes autorisées associées à des transmissions en cours et des demandes en attente.

Selon un mode de réalisation, chaque nœud du réseau comprend un capteur optronique capable d'acquérir des informations comprenant des données de type image et vidéo, les transmissions mises en œuvre par le procédé étant des transmissions de ces informations.

Selon un mode de réalisation, le premier type d'événement correspond à des événements relatifs à : une modification d'au moins une caractéristique d'un lien du réseau ; ou, une apparition de nouveau nœud dans le réseau.

Selon un mode de réalisation, le second type d'événement correspond à des événements relatifs à : une réception d'une nouvelle demande de transmission de la part d'un nœud source ou d'un nœud destinataire sans modification de topologie du réseau ; ou, une fin d'une transmission active sans modification de topologie du réseau.

Selon un mode de réalisation, le sous-ensemble déterminé est le sous-ensemble de cardinalité maximale compatible avec l'ensemble des contraintes définies et minimisant la fonction de coût à un moment d'arrêt de la procédure d'optimisation sous contrainte.

Selon un deuxième aspect de la présente invention, la présente invention concerne un dispositif de communication apte à maximiser une quantité de demandes de transmission autorisées parmi un ensemble de demandes de transmission dans un réseau sans fil mobile comprenant une pluralité de dispositifs de communication reliés par des liens, chaque lien étant associé à des capacités comprenant une bande passante et une latence, chaque transmission devant s'opérer sur un chemin de transmission et étant associée à des caractéristiques comprenant un débit et une latence maximale admissibles, ledit dispositif étant caractérisé en ce qu'il comprend : des moyens pour recevoir des événements ; des moyens pour déterminer un type d'un événement reçu dans un ensemble prédéfini d'événements, l'ensemble prédéfini d'événements comprenant un premier type d'événement impliquant une modification de topologie du réseau ; des moyens pour obtenir un ensemble de demandes de transmission ; et, des moyens pour optimiser sous contrainte comprenant: des moyens pour définir des contraintes comprenant des contraintes de débit et de latence en fonction des capacités de chaque lien impliqué dans chaque chemin de transmission retenu pour chaque demande de transmission de l'ensemble de demandes de transmission obtenu ; des moyens pour définir des sous-ensembles de l'ensemble de demandes de transmission obtenu ; des moyens pour associer chaque sous-ensemble défini avec une fonction de coût, la fonction de coût associée à un sous-ensemble prenant en compte les chemins de transmission retenus pour les demandes de transmission respectives comprises dans le sous-ensemble ; et, des moyens pour déterminer parmi les sous-ensembles définis, un sous-ensemble de cardinalité maximale compatible avec les contraintes définies et minimisant la fonction de coût associée, le sous-ensemble déterminé représentant les demandes de transmission à autoriser.

Selon un troisième aspect de la présente invention, la présente invention concerne un système de communication comprenant une pluralité de dispositifs de communication mobiles communicant selon un mode de communication sans fils, et comprenant un dispositif de communication selon le deuxième aspect.

Selon un quatrième aspect de la présente invention, la présente invention concerne un produit programme d'ordinateur comportant des instructions pour mettre en œuvre, par un dispositif, le procédé selon le premier aspect par un processeur du dispositif.

Selon un cinquième aspect de la présente invention, la présente invention concerne des moyens de stockage, stockant un programme d'ordinateur comportant des instructions pour mettre en œuvre, par un dispositif, le procédé selon le premier aspect lorsque ledit programme est exécuté par un processeur du dispositif.

Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, apparaîtront plus clairement à la lecture de la description suivante d'un exemple de réalisation, ladite description étant faite en relation avec les dessins joints, parmi lesquels :

- la Fig. 1 représente sous forme de schéma le principe d'un algorithme de gestion des demandes de transmission adapté à une application d'échange de données dans un réseau ad-hoc mobile;

- la Fig. 2 représente un algorithme de vérification de la compatibilité d'un trafic induit par une demande de transmission avec des caractéristiques du réseau ad-hoc mobile;

- la Fig. 3 représente un algorithme de test de la compatibilité d'un trafic induit par une demande de transmission avec des caractéristiques du réseau et prenant en compte des trafics déjà existants sur le réseau ad-hoc mobile;

- la Fig. 4 représente un algorithme d'optimisation sous contrainte de la quantité de transmissions actives sur le réseau ad-hoc mobile à un instant donné; - la Fig. 5 représente un algorithme de vérification de la compatibilité de transmissions existantes avec une évolution de la topologie du réseau ad-hoc mobile;

- la Fig. 6 représente un algorithme de mise à jour des transmissions sur le réseau ad-hoc mobile;

- la Fig. 7 illustre schématiquement un exemple d'architecture matérielle d'un dispositif apte à mettre en œuvre un nœud du réseau selon la présente invention; et

- la Fig. 8 illustre un exemple de réseau ad-hoc mobile.

L'invention est mise en œuvre dans un réseau de type réseau ad-hoc mobile et est particulièrement avantageuse dans un réseau ad-hoc mobile maillé dont un exemple est représenté par la Fig. 8. La Fig. 8 représente un réseau ad-hoc mobile maillé 800 comportant huit nœuds mobiles, numérotés de 801 à 808 sur la Fig. 8. Comme nous l'avons vu plus haut, chaque nœud comporte des moyens de communication sans fils et des moyens d'acquisition de données comme par exemple un capteur optronique. Les nœuds sont reliés entre eux par des liens sans fils, numérotés de 8001 à 8016 sur la Fig. 8. Le nombre de liens et leurs caractéristiques, telles que leur bande passante et leur latence, sont variables dans le temps. Un trafic induit par une transmission entre un nœud source et un nœud récepteur emprunte un certain nombre de liens qui forment entre eux un chemin de transmission. Le chemin de transmission entre deux nœuds emprunté par le trafic est le plus souvent déterminé par un algorithme de routage de type LSR. Comme nous pouvons le voir dans la Fig. 8, une transmission entre un nœud source et un nœud destinataire peut emprunter plusieurs chemins de transmission. Il est alors nécessaire de choisir parmi les chemins de transmission possibles, un chemin de transmission optimal suivant un critère donné, comme par exemple le nombre de nœuds traversés qui est à minimiser. Parmi les nœuds du réseau, un nœud particulier est prévu pour gérer la synchronisation des horloges de tous les nœuds et de mettre en œuvre un procédé de gestion des demandes de transmission selon l'invention. Ce nœud, que nous appellerons « nœud maître » par la suite, et numéroté 808 sur la Fig. 8, peut être défini par un utilisateur à l'initialisation du réseau.

Un algorithme de gestion des demandes de transmission selon l'invention est illustré à la Fig. 1. Cet algorithme est mis en œuvre par le nœud maître du réseau. L'algorithme de gestion des demandes de transmission peut être lancé dans une étape 11 lors de la réception d'un événement par le nœud maître. Dans le contexte de l'invention, un événement peut être de plusieurs types. Les deux premiers types d'événements envisagés n'induisent pas de modification de la topologie du réseau.

I. Il s'agit pour le premier de la réception d'une ou plusieurs nouvelles demandes de transmission formulée(s) soit par un nœud source, soit par un nœud destinataire, soit automatiquement, soit suite à une requête d'un utilisateur. Le procédé de l'invention consiste à insérer cette (ou ces) nouvelle(s) transmission(s) qui peut (peuvent) être acceptée(s) en prenant en compte les capacités du réseau et les transmissions actives, i.e. les transmissions en cours, mais aussi éventuellement les demandes de transmission qui n'auraient pas été honorées et qui sont restées en attente. On note que lorsqu'une demande de transmission concerne une transmission entre un nœud source et une pluralité de récepteurs, par exemple dans le cadre d'une transmission point-multipoint, on considère que la demande de transmission concerne une pluralité de transmissions point à point entre le nœud source et chacun des nœuds récepteurs. Chaque transmission point à point est alors vérifiée. Dans un mode de réalisation, chaque transmission point à point peut être acceptée et mise en œuvre indépendamment des autres transmissions point à point de la pluralité de transmissions point à point. Dans un autre mode de réalisation, lorsqu'au moins une transmission point à point de la pluralité de transmissions point à point n'est pas acceptée, la transmission point-multipoint est intégralement refusée, de sorte qu'aucune transmission point à point n'est mise en œuvre.

II. Pour le second, il s'agit de la cessation d'une transmission active. Cette fin de transmission libère des ressources sur le réseau.

Les deux types d'événements suivants induisent des changements de la topologie du réseau:

III. Il s'agit pour le premier, d'une modification de liens existants. Le réseau étant mobile, les nœuds se déplacent et les capacités des liens connectant ces nœuds entre eux évoluent au cours du temps. La bande passante de certains nœuds peut par exemple diminuer, ou s'annuler, ce qui peut entraîner un reroutage de certaines transmissions actives sur d'autres liens, ou l'arrêt de certaines transmissions. Inversement, la bande passante de certains liens peut augmenter. IV. Pour le second, il s'agit de l'établissement de nouveaux liens. Cet événement couvre l'arrivée d'un nouveau nœud dans le réseau. Ce nouveau nœud entraîne la création de nouveaux liens et l'introduction de nouveaux trafics associés au nouveau nœud, ce qui modifie les capacités du réseau. Des transmissions mises jusque-là en attente peuvent alors être honorées du fait de ces nouvelles capacités.

Nous verrons par la suite que la distinction entre les événements n'induisant pas de modification de la topologie du réseau et ceux induisant une telle modification permet de simplifier la résolution du problème de gestion des demandes de transmission.

Dans une autre mise en œuvre, l'algorithme de gestion des demandes de transmission peut être lancé périodiquement par exemple pour suivre les évolutions de la topologie du réseau ou des transmissions en cours. Le lancement de l'algorithme de gestion des demandes de transmission peut par exemple faire suite à un algorithme de mise à jour des tables de routage des nœuds du réseau, mis en œuvre par un protocole de routage, par exemple de type LSR.

L'algorithme de gestion des demandes de transmission se poursuit donc par l'identification du type du nouvel événement reçu par le nœud maître. Lors d'une étape 12, le nœud maître détermine si l'événement est de type I. Si oui, l'algorithme se poursuit par une étape 13 de vérification de la compatibilité d'une nouvelle demande de transmission avec les capacités du réseau que nous détaillons par la suite en relation avec les Figs. 2 à 4.

Sinon, le nœud maître détermine si l'événement est de type II lors d'une étape 14. Si c'est le cas, cette étape est suivie d'une étape 15 de mise à jour des transmissions que nous détaillerons par la suite en relation avec la Fig. 5.

Sinon, le nœud maître détermine si l'événement est de type III lors d'une étape 16. Si c'est le cas, l'algorithme se poursuit avec une étape 17 de vérification de la compatibilité des transmissions existantes avec les capacités du réseau que nous détaillerons en relation avec la Fig. 6.

Sinon, le nœud maître détermine si l'événement est de type IV lors d'une étape

18. Si c'est le cas, l'algorithme se poursuit par une étape 19 de mise à jour des transmissions que nous détaillerons par la suite de nouveau en relation avec la Fig. 6.

Si l'événement considéré ne correspond pas à un événement connu, aucune modification n'est apportée aux transmissions en cours. Les étapes 13, 15, 17 et 19 sont suivies par une étape 21 dans laquelle le nœud maître autorise que soient mises en œuvre des transmissions correspondant à un ensemble de demandes de transmission sélectionnées lors des étapes 13, 15, 17 et 19. Si aucun sous-ensemble n'a été retenu, aucune transmission n'est mise en œuvre.

Dans un mode de réalisation, si l'événement considéré ne correspond pas à un événement connu, le nœud maître met en œuvre un algorithme d'optimisation sous contrainte de la quantité de transmissions actives sur le réseau ad-hoc mobile décrit en relation avec la Fig. 4.

Une mise en œuvre détaillée de l'étape 13 de la Fig. 1 est décrite en Fig. 2. Lors d'une étape 131, des caractéristiques d'une nouvelle demande de transmission sont obtenues par le nœud maître par exemple sous la forme d'une requête. Les caractéristiques contenues dans la requête comprennent par exemple une identification du nœud source de la transmission demandée, une identification d'un ou plusieurs destinataires de cette transmission, un débit du trafic induit par cette transmission, une latence requise par cette transmission et un niveau de criticité de cette transmission. Cette nouvelle demande est insérée dans une liste de demandes en attente lors d'une étape 132. Cette liste peut être vide ou déjà contenir une ou plusieurs demandes de transmission en attente.

On utilise une variable D pour représenter le nombre de demandes de transmission en attente présentes dans la liste. Lors d'une étape 133, on initialise une variable d à la valeur « 0 ». Cette variable d est utilisée pour parcourir la liste des demandes en attente. Lors d'une étape 134, la variable d est comparée à la variable D pour déterminer si toutes les demandes de transmission en attente ont été considérées. Si des demandes restent à considérer, lors d'une étape 136, le nœud maître teste la compatibilité du trafic induit par la demande d'indice d avec les capacités du réseau et notamment avec les capacités des liens impliqués dans le chemin de transmission retenu pour le trafic induit par la demande d'indice d. Nous détaillerons l'étape 136 en relation avec la Fig. 3.

Si le trafic associé à la demande d'indice d est compatible avec le chemin de transmission retenu pour la transmission de ce trafic, le nœud maître effectue une étape 138 au cours de laquelle la variable d est incrémentée d'une unité pour passer à la demande de transmission suivante.

Si, lors de l'étape 134, la variable d a atteint la valeur de la variable D, toutes les demandes de transmission en attente sont acceptées par le nœud maître lors d'une étape 135. La liste des demandes en attente est alors vidée. Dans ce cas, les transmissions en cours peuvent continuer et les transmissions correspondant aux demandes en attente sont mises en œuvre.

Pour ce faire, la réservation des liens impliqués dans la transmission des trafics, pour toutes les demandes acceptées, peut être assurée par le protocole RSVP (protocole de réservation de ressources (« Resource reSerVation Protocol » en terminologie anglo- saxonne).

L'accès concurrent au médium des différentes transmissions pourra être assuré par des méthodes classiques de la couche liaison (« Médium Access Control Layer » en terminologie anglo-saxonne) de données du modèle OSI (« Open Systems Interconnection" en terminologie anglo-saxonne) comme les méthodes:

• CSMA/CA : « Carrier Sensé Multiple Access/collision avoidance »

• CSMA/CD : « Carrier Sensé Multiple Access/Collision Détection »

• CDMA : « Code Division Multiple Access »

· TDMA : « Time Division Multiple Access »

• FTDMA (ou OFDMA) : « Frequency Time Division Multiple Access » (ou « Orthogonal Frequency Division Multiple Access »).

Par contre, si, lors de l'étape 136, le nœud maître détermine qu'un des trafics induit par l'une des demandes en attente est incompatible avec une transmission sur un chemin de transmission retenu pour réaliser la transmission de ce trafic, le parcours de la liste est stoppé et une optimisation sous contrainte, que nous détaillerons plus loin en relation avec la Fig. 4, est lancée pour déterminer quelles transmissions doivent être acceptées.

On peut noter que les étapes 134, 135, 136 et 138 de l'algorithme de la Fig. 2 constituent une procédure simplifiée de détermination des demandes de transmission à autoriser. Cette procédure simplifiée permet d' éviter la mise en œuvre d'une optimisation sous contrainte, qui est une procédure complexe ayant un coût calculatoire élevé. Nous verrons par la suite que lorsque la topologie du réseau est modifiée, l'étape 137 d'optimisation sous contrainte est mise en œuvre directement sans mettre en œuvre la procédure simplifiée.

La Fig. 3 donne une représentation détaillée d'un exemple d'algorithme mettant en œuvre l'étape 136. Comme nous l'avons vu plus haut, chaque demande de transmission est associée à une information représentant un nœud source et une information représentant au moins un nœud destinataire. En utilisant un protocole de type LSR, il est possible de connaître le meilleur chemin de transmission reliant le nœud source à un nœud destinataire. Ce meilleur chemin de transmission est le chemin de transmission retenu pour toute transmission entre un nœud source et un nœud destinataire. Ce protocole permet de mettre à jour périodiquement la topologie du réseau.

L'algorithme de la Fig. 3 commence par l'initialisation, lors d'une étape 13601, d'une variable n à la valeur « 0 ». Cette variable sert à parcourir un ensemble de N chemins de transmission que doit suivre un trafic donné. Si un trafic est destiné à un seul nœud destinataire, comme c'est le cas en point-à-point, un seul chemin de transmission est considéré (N= 1 ) . Si un trafic est destiné à N (N> 1 ) nœuds destinataires, comme c'est le cas en point-multipoint, N chemins de transmission sont considérés. Lors d'une étape 13603, le nœud maître détermine si tous les chemins de transmission pris par un trafic t ont été envisagés. Si ce n'est pas le cas, les caractéristiques du chemin de transmission d'indice n sont déterminées par le nœud maître lors d'une étape 13605. Un chemin de transmission est associé à des nœuds qu'il traverse et à des liens reliant les nœuds traversés. On suppose que les capacités de chaque lien sont connues lors de cette étape par une extension du protocole LSR. En considérant qu'un chemin de transmission comprend L _c ( L _c ≥l) liens, chaque lien (identifié ci-après grâce à une variable X) constituant ce chemin de transmission est associé à une bande passante ΒΡ _λ Afin de parcourir l'ensemble des liens constituant le chemin de transmission d'indice n, la variable λ représentant des liens à parcourir est initialisée à la valeur « 0 » par le nœud maître lors d'une étape 13607. Le nœud maître compare ensuite la variable λ à L _c pour déterminer si tous les liens ont été pris en compte lors d'une étape 13609.

Si des liens restent à prendre en compte, une étape 13611 suit l'étape 13609. Au cours de l'étape 13611, une somme ( r _t + R ) d'un débit r _t associé au trafic t et d'un débit R des trafics concurrents existant sur le lien d'indice λ est comparée à la bande passante disponible sur le lien d'indice λ, ΒΡ _λ par le nœud maître. Les trafics concurrents sont ici des trafics utilisant le lien d'indice λ engendrés par des transmissions actives ou correspondant à des demandes de transmission d'indice d déjà considérées par l'algorithme de la Fig. 2. Si la somme est supérieure à la bande passante disponible, le trafic t est considéré comme incompatible avec les capacités du réseau. Sinon, l'algorithme continue avec le calcul de la latence de transmission du trafic t sur le chemin de transmission d'indice n (LATn) lors d'une étape 13613. On suppose ici que la latence de chaque lien LAT _X est connue lors de cette étape par une extension du protocole LSR. La latence du chemin de transmission d'indice n est la somme des latences de tous les liens compris dans le chemin de transmission d'indice n. La variable λ est ensuite incrémentée d'une unité par le nœud maître pour passer au lien suivant lors d'une étape 13615.

Si, lors de l'étape 13609, le nœud maître constate que tous les liens constituant le chemin de transmission d'indice n ont été pris en compte, le nœud maître compare la latence de transmission LATn du trafic t sur le chemin de transmission d'indice n à la latence LA Tt pour le trafic t. Si la latence calculée lors de l'étape 13613 est supérieure à la latence souhaitée, le trafic t est considéré comme incompatible avec les capacités du réseau. Sinon lors d'une étape 13619, le nœud maître incrémente la variable n d'une unité pour passer au chemin de transmission suivant.

Si, lors de l'étape 13603, tous les chemins de transmission retenus pour la transmission du trafic t ont été pris en compte sans que le trafic t soit considéré comme incompatible avec les capacités du réseau, le trafic t est déclaré compatible avec les capacités courantes du réseau lors d'une étape 13623.

De retour à la Fig. 2, si au moins un trafic lié à une demande en attente dans la liste de demandes en attente est considéré comme incompatible avec les caractéristiques du réseau, une optimisation du nombre de transmissions actives est mise en œuvre lors de l'étape 137. Cette optimisation est une optimisation sous contrainte.

Soit un ensemble de demandes de transmission. On suppose dans un premier temps que toutes les demandes de transmission sont d'un niveau de criticité égal. Par conséquent, le niveau de criticité n'est ici pas pris en compte pour ordonner les demandes de transmission entre elles. Chaque demande de transmission est associée à un trafic t appartenant à un ensemble de trafics de cardinal card(3 . Soit l'ensemble des sous-ensembles de trafics T ^* (de cardinal card(7* )) de 3tels que card( ^* ) < card(3). L'objectif de l'optimisation est donc de trouver un sous-ensemble de trafic T ^* maximisant card(J7* ), maximisant donc la quantité de transmissions actives à un instant donné.

Comme évoqué plus haut, on suppose ici pour simplifier qu'une transmission point-multipoint est un ensemble de transmissions point-à-point. Soit V _t l'ensemble des chemins de transmission possibles dans le réseau maillé utilisable pour un trafic t. Un protocole de routage permet d'identifier dans ce réseau le chemin de l'ensemble TJ _t minimisant une fonction de coût. Généralement ce chemin de transmission correspond au chemin de transmission le plus court, Le. le chemin de transmission minimisant le nombre de nœuds traversés.

L'algorithme d'optimisation peut prendre deux formes :

• Dans la première forme, on considère qu'un protocole de routage (potentiellement intégré à LSR) donne le meilleur chemin de transmission pour chaque trafic considéré. Les chemins de transmission font ainsi partie des données d'entrée de l'algorithme d'optimisation et ne sont donc pas remis en cause lors de l'optimisation. Seul le choix des trafics à autoriser est la donnée à optimiser pour maximiser le nombre de transmissions actives.

· Dans la seconde forme, les chemins de transmission eux-mêmes font partie des données à optimiser. On optimise alors conjointement la quantité de transmissions actives et les chemins de transmission utilisés par le trafic induit par chaque transmission active.

Dans la première forme, chaque trafic t considéré est associé à un chemin de transmission déterminé par le protocole de routage. Soit c^e T^ le chemin de transmission associé au trafic t. Ce chemin de transmission est associé à un ensemble de liens traversés X _t , chaque lien d'indice λ de X _t appartenant à un ensemble X composé des liens constituant le réseau. D'autre part, chaque trafic est associé à un débit r _t et à une latence désirée LA Tt.

Chaque lien d'indice λ du réseau est associé à une variable booléenne δ[ indiquant si le lien est utilisé ( δ[ =1) par le trafic t ou pas ( δ[ =0). De plus, chaque lien est associé à une bande passante maximale ΒΡ _λ et à une latence LAT .

L'optimisation sous contrainte nécessite une évaluation d'un coût associé à chaque solution trouvée. Ici le coût F _r* d'une solution correspondant à un sous-ensemble de trafic 7* est une somme de coûts fi respectivement associés aux chemins de transmission c _t utilisés pour les trafics t.

Dans le domaine des réseaux, il est classique d'utiliser la quantité de nœuds, aussi appelé nombre de sauts (« hop » en terminologie anglo-saxonne), impliqués dans un chemin de transmission pour représenter le coût d'un chemin de transmission. On considère en effet qu'en minimisant le nombre de nœuds impliqués dans un chemin de transmission, on minimise le risque que le trafic traversant ce chemin de transmission perturbe le réseau dans son ensemble. Minimiser le nombre de nœuds traversés par un chemin de transmission revient à minimiser le nombre de liens utilisés par ce chemin de transmission. Une fonction de coût représentant un nombre de liens est donc utilisée. La fonction de coût fi associée à un chemin de transmission et est alors donnée par :

Pour un ensemble de trafic t G T ^* , le coût global des transmissions sur leur chemin de transmission respectif est donné par :

F7* =∑∑¾

Le réseau utilisé implique plusieurs types de contraintes comprenant généralement une contrainte de débit et une contrainte de latence. Une contrainte de débit Cl est telle que le débit cumulé des trafics traversant un lien donné ne doit pas dépasser la bande passante admissible sur ce lien. Cette contrainte s'exprime, par exemple, de la manière suivante :

VA E X, ∑δ{.η≤ΒΡ _{λ (C1)}

Une contrainte de latence C2 est telle que la latence sur le chemin de transmission retenu pour un trafic t est compatible avec une latence souhaitée. On exprime cette contrainte, par exemple, de la manière suivante :

Vi e y* ô[.LAT _x < LAT _{t (C2)}

Pour un nombre de demandes de transmission autorisée donnée, l'algorithme d'optimisation sous contrainte cherche le sous-ensemble de trafics de taille maximum minimisant la fonction de coût _yt tout en restant compatible avec les capacités du réseau. Un troisième type de contrainte est donc une contrainte C3 de taille d'un sous ensemble de trafics optimal 3^,, .

W*, card( r _o l _t ) > card( T*) (C3).

La variable à maximiser est la taille du sous-ensemble de trafic 7* (i.e. le cardinal du sous-ensemble de trafic T ^* ). Si pour cette taille maximale, plusieurs solutions existent, l'algorithme choisit la solution minimisant la fonction de coût. L'optimisation peut donc se résumer de la manière suivante :

opt Γ *^ Γ

sous

t≡ûr* e *, ∑δ _λ ' ΙΛΤ _λ ≤ΙΛΤ, (C2) _>

λε ;

V *, card(jr _{o t} )≥card(jr*) (C3). ού2ζ _ρί est le sous-ensemble de trafics optimal, min(x) prend le minimum d'une variable x, card(if) donne le cardinal d'un ensemble £. Jusque-là, nous avons considéré que toutes les transmissions étaient d'un niveau de criticité égal. En réalité certaines transmissions sont plus critiques que d'autres, et les transmissions les plus critiques sont privilégiées. Le niveau de criticité est donc utilisé pour ordonner les demandes de transmission entre elles. Les demandes de transmission de niveaux de criticité les plus élevés doivent de préférence être maintenues en cas de surcharge du réseau. Une demande de transmission critique est par exemple une demande de transmission contenant une information d'importance élevée, ou encore une demande de transmission d'informations urgentes dont l'intérêt dépend de la date à laquelle elles sont reçues.

La prise en compte du niveau de criticité d'une transmission dans l'optimisation précédente peut se faire par l'ajout d'une contrainte :

t , Vi e {y - _opt } , \fp _t , \fp _topt , p _topt ≥ p _t (C4) où - y _p ^* _t I est l'ensemble des sous-ensembles de trafics de l'ensemble de trafics ne comprenant pas le sous-ensemble de trafics optimal^ , p _t est un niveau de criticité associé à une transmission comprise dans le sous-ensemble de trafics optimal V _opt et p _t est un niveau de criticité associé à une transmission comprise dans ^~ - df _p ^* _t ]

. Cette contrainte empêche qu'une transmission appartenant à l'ensemble optimal ait un niveau de criticité inférieur à une transmission qui n'aurait pas été sélectionnée dans l'ensemble optimal.

Dans un mode de réalisation, d'autres contraintes peuvent être envisagées comme par exemple, une contrainte dépendant de marges, une contrainte dépendant d'une tolérance aux défaillances par routage secondaire, une contrainte dépendant d'un temps maximal d'interruption d'un trafic, une contrainte dépendant d'un temps d'accès réseau, etc.

La Fig. 4 correspond à l'étape 137 illustrée dans la Fig. 2 et donne un exemple d'optimisation de l'ensemble de trafics autorisés. L'optimisation débute par une étape 13701 au cours de laquelle des caractéristiques du réseau sont obtenues par le nœud maître, notamment le nombre de nœuds dans le réseau, la bande passante et la latence de liens du réseau. De plus lors de cette étape, le nœud maître obtient l'ensemble des demandes de transmission comprenant les demandes acceptées correspondant à des transmissions actives en cours et les demandes en attente non acceptées.

L'optimisation se poursuit par une définition des contraintes à respecter lors de l'optimisation au cours d'une étape 13703. Dans le cas de trafics de niveaux de criticité égaux, seules les contraintes Cl, C2 et C3 sont à respecter. Dans le cas de niveaux de criticité inégaux, la contrainte C4 est à ajouter.

Lors d'une étape 13705, le sous-ensemble de trafics optimal V _opt associé aux demandes de transmission acceptées est initialisé à l'ensemble vide. Cette étape est suivie, lors d'une étape 13707, par la construction de la fonction de coût F _r* décrite ci- dessus et, lors d'une étape 13709, par l'initialisation d'une variable x à la valeur « 1 ». La variable x est utilisée pour rechercher le cardinal du sous-ensemble ïï ^* optimal. En prenant x=l, on suppose que, suite à l'algorithme de la Fig. 2, le nœud maître a pu déduire que toutes les demandes de transmission ne peuvent être honorées, et qu'au moins une demande de transmission doit être refusée. On peut remarquer que si l'optimisation avait été lancée sans passer par la procédure de détermination des demandes de transmission à autoriser simplifiée des étapes 134, 135, 136 et 138, la variable x aurait débuté à 0 pour vérifier si toutes les transmissions (en cours ou en attente) peuvent être acceptées.

Lors d'une étape 13711, le nœud maître calcule le cardinal du sous-ensemble de trafics 7 ^* dans cette itération (card(7 ^* )=card(3)-x), puis le nœud maître vérifie que ce nouveau cardinal est bien au moins égal au cardinal d'un sous-ensemble de trafics 7 ^e correspondant à des demandes de transmission de niveau de criticité élevé devant impérativement être acceptées.

Si une valeur de cardinal du sous-ensemble de trafics 7 ^* inférieure au cardinal du sous-ensemble de trafics 7 ^e est obtenue, cela signifie qu'aucune solution compatible avec les contraintes n'a pu être trouvée. Dans ce cas, l'algorithme se termine par une étape 13733. Lors de l'étape 13733, une notification est envoyée à chaque nœud de manière à ce que chaque opérateur associé à l'un des nœuds soit informé de la situation pour, par exemple, alerter chaque opérateur que les communications sur le réseau risquent d'être dégradées. Dans un mode de réalisation, lors de l'étape 13733, le sous- ensemble des trafics autorisés est le sous-ensemble de trafics 7° . Si le cardinal du sous-ensemble de trafic T ^* est supérieur ou égal au cardinal du sous-ensemble ïï° , une variable n _v , est initialisée à la valeur « 0 ». Cette variable est utilisée pour parcourir l'ensemble des sous-ensembles de trafics T ^* de taille card( ^* ) possibles de l'ensemble de trafics .

L'optimisation se poursuit par l'initialisation d'une variable Min à une valeur

MIN. Le nœud maître prend une valeur MIN suffisamment grande pour assurer que toute valeur de la variable Min calculée dans l'algorithme soit inférieure à la valeur MIN. Nous proposons à titre d'exemple, une valeur MIN calculée à partir de la formule de calcul du coût ^ _* en fixant δ[ à la valeur « 1 ». On ajoute la valeur « 1 » au résultat de ce calcul pour assurer qu'aucun coût F _r* ne pourra atteindre cette valeur. :

Lors d'une étape 13719, le nœud maître vérifie si tous les sous-ensembles de trafics df* de taille card(7* ) de l'ensemble de trafic ont été pris en compte. Le nombre total de sous-ensembles de trafics possibles 7* de l'ensemble de trafics Test donné par le coefficient binomial C™^ .

Si des sous-ensembles de trafics restent à prendre en compte, la valeur du coût du sous-ensemble de trafic df* courant est calculée et comparée à la variable Min lors d'une étape 13721. Si le coût F _r* du sous-ensemble de trafic ^* courant est inférieur à la valeur de la variable Min, cette étape est suivie d'une étape 13722 au cours de laquelle la compatibilité du sous-ensemble de trafic 7* considéré avec l' ensemble des contraintes est vérifiée. Si c'est le cas, la variable Min prend la valeur courante de la fonction de coût _* lors d'une étape 13723 et le sous-ensemble de trafics optimal V _opt prend la valeur du sous-ensemble de trafics 7* lors d'une étape 13725. Dans tous les cas, les étapes 13721 et 13722 sont suivies d'une étape 13727 qui permet d'incrémenter la variable n _v* d'une unité.

Si tous les sous-ensembles de trafics 7* de l'ensemble de trafics ont été parcourus sans trouver au moins un sous-ensemble compatible avec les contraintes, lors d'une étape 13728, le nœud maître diminue le cardinal du sous-ensemble de trafics 7* en augmentant la variable x d'une unité lors d'une étape 13731 puis en revenant à l'étape 1371 1. Par contre si au moins une solution a été trouvée, l'algorithme se termine lors d'une étape 13729 et le sous-ensemble de trafics optimal V _t calculé lors de l'étape 13725 est conservé. Ce sous-ensemble indique l'ensemble des demandes de transmission à accepter.

Dans une mise en œuvre particulière de l'optimisation de l'ensemble des transmissions autorisées de la Fig. 4, une contrainte supplémentaire peut être ajoutée dans l'étape 13722. L'objectif de cette contrainte supplémentaire est de minimiser les perturbations induites par un changement dans le réseau. Pour ce faire, le nœud maître tente de préserver les demandes de transmission actives en cours. Ainsi, si les conditions sur le réseau le permettent, les transmissions en cours peuvent se poursuivre jusqu'à leur terme. Pour ce faire, une mise en œuvre particulière de l'algorithme de la Fig. 4 consiste à allouer un niveau de criticité élevé aux demandes de transmission actives. Ainsi, le nœud maître fixe le niveau de criticité p des demandes de transmission actives en cours de la manière suivante :

Ρ _λ < ρ < Ρ ₂

où P _x est le niveau de criticité maximum parmi les demandes de transmission ne devant pas impérativement être honorées, et P ₂ est le niveau de criticité minimum des demandes de transmission devant impérativement être honorées.

On peut noter qu'une version sous-optimale de l'optimisation sous contrainte décrite en relation avec la Fig. 4 peut être utilisée. Dans cette solution, l'optimisation de l'ensemble des trafics autorisés de la Fig. 4 peut être arrêtée à tout moment par le nœud maître dès qu'au moins un sous-ensemble de trafics 7 ^* compatible avec les contraintes est trouvé. Cet arrêt peut être provoqué par un utilisateur ou suite à l'expiration d'un temps prédéfini d'exécution maximum de la procédure d'optimisation sous contrainte. Cette solution a donc l'avantage de réduire le coût calculatoire de l'optimisation par rapport à une optimisation complète. La solution obtenue au moment de l'arrêt de l'optimisation maximise la quantité de transmissions actives sur le réseau à un instant donné, mais n'est pas nécessairement la solution minimisant la fonction de

Dans un mode de réalisation, on considère qu'aucun protocole de routage n'a permis d'associer chaque trafic à un chemin de transmission. Dans ce mode de réalisation, le nœud maître optimise conjointement la quantité de transmissions actives et les chemins de transmission utilisés par le trafic associé à chaque transmission. Dans un mode de réalisation, l'étape 13721 est modifiée. Lors de l'étape 13721 modifié, une optimisation est mise en œuvre de manière à associer chaque trafic compris dans le sous ensemble de trafics ^* à un chemin de transmission minimisant une fonction de coût, parmi les chemins de transmission possibles pour ce trafic. La fonction de coût F _v* est calculée une fois que chaque trafic du sous ensemble de trafics T ^* est associé à un chemin de transmission de coût minimal.

L'algorithme décrit en relation avec la Fig. 4 est quasiment exhaustif puisqu'il examine quasiment toutes les solutions possibles et ne s'arrête que lorsqu'une solution compatible avec les contraintes est trouvée ou lorsqu' aucune autre solution que le sous ensemble 7° n'est trouvée. Cet algorithme quasi-exhaustif est envisageable tant que le nombre de transmissions envisagé est faible. Lorsque le nombre de demandes de transmission est élevé ou lorsque l'optimisation concerne l'optimisation conjointe de la quantité de transmissions actives et des chemins de transmission empruntés par le trafic associé à chaque transmission, cet algorithme peut avoir un coût calculatoire important. Dans un mode de réalisation, l'algorithme décrit en relation avec la Fig. 4 est remplacé avantageusement par un algorithme par séparation et évaluation également appelé selon le terme anglophone « branch and bound ». L'algorithme par séparation et évaluation est une approche générique de résolution de problèmes d'optimisation, et plus particulièrement d'optimisation discrète. Une particularité de cette approche est qu'elle évite d'analyser exhaustivement toutes les solutions possibles à un problème, tout en permettant de trouver une solution optimale.

De retour à la Fig. 1, l'étape 15 de mise à jour des transmissions est décrite en détail en relation avec la Fig. 5. La Fig. 5 reprend la Fig. 2 et conserve les étapes 133 à 138. Toutefois, les étapes 131 et 132 sont remplacées par une étape unique 151 de mise à jour de la liste des demandes de transmission. Lors de cette étape, la liste des demandes de transmission en attente reste inchangée. Par contre, la (ou les) transmission(s) qui a (ont) pris fin est (sont) retirée(s) de la liste des transmissions actives. La suite de l'algorithme de la Fig. 5 est en tout point identique à la suite de l'algorithme de la Fig. 2.

La Fig. 6 représente les modifications apportées à l'algorithme de la Fig. 2 pour gérer les modifications de liens existants correspondant à l'étape 17 de la Fig. 1. Les étapes 131 et 132 sont remplacées par une étape 171 d'obtention de la liste combinée des transmissions actives et des demandes de transmission en attente. La suite de l'algorithme est en tout point identique à l'algorithme de la Fig. 2. Les modifications de liens apparaissent lors de l'étape 13701 de la Fig. 4 sous forme de modifications des caractéristiques de certains liens, voire de modifications de la liste X des liens disponibles sur le réseau. Dans ce dernier cas, par exemple, certains nœuds du réseau sont hors de portée des autres nœuds du réseau. Dans ce cas, les liens menant à ces nœuds peuvent être supprimés de la liste∑. Dans une autre mise en œuvre, le nœud maître pourra donner à ces liens des caractéristiques particulières comme une bande passante BP _k nulle et une latence LAT _k infinie. Cette mise en œuvre permet de gérer plus facilement les nœuds qui sont temporairement hors de portée des autres nœuds du réseau. En effet, dans ce cas, les liens menant à ces nœuds apparaissent toujours dans la liste X des liens existants. Toutefois, lorsque des nœuds sont hors de portée, les caractéristiques des liens qui leurs sont associés sont telles que ces liens ne sont jamais sélectionnés pour réaliser une transmission.

On notera que l'étape 17 de vérification de la compatibilité des transmissions existantes avec les nouvelles caractéristiques du réseau ne peut pas appliquer la procédure de détermination des demandes de transmission à autoriser simplifiée des étapes 134, 135, 136 et 138 de la Fig. 2. En effet, dans ce cas, la topologie du réseau a changé. Or, l'application des étapes 134, 135, 136 et 138 n'est possible que lorsque la topologie est stable. Au moins une partie des chemins de transmission est donc à revoir. Dans ce cas, l'étape 171 est suivie directement par l'étape 137 d'optimisation sous contrainte.

L'apparition d'un ou plusieurs nouveaux nœuds dans le réseau correspondant à l'étape 19 de la Fig. 1 est traitée par l'algorithme de la Fig. 6. La prise en compte des nouveaux liens apparaît lors de l'étape 13701 de la Fig. 4. Dans ce cas, les nouveaux liens sont ajoutés à la liste X des liens disponibles sur le réseau. Le reste de la mise en œuvre de l'étape 19 est en tout point identique à la mise en œuvre de l'étape 17.

La Fig. 7 illustre schématiquement un exemple d'architecture matérielle d'un dispositif 700 apte à mettre en œuvre un nœud du réseau et notamment le nœud maître selon la présente invention. Le dispositif 700 comporte alors, reliés par un bus de communication 710 : un processeur ou CPU (« Central Processing Unit » en anglais) 701 ; une mémoire vive RAM (« Random Access Memory » en anglais) 702 ; une mémoire morte ROM (« Read Only Memory » en anglais) 703 ; une unité de stockage 704 ou un lecteur de support de stockage, tel qu'un lecteur de cartes SD (« Secure Digital » en anglais) ou un disque dur HDD (« Hard Disk Drive » en anglais) ; un capteur optronique 706 capable d'acquérir des données de type image, vidéo, audio ou d'autres informations et un ensemble d'interfaces 705 permettant de recevoir des données issues d'un ou plusieurs autres nœuds et de fournir des données issues du capteur optronique à d'autres nœuds, par exemple par le biais d'un réseau de communication tel que le réseau Ad-Hoc mobile décrit en relation avec la Fig. 8.

Le processeur 701 est capable d'exécuter des instructions chargées dans la RAM 702 à partir de la ROM 703, d'une mémoire externe (non représentée), d'un support de stockage, ou d'un réseau de communication (non représenté). Lorsque le dispositif 700 est mis sous tension, le processeur 701 est capable de lire de la RAM 702 des instructions et de les exécuter. Ces instructions forment un programme d'ordinateur causant la mise en œuvre, par le processeur 701, de tout ou partie des algorithmes et étapes décrits ci-dessus.

Tout ou partie des algorithmes et étapes décrits ci-dessus peut ainsi être implémenté sous forme logicielle par exécution d'un ensemble d'instructions par une machine programmable, tel qu'un DSP (« Digital Signal Processor » en anglais) ou un micro contrôleur, ou être implémenté sous forme matérielle par une machine ou un composant dédié, tel qu'un FPGA (« Field-Programmable Gâte Array » en anglais) ou un ASIC (« Application-Specifîc Integrated Circuit » en anglais). Cela signifie que seule une partie desdits modules peut être mise en œuvre sous forme logicielle alors que le reste desdits modules peut être mis en œuvre sous forme matérielle.