Keywords: Radio cognitive, programmation dynamique, métaheuristique, Cuckoo search, Firefly Cognitive radio, Dynamic programming, Metaheuristic, Cuckoo search, Firefly

Au cours de cette dernière décennie, le spectre a connu beaucoup de problèmes tels que la limitation et l'interférence. Ainsi, la radio cognitive est considérée comme une nouvelle approche pour améliorer l'utilisation efficace du spectre sans fil existant, entre l'utilisateur dit « primaire » qui possède une licence sur des bandes de fréquence non-occupées et un autre dit « secondaire » qui pourra accéder à tous moments à ces bandes. Dans ce travail, nous avons étudié un scénario de gestion du spectre, en utilisant une technique basée sur la négociation entre un utilisateur primaire et plusieurs utilisateurs secondaires. Pour cela, nous avons choisi la programmation dynamique comme méthode exacte, et deux métaheuristiques qui sont Cuckoo search et Firefly comme méthodes approchées, afin d'établir une étude comparative selon différents critères que nous avons fixés, tels que le temps de traitement, le coût obtenu, ainsi que le nombre d'utilisateurs secondaires satisfaits. Cette étude comparative nous a permis de prouver que le parallélisme de la programmation dynamique abouti à de meilleurs résultats par rapport aux autres algorithmes métaheuristiques.

Liste des figures

Liste des tableaux

GLOSSAIRE Acronyme Signification

RRC

Architecture de la radio cognitive

Les six composantes fonctionnelles de l'architecture de la radio cognitive sont [START_REF] Ngom | La radio cognitive[END_REF]:

1. La perception sensorielle de l'utilisateur qui inclut l'interface haptique (du toucher), acoustique, la vidéo et les fonctions de détection et de la perception. Les fonctions SP de l'utilisateur peuvent inclure un matériel optimisé, par exemple, pour calculer les vecteurs de flux vidéo en temps réel pour aider la perception d'une scène.

2. Les capteurs de l'environnement local (emplacement, la température, l'accéléromètre, compas, etc.)

3. Les applications système (les services médias indépendants comme un jeu en réseau).

4. Les fonctions SDR (qui incluent la détection RF et les applications radio de la SDR).

