基于关键复合松弛度的网络控制系统调度算法

陆仲达，蒋红霞，徐凤霞，李诚

(齐齐哈尔大学 计算机与控制工程学院，黑龙江 齐齐哈尔，161006)

摘要：提出基于关键复合松弛度的网络控制系统优先级调度。算法通过关键复合松弛度和关键截止期逐步确定当前时刻的最优调度任务，始终以关键截止期对任务进行优化调度，保证任务按照复合松弛度法则运行。给出确立任务优先级的详细步骤，搭建倒立摆NCS仿真平台验证了算法的有效性。从网络调度的角度，使得控制系统保证和维持在一个较低的延迟范围内的稳定，实现了网络条件下控制系统信息和数据的更稳定传输。

关键词：网络控制系统；调度算法；关键复合松弛度

中图分类号：TP13          文献标志码：A         文章编号：1672-7207(2011)S1-0246-04

Networked-control system scheduling algorithm based on critical compound laxity

LU Zhong-da, JING Hong-xia, XU Feng-xia, LI Cheng

(College of Computer and Control Engineering, Qiqihar University, Qiqihar 161006,China)

Abstract:  The critical compound laxity (CCL) priority scheduling algorithm on networked-control system is proposed. The critical compound laxity and critical deadline is taken into consideration to judge the moment optimal scheduling task progressively with the relative rule, ensures the task running according to the CL rule. The detailed priority judgment steps based on the rule are given, and the designed Inverted Pendulum NCS simulation platform verifies the effectiveness of the algorithm. From the perspective of network scheduling, the stability of control system is ensured and maintained at a lower delay and information and data transmission more steady of control system is realized under the condition of network.

Key words: networked-control system; scheduling algorithm; CCL

伴随计算机、控制和通信技术的交互发展，网络控制系统取代了传统的控制系统组件间的点对点布线连接，实现了传感器，控制器，执行器和其他一些节点间数据和信号的网络传输。这种实现方式具有系统布线简单，系统灵敏性高，故障诊断简单且易于维护许多优点。然而，由于网络所导致的延迟问题却无法避免，如果在设计系统时不加考虑，网络控制系统的性能会极大降低甚至导致控制系统不稳定。可从2个主要的方面解决这个问题：一是从控制的角度，另一方面是通过网络调度策略来解决^[1]。本文作者从网络调度策略的角度研究网络控制系统，介绍了最小松弛度优先级(Least Laxity First，简称LLF)调度算法，最小松弛度优先级调度算法是EDF改进后的一种算法。它采用任务的松弛度确定当前时刻的调度任务，松弛度越小优先级越高^[2]。对于最大可允许延迟的最小优化问题，LLF和EDF算法是优化的调度算法。基于复合松弛度法则的CL调度，从全局域上评估系统的调度性能，依据复合松弛度确定当前时刻最优调度任务，提出基于关键复合松弛度的网络控制系统调度算法，确保系统中所有任务按照关键复合松弛度(Critical Compound Laxity：简称CCL)和关键截止期运行，实现任务的全局优化调度。

1  算法描述

1.1  最小松弛度优先级调度

最小松弛度优先级算法是根据任务紧急程度也即任务的松弛度，来确定任务的优先级。任务的紧急程度越高，该任务所赋予的优先级就越高，应使之优先级执行^[3]。任务松弛度定义为任务必须完成时间减去任务本身运行时间与当前时间之和。在网络控制系统调度中，任务必须完成的时间也即任务截止时间。对于任务i，如果其任务截止期为100 ms，也即任务i必须在100 ms之前调度完成，任务本身的执行时间为30 ms，因此调度必须在70 ms之前进行，该任务的紧急程度也即松弛度为70 ms。任务按照松弛进行调度，松弛度最低的任务具有最高的优先级^[4]。

1.2  调度概念描述

对于当前调度时刻t，调度任务j_i，基本调度概念如下：

定义1  任务松弛度：任务的松弛度是指该任务在完成时间前可以延迟的时间，最小松弛度即任务完成前最大可延迟时间。

