MCFA : Minimum Cost Forwarding Algorithm
Ye et al. ont proposé l'algorithme MCFA (Minimum Cost Forwarding Algorithm), recherchant 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.
Pour prendre en compte les contraintes d'énergie des capteurs, MCFA utilise une méthode qui consomme moins de messages de contrôle. En effet, le problème de l'inondation est la prise de décision en tenant en compte seulement des optimums locaux. Ce qui engendre plusieurs émissions des messages ADV par le même noeud. Pour éviter cela, MCFA utilise un mécanisme de backoff. Le backoff permet de retarder la prise de décision sur la valeur locale du coût, en attendant la valeur optimale globale. L'intervalle du backoff dépend du coût du lien de réception : plus le coût est grand, plus on a de chance de recevoir une valeur plus optimale, donc on doit attendre plus de temps :
Init
Self.cost <- inf
OnRecvADV(cost,from)
If (cost+linkCost(from)<self.cost)
Self.cost <- cost+linkCost(from)
initBackof(cost+linkCost(from))
onBackoffTimeout()
broadcastADV(self.cost)
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 noeud relaie le paquet en remplaçant la valeur du coût par sa valeur locale :
OnRecvData(cost,from)
If (cost-linkCost(from)=self.cost)
broadcastData(self.cost)
