Brevet FR3053550A1 — publié le 20180105

DOMAINE DE L'INVENTION L'invention se rapporte au domaine des réseaux de télécommunications, en particulier les réseaux sans fil (incluant notamment les réseaux ad hoc et les réseaux maillés). ETAT DE LA TECHNIQUE Un réseau sans fil comprend une pluralité de noeuds reliés entre eux par des liens de communication sans fil. Il est bien connu que des noeuds suffisamment proches les uns les autres dans un tel réseau sans fil peuvent conduire à des interférences empêchant une transmission correcte de flux de données. Pour réduire voire éliminer ces interférences dans un réseau, il a été proposé de router différents flux de données en utilisant un grand nombre de noeuds différents du réseau. Les différents flux de données passent par des chemins du réseau suffisamment éloignés les uns des autres pour ne pas créer d'interférences. Toutefois, une telle stratégie a pour inconvénient d'augmenter la consommation énergétique du réseau. En effet, un seul noeud actif consomme plusieurs watts, voire des centaines de watts, même s'il n'a pas de données à émettre ou à recevoir. L'utilisation conjointe d'un grand nombre de noeuds du réseau est donc très énergivore. EXPOSE DE L'INVENTION Un but de l'invention est de router des flux de données dans un réseau sans fil d'une manière qui permette de réduire la consommation énergétique globale du réseau sans fil. Il est dès lors proposé, selon un premier aspect de l'invention, un procédé de routage d'une pluralité de flux de données dans un réseau de communication sans fil comprenant une pluralité de noeuds reliés par des liens de communication sans fil, le procédé comprenant des étapes de : - identification d'au moins un groupe de liens de communication sans fil du réseau qui interféreraient tous les uns avec les autres s'ils étaient utilisés simultanément pour transmettre des données, - détermination, pour chaque flux de données, d'un chemin dans le réseau pour transmettre le flux de données, chaque chemin étant caractérisé par un ensemble de noeuds du réseau, la détermination comprenant une résolution d'un système 3053550 2 d'équations dont les chemins sont solutions, le système d'équations définissant les règles suivantes : o le nombre total de noeuds à inclure dans les chemins est à minimiser, o pour chaque groupe identifié, le taux d'utilisation en capacité du groupe, 5 par la pluralité de flux de données, doit être inférieur ou égal à un seuil prédéterminé, o chaque flux est à transmettre depuis un noeud source prédéterminé du réseau vers un noeud destinataire prédéterminé du réseau, o tout noeud n'étant pas destinataire et recevant un flux doit retransmettre ce 10 flux à un seul autre noeud, - désactivation d'au moins un noeud du réseau qui n'est pas compris dans au moins un des chemins déterminés. Les règles définies par le système d'équations permettent d'obtenir des chemins solutions qui ont des noeuds en commun. En d'autres termes, ces règles conduisent à une 15 agrégation des différents flux de données à transmettre sur des noeuds communs. Ainsi, un grand nombre de noeuds du réseau ne font pas partie des chemins déterminés suite à la résolution du système d'équations définissant ces règles. En désactivant ces noeuds en grand nombre, la consommation énergétique consommée par le réseau pour router la pluralité de flux de données est considérablement réduite. 20 Le procédé peut être complété avec l'aide des caractéristiques optionnelles suivantes, prises seules ou en combinaison lorsque cela est techniquement possible : - le système d'équations définit en outre des règles indicatives qu'un codage réseau est à utiliser pour transmettre les flux de données. - Le procédé comprend une étape de configuration d'au moins un noeud du réseau en 25 lequel deux chemins déterminés se croisent, de sorte que le noeud mette en oeuvre un codage réseau des données transitant par les chemins qui se croisent. - la résolution du système d'équations est mise en oeuvre par un programme linéaire en nombre entier. - un groupe de liens est une clique d'un graphe de conflits comprenant des sommets 30 représentants les liens de communication sans fil du réseau, et des arêtes reliant des sommets, dans lequel une arête représente des interférences entre les liens de communication sans fil représentés par les sommets que l'arête relie. - la résolution du système d'équations produit, pour chaque lien de communication sans fil et pour chaque flux de donnée, un booléen indiquant si le lien de 3053550 3 communication sans fil est à utiliser pour transmettre ou non le flux de données, chaque chemin étant identifié par une pluralité de tels booléens. - le taux d'utilisation en débit d'un groupe est la somme des taux d'utilisation en capacité des liens du groupe par la pluralité de flux de données, le taux d'utilisation 5 en capacité d'un lien étant un rapport entre une capacité consommée sur le lien pour transférer la pluralité de données et une capacité à vide du lien. - le seuil prédéterminé est égal à 1. Il est également proposé, selon un deuxième aspect de l'invention, un produit programme d'ordinateur comprenant des instructions de code de programme pour 10 l'exécution des étapes du procédé qui précède, lorsque ce programme est exécuté par au moins un processeur. Il est en outre proposé, selon un troisième aspect de l'invention, un dispositif de routage d'une pluralité de flux de données dans un réseau de communication sans fil comprenant une pluralité de noeuds reliés par des liens de communication sans fil, le 15 dispositif comprenant : - au moins un processeur configuré pour : o déterminer au moins un groupe de liens de communication sans fil du réseau qui interféreraient tous les uns avec les autres si les liens du groupe étaient utilisés simultanément pour transmettre des données, 20 o déterminer, pour chaque flux de données, un chemin dans le réseau pour transmettre le flux de données, chaque chemin étant caractérisé par un ensemble de noeuds du réseau, la détermination comprenant une résolution d'un système d'équations dont les chemins sont solutions, le système d'équations définissant les règles suivantes : 25 ^ le nombre total de noeuds à inclure dans les chemins est à minimiser, ^ pour chaque groupe identifié, le taux d'utilisation en capacité du groupe, par la pluralité de flux de données, est inférieur ou égal à un seuil prédéterminé, ^ chaque flux est à transmettre depuis un noeud source prédéterminé 30 du réseau vers un noeud destinataire prédéterminé du réseau, ^ tout noeud n'étant pas destinataire et recevant un flux retransmet ce flux à un seul autre noeud, - une interface de commande configurée pour commander la désactivation d'au moins un noeud du réseau qui n'est pas compris dans au moins un des chemins déterminés. 35 3053550 4 Il est enfin proposé, selon un quatrième aspect de l'invention, un réseau de communication sans fil comprenant : - une pluralité de noeuds, - une pluralité de liens de communication sans fil entre des noeuds, 5 - au moins un processeur configure pour : o déterminer au moins un groupe de liens de communication sans fil du réseau qui interféreraient tous les uns avec les autres si les liens du groupe étaient utilisés simultanément pour transmettre des données, o déterminer, pour chaque flux de données, un chemin dans le réseau pour 10 transmettre le flux de données, chaque chemin étant caractérisé par un ensemble de noeuds du réseau, la détermination comprenant une résolution d'un système d'équations dont les chemins sont solutions, le système d'équations définissant les règles suivantes : ^ le nombre total de noeuds à inclure dans les chemins est à minimiser, 15 ^ pour chaque groupe identifié, le taux d'utilisation en capacité du groupe, par la pluralité de flux de données, est inférieur ou égal à un seuil prédéterminé, ^ chaque flux est à transmettre depuis un noeud source prédéterminé du réseau vers un noeud destinataire prédéterminé du réseau, 20 ^ tout noeud n'étant pas destinataire et recevant un flux retransmet ce flux à un seul autre noeud, - des moyens pour désactiver au moins un noeud du réseau qui n'est pas compris dans au moins un des chemins déterminés. 25 DESCRIPTION DES FIGURES D'autres caractéristiques, buts et avantages de l'invention ressortiront de la description qui suit, qui est purement illustrative et non limitative, et qui doit être lue en regard des dessins annexés sur lesquels : - La figure 1 représente schématiquement un réseau de communication sans fil et un 30 dispositif de routage selon un mode de réalisation de l'invention. - La figure 2 est un organigramme d'étapes d'un procédé de routage selon un mode de réalisation de l'invention. - La figure 3 illustre un routage de deux flux de données mis en oeuvre au moyen d'un procédé connu de l'état de la technique dans un réseau sans fil d'exemple. 3053550 5 - La figure 4 illustre un graphe de conflits associé au routage représenté sur la figure 3. - La figure 5 illustre un routage de deux flux de données mis en oeuvre au moyen d'un procédé selon un mode de réalisation de l'invention, dans le réseau sans fil 5 d'exemple représenté sur la figure 3. - La figure 6 illustre un graphe de conflits associé au routage représenté sur la figure 5. Sur l'ensemble des figures, les éléments similaires portent des références identiques. 10 DESCRIPTION DETAILLEE DE L'INVENTION Réseau sans fil et dispositif de routage En référence à la figure 1, un réseau de communication sans fil R comprend une pluralité de noeuds reliés par des liens de communication sans fil. Chaque noeud comprend des moyens pour recevoir des données et des moyens pour émettre des données dans une 15 zone de transmission prédéterminée. Le réseau est sujet à des interférences, dont on suppose le modèle connu. Par exemple, dans le cas d'un modèle d'interférence à deux sauts, un noeud donné du réseau interfère avec ses voisins et les voisins de ses voisins, si ces noeuds étaient utilisés simultanément pour transmettre des données. 20 Par - voisin », on désigne un noeud qui est relié directement au noeud donné par un lien de communication sans fil, sans que ce lien ne passe par d'autres noeuds. Le réseau peut être formellement représenté par un graphe G = (V,E), où V est l'ensemble des noeuds du réseau et E l'ensemble des liens de communication sans fil entre ces noeuds. Un lien (i,j) appartient à E si i et j appartiennent à V et si le noeud j est dans 25 la zone de transmission du noeud i. Les interférences entre les différents liens de communication sans fil du réseau peuvent être représentées par un deuxième graphe, conventionnellement appelé graphe de conflits. Le graphe de conflits comprend des sommets représentant les liens de communication sans fil du réseau, et des arêtes reliant des sommets. Une arête du graphe 30 de conflits représente des interférences entre les liens de communication sans fil représentés par les sommets que l'arête relie. Le réseau de communication sans fil comprend - ou est associé à - un dispositif de routage 1. Le dispositif de routage 1 est l'un des noeuds du réseau ou bien un équipement tiers. 3053550 6 Le dispositif de routage 1 comprend au moins un processeur 2, une interface de communication 4 avec les noeuds du réseau R, et une mémoire 6. Le processeur 2 est configuré pour exécuter un programme d'ordinateur, lequel est configuré pour résoudre un système d'équations, c'est-à-dire produire une solution de ce 5 système d'équations. Le programme d'ordinateur comprend un programme linéaire en nombre entier. Un tel programme linéaire en nombre entier traite des équations linéaires et consomme de la sorte des ressources du processeur 2 et de la mémoire 4 en quantité raisonnable. Le dispositif de routage 1 peut en outre être adapté pour contrôler à distance 10 l'activation et la désactivation des noeuds du réseau de communication sans fil. Ce contrôle peut typiquement être assuré par le programme d'ordinateur, exécuté par le processeur 1, avec le concours de l'interface de communication 4 du dispositif, comme il sera détaillé ci-après. Alternativement, les noeuds sont configurés pour détecter qu'ils n'ont pas de données 15 à transmettre, par exemple au terme d'un délai prédéterminé. Lorsqu'un noeud détecte qu'il n'a pas reçu de données à transmettre dans ce délai, il peut se désactiver tout seul. Procédé de routage de flux de données dans un réseau sans fil Il est considéré dans un premier temps que tous les noeuds du réseau sont actifs. 20 Le dispositif de routage 1 reçoit via son interface de communication 4 des données indiquant qu'une pluralité de flux de données est à transmettre dans le réseau R. Il est en outre supposé que le noeud source d'où provient chaque flux de données est prédéterminé, de même que le noeud destinataire vers où transmettre chaque flux (les noeuds sources des différents flux étant potentiellement différents, de même que les 25 noeuds destinataires). A ce stade, les chemins via lesquels transmettre les flux de données dans le réseau sont inconnus. En référence à la figure 2, un procédé de routage mis en oeuvre par le dispositif de routage 1 - plus spécifiquement par le programme exécuté par le processeur 2 - comprend 30 les étapes suivantes. Dans une première étape 101, le processeur 2 identifie les groupes de liens de communication sans fil du réseau interférant tous les uns avec les autres lorsque les liens du groupe sont utilisés simultanément pour transmettre des données. Chaque groupe identifié est une clique du graphe de conflits du réseau R. De façon 35 connue en elle-même, une clique d'un graphe est un sous-ensemble de sommets de ce 3053550 7 graphe tous reliés les uns avec les autres, le sous-ensemble étant de taille maximale en nombre de sommets qu'il contient. Dans une deuxième étape 102, le programme linéaire en nombre entier exécuté par le processeur 2 détermine une pluralité de chemins pour transférer les flux de données dans 5 le réseau (un chemin par flux). Chaque chemin est caractérisé par un ensemble de noeuds et un ensemble de liens de communications sans fil. La détermination des chemins mise en oeuvre par le programme linéaire en nombre entier comprend une résolution d'un système d'équations dont les chemins sont solutions. 10 Les données produites par le programme linéaire en nombre entier sont les suivantes : - Pour chaque noeud i du réseau, un booléen x, représentant l'état du noeud i (égal à 1 si le noeud est utilisé, c'est-à-dire s'il fait partie d'au moins un des chemins, 0 sinon). L'ensemble des booléens x, égaux à 1 représentent donc la partie du réseau qui sera sollicitée pour la transmission de la pluralité de flux de données. 15 - Pour chaque lien de communication (i,j) sans fil du réseau, un booléen xf,,j représentant l'utilisation du lien (i, j) pour le flux f (égal à 1 si le lien (i, j) est utilisé pour acheminer le flux f, 0 sinon). Le chemin pour transmettre le flux f peut donc être identifié par l'ensemble des booléens xf,,j égaux à 1. Le programme linéaire en nombre entier est configure avec la fonction objectif 20 suivante : Min II IEV Les données qui précèdent sont solutions d'un système d'équations résolues par le programme linéaire en nombre entier, les équations formant des contraintes associées à la fonction objectif. Ces équations sont par exemple préalablement mémorisées sous forme de code ou de données dans une mémoire du dispositif, et lues par le programme linéaire 25 en nombre entier en vue de leur résolution. Le système d'équations comprend les équations suivantes : (1) Egnec 1, vc E C (2) Lev X if Ekev X fk = 0, Vf E F,Vj E V -15f,Dfl 30 (3) EgsME xf:sf = 0, Vf E F (4) E(sf,0EE Vf E F (5) E(Df,i)EE )(1)fi = o, Vf E F (6) E(i,pf),E xfpf = 1, Vf E F 3053550 8 (7) EfeFx[,i - mi- = dij, V(i,j) E E (8) E(0),Exfi Vf E F, Vi E V - PT} fO si clij = c111= 0,V(i, j),U, i) E E (9) vi E V, x = ( 1 sinon 5 Dans ces équations, les notations suivantes sont utilisées : - F : ensemble des flux de données à transmettre ; - C : ensemble des cliques identifiées ; - d,j : capacité (par exemple en bit/s) réservé sur le lien (i, j) pour la transmission de la pluralité F de flux ; 10 - Cij : capacité à vide (par exemple en bit/s) du lien (i, j) ; - Sf : noeud source du flux f ; - Df : noeud destinataire du flux f ; - Mf : débit requis pour la transmission du flux f. L'équation (1) du système concerne les taux d'utilisation en capacité de chaque 15 clique. Cette équation (1) pose comme règle que ce taux d'utilisation ne doit pas dépasser 100% (ce taux peut être ajusté en fonction du type d'interférences). Dans l'équation (1) le taux d'utilisation en capacité d'un groupe (une clique) est la somme des taux d'utilisation en capacité des liens du groupe par la pluralité de flux de données, le taux d'utilisation en capacité d'un lien étant un rapport entre une capacité 20 consommée sur le lien pour transférer la pluralité de données et un débit à vide du lien. Les équations (2) à (6) sont représentatives d'un principe de conservation des flux de données dans le réseau : tout noeud recevant un flux doit, s'il n'en est pas le destinataire, le retransmettre à l'un de ses voisins (2), un flux ne peut revenir à sa source ou quitter sa destination (3 et 5), une source doit transmettre son flux à l'un de ses voisins 25 et une destination doit recevoir un flux de l'un de ses voisins (équations 4 et 6). L'équation (7) est représentative d'une agrégation possible de plusieurs des flux de données à transmettre le cas échéant via un même lien de communication sans fil : la capacité réservée sur un lien est égale à la somme des débits demandés par chacun des flux sur ce lien. 30 L'équation (8) pose comme règle qu'il doit être évité qu'un flux puisse suivre plusieurs chemins. L'équation (9) est une condition déterminant si un noeud est utilisé, c'est-à-dire s'il reçoit et/ou émet du trafic sur l'un de ses liens de communication. 3053550 9 La résolution des équations (1) à (9) permet d'obtenir des chemins solutions agrégés. Néanmoins, il se peut que la mise en oeuvre de ces seules équations (1) à (9) conduise à l'obtention de chemins solutions inadaptés pour respecter les débits de 5 transmission des flux de données, donc à une dégradation de la qualité des applications déployées sur le réseau (flux audio ou vidéo par exemple). L'utilisation conjointe du codage réseau est alors avantageuse pour minimiser le nombre de noeuds utilisés tout en maintenant un niveau de service requis. Dès lors, le système d'équations comprend avantageusement des équations 10 supplémentaires formant des règles indicatives qu'un codage réseau est à utiliser pour transmettre les flux de données. Ces équations supplémentaires sont les suivantes : (10) (EfeFinii, k) -wiik = 0, V(i,j),(j,k) E E (11) (Eu,k)EElnli, k) - x Mf = 0, V(i,j) E E, Vf E F 15 (12) (E(imeE k) - xfkMf = 0, v(j, k) E E, Vf E F où infik est le débit consommé par le flux f sur le lien de communication (i, j) lorsque k est le prochain noeud visité par le flux f et w,jk est le débit global consommé par la pluralité F de flux sur le lien (i, j) lorsque k est le prochain noeud visité par le ou les flux qui sont 20 passé par le lien (i,j). Il est à noter que ces équations supplémentaires entrent en synergie avec les équations précédentes (1) à (9) : en effet, au-delà des avantages associés à la mise en oeuvre d'un codage réseau dans le réseau, ces équations permettent l'obtention de chemins encore mieux agrégés. 25 Dans une troisième étape 103, le programme exécuté par le processeur 2 peut commander la désactivation d'au moins un noeud du réseau qui ne font partie d'aucun des chemins qui ont été déterminés à l'issue de la deuxième étape, via l'interface de communication 4. Cette désactivation peut par exemple comprendre l'envoi d'un message de 30 désactivation à chaque noeud concerné via l'interface de communication 4 du dispositif de routage.La désactivation d'un noeud peut être une mise en veille ou l'extinction de ce noeud. Un noeud en veille ou éteint ne consomme au plus que quelques milliwatts, ce qui constitue en soi une première économie d'énergie. Par ailleurs, un tel noeud n'envoie plus d'information (notamment de signalisation) et n'interfère plus avec son voisinage, 35 augmentant encore cette économie d'énergie. 3053550 10 Dans une quatrième étape 104, le dispositif de routage 4 configure les noeuds du réseau de sorte que les flux de données puissent être transmis dans le réseau via les chemins précédemment déterminés. Cette configuration peut typiquement comprendre l'envoi par le dispositif 1 via l'interface de communication 4 aux différents noeuds laissés 5 actifs du réseau des règles de routage indiquant à chaque noeud à quel autre voisin (et donc sur quel lien) transmettre des données d'un flux de données qu'il reçoit. Dans une cinquième étape 105, les flux de données f sont transmis dans le réseau via les chemins déterminés précédemment. Pour mieux mettre en évidence les avantages du procédé de routage ainsi mis en 10 oeuvre, prenons l'exemple du réseau de communication sans fil illustré en figure 3 comprenant dix noeuds dans lequel deux flux sont à transmettre en même temps, du noeud 1 au noeud 5 et du noeud 10 au noeud 6, respectivement. La mise en oeuvre d'un procédé de routage recherchant des plus courts chemins en nombre de sauts conduit à la détermination des chemins (a) et (b) représentés par deux 15 flèches. Les liens de communication sans fil faisant partie des deux chemins déterminés sont les suivants : [(1 -> 2), (2 -> 3), (3 -> 4), (4 -> 5)1 et [(10 -> 9), (9 -> 8), (8 -> 7), (7 -> 6)1. On suppose que le modèle d'interférence de ce réseau est à deux sauts (un noeud interfère avec ses voisins et leurs voisins). Le graphe de conflits associé au routage mis en 20 oeuvre sur la figure 3 est celui représenté sur la figure 4. Ce graphe de conflits comprend cinq cliques C1 à C5, comprenant les liens de communication sans fil suivants : 25 Sous l'hypothèse que les liens de communication sans fil ont chacun une capacité totale de 100 unités et que les flux de données requièrent chacun un débit de 20 unités, les 30 taux d'utilisation des cliques au sens de l'équation (1) seraient tous de 100% : 35 - C1 = [(1 -> 2), (2 -> 3), (3 -> 4), (4 -> 5), (8 -> 7)1 - C2 = [(7 -> 6), (8 -> 7), (9 -> 8), (10 -> 9), (3 -> 4)1 - C3 = [(3 -> 4), (4 -> 5), (8 -> 7), (9 -> 8), (10 -> 9)1 - Ca = [(2 -> 3), (3 -> 4), (4 -> 5), (8 -> 7), (9 -> 8)1 - C5 = [ (1 -> 2), (2 -> 3), (3 -> 4), (8 -> 7), (7 -> 6)1 - C1 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 100% - C2 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 100% - C3 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 100% - C4 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 100% - C5 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 100% 3053550 11 Dans ce cas, les débits requis pour transmettre les deux flux peuvent être respectés ; les flux pourraient être acheminés via les plus courts chemins en nombre de sauts sans dégradation de débit. Cependant, tous les noeuds sont actifs, consommant ainsi beaucoup d'énergie. 5 En appliquant le procédé de l'invention à ce même réseau, les chemins déterminés sont ceux représentés sur la figure 5. Ces deux chemins ne sollicitent pas les noeuds 7, 8 et 9 (qui sont dès lors mis en veille ou éteints). Les liens de communication sans fil compris dans les chemins déterminés sont les suivants : [(1 -> 2), (2 -> 3), (3 -> 4), (4 -> 5)1 10 et [(10 -> 5), (5 -> 4), (4 -> 3), (3 -> 2), (2 -> 1), (1 -> 6)1. La consommation d'énergie du réseau lorsque ce routage est mis en oeuvre est donc réduite comparativement au routage selon la figure 3. La détermination des chemins qui précèdent et la désactivation des noeuds non utilisés pour l'acheminement des flux de données conduit au graphe de conflits représenté 15 en figure 6. Les cliques de ce graphe de conflits différent sont alors les suivantes : - C1 = [(1 -> 2), (2 -> 3), (3 -> 4), (4 -> 5), (3 -> 2), (4 -> 3), (2 -> 1)1 - C2 = [(2 -> 1), (3 -> 2), (4 -> 3), (5 -> 4), (2 -> 3), (3 -> 4), (4 -> 5)1 - C3 = [ ( 1 -> 6), (2 -> 1), (3 -> 2), (4 -> 3), (1 -> 2), (2 -> 3), (3 -> 4)1 - C4 = [ (1 0 -> 5), (3 -> 4), (4 -> 5), (3 -> 2), (4 -> 3), (5 -> 4)1 20 Si l'équation (1) et les équations supplémentaires (10) à (12) n'étaient pas prises en compte au cours de la détermination des chemins, les taux d'utilisation des cliques seraient: - C1 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 140% - C2 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 140% 25 - C3 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 140% - C4 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 = 120% Le réseau est alors saturé. L'équation (1) doit donc être prise en compte pour ne pas saturer le réseau, mais pour la respecter dans l'exemple considéré, les débits de transmission des flux ne devraient 30 pas dépasser 14,28 afin de ne pas surcharger les cliques : - C1 : 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 +14,28/100 = 99,96 (~100 %) - C2 : 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 +14,28/100 = 99,96 (~100 %) 35 - C3 : 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 3053550 12 +14,28/100 = 99,96 (~100 %) - C4 : 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 + 14,28/100 +14,28/100 = 85,68% La consommation énergétique est donc réduite, mais au détriment de la qualité des 5 applications déployées. En associant l'agrégation et le codage réseau, c'est-à-dire en prenant en compte toutes les équations définies ci-dessus (non seulement les équations (1) à (9) mais également les équations (10) à (12)), les noeuds 2, 3 et 4 peuvent réduire leur nombre de transmissions en combinant les données reçues sur leurs différents liens en entrée. 10 En effet, le codage réseau fonctionne de la manière suivante dans l'exemple représenté sur la figure 5. Le noeud 1 envoie des premières données (appartenant à un premier flux) au noeud 2, et les mémorise temporairement. Le noeud 3 envoie des deuxièmes données (appartenant à un deuxième flux) au noeud 15 2, et les mémorise temporairement. Le noeud 2 reçoit du noeud 1 les premières données du premier flux, et reçoit également du noeud 3 des deuxièmes données du deuxième flux. Le noeud 2 combine les premières données et les deuxièmes données. Cette combinaison et par exemple une somme bit à bit au moyen de l'opérateur XOR ; d'autres 20 combinaisons sont cependant envisageables. Le noeud 2 transmet cette combinaison à chacun des noeuds 1 et 3. Comme le réseau est un réseau fil, le noeud ne met en oeuvre en réalité qu'une seule transmission pluridirectionnelle des données, ces données pouvant être captées par les noeuds voisins 1 et 3 qui sont à portée. 25 Le noeud 1 recevant la combinaison calculée, peut retrouver la valeur des deuxièmes données en combinant la combinaison reçue avec les premières qu'il avait mémorisée. Dans le cas de la somme avec opérateur XOR, le noeud 1 peut retrouver les deuxièmes données en effectuant à son tour une somme XOR bit à bit de la combinaison reçue avec les premières données qu'il avait mémorisées. 30 Similairement, le noeud 3 recevant la combinaison calculée, peut retrouver la valeur des premières données en combinant la combinaison reçue avec les deuxièmes qu'il avait mémorisées. Le même codage réseau est également mis en oeuvre par les noeuds 3 et 4. 3053550 13 On comprend ainsi que le codage réseau permet de réduire le nombre de transmission à effectuer pour transmettre le même volume de données dans le réseau sans fil, augmentant ainsi les débits. Dans ces conditions, pour reprendre l'exemple qui précède, dans lequel il était 5 considéré que les flux devaient être transmis avec un débit de 20 unités, les taux d'utilisation des cliques avec mise en oeuvre du codage réseau deviennent: - C1 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 - (20/100 + 20/100)* = 100 % - C2 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 10 - (20/100 + 20/100)* = 100 % - C3 : 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 - (20/100 + 20/100)* = 100 % - C4 20/100 + 20/100 + 20/100 + 20/100 + 20/100 + 20/100 - (20/100)* = 100 % 15 Dans les calculs numériques d'exemple exposés ci-dessus, les termes présentant un astérisque (*) représentent la capacité récupérée grâce au codage réseau limitant le nombre de transmissions. En conclusion, la prise en compte du codage réseau dans les équations résolues par le programme linéaire en nombre entier permet ainsi la désactivation de 30% des noeuds, 20 tout en garantissant les débits requis par les flux et en respectant la capacité du réseau. Comme indiqué précédemment, le dispositif de routage peut tout à fait être lui-même un noeud du réseau. Il peut par exemple être prévu que chaque noeud du réseau met en oeuvre le procédé de routage, et se désactive lui-même s'il arrive à la conclusion qu'il ne fait lui-même pas 25 partie d'un des chemins qu'il a déterminés. Un noeud peut également désactiver d'autres noeuds du réseau. REVENDICATIONS1. Procédé de routage d'une pluralité de flux de données dans un réseau de communication sans fil (R) comprenant une pluralité de noeuds reliés par des liens de communication sans fil, le procédé comprenant des étapes de : - identification (101) d'au moins un groupe de liens de communication sans fil du réseau qui interféreraient tous les uns avec les autres s'ils étaient utilisés simultanément pour transmettre des données, - détermination (102), pour chaque flux de données, d'un chemin dans le réseau pour transmettre le flux de données, chaque chemin étant caractérisé par un ensemble de noeuds du réseau, la détermination comprenant une résolution d'un système d'équations dont les chemins sont solutions, le système d'équations définissant les règles suivantes : o le nombre total de noeuds à inclure dans les chemins est à minimiser, o pour chaque groupe identifié, le taux d'utilisation en capacité du groupe, par la pluralité de flux de données, doit être inférieur ou égal à un seuil prédéterminé, o chaque flux est à transmettre depuis un noeud source prédéterminé du réseau vers un noeud destinataire prédéterminé du réseau, o tout noeud n'étant pas destinataire et recevant un flux doit retransmettre ce flux à un seul autre noeud, - désactivation (103) d'au moins un noeud du réseau qui n'est pas compris dans au moins un des chemins déterminés. 2. Procédé selon la revendication précédente, dans lequel le système d'équations définit en outre des règles indicatives qu'un codage réseau est à utiliser pour transmettre les flux de données. 3. Procédé selon la revendication précédente, comprenant une étape de configuration (104) d'au moins un noeud du réseau en lequel deux chemins déterminés se croisent, de sorte que le noeud mette en oeuvre un codage réseau des données transitant par les chemins qui se croisent. 4. Procédé selon l'une des revendications précédentes, dans lequel la résolution du système d'équations est mise en oeuvre par un programme linéaire en nombre entier. 3053550 15 5. Procédé selon l'une des revendications précédentes, dans lequel un groupe de liens est une clique d'un graphe de conflits comprenant des sommets représentants les liens de communication sans fil du réseau, et des arêtes reliant des sommets, dans lequel une arête 5 représente des interférences entre les liens de communication sans fil représentés par les sommets que l'arête relie. 6. Procédé selon l'une des revendications précédentes, dans lequel la résolution du système d'équations produit, pour chaque lien de communication sans fil et pour chaque 10 flux de donnée, un booléen indiquant si le lien de communication sans fil est à utiliser pour transmettre ou non le flux de données, chaque chemin étant identifié par une pluralité de tels booléens. 7. Procédé selon l'une des revendications précédentes, dans lequel le taux d'utilisation en 15 débit d'un groupe est la somme des taux d'utilisation en capacité des liens du groupe par la pluralité de flux de données, le taux d'utilisation en capacité d'un lien étant un rapport entre une capacité consommée sur le lien pour transférer la pluralité de données et une capacité à vide du lien. 20 8. Procédé selon l'une des revendications précédentes, dans lequel le seuil prédéterminé est égal à 1. 9. Produit programme d'ordinateur comprenant des instructions de code de programme pour l'exécution des étapes du procédé selon l'une de revendications précédentes, lorsque 25 ce programme est exécuté par au moins un processeur. 10. Dispositif de routage (1) d'une pluralité de flux de données dans un réseau de communication sans fil comprenant une pluralité de noeuds reliés par des liens de communication sans fil, le dispositif comprenant : 30 - au moins un processeur (2) configure pour : o déterminer au moins un groupe de liens de communication sans fil du réseau qui interféreraient tous les uns avec les autres si les liens du groupe étaient utilisés simultanément pour transmettre des données, o déterminer, pour chaque flux de données, un chemin dans le réseau pour 35 transmettre le flux de données, chaque chemin étant caractérisé par un 3053550 16 ensemble de noeuds du réseau, la détermination comprenant une résolution d'un système d'équations dont les chemins sont solutions, le système d'équations définissant les règles suivantes : ^ le nombre total de noeuds à inclure dans les chemins est à minimiser, 5 ^ pour chaque groupe identifié, le taux d'utilisation en capacité du groupe, par la pluralité de flux de données, est inférieur ou égal à un seuil prédéterminé, ^ chaque flux est à transmettre depuis un noeud source prédéterminé du réseau vers un noeud destinataire prédéterminé du réseau, 10 ^ tout noeud n'étant pas destinataire et recevant un flux retransmet ce flux à un seul autre noeud, - une interface de commande (4) configurée pour commander la désactivation d'au moins un noeud du réseau qui n'est pas compris dans au moins un des chemins déterminés. 15 11. Réseau (R) de communication sans fil comprenant : - une pluralité de noeuds, - une pluralité de liens de communication sans fil entre des noeuds, - au moins un processeur (2) configuré pour : 20 o déterminer au moins un groupe de liens de communication sans fil du réseau qui interféreraient tous les uns avec les autres si les liens du groupe étaient utilisés simultanément pour transmettre des données, o déterminer, pour chaque flux de données, un chemin dans le réseau pour transmettre le flux de données, chaque chemin étant caractérisé par un 25 ensemble de noeuds du réseau, la détermination comprenant une résolution d'un système d'équations dont les chemins sont solutions, le système d'équations définissant les règles suivantes : ^ le nombre total de noeuds à inclure dans les chemins est à minimiser, ^ pour chaque groupe identifié, le taux d'utilisation en capacité du 30 groupe, par la pluralité de flux de données, est inférieur ou égal à un seuil prédéterminé, ^ chaque flux est à transmettre depuis un noeud source prédéterminé du réseau vers un noeud destinataire prédéterminé du réseau, ^ tout noeud n'étant pas destinataire et recevant un flux retransmet ce 35 flux à un seul autre noeud, 3053550 17 - des moyens (1, 4) pour désactiver au moins un noeud du réseau qui n'est pas compris dans au moins un des chemins déterminés.