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

排队论及其在通信领域中的应用信息与通信工程学院2010211112班姓名：李红豆学号：10210367班内序号：26指导老师：史悦摘要排队论是为了系统的性态、系统的优化和\o"统计推断"统计推断，根据资料的合理建立模型，其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队是一种司空见惯的现象，因此排队论可以用来解决许多现实问题。利用排队论的知识可以来解决通信服务中的排队论问题。应用排队论一方面可以有效地解决通信服务系统中信道资源的分配问题；另一方面通过系统优化，找出用户和服务系统两者之间的平衡点，既减少排队等待时间，又不浪费信号资源，从而达到最优设计的完成。关键字排队论、最简单流、排队系统、通信引言排队论又称随机服务系统,主要解决与随机到来、排队服务现象有关的应用问题。是研究系统由于随机因素的干扰而出现排队(或拥塞)现象的规律的一门学科,排队论的创始人Erlang是为了解决电话交换机容量的设计问题而提出排队论。它适用于一切服务系统,包括通信系统、计算机系统等。可以说,凡是出现拥塞现象的系统,都属于随机服务系统。随着电子计算机的不断发展和更新,通信网的建立和完善,信息科学及控制理论的蓬勃发展均涉及到最优设计与最佳服务问题,从而使排队论理论与应用得到发展。正文排队论概述：1.1基本概念及有关概率模型简述：1.1.1排队论基本概念及起源：排队论是一个独立的数学分支有时也把它归到运筹学中。排队论是专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学也称为随机服务系统理论或拥塞理论。它专于研究各种排队系统概率规律性的基础上解决有关排队系统的最优设计和最优控制问题。排队论起源于20世纪初。当时美国贝尔Bell电话公司发明了自动电话以后如何合理配臵电话线路的数量以尽可能地减少用户重复呼叫次数问题出现了。1909年丹麦工程师爱尔兰A.K.Erlang发表了具有重要历史地位的论文“概率论和电话交换”从而求解了上述问题。1917年A.K.Erlang又提出了有关通信业务的拥塞理论用统计平衡概念分析了通信业务量问题形成了概率论的一个新分支。后经C.Palm等人的发展由近代概率论观点出发进行研究奠定了话务量理论的数学基础。排队论广泛应用在网络的设计和优化方法移动通信系统中的切换呼叫的处理方法随机接入系统的流量分析方法ATM业务流的数学模型及其排队分析方法等。1.1.2排队论系统的组成一个排队系统由三个基本部分组成，输入过程、排队规则和服务机构。Pk（t）=(λt)k这里的Pk（t）是在时间t内有k个顾客到达的概率，或是一个排队系统中在时间t内有k个顾客在等待或正在处理的概率，或是总的C条信道中有k条信道被占用概率。泊松过程的顾客到达时间间隔分布为顾客到达的时间间隔小于t的概率，即t内有顾客的概率分布。两相邻顾客到达的时间间隔是一连续型随机变量，用T表示。在时间内没有顾客到达的概率为P0（t）=(λt)00!则T的分布函数为F（t）=P(T≤t)=1-P(T>t)=1-e其概率密度函数为fT所以说，一个随机过程为“泊松到达过程”或“到达时间间隔为指数分布”实际上是一回事。一般来说大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。大量研究表明将电话呼叫当做最简单流处理得到的分析结果是正确的。1.3排队系统的主要性能指标最优化问题一般涉及排队系统的最优设计(静态优化),例如固话网中的中继电路群数目的确定,分组交换网中的存储空间容量的配等等。还涉及到排队系统的最优控制（动态优化），例如固话网中的中继电路群数目的增加与否、无线信道中的信道分配策略等。排队系统的性能指标描述了排队的概率规律性。通过计算一些性能指标，研究排队系统的最优化问题。现列举指标如下：排队长度，简称队长，是某观察时刻系统内滞留的顾客数。包括正在被服务的顾客。k是非负的离散型随机变量。通常用来描述队长k的指标有两个：k的概率分布与k的统计平均值Ls和平均等待队长Lq。知道了队长分布，就可以确定队长超过某个数量的概率从而能为设计排队空间的大小提供依据。等待时间，从顾客到达排队系统的时刻算起到它开始接受服务的时刻为止的这段时间为等待时间。平均等待时间Wq是等待时间的统计平均值。系统逗留时间是从顾客到达系统时刻算起到它接受服务完毕离开系统时刻为止的这段时间。平均系统逗留时间（或系统时间）Ws是系统逗留时间的统计平均值。系统效率：设某时刻有r个窗口被占用，若共有m个窗口则r/m就是窗口占用率。它的统计平均值为平均窗口占用率就是系统效率即η=rm空闲概率P0和拒绝概率Pn：P0为系统内无顾客的情况，即系统空闲状态概率。通过，可知系统的忙闲情况。拒绝系统Pn（或Pc）为系统内顾客已满、拒绝新到顾客进入系统的状态概率，也称为阻塞概率（或损失概率）。1.4两类重要排队系统模型的简要介绍及分析1.4.1M/M/1排队系统最简单的排队系统模型是M/M/1单窗口非拒绝系统。该系统的顾客到达为泊松流，设到达率为λ；服务时间为指数分布，设平均服务率为μ。图2M/M/1排队系统的状态转移图1.4.2M/M/m/(n)排队系统解决M/M/1系统的服务质量与系统效率之间的矛盾必须压缩排队长度、减小等待时间。通常可采用两种措施，增加窗口数和截止排队长度。增加窗口数可提高总服务率但意味着投资加大。而截止排队长度则通过降低系统质量来换取系统效率和稳定性。M/M/m(n)排队系统的模型（混合排队方式）中，顾客到达为泊松流，到达率为λ。同时有m个窗口，每个窗口对一位顾客的服务时间为指数分布，每个窗口的平均服务率为μ。顾客采用混合排队方式。队列长度为n，同时采取拒绝方式，即系统内最多可有n个顾客。图3M/M/m(n)排队系统的系统模型和状态转移图排队论在通信领域基于通信业务量的简单应用分析：排队论作为概率论的一个重要分支，在学术界各个领域都发挥着重要作用，而在通信领域，排队论的价值得到了空前的发掘，现就排队论在通信业务量的应用做出简要介绍以及相关讨论。2.1通信业务量基本理论设计和建设一个通信网及所配臵的设备是以全网业务量为主要依据的。进入通信网送到通信设备和线路上进行传输的语音、数据等输入信息统称为通信呼叫，简称呼叫，在排队论中对应顾客，呼叫长度（呼叫持续时间）对应服务时间。网中的呼叫源即是网内的所有用户。在网中传送的信息量称为通信业务量，也称为流量。信道数C或线路容量在排队论中对应窗口数m，而不同类型的呼叫事件也分别对应了不同的典型的排队模型。2.1.1呼叫的发生过程通常情况下，满足以下三个条件的呼叫条件称为称为纯随机呼叫：呼叫源无限多，即能够发生呼叫的用户数很大；处于占线状态（占用信道）的呼叫源数目相对少可不考虑；用户（呼叫）之间相互独立；呼叫的发生和交换网（或信道）的阻塞状态可分别考虑。若同时满足最简单流条件，即可表示为M/M/m(n)排队系统模型。实际通信网中的顾客（用户）数总是有限的，所以不存在严格的纯随机呼叫，而多属于准随机呼叫。准随机呼叫满足以下两个条件：呼叫源有限且用户之间仍相互独立。若同时满足最简单流条件，即可表示为M/M/m(n，N)排队系统模型。当N很大时(N>>k)或用户数非常多时准随机呼叫可近似当做纯随机呼叫处理。N越大这种近似越合理。实际通信网中往往会遇到多个顾客（用户）同时使用的状况，这就需要引入呼叫合成发生的情况来做分析。设有两个相互独立的呼叫源，各自按呼叫发生率λ1、λPP则合成呼叫发生数为k的概率为P所以说两个分别按λ1、λ2的泊松分布的合成等于呼叫发生率为λ1+λ2的泊松分布。易推得若有个各自任意速率,为λ2.1.2业务量和呼叫量业务量是在指定观察时间内各个线路（或信道）可能被占用的时间之和即占用的总时间。这些时间可以是重叠的或不重叠的。若某线路有m条信道，第i条信道被占用Qi秒，则m条信道或该线路上的业务量Q为Q=i=1mQr。业务量的量纲是时间。若一个信道代表一个电话话路则业务量或话务量的单位是秒/话路。这里的Q具不仅反映了信息源所发生的用户需求业务量业务量的强度通常称为呼叫量。它可定义为线路（或信道）可能占用的时间与观察时间之比，即呼叫量为a=业务量观察时间=Qr（erl），a是没有量纲的，通常使用“小时呼”或“爱尔兰（erl）”表示它的单位。通常取T为一小时。一个erl表示一小时一个完全被占用的信道的呼叫量，即单位小时或单位分钟的呼叫时长。根据定义呼叫量也可表示为a=λ电话网中的业务量称为话务量。话务量用来反映电话用户的通话频繁程度和通话时间的长短。表示为Y=Λst，其中λ表示单位时间内的呼叫次数，即呼叫强度（次/h）；对应排队论中的系统到达率。S表示一次呼叫的平均占用时长（h/次）；对应平均服务时间。T表示计算话务量的时间范围（h）。话务量含义反映了占用设备的程度，同时也反映了用户对电话网设备的需求。时延是指消息进入网内后直到被利用完毕所需的时间。包括等待时间、服务时间、处理时间、传输时延。其中传输时延一般是较小的，处理时间与消息内容有关，一般可从技术上缩短所占的份额不一定太大而且往往是恒定的。时延的主要部分是系统时间即等待时间和服务时间。2.1.3服务等级及服务系统业务量理论利用ErlangB公式或C公式，即业务量、中继线或信道数量和阻塞概率或呼叫等待概率之间的关系式在一定的服务等级上在已知业务量预测值的条件下确定中继电路数、长途电路数或求移动网中核心网的电路数、无线网的信道配臵等。目的是使固定数量的中继线路或信道可为一个数量更大的、随机的用户群体服务。服务等级表示为GoS（GradeofService）是表示拥塞的量。定义为呼叫阻塞概率（也称呼叫阻塞率），或呼叫延迟时间大于某一特定排队时间的概率。在实际的通信网中多为截止型的排队系统。当系统处于拒绝状态时系统是阻塞的将出现呼损。按处理阻塞呼叫（未接续的呼叫）的方式不同，通信网中通常用到两种服务系统：阻塞呼叫清除系统和阻塞呼叫延迟系统。阻塞呼叫清除系统不对阻塞呼叫请求进行排队即放弃阻塞呼叫的接续。这种系统又叫做阻塞系统或损失制系统、立接制系统。系统模型为M/M/m（m）或M/M/m（m，N），基本的阻塞呼叫清除系统为M/M/m（m）。而阻塞呼叫延迟系统系统模型为M/M/m（n）、M/M/m基本的阻塞呼叫延迟系统为M/M/m（n）。2.2举例分析——蜂窝移动网中的呼叫处理排队方案蜂窝移动通信是采用蜂窝无线组网方式，在终端和网络设备之间通过无线通道连接起来，进而实现用户在活动中可相互通信。其主要特征是终端的移动性，并具有越区切换和跨本地网自动漫游功能。蜂窝移动通信业务是指经过由基站子系统和移动交换子系统等设备组成蜂窝移动通信网提供的话音、数据、视频图像等业务。其中在GSM网络呼叫切换处理中常用三个典型的越区切换方案有无优先级方案、切换呼叫排队方案、信道预留方案。先分析如下：2.2.1无优先级方案系统模型表示为处理新呼叫和切换呼叫的排队模型M/M/C（C）。对这种这种方案来说小区中所有的C个信道均被新呼叫和越区切换呼叫所共享。基站处理以上两种呼叫的方法完全相同。任意一种呼叫，如在其到达的时刻基站内没有空闲信道那么到达的呼叫都将被系统阻塞。2.2.2切换呼叫排队方案系统模型表示为处理新呼叫的排队模型M/M/C（C），或处理切换呼叫的排队模型M/M/C（N）。就这种方案而言，小区中所有的C个信道同样被新呼叫和越区切换呼叫所共享。当上述两种呼叫同时到达并且小区中的信道全被占用时将对切换呼叫进行排队并阻塞新呼叫。如果在最大排队时间内无空闲信道可用就将阻塞切换呼叫。2.2.3信道预留方案系统模型表示为处理新呼叫的排队模型M/M/Sc（Sc）或处理切换呼叫的排队模型