Protocoles

de routage
dans les RCSF
1. Taxonomie des protocoles de routage:
Les méthodes employées afin d’étudiés les protocoles de routage pour
les RCSF peuvent être classifiées suivant plusieurs critères:
 Topologie du réseau:
l'organisation des capteurs
dans le réseau

Topologie Plate Topologie Hiérarchique

• Diviser les nœuds en plusieurs

niveaux de responsabilité.
Tous les nœuds possèdent le •Le réseau est partitionné en groupes
même rôle appelés "clusters".
•Un cluster est constitué d'un chef
(cluster-head) et de ses membres.
 Paradigme de
communication

Node centric Data centric Position

centric
Employé dans les Les communicants sont
réseaux identifiés par leurs Les positions des nœuds
conventionnels, données. représentent
le moyen principal
les communications Le système est une base d'adressage et de
se basent sur de données distribuée, routage.
l'identification des où les nœuds le routage s'effectue
nœuds par forment des tables grâce à
d'adresses IP. virtuelles, alimentées des techniques
par les données captées. géométriques afin
d'acheminer
l'information d'une zone
géographique vers une
autre.
 Type d'application

Time Driven Event Driven

les capteurs
Applications qui doivent réagir à des
nécessitent un prélèvement changements soudains des
périodique des données. valeurs
captées. Le protocole doit
Exemple: Applications de être réactif et doit donner
monitoring (feu, météo) des
afin d'établir des rapports réponses rapides à
périodiques. l'occurrence d'un certain
nombre d'évènements.
2. Exemples de protocoles de routage dans les
RCSF

a) SPIN

b) Directed Diffusion

c) MCFA : Minimum Cost Forwarding Algorithm

d) Rumour Routing
 SPIN
(Sensor Protocols for Information via Negotiation)

Le but de SPIN est de pallier aux problèmes de l'inondation, qui

sont :

• L'implosion due à la duplication inutile des réceptions d'un

même message.

• Le chevauchement lié au déploiement dense des capteurs. En

utilisant l'inondation, les capteurs d'une zone émettrons tous la
même donnée (ou presque).
Ces problèmes affectent grandement la durée de vie et les performances
du réseau. Pour les résoudre, SPIN adopte deux principes :

•La négociation : pour éviter le problème d'implosion, SPIN précède

l'émission d'une donnée par sa description, en utilisant la notion de
métadonnées.
Le récepteur aura le choix par la suite d'accepter la donnée ou
non. Ce mécanisme permet aussi de régler le problème de chevauchement.

•L'adaptation aux ressources : d'une manière continue, les noeuds

contrôlent leur niveau d'énergie. Le protocole SPIN accommode son
exécution suivant l'énergie restante du capteur, et modifie en conséquence le
comportement du noeud.
 Fonctionnement de SPIN :
Les communications dans SPIN se font en trois étapes :
• Lorsqu'un noeud veut émettre une donnée, il émet d'abord un message
ADV contenant une description de la donnée en question.
• Un noeud recevant un message ADV, consulte sa base d'intérêt. S'il est
intéressé par cette information, il émet un message REQ vers son voisin.
• En recevant un message REQ, l'émetteur transmet à l'intéressé la donnée
sous forme d'un message DATA.
 Directed Diffusion
Il s'agit d'établir des communications régulières entre nœuds.
Une demande prend la forme suivante :
– Type : type d'information demandée
– Fréquence : chaque combien de temps cette information doit être
transmise
– Zone : peut être utilisé pour définir, quand c'est possible, la zone
géographique (rectangle)
dans laquelle l'émetteur de l'information doit se situer
– Date de demande : date à laquelle la demande est faite
– Date d'expiration : date à partir de laquelle la demande n'est plus
maintenue
Un nœud qui est intéressé pour recevoir un certain type d'information
diffuse une telle demande à tous ses voisins et chaque noeud la rediffuse à
tous ses voisins (inondation). Même s'il la reçoit plusieurs fois, chaque
noeud ne la diffuse qu'une seule fois. Le ou les noeuds qui détiennent
l'information demandée la diffusent de la même façon.
Avec ces échanges les noeuds vont déterminer la ou les routes
possibles.
 Il faut maintenant choisir une route parmi les routes possibles ainsi
déterminées :
Méthode dite de Gradient-Based Routing

On va choisir la route la plus courte en nombre de hops :

chaque noeud détermine sa distance en hops au destinataire final, comme ses
voisins ont fait la même chose, le gradient du lien entre 2 noeuds A et B est la
différence entre la distance de B au destinataire et celle de A.
A choisira d'envoyer sur le lien de plus fort gradient (celle qui rapproche le
plus).
Méthode basée sur l'énergie
Au lieu de choisir une route optimale on conserve un ensemble de
routes possibles. Puis on choisit la route qui minimise l'énergie.
L'énergie consommée par chaque route est calculée lors de la diffusion
de la requête. Cette méthode permet d'augmenter la durée de vie du
réseau jusqu'à 40%.
 Propagation des intérêts et établissement des gradients