LLF算法中通过松弛度定义算法优先级：

             (1)

式中：d_i(t)，p_i(t)分别表示第i个调度任务的绝对截止期和剩余处理时间。

类似于松弛度，定义复合松弛度如下：

定义2 复合松弛度：任务在满足截止期d_i的情况下的最大可延迟时延。在时间域[m, n)上运行的工作j_i， 满足。定义任务集上所有任务的剩余处理时间和当前时刻任务的总剩余处理时间：

                (2)

任务j_i在t时刻的复合松弛度定义为：

      (3)

定义3任务集上任务的最小复合松弛度叫做任务的关键复合松弛度，记。

定义4 任务集上关键复合松弛度为的任务中，截止期最小的任务即关键任务，关键任务的截止期即当前时刻调度的关键截止期，满足

。

定义5 对于在线的动态优先级调度算法，假设所有任务的运行总是满足关键截止期，或者所有任务都在关键截止期时限内运行，就说算法满足复合松弛度法则或者为复合松弛度调度。

2  算法实现

2.1  优先级确立

基于LLF调度提出关键复合松弛度算法。与松弛度调度算法比较，复合松弛度考虑系统中所有任务的调度特性。系统为了保持较小的时延，需要最小复合松弛度尽可能的大，以便满足系统的极大延迟取得最小值^[5]。

随时间到达的任何调度任务，CL调度按如下3个步骤确定任务的调度优先级，确定当前时刻的最优调度任务。

步骤1选定可调度任务并计算对应的剩余处理时间。

步骤2按步骤1条件，确定任务对应的松弛度和关键复合松弛度。

步骤3确定任务关键截止期。

满足上述条件的任务即为当前时刻的最优调度任务。

随时间到达的n个调度任务，当前时刻已经完成的任务数为l，当前时刻未到达的调度任务数为m个，则可以描述任务为：

       (4)

式中：，；

当前时刻已经完成的调度任务和当前时刻未到达的调度任务分别为：

         (5)

      (6)

不考虑当前时刻已经完成的任务和没有到达的任务，则当前时刻可调度任务和任务对应的剩余处理时间为：

    (7)

   (8)

为了确定每个工作的关键复合松弛度，需要计算出中每个工作的复合松弛度。当前时刻调度的复合松弛度用表示，定义为：

    (9)

对于复合松弛度最小的任何工作，其复合松弛度即为期望的关键复合松弛度，该任务也即关键复合松弛度任务。比较任务集 中所有任务的复合松弛度，任务的复合松弛度关键复合松弛度可表示如下：

      (10)

因此，满足最小复合松弛度条件的任务确定。工作的截止期分别为。满足关键复合松弛度的任务，其截止期最小的值即为关键截止期，

     (11)

2.2  调度算例

当前时刻，工作1，2，3，4，5，6的集合。不考虑时已经完成的任务2和4以及没有到达的任务6，时可调度任务集合。调度相关参数如下表1所示。

表1  调度相关参数表

Table 1  Scheduling parameters

任务的相关调度数据计算法步骤如下：

步骤1 时可调度任务，调度任务满足在最大截止期时间限制,运行。工作集对应的剩余处理时间。

步骤2 计算工作复合松弛度。时刻工作1，3，5对应复合松弛度分别为：,

。因此工作1和工作3的复合松弛度最小，即为关键复合松弛度，。工作1和3满足关键复合松弛度，所以当前条件下确定的调度任务集为。

步骤3 计算关键截止期。复合松弛度任务满足，即为关键截止期任务。因为，由此可知，时调度任务关键截止期为。其他时刻的调度以此类推，任务满足CL法则下的调度。

3  仿真分析

为了评估算法调度性能，以倒立摆模型作为仿真对象。倒立摆各项物理参数如下：小车质量m=4 kg，摆杆质量m=0.3 kg，小车摩擦因数为 0.1 N·s/m，重力加速度为9.8 m/s²，摆杆惯量为6 g·m²；摆杆长度l为0.5 m，采样时间T=0.005 s。倒立摆线性系统模型：

        (12)

则系统状态方程为：

      (13)

