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

《排队论及其在通信领域中的应用.docx》由会员分享，可在线阅读，更多相关《排队论及其在通信领域中的应用.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上排队论及其在通信领域中的应用信息与通信工程学院班姓名：李红豆学号：班内序号：26指导老师：史悦一、 摘要排队论是为了系统的性态、系统的优化和，根据资料的合理建立模型，其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队是一种司空见惯的现象，因此排队论可以用来解决许多现实问题。利用排队论的知识可以来解决通信服务中的排队论问题。应用排队论一方面可以有效地解决通信服务系统中信道资源的分配问题；另一方面通过系统优化，找出用户和服务系统两者之间的平衡点，既减少排队等待时间，又不浪费信号资源，从而达到最优设计的完成。二、 关键字排队论、最简单流、排队系统、通信三、 引言

2、排队论又称随机服务系统, 主要解决与随机到来、排队服务现象有关的应用问题。是研究系统由于随机因素的干扰而出现排队(或拥塞) 现象的规律的一门学科, 排队论的创始人Erlang 是为了解决电话交换机容量的设计问题而提出排队论。它适用于一切服务系统,包括通信系统、计算机系统等。可以说, 凡是出现拥塞现象的系统, 都属于随机服务系统。随着电子计算机的不断发展和更新, 通信网的建立和完善, 信息科学及控制理论的蓬勃发展均涉及到最优设计与最佳服务问题, 从而使排队论理论与应用得到发展。四、 正文1、 排队论概述：1.1基本概念及有关概率模型简述：1.1.1排队论基本概念及起源：排队论是一个独立的数学分支

3、有时也把它归到运筹学中。排队论是专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学也称为随机服务系统理论或拥塞理论。它专于研究各种排队系统概率规律性的基础上解决有关排队系统的最优设计和最优控制问题。排队论起源于20世纪初。当时美国贝尔Bell电话公司发明了自动电话以后如何合理配臵电话线路的数量以尽可能地减少用户重复呼叫次数问题出现了。 1909年丹麦工程师爱尔兰A.K.Erlang发表了具有重要历史地位的论文“概率论和电话交换”从而求解了上述问题。 1917年A.K.Erlang又提出了有关通信业务的拥塞理论用统计平衡概念分析了通信业务量问题形成了概率论的一个新分支。后经C.Pal

4、m等人的发展由近代概率论观点出发进行研究奠定了话务量理论的数学基础。排队论广泛应用在网络的设计和优化方法移动通信系统中的切换呼叫的处理方法随机接入系统的流量分析方法ATM业务流的数学模型及其排队分析方法等。1.1.2排队论系统的组成一个排队系统由三个基本部分组成，输入过程、排队规则和服务机构。图1 排队系统的基本组成输入过程是描述顾客按怎样的规律到达排队系统的过程。包括以下三方面：（1）顾客总体数，指顾客的来源（简称顾客源）数量，顾客源数可以是无限的也可以是有限的；（2）顾客到达方式，描述顾客是怎样到达系统，是成批（集体）到达（每批数量是随机的还是确定性的）还是单个到达；（3）顾客流的概率分布

5、（或顾客到达的时间间隔分布），所谓顾客流，就是顾客在随机时刻一个个（一批批）到达排队系统的序列。排队规则包括排队系统类型和服务规则两方面内容。其中排队系统类型一般分为拒绝系统和非拒绝系统，表明服务机构是否允许顾客排队等待服务。拒绝系统又称拒绝方式、截止型系统。若用n表示系统允许排队的队长（也称截止队长），用m表示窗口数。当系统L满足n=m时，该系统为即时拒绝系统，也称为立接制系统、损失制系统。此时顾客到达后或立即被拒绝或立即被服务，不存在排队等待服务的情况。电话网就是即时拒绝系统。当系统L满足m 0是常数,则称X 服从参数为的泊松分布。2、指数分布一般，若随机变量t 取具有概率密度函数为f(t

6、)=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）时间内出现的顾客数只与时间长度t

7、有关而与起点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个顾客在等待或正在处理的概率，或是总的C条信道中有k条

