基于图论的网络控制系统动态调度策略研究

梅志慧，魏利胜，王家才

（安徽工程大学 电气工程学院，安徽 芜湖 241000）

网络控制系统（Networked Control Systems，NCSs）是计算机网络技术、工业控制技术及通信技术等学科理论的交叉、渗透和融合的产物，它可以满足高产量和高生产率的业务需求，给实际工业控制和经营决策提供了一种新的解决途径，在促进国家经济、社会、国防等领域的信息化发展中发挥着特殊的作用[1].但是，由于NCSs的控制器与被控对象之间嵌入了通信网络，导致其性能分析和系统设计变得非常复杂和困难，因此，如何从通信的角度研究NCSs调度策略，通过合理分配和管理网络资源以保证NCSs服务质量和控制质量，已成为一些从事NCSs科研工作者们努力的方向，并取得了初步研究成果.王艳[2]等提出了一种基于通信网络的动态调度器，实时调节控制系统的采样周期；陈文颖[3]等设计了一种适合网络环境的状态观测器，对数据丢包和时延进行了适当补偿；李金娜[4]等基于Lyapunov方法和图论理论，提出了一种新的稳定性判据，给出非线性离散和连续网络控制系统渐近稳定的充分条件，获得保持这两类系统稳定的最大允许时延界；另外，游科友[1]等提出了基于图论的控制系统研究，为网络控制系统调度策略的研究开辟了新的方向.

本文将在以上研究成果的基础上，进一步将图论中的网络流理论与调度策略相结合，引入到NCSs的路径规划中，并采用EDF优化网络带宽的分配，降低网络诱导时延和数据流量，以获取更好的网络服务质量和通信性能.

1 基于图论的NCSs路径优化

网络可以定义为具有两个不同的特定顶点x和y的加权连通图（D，w），记为N＝（Dxy，w），其中x和y分别代表发射点和接收点[5-9]，D代表权值，Dxy为顶点x和顶点y之间连线的权值，w为容量函数，假设w为非负的容量函数c，则网络N＝（Dxy，c）被称为容量网络，其中c在边a上的值c（a）称为边a的容量.如果对任何a∈E（D），c（a）都是非负整数，则成N为整容量网络.为使进、出网络节点的数据所经过的传输距离最短，满足数据对网络“实时性”的需求，同时实现现有网络动态分配的使用效率达到最大化，我们将采用网络流理论优化网络资源的配置[10-11].

某时间段内网络节点的传输数据汇总情况如表1所示.考虑到网络数据传输过程中，节点发送或接收所占比例甚多，则网络中节点发送、接收数据路径最短的实施步骤具体如下：

步骤1：按照节点使用时间的先后顺序，将网络节点之间由左到右进行有向连线，方向为数据传输开水时间从早到晚，从而形成由节点和箭头组成的网络图，从起点到终点的每一条有向路径上的节点都可以作为传输同一数据的节点组合.节点一次编号网络图如图1所示.

表1 假设某一时间段内网络中各节点传输数据汇总

步骤2：在图1基础上，按照各节点的时间顺序进行二次编号N（A，B），N表示编号，A表示N的前一个编号（若为起始点，则其编号为本身），B表示传输速率的累计，即前一个节点A的传输速率与本节点B传输速率之和.需要注意的是，如果A前有两个或多个已编号的节点，则选择B最大的那个节点，作为N的前一个编号.节点二次编号网络图如图2所示.

步骤3：假设图2中每个节点的传输速率代表节点的传输流量，传输速率越快，传输流量越大，从终点开始逆向寻找一个至起点传输速率最快的路径，并把这条路径上的节点安排给优先级最高的数据使用.在图2中，01-04-07即为该网络图中传输流量最大的网络节点组合，可以将这个节点组合按照节点开始时间的先后顺序分配给优先级最高的数据源使用.

步骤4：在网络图上去掉01-04-07的节点及其相关的箭头，再从新的起点开始寻找一条至终点传输速率最快的路径，并把这条路径上的节点安排给次优先级的数据使用.节点三次编号网络图如图3所示.由图3可知，02-06-08即为该网络图中传输流量最大的网络节点组合，可以将这3个节点按照节点数据传输开始时间的先后顺序分配给次优先级最高的数据源使用.

步骤5：重复以上步骤，此时网络图中仅剩下03和05网络节点，可依据传输流量的大小再次进行优先级的分配，直至所有节点分配完成.

图1 节点一次编号网络图

图2 节点二次编号网络图

图3 节点三次编号网络图

2 EDF调度策略

EDF（Earliest Deadline First）调度算法又称为最早时限优先调度算法[12]，该算法根据任务距离时限要求的大小来分配任务的优先级，距离时限越小的任务获得的优先级越高，反之越低.在这种调度算法的调度下，任务的优先级是不断变化的，因此它是一种动态调度算法，能够动态地调节信息的优先级.在信息负载较重的情况下，能够使得有限的资源得到更加合理分配，从而使得某些软实时系统在不可调度情况下，同样能够获得期望的性能.一组n个相互独立实时周期信息，用EDF调度算法的可调度条件：

3 仿真实验

在Matlab／Simulink仿真环境下，构建一个由4个网络控制子系统、1个干扰源和1个有线网络组成的网络控制系统[13-14]，如图4所示.其中子系统的内部结构如图5所示.仿真参数设置如下：

（1）被控对象传递函数.

（2）所有传感器节点均采用时间驱动方式对过程进行周期性采样，采样周期设为h＝0.001 s.

图4 NCSs仿真模型

图5 子系统内部结构图

（3）所有控制器节点采用离散的PⅠD控制算法.

