|
| 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
iv |
| Côte titre : |
MAI/0001 |
| En ligne : |
https://drive.google.com/file/d/1UKovt_IaQWPpLeB6c00wuun0Tnv_ROvB/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
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
iv |
| Côte titre : |
MAI/0001 |
| En ligne : |
https://drive.google.com/file/d/1UKovt_IaQWPpLeB6c00wuun0Tnv_ROvB/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
|
Ajouter le résultat dans votre panier Affiner la rechercheOptimisation des protocoles de routage dans les réseaux de capteurs avec l’approche de colonie de fourmis / BOUNOUNI, Mahdi
