Brevet FR3131166A1 — publié le 20230623

L’invention concerne un procédé de mise en œuvre dynamique de clusterisation de nœuds et de sélection de configuration de cluster conjointes au sein d’un réseau (10) de communication sans fil ad hoc de nœuds mobiles (20), où chaque nœud (20) d’un cluster est contraint d’itérer le cycle suivant : i/ déclenchement d’une étape de découverte de voisinage déterminant des informations actualisées comprenant l’identification de nœud(s) ; ii/ sélection d’une configuration de cluster par le nœud chef de cluster en fonction des informations actualisées, et déclenchement de la nouvelle configuration sélectionnée ; puis iv/ vérification qu’un ensemble de conditions relatives à la configuration mise en œuvre dans le cluster est bien vérifié, ledit ensemble de conditions déterminant si la stabilité de la configuration mise en œuvre dans le cluster est supérieure à un seuil fixé ; et si et seulement si l’ensemble de conditions est vérifié, déclenchement d’une fusion de clusters ou division du cluster ou d’un départ d’un ou plusieurs nœuds du cluster vers un autre cluster. Figure pour l’abrégé : Fig. 2 Mise en œuvre dynamique et conjointe de regroupement de nœuds et de sélection de configuration de groupe au sein d’un réseau de communication sans fil ad hoc de nœuds mobiles L’invention se situe dans le domaine des réseaux de communication sans fil ad hoc mobiles. Les applications ayant recours aux réseaux ad hoc couvrent un très large spectre : conférences, manifestations, opérations de secours (incendies, tremblement de terre, catastrophe naturelle, etc.), missions d'exploration… L’invention concerne plus spécifiquement les aspects de clusterisation et de configuration de cluster mis en œuvre dans ces réseaux et permettant aux nœuds de s'adapter en temps réel aux diverses fluctuations relatives aux conditions du canal radio, aux trafics, aux missions et aux différents mouvements des nœuds eux-mêmes ou de leur entourage. Par clusterisation, on entend le regroupement de nœuds entre eux, créant ainsi un ou des clusters (ou groupes) de nœuds, comprenant la sélection des nœuds parmi ceux du réseau ad hoc qui vont faire partie d’un même groupe, en fonction de critères prédéfinis. À titre d’illustration, N figure dans la plage [20-30] et g dans la plage [4-5]. N peut prendre des valeurs diverses, en centaines ou milliers. La valeur de g dépend de la forme d’onde, du trafic à écouler et plus globalement des services associés. Grouper ainsi des nœuds en clusters, associés chacun à un chef de cluster, présente un certain nombre d’avantages techniques, par exemple cela permet de limiter les échanges et la taille des tables de routage et de réduire l’impact de la mobilité sur la topologie entière. La ressource spectrale étant limitée, il est souvent nécessaire de sélectionner la configuration du cluster, notamment le canal logique (un canal logique étant une ressource temps fréquence allouée sur lesquels les nœuds peuvent échanger de l’information) sur lequel les nœuds d’un cluster communiquent, en fonction d’un certain nombre de critères, en vue par exemple de gérer spatialement les fréquences/canaux logiques, par exemple de gérer la réutilisation spatiale (il peut parfois y avoir moins de canaux logiques que de clusters), en conservant un niveau d’interférence suffisamment faible pour permettre une bonne qualité des communications. Par configuration dans ce document, on entend l’affectation à un cluster d’un ensemble d’attributs du cluster incluant au minimum son canal logique (sa couleur) ; d’autres attributs peuvent en outre être attribués sélectivement aux nœuds du cluster lors de l’opération de configuration, tels que, par exemple et de façon non exhaustive, l’ordonnancement des communications entre les nœuds du cluster et l’allocation de ressources (puissance d’émission, type de codage et/ou de modulation). On connaît par exemple le document FR3032848 « procédé pour générer des groupes au sein d’un réseau radio ad hoc » traitant exclusivement de la clusterisation ou encore le document FR3004309 « procédé distribué pour sélectionner une configuration dans les réseaux mobiles » traitant de la configuration. Ces solutions sont indépendantes et ne traitent pas le problème conjoint. Il ne suffit pas d’associer tel quel les deux solutions pour que cela fonctionne. FR3032848 « PROCEDE POUR GENERER DES GROUPES AU SEIN D'UN RESEAU RADIO AD HOC » traite du regroupement de nœuds de manière dynamique et distribuée dans un réseau mobile ad hoc. Cependant, il ne traite pas de la configuration de cet ensemble de nœuds. Le procédé dans FR3004309 permet de déterminer la configuration d’un ensemble de nœuds déjà formé en cluster et ainsi fixe, et ne permet donc pas de gérer des regroupements dynamiques de nœuds. Il est donc impératif d’appréhender de manière conjointe la formation dynamique de clusters et la configuration dynamique de ces clusters en tenant compte des interactions entre formation et configuration dynamiques de clusters. Cette invention a pour but de proposer une solution pour conjointement regrouper de manière distribuée et dynamique des nœuds et pour déterminer la configuration des ensembles de nœuds ainsi formés, tout en mutualisant la signalisation nécessaire aux deux aspects. A cet effet, suivant un premier aspect, la présente invention décrit un procédé de mise en œuvre dynamique conjointe de clusterisation de nœuds et de sélection de configuration de cluster au sein d’un réseau de communication ad hoc sans fil de nœuds mobiles, un cluster comprenant des nœuds, y compris un nœud désigné chef de cluster, partageant au moins un canal logique commun affecté au cluster, ledit procédé étant caractérisé en ce que : chaque nœud d’un cluster est contraint d’itérer le cycle de fonctionnement comprenant les étapes suivantes : i/ déclenchement d’une étape de découverte de voisinage déterminant des informations actualisées comprenant l’identification de nœud(s) voisins et le calcul d’indices de qualité des liens radio entre lesdits nœuds voisins et ledit nœud ; ii/ collecte par le nœud chef de cluster desdites informations actualisées par les nœuds dudit cluster et actualisation de métriques de configuration en fonction desdites informations ; iii/ sélection d’une configuration de cluster par le nœud chef de cluster en fonction des métriques de configuration actualisées, la sélection de la configuration comprenant au moins la sélection du canal logique associé au cluster et, si la configuration sélectionnée est différente de la configuration courante du cluster, déclenchement, par le nœud chef de cluster auprès de chaque nœud du cluster, de l’implémentation de la nouvelle configuration sélectionnée ; puis iv/ vérification qu’un ensemble de conditions relatives à la configuration mise en œuvre dans le cluster est bien vérifié, ledit ensemble de conditions déterminant si la stabilité de la configuration mise en œuvre dans le cluster est supérieure à un seuil fixé ; et si et seulement si l’ensemble de conditions est vérifié, déclenchement d’une évaluation du cluster par le nœud chef de cluster en fonction des informations actualisées à l’étape i/ et dans le cas où ladite étape d’évaluation détermine qu’une action de fusion du cluster avec un autre cluster ou de division du cluster ou de départ d’un ou plusieurs nœuds du cluster vers un autre cluster est à réaliser, mise en œuvre de ladite action suite au déclenchement auprès des nœuds du cluster, de ladite action ; si l’ensemble de conditions n’est pas vérifié, l’étape v est directement mise en œuvre ; v/ itération des étapes i à iv, qu’une nouvelle configuration ait été implémentée ou non, qu’une action de fusion ou de division ou de départ ait été implémentée ou non. L’invention permet de réguler et d’ordonnancer les fonctionnalités de configuration et de clusterisation, tout en permettant de mutualiser l’exploitation des informations de topologie collectées en début de cycle. Dans des modes de réalisation, un tel procédé comprendra en outre l’une au moins des caractéristiques suivantes : ledit ensemble de conditions comporte une ou plusieurs conditions, relatives à la configuration, parmi : aucun déclenchement de nouvelle configuration n’a été déclenchée à l’étape iii du cycle courant ; un temps supérieur à un seuil minimum prédéfini s’est écoulé depuis le dernier changement de configuration ; la configuration actuelle est mise en œuvre depuis les derniers θ stab cycles, où θ stab est une valeur entière prédéfinie ; dans l’étape de configuration de cluster, le nœud chef de cluster effectue une opération de désignation d’un nouveau chef de cluster parmi les nœuds du cluster en fonction desdites informations actualisées et le nœud chef de cluster transmet aux nœuds du cluster, au sein d’un même message, le nouveau canal logique sélectionné et l’indication du nouveau chef de cluster désigné ; dans l’étape d’évaluation du cluster, il est préalablement déterminé par le nœud chef de cluster, en fonction desdites informations actualisées, si le cluster vérifie un ensemble de conditions définissant les caractéristiques requises d’un cluster, et s’il est déterminé que le cluster ne vérifie pas lesdites conditions, une division de cluster est évaluée par le nœud chef du cluster ; s’il est déterminé que le cluster vérifie lesdites conditions, une opération de fusion du cluster ou de départ d’un sous-ensemble de nœud du cluster pour un autre cluster existant est évaluée par le nœud chef du cluster en fonction desdites informations actualisées, puis déclenchée le cas échéant ; à l’issue du cycle de fonctionnement, la formule d’une métrique en fonction des informations actualisées utilisée à l’étape iii pour sélectionner une configuration et dont le calcul à un cycle donné est fonction d’une valeur calculée au cycle précédent est modifiée par le remplacement de ladite valeur par une autre valeur. Suivant un deuxième aspect, l’invention décrit un programme d’ordinateur destiné à être installé dans la mémoire d’un nœud mobile d’un réseau de communication ad hoc sans fil et à être exécuté sur un microprocesseur du nœud, ledit programme d’ordinateur comprenant des instructions logicielles qui, lorsqu’elles sont exécutées sur le microprocesseur, mettent en œuvre les étapes, qui incombent audit nœud, d’un procédé selon le premier aspect de l’invention. Suivant un troisième aspect, l’invention décrit un nœud mobile d’un réseau de communication sans fil ad hoc de nœuds mobiles dans lequel un ou des cluster comprenant des nœuds, y compris un nœud désigné chef de cluster, partageant au moins un canal logique commun affecté au cluster, ledit nœud étant caractérisé en ce que : i/ le nœud est adapté, s’il fait partie d’un cluster, pour déclencher d’une étape de découverte de voisinage déterminant des informations actualisées comprenant l’identification de nœud(s) voisins et le calcul d’indices de qualité des liens radio entre lesdits nœuds voisins et ledit nœud et pour envoyer ces informations actualisées au nœud chef de cluster ; ii/ s’il est chef de cluster, le nœud est adapté pour collecter les informations actualisées par les nœuds dudit cluster et actualiser des métriques de configuration en fonction desdites informations ; iii/ s’il est chef de cluster : le nœud est adapté pour sélectionner une configuration de cluster en fonction des métriques de configuration actualisées, la sélection de la configuration comprenant au moins la sélection du canal logique associé au cluster et, si la configuration sélectionnée est différente de la configuration courante du cluster, et le nœud est adapté pour déclencher, auprès de chaque nœud du cluster, l’implémentation de la nouvelle configuration sélectionnée ; puis iv/ s’il est chef de cluster : le nœud est adapté alors pour vérifier si un ensemble de conditions relatives à la configuration mise en œuvre dans le cluster est bien vérifié, ledit ensemble de conditions déterminant si la stabilité de la configuration mise en œuvre dans le cluster est supérieure à un seuil fixé ; et si et seulement si l’ensemble de conditions est vérifié, le nœud est adapté pour déclencher une évaluation du cluster en fonction des informations actualisées à l’opération i/ et dans le cas où il détermine, au cours de ladite évaluation, qu’une action de fusion du cluster avec un autre cluster ou de division du cluster ou de départ d’un ou plusieurs nœuds du cluster vers un autre cluster est à réaliser, pour déclencher ladite action auprès des nœuds du cluster ; le nœud, s’il fait partie d’un cluster, est adapté pour itérer les opérations i à iv, qu’une nouvelle configuration ait été implémentée ou non, qu’une action de fusion ou de division ou de départ ait été implémentée ou non. Dans des modes de réalisation, un tel nœud comprendra en outre l’une au moins des caractéristiques suivantes : ledit ensemble de conditions relatives à la configuration comporte une ou plusieurs conditions parmi : aucun déclenchement de nouvelle configuration n’a été déclenchée à l’étape iii du cycle courant ; un temps supérieur à un seuil minimum prédéfini s’est écoulé depuis le dernier changement de configuration ; la configuration actuelle est mise en œuvre depuis les derniers θ stab cycles, où θ stab est une valeur entière prédéfinie ; le nœud est adapté pour, lors de la sélection de configuration de cluster, effectuer une opération de désignation d’un nouveau chef de cluster parmi les nœuds du cluster en fonction desdites informations actualisées et pour transmettre aux nœuds du cluster, au sein d’un même message, le nouveau canal logique sélectionné et l’indication du nouveau chef de cluster désigné. Suivant un quatrième aspect, l’invention décrit un réseau de communication sans fil ad hoc de nœuds mobiles, comportant une pluralité de nœuds mobiles selon le troisième aspect de l’invention. L’invention sera mieux comprise et d’autres caractéristiques, détails et avantages apparaîtront mieux à la lecture de la description qui suit, donnée à titre non limitatif, et grâce aux figures annexées, données à titre d’exemple. La représente un réseau de communication sans fil de nœuds ad hoc dans un mode de réalisation de l’invention ; La représente les étapes d’un procédé de configuration et clusterisation dans le réseau de la dans un mode de réalisation de l’invention ; Des références identiques peuvent être utilisées dans des figures différentes lorsqu’elles désignent des éléments identiques ou comparables. Procédé de mise en œuvre dynamique de clusterisation de nœuds et de sélection de configuration de cluster conjointes au sein d’un réseau de communication sans fil ad hoc (10) de nœuds mobiles (20), un cluster comprenant des nœuds, y compris un nœud désigné chef de cluster, partageant au moins un canal logique commun affecté au cluster, ledit procédé étant caractérisé en ce que : chaque nœud (20) d’un cluster est contraint d’itérer le cycle de fonctionnement comprenant les étapes suivantes : i/ déclenchement d’une étape de découverte de voisinage déterminant des informations actualisées comprenant l’identification de nœud(s) voisins et le calcul d’indices de qualité des liens radio entre lesdits nœuds voisins et ledit nœud (20) ; ii/ collecte par le nœud chef de cluster desdites informations actualisées par les nœuds dudit cluster et actualisation de métriques de configuration en fonction desdites informations ; iii/ sélection d’une configuration de cluster par le nœud chef de cluster en fonction des métriques de configuration actualisées, la sélection de la configuration comprenant au moins la sélection du canal logique associé au cluster et, si la configuration sélectionnée est différente de la configuration courante du cluster, déclenchement, par le nœud chef de cluster auprès de chaque nœud du cluster, de l’implémentation de la nouvelle configuration sélectionnée ; puis iv/ vérification qu’un ensemble de conditions relatives à la configuration mise en œuvre dans le cluster est bien vérifié, ledit ensemble de conditions déterminant si la stabilité de la configuration mise en œuvre dans le cluster est supérieure à un seuil fixé ; et si et seulement si l’ensemble de conditions est vérifié, déclenchement d’une évaluation du cluster par le nœud chef de cluster en fonction des informations actualisées à l’étape i/ et dans le cas où ladite étape d’évaluation détermine qu’une action de fusion du cluster avec un autre cluster ou de division du cluster ou de départ d’un ou plusieurs nœuds du cluster vers un autre cluster est à réaliser, mise en œuvre de ladite action suite au déclenchement auprès des nœuds du cluster, de ladite action ; si l’ensemble de conditions n’est pas vérifié, l’étape v est directement mise en œuvre ; v/ itération des étapes i à iv, qu’une nouvelle configuration ait été implémentée ou non, qu’une action de fusion ou de division ou de départ ait été implémentée ou non. Procédé de mise en œuvre dynamique de clusterisation de nœuds et de sélection de configuration de cluster conjointes selon la revendication 1, selon lequel ledit ensemble de conditions relatives à la configuration comporte une ou plusieurs conditions parmi : aucun déclenchement de nouvelle configuration n’a été déclenchée à l’étape iii du cycle courant ; un temps supérieur à un seuil minimum prédéfini s’est écoulé depuis le dernier changement de configuration ; la configuration actuelle est mise en œuvre depuis les derniers θ stab cycles, où θ stab est une valeur entière prédéfinie. Procédé de mise en œuvre dynamique de clusterisation de nœuds et de sélection de configuration de cluster conjointes selon l’une des revendications précédentes, selon lequel, dans l’étape de configuration de cluster, le nœud chef de cluster effectue une opération de désignation d’un nouveau chef de cluster parmi les nœuds du cluster en fonction desdites informations actualisées et le nœud chef de cluster transmet aux nœuds du cluster, au sein d’un même message, le nouveau canal logique sélectionné et l’indication du nouveau chef de cluster désigné. Procédé de mise en œuvre dynamique de clusterisation de nœuds et de sélection de configuration de cluster conjointes selon l’une des revendications précédentes, selon lequel, dans l’étape d’évaluation du cluster : - il est préalablement déterminé par le nœud chef de cluster, en fonction desdites informations actualisées, si le cluster vérifie un ensemble de conditions définissant les caractéristiques requises d’un cluster, et s’il est déterminé que le cluster ne vérifie pas lesdites conditions, une division de cluster est évaluée par le nœud chef du cluster, puis déclenchée le cas échéant ; - s’il est déterminé que le cluster vérifie lesdites conditions, une opération de fusion du cluster ou de départ d’un sous-ensemble de nœud du cluster pour un autre cluster existant est évalué par le nœud chef du cluster en fonction desdites informations actualisées, puis déclenchée le cas échéant . Procédé de mise en œuvre dynamique de clusterisation de nœuds et de sélection de configuration de cluster selon l’une des revendications précédentes, selon lequel, à l’issue du cycle de fonctionnement, la formule d’une métrique en fonction des informations actualisées utilisée à l’étape iii pour sélectionner une configuration et dont le calcul à un cycle donné est fonction d’une valeur calculée au cycle précédent est modifiée par le remplacement de ladite valeur par une autre valeur. Programme d’ordinateur destiné à être installé dans la mémoire d’un nœud mobile (20) d’un réseau (10) de communication sans fil ad hoc et à être exécuté sur un microprocesseur du nœud, ledit programme d’ordinateur comprenant des instructions logicielles qui, lorsqu’elles sont exécutées sur le microprocesseur, mettent en œuvre les étapes, qui incombent audit nœud, d’un procédé selon l’une des revendications 1 à 5. Nœud mobile (20) d’un réseau (10) de communication sans fil ad hoc de nœuds mobiles dans lequel un ou des clusters comprenant des nœuds, y compris un nœud désigné chef de cluster, partageant au moins un canal logique commun affecté au cluster, ledit nœud étant caractérisé en ce que : i/ le nœud (20) est adapté, s’il fait partie d’un cluster, pour déclencher d’une étape de découverte de voisinage déterminant des informations actualisées comprenant l’identification de nœud(s) voisins et le calcul d’indices de qualité des liens radio entre lesdits nœuds voisins et ledit nœud et pour envoyer ces informations actualisées au nœud chef de cluster; ii/ s’il est chef de cluster, le nœud (20) est adapté pour collecter les informations actualisées par les nœuds dudit cluster et actualiser des métriques de configuration en fonction desdites informations ; iii/ s’il est chef de cluster : le nœud (20) est adapté pour sélectionner une configuration de cluster en fonction des métriques de configuration actualisées, la sélection de la configuration comprenant au moins la sélection du canal logique associé au cluster et, si la configuration sélectionnée est différente de la configuration courante du cluster, et le nœud est adapté pour déclencher, auprès de chaque nœud du cluster, l’implémentation de la nouvelle configuration sélectionnée ; puis iv/ s’il est chef de cluster : le nœud (20) est adapté alors pour vérifier si un ensemble de conditions relatives à la configuration mise en œuvre dans le cluster est bien vérifié, ledit ensemble de conditions déterminant si la stabilité de la configuration mise en œuvre dans le cluster est supérieure à un seuil fixé ; et si et seulement si l’ensemble de conditions est vérifié, le nœud est adapté pour déclencher une évaluation du cluster en fonction des informations actualisées à l’opération i/ et dans le cas où il détermine, au cours de ladite évaluation, qu’une action de fusion du cluster avec un autre cluster ou de division du cluster ou de départ d’un ou plusieurs nœuds du cluster vers un autre cluster est à réaliser, pour déclencher ladite action auprès des nœuds du cluster ; le nœud (20), s’il fait partie d’un cluster, est adapté pour itérer les opérations i à iv, qu’une nouvelle configuration ait été implémentée ou non, qu’une action de fusion ou de division ou de départ ait été implémentée ou non. Nœud (20) selon la revendication 7, dans lequel ledit ensemble de conditions relatives à la configuration comporte une ou plusieurs conditions relatives à la configuration parmi : aucun déclenchement de nouvelle configuration n’a été déclenchée à l’étape iii du cycle courant ; un temps supérieur à un seuil minimum prédéfini s’est écoulé depuis le dernier changement de configuration ; la configuration actuelle est mise en œuvre depuis les derniers θ stab cycles, où θ stab est une valeur entière prédéfinie. Nœud (20) selon l’une des revendications 7 à 8, adapté pour, lors de la sélection de configuration de cluster, effectuer une opération de désignation d’un nouveau chef de cluster parmi les nœuds du cluster en fonction desdites informations actualisées et pour transmettre aux nœuds du cluster, au sein d’un même message, le nouveau canal logique sélectionné et l’indication du nouveau chef de cluster désigné. Réseau (10) de communication sans fil ad hoc de nœuds mobiles, comportant une pluralité de nœuds mobiles (20) selon l’une des revendications 7 à 9.