排队论及网内通信业务分析

1、第四章 排队论及网内通信业务分析 排队论是专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学，也称为随机服务系统理论，它所研究的问题有强烈的实际背景，其所得的结果有广泛的应用。它是在研究各种排队系统概率规律性的基础上，来解决有关排队系统的最优设计和最优控制问题。排队论起源于本世纪初。当时，美国贝尔（Bell）电话公司发明了自动电话以后，一方面，它满足了日益增长的电话通信需要，但另一方面也带来了新的问题，即如何合理配置电话线路的数量，以尽可能地减少用户呼叫次数问题。1909年，丹麦工程师爱尔兰（AKErlang）在热力学统计平衡概念的启发下，提出了历史上具有重要地位的论文“概率论和电

2、话交换”，从而，求解了上述这类问题。可以说，直到今天，通信系统仍然是排队论应用的主要领域。第二次世界大战期间，排队论日臻完善；战后，其应用更趋广泛。目前，在通信、运输、港口泊位设计、机器维修、库存控制、计算机设计等各个领域中排队论都获得了广泛应用。本章将介绍排队论理论基础知识及其在通信网中的应用网内通信业务分析和多址接入系统，主要包括下述几方面的内容：（1） 排队论基础（2） M / M / 1排队（3） M / M / m（n）排队（4） 排队论在通信网中的应用网内通信业务分析（5） 提高网效率的一些措施（6） 多址通信4.1 排队论基础4.1.1 基本概念 排队是日常生活中经常见到的现象。

3、例如人们到商店去购物，当售货员较少而顾客较多时就会出现排队。通信网中也有类似的排队现象。当人们要使用电话时，如果电话交换机的中继线均已被占用，用户就必须等待，这是一种无形的排队现象。又如存贮转发数据传输网中，当信息到达网路节点并等待处理与传输时，就会形成排队，这种排队是有形的，但我们不容易看到。在科学技术的各个领域中，这种有形或无形、看到或看不到的排队现象有许多。它们都存在要求服务的一方和提供服务的一方，可以把要求服务的一方统称为顾客，如电话用户产生的呼叫和待传送的信息；把提供服务的一方统称为服务机构，如电话交换设备、信息传输网路等；而把服务机构内的具体设施称服务员或服务窗口，如中继线、信道等

4、。顾客到达的数目和要求提供服务的时间长短都是不确定的，这种由要求随机性服务的顾客和服务机构两方面构成的系统称为随机服务系统。 顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因。当服务设施相对顾客需求较少时，排队现象会加剧，服务质量会降低，这将引起顾客的不满；当服务设施相对顾客需求较多时，排队现象会减缓，服务质量会提高，但服务机构费用增加，空闲时间增多，设备利用率下降。排队论就是利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系，以便合理地设计和控制随机服务系统，使之既能满足一定的服务质量要求又能节省服务机构的费用。 排队论理论对通信网设计和控制有很重要的意义。通

5、信网是为人们进行信息传递的服务机构，是一个庞大而复杂的整体。排队论是对通信网内的流量进行分析的数学工具。虽然对全网内业务流量的分析是非常困难的，但用排队论来研究网路上某节点或某几条有向径上的流量，在有些情况下可以得到精确或近似的解析结果，这些结果可以指导全网的流量设计。通信网设计要根据通信流量分析计算，达到通信质量标准要求。在通信服务时间内，对用户提供良好的服务，需要有足够的通路容量，通路容量不够，将导致拥塞现象，在电路交换网中，就意味着增加业务量损失（又称呼损），在分组交换网中，就意味着增加信息延时，从经济条件考虑，通路容量要有限制。因此，信息到达网络节点时要排队等待处理，排队时延与信息长度

6、，信息到达时间，以及信息处理顺序等有关。排队理论在定量分析分组交换网方面占有重要的作用。与状态有关的排队在电路交换网中占有重要的地位，用它可以估计通信网的性能，并能定量计算电话交换中的话务损失概率。实际上现代排队论大部分是在通过电话业务研究发展起来的。排队论在通信网分析和设计中起着关键作用。一、排队系统的组成 在排队系统中主要是要讨论供求之间的关系，为了统一认识，我们要对一些概念统一起来。今后凡是要求服务的对象统称为“顾客”，提供服务的一方统称为“服务窗口或服务员”，顾客与服务窗口构成一个随机服务系统或称排队系统。 一个排队系统能抽象地描述如下：为获得服务的顾客到达服务窗口前，窗口有空闲便立刻

