Brevet FR3076429A1 — publié le 20190705

Proc6d6 d'allocation de ressources radio dans un reseau sans fil, par apprentissage L'invention concerne le domaine des reseaux de communication sans 5 fil comprenant un ensemble de dispositifs communicants entre eux et etant organises sous forme de groupes. L'invention porte sur un procede d'allocation de ressources radio, en particulier des ressources radio sous forme de canaux logiques, dans un tel reseau. Autrement dit, ('invention concerne la gestion des attributions des ressources radio aux differents 10 groupes du reseau, pour communiquer. Par la suite ('expression « canal logique » designe un ensemble de ressources frequentielles et/ou temporelles allouees a un ou plusieurs terminaux pour communiquer. Un canal logique peut etre Mini par une loi de saut de frequence au cours du temps. Par exemple, un canal logique est 15 Mini par un canal frequentiel predetermine pour chaque intervalle temporel, au cours d'une sequence comprenant plusieurs intervalles temporels. Dans un reseau sans fil compose de dispositifs communicants entre eux, les communications utilisent des ressources radio, par exemple des 20 ressources frequentielles ou temporelles ou encore des ressources de niveau de puissance des signaux ernis pour communiquer. Par exemple, dans un reseau organise en groupes de dispositifs, chaque groupe utilise un ensemble de ressources radio, par exemple des canaux logiques, pour communiquer. 25 Si deux groupes utilisent les mernes canaux logiques pour communiquer, ils peuvent se brouiller mutuellement ou interferer entre eux selon la distance qui les separe. II est donc necessaire de prendre en compte les interferences mutuelles entre groupes pour allouer au mieux les ressources radio aux groupes du reseau avec un objectif global de 30 maximiser le nombre de liens de communications qui fonctionnent avec un 2 niveau de qualite de la liaison suffisant pour mettre en oeuvre les services rendus par le reseau. Pour limiter ('influence des interferences entre groupes d'un meme reseau, une solution existante consiste a attribuer des canaux frequentiels orthogonaux aux differents groupes du reseau. Cette solution est cependant limitee compte tenu du fait que la ressource spectrale disponible est elle meme le plus souvent limitee. Une autre solution consiste a effectuer une reutilisation spatiale des canaux en attribuant les monies canaux a des groupes suffisamment eloignes, pour peu que l'on sache a l'avance les positions des groupes, y compris dans le cas de reseaux mobiles. Cette allocation est alors statique et vaut pour toute la duree de la mission. Cette solution presente les limites de ('allocation statique a des objets dynamiques. Si des groupes se rapprochent en cours de mission, ils sont susceptibles de se brouiller mutuellement. II est donc necessaire de recourir a des solutions dynamiques qui permettent de realiser au cours du temps la meilleure allocation possible des canaux. Cette solution doit aussi etre distribuee aux groupes car it est difficile d'imaginer centraliser le calcul de cette repartition pour des raisons de latence, de point de vulnerabilite et de surcharge des signaux de signalisations. On connait par ailleurs, une methode d'allocation de ressources basee sur un algorithme mathernatique d'essai-erreur appele « trial and error learning » (TEL). Cette methode est decrite dans la publication scientifique 25 [1]. Cette methode possede de bonnes proprietes de convergence tout en etant mise en oeuvre de fawn decentralisee au sein de chaque groupe du reseau. Chaque prise de decision d'un groupe est basee sur un diagramme d'etat qui necessite uniquement des informations locales dont une metrique 30 de qualite pergue du fonctionnement des liens de communication au sein du 3 groupe. Les conditions de convergence de cet algorithme requierent cependant que Ia metrique de qualite percue par un groupe soit une valeur deterministe. C'est-b-dire que, pour chaque configuration du reseau, it existe une seule et unique valeur de qualite par groupe. Cependant, les canaux de 5 communications sont soumis a divers phenomenes aleatoires (evanouissements, bruit de mesure, ...) qui introduisent des variations de Ia valeur de qualite percue autour de sa valeur deterministe. Sous ces conditions, la methode proposee dans [1] ne converge plus vers un point de fonctionnement satisfaisant et les performances du reseau sont degradees. lo Un probleme que vise a resoudre ('invention est donc d'ameliorer la methode proposee dans [1] afin de retrouver une convergence et des performances satisfaisantes lorsque Ia metrique de qualite percue est perturbee par des phenomenes aleatoires. Un autre probleme a resoudre est de generaliser Ia methode a 15 d'autres algorithmes d'essai-erreur par exemple celui decrit dans les publications scientifiques [2] et [3]. L'invention permet de resoudre les limitations des solutions de l'art anterieur en proposant un procede d'allocation de ressources radio base sur 20 une methode essai-erreur mettant en oeuvre un diagramme d'etats, tel que decrit notamment dans les references [1], [2] et [3]. L'invention consiste notamment en ('introduction d'un intervalle de tolerance dont les bornes sont mises a jour de facon automatisee afin de prendre en compte ('influence non deterministe des perturbations des canaux de propagation dans un reseau sans fil. L'intervalle de tolerance est pris en compte lors des decisions effectuees dans les transitions du diagramme d'etat. Ces transitions dependent de la valeur courante de la metrique de qualite mesuree qui correspond a l'etat global des liens de communication dans un groupe du reseau. 4 L'invention a pour objet un procede d'allocation de ressources radio au sein d'un reseau de dispositifs communicants organises en groupes, le procede comprenant les etapes suivantes executees iterativement par au moins un dispositif communiquant de chaque groupe: 5 Selectionner une nouvelle configuration d'allocation de ressources radio a' a appliquer aux dispositifs du groupe, avec une probabilite de selection donnee, ou appliquer une configuration d'allocation de reference a, avec une probabilite complementaire a ladite probabilite de selection, 10 Mesurer une metrique u' de qualite globale des liens de communication entre dispositifs du groupe, Comparer la metrique de qualite mesuree u' avec une metrique de qualite de reference ii, la comparaison incluant la prise en compte d'un intervalle de tolerance [U. - 5_, ri + 541 autour de la metrique de 15 quake de reference, I'intervalle de tolerance etant Mini par un seuil de tolerance bas 5_ et un seuil de tolerance haut 5+, En fonction de ladite comparaison, effectuer, au sein d'un diagramme d'etats ayant un nombre d'etats predetermine, une transition depuis un etat de depart vers un etat d'arrivee, 20 - En fonction de l'etat d'arrivee, mettre a jour ou non la metrique de qualite de reference ii avec la metrique de qualite mesuree u' et/ou mettre a jour ou non la configuration d'allocation de reference a avec la nouvelle configuration d'allocation a', En fonction de ladite transition et de ladite comparaison, mettre a jour 25 une memoire contenant au moins une metrique de qualite mesuree de maniere a ce que les valeurs contenues dans la memoire soient stationnaires, Determiner une borne inferieure et une borne superieure de la distribution des metriques de qualite de sorte qu'un pourcentage 30 donne de valeurs sont comprises entre la borne inferieure et la borne superieure, 5 Determiner le seuil de tolerance haut 6+ a partir de Ia borne superieure et le seuil de tolerance bas 6_ a partir de la borne inferieure. Selon un aspect particulier de ['invention, Ia mise a jour de Ia memoire 5 comprend les stapes suivantes : Si une nouvelle configuration d'allocation de ressources radio est selectionnee, - Si Ia metrique de qualite de reference est mise a jour, reinitialiser la memoire avec Ia metrique de qualite mesuree, 10 - Sinon, ne pas mettre a jour la memoire, - Si Ia configuration d'allocation de reference est appliquee, - Si Ia metrique de qualite mesuree est comprise dans l'intervalle de tolerance, ajouter Ia metrique de qualite mesuree a Ia memoire, 15 - Sinon, ^ Si Ia metrique de qualite de reference est mise a jour, reinitialiser Ia memoire avec la metrique de qualite mesuree, ^ Sinon, ne pas mettre a jour Ia memoire. 20 Selon un mode de realisation particulier de ('invention, Ia metrique de qualite u' d'un groupe est egale au rapport entre un nombre de liens de communication en etat de fonctionner dans le groupe et le nombre de liens de communication total dans le groupe. Selon un mode de realisation particulier de ('invention, les ressources 25 radio sont des ressources frequentielles. Selon un mode de realisation particulier de ('invention, le diagramme d'etats comprend un etat satisfaisant et un etat non satisfaisant. Selon un mode de realisation particulier de ('invention, lorsque l'etat de depart est l'etat satisfaisant et qu'une nouvelle configuration d'allocation 30 de ressources radio a' est selectionnee : 6 on effectue une transition vers l'etat satisfaisant avec une probabilite de transition dependante de la metrique de qualite mesuree u' et on met a jour la metrique de qualite de reference u avec la metrique de qualite mesuree u' et on met a jour la 5 configuration d'allocation de reference a avec la nouvelle configuration d'allocation a', on effectue une transition vers l'etat non satisfaisant avec une probabilite complementaire a ladite probabilite de transition. Selon un mode de realisation particulier de ('invention, lorsque l'etat 10 de depart est l'etat satisfaisant et qu'on applique au groupe la configuration d'allocation de ressources radio de reference a : Si la metrique de qualite mesuree u' est comprise dans I'intervalle de tolerance [rt - 8_, u + 5+] autour de la metrique de qualite de reference ft, on effectue une transition vers l'etat satisfaisant, 15 Si la metrique de qualite mesuree u' n'est pas comprise dans I'intervalle de tolerance - 8_, u + 5.j : - on effectue une transition vers l'etat satisfaisant avec une probabilite de transition dependante de la metrique de qualite mesuree u' et on met a jour la metrique de qualite de 20 reference u avec la metrique de qualite mesuree u', - on effectue une transition vers l'etat non satisfaisant avec une probabilite complementaire a ladite probabilite de transition. Selon un mode de realisation particulier de ['invention, lorsque l'etat 25 de depart est l'etat non satisfaisant, on selectionne une nouvelle configuration d'allocation de ressources radio a' et : - on effectue une transition vers l'etat satisfaisant avec une probabilite de transition dependante de la metrique de qualite mesuree u' et on met a jour la metrique de qualite de reference a 30 avec la metrique de qualite mesuree u' et on met a jour la 7 configuration d'allocation de reference a avec la nouvelle configuration d'allocation a', - on effectue une transition vers l'etat non satisfaisant avec une probabilite complementaire a ladite probabilite de transition. 5 Selon un mode de realisation particulier de ('invention, le diagramme d'etats comprend en outre au moins un premier etat de transition et un second etat de transition. Selon un mode de realisation particulier de ('invention, lorsque l'etat de depart est l'etat satisfaisant et qu'une nouvelle configuration d'allocation 10 de ressources radio a' est selectionnee : - Si la metrique de qualite mesuree u' est inferieure ou egale a la somme de Ia metrique de qualite de reference ft et du seuil de tolerance haut 8+, on effectue une transition vers l'etat satisfaisant sans mettre a jour ni Ia metrique de qualite de reference tit ni la 15 configuration d'allocation de reference a , - Si la metrique de qualite mesuree u' est superieure a la somme de la metrique de qualite de reference u et du seuil de tolerance haut 8+ : - on effectue une transition vers l'etat satisfaisant avec une 20 probabilite de transition donnee et on met a jour la metrique de qualite de reference ft avec la metrique de qualite mesuree u' et on met a jour la configuration d'allocation de reference a avec Ia nouvelle configuration d'allocation a', - on effectue une transition vers l'etat satisfaisant avec une 25 probabilite complementaire a ladite probabilite de transition sans mettre a jour ni la metrique de qualite de reference u ni Ia configuration d'allocation de reference a. Selon un mode de realisation particulier de ('invention, lorsque l'etat de depart est l'etat satisfaisant et qu'on applique au groupe la configuration 30 d'allocation de ressources radio de reference a: 8 Si la metrique de qualite mesuree u' est comprise dans I'intervalle de tolerance [1:1 - 8_, U + 8+] autour de la metrique de qualite de reference ft, on effectue une transition vers l'etat satisfaisant sans mettre a jour la metrique de qualite de reference u, 5 - Si la metrique de qualite mesuree u' est superieure a Ia somme de la metrique de qualite de reference u et du seuil de tolerance haut 6+, on effectue une transition vers le premier etat de transition sans mettre a jour Ia metrique de qualite de reference u, Si la metrique de qualite mesuree u' est inferieure a la difference 10 entre Ia metrique de qualite de reference u et le seuil de tolerance bas 8_, on effectue une transition vers le second etat de transition sans mettre a jour la metrique de qualite de reference u. Selon un mode de realisation particulier de ('invention, lorsque l'etat de depart est le premier etat de transition, on applique la configuration 15 d'allocation de ressources radio de reference a et : Si la metrique de qualite mesuree u' est comprise dans I'intervalle de tolerance [U - 6_, U + 6+] autour de Ia metrique de qualite de reference U, on effectue une transition vers l'etat satisfaisant sans mettre a jour la metrique de qualite de reference ii, 20 Si la metrique de qualite mesuree u' est superieure a la somme de Ia metrique de qualite de reference U. et du seuil de tolerance haut 6+, on effectue une transition vers l'etat satisfaisant et on met a jour Ia metrique de qualite de reference ii avec la metrique de qualite mesuree u', 25 - Si Ia metrique de qualite mesuree u' est inferieure a la difference entre la metrique de qualite de reference U et le seuil de tolerance bas 6_, on effectue une transition vers le second etat de transition sans mettre a jour la metrique de qualite de reference U . Selon un mode de realisation particulier de ('invention, lorsque l'etat 30 de depart est le second etat de transition, on applique Ia configuration d'allocation de ressources radio de reference a et : 9 Si la metrique de qualite mesuree u' est comprise dans I'intervalle de tolerance - + 8+] autour de la metrique de qualite de reference U, on effectue une transition vers l'etat satisfaisant sans mettre a jour la metrique de qualite de reference 11, 5 Si la metrique de qualite mesuree u' est superieure a la somme de la metrique de qualite de reference u et du seuil de tolerance haut 8+, on effectue une transition vers le premier etat de transition sans mettre a jour la metrique de qualite de reference il, Si la metrique de qualite mesuree u' est inferieure a la difference 10 entre la metrique de qualite de reference U et le seuil de tolerance bas 8_, on effectue une transition vers l'etat non satisfaisant sans mettre a jour la metrique de qualite de reference U. Selon un mode de realisation particulier de ('invention, lorsque l'etat de depart est l'etat non satisfaisant, on selectionne une nouvelle 15 configuration d'allocation de ressources radio a' et : On effectue une transition vers l'etat satisfaisant avec une probabilite de transition donnee et on met a jour la metrique de qualite de reference U avec la metrique de qualite mesuree u' et on met a jour la configuration d'allocation de reference a avec la 20 nouvelle configuration d'allocation a', On effectue une transition vers l'etat non satisfaisant avec une probabilite complementaire a ladite probabilite de transition sans mettre a jour la metrique de qualite de reference u ni la configuration d'allocation de reference a . 25 L'invention a aussi pour objet un programme d'ordinateur comportant des instructions pour ('execution du procede d'allocation de ressources radio selon ('invention, lorsque le programme est execute par un processeur. L'invention a aussi pour objet un support d'enregistrement lisible par un processeur sur lequel est enregistre un programme comportant des 30 instructions pour ('execution du procede d'allocation de ressources radio selon ('invention, lorsque le programme est execute par un processeur. 10 L'invention a aussi pour objet un dispositif communicant apte communiquer avec une pluralite d'autres dispositifs communicants au sein d'un reseau organise en groupes, le dispositif communiquant comprenant 5 des moyens configures pour mettre en oeuvre le procede d'allocation de ressources radio selon ['invention. D'autres caracteristiques et avantages de Ia presente invention apparaitront mieux a Ia lecture de Ia description qui suit en relation aux 10 dessins annexes qui representent : Les figures 1 a 4, quatre diagrammes illustrant la mise en oeuvre d'une premiere methode d'allocation de ressources radio par essaierreur selon ['art anterieur, Les figures 5 et 6, deux diagrammes illustrant Ia mise en oeuvre d'une 15 seconde methode d'allocation de ressources radio par essai-erreur selon ['art anterieur, Les figures 7 a 10, les quatre diagrammes des figures 1 a 4 adaptes pour mettre en oeuvre Ia methode d'allocation de ressources radio selon un premier mode de realisation de ('invention, 20 Les figures 11 et 12, les deux diagrammes des figures 5 et 6 adaptes pour mettre en oeuvre la methode d'allocation de ressources radio selon un second mode de realisation de ('invention, La figure 13, un organigramme decrivant les principales etapes de mise en oeuvre de Ia methode d'allocation de ressources radio selon 25 ('invention, La figure 14, un diagramme de transitions entre differents etats d'une machine a etats pour illustrer Ia premiere etape de mise en oeuvre de Ia methode d'allocation de ressources radio selon ['invention, La figure 15, un schema illustrant un reseau sans fil organise en 30 groupes de dispositifs communicants, chaque groupe comprenant au moins un dispositif communicant configure pour executer ['invention, 11 - La figure 16, un schema illustrant un dispositif communicant configure pour executer ['invention. On decrit en premier lieu une premiere methode d'allocation de 5 ressources radio par essai-erreur selon l'art anterieur, a I'appui des figures 1 a 4. Cette premiere methode correspond a celle decrite dans le document de reference [1] et est designee par Ia suite methode TEL de l'acronyme « Trial and Error Learning ». Le principe de cette methode est le suivant. On considere un reseau de nceuds mobiles ou fixes aptes a communiquer entre 10 eux par une liaison sans fil. Le reseau de nceuds est un reseau ad-hoc. Les nceuds sont organises en groupes de nceuds. Dans chaque groupe, un nceud maitre est en charge d'executer la methode d'allocation de ressources radio pour determiner les ressources radio que doivent utiliser l'ensemble des nceuds du groupe pour communiquer a chaque instant. Les ressources 15 radio peuvent etre des ressources frequentielles ou peuvent comprendre des ressources frequentielles et temporelles ou encore des ressources en terme de niveau de puissance de signaux ernis. Plus generalement, les modes de realisation de ('invention sont decrits par Ia suite en considerant que les ressources radio sont des canaux logiques, comme Mini en preambule de 20 ce texte. A chaque instant, le nceud maitre recoit une information concernant l'etat des liens de communication sans fil au sein du groupe. Cette information est, par exemple, revue sous la forme d'une metrique de qualite globale de l'etat des liens de communication. Par exemple, la metrique peut 25 etre egale au ratio du nombre de liens de communication en kat de fonctionner sur le nombre de liens de communication total au sein du groupe. Un lien de communication en kat de fonctionner est un lien de communication dont le rapport signal a bruit et/ou le rapport signal a interferences est suffisamment eleve pour permettre une communication. De 30 maniere generale, le niveau de bruit et/ou interferences acceptable pour qu'un lien soit en kat de fonctionner peut dependre de la qualite de service 12 visee et du type de service que I'on souhaite mettre en ceuvre sur ce lien. A chaque instant, les liens de communication du reseau sont perturbes par le bruit mais aussi par les interferences generees par d'autres nceuds du reseau qui communiquent simultanement avec les mernes ressources radio 5 ou des ressources proches. Un objectif de la methode est de determiner a chaque instant, Ia meilleure allocation de ressources radio pour chaque groupe pour maximiser le nombre de liens de communication en etat de fonctionner dans ('ensemble du reseau. Autrement dit, la methode vise a maximiser Ia somme des 10 metriques de qualite sur ('ensemble des groupes que comprend le reseau. A chaque instant, le nceud maitre execute un ensemble d'actions qui dependent de son etat au sein d'un diagramme d'etat specifique a Ia methode TEL. Selon cette methode, le diagramme d'etat comprend quatre etats : un etat dit satisfaisant C dans lequel le nceud se trouve Iorsque Ia 15 configuration d'allocation de ressources est satisfaisante, un etat dit non satisfaisant D dans lequel le nceud se trouve lorsque la configuration d'allocation de ressources n'est pas satisfaisante et deux etats de transition H et W entre l'etat satisfaisant C et l'etat non satisfaisant D. Le premier etat de transition H est un etat de transition dit « optimiste ». Le second etat de 20 transition W est un etat de transition dit « vigilant ». Sans perte de generalite, d'autres diagrammes d'etats sont envisageables, notamment des diagrammes d'etats qui ne comprennent que deux etats C,D ou qui comprennent plus de deux etats de transition. 25 Les figures 1 a 4 decrivent le diagramme d'etat de Ia methode TEL et les actions executees par le nceud maitre selon l'etat de depart dans lequel it se trouve et selon Ia valeur de Ia metrique de qualite revue. Selon les notations utilisees dans les figures 1 a 4, Ia metrique de qualite mesuree a chaque nouvel instant est notee u', la metrique de qualite 30 de reference stockee en memoire par le nceud maitre est notee ii, Ia nouvelle configuration d'allocation de ressources appliquee au groupe est notee a', la 13 configuration d'allocation de ressources de reference appliquee a l'instant precedent et stockee en memoire par le nceud maitre est notee a. Une configuration d'allocation de ressources correspond a un canal logique alloue au groupe pour communiquer. Les metriques de qualite ont une valeur 5 croissante avec le niveau global de fonctionnement des liens de communication au sein d'un groupe. Autrement dit, plus la valeur de la metrique de qualite est faible, plus l'etat des liens au sein du groupe est degrade. Au contraire, plus la valeur de la metrique de quake est &levee, plus l'etat des liens au sein du groupe est satisfaisant. Avantageusement, la 10 metrique de qualite peut etre normee de sorte a etre ramenee a une valeur comprise dans l'intervalle [0 ;1]. La figure 1 decrit les transitions possibles a partir de l'etat satisfaisant C. A partir de l'etat C, le nceud maitre va soit selectionner aleatoirement une 15 nouvelle configuration d'allocation de ressources a' differente de Ia configuration d'allocation de ressources de reference a, avec une probabilite predeterminee e, soit conserver la configuration d'allocation de ressources de reference a' = a avec la probabilite complementaire 1- E. La probabilite e peut etre constante ou variable pour reduire le temps 20 de convergence. Avantageusement, la valeur de la probabilite E est prise dans l'intervalle [0 ;1] a une valeur proche de 0, par exemple 10-1,10-2,10-3. De preference, la valeur de la probabilite e est prise a une valeur qui n'est pas trop proche de 1 pour ne pas rendre le systeme instable. Dans le premier cas (a' # a), la nouvelle metrique de qualite mesuree 25 u' est comparee a la metrique de qualite de reference. Si u'>U, le nocud maitre accepte la nouvelle configuration a' et Ia nouvelle metrique de qualite u' comme references avec une probabilite predeterminee q. L'etat final reste l'etat satisfaisant C. Avec Ia probabilite complementaire 1-q, la configuration de reference et la metrique de 30 reference ne sont pas modifiees. La probabilite q est par exemple calculee via les relations suivantes : q = eGOL'-.0 avec G (x) = x + y2. Les 14 constantes yi et y2 sont choisies de sorte que pour toute valeur x appartenant a l'intervalle [0,1], 0 ii, le nceud maitre effectue une transition vers le premier etat de transition H et ne modifie pas ses valeurs de reference (a, ii). Si u' U, le nceud maitre effectue une transition vers l'etat satisfaisant C et modifie sa metrique de qualite de reference par la nouvelle metrique 20 mesuree : u = u'. Si u' U, le nceud maitre effectue une transition vers le premier etat de transition dit « optimiste » H. Si u' 1.7/. le sont a present Iorsque if>ii + 8+ . De merne le test u' L + U. II s'ensuit qu'un des deux seuils est necessairement nul et, pour retrouver l'egalite 8+ + 8_ = L + U, on force alors le seuil non nul a decroitre. Par exemple, imaginons qu'a la suite d'une mise a jour, 8_ = 0, alors dans ce cas, on forcera 8+ = L + U. Cette procedure va necessairement reduire l'intervalle de tolerance autour de u qui 20 ne convient pas. Cela a pour consequence d'amener le groupe a changer de valeur de reference au cours des prochaines iterations de l'algorithme. Lorsque la memoire n contient peu de valeurs, les seuils de tolerance doivent avoir une valeur importante qui soit telle que le groupe soit peu 25 sensible aux variations de Ia valeur de Ia metrique de qualite. Cela permet tout d'abord d'obtenir des valeurs de seuils de tolerance plus grandes que les valeurs get afin de faire converger les seuils par valeurs superieures. Cela permet de plus, de stabiliser le systeme pour que les valeurs revues par chaque groupe soient stationnaires. En considerant les risques R1 et R2 dans 30 les estimateurs, les bornes obtenues seront naturellement tres larges lorsque la memoire est de petite taille. 24 On decrit a present plus en detail un exemple de realisation possible de l'etape 103. 5 Les seuils de tolerance sont calcules a partir de la memoire n ainsi que de la valeur de reference 7.1. a ('instant t courant. La maniere de calculer les seuils de tolerance peut dependre de ('information contenue dans la metrique de qualite mesuree. Nous presentons ici un exemple de realisation 00 la metrique de quake est calculee a partir de valeurs de fonctionnement 10 de chaque lien i du groupe. Un lien i est considers comme etant en etat de fonctionner si la valeur revue li est egale a 1 et est considers comme defaillant si li est egale a 0. A cause des phenomenes aleatoires presents dans le systerne, cette valeur de fonctionnement est une variable aleatoire. Plus precisement cette variable suit une loi de Bernoulli de parametre pi pour 15 chaque lien i. Avec une probabilite pi le lien fonctionne (1i = 1), sinon it ne fonctionne pas (I, = 0 ). Dans cet exemple, la metrique de qualite mesuree est definie par 1 u = Zli N1 est le nombre de liens de communication dans un groupe. Comme la valeur de Ia metrique de quake u est la somme de variables 20 aleatoires independantes, on peut obtenir sa distribution en effectuant une convolution des distributions des lois de chaque lien i qui dependent de leur probabilite p1. A partir de Ia distribution exacte de u, il est possible de calculer directement Ia valeur des bornes ideales que Ion note L* et U. Supposons que les valeurs exactes des probabilites pi sont connues pour chaque lien i. 25 Dans ce cas, il est possible de calculer la distribution exacte, notee pdf, de la variable u. Autrement dit, pour k E [1, N1], pdf (Ni) est la probabilite que k liens soient en etat de fonctionner. Dans Ia suite de ce raisonnement, P(k) = Ek 1 pdf (L) est la probabilite qu'au moins k liens soient en etat de 25 fonctionner. Nous cherchons la valeur de k telle que la probabilite que k liens soient en etat de fonctionner est plus petite que 1112 L* represente cette valeur. Le calcul formel s'effectue de la maniere suivante L* = argmax fick(k) 5. 71 Autrement dit, Ia valeur de L* est la valeur Ia plus grande de k telle que la 5 probabilite d'avoir k liens qui soient en etat de fonctionner est plus faible que R1 2 - Concernant I'autre borne U*, on effectue un raisonnement symetrique (a droite de la distribution). Nous cherchons le nombre de liens k tels que Ia 10 probabilite que plus de k liens soient en etat de fonctionner soit plus faible que 2 . La probabilite complementaire a P(k) donne 1- P(k)= pdf i=k+1 La probabilite 1- P(k) represente la probabilite que k+1 liens ou plus soient en etat de fonctionner (voir indice de depart de Ia somme). Par consequent, 15 cela sous estime la probabilite que au plus k liens soient en etat de fonctionner et peut amener de l'instabilite dans I'algorithme. Pour resoudre cet inconvenient, on utilise simplement la valeur 1- P(k - 1) et Ia formule pour calculer la borne U* devient U* = argmin fkl 1 - P(k - 1) 5_ N. 2 20 Autrement dit Ia valeur de U* est la valeur minimum de k telle que la probabilite que au plus k liens soient en etat de fonctionner, 1- P(k - 1), soit plus faible que ft. Ensuite, on obtient les seuils de tolerance ideaux en utilisant les relations 8*.s. = U* et 6*_ = u - L*. En calculant les seuils de tolerance de cette 26 fawn, (1 - R1)x100 % des valeurs de u sont comprises dans l'intervalle [ii - 61, u + 6*+] avec une probabilite egale a 1. Un probleme est que pour obtenir les valeurs de seuils de tolerance 5 (51,6*+), it est necessaire de connaitre les parametres pi de chaque lien i. Pour calculer ces parametres, on utilise la memoire n qui est de taille finie, par consequent seul un acces a des valeurs de pi estimees pi est possible. On en deduit que l'on ne peut pas directement calculer L* et U* et donc on ne peut obtenir les valeurs de tolerances (8!..,8*+). Seules des valeurs 10 intermediaires L et U sont accessibles par le calcul et permettront d'obtenir les seuils de tolerance intermediaires (5_,S+). Pour ce faire, la methode proposee est basee sur une estimation d'un intervalle de confiance autour des parametres pi. II est possible avec la memoire n, de construire un intervalle de confiance note Ci = [pF,pt] autour de pi tel que pi appartient 15 l'intervalle Ci pendant (1 - R2)x100 pourcent du temps. On explique par la suite comment utiliser cet intervalle afin de calculer les bornes estimees de L* et U* notees L et U apres avoir presents son calcul. 20 Soient xi = (4, M mesures des valeurs de l'etat d'un lien li, nous savons que Ia variable 344 = Ekxk suit une loi binomiale, par consequent : M P(3714 = 1c113i) = k) (Pi)k(1 - Pi)m-k On utilise ensuite une approche Bayesienne pour trouver Ia loi a priori sur les valeurs de pi. En utilisant la formule precedente, on deduit que Ia loi a priori sur pi est proportionnelle a (pi)k(1 - pi)m-k. Pour obtenir une loi, on fait en 25 sorte que cette formule soit egale a 1 lorsque l'on integre sur le support de pi ([0,1]). Cela donne : (M 1)! k .NM-k P(PilYM (M- k)! (Pi) ( 27 Cette formule est l'integrande de la fonction beta incomplete notee Bint(pi,k + 1, M - k + 1). On peut directement en deduire l'intervalle Ci avec la confiance souhaitee (1 - R2) de la maniere suivante R2 pi = arg pi f k + 1, M - k + 1) dx = -2 Et pit = arg f 1 p1 1Bint(x, k + 1, M - k + 1) dx = -211 2 5 Ensuite on explique comment obtenir les valeurs de U et L avec ces approximations sur les valeurs des parametres pi, c'est-à-dire avec uniquement I'intervalle Ci autour de pi. Si on considere trois variables aleatoires de Bernoulli Xi, X2 et X3 de 10 parametres 0.95. 15 La valeur de R2 est, quant a elle, dependante de ('estimation utilisee dans le calcul des seuils. Par exemple, dans l'exemple decrit ci-dessus, R2 peut etre choisi tel que 1- R2 "t: 0.6. La valeur 1- R2 peut se percevoir comme la confiance dans I'estimateur utilise. Si 1- R2 est tres faible c'est qu'il y a une grande confiance dans la capacite de I'estimateur a trouver le parametre 20 recherché, en revanche si 1- R2 est tres grand alors ('estimation est tres preventive vis-à-vis des valeurs recues. II faut alors attendre beaucoup d'echantillons avant voir les seuils converger. L'invention peut etre mise en oeuvre en tant que programme 25 d'ordinateur comportant des instructions pour son execution. Le programme d'ordinateur peut etre enregistre sur un support d'enregistrement lisible par un processeur. L'invention peut etre executee totalement ou partiellement par un nceud maitre d'un groupe de nceuds communicants au sein d'un reseau. Un nceud correspond a un dispositif comprenant des moyens pour 30 communiquer avec d'autres nceuds voisins, par exemple par le biais d'une liaison de communication radio. 30 La reference a un programme d'ordinateur qui, lorsqu'il est execute, effectue l'une quelconque des fonctions decrites precedemment, ne se limite pas a un programme d'application s'executant sur un ordinateur h6te unique. Au contraire, les termes programme d'ordinateur et logiciel sont utilises ici 5 dans un sens general pour faire reference a tout type de code informatique (par exemple, un logiciel d'application, un micro logiciel, un microcode, ou toute autre forme d'instruction d'ordinateur) qui peut etre utilise pour programmer un ou plusieurs processeurs pour mettre en oeuvre des aspects des techniques decrites ici. Les moyens ou ressources informatiques 10 peuvent notamment etre distribues ("Cloud computing"), eventuellement selon des technologies de pair-a-pair. Le code logiciel peut etre execute sur n'importe quel processeur approprie (par exemple, un microprocesseur) ou cur de processeur ou un ensemble de processeurs, qu'ils soient prevus dans un dispositif de calcul unique ou repartis entre plusieurs dispositifs de 15 calcul (par exemple tels qu'eventuellement accessibles dans l'environnement du dispositif). Le code executable de chaque programme permettant au dispositif programmable de mettre en oeuvre les processus selon l'invention, peut etre stock& par exemple, dans le disque dur ou en memoire morte. De maniere generale, le ou les programmes pourront etre charges dans un des 20 moyens de stockage du dispositif avant d'être executes. L'unite centrale peut commander et diriger ('execution des instructions ou portions de code logiciel du ou des programmes selon l'invention, instructions qui sont stockees dans le disque dur ou dans la memoire morte ou bien dans les autres elements de stockage precites. 25 Alternativement, l'invention peut aussi etre mise en oeuvre au moyen d'un processeur qui peut etre un processeur generique, un processeur specifique, un circuit integre propre a une application (connu aussi sous le nom anglais d'ASIC pour « Application-Specific Integrated Circuit ») ou un 30 reseau de portes programmables in situ (connu aussi sous le nom anglais de FPGA pour « Field-Programmable Gate Array »). Chaque nceud du reseau 31 maille ainsi que requipement externe associe au nceud racine peut utiliser, pour mettre en oeuvre l'invention, un ou plusieurs circuits electroniques dedies ou un circuit a usage general. La technique de l'invention peut se realiser sur une machine de calcul reprogrammable (un processeur ou un 5 micro controleur par exemple) executant un programme comprenant une sequence d'instructions, ou sur une machine de calcul dediee (par exemple un ensemble de portes logiques comme un FPGA ou un ASIC, ou tout autre module materiel). 10 L'invention s'applique a tout reseau maille comprenant une pluralite de nceuds qui sont des dispositifs communicants mobiles ou fixes, qui peuvent etre localises, par exemple, dans des vehicules, des telephones intelligents ou tout type de terminal. 15 La figure 15 represente schematiquement un reseau ad-hoc comprenant une pluralite de terminaux communicants organises en groupes. Dans chaque groupe G, au moins un terminal N_M endosse le role de nceud maitre et est configure pour mettre en oeuvre le procede selon l'invention dans le but d'allouer des ressources de communication, par exemple des 20 ressources frequentielles, a ['ensemble des terminaux N_M, N_1,N_2,N_3,N_4 du groupe G. A cet effet, comme illustre sur la figure 16, le terminal N_M comprend les equipements necessaires a la mise en oeuvre de l'invention. II comprend notamment un dispositif MES pour mesurer, recevoir ou calculer une 25 metrique de quake des liens de communication entre terminaux du groupe. Par exemple la metrique de quake peut etre calculee a partir d'informations transmises par chaque terminal du groupe G en direction du terminal maitre N_M. Ces informations peuvent comprendre des mesures de rapport signal a bruit sur les liaisons de communication. 30 Le terminal N_M comprend egalement un calculateur CALC ou tout dispositif equivalent pour executer l'invention et un equipement d'allocation 32 ALLOC de ressources radio qui regoit a chaque instant Ia configuration d'allocation de ressources determinee par le calculateur et Ia communique a une entite exterieure au reseau en charge du controle d'allocation de ressources ou Ia communique directement aux nceuds du groupe G pour 5 qu'ils utilisent les ressources autorisees selon Ia configuration determinee, pour communiquer entre eux. 33 References [1] L. Rose, S. M. Perlaza, C. J. Le Martret, M. Debbah, "Self-organization in decentralized networks: a trial and error learning approach", IEEE 5 Transactions on Wireless communications, vol 13, no. 1, pp. 268-279, January 2014. [2] L. Rose, S. M. Perlaza, C. J. Le Martret, and M. Debbah, "Achieving pareto optimal equilibria in energy efficient clustered ad hoc networks," in 2013 IEEE International Conference on communications (ICC), June 2013, 10 pp. 1491-1495. [3] C. Ramesh, M. Schmitt, and J. Lygeros, "Distributed learning in the presence of disturbances," in 2016 European Control Conference (ECC), June 2016, REVENDICATIONS1. Procede d'allocation de ressources radio au sein d'un reseau de dispositifs communicants (N 1,N 2,N 3,N 4,N M) organises en groupes (G), le procede comprenant les etapes suivantes executees iterativement par au moins un dispositif communiquant (N_M) de chaque groupe (G) : Selectionner (100) une nouvelle configuration d'allocation de ressources radio a' a appliquer aux dispositifs du groupe, avec une probabilite de selection donnee, ou appliquer une configuration d'allocation de reference a, avec une probabilite complementaire ladite probabilite de selection, Mesurer (101) une metrique u' de qualite globale des liens de communication entre dispositifs du groupe (G), Comparer (102) la metrique de qualite mesuree u' avec une metrique de qualite de reference u, la comparaison incluant la prise en compte d'un intervalle de tolerance [171 - 5_, u + 5÷] autour de la metrique de qualite de reference, I'intervalle de tolerance etant Mini par un seuil de tolerance bas S._ et un seuil de tolerance haut 6+, En fonction de ladite comparaison, effectuer (103), au sein d'un diagramme d'etats ayant un nombre d'etats predetermine, une transition depuis un etat de depart vers un etat d'arrivee, En fonction de l'etat d'arrivee, mettre a jour ou non la metrique de qualite de reference u avec la metrique de qualite mesuree u' et/ou mettre a jour ou non la configuration d'allocation de reference a avec la nouvelle configuration d'allocation a', En fonction de ladite transition et de ladite comparaison, mettre a jour (104) une memoire contenant au moins une metrique de quake mesuree de maniere a ce que les valeurs contenues dans la memoire soient stationnaires, Determiner une borne inferieure et une borne superieure de la distribution des metriques de qualite de sorte qu'un pourcentage donne de valeurs sont comprises entre la borne inferieure et la borne superieure, 5 Determiner (105) le seuil de tolerance haut 5+ a partir de la borne superieure et le seuil de tolerance bas 5_ a partir de la borne inferieure. 2. Procede d'allocation de ressources radio selon la revendication 1 dans 10 lequel la mise a jour (104) de la memoire comprend les &apes suivantes : - Si une nouvelle configuration d'allocation de ressources radio est selectionnée, - Si la metrique de qualite de reference est mise a jour, reinitialiser la memoire avec la metrique de qualite mesuree 15 (A2), - Sinon, ne pas mettre a jour la memoire (A1), Si la configuration d'allocation de reference est appliquee, - Si la metrique de qualite mesuree est comprise dans I'intervalle de tolerance, ajouter la metrique de qualite 20 mesuree a la memoire (A3), - Sinon, ^ Si la metrique de qualite de reference est mise a jour, reinitialiser la memoire avec la metrique de qualite mesuree (A2), 25 ^ Sinon, ne pas mettre a jour la memoire (A1). 3. Procede d'allocation de ressources radio selon I'une des revendications precedentes dans lequel la metrique de qualite u' d'un groupe est egale au rapport entre un nombre de liens de communication en etat de 30 fonctionner dans le groupe et le nombre de liens de communication total dans le groupe. 36 4. Procede d'allocation de ressources radio selon l'une des revendications precedentes dans lequel les ressources radio sont des ressources frequentielles. 5 5. Procede d'allocation de ressources radio selon l'une des revendications precedentes dans lequel le diagramme d'etats comprend un etat satisfaisant (C) et un etat non satisfaisant (D). 10 6. Procede d'allocation de ressources radio selon Ia revendication 5 dans lequel, lorsque l'etat de depart est l'etat satisfaisant (C) et qu'une nouvelle configuration d'allocation de ressources radio a' est selectionnee : on effectue une transition vers l'etat satisfaisant (C) avec une probabilite de transition dependante de la metrique de qualite 15 mesuree u' et on met a jour la metrique de qualite de reference ft avec la metrique de qualite mesuree u' et on met a jour la configuration d'allocation de reference a avec la nouvelle configuration d'allocation a', on effectue une transition vers l'etat non satisfaisant (D) avec une 20 probabilite complementaire a ladite probabilite de transition. 7. Procede d'allocation de ressources radio selon l'une des revendications 5 ou 6 dans lequel, lorsque l'etat de depart est l'etat satisfaisant (C) et qu'on applique au groupe la configuration d'allocation de ressources radio 25 de reference a : - Si la metrique de qualite mesuree u' est comprise dans l'intervalle de tolerance [CI - 6_, ii + 6+] autour de la metrique de qualite de reference r.t, on effectue une transition vers l'etat satisfaisant (C), Si la metrique de qualite mesuree u' n'est pas comprise dans 30 l'intervalle de tolerance [11 - 5_, ii + 6+] : - on effectue une transition vers retat satisfaisant (C) avec une probabilite de transition dependante de Ia metrique de 37 qualite mesuree u' et on met a jour la metrique de qualite de reference u avec la metrique de qualite mesuree u', - on effectue une transition vers l'etat non satisfaisant (D) avec une probabilite complementaire a ladite probabilite de 5 transition. 8. Procede d'allocation de ressources radio selon I'une des revendications 5 a 7 dans lequel, lorsque l'etat de depart est l'etat non satisfaisant (D), on selectionne une nouvelle configuration d'allocation de ressources radio a' 10 et : on effectue une transition vers l'etat satisfaisant (C) avec une probabilite de transition dependante de Ia metrique de qualite mesuree u' et on met a jour Ia metrique de qualite de reference u avec Ia metrique de qualite mesuree u' et on met a jour la 15 configuration d'allocation de reference a avec la nouvelle configuration d'allocation a', on effectue une transition vers l'etat non satisfaisant (D) avec une probabilite complementaire a ladite probabilite de transition. 20 9. Procede d'allocation de ressources radio selon la revendication 5 dans lequel le diagramme d'etats comprend en outre au moins un premier etat de transition (H) et un second etat de transition (W). 25 10. Procede d'allocation de ressources radio selon la revendication 9 dans lequel, lorsque l'etat de depart est l'etat satisfaisant (C) et qu'une nouvelle configuration d'allocation de ressources radio a' est selectionnee : - Si la metrique de qualite mesuree u' est inferieure ou egale a la somme de la metrique de qualite de reference u et du seuil de 30 tolerance haut 8+, on effectue une transition vers l'etat satisfaisant (C) sans mettre a jour ni la metrique de qualite de reference u ni la configuration d'allocation de reference a , 38 - Si la metrique de qualite mesuree u' est superieure a la somme de la metrique de qualite de reference u et du seuil de tolerance haut 8+ : - on effectue une transition vers l'etat satisfaisant (C) avec 5 une probabilite de transition donnee et on met a jour la metrique de qualite de reference u avec la metrique de qualite mesuree u' et on met a jour la configuration d'allocation de reference a avec la nouvelle configuration d'allocation a', 10 - on effectue une transition vers l'etat satisfaisant (C) avec une probabilite complementaire a ladite probabilite de transition sans mettre a jour ni la metrique de qualite de reference u ni la configuration d'allocation de reference a. 15 11. Procede d'allocation de ressources radio selon I'une des revendications 9 ou 10 dans lequel, lorsque l'etat de depart est l'etat satisfaisant (C) et qu'on applique au groupe la configuration d'allocation de ressources radio de reference a: Si la metrique de qualite mesuree u' est comprise dans I'intervalle 20 de tolerance - 8_, u + 8+] autour de la metrique de qualite de reference U., on effectue une transition vers l'etat satisfaisant (C) sans mettre a jour la metrique de qualite de reference u, Si la metrique de qualite mesuree u' est superieure a la somme de la metrique de qualite de reference u et du seuil de tolerance haut 25 8+, on effectue une transition vers le premier etat de transition (H) sans mettre a jour la metrique de qualite de reference ft, - Si la metrique de qualite mesuree u' est inferieure a la difference entre la metrique de qualite de reference ft et le seuil de tolerance bas 6_, on effectue une transition vers le second etat de transition 30 (W) sans mettre a jour la metrique de qualite de reference u. 39 12. Procede d'allocation de ressources radio selon l'une des revendications 9 a 11 dans lequel, lorsque l'etat de depart est le premier etat de transition (H), on applique la configuration d'allocation de ressources radio de reference a et : 5 Si la metrique de qualite mesuree u' est comprise dans I'intervalle de tolerance - 6_, u + 6+] autour de la metrique de qualite de reference U, on effectue une transition vers l'etat satisfaisant (C) sans mettre a jour Ia metrique de qualite de reference U, Si la metrique de qualite mesuree u' est superieure a Ia somme de 10 la metrique de qualite de reference U et du seuil de tolerance haut 84., on effectue une transition vers l'etat satisfaisant (C) et on met a jour la metrique de qualite de reference U avec Ia metrique de qualite mesuree u', - Si la metrique de qualite mesuree u' est inferieure a la difference 15 entre la metrique de qualite de reference U et le seuil de tolerance bas 6_, on effectue une transition vers le second etat de transition (W) sans mettre a jour la metrique de qualite de reference u . 13. Procede d'allocation de ressources radio selon l'une des revendications 9 20 a 12 dans lequel, lorsque l'etat de depart est le second etat de transition (W), on applique la configuration d'allocation de ressources radio de reference a et : Si la metrique de qualite mesuree est comprise dans I'intervalle de tolerance [U - 6_, u + 6+] autour de la metrique de qualite de 25 reference U, on effectue une transition vers l'etat satisfaisant (C) sans mettre a jour la metrique de qualite de reference U, Si la metrique de qualite mesuree u' est superieure a la somme de la metrique de qualite de reference U et du seuil de tolerance haut 6+, on effectue une transition vers le premier etat de transition (H) 30 sans mettre a jour la metrique de qualite de reference U, Si la metrique de qualite mesuree u' est inferieure a la difference entre la metrique de qualite de reference U et le seuil de tolerance bas 6_, on effectue une transition vers l'etat non satisfaisant (D) sans mettre a jour la metrique de qualite de reference U. 5 14. Procede d'allocation de ressources radio selon I'une des revendications 9 a 13 dans lequel, lorsque l'etat de depart est l'etat non satisfaisant (D), on selectionne une nouvelle configuration d'allocation de ressources radio a' 10 et : On effectue une transition vers l'etat satisfaisant (C) avec une probabilite de transition donnee et on met a jour la metrique de qualite de reference 5 avec Ia metrique de qualite mesuree u' et on met a jour la configuration d'allocation de reference a avec la 15 nouvelle configuration d'allocation a', On effectue une transition vers l'etat non satisfaisant (D) avec une probabilite complementaire a ladite probabilite de transition sans mettre a jour Ia metrique de qualite de reference u ni la configuration d'allocation de reference a . 20 15. Programme d'ordinateur comportant des instructions pour ('execution du procede d'allocation de ressources radio selon ('une quelconque des revendications precedentes, lorsque le programme est execute par un processeur. 25 16.Support d'enregistrement lisible par un processeur sur lequel est enregistre un programme comportant des instructions pour ('execution du procede d'allocation de ressources radio selon ('une quelconque des revendications 1 a 14, lorsque le programme est execute par un 30 processeur. 41 17. Dispositif communicant (N_M) apte a communiquer avec une pluralite d'autres dispositifs communicants (N_1,N_2,N_3,N_4) au sein d'un reseau organise en groupes (G), le dispositif communiquant comprenant des moyens configures pour mettre en oeuvre le procede d'allocation de 5 ressources radio selon I'une quelconque des revendications 1 a 14.