基于PSO的控制系统中周期性任务的优化调度

王得利

（唐山市人才交流中心，河北 唐山 063000）

1 引言

实时控制系统是运行于计算机系统上，主要完成数据采集、控制计算、控制输出及报警等功能实时系统。为了充分利用处理器资源，减少系统的软硬件投资，往往在一个处理器上处理多个回路。而系统中的任务必须在一定的时间内完成，否则会出现灾难性后果[1]，这就涉及了实时多任务的调度问题。

针对实时任务的调度算法，Liu和 Layland[2]给出了著名的RMS算法和EDF算法，这两种算法都是针对周期性任务的调度算法。然而控制系统的性能与控制系统的采样周期有关[3－4]，因此出现了结合对系统性能进行优化的调度算法。文献[4]给出了计算优化采样频率的方法；文献[5]给出了使系统性能优化的动态调度算法。但是这些优化调度算法过于复杂。因此本文基于PSO算法设计控制系统的优化调度算法。

2 任务模型

典型的数字控制系统如图1所示。实际上这只是一个控制回路，根据系统的需要它将完成多种功能，各功能之间既相互联系、相互影响又相互独立，因此可以看作一个任务，这是一个周期性任务。另外系统的采样周期并非固定不变的，在保证控制回路稳定的前提下，根据系统的动态、静态性能指标要求以及对象的数学模型可以确定回路的采样周期[6]，这是采样周期最大值，记为，而为了保证系统的正常运行，系统的采样周期存在最小值（如必须大于该控制回路的采样、控制计算和控制输出的执行时间），记为。

在控制系统中，一般来说当控制算法、数据采集和控制输出的方法确定后各任务的执行时间是确定的。

图1 实时控制系统的结构

基于以上分析，我们给出控制系统的周期性任务模型如下：

定义1一个控制系统中的任务集可表示为

其中n≥1，iτ为一个回路任务，可表示为如下的形式

控制系统中除了回路任务外，还存在诸如报警等非周期任务。这类任务只要在一定的时间内调度完成即可，故可通过给非周期任务预留一定的处理器资源来实现对其调度，如采用带非周期服务器的调度算法[1]，因此本文主要研究回路任务的优化调度算法。

定义2若所有回路任务的所有实例都能在其时限之前完成，则称任务集S是可调度的。

为了分析合设计调度算法的方便，本文做如下假设：

（1）回路任务之间相互独立，回路任务时限等于周期；

（2）所有的任务在同一处理器上完成。

3 调度算法及优化

由任务模型可知，控制系统中的任务均为周期性任务，故可采用 Liu和 Layland[2]给出了著名速率单调调度算法（RMS）和最早截止期优先调度算法（EDF），考虑到EDF可以获得更高的处理器利用率，本文采用抢占式 EDF调度算法。由文献[2]可知，EDF调度算法的可调度条件如下：

引理1对于周期性任务集，采用抢占式EDF算法，当且仅当

时，任务集是可调度的。

根据Seto[4]的研究，控制系统的性能与采样周期和控制延迟有关，它们与控制系统的二次性能指标存在如下关系：

式中 ci, ai常数，可通过控制算法曲线获得。由文献[4]可知，Ji越小系统性能越好。由于各控制回路重要性不尽相同，结合前面任务的可调度性和采样周期的取值范围，则优化问题为：

约束条件：

当前的优化调度算法[3-5]过于复杂，本文基于优化搜索算法寻求最佳的采样周期。搜索算法中 PSO是一种源于对鸟群捕食行为的优化迭代算法，该算没有遗传算法中的采用交叉和变异操作，没有许多参数需要调整，因而实现简单。为去掉(5)式中的第一个不等式约束条件，采用惩罚函数法[7]，并通过准精确惩罚函数，使得优化问题变为：

式中M为正常数，用于调整对不合法个体的惩罚程度，则约束条件化为

粒子群算法将每个个体视为在n维搜索空间中，以一定速度飞行的没有质量和体积的粒子。每个粒子的飞行速度据其本身的飞行经验和群体的飞行经验进行调整。假设在n维目标搜索空间中，有m个粒子组成一个群落，其中第i个粒子表示为。在n维搜索空间中的位置为Ti，每个粒子的位置代表一个潜在的解。第i个粒子的飞行速度为n维向量，记为。记第i个粒子迄今为止搜索到的最优位置为，对应的适应值为pBest，整个粒子群迄今为止搜索到的最优位置为，对应的适应值为gBest。每个粒子的速度和位置按方程(8)和(9)进行迭代

式中 j,t均为1,...,n，t为迭代次数；ω为惯性权重，ω≥0；c1,c2为学习因子，也称加速因子。这两个参数对粒子群算法的收敛起的作用不是很大，但如果适当调整这两个参数，可以减少局部最小值的困扰，当然也会使收敛速度变快。为粒子i目前位置到粒子i迄今为止搜索到的最优位置在第j维上的距离；为粒子i目前位置到整个粒子群迄今为止搜索到的最优位置在第j维上的距离。

4 调度算法的仿真

为了验证前述方法的有效性，我们进行如下仿真，来考察对回路任务采样周期的优化情况。每个任务的最大采样周期在800到1000之间随机生成；每个任务的最小采样周期取为该任务最大采样周期的0.6倍；每个任务的权重是在0到1之间归一化生成的随机数；每个任务的执行时间在0到0.1倍的最大采样周期之间随机生成。按照上述任务参数生成方式，随机生成10个回路任务，任务参数如表1所示。

表1 控制系统回路任务参数

利用粒子群优化算法，采用前述算法流程，对上述 10个周期性任务的采样周期进行优化。设该粒子群中有粒子80个，共进行250次迭代。仿真后所得结果如表2和图2所示。利用 PSO算法，优化搜索了各个回路任务的最优采样周期。

表2 单处理器控制系统仿真结果

图2 控制系统平均目标函数和迭代次数之间的关系

利用表2的数据，根据处理器利用率计算公式

对单处理器的利用率进行计算，处理器的利用率为 0.999 991。该处理器的利用率非常接近于 1，表明采用本文所提出的单处理器控制系统的任务调度策略和回路任务采样周期优化方法，在满足所有回路任务均可调度这一前提下，系统计算资源的利用率很高。

同时，由图2可见，尽管最终进行了250次迭代，在第50次迭代时，平均目标函数值就已从约120收敛至约20左右，可见收敛速度快，运算效率之高。采用粒子群优化搜索算法，平均目标函数值从第0次迭代的120.9945被优化至第250次迭代的20.74327，优化幅度约为82.856%，优化效果显著。

5 结论

研究了控制系统中周期性任务，分析任务特性，给出了任务模型。为了提高处理器资源利用率，采用了 EDF调度算法。基于此，采用 PSO算法给出了控制任务采样周期的优化求取算法。仿真实验表明，本文给出的基于PSO的控制任务优化调度算法是有效的。