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

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

Problem Formulation
Current Networked Control Systems (NCS) theory often relies on simplified point-to-point or star-topology abstractions, treating packet losses as independent and identically distributed (i.i.d.) Bernoulli processes. This abstraction limits the controller's knowledge of network conditions, leading to suboptimal performance. Furthermore, the interface between the network and control layers is typically static, passing only fixed loss probabilities rather than dynamic state information.

This paper addresses the control of a linear plant over a lossy, multi-hop wireless mesh network. The specific problem involves a single control loop where a controller at the sensor must send control inputs to an actuator through a network with bursty packet losses and no delays (assuming the plant dynamics are significantly slower than the network deadline). The core challenge is to jointly design a network estimator and a controller that can utilize detailed, probabilistic predictions of future packet delivery sequences to compensate for network outages, rather than relying on static, i.i.d. assumptions.

Methodology
The authors propose a system architecture (Figure 2) comprising a network estimator ($\hat{N}$) and a Future-Packet-Delivery-optimized (FPD) Linear Quadratic Gaussian (LQG) controller ($C$).

1. Network Modeling:
   The wireless mesh network is modeled as a directed acyclic graph $G=(V, E)$ with a fixed, repeating Time Division Multiple Access (TDMA) schedule. The paper introduces two specific link models:

   • SIHS (Static Independent links, Hop-by-hop routing, Scheduled): Assumes links are static (either up or down) during the packet's transit.
   • GEIHS (Gilbert-Elliott Independent links, Hop-by-hop routing, Scheduled): Models each link as a two-state Markov chain (Gilbert-Elliott model) where links transition between "up" and "down" states with specific probabilities ($p_u, p_d$). This captures the bursty nature of wireless links.
     In both models, links are assumed to be independent, and routing is hop-by-hop with retransmissions upon failure.

2. Network Estimation and Prediction:
   The network estimator uses recursive Bayesian estimation to infer the state of the network topology based on the history of past packet deliveries (acknowledgements).

   • The estimator maintains a probability distribution over all possible topology realizations ($\tilde{G}$).
   • Using the network model and the history of packet deliveries, it computes the joint probability distribution of future packet delivery sequences ($f_{\nu_k}^{k+H-1}$) over a finite horizon $H$.
   • The SIHS estimator updates the belief about the static topology based on observed successes/failures.
   • The GEIHS estimator performs a prediction step (propagating the Markov chain states forward) and an update step (incorporating new observations), allowing it to track time-varying link states.
   • The output is a joint probability distribution of future packet deliveries, capturing correlations between successive deliveries, which is passed to the controller.

3. FPD Controller Design:
   The controller minimizes a finite-horizon LQG cost function. Unlike classical LQG controllers that assume i.i.d. packet losses or perfect delivery, the FPD controller utilizes the joint probability distribution provided by the network estimator.

   • The control policy is derived via dynamic programming (Bellman equation).
   • The optimal control gain $L_k$ depends on the conditional expectation of the future cost-to-go, which is calculated by enumerating all possible future packet delivery sequences weighted by their predicted probabilities.
   • This allows the controller to "look ahead" and adjust control inputs based on the likelihood of future packet losses, rather than reacting only to current state or assuming average behavior.

Key Contributions

• Advanced Network Modeling: The paper moves beyond i.i.d. Bernoulli models by utilizing a graph-based model with Gilbert-Elliott link dynamics and a specific TDMA schedule, capturing the bursty and correlated nature of packet losses in multi-hop networks.
• Recursive Bayesian Network Estimator: The authors propose two estimators (SIHS and GEIHS) that provide a joint probability distribution of future packet deliveries. This interface passes significantly more information (the full distribution) to the controller than traditional methods (which pass only a scalar loss probability).
• Optimal FPD Controller: A derivation of an optimal LQG controller that explicitly uses the predicted joint probability distribution of packet deliveries. The controller accounts for the correlation between future packet losses, allowing for proactive compensation.
• Complexity Analysis: The paper provides a rigorous analysis of the computational complexity, noting that while the estimators and controllers are "optimal" (no information loss), they are computationally expensive ($O(2^E)$ and $O(2^H)$ scaling), highlighting the trade-off between optimality and feasibility.

Results
The paper validates the approach through a simulation example involving a small mesh network with a specific routing topology and schedule.

• Estimation Performance: The GEIHS estimator successfully detects a link failure (link $(3, b)$) after a packet loss occurs. It updates its predictions, correctly forecasting subsequent packet losses due to the bursty nature of the link and the routing path.
• Control Performance: The FPD controller is compared against two suboptimal controllers: an IID controller (assuming i.i.d. losses) and an ON controller (assuming perfect delivery).
  • When a link failure occurs, the FPD controller, aware of the high probability of future losses, applies a larger control input earlier to compensate.
  • The IID and ON controllers, lacking this foresight, apply smaller inputs, assuming future packets will likely arrive.
  • Quantitative Results: In a Monte-Carlo simulation (10,000 runs), the FPD controller achieved a significantly lower LQG cost (681.68) compared to the IID controller (1,008.2) and the ON controller (1,158.9). This demonstrates that utilizing correlated packet delivery predictions improves control performance in the presence of bursty network outages.

Significance and Claims
The paper claims that by modeling the network as a graph of links with transmission success probabilities and using a recursive Bayesian estimator, it is possible to provide the controller with a joint probability distribution of future packet deliveries. This allows the controller to compensate for predicted network outages more effectively than controllers relying on simplified, independent loss models.

The authors modestly note that their approach is a step toward more sophisticated network modeling. They acknowledge that the GEIHS model assumes link independence, which may not capture all correlations in real-world networks, and that the computational complexity of the optimal solution is high. However, they assert that the GEIHS model serves as a valuable basis for comparison and that the proposed architecture demonstrates the potential benefits of a richer interface between the network and control layers. The work suggests that future research should focus on lower-complexity "suboptimal" estimators and robust controller designs that can handle inaccurate predictions.