Mécanismes d'adaptation autonome pour la radio cognitive

Mécanismes d'adaptation autonome pour la radio cognitive

Nicolas COLSON

06 mai 2009

2

Plan

Problématique de la thèse

Positionnement des travaux

Modèle de prise de décision autonome adopté

Organisation du moteur cognitif

Evaluation du moteur cognitif

Conclusions et perspectives

3







4

Défis pour la conception des futurs systèmes de communication

Optimiser la gestion des ressources disponibles– En développant de nouvelles techniques pour transmettre l’information plus

efficacement– En adaptant le comportement de la radio à son environnement

Développer l’intelligence embarquée– Limites des mécanismes d’adaptation actuels

– Définis sur des périmètres d’action étroits– Basés sur un nombre limité d’événements anticipés

– Motivations– Arrivée de la radio (définie) logicielle– Explosion du nombre d'objets communicants– Accroissement de la complexité– Conjoncture économique ultra compétitive

Radio adaptative Radio cognitive[Mitola99]

5

Adaptation totale et autonome au contexte opérationnel– Respecter le cadre de régulation contrôlant l’accès au spectre– Satisfaire les besoins de l’utilisateur en termes de qualité de service– Assurer une gestion optimisée des ressources disponibles

Exemples d'applications– Accès opportuniste au spectre– Conception cognitive du lien radio

Raisonner

Apprendre

Observer

Agir

Radio cognitive[Mitola99]

Sensibilité au contexte(mesures, estimations, …)

Reconfiguration du système de

communication

Décision sur la meilleure ligne de conduite à

adopter

Amélioration des performances avec les

expériences vécues

Conception d’un moteur cognitif

Introduction d’un cycle cognitif

6

Synoptique d'un moteur cognitif

Contexte opérationnel

Politiques de régulationFlexibilité des objets communicants

Mesures sur l’environnement radio(occupation spectrale, caractéristiques du canal)

Application sélectionnéePréférences de l’utilisateurPréférences de l’opérateurNiveau de batterie restant

Qualité du canal radio

Espace des objectifs

Espace de conception

Analyse du contexte

Modèle de l’environnement radio

Configurations disponibles

Contraintes de QoSCompromis recherché

Environnement radio

Exploration del’espace de conception

Configuration adaptée

du contexte Surveillance

7







8

Observer

Rechercher

Agir

Reconnaître

Mémoriser

Approche exploratoire

Observer

Décider

Agir

Prédire

Entraîner

Approche prédictive

Boucle en ligne

Boucle hors-ligne

Simuler

Analyser

Extraire

Diffuser

Observer

Agir

Inférer

Approche experte

Règles/politiques

[Mitola00][DARPA07] [Rieser04][Rondeau07] [Weingart07][Baldo08]

Algorithmes génétiquesRaisonnement par cas

Réseaux de neurones, HMM,réseaux bayésiens, SVM,modèles de régression, …

+Exploite les connaissances établies

Respect du cadre de régulation

-Dépendance à la qualité des connaissances

Effort humain importantApprentissage assisté

+Méthodologie générique

Exploration de larges espaces

-Complexité des mécanismes

Dépendance à des modèles analytiques

+Autonomie décisionnelle

-Choix d’un modèle représentatif

Données d’apprentissage à collecterRisque de complexité algorithmique

Approches cognitives existantes

9

Critères de conception du moteur cognitif

Observer

Décider /Expérimenter

Agir

Prédire

Entraîner

Analyser

Extraire

Surveiller

Surveillance

Décision

Expérimentation

Apprentissage

Processus

Autonomie décisionnelle– Capacités de prédiction– Exploration en ligne de l’espace de conception– Apprentissage incrémental

Efficacité dans la recherche d’une configuration adaptée– Maximiser les décisions optimales– Minimiser les mauvaises décisions– Assurer une bonne réactivité du moteur cognitif – Limiter l’impact des mécanismes cognitifs sur l’autonomie de la batterie

Mécanismes génériques– Souci de flexibilité et de pérennité

10







11

Etapes de résolution d’un problème de conception

Espace de conception

initial

- Contraintes matérielles- Contraintes de régulation- Contraintes de l’opérateur

RéductionEspace de conception

réduitRéduction

