Liste des Figures
Liste des Tableaux
Liste des abréviations
Introduction Générale
Chapitre I : Réseaux de capteurs sans fil : Concepts et applications
Introduction
I.1. Réseaux de capteurs sans fil
I.2. Anatomie d’un nœud capteur
I.3. Caractéristiques des réseaux de capteurs sans fil
I.4. Modèles de fonctionnement du réseau
I.5. Domaines d’application
I.6. Conception d’un réseau de capteurs sans fil:
I.7. Architecture
Conclusion
Chapitre II : Etude et classification des protocoles de routage dans les RCSFs
II.1. Taxonomie des protocoles de routage dans un RCSF
II.1.1. Taxonomie selon la topologie du réseau
II.1.2. Taxonomie selon le fonctionnement du protocole
II.1.3. Taxonomie selon les paradigmes de communication
II.1.4. Taxonomie selon l’établissement de la route
II.1.5. Taxonomie selon la mobilité
II.1.6. Taxonomie selon l’hétérogénéité
II.1.7. Taxonomie selon la couche de routage
II.2. Techniques de routage dans les piles de protocole des RCSFs
II.2.1. Zigbee
II.2.6. 6LoWPAN
Synthèse
II.3. Algorithmes de routage basés sur l’Optimisation par colonie de fourmis
II.3. 1. Algorithme de base
II.3. 2. Contrôle à base de fourmis (Ant-Based Control)
II.3. 3. AntNet
II.3. 4. Système de routage à base d'agent (ARS)
II.3. 5. AntHocNet
Synthèse
Conclusion
Chapitre III : Réseaux de capteurs IPv6 et ContikiRPL
Introduction
III.1. Réseaux de capteurs IPv6
III.1.1. Paradigme d'Internet des objets
III.1.2. Les réseaux à faible puissance et avec perte : LLNs
III.1.3. RPL : Le nouveau protocole de routage IPv6 pour les réseaux
III.1.3.1. RPL dans le modèle OSI
III.1.3.2. Topologie RPL
III.1.3.3. Messages de contrôles RPL
III.1.3.4. L’algorithme Trickle
III.1.3.5. Fonction objective (OF)
III.1.3.6. Définition du rang dans RPL
III.1.3.7. Les métriques de routage
III.1.3.8. Construction du DODAG
Conclusion
III.2.ContikiRPL
III.2.1. Contiki OS
III.2.2.Fonctionnement
III.2.3. Le Simulateur COOJA
III.2.3. Les composants ContikiRPL
III.2.3.1. Module des messages ICMP6
III.2.3.2. Module de construction du DAG
III.2.3.3. Module RPL Routes
III.2.3.4. Module Timers
III.2.3.5. Module fonction Objective
III.2.3.6. Module Headers
Conclusion
Chapitre IV : Contributions
Introduction
IV.1. Première Contribution
IV.1.1. Description de la première approche proposée
IV.1.2. Format des Messages de contrôle
IV.1.2.1. Message Hello
IV.1.2.2. Message requête de route
IV.1.2.3. Message de réponse de route
IV.1.2.4. Message erreur de route
IV.1.3. Modèle Mathématique
IV.1.4. Calcul des métriques relatives
IV.1.4.1. Délai
IV.1.4.2. Nombre de sauts
IV.1.4.3. La bande passante
IV.1.4.4. Phéromone
IV.1.5. Renforcement des routes
IV.1.5.1. Mise à jour phéromone
IV.1.5.2. Mise à jour du délai
IV.1.5.3. Mise à jour bande passante
IV.1.6. Phase de découverte de Route
IV.1.7. Phase de maintenance de route
IV.1.8. Simulation et résultat
IV.1.8. 1. Le délai moyen de bout en bout
IV.1.8. 2.Taux de livraison des paquets
Synthèse
IV.2. Deuxième Contribution
IV.2.1. Description de la deuxième approche proposée
IV.2.1.1. Interprétation de la disponibilité
IV.2.1.2. Paquets de contrôle
IV.2.2. Modèle Mathématique
IV.2.2.1. Disponibilité
IV.2.2.2. Energie Résiduelle minimale
IV.2.3. Déroulement de la phase de découverte de routes
IV.2.4. Phase de maintenance de route
IV.2.5. Simulation et résultat
IV.2.6. Tests et analyse des résultats
IV.2.6.1. Disparition du nœud 6
IV.2.6.2. Disparition du nœud 13
IV.2.6.3. Disparition du nœud 18
IV.2.6.4. Bilan de la disparition d’un nœud
Synthèse
IV.3. Troisième Contribution
IV.3.1. Description de la troisième approche proposée
IV.3.1.1. Calcul des métriques relatives
IV.3.1.1.1. Le Délai
IV.3.1.1.2. Energie Résiduelle Minimale
IV.3.1.1.3. Phéromone
IV.3.2. Route renforcement
IV.3.3. Calcul du rang
IV.3.4. Exemple de scénario
IV.3.5. Environnement de simulation
IV.3.6. Résultats et discussion
IV.3.6.
IV.3.6.2. Performance de transmission
IV.3.6.3. Amélioration du délai de bout-en-bout
Synthèse
IV.4. Évaluation expérimentale des performances du protocole RPL
IV.4. 1. Le délai de convergence du DAG
IV.4.2. Consommation d'énergie
IV.4.3. Perte de paquets
IV.4.4. Délai de bout en bout
Conclusion
Conclusion Générale et Perspectives
Annexes
Entreprendre une thèse en parallèle d'une activité professionnelle d'enseignant occasionne quelques difficultés, et nécessite le soutien de l'entourage, ce qui explique la longueur de ces remerciements.
Je remercie très chaleureusement mon directeur de thèse, monsieur le professeur Feham Mohammed, qui, malgré ses nombreuses occupations, a accepté de prendre la direction de cette thèse, transformant ainsi les difficultés rencontrées en une expérience enrichissante. Je lui suis également reconnaissant de m’avoir assuré un encadrement rigoureux tout au long de ces années.
Mes remerciements vont particulièrement à tous les membres du laboratoire STIC de l’Université Abou-Bekr Belkaid de Tlemcen, pour leurs encouragements et leur assistance qui m'ont permis de faire cette thèse dans de bonnes conditions.
Je suis grandement reconnaissante au professeur Congduc Pham de m’avoir accueilli dans le laboratoire LIUPPA de l’Université de Pau France. Merci également à tous les membres du laboratoire qui ont mis tout en œuvre pour que mon stage se déroule dans les meilleures conditions possible.
Je suis reconnaissant envers mon frangin le Pr. Belghachi Abderrahmane, dont le soutien et les précieux conseils m’ont guidé tout au long de ma recherche.
Je remercie les membres de jury de cette thèse qui ont accepté de siéger doivent aussi trouver ici l’expression de ma reconnaissance. Je remercie vivement Mr LEHSAINI Mohammed qui m'a fait l'honneur de présider le Jury de cette thèse. Mes remerciements les plus sincères vont aussi à Mr SENOUCI Sidi Mohammed, Mr HAFFAF Hafid, Mr SEKHRI Larbi et Mr MANA Mohamed pour avoir accepté d’examiner cette Thèse et d’avoir consacré une partie de leur temps à sa lecture.
A mes collègues de travail de l’université Tahri Mohammed de Béchar, je tiens à offrir ma plus sincère sympathie et mes remerciements les plus chaleureux.
Dédicaces
Je dédié ce travail à ma famille, ma mère, ma femme et mes quatre enfants Khaled, Ali, Anes et Serine, ma motivation et ma plus grande source d’inspiration.
L’évolution rapide de la technologie multimédia et l’intérêt commercial des compagnies pour populariser ce type d’application, ont fait de la qualité de service (Qds) un secteur d’une grande importance. Ces applications sont caractérisées par une quantité de donnée volumineuse par rapport à celle des applications traditionnelles des RCSFs. En outre, la Qds est désormais devenue une exigence fondamentale. Par ailleurs, assurer la Qds dans de tels réseaux est très délicat. Cependant, le changement de topologie imprévue peut nuire la continuité de service et le rend extrêmement difficile voire impossible. Il est légitime donc, de considérer la fiabilité des routes comme étant la contrainte de Qds principale à prendre en compte pour la transmission de données. La mission du routage consiste à déterminer le meilleur chemin entre la source et la destination dans le réseau selon certains critères de performance. Dans cette thèse, nous examinons certains des mécanismes de Qds existants dans la littérature de réseautage, et les caractéristiques inhérentes des RCSFs qui font qu'il est difficile de prévoir la qualité de service dans le réseau. Nous identifions alors quelques indicateurs de performance clés et nous décrivons certains mécanismes pour atteindre la qualité de service dans le réseau de capteurs. Notre thèse se présente sous la forme de quatre contributions scientifiques, chacune traitant une problématique bien spécifique.
Mots clés- RCSFs ; ACOs ; QdS ; Disponibilité ; Re-routage ; RPL
The fast evolution of multimedia technology and the commercial interest of the companies to popularize this type of application, favored the quality of service, a sector of great importance. These applications are characterized by a large amount of data compared to the traditional applications of WSNs. QoS has now become a fundamental requirement. Also, ensure QoS in such networks is very delicate. However, the unexpected change of topology may harm the continuity of service and makes it extremely difficult or impossible. It therefore legitimate to consider the reliability of the route as the main constraint of QoS to take into account for the data transmission. The mission of the routing consists in determining the best path between the source and the destination in the network as a performance criterion.
In this thesis, we have examined some existing mechanisms in literature for QoS networking, and inherent characteristics of WSNs that make it difficult to predict the quality of service in the network. We, then; identify some performance indicators key and we describe some mechanisms to achieve QoS in sensor network. Our thesis is presented in the form of four scientific contributions, each addressing a very specific problem.
Keywords- WSNs; ACO; QoS; availability; Re-routing; RPL.
Abbildung in dieser Leseprobe nicht enthalten
Figure I.1 : Un réseau de capteurs sans fil
Figure I.2 : Composants d’un nœud de capteur
Figure I.3 Les domaines d’applications des RCSFs.
Figure I.4 : Réseau de capteurs sans fil Plat
Figure I.5 : Réseau de capteurs sans fil Hiérarchique
Figure II.1 Taxonomie des protocoles de routage dans les RCSFs
Figure II.2 : Le protocole SPIN.
Figure II.3: Diffusion dirigée.
Figure II.4 : flux de données TTDD
Figure II.5 Echange de messages dans le protocole LOAD
Figure II.6 Schéma de routage 6LoWPAN
Figure II.7 Le problème du voyageur de commerce optimisé par l’algorithme AS.
Figure II.8 : Les fourmis en avant et arrière dans AntNet
Figure III.1 : Le paradigme d'Internet des objets (IdO)
Figure III.2 Intégration du protocole RPL dans l’architecture OSI.
Figure III.3 Topologie d’un réseau LLN avec les identifiants RPL.
Figure III.4 Structure du message de contrôle
Figure III.5 : Exemple illustrant la construction d’un DODAG.
Figure III.6: Différents types de trafic supporté par RPL.
Figure III.7 : Architecture du système Contiki
Figure III.8 Piles protocolaires pour Contiki
Figure III.9 Diagramme des composants de RPL
Figure III.10 Interactions entre les modules ICMP6 et les autres modules RPL.
Figure III.11 : Relation du module DAG avec les autres modules.
Figure III.12 : Relation entre le Module RPL Routes avec les autres modules
Figure III.13 : Fonctions d'interface entre le module Timers et les autres modules
Figure III.14 : Relation du module headers avec les autres modules RPL.
Figure IV.1: Le délai moyen de bout en bout
Figure IV.2: Taux de livraison des paquets densité des nœuds
Figure IV.3 : Répartition spatiale des nœuds
Figure IV.4 . Diagramme de séquence du scénario.
Figure IV. 5. Affichage d’ une trace avec Wireshark .
Figure IV. 6. Interface graphique du réseau sous Cooja
Figure IV.7. Consommation d'énergie des nœuds
Figure IV.8. Paquets reçus par le Sink
Figure IV.9. Le délai moyen de bout-en-bout
Figure IV.10. Banc d'essai expérimental pour la topologie à un saut.
Figure 4.11. Banc d'essai expérimental pour la topologie multi-sauts.
Figure IV.12. Délai de convergence expérimental du réseau RPL.
Figure IV.13. Energie moyenne consommée
Figure IV.14. Taux de paquets perdus pour différents nombre de sauts
Figure IV.15. Délai de bout en bout pour différents nombre de sauts
Table III.1 Les codes des différents messages de contrôle RPL
Table IV.1: Valeurs des paramètres d’ACO utilisées
Tableau IV.2 : Récapitulatif des résultats pour la disparition du nœud 6
Tableau IV.3 : Récapitulatif des résultats pour la disparition du nœud 13
Tableau IV.4 : Récapitulatif des résultats pour la disparition du nœud 18
Tableau IV.5 : Résultats de comparaison entre Cas1 et Cas2
Tableau IV.6. Paramètres de Contiki OS et COOJA.
Tableau IV.7. Paramètres du protocol RPL
Abbildung in dieser Leseprobe nicht enthalten
Les réseaux de capteurs sans fil (RCSFs) sont prédestines à devenir une partie intégrante de notre vie quotidienne. Cela est dû en grande partie aux progrès technologiques réalises dans les domaines de la miniaturisation des composants électroniques et de la standardisation des communications sans fil. Ces réseaux ont fait l'objet d'une activité de recherche intensive, dont l'objectif est de produire des réponses aux limitations et particularités qui leur sont associées. En particulier, la gestion efficace des ressources énergétiques ainsi que l'optimisation des protocoles de communication continuent d'être un domaine de recherche très fertile.
La recherche dans le domaine des capteurs connait actuellement une révolution importante, ouvrant des perspectives significatives dans de nombreux domaines d'applications (sécurité, santé, environnement, sécurité alimentaire, fabrication, télécommunications, robotique, ...). Les nouvelles technologies permettent de réduire l'encombrement, le coût et la consommation d'énergie et d'augmenter la précision et les performances des capteurs, des processeurs et des circuits spécifiques. Un nombre très important de capteurs peut donc être envisagé, intégré et organisé en réseau. Le développement de ces réseaux de capteurs constitue donc très certainement une prochaine étape dans l'évolution des technologies de l'information. Par conséquent, il est important de développer des axes de recherches permettant l'utilisation des réseaux denses, sans fils entre des nœuds hétérogènes et ayant pour rôles de collecter des données d'un environnement donné et de les diffuser au sein du réseau. Ce type de réseaux de capteurs pourrait avoir de très diverses applications. Cette diversité a conduit ces réseaux à supporter différents types de trafics et à fournir des services qui doivent être à la fois génériques et adaptatifs aux applications car les propriétés de la qualité de service (QdS) différent d'un type d'applications à un autre. Certaines applications exigent un certain niveau de QdS pour délivrer le contenu. Jusqu’ à présent, le besoin de réduire au minimum la consommation d’énergie a fait objet de la plupart des recherches dans les réseaux de capteurs. Peu d’études dans le domaine concernent les mécanismes pour délivrer efficacement la QdS.
Face à la multiplication du nombre d’applications qui requiert des exigences en termes de QdS, la prise en charge de la QdS dans les RCSFs devient un enjeu incontournable pour assurer leur succès. Cependant, cette prise en charge n’est pas aise. En effet, les contraintes imposées par ce type de réseaux sont multiples : le médium radio utilisé est peu fiable, la topologie entièrement dynamique, la puissance de calcul et la réserve d’énergie sont très limitées. De plus, la bande passante disponible est trop faible pour autoriser de lourds messages de contrôle. Enfin, la prise en charge de la QdS est un problème réparti sur l’ensemble du chemin qui sépare la source de la destination ; l’algorithme qui prend en charge la QdS est donc réparti. L’idée est d’assurer la QdS grâce à un processus de routage à base d’optimisation par colonie de fourmis (Ant Colonie Optimisation –ACO-) capable de détecter les chemins répondant aux exigences de QdS, couplé à un processus de réservation des routes détectés. Cependant, il faut intégrer à ce schéma la maintenance des routes rompues en cours de communication.
Une autre exigence dans la prise en charge de la QdS au niveau des RCSFs est d’assurer la compatibilité de cette prise en charge avec les autres types de réseaux avec lesquels une cohabitation sera nécessaire. En effet les réseaux de la future génération seront des réseaux hétérogènes intégrés, comme le concept de QdS fait intervenir l’idée de connexion, les solutions envisagées doivent être supportées par l’ensemble des nœuds et donc des réseaux mis en jeu par la connexion (solution de bout en bout)
L’objectif principal de cette thèse est de proposer des mécanismes efficaces de gestion de la QdS dans les RCSFs en nous focalisant sur l’aspect routage. Tout en prenant soin de fournir des solutions adaptées à des systèmes évolutifs à grande échelle. De manière spécifique, nous visons les objectifs suivants:
- Analyser les solutions déjà apportées en matière de QdS, en particulier au niveau du routage en vue de souligner leurs faiblesses.
- Concevoir et implémenter des algorithmes et protocoles qui permettent une meilleure gestion du problème de QdS dans les RCSFs.
- Evaluer la performance de ces algorithmes et protocoles en les comparants aux meilleurs modèles répertoriés dans la littérature.
A la suite de l’introduction générale, la thèse s’articule autour de quatre chapitres.
- Le premier chapitre de cette thèse fait l’objet sur les concepts des RCSFs, leurs domaines d’applications et les défis qui surviennent dans leur conception.
- Dans le deuxième chapitre, nous introduisons un état de l’art sur les algorithmes de routages pour les RCSFs. Préalablement à tout travail de recherche, il apparaît en effet indispensable de faire une analyser en profondeur les mécanismes qui ont prévalu dans les recherches antérieures.
- Le troisième chapitre est divisé en deux parties, dans la première partie on présente les réseaux de capteurs IPv6 ainsi que le protocole RPL. Dans la deuxième partie on présente l’implémentation du protocole RPL sous contiki OS.
- Dans le chapitre quatre, nous introduisons nos solutions pour optimiser la prise en compte de la QdS lors du routage dans les RCSFs, ainsi que les algorithmes et protocole qui en découlent. Puis nous présentons les détails d’implémentation de ces algorithmes et protocoles pour analyser leur performance. Ces simulations nous aiderons donc à optimiser les protocoles proposés et de les confronter aux algorithmes disponibles dans la littérature. En fin de ce chapitre nous présentons une évaluation expérimentale des performances du protocole RPL.
- Enfin, la conclusion permettra de faire une synthèse du travail réalisé en mettant en exergue les principales contributions apportées par notre travail. Dans cette partie, nous suggérons également des directions de recherche pour des travaux futurs.
Notre thèse se présente sous la forme de trois articles scientifiques, chacun traitant d'une problématique bien spécifique.
- Titre "Routing Diagram for the transport of video traffic in a WSN" Auteurs: Belghachi Mohamed, FEHAM Mohammed Acte : Journal of Theoretical and Applied Information Technology (JATIT) [Vol 17. No. 1 July 2010]. Journal indexé dans SCOPUS. E-ISSN 1817-3195 / ISSN 1992-8645
- Titre « QoS Based on Ant Colony Routing for Wireless Sensor Networks » Auteurs: Belghachi Mohamed, FEHAM Mohammed Acte: International Journal of Computer Science and Telecommunications (IJCST) [Volume 3, Issue 1, January 2012].
- Titre “QoS Routing diagram and route repair in WSN” Auteurs: Belghachi Mohamed, FEHAM Mohammed Acte : International Journal of Advanced Computer Science and applications (IJACSA) [Vol. 3, No. 12, 2012]. Journal indexé dans Thomson Reuters. ISSN: 21565570
- Titre “QoS routing RPL for Low power and Lossy Network” Auteurs: Belghachi Mohamed, FEHAM Mohammed Acte : International Journal of Distributed Sensor Network ( IJDSN ). Hindawi, Open Access. Article ID 971545, 10 pages, 2015. doi:10.1155/2015/971545. Journal indexé dans Thomson Reuters. ISSN: 1550-1329. Impact Factor 0.665
Les progrès réalisés ces dernières décennies dans les domaines de la microélectronique, de la micromécanique, et des technologies de communication sans fil, ont permis de produire avec un coût raisonnable des composants de quelques millimètres cubes de volume 1. Ces derniers, sont appelés nœuds capteurs, intégrant : une unité d’acquisition chargée de collecter des grandeurs physiques (chaleur, humidité, vibrations, etc…) et de les transformer en grandeurs numériques, une unité de traitement informatique et de stockage de données et un module de transmission sans fil. De ce fait, les nœuds capteurs sont de véritables systèmes embarqués. Le déploiement de plusieurs d'entre eux, en vue de collecter et transmettre des données environnementales vers un ou plusieurs points de collecte, d'une manière autonome, forme un réseau de capteurs sans fil. Dans ce chapitre, nous définissons les concepts de ce type de réseaux, les domaines d’application et les défis qui surviennent dans leur conception.
Les réseaux de capteurs sans fil (RCSFs) sont considérés comme un type spécial de réseaux ad hoc. Les nœuds de ce type de réseaux consistent en un grand nombre de nœuds capteurs capables de récolter et de transmettre des données environnementales d'une manière autonome 2. La position de ces nœuds n'est pas obligatoirement prédéterminée. Ils sont dispersés aléatoirement à travers une zone géographique, appelée champ d’acquisition, qui définit le terrain d'intérêt pour le phénomène capté. Les données captées sont acheminées à un nœud considéré comme un "point de collecte", appelé nœud puits (ou sink).
Ce dernier peut être connecté à l'utilisateur du réseau via Internet ou un réseau satellite (cf Figure I.1). Ainsi, l'usager peut adresser des requêtes aux autres nœuds du réseau, précisant le type de données requises et récolter les données environnementales captées par le biais du nœud puits.
Abbildung in dieser Leseprobe nicht enthalten
Figure I.1 : Un réseau de capteurs sans fil
Les RCSFs sont composés d’objets communicants (Nœuds) intégrés dans une zone d’intérêt, chaque objet communicant (cf Figure I.2) comporte 3:
- Unité d’acquisition
- Unité de traitement
- Unité de contrôle d’énergie
- Unité de transmission
Il peut contenir également, suivant son domaine d'application, des modules supplémentaires tels qu'un système de localisation (GPS), ou bien un système générateur d'énergie (cellule solaire,…). On peut même trouver des capteurs, un peu plus volumineux, dotés d'un système mobilisateur chargé de déplacer le capteur en cas de nécessité.
Abbildung in dieser Leseprobe nicht enthalten
Figure I.2 : Composants d’un nœud de capteur
Les réseaux de capteurs ne sont pas des réseaux ad hoc au sens classique du terme car ils ne fonctionnent pas de la même manière. Par exemple, la liaison radio étant intrinsèquement omnidirectionnelle, le réseau de capteur fonctionne par broadcast alors que les réseaux ad-hoc fonctionnent classiquement de pair à pair. Les caractéristiques les plus remarquables qui distinguent les réseaux de capteurs des réseaux ad hoc sont les suivantes 4:
- Nombre de nœuds : Pouvant atteindre plusieurs centaines voir davantage.
- Densité des nœuds : Pour des raisons de fiabilité d’une part mais aussi de par le mode de placement des nœuds il y aura en générale une forte voir très forte densité de nœuds.
- Fiabilité des nœuds: De par le mode de fabrication, de type industriel en très grande série, il n’est pas possible de contrôler le bon fonctionnement de chacun des nœuds. Par ailleurs, les nœuds disposants d’une énergie électrique limitée, certain tomberont en panne au bout d’un certain temps. C’est une caractéristique prise en compte dès le départ dans la conception du réseau.
- Topologie du réseau : En conséquence la topologie du réseau changera fréquemment. De plus il se peut très bien que l’on rajoute après coup de nouveaux nœuds, soit pour étendre le réseau ou plus sûrement pour compenser la défaillance d’un grand nombre de nœuds, après un certain temps de fonctionnement.
- Mode de communication : Comme vu dans l’introduction de cette partie, les nœuds communiquent par broadcast.
- Ressources : Les ressources sont très limitées : énergie électrique, puissance de calcul et capacité de stockage. L’ensemble du fonctionnement aura pour souci principal de limiter la consommation d’énergie afin de prolonger la durée de vie du réseau et ce au détriment de la qualité de service. En fait, l’utilisateur pourra, au moment du déploiement du réseau choisir entre durée de vie et performances.
- Identification : Les nœuds n’ont pas d’identifiant global à cause du nombre trop important de capteurs et de la surcharge que cela entraînerait.
On trouve plusieurs méthodes pour classer les réseaux de capteurs. Pour chaque type d’application, les réseaux de capteurs ont des caractéristiques différentes. Ils se distinguent, principalement, par le modèle de collecte des données, le modèle de déploiement des capteurs et le modèle de mobilité des nœuds.
Selon les interactions entre le réseau de capteurs et la station de base, nous citons trois modèles principaux 5:
- Surveillance périodique : Tous les capteurs envoient périodiquement leurs mesures à la station de base. Le type d’application visé concerne les applications de surveillance où le but principal est d’avoir une information régulière de la zone.
- Surveillance à la demande : Les capteurs ne transmettent pas spontanément les données de mesure, ils les envoient seulement lorsqu’ils reçoivent des requêtes explicites de la station de base. Ces requêtes peuvent être dirigées (sollicitation d’un capteur ou un groupe de capteurs) ou diffusées (requête de type conditionnel, par exemple tous les capteurs dont la mesure dépasse un seuil).
- Surveillance sur déclenchement d´évènements : Dans ce modèle, les capteurs envoient les mesures seulement lorsqu’il y a un évènement qui se produit, généralement le dépassement d’un seuil. Ce modèle est bien adapté par exemple à la détection d’intrusion.
- Applications hybrides : toute alliance des modèles de fonctionnements précédents.
Le déploiement des capteurs est la première opération dans le cycle de vie d’un réseau de capteurs. Le modèle de déploiement se définit par plusieurs paramètres, notamment le nombre de nœuds, la densité de déploiement et la méthode de déploiement : déterministe ou aléatoire 6.
- Le déploiement déterministe : lorsque la zone de surveillance est accessible et peu étendue, il est possible de positionner les nœuds à des emplacements préétablis. La position de chaque nœud est donc connue d’avance. Le rôle de chacun d’eux, et leurs interactions peuvent être programmés en fonction de leur position. C’est le cas par exemple pour les capteurs chargés de réguler la climatisation d’un immeuble ou de surveiller les constantes médicales de personnes malades. Ce type de déploiement peut devenir très contraignant, voire impossible pour les réseaux de capteurs à grande dimension.
- Le déploiement aléatoire : l’utilisation des capteurs dans des zones inaccessibles ou sensibles rend impossible un déploiement déterministe, au cours duquel chaque objet serait placé à une position prédéterminée. Les nœuds peuvent alors être déployés à l’aide de moyens divers. Dans les surveillances militaires par exemple, les capteurs pourraient être largués sur le terrain depuis un avion survolant la zone hostile. Il a souvent été question d’un déploiement aléatoire des capteurs, effectué comme un jeté de graines. En raison soit de l’hostilité de la zone à surveiller, soit de son immensité.
Le déploiement peut être fait d’un seul coup ou bien se faire de manière continue en rajoutant de nouveaux capteurs dans une même zone après des défaillances dues à l’épuisement des batteries pour prolonger la durée de vie du réseau. Le déploiement aléatoire ne peut pas fournir une distribution uniforme sur la région d’intérêt, ce qui amène de nouveaux problèmes dans les réseaux de capteurs pour garantir la couverture de la zone et la connexité du réseau.
On peut distinguer trois formes de mobilité dans les réseaux de capteurs 7:
- Mobilité des nœuds : La mobilité des capteurs ne concerne qu’un petit nombre d’applications, par exemple des applications militaires (les capteurs sont attachés à des soldats), des applications de surveillance des animaux d’élevage, ou des oiseaux migrateurs (les capteurs sont portés par les animaux) ou encore des surveillances des milieux marins (les capteurs suivent le mouvement du courant). Face à la mobilité des nœuds, le réseau doit se réorganiser assez fréquemment pour pouvoir fonctionner correctement. Le problème de la conservation de l’énergie des nœuds devient aussi plus ardu car les techniques de géolocalisation coutent de l’énergie et elles vont devoir être sollicitées plus fréquemment.
- Mobilité des puits : C’est un cas spécial de mobilité où seul le point de collecte est mobile. Cette forme de mobilité peut aussi être utilisée comme stratégie pour réduire la consommation d’énergie des réseaux de capteurs. Dans le principe où le trafic converge vers le puits, les nœuds proches du puits transmettent plus de paquets que les autres nœuds et donc épuisent plus vite leurs batteries. Si ce puits est mobile, les nœuds capteurs peuvent attendre son passage pour lui envoyer leurs données directement ou sur un petit nombre de sauts. Cela va réduire considérablement le trafic dans le réseau. Pour les réseaux de grande échelle, l’utilisation de plusieurs puits mobiles devient intéressante.
- Mobilité de l’évènement : Ce type de mobilité existe essentiellement dans les applications de suivi de cibles. Dans ce type d’application, il est habituellement important que l’évènement observé soit couvert par un nombre suffisant de nœuds. Par conséquent, les nœuds vont se réveiller autour de l’objet, pour le surveiller avec un taux d’activité élevée, et puis entrer en sommeil lorsque la cible s’éloigne. Pendant que la source d’évènement se déplace à travers le réseau, elle est accompagnée d’un secteur d’activité dans le réseau qui la suit.
Les caractéristiques des RCSFs permettent d’envisager un grand nombre d’applications d’observation réparties dans l’espace. Ces dernières peuvent se déployer dans de nombreux contextes : observation de l’environnement naturel (pollution, inondation, ...), militaire télésurveillance de champs de bataille, détection d’ennemis, ...), biomédical et surveillance médicale (détection de cancer, rétine artificielle, taux de glucose, diabètes,...) figure I.3, etc.
Abbildung in dieser Leseprobe nicht enthalten
Figure I.3 Les domaines d’applications des RCSFs.
Comme dans le cas de plusieurs technologies, le domaine militaire a été un moteur initial pour le développement des réseaux de capteurs. Le déploiement rapide, le coût réduit, l'auto organisation et la tolérance aux pannes des réseaux de capteurs sont des caractéristiques qui rendent ce type de réseaux un outil appréciable dans un tel domaine. Comme exemple d'application dans ce domaine 8, on peut penser à un réseau de capteurs déployé sur un endroit stratégique ou difficile d'accès, afin de surveiller toutes les activités des forces ennemies, ou d'analyser le terrain avant d'y envoyer des troupes (détection d'agents chimiques, biologiques ou de radiations).
Les altérations dans la structure d'un bâtiment, suite à un séisme ou au vieillissement, pourraient être détectées par des capteurs intégrés dans les murs ou dans le béton, sans alimentation électrique ou autres connexions filaires. Les capteurs doivent s'activer périodiquement et peuvent ainsi fonctionner durant des années. Un réseau de capteurs de mouvements peut constituer un système d'alarme distribué qui servira à détecter les intrusions sur un large secteur. Déconnecter le système ne serait plus aussi simple, puisque il n'existe pas de point critique.
La surveillance de voies ferrées pour prévenir des accidents avec des animaux et des êtres humains peut être une application intéressante des réseaux de capteurs. La protection des barrages pourrait être accomplie en y introduisant des capteurs 9. La détection prompte de fuites d'eau permettrait d'éviter des dégâts. Les êtres humains sont conscients des risques et attaques qui les menacent. Du coup, ils mettent à disposition toutes les ressources humaines et financières nécessaires pour leur sécurité. Cependant, des failles sont toujours présentes dans les mécanismes de sécurisation appliqués aujourd'hui, sans oublier leur coût très élevé. L'application des réseaux de capteurs dans le domaine de la sécurité pourrait diminuer considérablement les dépenses financières consacrées à la sécurisation des lieux et à la protection des êtres humains tout en garantissant de meilleurs résultats.
Des capteurs dispersés à partir d'un avion sur une forêt peuvent signaler un éventuel début d'incendie dans le champ d’acquisition; ce qui permettra une meilleure efficacité pour la lutte contre les feux de forêt. Dans les champs agricoles 10, les capteurs peuvent être semés avec les graines. Ainsi, les zones sèches seront facilement identifiées et l'irrigation sera donc plus efficace. Sur les sites industriels, les centrales nucléaires ou dans les pétroliers, des capteurs peuvent être déployés pour détecter des fuites de produits toxiques (gaz, produits chimiques, éléments radioactifs, pétrole, etc.) et alerter les utilisateurs dans un délai suffisamment court pour permettre une intervention efficace. Une grande quantité de capteurs peut être déployée en forêt ou dans un environnement de conservation de la faune afin de recueillir des informations diverses sur l'état du milieu naturel et sur les comportements de déplacement. Il est ainsi possible "d'observer", sans déranger, des espèces animales difficiles à étudier dans leur environnement naturel et de proposer des solutions plus efficaces pour la conservation de la faune.
On pourrait imaginer que dans le futur, la surveillance des fonctions vitales de l'être humain serait possible grâce à des capteurs qui pourront être avalés ou implantés sous la peau. Actuellement, des micro-caméras qui peuvent être avalées existent 11. Elles sont capables, sans avoir recours à la chirurgie, de transmettre des images de l'intérieur d'un corps humain avec une autonomie de 24 heures. Les auteurs d'une récente étude, présentent des capteurs qui fonctionnent à l'intérieur du corps humain pour traiter certains types de maladies. Leur projet actuel est de créer une rétine artificielle composée de 100 capteurs pour corriger la vue. D'autres ambitieuses applications biomédicales sont aussi présentées, tel que : la surveillance du niveau de glucose, le monitoring des organes vitaux ou la détection de cancers. L'utilisation des réseaux de capteurs dans le domaine de la médecine pourrait apporter une surveillance permanente des patients et une possibilité de collecter des informations physiologiques de meilleure qualité, facilitant ainsi le diagnostic de quelques maladies.
Il est possible d'intégrer des nœuds capteurs au processus de stockage et de livraison. Le réseau ainsi formé, pourra être utilisé pour connaître la position, l'état et la direction d'un paquet ou d'une cargaison. Il devient alors possible pour un client qui attend la réception d'un paquet, d'avoir un avis de livraison en temps réel et de connaître la position actuelle du paquet. Pour les entreprises manufacturières, les réseaux de capteurs permettront de suivre le procédé de production à partir des matières premières jusqu'au produit final livré 12. Grâce aux réseaux de capteurs, les entreprises pourraient offrir une meilleure qualité de service tout en réduisant leurs coûts. Dans les immeubles, le système de climatisation peut être conçu en intégrant plusieurs capteurs dans les tuiles du plancher et les meubles. Ainsi, La climatisation pourra être déclenchée seulement aux endroits où il y a des personnes présentes et seulement si c'est nécessaire. Le système distribué pourra aussi maintenir une température homogène dans les pièces. Utilisée à grande échelle, une telle application permettrait de réduire la demande mondiale en énergie réduisant du même coup les gaz à effet de serre.
Les RCSFs intéressent de plus en plus de chercheurs et d’industriels, en raison des nombreux défis qui surviennent. Par exemple, la topologie dynamique des RCSFs, la limitation des ressources des capteurs (par exemples : énergie, calcul, mémoire et bande passante) et les risques d’endommagement de ces derniers (par exemple : dans un feu de forêt). Un problème difficile particulièrement intéressant est la Qualité de Service (QdS) pour les RCSFs, où il s’agit de garantir une certaine qualité dans le service en se basant sur des critères quantitatifs et qualitatifs. La conception de RCSF est influencée par de nombreux paramètres 13:
Les capteurs utilisent leur réserve d’énergie à des fins de calcul et de transmission de données. La durée de vie d’un capteur dépend essentiellement de celle de sa batterie. Dans un RCSF, chaque noeud joue le rôle d’émetteur et de routeur. La défaillance énergétique d’un capteur peut changer significativement la topologie du réseau et imposer une réorganisation coûteuse de ce dernier 14.
Certains nœuds peuvent être défaillants ou inhibés à cause d’un manque d’énergie, d’un dommage physique ou d’une interférence. Ceci ne doit pas affecter la globalité de la tâche du réseau de capteurs. En cas de défaillance, de nouveaux liens et routes doivent être établis pour assurer la collecte des données. La redondance peut également être utilisée, tout en veillant à conserver une faible consommation d’énergie.
Chaque nœud perçoit une vue locale de son environnement, limitée par sa portée et sa précision. La couverture d’un vaste espace déterminé est donc composée de l’union de nombreuses couvertures de petite taille.
C’est un facteur dépendant de l’application qui affecte grandement les protocoles de routage. Le déploiement peut être déterministe ou aléatoire. Dans la première stratégie, les capteurs sont placés manuellement et les données peuvent donc être acheminées via des chemins prédéterminés. En revanche, avec une approche aléatoire, les capteurs sont éparpillés (e.g. largués d’un avion). Dans le cas d’une répartition non uniforme, une stratégie de groupement (clustering) peut s’avérer nécessaire.
La capture d’informations et la couverture des données requises dépendent essentiellement de l’application. Elles peuvent être classifiées selon différents modèles : en fonction du temps (surveillance périodique), des événements (réaction à l’occurrence d’un événement particulier), des requêtes (réponse à une demande d’une station de base) ou de manière hybride (combinaisons des précédentes approches).
Dans de nombreuses études, tous les capteurs d’une application sont considérés homogènes (i.e. même capacité de calcul, de communication et d’énergie). Néanmoins, en fonction de l’application, certains capteurs peuvent avoir des rôles différents, générant une architecture hétérogène. Par exemple, dans un RCSF hiérarchique, certains capteurs sont déclarés « chef » de leur groupe. Le routage vers les stations de base est alors traité par ces derniers.
Le nombre de capteurs déployés peut être de l’ordre de la centaine ou du millier, et vraisemblablement plus dans un futur proche. Les algorithmes de routage doivent donc être capables de fonctionner efficacement avec une grande quantité de capteurs. De plus, ces algorithmes doivent traiter un grand nombre d’événements sans être saturés.
La plupart des architectures réseau reposent sur des capteurs statiques. Pourtant, la mobilité des stations de base et/ou des capteurs est parfois nécessaire dans de nombreuses applications. La transmission de messages en provenance, ou vers, un noeud mobile est un autre défi. La capture peut être aussi bien statique que dynamique, dépendant de l’application (traque d’ennemis. surveillance de feux de forêt).
La plupart des RCSFs possèdent une densité importante de capteurs, excluant ainsi l’isolement de noeuds. Pourtant, le déploiement, la mobilité et les défaillances font varier la topologie du réseau, dont la connexité n’est pas toujours assurée.
De nombreux capteurs peuvent générer de la redondance dans les mesures effectuées. L’agrégation de paquets similaires en provenance de différents noeuds permet de réduire le nombre de transmissions (e.g. suppression de duplicata, minimum, moyenne, maximum, ...). Un traitement du signal peut également être effectué pour l’agrégation par fusion de données.
La recherche dans le domaine des capteurs subit actuellement une révolution importante, ouvrant des perspectives d'impacts significatifs dans de nombreux domaines d'applications. Cette diversité amène ces réseaux à supporter différents types de trafics et à fournir des services qui doivent être à la fois génériques et adaptatifs aux applications car les propriétés de la qualité de service (QdS) différent d'un type d'applications à un autre. Certaines applications exigent un certain niveau de qualité de services (QdS) pour délivrer le contenu. Jusqu’ à présent, le besoin de réduire au minimum la consommation d’énergie a fait objet de la plupart des recherches dans les réseaux de capteur. Peu d’études dans le domaine concernent les mécanismes pour délivrer efficacement la QdS au niveau applicatif à partir de métriques de niveaux réseau et liaison comme le délai ou la bande passante.
Les RCSFs sont plus vulnérables aux attaques que les réseaux filaires classiques. Cela se justifie par le fait que le contrôle des données transférées doit être minimisé pour limiter la surcharge du réseau. De plus, comme les messages envoyés transitent par plusieurs nœuds, il est difficile d’assurer qu’aucun nœud qui participe au routage n’accède à l’information véhiculée ou pire la modifie.
Il est d'une importance fondamentale pour le développement commercial des RCSFs pour fournir des services qui permettent l'interrogation du réseau pour récupérer des informations utiles à partir de n'importe où et à n'importe quel moment. Pour cette raison, les RCSFs du future seraient accessible à distance à partir de l'Internet, et devront donc être intégrés à l'architecture IP.
Les nœuds du réseau de capteurs sont en général éparpillés dans le milieu à étudier. Chacun d’entre eux à la possibilité d’acquérir, traiter et transmettre ces données vers un point de collecte, afin qu’elles soient acheminées vers l’utilisateur final. Il existe deux types d’architecture plate et hiérarchique 15.
Un RCSF plat est un réseau homogène, où tous les nœuds sont identiques en terme de ressources (matériel), excepté le Sink qui joue le rôle de nœud puits et qui est responsable de la transmission de l’information collectée à l’utilisateur final. En présence d’un très grand nombre de nœuds (densité de capteurs élevée), une communication multi-sauts peut être nécessaire pour l’architecture plate (Figure I.4).
Abbildung in dieser Leseprobe nicht enthalten
Figure I.4: Réseau de capteurs sans fil Plat
Pour réduire le coût et la complexité de la plus part des nœuds, introduction d’un ensemble de nœuds plus puissants. L’agrégation de nœuds en clusters permet de réduire la complexité des algorithmes de routage, d’optimiser la ressource médium en faisant gérer localement par un chef de cluster, de facilité l’agrégation des données, d’optimiser les dépenses d’énergie, et enfin de rendre le réseau plus scalable (Figure I.5).
Abbildung in dieser Leseprobe nicht enthalten
Figure I.5: Réseau de capteurs sans fil Hiérarchique
Le développement de ces réseaux de capteurs constitue très certainement une prochaine étape dans l'évolution des technologies de l'information. En effet, les évolutions technologiques et techniques rendent envisageables les réseaux de capteurs autonomes énergétiquement, ce qui est un point crucial pour leur intérêt pratique. De plus, les réseaux de capteurs s'insèrent dans un mouvement axé sur la diversification des objets communicants. Cette évolution provient de la constatation que les capacités de calcul et de stockage sont en passe de ne plus être considérées comme des ressources rares. La tendance va donc vers une multiplication d'objets intelligents, dotés de capacités de stockage et de traitement, et vers plus d'intercommunication entre objets et plus d'interfaces avec le monde physique Notons également que la nécessité pour les réseaux de capteurs de se limiter uniquement à des applications très bas débit n'apparaît pas comme un véritable problème, et ne va pas nécessairement à l'encontre de l'évolution des technologies de l'information. Pour s'en convaincre, citons le succès des SMS (messages courts échangés entre téléphones portables) qui sont très simples, pratiques et utiles, alors que les puissantes et complexes applications 3G haut débit ont toujours beaucoup de mal à percer. On se trouve donc dans le cas où ce type de réseaux est techniquement réalisable et s'inscrit dans l'ère du temps. C'est pourquoi il y a fort à parier que ce genre de réseaux donnera lieu à de multiples applications concrètes dans un futur proche.
La communication dans les réseaux de capteurs est soumise à divers phénomènes qui caractérisent les communications par ondes radio. Le plus connu est une forte atténuation du signal avec la distance, qui empêche deux nœuds trop éloignés l’un de l’autre de communiquer ensemble et force l’utilisation de mécanismes multi-sauts. De même, la corruption de messages lorsque deux nœuds trop proches émettent simultanément (collision) et le problème du nœud caché et nœud exposé sont des phénomènes propres aux réseaux sans fil. Le routage dans les réseaux de capteurs diffère du routage traditionnel, car le mode de communication dans les réseaux de capteurs est du type “plusieurs vers un” (n − to − one), ou “un vers plusieurs” one − to − n, c’est à dire que les informations recueillies par les capteurs sont ensuite centralisées vers une passerelle. Les flux qui transitent sur le réseau ont pour unique destination la passerelle. Cette dernière centralise les informations recueillies par les capteurs. Dans ce chapitre nous exposons les différents protocoles de routage propres aux RCSFs existants dans la littérature. Ensuite on présente les techniques de routage dans les piles de protocole des RCSFs (Zigbee et 6LowPan). Puis nous exposons quelques algorithmes de routage basés sur l’optimisation par colonie de fourmis.
Le routage consiste à découvrir un chemin entre source et destination. Les protocoles de routage proposés dans la littérature pour les RCSFs peuvent être classifiés selon sept concepts (figure II.1): selon la topologie du réseau, selon le fonctionnement du protocole, selon les paradigmes de communication, selon l’établissement de la route, selon la mobilité, selon l’hétérogénéité et selon la couche réseau [16, 17, 18].
Abbildung in dieser Leseprobe nicht enthalten
Figure II.1 Taxonomie des protocoles de routage dans les RCSFs
La topologie détermine l’organisation des capteurs dans le réseau. Il existe quatre topologies dans les protocoles de routage pour les RCSFs : Graphe orienté acyclique, plate, hiérarchique et géographique.
Dans ce type de topologie, les nœuds construisent un graphe orienté acyclique dont le sommet est le nœud puits. Chaque nœud dans le graphe possède un ou plusieurs parents. Le choix des parents est réalisé à l’aide d’une fonction objective définit par l’utilisateur. Un exemple typique de protocole de routage formant ce type de topologie est le protocole RPL.
Dans une topologie plate, tous les nœuds possèdent le même rôle. Ils sont semblables en termes de ressources et collaborent entre eux pour accomplir la tâche de routage. Les réseaux plats permettent une grande tolérance aux pannes. En plus, les protocoles de routage sont généralement simples (ex : Flooding, Gossiping, SPIN, Directed Diffusion, Rumor routing, EAR, ACQUIRE, COUGAR,…), dans cette classe de protocoles on peut citer:
II.1.1.2.1. Flooding et Gossiping:
Chaque nœud recevant pour la première fois le message le transmet à ses voisins 19, si on suppose l’absence de collisions, ce processus aboutit à une couverture complète du réseau. Malheureusement, cet algorithme très simple n’est pas efficace car il requiert la participation de tous nœuds du réseau, alors que cela n’est pas toujours nécessaire. En conséquence, il conduit à une grande quantité de messages redondants et d’énergie gaspillée. Pour le gossiping le nœud récepteur envoie le message à un voisin choisi aléatoirement.
II.1.1.2.2. Le protocole SPIN:
Le protocole SPIN 20, permet de disséminer des informations sur le réseau de manière ciblée. Le fonctionnement du protocole SPIN permet de réduire la charge du réseau par rapport aux méthodes de diffusion traditionnelles tel que l’inondation ou l’algorithme de Gossiping. Le protocole SPIN utilise essentiellement trois primitives ADV (Advertise) /REQ (Request) /DATA. Un nœud voulant émettre une donnée commence par envoyer un paquet ADV. Les nœuds qui reçoivent ce paquet vérifient qu’ils n’ont pas encore répondu à cette demande auquel cas ils renvoient un paquet REQ. Le nœud qui a initié la communication envoie alors un paquet DATA pour chaque réponse REQ reçue (cf Figure.II.2). Un nœud peut parfaitement ne pas répondre aux sollicitations, par exemple dans le but d’économiser son énergie, sans pour autant mettre le fonctionnement du protocole en défaut. Ensuite chaque nœud qui fait office de relais peut très bien agréger ses propres donnés aux données qui sont déjà contenue dans le paquet.
Abbildung in dieser Leseprobe nicht enthalten
Figure II.2 : Le protocole SPIN. Le nœud A annonce ses données au nœud B (a). B répond par une requête (b). B reçoit les données requises (c). B fait de la publicité à ses voisins (d). Qui répondent par des requêtes (e-f)
II.1.1.2.3. Le protocole Directed Diffusion:
Une requête intérêt définie par une liste de couples attribut-valeur est diffusée par le sink vers ses voisins 21. L’intérêt contient aussi plusieurs champs gradients. Un gradient est un lien de réponse de la part des voisins recevant l’intérêt. En utilisant les intérêts et les gradients, plusieurs chemins peuvent être établis entre le sink et la source (cf FigureII.3). L’un de ces chemins est sélectionné par renforcement. Si ce chemin échoue un nouveau ou un alternatif doit être choisi.
Abbildung in dieser Leseprobe nicht enthalten
Figure II.3: Diffusion dirigée. (a) Propagation de l’intérêt. (b) Construction des gradients initiaux. (c) Livraison de données par renforcement.
II.1.1.2.4. Le protocole Rumor routing:
Son principe 22 est de transmettre les requêtes aux nœuds qui ont observé un événement particulier. Quand un nœud détecte un événement, il l’ajoute à sa table locale et génère un agent. L’agent parcoure le réseau afin de propager des informations sur les événements locaux aux nœuds distants. Quand un nœud génère une requête pour un événement, les nœuds qui connaissent l’itinéraire, peuvent répondre en se référant à leur table d’événement.
II.1.1.2.5. le protocole COUGAR:
C’est un protocole 23 qui voie le réseau comme un énorme système de base de données répartie. L'idée principale est d'employer des requêtes déclaratives afin d’abstraire le traitement des requêtes des fonctions de la couche réseau et d’utiliser l'agrégation de données pour économiser de l'énergie. L'abstraction est soutenue par une nouvelle couche de requête entre les couches réseau et application.
II.1.1.2.6. le protocole ACQUIRE:
L’approche 24 considère le réseau comme une base de données répartie bien adaptée pour les requêtes complexes. Une requête est expédiée par le Sink et chaque nœud recevant la requête peut répondre partiellement en employant l'information dans son cache ou recueillit l'information de ses voisins accessible par « d » sauts puis la transmit a un autre capteur. Une fois la requête complètement résolue, elle est renvoyée au Sink
II.1.1.2.7. Le protocole EAR
Une solution hybride pour la tolérance aux pannes est proposée dans le protocole EAR 25. Pour son concept préventif, EAR offre une meilleure conservation d'énergie et définit plusieurs chemins de routage afin de garantir une fiabilité du transport et d'augmenter la durée de vie du réseau. En outre, un mécanisme de recouvrement de pannes est implémenté. Le protocole EAR supporte des réseaux de capteurs à collecteurs multiples (plusieurs nœuds puits). Chaque nœud capteur génère un paquet RPT (Report) contenant des informations pour les intérêts et préférences de l'utilisateur. Les paquets RPT peuvent être envoyés vers n'importe quel collecteur. Cependant, pour chaque nœud intermédiaire le protocole de routage choisit le meilleur chemin qui réduit la consommation d'énergie et la latence.
II.1.1.3. Protocole de routage hiérarchique
Dans les réseaux hiérarchiques, les nœuds ont différents rôles. Une des méthodes les plus utilisées est le clustering. Il consiste en un partitionnement du réseau en groupes (cluster). Chaque groupe est constitué de nœuds simples et d’un nœud leader (cluster-Head). Seul le nœud leader communique avec les autres nœuds ou avec la station de base. Les avantages de ce type protocole sont la scalabilité, la durée de vie du réseau et la consommation efficace de l’énergie sont assurés, (ex : LEACH, PEGASIS, MECN, SMECN, TEEN, APTEEN,...) dans cette classe de protocoles on peut citer:
II.1.1.3.1. le protocole LEACH:
LEACH 26 est un protocole de routage destiné aux réseaux de capteurs. Son principal avantage est de minimiser la consommation énergétique des éléments du réseau. Le protocole LEACH est un protocole hiérarchique, car le réseau est divisé en clusters, et chaque cluster possède un nœud “maître”, le nœud maître est en charge de la gestion de son cluster. Il est élu périodiquement parmi les nœuds formant le cluster, en fonction de l’état de sa batterie. Un message qui est émis par un nœud au sein d’un cluster, est ensuite routé par le nœud maître vers la passerelle du réseau de capteurs. Si on considère que la distance entre le nœud maître et un nœud du cluster est faible, la puissance nécessaire à l’envoi d’un paquet entre eux est aussi faible qu’une communication directe entre un nœud et la passerelle. Le protocole LEACH permet ainsi en structurant le réseau de manière hiérarchique de proposer un protocole qui économise l’énergie d’un capteur désirant émettre un paquet.
II.1.1.3.2. le protocole PEGASIS:
PEGASIS 27 est une amélioration du protocole LEACH. Au lieu de former plusieurs clusters, PEGASIS forme des chaînes de nœuds de sorte que chaque nœud transmet et reçoit d'un voisin et seulement un nœud est choisi parmi cette chaîne pour transmettre au Sink. Les données recueillies se déplacent d’un nœud à un autre, seront agrégées puis envoyées au Sink par un nœud leader. Dans le PEGASIS hiérarchique les nœuds construisent une chaîne qui forme un arbre hiérarchique, et chaque nœud leader choisi dans un niveau particulier transmet des données aux nœuds dans le niveau supérieur de la hiérarchie jusqu’à atteindre la station de base.
II.1.1.3.3. le protocole TEEN et APTEEN
TEEN 28 est un protocole hiérarchique développé afin de répondre aux besoins de réseaux réactifs. En effet, la plupart des protocoles considèrent que les capteurs ne doivent transmettre l’information qu’au bout d’un certain temps. Autrement dit, les délais de transmission d’une information peuvent être longs. De plus, il s’ensuit que certaines mesures sont transmises inutilement, puisque n’intéressant pas la “gateway”. Les auteurs de 28 ont donc proposés l’algorithme de remontée d’information suivant : une fois les clusters formés, la tête de cluster transmet deux seuils aux différents nœuds. Ces deux seuils, notés HT (Hard Treshosld), ST (Soft Tresholds) permettent aux capteurs de savoir s’il doit remonter l’information : le HT est la valeur minimum de la grandeur mesurée, au-delà de laquelle le capteur est susceptible de transmettre l’information. Lorsque ces valeurs sont au-dessus du HT, le capteur ne transmet l’information que si la valeur courante diffère d’au moins ST unités de la valeur précédemment transmise. On peut donc contrôler le nombre de paquets envoyés en jouant sur ces deux valeurs. TEEN permet donc de construire un protocole réactif, ce qui permet d’économiser de l’énergie. APTEEN 29 permet de trouver un compromis entre les protocoles proactifs (envoi de l’information à dates données) et les protocoles réactifs (envoi de l’information suivant différents critères). L’idée simple de (APTEEN) est de rajouter aux deux seuils précédemment décrits une troisième valeur, TC qui sera le temps maximal entre deux envois d’information mesurés. On assure ainsi qu’un capteur toujours vivant envoie périodiquement de l’information.
II.1.1.3.4. le protocole MECN et SMECN
MECN 30, utilise le GPS à basse puissance. L'idée principale est de trouver un sous-réseau, qui aura moins de nœuds et exige moins de puissance pour la transmission entre deux nœuds particuliers quelconques. SMECN (small MECN) est une extension de MECN. Le sous-réseau construit par SMECN est probablement plus petit (en termes de nombre d’arcs) que celui construit par MECN si les diffusions peuvent atteindre tous les nœuds dans une région circulaire autour du diffuseur.
II.1.1.4. Protocole de routage géographique
Les protocoles de routage géographique ont comme caractéristique commune deux étapes distinctes : la localisation d’un nœud et l’acheminement ou le routage des paquets vers ce nœud. Dans la première étape, il est nécessaire que le nœud source détermine la position géographique du nœud destinataire avant d’envoyer des paquets de données. L’acheminement ou le routage par un nœud est essentiellement basé sur la position de ses voisins immédiats du nœud destinataire. Les positions des voisins sont généralement connues, car chaque nœud envoie périodiquement sa position à ses voisins immédiats. Par ailleurs, la position des nœuds peut être communiquée par un satellite utilisant GPS si chaque nœud du réseau est équipé d’un GPS, (ex : GAF, GPSR, SAR, SPEED, GEAR,…) dans cette classe de protocoles on peut citer:
II.1.1.4.2. le protocole GAF:
GAF 31 conserve l'énergie par la mise en veille des nœuds inutiles dans le réseau sans affecter le niveau de fidélité du routage. Il forme une grille virtuelle pour le domaine couvert. Chaque nœud emploie sa position indiquée par le GPS pour s'associer à un point dans la grille virtuelle. Des nœuds liés au même point sur la grille sont considérés équivalents en termes de coût de routage. Une telle équivalence est exploitée en maintenant quelques nœuds situés dans un secteur particulier de la grille dans l'état de sommeil afin d’économiser de l’énergie.
II.1.1.4.3. le protocole GEAR:
L'idée est de restreindre le nombre d'intérêts dans la diffusion dirigée en considérant seulement certaine région plutôt que d'envoyer les intérêts au réseau entier 32.
II.1.1.4.4. Le protocole GPSR
Le protocole GPSR 33 a été, à l'origine, conçu pour les réseaux Ad-Hoc mobiles (MANETs) mais il a été rapidement adapté pour les RCSFs. Le protocole GPSR utilise les coordonnées des nœuds pour le routage. Ce protocole utilise deux stratégies différentes pour le routage: Transmission Gloutonne (Greedy Forwarding) et Transmission de Périmètre (Perimeter Forwarding). Avec le mode de transmission gloutonne, quand un nœud reçoit un paquet, il choisit le voisin le plus proche de la destination pour lui transmettre le paquet. Parfois, le nœud se trouve plus proche de la destination que tous ses voisins mais la destination finale reste inaccessible en un seul saut. Le nœud est, dans ce cas, face à un "trou". Les trous se forment à cause du déploiement aléatoire, de la présence d'obstacles radio, ou de la défaillance des nœuds. Pour pallier à ce problème, la transmission de périmètre est utilisée pour router le paquet autour du trou. Les paquets se déplacent, alors, autour du trou jusqu'à arriver à un nœud plus proche de la destination. A partir de là, la transmission gloutonne reprend la main.
Les protocoles de routage peuvent être classifiés selon leurs fonctionnalités en quatre catégories : routage basé sur la Qualité de service, routage basé sur les requêtes, routage basé sur les multi-chemins, routage basé sur la négociation et routage basé sur l’agrégation.
Dans les protocoles de routage base sur la QdS, le réseau doit équilibrer entre la consommation énergétique et la qualité de données. En particulier, le réseau doit satisfaire certaine métrique de QdS, par exemple : délai, réserve d’énergie, la bande passante disponible, etc. les protocoles de cette approche sont très recommandés pour la surveillance, on peut citer:
II.1.2.1. 1. Le protocole SAR:
Le protocole SAR est basé sur une approche multi-chemins géré par table qui s’efforce à réaliser l'efficacité énergétique et la tolérance aux fautes. SAR 34 crée des arbres en prenant en compte la métrique QdS, ressource énergétique sur chaque chemin et le niveau de priorité de chaque paquet. En utilisant ces arbres, des chemins multiples du Sink aux capteurs sont formés. Un de ces chemins est choisi selon les ressources énergétiques et QdS du chemin. SAR maintient multiples chemins des nœuds au Sink.
II.1.2.1.2. Le protocole SPEED:
Selon 35, le protocole exige de chaque nœud de maintenir des informations sur ses voisins et emploie une transmission géographique pour trouver les chemins. En outre, SPEED s’efforce d'assurer une certaine vitesse pour chaque paquet dans le réseau de sorte que chaque application puisse estimer le délai bout à bout pour les paquets en divisant la distance au Sink par la vitesse du paquet avant de prendre la décision d'admission. SPEED peut éviter la congestion quand le réseau est encombré.
Dans ce type de routage, un nœud génère des requêtes afin d’interroger les capteurs. Ces requêtes sont exprimées soit par un schéma valeur-attribut ou bien en utilisant un langage spécifique. Les nœuds qui détiennent les données requises doivent les envoyer au nœud demandeur à travers le chemin inverse de la requête (ex SPIN, Directed Diffusion, Rumor routing, COUGAR,…).
Dans cette catégorie, les protocoles de routage utilisent des chemins multiples afin d’augmenter la performance du réseau. La fiabilité d’un protocole peut être mesurée par sa capacité à trouver des chemins alternatifs entre la source et la destination en cas de défiance du chemin primaire (ex : SPIN, Directed diffusion,…).
En détectent le même phénomène, les nœuds capteurs inondent le réseau par les mêmes paquets de données. Ce problème de redondance peut être résolu en employant des protocoles de routage basés sur la négociation. En effet, avant de transmettre une information, les nœuds capteurs négocient entre eux leurs données en échangeant des paquets de signalisation spéciales, appelés métadonnées. Ces paquets permettent de vérifier si les nœuds voisins disposent déjà la donnée à transmettre. Cette procédure garantit que seules les informations utiles seront transmises et élimine la redondance de données (ex : SPIN, Directed diffusion, SAR, SPAN,…). Avec Span 36, le routage est assuré par un ensemble de nœuds dominants connectés. Un ensemble dominant connecté d’un réseau est un sous ensemble de nœuds dits coordinateurs, tel que chaque nœud dans le réseau est soit membre de l’ensemble dominant ou est voisin d’un nœud coordinateur. Les coordinateurs sont tout le temps dans l’état inactif, tandis que les nœuds non- coordinateurs qui sont en mode sommeil se réveillent périodiquement pour échanger du trafic avec les coordinateurs et pour participer dans l’élection de ces derniers. Les coordinateurs agissent comme des stations de base par rapport aux nœuds non-coordinateurs qui se trouvent en mode sommeil en conservant le trafic destiné à ces derniers jusqu’à ce qu’ils se réveillent. La stratégie SPAN est proactive ; les nœuds échangent périodiquement des messages Hello pour permettre la découverte des voisins. Un nœud marque soit même comme éligible d’être coordinateur, s’il trouve que deux parmi ses voisins ne peuvent pas communiquer ni directement ni à travers un ou deux coordinateurs. Chaque nœud marqué comme éligible attend pour un intervalle du temps en écoutant les notifications (pour être coordinateurs) des autres nœuds. Si ce nœud reste éligible après cet intervalle du temps, il envoie sa propre notification. Les nœuds les plus utiles (qui connectent plus de paires de nœuds) et les plus riches en énergie se déclarent comme coordinateurs plus rapidement. Un nœud qui a passé un certain temps comme coordinateur se retire pour donner de la chance à d’autres nœuds pour être coordinateurs. Cela permet d’équilibrer la consommation d’énergie entre les nœuds dans le réseau.
L’agrégation permet de minimiser le nombre d’envois des données identiques par plusieurs nœuds voisins et de répartir le traitement de ces données au niveau de chaque nœud afin d’acheminer vers la destination finale. Un nœud agrégateur combine les données provenant de plusieurs nœuds en une information significative. Sachant qu’un calcul consomme moins d’énergie qu’une communication, on prolonge la durée de vie du système en minimisant la quantité de données transmises (ex : SPIN, Directed diffusion, SAR, Rumor routing, COUGAR, LEACH,…).
Dans les RCSFs, il existe trois paradigmes de communication : centré nœud (Node centric), centré donnée (data centric) et centré position (position centric).
Dans les protocoles centrés nœud, le routage est basé sur l’identification des nœuds. Chaque source est traitée indépendamment. Chaque capteur source qui a les données appropriés répond en envoyant ses données à la station de base indépendamment de tous les autres capteurs. Ce paradigme est beaucoup plus employé dans les réseaux conventionnels, où les communications se basent sur l’identification des nœuds participants. Mais pour les RCSFS, un routage basé sur une identification individuelle des nœuds ne reflète pas l’usage réel du réseau. Pour cela, un autre paradigme a été introduit: centré donnée. Néanmoins, le paradigme centré nœud n’est pas à exclure totalement, car certaines applications nécessitent une interrogation individuelle des capteurs (ex : COUGAR, LEACH,…).
Dans les protocoles centrés donnée, le routage est effectué en fonction du contenu du paquet. Les nœuds capteurs s’intéressent uniquement à la donnée reçue sans toutefois se préoccuper du nœud qui est l’origine de cette donnée. En plus, les capteurs intermédiaires peuvent exercer une certaine forme d’agrégation sur ces données avant de les acheminer vers la station de base. Ainsi, le réseau peut être vu comme une base de données distribuées, où les nœuds forment des tables virtuelles, alimentées par les données captées (ex : SPIN, Directed diffusion).
Dans ce paradigme, les décisions de routage sont établies selon la position des nœuds la distance entre les nœuds voisins peut être estimée sur la base de la puissance signal arrivé. Cependant, les nœuds peuvent connaitre leur position grâce à un équipement GPS ou par un système de positionnement distribué. Par conséquent, ce type de mécanisme nécessite un déploiement d’une solution de positionnement, dont le degré de précision requis dépend de l’application ciblée (ex : GAF, SPEED, GEAR, SAR,…).
Suivant la manière de création et de maintenance des routes lors de l’acheminement des données, les protocoles de routage peuvent être classés en trois catégories : les protocoles proactifs, réactifs et hybrides.
Dans les protocoles proactifs, les routes sont créées à l’avance dans la phase d’initialisation. Chaque nœud du réseau maintient une table de routage pour toutes les destinations indépendamment de l’utilité des routes. Si un changement de topologie survient, la modification des tables de routage doit être diffusée. Ce type de protocole est adapté aux applications qui nécessitent un prélèvement périodique des données. Et par conséquent, les capteurs peuvent se mettre en veille pendant les périodes d’inactivité et n’enclencher de capture qu’à des instants particuliers (ex : OLSR, LEACH, PEGASIS,…).
Les protocole réactifs créent et maintiennent des routes à la demande. Lorsque le réseau a besoin d’une route, une procédure de découverte de route est lancée. Ce type de protocole est pratique pour les applications temps réel où les capteurs doivent réagir immédiatement à des changements soudains des valeurs captées (ex : SPIN, Directed diffusion, COUGAR, AODV, LOAD,…).
Les protocoles hybrides utilisent une combinaison des deux principes. Par exemple, ils utilisent le principe des protocoles proactifs pour apprendre le proche voisinage, ainsi, ils disposent de routes immédiatement dans le voisinage. Au-delà du voisinage, le protocole hybride fait appel aux principes des protocoles réactifs pour chercher des routes (ex : ZRP, APTEEN,…).
Dans les RCSFS, les nœuds capteurs situés à proximité du nœud puits épuisent rapidement leur batteries parce qu’ils servent de relais pour tous les paquets qui doivent être transmises au nœud puits. Dans les protocoles de routage basés sur la mobilité, le nœud puits se déplace aléatoirement de temps en temps dans le réseau afin d’équilibrer la dépense énergétique des différents nœuds du réseau, dans cette classe en peut citer:
Le protocole SEAD 37 prend en charge le transfert des données à partir d'une source fixe vers un Sink mobile via un réseau de nœuds stationnaires. L'architecture de SEAD commence par un nœud source qui construit son propre arbre de diffusion. Dans le cas de plusieurs nœuds source, il y a plusieurs arbres de diffusion. Le nœud Sink ne fait pas partie de l'arbre; au contraire, il crée une relation avec le nœud le plus proche appartenant à l'arbre. Le nœud le plus proche du Sink devient son nœud d'accès, qui vise à transférer les données de base par l'intermédiaire de l'arbre de diffusion. Une fois que les données sont disponibles au niveau du nœud d'accès, ce dernier transmet ces données vers le Sink. SEAD est très souple, car il permet au Sink de se déplacer et de changer son nœud d'accès. Le nœud d'accès change une fois que le seuil de distance entre le Sink et son nœud d'accès est atteint. La valeur de ce seuil permet de faire un compromis entre le délai du trajet et l'énergie consommée lors de la reconstruction de l'arbre. SEAD permet également la réduction du trafic réseau en étant capable d'envoyer des données sur plusieurs nœuds Sink.
Le protocole TTDD 38 est similaire à SEAD, les nœuds formant le réseau sont stationnaires et le réseau contient plusieurs Sink mobiles. La figure II.4 représente le flux de données TTDD. Au début chaque source construction sa structure de grille (un seul niveau). Une fois que la structure de grille est établie, les données demandées par le sink inondent la cellule locale pour trouver le nœud de diffusion de la cellule (c'est à dire le nœud le plus proche du sommet de la cellule virtuelle). Une fois le nœud de diffusion trouvé, le chemin entre le Sink et la source est établie. TTDD permet la réduction du trafic de données en demandant que les requêtés identiques provenant de différents nœuds Sink (voir Noeud G).
Abbildung in dieser Leseprobe nicht enthalten
Figure II.4 : flux de données TTDD
Le protocole DATA MULE 39 définit des nœuds mobiles spéciaux appelés MULE qui se déplacent à travers le réseau et choisit les données à partir des nœuds trouvés à proximité. Les transferts à courte portée peuvent utiliser les technologies de communication prometteuse telle qu’Ultra-Wide band (UWB) radios. En mettant en place des transferts de données à partir de la source vers le Sink via des MULE de données mobiles. Par conséquent, il y a une perte d’énergie importante en raison de l'écoute en continu nécessaire pour identifier le passage du MULE. En outre, la latence des données est élevée en raison du fait que les nœuds Sink doivent d'abord attendre les nœuds de source pour décharger les données et ensuite attendre MULE pour fournir les données. Cependant, un avantage important réside dans le faible coût de la mise en place et l'entretien du réseau.
Dans cette classe de protocole. Les nœuds de capacités différentes coexistent dans le réseau. Les nœuds puissants sont chargés de collecter et de router des données perçues par d’autres capteurs plus limités en énergie et capacité, dans cette classe en peut citer:
Le protocole CHR 40 utilise un seul Sink et deux types de capteurs pour former un réseau hétérogène, un grand nombre de capteurs moins puissant (base gamme), désignés par L-capteurs, et un petit nombre de capteurs puissants (haute de gamme), noté H-capteurs. Les deux types de capteurs sont statiques et utilisant un service de localisation. De plus, ces H- capteurs sont uniformément et aléatoirement distribuées dans la zone d’intérêt. Le protocole CHR partitionne le réseau hétérogène en groupes de capteurs (ou clusters), chacun étant composé de L-capteurs et dirigé par un H-capteur. Dans un cluster, les L-capteurs sont chargés de la détection et la transmission de paquets de données émis par d'autres L-capteurs vers le chef de cluster en multi-sauts. Les H-capteurs sont responsables de la fusion de données au sein de leurs propres groupes et la transmission de paquets de données agrégées provenant d'autres chefs de cluster en multi-sauts vers le Sink. Alors que L-capteurs utilisent la transmission de données à courte portée de leurs H-capteurs voisins dans le même cluster, les H-capteurs effectuent la communication de données à longue portée à d'autres H-capteurs voisins et le Sink.
Dans IDSQ 41 le réseau de capteurs est composé de nœuds hétérogènes, afin de maximiser le gain d’information, minimiser la latence de détection et de la consommation d'énergie pour la localisation des cibles et le suivi par l'interrogation de capteur dynamique et le routage de données. Pour économiser l'énergie, un seul sous-ensemble de capteurs doit être actif quand il y a des événements intéressants à signaler dans certaines parties du réseau. Le choix d'un sous-ensemble de capteurs actifs qui ont le plus d'information utile est équilibré par le coût de la communication nécessaire entre les capteurs. Des informations utiles peuvent être recherchées sur la base de la prévision dans l’espace et le temps des événements intéressants. Dans le protocole IDSQ, la première étape consiste à sélectionner un chef de cluster. Ce chef sera responsable de la sélection des capteurs optimaux basés sur une certaine mesure de l'utilité de l'information.
Cette approche est basée sur deux idées principales 42, CADR et IDSQ. CADR est réalisé en activant seulement les capteurs qui sont proches d'un événement particulier et en ajustant dynamiquement les chemins de données. Dans CADR, chaque nœud évalue un objectif information/coût et conduit les données suivant le gradient local et les besoins de l’utilisateur final. Dans IDSQ, le nœud demandeur peut déterminer quel nœud peut fournir l'information la plus utile avec un avantage additionnel d'équilibrer le coût énergétique.
Dans les RCSFs, les protocoles de routage utilisent la pile de protocole 6LowPan effectuant le routage soit au niveau de la couche adaptation (Mesh Under) ou soit au niveau de la couche réseau (Route Over) 43.
Ici, le routage s’effectue au niveau de la couche adaptation. Il est basé sur les adresses MAC et se fait avec les fragments du paquet IPv6. Dans ce cas, le paquet IPv6 n’est reconstitué que sur l’équipement destinataire. Pour envoyer un message (figure II.5), l’identification du nœud destinataire est utilisée et le message est transmis de proche en proche jusqu’à la destination finale (ex : AODV, LOAD, Dymolow, Hilow,…). Dans cette classe on peut citer:
II.1.7.1.1.
Le protocole de routage LOAD 44 est une version simplifiée du protocole AODV. LOAD n’utilise pas le numéro de séquence de la destination comme AODV dans les MANET. Pour éviter les boucles de routage, seule la destination génère des paquets de réponse de route (RREP). Une route est choisie par LOAD si le nombre de liens faible et le nombre de sauts sont petits le long du chemin de la source à la destination. En cas de rupture de liens, les nœuds tentent de réparer la route localement par broadcaste d’un message RREQ et un message RREP par unicast. Si le nœud ne peut pas réparer un lien localement, il envoi en monodiffusion (unicast) un RERR avec un code d'erreur qui indique la raison de l'échec de la réparation à l'expéditeur du message de données. Il ne nécessite pas de liste de précurseur comme le cas utilisé dans AODV pour transmettre les messages RERR. Il demande à la couche MAC un accusé de réception pour chaque message de données envoyé et est appelé en tant que Notification de couche de liaison (LLN). LOAD n'utilise pas le numéro de séquence la destination. La figure montre l'échange de messages dans le protocole LOAD.
Abbildung in dieser Leseprobe nicht enthalten
Figure II.5 Echange de messages dans le protocole LOAD
II.1.7.1.2. Le protocole DYMO-low
DYMO-low 45 est un protocole de routage dynamique pour les 6LoWPAN. Le protocole DYMO-low fournit une méthode efficace et simple basé sur AODV. DYMO effectue la découverte et l'entretien de route en utilisant des messages Route Request (RREQ), Route Réponse (RREP) et Route erreur (RERR). Le protocole de routage DYMO ne peut pas être appliqué directement dans 6LoWPAN en raison de son exigence en mémoire et de sa consommation énergétique. DYMO-low est un protocole de routage développé pour 6LoWPAN qui fonctionne directement sur la couche liaison pour créer une topologie maillée avec des dispositifs 6LoWPAN, de sorte que l’IP considère le WPAN comme un lien unique. DYMO- low utilise à la fois les adresses courtes de 16 bits de la couche liaison et les adresses étendues de 64 bits.
II.1.7.1.3. Le Protocole Hi-Low
Hi-Low 46 est un protocole de routage hiérarchique pour les 6LoWPAN. Il a était développé pour augmenter l'évolutivité des réseaux. L'une des caractéristiques distinctives de 6LoWPAN est l'affectation d’adresses de 16 bits courtes pour la norme IEEE 802.15.4. Hilow utilise des adresses de 16 bits courtes comme identifiant d'interface pour économiser de la mémoire et l’évolutivité du réseau. Hilow présente un modèle parent-enfant en initiant des procédures de numérisation. Chaque nœud du réseau, découvre son parent par diffusion d'un signal. S’il trouve un nœud parent 6LoWPAN dans son espace d'exploitation personnel (POS), alors il est associé avec le nœud parent 6LoWPAN en utilisant une adresse de 16 bits courte, sinon il se configure en tant que coordinateur (parent). Chaque nœud enfant dans le réseau reçoit son adresse de 16 bits à partir du nœud parent 6LoWPAN à condition que la règle suivante soit satisfaite:
Abbildung in dieser Leseprobe nicht enthalten
Lorsque le nœud courant veut envoyer un paquet à la destination, il détermine le nœud suivant pour transmettre le paquet. Une fois que la liaison est rompue, aucun mécanisme de rétablissement d'itinéraire n’est effectué pour réparer la route. Cela se traduit par la livraison non garantie de paquets dans le réseau.
Le routage se fait au niveau de la couche réseau où chaque nœud agit comme un routeur IP. Il est basé sur les adresses IPv6 et les tables de routage sont utilisées pour déterminer le chemin du paquet. Dans ce cas, le paquet IPv6 est reconstitué sur chaque équipement intermédiaire afin de prendre la décision de routage (ex : RPL,…).
On distingue deux piles de protocole dans les RCSFs : Zigbee et 6LowPan.
L’alliance ZigBee a été créée en 2002. C’est une association non lucrative de membres qui ont été parmi les premiers à croire au développement du marché des capteurs sans fils.
Zigbee est une alliance industrielle spécialisée dans les connexions de la grille de distribution de puissance électrique (Smart Grid), qui définit une suite de protocoles de hauts niveaux basée sur la norme IEEE 802.15.4. Elle définit les deux couches réseaux et applications et s’appuie sur la couche physique et la couche liaison des données spécifiées par IEEE 802.15.4. La pile Zigbee offre une solution de communication sans fil couplée avec un faible coût et une basse consommation d’énergie. Zigbee possède trois types de périphériques:
- Le coordinateur ZigBee (ZC):
- Un et un seul
- Tiers de confiance
- Racine du réseau et passerelle vers les autres réseaux
- Alimentation permanente
- Le routeur ZigBee (ZR):
- Equipement intermédiaire
- Qui route les paquets au sein du réseau
- Alimentation permanente
- L'équipement terminal Zigbee (ZED)
- Ne communique qu'avec un routeur ou le coordinateur
- Endormi la plupart du temps
La couche réseau supporte les topologies en étoile, en cluster et maillée. Dans la première, le réseau est contrôlé par le ZC qui, en plus des fonctions de création du réseau et de sa maintenance, assure la communication de tous les ZED entre eux. En effet, tous les autres nœuds ne communiquent qu’avec le ZC. Dans les autres topologies (cluster et maillée), le ZC est responsable de la création du réseau et de la définition de certains paramètres réseau.
La règle par défaut pour router une trame Zigbee est la suivante : si le nœud dispose d’une table de routage et s’il existe une entrée dans la table alors l’utiliser. Sinon, s’il n’existe pas une entrée dans la table et il existe une place libre alors, lancé une requête de découverte de route (Route Discovery). Sinon, router le long de l’arbre en utilisant le routage hiérarchique.
Les différents protocoles qu’on retrouve sous Zigbee sont (AODV, HERA, TR, ImpTR, Z-CAST)
6LoWPAN est le nom d’un groupe de travail crée afin de développer un réseau de communication utilisant IPv6 pour les systèmes embarqués à puissance limitée tels que les RCSFs, sur la couche physique IEEE 802.15.4. La pile 6LoWPAN comporte une couche adaptation qui permet de compresser les en-têtes et de fragmenter les paquets IPv6. Ipv6 définit un MTU (Maximum Transmission Unit) de 1280 octets, tandis qu’un paquet IEEE 802.15.4 ne compte que 127 octets. De ce fait, la couche adaptation permet d’implémenter une fragmentation de chaque IPv6 avant de l’envoyer sur la couche IEEE 802.15.4, et naturellement, d’implémenter la défragmentation à la réception. Tout comme Zigbee, 6LoWPAN comporte 3 types de nœud : Coordinateur, Routeur et Périphérique, et 3 types de topologies : étoile, hiérarchique et maillée.
Sous 6LoWPAN on distingue deux types de routage ( figure II.6) : Mesh-Under et Route-Over (cités précédemment). Plusieurs protocoles de routage ont été développés pour fonctionner sous 6LoWPAN. Parmi ces protocoles, nous pouvons citer:
- En Mesh-Under
- LOAD.
- DYMO-low.
- HiLOW.
- En Route-Over:
- RPL (Routing Protocol for Low power end lossy networks) 47. Nous nous intéresserons dans la suite au protocole RPL.
Abbildung in dieser Leseprobe nicht enthalten
Figure II.6 Schéma de routage 6LoWPAN
Les techniques développées pour le routage dans les réseaux de capteurs sont très nombreuses, et elles sont très fortement conditionnées par le type d’applications qui est souhaité. Toutes les problématiques définies dans le cadre des réseaux de capteurs ne sont pas intégralement résolues par les protocoles présentés précédemment. En effet le protocole LEACH résout le problème du passage à l’échelle du réseau en créant un algorithme de routage hiérarchique, ce qui permet de ne pas faire croître la complexité du réseau en fonction du nombre de nœuds, mais en fonction du nombre de degrés dans la hiérarchie mise en place. Mais la mise en place des clusters pour former la hiérarchie est un problème en soit, NP complet qui n’est pas résolu par ce protocole. Les protocoles basés sur la diffusion tels que SPIN et les algorithmes basés sur Gossiping sont des algorithmes qui sont très simples à mettre en œuvre et ils ne nécessitent pas la mise en place de politiques d’adressage complexes. Mais ces algorithmes eux ne peuvent être utilisés qu’avec quelques types de réseaux de capteurs pour lesquels il est facilement possible d’agréger les données qui sont transportées sur le réseau. Le routage géographique est pour sa part un protocole de routage qui résout les problématiques liées à la fois à l’adressage et à la complexité du réseau, mais il est très difficile de mettre en œuvre ce type de protocoles car cela implique que chaque noeud dispose d’un élément permettant de lui fournir une position précise et unique, même dans le cas d’une très forte densité de nœuds. Bien que la couche réseau ne soit pas encore définie par les autorités de normalisation, il semble que les protocoles utilisant des formations de réseaux en clusters tels que LEACH ou les principes définis dans les protocoles Bluetooth soient privilégiés. Mais ces techniques nécessitent une infrastructure protocolaire lourde et complexe, ainsi qu’une utilisation raisonnée de l’espace d’adressage; ce ne sont pas des principes en accord avec la philosophie des réseaux de capteurs. Les réseaux de capteurs sont des réseaux collaboratifs et très orientés vers un domaine d’application précis. Cela rend leurs structures beaucoup plus faciles à maîtriser que les réseaux ad hoc dans lesquels, à l’inverse des réseaux de capteurs, la mobilité et la nature très versatile des flux qui sont transportés rendent très difficile toute prévision. La mobilité du réseau rend elle-même la connectivité très peu maîtrisable. Par ailleurs, une structure bien établie rend également difficile toute modification de la couche réseau déjà existante. En revanche les réseaux de capteurs peuvent s’affranchir de cette complexité pour envisager d’autres modèles de piles de protocoles plus souples et moins hiérarchisés. Avec les réseaux de capteurs un pas de plus est franchi dans la direction de réseaux sans fil. Le déploiement de telles infrastructures, à la fois dynamiques et reconfigurables pose de nouveaux défis auxquels il faut répondre. Le manque de structure établie dans les réseaux sans fils conditionne les performances à la baisse. Pour pallier à cela, il est nécessaire de prendre en compte dans la conception de tels protocoles la modélisation des différents effets physiques qui interviennent dans le fonctionnement même du réseau.
Les métas heuristiques forment une famille d'algorithmes d'optimisation visant à résoudre des problèmes d'optimisation difficiles, pour lesquels des méthodes classiques plus efficaces ne sont pas connues. Elles sont généralement utilisées comme des méthodes génériques pouvant optimiser une large gamme de problèmes, sans nécessiter de changements profonds dans l'algorithme employé. Elles offrent un compromis intéressant entre la qualité des résultats et le temps de résolution. De nombreux métas heuristiques ont été développés depuis quelques années. Parmi ces dernières, nous comptons les algorithmes des colonies de fourmis proposées pour les problèmes d'optimisation combinatoire difficile. Les algorithmes à colonie de fourmis sont inspirés du comportement des fourmis réelles. Le comportement d'une colonie est beaucoup plus intéressant que celui d'une seule fourmi, en particulier dans les comportements collectifs de dépôt de phéromone et de suivi de traînée observés dans les colonies de fourmis. Les fourmis d'une colonie communiquent indirectement via des modifications dynamiques de leur environnement, les traînées de phéromone, et construisent ainsi une solution à un problème, en s'appuyant sur leur expérience collective et la manière pratiquée par les fournis pour trouver le plus court chemin entre la fourmilière et la source de nourriture. Le comportement des fourmis est un comportement collectif et collaboratif. Chaque fourmi a pour priorité le bien être de la communauté. Chaque individu de la colonie est à priori indépendant et n’est pas supervisé d’une manière ou d’une autre (système complètement distribué). La colonie est donc autocontrôlée par le biais de mécanismes relativement simples à étudier. En faisant une projection du comportement de ces insectes sur les caractéristiques des RCSFs, on remarque que le comportement des fourmis est bien adapté à ce type de réseaux et particulièrement lors du calcul des routes 48.
Dans l’algorithme AS 49, les fourmis sont placées sur les sommets du graphe (sur chaque ville). Elles se déplacent d’un sommet à l’autre en empruntant les arrêtes du graphe.
À chaque itération t (1<t<tmax), chaque fourmi k (k = 1,. ., m) parcourt le graphe et construit un trajet complet.
Pour chaque fourmi, le trajet entre une ville i et une ville j dépend de:
1. la liste des villes déjà visitées, qui définit les mouvements possibles à chaque pas, quand la fourmi k est sur la ville j :Jik
2. l’inverse de la distance entre les villes ηij = 1/ dij : appelée visibilité. Cette information statique est utilisée pour diriger le choix des fourmis vers des villes proches, et éviter les villes trop lointaines;
3. la quantité de phéromone déposée sur l’arête reliant les deux villes, appelée l’intensité de la piste τ ij (t). Ce paramètre définit l’attractivité d’une partie du trajet global et change à chaque passage d’une fourmi. C’est en quelque sorte une mémoire globale du système, qui évolue par apprentissage.
La règle de déplacement est la suivante:
Abbildung in dieser Leseprobe nicht enthalten
Où α et β deux paramètres contrôlant l’importance relative de l’intensité de la piste, τ ij (t), et de la visibilité, ηij. Avec α = 0, seule la visibilité de la ville est prise en compte; la ville la plus proche est donc choisie à chaque pas. Au contraire, avec β = 0, seules les pistes de phéromone sont utilisées. Pour éviter une sélection trop rapide d’un trajet, un compromis entre ces deux paramètres, jouant sur les comportements de diversification et d’intensification est nécessaire.
Après un tour complet, chaque fourmi laisse une certaine quantité de phéromones Δτijκ(t) sur l’ensemble de son parcours, quantité qui dépend de la qualité de la solution trouvée
Abbildung in dieser Leseprobe nicht enthalten
Où Tk(t) est le trajet effectué par la fourmi k à l’itération t, Lk(t) la longueur du tour et Q un paramètre fixé.
L’algorithme ne serait pas complet sans le processus d’évaporation des pistes de phéromone. En effet, pour éviter d’être piégé dans des solutions sous-optimales, il est nécessaire de permettre au système « d’oublier » les mauvaises solutions. On contrebalance donc l’additivité des pistes par une décroissance constante des valeurs des arêtes à chaque itération. La règle de mise à jour des pistes est donc
Abbildung in dieser Leseprobe nicht enthalten
Avec:
Abbildung in dieser Leseprobe nicht enthalten
m: est le nombre de fourmis.
La quantité initiale de phéromone sur les arêtes est une distribution uniforme d’une petite quantité τ 0 ≥ 0. La figure II.7 présente un exemple simplifié de problème du voyageur de commerce optimisé par un algorithme AS dont le pseudo code est présenté sur l’algorithme 2.1. Dans la figure 2.3, les points représentent les villes et l’épaisseur des arêtes représente la quantité de phéromone déposée: (a) exemple de trajet construit par une fourmi, (b) au début du calcul, tous les chemins sont explorés, (c) le chemin le plus court est plus renforcé que les autres, (d) l’évaporation permet d’éliminer les moins bonnes solutions.
Abbildung in dieser Leseprobe nicht enthalten
Figure II.7 Le problème du voyageur de commerce optimisé par l’algorithme AS.
Les étapes de l’algorithme de colonies de fourmis de base (Ant System) sont comme suit:
Abbildung in dieser Leseprobe nicht enthalten
Algorithme de colonies de fourmis pour le problème du voyageur de commerce.
Les auteurs de 50 proposent un algorithme appelé Contrôle à base de fourmis (ABC), qui est le premier système qui remplace les tables de routage avec des tables à phéromones. Les tables de phéromone ne contiennent donc pas explicitement des valeurs numériques quantitatives comme dans les ACOs mais l’effet produit reste identique puisque les phéromones des ACOs sont exprimées en probabilités lors de la procédure de choix des fourmis. Le but de cet algorithme est non seulement de trouver des routes relativement courtes mais aussi d’équilibrer la charge et d’éviter les congestions. Dans ABC, chaque nœud a une table de phéromone avec des probabilités pour chaque autre nœud dans le réseau (ce qui implique que chaque nœud est au courant de chaque autre nœud). Les fourmis sont lancées périodiquement par chaque nœud, chacun avec un nœud de destination aléatoire. Les fourmis se déplacer de nœud à nœud, en sélectionnant le nœud suivant pour passer en fonction des probabilités dans les tableaux de phéromone pour leur nœud de destination. En arrivant à un nœud, les fourmis mise à jour entries des valeurs de phéromone dans la table de ce nœud correspondant à leur nœud source. Les fourmis modifient donc la table pour augmenter le niveau de phéromone pointant vers leur nœud précédent, pour une fourmi de voyager à la fourmi de nœud source. Quand les fourmis parviennent à leur destination, ils meurent. Donc ABC a recours à une forme de routage à vecteur de distance. Bien qu'ABC soit un algorithme très simple, il a démontré que le méta heuristique d'ACO peut être efficacement utilisé pour le routage des paquets dans les réseaux à commutation de paquets.
Le principe d’AntNet se base sur l’algorithme ACO et sur les travaux de 51. L’algorithme AntNet utilise des agents mobiles (fourmis) qui ont pour but de détecter les encombrements dans le réseau, de trouver de nouvelles routes et de permettre ainsi aux routeurs de s’adapter aux changements du réseau.
Le principe général de l’AntNet est le suivant. A partir de chaque nœud ni, des fourmis sont lancés vers des destinations choisies aléatoirement, à des intervalles de temps régulier (Δt). Ces fourmis, appelées Forward Ants (FAnts), parcourent le réseau d’un nœud source à un nœud destination pour détecter les encombrements dans le réseau et trouver de nouvelles routes. Chaque FAnt a la capacité de mémoriser le chemin qu’elle traverse et le temps mis à le parcourir. Pour choisir le prochain nœud à visiter (soit nk), une FAnt positionnée sur un nœud (nj) se base essentiellement sur deux informations : le taux de phéromone présent sur le lien (nj, nk) et l’état de la file d’attente du routeur nk. Lorsqu’une FAnt arrive à destination, elle génère un autre type de fourmi, appelé BAnt (Backward Ant), et quitte la recherche. La BAnt va parcourir exactement le même chemin que sa congénère mais dans le sens inverse. Elle met à jour les tables de routage des nœuds traversés et les tables contenant certaines statistiques spécifiques à la charge du réseau en se basant sur les informations récoltées par la FAnt. Cependant, la BAnt va traverser les différents nœuds avec une priorité supérieure à celles des paquets. De ce fait, elle n’enregistre pas de retard sur son chemin. Une fois arrivée à la source, la BAnt est détruite. Le rôle de la BAnt est de mettre à jour les tables de routage. (Figure II.8)
Abbildung in dieser Leseprobe nicht enthalten
Figure II.8: Les fourmis en avant et arrière dans AntNet
Les différentes étapes de l’algorithme peuvent être résumées comme suit:
1. Tous les Δt, chaque nœud lance une fourmi FAnt et génère aléatoirement une destination (un nœud du graphe).
2. Chaque fourmi passe d’un nœud vers un autre selon une politique stochastique fonction du taux de phéromone sur le lien entre les deux nœuds et de l’information spécifique au problème qui est proportionnelle au taux de remplissage de la file d’attente entre les deux nœuds.
3. Chaque fourmi sauvegarde dans sa mémoire le parcours qu’elle a effectuée ainsi que le temps mis pour parcourir un lien entre deux nœuds. Le mémoire de la fourmi est une pile où sont empilées ces informations lors du passage d’un nœud vers un autre.
4. Lorsque la FAnt arrive à destination, elle génère une BAnt qui va recevoir toutes les informations récoltées par la FAnt et qui va parcourir le même chemin mais en sens inverse. La FAnt quitte la recherche.
5. Lors de son déplacement, la BAnt met à jour les tables de routage des nœuds visités.
Les auteurs 52 présentent une version élargie du système AntNet appelé système de routage à base d'agent (Agent-based Routing System). ARS maintient les principes de base du routage source mais ajoute le nombre de saute et des restrictions de bande passante pour produire un algorithme de routage restreint à la qualité de Service. Les deux restrictions suivantes ont été placées sur les fourmis en avant dans ARS:
- Si une fourmi en avant, ne pouvait pas sélectionner un nœud au prochain saut, depuis tous les liens sortants qui ne satisfont pas aux exigences de bande passante, donc la fourmi en avant meurt.
- Si une fourmi en avant a visité le même nœud au moins deux fois, alors la fourmi en avant meurt.
AntHocNet 53 est un algorithme de routage hybride pour les réseaux mobiles ad hoc construit autour du modèle des ACOs. Il est constitué à la fois d’un mécanisme proactif et d’un mécanisme réactif. Il ne maintient pas les routes entre toutes les paires de stations du réseau à tout instant comme le fait AntNet (dont il est fortement inspiré), mais maintient seulement les routes vers un ensemble de stations quand une demande d’échange de données est initiée. Dans une phase d’initialisation, l’algorithme adopte un comportement réactif où des agents « fourmis réactives » sont propagés dans le réseau à partir des sources, dans le but de trouver des chemins multiples vers les destinations. En accord avec le mécanisme des ACOs, les tables de routage des différentes stations sont considérées comme des pistes de phéromone dont les valeurs quantitatives rendent plus ou moins attractifs des chemins en fonction de leur qualité. Après la phase d’initialisation, les paquets de données sont transférés en choisissant des chemins de manière probabiliste et ce choix influencé par les tables de phéromone. En parallèle du transfert, une autre classe d’agents, les « fourmis proactives » est propagée dans le but de maintenir et de mettre à jour les tables de routage.
ACO est une méthode stochastique qui requiert de plus en plus l'attention de la communauté scientifique. Ce méta heuristique a prouvé sa performance pour plusieurs problèmes d'optimisation combinatoire. L'utilisation des traces de phéromone permet d'exploiter l'expérience de recherche acquise par les fourmis et ainsi renforcer l'apprentissage pour la construction de solutions dans les itérations futures de l'algorithme. En même temps, l'information heuristique peut guider les fourmis vers les zones prometteuses de l'espace de recherche. Un autre avantage d’ACO est que son domaine d'application est vaste. En principe, ACO peut être appliquée à n'importe quel problème d'optimisation discret pour lequel un mécanisme de construction de solution peut être conçu. Toutefois, ACO a ses propres inconvénients qui résident, principalement, dans les problèmes de paramétrage. En effet, ACO nécessite une instanciation des différents paramètres qui dépend du problème. Généralement, les paramètres correspondants aux meilleures solutions prouvées expérimentalement sont retenus.
Dans le domaine des RCSFs, de nombreux protocoles de routage ont été proposés dans la littérature, les travaux menés sur le support de la QdS ne sont pas très nombreux, la plupart de la communauté s’est focalisé sur des problèmes de l’énergie et des ressources limitées jugées plus importantes dans les applications de surveillance qui sont censées fonctionner pour de longues durées. Pourtant, il existe d’autres catégories d’applications qui ont de besoins de QdS très contraignants. Dans de ce chapitre, nous avons mis l’accent sur les principaux protocoles de routage dans les RCSFs. L’étude et l’analyse des principaux protocoles et approches de routage pour les RCSFs nous a permis de proposer nos approches pour optimiser la prise en compte de la QdS lors du routage, ainsi que les algorithmes et protocole qui en découlent.
[...]
