北邮通信网排队论期中论文资料

《北邮通信网排队论期中论文资料》由会员分享，可在线阅读，更多相关《北邮通信网排队论期中论文资料（19页珍藏版）》请在装配图网上搜索。

1、通信网期中论文排队论概述一、排队论基本概念排队论起源于本世纪初。当时，美国贝尔（ Bell ）电话公司发明了自动电话以后， 一方面， 它满足了日益增长的电话通信需要， 但另一方面也带来了新的问题， 即如何合理配置电话线路的数量， 以尽可能地减少用户呼叫次数问题。 1909年，丹麦工程师爱尔兰（A K Erlang ）在热力学统计平衡概念的启发下，提出了历史上具有重要地位的论文“概率论和电话交换” ，从而，求解了上述这类问题。可以说，直到今天，通信系统仍然是排队论应用的主要领域。第二次世界大战期间，排队论日臻完善；战后，其应用更趋广泛。目前，在通信、运输、港口泊位设计、 机器维修、 库存控制、

2、计算机设计等各个领域中排队论都获得了广泛应用。排队是日常生活中经常遇到的现象。 例如人们到商店去购物， 当售货员较少而顾客较多时就会出现排队； 在通信网中， 当人们要使用电话时， 如果电话交换机的中继线均已被占用， 用户就必须等待， 这是一种无形的排队现象。 在科学技术的各个领域中， 这种有形或无形、 看到或看不到的排队现象有许多。 它们都存在要求服务的一方和提供服务的一方， 可以把要求服务的一方统称为顾客， 如电话用户产生的呼叫和待传送的信息； 把提供服务的一方统称为服务机构， 如电话交换设备、信息传输网路等；而把服务机构内的具体设施称服务员或服务窗口，如中继线、信道等。顾客到达的数目和要求

3、提供服务的时间长短都是不确定的，这种由要求随机性服务的顾客和服务机构两方面构成的系统称为随机服务系统或排队系统。排队论也称随机服务系统理论， 它是一门研究处理随机服务系统排队现象的学科。 它的任务是考察服务系统随机现象的规律， 建立数学模型， 为决策者正确地设计与有效地运营服务系统而提供必要的科学依据， 使决策者在系统服务费用和顾客的有关等待费用之间达到经济上的平衡。服务系统的服务能力取决于服务员的数目、 能力， 也取决于顾客流的性质。所以排队论的基本任务是建立顾客流、服务员能力、服务系统效益之间的合理关系。它主要研究三部分：（ 1） 性态问题， 即研究各种排队系统的概率规律性， 主要是研究队

4、长分布、等待时间分布和忙期分布等，包括瞬态和稳态两种情形。（ 2）最优化问题，又分为静态最优和动态最优，前者是指最优设计，后者指现有排队系统的最优运营。（ 3）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。二、排队系统所研究的内容与目的1. 内容： 排队系统的数量指标， 即研究与排队现象有关的几个数量指标的概率规律性。它们是： 队长 k 即在排队系统中，顾客排队等待服务的队列长短。队长中包括正在接受服务的顾客数。队长k 是一个随机变量。在研究排队系统时，首先要确定队长是属于何种分布。 至少要知道它的平均值。 有时候还要知道系统中排队等待服务的顾客数，

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

6、的一个数量指标。逗留时间通常用其平均值Ws 来描述。 忙期和闲期分布从顾客来到空闲的窗口接受服务起，到窗口再次变成空闲为止的这段时间， 即窗口连续服务时间或有顾客的持续时间称为忙期。 它是一个随机变量。这是窗口最关心的数量指标。因为它关系到窗口的工作强度。与忙期相对应的是闲期， 即窗口连续保持空闲的时间长度或无顾客的持续时间称为闲期。值得指出的是，排队系统中忙期和闲期是相互交替出现的。此外，窗口的利用率（即忙期所占的百分比）也是一个重要的数量指标。窗口利用率=忙期/ （忙期+闲期）。一些特殊的排队系统，还有其固有的特殊数量 指标。2 .排队系统的优化问题。在研究了排队系统的一些数量指标的概率规

