排队论及其在通信领域中的应用

排队论及其在通信领域中的应用信息与通信工程学院2010211112班姓名：李红豆学号：10210367班内序号：26指导老师：史悦1一、摘要排队论是为了系统的性态、系统的优化和统计推断，根据资料的合理建立模型，其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队是一种司空见惯的现象，因此排队论可以用来解决许多现实问题。利用排队论的知识可以来解决通信服务中的排队论问题。应用排队论一方面可以有效地解决通信服务系统中信道资源的分配问题；另一方面通过系统优化，找出用户和服务系统两者之间的平衡点，既减少排队等待时间，又不浪费信号资源，从而达到最优设计的完成。二、关键字排队论、最简单流、排队系统、通信三、引言排队论又称随机服务系统,主要解决与随机到来、排队服务现象有关的应用问题。是研究系统由于随机因素的干扰而出现排队(或拥塞)现象的规律的一门学科,排队论的创始人Erlang是为了解决电话交换机容量的设计问题而提出排队论。它适用于一切服务系统,包括通信系统、计算机系统等。可以说,凡是出现拥塞现象的系统,都属于随机服务系统。随着电子计算机的不断发展和更新,通信网的建立和完善,信息科学及控制理论的蓬勃发展均涉及到最优设计与最佳服务问题,从而使排队论理论与应用得到发展。四、正文1、排队论概述：1.1基本概念及有关概率模型简述：1.1.1排队论基本概念及起源：排队论是一个独立的数学分支有时也把它归到运筹学中。排队论是专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学也称为随机服务系统理论或拥塞理论。它专于研究各种排队系统概率规律性的基础上解决有关排队系统的最优设计和最优控制问题。排队论起源于20世纪初。当时美国贝尔Bell电话公司发明了自动电话以后如何合理配臵电话线路的数量以尽可能地减少用户重复呼叫次数问题出现了。1909年丹麦工程师爱尔兰A.K.Erlang发表了具有重要历史地位的论文“概率论和电话交换”从而求解了上述问题。1917年A.K.Erlang又提出了有关通信业务的拥塞理论用统计平衡概念分析了通信业务量问题形成了概率论的一个新分支。后经C.Palm等人的发展由近代概率论观点出发进行研究奠定了话务量理论的数学基础。排队论广泛应用在网络的设计和优化方法移动通信系统中的切换呼叫的处理方法随机接入系统的流量分析方法ATM业务流的数学模型及其排队分析方法等。1.1.2排队论系统的组成一个排队系统由三个基本部分组成，输入过程、排队规则和服务机构。2图1排队系统的基本组成输入过程是描述顾客按怎样的规律到达排队系统的过程。包括以下三方面：（1）顾客总体数，指顾客的来源（简称顾客源）数量，顾客源数可以是无限的也可以是有限的；（2）顾客到达方式，描述顾客是怎样到达系统，是成批（集体）到达（每批数量是随机的还是确定性的）还是单个到达；（3）顾客流的概率分布（或顾客到达的时间间隔分布），所谓顾客流，就是顾客在随机时刻一个个（一批批）到达排队系统的序列。排队规则包括排队系统类型和服务规则两方面内容。其中排队系统类型一般分为拒绝系统和非拒绝系统，表明服务机构是否允许顾客排队等待服务。拒绝系统又称拒绝方式、截止型系统。若用n表示系统允许排队的队长（也称截止队长），用m表示窗口数。当系统L满足n=m时，该系统为即时拒绝系统，也称为立接制系统、损失制系统。此时顾客到达后或立即被拒绝或立即被服务，不存在排队等待服务的情况。电话网就是即时拒绝系统。当系统L满足mn时，该系统为延时拒绝系统，也称为混合制系统。此时容许一定数量的顾客排队等待，当系统内顾客总数达到截止队长时，新来的顾客就被拒绝而离去。带有缓冲存储的数据通信、分组交换等就属于这一类。非拒绝系统又称非拒绝方式、非截止型系统。系统排队队长无限制，允许顾客排队等待一般认为顾客数是无限的。例如公用电话。延时拒绝系统和非拒绝系统也称为等待制系统、缓接制系统。服务规则常见的有先到先服务(FCFS)和先入先出(FIFO)，同时也有后到先服务(LCFS)，在通信网中优先制服务也较为常见，同时在通信网中一般是顺序服务但有的也采用随机服务方式。服务机构包括窗口或服务员数量（当m=1时，称为单窗口排队系统。当m﹥1时，称为多窗口排队系统）、服务方式及排队方式和服务时间分布。服务方式是指在某一时刻系统内接受相同服务的顾客数。分为单个顾客接受服务（串列服务方式）和成批顾客同时接受服务（并列服务方式）。其中串列服务方式是m个窗口的串列排队系统。此时m个窗口服务的内容互不相同，某一时刻只能有一个顾客接受其中一个窗口的单项服务，每个顾客要依次经过这m个窗接受全部的服务。而并列服务方式是m个窗口的并列排队系统。此时m个窗口服务的内容相同，系统一次可以同时服务m个顾客。排队方式包括混合排队和分别排队两种方式。混合排队方式为顾客排成一个队列接受任意一空闲窗口的服务。分别排队方式为顾客排成m个队列同时分别接受m个窗口的相同服务。当m=1时在该系统中如果允许排队，则顾客只能排成一列队列接受服务。当m﹥1时在该系统中如果允许排队则有混合排队和分别排队两种排队方式。排队方式的选择取决于两种服务方式。服务时间和顾客到达时间一样，多数情况下是随机型的。要知道它的经验3Pk=P{X=k}=𝑘!𝑒{∫‒∞𝑓(𝑡)𝑑𝑡∫0𝜆𝑒‒𝜆𝑡𝑑𝑡1分布或概率分布。一般说来服务时间的概率分布有定长分布、指数分布、Erlang分布等。1.1.3排队系统的分类表示目前较为广泛采用的分类表示方法是D.G.Kendall提出的分类方法。表示为X/Y/m（n，N）。其中X表示顾客到达时间间隔分布，Y指服务时间分布m指窗口或服务员数目（此处特指并列排队系统），n指截止队长省略这一项表示n→∞，即为非拒绝系统，N指表示潜在的顾客总数对于潜在的无限顾客源即Nn→∞，时可省去这一项。表示不同输入过程（顾客流）和服务时间分布的符号有：M表示泊松（Poisson）流或指数分布。两者都具有马尔可夫随机过程性质。D表示定长分布Ek表示k阶Erlang分布。Gi表示一般相互独立的随机分布。G表示一般随机分布。例如M/M/1系统指顾客流为泊松流、服务时间为指数分布的单窗口排队系统。M/D/m系统指顾客流为泊松流、服务时间为定长分布、有m个窗口的排队系统。1.2有关的概率模型及最简单流1.2.1排队系统中常用的概率模型1、泊松分布设随机变量X所有可能取的值为0，1，2…而取各个值的概率为𝜆𝑘‒𝜆(k=0，1，2…)其中λ0是常数,则称X服从参数为λ的泊松分布。2、指数分布一般，若随机变量t取具有概率密度函数为𝜆𝑒‒𝜆𝑡𝑡0f(t)=0𝑡≤0其中λ0为常数,则称t服从参数为λ的指数分布,其分布函数F(t)为F(t)=𝑡𝑡==1-𝑒‒𝜆𝑡F(t)={0-𝑒‒𝜆𝑡𝑡0𝑡≤01.2.2最简单流通常把随机时刻出现的事件组成的序列称为随机事件流，例如用N(t)表示（0，t）时间内要求服务的顾客人数就是一个随机事件流。最简单流定义为，如果一个事件流{N(t),0}，这里以输入流为例，满足平稳性、无后效性和疏稀性三个条件则称该输入为最简单流。平稳性指在时间间隔t内到达k个顾客的概率只与t有关而与这间隔的起始时刻无关。即以任何时刻t0为起点（t0,t0+t）时间内出现的顾客数只与时间长度t有关而与起点t0无关。无后效性是指顾客到达时刻相互独立，即顾客各自独立地随机到达系统。此假设使顾客数k的随机过程具有马尔柯夫性。即在（t0,t0+t）时间内出现k个顾客与t0以前到达的顾客数无关。稀疏性是指在无限小时间间隔Δt内到达两个或两个以上顾客的概率可认为是零且在有限时间区间内到达的顾客数是有限的。即在充分小的时间区间Δt内发生两个或两个以上事件的概率是比Δt高阶的无穷小量。4Pk（t）=𝑘!𝑒P0（t）=0!𝑒𝑇在上述三个条件下，可以推出(𝜆𝑡)𝑘‒𝜆𝑡,k=1,2,3…这里的Pk（t）是在时间t内有k个顾客到达的概率，或是一个排队系统中在时间t内有k个顾客在等待或正在处理的概率，或是总的C条信道中有k条信道被占用概率。泊松过程的顾客到达时间间隔分布为顾客到达的时间间隔小于t的概率，即t内有顾客的概率分布。两相邻顾客到达的时间间隔是一连续型随机变量，用T表示。在时间内没有顾客到达的概率为(𝜆𝑡)0‒𝜆𝑡=𝑒‒𝜆𝑡则T的分布函数为F（t）=P(T≤𝑡)=1-P(Tt)=1-𝑒‒𝜆𝑡其概率密度函数为𝑓𝑇(𝑡)=𝑑𝐹𝑑𝑡(𝑡)=𝜆𝑒‒𝜆𝑡所以说，一个随机过程为“泊松到达过程”或“到达时间间隔为指数分布”实际上是一回事。一般来说大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。大量研究表明将电话呼叫当做最简单流处理得到的分析结果是正确的。1.3排队系统的主要性能指标最优化问题一般涉及排队系统的最优设计(静态优化),例如固话网中的中继电路群数目的确定,分组交换网中的存储空间容量的配等等。还涉及到排队系统的最优控制（动态优化），例如固话网中的中继电路群数目的增加与否、无线信道中的信道分配策略等。排队系统的性能指标描述了排队的概率规律性。通过计算一些性能指标，研究排队系统的最优化问题。现列举指标如下：排队长度，简称队长，是某观察时刻系统内滞留的顾客数。包括正在被服务的顾客。k是非负的离散型随机变量。通常用来描述队长k的指标有两个：k的概率分布与k的统计平均值Ls和平均等待队长Lq。知道了队长分布，就可以确定队长超过某个数量的概率从而能为设计排队空间的大小提供依据。等待时间，从顾客到达排队系统的时刻算起到它开始接受服务的时刻为止的这段时间为等待时间。平均等待时间Wq是等待时间的统计平均值。系统逗留时间是从顾客到达系统时刻算起到它接受服务完毕离开系统时刻为止的这段时间。平均系统逗留时间（或系统时间）Ws是系统逗留时间的统计平均值。系统效率：设某时刻有r个窗口被占用，若共有m个窗口则r/m就是窗口𝑟占用率。它的统计平均值为平均窗口占用率就是系统效率即𝜂=𝑚。空闲概率P0和拒绝概率Pn：P0为系统内无顾客的情况，即系统空闲状态概率。通过，可知系统的忙闲情况。拒绝系统Pn（或Pc）为系统内顾客已满、拒绝新到顾客进入系统的状态概率，也称为阻塞概率（或损失概率）。1.4两类重要排队系统模型的简要介绍及分析1.4.1M/M/1排队系统最简单的排队系统模型是M/M/1单窗口非拒绝系统。该系统的顾客到达为泊松流，设到达率为λ；服务时间为指数分布，设平均服务率为μ。5图2M/M/1排队系统的状态转移图1.4.2M/M/m/(n)排队系统解决M/M/1系统的服务质量与系统效率之间的矛盾必须压缩排队长度、减小等待时间。通常可采用两种措施，增加窗口数和截止排队长度。增加窗口数可提高总服务率但意味着投资加大。而截止排队长度则通过降低系统质量来换取系统效率和稳定性。M/M/m(n)排队系统的模型（混合排队方式）中，顾客到达为泊松流，到达率为λ。同时有m个窗口，每个窗口对一位顾客的服务时间为指数分布，每个窗口的平均服务率为μ。顾客采用混合排队方式。队列长度为n，同时采取拒绝方式，即系统内最多可有n个顾客。图3M/M/m(n)排队系统的系统模型和状态转移图2、排队论在通信领域基于通信业务量的简单应用分析：排队论作为概率论的一个重要分支，在学术界各个领域都发挥着重要作用，而在通信领域，排队论的价值得到了空前的发掘，现就排队论在通信业务量的应用做出简要介绍以及相关讨论。2.1通信业务量基本理论设计和建设一个通信网及所配臵的设备是以全网业务量为主要依据的。进入通信网送到通信设备和线路上进行传输的语音、数据等输入信息统称为通信呼叫，简称呼叫，在排队论中对应顾客，呼叫长度（呼叫持续时间）对应服务时间。网中的呼叫源即是网内的所有用户。在网中传送的信息量称为通信业务量，也称为流量。信道数C或线路容量在排队论中对应窗口数m，而不同类型的呼叫事件也分别对应了不同的典型的