离散系统仿真基础

3.离散系统仿真基础,离散事件动态系统(DEDS: Discrete Event Dynamic System)是指受事件驱动、系统状态跳跃式变化、系统状态迁移发生在一串离散时间点上的动态系统。,3.1 术语介绍,系统按照某些规律结合起来的，互相作用、相互依存的所有元素的集合。实体是对实际系统构成仿真模型所必须的、不可略去的各种系统（元素）的抽象。（实体）属性能描述该实体状态的一些量。它们可以是时间的函数，也可以不随时间变化。系统状态系统中全部实体的属性在某时刻t所取量值的集合S(t)定义为“系统状态”。,事件当t在T上按某种序列t1,t2,取值的过程中，系统状态发生了变化，就定义系统发生了某一“事件”。并把此时的ti值定义为“事件时刻”。活动任何引起系统状态改变的过程称为“活动”。因此“活动”的结果使系统发生“事件”。而两个相邻“事件时刻”，可以看成是某一“活动”的过程。,离散系统按照时间和事件关系的分类 :,时间离散系统本身可能连续，但只在一些特定的时刻，即T= t1,t2,上被考察。通常为了方便，各时间间隔选定为整常数。,S(t)S(t6)S(t1) 0 t1 t2 t6 t时间离散系统,时间连续而有离散事件这时，系统状态的变化，即事件时刻是不连续的，跳跃式的。,S(t)1（亮） 0 t1 t2 t3 t4 t5 t6 t人工控制的红绿灯系统,离散系统例子,不同实体可以分成两类：,静态实体这类实体在系统中往往处于被动地位。它们为动态实体提供服务。因而起设备作用。描述这类实体的最常见的属性有：忙、闲、数量、地点、速度、设备号、服务时间等。动态实体这类实体在系统中总是要求得到某些设备的服务。在系统的运行中，它们不断得以某种到达率“生成”。当从某一设备得到服务后，又流向其他设备以求服务。,系统环境能对系统产生影响的，属于系统以外的元素集合。仿真目的指仿真者希望通过仿真所获取系统的哪些性能，信息。仿真模型由系统数学模型根据仿真工具（语言）的特点，进行必要的结构变换，建立的合适算法。对同一系统，仿真的目的不同，所建的模型也将不同。,3.2 排队系统,在日常生活中，人们常常会见到各种各样的服务系统。例如：到食堂去买饭，炊事员和买饭人员构成一个服务系统；在公共汽车服务系统，由汽车、乘客和车站组成。服务系统的主要特征是出现排队。因此也称其为“排队系统”。,用于研究排队系统的理论基础是“排队论”,排队论最早由A. K. Erlang 于1918 年提出,在管理通讯和各类服务系统中有着广泛的应用,但是采用排队论方法来为DEDS 建模服务却是近二十年来的事。以排队论为基础的网络模型是离散事件系统仿真中最常用的模型。,随机排队系统的三个组成部分：,到达模式指含个类型的动态实体按怎样的规律到达。服务机构指同一时刻有多少服务设备可以接纳动态实体；对它们的服务需要多少时间。排队规则到达的动态实体将按怎样的次序接受服务。,离散仿真要解决的基本问题,如何通过已知的到达模式和服务时间的概率分布，研究排队系统的队列长度和服务设备“忙”或“闲”的程度，就是离散仿真要解决的基本问题。,几种常见的排队系统的结构：,动态实体到达离去一线一服务设备排队系统结构,动态实体到达 离去：一线并联服务设备排队系统结构,3.3 到达模式,确定型到达模式顾客有规则地按照一定的间隔时间到达。泊松到达模式满足4个条件平稳性：在a, a+t时间内有k个顾客到来的概率与a无关，只与t, k有关。记此概率为：Vk(t)在t时间间隔内到达k个顾客的概率。(P(k,t)无后效性：不相交区间内到达的顾客数是相互独立的。t1,t2到达数与t0,t1的到达数无关。普通性：令(t)表示在长度为t的区间内至少到达两个顾客的概率，则(t)=0 当t-0；有限性：在任意有限时间区间内到达有限个顾客的概率之和为1。,其中0为常数。令第i个顾客到达的时刻为i(I=1,2,)，1=0，且ti=i-i-1（i=1,2,），则顾客相继到达的间隔t是相互独立相同分布的。其到达间隔的分布为指数分布。,指数分布：,泊松分布到达模式实际上是指：到达间隔时间为指数分布的到达模式。,平均到达间隔时间Ta在考虑模型的总时间T中，共到达了n个“顾客”的情况下的比值T/n。平均到达率单位时间内到达的“顾客”数。=1/Ta。 到达间隔的分布函数A0(t)到达间隔时间大于t的概率。,A0(t) 1 F (t) A0(t) 0t,3.2.2 服务时间,定长分布这是最简单的情况。对每个动态实体的服务时间都是常数a，其分布函数为：指数分布当服务时间完全是随机的情况，可以用指数分布来表示。其分布函数：,正态分布在服务时间近似于常数的情况下，因多种随机因素的影响，使服务时间围绕这些常数值随机波动的情况。其中：0，a均值。F(x) 记为：N(a, 2)。当a=0，=1时，N(0,1)称为“标准正态分布”。,3.4 排队规则和队列的度量,排队规则动态实体应依一定的次序和规则接受服务。损失制动态实体到达时，如所有的服务设备均被占，则该实体就自动消失，永不再来。等待制动态实体到达时，如所有的服务设备均被占，则它们就排成队伍，等待服务。服务次序可以采用下列各种规则：先到先服务先到后服务随机服务优先权服务,排队规则,在优先权服务时，必须考虑当一个比现在正接受服务的实体具有更高优先权级别的动态实体到达之后，系统将会做出怎样的处理：优先权仅决定动态实体的排队先后。立即停止当前服务，为新到的高优先权的实体服务。,排队规则,3. 混合制队长有限制等待时间有限制逗留时间,队列的度量,设Ta为动态实体的平均到达间隔时间，=1/Ta为平均到达速度Ts是设备的平均服务时间，=1/Ts是平均服务速度。定义：业务量强度在已知平均到达速度和平均服务速度，业务量强度：u=/=Ts/Ta设备利用率得到服务的动态实体的到达速率与服务速度之比：=/,对队列进行度量通常考察两个量：,队列长度排队时间,3.5 设备利用率和服务质量,对系统做假设：动态实体数量是无限的，其到达速率不受排队长度的影响，并且所到达的实体不会中途离去；到达模式为泊松分布，服务设备利用率 0.75 对第二个要求如平均服务时间为10秒 = =1/10=0.1,Pw(t) 1.00.8 =0.80.6 =0.60.4 =0.40.2 =0.2 0 1 2 3 4 5 6 t,t=30秒 = t=3。查曲线得 Pw(3) 0.2 =0.6如果用更小的利用率，则会得到更低的概率。所以要求0.6。综合两个要求，可取0.6。为了使=0.6就要求顾客的平均到达时间Ta=Ts/=10/0.6=16.7（秒）。同样：对给定了到达间隔时间Ta时，也可求得Ts以达到满意的服务质量。,3.6 排队系统建模,（1）以排队论方法为基础的仿真模型设计技术主要适用于带时标的随机DEDS 系统。对排队系统来说，它只有两个基本的操作：“入队”和“离队”操作。排队模型的确切形式取决于服务设备的数量和排队线的数量。,YN （时间） 入队操作,Y N 离队操作,(2) Petri 网络模型 Petri网模型最早在1962年 Carl Adam Petri的博士论文中提出来，主要特性是具有较强的对并行、不确定性、异步和分布的描述能力和分析能力。Petri网是一个模型化的工具，它是设想来用于模型化某一类问题：即有同时平行事件的离散事件的系统的问题。Petri网模型化了系统，特别是系统的两个方面（事件和条件）及它们之间的关系。,(3)有限状态自动机模型 离散事件系统自动机及形式语言理论最早是由P. J .Ramadge 和W.M.Wonbarn 等人八十年代中期提出的,现已成为DEDS 研究的重要方法之一。有限状态自动机模型描述方法主要适用于逻辑定性模型和无时标确定性模型的建模。建立有限状态自动机模型的关键是,基于适当的仿真策略选用相应状态集合,建立正确的转移关系函数和输出关系函数。,4. 离散事件仿真策略与结构模型,仿真过程的运行调度控制（特别是在用高级语言编程时），是通过所谓的“仿真策略”来实现的。 例：对一个含有一些出纳员，一些顾客和对应每个出纳员的银行（多）排队线的系统。设：出纳员 数量5 服务速度 N(3,1) 顾客到达0.2, 0.8统计队列长度（平均，最大，最小，方差）出纳员利用率（平均，最大，最小，方差）顾客在银行的时间（平均，最大，最小，方差）,可以画出仿真程序的结构框图如下：,N YN 到达事件Y N Y,这是种“面向时间”的时钟(TIME)处理。通过多次运行程序（试验）统计得到结果。程序每做一次循环，就增加一个时间单位。此时不论系统是否有时间发生，程序总是要查询系统状态，如发现没有时间发生就跳过该事件的处理程序。这种方法的特点是：能和连续模型（进行时间离散）混合仿真。当事件子程序均能在一个时间单位内处理完成，则TIME的+1操作可以在机器硬件时钟的控制下执行，即仿真程序可以实时的（与机器时钟同步）运行。缺点是：计算机做了很多不必要的空操作。因为在两个相邻事件时刻之间，系统没有活动需要计算机处理。目前很少使用此方法。人们在研究了各种（离散）仿真调度方法的基础上，总结出三种通用的仿真策略，即：事件预定，活动扫描和进程互配。,4.1 面向事件结构模型,面向事件结构模型是按事件独立预定策略组建成的。对上述的银行系统为例，其仿真程序结构框图：,产生第一个顾客到达，填入事件表 N Y 到达事件 事务完成,事件表结构：,面向事件结构模型,在这里，仿真时钟TIME是根据当前事件的发生时刻进行离散变化的。“事件预定策略”强调：预定全部事件。事件将按显式调度。“事件功能”由事件程序实现。事件的调度是通过把事件按“事件标志”放在事件表中的方法来达到的。,4.2 活动扫描结构模型,当事件的发生不仅与时间有关，而且与其它条件也有关，即：只有在满足某些条件时发生。在这种情况下，由于活动持续时间的不确定性，无法预定活动的开始或终止时间。所以不易采用面向事件的结构模型。而活动扫描结构模型就是针对具有这种特点的系统的。,活动扫描结构模型,活动扫描结构要求对事件隐式调度。在这里，状态的转换被表示成一组称之为“活动”的函数。每次转换，由一个活动条件和一个动作组成。在每个（由预定事件生成时刻确定的）时间上，按某种（总体状态的）顺序扫描这些条件，如果出现一个条件是真，则立即执行与它联系的“动作”段；继续扫描，测试和执行，直到满足条件的活动都进行完。这是再按下一预定事件生成时刻向前推进模型的时钟。,活动扫描结构模型,按某种（总体状态）顺序扫描这些任务（包括检测小于当前时间应发生，但因条件未满足而延时发生的“以前”事件）。在使用活动扫描策略时，需要借助事件预定策略进行时间（钟）管理。事件预定策略不但要按预定事件的生成时刻向前推进仿真时钟，而且还按预定生成时刻激发事件（条件将在处理中测试）,活动扫描表结构：,4.3 进程互配模型结构,进程是一系列互相排斥的活动互配（在一个进程中，一次只能激活一个活动，进程中的活动间的连接关系：一个活动的结束，可以使该进程中的另一个活动的开始。不同的进程间会有重叠。（一个进程的活动需要取决于另一个进程中的活动的结束）。进程互配方法强调了这些进程之间的相互关系。,进程 到达 等待 离去 事件： 顾客4 排队 服务离去 等待顾客3 排队 服务 到达顾客2 服务 活动：排队顾客1服务空闲出纳2空闲 空闲 忙 空闲出纳1 E1 E2 E3 E4 E5 E7 E9 E10 时间（t） E6 E8进程运行时间示意图,进程互配模型结构,面向进程的结构适用于处理结构的仿真模型。它的设计特点是：为每一个实体（如银行系统的顾客/出纳员）建立一个进程（一个运行程序），该进程的可能的活动将反映一个（动态）实体的建立开始到结束为止所经历的一条路径。由于顾客的到达、出纳员对事务处理的时间随机性，就会出现有多个进程并存于仿真程序