7、律后， 可以在此基础上进一步研究排队系统的最优化问题。最优化问题一般涉及两种类 型：一类是研究排队系统的最优设计问题，它属于静态最优化问题。例如，电话 网中的中继电路群数目，分组交换网中的存储空间大小等，工厂在制品中间仓库 大小，医院病床数量的多少，机场跑道的数量，车站站台数等等。另一类是研究 排队系统的最优控制问题，它属于动态最优化问题。例如，电话网中的中继电路 群数目的增加与否，工具室是否增加工具分发工人等。3 .研究的目的就是既能在一定程度上满足顾客的需要，又使所需总费用为 最小。三、排队系统的构成在排队系统中主要是要讨论供求之间的关系， 规定凡是要求服务的对象统 称为“顾客”，提供服务

8、的一方统称为“服务窗口或服务员”，顾客与服务窗口构 成一个随机服务系统或称排队系统。一个排队系统能抽象地描述如下：为获得服务的顾客到达服务窗口前，窗口 有空闲便立刻得到服务，若窗口不空闲，则需要等待窗口出现空闲时再接受服务， 服务完后离开窗口，因此排队系统模型如下：服务完毕离去排队系统的基本组成般的排队系统有三个基本组成部分：输入过程、排队规则及服务机构。1 .输入过程：输入过程是指顾客到来时间的规律性，可能有下列不同情况：（ 1） 顾客总体数（顾客源）：顾客的组成可能是有限的，也可能是无限的。（ 2） 顾客到达方式：描述顾客是怎样来到系统的，可能是一个个的到来，也可能是成批的到来。（ 3）

9、顾客流的概率分布 （或顾客到达的时间间隔分布） ： 顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的。顾客流的概率分布一般有定长分布、二项分布、泊松流（最简单流） 、爱尔兰分布等。（ 4） 输入过程可以是平稳的， 即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的。2 . 排队规则：排队规则体现到来的顾客按怎样的方式和顺序接受服务，一般可分为损失制、等待制和混合制。3 1）损失制（消失制）：又称拒绝方式，拒绝系统，截止型。当顾客到达时，所有的服务台均被占用，顾客随即离去。4 2）等待制：又称非拒绝方式。当顾客到达时，所有的服务台均被占用

10、，顾客就排队等待，直到接受完服务才离去。例如出故障的机器排队等待维修就是这种情况。5 3） 混合制： 介于损失制和等待制之间的是混合制， 即既有等待又有损失。有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去。（ 4）排队方式还分为单列、多列和循环队列。3. 服务过程：（ 1）服务机构。主要分为单服务台、多服务台并联（每个服务台同时为不同顾客服务）、多服务台串联（多服务台依次为同一顾客服务）以及混合型。（ 2）服务规则。排队系统的运行性能不仅与统计分布有关，还与系统预先规定的工作方式有关。按服务规则划分，通常有：先到先服务（FCFS）或先入先出（FIFO）。这时

11、按顾客到达的先后，顺序服 务。这是常见的情况。无其它说明时，常按这种方式来分析。后到先服务（LCFS）。 这是不常见情况也可能出现， 如仓库中同品种的货物，出库时常是后进先出。计算机内存提取也有按此方式的。优先制服务。 对各类顾客分别事先赋予不同的优先级， 优先级愈高， 愈提前被服务。在通信网中，这种情况也较为常见。随机服务。 即当窗口有空闲时， 不按照排队序列而随意地指定一个顾客去接受服务。例如，电话交换台接通呼叫的电话就是一例。通信网中一般是顺序服务，即按照顾客到达的先后次序进行服务。有的也采用优先制服务方式。在实际应用中， 排队系统的费用优化是一个关键问题。 在排队系统中， 顾客总是希望

