排队论及其在通信领域中的应用
排队论及其在通信领域中的应用
排队论及其在通信领域中的应用
信息与通信工程学院
2010211112班
姓名：李红豆
学号：10210367
班内序号：26
指导老师：史悦
一、摘要
排队论是为了系统的性态、系统的优化和统计推断，根据资料的合理建立模型，其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队是一种司空见惯的现象，因此排队论可以用来解决许多现实问题。利用排队论的知识可以来解决通信服务中的排队论问题。应用排队论一方面可以有效地解决通信服务系统中信道资源的分配问题；另一方面通过系统优化，找出用户和服务系统两者之间的平衡点，既减少排队等待时间，又不浪费信号资源，从而达到最优设计的完成。
二、关键字
排队论、最简单流、排队系统、通信
三、引言
排队论又称随机服务系统, 主要解决与随机到来、排队服务现象有关的应用问题。是研究系统由于随机因素的干扰而出现排队(或拥塞) 现象的规律的一门学科, 排队论的创始人Erlang 是为了解决电话交换机容量的设计问题而提出排队论。它适用于一切服务系统,包括通信系统、计算机系统等。可以说, 凡是出现拥塞现象的系统, 都属于随机服务系统。随着电子计算机的不断发展和更新, 通信网的建立和完善, 信息科学及控制理论的蓬勃发展均涉及到最优设计与最佳服务问题, 从而使排队论理论与应用得到发展。
四、正文
1、排队论概述：
1.1基本概念及有关概率模型简述：
1.1.1排队论基本概念及起源：
排队论是一个独立的数学分支有时也把它归到运筹学中。排队论是专门研究由于随机因素的影响而产生的拥挤现象(排队、等待)的科学也称为随机服务系统理论或拥塞理论。它专于研究各种排队系统概率规律性的基础上解决有关排队系统的最优设计和最优控制问题。
排队论起源于20世纪初。当时美国贝尔Bell电话公司发明了自动电话以后如何合理配臵电话线路的数量以尽可能地减少用户重复呼叫次数问题出现了。 1909年丹麦工程师爱尔兰A.K.Erlang发表了具有重要历史地位的论文“概率论和电话交换”从而求解了上述问题。 1917年A.K.Erlang又提出了有关通信业务的拥塞理论用统计平衡概念分析了通信业务量问题形成了概率论的一个新分支。后经C.Palm等人的发展由近代概率论观点出发进行研究奠定了话务量理论的数学基础。
排队论广泛应用在网络的设计和优化方法移动通信系统中的切换呼叫的处理方法随机接入系统的流量分析方法ATM业务流的数学模型及其排队分析方法等。
1.1.2排队论系统的组成
一个排队系统由三个基本部分组成，输入过程、排队规则和服务机构。
分布或概率分布。一般说来服务时间的概率分布有定长分布、指数分布、Erlang分布等。
1.1.3排队系统的分类表示
目前较为广泛采用的分类表示方法是D.G.Kendall提出的分类方法。表示为X / Y / m（n，N）。其中X表示顾客到达时间间隔分布，Y 指服务时间分布m指窗口或服务员数目（此处特指并列排队系统），n指截止队长省略这一项表示n→∞，即为非拒绝系统，N 指表示潜在的顾客总数对于潜在的无限顾客源即N n→∞，时可省去这一项。
表示不同输入过程（顾客流）和服务时间分布的符号有：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…而取各个值的概率为
Pk=P{X=k}= ( k =0，1，2 …)
其中λ>0是常数,则称X 服从参数为λ的泊松分布。
2、指数分布
一般，若随机变量t 取具有概率密度函数为
f(t)=
其中λ>0为常数,则称t服从参数为λ的指数分布,其分布函数F( t)为
F(t)= ==1-
F(t)=
1.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高阶的无穷小量。
在上述三个条件下，可以推出
Pk（t）= ,k=1,2,3 …
这里的Pk（t）是在时间t内有k个顾客到达的概率，或是一个排队系统中在时间t内有k个顾客在等待或正在处理的概率，或是总的C条信道中有k条信道被占用概率。
泊松过程的顾客到达时间间隔分布为顾客到达的时间间隔小于t的概率，即t内有顾客的概率分布。两相邻顾客到达的时间间隔是一连续型随机变量，用T表示。在时间内没有顾客到达的概率为
P0（t）==
则T 的分布函数为
F（t）=P(T)=1-P(T>t)=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单窗口非拒绝系统。该系统的顾客到达为泊松流，设到达率为λ；服务时间为指数分布，设平均服务率为μ。
图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、排队论在通信领域基于通信业务量的简单应用分析：
排队论作为概率论的一个重要分支，在学术界各个领域都发挥着重要作用，而在通信领域，排队论的价值得到了空前的发掘，现就排队论在通信业务量的
应用做出简要介绍以及相关讨论。
2.1通信业务量基本理论
设计和建设一个通信网及所配臵的设备是以全网业务量为主要依据的。进入通信网送到通信设备和线路上进行传输的语音、数据等输入信息统称为通信呼叫，简称呼叫，在排队论中对应顾客，呼叫长度（呼叫持续时间）对应服务时间。网中的呼叫源即是网内的所有用户。在网中传送的信息量称为通信业务量，也称为流量。信道数C或线路容量在排队论中对应窗口数m，而不同类型的呼叫事件也分别对应了不同的典型的排队模型。
2.1.1呼叫的发生过程
通常情况下，满足以下三个条件的呼叫条件称为称为纯随机呼叫：呼叫源无限多，即能够发生呼叫的用户数很大；处于占线状态（占用信道）的呼叫源数目相对少可不考虑；用户（呼叫）之间相互独立；呼叫的发生和交换网（或信道）的阻塞状态可分别考虑。若同时满足最简单流条件，即可表示为M/M/m(n)排队系统模型。
实际通信网中的顾客（用户）数总是有限的，所以不存在严格的纯随机呼叫，而多属于准随机呼叫。准随机呼叫满足以下两个条件：呼叫源有限且用户之间仍相互独立。若同时满足最简单流条件，即可表示为M/M/m(n，N )排队系统模型。当N 很大时(N >>k)或用户数非常多时准随机呼叫可近似当做纯随机呼叫处理。N越大这种近似越合理。
实际通信网中往往会遇到多个顾客（用户）同时使用的状况，这就需要引入呼叫合成发生的情况来做分析。设有两个相互独立的呼叫源，各自按呼叫发
生率呈泊松分布，其呼叫发生概率分别为
则合成呼叫发生数为k的概率为
所以说两个分别按的泊松分布的合成等于呼叫发生率为的泊松分布。易推得若有个各自任意速率,为……的独立泊松流，则复合
流本身也为泊松过程其速率参数为λ=。
2.1.2业务量和呼叫量
业务量是在指定观察时间内各个线路（或信道）可能被占用的时间之和即
占用的总时间。这些时间可以是重叠的或不重叠的。若某线路有m条信道，第i
条信道被占用Qi秒，则m条信道或该线路上的业务量Q为。业务
量的量纲是时间。若一个信道代表一个电话话路则业务量或话务量的单位是秒/话路。这里的Q具不仅反映了信息源所发生的用户需求业务量也同时反映了通过m条信道的实际的通信业务量。
业务量的强度通常称为呼叫量。它可定义为线路（或信道）可能占用的时间与观察时间之比，即呼叫量为a==（erl），a是没有量纲的，通常使用
“小时呼”或“爱尔兰（erl）”表示它的单位。通常取T为一小时。一个erl 表示一小时一个完全被占用的信道的呼叫量，即单位小时或单位分钟的呼叫时
长。根据定义呼叫量也可表示为a=λ。
电话网中的业务量称为话务量。话务量用来反映电话用户的通话频繁程度和通话时间的长短。表示为Y=Λst，其中λ表示单位时间内的呼叫次数，即呼叫强度（次/h）；对应排队论中的系统到达率。S表示一次呼叫的平均占用时长（h/次）；对应平均服务时间。T表示计算话务量的时间范围（h）。话务量含义反映了占用设备的程度，同时也反映了用户对电话网设备的需求。
时延是指消息进入网内后直到被利用完毕所需的时间。包括等待时间、服务时间、处理时间、传输时延。其中传输时延一般是较小的，处理时间与消息内容有关，一般可从技术上缩短所占的份额不一定太大而且往往是恒定的。时延的主要部分是系统时间即等待时间和服务时间。
2.1.3服务等级及服务系统
业务量理论利用Erlang B公式或C公式，即业务量、中继线或信道数量和阻塞概率或呼叫等待概率之间的关系式在一定的服务等级上在已知业务量预测值的条件下确定中继电路数、长途电路数或求移动网中核心网的电路数、无线网的信道配臵等。目的是使固定数量的中继线路或信道可为一个数量更大的、随机的用户群体服务。
服务等级表示为GoS（Grade of Service）是表示拥塞的量。定义为呼叫阻塞概率（也称呼叫阻塞率），或呼叫延迟时间大于某一特定排队时间的概率。在实际的通信网中多为截止型的排队系统。当系统处于拒绝状态时系统是阻塞的将出现呼损。
按处理阻塞呼叫（未接续的呼叫）的方式不同，通信网中通常用到两种服务系统：阻塞呼叫清除系统和阻塞呼叫延迟系统。阻塞呼叫清除系统不对阻塞呼叫请求进行排队即放弃阻塞呼叫的接续。这种系统又叫做阻塞系统或损失制系统、立接制系统。系统模型为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）或处理切换呼叫的排队模型M/M/C（C）。系统专门为越区切换呼叫预留了部分信道。预留信道数为C-Sc ，剩余信道Sc则由新呼叫和越区切换呼叫所共享，当新呼叫到达小区时，如果基站中剩余的空闲信道数小于或等于预留信道数，就阻塞该呼叫请求。当切换呼叫请求到达小区时，如果基站中没有空闲信道就将其阻塞。
有上述分析可知预留信道方式是降低切换失败概率的一种有效方法，但它影响了信道利用率。切换失败概率的降低都是以新呼叫阻塞概率的升高为代价的。提高信道利用率和降低呼损可采取四个措施，如大群化效应、延迟效应、综合效应、迂回效应等，在此不再赘述。