7、得到服务，若窗口不空闲，则需要等待窗口出现空闲时再接受服务，服务完后离开窗口，因此排队系统模型可用图41表示。一个排队系统是由三个基本部分组成的：输入过程、排队规则及服务机构。 （1）输入过程 输入过程就是顾客按怎样的规律到达，它首先应包括顾客总体数，是有限的还是无限的；其次应说明顾客到达的方式，是成批到达（每批数量是随机的还是确定性的）还是单个到达；最后应说明相继到达的顾客（成批或单个）之间的时间间隔的分布是什么。 （2）排队规则 排队规则是指服务机构什么时候允许排队，什么时候不允许排队，即排队系统的类型；顾客在什么条件下不愿意排队，在什么条件下愿意排队；在顾客排队时，服务的顺序是什么，它可

8、以是先到先服务、后到先服务、随机服务、有优先权的服务等，即服务规则是什么。 （3）服务机构 服务机构主要是指窗口或服务员的数目；当有多个窗口或服务员进行服务时，服务方式是并列还是串列，此时顾客的排队方式又如何；服务时间服从什么分布等。排队系统服务机构排队规则 顾客到达 服务完毕离去 图41 排队系统的基本组成 下面简单地介绍一下这三个过程：1 输入过程 （1）顾客总体数：它是指顾客的来源（简称顾客源），顾客源可以是无限的，也可以是有限的。例如，到售票处购票的顾客总体数可以认为是无限的，因为一般不存在最大限制数。又如，厂内的待修设备，可以认为是有限源，因为厂内设备的总体数总是有限的。 （2）顾客

9、来到方式：描述顾客是怎样来到系统的。是一个个地来到呢？还是一批批地来到排队系统。例如，在库存管理中，把入库的物资看作是“顾客”，则往往是成批来到的例子。 （3）顾客流的概率分布（或顾客到达的时间间隔分布）：所谓顾客流，就是顾客在随机时刻一个（批）个（批）来到排队系统的序列。如电话呼叫流、列车到站流等等。求解排队系统有关运行指标问题，首先要确定顾客流的概率分布。即在一定的间隔时间内来到 ( = 1, 2, )个顾客的概率是多大，或相邻两个顾客到达的时间间隔分布是什么。顾客流的概率分布一般有定长分布、二项分布、泊松流（最简单流）、爱尔兰分布等。2 排队规则(1) 排队系统类型：排队系统一般分为损失

10、制和非损失制两大类。 损失制：又称拒绝方式，拒绝系统，截止型。 当顾客来到时，若系统中已有个顾客在等待（包括正在被服务的顾客），是允许排队队长，且个窗口均被占满则遭到拒绝。即不容许他排队而离去。可分为两种情况，一为当，是窗口数时，称为即时拒绝系统，也称立接制。此时，顾客到达后或立即被拒绝，或立即被服务。当前电话网中，常属于即时拒绝系统。另一为1，称为多窗口排队系统。顾客到达率，即单位时间内平均到达系统的顾客数量。反映了顾客到达系统 的快慢程度，也反映了需要服务一方对提供服务一方的要求。越大，说明系统的负载越重。对于电话系统，就是单位时间内发生的平均呼叫数；对于数据传输系统，就是单位时间内输入的

11、平均信息量。 的倒数称为平均到达时间间隔，即，若在观察时间T内有(T)个顾客到达， 在平衡的条件下，有 不一定全部进入到系统，其单位为个/时间单位或份/时间单位。个、份为一个信息单位。电话网中，就是一个呼叫，计算机网中就是一个信息单位。那么，实际能够进入系统的到达率，我们称之为平均到达率（或有效到达率），即单位时间内进入系统的平均顾客数，用表示，故有。其中, 为阻塞率（或拒绝概率）。对于非拒绝系统，,则。 服务员的服务速率，即单位时间内由一个服务员进行服务所离开系统的平均顾客数。对于=1的单服务员系统，就是系统的服务速率，对于1的多服务员系统，单位时间接受服务后离开系统的平均顾客数为（假设每个

