Soutenance mémoire
Exclusion Mutuelle Distribuée
Radio Cognitive
L‘évolution des Systèmes sans fil a déclenché une forte demande en terme de ressources spectrales, ces dernières sont devenues de plus en plus précieuses avec la prolifération rapide de standards et de services de radiocommunication. Le problème réside dans le fait que les systèmes sans fil de communication numérique n’exploitent pas l’intégralité de la bande de fréquence disponible. Pour pallier à ce problème, beaucoup de travaux de recherche ont été réalisés, et l’une des initiatives est l’idée de la radio cognitive (RC). La radio cognitive est une technique prometteuse pour l’utilisation efficace du spectre. Elle doit surveiller l’activité dynamique dans le spectre de l’utilisateur primaire et adapter la transmission des utilisateurs secondaires pour une meilleure allocation des ressources spectrales (Zayen, 2010). Dans ce chapitre, nous commençons par une définition du concept radio cognitive ainsi qu’un bref historique. Ensuite, nous nous intéressons successivement aux différents aspects de la RC : principe de fonctionnement, fonctions, architecture, etc.
La RC est une technologie émergente en matière d’accès sans fil, elle sert à améliorer l’utilisation du spectre radio en permettant l’accès aux opportunités spectrales disponibles de manière dynamique. Une radio cognitive était définie par Mitola dans son travail séminal comme « un système radio ayant la capacité de détecter, de prendre conscience de son environnement opérationnel et peut ajuster de façon dynamique et autonome ses paramètres de fonctionnement radio en conséquence ». Cette définition a été généralisée par la FCC d’être « un système radio ayant la capacité de détecter son environnement électromagnétique et d’ajuster de façon dynamique et autonome ses paramètres de fonctionnement radio afin de modifier le fonctionnement du système» (Khattab, 2012). La RC est une forme de communication sans fil dans laquelle un émetteur/récepteur détecte l’existence des canaux de communication inoccupés, et peut se déplacer dans ces canaux. Ceci permet d’optimiser l’utilisation des fréquences radio disponibles du spectre tout en minimisant les interférences avec d’autres utilisateurs (Benmammar, 2014).
Cette capacité permet d’adapter chaque appareil aux conditions spectrales du moment et offre donc un accès plus souple aux utilisateurs, 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 radio cognitive offre également une solution équilibrée au problème de l’encombrement du spectre. A partir de toutes ces définitions, une radio cognitive a deux caractéristiques principales qui la distinguent d’une radio traditionnelle: la cognition et la reconfigurabilité (Khattab, 2012). La cognition regroupe les divers processus mentaux allant de l’analyse perceptive de l’environnement à la commande motrice (en passant par la mémorisation, le raisonnement, les émotions, le langage…) (Benmammar, 2014). La deuxième caractéristique clé est la reconfigurabilité. Elle représente la capacité à s’adapter à divers paramètres radio de communication à savoir les bandes de fréquences, les largeurs de bandes des canaux radio, les techniques de modulation et de codage, etc. et cela sans avoir à changer la partie matérielle. Ceci afin de pouvoir utiliser la nouvelle bande (Nguyen, 2012).
Exclusion Mutuelle Distribuée
Un système distribué est un système constitué d’un ensemble de processus qui accèdent simultanément à certaines ressources. L’accès concurrent a posé de nouveaux conflits qui ont été résolu au moyen de l’exclusion mutuelle. L’exclusion mutuelle définie par Dijkstra est l’un des paradigmes fondamentaux des systèmes distribués pour garantir des accès cohérents aux ressources partagées. Elle doit assurer qu’au plus un processus peut exécuter une portion de code manipulant une ressource partagée, appelée section critique (SC), et de satisfaire toute demande d’accès à la SC au bout d’un temps fini (Lejeune, 2013). Plusieurs algorithmes d’exclusion mutuelle existent dans la littérature. Ils peuvent être divisés en deux catégories : les algorithmes à permissions et les algorithmes à jeton. Dans ce mémoire nous nous intéresserons à l’exclusion mutuelle distribuée à jeton. Dans ce chapitre, nous commençons néanmoins par une comparaison entre un système distribué et un système centralisé. Ensuite, nous donnons une définition formelle de l’exclusion mutuelle (les différents états des processus, les principales propriétés de l’exclusion mutuelle, …). Nous finissons respectivement par une classification des différentes classes des principaux algorithmes d’exclusion mutuelle distribuée et un état de l’art ainsi qu’une conclusion.
Ordonnancement
L’ordonnancement consiste à étudier les méthodes d’organiser et de planifier l’exécution d’opérations au cours du temps de façon à respecter un ensemble de contraintes. Le problème de la famine apparaît lorsqu’une requête de haute priorité peut empêcher en permanence les autres requêtes de plus basses priorités d’exécuter la SC. Cependant, ce problème est fortement lié à la définition de l’ordre total dans lequel les requêtes ont lieu; ces dernières peuvent être pénalisés par un temps d’attente infini pour accéder à la SC, ce qui viole ainsi la propriété de vivacité (Lejeune, 2013). Afin d’éviter le problème précité, une stratégie a été proposée qui exige que toute requête doit devenir en un temps fini la plus prioritaire de cet ordre (Lejeune, 2014). Dans la majorité des algorithmes, les requêtes sont satisfaites selon une politique d’ordonnancement « First In First Out » (FIFO) grâce à une horloge logique sur les requêtes ou bien grâce à l’horloge physique du détenteur du jeton (Lejeune, 2013). Cette politique d’ordonnancement permet d’assurer la vivacité, ainsi toute requête deviendra en un temps fini la plus prioritaire (Lejeune, 2014).
Etat de l’art
L’un des paradigmes les plus classiques de l’informatique distribuée est l’exclusion mutuelle distribuée. Elle consiste à définir un protocole exécuté par un ensemble de processus qui souhaitent se coordonner pour accéder à la SC, qui ne peut être utilisée que par un processus à la fois. Au cours des dernières années, plusieurs algorithmes d’exclusion mutuelle distribuée ont été proposés pour les réseaux ad hoc. Parmi ceux-ci, on trouve ceux proposés dans (Baldoni, 2002), dans cet algorithme le jeton est passé sur un anneau logique créé dynamiquement où chaque fois qu’un processus reçoit le jeton de son prédécesseur, il décide à la volée en utilisant une politique qui sélectionne comme processus successeur parmi ceux qui n’ont pas encore reçu le jeton. Chaque tour de l’anneau a un coordinateur qui est le seul processus qui peut bloquer le jeton et entrer dans un état inactif. Lorsqu’un noeud souhaite entrer en SC, il envoie une requête au coordinateur, déclenchant ainsi une circulation de jeton. Cela garantit que des scénarios optimaux de circulation de jeton pourraient se produire lorsque la demande de charge est lourde, et en n’émettant aucun message quand aucun processus ne demande la SC.
Cependant, un autre algorithme nommé Reverse Link (RL) est basé sur l’échange de jeton a été proposé dans (Walter, 1998). Le système contient un ensemble de noeuds et de ressources partagées, communiquant par un modèle à passage de messages sur un réseau sans fil. RL construit un graphe acyclique direct orienté par jeton. Ce graphe maintient plusieurs chemins menant au noeud contenant le jeton. Cet algorithme suppose que le réseau ne partitionne pas, les noeuds n’échouent pas et la perte de messages ne se produit pas. Dans l’algorithme RL, lorsqu’un noeud souhaite accéder à la ressource partagée, il envoie un message de demande le long d’une des liaisons de communication. Chaque noeud maintient une file d’attente contenant les identifiants des noeuds de voisinage à partir desquels il a reçu la demande pour le jeton. L’algorithme RL a été étendu respectivement en (Walter, 2001) et (Thiare, 2009) pour traiter le problème d’exclusion k-mutuelle. Ce dernier permet à la plupart des processus d’accéder à leurs sections critiques simultanément. Ceci pourrait être la conséquence où plusieurs copies identiques d’une ressource sont rendues disponibles dans le système ou que la ressource par sa nature peut être accédée par un ensemble de processus simultanément.
Dans le problème d’exclusion mutuelle de groupe (GME), plusieurs ressources sont partagées entre les noeuds. Les noeuds demandant d’accéder à la même ressource partagée peuvent le faire simultanément. Cependant, si les noeuds concourent pour accéder à des ressources différentes, un seul d’entre eux peut procéder. Les algorithmes pour résoudre le problème GME pour les réseaux mobiles ad hoc sont donnés dans (Jiang, 2002), (Thiare, 2007a) et (Myoupo, 2009). Ces algorithmes proposés sont adaptés à partir de l’algorithme RL. Dans ces algorithmes basés sur un jeton, le concept de lancer de poids est appliqué pour détecter que tous les noeuds accédant simultanément à la même ressource ont terminé leurs tâches. Ces algorithmes satisfont à l’exclusion mutuelle, au retard délimité et aux propriétés d’entrée simultanées. Ils sont sensibles à la formation de liens et à la rupture de liaison et convient donc aux réseaux mobiles ad hoc.
|
Table des matières
Table des matières
Liste des figures
Liste des tableaux
Liste des abréviations
Introduction générale
Chapitre I : Radio Cognitive
I.Introduction
II.Définition
III. Historique
IV.Architecture de la RC
V.Principe
VI.Fonctions
VI.1 Détection du spectre (Spectrum sensing)
VI.2 Gestion du spectre (Spectrum management)
VI.2.1 Analyse du spectre
VI.2.2 Décision sur le spectre
VI.3 Mobilité du spectre (Spectrum mobility)
VII. Cycle cognitif
VII.1 Phase d’observation (détecter et percevoir)
VII.2 Phase d’orientation
VII.3 Phase de planification
VII.4 Phase de décision
VII.5 Phase d’action
VII.6 Phase d’apprentissage
VIII. Relation entre la RC et la radio logicielle restreinte(SDR) Composantes de la RC
IX.1 Emetteur / Récepteur
IX.2 Analyseur de spectre (Spectrum analyser)
IX.3 Extraction de connaissances et apprentissage (Knowledge extraction/learning)
IX.4 Prise de décision (Decision making)
X.Langage pour la radio cognitive
XI.Domaines d’application
XI.1 Les réseaux sans fil de prochaine génération
XI.2 Coexistence de différentes technologies sans fil
XI.3 Services de cyber santé (eHealth services)
XI.3.1 Réseaux d’urgence
XI.3.2 Réseaux militaires
XII. Conclusion
Chapitre II : Exclusion Mutuelle Distribuée
I.Introduction
II. Différence entre un système distribué et un système centralisé
III. Définition de l’exclusion mutuelle
III.1 États des processus
III.2 Propriétés
III.3 Ordonnancement
III.4 Extensions de l’exclusion mutuelle
III.4.1 Exclusion mutuelle à priorité
III.4.2 Exclusion mutuelle à contraintes de temps
III.4.3 Exclusion mutuelle généralisée
III.4.4 Exclusion mutuelle de groupe
III.5 Métriques d’évaluation de performances
III.6 Mécanismes d’exclusion mutuelle
IV.Taxonomie des algorithmes distribués
IV.1 Algorithmes à permissions
IV.1.1 Permissions individuelles
IV.1.2 Permissions d’arbitre
IV.1.3 Permissions généralisées
IV.2 Algorithmes à jeton
IV.2.1 Algorithmes à jeton structurés
IV.2.1.1 Topologie statique
IV.2.1.2 Topologie dynamique
IV.2.2 Algorithmes à jeton non-structurés
IV.2.2.1 Algorithmes statiques
IV.2.2.2 Algorithmes dynamiques
Etat de l’art
Conclusion
Chapitre III : Contribution et résultats
I.Introduction
II.Suppositions
III. Système Multi-Agents (SMA)
IV.Outils de développement
IV.1 Plateforme JADE
IV.2 JFreeChart
V.Topologie du réseau utilisé
VI.Scénario
VII. Organigramme
VIII. Algorithme proposé
VIII.1 Pour la gestion de spectre
VIII.2 Pour la tolérance aux pannes
Présentation du fonctionnement
Présentation de l’application
Simulation
XII. Résultats obtenus
XIII. Évaluation des performances
XIV. Conclusion
Conclusion générale
BIBLIOGRAPHIE
Bibliographie
Annexe A
Télécharger le rapport complet