- Mesures sur l’environnement radio - Exigences de QoS

Espace de conceptionexplorable

Configuration adaptée

Politique d’optimisation(compromis recherché)

Exploration

1) Contraintes de faisabilité

2) Contraintes de performance

3) Préférences d’optimisation

12

Introduction de relations d’ordre entre les alternatives de configuration

Echelle relative de performance– Ordonne les configurations en fonction de leur robustesse face aux contraintes

de performance– Structure l’exploration de l’espace de conception pour l’apprentissage d’un

modèle prédictif fiable– Etablie par le modèle prédictif en fonction de l’environnement radio

– Confortée par des connaissances expertes plus ou moins fortes sur la robustesse relative des configurations

Echelle relative d’optimalité– Ordonne les configurations en fonction de leur satisfaction vis-à-vis des

préférences d’optimisation– Structure l’exploration de l’espace de conception pour la sélection d’une

configuration adaptée– Etablie par un système de notation

– S’appuyant sur des fonctions objectifs paramétrées

13

Apprentissage de la carte de performance1) Exemple d’espace de conception totalement ordonné

Echelle de performance

C0 C3C2 C4 C5C1 C6

[N. Kasabov, “Evolving Connectionist Systems. The Knowledge Engineering Approach”, Springer, 2007]

Systèmes connexionnistes évolutifs

6 MCS

(HCR: rang de plus haute compatibilité)

Méthode choisie pour cet apprentissage:

14

Apprentissage de la carte de performance2) Exemple d’espace de conception partiellement ordonné

Prédiction de l’échelle de performance

Prédiction de la configuration compatible la moins robuste– Déduction du rang de plus haute compatibilité (HCR)

Echelles de performance possibles

C0 C4C2 C3 C5C1 C6C0 C3C2 C4 C5C1 C6

HCR = 3

HCR = 0 HCR = 1 HCR = 2

HCR = 4

HCR = 4

HCR = 5 HCR = 6

HCR = 3

15

C0

C3C2 C4 C5C1

Prédiction des performances et prise de décision

C1 C2

C3C4

C5

C6

Identification de l’échelle de performance

Identification du HCR

C6C0

Espace de conception réduit

Plus grande robustesse à l'environnement radio

Plus grande probabilité de vérifier la contrainte

Calcul de l’échelle d’optimalité

Compromis plus intéressant (OP2)


Prise de décision

Prédiction qualitative

– Réduit le nombre d’informations à mémoriser

– Tolérance aux erreurs de prédiction

C4C2C1 C3

C3C4C1 C2

C3C2 C4 C5C1 C6

1)

3)

Scénario 1

C0

2)

Scénario 2

16 Décision prise

Performances prédites

C3C2 C4 C5C1

Tolérance aux erreurs de prédiction

C6C0



C4C2C1 C3

C3C4C1 C2

C5

C5

Scénario 1

Scénario 2

3

4

3

5

4

HCRRéel

4

4

4

4

4

HCRPrédit

Oui

Oui

Non

Non

Non

Erreurs de classement

Qualité de la décision

ErronéeOptimale

OptimaleOptimale

OptimaleErronée

OptimaleSous optimale

OptimaleOptimale

Scénario 2Scénario 1

Performances réelles

C3C2 C4 C5C1 C6C0

=

=

<>

>

Une erreur de prédiction n'entraîne pas systématiquement une mauvaise décision

17

Mise au point d’une stratégie stochastique d’exploration– Mémorisée par une équipe d’automates d’apprentissage

– Chaque automate retient la probabilité d’exploration locale (P i)– S’appuyant sur le partitionnement de l’espace de conception (réalisé par le système

connexionniste)

Intérêt d’une stratégie stochastique– L’expérimentation ne garantit pas toujours de trouver la configuration optimale dans un espace

partiellement ordonné– Le partitionnement de l’espace réalisé est incertain

La mise à jour de la stratégie dépend des résultats d’expérimentation

– Succès de la phase d’expérimentation– Modification des relations d’ordre– Mise à jour du rang de plus haute compatibilité

– Echec de la phase d’expérimentation– Aucune mise à jour des connaissances

Gestion du dilemme exploration/exploitation