5. Les fonctions de la cognition (pour les systèmes de contrôle, de planification, de l'apprentissage).

6. Les fonctions locales effectrices (synthèse de la parole, du texte, des graphiques et des affiches multimédias).

Cycle de cognition

La figure ci-dessous schématise les différentes activités de la cognition qui sont : l'observation, l'orientation, la planification, la décision, l'action et l'apprentissage.

 Phase d'orientation (Orient)

La phase d'orientation détermine l'importance de l'observation et de l'intensité de la réaction, parfois elle provoque une action qui sera lancé immédiatement comme un comportement réactif.

 Phase de planification (Plan)

Dans la phase de planification Un message entrant du réseau serait normalement traité par la génération d'un plan. Dans la recherche de qualité industrielle des radios cognitives, les modèles formels de la causalité seraient incorporés dans les outils de planification. Le plan devrait également inclure la phase de raisonnement dans le temps.

 Phase de décision (Decide)

L'objectif de cette phase est de choisir le meilleur plan parmi les plans de candidature.

 Phase d'action (Act)

Cette phase lance les processus sélectionnés qui s'orientent vers le monde extérieur ou aux états internes de la radio cognitive.

L'accès au monde extérieur consiste d'abord à composer des messages qui doivent être envoyés dans l'environnement en audio ou exprimés dans différents langages. Les actions sur les états internes comprennent le contrôle de ressources comme les canaux radio.

Une action radio cognitive peut également mettre à jour les modèles internes, par exemple, l'ajout de nouveaux modèles aux modèles internes qui existent.

 Phase d'apprentissage (Learn)

Cette phase dépend de la perception, des observations, des décisions et des actions. Elle peut se produire lorsqu'un nouveau modèle est créé en réponse à une action afin de mieux apprendre sur les différentes fonctionnalités de la radio cognitive.

Réseaux de radio cognitive

Partage du spectre (Spectrum sharing)

Cette fonction existe pour coordonner les transmissions entre les utilisateurs secondaires pour accéder au spectre.

Gestion du spectre (Spectrum management)

Les fonctions de gestion du spectre sont indispensables pour les radios cognitives afin de prendre la meilleure bande de spectre pour répondre aux exigences de qualité de service sur toutes les bandes de fréquences libres.

Ces fonctions de gestion peuvent être classées comme suit :

-Analyse du spectre : c'est le moyen d'analyser l'activité sur le spectre de fréquences, pour assurer que la transmission d'un utilisateur licencié PU n'est pas brouillée si le secondaire SU décide d'accéder pour pouvoir estimer la qualité du spectre, plusieurs techniques sont employées pour analyser le spectre, comme les algorithmes d'apprentissages de l'intelligence artificielle.

-Décision sur le spectre : Cette fonction est indispensable pour l'accès au spectre, elle dépend des résultats retenus par la phase d'analyse du spectre, plusieurs règles décisionnelles sont appliquées afin de déterminer la ou les bandes les plus adaptées à la transmission en cours.

Mobilité du spectre (Spectrum mobility)

C'est le processus qui permet à l'utilisateur de la radio cognitive de modifier sa fréquence de fonctionnement. L'utilisation du spectre d'une façon dynamique permet à des terminaux radio de fonctionner dans la meilleure bande de fréquence disponible.

La figure ci-dessous résume les différentes fonctions du RRC :

Domaines d'application des réseaux de radio cognitive

La radio cognitive a touché plusieurs domaines, parmi ces derniers on peut citer :

-Réseaux d'urgence : ils ont tiré profit des concepts de la radio cognitive pour garantir la fiabilité et la flexibilité de communication sans fil.

-Réseaux sans fil de la prochaine génération : La radio cognitive est la technologie clé qui pourrait résoudre le problème d'encombrement du spectre électromagnétique.

-Services de cyber santé : le concept de la radio cognitive peut s'employé dans certains services médicaux comme la gestion des soins de santé et la prise en charge des patients, ou bien les appareils.

-Coexistence de différentes technologies sans fil : la radio cognitive assure la coexistence de plusieurs technologies sans fil. Le chapitre suivant sera consacré à la présentation des différentes méthodes de résolution qui seront utilisées dans le cadre de ce travail.

Conclusion

Chapitre 2 :

Méthodes de résolution

Introduction

En ingénierie, les problèmes d'optimisation combinatoire consistent à sélectionner la meilleure méthode de résolution, il existe deux classes de méthodes pour résoudre ces problèmes.

Les méthodes exactes : ce sont les méthodes qui garantissent l'optimalité de la solution obtenue. Si la taille des données est importante, les méthodes exactes ne permettant pas d'avoir un temps de calcule raisonnable.

Les méthodes approchées : ne garantissent pas que la solution qu'elles fournissent soit optimale, elles sont fréquemment utilisées pour résoudre de problèmes qui sont souvent trop difficiles pour être résolus avec des méthodes exactes.

Dans ce chapitre, nous présentons en particulier la programmation dynamique pour les méthodes exactes et Cuckoo search et Firefly pour les méthodes approchées.

Les méthodes exactes

Les méthodes exactes sont également connues sous le nom de méthodes complètes, explorent l'espace de recherche de manière exhaustive et permettent de trouver la solution exacte d'un problème d'optimisation combinatoire, ces méthodes donnent une garantie de trouver la solution optimale pour une instance de taille finie dans un temps limité et de prouver son optimalité [START_REF] Puchinger | Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification[END_REF]. Parmi ces méthodes, on trouve le branch-and-cut (B&C) [START_REF] Padberg | A branch-and-cut algorithm for the resolution of largescale symmetric traveling salesman problems[END_REF], le branch-andbound (B&B) [START_REF] Lawler | Branch-and-bound methods: A survey[END_REF], le branch-and-price (B&P) [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF], branch-and-cut-and-price (B&C&P) [START_REF] Fukasawa | Robust branch-and-cut-and-price for the capacitated vehicle routing problem[END_REF] et la programmation dynamique [START_REF] Bellman | Dynamic Programming[END_REF].

Dans le cadre de ce travail nous avons utilisé la programmation dynamique comme méthode de résolution exacte.

La programmation dynamique

La programmation dynamique a été initiée par Bellman en 1957 [START_REF] Bellman | Dynamic Programming[END_REF] La programmation dynamique est connue pour résoudre les problèmes les plus répandus comme le problème de sac à dos, la tour de Hanoi, le chemin le plus court par Dijkstra.

La programmation dynamique peut être utilisée à la fois de haut en bas et de bas en haut. Et bien sûr, la plupart du temps, en se référant à la sortie de la solution précédente, il est moins coûteux que de recalculer en termes de cycles CPU.

Dans le cadre de ce travail nous avons parallélisé un traitement basé sur la programmation dynamique en utilisant les threads.

Les méthodes approchées 2.3.1 Les heuristiques

Le terme heuristique est utilisé pour des algorithmes qui trouvent des solutions parmi celles réalisables, mais ils ne garantissent pas que le meilleur sera trouvé, donc ils peuvent être considérés comme des algorithmes approximatifs et non précis. Ces algorithmes trouvent généralement une solution proche du meilleur rapidement et facilement. Parfois, ces algorithmes peuvent être précis, c'est-à-dire qu'ils trouvent la meilleure solution.

La méthode utilisée à partir d'un algorithme heuristique est l'une des méthodes connues, mais pour être facile et rapide, l'algorithme ignore ou même supprime certaines des demandes du problème.

Les métaheuristiques

Les métaheuristiques sont des techniques d'optimisation qui conviennent parfaitement pour résoudre les problèmes logistiques. Il existe un grand nombre de métaheuristiques différentes, parmi elles les méthodes individuelles et les méthodes basées sur la population.

Les techniques individuelles visent à se déplacer dans l'espace de recherche en s'appuyant sur un système de quartier qui permet aux gens de construire un ensemble de solutions voisines à partir d'une solution actuelle. Il existe plusieurs méthodes d'optimisation individuelles comme la recherche locale [START_REF] Marmion | Recherche locale et optimisation combinatoire: de l'analyse structurelle d'un probléme à la conception d'algorithmes efficaces[END_REF], recuit simulé [START_REF] Dreyfus | La méthode du recuit simulé[END_REF], algorithme kangourou [START_REF] Pollard | Monopoly and Discrete Logarithms[END_REF], recherche local itérée et recherche Tabou [START_REF] Glover | Future paths for integer programming and links to artificial intelligence[END_REF].

L'objectif des méthodes basées sur la population est d'initier une interaction entre les individus qui forment une population afin de générer de nouvelles solutions. Il existe plusieurs méthodes basées sur la population comme les algorithmes évolutifs [START_REF] Eiben | Introduction to evolutionary computing[END_REF],

l'algorithme de la colonisation des fourmis [START_REF] Dréo | Métaheuristiques pour l'optimisation difficile[END_REF] et l'optimisation des essaims de particules [START_REF] Eberhart | Swarm Intelligence (The Morgan Kaufmann Series in Evolutionary Computation[END_REF].

 Les algorithmes à base d'intelligence par essaim

En Par exemple, diverses études ont montré que le comportement vol de nombreux animaux et insectes a démontré les caractéristiques typiques des vols LEVY. [START_REF] Yang | Engineering optimisation by cuckoo search[END_REF] Le terme « Lévy Flight » a été inventé par Benoît Mandelbrot [START_REF] Mandelbrot | A life in many dimensions[END_REF], qui a utilisé cela pour une définition précise de la distribution des tailles de pas.

Le Lévy flight, est une marche aléatoire dans laquelle les étapes sont définies en fonction des longueurs des pas, qui ont une certaine distribution de probabilité, avec les directions des étapes étant isotrope et aléatoire.

Au cours de leurs trajectoires en air mort, les mouches des fruits (Drosophila melanogaster) explorent leur paysage à l'aide d'une série de voies de vol droites ponctuées par des saccades rapides à 90 ° [START_REF] Tammero | The influence of visual landscape on the free flight behaviour of fruit fly Drosophila melanogaster[END_REF]. Certaines saccades sont déclenchées par une expansion visuelle associée à l'évitement des collisions. Pourtant, de nombreuses saccades ne sont pas déclenchées par des repères visuels, mais plutôt apparaissent spontanément conduisant au style irrégulier du vol LEVY. [START_REF] Reynolds | Free-flight odor tracking in Drosophila is consistent with an optimal intermittent scale-free search[END_REF]  Description de l'algorithme

Pour plus de clarté dans la description de l'algorithme cuckoo search, trois règles idéalisées sont utilisées :

 Chaque cuckoo pond un oeuf à la fois, et les déverse dans un nid choisi au hasard.

 Les meilleurs nids de haute qualité des oeufs (solutions) seront reportés aux prochaines générations.

 Le nombre de nids disponibles d'accueil est fixe, et un hôte peut découvrir un oeuf étrangé avec une probabilité pa ∈ [0, 1]. Dans ce cas, l'oiseau hôte peut soit lancer l'oeuf loin ou abandonner le nid afin de construire un nouveau nid dans un nouvel emplacement. Par souci de simplicité, cette dernière hypothèse peut être approchée par une fraction pa des n nids étant remplacés par de nouveaux nids (avec de nouvelles solutions aléatoires à de nouveaux emplacements), dans ce travail nous avons utilisé pa=10% de la taille de la population.

Pour un problème de maximisation, la qualité ou la fonction fitness d'une solution peut tout simplement être proportionnel à la fonction objectif.

Sur la base de ces trois règles, les étapes de base de la recherche cuckoo peuvent être résumées comme indiqué dans le pseudo-code ci-dessous [START_REF] Yang | Cuckoo search via Lévy flights[END_REF]: Ou α est la taille de l'étape.

Le vol Lévy fournit une marche aléatoire tel que ses étapes aléatoires sont tirés de la distribution Levy avec grand pas. , avec 1< λ<3.

L'algorithme Firefly

 Inspiration

Les lucioles (en anglais FireFly) sont de petits coléoptères ailés capables de produire une lumière clignotante. Il existe environ deux mille espèces de lucioles, et la plupart des lucioles produisent des flashs courts et rythmés. Le motif des flashes est souvent unique pour une espèce particulière. La lumière clignotante est produite par un processus de bioluminescence, et les vraies fonctions de ces systèmes de signalisation continuent de débattre.

Ces insectes sont capables de produire de la lumière à l'intérieur de leur corps grâce à des organes spéciaux situés très près de la surface de la peau. Cette production de lumière est due à un type de réaction chimique appelée bioluminescence. [START_REF] Stanger-Hall | Phylogeny of North American fireflies (Coleoptera: Lampyridae): implications for the evolution of light signals[END_REF] Les femelles peuvent imiter les signaux lumineux des autres espèces afin d'attirer des mâles afin de les capturer et les dévorer. Les lucioles ont un mécanisme de type condensateur, qui se décharge lentement jusqu'à ce qu'un certain seuil soit atteint, ils libèrent l'énergie sous forme de lumière. Le phénomène se répète de façon cyclique.

L'Algorithme des lucioles développé par Yang [START_REF] Yang | Nature-inspired Metaheuristic algorithms, united kingdom[END_REF] est inspiré par l'atténuation de la lumière sur la distance et l'attraction mutuelle mais il considère toutes les lucioles comme unisexes. Evaluer les nouvelles solutions et mettre à jour l'intensité de la lumière

Fin pour

Fin pour

Classer les lucioles et trouver la meilleure solution actuelle

Fin tantque

Extraction de la solution.

Conclusion

A travers ce chapitre, nous avons présenté les méthodes de résolution que nous allons utiliser durant la réalisation de ce travail, nous nous sommes focalisés sur une méthode de résolution exacte qui est la programmation dynamique en donnant son principe, ensuite nous avons expliqué les méthodes de résolution approchée précisément les métaheuristiques en donnant une définition claire et précise des deux algorithmes qui seront utilisés par la suite (le Firefly et le Cuckoo search).

Le chapitre suivant sera consacré à la présentation des résultats obtenus lors de notre étude comparative entre la parallélisation de la programmation dynamique et l'utilisation du Firefly et du Cuckoo search.

Chapitre 3 :

Evaluation des résultats

Introduction

Dans le domaine de la radio cognitive, l'utilisateur primaire (PU) qui est en possession d'une licence est libre d'accéder à n'importe quel moment au spectre via ses bandes de fréquence, contrairement à l'utilisateur secondaire (SU) qui pourra accéder seulement a des bandes de fréquence non utilisées par le (PU), selon le critère de coopération entre les deux sans produire des interférences.

Un moteur cognitif utilise généralement les métaheuristiques pour son fonctionnement, ainsi, nous avons réalisé dans le cadre de ce travail une étude comparative entre deux métaheuristiques qui sont Cuckoo search et Firefly et une méthode exacte intitulée la programmation dynamique parallèle. L'objectif visé est de montrer l'intérêt de paralléliser une méthode exacte afin d'améliorer la gestion du spectre dans le cadre d'un réseau de radio cognitive.

Nous allons donc, dans ce qui suit présenter notre étude comparative et donner les résultats obtenus lors de la réalisation de ce travail.

La fonction objectif (fitness function)

La fonction objectif est une fonction qui sert à déterminer la meilleure solution a un problème d'optimisation combinatoire qui est soit de type maximiser ou de type minimiser jusqu'à l'obtention de la solution la plus favorable. Dans notre cas l'utilité de cette fonction est de maximiser le coût « bénéfice pour l'utilisateur primaire » et aussi le nombre de (SU) satisfait et de minimiser le temps de traitement « temps de réponse aux utilisateurs secondaire ».

Soit les paramètres suivants :

-n : le nombre de (SU).

-m : le nombre de canaux libres que possède le (PU).

-W : un tableau de taille n. W[i] est le nombre de canaux demandés par SUi.

-C : un tableau de taille n. C[i] est le prix proposé pour les W[i] par SUi.

-La fonction à optimiser est : Max .

-La contrainte à respecter est : ≤ m.

Réalisation des algorithmes et résultats

La programmation dynamique

Notre étude s'est basée sur le travail proposé par les auteurs dans [START_REF] Amraoui | Auction-based Agent Negotiation in Cognitive Radio Ad Hoc Networks[END_REF], travail réalisé avec la programmation dynamique mais sans les threads.

Nous avons donc visé en premier lieu l'amélioration de la programmation dynamique en se basant sur le parallélisme. Notre traitement s'effectue sur une matrice de taille n*m d'entier, le code s'exécute ligne par ligne et le résultat de la ligne suivante dépend de celui de la ligne précédente. Le graphe suivant montre les résultats obtenus. Le 1 veut dire que le SU fait partie de la solution.

M colonnes

Génération de nouvelles solutions

Critère d'arrêt

Nous avons choisi de fixer un certain nombre de génération comme critère d'arrêt de notre algorithme.

Le tableau suivant représente les résultats obtenus par l'algorithme CS :

Déplacement et mise à jour

À chaque nouvelle étape itérative de l'algorithme, la luminosité et l'attirance (atrractiveness) de chaque luciole (firefly) est calculée via la fonction objectif, ensuite l'algorithme compare chaque luciole avec tout le reste des lucioles, comparaison deux à deux selon la fonction objectif. Si la fonction objectif de la i-ème luciole est inférieure à la fonction objectif de la jème luciole I(i) < I(j) ce qui est exprimé par l'attirance, la première se déplacera vers la deuxième.

Les positions des lucioles sont mises à jour après avoir comparé la luminosité de chaque luciole avec toutes les autres lucioles et aussi en prenant compte des règles de connaissance de la luciole et de leurs voisins, ces règles sont la distance entre deux lucioles comparées, un mouvement aléatoire et la position initiale.

Par la suite, la nouvelle luciole est évaluée, sa position et son intensité de lumière sont mises à jour.

Critère d'arrêt

Pareil comme pour le CS, nous avons choisi de fixer un certain nombre de génération comme critère d'arrêt de notre algorithme. Après avoir lancé une dizaine de simulation de nos algorithmes avec des paramètres similaires (nombre de SU=12000, nombre de canaux=15000), nous avons fait leur moyenne afin de présenter les résultats obtenus lors de notre étude.

Paramétrage de l'algorithme firefly

Comparaison en termes de temps de traitement côté PU

Le graphe et le tableau suivent représente les résultats obtenus.

Comparaison en termes de nombre de SU satisfaits

Le graphe suivant représente une comparaison entre les 3 algorithmes en termes de SU satisfait. On constate que l'algorithme firefly nous donne la meilleure valeur, suivie par l'algorithme cuckoo search et en dernière position par la programmation dynamique, cette dernière offre ses résultats en termes de nombre de SU satisfaits indépendamment du nombre de threads.

On peut déduire que la métaheuristique firefly offre le meilleur résultat en termes du nombre de SU satisfaits grâce à son mode de recherche qui est plus adapté à ce type de problème.

Conclusion

A travers ce chapitre, nous avons pu présenter les résultats obtenus durant notre étude. Ces résultats montrent que l'implémentation des threads pour la programmation dynamique permet un estimable bénéfice pour le temps de réponse coté PU, ayant déjà montré sa preuve avec le gain « coût », néanmoins, elle satisfait moins de SU par rapport aux autres métaheuristiques (CS et FA). Un moteur cognitif utilisant nativement les métaheuristiques peut également se baser sur les méthodes exactes mais à condition de trouver un moyen algorithmique pour paralléliser la méthode exacte.

Conclusion générale

Les différentes recherches qui ont été menées au sujet de la radio cognitive ont permis de répondre à des défis relatifs à sa réalisation, ainsi qu'à son application auprès de technologies innovantes.

La radio cognitive est la technologie clé qui permettra de résoudre les problèmes de saturation Price afin d'obtenir des résultats plus performants. L'utilisation de la théorie des jeux [START_REF] Badr | Game theory applications in wireless networks: A survey[END_REF] est aussi envisageable afin de trouver un compromis entre l'utilisation des méthodes exactes et les méthodes approchées dans le contexte de la radio cognitive.

Références Bibliographiques

  Résumé ....................................................................................................................................... Table des matières ...................................................................................................................... Liste des figures ......................................................................................................................... Liste des tableaux ....................................................................................................................... GLOSSAIRE .............................................................................................................................. Introduction Générale ................................................................................................................. Chapitre 1 : Réseaux de radio cognitive ..................................................................................... 1.1 Introduction ...................................................................................................................... 1.2 Historique ......................................................................................................................... 1.3 Définition et principe ....................................................................................................... 1.4 Radio logiciel ................................................................................................................. 1.5 Relation entre radio cognitive et radio logicielle restreinte ........................................... 1.6 Architecture de la radio cognitive .................................................................................. 1.7 Cycle de cognition .......................................................................................................... 1.8 Réseaux de radio cognitive ............................................................................................ 1.8.1 Architecture des réseaux de radio cognitive ........................................................... 1.8.1.1 Réseau primaire ................................................................................................ 1.8.1.2 Réseau secondaire ............................................................................................ 1.8.2 Fonctions des réseaux de radio cognitive ................................................................ 1.8.2.1 Détection du spectre (Spectrum sensing) ......................................................... 1.8.2.2 Partage du spectre (Spectrum sharing) ............................................................. 1.8.2.3 Gestion du spectre (Spectrum management) .................................................... 1.8.2.4 Mobilité du spectre (Spectrum mobility) ......................................................... 1.8.3 Domaines d'application des réseaux de radio cognitive ......................................... 1.9 Conclusion ...................................................................................................................... Chapitre 2 : Méthodes de résolution ........................................................................................ 2.1 Introduction .................................................................................................................... 2.2 Les méthodes exactes ..................................................................................................... 2.2.1 La programmation dynamique ................................................................................ 2.3 Les méthodes approchées ............................................................................................... 2.3.1 Les heuristiques ....................................................................................................... 2.3.2 Les métaheuristiques ............................................................................................... 2.3.2.1 Cuckoo search .................................................................................................. 2.3.2.2 L'algorithme Firefly ......................................................................................... 2.4 Conclusion ...................................................................................................................... Chapitre 3 : Evaluation des résultats ........................................................................................ 3.1 Introduction .................................................................................................................... 3.2 La fonction objectif (fitness function) ............................................................................ 3.3 Réalisation des algorithmes et résultats ......................................................................... 3.3.1 La programmation dynamique ................................................................................ 3.3.2 L'algorithme cuckoo search .................................................................................... 3.3.2.1 Initialisation de la population ........................................................................... 3.3.2.2 Génération de nouvelles solutions .................................................................... 3.3.2.3 Critère d'arrêt ................................................................................................... 3.3.3 L'algorithme Firefly ................................................................................................ 3.3.3.1 Génération de la population initiale ................................................................. 3.3.3.2 Classement ....................................................................................................... 3.3.3.3 Déplacement et mise à jour .............................................................................. 3.3.3.4 Critère d'arrêt ................................................................................................... 3.3.3.5 Paramétrage de l'algorithme firefly ................................................................. 3.4 Etude Comparative ......................................................................................................... 3.4.1 Comparaison en termes de temps de traitement côté PU ........................................ 3.4.2 Comparaison en termes de gain coté PU ................................................................. 3.4.3 Comparaison en termes de nombre de SU satisfaits ............................................... 3.5 Conclusion ...................................................................................................................... Conclusion générale ................................................................................................................. Références Bibliographiques ....................................................................................................

Figure 1 . 1 :

 11 Figure 1.1 : architecture de la radio cognitive [8] .................................................................... Figure 1.2 : cycle de cognition [9] ........................................................................................... Figure 1.3 : les fonctions de RRC [10] ..................................................................................... Figure 3.1 : matrice de la programmation dynamique .............................................................Figure 3.2 : temps d'exécutions par rapport au nombre de threads ......................................... Figure 3.3 : comparaison en termes de temps de traitement .................................................... Figure 3.4 : comparaison en termes de gain(coût) ................................................................... Figure 3.5 : comparaison en termes du nombre de SU satisfaits .............................................

Tableau 3 . 1 :

 31 temps d'exécution en fonction du nombre de threads ........................................ Tableau 3.2 : coût et nombre de SU satisfaits obtenus par la programmation dynamique ...... Tableau 3.3 : résultats de l'algorithme Cuckoo search ............................................................ Tableau 3.4 : résultats de l'algorithme Firefly ......................................................................... Tableau 3.5 : résultats de la comparaison en termes de temps de traitement ...........................

Figure 1 . 1 :

 11 Figure 1.1 : architecture de la radio cognitive [7]

Figure 1 . 2 : 8 ]

 128 Figure 1.2 : cycle de cognition [8]