12、服务员的服务速率均为）。即系统服务率为。的倒数就是单个服务员对顾客的平均服务时间。也可通过对随机服务时间的统计值求平均的方法得到。三个基本参数之间的关系对随机服务系统的稳定性有很大影响。通常令 (4.1)为排队强度，又称稳定性参数。下面简要讨论对系统稳定性的影响。 若，即时，说明平均到达系统的顾客数小于平均离开系统的顾客数。这时系统是稳定的，可以采取不拒绝方式。若，即时，说明平均到达系统的顾客数多于平均离开系统的顾客数。如果系统采取非拒绝方式，系统的稳定性就无法保证，因为系统内的顾客会越来越多，所排队列会越来越长，系统将陷入混乱状态。如果采用拒绝方式，则可人为限制系统内的顾客数量，保证系统的稳

13、定性。三、排队系统分类的表示方法 目前较为广泛采用的分类表示方法是DG肯特尔（DGKendall）提出的分类方法。即根据输入过程时间分布、服务时间分布和窗口数量等特征为主来进行分类，并用字母符号来表示。即 X 表示顾客到达时间间隔分布。 Y 表示服务时间分布。 表示窗口或服务员数量（对并列排队系统）。 表示截止队长，省略这一项表示 ,即不拒绝系统。 表示潜在顾客总数，对于无限潜在顾客源，即时，可省去这一项。 表示不同输入过程（顾客流）和服务时间分布的符号有： 泊松（Poisson）流（或负指数分布）。两者都具有马尔可夫随机过程性质。 定长分布。 阶爱尔兰（Erlang）分布。 I 一般相互独立

14、的随机分布。 一般随机分布。例如：M/M1系统，系指顾客流为泊松流、服务时间为指数分布、有一个窗口的排队系统；又如：/系统，系指顾客流为泊松流、服务时间为定长分布、有个窗口的排队系统。一般如没有特别说明，则顾客总体数是无限源、属于等待制的排队系统。四、 排队系统所研究的内容与目的 1.内容：排队系统的数量指标，即研究与排队现象有关的几个数量指标的概率规律性。它们是： 队长 即在排队系统中，顾客排队等待服务的队列长短。队长中包括正在接受服务的顾客数。队长是一个随机变量。在研究排队系统时，首先要确定队长是属于何种分布。至少要知道它的平均值。有时候还要知道系统中排队等待服务的顾客数，它也是一个随机变

15、量。知道了队长分布，就可以确定队长超过某个数量的概率，从而能为设计排队空间的大小提供依据。通常用来描述队长的指标有两个，一个是队长的平均值，一个是队长的概率分布(t)。 等待和逗留时间分布 从顾客来到排队系统的时刻算起，到他（它）开始接受服务的时刻止，这段时间称为等待时间，它是一个随机变量。等待时间是顾客最为关心的数量指标，因为顾客总是希望他等待的时间愈短愈好。等待时间通常用其平均值来描述。从顾客来到系统时刻起，到他（它）接受服务完毕离开系统止这段时间称为逗留时间；也即等待时间加上服务时间，这也是一个随机变量，也是为顾客所关心的一个数量指标。逗留时间通常用其平均值来描述。 忙期和闲期分布 从顾

16、客来到空闲的窗口接受服务起，到窗口再次变成空闲为止的这段时间，即窗口连续服务时间或有顾客的持续时间称为忙期。它是一个随机变量。这是窗口最关心的数量指标。因为它关系到窗口的工作强度。与忙期相对应的是闲期，即窗口连续保持空闲的时间长度或无顾客的持续时间称为闲期。值得指出的是，排队系统中忙期和闲期是相互交替出现的。此外，窗口的利用率（即忙期所占的百分比）也是一个重要的数量指标。窗口利用率=忙期/（忙期+闲期）。一些特殊的排队系统，还有其固有的特殊数量指标。2排队系统的优化问题。在研究了排队系统的一些数量指标的概率规律后，可以在此基础上进一步研究排队系统的最优化问题。最优化问题一般涉及两种类型：一类是

