网络控制系统中的信息特征和信息调度

网络控制系统中的信息特征和信息调度
摘 要 文章首先阐述了网络控制系统中的信息特征和信息调度的概念和意义。根据网络控制系统的研究方法：调度与控制分开设计和调度与控制协同设计两大方面，介绍了网络控制系统中信息调度的研究现状。最后探讨了有待解决的问题和发展趋势。
关键词 网络控制系统；信息调度；静/动态调度；混合调度；调度与控制协同设计

1　引言
网络控制系统（Network Control System，NCS）是指传感器、控制器和执行器通过网络形成的闭环反馈控制系统。目前，大部分关于NCS的研究针对NCS存在的问题和特性建立系统模型、分析系统稳定性、给出控制方法和控制规律，以保证系统具有良好的稳定性和高质量的控制性能。然而NCS的性能不仅依赖于控制策略及控制规律的设计，而且还受到网络通信和网络资源的限制。信息调度尽量避免网络中信息的冲突和拥塞现象的发生，从而大大提高了网络控制系统的服务性能。
2 　NCS中的信息特征与信息调度概念
在NCS中网络传输的信息主要分为两类：实时性信息和非实时性信息[3]。实时性信息对时间要求非常苛刻，如果在规定时间的上限内某一信息未能起作用，则该信息将被丢弃，启用最新的信息。而在NCS信息调度策略中主要调度两类数据信息：周期性信息和非周期性信息。周期性信息是一种实时性信息，一般要求在传输周期时间内必须传送给目标节点，周期性信息也被称为时间触发信息或者同步信息。非周期性信息是指节点间的请求服务等信息，它们的发生时刻是随机的，非周期性信息也被称为事件触发信息、异步信息或者随机性信息。
此外，在NCS信息调度中不能忽视突发性信息，突发性信息指一些事先无法预知的突发性的或者随机的事件（例如报警信号、异常处理等），这类信息必须在一定时间内给予处理，否则系统可能出现异常甚至瘫痪。
在网络控制系统中，信息调度发生在应用层，即传感器、控制器与执行器之间信息传递的过程中。当系统网络中某节点发生数据传输碰撞时，信息调度规定节点的优先发送次序、发送时刻和时间间隔，以避免网络冲突。
在NCS中，如果网络控制系统的所有数据传输都能在任务时限内完成，则称网络控制系统的传输是可调度的。
3　典型的NCS信息调度算法
目前对网络控制系统中信息调度的研究主要分为调度与控制的分开设计和调度与控制的协同设计。
3.1　调度与控制的分开设计
在NCS的研究中，一类研究是针对通信网络，研究提高网络服务质量的信息调度方法；另一类研究是在一定的网络信息调度方法基础上，研究提高NCS性能的控制方法。因此，信息调度方法对改善NCS性能起着很大的作用。
根据信息对实时性的要求，信息调度分为静态调度（又称离线调度）、动态调度（又称在线调度）和混合调度。
3.1.1　静态优先级调度
目前静态调度算法很多，本文着重介绍以下几种典型的算法以及算法的改进。
速率单调静态优先级调度 (Rate Monotonic Scheduling Model) 算法的调度优先级由任务周期确定，在任务周期等于时限的同步实时任务系统中是最佳静态调度算法。但是该算法具有调度判定具有指数时间复杂度、对任务的执行周期限制的过于严格、只能处理具有固定周期的任务等缺点。鉴于上述缺点Lehoczky等[23]提出了扩大调度可行性条件的RM算法。Sha等[22]考虑到任务的阻塞，给出了非抢占服务方式下RM算法的可调度条件。叶明等[5]基于RM算法提出了一种新的实时调度算法(Hard Real-time Communication Scheduler，HRTCS)。文远保等[4]针对任务的周期和调度优先级关系不固定的流媒体提出了改进的RM算法。
截至时间单调调度模型(Deadline Monotonic Scheduling Model )策略的任务优先级由任务时限来决定。该调度算法要防止任务越过其时限而得不到调度，从而影响系统的实时性。当任务周期和时限相同或者所有同步周期性任务时，DM算法都是最佳静态调度算法。
由Hong等提出的基于时间窗的静态带宽调度算法避免了数据在网络传输过程中产生干扰和数据冲突。Hong等还将该调度方法应用于循环服务型NCS和CAN 网下的NCS中。
刘鲁源[6]等鉴于该调度方法只限于调度网络中的周期数据，提出基于同步相和异步相的时间窗调度算法，使非周期数据也可以采用该基于时间窗的静态调度算法。
3.1.2　动态优先级调度
在动态优先级调度算法中，任务的时间约束关系并没有完全确定，新任务的到达时间是未知的。下面介绍几种经典的动态优先级调度算法。
Liu和Layland提出的时限最早的任务优先调度（Earliest deadline first scheduling），任务优先级是任务时限与任务执行时刻的差，该算法对同步周期任务组是最佳的动态调度算法。鉴于EDF是抢占式调度算法，任务间的切换时需要大量开销。Baker[12]给出了非抢占士服务方式下EDF算法的可调度性条件。张惠娟等[11]提出了一种基于EDF算法的优先级驱动实时调度算法，较大程度地克服了EDF算法在多处理器系统中的调度缺点。刘怀等[10]提出了基于EDF算法的容错调度算法。张奇智等[7]采用非中断的EDF调度方法来改善周期性数据帧的端到端延迟。洪艳伟等[1]提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。
最小松弛优先调度(Least laxity first)和EDF算法可看作同类型的调度算法，任务优先级是完成时限和任务执行时刻的差再减去周期任务的执行时间。LLF算法尽量避免了长周期任务的频繁等待、执行，具有较小的抖动性。
最大误差优先—尝试一次丢弃(most error first-try once discard)是Walsh 等[8]人提出的基于在线获取的网络诱导传输误差和动态分配网络带宽的调度算法。
Otanez 等[9]人提出的基于死区的动态调度在确保系统性能的基础上动态地丢弃一定比率的数据，以减轻网络的负荷。但是当多个获准访问网络的数据包同时竞争网络资源时，该策略不能确定数据包发送的优先级。
基于业务平滑的动态调度是Kewon等利用业务平滑的技术控制Ethernet网的通信量，通过在Ethernet 网的UDP( TCP/ IP) 层和MAC 层插入定速率业务平滑器和自适应业务平滑器以限定MAC 层数据包的到达速率，并且保证网络诱导时延的有界性，从而提高网络的服务质量.
Cena等提出的优先级提升—分布式优先级排队调度( PP-DPQ)可以保证实时数据传输最大间隔具有确定上界，非实时数据在传输中公平地竞争网络资源。
基于时间窗的动态调度（Dynamic Time Window）是Raja对基于时间窗的静态调度算法进行改进，提出优先级循环服务和动态时间窗的带宽分配策略。
模糊动态调度是白涛[13]等将模糊控制理论引入到NCS 信息调度中，利用基于IF2THEN 规则的模糊逻辑确定数据传输的优先级。
3.1.3　混合调度
Zuberi等针对CAN 下网络控制系统，提出混合通信调度(MTS)策略。在设计调度策略时，考虑到数据实时性要求不同，可以分别采用不同的调度策略，以提高网络资源的可调度性。Tabuada等[27]给出的退火控制任务的事件触发实时调度是基于有反馈事例的事件触发调度器，并且给出了它如何保证系统性能的条件。
3.2　调度与控制的协同设计
目前关于控制与调度共同设计成为研究热点受到越来越多的重视，大体可分为开环调度和反馈控制实时调度两方面。
3.2.1　开环调度
1）对NCS 中各个控制环中数据传输节点采样周期和采样时刻的调度
Hong基于“窗口”的概念，给出了一种通过调度采样时间来减少时延的影响并提高网络利用率的调度算法，建立了NCS 控制系统性能与网络性能间的约束关系。但该算法是基于令牌环系统(token passing system) 和轮询系统(polling system) 的一文对象的调度，系统中信息类型仅限于周期性信息。Kim等[16 ]基于相同思想提出了适用于多文对象的采样时间调度算法。刘鲁源等[17 ]提出了利用剩余的时间窗口调度非实时数据提高了网络资源利用率的调度算法。
2）调度优化
Seto[19] 针对性能指标是单调递减并且是每一任务频率的凸函数的这样一类控制系统，提出了一种通过改变采样频率使得任务能被EDF和RM调度的新算法，而且系统的性能在有限计算资源的约束下可达到最优。但该算法没有考虑执行时间的变化与扰动问题。Cervin[20]考虑了具有时延变化的控制系统采样周期的选择问题，对低于一个采样周期的时延系统的采样周期进行了分析。Ryu 等[21] 以稳定状态误差、过冲、上升时间、沉降速度等作为控制性能参数，并将它们表示为采样周期和输入输出延时的函数，在可调度约束条件下用迭代算法对这些性能参数进行优化。何坚强等[24 ] 在上述研究的基础上给出了NCS 的优化模型并采用遗传算法来求取采样频率。Branicky 和Zhang 等[25 ]提出将非抢占RM调度算法应用于网络控制系统的调度，并给出了保证系统稳定和网络可调度的充分条件。在此基础上，Branicky等[26]进一步对网络传输时间进行了分配，给出了网络调度优化方法。
3.2.2 反馈控制实时调度
开环调度算法在负载能精确建模的动态或静态系统中可以取得很好的效果，可是在不可测的动态系统中，算法的有效性要极大地降低。近几年来，“闭环”调度由于可以应用于很多实时领域因而引起了很多人的关注。在Seto等提出的系统控制和调度离线集成设计的基础上，Cervin[14]提出一种将控制和调度动态弹性集成的框架，允许在线平衡控制性能和可用的计算资源。Stankovic等[18]提出了反馈控制实时调度的思想，而且还给出了一种结合PID 控制和EDF 调度器的反馈控制实时调度算法FC-EDF ( Feedback Control- Earliest Deadline First) 。汤贤铭等[2]提出了一种将动态死区控制和优先级分配相结合的反馈调度策略，用以解决在工作负载变动的环境中网络控制系统的控制与调度问题。Eker等[15]开发出了针对线性二次(Linear Quadratic) 控制的反馈控制器。在可调度的情况下通过调整控制环频率来优化控制性能。Zhao[28]提出了一种结合速率单调调度和新的动态调度的动态反馈调度，用于调度预控制器产生的控制信号的传输，该调度算法确保了系统的稳定性，并且保证系统时延不超过保证系统稳定的上限。
4 进一步可研究的参考方向
当前，NCS信息调度的研究已经取得了很多有益的成果。然而，NCS应用的复杂化以及NCS控制与调度的协调设计趋势，使得现有的信息调度方法已不能满足发展的需求。因此，给出信息调度的进一步研究问题和研究目标，以供参考。
（1）网络控制的复杂化和网络运行状况的多变性，需要智能化强、实时性好的在线调度算法。
（2）现有的研究结果大多限于单控制回路，对共享网络的多个控制回路的优化调度等问题需要进一步的研究。
（3）有带宽约束的变速率网络化控制系统的信息调度问题。
（4）不同数据流分配不同比例带宽，用来提高高优先级别数据流的服务质量，避免低优先级别的数据流由于网络超时而断开的研究。
（5）研究NCS 多目标优化问题的提取和求解。考虑网络利用率、数据包丢失率、系统稳定性等多重约束，建立NCS 多目标优化问题的数学模型。进而考虑NCS 的实时性要求，研究基于遗传算法等进化智能计算方法的NCS 分级多目标优化问题的求解方法。
（6）将系统性能的优化映射为较低层次的系统参数优化、网络参数选取、带宽资源调度问题，力求达到系统设计与网络实现的总体性能优化的目标。引入新的、更多的反映系统性能的优化指标，寻求新的融合网络与控制系统其它结合点将是未来的发展方向。
参考文献
[1] 洪艳伟，赖娟，杨斌.基于EDF 算法的可行性判定及实现.计算机技术与发展[J].2006，16(11)：97-102
[2] 汤贤铭，钱凯，俞金寿.网络控制系统动态死区反馈调度.华东理工大学学报[J].2007，33(5)：716-721
[3] 张庆灵，邱占芝.网络控制系统[M].北京市：科学出版社，2007.37-38
[4] 文远保，张炫.单调比率调度算法研究及改进.计算机工程与科学[J].2006，28(10)，68-70
[5] 叶明，罗克露，陈慧. 单调比率(RM)调度算法及应用.计算机应用[J].2005，25(4)：889-891
[6] LIU Luyuan，WAN Renjun，LI Bing. On static scheduling algorithm for networked control based on TTCAN protocol .Control and Decision[J ].2004，19 (7)： 814 - 816
[7] 张奇智，曹春生，张卫东.EDF 调度方法在交换式工业以太网中的实现.化工自动化及仪表[J]. 2004，31 (6)：41-43
[8] Walsh G C，Hong Ye. Scheduling of networked control systems . IEEE Control System Magazine[J].2001，21 (1)： 57 - 65
[9] Otanez P，Moyne J，Tilbury D. Using deadbands to reduce communication in networked control systems [A].The American Automatic Control Council[C]. Anchorage：Proceedings of the American control conference. 2002：615-619
[10] 刘怀，费树岷.基于EDF的分布式控制系统容错调度算法.软件学报[J].2003，14(8)1371-1378
[11] 张惠娟，周利华.一种基于EDF算法的多处理器实时调度算法.计算机工程与应用[J].2003，30(16)16-17
[12] 王智. 面向现场总线的分布式实时系统的建模与分析方法[D]. 博士，中国科学院，2000
[13] 白涛. 网络控制系统的性能分析与调度优化[D] . 硕士，上海交通大学，2005
[14] ARZEN K E，CERVIN A，EKER J . An introduction to control and scheduling co-design[A].In Proceedings of the 39th IEEE Conference on Decision and Control [C]Sydney： 2000，4865 - 4870
[15] EKER J，HAGANDER P，ARZEN K E. A feedback scheduler for real-time controller tasks. Control Engineering Practice[J].2000，8(12)：1369 -1378
[16] KIM Y H，PARK H S，KWON W H.A scheduling method for network based control systems[A]. In Proceedings of IEEE ACC[C].USA，1998：718 - 722
[17] 刘鲁源，万仁君，李斌. 基于TTCAN 协议的网络控制系统静态调度算法的研究.控制与决策 [J].2004，19(7)：813 - 816
[18] STANKOVIC J A，LU C Y，SON S H，et al . The case for feedback control real-time scheduling[A]. In Proceedings of the 11th Euromicro Conference on Real-Time Systems[C]. New York：1999，1：11 - 20
[19] SETO D，LEHOCZKYJ P，SHAL. Task period selection and schedulability in real-time systems[A]. In Proceedings of the 19th IEEE Real-time Systems Symposium[C]. Madrid，1998：188 - 198
[20] CERVIN A. Integrated control and real-time scheduling[D]. Ph. D. Dissertation，Department of Automatic Control Lund Institute of Technology，2003
[21] RYU M，HONG S. Toward automatic synthesis of schedulable real-time controllers. Integrated Computer aided Engineering[J].1998，5(3)：261 - 277
[22] TINDELL K，BUMS A. Analysis of Hard Real-time Communication. Real-Time System[J].1995，9(2)：147 - 173
[23] LEHOCZKYJ，SHAL，DING Y. The rate monotonic scheduling algorithm：exact characterization and average case behavior[A]. In Proceedings of IEEEReal-time Systems Symposium[C].Santa Monica：1989：166 - 171
[24] HE J Q，ZHANG H C，JING Y Z. A integrated control and scheduling optimization method of networked control systems. Journal of Electronic Science and Technology of China[J].2004，2(2)：56 - 59
[25] ZHANG W，BRANICKYM S，PHILIPS S M. Stability of networked control systems. IEEE Control Magazine[J].2001，21 (1)：84 - 99
[26] BRANICKYM S，PHILLIPS S M，ZHAN GW. Scheduling and feedbackcodesign for networked control systems. In Proceedings of IEEE Conference on Decision and Coutrol .Las Vegas[J].2002：1211 - 1217
[27] Tabuada，Paulo. Event- Triggered Real-Time Scheduling of Stabilizing Control Tasks. IEEE Transactions on Automatic Control[J].2007.9(52)： 1680-1685
[28] Zhao，Y. B. Integrated predictive control and scheduling co-design for networked control systems. Control Theory & Applications[J].2008，1(2)： 712