Composite Resource Scheduling for Networked Control Systems
Composite Resource Scheduling for Networked Control Systems
复制标题
DOI：
10.1109/rtss52674.2021.00025
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Peng Wu;Chenchen Fu;Tianyu Wang;Minming Li;Yingchao Zhao;C. Xue;Song Han
中科院分区：
文献类型：
--
作者：
Peng Wu;Chenchen Fu;Tianyu Wang;Minming Li;Yingchao Zhao;C. Xue;Song Han
网络控制系统（NCS）中的实时端到端任务调度需要共同考虑网络和计算资源，以保证所需的服务质量（QoS）。本文介绍了一种实时网络控制系统中复合资源调度（CRS）的新模型，该模型根据目标 NCS 的控制环路考虑了传感、计算和驱动部分的严格执行顺序。我们证明了一般的 CRS 问题是 NP 困难的，并研究了 CRS 问题的两个特殊情况。第一种情况限制计算和致动段具有单位大小的执行时间，而第二种情况则假设感测和致动段都具有单位大小的执行时间。我们提出了一种最佳算法来解决第一种情况，通过检查网络资源利用率为 100% 的时间间隔，并修改这些时间间隔内任务的截止时间来修剪搜索。对于第二种情况，我们提出了另一种基于新颖回溯策略的优化算法，以检查网络资源利用率大于100%的时间间隔，并根据这些间隔修改任务的计时参数。对于一般情况，我们设计了一种贪心策略，在网络和计算资源利用率大于100%的时间间隔内分别修改网络段和计算段的时序参数。通过大量的实验验证了所提出算法的正确性和有效性。
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.