第40卷第5期　2006年5月上海交通大学学报J OU RNAL OF SHAN GHA I J IAO TON G UNIV ERSIT YVol.40No.5　May 2006　收稿日期:2005206208作者简介:周平方(19762),男,湖南常宁人,博士生,主要从事实时系统、计算机控制系统等研究,E 2mail :zhoupf @.谢剑英(联系人),男,教授,博士生导师,电话(Tel.):021*********. 文章编号:100622467(2006)0520838205实时控制系统一种基于模型预测控制的反馈调度周平方,　谢剑英(上海交通大学自动化系,上海200030)摘　要:提出一种基于模型预测控制(M PC )的反馈调度算法(FS 2M PC ),可以在有限计算资源的情况下改进实时控制系统的性能.将被控的实时调度过程模型化为受约束的任务集密度控制问题.在FS 2MPC 算法中,约束条件保证任务集在最早截止时限优先(EDF )算法下是可调度的;同时,M PC 的优化目标通过减小控制任务的截止时限使整个任务集的密度尽可能接近100%,从而提高控制任务的优先级,降低输出抖动.仿真结果表明,在有限计算资源的情况下,FS 2M PC 显著地降低了由调度过程引起的控制性能损失.关键词:实时控制系统;反馈调度;模型预测控制;最早截止时限优先中图分类号:TP 273 文献标识码:AA Model Predictive Control 2Based Feedback Schedulingfor Real 2T ime Control SystemsZ HOU Pi ng 2f ang ,　X I E J i an 2y i ng(Dept.of Automation ,Shanghai Jiaotong Univ.,Shanghai 200030,China )Abstract :A feedback scheduling based on model p redictive control (FS 2M PC )was presented to improve t he cont rol performance of real 2time control system subject to limited comp utational resource.The controlled real 2time scheduling is modelled as a const rained density cont rol p roblem of t he total task set.In t he FS 2M PC ,t he const raint s guarantee t hat t he task set is schedulable by EDF (earliest deadline first )algorit hm.At t he same time ,t he optimization goal of M PC (model p redictive cont rol )makes t he density of t he total task set as clo se to 1as po ssible t hrough shortening cont rol tasks ’deadlines.As a result ,t he cont rol tasks obtain higher p riorities and t he outp ut jitter is reduced.The simulation result s illust rate t hat t he schedu 2ling induced control performance lo ss is reduced greatly by t he FS 2M PC subject to limited comp utational resource.Key words :real 2time cont rol system ;feedback scheduling (FS );model p redictive control (M PC );earliest deadline first (EDF ) 现代实时控制系统(R TCS )通常是基于一个实时内核,多个闭环控制任务在内核的基础上竞争性地使用共享的处理器时间.因此,处理器的时间被当作是一种最重要的资源,需要一定的调度算法来将其分配给各个任务.这样就可能引起控制任务的抖动,尤其是当周期很短、处理器利用率很高的时候.文献[1,2]中说明了控制任务中由调度引起的抖动的存在降低了R TCS的性能,甚至可能导致系统的不稳定.另外,从控制理论的角度来看,抖动还可以进一步分为采样的抖动(采样时刻的变化)以及输出的抖动(控制量输出时刻的变化).但是,如果A/D 转换是由时间触发的,没有包含在控制任务的内部,则可以认为采样是没有抖动的.这样,只需要考虑输出的抖动.在实时调度理论方面,一个直接而有效的减小输出抖动的方法就是给任务分配更紧的截止时限,而不是简单地等于其周期,然后按照任务的截止时限来调度任务[3].最近在控制理论方面的成果也证实了有可能通过截止时限分配来限定最大允许时变延迟的边界,并依此提供系统的稳定性保证[4,5].尽管给任务分配一个更小的截止时限有利于减少抖动,却使得整个任务集的可调度性变得较差.文献[6]在此基础上,加入任务集的可调度性约束条件,用线性规划的方法来分配任务的截止时限,但所采用的方法都是离线和静态的.反馈调度[7]的提出使得在线地分配截止时限成为可能,而目前已有的反馈调度方法[7,8]还没有显式地把有限的计算资源当作约束条件来处理.本文在最早截止时限优先(EDF)[9]算法的框架下,提出了一种基于模型预测控制(M PC)的反馈调度算法(FS2M PC),该算法在满足资源和可调度性约束的范围内动态调节控制任务的截止时限.约束条件保证任务集在EDF算法中是可调度的;同时, M PC的优化目标减小控制任务的截止时限使得任务集的密度尽可能地接近100%.这样,控制任务获得了更高的优先级,从而降低了输出抖动.1　问题描述1.1　E DF可调度性条件考虑单处理器环境下周期性任务的抢占式调度.基本的调度算法为EDF,它是按照绝对截止时限给任务指定优先级,时限越早,任务的优先级越高,并且已经证明是动态的最优调度算法.以Γ={τ1,τ2,…,τn}代表周期性任务组成的任务集,Γ′<Γ代表Γ中那些对抖动敏感的控制任务组成的子集.其他对抖动不敏感的周期任务,如状态监视任务等,组成Γ′的补集,由Γ′<Γ表示.每个任务τi由(T i,e i,D i)描述,其中,T i、e i和D i分别为任务的周期、最坏情况下执行时间和相对截止时限.目前使用得最广泛的EDF算法可调度性条件如以下定理[10]所述.定理　在抢占式单处理器环境中,周期性任务集Γ如果满足6n i=1e imin(D i,T i)≤1,则该任务集是可以被EDF算法所调度的.在该定理中,e imin(D i,T i)被称为任务τi的密度.所有任务密度之和称为整个任务集的密度,由Y 表示.当存在某个D i<T i时,密度Y大于相应的处理器利用率U U=6n i=1e i T i,这时,该不等式仅仅是可调度性的充分条件.本文采用的反馈调度方法是一种在线的方法,这种线性测试由于简便且易于理解,因而是比较合适的.1.2　问题描述对于Γ′中的任务,假定D i=T i.但是对于Γ′中的控制任务,令D i=T i/c,其中c(k)≥1,即所有控制任务截止时限的调节幅度相对于各自的周期是一样的.另外,由事件触发的非周期任务,如告警发布等,被当作是实时调度过程中的扰动.为简便起见,本文通过设置服务器机制将这些事件触发的非周期任务当成周期任务一并处理.因此整个任务集系统的密度Y由3部分组成:对抖动敏感的控制任务子集Γ′的密度YΓ′,对抖动不敏感的其他周期任务子集Γ′的密度YΓ′以及随时间变化的非周期任务处理器利用率Dist(k).其中, YΓ′等于其处理器利用率因子,YΓ′=UΓ′=6τi∈Γ′e i T i,为常数.选取整个任务系统密度作为输出y(k),控制任务子集密度作为状态变量x(k),截止时限调节因子作为控制量c(k).假定控制量输入c(k)与状态变量x(k)之间的关系为x(k+1)=f(x(k),c(k)).因此,被控的实时调度过程被模型化为整个任务集的密度控制问题,从而将R TCS中反馈调度的M PC问题描述为:被控对象x(k+1)=f(x(k),c(k))y(k)=x(k)+UΓ′+Dist(k)(1) 约束条件c(k)≥1,　y(k)≤1(2) 模型预测控制器的优化目标是使下面目标函数最小化:V(k)=6P i=1‖y(k+i|k)-r‖2Q+6M-1i=0‖Δc(k+i|k)‖2R(3)938　第5期周平方,等:实时控制系统一种基于模型预测控制的反馈调度 式中:P 为预测时域长度;M 为控制时域长度;Q 为跟踪误差权重;R 为控制量变化的惩罚权重;r 为y (k )的设定值.控制量受到c (k )≥1的约束.约束条件y (k )≤1是源于EDF 算法的可调度性条件.为了与约束条件保持一致,r 不应超过1.在本文中,r 被设置为等于1,即100%.由于M PC 在本质上是一个优化算法,FS 2M PC 会在每个周期中使目标函数最小化,这样控制器就会通过减小控制任务的截止时限使任务集的密度y (k )尽可能地接近其设定值100%.需要指出的是,y (k )的值是通过对实际测量到的处理器利用率以及控制任务额外增加的那部分密度两者求和得到的.1.3　被控对象的模型被控的多任务实时调度过程在本质上属于离散对象.建立被控对象的模型就是要导出控制量输入c (k )与状态变量x (k )之间的差分方程x (k +1)=f (x (k ),c (k )).显然,容易导出状态变量x (k )的稳态值Y Γ′=U Γ′c (k ),其中U Γ′=6τi∈Γ′e iT i 为子集Γ′的处理器利用率因子.在一般的离散事件系统中,x (k )通常是指在第k 个采样时刻的值.但是,在FS 2MPC 中,控制任务子集密度x (k )的概念是针对某一特定时间窗口而言的,该时间窗口即为FS 2MPC 的采样周期.由于各个任务的激活、执行并不同步,故控制量c (k )的改变并不能立即在状态变量x (k )中得到反映,而是存在由多步但是比较短暂的延迟组成的过渡过程.本文将这个过渡过程近似为时间常数为0<σ<1的惯性环节,从而得到c (k )和x (k )之间的差分方程如下:x (k +1)=σx (k )+U Γ′(1-σ)c (k )(4)也可以将上式改写成z 域的传递函数:X (k )C (k )=U Γ′(1-σ)z -11-σz-1(5) 根据上述描述和被控对象的模型,可以得到FS 2M PC 的框图如图1所示.其中,时间常数σ的值通过测量辨识得到,通常得到的σ值比较小,在0.05～0.25.图1　FS 2MPC 的框图Fig.1　The block diagramof FS 2MPC2　RTCS 中的FS 2MPC2.1　概　述R TCS 中的FS 2M PC 是基于Matlab 的两个工具箱开发的一个仿真器,如图2所示.一个为M PC 工具箱,该工具箱实现了反馈调度中的控制器;另一个为T rue Time 工具箱[2,11],该工具箱提供了一个实时内核,称为T rue Time 内核.开发的FS 2MPC 本身在该内核中作为一个周期性系统任务运行.图2　实时控制系统中FS 2MPC 的结构Fig.2　The architecture of FS 2MPC for R TCS 在图2中存在两个层次上的闭环控制.外部的N 个闭环,它们控制着相应的N 个对象,如电动机、锅炉等,是实际的物理过程,类似于分布式控制系统(DCS )或PL C 中的多回路控制应用.内部的闭环控制,用来在实时调度中动态调节控制任务的截止时限,即为FS 2M PC.2.2　模型预测控制器MPC 由于能够方便地处理约束条件,因而被应用在本文的实时调度过程中.根据上一节的描述,为FS 2M PC 设计了一个模型预测控制器.由于M PC核心计算过程已经被封装在工具箱中,控制器的设计主要是进行参数选择.由于被控对象的主要特征为包含一个采样周期的滞后,故可以先选择预测时域长度P =2;为简单起见选择控制时域长度M =1;假定跟踪误差权重Q =1,控制量变化惩罚权重R =0(FS 2M PC 为单输入单输出形式,Q 、R 均为数值而非矢量).由于FS 2M PC 本身是作为一个周期任务在内核中运行的,必须认真地选取该任务的周期T s .选择短的周期对FS 2M PC 的性能是有利的,但是会消耗较多的处理器资源;长的周期消耗处理器资源较少,但是会降低性能.另外,该周期必须足够长,以便48上　海　交　通　大　学　学　报第40卷　能够正确测量出处理器利用率的值,因为该值是通过在内核中对空闲时间的统计得出的.2.3　稳定性分析这里讨论的稳定性指的是图2中内环,即FS2 M PC的稳定性.具有终端约束条件的M PC中一个简单而有效的稳定性判据是:如果最优问题是可解的,并且在每一步都求出了解,则平衡点是稳定的[12],即可解性意味着稳定性.在FS2M PC中,平衡点就是输出的任务集密度的设定值.也就是说,如果模型预测控制器总能计算出合适的操作变量c(k),则输出变量y(k)就能收敛到设定值.显然,对于FS2 M PC,当且仅当下式成立时能得到合适的c(k):6τi ∈Γe iT i+Dist max≤1(6)式中,Dist max为Dist(k)的最大值.该稳定性条件的含义是比较明显的.这是因为,如果式(6)成立,意味着处理器负荷不足,即存在一定的处理器裕量,则处理器的这部分裕量就可以用来减小控制任务的截止时限.因此,总是能得到合适的c(k)值使得满足约束条件式(2),反之亦然.实际上式(6)是反馈调度中隐含的硬的资源约束.由于实际的处理器利用率不会超过1,该约束条件的含义是很明显的.因此,除了在过负荷的情形外,FS2M PC是稳定的.3　仿真实验及结果3.1　仿真实验的建立为了说明FS2M PC如何改善R TCS的性能,对一组相同的伺服电机做了大量的仿真实验.每个伺服电机的闭环控制描述如下:(1)伺服电机的传递函数G M(s)=1000s(s+1);(2)控制策略为PD(Proportional Differenti2 al),其参数选择为比例系数K=1.2,微分系数T d =0.05;(3)控制任务的执行时间假定为0.4ms;(4)采样周期为10ms;(5)参考输入为正弦曲线,幅值为2,周期4s.另外,预先产生一组对抖动不敏感的周期性任务,并动态地产生一组非周期任务用来模拟扰动的情形.FS2M PC的周期选择为100ms,其执行时间假定为8ms,这样相当于FS2MPC本身占处理器资源为8%.在仿真实验中,改变控制任务的个数,保持任务集其余部分不变,对FS2M PC进行了实验.仿真实验的参数如表1所示,仿真时间设为2s.表1　仿真参数T ab.1　The parameters for simulation 任务类型执行时间/ms周期/ms任务个数控制任务0.4104,6,8,10,12,14,16其他周期任务0.310～5015非周期任务0.550～15030FS2MPC810013.2　仿真实验及结果在仿真实验中,对采用FS2M PC与其他不同的调度策略以及不同的控制任务个数时的伺服电机的控制性能进行比较.第1组仿真实验是在单任务模式下进行的,也就是不加入True Time内核,用来得到在没有计算资源约束时伺服电机的理想控制性能.第2组仿真实验用来说明在有限的计算资源约束下,控制性能受到了怎样的损害.在True Time内核中,有10个伺服电机控制任务,以及一些其他的周期任务,并且在0.4s时动态产生一组非周期任务(见表1).调度算法采用基本的EDF算法.将在这组仿真实验中得到的伺服电机典型响应曲线与其在理想情况下的曲线进行对比,结果如图3(a)所示.由图3(a)可见,由于调度过程产生的抖动降低了控制性能,伺服电机的响应曲线明显偏离了所对应的理想情形.第3组仿真实验用来说明采用FS2M PC以后,通过尽可能地减小控制任务的截止时限,控制性能得到了改善.任务集的组成跟第2组实验相同,只是在内核中加入了FS2M PC以调节控制任务的截止时限.实验结果如图3(b)所示.在这次仿真实验中, FS2M PC的任务集密度y(k)、扰动Dist(k)和操作变量c(k)变化情况如图4所示.由图3(b)可见,即使有动态到达的非周期任务产生的扰动,伺服电机的输出也明显更接近理想情况.图4则说明了约束条件得到了满足,任务集的密度也是非常接近1的. 第4组仿真实验用来评价当控制任务占整个任务集不同比重时FS2MPC的性能.按表1所列的各种情况改变控制任务的个数,重复进行第2组和第3组实验.仿真结果用由调度过程引起的控制性能损失的指标J s进行衡量,该指标定义为J s=∫t sim0|y(t)-y ideal(t)|d t(7)式中:y ideal(t)和y(t)分别为理想情况和受到调度过程影响的伺服电机响应曲线;t sim为仿真时间.在每次仿真实验中,平均每个伺服电机的性能损失都被148　第5期周平方,等:实时控制系统一种基于模型预测控制的反馈调度 记录下来.分别采用基本EDF 算法和FS 2M PC ,J s指标的对照情况如图5所示.实验结果说明FS 2M PC 确实明显地降低了由调度过程引起的控制性能损失.从图5中还观察到,随着控制任务个数的增加,平均每个伺服电机的控制性能改善程度是降低的.这是因为当处理器利用率上升时,FS 2M PC 为了满足资源和可调度性约束,可以被用来减小控制任务截止时限的那部分能力也缩减了.图3　理想情况、基本EDF 算法以及采用FS 2MPC 的伺服电机输出响应对比Fig.3　The response comparison among ideal case ,basic EDF algorithm and FS 2MPC图4　FS 2MPC 中任务集密度、扰动以及控制量输入Fig.4　The density of task set ,disturbance and control in 2put of FS 2MPC图5　不同控制任务个数情况时的性能损失对比Fig.5　Contrast of the performance loss with varyingcontrol tasks number4　结　语本文在EDF 算法的框架下提出了一种基于M PC 的反馈调度方法(FS 2M PC ).分析表明,除了在处理器过负荷的情况外,FS 2M PC 是稳定的.需要采取一些额外的措施来保证反馈调度不出现过负荷的情形,这将是下一步值得研究的内容.通过在资源和可调度性约束的范围内减小控制任务的截止时限,FS 2M PC 使得整个任务集的密度尽可能地接近100%.这样,控制任务获得了更高的优先级,降低了抖动.仿真结果说明在有限计算资源的情况下FS 2M PC 改善了R TCS 的控制性能.参考文献:[1]　Marti P.Analysis and design of real 2time control sys 2tems with varying control timing constraints [D ].Spain :Dept of Automatic Control ,Technical Univ.of Catalonia ,2002.[2]　Cervin A ,Henriksson D ,Lincoln B ,et al .Howdoes control timing affect performance [J ].IEEE Control Systems Magazine ,2003,23(3):16-30.[3]　Baruah S K ,Buttazzo G ,G orinsky S ,et al .Schedu 2ling periodic task systems to minimize output jitter [C]//Proceedings of the R eal 2Time Computing Systems and Applications .Hong K ong :IEEE Computer Soci 2ety ,1999:62-69.[4]　Kao C Y ,Lincoln B.Simple stability criteria for sys 2tems with time 2varying delays [J ].Autom atica ,2004,40(8):1429-1434.[5]　Cervin A ,Lincoln B ,Eker J ,et al .The jitter marginand its application in the design of real 2time control systems [C]//Proceedings of R eal 2Time and Embed 2ded Computing Systems and Applications .G othen 2burg :Springer 2Verlag ,2004. (下转第847页)248上　海　交　通　大　学　学　报第40卷　。