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

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

《排队论及其在通信领域中的应用文档格式.docx》由会员分享，可在线阅读，更多相关《排队论及其在通信领域中的应用文档格式.docx（6页珍藏版）》请在冰点文库上搜索。

1、排队论概述：

1.1基本概念及有关概率模型简述：

排队论是一个独立的数学分支有时也把它归到运筹学中。

排队论是专门研究由于随机因素的影响而产生的拥挤现象（排队、等待）的科学也称为随机服务系统理论或拥塞理论。

它专于研究各种排队系统概率规律性的基础上解决有关排队系统的最优设计和最优控制问题。

排队论起源于20世纪初。

当时美国贝尔Bell电话公司发明了自动电话以后如何合理配臵电话线路的数量以尽可能地减少用户重复呼叫次数问题出现了。

1909年丹麦工程师爱尔兰发表了具有重要历史地位的论文“概率论和电话交换”从而求解了上述问题。

1917年又提出了有关通信业务的拥塞理论用统计平衡概念分析了通信业务量问题形成了概率论的一个新分支。

后经C.Palm等人的发展由近代概率论观点出发进行研究奠定了话务量理论的数学基础。

排队论广泛应用在网络的设计和优化方法移动通信系统中的切换呼叫的处理方法随机接入系统的流量分析方法ATM业务流的数学模型及其排队分析方法等。

系统的组成

一个排队系统由三个基本部分组成，输入过程、排队规则和服务机构。

图1排队系统的基本组成

输入过程是描述顾客按怎样的规律到达排队系统的过程。

包括以下三方面：

（1）顾客总体数，指顾客的来源（简称顾客源）数量，顾客源数可以是无限的也可以是有限的；

（2）顾客到达方式，描述顾客是怎样到达系统，是成批（集体）到达（每批数量是随机的还是确定性的）还是单个到达；

（3）顾客流的概率分布（或顾客到达的时间间隔分布），所谓顾客流，就是顾客在随机时刻一个个（一批批）到达排队系统的序列。

排队规则包括排队系统类型和服务规则两方面内容。

其中排队系统类型一般分为拒绝系统和非拒绝系统，表明服务机构是否允许顾客排队等待服务。

拒绝系统又称拒绝方式、截止型系统。

若用n表示系统允许排队的队长（也称截止队长），用m表示窗口数。

当系统L满足n=m时，该系统为即时拒绝系统，也称为立接制系统、损失制系统。

此时顾客到达后或立即被拒绝或立即被服务，不存在排队等待服务的情况。

电话网就是即时拒绝系统。

当系统L满足m<

n时，该系统为延时拒绝系统，也称为混合制系统。

此时容许一定数量的顾客排队等待，当系统内顾客总数达到截止队长时，新来的顾客就被拒绝而离去。

带有缓冲存储的数据通信、分组交换等就属于这一类。

非拒绝系统又称非拒绝方式、非截止型系统。

系统排队队长无限制，允许顾客排队等待一般认为顾客数是无限的。

例如公用电话。

延时拒绝系统和非拒绝系统也称为等待制系统、缓接制系统。

服务规则常见的有先到先服务（FCFS）和先入先出（FIFO），同时也有后到先服务（LCFS），在通信网中优先制服务也较为常见，同时在通信网中一般是顺序服务但有的也采用随机服务方式。

服务机构包括窗口或服务员数量（当m=1时，称为单窗口排队系统。

当m﹥1时，称为多窗口排队系统）、服务方式及排队方式和服务时间分布。

服务方式是指在某一时刻系统内接受相同服务的顾客数。

分为单个顾客接受服务（串列服务方式）和成批顾客同时接受服务（并列服务方式）。

其中串列服务方式是m个窗口的串列排队系统。

此时m个窗口服务的内容互不相同，某一时刻只能有一个顾客接受其中一个窗口的单项服务，每个顾客要依次经过这m个窗接受全部的服务。

而并列服务方式是m个窗口的并列排队系统。

此时m个窗口服务的内容相同，系统一次可以同时服务m个顾客。

排队方式包括混合排队和分别排队两种方式。

混合排队方式为顾客排成一个队列接受任意一空闲窗口的服务。

分别排队方式为顾客排成m个队列同时分别接受m个窗口的相同服务。

当m=1时在该系统中如果允许排队，则顾客只能排成一列队列接受服务。

当m﹥1时在该系统中如果允许排队则有混合排队和分别排队两种排队方式。

排队方式的选择取决于两种服务方式。

服务时间和顾客到达时间一样，多数情况下是随机型的。

要知道它的经验分布或概率分布。

一般说来服务时间的概率分布有定长分布、指数分布、Erlang分布等。

1.1.3排队系统的分类表示

目前较为广泛采用的分类表示方法是提出的分类方法。

表示为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…而取各个值的概率为

Pk=P{X=k}=λkk!

e-λ（k=0，1，2…）

其中λ>

0是常数,则称X服从参数为λ的泊松分布。

2、指数分布

一般，若随机变量t取具有概率密度函数为

f（t）=λe-λtt>

00t≤0

0为常数,则称t服从参数为λ的指数分布,其分布函数F（t）为

F（t）=-∞tf（t）dt=0tλe-λtdt=1-e-λt

F（t）=1-e-λtt>

00t≤0

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）=（λt）kk!

e-λt,k=1,2,3…