Figure 1 . 3 :

 13 Figure 1.3 : les fonctions de RRC [9]

A

  travers ce chapitre, nous avons pu introduire une présentation précise et détaillée de la radio cognitive dans ses composantes et ses fonctionnalités, ainsi que sa frontière avec la radio logicielle. Les possibilités et les éventualités assurées par cette technologie ainsi les champs d'action à exploiter et faire valoir pour la réalisation du concept de réseaux de radio cognitive, ont été démontrés.

  Tant que (t <NbrMaxGéneration) ou (critère d'arrêt) faire Créer un cuckoo (nommé i) aléatoirement par Levy Flight Evaluer sa qualité/fitness Fi Choisir un nid parmi n (nommé j) aléatoirement Si (Fi > Fj) alors Remplacer j par la nouvelle solution Fin Si Abandonner une fraction (pa) des pires nids et construire des nouveaux à de nouveaux emplacements à travers Levy Flight Garder les meilleures solutions (ou nids avec des solutions de qualité) Classer les solutions et trouver le meilleur Fin tant que Lors de la génération de nouvelles solutions pour un cuckoo appelé i (solution), un vol LEVY est effectué comme suit :



  Principe de fonctionnement L'algorithme Firefly (FA) développé par Xin-She Yang à l'Université de Cambridge en 2007 est basé sur l'émission de la lumière et l'absorption de la lumière ainsi que le comportement attractif entre les lucioles, il est développé pour résoudre les problèmes d'optimisation. L'algorithme tire son inspiration du comportement clignotant des lucioles. Les trois règles sont idéalisées en décrivant le FA [30] [31] : Toutes les lucioles sont unisexes de telles sortes que seront attirées vers d'autres indépendamment de leurs sexes.  L'attractivité des lucioles est directement proportionnelle à la luminosité entre eux, et est diminué une fois la distance entre deux lucioles augmente. Ainsi, pour tous les deux lucioles clignotantes quelconques, le moins lumineux sera attiré et se déplace donc vers le plus lumineux. La luminosité de la lumière clignotante peut être considérée comme une fonction objectif qui devra être optimisée. Le principe de base de la plupart des méthodes d'optimisation des métaheuristiques est la génération aléatoire de la population initiale de solutions candidates réalisables. Pour cela le processus de l'algorithme de luciole commence avec l'initialisation de la population des lucioles et donc chaque luciole dans une population représente une solution candidate, La taille de la population détermine le nombre de solutions ou la taille de l'espace de recherche dont le but est d'orienter la recherche à la meilleure localisation. Dans l'étape suivante, chaque luciole est évaluée en fonction de leurs conditions physiques (intensité lumineuse). À chaque nouvelle étape itérative, la luminosité et l'attirance de chaque luciole est calculée, la distance entre toutes lucioles peut être définie comme une distance cartésienne, la fonction de la distance développée est utilisée pour trouver la distance entre deux lucioles. La fonction de l'attractivité est définie en utilisant l'intensité lumineuse, la distance entre lucioles, et un coefficient d'absorption, le mouvement de luciole est défini par une fonction de mouvement, en utilisant la position actuelle, l'attractivité et une marche aléatoire, après avoir comparé la luminosité de chaque luciole avec toutes les autres lucioles, les positions des lucioles sont mises à jour en se basant sur les règles de connaissances sur les lucioles et sur leurs voisins. Après le déplacement, la nouvelle luciole est évaluée et l'intensité de sa lumière est mise à jour. Pendant la boucle de comparaison en paire, la meilleure solution actuelle est la mise à jour d'une manière itérative. Le Processus de comparaison par pair est répété jusqu'à la satisfaction des critères de terminaison. L'algorithme des lucioles est donné ci-dessous : Fonction objectif f(x), x = Générer la population initiale de lucioles (i =1,2, …, n) L'intensité lumineuse de est déterminée par f( ) Définir le coefficient d'absorption de la lumière ɣ Tant que (t < MaxGeneration) Pour i = 1 jusqu'à n ( n tt les lucioles) Pour j = 1 jusqu'à n (n tt les lucioles) (boucle interne) Si ( < ), deplacer la luciole i vers j ; finsi Varier l'attractivité par la distance r via exp[-ɣr]

Figure 3 . 1 :

 31 Figure 3.1 : matrice de la programmation dynamique

Figure 3 . 2 :Tableau 3 . 2 : 3 . 3 . 2 L'algorithme cuckoo search 3 . 3 . 2 . 1

 32323323321 Figure 3.2 : temps d'exécutions par rapport au nombre de threads

  Après avoir générer la population initiale, l'algorithme calcule pour chaque ligne de la matrice sa fonction objectif, le résultat obtenu est sauvegardé dans un tableau trié par ordre croissant, le meilleur individu de cette population est celui qui a le plus de gain. Ensuite, un nouvel individu sera créé aléatoirement par Levy flight, puis il sera comparé à un autre individu créé aussi aléatoirement. Si la fonction objectif de l'individu créé par Levy flight est supérieure à celle de l'individu créé aléatoirement on remplace ce dernier, sinon il n y'aura pas de changement. L'algorithme néglige une fraction de pires individus, cette fraction représente 10% de la population, ces pires individus seront remplacés par Levy flight.

Figure 3 . 3 :

 33 Figure 3.3 : comparaison en termes de temps de traitement

Tableau 3 . 5 : 3 . 4 . 2

 35342 résultats de la comparaison en termes de temps de traitement Comparaison en termes de gain coté PU Le graphe suivant représente une comparaison entre les 3 algorithmes en termes de coût.

Figure 3 . 4 :

 34 Figure 3.4 : comparaison en termes de gain (coût)

Figure 3 . 5 :

 35 Figure 3.5 : comparaison en termes du nombre de SU satisfaits La figure 3.5 illustre un histogramme de comparaison en termes de nombre de SU satisfaits entre les trois algorithmes.

  du spectre et les conflits d'accès à ce dernier. Les échanges qui sont faites lors d'une négociation d'accès au spectre entre les utilisateurs primaires et secondaires sont observés comme une opération délicate et aussi comme un problème d'optimisation combinatoire. Ainsi dans notre étude, nous nous somme focalisés sur une solution qui pourrait néanmoins donner un meilleur rendement à cette négociation, notre travail est bâti sur deux types d'approches pour aborder ce type de problème. D'une part les méthodes qui garantissent l'optimalité de la solution obtenue, ces méthodes sont appelées méthodes exactes, d'autre part les métaheuristiques qui permettent d'obtenir rapidement de bons résultats mais qui ne garantissent pas que l'optimum ait été trouvé, ces méthodes sont appelées méthodes approchées. Trois approches nous intéressent plus exactement, car elles sont à la base de tout le travail effectué dans ce rapport. Il s'agit de la programmation dynamique, une méthode d'optimisation exacte et des deux algorithmes métaheuristiques cuckoo search et firefly qui représentent les méthodes d'optimisation approchées. Dans ce travail nous avons donc expliqué ces trois algorithmes d'une manière très détaillée et nous avons introduit tout le vocabulaire qui leur est associé et qui nous a été utile dans la comparaison élaborée entre eux afin d'obtenir un résultat optimal qui va pouvoir appuyer le choix d'une méthode parmi celles étudiées. Ces résultats obtenus lors de l'étude comparative, valident un bénéfice pour la parallélisation de la méthode exacte en termes de temps de traitement et coût obtenu côté PU. Finalement et comme perspective, nous pouvons élargir ce travail pour aborder la parallélisation pour d'autres méthodes exactes comme le Branch and Bound, le Branch and

Chapitre 1 : Réseaux de radio cognitive 1.1 Introduction

  'évolution des systèmes de transmission augmente les risques d'interférences et de saturation du spectre électromagnétique. En effet, nous assistons actuellement à la multiplication des normes et des standards de télécommunication vu les progrès récents dans ce domaine. Le nombre croissant de standards normalisés permet d'agrandir l'éventail des offres et des services disponibles pour chaque utilisateur, d'ailleurs, la plupart des radiofréquences disponibles ont déjà été allouées [1]. Une étude réalisée par la FCC a montré que certaines bandes de fréquences sont partiellement occupées dans des emplacements particuliers et à des moments particuliers. Et c'est pour toutes ces raisons que la Radio Cognitive (RC) est apparue. L'idée de la RC est de partager le spectre entre un utilisateur dit primaire, et un utilisateur dit secondaire. L'objectif principal de

	Dans le deuxième chapitre : nous présentons les différentes méthodes utilisées dans ce rapport. Nous présentons les méthodes exactes et les méthodes approchées en se focalisant sur 1.2 Historique
	les heuristiques et les métaheuristiques ainsi que leurs caractéristiques. Nous donnons L'idée de la radio cognitive a été présentée officiellement par Joseph Mitola III à un séminaire
	Réseaux de Radio Cognitive Radio Cognitive également plus de détails sur les trois algorithmes : programmation dynamique, Cuckoo RC à KTH, l'Institut royal de technologie, en 1998, publié plus tard dans un article de Mitola et Le concept de Radio Cognitive (RC) est apparu comme un nouveau paradigme en 1999 en Search et Firefly ainsi que leurs fonctionnements. tant que prolongement de la Radio Définie par Logiciel (RDL). Il décrit la situation dans Gerald Q. Maguire, Jr en 1999 [4]. Connu comme le « Père de la radio logicielle ». Dr. Mitola
	RDL Dans le dernier chapitre : nous présentons les différents paramètres utilisés lors de laquelle les dispositifs radio intelligents et les entités de réseau associées se communiquent de est l'un des auteurs les plus cités dans le domaine. Mitola combine son expérience de la radio Radio Défini par Logiciel SRC l'implémentation des trois algorithmes. Nous expliquerons notre étude comparative en logicielle ainsi que sa passion pour l'apprentissage automatique et l'intelligence artificielle telle manière qu'ils sont en mesure d'ajuster leurs paramètres de fonctionnement en fonction Système de Radio Cognitive discutant les résultats obtenus. des besoins de l'utilisateur / du réseau et d'apprendre de l'expérience en même temps. Depuis, pour mettre en place la technologie de la radio cognitive. Et donc d'après lui :
	FCC il y a eu beaucoup d'efforts dans le milieu de la recherche sur les sujets liés à la RC. Les Federal Communications Commission « Une radio cognitive peut connaître, percevoir et apprendre de son environnement puis agir
	Ofcom WRC KTH WhiteSpaces-TVWS) ont également été lancées et ont progressé dans de nombreux World Radiocommunication Conference Kungliga Tekniska Högskolan organismes de normalisation. Presque tous les organismes de réglementation des États-Unis, d'Europe et de l'Asie et du Pacifique ont reconnu l'importance de SRC pour façonner la Introduction Office of Communications activités de normalisation sur les systèmes de Radio Cognitive (SRC) (y compris TV pour simplifier la vie de l'utilisateur ».
	SDR répartition du spectre. Les régulateurs comme FCC aux États-Unis et Ofcom au Royaume-Uni Software Defined Radio
	RF PU SU ont ouvert la voie à un accès secondaire à des appareils non autorisés sur des chaînes de Radio Fréquence Primary User télévision. Enfin, la conférence mondiale de radiocommunication (WRC 2012) [2] témoigne des discussions sur les modifications réglementaires requises pour permettre l'introduction du Générale Secondary User SRC. Malgré tous ces progrès, la radio cognitive est principalement un sujet de recherche
	URC aujourd'hui, et le marché sans fil n'a pas encore vu un déploiement / exploitation commerciale Utilisateur de la Radio Cognitive
	CPU massive de la technologie RC. La RC présentée par Mitola reste un concept futuriste où une Central Processing Unit
	IA connaissance omniprésente est intégrée dans tous les types de dispositifs / équipements / Intelligence Artificielle
	FA applications qui sont conscients de nos besoins / souhaits, les exécutant et rendant notre vie afin d'élaborer notre étude comparative selon différents critères que nous avons fixés (temps Firefly Algorithme de traitement, coût obtenu et nombre de SU satisfaits). Cette étude comparative nous a permis quotidienne plus facile [3].
	CS d'aboutir à des résultats démontants laquelle de ces méthodes citées offre le meilleur Cuckoo Search
	API rendement pour la gestion du spectre. A noter ici que nous avons opté pour la parallélisation Application Programming Interface La radio cognitive est une technologie clé qui pourrait révolutionner le monde des réseaux
	CDDL sans fil. Ces derniers jouissent continuellement d'une demande qui croît et qui engendre un de la programmation dynamique car la version sans threads est déjà traitée dans la littérature. Common Development and Distribution License important encombrement du spectre car l'efficacité de celui-ci est désormais mise en péril, la
	GPL Le présent rapport est organisé comme suit : General Public License RC est le concept qui permet de répondre à ce défi ; mieux utiliser le spectre c'est aussi
	HTML Dans le premier chapitre : nous donnerons une présentation claire et détaillée de la RC ainsi HyperText Markup Language augmenter les débits et rendre plus fiable la couche physique.
	que ses composantes et ses fonctionnalités et aussi sa frontière avec la radio logicielle puis de
	son architecture, des réseaux de RC de leurs fonctionnalités et de leurs domaines
	d'application.