[ M. A. L. Thathachar and P. S. Sastry, “Varieties of learning automata : An overview”,IEEE Transactions on Systems, Man and Cybernetics, vol. 32, no. 6, pp. 711–722, Dec. 2002]

Pi

Pi

18

Régression le long de l’échelle de performance

3

Processus d’expérimentation (exploration en ligne)1) Exemples de déroulement dans un espace de conception totalement ordonné

C0 C3C2 C4 C5C1 C6

C0 C3C2 C4 C5C1 C6

Attitude prudente

Attitude agressive

C0 C3C2 C4 C5C1 C6

HCR: 5 1 2 2

HCR: 5 3 2

C0 C3C2 C4 C5C1 C6

HCR: 2 3 4 4

Progression le long de l’échelle de performance (succès)

C0 C3C2 C4 C5C1 C6

HCR: 2 2

Progression le long de l’échelle de performance (échec)

Vérification de l’état actuel des connaissances– Tester la configuration associée au HCR

Réaction adaptée aux retours de l’environnement

C0 C3C2 C4 C5C1 C6

4

5

3

19

Introduction de connaissances expertes

Accélérant l’apprentissage d’un modèle prédictif fiable– Exploitées lors de l’expérimentation en ligne

De portée plus générale que des connaissances quantitatives Faciles à identifier par

– Un expert humain– Un processus hors-ligne– Le moteur cognitif lors de son opération

Simples à utiliserc3m3e3

(27)

c1m1e1(1)

c2m1e1(2)

c1m1e2(4)

c1m2e1(10)

c3m1e1(3)

c2m1e2(5)

c2m2e1(11)

c1m1e3(7)

c1m2e2(13)

c1m3e1(19)

c3m1e3(9)

c3m2e2(15)

c3m3e1(21)

c2m2e3(17)

c2m3e2(23)

c1m3e3(25)

c3m1e2(6)

c3m2e1(12)

c2m1e3(8)

c2m2e2(14)

c2m3e1(20)

c1m2e3(16)

c1m3e2(22)

c3m2e3(18)

c3m3e2(24)

c2m3e3(26)

ModulationCodage canal Égalisation

Graphe de robustesse

c1

c2

c3

m1

m2

m3

e1

e2

e3

20

1 010110

… …

Rang 8 10 13 149 11 126 71 ……Echelle de performance prédite

Configuration

…

C23

Processus d’expérimentation2) Exemples de déroulement dans un espace de conception partiellement ordonné

C9 C19C3 C6C7 C8C11 C13

C18 C24 C26

C27

C9 C15 C21 C17 C18

C3 C5 C11 C7 C13 C19

C6 C12 C8 C14 C20 C16

C2 C4 C10

C1

C22

C14

0 0 00

(région non explorée)

Nombre d’échecs

d’exploration

C1

Mémoire d’exploration

OuiOuiNon-Incohérence

2110NErreurs

NonOuiNonOuiContrainte

vérifiée

4.10-38.10-52.10-26.10-5TEB

C6C3C7C13

(vérification)Config. testée

ExploitationExplorationExplorationExplorationExplorationMode

0.77-0.12-0.42P

0.440.610.610.850.85PExploration

88777HCR

1 2

TEB cible = 10-3

21

1 422

… …

Rang 8 10 13 149 11 126 71 ……Echelle de performance prédite

Configuration

…

C23

Processus d’expérimentation2) Exemples de déroulement dans un espace de conception partiellement ordonné

C9 C19C3 C6C7 C8C11 C13

C18 C24 C26

C27

C9 C15 C21 C17 C18

C3 C5 C11 C7 C13 C19

C6 C12 C8 C14 C20 C16

C2 C4 C10

C1

C22

C14

1 02Nombre

d’échecs d’exploration

C1

Mémoire d’exploration

1 0

0.14

0.36

0.57

0.88

Prise de décision stochastique

(région déjà explorée)

22







23

Algorithme de supervision

Nouveau problème de conception

Processus d’analyse prédictive

Processus de décision

Processus d’expérimentation

Processus d’apprentissageConfiguration finale proposée

ExplorationExploitation

Violation des contraintes de QoS

Exploitation Exploration

Connaissance d’une configuration satisfaisante

Aucune configuration testée avec succès

Décision stochastique

Décision déterministe

