资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,别志松,zhisongbie,离散事件系统仿真方法,提纲,引子,离散事件仿真中的一些基本概念,离散事件仿真策略,三阶段法实例,小结,提纲,引子,离散事件仿真中的一些基本概念,离散事件仿真策略,三阶段法实例,小结,离散事件系统,系统中的状态只是在离散时间点上发生变化，而且这些离散时间点一般是不确定的，这种系统称为离散事件系统。,例子：高速公路收费口,车辆的到达时间一般是随机的；,向每辆车收取过路费的时间长度也是随机的；,描述该系统的状态是收费台的状态,(,忙或闲,),、车辆排队等待的队长。,显然，这些状态量的变化也只能在离散的随机时间点上发生。,离散事件系统的特征,与连续系统相比：,描述方式的特殊性：系统的状态变化往往无法用数学公式表示，描述方式通常为图、表等接近自然语言的方式。,动态性：离散事件系统总是动态变化的，时间是仿真模型中的一个关键变量。,随机性：离散事件系统总是包含排队过程。,由于离散事件系统固有的随机性，对这类系统的研究往往十分困难；,经典的概率及数理统计理论等学科为研究这类系统提供了理论基础；,对现实中的大量系统，惟有依靠计算机仿真技术才能提供较为完整的结果。,提纲,引子,离散事件仿真中的一些基本概念,离散事件仿真策略,三阶段法实例,小结,离散事件仿真中的基本概念,实体,事件,活动,进程,仿真时钟,统计计数器,实体,在离散事件系统中的实体可分为两大类：临时实体及永久实体。,临时实体,这类实体由系统外部到达系统，通过系统，最终离开系统。,例如高速公路收费口中车辆,永久实体,永久驻留在系统中的实体称为永久实体,例如收费台和收费通道。,临时实体按一定规律不断地到达,(,产生,),，在永久实体约束下通过系统，最后离开系统，整个系统呈现出动态过程。,实体与资源,系统中还有一类元素，被称为“资源”，与实体具有一些类似的特征，但是在特定应用的模型中不需要单独显式建模。,系统中的元素是建模为实体还是资源是建模者要决定的一个问题，取决于仿真目的。,如在无线通信系统仿真中，终端、基站等可能被建模为实体，功率、带宽等被建模为资源。,主动实体和被动实体,主动实体是那些可以主动产生活动的实体，如排队系统中的顾客，它的到达将产生排队活动或服务活动；,被动实体本身不能激发活动，只能在主动成分作用下发生状态变化。,实体与面向对象建模,实体有点类似于面向对象建模中的对象的概念,具有类似特征的对象通常以类的方式进行组织，每个类有不同的属性，同一类的不同对象对应的属性值可能不同。,属性值的两个作用：,第一个用于进行集合划分，具有相同属性的一些对象有时会被组织为一个集合；,第二是是用于控制实体的行为，这类属性与特定值之间的关系称为条件。,事件,事件就是引起系统状态发生变化的行为。从某种意义上说，离散事件系统是由事件来驱动的。,例如高速公路收费口：,定义“车辆到达”为一类事件，因为由于车辆到达，系统的状态,收费员的“状态”可能从闲,(,如果无车排队,),到忙。或者另一系统状态,排队的车辆数发生变化,(,队列车辆数加,1),。,定义“车辆离开”为一类事件，一辆车交费完毕后离开导致系统的一状态收费口“状态”由忙变成闲。,事件驱动,在一个系统中，往往有许多类事件发生，而事件的发生一般与某一类实体相联系,某一类事件的发生还可能会引起别的事件发生，或者是成为另一类事件发生的条件。,为了实现对系统中的事件进行管理，在仿真模型中必须建立事件表，表中记录每一发生了的或将要发生的事件类别和发生时间，以及与该事件相连的实体的有关属性等。,在仿真模型中，仿真钟的推进、程序的控制都是依靠事件来驱动的，除了系统中固有事件,(,又称为系统事件,),外，还有所谓程序事件,(,又称为计算机控制事件,),，它用于控制仿真进程。,活动,离散事件系统中的活动，通常用于表示两个可以区分的事件之间的过程，它标志着系统状态的转移。,例子：高速公路收费口,车辆的到达事件与该车辆开始接受收费服务事件之间可称为一个活动，该活动是系统的状态,(,车队长度,),发生变化；,车辆开始接受收费到该车辆交费完毕后离去也可视为一个活动，它使队长减,1,。,进程,进程由若干个有序事件及若干个有序活动组成，一个进程描述了它所包括的事件及活动间的相互逻辑关系及时序关系。,例子：高速公路收费口,一台车辆到达，经过排队、交费、直到交费完毕后离去可称为一个进程。,经常用进程表示临时实体的整个或部分生命周期。,事件、活动、进程三者间的关系,仿真时钟,仿真时钟用于表示仿真时间的变化。,与在连续系统仿真不同的是，离散事件动态系统的状态本来就只在离散时间点上发生变化，因而不需要离散化处理。,由于引起状态变化的事件发生时间的随机性，仿真时钟的推进步长则完全是随机的；,两个相邻发生的事件之间系统状态不会发生任何变化，因而仿真时钟可以跨过这些“不活动”周期。,从一个事件发生时刻推进到下一事件发生时刻，仿真时钟的推进呈现跳跃性，推进速度具有随机性。,是仿真的时间基础、仿真过程的推进器和驱动器。,统计计数器,连续系统仿真的目的是要得到状态变量的动态变化过程并由此分析系统的性能；而离散事件系统仿真的目的主要不是得到这些状态是如何变化的。,离散事件系统仿真的结果只有在统计意义下才有参考价值,由于变化是随机的，某一次仿真运行得到的状态变化过程只不过是随机过程的一次取样，若进行另一次，状态变化过程可能完全是另,种情况。,因此，离散事件系统仿真模型中，需要有一个统汁计数部件，以便统计系统中的有关变量。,提纲,引子,离散事件仿真中的一些基本概念,离散事件仿真策略,三阶段法实例,小结,常见的仿真策略,事件调度法,活动扫描法,进程交互法,三阶段法,事件调度法,基本思想是用事件的视角来分析真实系统；,定义事件以及每个事件发生所引起的系统状态变化；,按事件发生时间先后顺序来安排事件，并处理每个事件发生时的有关逻辑关系。,若按照这种策略建立模型时，所有的事件均放在事件表中。,事件调度法基本过程,模型中设有一个时间控制组件，它从事件表中选择具有最早发生时间的事件并将仿真钟修改到该事件发生的时间；,调用与该事件相应的事件处理模块；,该事件处理后返回时间控制组件。,事件的选择与处理不断进行，直到仿真终止条件或程序事件产生为止。,事件的发生与否有时不仅与时间有关，与其他条件也有关，即只有满足某些条件时才会发生，这种情况下事件列表的生成与管理会复杂化。,活动扫描法,基本思想是以活动为中心组织仿真过程。,主要特点,在活动扫描法中，系统由实体组成，实体包含着活动，这些活动的发生必须满足某些条件；,每一个主动实体均有一个相应的活动子程序，并且需要设置一个条件测试子程序用于进行条件测试；,设置一个活动扫描模块，这个模块不但需要扫描主动实体活动发生的时间，还需要扫描活动发生的条件。,仿真钟的推进不再单单决定于每个主动实体仿真钟最小值，还与条件处理有关。,活动扫描法的仿真模型中，对于实体间相互关系的定义除了实体本身的活动外，还需要包括对于“条件”的处理。,进程交互法,基本思想是以进程为中心组织整个仿真过程,主要特点,模型中的主动实体所发生的事件及活动按时间顺序进行组合，从而形成进程表。,一个实体一旦进入进程，它将尽可能执行尽可能多的活动，直到遇到某些条件满足才能执行的活动则进程停止，与其它实体的进程实现交互。,进程交互法既可以预定事件，又可对条件求值，兼有事件驱动法和活动扫描法的优点。,从用户的角度来看，该策略更易于使用，但其软件实现比事件驱动和活动扫描法要复杂得多。,三阶段法（,1,）,基本思想是将无条件事件和有条件事件的处理相分离，每一次修改仿真钟之后都会对两类事件分别进行处理。,两类事件,B,（,bound,或者,booked,）事件,发生时刻是可预测的，是无条件的,B,事件通常是“到达”或“结束”类事件。,如通信系统仿真中一次语音通话的发起与结束,C,（,conditional,）事件,发生与否是有条件的，通常与时间没有直接关系,C,事件通常与某活动是否开始相联系。,如一次呼叫是否被服务就是典型的,C,事件,三阶段法（,2,）,右图为三阶段法的处理过程,开始进入循环阶段之后，在仿真钟每,发生一次改变都会分成三个阶段执行,A,阶段：时间扫描。找出下一个最早发,生的时间，将系统仿真钟推进到该事件,的发生时刻。记录在该时刻要发生的,B,事件，形成一个,B,事件列表；,B,阶段：执行,B,事件列表,C,阶段：查询,C,事件表，逐一对事件表中,的事件进行条件测试，若条件满足则执,行相应的动作,提纲,引子,离散事件仿真中的一些基本概念,离散事件仿真策略,三阶段法实例,小结,三阶段法实例,B,事件,事件,类型,状态变化,规定的下一事件,B1,到达,X,呼叫到达并进入路由队列,B1,B2,到达,Y,呼叫到达并进入路由队列,B2,B3,完成动作,路由完成工作并输出,X,到接线员,1,队列，,Y,到接线员,2,队列,B4,完成动作,接线员,1,完成工作（完成接线数加,1,）,B5,完成动作,接线员,2,完成工作（完成接线数加,1,）,B6,仿真结束,C,事件,事件,类型,条件,状态改变,规定的下一个事件,C1,开始动作,电话在路由队列中并且路由空闲,路由把电话从路由队列中取出并开始工作,B3,C2,开始动作,电话在接线员,1,的队列中并且接线员,1,空闲,接线员,1,把电话从接线员,1,的队列中取出并开始工作,B4,C3,开始动作,电话在接线员,2,的队列中并且接线员,2,空闲,接线员,2,把电话从接线员,2,的队列中取出并开始工作,B5,t=0,31,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,初始化,空,空闲,空,空闲,空,空闲,B,事件列表,输出结果,事件,时间,工作完成,B1,5,X,0,B2,10,Y,0,B6,19,t=5,32,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,B,X1,空闲,空,空闲,空,空闲,C,空,X1,空,空闲,空,空闲,B,事件列表,结果,事件,时间,工作完成,B3,6,X,0,B2,10,Y,0,B1,10,B6,19,t=6,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,B,空,空闲,X1,空闲,空,空闲,C,空,空闲,空,X1,空,空闲,事件列表,结果,事件,时间,工作完成,B2,10,X,0,B1,10,Y,0,B4,10,B6,19,t=10,34,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,B,Y1,，,X2,空闲,空,空闲,空,空闲,C,X2,Y1,空,空闲,空,空闲,事件列表,结果,事件,时间,工作完成,B3,11,X,1,B1,15,Y,0,B6,19,B2,20,t=11,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,B,空,空闲,X2,空闲,空,Y1,C,空,空闲,空,X2,空,Y1,事件列表,结果,事件,时间,工作完成,B1,15,X,1,B4,16,Y,0,B5,18,B6,19,B2,20,t=12,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,B,空,空闲,X2,空闲,空,Y1,C,空,空闲,空,X2,空,Y1,事件列表,结果,事件,时间,工作完成,B1,15,X,1,B4,16,Y,0,B5,18,B6,19,B2,20,t=15,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,B,X3,空闲,空,X2,空,Y1,C,空,X3,空,X2,空,Y1,B,事件列表,结果,事件,时间,工作完成,B4,16,X,1,B3,16,Y,0,B5,18,B6,19,B2,20,B1,20,t=16,模型状态,阶段,路由队列,路由,接线员,1,队列,接线员,1,接线员,2,队列,接线员,2,B,空,空闲,X3,空闲,空,Y1,C,空,空闲,空,X3,空,Y1,事件列表,结果,事件,时间,工作完成,B5,18,X,2,B6,19,Y,0,B2,20,B1,20,B4,20,提纲,引子,离散事件仿真中的一些基本概念,离散事件仿真策略,三阶段法实例,小结,小结,与连续系统仿真相比，离散事件系统仿真并不关心采用什么样的数值算法，而更关注如何对仿真过程进行组织，也就是所谓的仿真策略问题。,三阶段法是目前广泛采用的、可操作性较强的离散事件仿真策略。,
展开阅读全文