Network Estimation and Packet Delivery Prediction for Control over Wireless Mesh Networks

Résumé technique : Estimation de réseau et prédiction de la livraison de paquets pour le contrôle sur les réseaux maillés sans fil

Formulation du problème
La théorie actuelle des systèmes de contrôle en réseau (NCS) repose souvent sur des abstractions simplifiées de type point à point ou topologie en étoile, traitant les pertes de paquets comme des processus de Bernoulli indépendants et identiquement distribués (i.i.d.). Cette abstraction limite les connaissances du contrôleur sur les conditions du réseau, ce qui conduit à des performances sous-optimales. De plus, l'interface entre la couche réseau et la couche de contrôle est typiquement statique, ne transmettant que des probabilités de perte fixes plutôt que des informations d'état dynamiques.

Cet article traite du contrôle d'un système linéaire sur un réseau maillé sans fil multi-sauts sujet aux pertes de paquets. Le problème spécifique concerne une boucle de contrôle unique où un contrôleur situé au niveau du capteur doit envoyer des entrées de commande à un actionneur à travers un réseau présentant des pertes de paquets par rafales (bursty) et sans délais (en supposant que la dynamique de l'asservissement est nettement plus lente que l'échéance du réseau). Le défi central consiste à concevoir conjointement un estimateur de réseau et un contrôleur capable d'utiliser des prédictions détaillées et probabilistes des séquences de livraison de paquets futures afin de compenser les interruptions de réseau, plutôt que de s'appuyer sur des hypothèses i.i.d. statiques.

Méthodologie
Les auteurs proposent une architecture système (Figure 2) comprenant un estimateur de réseau ($\hat{N}$) et un contrôleur LQG optimisé pour la livraison future de paquets (FPD - Future-Packet-Delivery-optimized) ($C$).

1. Modélisation du réseau :
   Le réseau maillé sans fil est modélisé comme un graphe acyclique dirigé $G=(V, E)$ avec un calendrier TDMA (Time Division Multiple Access) fixe et répétitif. L'article introduit deux modèles de liens spécifiques :

   • SIHS (Liens statiques indépendants, routage par saut, planifié) : Suppose que les liens sont statiques (actifs ou inactifs) pendant le transit du paquet.
   • GEIHS (Liens de Gilbert-Elliott indépendants, routage par saut, planifié) : Modélise chaque lien comme une chaîne de Markov à deux états (modèle de Gilbert-Elliott) où les liens transitent entre des états « haut » et « bas » avec des probabilités spécifiques ($p_u, p_d$). Cela capture la nature par rafales des liaisons sans fil.
     Dans les deux modèles, les liens sont supposés indépendants, et le routage est effectué par saut avec des retransmissions en cas d'échec.

2. Estimation et prédiction du réseau :
   L'estimateur de réseau utilise l'estimation bayésienne récursive pour inférer l'état de la topologie du réseau sur la base de l'historique des livraisons de paquets passées (accusés de réception).

   • L'estimateur maintient une distribution de probabilité sur toutes les réalisations possibles de la topologie ($\tilde{G}$).
   • En utilisant le modèle de réseau et l'historique des livraisons de paquets, il calcule la distribution de probabilité jointe des séquences de livraison de paquets futures ($f_{\nu_k}^{k+H-1}$) sur un horizon fini $H$.
   • L'estimateur SIHS met à jour la croyance concernant la topologie statique en fonction des succès ou échecs observés.
   • L'estimateur GEIHS effectue une étape de prédiction (propagation de l'état de la chaîne de Markov vers l'avant) et une étape de mise à jour (incorporation de nouvelles observations), lui permettant de suivre les états de liaison variables dans le temps.
   • La sortie est une distribution de probabilité jointe des livraisons de paquets futures, capturant les corrélations entre les livraisons successives, qui est transmise au contrôleur.

3. Conception du contrôleur FPD :
   Le contrôleur minimise une fonction de coût LQG à horizon fini. Contra\times aux contrôleurs LQG classiques qui supposent des pertes de paquets i.i.d. ou une livraison parfaite, le contrôleur FPD utilise la distribution de probabilité jointe fournie par l'estimateur de réseau.

   • La politique de contrôle est dérivée par programmation dynamique (équation de Bellman).
   • Le gain de contrôle optimal $L_k$ dépend de l'espérance conditionnelle du coût futur, qui est calculée en énumérant toutes les séquences de livraison de paquets futures possibles, pondérées par leurs probabilités prédites.
   • Cela permet au contrôleur de « regarder vers l'avenir » et d'ajuster les entrées de commande en fonction de la probabilité de pertes de paquets futures, plutôt que de réagir uniquement à l'état actuel ou de supposer un comportement moyen.

