Mise-à-jour du réseau

Nous  connaissons  dorénavant la représentation en graphe de notre réseau. Il faut maintenant mettre à jour les flots par rapport à l’ancienne itération ou rétroaction. Cela permet de réduire considérablement le temps d’exécution de l’algorithme de flot à coût minimal.

Le graphe de mise-à-jour est construit de manière suivante :

  • les coûts sont inversés : c devient 1/c;
  • les arcs dont la capacité est réduite prennent pour capacité cette baisse, ce sont des arcs marqués;
  • l’algorithme de Busacker & Gowen est effectué jusqu’à saturation de tous les arcs marqués (figure 16);
  • le graphe de mise à jour réduit le graphe de routage originel (figure 17);
  • l’algorithme de Busacker & Gowen est effectué sur le graphe originel mis à jour.

Ainsi nous avons un nouveau routage optimal de l’énergie.Sans titre10.png

Figure 15 : Routage avant mise-à-jour.

Sans titre9.png

Figure 16 : Algorithme de mise-à-jour du réseau.

Sans titre8.png

Figure 17 : Graphe mis à jour.
Publicités