8、信道被占用概率。泊松过程的顾客到达时间间隔分布为顾客到达的时间间隔小于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所以说，一个随机过程为“泊松到达过程”或“到达时间间隔为指数分布”实际上是一回事。一般来说大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。大量研究表明将电话呼叫当做最简单流处理得到的分析结果是正确的。1.

9、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)排队系统的模型（混合排队方式）中，顾客到达为泊松流，到达率为

12、。同时有m个窗口，每个窗口对一位顾客的服务时间为指数分布，每个窗口的平均服务率为。顾客采用混合排队方式。队列长度为n，同时采取拒绝方式，即系统内最多可有n个顾客。图3 M/M/m(n) 排队系统的系统模型和状态转移图2、 排队论在通信领域基于通信业务量的简单应用分析：排队论作为概率论的一个重要分支，在学术界各个领域都发挥着重要作用，而在通信领域，排队论的价值得到了空前的发掘，现就排队论在通信业务量的应用做出简要介绍以及相关讨论。2.1通信业务量基本理论设计和建设一个通信网及所配臵的设备是以全网业务量为主要依据的。进入通信网送到通信设备和线路上进行传输的语音、数据等输入信息统称为通信呼叫，简称呼

13、叫，在排队论中对应顾客，呼叫长度（呼叫持续时间）对应服务时间。网中的呼叫源即是网内的所有用户。在网中传送的信息量称为通信业务量，也称为流量。信道数C或线路容量在排队论中对应窗口数m，而不同类型的呼叫事件也分别对应了不同的典型的排队模型。2.1.1呼叫的发生过程通常情况下，满足以下三个条件的呼叫条件称为称为纯随机呼叫：呼叫源无限多，即能够发生呼叫的用户数很大；处于占线状态（占用信道）的呼叫源数目相对少可不考虑；用户（呼叫）之间相互独立；呼叫的发生和交换网（或信道）的阻塞状态可分别考虑。若同时满足最简单流条件，即可表示为M/M/m(n)排队系统模型。实际通信网中的顾客（用户）数总是有限的，所以不存

14、在严格的纯随机呼叫，而多属于准随机呼叫。准随机呼叫满足以下两个条件：呼叫源有限且用户之间仍相互独立。若同时满足最简单流条件，即可表示为M/M/m(n，N )排队系统模型。当N 很大时(N k)或用户数非常多时准随机呼叫可近似当做纯随机呼叫处理。N越大这种近似越合理。实际通信网中往往会遇到多个顾客（用户）同时使用的状况，这就需要引入呼叫合成发生的情况来做分析。设有两个相互独立的呼叫源，各自按呼叫发生率1、2呈泊松分布，其呼叫发生概率分别为Pk1t=(1t)kk!e-1tPk2t=(2t)kk!e-2t则合成呼叫发生数为k的概率为Pk t=1t+2tkk!e-(1+2)t所以说两个分别按1、2的泊

15、松分布的合成等于呼叫发生率为1+2的泊松分布。易推得若有个各自任意速率,为1、2、3、m的独立泊松流，则复合流本身也为泊松过程其速率参数为=i=1mi。2.1.2业务量和呼叫量业务量是在指定观察时间内各个线路（或信道）可能被占用的时间之和即占用的总时间。这些时间可以是重叠的或不重叠的。若某线路有m条信道，第i条信道被占用Qi秒，则m条信道或该线路上的业务量Q为 Q=i=1mQr 。业务量的量纲是时间。若一个信道代表一个电话话路则业务量或话务量的单位是秒/话路。这里的Q具不仅反映了信息源所发生的用户需求业务量也同时反映了通过m条信道的实际的通信业务量。业务量的强度通常称为呼叫量。它可定义为线路（

16、或信道）可能占用的时间与观察时间之比，即呼叫量为a=业务量观察时间=Qr（erl），a是没有量纲的，通常使用“小时呼”或“爱尔兰（erl）”表示它的单位。通常取T为一小时。一个erl表示一小时一个完全被占用的信道的呼叫量，即单位小时或单位分钟的呼叫时长。根据定义呼叫量也可表示为a=t。电话网中的业务量称为话务量。话务量用来反映电话用户的通话频繁程度和通话时间的长短。表示为Y=st，其中表示单位时间内的呼叫次数，即呼叫强度（次/h）；对应排队论中的系统到达率。S表示一次呼叫的平均占用时长（h/次）；对应平均服务时间。T表示计算话务量的时间范围（h）。话务量含义反映了占用设备的程度，同时也反映了用

