Université Sétif 1 Faculté des Sciences
A partir de cette page vous pouvez :
| Retourner au premier écran avec les catégories... |
Catégories
Ajouter le résultat dans votre panier Affiner la rechercheAdaptation d'application multimédia a l'environnement d'exécution / Chehili, el-batoul
Titre : Adaptation d'application multimédia a l'environnement d'exécution Type de document : texte imprimé Auteurs : Chehili, el-batoul ; DOUIDI, L, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (89f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie Logiciel
documents multimédias
différente plateforme
bootstrap
responsive design
navigateursIndex. décimale : 004 Informatique Côte titre : MAI/0183 Adaptation d'application multimédia a l'environnement d'exécution [texte imprimé] / Chehili, el-batoul ; DOUIDI, L, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (89f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie Logiciel
documents multimédias
différente plateforme
bootstrap
responsive design
navigateursIndex. décimale : 004 Informatique Côte titre : MAI/0183 Exemplaires
Code-barres Cote Support Localisation Section Disponibilité MAI/0183 MAI/0183 Mémoire Bibliothéque des sciences Français Disponible
Titre : Adaptation automatique des services web de qualité Type de document : texte imprimé Auteurs : SAFFIDIN, Rania ; ALTI, ADEL, Directeur de thèse Editeur : Setif:UFA Année de publication : 2012 Importance : 1 vol (52f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Service web, Ontologie, sensibilité aux contextes, Systèmes pervasifs, document multimédia, adaptation automatique et sémantique. Index. décimale : 004 Informatique Résumé :
Résumé :
Actuellement, les documents multimédia sont les aspects clés des technologies web. Ils doivent pouvoir être exécutés sur de nombreuses plates-formes (Smartphone, PDA, ordinateurs de bureau, Tablette etc.), qui a donné la naissance de nouveaux systèmes d’informations dits pervasifs. Ces différents contextes de présentation multimédia introduisent différentes contraintes sur la présentation elle-même. Par-exemple les contraintes d’utilisation et les préférences de l’utilisateur. En conséquence de ces dernières, le problème d’hétérogénéité soulève. Pour clarifier cette complexité, les documents multimédia doivent être adaptés.
Et notre travail consiste à définir une approche d’adaptation automatique et sémantique de documents multimédia basée sur les services web qui exécutent physiquement les services d’adaptation, ainsi sur une ontologie qui décrit les caractéristiques (Sémantique, Coût, Qualité ...) et c’est une extension des services Web qui permet de considérer la sensibilité aux contextes tout au long de sélection des services d’adaptation.
Note de contenu :
Table des matières
Introduction générale 1
Chapitre 1: Service Web Sémantique
1. Introduction 3
2. Service web 3
2.1. Définition des services web 3
2.2. Principaux objectifs 4
2.3. Architecture des services web 4
2.4. Standards utilisés pour les services web 5
2.5. Processus d’invocation d’un service web 6
2.6. Les avantages et les inconvénients des services web 7
3. Ontologies et web service sémantique 8
3.1. Présentation des ontologies 8
3.2. Langages du web sémantique 8
3.3. Les annotations sémantiques 10
3.4. Service web sémantique 10
3.5. Approches proposées pour les services Web sémantiques 11
4. Contexte et sensibilité aux contextes 12
4.1. Définition du contexte 13
4.2. Catégories du contexte 13
4.2.1. Contexte utilisateur 13
4.2.2. Contexte de l’environnement 14
4.2.3. Contexte dispositif 14
4.2.4. Contexte du service 14
5. Conclusion 14
Chapitre 2: Etat de domaine
1. Introduction 16
2. Problématique 16
3. Approches existantes 16
3.1. Adaptation côté serveur 17
3.2. Adaptation côté client 17
3.3. Adaptation intermédiaire 18
4. Discussion et proposition 20
5. Conclusion 21
Chapitre 3: Conception
1. Introduction 22
2. Le modèle fonctionnel du système d'adaptation 22
3. Approche automatique d’adaptation des données multimédia 23
3.1. Architecture générale 23
3.1.1. Profil utilisateur 24
3.1.2. Description des caractéristiques de document multimédia 25
3.1.3. Ontologie développée 25
3.2. Construction automatique d’adaptation automatique des services 32
4. Conclusion 34
Chapitre 4: Implémentation
1. Introduction 35
2. Outils de développement 35
2.1. Editeur d’ontologie 35
2.2. Le langage SWRL 35
2.3. NetBeans 36
2.4. Le langage Java 36
3. Implémentation du système 37
3.1. Validation 46
4. Conclusion 51
Conclusion générale 52
Côte titre : MAI/0040 Adaptation automatique des services web de qualité [texte imprimé] / SAFFIDIN, Rania ; ALTI, ADEL, Directeur de thèse . - [S.l.] : Setif:UFA, 2012 . - 1 vol (52f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Service web, Ontologie, sensibilité aux contextes, Systèmes pervasifs, document multimédia, adaptation automatique et sémantique. Index. décimale : 004 Informatique Résumé :
Résumé :
Actuellement, les documents multimédia sont les aspects clés des technologies web. Ils doivent pouvoir être exécutés sur de nombreuses plates-formes (Smartphone, PDA, ordinateurs de bureau, Tablette etc.), qui a donné la naissance de nouveaux systèmes d’informations dits pervasifs. Ces différents contextes de présentation multimédia introduisent différentes contraintes sur la présentation elle-même. Par-exemple les contraintes d’utilisation et les préférences de l’utilisateur. En conséquence de ces dernières, le problème d’hétérogénéité soulève. Pour clarifier cette complexité, les documents multimédia doivent être adaptés.
Et notre travail consiste à définir une approche d’adaptation automatique et sémantique de documents multimédia basée sur les services web qui exécutent physiquement les services d’adaptation, ainsi sur une ontologie qui décrit les caractéristiques (Sémantique, Coût, Qualité ...) et c’est une extension des services Web qui permet de considérer la sensibilité aux contextes tout au long de sélection des services d’adaptation.
Note de contenu :
Table des matières
Introduction générale 1
Chapitre 1: Service Web Sémantique
1. Introduction 3
2. Service web 3
2.1. Définition des services web 3
2.2. Principaux objectifs 4
2.3. Architecture des services web 4
2.4. Standards utilisés pour les services web 5
2.5. Processus d’invocation d’un service web 6
2.6. Les avantages et les inconvénients des services web 7
3. Ontologies et web service sémantique 8
3.1. Présentation des ontologies 8
3.2. Langages du web sémantique 8
3.3. Les annotations sémantiques 10
3.4. Service web sémantique 10
3.5. Approches proposées pour les services Web sémantiques 11
4. Contexte et sensibilité aux contextes 12
4.1. Définition du contexte 13
4.2. Catégories du contexte 13
4.2.1. Contexte utilisateur 13
4.2.2. Contexte de l’environnement 14
4.2.3. Contexte dispositif 14
4.2.4. Contexte du service 14
5. Conclusion 14
Chapitre 2: Etat de domaine
1. Introduction 16
2. Problématique 16
3. Approches existantes 16
3.1. Adaptation côté serveur 17
3.2. Adaptation côté client 17
3.3. Adaptation intermédiaire 18
4. Discussion et proposition 20
5. Conclusion 21
Chapitre 3: Conception
1. Introduction 22
2. Le modèle fonctionnel du système d'adaptation 22
3. Approche automatique d’adaptation des données multimédia 23
3.1. Architecture générale 23
3.1.1. Profil utilisateur 24
3.1.2. Description des caractéristiques de document multimédia 25
3.1.3. Ontologie développée 25
3.2. Construction automatique d’adaptation automatique des services 32
4. Conclusion 34
Chapitre 4: Implémentation
1. Introduction 35
2. Outils de développement 35
2.1. Editeur d’ontologie 35
2.2. Le langage SWRL 35
2.3. NetBeans 36
2.4. Le langage Java 36
3. Implémentation du système 37
3.1. Validation 46
4. Conclusion 51
Conclusion générale 52
Côte titre : MAI/0040 Exemplaires
Code-barres Cote Support Localisation Section Disponibilité MAI/0040 MAI/0040 Mémoire Bibliothéque des sciences Français Disponible
Titre : Les Agents mobiles comme approche d'équilibrage de charge sur un réseau Type de document : texte imprimé Auteurs : CHERBAL, Sara ; BENAOUDA, ABDELHAFID, Directeur de thèse Editeur : Setif:UFA Année de publication : 2012 Importance : 1 vol (62f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
systeme distribué
agent mobile
équilibrage de chargeIndex. décimale : 004 Informatique Côte titre : MAI/0020 Les Agents mobiles comme approche d'équilibrage de charge sur un réseau [texte imprimé] / CHERBAL, Sara ; BENAOUDA, ABDELHAFID, Directeur de thèse . - [S.l.] : Setif:UFA, 2012 . - 1 vol (62f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
systeme distribué
agent mobile
équilibrage de chargeIndex. décimale : 004 Informatique Côte titre : MAI/0020 Exemplaires
Code-barres Cote Support Localisation Section Disponibilité MAI/0020 MAI/0020 Mémoire Bibliothéque des sciences Français Disponible
Titre : Algorithme de contrôle de topologie dans les réseaux Ad Hoc Type de document : texte imprimé Auteurs : MEBARKIA, Ossama ; DRIF, AHLEM, Directeur de thèse Editeur : Setif:UFA Année de publication : 2012 Importance : 1 vol (64f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
algorithme
topologie
réseaux Ad HocIndex. décimale : 004 Informatique Résumé :
Conclusion
Les réseaux sans fil de type ad hoc sont des réseaux caractérisés par des ressources limitées en énergie. La conservation d'énergie s'avère donc être un facteur primordial pour la durée de vie du réseau. La technologie de batterie a été évoluée parallèlement aux avancements en technologie de communications sans fil. Actuellement la capacité de batteries ne peut pas être sensiblement améliorée, des efforts devraient être mis dans la conception des logiciels et des matériels d'énergie-efficace. Les dispositifs mobiles portatifs ont typiquement plusieurs composants hardware qui consomment la puissance de batterie, ces principaux matériels sont: écran d'affichage, disque, CPU, mémoire, et la carte d'interface sans fil (WNIC: Wireless Network Interface Card). Plusieurs travaux ont démontré que l'activité réseau est très coûteuse en énergie et que le composant WNIC peut consommer de 10 à 50% d'énergie totale du système. L'émission ainsi que la réception consomment une énergie importante. Toutes ces activités engendrent une dissipation d'énergie inadmissible dans les environnements ad hoc mobile. L'énergie consommée par un nœud est également en fonction de ses activités réseau au niveau des différentes couches.
Dans ce projet, nous nous somme penché sur les approches de contrôle de topologie, nous avons étudié le fonctionnement des trois catégories de ces approches. Les approches à base de localisation supposent que les informations les plus précises sur les positions des nœuds sont connues à l’exemple du protocole R&M. Les approches à base de direction estiment la direction relative de leurs voisins. Les approches de type voisinage sont basés sur le graphe k-voisins, c.est à dire le graphe dans lequel chaque nœud est relié à ses k voisins les plus proches.
Notre travail se fonde sur les approches de type voisinage en utilisant l’arbre MST et le sous graphe Power Spanner. Nous avons tirer profit de la capacité des nœuds de déterminer le nombre et l'identité de voisins dans le rang de transmission maximum pour établir une structure sur cet ensemble de voisin en tenant compte aux paramètres énergétiques. L’analyse et l’évaluation des deux algorithmes, nous a permis de conclure que le choix d'une meilleure stratégie pour augmenter la durée de vie de réseaux est liées aux plusieurs critères.
Nous envisageons dans un futur travail d’implémenter d’autre structure optimale en tirant profit des sous graphes possédant des propriétés satisfaisantes pour être appliquer comme des topologies virtuelle optimale .
Note de contenu :
Table des matières
Introduction générale 5
I Les Réseaux mobile Ad Hoc 7
I.1. Introduction 7
I.2. Les environnements mobiles 8
I.2.1 Les r´eseaux avec infrastructure 8
I.2.2 Les réseaux sans infrastructure 9
I.3. Les reseaux ad hoc 10
I.4. Modélisation d’un réseau ad hoc 11
I.5. Caractéristiques des réseaux ad hoc 12
I.6. Application des réseaux ad hoc 14
I.7. Avantage des réseaux ad-hoc 15
I.8. Conclusion 16
II La conservation d’énergie dans réseaux Ad Hoc 17
II.1 Introduction 17
II.2 Conservation d’énergie dans les réseaux ad hoc 18
II.3 Source de perte d’énergie 18
 Le mode inactif: 18
 Les collisions: 18
 Le sur débit des protocoles: 19
 Taux d’erreurs élevé: 19
II.3.1 Exemple d’épuisement d’une batterie du nœud : 19
II.4 Approche existante de la consommation d’énergie 20
II.4.1 Au niveau routage 20
a. MPTR (Minimum Total Transmission Power Routing) 20
b. MBCR (Minimum Battery Cost Routing) 21
c. MMBCR (Min Max Battery Cost Routing) 21
d. E-DSR(Energy Dynamic Source Routing) 22
e. EC-DSR (Energy Conserving Dynamic Source Routing) 22
II.4.2 Au niveau liaison de données 22
a. La couche MAC 22
II.4.3 Au niveau contrôle de topologie 23
II.5 Impact de la mobilité sur la conservation d'énergie 23
II.6 Conclusion 24
III. Protocole de contrôle de topologie 26
III.1 Introduction 26
III.2 Contrôle de topologie et conservation d’énergie 27
III.3 Mécanisme de contrôle de topologie 28
III.4 Taxonomie des protocoles de contrôle de topologie 29
III. 4.1 Les approches CTR homogène et Non homogène 29
III.4.2 Les approches de contrôle de topologie à base de localisation 30
III.4.3 Les approches de contrôle de topologie basée sur la direction 30
III.4.4 Les approches de contrôle de topologie basée sur le voisinage 30
III.4.5 Le per-paquet et le contrôle de topologie périodique 30
III.5 Les protocoles de contrôle de topologie 31
III.5.2 Le protocole R&M (Rodoplu et Meng 1999) 31
III.5.2 Le protocole MST (minimum Spanning Tree) 34
III.5.3 Le protocole LMST 35
III.5.4 Le protocole RNG (Relative Neighbordhood Graph) 37
III.6 Conclusion 39
IV. Simulation des algorithmes de contrôle de topologie 40
IV.1 Introduction 40
IV.2 Outils de simulation 41
IV.3 Présentation du simulateur NS2 41
IV.4 Pourquoi le simulateur NS-2 ? 42
IV.5 Le principe du simulateur NS2 43
IV.5.1 Le langage script TCL 44
IV.5.2 L'outil de visualisation NAM 44
IV.5.3 Format d’un fichier trace 44
IV.6 Evaluation des algorithmes de contrôle de topologie 45
IV.6.1 Les algorithmes de contrôle de topologie 45
IV.6.2 Préliminaires 45
IV.6.3 Modèle énergétique 46
IV.6.4 Algorithme des graphes (Power spanner) 47
IV.6.5 Algorithme MST (Minimum Spanning Tree) 48
IV.7 Simulation et études de performances 50
IV.7.1 Les paramètres de la simulation 50
IV.7.2 Les scenarios de la simulation 50
IV.7.3 Résultats de simulation 54
IV.8 Conclusion 56
Conclusion 57
Référence bibliographique 58
Annexe 61
Côte titre : MAI/0022 Algorithme de contrôle de topologie dans les réseaux Ad Hoc [texte imprimé] / MEBARKIA, Ossama ; DRIF, AHLEM, Directeur de thèse . - [S.l.] : Setif:UFA, 2012 . - 1 vol (64f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
algorithme
topologie
réseaux Ad HocIndex. décimale : 004 Informatique Résumé :
Conclusion
Les réseaux sans fil de type ad hoc sont des réseaux caractérisés par des ressources limitées en énergie. La conservation d'énergie s'avère donc être un facteur primordial pour la durée de vie du réseau. La technologie de batterie a été évoluée parallèlement aux avancements en technologie de communications sans fil. Actuellement la capacité de batteries ne peut pas être sensiblement améliorée, des efforts devraient être mis dans la conception des logiciels et des matériels d'énergie-efficace. Les dispositifs mobiles portatifs ont typiquement plusieurs composants hardware qui consomment la puissance de batterie, ces principaux matériels sont: écran d'affichage, disque, CPU, mémoire, et la carte d'interface sans fil (WNIC: Wireless Network Interface Card). Plusieurs travaux ont démontré que l'activité réseau est très coûteuse en énergie et que le composant WNIC peut consommer de 10 à 50% d'énergie totale du système. L'émission ainsi que la réception consomment une énergie importante. Toutes ces activités engendrent une dissipation d'énergie inadmissible dans les environnements ad hoc mobile. L'énergie consommée par un nœud est également en fonction de ses activités réseau au niveau des différentes couches.
Dans ce projet, nous nous somme penché sur les approches de contrôle de topologie, nous avons étudié le fonctionnement des trois catégories de ces approches. Les approches à base de localisation supposent que les informations les plus précises sur les positions des nœuds sont connues à l’exemple du protocole R&M. Les approches à base de direction estiment la direction relative de leurs voisins. Les approches de type voisinage sont basés sur le graphe k-voisins, c.est à dire le graphe dans lequel chaque nœud est relié à ses k voisins les plus proches.
Notre travail se fonde sur les approches de type voisinage en utilisant l’arbre MST et le sous graphe Power Spanner. Nous avons tirer profit de la capacité des nœuds de déterminer le nombre et l'identité de voisins dans le rang de transmission maximum pour établir une structure sur cet ensemble de voisin en tenant compte aux paramètres énergétiques. L’analyse et l’évaluation des deux algorithmes, nous a permis de conclure que le choix d'une meilleure stratégie pour augmenter la durée de vie de réseaux est liées aux plusieurs critères.
Nous envisageons dans un futur travail d’implémenter d’autre structure optimale en tirant profit des sous graphes possédant des propriétés satisfaisantes pour être appliquer comme des topologies virtuelle optimale .
Note de contenu :
Table des matières
Introduction générale 5
I Les Réseaux mobile Ad Hoc 7
I.1. Introduction 7
I.2. Les environnements mobiles 8
I.2.1 Les r´eseaux avec infrastructure 8
I.2.2 Les réseaux sans infrastructure 9
I.3. Les reseaux ad hoc 10
I.4. Modélisation d’un réseau ad hoc 11
I.5. Caractéristiques des réseaux ad hoc 12
I.6. Application des réseaux ad hoc 14
I.7. Avantage des réseaux ad-hoc 15
I.8. Conclusion 16
II La conservation d’énergie dans réseaux Ad Hoc 17
II.1 Introduction 17
II.2 Conservation d’énergie dans les réseaux ad hoc 18
II.3 Source de perte d’énergie 18
 Le mode inactif: 18
 Les collisions: 18
 Le sur débit des protocoles: 19
 Taux d’erreurs élevé: 19
II.3.1 Exemple d’épuisement d’une batterie du nœud : 19
II.4 Approche existante de la consommation d’énergie 20
II.4.1 Au niveau routage 20
a. MPTR (Minimum Total Transmission Power Routing) 20
b. MBCR (Minimum Battery Cost Routing) 21
c. MMBCR (Min Max Battery Cost Routing) 21
d. E-DSR(Energy Dynamic Source Routing) 22
e. EC-DSR (Energy Conserving Dynamic Source Routing) 22
II.4.2 Au niveau liaison de données 22
a. La couche MAC 22
II.4.3 Au niveau contrôle de topologie 23
II.5 Impact de la mobilité sur la conservation d'énergie 23
II.6 Conclusion 24
III. Protocole de contrôle de topologie 26
III.1 Introduction 26
III.2 Contrôle de topologie et conservation d’énergie 27
III.3 Mécanisme de contrôle de topologie 28
III.4 Taxonomie des protocoles de contrôle de topologie 29
III. 4.1 Les approches CTR homogène et Non homogène 29
III.4.2 Les approches de contrôle de topologie à base de localisation 30
III.4.3 Les approches de contrôle de topologie basée sur la direction 30
III.4.4 Les approches de contrôle de topologie basée sur le voisinage 30
III.4.5 Le per-paquet et le contrôle de topologie périodique 30
III.5 Les protocoles de contrôle de topologie 31
III.5.2 Le protocole R&M (Rodoplu et Meng 1999) 31
III.5.2 Le protocole MST (minimum Spanning Tree) 34
III.5.3 Le protocole LMST 35
III.5.4 Le protocole RNG (Relative Neighbordhood Graph) 37
III.6 Conclusion 39
IV. Simulation des algorithmes de contrôle de topologie 40
IV.1 Introduction 40
IV.2 Outils de simulation 41
IV.3 Présentation du simulateur NS2 41
IV.4 Pourquoi le simulateur NS-2 ? 42
IV.5 Le principe du simulateur NS2 43
IV.5.1 Le langage script TCL 44
IV.5.2 L'outil de visualisation NAM 44
IV.5.3 Format d’un fichier trace 44
IV.6 Evaluation des algorithmes de contrôle de topologie 45
IV.6.1 Les algorithmes de contrôle de topologie 45
IV.6.2 Préliminaires 45
IV.6.3 Modèle énergétique 46
IV.6.4 Algorithme des graphes (Power spanner) 47
IV.6.5 Algorithme MST (Minimum Spanning Tree) 48
IV.7 Simulation et études de performances 50
IV.7.1 Les paramètres de la simulation 50
IV.7.2 Les scenarios de la simulation 50
IV.7.3 Résultats de simulation 54
IV.8 Conclusion 56
Conclusion 57
Référence bibliographique 58
Annexe 61
Côte titre : MAI/0022 Exemplaires
Code-barres Cote Support Localisation Section Disponibilité MAI/0022 MAI/0022 $r non conforme -- bibliothéque FS indéterminé Disponible
Titre : Un algorithme distribué auto-stabilisant pour calculer un ensemble fortement dominant minimal Type de document : texte imprimé Auteurs : BADAOUI, Mouna ; SEMCHEDINE, FOUZI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (69f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Système réparti, Tolérance aux pannes, Pannes transitoires, Auto-stabilisation, Ensemble dominant, Ensemble fortement dominant minimal. Index. décimale : 004 Informatique Résumé :
Résumé
Un système réparti est un système constitué d’un ensemble d’unités de calcul autonomes
dotées de capacités de communication. Ces unités coopèrent pour effectuer une tâche globale.
La probabilité que certains éléments du système subissent des pannes est non négligeable car
un système parfait sans pannes n’existe pas dans la réalité. Ces pannes peuvent être classifiées
en fonction de leur durée, de leur étendue et de leur nature. Plusieurs mécanismes de tolérance
aux pannes se présentent dans la littérature. Dans cette mémoire, nous nous intéressons Ã
l’auto-stabilisation qui est un mécanisme de tolérance aux pannes non masquant.
Les algorithmes auto-stabilisants de domination ont une application importante dans les
systèmes répartis qui est le clustering. Le clustering consiste au regroupement des nœuds selon
un ou plusieurs paramètres comme le degré du nœud, son poids, etc. Le clustering basé sur
le degré du nœud permet de construire des clusters denses. Dans ce mémoire nous présentons
un algorithme auto-stabilisant qui calcule un ensemble fortement dominant en utilisant un
démon centralisé en se basant sur l’algorithme de Hedetniemi. Nous présentons également la
transformation de cet algorithme en un autre qui utilise un démon distribué.
Note de contenu :
Table des matières
Liste des figures ii
Introduction générale 1
1 Introduction aux Systèmes Distribués et à l’Auto-stabilisation 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Les systèmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Système réparti, réseau, système parallèle . . . . . . . . . . . . . . . . 6
1.2.2.1 Système réparti vs réseau . . . . . . . . . . . . . . . . . . . . 6
1.2.2.2 Système réparti vs système parallèle . . . . . . . . . . . . . . 6
1.2.3 Caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Défis de conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6 Modèles de communication . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6.1 Le modèle de communication par échange de messages . . . . 9
1.2.6.2 Le modèle de communication par mémoire partagée . . . . . . 9
1.3 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Taxonomie des pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1.1 Classification des pannes selon la localisation dans le temps . 11
1.3.1.2 Classification des pannes selon leur nature . . . . . . . . . . . 11
1.3.2 Les systèmes répartis et la tolérance aux pannes . . . . . . . . . . . . . 12
1.3.3 Mécanismes de tolérance aux pannes . . . . . . . . . . . . . . . . . . . 14
1.4 Auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Comment prouver l’auto-stabilisation . . . . . . . . . . . . . . . . . . . 16
1.4.2 Token-ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.3 Algorithmes auto-stabilisants de graphes . . . . . . . . . . . . . . . . . 17
1.4.4 Propriétés des algorithmes d’auto-stabilisation . . . . . . . . . . . . . . 18
1.4.4.1 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.4.2 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.5 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.6 Atomicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.7 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4.8 Mesures de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Algorithmes Auto-stabilisants de Calcul des Ensembles Dominants 24
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Notions de base de la théorie des graphes . . . . . . . . . . . . . . . . . . . . . 24
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Algorithmes de calcul d’un ensemble dominant minimal (MDS) . . . . 30
2.4.2 Algorithmes de calcul d’un ensemble K-dominant minimal (MKDS) . . 39
2.4.3 Autres algorithmes de domination . . . . . . . . . . . . . . . . . . . . . 43
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Un Algorithme Auto-stabilisant qui Calcule un MSDS 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Un algorithme auto-stabilisant qui calcule un MSDS . . . . . . . . . . . . . . . 46
3.2.1 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.2 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.3 Exemples d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Preuve de correction et de convergence de l’algorithme proposé . . . . . . . . . 50
3.3.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Implémentation et simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.1 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.2.1 Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2.2 Résultats de simulation . . . . . . . . . . . . . . . . . . . . . 57
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Conclusion générale 63
Bibliographie 64
Annexes 67
A L’application de Kuszner 68
B Codes sources des algorithmes implémentés 70
Côte titre : MAI/0074 Un algorithme distribué auto-stabilisant pour calculer un ensemble fortement dominant minimal [texte imprimé] / BADAOUI, Mouna ; SEMCHEDINE, FOUZI, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (69f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Système réparti, Tolérance aux pannes, Pannes transitoires, Auto-stabilisation, Ensemble dominant, Ensemble fortement dominant minimal. Index. décimale : 004 Informatique Résumé :
Résumé
Un système réparti est un système constitué d’un ensemble d’unités de calcul autonomes
dotées de capacités de communication. Ces unités coopèrent pour effectuer une tâche globale.
La probabilité que certains éléments du système subissent des pannes est non négligeable car
un système parfait sans pannes n’existe pas dans la réalité. Ces pannes peuvent être classifiées
en fonction de leur durée, de leur étendue et de leur nature. Plusieurs mécanismes de tolérance
aux pannes se présentent dans la littérature. Dans cette mémoire, nous nous intéressons Ã
l’auto-stabilisation qui est un mécanisme de tolérance aux pannes non masquant.
Les algorithmes auto-stabilisants de domination ont une application importante dans les
systèmes répartis qui est le clustering. Le clustering consiste au regroupement des nœuds selon
un ou plusieurs paramètres comme le degré du nœud, son poids, etc. Le clustering basé sur
le degré du nœud permet de construire des clusters denses. Dans ce mémoire nous présentons
un algorithme auto-stabilisant qui calcule un ensemble fortement dominant en utilisant un
démon centralisé en se basant sur l’algorithme de Hedetniemi. Nous présentons également la
transformation de cet algorithme en un autre qui utilise un démon distribué.
Note de contenu :
Table des matières
Liste des figures ii
Introduction générale 1
1 Introduction aux Systèmes Distribués et à l’Auto-stabilisation 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Les systèmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Système réparti, réseau, système parallèle . . . . . . . . . . . . . . . . 6
1.2.2.1 Système réparti vs réseau . . . . . . . . . . . . . . . . . . . . 6
1.2.2.2 Système réparti vs système parallèle . . . . . . . . . . . . . . 6
1.2.3 Caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Défis de conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6 Modèles de communication . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6.1 Le modèle de communication par échange de messages . . . . 9
1.2.6.2 Le modèle de communication par mémoire partagée . . . . . . 9
1.3 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Taxonomie des pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1.1 Classification des pannes selon la localisation dans le temps . 11
1.3.1.2 Classification des pannes selon leur nature . . . . . . . . . . . 11
1.3.2 Les systèmes répartis et la tolérance aux pannes . . . . . . . . . . . . . 12
1.3.3 Mécanismes de tolérance aux pannes . . . . . . . . . . . . . . . . . . . 14
1.4 Auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Comment prouver l’auto-stabilisation . . . . . . . . . . . . . . . . . . . 16
1.4.2 Token-ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.3 Algorithmes auto-stabilisants de graphes . . . . . . . . . . . . . . . . . 17
1.4.4 Propriétés des algorithmes d’auto-stabilisation . . . . . . . . . . . . . . 18
1.4.4.1 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.4.2 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.5 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.6 Atomicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.7 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4.8 Mesures de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Algorithmes Auto-stabilisants de Calcul des Ensembles Dominants 24
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Notions de base de la théorie des graphes . . . . . . . . . . . . . . . . . . . . . 24
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Algorithmes de calcul d’un ensemble dominant minimal (MDS) . . . . 30
2.4.2 Algorithmes de calcul d’un ensemble K-dominant minimal (MKDS) . . 39
2.4.3 Autres algorithmes de domination . . . . . . . . . . . . . . . . . . . . . 43
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Un Algorithme Auto-stabilisant qui Calcule un MSDS 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Un algorithme auto-stabilisant qui calcule un MSDS . . . . . . . . . . . . . . . 46
3.2.1 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.2 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.3 Exemples d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Preuve de correction et de convergence de l’algorithme proposé . . . . . . . . . 50
3.3.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Implémentation et simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.1 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.2.1 Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2.2 Résultats de simulation . . . . . . . . . . . . . . . . . . . . . 57
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Conclusion générale 63
Bibliographie 64
Annexes 67
A L’application de Kuszner 68
B Codes sources des algorithmes implémentés 70
Côte titre : MAI/0074 Exemplaires
Code-barres Cote Support Localisation Section Disponibilité MAI/0074 MAI/0074 Mémoire Bibliothéque des sciences Français Disponible
Permalink
Permalink
Permalink
Permalink
Permalink
Permalink
Permalink
Permalink
Permalink
Permalink
