下载掌阅APP，畅读海量书库
立即打开
仿真算法是确定仿真时钟推进策略的控制方法，是仿真控制的核心。目前为止，最常用的仿真算法有事件调度法（Event Scheduling）、活动扫描法（Activity Scanning）和进程交互法（Process Interaction）。
事件调度法由兰德公司在1963年提出，在美国广泛采用，欧洲不很流行。
事件调度法的基本思想是：将事件例程作为仿真模型的基本模型单元，按照事件发生的先后顺序不断执行相应的事件例程。每一个有确定发生时间的事件，都有一个事件例程，用事件例程来处理事件发生后对实体状态所产生的影响，并安排后续事件。
这种方法有一个时间控制程序，从事件表中选择具有最早发生时间的事件，并将仿真时钟修改到该事件发生的时刻，再调用与该事件相应的程序模块，对事件进行处理，该事件处理完毕后，返回时间控制程序。这样，事件的选择与处理不断地交替进行，直到仿真终止的程序事件发生为止。在这种方法中，任何条件的测试，均在相应的事件模块中进行，这显然是一种面向事件的仿真方法。
事件调度法用事件的观点分析真实系统，通过定义事件及每个事件的发生，引起系统状态的变化，按时间顺序，在每个事件发生时，确定并执行有关的逻辑关系。
1.事件调度法的基本步骤
1）初始化：给出当前仿真时钟、系统状态量及统计量的初始值。
2）扫描事件表，将当前仿真时钟增加到下一个最早发生事件的时间上。
3）处理该事件，相应地改变系统状态。
4）收集统计数据。
5）若仿真时间未结束，则返回步骤2）；否则，执行下一步。
6）分析收集的统计数据，产生报告。
2.事件调度法的参数
1）成分集合：定义为 C ={ α 1 .α 2 ， … ， α n }
主动成分： C A ={ α 1 ，α 2 ， … ， α m }
被动成分： C P ={ α m+ 1 ， α m+ 2 ， … ， α n }
2）描述变量：描述每一主动成分 α∈C A 的变量， α 的状态 s α ，值域 S α 。 s α 下一变化时刻的时间变量 t α 。
3）描述每一被动成分 α∈C P 的变量， α 的状态 s α ，值域 S α （被动成分的状态变化只有在主动成分作用下才能发生，其发生时间由主动成分来确定，因而不需要时间变量）。
4）描述所有成分的属性的变量：参数集合P={ p 1 ， p 2 ， …，p r }；成分间的相互关系，每个主动成分 α∈C A 的影响受主动 α 作用下其状态变化的描述，称为事件处理流程；各成分处理的优先级，即同时发生时的处理顺序（解结规则）。注意，在事件调度法中，一般主动成分也同时具有被动成分属性，以便接受其他主动成分的作用。
3.事件调度算法
1）执行初始化操作，包括 置 初始时间 t = t 0 ，结束时间 t∞ = t e ；事件表初始化，置系统初始事件；成分状态初始化：
2）操作事件表，包括：
●取出具有
事件记录，
●修改事件表。
3）推进仿真时钟。
TIME= t (s)
while(TIME<= t ∞ )则执行
case 根据事件类型 i
i =1执行第1类事件处理程序*
（*第 i 类事件处理程序对成分的状态变化进行建模，而且要进行统计计算）
i =2执行第2类事件处理程序
…
i =m执行第m类事件处理程序
endcase
取出具有 t ( s )=min{ t α | α∈C A }事件记录**
（**若具有 t ( s )=min{ t α | α∈C A }事件记录有若干个，则按解结规则处理）
重置仿真时间 TIME= t (s)
endwhile***
（***该算法中未包括仿真结束后对结果的分析等内容）
4.事件表处理
复杂系统运行中的事件表规模巨大，如果采用传统的处理方式，每处理完一个事件要将事件表中的所有项向上平移一行，这样的处理显然需要占用时间，为了提高处理效率，采用链表法是可取的。
活动扫描法的基本思想是：用活动的观点建模。系统由成分组成，而成分包含着活动，这些活动的发生必须满足某些条件，每一个主动成分均有一个相应的活动子例程，仿真过程中，活动的发生时间也作为条件之一，而且是较之其他条件具有更高的优先权。显然，活动扫描法由于包括了对事件发生时间的扫描，因而它也具有事件调度法的功能。
1.活动扫描法的设置
1）设置系统仿真钟TIME（即控制系统仿真时间）与成分仿真钟 t α 。系统仿真钟表示系统的仿真进程的推进时间，而成分仿真钟则记录该成分的活动发生时刻，两者的关系可能有三种情况。
① t α >TIME：表示该活动在将来某一时刻可能发生。
② t α =TIME：表示该活动如果条件满足则应立即发生。
③ t α <TIME：表示该活动按预定时间早应发生，但因条件未满足，到目前为止实际上仍未发生，当前是否发生，则只需判断其发生的条件。
2）设置条件处理模块——成分活动开始与结束其他的条件是否满足。
3）设置成分活动子程序——处理活动开始与结束时系统的状态变化。
2.活动扫描法的步骤
1）扫描所有活动。
2） t α ≤TIME的成分进行条件检验，看其活动开始与结束的条件是否满足，满足则是可激活成分。
3）对所有激活的成分，处理其相应的活动子程序，即修改系统的有关状态，并修改成分仿真时钟。
4）推进系统仿真时钟TIME。
5）继续步骤1）～4），直至仿真结束。
进程交互法采用进程（Process）描述系统，它将模型中的主动成分所发生的事件及活动按时间顺序进行组合，从而形成进程表，一个成分一旦进入进程，只要条件满足，它将完成该进程的全部活动。
系统仿真钟的控制程序采用两张事件表：其一是当前事件表（Current Events List，CEL），它包含了从当前时间点开始有资格执行事件的事件记录，但是该事件是否发生的条件（如果有的话）尚未判断；其二是将来事件表（Future Events List，FEL），它包含在将来某个仿真时刻发生事件的事件记录。每一个事件记录中包括该事件的若干属性，其中必有一个属性，说明该事件在进程中所处位置的指针。
这种方法综合了事件调度法和活动扫描法的特点，采用两张事件表。它首先按一定的分布产生到达实体并置于FEL中，实体进入排队等待；然后对CEL进行活动扫描，判断各种条件是否满足；再将满足条件的活动进行处理，仿真时钟推进到服务结束并将相应的实体从系统中清除；最后将FEL中最早发生的当前事件的实体移到CEL中，继续推进仿真时钟，对CEL进行活动扫描，直到仿真结束。
1.进程交互法的设置
1）设置一张当前事件表CEL，它包含了从当前时间点开始有资格执行事件的事件记录，但是该事件是否发生的条件尚需要判断。
2）设置一张将来事件表FEL，它包含了将来某个仿真时刻发生事件的事件记录。
3）设置系统仿真时钟TIME和成分仿真时钟 t α 。
2.进程交互法的步骤
1）推进系统仿真时钟TIME。
2）把满足 t α ≤TIME的所有事件从FEL表移至CEL表中。
3）取出CEL中的每一个事件，判断其所属的进程及在进程中的位置。
4）判断该事件发生的条件是否满足。
5）如果条件允许该进程尽可能连续推进，直到进程结束，该成分离开系统。
6）该进程推进过程中，遇到条件不满足时，记录下进程的位置，并退出该进程。
7）重复步骤3）～6），CEL中的事件处理完毕。
8）重复步骤1）～7），直到仿真结束。
1.系统描述
所有策略均提供主动成分及被动成分，每种成分均能接受其他成分的作用。在事件调度法中，只有主动成分才能施加作用，而在其他两种策略中，主动成分与被动成分均可施加作用。
在事件调度法中，系统的动态特性表现为主动成分不断产生事件，而在活动扫描法中则表现为主动成分产生活动；在进程交互法中则是通过成分在其进程中一步一步地推进来描述。
2.建模要点
在事件调度法中，用户要对所定义的全部事件进行建模，条件的测试只能在事件处理子例程中进行。
活动扫描法设置了一个条件子例程专用于条件测试，还设置一个活动扫描模块，该模块对所有定义的活动进行建模。
进程交互法则将一个进程分成若干步，每一步包括条件测试及执行活动两部分。
3.仿真时钟的推进
在事件调度法中，主动成分的下一事件发生时间保存在事件表中，定时模块不断地从事件表中取出具有最早发生事件的事件记录，并将仿真时钟推进到该事件发生时间，并转向该事件处理子例程执行。
活动扫描法除了设置了系统仿真时钟之外，每一个主动成分还没有成分仿真时钟。定时模块选择那些大于当前系统仿真时钟的值且是所有成分仿真时钟最小的那个成分仿真时钟，然后将系统仿真时钟推进到该时刻，并开始对活动扫描。
进程交互法采用将来事件表及当前事件表。当前事件表中的进程扫描完后，从将来事件表中取出具有最早发生事件的事件记录置于当前事件表中，将仿真时钟推进到该事件发生时间。一旦某个进程被执行，则要求尽可能多地走下去，但并不改变系统仿真时钟；如果该进程并未完成，则将其断点记录下来，即将中断时间及事件类型放到将来事件表中，如果当前事件表中有一项或几项的发生时间小于当前系统仿真时钟的值，则说明在以前的扫描中，发生该事件的条件未得到满足，本次应再次进行扫描。
4.评述
事件调度法：建模灵活，可应用范围广泛，但一般要求用户用通用的高级语言编写事件处理子例程，建模工作量大。
活动扫描法：对于各成分相关性很强的系统来说模型执行效率高。但是，建模时，除了要对各成分的活动进行建模外，仿真执行程序结构比较复杂，其流程控制要十分小心。
进程交互法：建模最为直观，其模型表示接近实际系统，特别适用于活动可以预测、顺序比较确定的系统，但是其流程控制复杂，建模灵活性不如事件调度法。
时间推进算法是指随着仿真的进程将仿真时间从一个时刻推进到另一个时刻的机制。对某一系统进行仿真时所采用的时间推进算法的种类以及仿真时间单位所代表的实际时间量的长短，不仅直接影响到计算机仿真的效率，甚至影响到仿真结果的有效性。
1.仿真驱动方式
仿真的驱动方式主要分为以下两种。
（1）时间驱动方式
仿真过程是由时间驱动而不是由事件驱动的。当仿真运行时，系统不考虑一个实体的输入信息是否发生变化，而是以仿真时间间隔为基本驱动信息，依次遍历各实体。虽然这种方式非常简单，容易实现，但执行效率比较低。因为不论一个实体是否需要运行，它在每一仿真时刻都要被访问扫描到，这对于存在许多低运行频率实体的仿真系统而言，资源的浪费是极其可观的。
（2）事件驱动方式
该算法首先保证仿真系统不是在每一仿真时刻都将内部的实体扫描一遍，而是由事件作为驱动信息来运行实体。事件驱动算法在仿真系统中定义一个全局时钟变量，每次实体运行后修改全局时钟，同时确定下一事件对实体的触发时刻，很显然这种方式的仿真时间推进效率相对于时间驱动方式要高很多。
2.时间推进算法分类
（1）保守时间推进算法
它最大的特征是严格禁止在仿真过程中发生因果关系错误，保证各类事件是按时间的先后顺序处理执行。保守算法的主要任务是确定何时能安全地执行某一事件，它常常依赖于仿真模型的行为信息，如模型内子模块之间通信的拓扑结构，或模型的超前性等来确定哪个事件是“安全”的，能被安全地处理。
（2）乐观时间推进算法
所谓乐观时间推进算法是指依赖于退回机制来消除由于接收到落后的信息而对事件产生错误处理的一种方法，它更为积极地允许节点更加乐观地处理事件。它的目标是最大程度地发掘仿真系统的并行性，提高系统的运行效率。这种算法具有风险性，如果发生因果关系错误就要求回退到发生错误之前的时刻重新开始执行，因此需要大量的系统资源来保存仿真过程中的状态和数据。
（3）受约束的乐观时间推进算法
乐观方法曾一度广泛地被认为是一种能够始终获得高效率的方法，但是实践证明对乐观性缺乏理智的控制往往会导致极差的性能，所以有必要对乐观的方法进行一定的限制。依据不同的约束控制标准又可以分为基于窗口的策略、基于惩罚的策略、基于知识的策略、基于概率的策略等。
（4）混合时间推进算法
该算法是保守时间推进算法与乐观时间推进算法的混合，将两者结合起来，取长补短，则有可能获得更好的性能，由此人们提出了混合时间推进算法。通过比较研究，保守算法和乐观算法的优缺点恰恰具有一定的互补性：保守算法的仿真并行性利用不高，运行效率较低，但不会发生因果关系错误；相比之下乐观算法则较容易发生因果错误，从而增加仿真运行的复杂性，但能有效地利用仿真系统现有的资源，最大限度地发掘潜在的并行性。
（5）自适应时间推进算法
该算法可以看作是一种动态调整的混合时间推进算法，但它的基本思想是随着仿真状态的变化而动态地选择或修改其执行方式。主要是通过动态地改变一个或多个变量，从而使系统在保守与乐观之间适当调整。自适应时间推进算法在保守与乐观之间架起了一座桥梁，并且可以根据需要使自适应时间推进算法逼近任何一种策略。很显然，这种算法在混合时间推进算法基础上又进了一步。