Optimal Energy-Efficient Regular Delivery of Packets in Cyber-Physical Systems

Xueying Guo, Rahul Singh, P. R. Kumar, Zhisheng Niu

Abstract

In cyber-physical systems such as in-vehicle wireless sensor networks, a large number of sensor nodes continually generate measurements that should be received by other nodes such as actuators in a regular fashion. Meanwhile, energy-efficiency is also important in wireless sensor networks. Motivated by these, we develop scheduling policies which are energy efficient and simultaneously maintain "regular" deliveries of packets. A tradeoff parameter is introduced to balance these two conflicting objectives. We employ a Markov Decision Process (MDP) model where the state of each client is the time-since-last-delivery of its packet, and reduce it into an equivalent finite-state MDP problem. Although this equivalent problem can be solved by standard dynamic programming techniques, it suffers from a high-computational complexity. Thus we further pose the problem as a restless multi-armed bandit problem and employ the low-complexity Whittle Index policy. It is shown that this problem is indexable and the Whittle indexes are derived. Also, we prove the Whittle Index policy is asymptotically optimal and validate its optimality via extensive simulations.

Introduction

In modern Cyber-Physical Systems (CPS), such as in-vehicle wireless sensor networks, maintaining a steady stream of data is critical. Actuators rely on regular packet deliveries from sensors to ensure system stability and performance. If the inter-delivery time—the duration between successive successful packet receptions—becomes too long or irregular, the physical system can suffer from degraded performance or even instability.

However, most sensor nodes are battery-powered, making energy efficiency a paramount concern. This creates a fundamental conflict: frequent transmissions improve regularity but deplete energy, while infrequent transmissions conserve energy at the cost of regularity. Existing scheduling research often prioritizes throughput or average delay, which does not inherently guarantee the "regularity" required by CPS. This paper addresses this gap by developing a scheduling framework that explicitly balances energy consumption with a penalty for irregular deliveries.

Methodology

The authors approach the problem through several layers of mathematical modeling:

Markov Decision Process (MDP)

The system is initially modeled as an MDP where the state of each sensor is defined as the time elapsed since its last successful delivery. To handle the potentially infinite state space, a "Reduction Lemma" is proven, transforming the problem into an equivalent finite-state MDP by capping the state at a specific delivery threshold ($\tau_n$).

Restless Multi-Armed Bandit Problem (RMBP)

While the finite MDP is solvable, its computational complexity grows exponentially with the number of sensors ($N$), making it impractical for large-scale systems. To overcome this, the problem is reformulated as a Restless Multi-Armed Bandit Problem (RMBP). In this framework, each sensor acts as a "bandit" that can be either "active" (transmitting) or "passive" (waiting).

Whittle Index Policy

The core contribution is the derivation of the Whittle Index policy. The authors prove that the problem is indexable, allowing for the calculation of a "Whittle Index" for each sensor. This index represents the priority of scheduling a sensor based on its current state. A closed-form expression for the Whittle Index was derived:

$$W_n(i) = p_n(i + 1)(1 - p_n)^{\tau_n-(i+1)} - \eta E_n$$

This formula enables real-time scheduling with minimal computational overhead by simply ranking sensors according to their index values.

Results and Discussion

The proposed policy was evaluated through extensive numerical simulations involving up to 80 clients with heterogeneous characteristics.

The Energy-Regularity Trade-off

The parameter $\eta$ serves as a tuning knob for the system. By adjusting $\eta$, operators can navigate the trade-off between energy efficiency and delivery regularity. As shown in Figure 1, increasing $\eta$ significantly reduces average energy consumption, though it leads to a predictable increase in the inter-delivery penalty.

Trade-off between inter-delivery penalty and energy consumption for varying \eta.

Asymptotic Optimality

A key theoretical and practical result is the asymptotic optimality of the Whittle Index policy. Using fluid model analysis, the authors proved that as the number of sensors $N$ increases, the policy's performance converges to the theoretical optimal lower bound. Simulation results in Figure 2 confirm this, showing that the optimality gap becomes negligible as the number of clients reaches 40–50.

Performance comparison between the Whittle Index policy and the relaxed optimal policy as the number of clients increases.

Conclusion

This research provides a robust framework for energy-efficient scheduling in CPS. By leveraging the Whittle Index policy, the system achieves near-optimal performance with low computational complexity, making it suitable for real-time implementation on low-power hardware.

Future work may address the limitations of static channel probabilities by incorporating time-varying success rates ($p_n$) to better reflect real-world wireless environments. Additionally, exploring dynamic delivery thresholds based on the physical state of the system could further enhance the adaptability of the scheduling policy.

Summary updated

Abstract

In cyber-physical systems such as in-vehicle wireless sensor networks, a large number of sensor nodes continually generate measurements that should be received by other nodes such as actuators in a regular fashion. Meanwhile, energy-efficiency is also important in wireless sensor networks. Motivated by these, we develop scheduling policies which are energy efficient and simultaneously maintain "regular" deliveries of packets. A tradeoff parameter is introduced to balance these two conflicting objectives. We employ a Markov Decision Process (MDP) model where the state of each client is the time-since-last-delivery of its packet, and reduce it into an equivalent finite-state MDP problem. Although this equivalent problem can be solved by standard dynamic programming techniques, it suffers from a high-computational complexity. Thus we further pose the problem as a restless multi-armed bandit problem and employ the low-complexity Whittle Index policy. It is shown that this problem is indexable and the Whittle indexes are derived. Also, we prove the Whittle Index policy is asymptotically optimal and validate its optimality via extensive simulations.
BibTeX
@inproceedings{guo2015optimal,
  author = {Xueying Guo and Rahul Singh and P. R. Kumar and Zhisheng Niu},
  title = {{Optimal Energy-Efficient Regular Delivery of Packets in Cyber-Physical Systems}},
  booktitle = {ICC},
  year = {2015},
  doi = {10.1109/icc.2015.7248814},
}
Figure