这里的Pk（t）是在时间t内有k个顾客到达的概率，或是一个排队系统中在时间t内有k个顾客在等待或正在处理的概率，或是总的C条信道中有k条信道被占用概率。

泊松过程的顾客到达时间间隔分布为顾客到达的时间间隔小于t的概率，即t内有顾客的概率分布。

两相邻顾客到达的时间间隔是一连续型随机变量，用T表示。

在时间内没有顾客到达的概率为

P0（t）=（λt）00!

e-λt=e-λt

则T的分布函数为

F（t）=P（T≤t）=1-P（T>

t）=1-e-λt

其概率密度函数为

fTt=dFT（t）dt=λe-λt

所以说，一个随机过程为“泊松到达过程”或“到达时间间隔为指数分布”实际上是一回事。

一般来说大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。

大量研究表明将电话呼叫当做最简单流处理得到的分析结果是正确的。

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、排队论在通信领域基于通信业务量的简单应用分析：

排队论作为概率论的一个重要分支，在学术界各个领域都发挥着重要作用，而在通信领域，排队论的价值得到了空前的发掘，现就排队论在通信业务量的应用做出简要介绍以及相关讨论。

2.1通信业务量基本理论

设计和建设一个通信网及所配臵的设备是以全网业务量为主要依据的。

进入通信网送到通信设备和线路上进行传输的语音、数据等输入信息统称为通信呼叫，简称呼叫，在排队论中对应顾客，呼叫长度（呼叫持续时间）对应服务时间。

网中的呼叫源即是网内的所有用户。

在网中传送的信息量称为通信业务量，也称为流量。

信道数C或线路容量在排队论中对应窗口数m，而不同类型的呼叫事件也分别对应了不同的典型的排队模型。

2.1.1呼叫的发生过程

通常情况下，满足以下三个条件的呼叫条件称为称为纯随机呼叫：

呼叫源无限多，即能够发生呼叫的用户数很大；

处于占线状态（占用信道）的呼叫源数目相对少可不考虑；

用户（呼叫）之间相互独立；

呼叫的发生和交换网（或信道）的阻塞状态可分别考虑。

若同时满足最简单流条件，即可表示为M/M/m（n）排队系统模型。

实际通信网中的顾客（用户）数总是有限的，所以不存在严格的纯随机呼叫，而多属于准随机呼叫。

准随机呼叫满足以下两个条件：

呼叫源有限且用户之间仍相互独立。

若同时满足最简单流条件，即可表示为M/M/m（n，N）排队系统模型。

当N很大时（N>

>

k）或用户数非常多时准随机呼叫可近似当做纯随机呼叫处理。

N越大这种近似越合理。

实际通信网中往往会遇到多个顾客（用户）同时使用的状况，这就需要引入呼叫合成发生的情况来做分析。

设有两个相互独立的呼叫源，各自按呼叫发生率λ1、λ2呈泊松分布，其呼叫发生概率分别为

Pk1t=（λ1t）kk!

e-λ1t

Pk2t=（λ2t）kk!

e-λ2t

则合成呼叫发生数为k的概率为

Pkt=[λ1t+λ2t]kk!

e-（λ1+λ2）t

所以说两个分别按λ1、λ2的泊松分布的合成等于呼叫发生率为λ1+λ2的泊松分布。

易推得若有个各自任意速率,为λ1、λ2、λ3、λm……的独立泊松流，则复合流本身也为泊松过程其速率参数为λ=i=1mλi。

2.1.2业务量和呼叫量

业务量是在指定观察时间内各个线路（或信道）可能被占用的时间之和即占用的总时间。

这些时间可以是重叠的或不重叠的。

若某线路有m条信道，第i条信道被占用Qi秒，则m条信道或该线路上的业务量Q为Q=i=1mQr。

业务量的量纲是时间。

若一个信道代表一个电话话路则业务量或话务量的单位是秒/话路。

这里的Q具不仅反映了信息源所发生的用户需求业务量也同时反映了通过m条信道的实际的通信业务量。

业务量的强度通常称为呼叫量。

它可定义为线路（或信道）可能占用的时间与观察时间之比，即呼叫量为a=业务量观察时间=Qr（erl），a是没有量纲的，通常使用“小时呼”或“爱尔兰（erl）”表示它的单位。

通常取T为一小时。

一个erl表示一小时一个完全被占用的信道的呼叫量，即单位小时或单位分钟的呼叫时长。

根据定义呼叫量也可表示为a=λt。

电话网中的业务量称为话务量。

话务量用来反映电话用户的通话频繁程度和通话时间的长短。

表示为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）或处理切换呼叫的排队模型M/M/C（C）。

系统专门为越区切换呼叫预留了部分信道。

预留信道数为C-Sc，剩余信道Sc则由新呼叫和越区切换呼叫所共享，当新呼叫到达小区时，如果基站中剩余的空闲信道数小于或等于预留信道数，就阻塞该呼叫请求。

当切换呼叫请求到达小区时，如果基站中没有空闲信道就将其阻塞。

有上述分析可知预留信道方式是降低切换失败概率的一种有效方法，但它影响了信道利用率。

切换失败概率的降低都是以新呼叫阻塞概率的升高为代价的。

提高信道利用率和降低呼损可采取四个措施，如大群化效应、延迟效应、综合效应、迂回效应等，在此不再赘述。