Lcette gestion du spectre consiste à obtenir un taux maximum de l'exploitation du spectre radio, pour que cela fonctionne, l'utilisateur secondaire doit être capable de détecter d'une manière dynamique l'espace blanc, de se configurer pour transmettre, de détecter le retour de l'utilisateur primaire et ensuite cesser de transmettre et chercher un autre espace blanc. Le standard IEEE 802.22, qui est basé sur ce concept, est actuellement en cours de développement

[START_REF] Amraoui | Accès Dynamique au Spectre dans le Contexte de la Radio Cognitive[END_REF]

.

Dans ce rapport, nous tenterons d'apporter une solution à la gestion du spectre en utilisant une technique basée sur la négociation entre un PU et plusieurs SUs, pour cela nous avons étudiés deux approches de résolution, la première est dite exacte et la seconde est dite approchée.

Nous avons choisi la programmation dynamique comme méthode exacte ainsi que deux métaheuristiques qui sont Cuckoo Search (CS) et Firefly (FA) comme méthodes approchées

1.3 Définition et principe

  La radio logicielle est un ensemble de technologies pour définir les paramètres et les fonctions des émetteurs-récepteurs radio, y compris la fréquence des opérateurs, la bande passante de modulation, le codage des canaux et l'agilité fréquence / espace / temps / code. Dans les générations précédentes de systèmes de télécommunications, ces paramètres et fonctions étaient parfois sélectionnables, mais généralement définis par le matériel, avec une programmation programmée limitée au traitement du signal numérique en bande de base[START_REF] Mitola | Encyclopedia of Telecommunications[END_REF].

	La RC est une forme de communication sans fil dans laquelle un émetteur/récepteur peut
	détecter intelligemment les canaux de communication qui sont en cours d'utilisation et ceux
	qui ne le sont pas, et peut se déplacer dans les canaux inutilisés. Ceci permet d'optimiser
	l'utilisation des fréquences radio disponibles du spectre tout en minimisant les interférences
	avec d'autres utilisateurs [1].
	La radio cognitive est une nouvelle technologie qui permet, à l'aide d'une radio logicielle, de
	définir ou de modifier les paramètres de fonctionnement de la fréquence radio d'un noeud
	réseau (téléphone sans fil ou un point d'accès sans fil), comme par exemple, la gamme de
	fréquences, le type de modulation ou la puissance de sortie [5].
	Cette capacité permet d'adapter chaque appareil aux conditions spectrales du moment et offre
	donc aux utilisateurs un accès plus souple, efficace et complet à cette ressource. Cette
	approche peut améliorer considérablement le débit des données et la portée des liaisons sans
	augmenter la bande passante ni la puissance de transmissions. La RC offre également une
	solution équilibrée au problème de l'encombrement du spectre en accordant d'abord l'usage
	prioritaire au propriétaire du spectre, puis en permettant à d'autres de se servir des portions
	inutilisées du spectre.

Un réseau cognitif coordonne les transmissions suivant différentes bandes de fréquences et différentes technologies en exploitant les bandes disponibles à un instant donné et à un endroit donné. Il a besoin d'une station de base capable de travailler sur une large gamme de fréquences afin de reconnaître différents signaux présents dans le réseau et se reconfigurer intelligemment.

1.4 Radio logiciel

Après plusieurs années de développement un nouveau concept est apparu qui est la radio logicielle restreinte (software defined radio ou SDR), elle définit une collection de technologies matérielles et logicielles où certaines ou toutes les fonctions d'exploitation de la radio (également appelées traitement de couche physique) sont implémentées via un logiciel ou un microprogramme modifiable fonctionnant sur des technologies de traitement programmables. Ces dispositifs comprennent des tableaux de portes programmables sur site, des processeurs de signaux numériques, des processeurs à usage général ou d'autres processeurs programmables spécifiques à l'application. L'utilisation de ces technologies permet d'ajouter de nouvelles fonctions et capacités sans fil aux systèmes radio existants sans nécessiter de nouveau matériel.

1.

5 Relation entre radio cognitive et radio logicielle restreinte

  Les systèmes de radio cognitive sont un domaine d'activité de recherche, et les applications sont en cours d'étude et d'essai. Les systèmes qui utilisent certaines fonctionnalités cognitives ont déjà été déployés, et certaines administrations autorisent ces systèmes (par exemple, la sélection dynamique de la fréquence). Ces administrations ont des processus nationaux d'approbation des équipements pour protéger les services existants contre les interférences nuisibles. Un système radio mettant en oeuvre des technologies de radio cognitive peut cependant avoir un impact sur les pays voisins et une coordination peut être nécessaire.Lorsqu'il existe des applications dans lesquelles la technologie des systèmes radio cognitifs est implémentée sur une base de non-interférence et de non-protection, l'administration concernée devrait s'assurer que les interférences ne seront pas générées.

On s'attend à ce que les technologies de la radio logicielle restreinte et de la radio cognitive offrent une flexibilité supplémentaire et offrent une efficacité améliorée à l'utilisation globale du spectre.

Ces technologies peuvent être combinées ou déployées de manière indépendante, et peuvent être mises en oeuvre dans des systèmes de tout service de radiocommunication, n'importe quel système utilisant des technologies de radio logicielle restreinte ou de radio cognitive doit fonctionner conformément aux dispositions du règlement des radiocommunications. La technologie radio logicielle restreinte fonctionne maintenant dans certains systèmes et réseaux dans les services mobiles, de radiodiffusion et de radiodiffusion par satellite, fixe et mobile par satellite. Elle offre une flexibilité dans la conception du système radio et peut aider à la compatibilité directe. La mise en oeuvre complète du concept de systèmes de radio logicielle restreinte et de systèmes de radio cognitive est susceptible d'être réalisée progressivement pour plusieurs raisons, y compris l'état actuel de la technologie. L'utilisation de ces technologies dans certains groupes peut poser des défis spécifiques et uniques de nature technique ou opérationnelle, qui doivent faire l'objet d'une évaluation attentive et complète de l'union international de télécommunication.

1 Architecture des réseaux de radio cognitive

	L'architecture des réseaux de radio cognitive se divise en deux : réseau primaire et réseau
	secondaire.
	1.8.1.1 Réseau primaire
	Le réseau primaire comporte une licence, cette dernière est attribuée par des organisations
	gouvernementales. Les réseaux mobiles sont un modèle de réseaux primaires dans lesquels les
	bandes spectrales sont les possesseurs.

Les réseaux de radio cognitive sont une approche novatrice de l'ingénierie sans fil dans laquelle les radios sont conçues avec un niveau d'intelligence et d'agilité sans précédent. Cette technologie avancée permet aux appareils radio d'utiliser le spectre (c'est-à-dire les fréquences radio) de manière entièrement nouvelle et sophistiquée. Les radios cognitives ont la capacité de surveiller, de détecter les conditions de leur environnement d'exploitation et de reconfigurer dynamiquement leurs propres caractéristiques pour mieux correspondre à ces conditions. À l'aide de calculs complexes, les réseaux de radio cognitive (RRC) peuvent identifier des altérations potentielles pour la qualité de la communication, comme les interférences, la perte de chemin, l'ombre et la décoloration multi-voies. Ils peuvent ensuite ajuster leurs paramètres de transmission, tels que la puissance, la fréquence et la modulation pour assurer une expérience de communication optimisée pour les utilisateurs.

1.8.

Le réseau primaire détient deux éléments :

-Utilisateur primaire (PU) : L'utilisateur primaire possède une licence qui lui simplifie l'accès à certaines bandes spectrales. Elle lui offre également la capacité d'opérer à tout moment sur ces stations de base et de ne pas être perturbé par des utilisateurs inconnus. L'accès est inspecté uniquement par leurs stations de base, là où aucune interférence extérieure ne doit intervenir.

-Station de base des PU : La station de base des PU est une architecture immobile du réseau primaire qui lui est doté d'une licence lui permettant d'agir sur la bande spectrale telle que les stations de base des systèmes cellulaires.

1.

8.1.2 Réseau secondaire Nommé

  Le serveur spectral fait partie du RRC, il est utilisé pour partager

	les ressources spectrales entre plusieurs URC dans le même réseau. Ce serveur est
	relié à chaque réseau secondaire et opère comme un gestionnaire d'information
	spectrale.
	1.8.2 Fonctions des réseaux de radio cognitive
	Les principales fonctions des réseaux de radio cognitive sont :
	secondaire SU appelé aussi utilisateur non-licencié, ne dispose pas de licence pour
	pouvoir diffuser sur la bande spectrale. Cependant, ils seront aptes à partager la bande
	spectrale avec les utilisateurs primaires à l'aide des fonctionnalités supplémentaires
	dont ils sont équipés.

réseau non-licencié car il ne possède pas de licence pour fonctionner sur la bande spectrale. D'où le besoin de plusieurs fonctionnalités supplémentaire afin de classer les bandes spectrales licenciées de façon opportuniste, le réseau secondaire se compose de quatre éléments :

-Utilisateur à radio cognitive : L'utilisateur à radio cognitive URC, ou bien utilisateur -Station de base des URC : nommée aussi station de base non licenciée, est une architecture immobile dotées de capacités cognitives. L'URC se connecte à la station de base pour accéder à d'autre réseaux ou services.

-Serveur spectral :

1.8.2.1 Détection du spectre (Spectrum sensing)

La détection du spectre permet au réseau de radio cognitive de réunir les informations sur l'état d'utilisation des bandes spectrales. Le RRC doit donc détecter les bandes utilisées par les PU et les SU ainsi que les trous du spectre avant de faire l'attribution des bandes du spectre aux SU. En effet, le RRC doit repérer les informations concernant la transmission des PU et des SU pour mesurer l'interférence qu'ils peuvent accepter et s'ils peuvent coexister avec les autres utilisateurs secondaires, puisque le RRC assure un accès dynamique au spectre pour les SU, il doit aussi détecter les trous du spectre ou les bandes du spectre non utilisées afin de les utiliser dans la prochaine allocation. Les trous du spectre peuvent provenir des bandes sous licence appartenant aux utilisateurs primaires qui lâchent dans certain cas leurs bandes et donc le RRC pourra les affecter aux utilisateurs secondaires. Ils peuvent aussi provenir des bandes non soumises à des licences qui était utilisée par les utilisateurs secondaires qui les ont lâchés pour utiliser des bandes plus favorables en termes de qualité de service.

  doit être trouvée. L'idée de base est que l'on peut déduire une ou la solution optimale d'un problème en combinant des solutions optimales d'une série de sousproblèmes consistant à choisir des séquences plus courtes de décisions. Les solutions des problèmes sont calculées de manière ascendante, c'est-à-dire qu'on débute par les solutions

	des sous-problèmes les plus petits pour ensuite déduire progressivement les solutions de
	l'ensemble [16].
	La programmation dynamique est une approche d'optimisation qui transforme un problème
	complexe en une séquence de problèmes plus simples, sa caractéristique essentielle est la
	nature à plusieurs stades de la procédure d'optimisation. En plus des techniques d'optimisation
	décrites précédemment, la programmation dynamique fournit un cadre général pour analyser

, elle s'appuie sur un principe simple, appelé le principe d'optimalité de Bellman : « Une politique optimale est formée de sous-politiques optimales ». Le mot politique désigne une séquence de décisions définissant une solution d'un problème d'optimisation. Concrètement, la programmation dynamique est une méthode utilisée pour résoudre des problèmes où une séquence de décisions optimale de nombreux types de problèmes. Dans ce cadre, une variété de techniques d'optimisation peut être utilisée pour résoudre des aspects particuliers d'une formulation plus générale.

Habituellement, la créativité est nécessaire avant de pouvoir reconnaître qu'un problème particulier peut être efficacement lancé en tant que programme dynamique, et souvent des idées subtiles sont nécessaires pour restructurer la formulation afin qu'elle puisse être résolue efficacement.

  Dans le cadre de ce travail nous avons étudié deux métaheuristique à base d'intelligence par essaim, le cuckoo search (CS) et l'algorithme des lucioles (FA).

	2.3.2.1 Cuckoo search
	 Inspiration
	Cuckoo sont des oiseaux éblouissant, non seulement à cause des beaux sons qu'ils peuvent
	faire, mais aussi à cause de leur stratégie de reproduction agressive. Certaines espèces comme
	les ani et Guira cuckoos pondent leurs oeufs dans des nids communautaires, mais ils peuvent
	retirer les oeufs des autres pour augmenter la probabilité d'éclosion de leurs oeufs. Un certain
	nombre d'espèces engage le parasitisme obligatoire en posant leurs oeufs dans les nids d'autres
	déplacement très simples dans l'espace des solutions, les parties peuvent converger  Lévy flight
	progressivement vers un minimum local. Cette métaheuristique donne l'aspect de mieux Dans la nature, la recherche des animaux pour la nourriture est d'une manière aléatoire ou
	fonctionner pour des espaces en variables continues. quasi-aléatoire. En général, le chemin de recherche de nourriture d'un animal est
	Au départ de l'algorithme, chaque partie est donc positionnée aléatoirement ou non dans véritablement une marche aléatoire car le prochain mouvement est basé sur la localisation

intelligence artificielle (IA), l'intelligence en essaim fait référence à cette intelligence collective des sociétés d'animaux. Elle a fait l'objet de nombreux travaux de recherche, ce type d'algorithme se repose entre autres sur un modèle permettant de simuler le déplacement d'un groupe d'individus (oiseaux, insectes…). Cette méthode d'optimisation s'appuie sur la collaboration des individus entre eux. Cette idée veut qu'un groupe d'individu peu intelligent puisse posséder une organisation globale complexe. De même, grâce à des règles de l'espace de recherche du problème. Chaque itération fait bouger les parties en fonction de trois composantes : sa meilleure solution, sa vitesse de déplacement ainsi que la meilleure solution obtenue dans son voisinage. oiseaux d'accueil (souvent d'autres espèces). Certains oiseaux hôtes peuvent engager un conflit direct avec les cuckoos intrus. Si un oiseau hôte découvre que les oeufs ne sont pas sa propriété, il va soit jeter ces oeufs exotiques loin ou tout simplement abandonner son nid et construit un nouveau nid ailleurs.

Certaines espèces des cuckoo telles que le couvain-parasitaire Tapera ont évolué de telle manière que les cukoos parasites femelles sont souvent très spécialisés dans la mimique en couleur et motif des oeufs de quelques espèces hôtes choisies. Ceci réduit la probabilité de leurs oeufs étant abandonné et augmente ainsi leur reproductivité. De plus, le moment de la ponte de certaines espèces est également étonnant. Parasite cuckoos choisissent souvent un nid où l'oiseau hôte viens juste de poser ses propres oeufs. En général, les oeufs de cuckoo éclosent un peu plus tôt que les oeufs des hôtes. Une fois que le premier poussin cuckoo est hachurée, la première action de l'instinct est qu'il il va expulser les oeufs hôtes aveuglément en les propulsant hors du nid, ce qui augmente la part du poussin cuckoo de nourriture fournie par son oiseau hôte. Les études montrent également qu'un poussin cuckoo peut aussi imiter l'appel de poussins d'accueil pour avoir accès à plus de possibilités d'alimentation.

[START_REF] Yang | Cuckoo search via Lévy flights[END_REF]

(état actuel), et la probabilité de transition au prochain emplacement. Quelle direction il choisit dépend implicitement sur une probabilité qui peut être modélisée mathématiquement.

  Dans une situation où l'on ne connait rien sur le problème à résoudre, il est important que la population initiale soit répartie sur tout le domaine de recherche.Par contre le choix d'une population avec une taille trop grande peut augmenter considérablement le temps de calcul sachant que le temps est un critère primordial dans le cadre de ce travail, et si la taille de la population est trop petite, il y aura une convergence rapide car l'algorithme n'a pas un grand aperçu sur l'espace de recherche, dans ce rapport la taille de la population qu'on a pu choisir afin de parvenir à de meilleurs résultats est 100.Le classement se fait par rapport à la fonction objectif, de ce fait dans notre algorithme le classement se fait selon l'intensité de la lumière de chaque luciole. Ce classement sert à déterminer le meilleur individu ou le pire individu, dans notre cas la fonction objectif cherche à maximiser les critères donc le classement se fait par ordre croissant ce qui donne que le meilleur est le maximum du classement.

	3.3.3.2 Classement
	Coût	Temps d'exécution en ms	Nombre de SU satisfaits
	295637	1696	22
	Tableau 3.3 : résultats de l'algorithme Cuckoo search
	3.3.3 L'algorithme Firefly
	3.3.3.1 Génération de la population initiale

L'algorithme des lucioles « Firefly algorithm » génère une population initiale qui est une combinaison de solutions possibles, cette population est initialisée aléatoirement.

  La mise en place de l'algorithme des lucioles n'est pas si compliqué contrairement à son paramétrage car le choix des valeurs est une étape assez difficile, tout d'abord car ces paramètres dépendent du type de problème à résoudre, la plupart du temps les valeurs de ces paramètres sont configurées en fonction des résultats obtenus lors d'une séquence d'exécution de l'algorithme. Dans notre algorithme Firefly nous avons pris en compte différents paramètres comme la taille de la population initiale ainsi que l'attraction de la luciole qui est en relation avec l'intensité de la lumière, la distance aussi car c'est un paramètre très important et enfin le coefficient d'absorption γ∈ [0,1], car il contrôle la variation de l'attractivité en fonction de la distance entre deux lucioles. Après avoir fait une dizaine d'exécutions de notre algorithme nous avons pu obtenir nos résultats en termes de temps d'exécution, coût et nombre de SU satisfaits. Le tableau suivant représente les différents résultats obtenus : Dans cette partie, nous allons élaborer une comparaison entre les résultats obtenus avec l'implémentation de la programmation dynamique ainsi que les deux métaheuristiques Cuckoo search et Firefly. Cette comparaison a été conçue en se basant sur plusieurs critères, qui sont : le temps de traitement côté PU, le coût et le nombre de SU satisfaits.

	Coût	Temps d'exécution en ms	Nombre de SU satisfaits
	291154	1925	30
		Tableau 3.4 : résultats de l'algorithme Firefly
	3.4 Etude Comparative

  On remarque aussi que le temps de traitement pour la programmation dynamique va diminuer entre 4 et 16 threads pour se stabiliser après avoir franchis la barre des 16 threads, notez bien qu'une fois le nombre de 32 threads dépassé, le graphe va s'accroître à cause de la perte du temps lors de la communication entre les threads. Donc, d'après notre étude, on peut dire que la programmation dynamique offre de meilleurs résultats lorsqu'on utilise plus de 4 threads, c'est-à-dire qu'en combinant la programmation dynamique (méthode exacte) et les threads, on obtient des résultats remarquablement supérieurs aux cuckoo search et firefly (métaheuristiques).

	Il est nécessaire pour l'utilisateur primaire de satisfaire les demandes des utilisateurs
	secondaires dans un laps de temps très court, car ce critère est très important à cause de
	l'environnement de la radio cognitive et aussi pour satisfaire la demande des utilisateurs
	secondaire.
	1	2	4	8	16	32
	3645	2862	1564	1100	700	700

Au début, la différence est remarquable entre les trois graphes de la figure

3

.3 qui illustre le temps de traitement des trois algorithmes. On remarque que les résultats des deux métaheuristique cuckoo search et firefly sont fixes, leurs valeurs sont inchangées par rapport au graphe de la programmation dynamique qui dépend du nombre de threads. On voit clairement que le temps de traitement (d'exécution) diminue pour la programmation dynamique en utilisant plus de threads. A partir de 4 threads, on constate que la programmation dynamique se rapproche des deux métaheuristiques pour ensuite les dépasser et obtenir de meilleurs résultats.

Tableau 3.1 : temps d'exécution en fonction du nombre de threads


Simona Dobre
email: simona.dobre@cran.uhp-nancy.fr

Sorin Olaru
email: sorin.olaru@supelec.fr

Didier Dumur
email: didier.dumur@supelec.fr

Explicit predictive control laws with a nonlinear constraints handling mechanism

Keywords: Predictive control, constraints, parameterized polyhedra

This paper is dealing with the receding horizon optimal control techniques having as main goal the reduction of the computational effort inherent to the use of on-line optimization routines. The off-line construction of the explicit solution for the associated multiparametric optimization problems is advocated with a special interest in the presence of nonlinearities in the constraints description. The proposed approach is a geometrical one, based on the topology of the feasible domain. The resulting piecewise linear state feedback control law has to accept a certain degree of suboptimality, as it is the case for local linearizations or decompositions over families of parametric functions. In the presented techniques, this is directly related to the distribution of the extreme points on the frontier of the feasible domain.

I. INTRODUCTION

Conceiving optimal control policies implies the use of an infinite horizon for accounting the system behavior for coping with all the possible system evolutions. However, the infinite horizon will lead in a general case to an infinite number of optimization variables. Adding the presence of constraints and eventually the structural problems inherited from the model used for the prediction, one can have the picture of the difficulties in implementing such an infinite horizon optimal control algorithm.

The Model-based Predictive Control (MPC) is the practical methodology which uses an optimization based philosophy but only emulates the infinite horizon by sliding the prediction window [START_REF] Camacho | Model Predictive Control[END_REF], [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF]. It leads by consequence to a tractable computational framework with interesting constraints handling capabilities.

The control action u t at state x t is obtained from the control sequence k * u = [u T t , . . . , u T t+N -1 ] T as a result of the optimization problem:

min ku ϕ(x t+N ) + N -1 k=0 l(x t+k , u t+k ) subj. to : x t+1 = f (x t ) + g(x t )u t ; h(x t , k u ) ≤ 0 (1)
constructed for a finite prediction horizon N , cost per stage l(.), terminal weight ϕ(.), the system dynamics described by f (.), g(.) and the constraints written in a compact form using elementwise inequalities on functions linking the states and the control actions, h(.).

The present paper deals with the case when ϕ and l are quadratic functions of x and k u , f and g are linear, leading to an optimisation problem :

k * u = arg min ku 0.5k T u Hk u + k T u F x ( 2
)
A in k u ≤ b in + B in x f (x, k u ) 0
Unfortunately, the control sequence k * u is optimal only for a single initial condition -x t and produces an openloop trajectory which contrasts with the need for a feedback control law. This drawback is overcome by solving the local optimization [START_REF] Goodwin | Constrained Control and Estimation[END_REF] for every (measured) state, thus indirectly producing a state feedback law. However, taking into account that the measurements can be available faster than the optimal control sequence becomes available (as output of the optimization solver), an important information can be lost with irreversible consequences on the closed-loop performances.

The system state can be interpreted as a vector of parameters, and the problems to be solved are part of the multiparametric optimization programming family [START_REF] Gal | Multiparametric Linear Programming[END_REF]. From the cost function point of view, the parametrization is somehow easier to deal with, the unconstrained optimum being k uc u = H -1 F x. The parametrization of the feasible domain is more difficult to deal with. The approach adopted in the following uses the concept of parameterized polyhedra for the convex sets and Voronoi partitions of the parameters space for the non-convex case. This is equivalent to constraints linearization, their activation with respect to the optimum search being then readily expressed [START_REF] Goodwin | Constrained Control and Estimation[END_REF] (as long as the Abadie's constraints qualification holds). Indeed, the KKT optimality conditions can be used for characterizing the partitions of the state space for the control law. From the computational point of view, this is the technique which assures the less computational effort [START_REF] Tondel | An algorithm for multiparametric quadratic programming and explicit MPC solutions[END_REF]. From the point of view of the feasible domain topology, the dual representation generators/constraints can bring useful information.

One can find in the literature alternative techniques for explicit solution construction in the case of nonlinear systems. The main assumption consists in the convexity of the optimisation problem. In [START_REF] Fotiou | An algebraic geometry approach to nonlinear parametric optimization in control[END_REF] a linearization is done over a specific class of functions (polynomial), in [START_REF] Grancharova | Computational Aspects of Approximate Explicit Nonlinear Model Predictive Control[END_REF] a sampling of the parameters space is performed or one can replace directly the nonlinear bounds of the feasible domain by an approximated linearized one [START_REF] Olaru | Explicit constrained model predictive control. The influence of constraints redundancy[END_REF].

II. FROM FINITE TIME OPTIMAL CONTROL TO MULTIPARAMETRIC OPTIMIZATION

MPC implies the minimization of a cost index based on the predicted plant evolution. The first part of the optimal control sequence is effectively applied after the "receding horizon principle".

A. Optimal control

Consider the discrete linear time-invariant system in a state-space description:

x t+1 = Ax t + Bu t y t = Cx t , t ∈ N + (3)
where x t ∈ R n and u t ∈ R m are the state and control vector. It is assumed throughout that the pair (A, B) is stabilizable. At each sampling time, the current state (assumed to be available) x t = x t|t can be used to find the

optimal control sequence k * u = u T t|t , • • • , u T t+Ny-1|t T : k * u = arg min ku x T t+Ny|t P x t+Ny|t + + Ny-1 k=0 x T t+k|t Qx t+k|t + u T t+k|t Ru t+k|t (4) subject to:    x t+k+1|t = Ax t+k|t + Bu t+k|t , k 0 g u t+k|t , x t+k|t γ, 0 k N y -1 u t+k|t = K LQR x t+k|t + e, N u k N y -1
where Q = Q T 0 and R = R T > 0 are the weighting matrices and the pair Q 1/2 , A is detectable. The inequality constraints are fully described by the Lipschitz function, g and by γ ∈ R q . The prediction horizon -N y , the control horizon N u N y -together with Q and R are the knobs of the control design. K LQR is the stabilizing feedback control gain for unconstrained linear systems calculated using the solution of a discrete algebraic Riccati equation:

P = Q + A T P A -K T LQR R + B T P B K LQR K LQR = R + B T P B -1 B T P A ( 5
)
and e is the new input vector, calculated as:

e = C (I -A + BK LQR ) -1 B -1 y c ( 6
)
with y c the desired output.

The optimization problem presented here is a modified version of the constrained infinite horizon linear quadratic problem where both the cost index and the inequality constraints are defined along an infinite prediction horizon. The fact that the explicit constraints cover here only the instants until N y is due to the implicit terminal conditions implying that the choice of N y is made such that the usage of u t+k|t = K LQR x t+k|t + e will not trespass the feasible region for k N y . Constructive methods exist to determine the appropriate N y for each specific system and set of constraints. The overall optimisation problem is tractable with standard quadratic methods as it has p = m • N y decision variables and (q + m) N y constraints (with q -the number of inequality constraints).

Compacting the state involved in the optimization problem [START_REF] Camacho | Model Predictive Control[END_REF]

as x = x T t+1|t , • • • , x T t+Ny|t T
and noting x = x t|t the cost function could be rewritten in the matrix formulation as:

k * u = arg min ku x T Qx + x T Qx + k T u Rk u (7) subject to : h (x, x, k u ) γ J • k u = K • x + ē where Q = diag [Q, • • • , Q, P ] ∈ R Nyn×Nyn , R = diag [R, • • • , R] ∈ R Nym×Nym , K = 0 (Ny-Nu)m×Nun diag [K LQR , • • • , K LQR ] J = 0 (Ny-Nu)m×Num I (Ny-Nu)m ē =    e . . . e    ∈ (Ny-Nu)m×1 , γ =      γ γ . . . γ      ∈ Nyq×1 h (x, x, k u ) =    g x, u t|t . . . g x t+Ny-1|t , u t+Ny-1|t    .
The system's state evolution can be transformed in a compact form:

x = Φx + Γk u [START_REF] Olaru | Explicit constrained model predictive control. The influence of constraints redundancy[END_REF] with

Φ =      A A 2 . . . A Ny      ∈ Nyn×n and Γ =        B 0 n×m 0 n×m • • • 0 n×m AB B 0 n×m • • • 0 n×m A 2 B AB B • • • 0 n×m . . . . . . . . . . . . . . . A Ny-1 B A Ny-2 B A Ny-3 B • • • B       
The optimization problem (2) within MPC becomes:

k * u = arg min ku k T u Hk u + 2k T u F x + x T Gx (9) subject to f (x, k u ) b in A eq k u = b eq + B eq x with H = R+Γ T • Q•Γ, F = Γ T • Q•Φ, G = Q+Φ T • Q•Φ, b in = γ, A eq = J -K • Γ, B eq = K • Φ, b eq = ē and f (x, k u ) = h (x, Φ • x + Γ • k u , k u ).

III. PARAMETRIZATION OF POLYHEDRAL DOMAINS

A. Double representation

A mixed system of linear equalities and inequalities defines a polyhedron [START_REF] Motzkin | The Double Description Method[END_REF]. In the parameter free case, it is represented by the equivalent dual (Minkowski) formulation:

P = {k u ∈ R p |A eq k u = b eq ; A in k u ≤ b in } ⇐⇒ P = conv.hullV + coneR + lin.spaceL generators ( 10
)
where conv.hullV denotes the set of convex combinations of vertices V = {v 1 , . . . , v ϑ }, coneR denotes nonnegative combinations of unidirectional rays in R = {r 1 , . . . , r ρ } and lin.spaceL = {l 1 , . . . , l λ } represents a linear combination of bidirectional rays (with ϑ, ρ and λ the cardinals of the related sets). This dual representation [START_REF] Schrijver | Theory of linear and integer programming[END_REF] in terms of generators can be rewritten as:

P = k u ∈ R p | k u = ϑ i=1 α i v i + ρ i=1 β i r i + λ i=1 γ i l i ; 0 ≤ α i ≤ 1, ϑ i=1 α i = 1 , β i ≥ 0 , ∀γ i (11
) with α i , β i , γ i the coefficients describing the convex, nonnegative and linear combinations in [START_REF] Leverge | A note on Chernikova's algorithm[END_REF].

Numerical methods like the Chernikova algorithm [START_REF] Leverge | A note on Chernikova's algorithm[END_REF] are implemented for constructing the double description, either starting from constraints [START_REF] Leverge | A note on Chernikova's algorithm[END_REF] either from the generators ( 11) representation.

B. The parametrization

A parameterized polyhedron [START_REF] Loechner | Parameterized polyhedra and their vertices[END_REF] is defined in the implicit form by a finite number of inequalities and equalities with the note that, in both cases, the affine part depends linearly on a vector of parameters x ∈ R n :

P(x) = k u (x) ∈ R p |A eq k u = B eq x + b eq ; A in k u ≤ B in x + b in } = k u (x)| k u (x) = ϑ i=1 α i (x)v i (x) + ρ i=1 β i r i + λ i=1 γ i l i 0 ≤ α i (x) ≤ 1, ϑ i=1 α i (x) = 1 , β i ≥ 0 , ∀γ i . ( 12
)
This dual representation of the parameterized polyhedral domain reveals the fact that only the vertices are concerned by the parametrization (resulting the so-called parameterized vertices -v i (x)), whereas the rays and the lines do not change with the parameter's variation. In order to effectively use the generators representation in [START_REF] Schrijver | Theory of linear and integer programming[END_REF], several aspects have to be clarified regarding the parametrization of the vertices (see for exemple [START_REF] Loechner | Parameterized polyhedra and their vertices[END_REF] and the geometrical toolboxes like POLYLIB [START_REF] Wilde | A library for doing polyhedral operations[END_REF]). Indeed the projections are to be computed for all the nfaces, those which are degenerated are to be discarded and all the others are stored as validity domains -D vi ∈ R n , for the parameterized vertices that they are identifying:

D vi = Proj n F n j ( P ) (13)
Once the parameterized vertices are identified and their validity domain stored, the dependence on the parameters vector can be found using the supporting hyperplanes for each n-face:

v i (x) = A eq Āinj -1 B eq Binj x + b eq binj (14)
where Āinj , Binj , binj represent the subset of the inequalities, satisfied by saturation for F n j ( P ). The inversion is well defined as long as the faces with degenerate projections are discarded.

IV. MULTIPARAMETRIC OPTIMIZATION In [START_REF] Motzkin | The Double Description Method[END_REF], the optimization problem acts in the space of future control actions while the current state vector x influences the unconstrained optimum and the affine part of the constraints, acting as a parameter. This dependance transforms the classical optimization problem in a multiparametric one (the use of "multiparametric" syntagm is for discriminating the case when the parameter is scalar).

A. A mature framework

A popular class of control problems described by ( 9) presents quadratic cost functions and linear constraints:

k * u = arg min ku 0.5k T u Hk u + k T u F x subject to : A in k u ≤ b in + B in x ( 15
)
This is known in the literature as the multiparametric quadratic problem (mpQP) and its optimality conditions (Karush-Kuhn-Tucker) are resumed by:

• Primal feasibility:

A in k * u B in x + b in ( 16
)
• Dual feasibility:

Hk * u + F T x + A T in µ = 0 µ 0 (17)
• Complementary slackness:

µ T (A in k * u -B in x -b in ) = 0 (18)

B. Explicit solution for mpQP

Exploiting these conditions the global solution can be explicitly represented by a piecewise linear and continuous function [START_REF] Bemporad | The explicit linear quadratic regulator for constrained systems[END_REF], [START_REF] Seron | Characterisation of Receding Horizon Control for Constrained Linear Systems[END_REF]:

k * u (x) = K i * x + κ i , for x ∈ D i , i ∈ I ( 19
)
with I ⊂ N the index set for all combinations of constraints ( Āin , Bin , bin ) saturated by a local optimum. The linear dependence is assured by:

K i = H -1 ĀT in ( Āin H -1 ĀT in ) -1 ( Bin + Āin H -1 F T )- -H -1 F T ; κ i = H -1 ĀT in ( Āin H -1 ĀT in ) -1 b in , ( 20
) and the regions D i are convex polyhedra in R n defined by:

(A in K i -B in )x ≤ b in -κ i -( Āin H -1 ĀT in ) -1 ( Āin H -1 F T x + bin + Bin x) ≥ 0 (21)
the second set of inequalities being originated by the positiveness of the Lagrange multipliers (µ i ≥ 0). MPC uses only the first component of this optimal solution:

u MP C (x) = K MP C i * x + κ MP C i , with i s.t. x ∈ D i , ( 22
) and K MP C i , κ MP C i the first components of K i , κ i .

C. A topological approach

The piecewise linear structure of the optimal solution can be obtained also by using the parameterized vertices [START_REF] Bemporad | The explicit linear quadratic regulator for constrained systems[END_REF] associated to the set of active constraints [START_REF] Olaru | A Parameterized Polyhedra Approach for Explicit Constrained Predictive Control[END_REF]. In this case the main idea is to consider the unconstrained optimum:

k uc u (x t ) = H -1 F x t and its position with respect to the feasible domain given by a parameterized polyhedron as in [START_REF] Schrijver | Theory of linear and integer programming[END_REF].

If a simple transformation is performed:

ku = H 1/2 k u
then the isocost curves of the quadratic function are transformed from ellipsoid into circles centered in kuc u (x t ) = H -1/2 F x t . Further one can use the Euclidean projection in order to retrieve the explicit solution. Indeed if the unconstrained optimum kuc u (x t ) is contained in the feasible domain P(x t ) then it is also the solution of the constrained case, otherwise existence and uniqueness are assured as follows:

Proposition: For any exterior point ku (x t ) / ∈ P(x t ), there exists an unique point characterized by a minimal distance with respect to kuc u (x t ). This point satisfies:

( kuc u (x t ) -k * u (x t )) T ( ku -k * u (x t )) 0, ∀ ku ∈ P(x t )
The construction mechanism uses the parameterized vertices in order to split the regions neighboring the feasible domain in zones characterized by the same type of projection. In figure 1 a simple example is given starting from the parameterized polyhedron P in the extended space (argument and parameters), the regions with the same type of projection are found and finally the explicit solution in terms of a piecewise linear function of parameters is obtained.

V. HANDLING NONLINEARITIES

Consider now the case of mixed type of constraints (linear/nonlinear):

k * u = arg min ku 0.5k T u Hk u + k T u F x (23) h (x, k u ) 0 A in k u ≤ b in + B in x
An important point to note is the quadratic form of the cost function which offers interesting structural properties (convexity, uniqueness of the unconstrained optimum). This is not restricting the generality for control systems described by (3) as long as the usual choice for the cost function is the "sum of squared error weighted by (norm 2) control effort".

A. Optimality conditions for nonlinear constraints

Let x be a feasible parameter vector. The KKT optimality conditions can still be formulated as:

• Primal feasibility:

h (x, k u ) 0 A in k u ≤ b in + B in x (24)
• Dual feasibility:

Hk u + F T x + A T in µ + ∇ ku h(x, k u ) T ν = 0 µ 0, ν 0 (25) • Complementary slackness: [µ T ν T ] A in k u -B in x -b in h (x, k u ) = 0 (26)
The difference resides in the fact that the KKT conditions are only necessary and not sufficient for optimality due to the presence of nonlinearity.

B. The topology of the feasible domain

Indeed the sufficiency is lost due to the lack of constraint qualification (the Abadie constraint qualification holds automatically for the linear constraints but needs additional assumptions for the nonlinear case, see the next theorem).

Theorem (KKT sufficient conditions) [1]: Let x = x and the associated feasible domain U(x) be a nonempty set in R Nym described by the constraints in (23), with

h i (x, k u ) : R Nym → R, the components of h(x, k u ). Let k * u ∈ U(x) and let I = {i : h i (x, k * u = 0)} , J = j : A inj k * u -B inj x -b inj = 0)
. Suppose the KKT conditions hold, such that:

Hk * u + F T x + µ j A T inj + ν i ∇ ku h i (x, k * u ) T = 0 (27) If h i is quasiconvex at k * u for i ∈ I,

then this is a global solution to the problem (23)

Due to these problems, up to date, the explicit solutions for the general nonlinear multiparametric programming case were not tackled. Only for convex nonlinearities approximate explicit solutions were proposed [START_REF] Grancharova | Computational Aspects of Approximate Explicit Nonlinear Model Predictive Control[END_REF].

In the following a solution based on linear approximation of feasible domains is proposed. This will answer the question regarding the optimality of a solution with piecewise linear structure.

C. Preliminaries for linear approximations of mixed linear/nonlinear feasible domains

The idea is to exploit the existence of linear constraints in (23) and construct exact solutions as long as the unconstraint optimum can be projected on them. In a second stage if the unconstrained optimum is projected on the convex part of the nonlinear constraints, then an approximate solution is obtained by their linearization. Finally if the unconstrained optimum has to be projected on the nonconvex nonlinear constraints then a Voronoi partition is used to construct the explicit solution.

Before detailing the algorithms several useful tools have to be introduced: Figure 2 illustrates two common types of gridding, the linear and the spherical one (note that the linear distribution of points can be very conservative for large dimensions spaces). For each point of the grid x ∈ G a set of points on the frontier of the feasible domain D(x) can be obtained V x by the same kind of parceling. By collecting V x for all x ∈ G a distribution of points V G in the extended arguments+parameters space is obtained.

2) Convex hulls: A basic operation is the construction of the convex hull (or a convenable approximation) for the feasible domain in (23). Writing this parameterized feasible domain as:

D(x) = k u h (x, k u ) 0 A in k u ≤ b in + B in x (28)
and using the distribution of points on the frontier V G , one can define in the extended (argment+parameters) space a convex hull C VG :

C VG = k u x ∈ R mNy+n ∃ k ui x i , i = 1..mN y + n + 1, k ui ∈ V G , t.q. k u x = mNy+n+1 i=1 λ i k ui x i , mNy+n+1 i=1 λ i = 1; λ i ≥ 0 } (29)
3) Voronoi partition: The Voronoi partition is the decomposition of a metric space R n in regions associated with a specified discrete set of points.

