SAAFA-76-MRRRCH
Présentation des réseaux Ad hoc et des RCSFs
Les applications des réseaux Ad hoc
Les recherches sur les réseaux Ad hoc ont été initiées par le DARPA (Defence Advanced Research Projects Agency) avec le développement de PRN (Packet Radio Networks) [9]. Ce protocole, conçu par l’armée américaine, permet de déployer une infrastructure de communication entre chaque bataillon, par l’intermédiaire de 7 Présentation des réseaux Ad hoc et des RCSFs plusieurs véhicules communiquant ensemble. Il possède de bonnes solutions, comme la prise en compte de la qualité des liens. Mais ce protocole possède de trop nombreux défauts. D’une part, il prend l’hypothèse que l’ensemble des entités se déplace lentement (avec peu de changements dans la topologie du réseau). D’autre part, la difficulté de concevoir (dans les années 70) des dispositifs électroniques suffisants pour mémoriser les paquets lors d’une réémission impliquait un matériel de taille assez importante et difficile à utiliser. Le fait que ce soit les militaires qui aient commencé les premières expérimentations sur les réseaux Ad hoc n’est pas un hasard. En effet, cette infrastructure est très adaptée aux environnements hostiles, car leur déploiement est rapide et ils sont robustes dans le cas des pertes de liens. De plus, la possibilité de posséder plusieurs routes renforce la fiabilité de l’ensemble du réseau. Ils sont donc particulièrement intéressants pour un système de communication sur les champs de bataille mais aussi dans d’autres environnements. On peut évoquer les sinistres (tremblements de terre, inondations, etc.) où l’ensemble des infrastructures existantes a été détruit. Les unités de secours disposent alors d’un moyen de communication qui n’est pas influencé par les dégâts causés à l’environnement. Ou encore, les survivants qui peuvent établir un réseau pour aider à leur localisation. Les réseaux Ad hoc peuvent aussi être utilisés pour relier plusieurs ordinateurs entre eux. Ils sont donc adaptés pour la tenue de réunions, où la nécessité d’une infrastructure pour les communications est soutenue par l’ensemble des participants. Il existe également des recherches proposant d’utiliser les réseaux Ad hoc dans les véhicules routiers. On peut entrevoir de nombreuses applications possibles pour un tel usage : distribution d’information au niveau local (risque d’accidents ou d’encombrements), aide automatique à la conduite (feux d’avertissement), téléphonie entre véhicules, etc. Avec l’émergence de l’informatique mobile et les possibilités offertes par l’informatique vestimentaire (Wearable computing) chaque usager se voit doté d’ordinateurs qu’il transporte avec lui. Ces appareils peuvent se mettre à communiquer entre eux ou avec l’environnement. Dans le premier cas, on parle de réseau personnel (PAN : Personal Area Network) et la solution Ad hoc permet la liaison entre chacun des éléments (avec l’utilisation du Bluetooth par exemple, adapté pour de petits objets et 8 Présentation des réseaux Ad hoc et des RCSFs de courtes distances). Dans le deuxième cas, les réseaux Ad hoc permettent à chacun de se connecter à l’environnement et d’y participer sans pré-requis particulier. On parle alors d’informatique omniprésente (Ubiquitous Computing) : chaque entité se configure en fonction des communications disponibles, de façon transparente pour l’utilisateur. Un autre domaine très intéressant pour les réseaux Ad hoc concerne les capteurs. Ce sont des équipements possédant des capacités limitées (énergie, mémoire, processeur, bande passante) et de taille réduite. Ces équipements ont de nombreux domaines d’applications. Ils sont en général utilisés en grande quantité et les réseaux Ad hoc permettent alors la liaison entre tous ces équipement
Routage dans les réseaux Ad hoc
Du fait que le rayon de propagation des transmissions des hôtes soit limité et afin que le réseau ad hoc reste connecté (toute unité mobile peut atteindre toute autre), il se peut qu’un hôte mobile se trouve dans l’obligation de demander de l’aide à un autre hôte pour pouvoir communiquer avec son correspondant. Il se peut donc que l’hôte destination soit hors de la portée de communication de l’hôte source, ce qui nécessite l’emploi d’un routage interne par des nœuds intermédiaires afin de faire acheminer les paquets de messages à la bonne destination. La gestion de l’acheminement des données ou le routage, consiste à assurer une stratégie qui garantit, à n’importe quel moment, la connexion entre n’importe quelle paire de nœuds appartenant au réseau [66]. 1.3.4.1 Caractéristiques des algorithmes de routage Un algorithme de routage doit être en mesure d’optimiser les ressources du réseau, éviter les boucles de routage, empêcher la concentration du trafic autour de certains nœuds ou liens, assurer un routage optimal tout en prenant en compte les différentes métriques de coûts, s’adapter aux changements de topologie rapidement en proposant de nouvelles routes acceptables, même en cas de forte mobilité des terminaux [22] [70] [21]. La méthode adoptée dans le routage, doit donc offrir le meilleur acheminement des données en respectant les différentes métriques de coûts utilisées. 9 Présentation des réseaux Ad hoc et des RCSFs 1.3.4.2 Classification des protocoles de routage dans les réseaux Ad hoc Les protocoles de routage dans les réseaux Ad hoc sont fondés sur les principes fondamentaux du routage, qui sont : l’inondation, le vecteur de distance, le routage à la source et l’état de lien. Deux grandes catégories de protocoles se sont formées à partir de la normalisation de MANET. Les protocoles de routage proactifs qui établissent les routes à l’avance et les protocoles de routage réactifs qui cherchent les routes à la demande. D’autres classes sont à citer, à savoir les protocoles de routage hybrides (mélange des protocoles proactifs et réactifs), géographiques, hiérarchiques, à qualité de service et multicast [74]. La figure ci-dessous présente une classification des protocoles de routage pour les réseaux Ad hoc qui peuvent être classés en deux grandes classes suivant la manière de création et de maintenance de routes lors de l’acheminement des données
|
Table des matières
Table des Figures i
Liste des tableaux
Introduction générale
1 Présentation des réseaux Ad hoc et des RCSFs
1.1 Introduction
1.2 Présentation des environnements mobiles
1.3 Les réseaux Ad hoc
1.3.1 Définition d’un réseau Ad hoc
1.3.2 Caractéristiques des réseaux ad hoc
1.3.3 Les applications des réseaux Ad hoc
1.3.4 Routage dans les réseaux Ad hoc
1.4 Les réseaux de capteurs sans fil
1.4.1 Définition des réseaux de capteurs sans fil
1.4.2 Architecture
1.4.3 Communication dans les réseaux de capteurs sans fil
1.4.4 Classification des réseaux de capteurs sans fil
1.4.5 Facteurs de conception des réseaux de capteurs sans fil
1.4.6 Domaines d’application
1.4.7 Scénarios typiques
1.5 Comparaison entre les réseaux ad hoc et les réseaux de capteurs
1.6 Conclusion
2 Routage et économie d’énergie dans les RCSFs
2.1 Introduction
2.2 Les Défis du routage dans les réseaux de capteurs
2.2.1 Le déploiement des capteurs
2.2.2 Modèle de livraison de données
2.2.3 Hétérogénéité des nœuds/liens
2.2.4 Qualité de service
2.2.5 Agrégation/fusion de données
2.2.6 Dynamicité du réseau et mobilité
2.3 Les approches de routage dans les réseaux de capteurs
2.3.1 Classification selon la structure du réseau
2.3.2 Classification selon les fonctions des protocoles
2.3.3 Classification selon l’établissement de la route
2.3.4 Classification selon l’initiateur de communication
2.4 Mécanismes de minimisation de la consommation d’énergie dans les réseaux de capteurs sans fil
2.4.1 Energie de capture
2.4.2 Energie de traitement
2.4.3 Energie de communication
2.5 Conclusion
3 Equilibrage de charge dans les RCSFs
3.1 Introduction
3.2 Principe de l’équilibrage de charge
3.3 Application des techniques d’équilibrage de charge aux RCSFs
3.3.1 Protocole avec réception en O(1)
3.3.2 VCA (An Energy-Efficient Voting-Based Clustering Algorithm for Sensor Networks)
3.3.3 Algorithme de clusterisation et d’équilibrage de charge dans les RCSFs avec cluster-heads mobiles
3.3.4 Algorithme d’optimisation de la durée de vie dans un réseau de capteurs
3.3.5 Algorithme d’équilibrage de charge à nœud central pour les RCSFs
3.4 Principe de l’algorithme d’équilibrage de charge proposé
3.5 Conclusion
4 Algorithme de regroupement avec équilibrage de charge pour les RCSFs (CLB) 75
4.1 Introduction
4.2 Motivations
4.3 Clusterisation par équilibrage de charge
4.3.1 Phase d’initialisation
4.3.2 Phase d’auto-désignation des cluster-heads
4.3.3 Phase de rattachement aux cluster-heads
4.3.4 Phase de mise à jour des poids d’éligibilité et des facteurs de charge
4.4 Simulation et analyse des performances
4.4.1 Métriques de performances
4.4.2 Modèle de simulation
4.4.3 Evaluation de performances
4.5 Conclusion
Conclusion générale & Perspectives
Bibliographie
Télécharger le rapport complet