12、尽快接受服务，为了减少顾客逗留时间（降低逗留费用） ，需要提高服务水平 （缩短服务台的服务时间或增加服务台数目） ， 但这样又会增加服务成本，因此优化的目标是使二者的费用总和最小。排队论的应用非常广泛， 它适用于一切服务系统。 尤其在通信系统、 交通系统、计算机、存贮系统、生产管理系统等发面应用得最多。排队论的产生与发展来自实际的需要也必将影响它今后的发展方向。四、排队模型的表示方法目前较为广泛采用的分类表示方法是D. G.肯特尔（D. G. Kendall ）提出的分类方法。 即根据输入过程时间分布、 服务时间分布和窗口数量等特征为主来进行分类，并用字母符号来表示。即X/Y/m （n,N）X

13、表示顾客到达时间间隔分布。Y表示服务时间分布。m 表示窗口或服务员数量（对并列排队系统） 。n 表示截止队长，省略这一项表示 n , 即不拒绝系统。N 表示潜在顾客总数，对于无限潜在顾客源，即 N 时，可省去这一项。表示不同输入过程（顾客流）和服务时间分布的符号有：泊松（ Poisson ）流（或负指数分布） 。两者都具有马尔可夫随机过 程性质。D定长分布。Ekk阶爱尔兰（Erlang）分布。GI 一般相互独立的随机分布。G 一般随机分布。常用概念及符号：系统状态：指一个排队系统中的顾客数（包括正在被服务的顾客数） 。N（t）:在时刻t排队系统中的顾客数，即系统在时刻t的瞬时状态。R：在时刻t

14、系统中恰好有k个顾客的概率。k ：当系统中有k 个顾客时，新来顾客的到达率（单位时间内新顾客的到达数） 。k：当系统中有k个顾客时，整个系统的平均服务率（单位时间内服务完毕离去的顾客数） 。Ls ：平均队长，指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的数学期望。Lq ：平均排队，: 指系统内等待服务的顾客数的数学期望指在系统中排队等待服务的顾客数。Ws ：平均逗留时间，指顾客在系统内逗留时间（包括排队等待的时间和接受服务的时间）的数学期望。Wq ：平均等待时间，指一个顾客在排队系统中排队等待时间的数学期望。Tb ：平均忙期，指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机

15、 构再次空闲止的时间）长度的数学期望。Pn （t） ：在时刻 t 、系统状态为 n 的概率。Pn : 稳态时系统状态为 n 的概率。c ：项目总花费g ：服务设备总投资:平均到达率Cs：服务机构单位时间的费用，为常数 6.67Cw：顾客在系统停留单位时间的费用，为常数 10五、排队系统的常用概率模型排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服务时间不可能是负值，因此，它的分布是非负随机变量的分布。最常 用的分布有泊松分布、确定型分布，指数分布和爱尔朗分布。1 .泊松分布设随机变量 所有可能取的值为0, 1, 2,而取各个值的概率为kPk P k ek=0, 1, 2

16、 k!其中0是常数，则称服从参数为 的泊松分布。其均值为 E()方值为 D()2 .指数分布般地，若随机变量t取具有概率密度函数为f(t)其中0为常数，则称t服从参数为的指数分布，其分布函数F(t)为:tt tF(t) f(t)dt e dt 1 e所以,t 1E (t) tf (t)dt t e dt 一故其均值为：E (t)D(t) E(t2) E(t)2ot2tdt 11dt 22故方差为：D(t);六、生灭过程生灭过程是用来处理输入为最简单流，服务时间为指数分布的这一类最简单 排队模型的方法，即M/M/m(n,N)过程。生灭过程恰好反映了一个排队服务系统 的瞬时状态N(t)将怎样随时间

