La propagation et la délivrance des données
dans un RCSF représentent la fonctionnalité la plus importante du
réseau. Elle doit prendre en considération toutes les
caractéristiques des capteurs afin d'assurer les meilleures performances
du système : durée de vie, fiabilité, temps de
réponse, ... etc.
Vu la spécificité des RCSF, un nombre important
de recherches sont orientées vers une violation du découpage en
couches protocolaires indépendantes, et introduisent la notion de cross
layer optimisation. Par exemple, en utilisant des mécanismes
d'agrégation, les routeurs intermédiaires doivent accéder
à la donnée afin d'établir des résumés des
lectures de la région [9].
III.2.1 Taxonomie des protocoles de routages
Taxonomie
Récemment, les protocoles de routage pour les RCSF ont
été largement étudiés, et différentes
études ont été publiées. Les méthodes
employées peuvent être classifiées suivant plusieurs
critères comme illustré sur la figure suivante :
Topologie du réseau [9]
La topologie détermine l'organisation des capteurs dans
le réseau. Il existe deux principales topologies dans les protocoles de
routage pour les RCSF.
> Topologie plate : dans une topologie
plate, tous les noeuds possèdent le même rôle. Les noeuds
sont semblables en termes de ressources.
> Topologie hiérarchique : afin
d'augmenter la scalabilité du système, les topologies
hiérarchiques ont été introduites en divisant les noeuds
en plusieurs niveaux de responsabilité. L'une des méthodes les
plus employées est le clustering, où le réseau est
partitionné en groupes appelés "clusters". Un cluster est
constitué d'un chef (cluster-head) et de ses membres.
57
Etablissement de la route
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 séparés en trois
catégories : les protocoles proactifs, les protocoles réactifs et
les protocoles hybrides. [32]
> Protocole proactif : Ces protocoles de
routage essaient de maintenir les meilleurs chemins existants vers toutes les
destinations possibles au niveau de chaque noeud du réseau. Les routes
sont sauvegardées mêmes si elles ne sont pas utilisées.
Chaque noeud du réseau maintient une table de routage pour toutes les
destinations indépendamment de l'utilité des routes. Les
protocoles proactifs sont adaptés 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 leur
dispositif de capture qu'à des instants particuliers.
> Protocole réactif : Ces
protocoles (dits aussi, les protocoles de routage à la demande)
créent et maintiennent des routes selon les besoins. Lorsque le
réseau a besoin d'une route, une procédure de découverte
de route est lancée. Ce type de protocoles est pratique pour des
applications temps réel où les capteurs doivent réagir
immédiatement à des changements soudains des valeurs
captées. En effet, un prélèvement périodique des
données aurait été inadapté pour ce type de
scénarios.
> Protocole hybride : Ces protocoles
combinent les deux idées des protocoles proactifs et réactifs.
Ils utilisent un protocole proactif pour apprendre le proche voisinage (par
exemple le voisinage à deux ou à trois sauts), ainsi, ils
disposent de routes immédiatement dans le voisinage. Au-delà de
la zone du voisinage, le protocole hybride fait appel à un protocole
réactif pour chercher des routes.
Heinzelman et al ont proposé une famille de protocoles
appelée SPIN (Sensor Protocols for Information via Negotiation),
reposant sur un modèle de négociation afin de propager
l'information dans un réseau de capteurs. 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).
· L'ignorance des ressources, car d'inondation ne prend pas
en considération les ressources des noeuds.
Ces trois problèmes affectent grandement la durée
de vie et les performances du réseau. Pour les résoudre, SPIN
adopte deux principes :
o 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.
o 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.
La figure suivante illustre ces trois étapes :
59
III.2.2.2 Directed Diffusion [9]
Aperçu
Directed Diffusion est un protocole de propagation de
données, permettant d'utiliser plusieurs chemins pour le routage
d'information. Le puits diffuse un intérêt sous forme de
requête, afin d'interroger le réseau sur une donnée
particulière. Il se base sur le modèle publish/subscribe. DD
repose sur quatre éléments : nomination des données,
propagation des intérêts et établissement des gradients,
propagation des données et renforcement des chemins.
1. Nomination des données
L'adressage dans DD utilise un schéma attribut-valeur
afin de décrire les intérêts et les rapports de
données.
Exemple : Nomination des données
Par exemple, dans une application de protection de forêts,
une requête peut être effectuée sous cette forme :
Type = GetTemperature Zone = [100, 100, 120, 120]
Interval = 10 ms
Durartion = 1 mn
Une réponse d'un capteur pourra être
formulée ainsi :
Type = GetTemperature Location = (110, 115) Temperature
= 32
Timestamp = 11:32:10
2. 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.
Figure3.3 Propagation des intérêts et
établissement des gradients.
61
Propagation des l'intérêts
Afin de propager l'intérêt, DD emploie l'inondation
globale du réseau. Chaque noeud maintient localement un cache
d'intérêt contenant les informations suivantes :
· La description de l'intérêt, en utilisant le
schéma de nomination.
· Un ensemble de gradients.
Définition : Gradient
Un gradient est un vecteur représentant
l'intérêt. Il est caractérisé par une direction et
une amplitude : la direction est modélisée par le voisin
émetteur de l'intérêt, et l'amplitude est
représentée par le débit de données. En plus,
chaque entrée contient un champ limitant la durée de
validité du gradient.
Méthode : Etablissement des gradients
Lorsqu'un noeud reçoit un intérét, il
parcourt son cache :
· Si le cache ne contient aucune entrée relative
à l'intérêt reçu, une nouvelle entrée est
créée avec un gradient vers le voisin émetteur.
· Dans le cas contraire, le noeud recherche un gradient
vers le voisin émetteur, et met à jour en conséquence
l'entrée en question.
Après le traitement du cache, le noeud relaie
l'intérêt vers ses voisins. La méthode la plus simple est
d'utiliser l'inondation.
3. 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 calcule 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).
Lorsqu'un noeud reçoit une donnée, il recherche un
intérét équivalent dans son cache. Siaucune
entrée n'est trouvée, le paquet est supprimé. Dans le cas
contraire, en consultant la liste des gradients, le noeud relaie la
donnée vers ses voisins, suivant le débit de chacun d'eux.
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.
4. 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.
Figure3.4 Renforcement des chemins
? 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.
