University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur SEMCHEDINE, FOUZI |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheUn algorithme distribué auto-stabilisant pour calculer un ensemble fortement dominant minimal / BADAOUI, Mouna
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 (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0074 MAI/0074 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Un algorithme évolutionnaire pour la sélection des vues matérialisées dans l’entrepôt de données Type de document : texte imprimé Auteurs : KARA, Sara ; SEMCHEDINE, FOUZI, Directeur de thèse Importance : 1 vol (51f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : vue matérialisée, entrepôt de données, les algorithmes d’optimisation, méta-heuristiques, requête OLAP. Index. décimale : 004 Informatique Résumé :
Résumé
L’importance du volume des entrepôts de données rend les requêtes très lourdes. Des améliorations sur les techniques d’optimisation des requêtes ont été exigés afin d’accélérer l’exécution de ces requêtes. Parmi ces techniques : les vues matérialisées. Cette technique a connu un important problème d’optimisation ; il s’agit du problème de sélection des vues. La matérialisation de tous les vues accélère l’exécution de n’importe quelle requête mais nécessite un coût considérable pour les maintenir. Par contre, la maintenance des vues rend les résultats des requêtes plus bénéfiques pour les décideurs. Ces contraintes rendent la sélection des vues un problème Non Polynomial-difficile. Ce type de problème n’a pas une solution exacte, ce qui fait appel à des heuristiques pour le résoudre. Nous avons proposé dans ce mémoire une solution par l’adaptation de la recherche taboue pour résoudre le problème de sélection des vues afin de satisfaire les différentes contraintes d’optimisation des requêtes.
Note de contenu :
Table des matières
Introduction générale 1
Contexte du travail 1
Plan du mémoire 2
Chapitre 1 : Les entrepôts de données et les systèmes décisionnels
1. Introduction 3
2. Définition d’un entrepôt de données 3
3. Caractéristiques 3
4. Les systèmes OLTP versus les systèmes OLAP 4
5. Les entrepôts de données et les systèmes décisionnels 5
5.1. Extraction 5
5.2. Transformation 6
5.3. Chargement 6
6. L’architecture d’un entrepôt de données 7
6.1. Données de détail courantes 7
6.2. Données de détail anciennes 7
6.3. Données agrégés 7
6.4. Métadonnées 7
7. La modélisation multidimensionnelle 8
7.1. Les concepts de base 9
7.1.1. Les faits 9
7.1.2. Les dimensions 9
7.1.3. La hiérarchie 9
7.2. Les schémas relationnels 9
7.2.1. Le modèle en étoile 9
7.2.2. Le modèle en flocon de neige 10
7.2.3. Le modèle en constellation 11
7.3. Le schéma multidimensionnel 12
8. La modélisation logique 12
8.1. ROLAP 13
8.2. MOLAP 13
9. La manipulation des données multidimensionnelles 14
9.1. Opérations classiques 14
9.2. Opérations agissant sur la structure 14
9.2.1. La rotation 14
9.2.2. La permutation 14
9.2.3. La division 15
9.2.4. L’emboitement 15
9.3. Opérations agissant sur la granularité 15
9.3.1. Le forage vers le haut 15
9.3.2. Le forage vers le bas 15
10. Conclusion 15
Chapitre 2 : La sélection des vues matérialisées dans l’entrepôt de
1. Introduction 16
2. Les vues matérialisées 16
2.1. Le problème de sélection des vues matérialisées PSV 17
2.1.1. Matérialiser toutes les vues 17
2.1.2. Ne matérialiser aucune vue 17
2.1.3. Matérialiser une partie de cube de données 17
2.2. La maintenance des vues matérialisées 18
3. Le modèle de coût 19
3.1. Le coût d’évaluation des requêtes 19
3.2. Le coût de maintenance des vues 19
3.3. Le coût opérationnel 19
4. Les contraintes 20
4.1. Les contraintes orientées systèmes 20
4.1.1. La contrainte d’espace 20
4.1.2. La contrainte de temps de maintenance 20
4.2. Les contraintes orientées utilisateurs 20
4.2.1. La contrainte d’exactitude de données de réponse 20
4.2.2. La contrainte de temps de réponse à la requête 21
5. La représentation de l’espace de recherche 21
5.1. L’algèbre relationnel 21
5.2. Le graphe orienté acyclique 22
5.3. Le graphe AND/OR 22
5.4. Le treillis 23
6. Les algorithmes pour la résolution du problème PSV 24
6.1. Les algorithmes sans contraintes 24
6.1.1. L’algorithme de Yang et al. 24
6.1.2. L’algorithme de Hrong et al. 25
6.1.3. L’algorithme de Dhote et al. 27
6.2. Les algorithmes avec contraintes 27
6.2.1. L’algorithme de Panos et al. 27
6.2.2. L’algorithme de Yang.Jal. 28
6.2.3. L’algorithme d’Ashedevi et al. 29
6.2.4. L’algorithme de Zhou et al. 29
6.2.5. L’algorithme de Choudhari et al. 30
6.2.6. L’algorithme d’Ashedevi et al. 29
7. Conclusion 32
Chapitre 3 : Proposition et conception d’une solution pour la sélection des vues matérialisées
1. Introduction 34
2. La recherche tabou 34
2.1. Notion de voisinage 34
2.2. L’optimum local 35
2.3. L’optimum global 35
2.4. Fonctionnement de l’algorithme tabou 35
2.5. Les améliorations possibles 37
2.5.1. L’intensification 37
2.5.2. La diversification 37
3. L’optimisationmultiobjectif 38
3.1. Formalisation du problème d’optimisation multiobjectif 38
3.2. Notion de dominance de Pareto (optimalité) 38
3.3. Métaheuristiques pour les problèmes multiobjectif 39
4. Conception de la solution 40
4.1. L’entrepôt de données multidimensionnels 40
4.2. Le treillis multidimensionnel 41
4.3. Le modèle de cout 41
4.4. La résolution avec la recherche tabou 42
4.4.1. La génération du treillis 42
4.4.2. La solution initiale 42
4.4.3. La génération de l’ensemble de voisinage 43
5. Conclusion 43
Chapitre 4 : Validation de la solution proposée
1. Introduction 44
2. Description de l’outil de simulation 44
3. Le modèle TPC-D benchmark 44
4. La résolution du problème de sélection des vues matérialisées 47
4.1. La résolution par l’algorithme BPUS 47
4.2. La résolution par la méthode de recherche taboue 47
4.3. Résultat de la simulation 48
5. Conclusion 49
Conclusion générale 50
Côte titre : MAI/0084 Un algorithme évolutionnaire pour la sélection des vues matérialisées dans l’entrepôt de données [texte imprimé] / KARA, Sara ; SEMCHEDINE, FOUZI, Directeur de thèse . - [s.d.] . - 1 vol (51f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : vue matérialisée, entrepôt de données, les algorithmes d’optimisation, méta-heuristiques, requête OLAP. Index. décimale : 004 Informatique Résumé :
Résumé
L’importance du volume des entrepôts de données rend les requêtes très lourdes. Des améliorations sur les techniques d’optimisation des requêtes ont été exigés afin d’accélérer l’exécution de ces requêtes. Parmi ces techniques : les vues matérialisées. Cette technique a connu un important problème d’optimisation ; il s’agit du problème de sélection des vues. La matérialisation de tous les vues accélère l’exécution de n’importe quelle requête mais nécessite un coût considérable pour les maintenir. Par contre, la maintenance des vues rend les résultats des requêtes plus bénéfiques pour les décideurs. Ces contraintes rendent la sélection des vues un problème Non Polynomial-difficile. Ce type de problème n’a pas une solution exacte, ce qui fait appel à des heuristiques pour le résoudre. Nous avons proposé dans ce mémoire une solution par l’adaptation de la recherche taboue pour résoudre le problème de sélection des vues afin de satisfaire les différentes contraintes d’optimisation des requêtes.
Note de contenu :
Table des matières
Introduction générale 1
Contexte du travail 1
Plan du mémoire 2
Chapitre 1 : Les entrepôts de données et les systèmes décisionnels
1. Introduction 3
2. Définition d’un entrepôt de données 3
3. Caractéristiques 3
4. Les systèmes OLTP versus les systèmes OLAP 4
5. Les entrepôts de données et les systèmes décisionnels 5
5.1. Extraction 5
5.2. Transformation 6
5.3. Chargement 6
6. L’architecture d’un entrepôt de données 7
6.1. Données de détail courantes 7
6.2. Données de détail anciennes 7
6.3. Données agrégés 7
6.4. Métadonnées 7
7. La modélisation multidimensionnelle 8
7.1. Les concepts de base 9
7.1.1. Les faits 9
7.1.2. Les dimensions 9
7.1.3. La hiérarchie 9
7.2. Les schémas relationnels 9
7.2.1. Le modèle en étoile 9
7.2.2. Le modèle en flocon de neige 10
7.2.3. Le modèle en constellation 11
7.3. Le schéma multidimensionnel 12
8. La modélisation logique 12
8.1. ROLAP 13
8.2. MOLAP 13
9. La manipulation des données multidimensionnelles 14
9.1. Opérations classiques 14
9.2. Opérations agissant sur la structure 14
9.2.1. La rotation 14
9.2.2. La permutation 14
9.2.3. La division 15
9.2.4. L’emboitement 15
9.3. Opérations agissant sur la granularité 15
9.3.1. Le forage vers le haut 15
9.3.2. Le forage vers le bas 15
10. Conclusion 15
Chapitre 2 : La sélection des vues matérialisées dans l’entrepôt de
1. Introduction 16
2. Les vues matérialisées 16
2.1. Le problème de sélection des vues matérialisées PSV 17
2.1.1. Matérialiser toutes les vues 17
2.1.2. Ne matérialiser aucune vue 17
2.1.3. Matérialiser une partie de cube de données 17
2.2. La maintenance des vues matérialisées 18
3. Le modèle de coût 19
3.1. Le coût d’évaluation des requêtes 19
3.2. Le coût de maintenance des vues 19
3.3. Le coût opérationnel 19
4. Les contraintes 20
4.1. Les contraintes orientées systèmes 20
4.1.1. La contrainte d’espace 20
4.1.2. La contrainte de temps de maintenance 20
4.2. Les contraintes orientées utilisateurs 20
4.2.1. La contrainte d’exactitude de données de réponse 20
4.2.2. La contrainte de temps de réponse à la requête 21
5. La représentation de l’espace de recherche 21
5.1. L’algèbre relationnel 21
5.2. Le graphe orienté acyclique 22
5.3. Le graphe AND/OR 22
5.4. Le treillis 23
6. Les algorithmes pour la résolution du problème PSV 24
6.1. Les algorithmes sans contraintes 24
6.1.1. L’algorithme de Yang et al. 24
6.1.2. L’algorithme de Hrong et al. 25
6.1.3. L’algorithme de Dhote et al. 27
6.2. Les algorithmes avec contraintes 27
6.2.1. L’algorithme de Panos et al. 27
6.2.2. L’algorithme de Yang.Jal. 28
6.2.3. L’algorithme d’Ashedevi et al. 29
6.2.4. L’algorithme de Zhou et al. 29
6.2.5. L’algorithme de Choudhari et al. 30
6.2.6. L’algorithme d’Ashedevi et al. 29
7. Conclusion 32
Chapitre 3 : Proposition et conception d’une solution pour la sélection des vues matérialisées
1. Introduction 34
2. La recherche tabou 34
2.1. Notion de voisinage 34
2.2. L’optimum local 35
2.3. L’optimum global 35
2.4. Fonctionnement de l’algorithme tabou 35
2.5. Les améliorations possibles 37
2.5.1. L’intensification 37
2.5.2. La diversification 37
3. L’optimisationmultiobjectif 38
3.1. Formalisation du problème d’optimisation multiobjectif 38
3.2. Notion de dominance de Pareto (optimalité) 38
3.3. Métaheuristiques pour les problèmes multiobjectif 39
4. Conception de la solution 40
4.1. L’entrepôt de données multidimensionnels 40
4.2. Le treillis multidimensionnel 41
4.3. Le modèle de cout 41
4.4. La résolution avec la recherche tabou 42
4.4.1. La génération du treillis 42
4.4.2. La solution initiale 42
4.4.3. La génération de l’ensemble de voisinage 43
5. Conclusion 43
Chapitre 4 : Validation de la solution proposée
1. Introduction 44
2. Description de l’outil de simulation 44
3. Le modèle TPC-D benchmark 44
4. La résolution du problème de sélection des vues matérialisées 47
4.1. La résolution par l’algorithme BPUS 47
4.2. La résolution par la méthode de recherche taboue 47
4.3. Résultat de la simulation 48
5. Conclusion 49
Conclusion générale 50
Côte titre : MAI/0084 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0084 MAI/0084 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Amélioration du mécanisme de gestion MAC pour les réseaux de capteurs sans fil Type de document : texte imprimé Auteurs : Korrichi, nihed ; SEMCHEDINE, FOUZI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (52f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
capteurs sans fil
MAC
Duty cycle
gestion énergieRésumé : RESUME
La recherche dans le domaine des réseaux de capteurs sans fil fixe comme objectif
principal le développement d‟algorithmes et de protocoles assurant une
consommation énergétique minimale. Pour prolonger la durée de vie d‟un réseau de
capteur sans fil tout en assurant les trois tâches principales d‟un nœud capteur :
capture, traitement et l‟envoi des données, il faut bien conserver l'énergie des nœuds
capteurs. Ceci a motivé des travaux de recherche à se focaliser sur les couches MAC
(Medium Access Control) et réseau. Dans notre travail, nous nous intéressons à la
couche MAC afin de partager le canal équitablement et efficacement mais surtout en
minimisant la consommation d'énergie en évitant les principales causes de
consommation d'énergie :l'overhearing, l'overmiting et les fréquentes transitions entre
les modes "en veille" et "activité". Nous avons proposé dans ce mémoire un protocole
asynchrone de classe de protocoles basés sur a contention avec un mécanisme duty
cycle afin d‟optimiser l‟énergie .Les résultats de simulation montrent que le protocole
améliore les performances en termes de consommation d‟énergie et minimise le délai
de bout-en-bout de délivrance de paquets.
Note de contenu : Table des matières
Introduction générale.................................................................................................. i
Organisation du mémoire............................................................................................ii
Chapitre1: les Réseaux de Capteurs Sans Fil
1.1 Introduction............................................................................................................1
1.2.Les réseaux de capteurs sans fil (RSCF).....................................................................1
1.2.1. Architecture des RCSF.......................................................................................1
1.2.2. La collecte d‟information....................................................................................2
1.2.3. Les topologies des RCSF....................................................................................3
1.3. La pile protocolaire.................................................................................................3
1.4. Les capteurs sans fil................................................................................................4
1.5. Les domaines d‟application d‟un RCSF.....................................................................6
1.6. Les facteurs de conception des RCSF........................................................................8
1.7. Réseaux de capteurs vs réseaux ad hoc......................................................................9
1.8. La consommation d‟énergie dans les RCSF .............................................................10
1.9.Les sources de gaspillage d‟énergie .........................................................................11
1.10. Conclusion.........................................................................................................12
Chapitre2: Analyse des protocoles de la couche MAC
2.1 Introduction:.........................................................................................................13
2.2. Les mécanismes de conservation de l‟énergie...........................................................13
2.3. La couche liaison de données.................................................................................15
2.4. Les protocoles MAC pour les RCSFs : ....................................................................15
2.4.1. Les Protocoles Mac basés sur TDMA :...............................................................15
2.4.1.1. Protocoles à base de TDMA centralisés ......................................................16
2.4.1.1.1 BMA ....................................................................................................16
2.4.1.1.2. ED-TDMA ...........................................................................................17
2.4.1.2. Protocoles à base de TDMA distribués ............................................................19
2.4.1.2.1. TRAMA :.............................................................................................19
2.4.1.2.2. TDMA-CA ..........................................................................................20
2.4.2.Protocoles MAC basés sur la contention ................................................................22
2.4.2.1 Les protocoles MAC synchrones ou slottés : .....................................................22
2.4.2.1. S-MAC...................................................................................................23
2.4.2.2. T-MAC...................................................................................................24
2.4.2.2.Les protocoles MAC asynchrones....................................................................26
2.4.2.2.1. B-MAC................................................................................................26
2.4.2.2.2. WiseMAC ............................................................................................27
2.4.3. Protocoles MAC hybrides...................................................................................29
2.4.3. 1. G-MAC ......................................................................................................29
2.4.3. 2. A-MAC ......................................................................................................30
2.4.3. 3. Z-MAC.......................................................................................................31
2.5. Conclusion ..........................................................................................................33
Chapitre3 : Contribution et Simulation
3.1. Introduction : .......................................................................................................34
I. Première partie ........................................................................................................34
3.2Description générale du protocole proposé ................................................................34
3.3.Présentation du protocole proposé ...........................................................................35
3.3.1. Les Hypothèses...............................................................................................35
3.4. L‟algorithme proposé :..........................................................................................36
3.5. Le design du protocole: .........................................................................................37
3.5.1. Sleepstate: ......................................................................................................38
3.5.3 Réglage du temps de sommeil dynamiquement :...................................................39
3.5.4. Les opérations des nœuds de DSA-MAC............................................................40
3.6. L'algorithme de protocole ......................................................................................41
3.7. la cotribution ……………………………………………………………………………………………………………....42
II. Deuxiéme partie .....................................................................................................43
3.8. L‟environnement de développement .......................................................................43
3.9. Etapes de réalisation de l‟algorithme proposé...........................................................43
3.10 Le principe de CSMA/CA.....................................................................................45
3.11 L‟algorithme de backoffexponentiel BEB (Binary Exponential Backoff)...................46
3.12. Les paramètres d‟évaluation du système ................................................................47
3.13. Les paramètres de simulation ...............................................................................48
3.14.Etude des résultats de simulation ...........................................................................48
3.14.1 Comparaison de l‟énergie consommée...............................................................48
3.14.2. Comparaison de la latence de bout-en-bout .......................................................49
3.14.3. Comparaison du taux de paquets délivrés..........................................................51
3.15. Conclusion ......................................................................................................52
Conclusion générale et perspectives..............................................................................53Côte titre : MAI/0115 En ligne : https://drive.google.com/file/d/19WBeBCBT8CRD8Jt4Nb4aaujV1ajvl7jJ/view?usp=shari [...] Format de la ressource électronique : Amélioration du mécanisme de gestion MAC pour les réseaux de capteurs sans fil [texte imprimé] / Korrichi, nihed ; SEMCHEDINE, FOUZI, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (52f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
capteurs sans fil
MAC
Duty cycle
gestion énergieRésumé : RESUME
La recherche dans le domaine des réseaux de capteurs sans fil fixe comme objectif
principal le développement d‟algorithmes et de protocoles assurant une
consommation énergétique minimale. Pour prolonger la durée de vie d‟un réseau de
capteur sans fil tout en assurant les trois tâches principales d‟un nœud capteur :
capture, traitement et l‟envoi des données, il faut bien conserver l'énergie des nœuds
capteurs. Ceci a motivé des travaux de recherche à se focaliser sur les couches MAC
(Medium Access Control) et réseau. Dans notre travail, nous nous intéressons à la
couche MAC afin de partager le canal équitablement et efficacement mais surtout en
minimisant la consommation d'énergie en évitant les principales causes de
consommation d'énergie :l'overhearing, l'overmiting et les fréquentes transitions entre
les modes "en veille" et "activité". Nous avons proposé dans ce mémoire un protocole
asynchrone de classe de protocoles basés sur a contention avec un mécanisme duty
cycle afin d‟optimiser l‟énergie .Les résultats de simulation montrent que le protocole
améliore les performances en termes de consommation d‟énergie et minimise le délai
de bout-en-bout de délivrance de paquets.
Note de contenu : Table des matières
Introduction générale.................................................................................................. i
Organisation du mémoire............................................................................................ii
Chapitre1: les Réseaux de Capteurs Sans Fil
1.1 Introduction............................................................................................................1
1.2.Les réseaux de capteurs sans fil (RSCF).....................................................................1
1.2.1. Architecture des RCSF.......................................................................................1
1.2.2. La collecte d‟information....................................................................................2
1.2.3. Les topologies des RCSF....................................................................................3
1.3. La pile protocolaire.................................................................................................3
1.4. Les capteurs sans fil................................................................................................4
1.5. Les domaines d‟application d‟un RCSF.....................................................................6
1.6. Les facteurs de conception des RCSF........................................................................8
1.7. Réseaux de capteurs vs réseaux ad hoc......................................................................9
1.8. La consommation d‟énergie dans les RCSF .............................................................10
1.9.Les sources de gaspillage d‟énergie .........................................................................11
1.10. Conclusion.........................................................................................................12
Chapitre2: Analyse des protocoles de la couche MAC
2.1 Introduction:.........................................................................................................13
2.2. Les mécanismes de conservation de l‟énergie...........................................................13
2.3. La couche liaison de données.................................................................................15
2.4. Les protocoles MAC pour les RCSFs : ....................................................................15
2.4.1. Les Protocoles Mac basés sur TDMA :...............................................................15
2.4.1.1. Protocoles à base de TDMA centralisés ......................................................16
2.4.1.1.1 BMA ....................................................................................................16
2.4.1.1.2. ED-TDMA ...........................................................................................17
2.4.1.2. Protocoles à base de TDMA distribués ............................................................19
2.4.1.2.1. TRAMA :.............................................................................................19
2.4.1.2.2. TDMA-CA ..........................................................................................20
2.4.2.Protocoles MAC basés sur la contention ................................................................22
2.4.2.1 Les protocoles MAC synchrones ou slottés : .....................................................22
2.4.2.1. S-MAC...................................................................................................23
2.4.2.2. T-MAC...................................................................................................24
2.4.2.2.Les protocoles MAC asynchrones....................................................................26
2.4.2.2.1. B-MAC................................................................................................26
2.4.2.2.2. WiseMAC ............................................................................................27
2.4.3. Protocoles MAC hybrides...................................................................................29
2.4.3. 1. G-MAC ......................................................................................................29
2.4.3. 2. A-MAC ......................................................................................................30
2.4.3. 3. Z-MAC.......................................................................................................31
2.5. Conclusion ..........................................................................................................33
Chapitre3 : Contribution et Simulation
3.1. Introduction : .......................................................................................................34
I. Première partie ........................................................................................................34
3.2Description générale du protocole proposé ................................................................34
3.3.Présentation du protocole proposé ...........................................................................35
3.3.1. Les Hypothèses...............................................................................................35
3.4. L‟algorithme proposé :..........................................................................................36
3.5. Le design du protocole: .........................................................................................37
3.5.1. Sleepstate: ......................................................................................................38
3.5.3 Réglage du temps de sommeil dynamiquement :...................................................39
3.5.4. Les opérations des nœuds de DSA-MAC............................................................40
3.6. L'algorithme de protocole ......................................................................................41
3.7. la cotribution ……………………………………………………………………………………………………………....42
II. Deuxiéme partie .....................................................................................................43
3.8. L‟environnement de développement .......................................................................43
3.9. Etapes de réalisation de l‟algorithme proposé...........................................................43
3.10 Le principe de CSMA/CA.....................................................................................45
3.11 L‟algorithme de backoffexponentiel BEB (Binary Exponential Backoff)...................46
3.12. Les paramètres d‟évaluation du système ................................................................47
3.13. Les paramètres de simulation ...............................................................................48
3.14.Etude des résultats de simulation ...........................................................................48
3.14.1 Comparaison de l‟énergie consommée...............................................................48
3.14.2. Comparaison de la latence de bout-en-bout .......................................................49
3.14.3. Comparaison du taux de paquets délivrés..........................................................51
3.15. Conclusion ......................................................................................................52
Conclusion générale et perspectives..............................................................................53Côte titre : MAI/0115 En ligne : https://drive.google.com/file/d/19WBeBCBT8CRD8Jt4Nb4aaujV1ajvl7jJ/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0115 MAI/0115 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Amélioration du routage Cross-Layer pour les réseaux de capteurs sans fil Type de document : texte imprimé Auteurs : Sekhri,lamia yasmine ; SEMCHEDINE, FOUZI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (45f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
capteurs sans fil
routage
Cross-Layer
CLEEPIndex. décimale : 004 Informatique Résumé : Résumé
Les recherches dans les réseaux de capteurs sans fil visent à développer des protocoles
et des algorithmes pour faire face au problème de la consommation énergétique, afin de la
minimiser au maximum. La plupart de ces recherches sont basées sur l‟approche
monocouche du modèle OSI. Récemment, les chercheurs s‟orientent vers l‟exploitation de
plusieurs couches à la fois afin d‟optimiser la consommation d‟énergie.
Dans ce mémoire, nous avons proposé une variante afin d‟améliorer un protocole de
routage Cross-Layer dans les réseaux de capteurs sans fil et qui considère la couche
physique, la couche MAC et la couche réseau. Les résultats obtenus lors de la simulation
montrent que le protocole améliore les performances en termes de consommation d‟énergie,
de taux de délivrances de paquets et équilibre la charge énergétique des capteurs, en
comparaison avec les protocoles EECP, CLEEP et SMAC.
Note de contenu : Tables des matières
Introduction générale...................................................................................................................i
Organisation du mémoire ..........................................................................................................iii
Chapitre I : Les réseaux de capteurs sans fil
1.1. Introduction ..................................................................................................................... 1
1.2. Les capteurs sans fil ........................................................................................................ 1
1.2.1. Définition ................................................................................................................. 1
1.2.2. Architecture d‟un capteur sans fil ............................................................................ 2
1.3. Les réseaux de capteurs sans fil (RSCF)......................................................................... 3
1.3.1. Architecture des RCSF ............................................................................................ 3
1.3.2. Architecture protocolaire ......................................................................................... 4
1.3.2. La Collecte d‟information ........................................................................................ 5
1.3.3. Les topologies des RCSF ......................................................................................... 6
1.3.4. Domaines d‟application des RCSF .......................................................................... 7
1.3.5. Facteurs de conception des RCSF............................................................................ 8
1.4. La consommation d‟énergie dans un nœud capteur........................................................ 9
1.4.1. Énergie de capture................................................................................................... 9
1.4.2. Énergie de traitement .............................................................................................. 9
1.4.3. Énergie de communication.................................................................................... 10
1.5. Les sources de gaspillage d‟énergie .............................................................................. 10
1.6. Conclusion..................................................................................................................... 11
Chapitre II : Les protocoles de routage Cross-Layer
2.1. Introduction ................................................................................................................... 12
2.2. La conception Cross-Layer (inter-couches) ................................................................. 12
2.3. Les architectures Cross-Layer....................................................................................... 13
2.3.1. Architecture Cross-Layer à base de communication directe ................................ 13
2.3.2. Architecture Cross-Layer à base de communication indirecte ............................ 14
2.3.3. Architecture Cross-Layer à base de nouvelles abstractions.................................. 14
2.4. Les protocoles de routage Cross-Layer......................................................................... 14
2.4.1. Le protocole S-MAC.............................................................................................. 15
2.4.2. Le protocole EFS-C ............................................................................................... 15
2.4.3. Le protocole MAC-CROSS .................................................................................. 16
2.4.4. Le protocole CL-MAC........................................................................................... 17
2.4.5. Le protocole CLEEP .............................................................................................. 18
2.4.6. Le protocole ECLP ................................................................................................ 19
2.4.7. Le protocole CLP................................................................................................... 20
2.5. Conclusion..................................................................................................................... 21
Chapitre III : Amélioration d'un protocole de routage Cross-Layer
3.1. Introduction ................................................................................................................... 22
3.2. Motivation ..................................................................................................................... 22
3.3. Le protocole EECP (Energy Efficient Cross-layer Protocol)........................................ 23
3.3.1. Les hypothèses....................................................................................................... 23
3.3.2. Conception du protocole ........................................................................................ 24
3.4. Amélioration du protocole EECP.................................................................................. 27
3.4.1. Le problème des trous et l‟insuffisance énergétique.............................................. 27
3.4.2. Solution proposée................................................................................................... 28
3.4.2.1. Ajouter une contrainte sur l‟énergie résiduelle du nœud suivant ................... 29
3.4.2.2. Augmenter la puissance de transmission........................................................ 29
3.5. Conclusion..................................................................................................................... 32
Chapitre IV : Simulation et évaluation des performances
4.1. Introduction ................................................................................................................... 33
4.2. Environnement de la simulation.................................................................................... 33
4.2.1. Choix du langage de programmation..................................................................... 33
4.2.2. Description du simulateur...................................................................................... 34
4.2.3. Fonctionnement du simulateur............................................................................... 35
4.2.4. Les paramètres de simulation................................................................................. 36
4.3. Les métrique d‟évaluation des performances................................................................ 37
4.3.1. La durée de vie du réseau .......................................................................................... 37
4.3.2. L‟énergie résiduelle moyenne (ARE) .................................................................... 37
4.3.3. L‟énergie résiduelle (RE)....................................................................................... 37
4.3.4. Le taux de délivrance des paquets (PDR).............................................................. 38
4.4. Résultats et interprétations............................................................................................ 38
4.4.1. Energie résiduelle moyenne ................................................................................... 38
4.4.2. Energie résiduelle................................................................................................... 40
4.4.3. Durée de vie du réseau........................................................................................... 43
4.4.4. Taux de délivrances de paquets ............................................................................. 43
4.5. Conclusion..................................................................................................................... 45
Conclusion générale
BibliographieCôte titre : MAI/0129 En ligne : https://drive.google.com/file/d/11LOt89mOMRb4rxZ_ugw9lMUdw_qPfqxn/view?usp=shari [...] Format de la ressource électronique : Amélioration du routage Cross-Layer pour les réseaux de capteurs sans fil [texte imprimé] / Sekhri,lamia yasmine ; SEMCHEDINE, FOUZI, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (45f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
capteurs sans fil
routage
Cross-Layer
CLEEPIndex. décimale : 004 Informatique Résumé : Résumé
Les recherches dans les réseaux de capteurs sans fil visent à développer des protocoles
et des algorithmes pour faire face au problème de la consommation énergétique, afin de la
minimiser au maximum. La plupart de ces recherches sont basées sur l‟approche
monocouche du modèle OSI. Récemment, les chercheurs s‟orientent vers l‟exploitation de
plusieurs couches à la fois afin d‟optimiser la consommation d‟énergie.
Dans ce mémoire, nous avons proposé une variante afin d‟améliorer un protocole de
routage Cross-Layer dans les réseaux de capteurs sans fil et qui considère la couche
physique, la couche MAC et la couche réseau. Les résultats obtenus lors de la simulation
montrent que le protocole améliore les performances en termes de consommation d‟énergie,
de taux de délivrances de paquets et équilibre la charge énergétique des capteurs, en
comparaison avec les protocoles EECP, CLEEP et SMAC.
Note de contenu : Tables des matières
Introduction générale...................................................................................................................i
Organisation du mémoire ..........................................................................................................iii
Chapitre I : Les réseaux de capteurs sans fil
1.1. Introduction ..................................................................................................................... 1
1.2. Les capteurs sans fil ........................................................................................................ 1
1.2.1. Définition ................................................................................................................. 1
1.2.2. Architecture d‟un capteur sans fil ............................................................................ 2
1.3. Les réseaux de capteurs sans fil (RSCF)......................................................................... 3
1.3.1. Architecture des RCSF ............................................................................................ 3
1.3.2. Architecture protocolaire ......................................................................................... 4
1.3.2. La Collecte d‟information ........................................................................................ 5
1.3.3. Les topologies des RCSF ......................................................................................... 6
1.3.4. Domaines d‟application des RCSF .......................................................................... 7
1.3.5. Facteurs de conception des RCSF............................................................................ 8
1.4. La consommation d‟énergie dans un nœud capteur........................................................ 9
1.4.1. Énergie de capture................................................................................................... 9
1.4.2. Énergie de traitement .............................................................................................. 9
1.4.3. Énergie de communication.................................................................................... 10
1.5. Les sources de gaspillage d‟énergie .............................................................................. 10
1.6. Conclusion..................................................................................................................... 11
Chapitre II : Les protocoles de routage Cross-Layer
2.1. Introduction ................................................................................................................... 12
2.2. La conception Cross-Layer (inter-couches) ................................................................. 12
2.3. Les architectures Cross-Layer....................................................................................... 13
2.3.1. Architecture Cross-Layer à base de communication directe ................................ 13
2.3.2. Architecture Cross-Layer à base de communication indirecte ............................ 14
2.3.3. Architecture Cross-Layer à base de nouvelles abstractions.................................. 14
2.4. Les protocoles de routage Cross-Layer......................................................................... 14
2.4.1. Le protocole S-MAC.............................................................................................. 15
2.4.2. Le protocole EFS-C ............................................................................................... 15
2.4.3. Le protocole MAC-CROSS .................................................................................. 16
2.4.4. Le protocole CL-MAC........................................................................................... 17
2.4.5. Le protocole CLEEP .............................................................................................. 18
2.4.6. Le protocole ECLP ................................................................................................ 19
2.4.7. Le protocole CLP................................................................................................... 20
2.5. Conclusion..................................................................................................................... 21
Chapitre III : Amélioration d'un protocole de routage Cross-Layer
3.1. Introduction ................................................................................................................... 22
3.2. Motivation ..................................................................................................................... 22
3.3. Le protocole EECP (Energy Efficient Cross-layer Protocol)........................................ 23
3.3.1. Les hypothèses....................................................................................................... 23
3.3.2. Conception du protocole ........................................................................................ 24
3.4. Amélioration du protocole EECP.................................................................................. 27
3.4.1. Le problème des trous et l‟insuffisance énergétique.............................................. 27
3.4.2. Solution proposée................................................................................................... 28
3.4.2.1. Ajouter une contrainte sur l‟énergie résiduelle du nœud suivant ................... 29
3.4.2.2. Augmenter la puissance de transmission........................................................ 29
3.5. Conclusion..................................................................................................................... 32
Chapitre IV : Simulation et évaluation des performances
4.1. Introduction ................................................................................................................... 33
4.2. Environnement de la simulation.................................................................................... 33
4.2.1. Choix du langage de programmation..................................................................... 33
4.2.2. Description du simulateur...................................................................................... 34
4.2.3. Fonctionnement du simulateur............................................................................... 35
4.2.4. Les paramètres de simulation................................................................................. 36
4.3. Les métrique d‟évaluation des performances................................................................ 37
4.3.1. La durée de vie du réseau .......................................................................................... 37
4.3.2. L‟énergie résiduelle moyenne (ARE) .................................................................... 37
4.3.3. L‟énergie résiduelle (RE)....................................................................................... 37
4.3.4. Le taux de délivrance des paquets (PDR).............................................................. 38
4.4. Résultats et interprétations............................................................................................ 38
4.4.1. Energie résiduelle moyenne ................................................................................... 38
4.4.2. Energie résiduelle................................................................................................... 40
4.4.3. Durée de vie du réseau........................................................................................... 43
4.4.4. Taux de délivrances de paquets ............................................................................. 43
4.5. Conclusion..................................................................................................................... 45
Conclusion générale
BibliographieCôte titre : MAI/0129 En ligne : https://drive.google.com/file/d/11LOt89mOMRb4rxZ_ugw9lMUdw_qPfqxn/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0129 MAI/0129 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Conception et implémentation d'un simulateur pour les réseaux de capteurs sans fil Type de document : texte imprimé Auteurs : Khalfi,hanane ; SEMCHEDINE, FOUZI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (45f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
capteurs sans fil
gestion d’énergie
simulateur
système Multi-agentsIndex. décimale : 004 Informatique Résumé : Résumé
Le réseau de capteur sans fil « RCSF » est une technologie émergente qui vise Ã
offrir des capacités innovantes. Son utilisation ne devrait cesser d’augmenté et ceci dans
de nombreux domaines qu’ils soient scientifique, militaire ou industrielle. Une des
contraintes principales de conception des RCSF est la simulation du comportement de
ses nœuds.
L’objectif principal de ce mémoire est de réaliser un simulateur de réseau de capteur
sans fil afin de rendre plus pratique la tâche de simulation des RCSFs. Notre simulateur
est un système multi-agents où les nœuds capteurs sont des agents qui se lancent au
moment du déploiement du réseau afin d’émuler le comportement réel d’un RCSF. Pour
rendre portable le simulateur, ce dernier a été développé en JAVA.
Note de contenu : 1. Table des matières
Introduction générale ---------------------------------------------------------------------------------1
Chapitre 1 : les concepts de base des RCSFs----------------------------------------------------------3
1. Introduction _____________________________________________________3
2. NÅ“ud capteur ____________________________________________________3
2.1 Définition ____________________________________________________3
2.2 Architecture _______________________________________________________ 3
3. Réseau de capteurs sans fil __________________________________________5
3.1 Définition ____________________________________________________5
3.2 Architecture protocolaire________________________________________6
3.3 Caractéristiques des réseaux de capteurs sans fil _____________________7
3.4 Domaine d’application __________________________________________8
4. Les simulateurs des RCSFs ___________________________________________8
4.1 NS-2 ________________________________________________________9
4.2 OMNET++ ___________________________________________________10
4.3 GloMoSim___________________________________________________10
4.4 Opnet ______________________________________________________11
4.5 J-Sim _______________________________________________________12
5. Conclusion ______________________________________________________12
Chapitre 2 : Conception --------------------------------------------------------------------------- 13
1. Introduction ____________________________________________________ 13
2. Prometheus ____________________________________________________ 13
3. La spécification du système ________________________________________ 14
3.1 Les buts du système __________________________________________ 14
3.1.1 Les sous buts du système ___________________________________ 14
3.2 Les fonctionnalités __________________________________________ 17
3.2.1 Descripteur textuelle _______________________________________ 17
3.3 Les scénarios des cas d’utilisation _______________________________ 24
4. Conception architecturale _________________________________________ 25
4.1 Les types d’agents ___________________________________________ 25
4.2 Diagramme de couplage de données ____________________________ 25
4.3 Diagramme de rôles d’agents __________________________________ 26
4.4 Diagramme d’accointance _____________________________________ 26
4.5 Diagramme d’interaction ______________________________________ 27
5. La conception détaillée ___________________________________________ 28
5.1 Diagramme de vue de l’agent interface __________________________ 28
5.2 Diagramme de vue de l’agent système ___________________________ 29
5.3 Diagramme de vue de l’agent station ____________________________ 29
5.4 Diagramme de vue de l’agent capteur____________________________ 30
6. Conclusion _____________________________________________________ 31
Chapitre 3 : Réalisation ----------------------------------------------------------------------------33
1. Introduction ____________________________________________________ 33
2. Choix technique _________________________________________________ 33
2.1 Le langage Java______________________________________________ 33
2.2 L’environnement de développement eclipse ______________________ 33
2.3 Choix de la plateforme Jade____________________________________ 34
3. Implémentation du système _______________________________________ 34
3.1 Fonctionnement du système ___________________________________ 34
3.2 Implémentation de l’interface __________________________________ 35
3.2.1 L’interface de démarrage ____________________________________ 35
3.3 Les courbes tracées __________________________________________ 41
4. Conclusion _____________________________________________________ 42
Conclusion générale ------------------------------------------------------------------------------- 43
Bibliographie -----------------------------------------------------------------------------------------44Côte titre : MAI/0127 En ligne : https://drive.google.com/file/d/12RTnzCKmN-osNkO-xS2kcqviji9ediKp/view?usp=shari [...] Format de la ressource électronique : Conception et implémentation d'un simulateur pour les réseaux de capteurs sans fil [texte imprimé] / Khalfi,hanane ; SEMCHEDINE, FOUZI, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (45f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
capteurs sans fil
gestion d’énergie
simulateur
système Multi-agentsIndex. décimale : 004 Informatique Résumé : Résumé
Le réseau de capteur sans fil « RCSF » est une technologie émergente qui vise Ã
offrir des capacités innovantes. Son utilisation ne devrait cesser d’augmenté et ceci dans
de nombreux domaines qu’ils soient scientifique, militaire ou industrielle. Une des
contraintes principales de conception des RCSF est la simulation du comportement de
ses nœuds.
L’objectif principal de ce mémoire est de réaliser un simulateur de réseau de capteur
sans fil afin de rendre plus pratique la tâche de simulation des RCSFs. Notre simulateur
est un système multi-agents où les nœuds capteurs sont des agents qui se lancent au
moment du déploiement du réseau afin d’émuler le comportement réel d’un RCSF. Pour
rendre portable le simulateur, ce dernier a été développé en JAVA.
Note de contenu : 1. Table des matières
Introduction générale ---------------------------------------------------------------------------------1
Chapitre 1 : les concepts de base des RCSFs----------------------------------------------------------3
1. Introduction _____________________________________________________3
2. NÅ“ud capteur ____________________________________________________3
2.1 Définition ____________________________________________________3
2.2 Architecture _______________________________________________________ 3
3. Réseau de capteurs sans fil __________________________________________5
3.1 Définition ____________________________________________________5
3.2 Architecture protocolaire________________________________________6
3.3 Caractéristiques des réseaux de capteurs sans fil _____________________7
3.4 Domaine d’application __________________________________________8
4. Les simulateurs des RCSFs ___________________________________________8
4.1 NS-2 ________________________________________________________9
4.2 OMNET++ ___________________________________________________10
4.3 GloMoSim___________________________________________________10
4.4 Opnet ______________________________________________________11
4.5 J-Sim _______________________________________________________12
5. Conclusion ______________________________________________________12
Chapitre 2 : Conception --------------------------------------------------------------------------- 13
1. Introduction ____________________________________________________ 13
2. Prometheus ____________________________________________________ 13
3. La spécification du système ________________________________________ 14
3.1 Les buts du système __________________________________________ 14
3.1.1 Les sous buts du système ___________________________________ 14
3.2 Les fonctionnalités __________________________________________ 17
3.2.1 Descripteur textuelle _______________________________________ 17
3.3 Les scénarios des cas d’utilisation _______________________________ 24
4. Conception architecturale _________________________________________ 25
4.1 Les types d’agents ___________________________________________ 25
4.2 Diagramme de couplage de données ____________________________ 25
4.3 Diagramme de rôles d’agents __________________________________ 26
4.4 Diagramme d’accointance _____________________________________ 26
4.5 Diagramme d’interaction ______________________________________ 27
5. La conception détaillée ___________________________________________ 28
5.1 Diagramme de vue de l’agent interface __________________________ 28
5.2 Diagramme de vue de l’agent système ___________________________ 29
5.3 Diagramme de vue de l’agent station ____________________________ 29
5.4 Diagramme de vue de l’agent capteur____________________________ 30
6. Conclusion _____________________________________________________ 31
Chapitre 3 : Réalisation ----------------------------------------------------------------------------33
1. Introduction ____________________________________________________ 33
2. Choix technique _________________________________________________ 33
2.1 Le langage Java______________________________________________ 33
2.2 L’environnement de développement eclipse ______________________ 33
2.3 Choix de la plateforme Jade____________________________________ 34
3. Implémentation du système _______________________________________ 34
3.1 Fonctionnement du système ___________________________________ 34
3.2 Implémentation de l’interface __________________________________ 35
3.2.1 L’interface de démarrage ____________________________________ 35
3.3 Les courbes tracées __________________________________________ 41
4. Conclusion _____________________________________________________ 42
Conclusion générale ------------------------------------------------------------------------------- 43
Bibliographie -----------------------------------------------------------------------------------------44Côte titre : MAI/0127 En ligne : https://drive.google.com/file/d/12RTnzCKmN-osNkO-xS2kcqviji9ediKp/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0127 MAI/0127 Mémoire Bibliothéque des sciences Français Disponible
Disponible
PermalinkPermalinkPermalink