Contributions clés

• Modélisation de réseau avancée : L'article dépasse les modèles de Bernoulli i.i.d. en utilisant un modèle de graphe avec une dynamique de lien de type Gilbert-Elliott et un calendrier TDMA spécifique, capturant la nature par rafales et corrélée des pertes de paquets dans les réseaux multi-sauts.
• Estimateur de réseau bayésien récursif : Les auteurs proposent deux estimateurs (SIHS et GEIHS) qui fournissent une distribution de probabilité jointe des livraisons de paquets futures. Cette interface transmet beaucoup plus d'informations (la distribution complète) au contrôleur que les méthodes traditionnelles (qui ne transmettent qu'une probabilité de perte scalaire).
• Contrôleur FPD optimal : Une dérivation d'un contrôleur LQG optimal qui utilise explicitement la distribution de probabilité jointe prédite des livraisons de paquets. Le contrôleur tient compte de la corrélation entre les pertes de paquets futures, permettant une compensation proactive.
• Analyse de complexité : L'article fournit une analyse rigoureuse de la complexité computationnelle, notant que bien que les estimateurs et les contrôleurs soient « optimaux » (aucune perte d'information), ils sont coûteux en termes de calcul (mise à l'échelle en $O(2^E)$ et $O(2^H)$), soulignant le compromis entre optimalité et faisabilité.

Résultats
L'article valide l'approche via un exemple de simulation impliquant un petit réseau maillé avec une topologie de routage et un calendrier spécifiques.

• Performance de l'estimation : L'estimateur GEIHS détecte avec succès une défaillance de liaison (liaison $(3, b)$) après une perte de paquet. Il met à jour ses prédictions, prévoyant correctement les pertes de paquets suivantes dues à la nature par rafales de la liaison et au chemin de routage.
• Performance du contrôle : Le contrôleur FPD est comparé à deux contrôleurs sous-optimaux : un contrôleur IID (supposant des pertes i.i.d.) et un contrôleur ON (supposant une livraison parfaite).
  • Lorsqu'une défaillance de liaison se produit, le contrôleur FPD, conscient de la haute probabilité de pertes futures, applique une entrée de commande plus importante plus tôt pour compenser.
  • Les contrôleurs IID et ON, manquant de cette prévoyance, appliquent des entrées plus faibles, supposant que les paquets futurs arriveront probablement.
  • Résultats quantitatifs : Dans une simulation de Monte-Carlo (10 000 exécutions), le contrôleur FPD a obtenu un coût LQG nettement inférieur (681,68) par rapport au contrôleur IID (1 008,2) et au contrôleur ON (1 158,9). Cela démontre que l'utilisation de prédictions de livraison de paquets corrélées améliore les performances de contrôle en présence d'interruptions de réseau par rafales.

Signification et affirmations
L'article affirme qu'en modélisant le réseau comme un graphe de liaisons avec des probabilités de succès de transmission et en utilisant un estimateur bayésien récursif, il est possible de fournir au contrôleur une distribution de probabilité jointe des livraisons de paquets futures. Cela permet au contrôleur de compenser plus efficacement les interruptions de réseau prédites que les contrôleurs reposant sur des modèles de perte simplifiés et indépendants.

Les auteurs notent avec modestie que leur approche est une étape vers une modélisation de réseau plus sophistiquée. Ils reconnaissent que le modèle GEIHS suppose l'indépendance des liaisons, ce qui peut ne pas capturer toutes les corrélations dans les réseaux réels, et que la complexité de calcul de la solution optimale est élevée. Cependant, ils affirment que le modèle GEIHS sert de base de comparaison précieuse et que l'architecture proposée démontre les avantages potentiels d'une interface plus riche entre les couches réseau et de contrôle. Ce travail suggère que les recherches futures devraient se concentrer sur des estimateurs « sous-optimaux » de plus faible complexité et sur des conceptions de contrôleurs robustes capables de gérer des prédictions inexactes.