其中，r（k）为读取的输入参考值，通过调用系统函数tt AnalogIn（1）从信号发生器中获取；y（k）为读取的传感器传输的采样值，通过调用系统函数tt Get Msg获取；h＝0.001 s为采样周期；k＝1.5为比例系数；Ti＝0.12为积分系数；Td＝0.035为微分系数；以上参数均在传感器及控制器的初始化程序中完成.

（4）采样值首先通过网络发送到控制器节点，控制器接收到采样值后首先计算控制信号，然后将计算结果发送到执行器节点，执行器节点随后执行该控制信号，工作方式是事件驱动，并将其传送到传感器节点，传感器节点收到执行器节点传送来的信号后做出回应，将信号向相应网络节点发送.

（5）执行器接收并执行控制器传过来的任务信号，因为仿真中采用的是EDF算法，所以对于执行器截止时间并不做严格限制，这里设置默认其一直处于工作状态.

（6）在仿真中引入了一个干扰源，具有高优先级，它发送的信号通过在计算机节点中执行，来模拟网络通信中的干扰，干扰周期设置为0.001 s，干扰数据速率设置为100 bit／s.

（7）网络模型选用CAN总线，其网络数据传输速率为20 Mbit／s，其带宽资源配置方式需进行初始化设置，使其在每次执行传输任务的同时，重新对带宽资源进行计算并重新分配.

4 仿真分析

建模时，每个子系统的时延、任务优先级、任务周期、传输速率、调度策略等参数的设置均不相同，并设置干扰信号占用了网络20%的带宽资源，系统的采样时间取为0.01 s，传感器到控制器的传输时延为0.002～0.005 s不等，控制器本身的计算时延为0.005 s，控制器到执行器的传输时延为0.002～0.005 s不等.通过以上设置，来模拟一个存在网络时延和网络丢包的通信环境[15].

在通信环境中加入干扰信号后，不同对象输出在经过网络传输后，其跟踪参考输入r（k）的变化曲线也不尽相同，信号振荡幅度表明了在网络传输过程中对信号造成的影响（包括时延、丢包、误差等）.当系统存在网络干扰造成延时时，在调度策略的影响下，所有任务均能够在其截至日期之前结束.但是，系统的品质明显变差.如果时延继续增大，系统就有可能不稳定，并且，如果加大干扰所占带宽资源的比例，其对网络传输造成的影响也将是致命的.

为解决这一问题，根据本文给出的方法来解决网络资源的协议问题，对有限的带宽资源进行最大化利用，不仅可以提高传输的效率，且省去了对调度算法的再次复杂编程，从而解决外部干扰对信号传输造成的影响.因此，这里对网络初始化模块中的出、入口函数重新进行定义之后，得到不一样的响应曲线，改进前和改进后两种调度方法得出的响应曲线的比较图如图6所示.其中，实线方波代表参考信号r（k），虚线代表在EDF调度策略的响应曲线，点线代表基于图论的动态调度策略的响应曲线.从图6中可以更为直观地观察两种算法的运行效果.以上仿真结果验证了改进后的调度策略优势所在，采用新的资源分配方式大大提高了信号传输的可靠性，同时也提高了系统的稳定性，因此改进后的调度策略具有很好的可行性.

图6 两种调度策略结果的比较图

5 结论

本文在EDF调度策略研究的基础上引入图论思想，构建了节点的网络分配模型，并利用Matlab仿真环境建立仿真模型，验证了图论思想在网络动态调度中应用的可行性.说明Matlab可以为研究控制与通信网络的复杂系统提供一个良好的实验平台，并具有一定的指导意义.

[1]游科友，谢立华.网络控制系统的最新研究综述[J].自动化学报，2013，39（2）：101-118.

[2]王艳.网络控制系统的控制与调度研究[D].南京：南京理工大学，2006：56-68.

[3]陈文颖.网络控制系统的稳定性研究及调度策略[D].北京：华北电力大学，2010.

[4]李金娜，张庆灵，于海斌.网络控制系统稳定性的图理论[J].控制理论与应用，2009，11：1 309-1 315.

[5]方富贵.图论的算法和应用研究[J].计算机与数字工程，2012，2：115-117，132.

[6]许培，陈其工，葛愿.具有随机丢包的无线网络控制系统仿真研究[J].安徽工程大学学报：自然科学版，2013，28（3）：59-61.

[7]田中大，高宪文，史美华，等.资源受限网络控制系统的模糊反馈调度[J].电机与控制学报，2013，1：94-101.

[8]张水舰，刘学军，杨洋.动态随机最短路径算法研究[J].物理学报，2012，16：1-10.

[9]程远.网络最短路径的一种更新策略[J].计算机应用与软件，2013，1：171-175.

[10]王晶，戴君.不确定交通网络中可靠路径选择模型与算法[J].统计与决策，2014，6：21-24.

[11]黄冠利，吕江毅，廉诗阳.动态路径优化交通流控制及其仿真实现[J].测控技术，2014，1：148-152.

[12]袁暋，檀明.EDF调度算法可调度性分析方法的改进研究[J].计算机应用研究，2013，8：2 429-2 431.

[13]王万良，蒋一波，李祖欣，等.网络控制与调度方法及其应用[M].北京：科学出版社，2009.

[14]刘兴光.网络控制系统中的优化调度方法仿真[J].计算机仿真，2013，12：269-272.

[15]TIPSUWAN Y，KAMONSANTIROJ S，SRISABYE J，etal.An auction-based dynamic bandwidth allocation with sensitivity in a wireless networked control system[J].Computers ＆Industrial Engineering，2009，57：114-124.