University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'éditeur
Setif:UFA |
Documents disponibles chez cet éditeur
![](./images/expand_all.gif)
![](./images/collapse_all.gif)
Titre : Optimisation par essaims de particules sous scilab Type de document : texte imprimé Auteurs : Saber,Amina, Auteur ; Semchedine ,Moussa, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (63 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Index. décimale : 004 - Informatique Côte titre : MAI/0237 Optimisation par essaims de particules sous scilab [texte imprimé] / Saber,Amina, Auteur ; Semchedine ,Moussa, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (63 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Index. décimale : 004 - Informatique Côte titre : MAI/0237 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0237 MAI/0237 Mémoire Bibliothéque des sciences Français Disponible
DisponibleOptimisation des performances d’une ligne à retard acoustique à base de l’AlN dopé par Cr : application aux résonateurs à faible consommation d’énergie / Oussama Mansar
![]()
Titre : Optimisation des performances d’une ligne à retard acoustique à base de l’AlN dopé par Cr : application aux résonateurs à faible consommation d’énergie Type de document : texte imprimé Auteurs : Oussama Mansar ; Farouk Laidoudi, Directeur de thèse Editeur : Setif:UFA Année de publication : 2021 Importance : 1 vol. (61 f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Physique Mots-clés : Méthode DFT
Méthode des éléments finis
Ondes acoustiques SAW
AlCrN
Résonateur électroacoustiqueIndex. décimale : 530 Physique Résumé :
Ce travail a comme objectif l’étude des performances d’un résonateur à onde acoustique de surface SAW à base de nitrure d’aluminium dopé par Chrome Cr sur substrat en saphir. Les paramètres électromécaniques de l’AlCrN ont été obtenus des calculs par la méthode de la densité fonctionnelle pour différentes concentrations de Cr dont une amélioration de la piézoélectricité a été remarquée. La vitesse de phase et le facteur de couplage électromécanique K² des modes acoustiques de surface SAW dans l’AlCrN ont été obtenues par la méthode des éléments finis FEM pour différentes Cr concentrations et différentes valeurs de hAlCrN/λ. En outre, l’admittance électrique et le coefficient de transmission S21 du mode de Rayleigh ont été obtenus numériquement. La comparaison des résultats obtenus par FEM avec d’autres résultats dans la littérature a montré une amélioration considérable des caractéristiques du résonateur SAW après incorporation du Cr en permettant la conception et la réalisation des résonateurs électroacoustiques avec faible consommation de l’énergie.Côte titre : MAPH/0477 En ligne : https://drive.google.com/file/d/1oAuQamjMWGWz01i56ndjECoaCWWQth7i/view?usp=shari [...] Format de la ressource électronique : Optimisation des performances d’une ligne à retard acoustique à base de l’AlN dopé par Cr : application aux résonateurs à faible consommation d’énergie [texte imprimé] / Oussama Mansar ; Farouk Laidoudi, Directeur de thèse . - [S.l.] : Setif:UFA, 2021 . - 1 vol. (61 f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Physique Mots-clés : Méthode DFT
Méthode des éléments finis
Ondes acoustiques SAW
AlCrN
Résonateur électroacoustiqueIndex. décimale : 530 Physique Résumé :
Ce travail a comme objectif l’étude des performances d’un résonateur à onde acoustique de surface SAW à base de nitrure d’aluminium dopé par Chrome Cr sur substrat en saphir. Les paramètres électromécaniques de l’AlCrN ont été obtenus des calculs par la méthode de la densité fonctionnelle pour différentes concentrations de Cr dont une amélioration de la piézoélectricité a été remarquée. La vitesse de phase et le facteur de couplage électromécanique K² des modes acoustiques de surface SAW dans l’AlCrN ont été obtenues par la méthode des éléments finis FEM pour différentes Cr concentrations et différentes valeurs de hAlCrN/λ. En outre, l’admittance électrique et le coefficient de transmission S21 du mode de Rayleigh ont été obtenus numériquement. La comparaison des résultats obtenus par FEM avec d’autres résultats dans la littérature a montré une amélioration considérable des caractéristiques du résonateur SAW après incorporation du Cr en permettant la conception et la réalisation des résonateurs électroacoustiques avec faible consommation de l’énergie.Côte titre : MAPH/0477 En ligne : https://drive.google.com/file/d/1oAuQamjMWGWz01i56ndjECoaCWWQth7i/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAPH/0477 MAPH/0477 Mémoire Bibliothéque des sciences Français Disponible
DisponibleOptimisation des performances par administration et tuning d’entrepôt de données / TOUMI, Lyazid
![]()
Titre : Optimisation des performances par administration et tuning d’entrepôt de données Type de document : texte imprimé Auteurs : TOUMI, Lyazid, Auteur ; Abdelouahab Moussaoui, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (134 f .) Format : 29 cm Catégories : Informatique Mots-clés : Entrepôts de données, auto-administration et tuning, conception physique des entrepôts
de données, optimisation, programmation linéaire, fouille de données, fragmentation
horizontale, sélection d’indexes binaires de jointures.Résumé : Résumé :
Cette thèse présente un travail sur l’administration et tuning d’entrepôts de données, précisément
aborde le problème de sélection d’indexes binaires de jointure (PSIJB) et le problème de la
fragmentation horizontale dérivé (PFHD). La thèse propose trois contributions à la recherche, la
première contribution utilise les essaims de particule pour résoudre le PSIJB. La deuxième permet de
modéliser le PSIJB en utilisant la programmation linéaire en nombre entier. Dans la troisième
contribution, nous avons proposé une nouvelle méthodologie pour résoudre le PFHD. Toutes les
approches proposées ont été validées par des tests sous un entrepôt de données utilisant des classes de
problèmes. Ces tests ont montré l’efficacité des approches proposées en terme de temps, de qualité
ainsi que d’exactitudes.
Note de contenu : TABLE OF CONTENTS
Page
List of Tables ix
List of Figures xi
1 Introduction 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis goals and results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Academic publication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I Backgrounds and state of art 7
2 Data warehouses architecture and design 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Data warehouses architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 The Data Cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Data warehouse physical design . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Data warehouse tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6 DBMS tuning tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Indexes selection problem in data warehouses 17
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Indexation techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1 B-tree index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2 Projection index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.3 Hash index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.4 Bitmap Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.5 Join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.6 Star join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.7 Bitmap join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Bitmap join indexes selection problem in data warehouses . . . . . . . . . . 22
3.3.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2.1 Data access cost in presence of useful SBJIs (IndexCost) . 24
3.3.2.2 Data access cost in absence of useful SBJIs(JoinCost) . . . 24
3.3.2.3 Size of SBJI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Background of indexes selection problem . . . . . . . . . . . . . . . . . . . . . 25
3.4.1 Frank et al. approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.2 Choenni’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.3 Gundem’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.4 Golfarelli’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.5 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.5.1 Mining closed frequent pattern . . . . . . . . . . . . . . . . 29
3.4.5.2 General schema of the data mining approach . . . . . . . . 30
3.4.6 Extended data mining based approach . . . . . . . . . . . . . . . . . . 31
3.4.7 Genetic algorithm based approach . . . . . . . . . . . . . . . . . . . . 32
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Horizontal partitioning in data warehouses 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Horizontal partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Horizontal partitioning example . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5 Horizontal partitioning advantages . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5.1 Horizontal Partitioning for databases administration . . . . . . . . . 40
4.5.2 Partitioning for performance optimization . . . . . . . . . . . . . . . 40
4.5.3 Partitioning for the availability . . . . . . . . . . . . . . . . . . . . . . 40
4.6 Horizontal partitioning modes . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.1 Range partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.2 Hach partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6.3 List partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6.4 Composite partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.5 Multicolumn partitioning mode . . . . . . . . . . . . . . . . . . . . . . 46
4.6.6 Reference partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 47
4.6.7 Virtual column partitioning . . . . . . . . . . . . . . . . . . . . . . . . 48
4.7 Horizontal partitioning problem in data warehouses . . . . . . . . . . . . . . 49
4.7.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.7.2 Cost model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.8 Background of approaches for the horizontal partitioning Problem . . . . . 50
4.8.1 Workload-based approach . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.8.2 Attribute affinity based approach . . . . . . . . . . . . . . . . . . . . . 51
4.8.3 Cost based approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.4 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.5 Constrained cost based approach . . . . . . . . . . . . . . . . . . . . . 53
4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
II Contributions 57
5 Particle swarm optimization for solving SBJISP 59
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Particle Swarm Optimization (PSO) . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2.1 The PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.2 Binary particle swarm optimization (BPSO) . . . . . . . . . . . . . . . 61
5.2.3 Inertia weight considerations for BPSO . . . . . . . . . . . . . . . . . 62
5.3 BPSO for the SBJI selection problem . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.1 Query workload parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.2 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.3 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.4.3.1 The smaller size problem set CSP results . . . . . . . . . . 69
5.4.3.2 The moderate size problem set CMP results . . . . . . . . 72
5.4.3.3 The larger size problem set CLP results . . . . . . . . . . . 74
5.4.4 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 76
5.4.4.1 Scalability results for the smaller size problem set CSP. . 76
5.4.4.2 Scalability results for the moderate size problem set CMP. 79
5.4.4.3 Scalability results for the larger size problem set CLP. . . 82
5.4.5 Performance results for the classes CSP, CMP and CLP using Oracle
DBMS cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6 Mixed-Integer linear programming for SBJISP 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2 Linear programming definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.1 Linear program solution time . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.2 Mixed Integer Programming . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3 Mathematical formulation of SBJI selection problem . . . . . . . . . . . . . . 92
6.3.1 SBJISP constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.3.2 SBJISP objective Function . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2.1 The smaller size problem set CSP results . . . . . . . . . . 98
6.4.2.2 The moderate size problem set CMP results . . . . . . . . 98
6.4.2.3 The larger size problem set CLP results . . . . . . . . . . . 101
6.4.3 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 101
6.4.3.1 Scalability results for the smaller size problem set CSP. . 101
6.4.3.2 Scalability results for the moderate size problem set CMP. 102
6.4.3.3 Scalability results for the larger size problem set CLP. . . 105
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7 Efficient methodology for Reference Horizontal partitioning in data warehouses 109
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 The proposed methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.1 Predicates attraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.2 Clustering of Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2.3 Determining the number of clusters . . . . . . . . . . . . . . . . . . . 113
7.2.3.1 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2.4 Discrete particle swarm optimization for selecting horizontal partitioning schema . . . . . . . . . . . . . 114
7.2.4.1 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3.1 The smaller size problem set CSP results . . . . . . . . . . 117
7.3.3.2 The moderate size problem set CMP results . . . . . . . . 120
7.3.3.3 The larger size problem set CLP results . . . . . . . . . . . 122
7.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
8 Conclusions 125
8.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.2 Future research directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Bibliography 127Côte titre : DI/0022 En ligne : https://drive.google.com/file/d/1qaEXnuqod_wfImnJx2cU1N0-S8Fil2eT/view?usp=shari [...] Format de la ressource électronique : Optimisation des performances par administration et tuning d’entrepôt de données [texte imprimé] / TOUMI, Lyazid, Auteur ; Abdelouahab Moussaoui, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (134 f .) ; 29 cm.
Catégories : Informatique Mots-clés : Entrepôts de données, auto-administration et tuning, conception physique des entrepôts
de données, optimisation, programmation linéaire, fouille de données, fragmentation
horizontale, sélection d’indexes binaires de jointures.Résumé : Résumé :
Cette thèse présente un travail sur l’administration et tuning d’entrepôts de données, précisément
aborde le problème de sélection d’indexes binaires de jointure (PSIJB) et le problème de la
fragmentation horizontale dérivé (PFHD). La thèse propose trois contributions à la recherche, la
première contribution utilise les essaims de particule pour résoudre le PSIJB. La deuxième permet de
modéliser le PSIJB en utilisant la programmation linéaire en nombre entier. Dans la troisième
contribution, nous avons proposé une nouvelle méthodologie pour résoudre le PFHD. Toutes les
approches proposées ont été validées par des tests sous un entrepôt de données utilisant des classes de
problèmes. Ces tests ont montré l’efficacité des approches proposées en terme de temps, de qualité
ainsi que d’exactitudes.
Note de contenu : TABLE OF CONTENTS
Page
List of Tables ix
List of Figures xi
1 Introduction 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis goals and results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Academic publication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I Backgrounds and state of art 7
2 Data warehouses architecture and design 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Data warehouses architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 The Data Cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Data warehouse physical design . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Data warehouse tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6 DBMS tuning tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Indexes selection problem in data warehouses 17
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Indexation techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1 B-tree index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2 Projection index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.3 Hash index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.4 Bitmap Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.5 Join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.6 Star join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.7 Bitmap join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Bitmap join indexes selection problem in data warehouses . . . . . . . . . . 22
3.3.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2.1 Data access cost in presence of useful SBJIs (IndexCost) . 24
3.3.2.2 Data access cost in absence of useful SBJIs(JoinCost) . . . 24
3.3.2.3 Size of SBJI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Background of indexes selection problem . . . . . . . . . . . . . . . . . . . . . 25
3.4.1 Frank et al. approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.2 Choenni’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.3 Gundem’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.4 Golfarelli’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.5 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.5.1 Mining closed frequent pattern . . . . . . . . . . . . . . . . 29
3.4.5.2 General schema of the data mining approach . . . . . . . . 30
3.4.6 Extended data mining based approach . . . . . . . . . . . . . . . . . . 31
3.4.7 Genetic algorithm based approach . . . . . . . . . . . . . . . . . . . . 32
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Horizontal partitioning in data warehouses 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Horizontal partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Horizontal partitioning example . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5 Horizontal partitioning advantages . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5.1 Horizontal Partitioning for databases administration . . . . . . . . . 40
4.5.2 Partitioning for performance optimization . . . . . . . . . . . . . . . 40
4.5.3 Partitioning for the availability . . . . . . . . . . . . . . . . . . . . . . 40
4.6 Horizontal partitioning modes . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.1 Range partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.2 Hach partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6.3 List partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6.4 Composite partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.5 Multicolumn partitioning mode . . . . . . . . . . . . . . . . . . . . . . 46
4.6.6 Reference partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 47
4.6.7 Virtual column partitioning . . . . . . . . . . . . . . . . . . . . . . . . 48
4.7 Horizontal partitioning problem in data warehouses . . . . . . . . . . . . . . 49
4.7.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.7.2 Cost model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.8 Background of approaches for the horizontal partitioning Problem . . . . . 50
4.8.1 Workload-based approach . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.8.2 Attribute affinity based approach . . . . . . . . . . . . . . . . . . . . . 51
4.8.3 Cost based approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.4 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.5 Constrained cost based approach . . . . . . . . . . . . . . . . . . . . . 53
4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
II Contributions 57
5 Particle swarm optimization for solving SBJISP 59
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Particle Swarm Optimization (PSO) . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2.1 The PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.2 Binary particle swarm optimization (BPSO) . . . . . . . . . . . . . . . 61
5.2.3 Inertia weight considerations for BPSO . . . . . . . . . . . . . . . . . 62
5.3 BPSO for the SBJI selection problem . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.1 Query workload parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.2 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.3 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.4.3.1 The smaller size problem set CSP results . . . . . . . . . . 69
5.4.3.2 The moderate size problem set CMP results . . . . . . . . 72
5.4.3.3 The larger size problem set CLP results . . . . . . . . . . . 74
5.4.4 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 76
5.4.4.1 Scalability results for the smaller size problem set CSP. . 76
5.4.4.2 Scalability results for the moderate size problem set CMP. 79
5.4.4.3 Scalability results for the larger size problem set CLP. . . 82
5.4.5 Performance results for the classes CSP, CMP and CLP using Oracle
DBMS cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6 Mixed-Integer linear programming for SBJISP 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2 Linear programming definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.1 Linear program solution time . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.2 Mixed Integer Programming . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3 Mathematical formulation of SBJI selection problem . . . . . . . . . . . . . . 92
6.3.1 SBJISP constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.3.2 SBJISP objective Function . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2.1 The smaller size problem set CSP results . . . . . . . . . . 98
6.4.2.2 The moderate size problem set CMP results . . . . . . . . 98
6.4.2.3 The larger size problem set CLP results . . . . . . . . . . . 101
6.4.3 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 101
6.4.3.1 Scalability results for the smaller size problem set CSP. . 101
6.4.3.2 Scalability results for the moderate size problem set CMP. 102
6.4.3.3 Scalability results for the larger size problem set CLP. . . 105
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7 Efficient methodology for Reference Horizontal partitioning in data warehouses 109
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 The proposed methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.1 Predicates attraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.2 Clustering of Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2.3 Determining the number of clusters . . . . . . . . . . . . . . . . . . . 113
7.2.3.1 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2.4 Discrete particle swarm optimization for selecting horizontal partitioning schema . . . . . . . . . . . . . 114
7.2.4.1 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3.1 The smaller size problem set CSP results . . . . . . . . . . 117
7.3.3.2 The moderate size problem set CMP results . . . . . . . . 120
7.3.3.3 The larger size problem set CLP results . . . . . . . . . . . 122
7.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
8 Conclusions 125
8.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.2 Future research directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Bibliography 127Côte titre : DI/0022 En ligne : https://drive.google.com/file/d/1qaEXnuqod_wfImnJx2cU1N0-S8Fil2eT/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DI/0022 DI/0022 Thèse Bibliothéque des sciences Français Disponible
Disponible
Titre : Optimisation physique des Entrepôt de Données : Cas des Structures redondantes Type de document : texte imprimé Auteurs : MEKIDECHE, MANEL ; TOUMI, Lyazid, Directeur de thèse Editeur : Setif:UFA Année de publication : 2012 Importance : 1 vol (54f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie logiciel
optimisation physique
Entrepôt de Donnée
Structures redondantesIndex. décimale : 004 Informatique Résumé : Conclusion générale
Dans ce travail nous avons concentré sur les techniques d’optimisation des requêtes dans les entrepôts de données et plus précisément sur les problèmes de sélection d’index binaire de jointure, où nous avons proposé une nouvelle heuristique à base des essaims de particules pour résoudre le problème de sélection d’une configuration d’index binaire de jointure et d'autre part nous avons étudier ce qui a été déjà proposé comme approches. A la fin nous avons validé notre approche, où une comparaison a été faite avec l’approche Dynaclose. Du point de vue empirique nous avons implémenté ces algorithmes, qui nous y a permis de calculé les couts d’E/S des requêtes en présence des configurations d’index sélectionnés par les deux approches BPSO et Dynaclose afin d’arriver a tiré des conclusions sur les performances de chacune des approches. A la fin nous avons déduit que notre approche a prouvé son efficacité quand à l’optimisation des performances des entrepôts de données. L’idée de proposer une nouvelle approche pour sélectionner une configuration d’index de jointure binaire est très originale et prometteuse.
D’après les efforts que nous avons fournis durant toute l’année, nous estimons que les objectifs fixés au départ de ce travail sont achevé à un taux élevé de 90%, où nous avons proposé une nouvelle approche et nous avons validé avec des approches déjà proposé et nous avons arrivé à apprendre beaucoup de choses intéressantes et motivantes tels que, les problèmes et les technique de résolutions de problèmes, les entrepôts de données (conception et administration) et les techniques de fouille de données (Close et Charm). Comme perspectives de ce travail, nous jugions nécessaire de faire d’autres types expérimentations, ainsi d’ajouter d’autres paramètres dans le model de coût tel que le Buffer et de proposer les BPSO pour la sélection des index binaire de jointure multi-attributs.Côte titre : MAI/0025 En ligne : https://drive.google.com/file/d/12_fxPIsIWTWj06iVwDAWXkJCu3V0b9cM/view?usp=shari [...] Format de la ressource électronique : Optimisation physique des Entrepôt de Données : Cas des Structures redondantes [texte imprimé] / MEKIDECHE, MANEL ; TOUMI, Lyazid, Directeur de thèse . - [S.l.] : Setif:UFA, 2012 . - 1 vol (54f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie logiciel
optimisation physique
Entrepôt de Donnée
Structures redondantesIndex. décimale : 004 Informatique Résumé : Conclusion générale
Dans ce travail nous avons concentré sur les techniques d’optimisation des requêtes dans les entrepôts de données et plus précisément sur les problèmes de sélection d’index binaire de jointure, où nous avons proposé une nouvelle heuristique à base des essaims de particules pour résoudre le problème de sélection d’une configuration d’index binaire de jointure et d'autre part nous avons étudier ce qui a été déjà proposé comme approches. A la fin nous avons validé notre approche, où une comparaison a été faite avec l’approche Dynaclose. Du point de vue empirique nous avons implémenté ces algorithmes, qui nous y a permis de calculé les couts d’E/S des requêtes en présence des configurations d’index sélectionnés par les deux approches BPSO et Dynaclose afin d’arriver a tiré des conclusions sur les performances de chacune des approches. A la fin nous avons déduit que notre approche a prouvé son efficacité quand à l’optimisation des performances des entrepôts de données. L’idée de proposer une nouvelle approche pour sélectionner une configuration d’index de jointure binaire est très originale et prometteuse.
D’après les efforts que nous avons fournis durant toute l’année, nous estimons que les objectifs fixés au départ de ce travail sont achevé à un taux élevé de 90%, où nous avons proposé une nouvelle approche et nous avons validé avec des approches déjà proposé et nous avons arrivé à apprendre beaucoup de choses intéressantes et motivantes tels que, les problèmes et les technique de résolutions de problèmes, les entrepôts de données (conception et administration) et les techniques de fouille de données (Close et Charm). Comme perspectives de ce travail, nous jugions nécessaire de faire d’autres types expérimentations, ainsi d’ajouter d’autres paramètres dans le model de coût tel que le Buffer et de proposer les BPSO pour la sélection des index binaire de jointure multi-attributs.Côte titre : MAI/0025 En ligne : https://drive.google.com/file/d/12_fxPIsIWTWj06iVwDAWXkJCu3V0b9cM/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0025 MAI/0025 Mémoire Bibliothéque des sciences Français Disponible
DisponibleOptimisation des protocoles de routage dans les réseaux de capteurs avec l’approche de colonie de fourmis / BOUNOUNI, Mahdi
![]()
Titre : Optimisation des protocoles de routage dans les réseaux de capteurs avec l’approche de colonie de fourmis Type de document : texte imprimé Auteurs : BOUNOUNI, Mahdi ; Abdelhafid Benaouda, Directeur de thèse Editeur : Setif:UFA Année de publication : 2012 Importance : 1 vol (68 f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : réseaux de capteurs sans fil,routage,simulation à événements discrets,performance,optimisation par colonie de fourmis (ACO). Index. décimale : 004 Informatique Résumé : Résumé
Le besoin du monde actuel d’utiliser les technologies sans fil pour extraire des informations
à partir des milieux très sensibles, hostiles et inaccessibles a fait appel au réseau de
capteurs. Cependant, la miniaturisation des capteurs nécessite des mécanismes de conservation
d’énergie de ces derniers afin d’étendre la durée de vie du réseau. Beaucoup de travaux
ont été faites pour minimiser la consommation inutile d’énergie, en se focalisant sur les deux
couches MAC et Réseau. Nous avons proposé deux protocoles de routage qui présentent
des versions améliorées de Gossiping et Leach où la probabilité qu’un capteur voisin est
choisi selon l’approche d’optimisation par colonie de fourmis afin d’acheminer la donnée.
Les résultats de simulation ont montré une amélioration très appréciable en termes d’énergie
moyenne restante, de durée de vie et de temps de réponse.
Mots clés :réseaux de capteurs sans fil, routage, simulation à événements discrets, performance,
optimisation par colonie de fourmis (ACO).Note de contenu : Table des matières i
Liste des figures vi
Liste des tableaux vii
1 Introduction générale 1
1.1 Contexte général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation et problématique . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Contribution et structure du mémoire . . . . . . . . . . . . . . . . . 3
2 Généralités sur les réseaux de capteurs 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Architecture d’un noeud capteur . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Architecture Matérielle . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Architecture logicielle . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Architecture de communication d’un RCSF . . . . . . . . . . . . . 7
2.4 Domaines d’application des RCSFs . . . . . . . . . . . . . . . . . . 7
2.5 Caractéristiques des réseaux de capteurs . . . . . . . . . . . . . . . 9
2.6 Contraintes de conception des RCSF . . . . . . . . . . . . . . . . . 10
2.7 Pile protocolaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.8 Consommation d’énergie dans les RCSF . . . . . . . . . . . . . . 12
2.9 Comparaison entre les réseaux WSN et Ad Hoc . . . . . . . . . . 14
2.10 Différentes problématiques dans les réseaux de capteurs . . . . 14
2.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Le routage dans les réseaux de capteurs 16
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Facteurs de conception des protocoles de routage en RCSF . . 17
3.3 Contraintes de routage dans les réseaux de capteurs sans fil . . 18
3.4 Classes des protocoles de routage dédiés aux RCSF . . . . . . . 18
3.4.1 Classes principales des protocoles de routage . . . . . . . 19
3.4.1.1 Routage plat . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.1.2 Routage hiérarchique . . . . . . . . . . . . . . . . . . . 20
3.4.1.3 Routage géographique . . . . . . . . . . . . . . . . . . . 22
3.4.2 Sous-classes des protocoles de routage . . . . . . . . . . . 22
3.4.2.1 Routage basé sur les chemins multiples . . . . . . . . . . 22
3.4.2.2 Routage basé sur les requêtes . . . . . . . . . . . . . . . 23
3.4.2.3 Protocoles basés sur la négociation . . . . . . . . . . . . 23
3.4.2.4 Routage basé sur la qualité de service . . . . . . . . . . . 23
3.5 Routage avec prise en compte de l’énergie . . . . . . . . . . . . . 24
3.5.1 Routage avec réduction de données . . . . . . . . . . . . . . 24
3.5.1.1 Architectures à base de clusters . . . . . . . . . . . . . . 24
3.5.1.2 Architectures à base de chaînes . . . . . . . . . . . . . . 25
3.5.1.3 Architectures à base d’arbres . . . . . . . . . . . . . . . 25
3.6 Routage basé sur le fonctionnement des colonies de fourmis . . 26
3.6.1 Aspect biologique : les fourmis réelles . . . . . . . . . . . . 27
3.6.2 Aspect informatique : l’agent fourmi . . . . . . . . . . . . . 27
3.6.3 L’algorithme ACO : Simple ant colony optimization metaheuristic
algorithm . . . . . . . . . . . . . . . . . . . . . . . . 28
3.7 Approche ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 Proposition et conception du système 31
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 La proposition : Ant-pro . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Stratégies proposées . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.1 Première stratégie : Ant-pro . . . . . . . . . . . . . . . . . . 33
4.3.2 Deuxième stratégie : Ant-pro à 4 sauts . . . . . . . . . . . 33
4.4 Première partie : Amélioration de Gossiping . . . . . . . . . . . . 34
4.4.1 Etude critique des protocoles de routage linéaires basés
sur GOSSIPING . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.4.2 Les motivations de la proposition . . . . . . . . . . . . . . . 35
4.4.3 Proposition du protocole Ant-Gossiping . . . . . . . . . . 35
4.5 Deuxième partie : Amélioration de LEACH . . . . . . . . . . . . 37
4.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5.2 Etude critique du protocole LEACH . . . . . . . . . . . . . 38
4.5.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5.4 Proposition du protocole Ant-LEACH . . . . . . . . . . . . 39
4.5.4.1 Le fonctionnement de notre protocole . . . . . . . . . . . 40
4.5.4.2 Les principales différences entre Ant-LEACH et LEACH 40
4.6 Concepts de modélisation et techniques d’évaluation de performance . . . . 42
4.6.1 La modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6.2 Concepts d’évaluation de performance des réseaux . . . . 42
4.7 Techniques d’évaluation de performances . . . . . . . . . . . . . . 42
4.7.1 La simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.8 La conception du système . . . . . . . . . . . . . . . . . . . . . . . . 43
4.8.1 Le but de l’application . . . . . . . . . . . . . . . . . . . . . . 43
4.8.2 Modélisation du système . . . . . . . . . . . . . . . . . . . . 44
4.8.3 Description du modèle . . . . . . . . . . . . . . . . . . . . . . 45
4.8.3.1 Algorithme de simulation . . . . . . . . . . . . . . . . . 46
4.8.3.2 Les métriques de performance . . . . . . . . . . . . . . 46
4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 Simulation et interprétation des résultats 49
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Aperçu sur les simulateurs des réseaux de capteurs . . . . . . . . 49
5.3 Le choix de Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 Les étapes de réalisation du simulateur . . . . . . . . . . . . . . . 50
5.4.1 Déploiement du réseau . . . . . . . . . . . . . . . . . . . . . 50
5.4.2 Création de l’échéancier . . . . . . . . . . . . . . . . . . . . . 51
5.4.3 Découverte des voisins . . . . . . . . . . . . . . . . . . . . . 51
5.4.4 Application des algorithmes de routages . . . . . . . . . . 51
5.4.5 Affichages des résultats de la simulation . . . . . . . . . . 52
5.4.5.1 Les paramètres de simulation . . . . . . . . . . . . . . . 52
5.4.5.2 Comparaison entre les protcoles : Gossiping, Ant-Gossiping
et Ant-Gossping à 4 sauts . . . . . . . . . . . . . . . . . 53
5.4.5.3 Comparaison entre les protcoles : LEACH et Ant-LEACH 56
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Conclusion et perspectives 59
Annexe A 61
Bibliographie 64
ivCôte titre : MAI/0001 En ligne : https://drive.google.com/file/d/1UKovt_IaQWPpLeB6c00wuun0Tnv_ROvB/view?usp=shari [...] Format de la ressource électronique : Optimisation des protocoles de routage dans les réseaux de capteurs avec l’approche de colonie de fourmis [texte imprimé] / BOUNOUNI, Mahdi ; Abdelhafid Benaouda, Directeur de thèse . - [S.l.] : Setif:UFA, 2012 . - 1 vol (68 f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : réseaux de capteurs sans fil,routage,simulation à événements discrets,performance,optimisation par colonie de fourmis (ACO). Index. décimale : 004 Informatique Résumé : Résumé
Le besoin du monde actuel d’utiliser les technologies sans fil pour extraire des informations
à partir des milieux très sensibles, hostiles et inaccessibles a fait appel au réseau de
capteurs. Cependant, la miniaturisation des capteurs nécessite des mécanismes de conservation
d’énergie de ces derniers afin d’étendre la durée de vie du réseau. Beaucoup de travaux
ont été faites pour minimiser la consommation inutile d’énergie, en se focalisant sur les deux
couches MAC et Réseau. Nous avons proposé deux protocoles de routage qui présentent
des versions améliorées de Gossiping et Leach où la probabilité qu’un capteur voisin est
choisi selon l’approche d’optimisation par colonie de fourmis afin d’acheminer la donnée.
Les résultats de simulation ont montré une amélioration très appréciable en termes d’énergie
moyenne restante, de durée de vie et de temps de réponse.
Mots clés :réseaux de capteurs sans fil, routage, simulation à événements discrets, performance,
optimisation par colonie de fourmis (ACO).Note de contenu : Table des matières i
Liste des figures vi
Liste des tableaux vii
1 Introduction générale 1
1.1 Contexte général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation et problématique . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Contribution et structure du mémoire . . . . . . . . . . . . . . . . . 3
2 Généralités sur les réseaux de capteurs 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Architecture d’un noeud capteur . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Architecture Matérielle . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Architecture logicielle . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Architecture de communication d’un RCSF . . . . . . . . . . . . . 7
2.4 Domaines d’application des RCSFs . . . . . . . . . . . . . . . . . . 7
2.5 Caractéristiques des réseaux de capteurs . . . . . . . . . . . . . . . 9
2.6 Contraintes de conception des RCSF . . . . . . . . . . . . . . . . . 10
2.7 Pile protocolaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.8 Consommation d’énergie dans les RCSF . . . . . . . . . . . . . . 12
2.9 Comparaison entre les réseaux WSN et Ad Hoc . . . . . . . . . . 14
2.10 Différentes problématiques dans les réseaux de capteurs . . . . 14
2.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Le routage dans les réseaux de capteurs 16
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Facteurs de conception des protocoles de routage en RCSF . . 17
3.3 Contraintes de routage dans les réseaux de capteurs sans fil . . 18
3.4 Classes des protocoles de routage dédiés aux RCSF . . . . . . . 18
3.4.1 Classes principales des protocoles de routage . . . . . . . 19
3.4.1.1 Routage plat . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.1.2 Routage hiérarchique . . . . . . . . . . . . . . . . . . . 20
3.4.1.3 Routage géographique . . . . . . . . . . . . . . . . . . . 22
3.4.2 Sous-classes des protocoles de routage . . . . . . . . . . . 22
3.4.2.1 Routage basé sur les chemins multiples . . . . . . . . . . 22
3.4.2.2 Routage basé sur les requêtes . . . . . . . . . . . . . . . 23
3.4.2.3 Protocoles basés sur la négociation . . . . . . . . . . . . 23
3.4.2.4 Routage basé sur la qualité de service . . . . . . . . . . . 23
3.5 Routage avec prise en compte de l’énergie . . . . . . . . . . . . . 24
3.5.1 Routage avec réduction de données . . . . . . . . . . . . . . 24
3.5.1.1 Architectures à base de clusters . . . . . . . . . . . . . . 24
3.5.1.2 Architectures à base de chaînes . . . . . . . . . . . . . . 25
3.5.1.3 Architectures à base d’arbres . . . . . . . . . . . . . . . 25
3.6 Routage basé sur le fonctionnement des colonies de fourmis . . 26
3.6.1 Aspect biologique : les fourmis réelles . . . . . . . . . . . . 27
3.6.2 Aspect informatique : l’agent fourmi . . . . . . . . . . . . . 27
3.6.3 L’algorithme ACO : Simple ant colony optimization metaheuristic
algorithm . . . . . . . . . . . . . . . . . . . . . . . . 28
3.7 Approche ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 Proposition et conception du système 31
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 La proposition : Ant-pro . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Stratégies proposées . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.1 Première stratégie : Ant-pro . . . . . . . . . . . . . . . . . . 33
4.3.2 Deuxième stratégie : Ant-pro à 4 sauts . . . . . . . . . . . 33
4.4 Première partie : Amélioration de Gossiping . . . . . . . . . . . . 34
4.4.1 Etude critique des protocoles de routage linéaires basés
sur GOSSIPING . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.4.2 Les motivations de la proposition . . . . . . . . . . . . . . . 35
4.4.3 Proposition du protocole Ant-Gossiping . . . . . . . . . . 35
4.5 Deuxième partie : Amélioration de LEACH . . . . . . . . . . . . 37
4.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5.2 Etude critique du protocole LEACH . . . . . . . . . . . . . 38
4.5.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5.4 Proposition du protocole Ant-LEACH . . . . . . . . . . . . 39
4.5.4.1 Le fonctionnement de notre protocole . . . . . . . . . . . 40
4.5.4.2 Les principales différences entre Ant-LEACH et LEACH 40
4.6 Concepts de modélisation et techniques d’évaluation de performance . . . . 42
4.6.1 La modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6.2 Concepts d’évaluation de performance des réseaux . . . . 42
4.7 Techniques d’évaluation de performances . . . . . . . . . . . . . . 42
4.7.1 La simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.8 La conception du système . . . . . . . . . . . . . . . . . . . . . . . . 43
4.8.1 Le but de l’application . . . . . . . . . . . . . . . . . . . . . . 43
4.8.2 Modélisation du système . . . . . . . . . . . . . . . . . . . . 44
4.8.3 Description du modèle . . . . . . . . . . . . . . . . . . . . . . 45
4.8.3.1 Algorithme de simulation . . . . . . . . . . . . . . . . . 46
4.8.3.2 Les métriques de performance . . . . . . . . . . . . . . 46
4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 Simulation et interprétation des résultats 49
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Aperçu sur les simulateurs des réseaux de capteurs . . . . . . . . 49
5.3 Le choix de Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 Les étapes de réalisation du simulateur . . . . . . . . . . . . . . . 50
5.4.1 Déploiement du réseau . . . . . . . . . . . . . . . . . . . . . 50
5.4.2 Création de l’échéancier . . . . . . . . . . . . . . . . . . . . . 51
5.4.3 Découverte des voisins . . . . . . . . . . . . . . . . . . . . . 51
5.4.4 Application des algorithmes de routages . . . . . . . . . . 51
5.4.5 Affichages des résultats de la simulation . . . . . . . . . . 52
5.4.5.1 Les paramètres de simulation . . . . . . . . . . . . . . . 52
5.4.5.2 Comparaison entre les protcoles : Gossiping, Ant-Gossiping
et Ant-Gossping à 4 sauts . . . . . . . . . . . . . . . . . 53
5.4.5.3 Comparaison entre les protcoles : LEACH et Ant-LEACH 56
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Conclusion et perspectives 59
Annexe A 61
Bibliographie 64
ivCôte titre : MAI/0001 En ligne : https://drive.google.com/file/d/1UKovt_IaQWPpLeB6c00wuun0Tnv_ROvB/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0001 MAI/0001 Mémoire Bibliothéque des sciences Français Disponible
DisponiblePermalinkOptimisation de la recherche d'information sur le web par les techniques vectorielles / Djessas, ouissem
PermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkUn outil de transformation automatique d’un réseau de Petri vers la logique de réécriture / Messous ,Randa
![]()
PermalinkOutils de mesure de pression et d’échantillonnage: Cas des réservoirs du Triasique (Bassin d’Oued Mya) / Siouani .Ali abdo Elmounaime
![]()
PermalinkUn package de méthodes numériques pour résoudre des équations aux dérivées partielles / Amina Atoui
![]()
PermalinkPaquet d'ondes gaussiennes accompagnant les états cohérents pour l'oscillateur harmonique inversé / Ishak Bouguerche
![]()
PermalinkPermalinkParadigmes bio-inspirés pour la modélisation de la mobilité de sink dans les réseaux de capteurs sans fil / Benzine,Ahmed Redha.
![]()
PermalinkPermalinkPermalinkParticule relativiste avec Spin dans un champ externe et Èquation classique dÃÈvolution de Spin. / Oussama Bouchelaghem
![]()
PermalinkPartitionnement de données quantitatives par les techniques de la fouille de données / Khaireddine Latreche
![]()
PermalinkPermalinkPermalinkLes Phénomènes de conduction dans une structure semi-conductrice à hétérojonction / Abdelkrim Benabbas
PermalinkPiegeage d'especes polluantes inorganiques dans la porosite des sba-15 et la matrice des hdLs / Kharmouche Hanadi
PermalinkPermalinkPermalinkPermalinkLes plantes et leurs métabolites secondaires comme ersatz des antibiotiques ? Études in vitro et in silico / Gift Mathats,Bwalya
![]()
PermalinkPermalinkPermalinkPlateforme sémantique Cloud Computing pour la gestion des applications ERP sensibles au contexte / Reffad,Hamza
![]()
PermalinkPermalinkPermalinkPermalinkUn portail web selon une architecture orientée Web Service pour le suivi des appels d’offres / Cherabite, Kamel
![]()
PermalinkPermalinkPermalinkPermalinkPermalink