University Sétif 1 FERHAT ABBAS Faculty of Sciences
Catégories
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Clustering algorithm using K-means and Cuckoo Search Type de document : texte imprimé Auteurs : LEGRIB, Med El-Amine ; KAMEL, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (49f.) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Cluster,clustering data,k-means,cuckoo search,metaheuristics,datamining,
Knowledge Discovery.Index. décimale : 004 Informatique Résumé : Abstract
Cluster analysis comprises a range of methods for classifying multivariate data into
subgroups. By organizing multivariate data into such subgroups, clustering can help
reveal the characteristics of any structure or patterns present. These techniques have
proven useful in a wide range of areas such as medicine, psychology, market research
and bioinformatics. in this thesis we will take a look on many clustering algorithms
and implement our solution for clustering data using k-means and cuckoo search algorithms evaluate the result of our work using the benchmark of various dataset proposed
in UC Irvine Machine Learning Repository ,result showed a good k-means algorithm
initialization
Note de contenu : Contents
Dedication 1
abstract 2
Introduction 6
1 DATA Mining 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Definition DATA MINIG . . . . . . . . . . . . . . . . . . . 8
1.3.2 Definition KNOWLEDGE Discovery in Databases . . . . . . 9
1.3.3 Definition machine learning . . . . . . . . . . . . . . . . . . 9
1.3.3.1 Leaning style . . . . . . . . . . . . . . . . . . . . 10
1.3.3.1.1 Supervised Learning: . . . . . . . . . . . 10
1.3.3.1.2 Unsupervised Learning . . . . . . . . . . 10
1.3.3.1.3 Semi-Supervised Learning . . . . . . . . 10
1.3.3.1.4 Reinforcement Learning: . . . . . . . . . 10
1.4 data mining tasks [Kan11] . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Predictive Method . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Description Method . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Types of Data Mining System . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 Classification of data mining systems according to the type of
data source mined . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 Classification of data mining systems according to the data model 11
1.5.3 Classification of data mining systems according to the kind of
knowledge discovered . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Classification of data mining systems according to mining techniques used . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Data Mining in the real world [UGP96] . . . . . . . . . . . . . . . . 12
1.6.1 Finance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.2 Telecommunication . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.3 Biological Data Analysis . . . . . . . . . . . . . . . . . . . . 12
1.6.4 Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Clustering and classification . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1.1 The decision tree . . . . . . . . . . . . . . . . . . . 13
1.7.2 cluster and Clustering . . . . . . . . . . . . . . . . . . . . . 13
1.7.3 Reasons of clustering . . . . . . . . . . . . . . . . . . . . . . 13
1.7.4 application of cluster analysis . . . . . . . . . . . . . . . . . 14
1.7.4.1 market Research . . . . . . . . . . . . . . . . . . 14
1.7.4.2 Astronomy . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.3 psychology . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.4 Weather classification . . . . . . . . . . . . . . . . 14
1.7.4.5 Archeology . . . . . . . . . . . . . . . . . . . . . 14
1.7.5 Data type in cluster analysis . . . . . . . . . . . . . . . . . . 14
1.7.5.1 Clustering categorical Data . . . . . . . . . . . . . 14
1.7.5.2 Clustering Text Data . . . . . . . . . . . . . . . . 15
1.7.5.3 Clustring multimedia data . . . . . . . . . . . . . 15
1.7.5.4 Clustering time-series data . . . . . . . . . . . . . 15
1.7.6 Distances and similarities . . . . . . . . . . . . . . . . . . . 16
1.7.7 Clustering algorithms . . . . . . . . . . . . . . . . . . . . . 16
1.7.7.1 The hierarchical clustering . . . . . . . . . . . . . 16
1.7.7.1.1 Agglomerative and divisive methods . . . 17
1.7.7.1.2 BIRCH ALGORITHEM [TzRr96] . . . . 18
1.7.7.2 The partitional clustering . . . . . . . . . . . . . . 19
1.7.7.2.1 The Heuristics methods . . . . . . . . . . 20
1.7.7.2.1.1 K-means . . . . . . . . . . . . . . 20
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 MetaHeuristics 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Deintion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Metaheuristics for Clustering . . . . . . . . . . . . . . . . . . . . . . 23
2.5.1 Clustering by evolutionary algorithms . . . . . . . . . . . . . 23
2.5.2 Clustering by artificial ants . . . . . . . . . . . . . . . . . . . 26
2.5.3 Clustering particle swarm . . . . . . . . . . . . . . . . . . . 27
2.5.4 Clustering by artificial immune system . . . . . . . . . . . . 28
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Meta-heuristics+K-means 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 K-Means and firefly . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 K-Means and PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Integrating Nature-inspired Optimization Algorithms to K-means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Firefly and k-means in image processing . . . . . . . . . . . . . . . . 36
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4 implementation 38
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.1 Iris Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.2 Wine Data Set . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.2.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.3 Poker Hand Data Set . . . . . . . . . . . . . . . . . . . . . . 39
4.3.4 datasets uses . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Algorithm k-means/cuckoo-search . . . . . . . . . . . . . . . . . . . 40
4.5 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.1 Hardware used . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.2 Software used . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.3 Software manual guide . . . . . . . . . . . . . . . . . . . . . 41
4.5.3.1 Cluster validity . . . . . . . . . . . . . . . . . . . 42
4.5.3.2 Clusters . . . . . . . . . . . . . . . . . . . . . . . 42
4.5.4 Screen shot . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6 Results and evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.1 Compactness intra-cluster . . . . . . . . . . . . . . . . . . . 44
4.6.2 Separation inter-cluster . . . . . . . . . . . . . . . . . . . . . 44
4.6.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.7 Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.8 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
General conclusion 46
References 49Côte titre : MAI/0080 En ligne : https://drive.google.com/file/d/1y8oDElqZXLYljFg0uiN0Fl4Et9sDZYJ4/view?usp=shari [...] Format de la ressource électronique : Clustering algorithm using K-means and Cuckoo Search [texte imprimé] / LEGRIB, Med El-Amine ; KAMEL, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (49f.) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Cluster,clustering data,k-means,cuckoo search,metaheuristics,datamining,
Knowledge Discovery.Index. décimale : 004 Informatique Résumé : Abstract
Cluster analysis comprises a range of methods for classifying multivariate data into
subgroups. By organizing multivariate data into such subgroups, clustering can help
reveal the characteristics of any structure or patterns present. These techniques have
proven useful in a wide range of areas such as medicine, psychology, market research
and bioinformatics. in this thesis we will take a look on many clustering algorithms
and implement our solution for clustering data using k-means and cuckoo search algorithms evaluate the result of our work using the benchmark of various dataset proposed
in UC Irvine Machine Learning Repository ,result showed a good k-means algorithm
initialization
Note de contenu : Contents
Dedication 1
abstract 2
Introduction 6
1 DATA Mining 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Definition DATA MINIG . . . . . . . . . . . . . . . . . . . 8
1.3.2 Definition KNOWLEDGE Discovery in Databases . . . . . . 9
1.3.3 Definition machine learning . . . . . . . . . . . . . . . . . . 9
1.3.3.1 Leaning style . . . . . . . . . . . . . . . . . . . . 10
1.3.3.1.1 Supervised Learning: . . . . . . . . . . . 10
1.3.3.1.2 Unsupervised Learning . . . . . . . . . . 10
1.3.3.1.3 Semi-Supervised Learning . . . . . . . . 10
1.3.3.1.4 Reinforcement Learning: . . . . . . . . . 10
1.4 data mining tasks [Kan11] . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Predictive Method . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Description Method . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Types of Data Mining System . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 Classification of data mining systems according to the type of
data source mined . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 Classification of data mining systems according to the data model 11
1.5.3 Classification of data mining systems according to the kind of
knowledge discovered . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Classification of data mining systems according to mining techniques used . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Data Mining in the real world [UGP96] . . . . . . . . . . . . . . . . 12
1.6.1 Finance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.2 Telecommunication . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.3 Biological Data Analysis . . . . . . . . . . . . . . . . . . . . 12
1.6.4 Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Clustering and classification . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1.1 The decision tree . . . . . . . . . . . . . . . . . . . 13
1.7.2 cluster and Clustering . . . . . . . . . . . . . . . . . . . . . 13
1.7.3 Reasons of clustering . . . . . . . . . . . . . . . . . . . . . . 13
1.7.4 application of cluster analysis . . . . . . . . . . . . . . . . . 14
1.7.4.1 market Research . . . . . . . . . . . . . . . . . . 14
1.7.4.2 Astronomy . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.3 psychology . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.4 Weather classification . . . . . . . . . . . . . . . . 14
1.7.4.5 Archeology . . . . . . . . . . . . . . . . . . . . . 14
1.7.5 Data type in cluster analysis . . . . . . . . . . . . . . . . . . 14
1.7.5.1 Clustering categorical Data . . . . . . . . . . . . . 14
1.7.5.2 Clustering Text Data . . . . . . . . . . . . . . . . 15
1.7.5.3 Clustring multimedia data . . . . . . . . . . . . . 15
1.7.5.4 Clustering time-series data . . . . . . . . . . . . . 15
1.7.6 Distances and similarities . . . . . . . . . . . . . . . . . . . 16
1.7.7 Clustering algorithms . . . . . . . . . . . . . . . . . . . . . 16
1.7.7.1 The hierarchical clustering . . . . . . . . . . . . . 16
1.7.7.1.1 Agglomerative and divisive methods . . . 17
1.7.7.1.2 BIRCH ALGORITHEM [TzRr96] . . . . 18
1.7.7.2 The partitional clustering . . . . . . . . . . . . . . 19
1.7.7.2.1 The Heuristics methods . . . . . . . . . . 20
1.7.7.2.1.1 K-means . . . . . . . . . . . . . . 20
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 MetaHeuristics 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Deintion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Metaheuristics for Clustering . . . . . . . . . . . . . . . . . . . . . . 23
2.5.1 Clustering by evolutionary algorithms . . . . . . . . . . . . . 23
2.5.2 Clustering by artificial ants . . . . . . . . . . . . . . . . . . . 26
2.5.3 Clustering particle swarm . . . . . . . . . . . . . . . . . . . 27
2.5.4 Clustering by artificial immune system . . . . . . . . . . . . 28
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Meta-heuristics+K-means 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 K-Means and firefly . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 K-Means and PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Integrating Nature-inspired Optimization Algorithms to K-means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Firefly and k-means in image processing . . . . . . . . . . . . . . . . 36
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4 implementation 38
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.1 Iris Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.2 Wine Data Set . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.2.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.3 Poker Hand Data Set . . . . . . . . . . . . . . . . . . . . . . 39
4.3.4 datasets uses . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Algorithm k-means/cuckoo-search . . . . . . . . . . . . . . . . . . . 40
4.5 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.1 Hardware used . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.2 Software used . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.3 Software manual guide . . . . . . . . . . . . . . . . . . . . . 41
4.5.3.1 Cluster validity . . . . . . . . . . . . . . . . . . . 42
4.5.3.2 Clusters . . . . . . . . . . . . . . . . . . . . . . . 42
4.5.4 Screen shot . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6 Results and evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.1 Compactness intra-cluster . . . . . . . . . . . . . . . . . . . 44
4.6.2 Separation inter-cluster . . . . . . . . . . . . . . . . . . . . . 44
4.6.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.7 Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.8 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
General conclusion 46
References 49Côte titre : MAI/0080 En ligne : https://drive.google.com/file/d/1y8oDElqZXLYljFg0uiN0Fl4Et9sDZYJ4/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0080 MAI/0080 Mémoire Bibliothéque des sciences Anglais Disponible
DisponibleClustering basé sur les algorithmes de différence de profondeur, Kmeans et Q-Learning dans les WSNs-IoT / Djamila Maroua Chitri
Titre : Clustering basé sur les algorithmes de différence de profondeur, Kmeans et Q-Learning dans les WSNs-IoT Type de document : texte imprimé Auteurs : Djamila Maroua Chitri, Auteur ; Selma Boufenik ; Zouaoui Zibouda Aliouat Née, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2023 Importance : 1 vol (51 f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : L’internet des objets
Les réseaux de capteurs sans fil
Apprentissage automatique
RegroupementIndex. décimale : 004 - Informatique Résumé : l’intégration de l’Internet des Objects (IdO) dans les Réseaux de Capteurs Sans Fil
(RCSFs) pose des défis spécifiques liés à la gestion des ressources limitées des capteurs,
tels que l’énergie, la mémoire et la puissance de calcul. Pour résoudre ces problèmes,
l’utilisation de techniques de clustering dans les RCSFs s’avère être une solution efficace.
Le clustering dans les RCSFs est une méthode importante pour regrouper les noeuds
capteurs en groupes afin de faciliter la communication et de réduire la consommation
d’énergie. Cependant, la détermination du nombre optimal de clusters est un défi
majeur dans la division en cluster pour les RCSFs. Les méthodes de détection de
cluster basées sur Machine Learning (ML), telles que la méthode du coude, la méthode de silhouette et la statistique de l’écart ont été utilisé avec succès, cependant,
elles présentent des limitations dans la gestion de données complexes avec des clusters
non convexes. Des approches plus récentes, telles que la méthode de Différence de
Profondeur (DdP), ont été proposées pour surmonter ces limitations. Cette méthode
introduite avec l’algorithme de clustering k-means peut construite un routage basé sur
cluster efficace pour les RCSFs.
Le nœud Cluster Head (CH), joue un rôle essentiel dans l’organisation, la gestion
des données, le routage et la conservation de l’énergie dans les RCSFs basé sur cluster.
Un Super-Head peut être selectionné en utilisant l’algorithme d’apprentissage par renforcement Q-learning pour offrir une solution prometteuse pour résoudre le problème
de consommation excessive d’énergie par le nœud CH dans les réseaux de capteurs,
prolongeant ainsi la durée de vie du réseau = The integration of Internet Of things (IoT) into Wireless Sensor Networks (WSNs)
also poses specific challenges. One of the main problems is related to managing the
limited resources of sensors, such as energy, memory, and computational power. To
address these issues, the use of clustering techniques in WSNs proves to be an effective
solution.
Clustering in WSNs is an important method for grouping sensor nodes into clusters
to facilitate communication and reduce energy consumption. However, determining the
optimal number of clusters is a major challenge in cluster formation for WSNs. Machine
learning-based cluster detection methods, such as the elbow method, silhouette method,
and gap statistic, have been successfully used. However, they have limitations in
handling complex data with non-convex clusters. More recent approaches, such as the
Depth Difference (DeD) method, have been proposed to overcome these limitations.
This method can be combined with the k-means clustering algorithm to construct an
efficient cluster-based routing for WSNs.
The Cluster Head (CH) node, plays an essential role in organization, data management, routing, and energy conservation in cluster-based RCSFs. A Super-Head can
be selected using the Q-learning reinforcement learning algorithm to offer a promising
solution to the problem of excessive energy consumption by the CH node in sensor
networks, thus extending the network lifetime.
Côte titre : MAI/0771 En ligne : https://drive.google.com/file/d/1ygbPCA_GRwEYUdG4HYtfL1bSkhGgI0-G/view?usp=drive [...] Format de la ressource électronique : Clustering basé sur les algorithmes de différence de profondeur, Kmeans et Q-Learning dans les WSNs-IoT [texte imprimé] / Djamila Maroua Chitri, Auteur ; Selma Boufenik ; Zouaoui Zibouda Aliouat Née, Directeur de thèse . - [S.l.] : Sétif:UFS, 2023 . - 1 vol (51 f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : L’internet des objets
Les réseaux de capteurs sans fil
Apprentissage automatique
RegroupementIndex. décimale : 004 - Informatique Résumé : l’intégration de l’Internet des Objects (IdO) dans les Réseaux de Capteurs Sans Fil
(RCSFs) pose des défis spécifiques liés à la gestion des ressources limitées des capteurs,
tels que l’énergie, la mémoire et la puissance de calcul. Pour résoudre ces problèmes,
l’utilisation de techniques de clustering dans les RCSFs s’avère être une solution efficace.
Le clustering dans les RCSFs est une méthode importante pour regrouper les noeuds
capteurs en groupes afin de faciliter la communication et de réduire la consommation
d’énergie. Cependant, la détermination du nombre optimal de clusters est un défi
majeur dans la division en cluster pour les RCSFs. Les méthodes de détection de
cluster basées sur Machine Learning (ML), telles que la méthode du coude, la méthode de silhouette et la statistique de l’écart ont été utilisé avec succès, cependant,
elles présentent des limitations dans la gestion de données complexes avec des clusters
non convexes. Des approches plus récentes, telles que la méthode de Différence de
Profondeur (DdP), ont été proposées pour surmonter ces limitations. Cette méthode
introduite avec l’algorithme de clustering k-means peut construite un routage basé sur
cluster efficace pour les RCSFs.
Le nœud Cluster Head (CH), joue un rôle essentiel dans l’organisation, la gestion
des données, le routage et la conservation de l’énergie dans les RCSFs basé sur cluster.
Un Super-Head peut être selectionné en utilisant l’algorithme d’apprentissage par renforcement Q-learning pour offrir une solution prometteuse pour résoudre le problème
de consommation excessive d’énergie par le nœud CH dans les réseaux de capteurs,
prolongeant ainsi la durée de vie du réseau = The integration of Internet Of things (IoT) into Wireless Sensor Networks (WSNs)
also poses specific challenges. One of the main problems is related to managing the
limited resources of sensors, such as energy, memory, and computational power. To
address these issues, the use of clustering techniques in WSNs proves to be an effective
solution.
Clustering in WSNs is an important method for grouping sensor nodes into clusters
to facilitate communication and reduce energy consumption. However, determining the
optimal number of clusters is a major challenge in cluster formation for WSNs. Machine
learning-based cluster detection methods, such as the elbow method, silhouette method,
and gap statistic, have been successfully used. However, they have limitations in
handling complex data with non-convex clusters. More recent approaches, such as the
Depth Difference (DeD) method, have been proposed to overcome these limitations.
This method can be combined with the k-means clustering algorithm to construct an
efficient cluster-based routing for WSNs.
The Cluster Head (CH) node, plays an essential role in organization, data management, routing, and energy conservation in cluster-based RCSFs. A Super-Head can
be selected using the Q-learning reinforcement learning algorithm to offer a promising
solution to the problem of excessive energy consumption by the CH node in sensor
networks, thus extending the network lifetime.
Côte titre : MAI/0771 En ligne : https://drive.google.com/file/d/1ygbPCA_GRwEYUdG4HYtfL1bSkhGgI0-G/view?usp=drive [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0771 MAI/0771 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Clustering basé sur l'intelligence en Essaim dans les réseaux de capteurs sans fil Type de document : texte imprimé Auteurs : Ghéraf,amira ; Djamila Mechta, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (61f.) 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
RCSF
AFSA
protocole LEACH-C
clustering hiérarchique
Cluster headIndex. décimale : 004 Informatique Résumé : Résumé:
Le Clustering est l'une des techniques les plus efficaces pour conserver l'énergie dans les
réseaux de capteurs sans fil. Son objectif principal est d’organiser le réseau en plusieurs
groupes appelés clusters, et sélectionner un chef pour Chaque groupe nommé cluster head
(CH) responsable d’agréger les données de ses membres pour les envoyer à la station de
base (SB). Dans ce travail nous avons étudié le problème de la consommation d’énergie et
le prolongement de la durée de vie dans les RCSFs afin de proposer un nouveau protocole
de clustering hiérarchique C-AFSA basé sur les comportements :swarm,prey ,follow
d’AFSA (artifitial fish swarm algorithm) pour la sélection des CHs et formation des
clusters. Les performances de notre algorithme sont évaluées et comparées avec le
protocole standard LEACH-C à travers une simulation à l’aide du simulateur réseau NS2.Note de contenu : Table des matières
Introduction générale………………………………………………………………….. 1
Organisation du mémoire……………………………………………………………... 2
Chapitre1 : clustering basé sur les méthodes bio-inspirés……………………………... 3
1.1.Introduction……………………………………………………………………... 4
1.2.Algorithmes basés sur PSO……………………………………………………... 5
1.2.1. PSO-HC…………………………………………………………………. 5
1.2.2. KPSO Hybrid protocol………………………………………………….. 7
1.3. Algorithme basé sur les réseaux neurone………………………………………. 8
1.3.1. CNN-LEACH……………………………………………………………. 8
1.4. Algorithme basé sur la Pollinisation ………………………………………….. 8
1.4.1.PBO………………………………………………………………………. 8
1.5. Algorithme basé sur essaim de poisson………………………………………... 10
1.5.1. AFSA……………………………………………………………………. 10
1.6. Algorithmes génétiques………………………………………………………… 13
1.6.1. GA……………………………………………………………………… 13
1.6.2. CGC (centralized genetic-based clustering)…..……………………….. 15
1.7. Conclusion……………………………………………………………………… 20
Chapitre 2 : protocole proposé C-AFSA………………………………………………. 21
2.1. Introduction…………………………………………………………………….. 22
2.2 LEACH_C………………………………………………………………………. 22
2.2.1. Phase d’initialisation…………………………………………………… 22
2.2.2. Phase de transmission………………………………………………….. 23
2.3. Généralités sur AFSA (artificial fish swarm algorithm)……………………….. 24
2.4. Caractéristiques du protocole proposé…………………………………………. 25
2.4.1. Les paramètre du protocole……………………………………………. 25
2.4.2. Les propriétés du modèle du réseau…………………………………………………. 25
2.5. Description générale du protocole proposé……………………………………. 26
2.6. Description détaillée du protocole proposé……………………………………. 27
2.6.1 Division virtuelle du réseau…………………………………………….. 27
2.6.2 Election des CHs initiaux………………………………………………. 28
2.6.3 Application des comportements d’AFSA dans la sélection des CHs…… 29
2.6.3.1- comportement de proie (Prey) :prey_ch ………………………... 30
2.6.3.2- comportement d’essaim (swarm) :swarm_ch…………………… 31
2.6.3.3- comportement de suivie (follow) : follow_ch…………………… 32
2.6.4. La formation des clusters en utilisant les comportements AFSA………. 34
2.6.4.1 .Clutering initial…………………………………………………. 35
2.6.4.2. Prey clustering (prey_clust)…………………………………….. 35
2.6.4.3.swarm clustering (swarm_clust)………………………………… 36
2.6.4.4. Follow clustering (follow_clust)……………………………….. 38
2.6.5. La fonction objectif (Fitness)…………………………………………... 39
2.7. Le modèle d’énergie…………………………………………………………... 40
2.8. La transmission des données………………………………………………….. 40
2.9. Conclusion…………………………………………………………………….. 41
Chapitre 3 : mise en œuvre……………………………………………………………. 42
3.1. Introduction…………………………………………………………………………………………………… 43
3.2. L’environnement de développement…………………………………………... 43
3.3.1. NS2……………………………………………………………………… 43
3.2.2 Intégration des packages de LEACH…………………………………….. 43
3.3. Simulation……………………………………………………………………… 43
3.3.1. Paramètre du protocole………………………………………………….. 43
3.3.2. Résultats de la simulation……………………………………………….. 44
3.4. Les métriques de performance…………………………………………………. 45
3.5 Partie 1 : comparaison dans un réseau de petite taille………………………….. 45
3.5.1 Paramètres du réseau…………………………………………………………………………… 45
3.5.2 Comparaison de l’énergie consommée…………………………………... 46
3.5.3 Comparaison des données reçues par la SB…………………………………………… 46
3.5.4 Comparaison de la durée de vie…………………………………………………………….. 47
3.6 Partie 2 : comparaison dans un réseau à grande échelle………………………... 49
3.6.1 Paramètres de simulation………………………………………………… 49
3.6.2. Comparaison de l’énergie consommée………………………………….. 50
3.6.3 Comparaison des données reçues par la SB…………………………………………… 51
3.6.4 Comparaison de la durée de vie……………………………………………………………. 52
3.7 Conclusion………………………………………………………………………... 53
Conclusion générale et perspectives …………………………………………………... 55
Bibliographie…………………………………………………………………………… 56
Annexes………………………………………………………………………………… 58Côte titre : MAI/0128 En ligne : https://drive.google.com/file/d/15jklEQ7FTbdGc27iw_3fmD_h7f0n6zD2/view?usp=shari [...] Format de la ressource électronique : Clustering basé sur l'intelligence en Essaim dans les réseaux de capteurs sans fil [texte imprimé] / Ghéraf,amira ; Djamila Mechta, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (61f.) ; 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
RCSF
AFSA
protocole LEACH-C
clustering hiérarchique
Cluster headIndex. décimale : 004 Informatique Résumé : Résumé:
Le Clustering est l'une des techniques les plus efficaces pour conserver l'énergie dans les
réseaux de capteurs sans fil. Son objectif principal est d’organiser le réseau en plusieurs
groupes appelés clusters, et sélectionner un chef pour Chaque groupe nommé cluster head
(CH) responsable d’agréger les données de ses membres pour les envoyer à la station de
base (SB). Dans ce travail nous avons étudié le problème de la consommation d’énergie et
le prolongement de la durée de vie dans les RCSFs afin de proposer un nouveau protocole
de clustering hiérarchique C-AFSA basé sur les comportements :swarm,prey ,follow
d’AFSA (artifitial fish swarm algorithm) pour la sélection des CHs et formation des
clusters. Les performances de notre algorithme sont évaluées et comparées avec le
protocole standard LEACH-C à travers une simulation à l’aide du simulateur réseau NS2.Note de contenu : Table des matières
Introduction générale………………………………………………………………….. 1
Organisation du mémoire……………………………………………………………... 2
Chapitre1 : clustering basé sur les méthodes bio-inspirés……………………………... 3
1.1.Introduction……………………………………………………………………... 4
1.2.Algorithmes basés sur PSO……………………………………………………... 5
1.2.1. PSO-HC…………………………………………………………………. 5
1.2.2. KPSO Hybrid protocol………………………………………………….. 7
1.3. Algorithme basé sur les réseaux neurone………………………………………. 8
1.3.1. CNN-LEACH……………………………………………………………. 8
1.4. Algorithme basé sur la Pollinisation ………………………………………….. 8
1.4.1.PBO………………………………………………………………………. 8
1.5. Algorithme basé sur essaim de poisson………………………………………... 10
1.5.1. AFSA……………………………………………………………………. 10
1.6. Algorithmes génétiques………………………………………………………… 13
1.6.1. GA……………………………………………………………………… 13
1.6.2. CGC (centralized genetic-based clustering)…..……………………….. 15
1.7. Conclusion……………………………………………………………………… 20
Chapitre 2 : protocole proposé C-AFSA………………………………………………. 21
2.1. Introduction…………………………………………………………………….. 22
2.2 LEACH_C………………………………………………………………………. 22
2.2.1. Phase d’initialisation…………………………………………………… 22
2.2.2. Phase de transmission………………………………………………….. 23
2.3. Généralités sur AFSA (artificial fish swarm algorithm)……………………….. 24
2.4. Caractéristiques du protocole proposé…………………………………………. 25
2.4.1. Les paramètre du protocole……………………………………………. 25
2.4.2. Les propriétés du modèle du réseau…………………………………………………. 25
2.5. Description générale du protocole proposé……………………………………. 26
2.6. Description détaillée du protocole proposé……………………………………. 27
2.6.1 Division virtuelle du réseau…………………………………………….. 27
2.6.2 Election des CHs initiaux………………………………………………. 28
2.6.3 Application des comportements d’AFSA dans la sélection des CHs…… 29
2.6.3.1- comportement de proie (Prey) :prey_ch ………………………... 30
2.6.3.2- comportement d’essaim (swarm) :swarm_ch…………………… 31
2.6.3.3- comportement de suivie (follow) : follow_ch…………………… 32
2.6.4. La formation des clusters en utilisant les comportements AFSA………. 34
2.6.4.1 .Clutering initial…………………………………………………. 35
2.6.4.2. Prey clustering (prey_clust)…………………………………….. 35
2.6.4.3.swarm clustering (swarm_clust)………………………………… 36
2.6.4.4. Follow clustering (follow_clust)……………………………….. 38
2.6.5. La fonction objectif (Fitness)…………………………………………... 39
2.7. Le modèle d’énergie…………………………………………………………... 40
2.8. La transmission des données………………………………………………….. 40
2.9. Conclusion…………………………………………………………………….. 41
Chapitre 3 : mise en œuvre……………………………………………………………. 42
3.1. Introduction…………………………………………………………………………………………………… 43
3.2. L’environnement de développement…………………………………………... 43
3.3.1. NS2……………………………………………………………………… 43
3.2.2 Intégration des packages de LEACH…………………………………….. 43
3.3. Simulation……………………………………………………………………… 43
3.3.1. Paramètre du protocole………………………………………………….. 43
3.3.2. Résultats de la simulation……………………………………………….. 44
3.4. Les métriques de performance…………………………………………………. 45
3.5 Partie 1 : comparaison dans un réseau de petite taille………………………….. 45
3.5.1 Paramètres du réseau…………………………………………………………………………… 45
3.5.2 Comparaison de l’énergie consommée…………………………………... 46
3.5.3 Comparaison des données reçues par la SB…………………………………………… 46
3.5.4 Comparaison de la durée de vie…………………………………………………………….. 47
3.6 Partie 2 : comparaison dans un réseau à grande échelle………………………... 49
3.6.1 Paramètres de simulation………………………………………………… 49
3.6.2. Comparaison de l’énergie consommée………………………………….. 50
3.6.3 Comparaison des données reçues par la SB…………………………………………… 51
3.6.4 Comparaison de la durée de vie……………………………………………………………. 52
3.7 Conclusion………………………………………………………………………... 53
Conclusion générale et perspectives …………………………………………………... 55
Bibliographie…………………………………………………………………………… 56
Annexes………………………………………………………………………………… 58Côte titre : MAI/0128 En ligne : https://drive.google.com/file/d/15jklEQ7FTbdGc27iw_3fmD_h7f0n6zD2/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0128 MAI/0128 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Clustering based on whale optimization algorithm for IoT networks Type de document : texte imprimé Auteurs : Soundous Ayet-Errahmane Aissaoui, Auteur ; Dounia Reggad ; Zibouda Zouaoui, Directeur de thèse Editeur : Setif:UFA Année de publication : 2024 Importance : 1 vol (65 f .) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Internet of Things (IoT)
Wireless Sensor Networks (WSN)
Whale optimization
Algorithm (WOA)
Energy consumption
Network lifetimeIndex. décimale : 004 - Informatique Résumé :
The Internet of Things (IoT) is an innovative concept in the field of information and
communication technologies, allowing each entity (human, animal, or object) to send and
receive data via networks such as the Internet or Intranet. Wireless sensors, powered by
batteries, have limited energy resources, and their replacement is often impractical, which
limits the lifespan of wireless sensor networks. Therefore, reducing the energy consumption
of the sensors used in IoT networks is a crucial challenge to prolong the network’s lifespan.
Clustering, which groups sensor nodes into clusters, is an effective solution to improve
communication and reduce energy consumption in wireless sensor networks (WSNs). Each
cluster is led by a node called Cluster Head (CH), responsible for organization, data management,
and routing, which directly influences energy consumption and network lifespan.
Therefore, we need an effective method to select them carefully to ensure optimal performance
and energy efficiency.
The Whale Optimization Algorithm (WOA), inspired by the social behavior of humpback
whales, offers a promising solution for selecting CHs optimally. This method ensures
efficient management and optimal organization of communications, improving performance
and extending the network’s lifespan.Note de contenu : Sommaire
Abstract i
Résumé ii
Table of contents viii
List of figures x
List of tables xi
List of algorithms xii
General Introduction 1
1 Internet of Things, Wireless Sensor Networks and Clustering 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 IoT definition : One paradigm, many visions . . . . . . . . . . . . . . . . . . 3
1.3 IoT architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 IoT Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 RFID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 WSN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.3 Middleware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.4 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 IoT Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Future IoT Requierements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7 Wireless Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.2 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7.3 Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7.4 Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.8 WSNs in IoT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9.1 Clustering definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9.2 Clustering Objectives in WSN . . . . . . . . . . . . . . . . . . . . . . 18
1.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Clustering Approaches 21
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Clustering Basic concepts and phases . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Cluster Formation Phase . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Cluster Head Selection Methods . . . . . . . . . . . . . . . . . . . . . 22
2.3 Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Classical Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Machine Learning algorithms . . . . . . . . . . . . . . . . . . . . . . 25
2.3.3 Bio-inspired Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Contribution, Experiments and Results 39
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 Network model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Energetic model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.3 Trafic model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Cluster head Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.3 Cluster Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.4 Intra-cluster communication . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.5 Inter-cluster communication . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.6 Reclustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 Implementation and writing tools . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5 Simulation and performance evaluation . . . . . . . . . . . . . . . . . . . . . 49
3.5.1 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.2 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
General Conclusion 59Côte titre : MAI/0845 Clustering based on whale optimization algorithm for IoT networks [texte imprimé] / Soundous Ayet-Errahmane Aissaoui, Auteur ; Dounia Reggad ; Zibouda Zouaoui, Directeur de thèse . - [S.l.] : Setif:UFA, 2024 . - 1 vol (65 f .) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Internet of Things (IoT)
Wireless Sensor Networks (WSN)
Whale optimization
Algorithm (WOA)
Energy consumption
Network lifetimeIndex. décimale : 004 - Informatique Résumé :
The Internet of Things (IoT) is an innovative concept in the field of information and
communication technologies, allowing each entity (human, animal, or object) to send and
receive data via networks such as the Internet or Intranet. Wireless sensors, powered by
batteries, have limited energy resources, and their replacement is often impractical, which
limits the lifespan of wireless sensor networks. Therefore, reducing the energy consumption
of the sensors used in IoT networks is a crucial challenge to prolong the network’s lifespan.
Clustering, which groups sensor nodes into clusters, is an effective solution to improve
communication and reduce energy consumption in wireless sensor networks (WSNs). Each
cluster is led by a node called Cluster Head (CH), responsible for organization, data management,
and routing, which directly influences energy consumption and network lifespan.
Therefore, we need an effective method to select them carefully to ensure optimal performance
and energy efficiency.
The Whale Optimization Algorithm (WOA), inspired by the social behavior of humpback
whales, offers a promising solution for selecting CHs optimally. This method ensures
efficient management and optimal organization of communications, improving performance
and extending the network’s lifespan.Note de contenu : Sommaire
Abstract i
Résumé ii
Table of contents viii
List of figures x
List of tables xi
List of algorithms xii
General Introduction 1
1 Internet of Things, Wireless Sensor Networks and Clustering 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 IoT definition : One paradigm, many visions . . . . . . . . . . . . . . . . . . 3
1.3 IoT architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 IoT Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 RFID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 WSN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.3 Middleware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.4 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 IoT Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Future IoT Requierements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7 Wireless Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.2 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7.3 Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7.4 Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.8 WSNs in IoT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9.1 Clustering definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9.2 Clustering Objectives in WSN . . . . . . . . . . . . . . . . . . . . . . 18
1.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Clustering Approaches 21
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Clustering Basic concepts and phases . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Cluster Formation Phase . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Cluster Head Selection Methods . . . . . . . . . . . . . . . . . . . . . 22
2.3 Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Classical Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Machine Learning algorithms . . . . . . . . . . . . . . . . . . . . . . 25
2.3.3 Bio-inspired Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Contribution, Experiments and Results 39
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 Network model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Energetic model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.3 Trafic model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Cluster head Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.3 Cluster Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.4 Intra-cluster communication . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.5 Inter-cluster communication . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.6 Reclustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 Implementation and writing tools . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5 Simulation and performance evaluation . . . . . . . . . . . . . . . . . . . . . 49
3.5.1 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.2 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
General Conclusion 59Côte titre : MAI/0845 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0845 MAI/0845 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
Titre : Clustering dans Internet des Véhicules Type de document : texte imprimé Auteurs : Laid,Khalil, Auteur ; Djamila Mechta, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (64 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : IoT
VANET
IoV
clustering
Algorithme multi-saut
Graphe connexeIndex. décimale : 004 Informatique Résumé : Dans nos jour, les chercheurs ont accordé beaucoup d’attention à l’Internet du
véhicule en raison de l’évolution continue du réseau automobile, qui a conduit boucoup
des difficultés telles que la scalabilité, la sécurité, la mobilité, topologie dynamique et
le grand nombre de véhicules qui augmente le nombre des messages Échangés.
Pour cette raison, de nombreux mécanismes de contrôle ont été proposés par les chercheurs,
parmi les mécanismes les plus importants est le clustering.
À cet égard, nous avons proposé deux contributions centralisées de clustering multisauts
en milieu urbain sous contraints de : RSU(Road Side Unit) sont présents sur
toutes les routes, les positions des RSUs sont connus par les véhicules via le GPS.
La première contribution dépend des voisins multi-saut pour la formation du clusetr,
permet de sélectionner un seul CH (Cluster Head) à chaque région de l’RSU, avec une
liste de SCHs (Second Cluster Head) éligibles pour être CH en cas de la panne du CH.
La deuxième contribution permet de sélectionner plusieurs CHs dans la région de l’RSU,
et un seul SCH parmi les voisins directs du CH initial avec la valeur d’occurrence maximale.
Cette contribution dépend du concept de direction et des graphes connexes pour
obtenir des clusters bien connecter.
Ces contributions améliorent la stabilité des clusters, réduisent le délai de transmission
et le taux de réception des messages.
Nous évaluons ces contributions dans les simulateurs de réseau OMNet et NS2, le simulateur
de mobilité SUMO et le framework des veines.Note de contenu : Sommaire
Introduction générale xiii
1 Généralités sur Internet des véhicules 1
Partie 1 : Internet des véhicules 2
1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 L’architecture et la communication dans IoVs . . . . . . . . . . . . . . 2
1.2.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Les Technologies de communication . . . . . . . . . . . . . . . . . . . . 6
1.3.1 La norme IEEE 802.11p . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Technologies d’accès sans fil . . . . . . . . . . . . . . . . . . . . 6
1.4 Les Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Les applications de sécurité . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Les applications du services d’infotainment . . . . . . . . . . . 13
1.4.3 L’efficacité de transport . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Projets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.1 Car TALK 2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
vi
SOMMAIRE
1.5.2 Connected car Project Local Motors . . . . . . . . . . . . . . . 15
1.5.3 SCOOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.4 NOW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.5 FleetNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6 Les Caractéristiques et les défis . . . . . . . . . . . . . . . . . . . . . . 16
1.6.1 Les caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.2 Les défis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.7 Comparaison entre l’IoV et VANET . . . . . . . . . . . . . . . . . . . . 18
Partie 1 : Le Clustering dans l’IOV 19
1.8 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.9 Les types de clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.9.1 Clustering basé sur les prédectifs . . . . . . . . . . . . . . . . . 20
1.9.2 Clustering basé sur les voisins . . . . . . . . . . . . . . . . . . . 20
1.9.3 Clustering basé sur la mobilitée . . . . . . . . . . . . . . . . . . 21
1.9.4 Clustering basé sur le poid . . . . . . . . . . . . . . . . . . . . . 21
1.10 Travaux connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.10.1 CBSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.10.2 MCA-V2I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.3 VMaSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.4 HCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.5 NSCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.6 NMBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.10.7 N-Hops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
vii
SOMMAIRE
1.10.8 DMCNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.10.9 DHCV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.10.10NSCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2 Contributions 29
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Premier propositon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.1 Les notations utilisées dans cette étude . . . . . . . . . . . . . . 30
2.2.2 Les types des messages . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.3 La structure des messages . . . . . . . . . . . . . . . . . . . . . 31
2.2.4 Schéma Explicatif de formation de cluster . . . . . . . . . . . . 32
2.2.5 Les étapes de formation de cluster . . . . . . . . . . . . . . . . . 32
2.2.6 Les états principaux de formation des clusters . . . . . . . . . . 38
2.2.7 Analyse théorique . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.8 Métriques d’évaluation des performances . . . . . . . . . . . . . 42
2.2.9 Implémentation et résultats obtenus . . . . . . . . . . . . . . . . 43
2.3 Deuxieme proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.1 Analyse théorique . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3.2 Implémentation et résultats obtenus . . . . . . . . . . . . . . . . 51
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3 Annexe 56
3.1 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.1 Versions compatibles . . . . . . . . . . . . . . . . . . . . . . . . 56
viii
SOMMAIRE
3.1.2 Installation des outiles sous Ubntu 16.04 . . . . . . . . . . . . . 56
3.2 implementation de l’algorithme . . . . . . . . . . . . . . . . . . . . . . 61
3.2.1 message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2.2 application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Bibliographie 64Côte titre : MAI/0314 En ligne : https://drive.google.com/file/d/179z9mnHm89zZZVa4qVlnNAMvBzF3KuTt/view?usp=shari [...] Format de la ressource électronique : Clustering dans Internet des Véhicules [texte imprimé] / Laid,Khalil, Auteur ; Djamila Mechta, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (64 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : IoT
VANET
IoV
clustering
Algorithme multi-saut
Graphe connexeIndex. décimale : 004 Informatique Résumé : Dans nos jour, les chercheurs ont accordé beaucoup d’attention à l’Internet du
véhicule en raison de l’évolution continue du réseau automobile, qui a conduit boucoup
des difficultés telles que la scalabilité, la sécurité, la mobilité, topologie dynamique et
le grand nombre de véhicules qui augmente le nombre des messages Échangés.
Pour cette raison, de nombreux mécanismes de contrôle ont été proposés par les chercheurs,
parmi les mécanismes les plus importants est le clustering.
À cet égard, nous avons proposé deux contributions centralisées de clustering multisauts
en milieu urbain sous contraints de : RSU(Road Side Unit) sont présents sur
toutes les routes, les positions des RSUs sont connus par les véhicules via le GPS.
La première contribution dépend des voisins multi-saut pour la formation du clusetr,
permet de sélectionner un seul CH (Cluster Head) à chaque région de l’RSU, avec une
liste de SCHs (Second Cluster Head) éligibles pour être CH en cas de la panne du CH.
La deuxième contribution permet de sélectionner plusieurs CHs dans la région de l’RSU,
et un seul SCH parmi les voisins directs du CH initial avec la valeur d’occurrence maximale.
Cette contribution dépend du concept de direction et des graphes connexes pour
obtenir des clusters bien connecter.
Ces contributions améliorent la stabilité des clusters, réduisent le délai de transmission
et le taux de réception des messages.
Nous évaluons ces contributions dans les simulateurs de réseau OMNet et NS2, le simulateur
de mobilité SUMO et le framework des veines.Note de contenu : Sommaire
Introduction générale xiii
1 Généralités sur Internet des véhicules 1
Partie 1 : Internet des véhicules 2
1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 L’architecture et la communication dans IoVs . . . . . . . . . . . . . . 2
1.2.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Les Technologies de communication . . . . . . . . . . . . . . . . . . . . 6
1.3.1 La norme IEEE 802.11p . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Technologies d’accès sans fil . . . . . . . . . . . . . . . . . . . . 6
1.4 Les Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Les applications de sécurité . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Les applications du services d’infotainment . . . . . . . . . . . 13
1.4.3 L’efficacité de transport . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Projets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.1 Car TALK 2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
vi
SOMMAIRE
1.5.2 Connected car Project Local Motors . . . . . . . . . . . . . . . 15
1.5.3 SCOOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.4 NOW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.5 FleetNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6 Les Caractéristiques et les défis . . . . . . . . . . . . . . . . . . . . . . 16
1.6.1 Les caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.2 Les défis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.7 Comparaison entre l’IoV et VANET . . . . . . . . . . . . . . . . . . . . 18
Partie 1 : Le Clustering dans l’IOV 19
1.8 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.9 Les types de clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.9.1 Clustering basé sur les prédectifs . . . . . . . . . . . . . . . . . 20
1.9.2 Clustering basé sur les voisins . . . . . . . . . . . . . . . . . . . 20
1.9.3 Clustering basé sur la mobilitée . . . . . . . . . . . . . . . . . . 21
1.9.4 Clustering basé sur le poid . . . . . . . . . . . . . . . . . . . . . 21
1.10 Travaux connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.10.1 CBSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.10.2 MCA-V2I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.3 VMaSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.4 HCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.5 NSCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10.6 NMBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.10.7 N-Hops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
vii
SOMMAIRE
1.10.8 DMCNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.10.9 DHCV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.10.10NSCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2 Contributions 29
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Premier propositon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.1 Les notations utilisées dans cette étude . . . . . . . . . . . . . . 30
2.2.2 Les types des messages . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.3 La structure des messages . . . . . . . . . . . . . . . . . . . . . 31
2.2.4 Schéma Explicatif de formation de cluster . . . . . . . . . . . . 32
2.2.5 Les étapes de formation de cluster . . . . . . . . . . . . . . . . . 32
2.2.6 Les états principaux de formation des clusters . . . . . . . . . . 38
2.2.7 Analyse théorique . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.8 Métriques d’évaluation des performances . . . . . . . . . . . . . 42
2.2.9 Implémentation et résultats obtenus . . . . . . . . . . . . . . . . 43
2.3 Deuxieme proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.1 Analyse théorique . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3.2 Implémentation et résultats obtenus . . . . . . . . . . . . . . . . 51
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3 Annexe 56
3.1 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.1 Versions compatibles . . . . . . . . . . . . . . . . . . . . . . . . 56
viii
SOMMAIRE
3.1.2 Installation des outiles sous Ubntu 16.04 . . . . . . . . . . . . . 56
3.2 implementation de l’algorithme . . . . . . . . . . . . . . . . . . . . . . 61
3.2.1 message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2.2 application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Bibliographie 64Côte titre : MAI/0314 En ligne : https://drive.google.com/file/d/179z9mnHm89zZZVa4qVlnNAMvBzF3KuTt/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0314 MAI/0314 Mémoire Bibliothéque des sciences Français Disponible
DisponiblePermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalink
PermalinkPermalinkPermalinkPermalinkPermalink
PermalinkPermalink