Lorsqu'un puits requiert une donnée du réseau, il propage un intérêt,

contenant sa description ainsi que le débit d'information désiré.
Initialement, le puits spécifie un grand intervalle, dans un but
d'exploration. Cela permet d'établir les gradients et de découvrir
d'éventuelles sources, sans pour autant encombrer le réseau.

Afin de propager l'interêt, DD emploie

Lorsqu'un noeud reçoit un intérêt, il parcourt
l'inondation globale du réseau.
son cache .
 Propagation des données

Lorsque l'intérêt atteint les sources ciblées, les capteurs commencent

la récolte d'information. Pour un intérêt donné, un capteur calcul le
débit le plus élevé et prélève les données en conséquence. En
consultant les gradients relatifs à l'intérêt, le noeud détermine les
prochains sauts vers les puits (chacun avec son propre débit).

Remarque : Evitement des boucles

Avant de relayer une donnée à ses voisins, un noeud utilise son cache
de données. Ce cache enregistre les données récemment émises par les
voisins. Cela évite la création de boucles, en supprimant les données
déjà rencontrées.
 Renforcement des chemins
Renforcement positif
Lorsque le puits reçoit les premières données, il renforce le chemin vers le
voisin émetteur, en augmentant le débit de captage. Cela permet de
clôturer la phase d'exploration, et d'entamer la phase de récolte
d'information. Le renforcement ne doit pas s'arrêter au niveau des voisins
du puits, mais doit se propager éventuellement jusqu'aux sources. Pour ce
faire, lorsqu'un noeud reçoit un message de renforcement, il consulte son
cache d'intérêt. Si le débit spécifié dans le message est plus grand que tous
les autres débits des gradients présents, le noeud doit renforcer un de ses
voisins. Le voisin est choisi en utilisant le cache de données.
Renforcement négatif
Dans le cas de panne d'un lien (perte de paquet,
débit réduit, etc.) le puits peut
envoyer un renforcement négatif sur le chemin en
panne en spécifiant le débit de
base (exploratoire), et en procédant à un
renforcement positif d'un chemin
alternatif.
 MCFA : Minimum Cost Forwarding Algorithm

Il consiste à chercher un chemin minimal entre la source et le puits, tout en

considérant les limites des réseaux de capteurs.
Le protocole vise à atteindre trois principaux buts :
 L'optimalité : en acheminant les données sur des chemins à coût
minimum.
 La simplicité : qui se traduit par une faible consommation en mémoire, et
la non nécessité d'une identification des noeuds.
 La scalabilité : étant donnée la faible consommation en mémoire et
l'absence d'identificateur de noeuds, le protocole peut être utilisé pour un
grand nombre de noeuds. En plus, la phase de construction des routes ne
consomme qu'un message par capteur.
Chaque noeud maintient une variable de coût, qui détermine le coôt minimal
vers le puits sur le chemin optimal. Plusieurs mesures peuvent être
employées, suivant l'application voulue : nombre de sauts, consommation
d'énergie, . . . etc.
L'algorithme se déroule en deux phases : calcul des coûts, relais des paquets.
 Etablissement des valeurs de coût

Une solution simple pour la détermination des valeurs locales des coûts
est d'utiliser l'inondation. Initialement, le puits émet un message ADV
contenant un coût nul. Tous les autres noeuds initialisent leur coût à une
valeur infinie. Lorsqu'un noeud reçoit un message ADV, il vérifie si la
valeur reçue additionnée au coût du lien est plus petite que la valeur
locale. Dans ce cas, le noeud met à jour sa valeur locale et émet un
nouveau message ADV.
Relais des paquets
Le relais dans MCFA n'utilise aucune identification des noeuds et aucune
table de routage. Ce qui rend MCFA assez adapté aux environnements de
capteurs. Lorsqu'un paquet est émis par une source vers le puits, il
contient le coût minimal local du noeud. A la réception d'un paquet de
donnée, le noeud vérifie si son coût local est égal au coût reçu moins le
coût du lien de réception. Dans ce cas, le nœud relaie le paquet en
remplaçant la valeur du coût par sa valeur locale :
 Rumour Routing
L'idée clé de cette méthode est de trouver les routes pour les requêtes vers les nœuds qui
ont observé un événement particulier, plutôt que d'inonder tout le réseau pour récupérer
des informations sur les événements survenus.

Afin de diffuser un événement sur le réseau, l’algorithme de routage par rumeur

emploie des paquets appelés agents. Quand un nœud détecte un événement, il ajoute cet
événement à sa table locale, appelée table d'événements et génère un agent. Cet agent
parcourt le réseau afin de propager des informations sur des événements locaux pour les
nœuds distants.
Quand un nœud génère une requête pour un événement, les nœuds qui connaissent le
chemin, répondent à la requête en inspectant leur
table événement. Donc, il n'est pas nécessaire d'inonder tout le réseau, ce qui réduit le
coût de communication.
D'autre part, ce routage n’utilise qu'un seul chemin entre la source
et la destination au lieu de la diffusion dirigée où les données peuvent être acheminées
par des routes multiples.
 Agents d'évènements

