通信网理论基础第4章

第4章排队论基础,41排队论基础一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标42M/M/m(n)排队一、M/M/1排队系统二、M/M/m(n)排队,排队论：是一个独立的数学分支，有时也把它归到运筹学中。专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学，也称为随机服务系统理论。所研究的问题有着强烈的实际背景，其所得的结果有广泛的应用。目的：在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优设计和最优控制问题。,排队论起源：排队论起源于二十世纪初。当时，美国贝尔（Bell）电话公司发明了自动电话。如何合理配置电话线路的数量，以尽可能地减少用户重复呼叫次数问题出现了。1909年，丹麦工程师爱尔兰（AKErlang）在热力学统计平衡概念的启发下，提出了历史上具有重要地位的论文“概率论和电话交换”，解决了上述问题。第二次世界大战期间，排队论日臻完善；战后，其应用更趋广泛。,应用：在通信、交通、港口泊位设计、机器维修、库存控制、计算机设计等各个领域中排队论都获得了广泛应用。通信系统仍然是排队论应用的主要领域，也是其发展的重要推动力量。经过通信、计算机和应用数学三个领域的研究学者的努力研究，排队论得到了迅速的发展。在宽带综合业务数字网中，异步传送模式，统计复用，随机多址接入中都涉及到许多排队论问题，而且正在研究解决中，如ATM业务流的数学模型及其排队分析方法。,经典（或古典）排队论：把相继到达“顾客”的到达时间间隔和服务时间都相互独立的排队论内容称为经典（或古典）排队论。经典排队论仍是新的排队论的基础，而且，通信领域的许多问题可以用它来解决。内容：排队论基础M/M/m（n）排队通信业务量分析多址接入系统业务分析,一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标,一、基本概念（一）排队系统的组成（二）排队系统的三个基本参数（三）排队系统分类的表示方法,排队：无形的排队电话网，有形的排队分组交换。顾客：要求服务的一方统称为顾客，如电话用户产生的呼叫和待传送的分组信息。服务机构：提供服务的一方统称为服务机构，如电话交换设备、信息传输网路等。服务员或服务窗口：把服务机构内的具体设施称服务员或服务窗口，如中继线、信道等。排队系统（随机服务系统）：由要求随机性服务的顾客和服务机构两方面构成的系统称为排队系统（随机服务系统）。,产生排队现象的根本原因：顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因。应用的理论：概率论和随机过程理论。研究的内容：研究随机服务系统内服务机构与顾客需求之间的关系（供求关系），以便合理地设计和控制随机服务系统，使之既能满足一定的服务质量要求又能节省服务机构的费用。,线路容量不够，将导致拥塞现象。电路交换网增加业务量损失（又称呼损）分组交换网增加信息延时。从经济条件考虑，线路容量要有限制。信息到达网络节点时要排队等待处理，排队时延与信息长度，信息到达时间，以及信息处理顺序等有关。,（一）排队系统的组成,排队系统的基本组成,（一）排队系统的组成一个排队系统是由三个基本部分组成的：输入过程、排队规则及服务机构。1输入过程输入过程就是描述顾客按怎样的规律到达排队系统，包括以下三方面：（1）顾客总体数：指顾客的来源（简称顾客源），可以是无限的，也可以是有限的。根据情况电话呼叫次数有时认为是有限的，有时认为是无限的。（2）顾客到达方式：描述顾客是怎样来到系统的，是成批到达（每批数量是随机的还是确定性的）还是单个到达。,（3）顾客流的概率分布（或顾客到达的时间间隔分布）：所谓顾客流，就是顾客在随机时刻一个（批）个（批）来到排队系统的序列。相继到达的顾客（成批或单个）之间的时间间隔的分布或到达顾客流的概率分布的是什么。如电话呼叫流、列车到站流等等。求解排队系统有关运行指标问题，首先要确定顾客流的概率分布。即在一定的间隔时间内到达k(k=1,2,)个顾客的概率是多大，或相邻两个顾客到达的时间间隔分布是什么。顾客流的概率分布一般有定长分布、二项分布、泊松流（最简单流）、爱尔兰分布等。,2.排队规则排队规则包括以下两方面：(1)排队系统类型：表明服务机构是否允许顾客排队等待服务。排队系统一般分为拒绝系统和非拒绝系统两大类。拒绝系统：又称拒绝方式，截止型系统。设n是系统允许排队队长（也称截止对长），m是窗口数。分为两种情况：即时拒绝系统：n=m的系统。此时，顾客到达后或立即被拒绝，或立即被服务，不存在排队等待服务的情况。电话网就是即时拒绝系统。,延时拒绝系统：m1的多窗口系统，单位时间接受服务后离开系统的平均顾客数为m（假设每个窗口的服务速率均为）。即系统服务率为m。的倒数1/就是单个窗口对顾客的平均服务时间。稳定性参数（排队强度）：,对系统稳定性的影响：若1，即m时，说明平均到达系统的顾客数小于平均离开系统的顾客数。这时系统是稳定的，可以采取非拒绝方式和拒绝系统。若1，即m时，说明平均到达系统的顾客数多于平均离开系统的顾客数。采用拒绝方式，则可人为限制系统内的顾客数量，保证系统的稳定性。,一、基本概念（一）排队系统的组成（二）排队系统的三个基本参数（三）排队系统分类的表示方法,（三）排队系统分类的表示方法采用DG肯特尔（DGKendall）提出的分类方法：X/Y/m(n,N)X：表示顾客到达时间间隔分布。Y：表示服务时间分布。m：表示窗口或服务员数目（此处特指并列排队系统）。n：表示截止队长，省略这一项表示n，即为非拒绝系统。N：表示潜在顾客总数，对于无限潜在顾客源，即N时，可省去这一项。,表示不同输入过程（顾客流）和服务时间分布的符号有：泊松（Poisson）流（或指数分布）。两者都具有马尔可夫随机过程性质。：定长分布。EK：K阶爱尔兰（Erlang）分布。I：一般相互独立的随机分布。：一般随机分布,一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标,二、有关的概率模型及最简单流（一）排队系统常用的概率模型（二）排队系统中几个常用的概念（三）最简单流,（一）排队系统常用的概率模型需复习的概念：随机变量（离散型，连续型）；概率及概率分布函数、概率密度函数；数学期望（均值）、方差（偏差）；概率的归一性。,1.泊松分布设随机变量X所有可能取的值为0，1，2，而取各个值的概率为k=0，1，2其中0是常数，则称X服从参数为的泊松分布。其均值为方值为,指数分布一般地，若随机变量t取具有概率密度函数为其中0为常数，则t称服从参数为的指数分布，其分布函数F(t)为：其均值为方值为,二、有关的概率模型及最简单流（一）排队系统常用的概率模型（二）排队系统中几个常用的概念（三）最简单流,（二）排队系统中几个常用的概念1.系统状态：指一个排队系统中的顾客数（包括正在被服务的顾客数）。2.N(t)：在时刻t排队系统中的顾客数，即系统在时刻t的瞬时状态。3.Pk(t)：在时刻t系统中恰好有k个顾客的概率。4.k：当系统中有k个顾客时，新来顾客的到达率（单位时间内新顾客的到达数）。5.k：当系统中有k个顾客时，整个系统的平均服务率（单位时间内服务完毕离去的顾客数）。对所有k值，当k为常数时，用代替k，当k1时，k为常数时，用代替k。,6稳定状态：当一个排队服务系统运转一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于稳定状态。排队论中主要研究系统处于稳定状态的工作情况。这时Pk(t)可写为Pk,N(t)可写为N。,二、有关的概率模型及最简单流（一）排队系统常用的概率模型（二）排队系统中几个常用的概念（三）最简单流,（三）最简单流随机事件流：通常把随机时刻出现的事件组成的序列称为随机事件流，例如：用N(t)表示（0，t）时间内要求服务的顾客人数就是一个随机事件流。1.最简单流如果一个事件流N(t）,t0,这里以输入流为例，满足下述三个条件则称该输入为最简单流。（1）平稳性（2）无后效性（3）稀疏性,（1）平稳性在时间间隔t内，到达k个顾客的概率只与t有关，而与这间隔的起始时刻无关。即以任何时刻t0起点，(t0,t0+t)时间内出现的顾客数k只与时间长度t有关而与起点t0无关。N(t）：表示(t0,t0+t)内出现的顾客数Pk(t)：表示N(t）=k的概率，则k=0,1,2,（2）无后效性顾客到达时刻互相独立，即顾客各自独立地随机到达。此假设使顾客数k(t)的随机过程具有马尔柯夫性。即在(t0,t0+t)时间内出现k个顾客与t0以前到达的顾客数无关。（3）稀疏性在无限小时间间隔t内，到达两个或两个以上顾客的概率可认为是零，且在有限时间区间内到达的顾客数是有限的。即在充分小的时间区间t内，发生两个或两个以上事件的概率是比t高阶的无穷小量，即t0时,有,在上述三个条件下，可以推出这里，Pk(t)是在时间t期间有k个顾客到达的概率，或一个排队系统中在时间t内有k个顾客在等待或正在处理的概率，也可以是总的C条信道中有k条信道被占用概率等。,均值为2泊松过程的顾客到达时间间隔分布顾客到达时间间隔分布：就是顾客到达的时间间隔小于t的概率，即t内有顾客的概率分布。两相邻顾客到达的时间间隔是一连续随机变量，用T表示。在时间t内没有顾客到达的概率为则T的分布函数：,概率密度函数：即随机变量t服从指数分布，则顾客到达的平均时间间隔为总结：一个随机过程为“泊松到达过程”或“到达时间间隔为指数分布”实际上是一回事。如果随机事件到达的间隔时间相互独立并且服从同一指数分布，则这样的随机事件流是最简单流。,3服务时间分布服务时间：也叫占用时间，指一个顾客接受服务时实际占用一个窗口的时间，也就是服务结束的间隔时间，用表示。服务过程：也就是顾客离去的过程。当一个服务完毕的顾客离开系统时，下一个顾客立即得到服务,后者离去，二者的间隔时间即为服务时间。若顾客的离去过程也满足最简单流条件，则离去过程（既服务过程）亦为泊松过程，即有,离去时间间隔分布（服务时间间隔分布）为指数分布，即服务时间间隔的概率密度函数为完成服务的平均时间：例4.8设电话呼叫按30次/小时的泊松过程进行，求5分钟间隔内，不呼叫的概率，呼叫3次的概率。,最简单流满足的指数时间分布又称为M分布，因为这种分布使排队过程具有马尔柯夫（Markov）性。一般说来，大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。通信网中的信息流量，在有些系统中可以看作是最简单流，例如电话交换系统中的呼叫流。但是在很多通信系统中，信息流不能假设为最简单流，因而不能套用上面的相关结论。例如，对于包交换系统，服务时间是固定长；对于成批进行信息处理的系统，输入流服从EK分布等。,一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标,三、生灭过程生灭过程是用来描述输入过程为最简单流，服务时间为指数分布的这一类最简单的排队模型，即M/M/m(n，N)过程。生灭过程定义：设有某个系统，具有状态集S=0，1，2，若系统的状态随时间t变化的过程N(t）,t0满足以下条件，则称为一个生灭过程。设在时刻t系统处于状态k的条件下，再经过长为t(t0)的时间，即当tt+t时，有,(1)转移到k+1(0k+)状态的转移概率为kt+o(t)。(2)转移到k1(1k+)状态的转移概率为kt+o(t)。(3)转移到Sk1,k,k+1状态的转移概率为o(t)。其中k0,k0，且均为与时间无关的固定常数。若S仅包含有限个元素S=0，1，2,，同时也满足以上条件，则称为有限状态生灭过程。,讨论：生灭过程在t时刻处于k状态的概率分布，或者说当tt+t时，求解Pk(t+t)(t0)，即求：设系统在(t+t)时刻处于k状态，根据生灭过程的定义，这一事件可分解为如下四个互不相容的事件之和：(1)在t时刻处于k状态，在(t+t)时刻仍处于k状态其转移概率为即,(2)在t时刻处于k-1状态，在(t+t)时刻处于k状态其转移概率为即(3)在t时刻处于k+1状态，在(t+t)时刻处于k状态其转移概率为即(4)在t时刻处于别的状态(即不是k,k-1,k+1状态)，在(t+t)时刻处于k状态其转移概率为,即tt+t，k1,k,k+1k，求Pk。,t内状态转移示意图(t0),得生灭过程的系统稳定状态方程（简称系统方程）,生灭过程的状态转移图,结论：“进入某状态的概率等于离开该状态的概率”,由：得生灭过程在t时的稳定状态概率,一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标,四、排队系统的主要性能指标通信网络的设计与规划的目的：在一定程度上满足顾客的需要，又使所需总费用为最小。排队论研究排队系统的最优化问题。最优化问题一般涉及两种类型：排队系统的最优设计(静态优化)问题。例如，电话网中的中继电路群数目，分组交换网中的存储空间大小等，工厂的中间制品仓库大小，医院病床数量的多少，机场跑道的数量，车站站台数等等。排队系统的最优控制(动态优化)问题。例如，电话网中的中继电路群数目的增加与否，工具室是否增加工具分发工人等。,排队系统的性能指标(1)排队长度k。简称队长，是某时刻观察系统内滞留的顾客数，包括正在被服务的顾客。k是非负的离散随机变量，需用概率来描述。描述队长k的指标有两个：1、队长k的概率分布Pk(t)（Pk或rk或dk）2、队长k的统计平均值Ls或平均等待队长Lq。确定了队长的分布，就可以确定队长超过某个数量的概率，从而能为设计排队空间的大小提供依据。,三种观察方式（观察时间）：a.随机地取t时刻来观察，相当于服务员或旁观者的随机观察。在平稳条件下，队长为k的概率记为Pk。b.顾客到达时刻所观察到的人数，不包括刚到的顾客，其概率可记为rk；c.顾客被服务完毕将离开时所看到的人数，不包括正在离去的顾客，其概率记为dk。,一般Pk、rk和dk是不同的：a.对于顾客到达规律具有马尔柯夫性的系统,则Pk=rk。因为到达瞬间t是纯随机的，与旁观者的随机取t一样。b.满足疏稀性，当每瞬间到达人数或离去人数只能是一人时，则rk=dk；到达时有k个顾客排队每次都与离去时有k个顾客排队相对应。c.满足疏稀性时，只要顾客到达是泊松流，就有Pk=rk=dk。d.到达规律不是泊松流，就不能得到上述结论。,平均队长Ls：队长k的统计平均值。平均等待队长Lq：系统内排队等待的平均顾客数。：正在服务的平均顾客数（或平均占用窗口数）。,（非拒绝系统）,（拒绝系统）,（2）等待和系统逗留时间分布等待时间：从顾客到达排队系统的时刻算起，到他（它）开始接受服务的时刻止这段时间。平均等待时间Wq：等待时间的统计平均值。系统逗留时间（或系统时间）：从顾客来到系统时刻起，到他（它）接受服务完毕离开系统止这段时间。这也是一个连续随机变量。平均系统逗留时间Ws：系统时间的统计平均值。,服务时间：这是一个顾客被服务的时间，即顾客从开始被服务起到离开系统的时间间隔。平均服务时间：的统计平均值。一个平均到达率为e的排队系统，在平均的意义上，有,列德尔（Little）公式,适用于任何排队系统,（3）系统效率：为平均窗口占用率。（4）空闲概率P0和拒绝概率PnP0：为系统内无顾客的情况，即系统空闲状态概率。通过P0，可知系统的忙闲情况。Pn：对于拒绝系统，Pn（或Pc）为系统内顾客已满，拒绝新到顾客进入系统的状态概率，也称为损失概率。,422M/M/m(n)排队一、M/M/1排队系统二、M/M/m(n)排队,一、M/M/1排队系统顾客到达时间间隔和服务时间均为指数分布的单窗口非拒绝系统。设顾客到达率为，平均服务率为。,M/M/1排队系统的状态转移图,（一）求解P0、Pk,M/M/1排队系统的状态概率分布（=0.5）,（二）M/M/1排队系统的主要性能指标1平均队长Ls和平均等待队长Lq,M/M/1排队系统中平均队长Ls随变化的关系,2顾客平均等待时间Wq及系统时间Ws3系统效率,例4.9在某数据传送系统中，有一个数据交换节点。信息包是按泊松流到达此节点。已知平均每小时来到20个信息包，此节点的处理时间服从指数分布，平均处理每个信息包需要2.5分钟，试求该节点的有关性能指标。,结论：M/M/1系统的主要问题是服务质量和系统效率之间有矛盾。要解决好这一矛盾，必须能在提高效率的同时，设法压缩排队长度以减小等待时间。：系统内有顾客的概率，亦即窗口忙的概率。为了提高服务资源的利用率，就希望选择得大一些。系统效率：Wq服务质量从顾客的观点来看，常希望小一些。等待时间,从系统的稳定性方面看，必须使1。当1时，以上公式都将不适用。实际上此时Ls和Wq均将趋于无限，或者说队长将不断增大，不能达到稳定，系统已不能稳定地工作。总之，的取值应兼顾系统效率、等待时间和稳定性诸因素。,M/M/1排队系统的平均队长与时间的关系,422M/M/m(n)排队一、M/M/1排队系统二、M/M/m(n)排队,二、M/M/m(n)排队（一）M/M/m(n)排队系统（二）M/M/1(n)排队系统（三）M/M/m(m)系统,二、M/M/m(n)排队M/M/1系统的主要缺点：服务质量与系统效率的矛盾不易解决。措施：压缩排队长度，减小等待时间。通常有两种措施：（1）增加窗口数。对于一定的顾客到达率，增加窗口能减少等待时间，同时也能提高效率。这是一种积极的措施。如在通信网中，增加信道数，扩大线路的传输带宽或提高传输速率和处理速率。缺点：投资加大。,（2）截止排队长度：采用拒绝型系统。这是一种消极措施。提高了系统效率和稳定性，减小了等待时间，但有顾客被拒绝。缺点：降低了系统质量。综合为：截止型多窗口M/M/m(n)排队系统（混合排队方式）（一）M/M/m(n)排队系统M/M/m(n)排队系统：a.顾客到达间隔时间服从指数分布，顾客到达率为；b.有m个窗口，每个窗口对一位顾客的服务时间均为指数分布，每个窗口的平均服务率为；c.采取拒绝方式，系统内最多可有n个顾客。,M/M/m(n)排队系统的系统模型和状态转移图,1.求解P0、Pk,2.M/M/m(n)排队系统的主要性能指标（1）平均队长Ls和平均等待队长Lq及正在服务的平均顾客数,（2）顾客平均等待时间Wq及系统时间Ws,（3）系统效率,（二）M/M/1(n)排队系统1.求解P0、Pk2主要性能指标（1）平均队长Ls,（2）顾客平均等待时间Wq归一化平均等待时间Wq为（3）系统效率,（4）顾客被拒绝的概率P