通信网第3章-排队论及其应用

第3章排队论及其应用第3章排队论及其应用通信网规划设计和优化遵循的原则：能够满足各项性能指标要求又节省费用的设计或优化方案。对设计人员的要求：掌握相应的理论基础知识和网络分析的计算方法，以便对通信网的性能进行分析与指标计算，为设计和优化提供理论数据。应用的数学理论：排队论。它起源于最早的电话系统，可应用于很多领域，目前通信网仍是其中一个重要的应用领域。2本章学习要求重点掌握和理解排队论的基本概念、M/M/m(n)排队系统的模型分析方法，了解它们在网络中的实际应用。掌握通信网业务量的基本概念，理解、掌握和运用ErlangB公式和ErlangC公式及其在业务分析中的具体应用；能够运用这些知识分析和计算实际网络的性能指标。掌握随机接入系统的工作原理及其业务分析方法。3第3章排队论及其应用3.1排队论基础3.2M/M/m(n)排队系统3.3通信业务量分析3.4随机接入系统业务量分析43.1排队论基础3.1.1基本概念3.1.2有关的概率模型及最简单流3.1.3排队系统的主要性能指标53.1.1基本概念排队论（QueuingTheory）是一个独立的数学分支，有时也把它归到运筹学中。排队论是专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学，也称为随机服务系统理论或拥塞理论（CongestionTheory）。它是在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优设计和最优控制问题。63.1.1基本概念排队论的起源：排队论起源于20世纪初。当时，美国贝尔（Bell）电话公司发明了自动电话以后，如何合理配置电话线路的数量，以尽可能地减少用户重复呼叫次数问题。1909年，丹麦工程师爱尔兰（A.K.Erlang）发表了具有重要历史地位的论文“概率论和电话交换”，从而求解了上述问题。1917年，A.K.Erlang又提出了有关通信业务的拥塞理论，用统计平衡概念分析了通信业务量问题，形成了概率论的一个新分支。后经C.Palm等人的发展，由近代概率论观点出发进行研究，奠定了话务量理论的数学基础。经过通信、计算机和应用数学三个领域的研究学者的努力，排队论得到了迅速的发展和应用。73.1.1基本概念应用：网络的设计和优化方法；移动通信系统中的切换呼叫的处理方法；随机接入系统的流量分析方法；业务流的数学模型及其排队分析方法等。经典排队论把相继到达“顾客”的到达时间间隔和服务时间都相互独立的排队论内容称为经典（或古典）排队论。经典排队论仍是新的排队论的基础，而且通信领域的许多问题可以用它来解决。83.1.1基本概念1．排队的概念通信网中的排队现象：无形的排队：如打电话有形的排队：如数据分组的传送顾客:把要求服务的一方统称为“顾客”，如电话用户产生的呼叫和待传送的分组信息。服务机构:把提供服务的一方统称为服务机构，如电话交换设备、信息传输网络等。服务窗口或服务员:把服务机构内的具体设施统称为“服务窗口”或“服务员”，如中继线路、信道等。排队系统（随机服务系统）:由要求随机性服务的顾客和服务机构两方面构成的系统称为随机服务系统或排队系统。93.1.1基本概念产生排队的原因：顾客需求的随机性和服务设施的有限性。应用的理论：概率论和随机过程理论研究目的：研究排队系统内服务机构与顾客需求之间的关系，以便合理地设计和控制排队系统，使之既能满足一定的服务质量要求又能节省服务机构的费用。103.1.1基本概念2．排队系统的组成一个排队系统由三个基本部分组成：输入过程排队规则服务机构排队系统排队规则服务机构顾客到达服务完毕离去图3.1排队系统的基本组成113.1.1基本概念（1）输入过程描述顾客按怎样的规律到达排队系统，包括以下三方面：顾客总体数：指顾客的来源（简称顾客源）数量，顾客源数可以是无限的，也可以是有限的。顾客到达方式：描述顾客是怎样到达系统的，是成批（集体）到达（每批数量是随机的还是确定性的）还是单个到达。顾客流的概率分布（或顾客到达的时间间隔分布）：所谓顾客流，就是顾客在随机时刻一个个（一批批）到达排队系统的序列。123.1.1基本概念（2）排队规则排队规则包括：排队系统类型服务规则排队系统类型：排队系统一般分为：拒绝系统非拒绝系统表明服务机构是否允许顾客排队等待服务。133.1.1基本概念拒绝系统：又称拒绝方式、截止型系统。n：系统允许排队的队长（也称截止队长）。m：窗口数。分为两种情况：即时拒绝系统：n=m的系统。此时，顾客到达后或立即被拒绝，或立即被服务，不存在排队等待服务的情况。电话网就是即时拒绝系统。延时拒绝系统：mn的系统。此时容许一定数量的顾客排队等待，当系统内顾客总数达到截止队长时，新来的顾客就被拒绝而离去。带有缓冲存储的数据通信、分组交换等就属于这一类。143.1.1基本概念非拒绝系统：又称非拒绝方式、非截止型系统。系统排队队长无限制，允许顾客排队等待（一般认为顾客数是无限的）。要求该类系统稳定性参数要满足1。即时拒绝系统：也称为立接制系统、损失制系统。延时拒绝系统：也称为混合制系统。延时拒绝系统和非拒绝系统：也称为等待制系统、缓接制系统。153.1.1基本概念服务规则先到先服务(FCFS)或先入先出(FIFO)这是常见的情况。若无其他说明时，常按这种方式来分析。后到先服务(LCFS)优先制服务在通信网中，这种情况也较为常见。随机服务通信网中一般是顺序服务，但有的也采用优先制服务方式。163.1.1基本概念（3）服务机构服务机构包括以下三方面内容。窗口或服务员数量当m=1时，称为单窗口排队系统。当m1时，称为多窗口排队系统。服务方式及排队方式服务时间分布173.1.1基本概念服务方式及排队方式服务方式是指在某一时刻系统内接受相同服务的顾客数，即是单个顾客接受服务（串列服务方式）还是成批顾客同时接受服务（并列服务方式）。串列服务方式：即m个窗口的串列排队系统。此时，m个窗口服务的内容互不相同，某一时刻只能有一个顾客接受其中一个窗口的单项服务，每个顾客要依次经过这m个窗口接受全部的服务。并列服务方式：即m个窗口的并列排队系统。此时，m个窗口服务的内容相同，系统一次可以同时服务m个顾客。183.1.1基本概念排队方式：包括混合排队和分别排队两种方式混合排队方式：顾客排成一个队列，接受任意一个空闲窗口的服务。分别排队方式：顾客排成m个队列，同时分别接受m个窗口的相同服务。当m=1时，在该系统中，如果允许排队，顾客则只能排成一列队列接受服务。当m1时，在该系统中，如果允许排队，则有混合排队和分别排队两种排队方式。排队方式的选择取决于两种服务方式。193.1.1基本概念图3.2服务方式与排队方式203.1.1基本概念服务时间分布服务时间和顾客到达时间一样，多数情况下是随机型的。要知道它的经验分布或概率分布。一般来说，服务时间的概率分布有定长分布、指数分布、Erlang分布等。21：在时刻t系统中有k个顾客的概率。:在时刻t排队系统中的顾客数，即系统在时刻t的瞬时状态。，可写成N。3.1.1基本概念3.排队系统中常用的几个定义系统状态：指一个排队系统中的顾客数（包括正在被服务的顾客数）。)(tPk)(tN)(tPk稳定状态：当一个排队系统运转一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于稳定状态。排队论中主要研究系统处于稳定状态下的工作情况。稳定状态时工作情况与时刻t无关，这时可写成kP)(tN223.1.1基本概念4.排队系统的三个基本参数任何排队系统都有三个基本参数m、、，称为排队模型的三要素。m参数称为窗口数或服务员数目，表征系统的资源量。它表示系统中有多少服务设施可同时向顾客提供服务。参数顾客到达率或系统到达率，即单位时间内到达系统的平均顾客数。其单位为个/时间或份/时间。反映了顾客到达系统的快慢程度，也反映了需要服务的一方对提供服务的一方的要求。越大，说明系统的负载越重。的倒数称为平均到达时间间隔，即T/1T233.1.1基本概念在无限顾客源的情况下，顾客的到达按集体到达方式考虑，式（3.1）中的系统到达率为常数。系统的有效到达率e：实际能够进入系统并接受服务的到达率，即单位时间内进入系统的平均顾客数（3.1）nP为阻塞概率（或拒绝概率）。对于非拒绝系统，0nPe则)1(neP243.1.1基本概念在有限顾客源的情况下，顾客的到达按单个到达方式考虑。设每个顾客的到达率λ0相同，λ0是有限顾客源中每个顾客在单位时间内到达系统的平均数。N：顾客源总数；Ls：系统的平均队长；（N-Ls)：系统外的顾客平均数。此时系统的有效到达率为（3.2）0)(seLN25参数:是一个服务员（或窗口）的服务速率，即单位时间内由一个服务员（或窗口）进行服务所离开系统的平均顾客数。：当系统中有k个顾客时，整个系统的平均服务率（单位时间内服务完毕离去的平均顾客数），即k状态的系统服务率，则有3.1.1基本概念k0)00kN-kkk有限顾客源，（为常数，无限顾客源，（3.3）：当系统中有k个顾客时，新到顾客的到达率（单位时间内新顾客的到达数）或系统到达率，即k状态（系统中有k个顾客时）的系统到达率，则有kmkmmmkmkmk,1,11（3.4）263.1.1基本概念对系统稳定性的影响：若1，即m时，说明平均到达系统的顾客数小于平均离开系统的顾客数。这时系统是稳定的，可以采取非拒绝方式或拒绝方式。若1，即m时，说明平均到达系统的顾客数多于平均离开系统的顾客数。必须采用拒绝方式，人为地限制系统内的顾客数量，保证系统的稳定性。：的倒数1/，是单个窗口对顾客的平均服务时间，也是一个呼叫的平均持续时间。/1：为排队强度，又称稳定性参数。)/(m(3.5)273.1.1基本概念5.排队系统分类的表示方法目前较为广泛采用的分类表示方法是D.G.Kendall提出的分类方法：X/Y/m（n，N)X：顾客到达时间间隔分布Y：服务时间分布m：窗口或服务员数目（此处特指并列排队系统）n：截止队长，省略这一项表示n，即为非拒绝系统N：表示潜在的顾客总数，对于潜在的无限顾客源，即N时，可省去这一项283.1.1基本概念表示不同输入过程（顾客流）X和服务时间分布Y的符号有：Ｍ：泊松分布（或指数分布），两者都具有马尔可夫随机过程性质.Ｄ：定长分布Ek：k阶Erlang分布ＧI：一般相互独立的随机分布Ｇ：一般随机分布M/M／1系统：指顾客流为泊松流、服务时间为指数分布、单窗口排队系统。Ｍ/Ｄ/m系统：指顾客流为泊松流、服务时间为定长分布、有m个窗口的排队系统。一般如没有特别说明，则认为顾客总体数是无限源、属于非拒绝方式的排队系统。293.1排队论基础3.1.1基本概念3.1.2有关的概率模型及最简单流3.1.3排队系统的主要性能指标303.1.2有关的概率模型及最简单流1.排队系统中常用的概率模型（1）泊松分布设随机变量X所有可能取的值为0，1，2，…，而取各个值的概率为k=0，1，2…(3.6)其中0是常数，则称X服从参数为的泊松分布。其均值为(3.7)方差为(3.8）ekkΧPPkk!}{)(ΧE)(ΧD313.1.2有关的概率模型及最简单流（2）指数分布一般，若随机变量t取具有概率密度函数为(3.9)其中0为常数，则称t服从参数为的指数分布，其分布函数F(t)为其均值为(3.11)方差为(3.12）ttttedtedttftF1)()((3.10）0()00tetftt0001)(ttetFt1)(tE21)(tD323.1.2有关的概率模型及最简单流2．最简单流随机事件流：通常把随机时刻出现的事件组成的序列称为随机事件流，例如用N(t