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

1任务模型，系统模型与容错模型分布式控制系统11系统模型和任务模型一个分布式控制系统往往需要对大量的参数进行控制，因而形成了数量众多的控制回路，这些控制回路运行在以有限带宽互联网络的数量众多的处理器，每个处理器运行一定数目的控制回路。每个回路以一个固定的频率重复执行，需要完成多种功能，如被控量的检测、根据检测的被控量和确定的控制规律确定控制量并通过执行机构来调节被控对象使之按照预定的目标运行，这些是基本的控制功能，同时还有许多辅助功能，如对被控对象进行监视（即显示控制状态）、数据的存储、对运行状态的优化等等。这些功能之间相互联系、相互影响，故可将一个控制回路看成一个任务，称为回路任务，显然它是周期性运行的。同时，为了实现这些不同的功能，分布式控制系统往往采用多种不同类型处理器以适应需要，故分布式控制系统是异构的。基于此，分布式控制系统描述如下。定义1异构分布式控制系统描述为一个处理器集合MERGEFORMAT1112P,2M其中，为处理器集；为第个处理器；为处理器数目。P1IMI处理器定义成一个二元组IMERGEFORMAT12,IPF其中，表示处理器处理能力系数；表示该处理器在每个周期内所分配的所有任务的完成时间。F由于在异构系统中的处理器类型不同，即一个任务在不同的处理器上的执行时间不同，因此根据单个任务在不同处理器上的运行时间引入执行时间向量如下MERGEFORMAT131,2,IIIICCM其中表示控制回路任务在处理器上的执行时间。ICJIPJ为了表示处理器的处理器速度的不同，引入处理能力系数向量。定义2在处理器集合中任意选取一个处理器作为标准处理器，处理器集的处理能力系数向量NOR定义为MERGEFORMAT12,1,INORINORINORINORMJCCJMINPP14其中表示任务在标准处理器上的执行时间，表示任务在处理器上的执行时间，INORCI1I1P表示任务在处理器上的执行时间，表示任务在处理器上的执行时间，表示2IP2PIJCJIMCP任务在处理器上的执行时间。M按照上述定义，将处理器的处理能力系数定义为处理能力系数向量的第个分量1JMJ，标准处理器的处理能力系数。INORJJCP1INORNORC在处理能力系数向量的定义中使用了任务的执行时间进行计算，但是处理器处理能力向量与任I务的选取无关，下面给出。定理1处理器的处理能力系数与任务的选取无关。PJMJI证明分布式系统逐渐向开放式方向发展，系统中的控制回路任务需要能够在异构的处理器上运行，一般不会针对特定的处理器进行优化，因此，同一任务在不同处理器上的运行时间与处理器性能成反比。所以，下面的等式成立MERGEFORMAT11,1PKIJPKIJMPKIMPACPACPACI15其中表示控制回路任务在处理器上的执行时间，表示控制回路任务在处理器上的1ICPI1PIJCPIPJ执行时间，表示控制回路任务在处理器上的执行时间；表示处理器的处理能力，IMIM1PKA1表示处理器的处理能力，表示处理器的处理能力。JPKPAPJMPKPAPMERGEFORMATINORJPKJPKINORJNORNORJJJPKCA16其中表示控制回路任务在处理器上的执行时间，表示控制回路任务在处理器IJCPIPJINORCI上的执行时间，表示处理器的处理能力，表示处理器的处理能力。PNORJPKAJNORPKAPNOR因此，的大小由和的比值决定，是由处理器集合自身的性质确定的，与任务的选取JJPKPNORPK无关。有前述知，控制系统中的回路任务是周期性任务。同时它们是一类强实时任务，因为如果任务不能在其时限前完成，会出现严重后果，如产品质量下降给企业造成经济损失、武器系统不能实现对既定目标的攻击等，因此这类任务在任何情况下都必须在它们的时限完成。然而随着控制系统复杂性的提高，系统出现故障的概率增加，为了使任务在系统出现故障时仍能按时完成，需要提高系统的容错能力。由于版本复制技术是广泛采用的容错方法，本文采用该技术设计容错算法。为此，每个回路任务都有两个版本，称为主版本和副版本，它们分配在不同的处理上，当主版本执行顺利完成时，副版本取消执行，当主版本因系统故障执行失败时，执行分配在其他处理器上该任务对应的副版本，从而实现容错。由于系统出现的概率比较小，因此本文采用IC（非精确计算技术），任务的主版本包括的功能比较多，如被控量的检测、根据检测的被控量和确定的控制规律确定控制量并通过执行机构来调节被控对象使之按照预定的目标运行、对被控对象进行监视（即显示控制状态）、数据的存储、对运行状态的优化等，以保证系统的控制性能。而副版本仅包含必要的功能，如被控量的检测、简单和必要的控制计算确定控制量并通过对被控对象进行调节等，即实现控制的必要功能。由此可见，主版本的执行时间比较长，而副版本的执行时间比较短。基于此，任务模型描述如下定义3分布式控制系统中的任务集为，其中为任务数目，为第个回路任1,N2NI务且表示为一个四元组。MERGEFORMAT17,PBITDT式中为采用周期，为任务时限，为任务主版本，为任务的副版本。和描述为三元组TDPTTPTBMERGEFORMAT18,PBNORTCPAF式中表示对应版本的在标准处理器最大执行时间，表示对应版本所在的处理器，表示对NORCNORA应版本的到达时间，表示对应版本的最大完成时间。F任务的主副版本在处理器的执行时间使用下式计算IJPMERGEFORMAT19,PBPBINORINORIJIJJJTCTCTTP式中为对应任务主版本在标准处理器上的最大执行时间，为对应任务主版PIJTCPPITJPINORT本在标准处理器上的最大执行时间，为对应任务副版本在处理器上的最大执行PITNORPBIJTCPBITJP时间，为对应任务主版本在标准处理器上的最大执行时间，表示处理器的处理能PIJTCPITJJJ力系数。任务的副版本仅实现必要和简化的功能，而任务的主版本需要实现较多的功能，所以，其中为任务的主版本在标准处理器上的执行时间，为任PBINORINORTTPINORTCIPITPNORBINORTC务的副版本在标准处理器上的执行时间，这表示在同一个处理器上的同一个任务主版本的执行IIPR时间比副版本的执行时间长。任务的副版本用于纠错，在任务的主版本失败后执行，本文处理的静态调度问题不能预先检测到主版本是否发生故障，以及发生故障的时刻，但是，其中表示故障时间，表示主版本PFAILITTFFAILTPITF最大完成时间，这说明任务主版本故障的时间在主版本正常完成的时间之前。所以，任务的副版本在主版本的最大完成时间后开始运行，所以，其中表示主版本最大完成时间，表示PBIITFTAPITBITA副版本到达时间。本文针对同步分布式控制系统研究软件故障和硬件故障容错调度算法，即。由12NTT于控制系统采样周期可以在一定范围内取值，将满足系统控制要求的最大采样周期记为。MAX为了评价调度算法，处理器资源利用率定义如下。定义4处理器的平均利用率为回路任务主版本的总时间与处理器运行时间之比的平均值。描述如下MERGEFORMAT110MAX11PNPINORJTCT其中，表示回路任务主版本在标准处理器上的执行时间，表示控制系统的最大采PINORTCIMAXT样周期，表示处理器的处理能力系数。PIPI12容错模型为了简化设计和分析调度算法，对任务和处理器作如下假设1假设任务数目和处理器数目是固定的。因为当分布式控制系统设计完成以后，系统的控制对象是确定的，系统的参数也是确定的，因此系统的控制回路数目是确定的，任务数目是确定的，处理器的数目也是确定的。2假设系统中所有任务的截止时间等于周期，因为控制系统中的周期性任务一般只对一个参数进行控制，只要控制回路能够在采样周期之前送出控制量，就可以进行调节，实现系统的控制功能。3假设每个时刻只有一个处理器出现故障，由于系统出现故障的概率很低，显然两个处理器同时出现的概率远远小于一个故障出现的概率，所以假设合理。4假设每个处理器都是相互独立的，一个任务发生故障以后不会影响到其他任务。因为硬件可以采用故障隔离技术，这样处理器只有两种状态，一种是正常运行状态，一种时故障状态。5假设处理器故障持续时间是有限的。因为采用硬件冗余技术，可以实现对永久硬件故障的容错，系统通过使用冗余处理器恢复任务的运行。2容错调度算法设计本文针对分布式控制系统中的周期性回路任务，采用主副版本技术设计容错调度算法，即每个回路任务都有两个版本主版本和副版本。当主版本由于硬件故障而执行失败时，执行分配到其他处理器上PTBT该任务的副版本，从而实现容错，保证任务的正常完成。考虑到被动副版本技术可以充分利用处理器资源，所以本文采用被动副版本技术。调度序列设计原理1设计一个调度序列，包含所有任务的主版本和副版本，以实现容错；2分配到同一个处理器上的任务根据它们在调度序列中的排列顺序执行，在调度序列中先出现的先执行，在调度序列中后出现的后执行；3分配到不同处理器上的任务可并行执行，以提高资源利用率，但同一个任务的主版本和副版本必须串行执行。因而，本算法设计分为两个步骤（1）构造符合要求的调度序列；（2）将任务（包括主版本和副版本）分配到各个处理器上。21调度序列的构建调度序列表示所有任务主版本和副版本的分配顺序，下面给出调度序列的定义。定义5任务集合的一个调度序列定义为个任务组成的序列，其中表2N12IANSIN示任务集合中任务的总数，表示调度序列中的第个任务，同一个任务第一次出现表示任务IASII的主版本，第二次出现表示任务的副版本。IPITIIBIT例1假设系统共有6个回路任务，有3个处理器。调度序列及其表示的任务版本序列如图1所示。假设任务，分配在处理器上，任务，分配在处理器上，其余4PT23PTB1P1PT4B1T5B2P的任务分配在处理器上。则这两个处理器上任务执行顺序如图2所示。P416242315356调度序列4PT16PT24BT23PT1B5PT3B5T6B任务版本图1调度序列及对应的任务版本4PT2PT3PT3BT1P1PT4BT1BT5BT26PT2BT5PT6BT3P图2各处理器上任务的执行顺序并不是所有的由回路任务构成的调度序列都满足要求，调度序列中必须包含每个任务的主版本和副版本才是有效的。同时，调度序列还要保证每个各个任务出现的顺序符合优先级的要求。只有满足要求的调度序列才可用于调度的，基于此给出合法调度序列的定义。定义6对于第一节给出的任务模型和系统模型，当一个调度序列满足下面的两个条件，调度序列才称为合法的调度序列1调度序列包含每个回路任务，使得每个回路任务都会被分配到处理器上执行并完成控制功能；2每个回路任务在调度序列中出现的次数必须是两次，分别代表该任务的两个独立版本（主版本和副版本），使得每个回路任务能够在发生故障后得到纠正。根据合法调度序列的定义，可以计算出给定的任务集合的所有合法调度序列的数目。定理2任务集合中包含个任务，那么上所有合法的调度序列总数为。N2N证明因为任务集合中包含个任务，所以调度序列的长度为，个整数的全排列数为。2N而不同的整数在序列中出现的次数为2，这样中排列是相同的，所以调度序列的总数为。N2N22任务分配算法由于回路任务的主版本和副版本必须在处理器上运行，因此必须将任务的主版本和副版本分配到各个处理器上。而任务的分配问题为NP难题，故一般采用启发式任务分配算法求取次优解。本文基于首次适应策略给出启发式任务分配策略，分配的原则是将任务分配到该任务完成最早的处理器上，且同一个回路任务的主版本和副版本分配在不同的处理器上。因此需要计算任务在各处理器上完成时间。221计算任务在各处理器上的完成时间的计算假设给定的调度序列上的第个任务为，用下面的方法计算任务的完成时间SKII1如果任务是主版本，将任务分配到处理器上时，必须等待处理器上的前一个执行的任务执IIJPL行完成（本文采用静态分配策略，任务发生故障的时间无法在分配阶段得到，所以必须等待到任务执行完成所需要的时间），任务的完成时间为，因此，任务的到达时间。LLJFIPILJAF2如果任务是副版本，因为副版本用于容错，它必须等待到任务的主版本完成后再开始执行，那么I，其中表示主版本最大完成时间，表示副版本到达时间，该任务的到达PBIITFTAPITFBITA时间。如果任务是主版本，只要等待到执行完成即可，该任务的到达MAX,PPIILJTIL时间。ILJAF3任务的完成时间即为到达时间经过任执行完成后的时刻，为。PPIJIIJFAC按照上述方法，我们给出算法1。算法1任务在处理器上最小完成时间的计算。1输入选择的处理器，当前要分配的任务，该处理器上前一个执行的任务，及任务的完成JPILL时间。LJF2如果是任务主版本执行ERRORREFERENCESOURCENOTFOUND，否则执行4。I3对于主版本任务，该任务的到达时间，其中表示前一个执行的任务的完PITPILJAFPLJFL成时间。下一步执行5。4对于副版本任务，该任务的到达时间，其中表示前一个执行BITMAX,PIILJTLJ的任务的完成时间，表示任务的主版本的完成时间。下一步执行5。LPITFBITI5任务的完成时间，其中表示任务的到达时间，表示任务在处PPIJIIJACIAIPIJCI理器上的最大执行时间。JP222任务的分配算法容错调度要求分配算法具有下面的特性1分配处理器时需要保证同一个任务的主版本和副版本不会被分配到同一个处理器上，算法只要在分配任务的副版本时，不把该版本分配到主版本使用的处理器即可。2任务的副版本必须在主版本执行完成后开始执行，所以算法必须判断当前任务是否为主版本。算法2任务的分配算法。1输入回路任务数目，每个回路任务主版本和副版本在标准处理器上的执行时间和NPINORTC（其中），处理器数目，每个处理器处理能力系数（其中）,所设计BINORTC1IMJP1JM的调度序列。S2令。开始分配第一个任务。K3判断序列中第个位置上的任务是主版本还是副版本，如果是主版本，执行3A，否则执行3B。K3A该位置上的任务为，根据算法1计算任务在各处理器上的完成时间，（其中PITPITPIJTFP），如果处理器满足，则任务分配到处理器；下一1JMPM1PMINPPPIMLLTFTFPITM步执行4。3B该位置上的任务为，根据算法1计算任务在除去（任务对应的主版本任务所在的BITBITPITBIT处理器）外各处理器上的完成时间，如果处理器满足，BIJTFPPM1PMINPLIBIMILTFF则任务分配在处理器。下一步执行4。BITPM4如果，令并重复（3）步；否则任务分配结束。2KN1K注1任务分配算法是静态分配算法，在系统运行前进行，在系统开始运行后，各任务所在的处理器不发生变化，从而减少算法的开销。注2当分配第个任务时，若果通过调度序列判断当前任务是主版本还是副版本，需要扫描前面KS已经分配的任务，时间复杂性为，开销较大。可以使用一个向量保存已经分配好的主版本任OKPTF务完成时间，在任务主版本尚未分配时，向量中的完成时间记为，可以通过检测该任务的完成时间在向0量中是否为，判断当前任务是否为副版本，时间复杂性为，同时，也可以简化算法1中副版本到01O达时间的计算。BITA对于一个容错调度算法生成的调度方案，必须能够使得系统中的任务能够在截止时间前完成，这样的调度方案才是有效的，为了简化可调度性的判断，下面给出系统响应时间的定义。定义7将调度序列中在一个周期内所有处理器完成全部任务的时间称为系统的响应时间，记为S，如果无需区分调度序列，可以简记为。RSR定理3如果一个调度序列对应的系统响应时间满足，那么这个调度序列是容错可调度的。MAXT证明周期性任务的截止时间等于其周期，而所有回路任务的周期相等，周期为，因为每个DMAXT任务的完成时间均满足，所以所有任务都能在前完成，所以调度序列是可调度的。MAXIFRTAX另外，调度序列中包含每个任务的主副版本，提供了容错机制，所以调度序列是容错可调度的。注3定理3给出了判断分布式控制系统中回路任务容错可调度的充分条件。如果对于分布式控制系统能够找到一个满足定理3的调度序列，则系统是容错可调度的。但如果对于一个分布式控制系统找不到满足定理3的调度序列，不能判断系统中的任务是否容错可调度的。控制回路的采样周期越小，系统的控制性能越高，因此可选择使系统中的回路任务容错可调度的条件下选择最小的采样周期，故对于一个调度序列可选择系统响应时间作为回路任务的采样周期，称为最佳采样周期。如果存在一个合法调度序列，其系统的响应时间在所有的调度序列中最小，则该调度序列称为最佳调度序列，此时对应的最佳采样周期称为优化采样周期，记作。OPTT23调度序列的优化231调度序列对采样周期的影响对于一个分布式控制系统，采样不同的调度序列，可获得的系统最佳采样周期可能不同。例2处理器处理能力系数向量,回路任务共有6个，任务主版本的执行时间分别为1268,76,87,94,84,71,对应的副版本的执行时间分别为14，18，20，22，24，14。下表为不同调度序列的响应时间。调度序列响应时间1S164245332516300221134656453229831244366531523344S425351614236294表格1调度序列的响应时间由此可见采用不同的调度序列，可获得的最佳采样周期也可能不同。对于不同的调度序列，各自的响应时间相差较大，特别是在分布式控制系统中回路任务数目众多（可能多达数百个），不同调度序列的系统响应时间差别很大，因此需要构造最佳的调度序列，减少采样周期，以提高系统的控制性能。232优化算法设计考虑到系统中所有回路任务的采样周期相同，减少采样周期可提高回路任务的控制性能，因此要对调度序列进行调优得到更短的采样周期。然而，在分布式系统中，周期性任务数目众多，合法调度序列的数目很大，同时，调度序列的最佳采样周期不能通过显示函数关系描述，故很难获取最佳调度序列，因此本文使用离散粒子群算法（DPSO）获得最优调度序列。粒子群（PSO）算法是一种基于种群的优化算法，与遗传（GA）算法相比，粒子群算法没有交叉与变异这些演化操作，而且参数较少，因而比较简单。粒子群算法在先随机生成一组可能解作为种群，随后通过更新可能解寻找最优解。种群中的每一个可能解称为粒子，每个粒子根据局部最优解和全局最优解更新其速度，从而得到新的可能解，即下一代的粒子。然而，EBERHART和KENNEDY提出的PSO中粒子的解空间是连续的，只能解决连续优化问题。然而许多工程问题中，问题的解是离散的整数，为了解决这些问题，出现了离散粒子群（DPSO）算法。使用DPSO算法优化处理器调度问题中的合法调度序列，可以先生成个粒子，每个粒子的一个位置L表示解空间的一个可能解，即一个合法的调度序列。第个粒子的第个位置用一个维向量表示。IK2NISK向量中的每一个元素都为一个整数，且同一个整数在向量出现两次，第一次出现表示回路任务的主版本，第二次出现表示回路任务的副版本。每个粒子对应一个可能解，需要定义一个函数计算出适应值，评价这个可能解的质量，对于调度序列，我们使用算法2计算出调度序列的系统响应时间，作为该粒子的适应值。第个粒子经历了代演化后的最佳值记为，表示第个粒子经历的全部个位置中的最佳位置。全IKIBESTSKIK局最佳值记作，表示所有粒子经历了代演化后的所有位置中的最佳位置，即所有生成的调度序GBESTS列中最佳的调度序列。第个粒子经历了代演化后的速度用一个维向量表示，我们根据第个粒IK2NIVKI子的速度更新第个粒子的位置。下面考虑位置更新操作问题。IVK为了实现DPSO算法中粒子位置的更新操作，现有的文献中，主要下面的2种策略1将速度作为位置变化的概率。KENNEDY博士和EBERHART博士于1997年率先提出了一种针对01规划问题的二进制PSO（BPSO）算法，在BPSO中，通过将每个粒子某些位上0，1之间的翻转实现位置更新操作；2直接将连续PSO用于离散问题的求解。PARSOPOULOS等人设计DPSO算法解决整数规划问题时，直接采用连续PSO算法中的位置和速度更新操作寻找最优解，只是在计算每个粒子的适应值时进行取整操作，评价当前解的质量。任务调度问题中的每个可能解是一个维向量。如果采用上面提到的策略2，将维实向量空间中2NN的解进行取整操作，得到的整数解往往是不能满足该优化问题的约束条件的。事实上，随机产生一个维并且每个分量为在中之间的向量，这个向量满足约束条件的概率为。当时，2N1N2NSTP1，位置更新操作会产生大量不满足约束条件的解，使算法长期处在计算不合法的解得状态，浪08STP费大量的计算时间。因此，本文使用类似于BPSO算法的方法，将粒子的速度作为位置变化的概率。与BPSO算法不同的是，对某个位置上每个分量的更新是交换操作，这样可以保证新的位置仍然满足约束条件。233位置更新算法设计根据策略1，将速度作为位置变化的概率，给出下面的位置更新算法算法3位置更新算法。1输入第个粒子的第个位置，第个粒子的新速度，第个粒子的最佳值，IKISI1IVKIIBESTSK全局最佳值。GBESTS2基于局部最佳值的更新操作包括步骤2A2B2C2D2EIKIBESTK2A首先将速度向量规范化，即先将向量的每个分量取绝对值后，再将向量的1IV1IVK1IVK每个分量除以所有分量的最大值，得到规范后的速度。的每个分量是范INORM1INORMVK0,围内的一个实数，这个实数表示位置对应的分量更新的概率。IS2B令。1L2C的第个分量为，随机产生和之间的一个实数，如果，对的第个INORMVKLLP01LQLLPISKL分量进行更新操作，执行步骤2D；如果，表示不需要，对的第个分量进行更新操作，LLQPISK执行步骤2E。2D的第个元素为，局部最佳值的第个分量为，如果表示的是ISKL,ILXKIBESTSKL,IBESTLX,IBESTLXK任务主版本，那么在中寻找该任务第一次出现的分量，交换它和，如果表示的IS,ILK,ISTL是任务副版本，那么在中寻找该任务第二次出现的分量，交换它和。下一步执行步骤2E。IK,ILX2E如果，执行步骤2C；如果，位置更新完毕，更新的结果为，2LN1L2LNISK1ISK执行步骤3。例3更新操作假设系统中有6个回路任务，2个处理器，第个粒子的第个位置为基于局部最佳值IKIK的更新操作如下。第个粒子的速度为，将的每个分量取绝对值后，除以最大值IBESTSKI1IVK1I5，得到规范化的向量。当时时，随机产生的实数，满足，进行1INORMVK0L0IP03PIP了更新操作。对应的分量为6，表示任务的副版本，在中找到该版本的分量6，将它IBESTS66BTISK与的分量2交换，得到了。IKIS1033240045021IVK020006060408000008100004INORMK351442612635IBESTS354266141235IK3542621416351IS图3位置更新操作3基于全局最佳值的更新操作包括步骤3A3B3C3D3E1ISKGBESTSK3A首先将速度向量规范化，即先将向量的每个分量取绝对值后，再将向量的1IVK1IVK1IVK每个分量除以所有分量的最大值，得到规范后的速度。的每个分量是范INORM1INORMVK0,围内的一个实数，这个实数表示位置对应的分量更新的概率。IS3B令。1L3C的第个分量为，随机产生和之间的一个实数，如果，对的第个分量INORMVKLLP01LQLLPISKL进行更新操作，执行步骤3D；如果，对不进行更新操作，执行步骤3E。3D的第个分量为，全局最佳值的第个分量为，如果表示的是ISL,ILXKGBESTSKL,GBESTLXK,GBESTLX任务主版本，那么在中寻找该任务第一次出现的分量，交换它和，如果表示的IS,IL,STLK是任务副版本，那么在中寻找该任务第二次出现的分量，交换它和。IK,ILXK3E如果，执行步骤3C；如果，执行步骤4。2LN1L2LN4如果，和全局最佳值完全相同，位置更新操作中，不会改变任何一个位置，因此引入ISKIBESTS一种新的位置交换方法，即随机选取两个不同的分量进行交换。每次位置更新操作都得到了一个新的调度序列，我们必须保证新的序列仍然是可调度的序列，否则优化操作得到的新序列不合法，那么将无法满足优化的条件，得到的优化值将不是容错可调度的。因此，我们必须证明通过位置更新操作得到的新序列也是可调度的序列。先证明每一步更新操作都是合法的。定理4如果是合法的调度序列，那么仍然是合法的调度序列。ISK1ISK证明在每一次操作只进行了元素位置的改变，因此每个整数出现的次数不会发生改变。这样每个都在中出现了，并且出现次数为2，所以仍然是合法的调度序列。,1IN1II下面证明粒子经过任意次操作后都是合法的。定理5如果粒子初始位置是合法的，那么经过任意次更新后的位置也是合法的。证明使用数学归纳法。1初始位置依据生成的条件，必须是合法的调度序列。0IS2如果位置是合法的调度序列，根据可以定理4得到仍然是合法的调度序列。IK1ISK3由数学归纳法可知，对于任意的，位置都是合法的调度序列。NNIN根据上面的位置更新算法，给出相应的粒子群算法。算法4序列优化算法1输入回路任务数目，每个回路任务主版本和副版本在标准处理器上的执行时间和PINORTC（其中），处理器数目，每个处理器处理能力系数（其中）。BINORTC1INMJP1JM2，初始化个粒子，即随机产生个调度序列作为粒子，局部最佳值0KLL,1ISKIL，随机生成个向量作为初始速度。,IBESTISKI2N,IVI3在局部最佳值中寻找全局最佳值，响应时间满足,1IBESTSGBESTGBEST。1MINGBESTIBESTLRKRK4对每个粒子的位置进行位置更新操作。,ISL4A计算新的速度121IIGBESTIIBESTIVKWKCRANDSKCRANDSKMERGEFORMAT111其中表示第个粒子的第个速度，是惯性权值，表示第个粒子的第个速度，1IVKI1KWIVKIK是全局加速因子，表示在范围内产生的一个随机数，表示全局最佳值，1C1RAND0,GBESTS表示第个粒子的第个位置，是局部加速因子，表示在范围内产生的一个随ISI2C2RAND0,1机数，表示局部最佳值。IBESTK4B使用算法3计算出新的位置。,ISIL1,ISKIL4C如果新位置的响应时间满足，新的局部最佳值1IIRIIBESTRSK，否则。IBESTSKIBESTIBESTK5，重复34直到达到终止条件。3算法仿真基于第一节给出的任务模型和处理器模型，对上面的优化算法进行模拟，验证算法的执行效果。处理器的处理能力系数为区间上均匀分布的随机数，任务主版本的执行时间为区间上均匀分布1,580,1的随机数，任务副版本和主板本执行时间的比值为区间上均匀分布的随机数。任务个数为100个，03,4处理器个数为10个。离散粒子群算法的惯性权值，全局加速因子，局部加速因子，1W1C2C10粒子个数为80个，演化代数为250代。产生的任务主副版本在标准处理器上的执行时间见表2，处理器的处理能力系数见表3。表格2各处理器处理能力系数处理器编号J12345678910处理能力系数JP100133109135102114102105141135表3主副版本任务的执行时间任务编号I123456789101112131415主版本执行时间PINORTC869980898896968390899394958594副版本执行时间I313525343232342828292930312929任务编号I161718192021222324252627282930主版本执行时间PINORT93838290100879284958590949810091副版本执行时间IC363329313334312636292932303136任务编号I313233343536373839404142434445主版本执行时间PINORT828385978597859987848592898797副版本执行时间I323026312937263028313234313132任务编号I464748495051525354555657585960主版本执行时间PINORTC929199869595879181819196998291副版本执行时间I342936273229323031363230263129任务编号I616263646566676869707172737475主版本执行时间PINORT898087839686918392859394958981副版本执行时间IC372630283132343131323429362732任务编号I767778798081828384858687888990主版本执行时间PINORT84998397911008189821008096979881副版本执行时间I293232312932263127392731383928任务编号I919293949596979899100主版本执行时间PINORTC88859689998385838298副版本执行时间I27283332323032272632仿真程序使用MATLAB语言进行编写，算法2的流程图为流程图1任务分配算法，算法4的流程图为流程图2粒子群优化算法。开始输入数据K1判断任务是否为主版本计算任务在各处理器上的完成时间是找出对应的主版本所在处理器否计算任务在除主版本所在处理器外的各处理器上的完成时间将任务分配在完成时间最短的处理器上将任务分配在完成时间最短的处理器上输出该任务分配的处理器输出该任务分配的处理器KK1判断K2N是分配结束否流程图1任务分配算法开始输入处理能力系数，任务主副版本的执行时间初始化局部最优值和全局最优值初始化L个粒子计算局部最优值I1IGG为代数计算全局最优值是J1JL计算第J个粒子的速度是更新第J个粒子的位置计算新的响应时间判断响应时间是否比局部最优值小更新局部最优值YJJ1II1否计算全局最优值输出最优调度序列结束否流程图2粒子群优化算法为了消除初始粒子随机选取的影响，在相同的参数下重复进行仿真，得到每一代的响应周期取平均值，得到的目标函数和代数之间的关系如图4所示。图4每代粒子的平均最优值图5每代的全局最优值通过优化得到的最佳周期为1031，得到的每个任务主副版本的处理器，到达时间及完成时间见表4，与最大采样周期相比有所降低，提高了采样频率，改善了系统性能。从图4中可以看出，随着进化代数的变化，目标函数逐渐降低，并最后收敛于一个最小值，说明算法可以得到优化的调度序列，使系统的性能得到优化。任务编号12345678910主版本所在处理器310591029295主版本到达时间846721700399400131338634588主版本完成时间16374524863464472199400698675副版本所在处理版本到达时间7898986579737957686038631010878副版本完成时间82093268110038247916378901031899任务编号11121314151617181920主版本所在处理器7103102110764主版本到达时间5555308243360003600470主版本完成时间64660091139971936144079544副版本所在处理器8823587871副版本到达时间8587991007939809529440711330881副版本完成时间8868281030966837563472739360914任务编号21222324252627282930主版本所在处理器1222476445主版本到达时间51614321266254416279397193499主版本完成时间603212275733607250161470267588副版本所在处理器211091017694副版本到达时间878726969908921448867580984964副版本完成时间9047579889349424778986061006991任务编号313233