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