17、t而变化。定义：设有某个系统,具有状态集 S=0, 1, 2,若系统的状态随时间 t变化的过程N(t)； t 0满足以下条件，则称为一个生灭过程。设在时刻t系统处于状态k的条件下，再经过长为 t (微小增量)的时间， 有： 转移到k 1 (0 k)状态的转移概率为k t+o( t)0 转移到k 1(1 k)状态的转移概率为 k t+o( t) 0 转移到S - k 1, k, k 1状态的概率为o( t) 0其中k 0, k 0均为与t无关的固定常数。若S仅包含有限个元素S=0, 1, 2,，n,也满足以上条件，则称为有 限状态生灭过程。k 1, 2,生灭过程的系统稳定状态方程(简称系统方程)

18、：k Pkk 1Pk 1 k 1 Pk 1 k Pk0P0尸10生灭过程的状态转移图(图中的数字代表系统的状态，箭头代表状态间的转移关系，箭头旁的参数 k,k代表转移率)：生灭过程的状态转移图生灭过程在t时的稳定状态概率：1 k 1 k 20k 1 k k 11Pk-k-20Pok 1, 2,k k 11七、排队系统的主要性能指标1 .排队长度k：简称队长，是某时刻观察系统内滞留的顾客数，包括正在 被服务的顾客。显然，k是非负的离散随机变量，需用概率来描述。通常有以下 三种观察方式，一是随机地取t时刻来观察，相当于服务员或旁观者的随机观察。 在平稳条件下，队长为k的概率记为P另一是顾客到达时刻

19、所观察到的人数， 不包括刚到的顾客，其概率可记为rk ;第三种观察方式是顾客被服务完毕将离开 时所看到的人数，不包括正在离去的顾客，其概率记为dk。以上三种观察结果， 一般Pk、4和dk是不同的；但对于顾客到达规律具有前述的马尔柯夫性的系统 ： 则rk= Pk,因为到达瞬间t此时是纯随机的，与旁观者的随机取t 一样。止匕外， 当每瞬间到达人数或离去人数只能是一人时，则 k = dk；到达时有k个人排队每 次都与离去时有k个人排队相对应。所以满足疏稀性时，只要顾客到达是泊松流， 就有Pk = rk = dk ,但到达规律不是泊松流，就不能得到上述结论。关于队长，主 要是求解Pk、鼠和dk以及计算

20、k的统计平均值Ls,称为平均队长。系统内排队等待的平均顾客数称为平均等待队长, 示，则有下式成立：Ls=Lq+ r其中LskPkk 0n或LskPkk 0Lq（k-m）Pkk m 1n或Lq（k-m）Pkk m 1用Lq表示。正在服务的平均顾客数用r表（非拒绝系统）（拒绝系统）（非拒绝系统）（拒绝系统）2 .等待时间W这是顾客到达至开始被服务这段时间。 W是连续随机变量,其统计平均值Wq称为平均等待时间，是排队系统的另一重要指标。顾客希望Wq 愈小愈好。在通信网中， Wq是信息在网内的平均时延的主要部份。其它时延如 传输时间、处理时间等一般均为常量，而且一般是较小的。3 .服务时间：这是一个顾

21、客被服务的时间，即顾客从开始被服务起到离 开系统的时间问隔。的统计平均值一称为平均服务时间。1 。4 .系统时间S:这是顾客从到达至离开的这段时间， 又称系统内停留时间S的统计平均值称为平均系统逗留时间 Ws,显然有WsWqr1即 Ws Wq 一一个平均到达率为 e的排队系统，在平均的意义上，有e , Ws = Lse - Wq = Lq以上两式称为列德尔（Little ）公式，适用于任何排队系统。5 .系统效率：这可定义为平均窗口占用率。某时刻有 r个窗口被占用,若共有m个窗口，则r/ m就是占用率。显然r/ m是一个随机变量，它的统计平均值就是系统效率，即愈大，服务资源的利用率愈高。八、M

