Abstract
Real-time end-to-end task scheduling in networked control systems (NCSs) requires the joint consideration of both network and computing resources to guarantee the desired quality of service (QoS). This paper introduces a new model for composite resource scheduling (CRS) in real-time networked control systems, which considers a strict execution order of sensing, computing, and actuating segments based on the control loop of the target NCS. We prove that the general CRS problem is NP-hard and study two special cases of the CRS problem. The first case restricts the computing and actuating segments to have unit-size execution time while the second case assumes that both sensing and actuating segments have unit-size execution time. We propose an optimal algorithm to solve the first case by checking the intervals with 100% network resource utilization and modify the deadlines of the tasks within those intervals to prune the search. For the second case, we propose another optimal algorithm based on a novel backtracking strategy to check the time intervals with the network resource utilization larger than 100% and modify the timing parameters of tasks based on these intervals. For the general case, we design a greedy strategy to modify the timing parameters of both network segments and computing segments within the time intervals that have network and computing resource utilization larger than 100%, respectively. The correctness and effectiveness of the proposed algorithms are verified through extensive experiments.
Introduction: The Challenge of Joint Resource Management
In modern Networked Control Systems (NCSs), such as autonomous drones or industrial robotics, tasks follow a rigid control loop: Sensing (data transmission over a network) $\rightarrow$ Computing (processing control logic on a CPU) $\rightarrow$ Actuating (sending commands back over the network). Historically, network and computing resources have been scheduled independently. This siloed approach was sufficient when computation was negligible. However, modern control methods like Model Predictive Control (MPC) or vision-based processing introduce significant computational delays.
When scheduled separately, these resources often become "fragmented." A system might have ample CPU capacity but no available network window to transmit the resulting command, leading to missed deadlines and degraded control quality. This paper addresses this by proposing the Composite Resource Scheduling (CRS) model, which treats the sensing, computing, and actuating segments as a single, dependent chain.
Complexity and Task Models
The authors demonstrate that the general CRS problem is NP-hard in the strong sense, proved via a reduction from the 3-Partition problem. To tackle this complexity, the research identifies and solves two specific sub-cases:
- The $h-1-1$ model: Characterized by long sensing times but short (unit-size) computing and actuating segments.
- The $1-m-1$ model: Characterized by short sensing and actuating segments but long computing times.
For the general case ($h_1-h_2-h_3$), where all segments have arbitrary lengths, the paper proposes a heuristic greedy strategy with a roll-back mechanism.
The "Tight Interval" Strategy
A core innovation of this work is the focus on "bottleneck" intervals rather than the entire timeline. For the $h-1-1$ and $1-m-1$ models, the proposed optimal algorithms identify Effective Network Tight Intervals (ENTI)—time windows where network resource utilization reaches 100%.
By identifying these intervals, the scheduler can "nudge" task deadlines, effectively pruning the search space. If a schedule fails, the algorithm uses a backtracking strategy to adjust timing parameters and resolve conflicts. Unlike previous models that often assumed non-preemptive phases, the CRS model allows network segments to be preemptive, providing the flexibility required for high-speed industrial networks.
Experimental Results
The algorithms were evaluated using 1,000 trials of synthetically generated task sets with varying utilization levels (0.2 to 0.9) using the UUniSort algorithm. Performance was compared against standard baselines like Earliest Deadline First (EDF) and a Z3 SMT solver.
Key findings include:
- Improved Schedulability: The CRS heuristic successfully scheduled 10-12% more cases than standard EDF or Least Laxity First (LLF) under high resource utilization (0.6–0.7).
- Efficiency: While the optimal SMT solver often took over two hours per case, the CRS algorithms achieved results in an average of 74 milliseconds, making them suitable for real-time system configuration.
- Near-Optimality: The heuristic performance remained within a 0.4% to 7% gap of the theoretical upper bound, even at extreme utilization levels.
Conclusion and Future Work
The CRS model provides a robust framework for managing the interdependencies of network and computing resources in NCSs. While currently focused on single-channel networks and uniprocessor CPUs, future work will extend these algorithms to multi-channel wireless environments and multi-core controllers. Additionally, the authors plan to validate these findings on physical testbeds to account for real-world factors like jitter and packet loss.
Summary updated