通信网理论基础第4章

1第4章排队论基础4．1排队论基础一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标4．2M/M/m(n)排队一、M/M/1排队系统二、M/M/m(n)排队2排队论：是一个独立的数学分支，有时也把它归到运筹学中。专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学，也称为随机服务系统理论。所研究的问题有着强烈的实际背景，其所得的结果有广泛的应用。目的：在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优设计和最优控制问题。3排队论起源：排队论起源于二十世纪初。当时，美国贝尔（Bell）电话公司发明了自动电话。如何合理配置电话线路的数量，以尽可能地减少用户重复呼叫次数问题出现了。1909年，丹麦工程师爱尔兰（A．K．Erlang）在热力学统计平衡概念的启发下，提出了历史上具有重要地位的论文“概率论和电话交换”，解决了上述问题。第二次世界大战期间，排队论日臻完善；战后，其应用更趋广泛。4应用：在通信、交通、港口泊位设计、机器维修、库存控制、计算机设计等各个领域中排队论都获得了广泛应用。通信系统仍然是排队论应用的主要领域，也是其发展的重要推动力量。经过通信、计算机和应用数学三个领域的研究学者的努力研究，排队论得到了迅速的发展。在宽带综合业务数字网中，异步传送模式，统计复用，随机多址接入中都涉及到许多排队论问题，而且正在研究解决中，如ATM业务流的数学模型及其排队分析方法。5经典（或古典）排队论：把相继到达“顾客”的到达时间间隔和服务时间都相互独立的排队论内容称为经典（或古典）排队论。经典排队论仍是新的排队论的基础，而且，通信领域的许多问题可以用它来解决。内容：排队论基础M/M/m（n）排队通信业务量分析多址接入系统业务分析6一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标7一、基本概念（一）排队系统的组成（二）排队系统的三个基本参数（三）排队系统分类的表示方法8排队：无形的排队——电话网，有形的排队——分组交换。顾客：要求服务的一方统称为顾客，如电话用户产生的呼叫和待传送的分组信息。服务机构：提供服务的一方统称为服务机构，如电话交换设备、信息传输网路等。服务员或服务窗口：把服务机构内的具体设施称服务员或服务窗口，如中继线、信道等。排队系统（随机服务系统）：由要求随机性服务的顾客和服务机构两方面构成的系统称为排队系统（随机服务系统）。9产生排队现象的根本原因：顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因。应用的理论：概率论和随机过程理论。研究的内容：研究随机服务系统内服务机构与顾客需求之间的关系（供求关系），以便合理地设计和控制随机服务系统，使之既能满足一定的服务质量要求又能节省服务机构的费用。10线路容量不够，将导致拥塞现象。电路交换网→增加业务量损失（又称呼损）分组交换网→增加信息延时。从经济条件考虑，线路容量要有限制。信息到达网络节点时要排队等待处理，排队时延与信息长度，信息到达时间，以及信息处理顺序等有关。11（一）排队系统的组成排队系统排队规则服务机构顾客到达服务完毕离去排队系统的基本组成12（一）排队系统的组成一个排队系统是由三个基本部分组成的：输入过程、排队规则及服务机构。1．输入过程输入过程就是描述顾客按怎样的规律到达排队系统，包括以下三方面：（1）顾客总体数：指顾客的来源（简称顾客源），可以是无限的，也可以是有限的。根据情况电话呼叫次数有时认为是有限的，有时认为是无限的。（2）顾客到达方式：描述顾客是怎样来到系统的，是成批到达（每批数量是随机的还是确定性的）还是单个到达。13（3）顾客流的概率分布（或顾客到达的时间间隔分布）：所谓顾客流，就是顾客在随机时刻一个（批）个（批）来到排队系统的序列。相继到达的顾客（成批或单个）之间的时间间隔的分布或到达顾客流的概率分布的是什么。如电话呼叫流、列车到站流等等。求解排队系统有关运行指标问题，首先要确定顾客流的概率分布。即在一定的间隔时间内到达k(k=1,2,…)个顾客的概率是多大，或相邻两个顾客到达的时间间隔分布是什么。顾客流的概率分布一般有定长分布、二项分布、泊松流（最简单流）、爱尔兰分布等。142.排队规则排队规则包括以下两方面：(1)排队系统类型：表明服务机构是否允许顾客排队等待服务。排队系统一般分为拒绝系统和非拒绝系统两大类。①拒绝系统：又称拒绝方式，截止型系统。设n是系统允许排队队长（也称截止对长），m是窗口数。分为两种情况：即时拒绝系统：n=m的系统。此时，顾客到达后或立即被拒绝，或立即被服务，不存在排队等待服务的情况。电话网就是即时拒绝系统。15延时拒绝系统：mn的系统。此时容许一定数量的顾客排队等待，当系统内顾客总数达到截止队长n时，新来的顾客就被拒绝而离去。即当顾客到达系统时，系统中已有k个顾客（包括正在被服务的顾客），若kn，且m个窗口有空闲，就立即接受服务，如果m个窗口均被占满，则允许顾客排队等待服务；若k=n，m个窗口必均被占满，则遭到拒绝，即不容许该顾客排队而离开系统。带有缓冲存储的数据通信，分组交换等就属于这一类。16②非拒绝系统：又称非拒绝方式，非截止型系统。系统排队队长无限制，允许顾客排队等待（一般认为顾客数是无限的）。当顾客到达系统时，若所有的窗口都已被占用，顾客就加入排队行列等待服务。例如，公用电话。要求该类系统稳定性参数ρ要满足ρ‹1。有时，称即时拒绝系统为立接制系统、损失制系统；称延时拒绝系统为混合制系统；称延时拒绝系统和非拒绝系统为等待制系统、缓接制系统。17(2)服务规则①先到先服务(FCFS)或先入先出(FIFO)。顺序服务。②后到先服务(LCFS)。如；计算机内的堆栈区域就是按此方式工作的。③优先制服务。对各类顾客分别事先赋予不同的优先级，优先级愈高，愈提前被服务。④随机服务。即当窗口有空闲时，不按照排队序列而随意地指定一个顾客去接受服务。例如，电话交换机接通呼叫的电话就是一例。通信网中一般是顺序服务，但有的也采用优先制服务方式。183.服务机构服务机构包括以下三方面内容：(1)窗口或服务员数量当m=1时，称为单窗口排队系统。当m1时，称为多窗口排队系统。(2)服务方式及排队方式服务方式：指在某一时刻接受服务的顾客数，即是单个顾客接受服务（串列服务方式）还是成批顾客同时接受服务（并列服务方式）。串列服务方式：即m个窗口的串列排队系统。此时，m个窗口的服务内容互不相同，每个窗口一次只能有一个顾客接受服务，每个顾客要依次经过这个窗口接受全部的服务。19并列服务方式：即m个窗口的并列排队系统。此时，m个窗口的服务内容相同，系统一次可以同时服务m个顾客。排队方式：包括混合排队和分别排队两种方式。混合排队：顾客排成一队。分别排队：顾客排成m个队列。20服务方式与排队方式21（3）服务时间分布服务时间和顾客到达时间一样，多数情况下是随机型的。为此，要知道它的经验分布或概率分布。一般说来，服务时间的概率分布有：定长分布、指数分布、爱尔兰分布等。22一、基本概念（一）排队系统的组成（二）排队系统的三个基本参数（三）排队系统分类的表示方法23（二）排队系统的三个基本参数任何排队系统都有三个参量m、λ、μ，称为排队模型三要素。（1）m：称为窗口数或服务员数目，表征系统的资源量。它表示系统中有多少服务设备可同时向顾客提供服务。例如机场供飞机起降的跑道数，通信系统中的线路数等。（2）λ：顾客到达率或系统到达率，即单位时间内平均到达系统的顾客数量。其单位为个/时间单位或份/时间单位，个、份为一个信息单位。对于电话系统→单位时间内发生的平均呼叫数对于数据传输系统→单位时间内输入的平均信息量24λ的倒数称为平均到达时间间隔，即。若在观察时间t内有N(t)个顾客到达，在平衡的条件下，有平均到达率（或有效到达率）：单位时间内进入系统的平均顾客数，用表示e：其中,Pn为阻塞率（或拒绝概率）。对于非拒绝系统，Pn=0，则e=。T1TttNt)(lim)1(neP25假设在无限源的情况下，顾客到达按全体顾客到达方式考虑的，故顾客到达率为平均到达率λ。在有限源的情况下，顾客到达则是按单个顾客到达方式考虑的。设每个顾客的到达率λ0相同，λ0是有限源中每个顾客在单位时间内到达系统的平均数。设顾客源数为N，则系统外的顾客平均数为（N-LS)，LS是系统的平均队长。系统的有效到达率为：k状态的系统到达率为：0)(seLN0)(kNk26（3）μ：服务员（或窗口）的服务速率，即单位时间内由一个服务员（或窗口）进行服务所离开系统的平均顾客数。m=1的单窗口系统，μ就是系统的服务速率。m1的多窗口系统，单位时间接受服务后离开系统的平均顾客数为mμ（假设每个窗口的服务速率均为μ）。即系统服务率为mμ。μ的倒数1/μ就是单个窗口对顾客的平均服务时间。稳定性参数（排队强度）ρ：1m/27ρ对系统稳定性的影响：若ρ‹1，即λ‹mμ时，说明平均到达系统的顾客数小于平均离开系统的顾客数。这时系统是稳定的，可以采取非拒绝方式和拒绝系统。若ρ≥1，即λ≥mμ时，说明平均到达系统的顾客数多于平均离开系统的顾客数。采用拒绝方式，则可人为限制系统内的顾客数量，保证系统的稳定性。28一、基本概念（一）排队系统的组成（二）排队系统的三个基本参数（三）排队系统分类的表示方法29（三）排队系统分类的表示方法采用D．G．肯特尔（D．G．Kendall）提出的分类方法：X/Y/m(n,N)X：表示顾客到达时间间隔分布。Y：表示服务时间分布。m：表示窗口或服务员数目（此处特指并列排队系统）。n：表示截止队长，省略这一项表示n→∞，即为非拒绝系统。N：表示潜在顾客总数，对于无限潜在顾客源，即N→∞时，可省去这一项。30表示不同输入过程（顾客流）和服务时间分布的符号有：Ｍ：泊松（Poisson）流（或指数分布）。两者都具有马尔可夫随机过程性质。Ｄ：定长分布。EK：K阶爱尔兰（Erlang）分布。ＧI：一般相互独立的随机分布。Ｇ：一般随机分布31一、基本概念二、有关的概率模型及最简单流三、生灭过程四、排队系统的主要性能指标32二、有关的概率模型及最简单流（一）排队系统常用的概率模型（二）排队系统中几个常用的概念（三）最简单流33（一）排队系统常用的概率模型需复习的概念：随机变量（离散型，连续型）；概率及概率分布函数、概率密度函数；数学期望（均值）、方差（偏差）；概率的归一性。341.泊松分布设随机变量X所有可能取的值为0，1，2，…，而取各个值的概率为k=0，1，2…其中λ0是常数，则称X服从参数为λ的泊松分布。其均值为方值为ekkΧPPkk!}{)(ΧE)(ΧD35２．指数分布一般地，若随机变量t取具有概率密度函数为其中λ0为常数，则t称服从参数为λ的指数分布，其分布函数F(t)为：其均值为方值为000)(ttetft0001)(ttetFt1)(tE21)(tD36二、有关的概率模型及最简单流（一）排队系统常用的概率模型（二）排队系统中几个常用的概念（三）最简单流37（二）排队系统中几个常用的概念1.系统状态：指一个排队系统中的顾客数（包括正在被服务的顾客数）。2.N(t)：在时刻t排队系统中的顾客数，即系统在时刻t的瞬时状态。3.Pk(t)：在时刻t系统中恰好有k个顾客的概率。4.λk：当系统中有k个顾客时，新来顾客的到达率（单位时间内新顾客的到达数）。5.μk：当系统中有k个顾客时，整个系统的平均服务率（单位时间内服务完毕离去的顾客数）。对所有k值，当λk为常数时，用λ代替λk，当k≥1时，μk为常数时，用μ代替μk。386．稳定状态：当一个排队服务系统运转一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于稳定状态。排队论中主要研究系统处于稳定状态的工