Brevet FR3072851A1 — publié le 20190426

PROCÉDÉ D'ALLOCATION DE RESSOURCES DE TRANSMISSION À APPRENTISSAGE PAR RENFORCEMENT DESCRIPTION DOMAINE TECHNIQUE Le domaine de l'invention est celui des systèmes de télécommunication multi-accès offrant une pluralité de ressources de transmission. L'invention concerne la gestion des ressources de transmission et porte plus particulièrement sur un ordonnancement mis en oeuvre en deux étapes découplées avec tout d'abord un ordonnancement dans le domaine temporel pour sélectionner un groupe de flux de données sur la base de besoins en termes de qualité de service, typiquement les flux de données plus urgents, puis un ordonnancement dans le domaine fréquentiel prenant en considération l'état du canal de transmission pour allouer les ressources radio aux flux de données du groupe sélectionné. ÉTAT DE LA TECHNIQUE ANTÉRIEURE Les réseaux mobiles de 5ème génération seront caractérisés par la présence de multiples services dont les besoins seront extrêmement hétérogènes. Par exemple les services de Haut Débit mobile extrême (ou Extreme Mobile Broadband) nécessitent des débits de données très importants, les applications Ultra-Fiables à Faible latence (ou Ultra-reliable Low latency) nécessitent de très faibles latences et de très faibles taux d'erreur, et les services de communication massive de type machine (pour Massive Machine-type Communication) vont imposer la présence d'une très importante densité de connexions d'utilisateurs. Ces différents besoins sont souvent contradictoires et l'optimisation conjointe de ces besoins est un problème difficile à résoudre. La technique d'accès OFDMA (Orthogonal Frequency Division Multiple Access) permet une allocation de la ressource radio à granularité fine où chaque unité de ressource RB (Resource Block) peut être allouée et modulée de façon adaptative pour exploiter et tirer avantage des diversités fréquentielles de chaque utilisateur. Pour 2 répondre aux besoins hétérogènes en termes de Qualité de Servive (QoS pour Quality of Service) des différents services d'un réseau de 5ème génération, une gestion flexible de la ressource radio (RRM pour Radio Resource Management) est nécessaire. La gestion de la ressource radio exploite un ordonnanceur de paquets 5 qui est en charge de partager la ressource radio entre les différents utilisateurs actifs à chaque intervalle temporel de transmission. Cet ordonnanceur dispose d'un ensemble de règles d'ordonnancement utilisées pour contrôler les paramètres tels que la puissance de transmission, le schéma de codage et modulation et la bande passante allouée. L'objectif est d'utiliser aussi efficacement que possible les ressources radio pour augmenter 10 l'efficacité spectrale, tout en garantissant aux utilisateurs le niveau de service requis par chaque demande de trafic. On peut distinguer les quatre types de règles d'ordonnancement suivants. - Règles de type « Canal inconnu / QoS inconnue ». Ces règles sont caractérisées 15 par une implémentation très simple ne nécessitant ni connaissance d'un indicateur de qualité du canal (COI pour Channel Quality Indicator) ni mesures de QoS. Par exemple, un ordonnanceur de type Round-Robin alloue une bande passante identique à chaque utilisateur actif ; - Règles de type « Canal inconnu / QoS connue ». Ces règles visent à satisfaire des 20 besoins en termes de QoS sans prendre en compte les informations COI. Par exemple, la règle EDF (pour Earliest to Deadline First) attribue une priorité d'autant plus grande à un paquet que son échéance d'envoi est proche, sans aucune considération de l'état du canal ; - Règles de type « Canal connu / QoS inconnue ». Ces règles fournissent un bon 25 compromis entre performance et complexité en prenant en considération la diversité des utilisateurs. Leur performance reste toutefois soumise à la fiabilité des informations COI. On peut notamment citer la règle MCI (pour Maximum Carrier to Interference) qui vise à maximiser le débit total instantané ; - Règles de type « Canal connu / QoS connu ». Ces règles prennent en considération à la fois des informations QoS et COI. On peut notamment citer les règles 3 PF-BF (pour Proportional Fair - Barrier Function), PF-EXP (pour Proportional Fair - EXPonential) et PF-OPLF (pour Proportional Fair - Opportunistic Packet Loss Fair) qui s'attachent respectivement à garantir un débit, à minimiser les délais et à réduire le taux de perte de paquet. 5 Aucune de ces règles ne peut être considérée comme la solution la plus appropriée pour toutes les conditions de réseau et tous les besoins de QoS. Pour répondre à des contraintes de délai, un ordonnancement en deux étapes découplées a été proposé avec tout d'abord un ordonnancement dans le domaine temporel pour sélectionner un groupe de paquets sur la base de besoins en termes de qualité de service, 10 typiquement les paquets plus urgents, puis un ordonnancement dans le domaine fréquentiel prenant en considération l'état du canal de transmission pour allouer les ressources radio aux paquets du groupe sélectionné. Un tel ordonnancement est par exemple connu des brevets EP 2 148 478 B1 et EP 2 936 908 B1. Mais ces solutions d'ordonnancement ne permettent pas de différentier de multiples catégories de trafic 15 ayant différents besoins en termes de QoS. EXPOSÉ DE L'INVENTION L'invention a pour objectif de proposer un procédé d'ordonnancement de paquets appartenant à une pluralité de catégories de paquets dans un système de télécommunication multi-accès partageant une pluralité de ressources de transmission, 20 capable de traiter des flux de données hétérogènes tout en étant apte à offrir des performances optimales en termes de satisfaction de contraintes QoS. A cet effet, l'invention propose un procédé qui comprend, pour un état du système de télécommunication multi-accès, la détermination, par itérations d'un apprentissage par renforcement, d'un plan d'allocation de ressource venant maximiser 25 une somme de récompenses. Chaque itération de l'apprentissage par renforcement comprend : - une allocation des ressources de transmission aux flux de données selon un plan d'allocation de ressources ; - la transmission des paquets au moyen des ressources de transmission allouées ; 4 - pour chacune des catégories de flux de données, le calcul d'au moins un indicateur de performance de transmission de chacun des flux de données de la catégorie, et la comparaison, pour chacun des flux de données de la catégorie, de l'au moins un indicateur de performance de transmission calculé à un seuil représentatif d'une 5 contrainte de qualité de service portant sur l'au moins un indicateur de performance de transmission pour la catégorie, et - la détermination d'une récompense en fonction du résultat de ladite comparaison pour chacun des flux de données de chacune des catégories. Certains aspects préférés mais non limitatifs de ce procédé sont les 10 suivants : - le plan d'allocation de ressources comprend une règle de hiérarchisation et au moins une première et une seconde règle d'ordonnancement, l'allocation des ressources de transmission comprenant deux étapes consistant en : o un ordonnancement dans le domaine temporel réalisé par un classificateur 15 temporel configuré pour hiérarchiser les catégories de flux de données selon la règle de hiérarchisation en au moins une catégorie prioritaire et une catégorie secondaire ; et o un ordonnancement dans le domaine fréquentiel réalisé par un classificateur fréquentiel configuré pour : 20 - ordonnancer les flux de données de la catégorie prioritaire selon la première règle d'ordonnancement et allouer des ressources de transmission aux flux de données de la catégorie prioritaire ainsi ordonnancés; et - en cas de ressources restantes, ordonnancer les flux de données de 25 la catégorie secondaire selon la seconde règle d'ordonnancement et allouer des ressources de transmission restantes aux flux de données de la catégorie secondaire ainsi ordonnancés. - chaque itération de l'apprentissage par renforcement comprend: 5 o selon une probabilité Pa, une sélection d'exploitation consistant à sélectionner le plan d'allocation de ressources venant maximiser la somme des récompenses à ce stade des itérations ; et o selon une probabilité 13,2,, une sélection d'exploration consistant à 5 sélectionner un plan d'allocation de ressources différent du plan d'allocation de ressources venant maximiser la somme des récompenses à ce stade des itérations. l'au moins un indicateur de performance de transmission est l'un parmi un délai de transmission, un débit de transmission et un taux de perte de transmission. 10 BRÈVE DESCRIPTION DES DESSINS D'autres aspects, buts, avantages et caractéristiques de l'invention apparaîtront mieux à la lecture de la description détaillée suivante de formes de réalisation préférées de celle-ci, donnée à titre d'exemple non limitatif, et faite en référence aux dessins annexés sur lesquels : 15 - la figure 1 est un schéma illustrant un procédé d'ordonnancement de paquets exploitant une table de correspondance (LUT pour look up table) dont le contenu résulte de la mise en oeuvre d'un apprentissage par renforcement ; - la figure 2 est un schéma illustrant un mode de réalisation possible de l'apprentissage par renforcement mettant en oeuvre un compromis 20 exploitation/exploration. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS L'invention se place dans le cadre d'un système de télécommunication multi-accès où une pluralité d'utilisateurs et/ou d'applications ont accès à des ressources de transmission communes, et dans lequel, pour chaque accès, les données sont 25 transmises sous forme de paquets. Un exemple typique d'utilisation de l'invention est celui d'un système OFDMA dans lequel la bande passante disponible est divisée en NRB unités de ressource RB (Resource Block) où une unité de ressource RB représente la 6 quantité minimale de ressources fréquentielles qu'une station de base peut allouer à chaque intervalle de transmission (TTI pour Transmission Time interval). Dans le cadre de l'invention, le système de télécommunication offre ses ressources de transmission à P catégories de flux de données (dans ce qui suit un flux de 5 données est associé à un utilisateur). On note ainsi Tc = {1 ...P} l'ensemble des catégories de flux de données. Chaque catégorie p E Tc est caractérisée par un ensemble d'utilisateurs actifs UEp = In. /pl (i.e. un ensemble de flux de données) et un ensemble d'objectifs et d'exigences spécifiques en termes de QoS, noté Op = fi N0}, cet ensemble Op comprenant par exemple un débit garanti GBR (Guaranteed Bit Rate), un 10 délai, un taux de perte de paquets PLR (Packet Loss Rate). Afin d'ordonnancer de manière efficace des catégories de flux de données hétérogènes présentant différentes priorités, l'invention exploite un planificateur configuré pour, à chaque intervalle temporel de transmission, sélectionner un plan d'allocation de ressources et réaliser une allocation des NRB ressources de 15 transmission aux flux de données conformément au plan d'allocation de ressources sélectionné. Dans un mode de réalisation privilégié représenté sur la figure 1, le planificateur est configuré pour réaliser un ordonnancement en deux étapes découplées, avec tout d'abord une étape d'ordonnancement dans le domaine temporel TD puis une étape d'ordonnancement dans le domaine fréquentiel FD. Comme cela sera détaillé par la 20 suite, le plan d'allocation des ressources comprend dans ce cas une règle de hiérarchisation et au moins une première et une seconde règle d'ordonnancement. A un intervalle de transmission TTI t, le système de télécommunication présente un état courant s[t] et chaque catégorie de flux de données p E Tc présente un état courant s[t]. L'ordonnancement dans le domaine temporel est réalisé par un 25 classificateur temporel CT configuré pour réaliser la sélection d'une règle de hiérarchisation et la hiérarchisation des catégories de flux de données selon la règle de hiérarchisation sélectionnée en au moins une catégorie prioritaire et une catégorie secondaire. Le classificateur temporel CT vient ainsi hiérarchiser les catégories de flux de données en fonction de leurs états courants et les fait suivre de manière itérative à un 7 classificateur fréquentiel CF, de la plus prioritaire à la moins prioritaire, pour définir l'ordonnancement dans le domaine fréquentiel. Une stratégie possible de hiérarchisation consiste à déterminer l'ordonnancement des flux de données selon un niveau de priorité («priority level ») qui 5 correspond à chaque flux, comme défini par exemple dans le tableau 6.1.7 du 3GPP Technical Specification Group Services and System Aspects, « TS 23.203, Policy and charging control architecture, » (Release 14), V14.4.0, Juin 2017. Une autre stratégie possible est la hiérarchisation des flux de données donnant la priorité aux flux GBR (flux à débit garanti, GBR désignant un « Guaranteed Bit Rate ») vis-à-vis des flux non-GBR (flux à 10 débit non garanti). Dans l'exemple de la figure 1, c'est la catégorie p qui est sélectionnée en tant que catégorie prioritaire. L'ordonnancement dans le domaine fréquentiel est réalisé par le classificateur fréquentiel CF qui exploite en entrée l'état des utilisateurs 15 ts" [t], ...,sp jp MI de la catégorie sélectionnée p. Le classificateur fréquentiel est configuré pour réaliser : o la sélection d'une première règle d'ordonnancement, la réalisation d'un ordonnancement des flux de données de la catégorie prioritaire selon la première règle d'ordonnancement sélectionnée et une allocation de ressources aux flux de 20 données de la catégorie prioritaire ordonnés conformément au premier ordonnancement ; et o en cas de ressources restantes, la sélection d'une seconde règle d'ordonnancement, la réalisation d'un ordonnancement des flux de données de la catégorie secondaire selon la seconde règle d'ordonnancement sélectionnée et une 25 allocation des ressources restantes aux flux de données de la catégorie secondaire ordonnés selon le second ordonnancement. Le classificateur fréquentiel CF sélectionne ainsi la règle d'ordonnancement la plus appropriée % parmi NR règles possibles (up E 11 = f0,1, ...,NR}) pour améliorer la QoS des flux de données de la catégorie prioritaire p. Ici 30 uk = 0 indique que la catégorie k ne fait pas l'objet d'un ordonnancement du fait d'une 8 absence de ressources restantes. Des exemples de règles d'ordonnancement ont été donnés dans la partie introductive. L'application de la règle d'ordonnancement la plus appropriée up fournit pour chaque utilisateur ip E UEp de la catégorie sélectionnée p sa priorité iljup,ip 5 dans le schéma d'allocation de ressources. L'allocation de ressource AR est réalisée de manière itérative en venant allouer une unité de ressource RB disponible à l'utilisateur de plus haute priorité, soit jusqu'à ce qu'il n'y ait plus de ressources disponibles (i.e. toutes les unités de ressource RB ont été allouées) soit jusqu'à ce tous les utilisateurs ip E UEp de la catégorie prioritaire p aient été servis (i.e. il n'y a plus de données à transmettre 10 pour cette catégorie de flux de données). Dans ce dernier cas, s'il y a des ressources restantes, le classificateur temporel CT fait passer le flux de données catégorie secondaire de plus haut niveau au classificateur fréquentiel CF. Et ainsi de suite tant que toutes les unités de ressource RB n'ont pas été allouées ou que tous les utilisateurs de toutes les catégories n'ont pas été servis. On note J = Ut], } l'ensemble qui décrit le 15 nombre d'unités de ressource RB alloué à chaque TTI t à chacune des catégories p E T. Dans le cadre de l'invention, le planificateur est configuré pour interroger une table de correspondance LUT afin d'identifier, à partir de l'état courant s[t] du système de télécommunication multi-accès, le plan d'allocation de ressources à mettre en oeuvre. Dans le cadre du mode de réalisation privilégié, l'un et/ou l'autres des 20 classificateurs temporel CT et fréquentiel CF sont configurés pour réaliser, à chaque intervalle temporel de transmission TTI, l'interrogation de la table de correspondance LUT pour identifier, à partir de l'état courant s[t] du système de télécommunication multiaccès, respectivement la règle de hiérarchisation et/ou la première règle d'ordonnancement up (et le cas échéant la ou les règles d'ordonnancement applicables à 25 la ou les catégories secondaires faisant l'objet d'une allocation de ressources) à sélectionner. L'invention porte selon un premier aspect sur la création de la table de correspondance. Elle concerne plus particulièrement un procédé de détermination d'une allocation de ressources à des paquets appartenant à une pluralité de catégories de flux 30 de données dans un système de télécommunication multi-accès partageant une pluralité 9 de ressources de transmission, ce procédé comprenant, pour un état du système de télécommunication multi-accès, la détermination, par itérations d'un apprentissage par renforcement, d'une allocation de ressource venant maximiser une somme de récompenses. 5 Chaque itération de l'apprentissage par renforcement comprend : - une allocation des ressources de transmission aux flux de données selon un plan d'allocation de ressources ; - la transmission des paquets au moyen des ressources de transmission allouées; - pour chacune des catégories de flux de données, le calcul d'au moins un indicateur 10 de performance de transmission (KPI pour Key Performance indicator) de chacun des flux de données de la catégorie, et la comparaison, pour chacun des flux de données de la catégorie, d'au moins un indicateur de performance de transmission calculé (noté à un seuil (noté )1),0 ) représentatif d'une contrainte de qualité de service QoS portant sur au moins un indicateur de performance de transmission pour la catégorie, 15 et - la détermination d'une récompense en fonction du résultat de ladite comparaison pour chacun des flux de données de chacune des catégories. Ainsi, pour permettre de satisfaire les contraintes en termes de QoS de catégories hétérogènes de flux de données, l'invention utilise un apprentissage par 20 renforcement pour apprendre le plan d'allocation de ressources optimal à mettre en oeuvre par le planificateur. Dans le cadre du mode de réalisation privilégié, l'apprentissage par renforcement permet de déterminer la règle de hiérarchisation et/ou les règles d'ordonnancement optimales à mettre en oeuvre respectivement par le classificateur temporel qui hiérarchise de manière dynamique les différentes catégories 25 de flux de données et par le classificateur fréquentiel qui sélectionne la règle d'ordonnancement la plus appropriée pour allouer des ressources de transmission à la catégorie de flux de données activée (i.e. d'abord la catégorie prioritaire puis les catégories secondaires selon la hiérarchisation réalisée par le classificateur temporel). 10 Dans un mode de réalisation, les deux classificateurs temporel et fréquentiel exploitent une table de correspondance issue d'un apprentissage par renforcement. Dans un autre mode de réalisation, seul le classificateur fréquentiel 5 exploite une table de correspondance issue d'un apprentissage par renforcement. Cet apprentissage permet d'apprendre la stratégie la plus appropriée pour allouer des ressources de transmission aux différentes catégories de flux de données et ainsi de déterminer la règle d'ordonnancement à appliquer à une catégorie donnée pour optimiser la QoS. Dans un tel cas de figure, le classificateur temporel peut être 10 relativement simple, et mettre par exemple en oeuvre une stratégie de type Round-Robin ou une stratégie basée sur des priorités fixes pour les catégories de flux de données (de sorte qu'une première catégorie n'est traitée par le classificateur fréquentiel que lorsque les catégories de priorité supérieure n'ont pas de données à transmettre). Dans encore un autre mode de réalisation, seul le classificateur 15 temporel exploite une table de correspondance issue d'un apprentissage par renforcement. Cet apprentissage permet, pour un état courant du système s[t], de déterminer la règle de hiérarchisation des catégories de flux de données la plus appropriée. Dans un tel cas de figure, le classificateur fréquentiel peut être relativement simple, et mettre par exemple en oeuvre la stratégie MCI ou la stratégie EDF. 20 On décrit dans ce qui suit la réalisation de l'apprentissage par renforcement dans le cadre du mode de réalisation privilégié où les deux classificateurs exploitent une table de correspondance issue d'un tel apprentissage. D'une manière générale, l'apprentissage par renforcement a pour objectif d'apprendre, à partir d'expériences, ce qu'il convient de faire en différentes 25 situations, de façon à optimiser une récompense quantitative au cours du temps. A chaque instant t, un contrôleur observe l'état complet du système s et réalise une action donnée a. A l'instant t+1, le contrôleur observe un nouvel état s' and perçoit une récompense r qui évalue l'optimalité de l'action précédente. Le contrôleur passe par un ensemble de transitions (i.e. d'un état à un autre) et explore toutes les paires état-action 30 possibles jusqu'à déterminer le comportement décisionnel (appelé stratégie ou politique, 11 et qui est une fonction associant à l'état courant l'action à exécuter) optimal en ce sens qu'il maximise la somme des récompenses au cours du temps. Soit S l'espace des états du système, et s = [s1, ...,sp] E S l'état courant du système, qui décrit l'état de chacune des catégories de flux de données. L'état 5 sp de la catégorie p est défini par l'état de chacun de ses utilisateurs, sp = [s1 spjp[t]I. Les éléments qui décrivent l'état de chaque catégorie peuvent être séparés entre elements incontrôlables et éléments contrôlables selon qu'ils dépendent ou non de l'action réalisée par le contrôleur. On note ainsi sp = V p E Tc. avec sic' un état contrôlable et sii", un état incontrôlable. L'état incontrôlable sii", 10 inclut le nombre d'utilisateurs actifs par catégorie, les indicateurs COI des utilisateurs et leur débit entrant de données. L'état contrôlable est caractérisé par les indicateurs de performance de transmission KPI (pour Key Performance indicator) instantanés des utilisateurs et leurs écarts par rapport aux contraintes de QoS. Les Nop indicateurs KPI instantanés (l'un et/ou l'autre parmi un délai de transmission, un débit de transmission et 15 un taux de perte de transmission par exemple) d'un utilisateur ip de la catégorie p peuvent être décrits par le vecteur x[t] = xp,,p,Nop [tg Les contraintes de QoS de la catégorie p vis-à-vis de ces indicateurs KPI peuvent être décrites par le vecteur ; = ...,.)Cp,Nopl, avec )1),0 un seuil représentatif d'un contrainte de qualité de service QoS portant sur l'indicateur de performance de transmission o pour la 20 catégorie p. Ainsi pour chaque utilisateur l'état contrôlable s'écrit s[t] = (x,[ [t], Xpjp [t] ). On note A = ACT X ACF l'ensemble des actions possibles du contrôleur de l'apprentissage par renforcement, avec An- l'ensemble des actions correspondant au classificateur temporel et AcR l'ensemble des actions correspondant au classificateur 25 fréquentiel. Plus spécifiquement, An- = {ACT,1, ---,ACT,N} est un ensemble de taille N = P!, où chaque action correspond à une hiérarchisation possible des P catégories de flux de donnés. Et AcR = fi, ...,NR} est un ensemble de règles d'ordonnancement de taille NR, où l'action j e AcF correspond à la sélection de la ième règle 12 d'ordonnancement. Ainsi a = {acT,acF} E A est la paire d'actions constituée des actions réalisées par chacun des classificateurs. La fonction de récompense R calcule l'optimalité d'appliquer l'action a à partir d'un état s. Elle prend en considération, pour chacun des flux de données de 5 chacune des catégories et pour chaque indicateur de performance, l'écart entre l'indicateur instantané du flux de données et le seuil représentatif d'une contrainte de qualité de service portant sur l'indicateur pour la catégorie à laquelle appartient le flux de données. Cette fonction de récompense pour le classificateur temporel peut être 10 déterminée comme Ks,acs, aps) = EpP=1 rp(sp, acs,up), où rp(sp, acs,up) est la récompense perçue au classificateur fréquentiel lors que la règle d'ordonnancement up est utilisée pour la catégorie p d'état sp, étant donné la sélection de la règle de hiérarchisation acs. Ainsi, la récompense perçue au classificateur temporel correspond à la somme de toutes les récompenses du classificateur fréquentiel. Au niveau du 15 classificateur fréquentiel, la fonction de récompense peut être déterminée comme rp(sp,acs,up) = EI,P_1E0N°1P(1 - x,0Ximp,0 1), à savoir comme étant la somme des P - récompenses pour chaque utilisateur ip E UEp et pour chaque indicateur KPI o E O. Selon l'invention, l'apprentissage par renforcement peut réaliser un compromis entre exploitation et exploration, où l'exploitation consiste à refaire les 20 actions qui, selon l'expérience acquise, vont maximiser la récompense cumulée et où l'exploration consiste à parcourir des couples (état, action) à la recherche d'une récompense cumulée plus grande, mais au risque d'adopter parfois un comportement sous-optimal. Plus particulièrement, l'apprentissage par renforcement vient retenir un compromis entre exploration et exploitation qui consiste à suivre la politique optimale 25 courante la plupart du temps, tout en choisissant plus ou moins régulièrement une action aléatoire. Ainsi, l'apprentissage par renforcement selon l'invention comprend à chacune des itérations : 13 - selon une probabilité Pa, une sélection d'exploitation consistant à sélectionner un plan d'allocation de ressources (la règle de hiérarchisation et/ou la première règle d'ordonnancement dans le mode de réalisation privilégié), défini par l'action a, venant maximiser la somme des récompenses à ce stade des 5 itérations ; et - selon une probabilité Pa*, une sélection d'exploration consistant à sélectionner un plan d'allocation de ressources (la règle de hiérarchisation et/ou la première règle d'ordonnancement dans le mode de réalisation privilégié) potentiellement sous-optimal, défini par l'action a* # a. 10 Dans une première réalisation possible, on adopte le mécanisme appelé E-greedy selon lequel Pa = 1 - E, E étant positif et strictement inférieur à 1, et Pa, = £ , , ou K est égal à N ou NR selon que l'on considère la règle de hiérarchisation ou la K-1 règle d'ordonnancement. Des solutions alternatives à ce mécanisme existent (par exemple l'exploration de Boltzmann) qui, lors d'une itération, associent à chaque action a 15 une probabilité d'être choisie en fonction de récompenses perçues aux itérations précédentes, lorsque cette action est sélectionnée dans l'état s. Reprenant l'exemple où les deux classificateurs exploitent une table de correspondance optimisée via l'apprentissage par renforcement, la mise en oeuvre du compromis exploration/exploitation est illustrée par la figure 2. Sur cette figure, l'état du 20 système à l'instant t s[t] est fourni à un premier module d'apprentissage par renforcement 1 en charge de déterminer la politique optimale en termes de hiérarchisation des catégories de flux de données. Un premier module de compromis exploitation/exploration 2 va sélectionner, selon le mécanisme E-greedy, avec une probabilité 1-E, l'action an, E An- déterminée par le premier module d'apprentissage par 25 renforcement 1 sur la base de la politique apprise à ce stade des itérations et, avec une probabilité E, une action aléatoire ctc*T. Le classificateur temporel CT fournit ensuite successivement les différentes catégories de flux de données au classificateur fréquentiel en fonction de la règle de hiérarchisation sélectionnée (i.e. selon l'action an, ou ac*T sélectionnée). Un 14 processus itératif démarre alors, qui s'achève lorsque toutes les catégories de flux de données ont été servies ou lorsque l'intégralité des ressources a été allouée. Si selon l'action an, ou ac*T sélectionnée, la catégorie p doit faire l'objet d'un ordonnancement à la nième itération de ce processus, l'état sp des utilisateurs 5 appartenant à cette catégorie p est fourni à un second module d'apprentissage par renforcement 3 en charge de déterminer la politique optimale en termes d'ordonnancement des utilisateurs. Un second module de compromis exploitation/exploration 4 va sélectionner, avec une probabilité 1-E, l'action acF = up déterminée par le second module d'apprentissage par renforcement 3 sur la base de la 10 politique apprise à ce stade des itérations et, avec une probabilité E, une action aléatoire up. Comme pour le premier module 2, d'autres mécanismes que le E-greedy (tels que l'exploration de Boltzmann exploration) peuvent être sélectionnés pour optimiser le compromis entre exploration et exploitation. Ensuite, une récompense rp (Sp, {aCS, aC*T } , {Up, p }) est associée à 15 l'action up ou up* sélectionnée. L'ensemble des actions up ou up* mises en oeuvre pour chacune des P catégories est noté acF. Lorsque le processus itératif s'achève (lorsque toutes les catégories de flux de données ont été servies ou lorsque l'intégralité des ressources a été allouée), une récompense globale Ks,{acT, ac*T}, acF) qui dépend des récompenses perçues pour chaque catégorie est associée à l'action an, ou ac*T mise en 20 oeuvre par le classificateur temporel CT. Cette récompense globale est utilisée pour mettre à jour les modules d'apprentissage par renforcement 1, 3. Cette mise à jour exploite typiquement la différence entre la récompense escomptée qui est basée sur l'expérience passée et la nouvelle récompense. Lorsque cette différence devient suffisamment faible (par exemple inférieure à 101), le processus d'apprentissage peut 25 être interrompu et la politique apprise peut être stockée dans la table de correspondance LUT. Les classificateurs CT et CF peuvent alors venir simplement consulter cette table pour sélectionner les règles de hiérarchisation et d'ordonnancement optimales pour un état courant donné du système de télécommunication. On notera que lorsque dans un mode de réalisation possible décrit ci-après, la fonction reliant l'état à l'action est 30 approximée par une fonction d'approximation, et les coefficients de la fonction 15 d'approximation sont stockés dans la table de correspondance en lieu de la politique optimale. Différentes variantes de réalisation sont décrites par la suite. Représentation de l'état du système 5 Afin de réduire la complexité de la solution proposée par l'invention et d'accélérer le processus d'apprentissage, différentes variantes de réalisation peuvent être mises en oeuvre, de manière indépendante ou de manière conjointe, pour simplifier la représentation de l'état du système. Comme mentionné précédemment, cet état est composé d'éléments contrôlables et d'éléments incontrôlables. Ces variantes de 10 réalisation visent spécifiquement à représenter de manière efficace l'état en fonction de cette classification. Compression de l'espace de l'état contrôlable Selon cette variante, les variables de l'état contrôlable spc (par exemple délai, débit et taux de perte de paquets) de chacune des catégories de flux de données 15 font l'objet d'un traitement statistique, par exemple pour en calculer la moyenne et la variance. De cette manière, l'état contrôlable n'est plus dépendant du nombre d'utilisateurs Ip dans chacune des catégories de flux de données. La dimension de l'état est ainsi réduit de EpET, ip - op à EpETc, 2 - O. Compression de l'espace de l'état incontrôlable 20 Selon cette variante, les variables de l'état incontrôlable spu de chacune des catégories font l'objet d'un traitement statistique de manière à réduire la taille de cet état. Pour certains paramètres, comme pour l'indicateur COI, il est possible d'éliminer la dépendance au nombre d'utilisateurs /dans la catégorie et à la bande passante (i.e. le nombres NRB d'unités de ressources disponibles). Au contraire, pour d'autres 25 paramètres, comme les caractéristiques du flux de données, il est seulement possible d'éliminer la dépendance au nombre d'utilisateurs. Des algorithmes de regroupement (clustering) ou de classification peuvent être utilisés à cet effet. Parmi les algorithmes de regroupement, on peut citer les heuristiques de Lloyd ou de Swap. Parmi les algorithmes de classification, on peut citer les machines à vecteurs de support (SVM pour Support 16 Vector Machine) ou les réseaux de neurones à fonctions de base radiale (RBFNN pour Radial Basis Function based Neural Networks). Récompense On a présenté dans ce qui précède un exemple de calcul d'une fonction 5 de récompense. D'autres fonctions peuvent toutefois être calculées, toutes dépendantes des indicateurs KPI et des contraintes QoS. La récompense attribuée au classificateur temporel peut par exemple être normalisée par le nombre de catégories de flux de données, tandis que la récompense attribuée au classificateur fréquentiel peut par exemple être normalisée par le nombre d'utilisateurs et le nombre d'indicateurs KPI dans 10 la catégorie considérée. Techniques d'apprentissage par renforcement De nombreuses techniques d'apprentissage par renforcement ont été proposées dans la littérature et peuvent être utilisées pour créer la table de correspondance. D'une manière générale, l'objectif d'un apprentissage par renforcement 15 est d'identifier la politique Ir qui minimise (respectivement qui maximise) la valeur attendue d'une certaine fonction J( Ir ) représentative d'un coût (respectivement d'une récompense) associé à la réalisation de la politique 7r. Cette fonction Kif ) peut représenter une somme de récompenses dévaluées: /(71-) = E Ytrt-Filso,TCI , 20 Où so est l'état initial, rt+1 est la récompense perçue lorsque la politique Ir est mise en oeuvre partant de l'état soet y e [0; 1] est un taux de dévaluation qui détermine la valeur courante de récompenses futures. La fonction Kif ) peut également être représentée comme une récompense moyenne selon : 1 n'l J ( TC ) = lim -E IL rt-Filffi. n->G0 n t=o 1 co t = 0 25 En outre, les algorithmes d'apprentissage par renforcement peuvent être divisés en trois groupes : critique pur, acteur pur, acteur-critique. 17 Méthodes « critique pur)> Ces méthodes apprennent la stratégie optimale Ir en utilisant une fonction Q'T(s, a) qui évalue la valeur de chaque paire état-action (s, a) alors qu'il n'y a pas de fonction explicite pour représenter et évaluer la politique en cours 5 d'apprentissage. Lorsque l'objectif est de maximiser une somme dévaluée de récompenses, ns, a) peut être définie selon : Q'T (s, a) = E1 ip yt r(st,at)lso = s; ac, = a, n- . t=o Selon l'équation d'optimalité de Bellman, the valeur optimale Q*(s, a) peut être calculée de manière récursive comme suit: Q*(s, a) = E Ir (s, a) + y max Q(s' , ap I s, al afeA Où s' est l'état suivant observé lorsque l'action a est appliquée en présence de l'état s. 10 Après convergence, il est possible de déterminer l'action optimale a* pour l'état courant s, de telle sorte que Q* (s, a) soit maximal : a* = argmax Q*( a) ale A Au final, les paires état-action optimales sont stockées dans la table de correspondance. Méthodes "acteur pur" 15 Ces méthodes fonctionnent avec une famille de politiques paramétriques visent à optimiser la fonction J( n- ) directement sur l'espace de paramètres de la politique. Un gradient de la performance, vis-à-vis des paramètres d'acteur, est directement estimé par simulation, and les paramètres sont mis à jour dans une direction d'amélioration. Les méthodes "acteur pur" présentent l'avantage par 20 rapport aux méthodes "critique pur" de permettre à la politique de générer des actions dans un espace d'actions complétement continu. Considérons une paramètrisation de la politique Ir par le vecteur de paramètres O. J( n- ) est une fonction de la politique paramétrique Ire, et est fonction de O. Le gradient de./ par rapport à 61 est décrit par: af alre Vej alre a61. 18 Ensuite, en utilisant des techniques d'optimisation classiques (comme la descente de gradient), une solution localement optimale de la fonction J peut être identifiée. Un inconvénient de l'approche "acteur pur" est que le gradient estimé peut présenter une variance importante, ce qui accroît la durée nécessaire à l'apprentissage. 5 Méthodes "acteur-critique" Ces méthodes visent à combiner les avantages des méthodes "acteur pur" et "critique pur". Comme pour les méthodes "acteur pur", ces méthodes sont capables de prescrire des actions continues, alors que la variance importante des méthodes "acteur pur" est contrecarrée en ajoutant une critique dont le rôle est 10 d'évaluer la politique courante prescrite par l'acteur. Fonction approximatrice de l'apprentissage par renforcement L'espace état-action peut s'avérer combinatoire et immense. Le problème est alors non seulement la quantité de mémoire nécessaire pour la table de correspondance, mais également le temps et les données nécessaires pour réaliser 15 l'apprentissage de la politique optimale. Approximation par une fonction linéaire Il est possible d'avoir recours à une fonction approximatrice ) sous la forme d'une fonction linéaire d'un vecteur de poids O. Alors, à chaque état s N T correspond un vecteur de caractéristiques cp(s) A ((Ms), ...,(p72(s)) ayant le même 20 nombre de composants que O. Il existe de nombreuses manières d'élaborer les caractéristiques à partir des états, par exemple la fonction de base Fourier ou le codage par tuile (Tue Coding). En général, la fonction approximatrice est donnée par le produit scalaire entre 0 et cp(s): .1( ., 0 ) = OT cp(s) = Er=i 0 - cp,(s).-Les fonctions individuelles cp, sont appelées fonctions de base parce 25 qu'elles forment une base linéaire pour l'ensemble des fonctions linéaires de cette forme. Construire un vecteur de caractéristiques de n dimensions pour représenter les états est équivalent à sélectionner un ensemble de n fonctions de bases. Il est naturel d'utiliser une descente de gradient stochastique avec une approximation de fonction linéaire pour mettre à jour 0 de manière itérative jusqu'à convergence. 30 Approximation au moyen d'un système d'inférence flou 19 Pour représenter de manière efficace l'état d'un système, une solution bien connue consiste à intégrer un système d'inférence flou (FIS pour Fuzzy Inference System) dans l'algorithme de 0.-apprentissage. Le système FIS est basé sur la logique floue dans laquelle, à la différence de la logique standard, la vérité de toute affirmation est une 5 question de degré, i.e. est notée par une valeur comprise entre 0 et 1. Par ailleurs, le système FIS utilise des variables linguistiques, c'est à dires des variables dont les valeurs sont des mots, comme « haut » ou « bas ». Chaque variable linguistique xi est associée à un ensemble de termes T(xi) qui inclue tous les ensembles flous correspondant aux valeurs linguistiques de xi. La phase d'apprentissage comprend trois phases: fuzzification, 10 calcul des valeurs de vérité et défuzzification. Approximation par un réseau de neurones Les réseaux de neurones sont un outil puissant pour estimer la fonction optimale :f( 0). Comme pour l'approche par approximation linéaire, durant la phase d'apprentissage, à l'itération i, les nouveaux poids 0, sont calculés de manière à ce que 15 l'erreur quadratique moyenne dans l'équation de Bellman soit réduite. Toutefois, dans ce cas, la fonction approximatrice est calculée comme une fonction non-linéaire des poids 0. Plus particulièrement, si l'on considère un réseau de neurone prédictif à trois niveaux, avec un niveau caché composé de D noeuds et un niveau d'entrée composé de M noeuds, la sortie k peut être calculée comme suit : h ( .z9j1;i - xi +191,0 +1911,0 i=i Yk(x, 0) = D M 20 Où x correspond aux entrées du réseau de neurones, 0 est l'ensemble des poids dans le réseau de neurones, h est la fonction d'activation des noeuds cachés (une fonction sigmoïde non linéaire différentiable telle que la sigmoïde logistique ou l'hyperboloïde tangente), et a est la fonction d'activation (la fonction identité est utilisée ici) des noeuds de sortie. 25 L'invention porte ainsi sur un procédé de détermination d'une allocation de ressources qui met en oeuvre l'apprentissage par renforcement décrit précédemment pour déterminer le plan d'allocation de ressources optimal pour un état donné du 20 système de télécommunication. Elle porte également sur l'exploitation de cet apprentissage et concerne ainsi un procédé d'ordonnancement de paquets comprenant à chaque intervalle temporel de transmission la sélection d'un plan d'allocation de ressources et une allocation des ressources de transmission aux flux de données 5 conformément au plan d'allocation de ressources sélectionné. Cette sélection est réalisée par interrogation d'une table de correspondance dont le contenu résulte de la mise en oeuvre de l'apprentissage par renforcement et qui permet d'identifier, à partir de l'état courant du système de télécommunication multi-accès, le plan d'allocation de ressources à sélectionner. L'invention s'étend à un produit programme d'ordinateur comprenant des 10 instructions de code de programme pour l'exécution du procédé d'ordonnancement lorsque ledit programme est exécuté par un ordinateur, ainsi qu'a un noeud d'un système de télécommunication multi-accès qui comprend une table de correspondance dont le contenu résulte de la mise en oeuvre de l'apprentissage par renforcement et un planificateur configuré pour, à chaque intervalle de transmission, interroger la table de 15 correspondance pour identifier, à partir de l'état courant du système de télécommunication multi-accès, un plan d'allocation de ressources, et réaliser une allocation de ressources de transmission aux flux de données conformément au plan d'allocation REVENDICATIONS1. Procédé de détermination d'une allocation de ressources pour des paquets appartenant à une pluralité de catégories de flux de données dans un système de télécommunication multi-accès partageant une pluralité de ressources de transmission, caractérisé en ce qu'il comprend, pour un état du système de télécommunication multiaccès, la détermination, par itérations d'un apprentissage par renforcement, d'un plan d'allocation de ressource venant maximiser une somme de récompenses, chaque itération de l'apprentissage par renforcement comprenant : - une allocation des ressources de transmission aux flux de données selon un plan d'allocation de ressources ; - la transmission des paquets au moyen des ressources de transmission allouées ; - pour chacune des catégories de flux de données, le calcul d'au moins un indicateur de performance de transmission de chacun des flux de données de la catégorie, et la comparaison, pour chacun des flux de données de la catégorie, de l'au moins un indicateur de performance de transmission calculé à un seuil représentatif d'une contrainte de qualité de service portant sur l'au moins un indicateur de performance de transmission pour la catégorie, et - la détermination d'une récompense en fonction du résultat de ladite comparaison pour chacun des flux de données de chacune des catégories. 2. Procédé selon la revendication 1, dans lequel le plan d'allocation de ressources comprend une règle de hiérarchisation et au moins une première et une seconde règle d'ordonnancement, l'allocation des ressources de transmission comprenant deux étapes consistant en : - un ordonnancement dans le domaine temporel réalisé par un classificateur temporel (CT) configuré pour hiérarchiser les catégories de flux de données selon la règle de hiérarchisation en au moins une catégorie prioritaire et une catégorie secondaire ; et 22 - un ordonnancement dans le domaine fréquentiel réalisé par un classificateur fréquentiel (CF) configuré pour : o ordonnancer les flux de données de la catégorie prioritaire selon la première règle d'ordonnancement et allouer des ressources de transmission aux flux de données de la catégorie prioritaire ainsi ordonnancés; et o en cas de ressources restantes, ordonnancer les flux de données de la catégorie secondaire selon la seconde règle d'ordonnancement et allouer des ressources de transmission restantes aux flux de données de la catégorie secondaire ainsi ordonnancés. 3. Procédé selon la revendication 2, dans lequel la récompense déterminée à chaque 1 Nop itération est la somme EpP=1 rp(acT,up), avec rp(acT,up) = EiP_ y ( 1_0.1,1- - P - 1.)Cp,0 - xp,,p,01), où P désigne le nombre de categories, acT la règle de hiérarchisation, up la règle d'ordonnancement appliquée aux flux de données de la catégorie p, Ip le nombre 15 de flux de données de la catégorie p, 1\10p le nombre d'indicateurs de performance de transmission de la catégorie p, )1),0 le seuil représentatif d'une contrainte de qualité de service portant sur l'indicateur de performance de transmission o pour la catégorie p et xp,,p,0 l'indicateur de performance de transmission o du flux de données ip. 20 4. Procédé selon l'une des revendications 1 à 3, dans lequel chaque itération de l'apprentissage par renforcement comprend: - selon une probabilité Pa, une sélection d'exploitation consistant à sélectionner le plan d'allocation de ressources venant maximiser la somme des récompenses à ce stade des itérations ; et 25 - selon une probabilité une sélection d'exploration consistant à sélectionner un plan d'allocation de ressources différent du plan d'allocation de ressources venant maximiser la somme des récompenses à ce stade des itérations. 5 10 23 5. Procédé selon l'une des revendications 1 à 4, dans lequel l'au moins un indicateur de performance de transmission est l'un parmi un délai de transmission, un débit de transmission et un taux de perte de transmission. 5 6. Procédé d'ordonnancement de paquets appartenant à une pluralité de catégories de flux de données dans un système de télécommunication multi-accès partageant une pluralité de ressources de transmission, caractérisé en ce qu'il comprend, à chaque intervalle temporel de transmission, la sélection d'un plan d'allocation de ressources et une allocation des ressources de transmission aux flux de données conformément au plan 10 d'allocation de ressources sélectionné, ladite sélection étant réalisée par interrogation d'une table de correspondance (LUT) dont le contenu résulte de la mise en oeuvre du procédé selon l'une des revendications 1 à 5 à et qui permet d'identifier, à partir de l'état courant du système de télécommunication multi-accès (s[t)]), le plan d'allocation de ressources à sélectionner. 15 7. Produit programme d'ordinateur comprenant des instructions de code de programme pour l'exécution du procédé selon la revendication 6 lorsque ledit programme est exécuté par un ordinateur. 20 8. Noeud d'un système de télécommunication multi-accès partageant une pluralité de ressources de transmission entre des paquets appartenant à une pluralité de catégories de flux de données, comprenant une table de correspondance (LUT) dont le contenu résulte de la mise en oeuvre du procédé 1 à 5 et un planificateur configuré pour, à chaque intervalle de transmission, interroger la table de correspondance pour identifier, 25 à partir de l'état courant du système de télécommunication multi-accès (s[t)]), un plan d'allocation de ressources, et réaliser une allocation de ressources de transmission aux flux de données conformément au plan d'allocation de ressources identifié.