Let S = {s 1 , s 2 , ..., s ν } be a collection of ν points in R n . For each point s i a set V i is associated such that i V i = R n . The definition of V i will be:

V i = {x ∈ R n | x -v i 2 ≤ x -v i 2 , ∀j = i} (30)
It can be observed that each frontier of V i is part of the bisection hyperplane between s i and one of the neighbor points s j . As a consequence of this fact, the regions V i are polyhedrons. Globally, the Voronoi partition is a decomposition of space R n in ν polyhedral regions.

D. Nonparameterized case

Notation:

F(X)
The frontier of a compact set X Int(X)

The interior of a compact set X Consider nonparameterized optimization problem with mixed type of constraints:

k * u = arg min ku 0.5k T u k u + c T k u (31) h (k u ) 0 A in k u ≤ b in + B in x
C V 3) Split the set V as V ∪ V L ∪ V NL ∪ V • V ∈ F(C V ) and C V = C V\ V (those points in
V which lie on the frontier of C V but are not vertices);

• V L ∈ V \ V, V L ∈ F(C V ) and V L saturate at least one linear constraint in (31) • V NL ∈ V \ V, V NL ∈ F(C V ) and V NL saturate only nonlinear constraints in (31) • V ∈ Int(C V ) 4)
Construct the dual representation of C V . This will be represented as an intersection of halfspaces H.