22、/M/1排队1 .基本模型M/M/1排队系统可用下图所示的排队系统模型来表示，这是最简单的排队系统，是分析较复杂排队系统的基础。泊桧输入过程服舞机构m 一个服筠员指数服翦时间分布M/M/1排队系统模型及状态转移图系统的稳态方程为:P1P00Pk1Pk 1()Pk 0系统状态概率为:P0Pk(1) kPkk 1 k 2 ? ? ?0? P 0k k-1 ? ? ?1P0(1-因为M/M/1系统也属于生灭过程，我们也可以直接引用生灭过程的结论来求解Pk,对于M/M/1排队所以2 .M/M/1排队系统的各项性能指标(1)平均队长Ls和平均等待队长LqLskPkk(1k 0k 02(1)(2 223即

23、LsPo是系统空闲的概率，则服务窗口的忙期的概率P忙为:Pt1P01 (1)也即系统忙期的概率P忙就是系统的负荷率Lq Ls P忙 Ls 2)(2)平均等待时间Wq及系统时间Ws当某顾客进入系统时，如果系统内没有顾客就可立即接受服务， 如果系统内 已有k个顾客则需等待，一个顾客接受服务的平均时间为1/ ,故可得顾客平均 等待时间：k 111WqPkkPkLs - k 0k 01_111Ws Wq-当然，从eWs Ls亦可得之。(3)系统效率由于M/M/1系统是单服务员系统，所以系统效率就是系统内有顾客的概率Pk 1 Po k 1(4)忙期和闲期的统计特性闲期(1):指系统中无顾客的持续时间。忙

24、期(Tb):指系统中有顾客的持续时间。Ti, Tb为连续非负随机变量。 闲期Ti的分布：Ti为顾客到达的平均间隔时间，其分布与顾客到达规律相同在M/M/1系统中，顾客到达规律为指数分布，则 Ti的概率密度函数为：fi(t) e1 其均值为：T i -忙期Tb的分布：设在Tb内有n个顾客数，n：离散随机变量，Tb：连续随机变量。对于M/M/1系统，系统的空闲概率：P0 1由平稳性：Po所以TbTb可见，Tb的均值Tb与系统逗留时间Ws相同。 忙期内的顾客平均数n :即忙期内的平均队长对于M/M/1系统，忙期概率P忙=1 Po=Ls所以n = Ls2t：=/1或由1Tb n - M/M/1问题的主

25、要参量均取决于排队强度。为了提高服务资源的利用率，希望 选择得大一些；然而 越大，Wq越大，顾客将等候较久才能被服务，排 队系统的服务质量下降，因此从顾客的观点来看，希望 小一些。止匕外，当 1时，以上公式都将不适用。总之，的取值应兼顾系统效率、等待时间和稳定性诸因素。由此可知，M/M/1系统的主要问题是服务质量和系统效率之间有矛盾 九、M/M/m(n)排队1. M/M/m(n)排队系统的基本模型M/M/m( n)排队系统的模型和状态转移图如下。顾客到达间隔时间服从负指 数分布，顾客到达率为，有m个服务员；每个服务员对一位顾客的服务时间均为负指数分布，每个服务员平均服务率为；采取拒绝方式，系统

26、内最多可有n 个顾客；当系统的顾客数k m时有k个服务员在工作，系统的服务率为k ,当 系统内的顾客数m k n时m个服务员均在工作，系统的服务率为m ，顾客采 用混合排队。窗口未占满时，顾客到达后立即接受服务；窗口占满时，顾客依先 到先服务规则等待，任一窗口有空即被服务。当队长(包括正在被服务的顾客) 长达n时，新来顾客即被拒绝而离去。神输丛J服务机构手也个服务员蘸止M片为内：指颜服务时将分布M/M/m( n)排队系统的系统模型和状态转移图根据系统的状态转移图可得稳态方程为：P1Pok 0(k )PkPki(k1) Pk i0 km(m )PkPk 1mPk 1m knm PnPn 1k n

27、n根据系统的稳态方程进行递推，并由概率的归一性Pk 1,可以求得:k 0PkPo(m)kp P0k!m mm!kPom1(m )kk!0kmm k nk nmmm!m1(m )k (m )m 1 nm1 k o k! m! 1也可以由生灭过程得到同样结论对于M/M/m(n)系统，当m 1, n时变为M/M/1系统，当m=1时为单服务员延时拒绝系统，当m = n时为多服务员即时拒绝系统，当n 时为多服务 员不拒绝系统，说明这些系统都是 M/M/m( n)系统的特例。2. M/M/m (项 排队系统的各项性能指标(1)平均队长Ls和平均等待队长Lq及正在服务的平均顾客数rnLs = k? Pkk

28、0kmm 1 (m ) _ n . mk ?P0+ k?-k 0 k! k m m!?P0kmn m 1n m 21 (m ) (m ) m (m 1) (n 1) n ? ?2k 1(k 1)! m!(1)2其中，P0m 1(m )k(m )m 1 n m 1 ?k 0 k! m! (1)nLq (k m)Pkk m 1kPkk m 1nmPkk m 1m(kPkk 0nmPk)k m 1Ls rnmPkk m 1m所以r kPkk 0r:正在被服务的平均顾客数或占用的平均窗口数(2)顾客平均等待时间wq和系统时间Wsm 1n mn m 1mPom 1 (n m 1) ?(nm) ?VW?q

29、 m!( 1)2Ws Wq -(其中，工为系统的服务时间)(3)系统效率(1Pn)m(1r1、m (1Pn)mm3. M/M/1(n)排队系统性能指标(1)求 Po, Pk当m=1时由式(4.48)和(4.49)可求出系统状态概率为PoPknLskPkk o1 n n 1(n 1) n1n-1顾客平均等待时间Wqn 1 kPkk 11 n n 1(n1) n1 n 11111(2)主要性能指标平均队长Ls系统效率当k=0时系统服务员空闲, 效率n时服务员始终处于繁忙状态，系统nPk1Pok 1顾客被拒绝的概率Pn顾客被拒绝的概率就是系统的顾客损失率，当k = n时顾客即遭到拒绝,所以顾客损失率

30、就是PnPn若 1,且 n1,有 n 11则Pn(1) n(3)对通信网中的非实时性数据、电传等业务，根据时延指标和存贮器的容量， 可以采取一定截止队长的延时拒绝系统，甚至在业务量与存贮器容量满足一定关 系时采取非拒绝系统，这样可提高系统效率并降低信息丢失率。随着半导体技术 的发展，存贮器的容量不断扩大。为通信系统和通信网的发展奠定了基础。4. M/M/m( m)排队系统性能指标当系统中的顾客数等于服务员数时，新到的顾客就遭到拒绝，这种系统就是 M/M/m( m)即时拒绝系统。电话通信网一般采用即时拒绝系统。(1)求 Po、Pk ：系统状态概率PkPo(m )kk!mk(m )k!1Pom0k

31、mk!k!式中a / ，是电话通信网中的流入话务量强度。当顾客到达即时拒绝系统时，如果km,则立即接受服务；如果k = m,就 被拒绝立即离去，因此不需要求顾客等待时间，平均队长Ls也变为平均处于忙状态的服务员数量。(2)主要性能指标平均队长m (m)kLsk(WP0a Pm)k 0k!顾客被拒绝的概率PnP,a m /m !m mak/k!k 0这就是话务理论方面非常著名的爱尔兰呼损公式， 其中a / = S为流入话务量强度，m代表交换机出线的线束容量。Pm也称为呼损率，一般用Pc表示。系统效率m kP1-Pk一m Ls a(1 Pm) kPkPo1k 1 k 2k * 1 k k- 1-,且 1