ou stochastique

Décision déterministe

Satisfaction des contraintes de QoS

24

Organisation structurelle du moteur cognitif

Moteur cognitif

Structuration del’espace de conception

(module DSS)

Algorithme RALFE

Prédiction de l’adéquation des configurations

(module CAP)

Indice de la configuration compatible la moins robuste

Echelle d’optimalité

Cotation des configurations(module GS)

Analyse ducomportement de la radio

(module RBA)

Evaluation / Comparaisondes décisions

Politique de restriction (QoS requise)

Etat du canalPolitique

d’optimisation

Modélisation du contexte opérationnel

(module CSM)

Indicateurs de performance(e.g. BER)

Moteur d’inférence

Espace de conception réduit

Apprentissage

Connaissances expertes

- Mesures sur le canal radio (e.g. SNR)- Informations contextuelles (e.g. politiques de régulation, flexibilité des objets communicants, application sélectionnée, niveau de la batterie)

Décision(i.e. configuration sélectionnée)

Radio logicielle

Probabilité d’exploration Mémoire d’exploration

Echelle de performance

Résolution du problème de conception

Analyse du contexte opérationnel

Reason And Learn From Experience

25




Organisation fonctionnelle du moteur cognitif



26

RXTX

Codage canal(n, k, t)

Modulation(M)

Canal sélectif

EgalisationDémodulation

(M)

Taux d’erreurs binaires résiduel

Profil de puissance associé aux multi-trajets, SNR

Moteur cognitif

Décodage canal

(n, k, t)

Illustration de l'étude de cas sur un scénario de test

BCH(127, 92, 5)c1

BCH(127, 120, 1)c2

Pas de codagec3 Pas d’égaliseure3

Égaliseur linéairee2

MLSEe1

ModulationCodage canal Égalisation

BPSKm1

QPSKm2

8-PSKm3

Carte de performance pour un canal déterministe à deux trajetsOptions de reconfiguration considérées

333 = 27 configurations disponibles

Objectif: Evaluer les capacités d'apprentissage autonome du moteur cognitif

27

Evaluation de la qualité des décisions prises

Pourcentage de problèmes résolussans prendre de mauvaise décision

Pourcentage de problèmes se terminant par la sélection de la configuration optimale

Le moteur cognitif – améliore son expertise sur l’espace de conception– apprend à limiter les risques d’expérimentation

La décision finale est quasiment toujours optimale

22%

81%

100%

97%

28

Evaluation de l’efficacité du moteur cognitif dans sa recherche d’une configuration adaptée

Nombre moyen de décisions prises par problème traité

Nombre moyen de mauvaises décisions prises par problème traité

(erreurs de prédiction, tentatives d’exploration ratées)

Le moteur cognitif trouve une solution adaptée de plus en plus rapidement

Le moteur cognitif apprend à minimiser les mauvaises décisions responsables d’une dégradation de la QoS

L’introduction de connaissances expertes accélère l’exploration de l’espace de conception

1

28

13

1,5

0

12,1

2,8

0,26

29

Evolution de la stratégie stochastique d’exploration

Après 100 problèmes Après 500 problèmes



Probabilité d’exploration moyennée sur l’ensemble des automates d’apprentissage

0,26

1

0

30

Fiabilité du modèle prédictif




Fiabilité des prédictions etimpact sur la qualité des décisions prises

88%

83%

40%

31

Impact du moteur cognitif sur les indicateurs de performance de la radio

32

+

+++++

Comportement sur d’autres scénarios de test

Aucune mauvaise décision

Solution finale optimale

Nombre de décisions

Nombre de mauvaises décisions

Probabilité d’exploration

Fiabilité du moteur cognitif

Nombre de règles

94.8

95.4

1.16

0.052

0.079

93.9

255.8

80.9

97.0

1.51

0.26

0.258

87.6

1521.8

82.5

97.5

1.46

0.22

0.242

87.9

1379.0

+

+++++

+-

C1

C24

C4C2

C3 C5

C10

C6

C7C11

C12 C14

C13

C8 C20

C18 C26

C27

C19

C16 C22

C9 C15 C17C21 C23 C25

C19

C1

C4

C2

C5 C3

C10

C6

C13

C14 C12

C7

C8

C9C24