5) Split H in H ∪ H • H ⊂ H such that ∃x ∈ C V with S( H, x) = ∅ and B(R NL , x) = ∅ • H = H \ H 6) Project the unconstrained optimum k u = -c on C V : k * u ← P roj C V {-c} (as it was illustrated in figure 1c) 7) If k *
u saturates a subset of constraints K ⊂ H a) Retain the set of points:

S = v ∈ V|∀k u ∈ C V s.t. Sat( H, k u ) = K; B(R NL , k u ) = Sat(R NL , v

E. Explicit solution -taking into account the parametrization

Consider now the multiparametric optimization:

k * u = arg min ku 0.5k T u Hk u + k T u F x (32) h (x, k u ) 0 A in k u ≤ b in + B in x
and the set:

D = k u x ∈ R mNy+n h (x, k u ) 0 A in k u ≤ b in + B in x
Algorithm: 1) Grid the parameters space R n and retain the feasible nodes G 2) Obtain in the extended argument+parameters space a set of points (V G ) lying on the frontier of D 3) Construct the convex hull C V for the points in

V G 4) Split the set V G as V ∪ V L ∪ V NL ∪ V • V ∈ F(C V ) and C V = C V\ V (those points in
V which lie on the frontier of C V but are not vertices);

• V L ∈ V G \ V, V L ∈ F(C V ) and V L saturate at least one linear constraint in (31) • V NL ∈ V G \ V, V NL ∈ F(C V ) and V NL saturate only nonlinear constraints in (31) • V ∈ Int(C V )
5) Construct the dual representation of C V . This will be represented as a intersection of halfspaces H.

