网络控制系统中信息与任务的混合调度算法的研究

同步网络控制系统网络控制系统NETWORKEDCONTROLSYSTEMS,NCS是一种全分布式、网络化实时反馈控制系统，是通过通信网络实现某个区域现场的传感器、控制器和执行器之间进行数据传输，实现协调操作与控制。由于网络控制系统具有控制灵活、可靠性高、维护和扩展方便、可实现复杂的控制等优点，因此网络控制系统取得了广泛的应用。图31网络控制系统的结构图二任务模型和系统模型一般来说，典型网络控制系统的结构如图31所示。系统中存在众多的控制器，需要实现对大量对象的控制。每一个控制回路都需要实现如下功能传感器采集被控对象参数信息，通过网络将采集的被控对象参数信息传给控制器，控制器根据预定的控制规律进行控制计算得到控制量，通过网络将控制量送给执行器，执行器通过相应的操作从而调节被控对象。这些功能相互影响，紧密联系，因此一个控制回路可看成一个任务，称为回路任务。显然每个回路任务包括5部分，它们在不同的设备上运行，其中传感器采集被控对象的信息由传感器完成，被控制对象的信息由传感器送到控制器及控制量由控制器送给执行器通过网络传送，控制量的计算由控制器完成，根据控制量调节被控制对象由执行机构完成。它们之间存在着严格的执行顺序要求首先控制对象的信息由传感器送到控制器，然后是控制器计算出控制量，最后是控制量由控制器通过网络传送送给执行器，执行机构根据控制量调节被控制对象。由于传感器采集信息和执行机构调节被控对象都是有传感器和执行机构独立完成，它们与控制器和网络无关，而一个控制器往往需要执行多个控制回路的控制计算任务，同1控制器1控制器N执行器1网络执行器N传感器1传感器N对象1对象N时网络需要传送所有回路任务中需要传送的信息，因此我们仅考虑网络上需要传送的信息和控制计算等任务的调度问题。网络控制系统中每个回路以一个固定的频率重复执行，因此我们可以将回路任务看成周期性任务。每个回路任务的子任务之间不仅有严格的执行顺序，而且之间是相互制约的，需要传感器采集控制对象的参数信息，控制器才可以根据约定的控制规律进行控制计算得到控制量；需要控制器根据约定的控制规律进行控制计算得到控制量才能通过网络送给执行器，执行器才能通过相关的操作从而调节被控对象。由于在一个确定的网络控制系统中，每个控制回路中所要采集的信息量、控制任务的计算程序和传送到执行器的控制量是不变的，因此这三个子任务的执行是有严格的时间约束的。在此基础上给出网络控制系统中的回路任务模型。定义1网络控制系统中的回路任务集可以表示为1,1表示第1个回路任务，表示第I个回路任务，表示回路任务的总数）。我1们将定义为五元组，其中表示回路任务采样周期，1,1,2,3表示允许的最大采样周期，表示从传感器到控制器传送的采集信息任务，1表示控制器执行的任务，表示从控制器到执行器传送的控制信息任务。由23于是信息任务，所以和可以定义为一个二元组，其中表示信1,2,313,息任务的传送时间,A表示信息任务的到达时间。则可以定义为一个三元组2，其中为控制任务的执行时间，为控制任务的开始时间，,为控制任务所分配处理器。显然这些子任务的执行顺序为。123定义2由于网络控制系统的复杂性，功能种类的多样性，因此在实际操作中会选择不同的处理器来完成对应的功能，所以网络控制系统是一个有限的多处理器的集合。网络控制系统描述成一个有限个的多处理器组成的集合，R，其中，1,2,2其中表示处理器的总数，表示控制任务所分配处理器，表示第个处理器，表示处理器的性能。定义3在网络控制系统中，需要实现多种功能，需要不同的处理器来进行，而处理器的性能决定了它的执行速度。系统的性能越高，需要的处理器的性能越高，控制系统中的处理器（控制器）的执行速度越快。我们在一个分布式网络控制系统中，选择一个处理器作为标准处理器，将处理器的性能设置为1。其它处理器的性能按下式计算1式中为控制任务所分配处理器，表示处理器的性能，表示的是任务在标准处理器上的执行时间，表示该任务在处理器上的执行时间。为了简化设计和分析调度算法，本文作出以下三点假设（1）回路任务之间相互独立。一个分布式控制系统往往需要控制大量的参数，从而形成了数量众多的控制回路，一个控制回路即一个回路任务，这些控制回路运行在数量众多的处理器上，每个处理器运行一定数目的控制回路，回路任务之间不免有干扰，所以为了简化设计和分析调度算法，我们假设回路任务之间是相互独立的。（2）处理器控制器数目固定，回路任务数目固定。当设计完成一个已经确定的控制系统，它所要控制的参数是确定的，所以我们可以假设回路任务是确定的，即回路任务数目也是固定的；在设计这个控制系统时，它的系统是确定的，所以系统里的处理器（控制器）是确定的，处理器（控制器）数目是固定的。（3）回路任务时限等于周期。在一个已经确定的网络控制系统中，每一个控制回路在一段时间内会循环一次，回路任务具有周期性，以一定的频率运行，因此回路任务每一次循环时间不可以超过周期，所以回路任务时限等于周期。三调度算法的设计显然这两类任务在不同的资源上执行，并且他们之间存在执行顺序和严格时间的约束，所以传统的分布式实时系统的调度算法不适用。由于信息任务和控制任务的实时性，子任务的执行问题，在调度算法中我们在一个采样周期内设计回路任务的调度序列，来确定每个子任务什么时候在处理器或网络上执行并且同时在哪个处理器或者网络上执行，确定每个回路任务中的各子任务的执调度序列32143124任务版本T31T21T11T41T33T13T33T43调度序列1323141321424任务版本T31T21T32T11T41T12T33T22T13T42T33T43行顺序，而调度算法则是最后将每个回路任务的控制任务分配到各个处理器上。调度序列的构成回路任务调度序列是由回路任务构成，每个回路任务在调度序列中出现3次，第一次出现表示该回路任务中的传感器采集被控对象参数信息子任务，第二次出现表示该回路任务中的通过网络将采集的被控对象参数信息传给控制器的控制子任务，第三次出现表示该回路任务中的通过网络将控制量送给执行器的信息子任务。在同一个资源上执行的任务按照它们在调度序列中出现的先后次序来执行，不同资源上的任务可以并行执行；但是同一个回路任务的子任务必须等到其前一个子任务执行完成，才可以执行。从而保证回路任务的各个子任务的优先约束关系。对于，回路任务在每个调度序列中出现3次，按出现的次序分别表示从传感器到控制器传送的信息任务，的控制任务到执行器传送的信1息任务，从控制器到执行器传送的信息任务。23传感器采集被控对象参数信息，通过网络将采集的被控对象参数信息传给控制器，控制器根据预定的控制规律进行控制计算得到控制量，例1，假设有四个回路任务，两个处理器，其中回路任务1,3的控制子任务分配在处理1上，回路任务2,4的控制子任务分配在处理器2上，设构造如图32的调度序列图32构造的调度序列由调度序列可得网络和各处理器上任务执行的先后顺序如图所示图32A调度序列及其对应的任务执行序列调度序列1323141321424图32B网络上信息任务的执行顺序图32C处理器上执行顺序由此可见，通过构造调度序列，可以控制各个任务的执行顺序，并保证每个回路子任务的执行顺序。回路任务的控制任务的分配算法原理是将控制任务分配到完成该任务时间最早的处理器上。由此控制任务的分配算法如下（1）输入处理器数目，回路任务数目，任务的执行时间，各处理器的处理性能。U（2）构造调度序列，如例1（3）读取第一个任务或者第个任务，判断该任务是信息任务还是控制任I务，如果是信息任务，就不予考虑；如果判断为控制任务，则先计算该任务在各个处理器上的完成时间，并将该控制任务分配到完成时间最早的处理器上，因此，需要计算各处理器运行任务的结束时间。2以下为在处理器上完成的时间的算法在某一个处理器上，设为的执行开始时间即也为22的任务到达时间，任务的执行必须要求同一个回路任务中的前一个任务22要完成，并且要求和分配到相同的处理器上的在调度序列里比它前一个12的任务也要完成，则取任务和任务之间完成时间的最大值。J221J2处理器131任务版本T32T12处理器224任务版本T22T42调度序列2231342143124任务版本T21T31T11T32T41T22T12T42T33T13T23T43调度序列1323141321424任务版本T31T21T32T11T41T12T33T22T13T42T33T43则21，2其中为同一个回路任务中的前一个任务要完成的时间，和分1122配到相同的处理器上的在调度序列里比它前一个的任务的完成时间。J2任务在处理器上的执行时间，可以得到22的完成执行时间为，其中必须取整。22222计算某个控制任务在各个处理器上的完成时间，将这个控制任务分配到完成时间最少的处理器上，以上可以看出该算法为静态算法，因为在系统运行前把任务分配到各个处理器上，任务运行时任务所在的处理器是不变的，这样可以减少算法的开销。例2，构造的调度序列中有四个回路任务，两个处理器，任务参数如表33，设计两个不同的调度序列如图34AB，执行时间任务TITI1TI2TI3T110825T28847T310856T35836表33任务参数图34A调度序列1图34B调度序列2调度序列1中要求任务只需要等前一个任务完成就可以继续运行。T32T31需要等同一个回路中的前一个任务完，还需要等和同T12T11T12T12一个处理器的前一个任务完成才可以继续执行，因此的开始执行时间取两T12个任务的执行结束时间的最大值。调度序列2同理。根据调度序列1和调度算法得到的各回路控制任务在各个处理器上的开始时间和结束时间如表34，表35和表36表34调度序列1控制任务处理器分配执行时间108851058268458376调度序列323141321424开始时间010101828289595110110179193结束时间1018952833110101179115193186199表35调度序列1开始时间和结束时间执行时间810108558482836576调度序列231342143124开始时间0818182089210310317492186结束时间81820103259217418610917999192表36调度序列2开始时间和结束时间很显然，根据参考文献可以看出，控制系统中的任务与采样周期和控制回路的端端延迟有关，那么一旦处理器的调度算法和分配算法确定之后，对一个调度处理器1处理器2控制任务开始时间结束时间开始时间结束时间分配处理器T1295177281102T22951791101941T32109510951T421792621101932序列而言，每个任务的开始执行时间和结束执行时间是确定的，因此端端延迟是确定的，所以只与采样周期有关，我们要对采样周期进行优化。四调度算法的优化通过上面的论述，本文要对采样周期进行优化，也就是要获得最佳调度序列从而实现对调度算法的优化，而网络控制系统大多比较复杂，系统中存在众多的控制器，需要实现对大量对象的控制，系统中包含了许多的回路任务，因此存在有数目非常大的合法的调度序列，而且函数关系无法完全描述出调度序列和其中获得的最佳采样周期之间的关系，所以想要获取最佳调度序列并不容易。之前为了解决调度序列和最佳采样周期之间的关系，而出现了例如遗传算法（GA）、粒子群算法（PSO）等这一系列优化算法。粒子群算法（PSO）和遗传算法（GA）进行对比，粒子群算法（PSO）里参数比较少，而且不要交叉和变异操作，所以相对遗传算法（GA）比较简单。本文通过改进粒子群算法，来优化调度序列，从而优化控制系统的采样周期。在粒子群算法PSO中，粒子群有两个参数，一个是位置，一个是速度。系统随机产生个粒子，每个粒子的一个位置表示空间中一个可能解也就是表示一个调度序列，用一个维向量表示第个粒子的第个位置。向量中的每2一个元素都是一个整数，且同一个整数在向量出现3次，每一次表示回路任务的一个子任务。每个粒子在运动过程中在经历的所有位置里会发现自己的最佳位置也就是局部最优，第个粒子的最佳值表示为，表示第个粒子经历的所有位置中的最优位置。而所有粒子在运动过程中经历的局部最优中会发现所有粒子的最佳位置也就是全局最优,所有粒子经历的所有位置中的最优位置表示为全局最佳值，也就是所有形成的调度序列中最优调度序列。在KENNEDY和EBERHART提出的位置更新公式中粒子中的所有位置向量的元素是连续的整数，但是我们粒子群中粒子中的所有位置向量的元素都是非连续的整数，而所以不能采用该位置更新公式。在和基础上粒子群算法的位置更新算法如下。（1）第个粒子的第个位置序列在最优位置序列为基础的更新操作。首先从最优位置序列中随机选择一个片段的元素，并将它们放在更新后的序列的对应位置上。然后将中与所选择片段中的相同的元素1（包括整数值和出现的次数）剔除掉。最后将中剔除后剩余的元素放在中已放置选择片段元素的前面和后面（不改变排列顺序）。例3，假设1系统中有3个回路任务，2个处理器并且，基于的更新操作如图1,3137所示。在最优位置序列中把第4个位置到第6个位置上的元素选择为一个片段（见图第一行）,放到的第4个位置到第6个位置上，同时将1中的刚刚选择的片段中相同的元素剔除掉见图中第二行，将剔除掉相同元素后剩余的元素分别放在前后，由于只有第4个位置到第6个位1置已经放置了片段，因此前后元素分为两部分，也就是前3个元素和后3个元素放到中见图中第三行。1图37在基础上的更新操作（2）更新后得到的局部最优位置序列在全局最佳值的基础上更1新操作。（参照（1）进行操作）首先从全局最佳值序列中随机选择一个片段的元素，并将它们放在的对应位置上。而剔除掉中与随机选择的片段中的相同的元11素。最后将中剔除后剩余的元素放在中选择的片段元素的前11面和后面（不改变排列顺序）。例4，假设系统中有3个回路任务，2个处理器并且，如下图38所示。在全局最佳值中把第5个位置到第7个位置1,31上的元素选择为一个片段（见图第一行）,放到的第5个位置到第6个1231321123213剔除元素123