倒立摆网络控制系统信息调度框图如图1所示。图中s_k表示在第k次采样中通过网络成功传送到执行器的部分控制信号，r_k表示第k次采样中通过网络被控制器成功接收的部分测量信号，其中s_k，r_k，u_k，y_k均为离散时间信号，s_c表示调度算法功能模块。

图1  倒立摆网络控制系统调度框图

Fig.1  Inverted pendulum NCS scheduling

搭建网络控制系统模型，仿真结果如下图2所示。

从图2可知：改进的基于关键复合松弛度的调度算法，在相同的理想实验条件下，对于相同的系统信号，系统具有更加平稳的性能，输出对输入的响应误差更小。从调度的角度来说，算法对网络资源的调度满足更小的系统响应误差和更好的稳定性能。关键复合松弛度调度算法始终以关键截止期进行任务的调度，对于随时间到达的调度任务，总能保证任务按照CL法则运行^[6]。与LLF算法比较，改进的关键复合松弛度算法对系统输入有较小的响应误差，系统输出对系统输入信号有较好的跟踪效果，通过调度改善了网络控制系统性能。关键复合松弛度调度保证了任务以尽可能大的复合松弛度运行而不错过任务截止期时限，调度延迟相对减少。

图2  系统响应误差

Fig.2  NCS response error

4  结论

对基于复合松弛度的网络控制系统调度算法进行了研究，在松弛度最小最优先算法的基础上，给出了关键复合松弛度和关键截止期定义，同时给出了详细的优先级确立步骤。关键复合松弛度调度算法考虑当前时刻所有在线的任务，通过任务复合松弛度、任务关键复合松弛度和任务关键截止期确立当前时刻最优调度任务，算法始终以关键截止期对任务进行优化调度，总能保证任务按照复合松弛度法则运行。关键复合松弛度保证了任务以尽可能大的复合松弛度运行而不错过任务截止期时限，调度延迟相对减少。从网络调度策略的角度，使得闭环控制系统保证在一个较低的延迟范围内的稳定，在某种程度上，网络控制系统较低的延迟时间也就意味着较好的实时响应和较低的传输误差^[7]，NCS性能相对得到提高，实现了网络条件下控制系统信息和数据的更稳定传输。

参考文献：

[1] Velasco M, Fuertes J M. A control approach to bandwidth management innetworked control systems[C]//Proceedings of the 30th IEEE Annual Conference on Industrial Electronics Society. Washington, USA: IEEEE, 2004: 2343-2348.

[2] Velasco M, Marti P, Frigola M. Bandwidth management for distributed control of higyly articulated robots[C]//Proceedings of the International Conference on Robotics and Automation. Barcelona, Spain: IEEEE, 2005: 265-270.

[3] CHEN Zhang, David cordes. Resource access control for dynamic priority distributedreal-time systems[J]. Real-time system, 2006, 34: 101-127.

[4] 蒋红霞, 徐凤霞, 陆仲达. 一种基于优先级表的网络控制系统混合调度算法[C]//中国控制会议29th论文集. 北京, 2010: 4428-4432.
JIANG Hong-xia, XU Feng-xia, LU Zhong-da. A hybrid NCS scheduling algorithm based on priority table[C]//Proceedings of 29thChineseControlConference. Beijing, 2010: 4428-4432.

[5] Lam T W, To K K. Performance guarantee for online deadline scheduling in the presence of overload[C]//Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 2001.

[6] Patchrwat. Generaliazation of EDF and LLF: Identifying all optimal online algorithms for minimizing maximum lateness[J]. Algorithmica, 2008, 50: 312-328.

[7] Park H S, Kim D S, Kwon W H. A scheduling method for network-based control systems[J]. IEEE Transaction on Control Systems Technology, 2002, 10(3): 318-330.

(编辑 陈爱华)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：黑龙江省教育厅面上项目 (11551537)

通信作者：陆仲达(1970-)，男，黑龙江哈尔滨人，教授，主要从事计算机控制和网络控制研究；电话：0452-2738183；E-mail：lu_zhongda@163.com