6) Split H in H ∪ H • H ⊂ H such that ∃x ∈ C V with S( H, x) = ∅ and B(R NL , x) = ∅ • H = H \ H 7) Project the set U = k u x k u x = H -1 F I x, ∀x ∈ R n on C V : U * ← P roj C V U 8)
If ∃x 0 such that the point:

k * u x 0 = U * ∩ k u x x = x 0
saturates a subset of constraints

K(x 0 ) = S H, k u x 0 ⊂ H then: a) Construct U NL (x 0 ) = k u x ∈ U k * u x ∈ U * t.q. S H, k u x 0 = K(x 0 )
b) Perform:

U * = U * \ k u x S H, k u x 0 = K(x 0 )
c) Retain the set of points:

S = v ∈ V|∀ k u x ∈ C V with S( H, k u x ) = K(x 0 ) ⇒ B(R NL , x) = S(R NL , v)} d)

VI. NUMERICAL EXAMPLE

A. Simple convex multiparametric nonlinear program

Consider the discrete-time linear system:

x t+1 = 0.9 1 0 1

x t + 1 -1 u t (33)
and a predictive control law with a prediction horizon of three sampling times and a control horizon of two steps.

A nonlinear set of constraints will be also considered:

   2 k=0 u 2 t+k ≤ 1 2 k=0 u 2 t+k ≤ ln( 0 1 x t + 1) 0 1 x t+k ≥ 0; k = 0, 1, 2 (34)