C20

C22C15

C21 C23

C11

C16

C17 C25

C18 C26

C27

La progression du moteur cognitif dépend de

– la difficulté de l’espace de conception– Nombre et taille des régions de classification

– Croisement des courbes de performance

– la qualité des connaissances embarquées

C2

C3

C4

C5

C1

C6

33

Prise en compte d’une contrainte de performance différente

SNR

TEB tolérable

Passage d’une carte 2D à une carte 4D

Généralisation à d’autres études de cas

Méthodologie applicable à tout espace de conception

– Apprentissage de la carte de performance

SNR

Débit minimum

SNR

QoS cible

SNR

Bande de cohérence

Temps de cohérence

QoS1

SNR

QoS2

SNR

QoS3

Temps de cohérence Temps de cohérence

Bande de cohérence Bande de cohérence

34




Organisation fonctionnelle du moteur cognitif



35

Contributions principales

Mise au point d’un modèle original de prise de décision autonome– Prédiction qualitative des performances des configurations– Conception d’un processus d’expérimentation en ligne– Apprentissage incrémental de cartes de performance – Identification de connaissances expertes permettant d’assister le moteur cognitif

dans ses prises de décision– Gestion innovante du dilemme exploration/exploitation

Sélection et intégration de techniques d’intelligence artificielle appropriées– Systèmes connexionnistes évolutifs– Automates d’apprentissage

Organisation des mécanismes cognitifs– Architecture structurée, modulaire et évolutive– Réflexions sur des mécanismes complémentaires pour améliorer le

comportement du moteur cognitif

36

Perspectives

Validation expérimentale des propositions d'amélioration du moteur cognitif

Prise en compte de différentes échelles de temps des variations du contexte

Exploration des limites du moteur cognitif pour des espaces de conception toujours plus complexes

Application des concepts à l’accès opportuniste au spectre dans une optique d'optimisation des performances

37

Publications

1 article de revue internationale– N. Colson, A. Kountouris, A. Wautier, L. Husson, "A Generic Cognitive Framework for Supervising the Radio Dynamic

Reconfiguration. An AI approach based on design problem classification", Annals of Telecommunications, special issue on Cognitive Radio, to be published

3 communications internationales avec actes– N. Colson, A. Kountouris, A. Wautier, L. Husson, "Autonomous Decision Making Process Supporting Cognitive

Waveform Design", Proc. PIMRC08, Cannes, France, Sept. 2008– N. Colson, A. Kountouris, A. Wautier, L. Husson, "Autonomous Decision Making Process for Dynamic

Reconfiguration of Cognitive Radios", Proc. ICCCN08, Virgin Island, USA, Aug. 2008– N. Colson, A. Kountouris, A. Wautier, L. Husson, "Cognitive Decision Making Process Supervising the Radio Dynamic

Reconfiguration", Proc. CROWNCOM08, Singapore, May 2008

Participation au projet IST européen ORACLE– B. Bochow, S. Chantaraskul, N. Colson, A. Kountouris, K. Moessner, S. Thilakawardana, J. Tiemann, "Definition of

context filtering mechanisms and policy framework", ORACLE WP4, Deliverable D4.2, May 2007– B. Bochow, N. Colson, L. Huang, A. Kountouris, K. Moessner, S. Thilakawardana, M. Smirnov, "Draft OR Policy

Framework", ORACLE WP4, Deliverable D4.1, Nov. 2006

1 communication nationale sans acte– N. Colson, A. Kountouris, "Une application de la radio intelligente : Adaptation dynamique de la complexité

algorithmique", Journées Scientifiques du CNFRS intitulée "Vers des radiocommunications reconfigurables et cognitives", Paris, France, Mars 2006

6 rapports internes– N. Colson, A. Kountouris "Wireless Radio and the Internet of Things : a case for Cognitive Radio", Novembre 2007– N. Colson "Réseaux de neurones", Novembre 2006– N. Colson "Techniques de prise de décision", Octobre 2006– N. Colson "Canal radio", Octobre 2006– N. Colson "Logique floue et théorie des possibilités", Septembre 2006– N. Colson "Systèmes experts et systèmes experts flous", Août 2006

Documents

Mécanismes d'adaptation autonome pour la radio cognitive