Brevet FR3105681A1 — publié le 20210625

La présente invention concerne un procédé et un dispositif de détermination d’une topologie d’un réseau de communication composé d’une pluralité de nœuds connectés ou non respectivement à au moins un équipement, un des nœuds dit nœud racine étant relié à un réseau extérieur. Selon l’invention : on détermine (E300) une classe de service pour chaque nœud, on obtient (E303), de chaque nœud, des informations représentatives de la qualité du lien entre le nœud et d’autres nœuds, on calcule (E304), pour chaque lien, des paramètres représentatifs de la qualité du lien, on classe (E301) les nœuds selon leur classe de service et selon le nombre de liens composant le chemin qui les sépare du nœud racine, on détermine (E307), pour chaque nœud et selon le classement, les chemins possibles reliant le nœud au nœud racine, on calcule (E308) pour chaque chemin déterminé d’un score, on sélectionne (E309) le chemin pour le nœud ayant le meilleur score. Fig. 3 Procédé et dispositif de détermination d’une topologie d’un réseau de points d’accès sans fils L’invention concerne un procédé et un dispositif de détermination d’une topologie d’un réseau de points d’accès sans fils. La détermination d’une topologie dans un réseau de points d’accès sans fils est souvent basée sur des algorithmes de recherche d’un chemin dans un graphe. Par exemple, l’algorithme de Dijkstra permet de résoudre le problème du plus court chemin d’un point à un autre. Plus précisément, il calcule des plus courts chemins à partir d'une source dans un graphe orienté pondéré par des réels positifs. L’utilisation d’un tel algorithme dans un réseau domestique comprenant plusieurs points d’accès sans fils donne un résultat qui n’est pas adapté aux différents équipements qui sont reliés aux points d’accès. Ces équipements sont par exemple des décodeurs audio/vidéo, des téléviseurs, des téléphones ou des équipements échangeant des données. Il est alors souhaitable de pouvoir déterminer une topologie d’un tel réseau qui soit adaptée aux différents types d’équipements qui sont reliés aux points d’accès. La présente invention a pour but de résoudre les inconvénients de l’art antérieur en proposant un dispositif et un procédé de détermination d’une topologie d’un réseau qui prend en compte les différents types d’équipements qui sont reliés aux points d’accès. A cette fin, l’invention concerne un procédé de détermination d’une topologie d’un réseau de communication composé d’une pluralité de nœuds connectés ou non respectivement à au moins un équipement, un des nœuds dit nœud racine étant relié à un réseau extérieur, caractérisé en ce que le procédé comporte les étapes de : - détermination d’une classe de service pour chaque nœud, la classe de service étant déterminée en fonction de l’équipement relié au nœud, - obtention, de chaque nœud, d’informations représentatives de la qualité du lien entre le nœud et d’autres nœuds, - calcul, pour chaque lien, de paramètres représentatifs de la qualité du lien, - classement des nœuds selon leur classe de service et pour les nœuds ayant la même classe de service en fonction du nombre de liens composant le chemin qui les sépare du nœud racine, - détermination, pour chaque nœud et selon le classement, de chemins possibles reliant le nœud au nœud racine, - calcul, pour chaque chemin déterminé, d’un score à partir de paramètres représentatifs de la qualité du lien et à partir de valeurs de coefficients dépendantes de la classe de service du nœud, - sélection du chemin pour le nœud ayant le meilleur score. L’invention concerne aussi un dispositif de détermination d’une topologie d’un réseau de communication composé d’une pluralité de nœuds connectés ou non respectivement à au moins un équipement, un des nœuds dit nœud racine étant relié à un réseau extérieur, caractérisé en ce que le dispositif de détermination comporte : - des moyens de détermination d’une classe de service pour chaque nœud, la classe de service étant déterminée en fonction de l’équipement relié au nœud, - des moyens d’obtention, de chaque nœud, d’informations représentatives de la qualité du lien entre le nœud et d’autres nœuds, - des moyens de calcul, pour chaque lien, de paramètres représentatifs de la qualité du lien, - des moyens de classement des nœuds selon leur classe de service et pour les nœuds ayant la même classe de service en fonction du nombre selon le nombre de liens composant le chemin qui les sépare du nœud racine, - des moyens de détermination, pour chaque nœud et selon le classement, de chemins possibles reliant le nœud au nœud racine, - des moyens de calcul, pour chaque chemin déterminé, d’un score à partir de paramètres représentatifs de la qualité du lien et à partir de valeurs de coefficients dépendantes de la classe de service du nœud, - des moyens de sélection du chemin pour le nœud ayant le meilleur score. Ainsi, en prenant en compte le type d’équipement relié à chaque nœud et en lui attribuant une classe en fonction de l’équipement relié au nœud, en classant les nœuds en fonction de leur classe de service et en déterminant un score fonction de valeurs de coefficients dépendantes de la classe de service du nœud, la présente invention détermine une topologie optimale qui prend en compte les différents types d’équipements qui sont reliés aux points d’accès. Selon un mode particulier de réalisation, lorsque qu’un chemin est sélectionné pour un nœud, le procédé comporte en outre les étapes de : - association, à chaque lien du chemin sélectionné, d’une variable dite fixée, - association, à chaque nœud du chemin par lequel le chemin passe, d’une variable résolu, et détermination pour chaque nœud suivant de chemins possibles reliant le nœud suivant au nœud racine effectuée en outre sans utiliser les liens formant une boucle avec d’autres liens auxquels est associée la variable fixée. Selon un mode particulier de réalisation, la détermination de chemins possibles reliant le nœud suivant au nœud racine est effectuée si le nœud suivant n’est pas associé à la variable résolu. Selon un mode particulier de réalisation, les informations représentatives de la qualité du lien entre le nœud et d’autres nœuds sont le débit physique du lien et la latence. Selon un mode particulier de réalisation, le réseau de communication est un réseau domestique. Selon un mode particulier de réalisation, le dispositif de détermination de la topologie est compris dans un nœud. L’invention concerne aussi un programme d’ordinateur, caractérisé en ce qu’il comprend 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 dudit dispositif. L’invention concerne aussi des moyens de stockage, caractérisés en ce qu’ils stockent un programme d’ordinateur comprenant 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 dudit 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 : représente schématiquement un réseau de communication sans fils constitué d’une pluralité de nœuds dans lequel la présente invention est implémentée ; illustre schématiquement un exemple d’architecture matérielle d’un nœud qui détermine la topologie du réseau selon la présente invention ; illustre un exemple d’un algorithme exécuté par le nœud qui détermine la topologie du réseau selon la présente invention ; illustre un exemple dans lequel tous les liens possibles entre les nœuds C et R du réseau de communication sans fil sont représentés ; illustre un exemple de la topologie des chemins dans le réseau de communication sans fils déterminée par la présente invention. EXPOSE DETAILLE DE MODES DE REALISATION La Fig. 1 représente schématiquement un réseau de communication sans fil constitué d’une pluralité de nœuds dans lequel la présente invention est implémentée. Le réseau de communication sans fil tel que représenté en Fig. 1 est composé de six nœuds. Le réseau de communication sans fil est par exemple un réseau de communication sans fil de type WIFI. Le nœud R est un nœud dit racine. Le nœud R est par exemple une passerelle résidentielle qui relie le réseau de communication sans fils à un réseau extérieur tel qu’un réseau internet qui émet et reçoit des données. Le nœud R est selon l’invention le point de départ de l’arbre couvrant la topologie du réseau déterminée par la présente invention. Les nœuds A, B, C, D et E sont reliés ou non respectivement à au moins un équipement. Par exemple, le nœud B est un nœud relié à un téléviseur de haute définition, le nœud C est par exemple relié à un décodeur audiovisuel, le nœud D est par exemple relié à un téléphone. Chaque nœud est apte à effectuer des mesures qualitatives sur chaque lien le reliant à un autre nœud. Par exemple, la présente invention est décrite dans un exemple qui utilise comme mesures qualitatives des mesures de débit physique (PHY rate) et des mesures de latence sur chaque lien le reliant à un autre nœud, mais d’autres types de mesures sont envisageables, comme par exemple le taux de perte de paquets. Un seul nœud exécute l’algorithme selon la présente invention. La présente invention est décrite dans un exemple dans lequel le nœud R détermine la topologie du réseau. Bien entendu, la détermination de la topologie du réseau peut être effectuée par un autre nœud. Le nœud qui détermine la topologie du réseau est appelé par la suite nœud concentrateur. Bien entendu la présente invention peut être exécutée par un dispositif informatique distant, par exemple compris dans le réseau extérieur. Dans l’exemple de la Fig. 1, le nœud B est relié par un lien radio au nœud A, le nœud A est relié par un lien radio au nœud R, le nœud R est relié par un lien radio au nœud C, le nœud C est relié par un lien radio au nœud D et le nœud D est relié par un lien radio au nœud A. Il est à remarquer que les liens reliant les nœuds peuvent être en totalité ou en partie des liens filaires. La Fig. 2 illustre schématiquement un exemple d’architecture matérielle du nœud concentrateur qui détermine la topologie du réseau selon la présente invention. Dans l’exemple de la Fig. 2, le nœud concentrateur est le nœud R. Le nœud R comprend : - un processeur, micro-processeur, ou microcontrôleur 200 ; - une mémoire volatile 203 ; - une mémoire non volatile 202 ; - éventuellement, un lecteur 204 de medium de stockage tel qu’un lecteur de carte SD (Secure Digital Card en anglais ou Carte Numérique Sécurisée en français) ou un disque dur ; - une interface réseau 205 ; - un bus de communication 201 reliant le processeur 200 à la mémoire ROM 202, à la mémoire RAM 203, au lecteur de médium de stockage 204 et à l’interface 205. Le processeur 200 est capable d’exécuter des instructions chargées dans la mémoire volatile 203 à partir de la mémoire non volatile 202, d’une mémoire externe (non représentée), d’un support de stockage, tel qu’une carte SD ou autre, ou d’un réseau de communication. Lorsque le concentrateur 20 est mis sous tension, le processeur 200 est capable de lire de la mémoire volatile 203 des instructions et de les exécuter. Ces instructions forment un programme d’ordinateur qui cause la mise en œuvre, par le processeur 200, de tout ou partie du procédé décrit en relation avec la Fig. 3. Tout ou partie du procédé décrit en relation avec la Fig. 3 peut être implémenté sous forme logicielle par exécution d’un ensemble d’instructions par une machine programmable, telle qu’un DSP ( Digital Signal Processor en anglais ou Unité de Traitement de Signal Numérique en français) ou un microcontrôleur ou être implémenté sous forme matérielle par une machine ou un composant dédié, tel qu’un FPGA ( Field-Programmable Gate Array en anglais ou Matrice de Portes Programmable sur le Terrain en français) ou un ASIC ( Application- Specific Integrated Circuit en anglais ou Circuit Intégré Spécifique à une Application en français). La Fig. 3 illustre un exemple d’un algorithme exécuté par le nœud qui détermine la topologie du réseau selon la présente invention. A l’étape E300, le nœud concentrateur détermine la classe de service de chaque nœud du réseau de communication sans fil. Chaque nœud informe le nœud concentrateur de la classe de service qui lui est associée. Si un nœud est relié à un téléphone, la classe de service associée au nœud est de la classe voix sur IP VOIP ; si le nœud est relié à un décodeur audiovisuel la classe de service associée au nœud est télévision sur IP TV Ultra Haute Définition IPTV UHD ; si le nœud est relié à un téléviseur la classe de service associée au nœud est IP TV Haute Définition IPTV HD. Pour les autres nœuds, la classe de service associée est données. En variante, l’usager du réseau de communication ou l’opérateur du réseau de communication détermine la classe de service de chaque nœud par l’intermédiaire d’une interface graphique représentant les différents nœuds. L’usager ou l’opérateur attribue une classe de service à chaque nœud par l’intermédiaire de l’interface graphique. Ainsi, la classe de service attribuée aux nœuds A, E et R est données, la classe de service associée au nœud B est IPTV UHD, la classe de service associée au nœud C est IPTV HD et la classe de service associée au nœud D est VOIP. A l’étape E301, les nœuds sont ordonnés selon leur classe de service. Par exemple, les nœud dont la classe de service est IPTV UHD sont classés en premier, les nœuds dont la classe de service est IP TV HD sont classés après les nœuds dont la classe de service est IPTV UHD, les nœuds dont la classe de service est VOIP sont classés après les nœuds dont la classe de service est IPTV HD et les nœuds dont la classe de service est données sont classés après les nœuds dont la classe de service est VOIP. Au sein d’une même classe de service, les nœuds sont classés selon le nombre de liens composant le chemin qui les sépare du nœud racine dans une topologie avant la mise en œuvre du procédé selon la présente invention. Le nœud ayant le chemin le plus court est classé en premier. Lorsque deux nœuds d’une même classe de service ont le même nombre de liens composant le chemin qui les sépare du nœud racine, un choix arbitraire est par exemple effectué. Ainsi, le nœud C est classé en premier, le nœud B est classé en second, le nœud D est classé en troisième, le nœud R est classé en quatrième, le nœud A est classé en cinquième et le nœud E est classé en sixième. A l’étape E302, deux valeurs de coefficients α et β sont attribuées pour chaque classe de service. A la classe de service IPTV UHD sont attribuées les valeurs α=1 et β=0 ; à la classe de service IPTV HD sont attribuées les valeurs α=0.8 et β=0.2 ; à la classe de service VOIP sont attribuées les valeurs α=0 et β=1 et à la classe de données sont attribuées les valeurs α=0.5 et β=0.5. Ces valeurs de coefficients vont permettre par la suite de déterminer une topologie optimale qui est adaptée à chaque équipement relié à un nœud. A l’étape E303, le concentrateur collecte de chaque nœud les mesures de débit physique (PHY rate) et les mesures de latence sur chaque lien reliant le nœud à un autre nœud. A l’étape E304, le concentrateur caractérise chaque lien pour lequel il a obtenu les mesures de débit physique (PHY rate) et les mesures de latence. Le concentrateur détermine pour chaque lien la valeur d’une variable notée coût_débit et la valeur d’une variable notée coût_latence à l’aide des formules suivantes : Coût_débit= 5-(5*Phy rate/(Max(Phy rates)) Coût_latence= 5*(latence-Min(latences))/Max(latences). où Phy rate est la mesure du débit physique pour le lien, latence est la mesure de latence pour le lien, Max(Phy rate) est la valeur de débit physique maximale obtenue parmi l’ensemble des mesures de débit obtenues des liens, Max(latences) est la valeur de latence maximale obtenue parmi l’ensemble des mesures de latence obtenues des liens et Min(latences) est la valeur de latence minimale obtenue parmi l’ensemble des mesures de latence obtenues des liens. A l’étape E305, le concentrateur associe la variable flexible à chaque lien et la variable non résolu à chaque nœud. A l’étape E306, le concentrateur sélectionne le premier nœud selon l’ordre déterminé à l’étape E301. Ainsi selon l’exemple précédent, le nœud C est sélectionné. A l’étape E307, le concentrateur détermine tous les chemins possibles entre le nœud sélectionné et le nœud racine à partir des différents liens dont les mesures ont été obtenues à l’étape E303 sans utiliser les liens formant une boucle avec d’autres liens auxquels est associée la variable fixée. Par exemple, le concentrateur détermine les chemins suivants entre le nœud C sélectionné et le nœud racine R : CR, CAR, CBR, CABR, CBAR, CDAR, CDBR, CDBAR, CEDBR et CEDBAR. Dans cet exemple, les successions de lettres symbolisent les différents nœuds par lequel le chemin passe. La Fig. 4 illustre un exemple dans lequel tous les liens possibles entre les nœuds C et R du réseau de communication sans fil sont représentés. A l’étape E308, le concentrateur détermine un score S(C) pour chaque chemin possible entre le nœud sélectionné et le nœud racine selon la formule suivante : où α et β prennent les valeurs correspondant à la classe de service du nœud sélectionné, l est l’indice associé à chaque lien du chemin. A l’étape E309, le concentrateur détermine le meilleur chemin parmi tous les chemins possibles à partir des scores calculés à l’étape E308. Le meilleur chemin est le chemin ayant le score minimum. Ainsi, en utilisant les coefficients α et β qui dépendent de la classe de service du nœud sélectionné, la topologie déterminée est optimale et est adaptée à l’équipement relié au nœud. Par exemple, le meilleur chemin est le chemin CAR. A l’étape E310, le concentrateur associe la variable fixé à chaque lien du meilleur chemin déterminé. Par exemple, la variable fixée est associée aux liens entre les nœuds C et A et entre les nœuds A et R. A l’étape E311, le concentrateur associe la variable résolu aux nœuds par lequel le chemin passe, par exemple aux nœuds C, A et R. A l’étape E312, le concentrateur vérifie s’il existe un nœud dont la variable associée est non résolu. Dans l’affirmative, le concentrateur passe à l’étape E314. Dans la négative, le concentrateur passe à l’étape E315. A l’étape E314, le concentrateur sélectionne le nœud suivant dont la variable associée est non résolu selon l’ordre déterminé à l’étape E301 et retourne à l’étape E307. Par exemple, le nœud sélectionné est le nœud B. Le concentrateur exécute les étapes E307 à E312 pour le nœud B sélectionné pour déterminer le chemin optimal reliant le nœud B au nœud R. Tous les chemins contenant le lien CR sont exclus car ils créent une boucle avec les liens CA et AR. Par exemple, le meilleur chemin est le chemin BR. La variable fixée est associée au lien entre les nœuds B et R. Le concentrateur associe la variable résolu au nœud B. A l’étape E314, le concentrateur sélectionne le nœud suivant dont la variable associée est non résolu selon l’ordre déterminé à l’étape E301 et retourne à l’étape E307. Par exemple, le nœud sélectionné est le nœud D. Le concentrateur exécute les étapes E307 à E312 pour le nœud D sélectionné pour déterminer le chemin optimal reliant le nœud D au nœud R et sélectionne ensuite le nœud E pour l’exécution des étapes E307 à E312 pour déterminer le chemin optimal reliant le nœud E au nœud R. A l’étape E315, le concentrateur transfère chaque chemin déterminé aux autres nœuds pour une application de la topologie déterminée. La Fig. 5 illustre un exemple de la topologie des chemins dans le réseau de communication sans fils déterminée par la présente invention. Procédé de détermination d’une topologie d’un réseau de communication composé d’une pluralité de nœuds connectés ou non respectivement à au moins un équipement, un des nœuds dit nœud racine étant relié à un réseau extérieur, caractérisé en ce que le procédé comporte les étapes de : détermination (E300) d’une classe de service pour chaque nœud, la classe de service étant déterminée en fonction de l’équipement relié au nœud, obtention (E303), de chaque nœud, d’informations représentatives de la qualité du lien entre le nœud et d’autres nœuds, calcul (E304), pour chaque lien, de paramètres représentatifs de la qualité du lien, classement (E301) des nœuds selon leur classe de service et pour les nœuds ayant la même classe de service selon le nombre de liens composant le chemin qui les sépare du nœud racine, détermination (E307), pour chaque nœud et selon le classement, de chemins possibles reliant le nœud au nœud racine, calcul (E308), pour chaque chemin déterminé, d’un score à partir de paramètres représentatifs de la qualité du lien et à partir de valeurs de coefficients dépendantes de la classe de service du nœud, sélection (E309) du chemin pour le nœud ayant le meilleur score. Procédé selon la revendication 1, caractérisé en ce que lorsque qu’un chemin est sélectionné pour un nœud, le procédé comporte en outre les étapes de : association, à chaque lien du chemin sélectionné, d’une variable dite fixée, association, à chaque nœud du chemin par lequel le chemin passe d’une variable résolu, et en ce que la détermination pour chaque nœud suivant, de chemins possibles reliant le nœud suivant au nœud racine est en outre effectuée sans utiliser les liens formant une boucle avec d’autres liens auxquels est associé la variable fixée. Procédé selon la revendication 2, caractérisé en ce que la détermination de chemins possibles reliant le nœud suivant au nœud racine est effectuée si le nœud suivant n’est pas associé à la variable résolu. Procédé selon l’une quelconque des revendications précédentes, caractérisé en ce que les informations représentatives de la qualité du lien entre le nœud et d’autres nœuds sont le débit physique du lien et la latence. Procédé selon l’une quelconque des revendications précédentes, caractérisé en ce que le réseau de communication est un réseau domestique. Dispositif de détermination d’une topologie d’un réseau de communication composé d’une pluralité de nœuds connectés ou non respectivement à au moins un équipement, un des nœuds dit nœud racine étant relié à un réseau extérieur, caractérisé en ce que le dispositif de détermination comporte : des moyens de détermination d’une classe de service pour chaque nœud, la classe de service étant déterminée en fonction de l’équipement relié au nœud, des moyens d’obtention, de chaque nœud, d’informations représentatives de la qualité du lien entre le nœud et d’autres nœuds, des moyens de calcul, pour chaque lien, de paramètres représentatifs de la qualité du lien, des moyens de classement des nœuds selon leur classe de service et pour les nœuds ayant la même classe de service selon le nombre de liens composant le chemin qui les sépare du nœud racine, des moyens de détermination, pour chaque nœud et selon le classement, de chemins possibles reliant le nœud au nœud racine, des moyens de calcul, pour chaque chemin déterminé, d’un score à partir de paramètres représentatifs de la qualité du lien et à partir de valeurs de coefficients dépendantes de la classe de service du nœud, des moyens de sélection du chemin pour le nœud ayant le meilleur score. Nœud caractérisé en ce qu’il comporte le dispositif selon la revendication 6. Programme d’ordinateur caractérisé en ce qu’il comprend des instructions pour mettre en œuvre, par un dispositif, le procédé selon l’une des revendications 1 à 5, lorsque ledit programme est exécuté par le dispositif. Un support d’enregistrement sur lequel est stocké un programme d’ordinateur comprenant des instructions pour mettre en œuvre, par un dispositif, le procédé selon l’une des revendications 1 à 5, lorsque ledit programme est exécuté par le dispositif.