It is obvious that the topology of the feasible domain is changing with the system dynamics, which means that the state vector represents in fact a parameter. More precisely, in our case only the second component of the state, x t is influencing the shape of the feasible domain and thus one can draw this dependence on the parameter as in figure 3. Further this parameterized convex shape can be approxi-Fig. 3.

The nonlinear dependence of the feasible domain on the parameters mated with a set of parameterized linear inequalities and obtain a double description of a parameterized polyhedron as in figure 4(a). A precutting in zones with regular shape (figure 4(b)) can help in the development of explicit solution due to the important degree of redundancy. Finally the nonlinear MPC law for the system (33) and the constraints (34) can be approximated by the explicit solution found in terms of a piecewise linear control law as in figure 5.

B. Example of non-Convex problem

Consider the MPC problem implemented using the first control action of the optimal sequence: x

                                         x t+k+1|t = A 1 1 0 1 x t+k|t + B 1 0 2 1 u t+k|t k 0 -2 -2 u t+k|t 2 2 0 k N y -1 (u 1 t+k|t ) 2 + u 2 t+k|t -2 2 √ 3 0 k N y -1 (u 1 t+k|t ) 2 + u 2 t+k|t + 2 2 √ 3 0 k N y -1 u t+k|t = 0.59 0.76 -0.42 -0.16 KLQR x t+k|t N u k N y -1
One can observe the presence of both linear and nonlinear constraints. By following the previous algorithm, in the first stage, the partition of the state space is performed by considering only the linear constraints (figure 6(a)). Each such region correspond with a specific projection law. By simply verifying the regions where this projection law obey the nonlinear constraints, the exact part of the explicit solution is obtained (figure 6(b)).

Further, a distribution of points on the nonlinear frontier of the feasible domain has to be obtained and the associated Voronoi partition obtained. By superposing it to the regions non covered at the previous step one obtain a complete covering of the arguments space. Figure 7(a) depicts such a complete partition for distribution of 10 points for each nonlinear constraint. Finally the complete explicit solution for the two cases are described in figures 9(a) and 19(b). The discontinuities are observable as well as the increase in resolution over the nonlineairity with the augmentation of the number of points in the Voronoi partition.

In order to give a give an image of the complexity it must be said that the explicit solutions have 31 and 211 regions respectively and the computational effort was less than 2s in the first case and 80s in the second case, mainly spent in the construction of supplementary regions in the Voronoi partition.

VII. CONCLUSIONS

The construction of explicit solution for receding horizon optimal control problems was presented with a special attention to the nonlinear constraints handling mechanism. The geometrical approach exploits the topology of the feasible domain. As long as the unconstraint optimum is projected on a linear set of constraints one obtains the exact solutions. For the regions where the unconstraint optimum violates nonlinear constraints, a technique based on Voronoi partition allows the construction of approximate explicit solution. The degree of suboptimality for the solution under active nonlinear constraints is directly related to the distribution of the extreme points on the frontier of the feasible domain. The presented algorithm can be used in a recursive manner in order to improve the quality of the explicit solution. However this is done with the price of an increased complexity for the piecewise control law.

Fig. 1 .

 1 Fig. 1. From the feasible domain as a parameterized polyhedron to the explicit solution

Fig. 2 .

 2 Fig. 2. Example of grid of the parameters space

1 )

 1 In relation with the feasible domain D of this optimization problem one can define: R L (D) The set of linear constraints in the definition of D R NL (D) The set of nonlinear constraints in the definition of D S(R * , k u ) The subset of constraints in R * (either R L either R NL ) saturated by the vector k u B(R * , k u ) The subset of constraints in R * . violated by the vector k u Algorithm: Obtain a set of points (V) on the frontier of the feasible domain D 2) Construct the convex hull

  )} b) Construct the Voronoi partition for the collection of points in S c) Position k * u w.r.t. this partition and map the suboptimal solution k * u ← v where v is the vertex corresponding to the active region 8) If the quality of the solution is not satisfactory, improve the distribution of the points V by augmenting the resolution around k * u and restart from (2).

  Construct the Voronoi partition for the collection of points in S e) Position U NL (x 0 ) w.r.t. this partition and map the suboptimal solution U * NL (x 0 ) ← U NL (x 0 ) by using the vertex v for each active region. jump to (10) 9) Return to point (8) 10) If the quality of the solution is not satisfactory, improve the distribution of the points V G and restart from (2).

Fig. 4 .

 4 Fig. 4. (a) The approximation by a parameterized polyhedron; (b) Regions in the parameters' space corresponding to redundancy-free constraints sets.

Fig. 5 .

 5 Fig. 5. Explicit solution as a piecewise linear function.

Fig. 6 .

 6 Fig. 6. a) Partition of the arguments space (linear constraints only). b) Retention of the regions with feasible linear projections.

Figure 7 Fig. 7 .

 77 Fig. 7. a) Partition of the arguments space (nonlinear case) -10 points per nonlinear constraint. b) Partition of the arguments space (nonlinear case) -100 points per nonlinear constraint. By correspondence, the figures 8(a) and 8(b) describe the partition of the state space for the explicit solution.

Fig. 8 .

 8 Fig. 8. a) Partition of the state space -10 points per nonlinear constraint. b) Partition of the state space -100 points per nonlinear constraint.

Fig. 9 .

 9 Fig. 9. a) Explicit control law -10 points per nonlinear constraint. b) Explicit control law -100 points per nonlinear constraint.

  T t+k|t Qx t+k|t + u T t+k|t Ru t+k|t +

			+x T t+Ny|t P x t+Ny|t
						(35)
	with
	Q =	10 0 0 1	; R =	2 0 0 3	; P =	13.73 2.46 2.46 2.99