17、研究排队系统的最优设计问题，它属于静态最优化问题。例如，电话网中的中继电路群数目，分组交换网中的存储空间大小等，工厂在制品中间仓库大小，医院病床数量的多少，机场跑道的数量，车站站台数等等。另一类是研究排队系统的最优控制问题，它属于动态最优化问题。例如，电话网中的中继电路群数目的增加与否，工具室是否增加工具分发工人等。3研究的目的就是既能在一定程度上满足顾客的需要，又使所需总费用为最小。 4.1.2 有关的概率模型及最简单流 一、排队系统常用的概率模型 通常，我们预先并不知道有关信息到达时间及信息长度等方面的知识。无论是信息到达时间或信息长度都具有随机变化的性质，因此我们必须依靠概率的概念来分析

18、排队的问题。以信息长度这个问题为例，我们虽然不知道下次将到达的信息的确切长度，但是根据以前长期对信息长度的统计我们可以知道出现各种信息长度的概率。下面介绍一下在本章排队系统中常用到的两种概率模型：泊松分布和指数分布。 泊松分布 设随机变量所有可能取的值为0，1，2，而取各个值的概率为 =0，1，2 (4.2) 其中0是常数，则称服从参数为的泊松分布。其均值为 (4.3)方值为 (4.4）指数分布 一般地，若随机变量取具有概率密度函数为 (4.5） 其中0为常数，则称服从参数为的指数分布，其分布函数为： 所以 (4.6） 故其均值为： (4.7） 故方差为： (4.8）二、排队系统中几个常用的概

19、念1. 系统状态：指一个排队系统中的顾客数（包括正在被服务的顾客数）。2. : 在时刻排队系统中的顾客数，即系统在时刻的瞬时状态。3. : 在时刻系统中恰好有个顾客的概率。4. ：当系统中有个顾客时，新来顾客的到达率（单位时间内新顾客的到达数）。 5.:当系统中有个顾客时，整个系统的平均服务率（单位时间内服务完毕离去的顾客数）。对所有值，当为常数时，用代替，当1时，为常数时，用代替。 6稳定状态：当一个排队服务系统开始运转时，系统状态很大程度上取决于系统的初始状态和运转经历的时间，但过了一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于稳定状态。由于对系统的瞬时状态研究分析起来

20、很困难，故排队论中主要研究系统处于稳定状态的工作情况。由于稳定状态时工作情况与时刻无关，这时可写为,可写为 。 三、最简单流 通常把随机时刻出现的事件组成的序列称为随机事件流，例如用表示（0，）时刻内要求服务的顾客人数就是一个随机事件流。1. 最简单流如果一个事件流,0,这里以输入流为例，满足下述三个条件则称该输入为最简单流。（1） 平稳性：在时间间隔内，到达个顾客的概率只与有关，而与这间隔的起始时刻无关。 即以任何时刻起点，时间内出现的顾客数只与时间长度有关而与起点无关，因此用表示内出现的顾客数，表示=的概率，则 = 0, 1, 2, =1 (2) 无后效性：顾客到达时刻互相独立，即顾客各自

21、独立地随机到达。此假设使顾客数()的随机过程具有马尔柯夫性。即在时间内出现个顾客与以前到达的顾客数无关。 (3) 疏稀性：在无限小时间间隔内，到达两个或两个以上顾客的概率可认为是零，且在有限时间区间内到达的顾客数是有限的。即在充分小的时间区间内，发生两个或两个以上事件的概率是比高阶的无穷小量，即0时,有 =o() , 在上述三个条件下，可以推出 = (4.9)证明如下： 设长为的时间区段内分成等分，每分长度=为充分小。根据疏稀性及概率的归一性，若在内落入一个“点”，即来到一个顾客，则可以写成，其概率近似为。如果在内没有落入一个“点”，即内没有顾客来到系统，其概率就近似为。由于流的无后效性，在个

22、中有顾客来到或没有顾客来到可以看作是次独立试验。这里要研究的问题是：计算在个中有个顾客来到的概率。根据二项分布有 = C()(1) (4.10）当时 (4.11）式就是所谓泊松过程在时间间隔内有个顾客到达系统的概率表达式，或称做最简单流的一维概率分布。上式中，为顾客在时间内来到数，取整数或零。 当=1时，则 有时，需要计算给定顾客数的概率，即求时间内有个以上顾客来到概率，它是等于个顾客来到概率的对立事件，即 = 注意，在推导中，我们说()是在时间期间有个顾客到达的概率，但也可以是一个排队系统中在时间内有个顾客在等待或正在处理的概率，也可以是总的条信道中有条信道被占用概率等等。 知道了后，即可求

23、在时间内有个顾客到达的均值和方差： = (4.12) 式中 = = = (4.13)由此可见，泊松分布的方差在数值上等于均值（数学期望值），由此得出 = (4.14) 可见，就是顾客的平均到达率，每秒平均到达顾客数，这一参数在通信网设计中经常要用到。 2泊松过程的信息到达的时间间隔分布 有时候，我们对泊松过程中信息到达的时间间隔分布感兴趣。下面求到达间隔的概率。由式(4.11）可以求出在时间内没有发生呼叫的概率为 换一种说法，就是在两个相邻呼叫的时间间隔大于的概率。虽然，两相邻呼叫时间间隔是一连续随机变量，用表示呼叫间隔这一随机变量，则的分布函数： (4.15) 由此式立即可得概率密度函数=e

24、，随机变量服从指数分布，则顾客到达的平均时间间隔为 (4.16) 平均顾客到达间隔是平均顾客到达率的倒数，这是合乎逻辑的。 顺便指出，说一个随机过程为“泊松到达过程”或“到达间隔为指数分布”实际是一回事。 可见最简单流与指数分布有着密切的关系。如果随机事件到达的间隔时间相互独立并且服从同一指数分布，则这样的随机事件流是最简单流。3服务时间分布 服务时间：也叫占用时间，指一个顾客接受服务时实际占用一个窗口的时间。服务时间也就是服务结束间隔时间。 服务过程：也就是顾客离去的过程,当一个服务完毕的顾客离开系统时,下一个顾客立即得到服务, 后者离去，二者的间隔时间即为服务时间。由前面推导可知，若顾客的

25、离去过程也满足最简单流条件，则离去过程（既服务过程）亦为泊松过程。离去时间间隔分布（服务时间间隔分布）为指数分布，即服务时间间隔的概率密度函数为 (4.17） 完成服务的平均时间： (4.18) 即为平均服务速率的倒数。 例4.1 设电话呼叫按30次/小时的泊松过程进行，求5分钟间隔内，不呼叫的概率，呼叫3次的概率。 解：按题意=30次/小时=0.5次/分钟 =5分钟, k = 0及k = 5 故5分钟不呼叫的概率为: 5分钟内呼叫3次的概率为: 最简单流在现实世界中常遇到，如市内交通事故、稳定情形下电话呼唤次数、到车站等车的乘客数、上下班高峰过后通过路口的自行车流、人流、汽车流等都是或近似最

26、简单流。一般说来，大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。 通信网中的信息流量，在有些系统中可以看作是最简单流，例如电话交换系统中的呼叫流。虽然呼叫流在白天和夜间的强度相差很多，但当考察的时间限制在某段时间范围时，例如最繁忙的一小时，可以认为呼叫流具有平稳性。对于无后效性和稀疏性，电话呼叫流也不可能完全满足。例如，如果用户的一次呼叫没有成功或被叫用户不在，则过一段时间后会出现重复呼叫。但是可以作一定的近似，使电话呼叫流满足无后效性和稀疏性的条件。并且大量研究也表明，将电话呼叫当作简单流处理，得到的分析结果是正确的。但是在很多通信系

27、统中，信息流不能假设为最简单流，因而不能套用上面的相关结论。例如，对于包交换系统，服务时间是固定长；对于成批进行信息处理的系统，输入流服从分布等。读者需要时可以查阅“排队论”或“随机服务系统”方面的参考书。最简单流满足的指数时间分布又称为M分布，因为这种分布使排队过程具有马尔柯夫（Markov）性。 4.1.3 生灭过程 生灭过程是用来处理输入为最简单流，服务时间为指数分布的这一类最简单排队模型的方法，即M/M/过程。生灭过程恰好反映了一个排队服务系统的瞬时状态将怎样随时间而变化。 定义：设有某个系统，具有状态集S=0，1，2，若系统的状态随时间变化的过程；0满足以下条件，则称为一个生灭过程。

28、 设在时刻系统处于状态的条件下，再经过长为（微小增量）的时间，有(1) 转移到状态的转移概率为+o()。(2) 转移到状态的转移概率为+o()。(3) 转移到S -,状态的概率为o()。其中 0, 0均为与无关的固定常数。 若S仅包含有限个元素S=0，1，2, ，也满足以上条件，则称为有限状态生灭过程。 生灭过程的例子很多，例如，一地区人口数量的自然增减、细菌繁殖与死亡、服务窗口前顾客数量的变化都可看作或近似看作生灭过程模型。 现在来讨论系统在时刻处于状态的概率分布，就是求 这里设表示系统中的顾客数。 设系统在时刻+处于状态，这一事件可分解为如下四个互不相容的事件之和：（1） 在时刻处于状态，

29、而在时刻+仍处于状态，其概率为(1-)(1-)+o(),进一步将高阶无穷小项略去得(1-)+o()，其物理意义为在（,+）时间间隔内既无顾客到达也无顾客离去或有一个顾客到达同时有一个顾客离去。（2） 在时刻处于状态-1，而在时刻+处于状态，其概率为(1-)+o(),进一步整理并舍去高阶无穷小项，得()+o()，其物理意义为在（，）时间间隔内有一个顾客到达而无顾客离去。 (3) 在时刻处于状态，而在时刻+处于状态，其概率为（） +o()，进一步整理得+o()，其物理意义为在（，）时间间隔内 有一个顾客离去而无顾客到达。 (4) 在时刻处于别的状态(即不是,），而在时刻+处于状态,其概率为 0(）

30、。由全概率公式，有 =(1-)+o()类似地，对= 0有 (+)=()(1-)+()+o() 将上面诸式，右边不含的项移到左边，用除两边，然后令，假设极限存在，就得到差分微分方程组： (4.19） 解出这组方程，即可得到时刻系统的状态概率分布,S，即生灭过程的瞬时解。一般说来，解方程组(4.19)比较困难。 假设当时，的极限存在。 = 同时可以证明 =0 这样方程组(4.19)两边对取极限，就得到线性方程组 (4.20） 移项后，(4.20)变成 (4.21)式(4.21）称为生灭过程的系统稳定状态方程（简称系统方程），由(4.21）式可以画出生灭过程的状态转移图，见图43所示。图中的数字代表

31、系统的状态，箭头代表状态间的转移关系，箭头旁的参数代表转移率。 图43 生灭过程的状态转移图 所以 = 假设 + 由于，就能解出 (4.22) 这就是生灭过程在时的稳定状态概率。在大多数实际问题中，当很大时，系统会很快趋于统计平衡。 4.1.4 排队系统的主要性能指标在分析排队系统时，往往需求解下列各项主要指标。 1排队长度：简称队长，是某时刻观察系统内滞留的顾客数，包括正在被服务的顾客。显然，是非负的离散随机变量，需用概率来描述。通常有以下三种观察方式，一是随机地取时刻来观察，相当于服务员或旁观者的随机观察。在平稳条件下，队长为的概率记为；另一是顾客到达时刻所观察到的人数，不包括刚到的顾客，

32、其概率可记为；第三种观察方式是顾客被服务完毕将离开时所看到的人数，不包括正在离去的顾客，其概率记为。以上三种观察结果，一般、和是不同的；但对于顾客到达规律具有前述的马尔柯夫性的系统,则= ，因为到达瞬间此时是纯随机的，与旁观者的随机取一样。此外，当每瞬间到达人数或离去人数只能是一人时，则=；到达时有个人排队每次都与离去时有个人排队相对应。所以满足疏稀性时，只要顾客到达是泊松流，就有=，但到达规律不是泊松流，就不能得到上述结论。关于队长，主要是求解、和以及计算的统计平均值，称为平均队长。系统内排队等待的平均顾客数称为平均等待队长，用表示。正在服务的平均顾客数用表示，则有下式成立： =+ (4.2

33、3） 其中 （非拒绝系统） (4.24) 或 （拒绝系统） (4.25) （非拒绝系统） (4.26） 或 （拒绝系统） (4.27） 2等待时间W：这是顾客到达至开始被服务这段时间。W是连续随机变量，其统计平均值称为平均等待时间，是排队系统的另一重要指标。顾客希望愈小愈好。在通信网中，是信息在网内的平均时延的主要部份。其它时延如传输时间、处理时间等一般均为常量，而且一般是较小的。 3服务时间：这是一个顾客被服务的时间，即顾客从开始被服务起到离开系统的时间间隔。的统计平均值称为平均服务时间。 。 4系统时间S：这是顾客从到达至离开的这段时间，又称系统内停留时间。 S的统计平均值称为平均系统逗留

34、时间，显然有 即 (4.28） 一个平均到达率为的排队系统，在平均的意义上，有 = (4.29） = (4.30) 式(4.29）和(4.30)称为列德尔（Little）公式，适用于任何排队系统。 5系统效率：这可定义为平均窗口占用率。某时刻有r个窗口被占用，若共有个窗口，则r/就是占用率。显然r/是一个随机变量，它的统计平均值就是系统效率，即 = (4.31)愈大，服务资源的利用率愈高。4.2 M/M/1排队本节讨论最简单的排队模型，即顾客到达时间间隔和服务时间均为指数分布的单窗口非拒绝系统。设顾客到达率为，平均服务率为。M/M/1排队系统可以用图44所示的排队系统模型来表示，这是最简单的排

35、队系统，是分析较复杂排队系统的基础。 图44 M/M/1排队系统模型 4.2.1 M/M/1排队系统 一、求解思路 求解的思路如下： （1）取队长作为状态变量。某时刻系统所处的状态主要是指系统内此时的顾客数量，是随机的，并且总在变动，这种变动与进入系统的顾客数和离开系统的顾客数有关。 （2）建立系统状态概率的微分方程。对于随机变量，通常用其概率来表示，的概率称为系统的状态概率。系统状态的变化满足一定的规律，这种规律可以用系统状态概率的微分方程来描述。系统状态概率的微分方程可简称为系统方程。 （3）求解系统方程，得到的表示式。 (4) 求解系统的各项指标。 二、求解过程 由于M/M/1排队系统的

36、顾客到达间隔时间和服务时间均为指数分布，只有一个服务员，因此可以作如下三点假设： （1）在足够小的时间间隔内，顾客进入系统只能出现两种情况：一个顾客到达系统或者没有顾客到达系统，其概率分别为和（1-）。 （2）在足够小的时间间隔内，顾客离开系统只有两种情况，有一个顾客离开或者没有顾客离开，其概率分别为和（1-）。 （3）在足够小的时间间隔内，系统状态只能向相邻状态转移，或者不转移。即如果时刻系统内有个顾客，在时刻系统内只可能有-1或或+1个顾客。 现在通过研究和+()时刻的系统状态转移情况来建立系统方程。 设系统在时刻为状态，其概率为()，系统在时刻的状态只能为-1，+1三种状态之一，如图45

37、所示。图45 内状态转移示意图如果时刻系统为()状态，在内若有一个顾客到达而无顾客离去，则可使系统在时刻为状态，其条件概率为 ()(1) 如果时刻系统为状态，在内若有一个顾客到达，同时有一个顾客离去，或者既无顾客到达也无顾客离去，则可使系统在+时刻仍为状态，其条件概率为 ()+(1)(1) 如果时刻系统为+1状态，在内若有一个顾客离去而无顾客到达，则可使系统在+时刻为状态，其条件概率为 ()(1) 以上三种情况是互相独立的，因此可使用概率加法定理，得到(+)=()(1)+()+(1) (1)+()(1) 忽略（）项，整理可得 令，可得M/M/1排队系统当1时的系统方程为 1 (4.32) 在上

38、述过程中，只要考虑到系统内的顾客数不能为负值，而且系统在时刻为0状态，在内不会有顾客离去，即可推导出=0时的系统方程为 (4.33） 对于系统方程(4.32)和(4.33)，我们要求出它的稳态解，也就是当系统运行一段时间后进入稳定状态的情况，这时系统状态概率与无关，即， 可记为，由式(4.32）和(4.33)得到系统的稳态方程为 (4.34)若已知, 令，即可求出 令式(4.34)中并将代入，又可求出 = 利用递推法可得 (4.35)确定要根据概率的归一性，即当时，此式是收敛的。在讲述排队系统基本参数时已知，非拒绝系统应使才能使系统稳定工作，这里进一步得到了验证，于是有求得： (4.36）由此

39、，可以得到系统状态概率为 (4.37) 根据系统方程可以画出M/M/1排队系统的状态转移图，见图46所示，图中的数字代表系统的状态，箭头代表状态间的转移关系，箭头旁的参数，代表转移率。图46 M/M/1排队系统的状态转移图如果已知一个排队系统的状态转移图，则很容易得到它的稳态方程，因为从式(4.34)可知，稳态方程中“进入某状态的概率等于离开该状态的概率”。如状态为2时有四条转移线，从两条入线所示的转移关系可得在（）时间内进入状态2的概率为，从两条出线所示的转移关系可得在内离开状态2的概率为，两边消去可得 它和用式(4.34)令=2得到的结果相同。 因为M/M/1系统也属于生灭过程，我们也可以

40、直接引用生灭过程的结论来求解,。对于M/M/1排队 所以结论与方法1相同。时的概率分布如图47所示。 图47 M/M/1排队系统的状态概率分布（=0.5） 4.2.2 M/M/1排队系统的各项性能指标 1平均队长和平均等待队长 即 = (4.38) 我们也可看出：是系统空闲的概率，则服务窗口的忙期的概率为： 也即系统忙期的概率就是系统的负荷率。 (4.39）与的关系如图48所示。 图48 M/M/1排队系统中平均队长随变化的关系 2平均等待时间及系统时间 当某顾客进入系统时，如果系统内没有顾客就可立即接受服务，如果系统内已有个顾客则需等待，一个顾客接受服务的平均时间为1/，故可得顾客平均等待时

41、间： (4.40） (4.41)当然，从亦可得之。 3系统效率 由于M/M/1系统是单服务员系统，所以系统效率就是系统内有顾客的概率 (4.42) 4忙期和闲期的统计特性 闲期（）：指系统中无顾客的持续时间。 忙期（）：指系统中有顾客的持续时间。，为连续非负随机变量。 闲期的分布：为顾客到达的平均间隔时间，其分布与顾客到达规律相同。在M/M/1 系统中，顾客到达规律为指数分布，则的概率密度函数为： (4.43) 其均值为： (4.44） 忙期的分布：设在内有个顾客数，：离散随机变量，：连续随机变量。对于 M/M/1系统，系统的空闲概率：由平稳性： 所以 (4.45） 可见，的均值与系统逗留时间

42、相同。 忙期内的顾客平均数 ： 即忙期内的平均队长。 对于M/M/1系统，忙期概率P忙= P忙= 所以 = /P忙= 或由 得 (4.46） 下面举例说明M/M/1系统的应用。例4.2 在某数据传送系统中，有一个数据交换节点。顾客的信息包是按泊松流到达此节点。已知平均每小时来到20个信息包，此节点的处理时间服从指数分布，平均处理每个信息包需要2.5分钟，试求该节点的有关运行指标。解： 根据题意可知，此系一M/M/1等待制系统。且已知个/分钟，个/分钟， 系统有关运行指标可计算如下： ： 反之，其忙期概率为 ：系统内顾客逗留平均数为 （个） ：系统内顾客排队等待平均数为 （个） ：每一顾客在系统

43、内平均逗留时间为 （分钟） ：每一顾客在系统内平均排队等待时间为 （分钟） 例4.3 某机关接待室只有一位对外接待人员，每天工作10小时。来访人员和接待时间都是随机的。若来访人员按泊松流输入，其输入强度为人/小时；接待时间服从负指数分布，其服务强度为人/小时。现要求知道：(1) 来访者需要在接待室逗留多久、等待多久？(2) 排队等待接待的平均人数。(3) 若希望来访者逗留时间减少一半，则接待人数应提高多少？ 解： 根据题意，已知 。（1）（小时）=120（分） （小时）=112（分）（2）（人）（3）今要求（小时）（即比减少一半），则 也即 ， 得： 即每小时若能平均接待8人，可使来访者平均逗留时间比原来减少一半。由以上计算可见，M/M/1问题的主要参量均取决于排队强度。首先由于是系统内有顾客的概率，亦即窗口忙的概率，