TG-LL
LES PROTOCOLES DE ROUTAGES DANS LES RCSF
Les protocoles de routages dans les RCSF
Introduction
Dans les RCSF, on doit assurer la fidélité de détection, de routage et de livraison. La fidélité de détection consiste à assurer la couverture de tout point de la zone d’intérêt par au moins un capteur. La fidélité de routage consiste à établir au moins un chemin entre tout capteur et la station de base alors que la fidélité de livraison permet d’assurer que les messages arrivent aux destinataires sans erreur.
Dans ce chapitre, on présente les critères de performances des protocoles de routage, une classification des protocoles de routage et les principaux protocoles sous-jacents à chaque classe.
Critères de performance des protocoles de routage dans les RCSF
La spécificité des RCSF a permis d’instaurer des critères de performances bien particuliers pour les protocoles de routage conçus à ce type de réseaux. Parmi ces critères, nous citons :
– Évolutivité: l’évolutivité est un facteur important dans les RCSF. Une zone de réseau n’est pas toujours statique, elle change selon les besoins des utilisateurs ou à cause de l’occurrence des pannes. A cet effet, tous les nœuds dans le domaine du réseau doivent être en mesure de s’adapter aux changements de la topologie.
– L’énergie: Les capteurs présentent une autonomie d’énergie et les batteries dont ils disposent sont rarement rechargeables et remplaçables. De ce fait, chaque nœud doit économiser la consommation de l’énergie pour assurer ses activités : la détection, le traitement, le stockage et la transmission. Par ailleurs, pour acheminer les paquets vers la station de base, il devra utiliser un protocole de routage performant en termes d’énergie. Ce protocole de routage doit en particulier minimiser le nombre de paquets transmis puisque la transmission est l’opération qui consomme plus d’énergie.
– Le temps de traitement: il se réfère au temps pris par le nœud dans le réseau pour assurer l’ensemble des opérations commençant par la détection, le traitement des données, leur stockage, leur transmission ou leur réception sur le réseau. En outre, l’information devrait y arriver au poste de contrôle dans une durée raisonnable en particulier pour les applications orientées événement.
– Le schéma de transmission: la transmission de données par les capteurs vers la destination ou la station de base se fait par un schéma de routage à un seul saut ou à multi-sauts. Par exemple, dans un réseau plat le schéma de routage se fait de nœud en nœud jusqu’à l’arrivée à la station de base. Cependant, dans les protocoles de routage hiérarchiques à l’instar de LEACH les clusterheads communiquent directement l’information à la station de base.
– Synchronisation : dans les communications radio entre les nœuds d’un RCSF, les capteurs écoutent en permanence les transmissions et consomment de l’énergie s’ils ne sont pas synchronisés entre eux. Pour cela, un nœud doit savoir gérer son temps de veille en tenant compte des périodes de veille de ses voisins.
– Overhead: Avant l’établissement des routes, les capteurs échangent des paquets de contrôle.
De ce fait, un protocole de routage performant doit minimiser son overhead. En outre, lors de l’échange de données, on assiste à éviter les collisions pour minimiser les envois multiples.
– Fiabilité de livraison : la plupart des protocoles de routage ont été conçus dans un environnement idéal. Néanmoins, la présence des obstacles pour y avoir un impact négatif sur la qualité des messages reçus. De ce fait, il est recommandé de prendre en considération la qualité des liens avant toute communication et le type d’environnement dans lequel ces capteurs sont déployés.
Taxonomie des protocoles de routage dans RCSFs
En raison de l’évolution du domaine d’applications des RCSF, de nombreux nouveaux algorithmes ont été proposés pour le problème de routage de données dans ce type de réseaux. Ces techniques de routage prennent en considération les caractéristiques des nœuds de capteurs ainsi que les exigences des applications. La majorité de ces protocoles de routage pourra être classée en trois catégories : données centrées (data-centric), hiérarchiques et basés sur la localisation (location-based) comme il existe une quatrième catégorie qui est basée sur les flux de réseau ou la qualité de service (QoS). Les protocoles de données centrées sont basés sur des requêtes et dépendent de la désignation des données souhaitées, ce qui contribue à éliminer de nombreuses transmissions redondantes. Les protocoles hiérarchiques visent à regrouper les nœuds afin que les clusterheads puissent faire une agrégation des données en vue d’économiser l’énergie. Les protocoles basés sur la localisation utilisent les informations de position pour transmettre les données vers les régions concernées. La dernière catégorie comprend des approches de routage qui sont basées sur la modélisation des flux et des protocoles ayant des exigences en termes de qualité de service.
Actuellement, on distingue deux types de protocoles de routage : les protocoles de routage classiques qui sont dédiés aux réseaux de capteurs de taille modeste et les protocoles basés sur les heuristiques qui sont conçus aux réseaux de capteurs denses et qui ont dans certains cas des exigences en termes de qualité de service [16]. Ces deux types de protocoles sont classés en quatre catégories qui sont citées avant.
Dans cette section, nous allons explorer les techniques de routage les plus répondues et nous discutons quelques protocoles chacun d’eux dans sa catégorie appropriée. Ceci est dans le but de mieux comprendre les protocoles de routage actuel pour les réseaux de capteurs sans fil et tirer profit de leurs avantages dans notre contribution.
Dans de nombreuses applications de réseaux de capteurs, il est impossible d’attribuer un identifiant à chaque nœud en raison du grand nombre de nœuds déployés. Cette absence d’identification des nœuds ainsi que le déploiement aléatoire des capteurs font qu’il est difficile de sélectionner un ensemble spécifique de capteurs pour être interrogé. Par conséquent, les données sont généralement transmises depuis chaque nœud dans la zone de déploiement avec une redondance importante. Puisque ce processus de transmission de données est inefficace en termes de consommation d’énergie, les protocoles de routage qui seront en mesure de sélectionner un ensemble de capteurs et d’utiliser l’agrégation de données lors de la transmission des données ont été pris en considération. Cette considération a conduit à l’acheminement de données-centrique, qui est différent du traditionnel routage basé sur les adresses où les routes sont créées entre les nœuds adressables.
Dans le routage de données-centrées, la station de base envoie des requêtes à certaines régions et attend les données provenant des capteurs situés dans les régions visées. Puisque les données sont demandées par le biais de requêtes, la précision des attributs est nécessaire pour spécifier les propriétés des données. SPIN [17] est le premier protocole de données-centrées, qui considère la négociation de données entre les nœuds afin d’éliminer les données redondantes et économiser l’énergie. Puis, Directed Diffusion [18] a été développé et est devenu une avancée dans le routage de données-centré. Ensuite, de nombreux autres protocoles ont été proposés soit basés sur le protocole Directed Diffusion [19-21] ou basés sur un concept similaire [22-25].
Nous allons décrire dans ce qui suit, les principaux protocoles faisant partie à cette catégorie en mettant en évidence les idées clés.
Données centrées:
SPIN: »Sensor Protocol for Information via Negotiation »
SPIN est l’un des premiers protocoles de routage de catégorie données-centré. SPIN nomme les données en utilisant des descripteurs ou des méta-données. Avant la transmission, les méta-données sont échangées entre les capteurs via un mécanisme d’annonce de données (Data Advertisement), qui est la principale caractéristique de SPIN. Chaque nœud qui reçoit de nouvelles données, annonce à ses voisins cette information et ceux parmi ses voisins qui ne disposent pas de données, envoient un message de demande de données à ce dernier. Ce processus de négociation a permis de résoudre les problèmes classiques causés par le processus d’inondation tels que les données redondantes et le chevauchement des zones de détection. De ce fait, l’efficacité énergétique est améliorée. La figure 2.1 résume le processus de négociation de méta-données dans SPIN.
Directed Diffusion
Diffusion Diffusion [18,26] est un protocole de routage données-centré dédié aux RCSF. DD vise à diffuser des données par le biais de nœuds en utilisant un schéma de nommage pour les données. La principale raison derrière l’utilisation de ce schéma est de se débarrasser des opérations inutiles de la couche réseau afin d’économiser de l’énergie. Diffusion Direct suggère l’utilisation de paires attribut-valeur pour les données et interroge les capteurs en utilisant ces paires. Afin de créer une requête, un intérêt est défini en utilisant une liste de paires attribut-valeur tels que le nom des objets, l’intervalle, la durée, zone géographique, etc. L’intérêt est diffusé par la station de base vers ses voisins et chaque nœud recevant l’intérêt peut faire la mise en cache pour une utilisation ultérieure. Les nœuds ont également la possibilité de faire l’agrégation des données, qui est modélisé par un problème d’arbre minimum de Steiner [27].
Les intérêts dans les caches sont ensuite utilisés pour comparer les données reçues avec les valeurs dans les intérêts. L’entrée d’intérêt contient également plusieurs champs de gradient. Un gradient est un lien de réponse à un voisin dont l’intérêt a été reçu. Il est caractérisé par le débit, la durée et le temps d’expiration provenant des champs de l’intérêt reçu. Par conséquent, en utilisant les intérêts et les gradients, les chemins sont établis entre la station de base et les nœuds sources. Plusieurs chemins peuvent être établis de telle sorte que l’un d’eux est sélectionné par un processus de renforcement positif. La station de base réémet le message d’intérêt initial à travers le chemin d’accès sélectionné à un intervalle plus petit et renforce donc le nœud source sur ce chemin pour envoyer des données plus fréquemment. Figue.2.2 résume le fonctionnement du protocole directed diffusion.
Figure 2.2:Transmission des données dans le protocole Directed diffusion [18]
Energy-aware routing
Shah et Rabaey [24] ont proposé d’utiliser un ensemble de chemins semi-optimaux de temps à autre pour augmenter la durée de vie du réseau. Ces chemins sont choisis au moyen d’une fonction de probabilité qui dépend de la consommation d’énergie de chaque chemin. La durée de vie du réseau est la métrique principale que ce protocole la vise.Le protocole Energy-Aware fait valoir que l’utilisation tout le temps le chemin dont la consommation d’énergie est minimale va épuiser rapidement l’énergie des nœuds sur ce chemin. Pour cela, l’un des chemins multiples est utilisé avec une certaine probabilité, ce qui augmente la durée de vie du réseau. Le protocole suppose que chaque nœud est adressable par un mode d’adressage qui inclut l’emplacement et le type de nœud. Il s’exécute en trois phases:
– Phase Set-up: des inondations locales se produisent pour trouver les chemins et créer les tables de routage. En faisant cela, le coût de l’énergie totale est calculé par chaque nœud. Par exemple, si la requête est envoyée à partir du nœud Ni au nœud Nj, Nj calcule le coût de la trajectoire comme suit:
La mesure de l’énergie utilisée est calculée en fonction des coûts de transmission et de réception ainsi que l’énergie résiduelle des nœuds. Les chemins qui ont un coût très élevé sont éliminés. La sélection des nœuds est effectuée en fonction de la proximité de la destination. Le nœud attribue une probabilité à chacun de ses voisins dans la table de routage, nommée aussi la table de transfert (FT: Forwarding Table) correspondant aux chemins formés. La probabilité est inversement proportionnelle au coût, à savoir:
Nj calcule ensuite le coût moyen pour atteindre la destination en utilisant les voisins dans la table de transfert (FTJ) selon la formule suivante:
Ce coût moyen calculé par Nj est assigné au champ « coût » de la demande et transmis par la suite dans le voisinage de Nj.
– Phase de communication de données: Chaque nœud transmet le paquet en choisissant aléatoirement un nœud à partir de sa table de transfert selon certaines probabilités.
– Phase de maintenance de route: les inondations locales sont rarement effectuées pour garder tous les chemins opérationnels.
Ce protocole fournit de meilleures performances comparé au protocole Directed Diffusion en termes de consommation d’énergie et de durée de vie. Cependant, ce protocole nécessite la collecte des informations de localisation et la mise en place d’un mécanisme d’adressage pour les nœuds, ce qui complique le passage à l’échelle.
Protocoles hiérarchiques :
Dans une architecture plate, les protocoles perdent leurs performances lors du passage à l’échelle. A cet effet, pour permettre au réseau de faire face à une charge supplémentaire et d’être en mesure de couvrir une grande zone d’intérêt sans dégrader le service, l’architecture hiérarchisée a été adoptée dans certaines techniques de routage.
L’objectif principal du routage hiérarchique est de maintenir efficacement la consommation d’énergie des nœuds en les impliquant dans un schéma de communication multi-sauts et en effectuant l’agrégation de données afin de diminuer le nombre de messages transmis à la station de base. Dans une architecture clustérisée, la formation des clusters est généralement basée sur l’énergie résiduelle des capteurs et de la proximité du capteur de son clusterhead correspondant. [28,29]
LEACH [30] est l’une des premières approches de routage hiérarchique pour les RCSF. L’idée proposée dans LEACH a été une source d’inspiration pour de nombreux protocoles de routage hiérarchiques [22,31-33], bien que certains protocoles ont été développés indépendamment [34,35]. Dans ce qui suit, nous explorons les principaux protocoles de routage hiérarchiques dédiés aux RCSF.
LEACH
LEACH est l’un des algorithmes de routage hiérarchiques les plus populaires pour les RCSF. L’idée est de former des clusters basés sur la puissance du signal reçu et utiliser les clusterheads comme des routeurs à la station de base. Ceci permettra d’économiser l’énergie puisque les transmissions ne seront effectuées que par ces clusterheads plutôt que par tous les nœuds.
Tous les traitements de données tels que la fusion ou l’agrégation de données sont assurés par les clusterheads. Ces clusterheads changent de rôle au hasard au fil du temps afin d’équilibrer la dissipation d’énergie des nœuds. Cette décision est prise par le nœud en choisissant un nombre aléatoire entre 0 et 1. Le nœud devient clusterhead pour le cycle actuel si le nombre généré est inférieur au seuil suivant:
où p est le pourcentage désiré de clusterheads (par exemple 5%), r est la période courante, et G est l’ensemble des nœuds qui n’ont pas été des clusterheads dans les 1/p dernières périodes.
La figure 2.3 illustre la phase de formation de clusters et comment se fait la transmission de données à la station de base dans LEACH.
Figure 2.3:Illustration du clustering dans le protocole LEACH [14]
Quoique LEACH fournit de meilleurs résultats, mais l’élection périodique des clusterheads pourra être une charge supplémentaire à cause de l’augmentation des messages d’avertissement lors de l’élection de nouveaux clusterheads, ce qui peut diminuer le gain en consommation d’énergie. [14]
PEGASIS
Le protocole PEGASIS (Power Efficient Gatering in Sensor Information System) [31] est l’une des améliorations du protocole LEACH où les nœuds dans ce protocole se rangent sous forme d’une chaîne suivant deux principes:
– Principe 1: chaque nœud communique qu’avec son voisin le plus proche.
– Principe 2: les nœuds auront le droit de transmettre vers la station de base à tour de rôle.
Figure 2.4:Exemple d’une chaîne de nœuds dans le protocole PEGASIS [31]
Bien que PEGASIS construit une chaîne reliant tous les nœuds pour équilibrer la dissipation d’énergie du réseau, il y a encore quelques défauts avec ce régime :
1) Dans les applications de détection temps réel, la seule chaîne longue peut introduire un temps de retard de données inacceptable.
2) Puisque le leader de la chaîne est élu à tour de rôle, dans certains cas, plusieurs nœuds de capteurs pourraient inversement transmettre leurs données agrégées au leader désigné, même si ils sont proches de la station de base qu’au leader de la chaîne. Cela se traduira par des voies de transmission redondantes, et donc une grande perte d’énergie.
3) Le leader de la chaîne unique peut devenir un goulot d’étranglement quand il cesse de fonctionner.
TEEN
Le protocole LEACH est destiné aux applications time-driven. Dans ce type d’applications, les données sont transmises à la station de base d’une manière périodique. Cependant, ce genre de protocole est inadapté pour les applications event-driven, où un comportement réactif est nécessaire pour le bon fonctionnement du système. Dans cette optique, TEEN (Threshold sensitive Energy Efficient sensor Network protocol) [22] a été développé pour modeler LEACH afin de répondre aux exigences des applications event-driven.
La majorité du comportement de TEEN est semblable au protocole LEACH. Cependant, quelques différences existent entre les deux protocoles par exemple dans le protocole TEEN, les clusterheads élus ne transmettent pas un schedule TDMA aux membres de leurs clusters, mais émettent un message contenant les informations suivantes :
– Attributs : représentent la tâche demandée au capteur.
– Hard threshold (HT): détermine la valeur critique après laquelle les membres doivent envoyer leurs rapports de données.
– Soft threshold (ST): spécifie le changement minimal obligeant le nœud à envoyer un nouveau rapport.
Lorsqu’un nœud s’aperçoit que la valeur captée a dépassé le seuil HT, il devra émettre un rapport à son clusterhead correspondant. Il ne réémet un nouveau rapport que si la valeur change radicalement, (i.e: la différence dépasse ST). Ce mécanisme permet d’implémenter un comportement réactif, tout en limitant le nombre de messages utilisés. La figure 2.5 résume le fonctionnement du protocole TEEN.
CHIRON
Le protocole CHIRON [36] (Energy-efficient Chain based-Hierarchical Routing Protocol) est classifié parmi les protocoles hiérarchiques. Le routage dans ce protocole se base sur les étapes suivantes:
– Construction des groupes: L’objectif principal de cette phase est de diviser le champ de détection en un certain nombre de zones de taille réduite de sorte que CHIRON peut créer plusieurs chaînes plus courtes pour réduire le temps de propagation des données.
Au lieu d’utiliser des clusters concentriques comme dans le protocole EPEGASIS, le protocole CHIRON adopte la technique de BeamStar [37] pour organiser ses clusters. Après que les nœuds de capteurs soient dispersés, le station de base balaie progressivement toute la zone de détection, en changeant successivement des niveaux de puissance de transmission et les directions de son antenne, pour envoyer des informations de contrôle (y compris les valeurs de R et θ) à tous les nœuds. Tous les nœuds recevant les paquets de contrôle, peuvent facilement déterminer le cluster auquel ils peuvent appartenir. En outre, par l’indication d’intensité du signal reçu (RSSI), chaque nœud peut également connaitre la distance qui le sépare de la station de base (ni, BS). Un exemple de clustering avec R = 1..3 et θ = 1..2 est représenté par la Figure 2.6.
– Phase de formation des chaînes : Dans cette phase, les nœuds de chaque groupe Gx,y seront reliés entre eux pour former une chaîne cx, y. Le processus de formation de chaînes est le même que celui dans PEGASIS. Pour chaque groupe Gx,y, le nœud ni ayant la valeur maximale de dis(ni, BS) (le nœud est le plus éloigné de la station de base) initie le processus de création de la chaîne du groupe. En utilisant un algorithme glouton, le nœud le plus proche (à ni) sera choisi pour être lié au nœud ni, ce dernier initie à son tour la prochaine étape d’établissement de liaison. Le processus est répété jusqu’à ce que tous les nœuds soient mis ensemble, et donc finalement une chaîne du groupe cx, y est formée. La figure 2.7 montre l’ensemble de chaînes de groupe qui sont construits à partir de l’environnement de détection de la figure précédente.
Figure 2.7:Phase d’élection [36]
La phase d’élection d’un nœud chef : Pour la transmission de données, un nœud leader dans chaque chaîne du groupe doit être sélectionné pour la collecte et la transmission des données agrégées à la station de base. Contrairement aux protocoles PEGASIS et EPEGASIS, dans lesquels le chef de dans chaque chaîne est élu d’une manière périodique selon la politique round-robin, CHIRON choisit le leader de la chaîne (lx, y) en fonction de la valeur maximale RES(ni) des nœuds de groupe. Dans un premier temps, dans chaque groupe, le nœud le plus éloigné de la station de base est choisi comme chef de chaîne du groupe. Après cela, pour chaque tour de transmission de données, le nœud ayant l’énergie résiduelle maximale sera élu comme chef de chaîne du groupe. L’énergie résiduelle de chaque nœud ni peut être injectée avec les données fusionnées au leader de la chaîne lx, y le long de la chaîne cx,y, de sorte que le chef de la chaîne peut déterminer quel nœud sera le nouveau chef de chaîne pour le prochain tour de transmission.
– Phase de collecte et de transmission de données : Après les trois phases précédentes, on assiste à la phase de collecte et de transmission des données. La procédure de transmission de données dans CHIRON est similaire à celle dans PEGASIS. Tout d’abord, les nœuds ordinaires dans chaque groupe Gx,y transmettent leurs données collectées à leur leader correspondant lx,y , en passant par les nœuds les plus proches le long de la chaîne cx,y. Et puis, à partir des groupes les plus éloignés, les leaders des chaînes transmettent leurs données agrégées à la station de base selon un schéma de routage multi-sauts (leader-to-leader). Afin d’éviter une distance de transmission plus longue entre deux leaders, et donc donner lieu à une grande quantité de dissipation d’énergie, un leader voisin à lx,y avec les qualifications suivantes sera élu comme nœud relai:
i) il est plus proche de la base station que lx,y;
ii) la distance à lx,y est minimale. La figure 2.8 montre un exemple d’élection d’un nœud relai et l’acheminement des données par suite, les deux nœuds leaders l1,3 et l2,3 sélectionnent le leader l2,2 comme nœud relais. Tandis que, le nœud leader l2,2 envoie ses données fusionnées à son relai l1,2. Le processus est répété jusqu’à ce qu’un chemin de transmission en cascade pour atteindre la station de base soit créé.
Figure 2.8:Acheminement des données [36]
ETR » Energy-aware Tree Routing protocol »
Comme son nom l’indique, ETR [38] utilise un arbre afin d’hiérarchiser le réseau et d’acheminer les données par la suite. ETR s’exécute en trois étapes :
– Etablissement des routes: dans cette étape une structure hiérarchique sera créée selon la démarche suivante:
• La station de base diffuse un message contenant son adresse et son niveau dans la hiérarchie (niveau 0 pour la station de base).
• Chaque nœud qui reçoit un message, calcule son niveau (niveau=niveau reçu dans le message +1), ajoute de nœud transmetteur dans la liste des parents et de même il diffuse un message contenant son adresse et son niveau.
Figure 2.9:Définition des niveaux [38]
– Transmission des données: chaque nœud voulant envoyer des données construit un message contenant son adresse et l’envoie à son père, le processus sera répété jusqu’à ce que la donnée arrive à sa destination.
– Maintenance des routes : le protocole essaie d’analyser l’énergie des nœuds et reconstruire les liens entre les nœuds et leurs parents si c’est nécessaire.
Les protocoles basés sur la localisation
Dans le routage, certains des protocoles pour les réseaux de capteurs nécessitent des informations de localisation pour les nœuds. Les informations de leur emplacement respectif est nécessaire de manière à faciliter le calcul de la distance entre deux nœuds, et être capable de diffuser une requête sur une région particulière, éliminant ainsi le nombre de transmission [39]. Ceci contribue à l’estimation de la consommation d’énergie.
Geographic adaptive fidelity (GAF)
GAF [40] a été conçu principalement pour les réseaux ad-hoc mobiles, mais il est également applicable aux réseaux de capteurs. Il garantit une faible consommation d’énergie dans réseau en désactivant les nœuds qui ne sont pas impliqués dans le processus de routage sans nécessairement affecter les performances du routage. Chaque nœud est doté d’un GPS lui permettant de connaître son emplacement sur une grille virtuelle.
Dans GAF, les nœuds changent d’état en passant du mode « En dormi » au mode « actif » et vice-versa afin d’équilibrer la charge de consommation d’énergie. Les trois états qui existent dans GAF sont : « découverte » pour connaitre l’emplacement des voisins sur la grille, « actif » indiquant la participation des nœuds dans le routage, et « veille » lorsque la radio est éteinte.
GAF peut également être considéré comme un protocole de routage hiérarchique, où les clusters sont basés sur les informations géographiques. Dans chacune des zones de la grille, il existe un nœud principal qui transmet les données vers d’autres nœuds. GAF diffère des protocoles hiérarchiques puisque le nœud leader ne fait pas de l’agrégation ou la fusion des données.
Geographic and energy-aware routing (GEAR)
GEAR [41] est un algorithme de routage à haut rendement énergétique conçu pour le routage des requêtes à des régions cibles dans un réseau de capteurs. Dans, GEAR, chaque nœud est doté d’un GPS pour identifier son emplacement. Par ailleurs, GEAR utilise des heuristiques basées sur l’information géographique pour la sélection de nœuds pour acheminer les données vers la station de base. L’objectif principal dans GEAR est de limiter le nombre de cibles dans Directed Diffusion en considérant uniquement une région plutôt que de viser l’ensemble des cibles dans les différentes régions de déploiement des réseaux. En procédant de cette manière, GEAR peut conserver plus d’énergie que le protocole Directed Diffusion.
Dans GEAR, chaque nœud conserve un coût estimé et un coût d’apprentissage pour atteindre la destination à travers ses voisins. Le coût estimé est une combinaison de l’énergie résiduelle et la distance qui le sépare du nœud destinataire. Le coût d’apprentissage est un raffinement du coût estimé qui représente le routage autour des trous dans le réseau. Un trou se produit quand un nœud n’a pas de voisin proche dans la région cible. S’il n’y a pas de trous, le coût estimé est égal au coût apprentissage.
Le coût d’apprentissage se propage un saut en arrière chaque fois qu’un paquet atteint la destination afin que la configuration de la route pour le prochain paquet sera ajusté. GAER s’exécute en deux phases:
– Transfert des paquets vers la région cible: à la réception d’un paquet, un nœud vérifie ses voisins pour voir s’il y a un voisin qui est plus proche de la région cible que lui-même. S’il y a plusieurs qui sont proches, le plus proche voisin de la région cible est choisi comme saut suivant. Si tous ses voisins sont plus loin de la région cible que le nœud lui-même, cela signifie qu’il y a un trou. Dans ce cas, l’un des voisins est prélevé pour transmettre le paquet sur la base de la fonction de coût d’apprentissage. Ce choix peut alors être mis à jour en fonction de la convergence du coût d’apprentissage lors de la livraison de paquets.
– La transmission des paquets au sein de la région: si le paquet a atteint la région, il peut être diffusé dans cette région géographique soit par le transfert récursif ou l’inondation restreinte. L’inondation restreinte est bonne lorsque les capteurs ne sont pas densément déployés. Dans les réseaux à haute densité, la transmission géographique récursive est économe en énergie que l’inondation restreinte. Dans ce cas, la région est divisée en quatre sous-régions et quatre copies du paquet sont créées. Ce processus de fractionnement et transfert continue jusqu’à ce que les régions avec un seul nœud soient épuisées. GEAR ne réduit pas seulement la consommation d’énergie, mais surpasse également GPSR [42] en termes de livraison de paquets.
Principaux protocoles de routage basés sur les heuristiques
Les protocoles de routage classiques ont prouvé leur faiblesse lors du passage à l’échelle dans les réseaux de capteurs en termes de latence, durée de vie, etc. A cet effet, de nouvelles approches basées sur les heuristiques ont été révélées pour surpasser les failles présentées par les algorithmes de routage classiques. Parmi ces algorithmes, nous trouvons la colonie de fourmis, le recuit simulé, les algorithmes génétiques, la méthode tabou. Dans ces heuristiques, il y avait l’imitation du comportement des espèces naturelles telles que les fourmis.
Les colonies de fourmi sont l’un des heuristiques les plus utilisées dans la procédure de routage. Le routage basé sur ces dernières représente une approche prometteuse, où le comportement des fourmis et la communication entre elles en se basant sur l’adoption de produits chimiques comme substance connue sous le nom de phéromones paré très intéressante et peut être projeté dans les réseaux à grandes échelles [43].
CRP « Comprehensive Routing Protocol «
Dans l’objectif d’améliorer le protocole EAR, le protocole CRP [44] a été fondu en se basant sur l’utilisation de l’heuristique colonie de fourmi. Ce protocole repose sur trois phases importantes :
– Configuration de la table de routage : dans cette phase une exploration de tous les chemins qui relient la source à une destination serra déclenchée. Ensuite et pour chaque chemin trouvé le protocole lui attribue une certaine probabilité selon les critères suivants:
la quantité des phéromones.
l’énergie restante de chaque un des nœuds qui forment le chemin.
la fréquence qu’un nœud serra considéré comme étant un routeur.
– Communication de données : le nœud source envoie le paquet de données à l’un de ses voisins de la table de transfert, avec la probabilité choisie par le voisin. Chacun des nœuds intermédiaires transmet le paquet de données vers un voisin choisi aléatoirement dans sa table de transfert, également avec la probabilité du voisin étant choisie égale à la probabilité de la table de transfert. Ceci se poursuit jusqu’à ce que le paquet de données atteigne le nœud de destination. Durant la transmission de données, quand un nœud est choisi comme un nœud relai, la concentration de phéromone sur la branche reliant ces deux nœuds doit être mise à jour selon les équations suivantes:
Où lij est la quantité de phéromone sur chemin reliant i et j et phéromone de mise à jour est la quantité de
– Maintenance de routes : Cette phase est responsable de rétablir les routes et mettre à jour des tables de routage. Des inondations locales sont effectuées fréquemment de la destination à la source pour maintenir tous les chemins opérationnels et mettre à jour les tables de routage en fonction des conditions actuelles.
Les résultats fournis par CRP ont montré qu’il dépasse ceux du protocole EAR. Cependant, CRP manque des métriques de qualité de service.
|
Table des matières
INTRODUCTION GENERALE
1. CHAPITRE I GENERALITES SUR LES RESEAUX DE CAPTEURS SANS FIL
1.1. INTRODUCTION
1.2. QU’EST-CE QU’UN CAPTEUR ?
1.2.1. Définition d’un noeud capteur
1.2.2. Catégories de capteurs
1.3. LES RESEAUX DE CAPTEURS SANS FIL
1.3.1. Caractéristiques des réseaux de capteurs sans fil
1.3.2. Domaines d’applications
a. Applications militaires
b. Découvertes de catastrophes naturelles
c. Détection d’intrusions
d. Applications métier
e. Surveillance médicale
f. Contrôle d’édifices
g. Applications environnementales
h. La domotique
1.3.3. Catégories de communications dans les RCSF
a. Scénario périodique
b. Selon la demande
c. Scénario orienté événement (event-driven)
1.4. CONTRAINTES DE ROUTAGE DANS LES RCSF
1.5. CONCLUSION
2. CHAPITRE II LES PROTOCOLES DE ROUTAGES DANS LES RCSF
2.1. INTRODUCTION
2.2. CRITERES DE PERFORMANCE DES PROTOCOLES DE ROUTAGE DANS LES RCSF
2.3. TAXONOMIE DES PROTOCOLES DE ROUTAGE DANS RCSFS
2.3.1. Données centrées
a. SPIN « Sensor Protocol for Information via Negotiation »
b. Directed Diffusion
c. Energy-aware routing
2.3.2. Protocoles hiérarchiques
a. LEACH
b. PEGASIS
c. TEEN
d. CHIRON
e. ETR » Energy-aware Tree Routing protocol »
2.3.3. Les protocoles basés sur la localisation
a. Geographic adaptive fidelity (GAF)
b. Geographic and energy-aware routing (GEAR)
2.3.4. Principaux protocoles de routage basés sur les heuristiques
a. CRP « Comprehensive Routing Protocol »
b. ACALEACH » Ant Colony clustering algorithm »
c. MSRP » Multi-SinkRoutingprotocol »
d. Ant colony multicast trees (ACMT)
2.4. CONCLUSION
3. CHAPITRE III TECHNIQUES D’OPTIMISATIONS POUR LES RESEAUX LES HEURISTIQUES
3.1. INTRODUCTION
3.2. CLASSES D’ALGORITHMES POUR LES PROBLEMES NP_DIFFICILES
3.2.1. Les algorithmes d’approximation
3.2.2. Les algorithmiques heuristiques
3.2.3. Les algorithmes probabilistes
3.2.4. Les méta-heuristiques
3.3. EXEMPLE DE META-HEURISTIQUE
3.3.1. La colonie de fourmis
3.3.2. La méthode Tabou
3.3.3. Le recuit simulé
3.3.4. Les algorithmes génétiques
3.4. CONCLUSION
4. SCHEMAS DE ROUTAGE BASES SUR LES ALGORITHMES GENETIQUES
4.1. INTRODUCTION
4.2. ENVIRONNEMENT DU DEVELOPPEMENT OMNET++
4.2.1. Les modules
4.2.2. Les canaux de communication(Channel)
4.2.3. Les messages
4.2.4. Les fichiers de descriptions »Ned File »
4.3. SCHEMA DE ROUTAGE BASE SUR LES ALGORITHMES GENETIQUES
4.3.1. La désignation de la population initiale
4.3.2. La fonction objective « fitness »
4.3.3. L’étape de croisement
4.3.4. L’étape de sélection
4.3.5. Critère d’arrêt
4.3.6. Choix de la meilleure solution
4.4. IMPLEMENTATION SUR OMNET++
4.4.1. Le module station de base
4.4.2. Le module capteur
4.4.3. Définition des types de messages
4.5. FONCTIONNEMENT DU RESEAU
4.6. MODELE ENERGETIQUE
4.7. SIMULATION
4.7.1. Paramètres de simulation
4.7.2. Résultats de la simulation
a. La version énergie
b. Version distance
4.8. DISCUSSION DES RESULTATS
4.9. COMPARAISON AVEC D’AUTRES PROTOCOLES
4.10. AMELIORATIONS PROPOSEES
4.10.1. Changement de la méthode de sélection
4.10.2. Routage avec ajustement de puissance de transmission
4.11. CONCLUSION
CONCLUSION GENERALE
REFERENCES BIBLIOGRAPHIQUES
Télécharger le rapport complet
