1、离散事件系统建模与仿真学习报告 离散事件系统建模与仿真课程学习报告 课程名称 离散事件系统建模与仿真 学生姓名 学生班级 测控 学生学号 2012 指导老师 时 间 离散事件系统建模与仿真摘 要离散事件系统仿真是现代仿真技术的主要研究热点之一。离散事件系统是一类在工程技术、经济、军事等领域常见的系统，它们的状态在一些不均匀的离散时刻发生变换且状态变换的内部机制比较复杂，往往无法用常规的数学方法来描述。离散事件系统仿真是当前研究这一类系统的最有用处的方法之一。要对系统进行仿真研究，首先需要建立系统的仿真模型。笔者比较详细地探讨了离散事件系统仿真建模的核心仿真流程管理、离散事件系统的三种仿真建模策
2、略，即：事件调度法、活动扫描法、进程交互法。关键词：离散事件系统，仿真建模，仿真策略，系统仿真，事件调度法1 基本概念1.1 系统仿真与系统系统仿真是以相似原理、系统技术、信息技术及其应用领域有关专业技术为基础，以计算机和各种专用物理效应设备为工具，利用系统模型对真实的或假想的系统进行动态研究的一门多学科的综合性技术口。相似论是系统仿真的主要理论依据。系统仿真研究的对象是系统。系统是指具有某些特定功能、按照某些规律结合起来、互相作用、互相依存的所有事物的集合或总和。任何系统都存在三方面需要研究的内容，即实体、属性和活动。实体是存在于系统中的每一项确定的物体。属性是实体所具有的每一项有效的特性。
3、活动是导致系统状态发生变化的一个过程。活动是在一段时间内发生的情况，活动反映了系统的变化规律。存在系统内部的实体、属性和活动组成的整体称为系统的状态。处于平衡状态的系统统称为静态系统，状态随时间不断变化着的系统为动态系统。根据系统状态的变化是否连续可将系统分为连续系统和离散系统及连续离散混合系统。连续系统的状态变量是连续变化的。离散系统包括离散时间系统和离散事件系统，离散时间系统的状态变量是间断的，但是它和连续系统具有相似的性能，它们的系统模型都能用方程的形式加以描述。1.2 离散事件系统离散事件系统是指受事件驱动、系统状态跳跃式变化的动态系统。离散事件系统的系统状态仅在离散的时间点上发生变化
4、，而且这些离散时间点一般是不确定的。这类系统中引起状态变化的原因是事件，通常状态变化与事件的发生是一一对应的。事件的发生一般带有随机性，即事件的发生不是确定性的，而是遵循某种概率分布。而且事件的发生没有持续性，在一个时间点瞬间完成。离散事件系统的系统模型不能用方程的形式描述。离散事件系统的研究方法是排队论和运筹论。针对离散事件系统的仿真就称为离散事件系统仿真。1.3 系统模型系统模型是对实际系统的一种抽象，是系统本质的表述，是人们对客观世界反复认识、分析，经过多级转换、整合等相似过程而形成的最终结果，它具有与系统相似的数学描述形式或物理属性，以各种可用的形式，给出研究系统的信息。系统仿真中所用
5、的模型分为实体模型和数学模型。在离散事件系统仿真中使用的是数学模型。数学模型包括原始系统数学模型和仿真系统数学模型，原始系统数学建模过程被称为一次建模，是使用数学或其他类似的方法建立相应的模型。仿真系统数学模型是一种适合在计算机上进行运算和试验的模型。仿真系统数学建模过程被称为二次建模，在本文中将其称为仿真建模。在下文中为叙述方便，将原始系统数学模型和仿真系统数学模型分别简称为数学模型和仿真模型。1.4 描述离散事件系统的基本概念（1）实体（Entity）。构成系统的各种成分称为实体，用系统论的术语，它是系统边界内的对象。实体可分为f艋时实体与永久实体两大类。在系统中只存在一段时间的实体叫临时
6、实体，这类实体由系统外部到达系统，通过系统，最后离开系统。永久驻留在系统中的实体则叫永久实体，只要系统处于活动状态，这些实体就存在。（2）属性（Attribute）。实体由它的属性来描述，属性反映实体的某些性质。对于一个客观实体，其属性很多，在仿真建模中，只需使用与研究目的有关的那部分属性，从而也只需要对这一部分属性进行描述。（3）状态（State）。在某一确定时间，系统的状态是系统中所有实体的属性的集合。（4）事件（Event）。事件是引起系统状态发生变化的行为，它是在某一时间点上的瞬间行为。离散事件系统可以看作是由事件驱动的。（5）活动（Activity）。实体在两个事件之间保持某一状态的
7、持续过程称为活动。活动的开始与结束都是由事件引起的。（6）进程（Process）。进程由和某类实体相关的事件及若干活动组成。一个进程描述了它所包括的事件及活动间的相互逻辑关系和时序关系。2 离散事件系统仿真建模在建立了系统的数学模型后，需要根据计算机运算特点、仿真方式、计算方法、精度要求等，将其转换为能够在计算机上运行（或试验）的仿真模型，即进行仿真建模。在离散事件系统的仿真建模中，主要应根据随机发生的离散事件、代表系统中所描述主要对象的实体流以及仿真时间的推进机制，按照系统的运行进程来建立仿真模型。顾客到达事件服务开始事件服务结束事件离散事件系统仿真建模的目标是要建立与系统数学模型有同构或同
8、态关系的、能在计算机上试验的模型。为了正确地进行离散事件系统仿真建模，除了上面介绍的相关概念外，还须弄清离散事件系统仿真程序的主要组成成分、流程管理。2.1 离散事件系统仿真程序的主要成分离散事件系统的仿真程序，从其功能结构的角度来看，通常包含以下几个部分：（1）系统状态变量 用于记录系统在不同时刻的状态；（2）时钟变量 用于记录当前时刻的仿真时钟值；（3）事件表 按时间顺序记录仿真过程中将要发生的事件，即当前时刻以后的事件；（4）统计计数器 用于记录有关仿真过程中系统性能的统计信息；（5）初始化子程序 仿真运行开始前进行初始化的子程序；（6）时钟推进子程序 由事件表确定下一事件，然后将仿真时
9、钟推进到该事件发生时间的子程序；（7）调度子程序 将仿真过程中产生的未来事件插入事件表中的子程序；（8）事件子程序 每一类事件对应有一个事件子程序，相应的事件发生时，。就转入该事件的子程序进行处理，更新系统的状态，产生新的事件；（9）统计报告子程序 根据统计计数器的值计算并输出系统性能的估计值；（10）随机数产生子程序 产生给定分布随机数的一组子程序；（11）主程序 调用时钟推进子程序，然后将控制转移到相应的事件子程序，完成仿真程序的总体控制。使用通用高级语言（如C，C+，FORTRAIN，PASCAL，BASIC等）进行离散事件系统仿真程序设计时，以上各部分需要用户自行编程，工作量大。而仿真
10、语言或仿真软件包中提供了上述大部分功能，通过组合可以迅速开发出所需的仿真程序。2.2 仿真程序的流程管理仿真流程管理（即仿真调度）是仿真建模的核心，在此主要讨论时间进程管理、同时事件管理等。2.2.1 时间进程管理研究系统一般是为了认识其状态随时间变化的规律，所以需要。一个仿真时间变量。离散事件系统中时间的变化是用一个逻辑时钟时间的数来表示的。除了实时仿真以外，仿真时间意味着仿真时钟时间而不是仿真所用的机时，二者之间没有直接的联系。在离散事件系统仿真中，仿真时钟有两种推进方式。（1）面向时间间隔的时钟推进方式口。在这种时钟推进方式中，仿真时钟按足够小的时间间隔等距推进，使得每个时间间隔中基本上
11、不会出现两个或两个以上的离散事件。每次时钟推进都需要扫描所有活动的完成时刻，以检查在此时间间隔中有无事件发生，若有事件发生则记录此时间区间，从而更新由此事件引起的状态变量的变化。这种推进方式要求每次时钟推进都必须扫描所有正在执行的活动如图1所示。图1 面向时间间隔的时钟推进流程图（2）面向事件的时钟推进方式口。在这种时钟推进方式下，仿真时钟按照下一离散事件预计将要发生的时刻以不同的时间间隔向前推进，即仿真时钟每次都跳跃性地推进到下一事件发生的时刻。为此，必须将各事件按发生时间的先后次序进行排列，仿真时钟则按事件发生的时刻推进。每当某一事件发生时，系统开始处理相应的“活动”，并计算由该事件触发产
12、生的未来事件的发生时刻，经过一定活动处理时间后，仿真时钟将推进到下一事件发生的时刻上。这个过程不断地重复，直到仿真运行满足规定的终止条件为止。其简要流程如图2所示。图2 面向时间的时钟推进流程图2.2.2 同时事件管理同时事件即同一时间点上发生的若干事件。在仿真中，对发生在同一时刻的几个同时事件的管理有以下方法：（1）同类同时事件管理。发生在同一时刻且隶属于同一类型的几个同时事件叫同类同时事件。同类同时事件的发生会导致模型的下一状态出现多种可能值。为此，我们需要先定好条件，以使状态取值成为唯一，也就是要规定一种排队规则来管理这些同类同时事件。例如，先进先出（或先到先服务）规则、后进先出（或后到
13、先服务）规则、随机规则以及优先服务规则等。（2）混合同时事件管理。发生在同一时刻但不属于同一类型的几个同时事件叫混合同时事件。确定这些混合同时事件所造成的状态变化，通常有一步法与解结法。一步法就是直接确定混合同时事件所形成的结果状态；解结法却是把几个同时事件分解成多个单独事件的序列进行处理。对于简单情况，一步法与解结法将会得到相同的结果。但一步法不易写成通用形式，且流程管理中的通道选择较复杂；而解结法通用于各种仿真语言中，因为使用该法时模型结构简单，便于写成通用形式。3 离散事件系统的仿真离散事件系统只在一些离散的时间点上由事件改变其状态，因此它是由事件驱动的。驱动某一离散事件系统的所有事件按
14、其发生的时间先后构成了一个序列，通常要求按时间先后顺序处理事件，而不能颠倒。离散事件系统仿真的关键是按时间顺序确定这一序列，离散事件系统仿真建模的核心是如何组织这些事件。离散事件系统中的各类事件可以在不同层次上来组织。离散事件系统的仿真模型是由实体及其间的关系组成。实体状态的变化即为事件，同一实体在两个相继事件间所处的过程称为实体的活动，同一实体若干活动的延续构成一个进程。因此活动、进程都是以事件为基础构成，其粒度有大于事件。通常可以从事件、活动、进程三个不同的层次来组织事件，即处理离散事件模型的三种典型处理方法（组织事件的方法）：事件调度法、活动描述法、进程交互法。在这三种不同的方法中相应采
15、用三种不同的仿真策略，即事件调度、活动扫描和进程交互。也就是说在离散事件系统的仿真建模中我们可以采用上述三种不同的策略，采用相应的三种方法来组织事件，进而也就形成了三种不同的仿真建模方法：面向事件的仿真建模方法、面向活动的建模方法和面向进程的建模方法。所以在有的资料中将仿真策略称为仿真建模策略，又将仿真建模策略称为仿真建模方法。下面我们分别介绍这三种不同的方法。3.1 事件调度法事件调度法以事件为分析系统的基本单元，通过定义事件以及每个事件发生后对系统状态的影响，按时间顺序执行每个事件并策划新的事件来驱动仿真模型的运行。事件调度法的仿真模型（采用面向事件的仿真建模方法建立的仿真模型）主要由若干
16、事件子模块构成。所有这些事件均放在事件表中，模型中设有一个时间控制程序。仿真的过程是：从事件表中选择发生时间最早的事件，将仿真时钟推进到该事件发生的时间，并调用该事件的子模块处理事件修改系统状态和策划新的事件，然后返回时间控制程序，重复这一过程，直至满足仿真结束的条件。事件调度法的算法如下：执行仿真初始化操作：置仿真开始时间和结束时间；初始化事件表，设置初始事件；状态初始化。置仿真时钟为仿真初始时间：WHILE（仿真时钟结束时间）执行：操作事件表：取出发生时间最早的事件，设类型为i；将仿真时钟推进到上事件的发生时间;Case事件类型i=1：执行第1类事件处理程序.i=n：执行第n类事件处理程序
17、End CaseENDWHILE在该算法中还应规定具有相同发生时间的事件的先后处理顺序，即上面提到的同时事件管理。3.2活动扫描法从本质上讲，事件调度法是一种预定事件发生时间的方法。然而，有时事件除了与时间有关，还需要满足另外某些条件才能发生。这样，由于这类系统的活动持续时间的不确定性，无法预定活动的开始与结束时间，仿真建模一般采用活动扫描法。活动的发生必须满足一定的条件，其中活动发生的时间是优先级最高的条件，即首先应该判断该活动的发生时间是否满足，然后再判断其他条件。活动扫描法的算法如下：执行仿真初始化操作：置仿真的开始时间和结束时间；设置主动成分i的仿真时钟为T（i），T（i）表示成分i的
18、下一事件发生时间；状态初始化。置仿真时钟为仿真开始时间。WHILE（仿真时间结束时间）则执行扫描FOR j=最高优先数到最低优先数将优先数为j的成分置成iIF（Ti仿真时间且成分i的活动条件为真）THEN执行相应活动子程序退出当前循环重新开始扫描ENDIFENDFOR置仿真时钟=min（Ti，i=1,，主动成分个数）ENDWHILE用该方法建立仿真模型时，关键是建立活动子例程，包括此活动发生引起的实体自身状态变化以及对其它实体产生的影响等，然后用条件处理模块来控制仿真的推进，即对满足条件的活动调用其相应的活动子例程进行处理，处理完后再返回条件处理模块。如此重复执行直到仿真活动终止。3.3进程交
19、互法进程交互法采用进程描述系统，它将模型中的主动成分经历系统时所发生的事件及活动按时间顺序进行组合，从而形成进程。一个实体一旦进入进程，它将完成该进程的全部活动。软件实现时，系统仿真时钟的控制程序采用两张事件表，其一是当前事件表（CEI:CurrentEventsList），它包含了从当前时间点开始有资格执行的事件记录，但是该事件是否发生的条件（如果有）尚未判断。其二是将来事件表（FEL:FutureEventsList），它包含了在将来某个仿真时刻发生的事件的事件记录。当仿真时钟推进时，将发生时间不大于仿真时钟的所有事件记录从FEL移到CEL中，然后对CEL中的每个事件记录进行扫描。对于从C
20、EL中取出的每一个事件记录，首先判断它事件记录所属的进程以及在进程中所处的位置。该事件是否发生则取决于发生条件是否为真，若为真，则发生包含该事件的活动，只要条件允许，该进程要尽可能多地向前推进，直到结束；当CEL中的所有记录处理完毕后，结束对CEL的扫描，继续推进仿真时钟，即把将来事件表中的最早发生的事件记录移到CEL中，如此重复执行直到仿真结束。这种策略可用以下算法来描述：执行仿真初始化操作：设置仿真开始时间与结束时间；设置初始化事件，并置于FEL中；将FEL中有关事件记录置于CEL中；成分状态初始化。置系统仿真时钟为仿真开始时间。WHILE（仿真时间结束时间）则执行：扫描CEL推进仿真钟仿
21、真时钟置为FEL安排的最早时间IF（仿真时钟结束时间）则将FEL中所有在仿真时钟指示时间发生的事件记录移到CEL中ENDIFENDWHILE从上面的讨论可以看出，进程交互法既可预定事件，又可对条件求值，因而它兼有事件调度法及活动扫描法两者的特点。4 讨 论总的来说，事件调度法、活动扫描法、进程交互法各有优缺点。事件调度法建模灵活，可应用范围相对较广。活动扫描法对各事件之间相关性很强的系统来说，模型执行效率高，但需要用户对各实体的活动进行建模，仿真执行程序也比较复杂。进程交互法建模最为直观，其模型表示接近真实系统，特别适用于活动可以预测，顺序比较确定的系统，但是其流程控制复杂，建模灵活性差。在复杂系统仿真中，按进程来组织事件可以使众多的事件条理清晰，因而成为最通用的方法。在具体建模时可根据需要采用一种方法，或同时采用几种。对于离散事件系统，其仿真模型的建立一般是采用流程图的形式表示。模型的总体结构随着所采用的建模方法的不同而不同。参考文献1黄柯棣。系统仿真技术M。北京：国防科技大学出版社，1998。2康风举。现代仿真技术与应用I-M。北京：国防工业出版社，2001。3韦有双，杨湘龙，王 飞。虚拟现实技术与系统仿真M。北京：国防工业出版社，2004。