Lorsqu'un noeud observe un nouvel évènement, il crée un nouvel agent

suivant une certaine probabilité. L'agent contient la tablae d'évènements
parcourus au sein du chemin ainsi que le nombre de sauts vers la source
de chaque évènement. De plus, l'agent doit transporter avec lui la liste
des noeuds parcourus ainsi que leurs voisin directs. La source choisit un
voisin aléatoire et lui émet l'agent. Lorsqu'un noeud reçoit un agent, il
effectue les opérations suivantes :
• Si l'agent contient un nouvel événement, une nouvelle entrée dans la
table locale est créée.

• Le nœud met à jour sa table locale et/ou la table de l'agent pour les
entrées communes, suivant le nombre de sauts optimal : i.e. si l'agent
possède une route plus courte vers un certain événement, le noeud met à
jour sa table, et vice-versa. Cette méthode permet d'optimiser des routes
déjà établies par d'autres agents.

• Si le nœud connaît des événements non connus par l'agent, il ajoute les
entrées nécessaires dans la table de l'agent.

• Le nœud choisit comme prochain saut un de ses voisins n'appartenant

pas à la liste des nœuds de l'agent, et modifie en conséquence sa table
locale pour le prochain saut vers le puits (i.e. le nœud choisi représente le
prochain vers le puits).
• Le nœud ajoute à la liste des nœuds parcourus son identificateur, ainsi
que ceux de ses voisins.
• Le message est envoyé au nœud choisi.
 Les protocoles de routage basés sur la localisation

Les protocoles de routage basés sur la localisation utilisent les

informations d’emplacement pour guider la découverte de routage et la
transmission des données. Ils permettent la transmission
directionnelle de l’information en évitant l’inondation d’information
dans l’ensemble du réseau.

Par conséquent, le coût de contrôle de l’algorithme est réduit et le

routage est optimisé.
De plus, avec la topologie réseau basée sur des informations de
localisation de nœuds, la gestion du réseau devient simple.

L’inconvénient de ces protocoles de routage est que chaque nœud

doit connaître l’emplacement des autres nœuds.
 Minimum Energy Communication Network (MECN)

un protocole de routage qui cherche à établir et à entretenir une énergie minimale

pour les réseaux sans fil en utilisant des GPS de faible puissance. MECN utilise
une station de base comme destination de l'information, ce qui est toujours le cas
pour les réseaux de capteurs. MECN identifie une
région de relais pour chaque noeud. La région de relais se compose de noeuds
dans une zone périphérique où la transmission à travers ces noeuds est plus
économe en énergie que la transmission directe. L'idée principale de MECN est
de trouver un sous-réseau qui a moins de noeuds et qui nécessite moins d'énergie
pour la transmission entre deux noeuds quelconques.
Cela est effectué en utilisant une recherche localisée pour chaque noeud en
prenant en considération sa région de relais
 GAF (Geographic Adaptive Fidelity)

un protocole de routage basé sur la

localisation des noeuds. Il est conçu
principalement pour les réseaux mobiles ad
hoc, mais peut être applicable aux réseaux de
capteurs. La localisation des noeuds dans
GAF pourrait
être fournie à l’aide d’un GPS ou d’autres
techniques de localisation . Il consiste à
former des grilles virtuelles de la zone
concernée en partitionnant cette zone où les
nœuds sont déployés en de petites zones
telles que, pour deux grilles adjacentes Gx et
Gy, tous les noeuds de Gx peuvent
communiquer avec tous les noeuds Gy. Ainsi,
ce système de
partitionnement GAF assure la fidélité du
routage car il existe au moins un chemin
entre un noeud et la station de base.
Les Protocoles hiérarchiques
 LEACH (Low Energy Adaptive Clustering
Hierarchical)

L'idée est de former des clusters de noeuds de capteurs basés sur les zones où il y
a un fort signal reçu, puis utiliser des clusters-heads locaux comme passerelle
pour atteindre la destination.

Cela permet d'économiser de l'énergie car les transmissions ne sont effectuées que
par les cluster-head plutôt que par tous les noeuds de capteurs.
 PEGASIS (Power-Efficient GAthering in Sensor Information Systems)

• est une version améliorée du protocole LEACH.

• PEGASIS forme des chaînes plutôt que des clusters de noeuds de

capteurs afin que chaque nœud transmette et reçoive uniquement des
données d'un voisin. Un seul noeud est sélectionné à partir de cette chaîne
pour transmettre à la station de base. L'idée de PEGASIS est qu'il utilise
tous les noeuds pour transmettre ou recevoir des données avec ses plus
proches voisins. Il déplace les données reçues de noeud à noeud, puis les
données seront agrégées jusqu'à ce qu'elles atteignent tous la station de
base.
Donc, chaque noeud du réseau est tour à tour un chef de file de la chaîne,
ainsi que responsable pour transmettre l'ensemble des données recueillies et
fusionnées par la chaîne de noeuds au niveau de la station de base.