Brevet FR2954028A1 — publié le 20110617

La présente invention concerne un procédé permettant de calculer un chemin avec une qualité de service déterminée dans un réseau multi sauts ainsi qu'un équipement de gestion de noeud de réseau. Elle a des applications dans le domaine de la gestion des échanges de données sur des réseaux de communication notamment pour des applications multimédia temps réel sur réseaux ad hoc sans fil, téléphonie sur réseaux ad hoc, vidéoconférence sur réseaux ad hoc. Elle permet une coexistence de ces applications avec d'autres applications classiques telles que la toile (le web), le transfert de fichiers, etc. Le routage consiste à trouver un chemin entre un noeud source et un noeud destination dans un réseau. Ce chemin sera emprunté par des paquets de données adressés à la destination. Un chemin est une suite de liens. Un lien est une connexion physique qui relie deux noeuds voisins du réseau. Une métrique sur un lien est une valeur associée à l'état du lien à un instant donné. Une métrique sur un chemin est une combinaison (addition, multiplication, minimum, ou toute autre fonction) des métriques sur chaque lien composant le chemin. Une application peut avoir besoin que les paquets qu'elle échange sur le réseau empruntent des chemins dont le niveau de qualité de service est suffisant. On entend par qualité de service un ensemble de valeurs mesurables caractérisant une liaison entre une source et une destination dans un réseau comme par exemple le délai d'acheminement, le débit maximal possible, le taux de perte des paquets, etc. Pour cela il est nécessaire de calculer des chemins qui offrent un niveau de qualité de service satisfaisant. Ainsi, lorsque des applications communiquent à travers le réseau, les paquets de données échangés empruntent des chemins qui offrent à ces applications le niveau de qualité de service requis pour leur fonctionnement. Classiquement, dans un réseau filaire, une métrique sur un lien est souvent indépendante de l'état d'autres liens ce qui la rend facile à estimer. En revanche, dans un réseau sans fil, l'état d'un lien est bien plus souvent dépendant de celui des autres liens. Ceci rend l'estimation de la métrique sur lien plus compliquée dans les réseaux sans fil. Une ou plusieurs métriques de manière générale sont utilisées dans le routage dit avec qualité de service, dans lequel il s'agit de trouver un chemin respectant la valeur requise par une application pour chacune de ces métriques. Les algorithmes de routage existants ignorent l'impact de l'utilisation d'un chemin sur ces métriques. En le traversant, un paquet modifie l'état d'un lien or cette modification n'est pas prévue dans le calcul initial du chemin dans les procédés classiques, ce qui peut conduire à un résultat insatisfaisant. En effet, les approches existantes de calcul de chemin avec qualité de service s'appuient sur la supposition qu'une métrique sur un lien n'est modifiée que par les paquets de données qui le traversent. L'expérience dans les réseaux sans fil montre que cette supposition est fausse dans la majorité des cas. La présente invention propose que l'estimation des métriques ne soit pas séparée du calcul du chemin lui-même, puisque les métriques d'un lien dépendent aussi des autres liens qui composent le chemin calculé. Ainsi, pour calculer des chemins qui offrent un niveau de qualité de service satisfaisant, on prend en compte l'interférence générée sur le chemin lui-même par les paquets l'empruntant. Grâce à la mise en oeuvre de l'invention, les chemins calculés répondent bien aux requis des applications qui les utilisent, puisque le niveau de qualité de service qu'ils offrent est suffisant. Par conséquent, les applications peuvent fonctionner correctement. Cette possibilité d'utiliser des chemins de qualité de service suffisante garantit que les communications entre les applications qui empruntent les chemins calculés n'utilisent pas plus de ressources que celles offertes par le réseau. Ainsi la saturation du réseau est évitée. Enfin, globalement, les ressources offertes par le réseau sont mieux partagées par les applications, ce qui rend la coexistence d'applications de différents requis possible. Ainsi, l'invention concerne un procédé de routage qualitatif de données dans un réseau de communication multi sauts ad hoc, ledit procédé permettant de déterminer en fonction d'un critère de qualité de communication déterminable au moins un chemin de passage des données par des liens entre des noeuds, entre un noeud source et un noeud destination dudit réseau, la valeur du critère de qualité d'un chemin donné étant calculable en fonction d'au moins une métrique de liens déterminable dans ledit réseau, les liens pouvant interférer entre eux lors du passage des données. Selon l'invention, dans la détermination du chemin on prend en compte l'interférence intra-flux et pour un critère de qualité de communication qui est une valeur minimale B de bande passante à satisfaire, on utilise un protocole de routage pour réseau ad hoc afin de déterminer la topologie globale du réseau et, étant donné un paramètre H > 1, on détermine les liens interférents de la manière suivante : - chaque noeud du réseau détermine un graphe global de conflit, défini de la manière suivante : chaque sommet de ce graphe global de conflit représentant un lien dans une topologie globale partielle et chaque arête de ce graphe global de conflit représentant une relation de conflit entre deux liens de la topologie globale partielle, c'est-à-dire que ces liens sont distants d'au plus H sauts d'après la topologie globale partielle ; - chaque noeud ayant un graphe global de conflit détermine les sous graphes complets maximaux, dits « cliques », du graphe global de conflit, et ledit noeud détermine le chemin de passage dans le réseau par résolution du système linéaire suivant avec les contraintes d'intégralité suivantes : Min. 1 (i, j)EE S.t. (s,j)DE (j,$)DE ^ Ixjt ^^1 (t,j)EE (j,t)EE xij^~xji^O ^1^{s,t} (i, j)EE (j,i)EE B (ù.xi1. ^ ) B ^1 ij (i,j)Ic ^ c ^ K xip{0,1 } ^ (i,j)^ E où K est l'ensemble des cliques du graphe global de conflit en considérant que s est un noeud source, t un noeud destination et i, j des indices de référence des noeuds du réseau, C1 la capacité de débit à vide du lien entre les noeuds i et j , B,1 la proportion de la capacité à vide qui est utilisée sur le lien entre les noeuds i et j pour les flux existants et la différence de B11 par rapport à 1 correspond donc à la proportion de flux libre utilisable restant par rapport à la capacité à vide sur ledit lien (i, j) , E étant l'ensemble des liens entre les noeuds. Dans divers modes de mise en oeuvre de l'invention, les moyens 10 suivants pouvant être utilisés seuls ou selon toutes les combinaisons techniquement possibles, sont employés : - dans l'étape de détermination de la topologie globale du réseau on détermine une topologie locale totale du réseau, - dans l'étape de détermination de la topologie globale du réseau on 15 détermine une topologie globale partielle du réseau, - dans l'étape de détermination de la topologie globale du réseau, cette dernière est déterminée de la manière suivante : - chaque noeud du réseau détermine une topologie locale totale du réseau comportant, d'une part, tous les noeuds correspondants à ses 20 voisins directs, dits "à un saut", et tous les voisins directs de ses voisins direct, alors dits "à deux sauts", et, d'autre part, tous les liens entre lui-même et ses voisins à un saut et entre ses voisins à un saut et leurs propres voisins à un saut; ladite topologie étant dite topologie locale totale à deux sauts, 25 - chaque noeud détermine un sous-ensemble de ses voisins, dits "MPR" qui lui permettent de joindre tous ses voisins à deux sauts et communique périodiquement à ses voisins à un saut la liste du/des voisins qui a/ont été déterminés comme MPR; - chaque noeud qui a été déterminé comme MPR par au moins un 30 voisin diffuse périodiquement dans le réseau la liste du/des voisins qui l'a/ont choisi comme MPR, ladite liste étant dite liste « MPR-S »; - par agrégation des listes MPR-S, chaque noeud reconstitue une topologie globale partielle du réseau comportant tous les noeuds et un ensemble de liens entre les noeuds permettant de trouver au moins un chemin vers chaque autre noeud du réseau, - le protocole de routage pour réseau ad hoc utilisé est OLSR, AODV, DSR TBRPF, ou FSR, les étapes de détermination de la topologie globale partielle du réseau et du graphe de conflit sont effectuées séparément au sein d'un noeud, le graphe de conflit étant déterminé après la détermination de la topologie globale partielle du réseau, - la capacité à vide de chaque lien adjacent à un noeud est déterminée par une méthode qui prend effectivement en compte les conflits existant entre les liens voisins, - la proportion de capacité à vide utilisée par les liens existants est déterminée par une méthode basée sur le comptage de la quantité de données envoyée sur chaque lien par unité de temps, - le réseau est un réseau sans fil radio, - la détermination des sous graphes complets maximaux utilise soit un algorithme exact, tel que celui de Bron-Kerbosch (1973), ou une méthode approchée, - on introduit dans les messages de contrôle TC du protocole OLSR les valeurs des capacités à vide ainsi que la proportion de la capacité à vide utilisée pour chaque MPR-S. L'invention concerne également un équipement de gestion d'un noeud d'un réseau de communication mufti sauts ad hoc qui est spécialement configuré pour fonctionner selon le procédé décrit. La présente invention, sans qu'elle en soit pour autant limitée, va maintenant être exemplifiée avec la description qui suit de modes de réalisation et de mise en oeuvre en relation avec la Figure 1, qui est un schéma d'un exemple de réseau de communication sans fil avec des noeuds et deux chemins entre les noeuds de départ a et destination v et la Figure 2 qui est un schéma d'un autre exemple de réseau de communication sans fil avec des noeuds et deux chemins entre les noeuds de départ a et destination f. A titre d'exemple de réalisation, on va présenter un calcul de la capacité d'un chemin en fonction des capacités des différents liens entre noeuds composant le chemin. Un noeud est au minimum un équipement de réception et de retransmission comportant des moyens de calcul pour gestion des flux le traversant. En pratique, le noeud peut être soit un équipement spécifiquement dédié au réseau, soit un équipement assurant en outre d'autres fonctions comme par exemple un microordinateur dans un réseau de microordinateurs. Le noeud peut recevoir des données d'un ou plusieurs autres noeuds et les retransmettre à un ou plusieurs autres noeuds. Le lien entre les noeuds peut être filaire mais il est de préférence sans fil et en particulier de type radio. Dans un réseau ad hoc la topologie peut évoluer au cours du temps et le/les chemins de passage des données peuvent également évoluer au cours du temps. La gestion des chemins est faite de façon distribuée, chaque noeud participant à la gestion. On considère par exemple le cas d'un noeud source qui souhaite démarrer un flux vidéo demandant une bande passante de X bits/sec. Avec les modèles existants, la capacité d'un chemin serait le minimum des capacités que proposent les liens. Or, les liens sont corrélés et ne peuvent pas transmettre en parallèle. En conséquence, pour effectivement avoir la bande passante attendue, le chemin à trouver pour les X bits/sec serait en fait un chemin où le minimum en comptant les corrélations est supérieur ou égal à X. Dans la Figure 2, on a représenté un exemple où il existe deux possibilités pour aller d'une source à une destination (a vers v). Le tracé en cercle continu représente la zone de couverture des noeuds h et o et le tracé en pointillé, celle de leurs zones d'interférences. Lorsqu'un noeud transmet sur un lien (par exemple o vers p), aucun autre noeud dans les zones d'interférence de o et de p ne peuvent transmettre. La capacité disponible sur un lien dépend donc des capacités utilisées par les liens dont au moins une extrémité est dans la zone d'interférence d'au moins une extrémité du lien. Par extension, la capacité disponible d'un chemin dépend des capacités utilisées par les liens dont au moins une extrémité est dans la zone d'interférence d'au moins une extrémité d'au moins un lien du chemin. Rechercher des chemins satisfaisants en tenant compte de ce phénomène est donc très complexe et les solutions existantes ignorent ce problème. Avec la présente invention, on détermine des chemins qui offrent au minimum une capacité disponible donnée, tout en tenant compte des corrélations entre les capacités des liens. A cette fin des calculateurs de gestion du réseau exécutent des algorithmes de calcul pour cette détermination des chemins. Pour cela, on détermine la topologie du réseau, par exemple calculée par un protocole de routage proactif comme OLSR et on retourne le chemin qui satisfait la bande passante requise. Plusieurs étapes sont effectuées : - grouper les liens interférents sans le passage du flux de données, puis - sélectionner le chemin parmi les différentes possibilités en tenant compte de l'interférence intra-flux. Plus précisément, on détermine la topologie du réseau en utilisant un protocole de routage pour réseaux ad hoc. Parmi les protocoles existants, on peut utiliser par exemple le protocole OLSR pour « Optimized Link State Routing », qui fonctionne de la façon suivante : - les noeuds échangent périodiquement des messages HELLO contenant la liste des noeuds voisins desquels ils ont reçu récemment un 15 message HELLO; - par l'agrégation des informations contenues dans les messages HELLO reçus, chaque noeud reconstitue en mémoire une topologie locale totale du réseau, contenant tous les voisins directs, dits « à un saut », et les voisins des voisins, dits « à deux sauts », et tous les liens entre lui-même et 20 ses voisins à un saut et entre ses voisins à un saut et leurs propres voisins à un saut; - chaque noeud choisit un sous-ensemble de ses voisins, dits « MPR » pour « multipoint relays », qui lui permettent de joindre tous ses voisins à deux sauts et déclare dans ses messages HELLO quel voisin a été choisi 25 comme MPR; - chaque noeud qui a été choisi comme MPR par au moins un voisin diffuse périodiquement dans le réseau des messages dits TC (« Topology Control ») contenant la liste des voisins qui l'ont choisi comme MPR, et dits « MPR-S » pour « MPR-selectors »; 30 - par l'agrégation des informations contenues dans les messages TC, chaque noeud reconstitue en mémoire une topologie globale partielle du réseau contenant tous les noeuds et suffisamment de liens entre les noeuds pour permettre de trouver un chemin vers chaque noeud. Un paramètre de la solution est le nombre de sauts H en deçà duquel deux liens partagent une même ressource de capacité (bande passante). En réseaux sans fil, les noeuds utilisant un médium radio commun, les liens ne peuvent être tous utilisés en même temps. Il s'agit donc de déterminer les ensembles de liens en conflit pour une ressource commune. Pour ce faire, chaque noeud maintient un graphe de conflit: - chaque sommet du graphe de conflit représente un lien de la topologie globale partielle ; - chaque arête du graphe de conflit représente une relation de conflit entre deux liens de la topologie globale partielle. Les cliques (sous graphes complets maximaux) du graphe de conflit représentent les ensembles de liens en conflit pour une ressource de capacité commune. Pour la détermination des chemins, on met en oeuvre la méthode qui suit. Étant donné un noeud source s, un noeud destination t et une bande passante minimale B à satisfaire, un chemin faisable est solution du programme linéaire avec contraintes d'intégralité suivantes : Min. lx," (i, j)EE s.t. xs, ^ xjs ^1 (s,j)DE (j,$)DE ^Ixjt^El (t,j)EE (j,t)EE 1 x13 ^ 1 xji ^ 0 ^ 1 ^ {S,t} (i, j)EE (j,i)EE B ^ Bij) ^ 1 jCu ^ c ^ K xq^{0,1} ^(i,j)^E où Kest l'ensemble des cliques du graphe de conflit, Cid est la capacité à vide du lien (i,j) et B11 est la portion de capacité à vide déjà utilisée. Pour en revenir à la Figure 1, l'application de ces méthodes, en considérant une interférence à deux sauts, on obtient l'ensemble de cliques suivant : { (a, b), (a, g), (b, c) } { (a, b), (a, g), (g, h) } { (a, b), (b, c), (c, d) } { (b, c), (c, d), (d, e) } { (c, d), (d, e), (e, f) } K. { (d, e), (e, f ), (k, f) } {(e,f),(1,k),(k,f)} { (a, g), (g, h), (h, 1) } { (g, h), (h, 1), (j, l) } { (h, 1), (a, i), (i, k) } { (a, l), (!, k), (k, f) } La capacité disponible sur le chemin (a, b, c, d, e, f) est obtenue en 5 cherchant la valeur Ro maximale telle que: Bab+ Ro + Bag +Bbc + Ro Sur la figure 1, les valeurs numériques indiquées entre les noeuds correspondent aux valeurs de capacité restante/disponible (soit 1 - B..). On remplace dans la liste d'inégalités précédente, les B.. par leurs valeurs et on obtient: { 10 Ro1/2(1-1/4-1/4) =1/4 Ro 1-1 /4 =3/4 Ro1/3(1-1/4-1/4-1/4) =1/12 Ro1/3(1-1/4-1/4-1/4) =1/12 Ro1/3(1-1/4-1/4-1/4) =1/12 Ro1/2(1-1/4-1/4) =1/4 Ro 1-1 /4 =3/4 La valeur Ro maximale qui satisfait ces équations est donc 1/12 De même, on calcule la capacité disponible sur (a, g, h, i, j, k, f) en cherchant la valeur R1 maximale telle que: Bab+Bag+R1+Bbc X bits/sec). On comprend bien que l'invention peut être déclinée selon de nombreuses autres possibilités sans pour autant sortir du cadre défini par la 15 description et les revendications. REVENDICATIONS1. Procédé de routage qualitatif de données dans un réseau de communication multi sauts ad hoc, ledit procédé permettant de déterminer en fonction d'un critère de qualité de communication déterminable au moins un chemin de passage des données par des liens entre des noeuds, entre un noeud d'entrée et un noeud de sortie dudit réseau, la valeur du critère de qualité d'un chemin donné étant calculable en fonction d'au moins une métrique de liens déterminable dans ledit réseau, les liens pouvant interférer entre eux lors du passage des données, caractérisé en ce que dans la détermination du chemin on prend en compte l'interférence intra-flux et pour un critère de qualité de communication qui est une valeur minimale B de bande passante à satisfaire, on utilise un protocole de routage pour réseau ad hoc afin de déterminer la topologie globale du réseau et, en ce que, étant donné un paramètre H > 1, on détermine les liens interférents de la manière suivante : - une fois le protocole de routage fonctionnel, chaque noeud du réseau détermine un graphe global de conflit, dans ledit graphe de conflit, chaque sommet représentant un lien dans une topologie globale partielle et chaque arête de ce graphe global de conflit représentant une relation de conflit entre deux liens de la topologie globale partielle, c'est-à-dire que ces liens sont distants d'au plus H sauts d'après la topologie globale partielle ; - chaque noeud ayant un graphe global de conflit détermine les sous graphes complets maximaux, dits « cliques », du graphe global de conflit, et ledit noeud détermine le chemin de passage dans le réseau par résolution du système linéaire suivant avec les contraintes d'intégralité suivantes : Min. 1 (i,j)EE S.t.ùxjs=1 (s,j)eE (j,$)eE xtj ù xi, =ù1 (t,j)EE (j,t)EE lxijû =0 V/e {s,t} (i,j)EE (j,i)EE B (ù.x ij + Bij) 1 Vc E K x1JE{0,1} V(i,j)EE où K est l'ensemble des cliques du graphe global de conflit en considérant que s est un noeud source, t un noeud destination et i, j des indices de référence des noeuds du réseau, C1 la capacité de débit à vide du lien entre les noeuds i et j , B# la proportion de la capacité à vide qui est utilisée sur le lien entre les noeuds i et j pour les flux existants et la différence de B11 par rapport à 1 correspond donc à la proportion de flux libre utilisable restant par rapport à la capacité à vide sur ledit lien (i, j) , E étant l'ensemble des liens entre les noeuds. 2. Procédé selon la revendication 1, caractérisé en ce que le protocole 10 de routage pour réseau ad hoc utilisé est OLSR, AODV, DSR TBRPF, ou FSR. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que les étapes de détermination de la topologie globale partielle du réseau et du graphe de conflit sont effectuées séparément au sein d'un noeud, le graphe 15 de conflit étant déterminé après la détermination de la topologie globale partielle du réseau. 4. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le réseau est un réseau sans fil radio. 5. Procédé selon l'une quelconque des revendications précédentes, 20 caractérisé en ce que pour la détermination des sous graphes complets maximaux, on utilise une méthode choisie parmi la méthode exacte de Bron-Kerbosch ou une méthode approchée. 6. Procédé selon la revendication 1, caractérisé en ce que le protocole de routage utilisé est OLSR, dans lequel on introduit dans les messages de {contrôle TC les valeurs des capacités à vide ainsi que la proportion de la capacité à vide utilisée pour chaque MPR-S. 7. Equipement de gestion d'un noeud d'un réseau de communication multi sauts ad hoc, caractérisé en ce qu'il est spécialement configuré pour fonctionner selon le procédé de l'une quelconque des revendications précédentes.