17、户对电话网设备的需求。时延是指消息进入网内后直到被利用完毕所需的时间。包括等待时间、服务时间、处理时间、传输时延。其中传输时延一般是较小的，处理时间与消息内容有关，一般可从技术上缩短所占的份额不一定太大而且往往是恒定的。时延的主要部分是系统时间即等待时间和服务时间。2.1.3服务等级及服务系统业务量理论利用Erlang B公式或C公式，即业务量、中继线或信道数量和阻塞概率或呼叫等待概率之间的关系式在一定的服务等级上在已知业务量预测值的条件下确定中继电路数、长途电路数或求移动网中核心网的电路数、无线网的信道配臵等。目的是使固定数量的中继线路或信道可为一个数量更大的、随机的用户群体服务。服务等级表

18、示为GoS（Grade of Service）是表示拥塞的量。定义为呼叫阻塞概率（也称呼叫阻塞率），或呼叫延迟时间大于某一特定排队时间的概率。在实际的通信网中多为截止型的排队系统。当系统处于拒绝状态时系统是阻塞的将出现呼损。按处理阻塞呼叫（未接续的呼叫）的方式不同，通信网中通常用到两种服务系统：阻塞呼叫清除系统和阻塞呼叫延迟系统。阻塞呼叫清除系统不对阻塞呼叫请求进行排队即放弃阻塞呼叫的接续。这种系统又叫做阻塞系统或损失制系统、立接制系统。 系统模型为M/M/m（m）或M/M/m（m，N），基本的阻塞呼叫清除系统为 M/M/m（m）。而阻塞呼叫延迟系统系统模型为M/M/m（n）、M/M/m基本的

19、阻塞呼叫延迟系统为 M/M/m（n）。2.2举例分析蜂窝移动网中的呼叫处理排队方案蜂窝移动通信是采用蜂窝无线组网方式，在终端和网络设备之间通过无线通道连接起来，进而实现用户在活动中可相互通信。其主要特征是终端的移动性，并具有越区切换和跨本地网自动漫游功能。蜂窝移动通信业务是指经过由基站子系统和移动交换子系统等设备组成蜂窝移动通信网提供的话音、数据、视频图像等业务。其中在GSM网络呼叫切换处理中常用三个典型的越区切换方案有无优先级方案、切换呼叫排队方案、信道预留方案。先分析如下：2.2.1无优先级方案系统模型表示为处理新呼叫和切换呼叫的排队模型M/M/C（C）。对这种这种方案来说小区中所有的C个

20、信道均被新呼叫和越区切换呼叫所共享。基站处理以上两种呼叫的方法完全相同。任意一种呼叫，如在其到达的时刻基站内没有空闲信道那么到达的呼叫都将被系统阻塞。2.2.2切换呼叫排队方案系统模型表示为处理新呼叫的排队模型M/M/C（C），或处理切换呼叫的排队模型M/M/C（N）。就这种方案而言，小区中所有的C个信道同样被新呼叫和越区切换呼叫所共享。当上述两种呼叫同时到达并且小区中的信道全被占用时将对切换呼叫进行排队并阻塞新呼叫。如果在最大排队时间内无空闲信道可用就将阻塞切换呼叫。2.2.3信道预留方案系统模型表示为处理新呼叫的排队模型M/M/Sc（Sc）或处理切换呼叫的排队模型M/M/C（C）。系统专门为越区切换呼叫预留了部分信道。预留信道数为C-Sc ，剩余信道Sc则由新呼叫和越区切换呼叫所共享，当新呼叫到达小区时，如果基站中剩余的空闲信道数小于或等于预留信道数，就阻塞该呼叫请求。当切换呼叫请求到达小区时，如果基站中没有空闲信道就将其阻塞。 有上述分析可知预留信道方式是降低切换失败概率的一种有效方法，但它影响了信道利用率。切换失败概率的降低都是以新呼叫阻塞概率的升高为代价的。提高信道利用率和降低呼损可采取四个措施，如大群化效应、延迟效应、综合效应、迂回效应等，在此不再赘述。专心-专注-专业