排队论及其在通信中的应用.doc

排队论及其在通信中的应用姓名：徐可 学号：2012202120131 专业：通信与信息系统摘要：排队论又称随机服务系统理论，它广泛应用于通信领域，是通信网络流量设计的基础理论。本文通过对排队论基本概念的介绍，进而阐述了排队论在通信网中的应用，以实例分析的方法揭示了排队论在通信网络流量设计中的重要作用。关键词：排队论 通信网络 Abstract:Queuing theory which is also called the theory of random service system is widely used in the communication field,and it is the basic theory of traffic flow in the communication network design.This paper introduce the basic concept of queuing theory, and expounds the queuing theory in communication network applications. with a case analysis,this paper reveals the important role of the queuing theory in communication network design .Key words: Queuing theory communication network 1 排队论基本概念1.1 排队系统的概念把要求服务的一方称为顾客，把提供服务的一方称为服务机构，而把服务机构内的具体设施称为服务员（或服务窗口）。顾客要求的随机性和服务设施的有限性是产生排队现象的根本原因。排队论就是利用概率论和随机过程理论，研究随机服务系统内服务机构与顾客需求之间的关系，以便合理地设计和控制排队系统1。由于顾客到达的数目和要求提供服务的时间长短都是不确定的，这种由要求随机性服务的顾客和服务机构两方面构成的系统称为随机服务系统或排队系统。1.2 排队系统的基本参数排队系统的基本参数包括：顾客到达率，服务员数目，和服务员服务速率。1.2.1 顾客到达率顾客到达率是单位时间内平均到达排队系统的顾客数量。反映了顾客到达系统的快慢程度，越大，说明系统的负载越重。一般，排队系统中顾客的到达是随机的，即任意相邻两顾客到达的时间间隔T是一个随机变量。T的统计平均就是顾客到达的平均时间间隔，其倒数为顾客到达率，即1.2.2服务员数目服务员数目就是排队系统内可以同时提供服务的设备或者窗口数，它表征服务机构的资源。1.2.3 服务员服务速率服务员服务速率指的是单位时间内由一个服务员进行服务而离开排队系统的平均顾客数。设一个顾客被服务的时间为，它也是一个随机变量。的统计平均就是一个顾客被服务的平均时间，即为单个服务员对顾客的平均服务时间，显然其倒数为服务员服务速率，即1.3 排队系统的三个特征排队系统在运行中包括三个过程：顾客输入过程它说明了顾客到达的规律，与顾客的到达率和顾客到达时间的随机性有关；排队过程与排队规则有关；顾客接受服务（然后离去）的过程取决于服务机构的效率和服务时间的长短。1.3.1 顾客到达间隔时间的分布函数如果顾客的输入过程满足下述的三个条件，则称该输入为最简单流。（1）平稳性。在某一指定的时间间隔t内，到达k个顾客的概率只与t的长度有关，而与这间隔的起始时刻无关。（2）稀疏性。将t分成n个足够小的区间，在内到达两个或者两个以上的顾客的概率为零。（3）无后效性（或独立性）。在某一个内顾客到达的概率和其他区间上顾客到达的概率无关。当输入是最简单流时，在给定时间间隔t内系统有k个顾客到达的概率为该分布为泊松分布。由此可见，最简单流在t时间间隔内到达系统的顾客数量服从泊松分布。相应地，顾客到达间隔时间T的概率密度函数为即，最简单流的顾客到达时间间隔T服从负指数分布规律。1.3.2 服务时间的分布函数假设顾客接受服务的过程也满足最简单流的平稳性，稀疏性和独立性。可以得到服务时间的概率分布函数为其概率密度函数为可见，服务时间也服从负指数分布。综上可见，对最简单流，所对应的概率分布是负指数分布，又称为M分布。1.3.3 排队规则（1） 损失制系统（即时拒绝方式）。电话通信网一般采用即时拒绝方式。（2）等待制系统（不拒绝方式）。（3）混合制系统（时延拒绝方式）2 排队系统2.1 排队系统的表示排队系统通常用符号X/Y/m/n表示。其中X是顾客到大间隔时间的分布，Y是服务时间的分布，m是服务员个数，n是排队系统中允许的顾客数，也称为截止队长。当n为时（即为不拒绝方式），可省略。常用的分布符号有：M负指数时间分布；D定长时间分布；k阶爱尔兰时间分布；k阶超指数时间分布。2.2 常见排队系统一些常见的排队系统有：（1） M/M/m/n排队系统。顾客到达间隔时间的分布和服务时间的分布均为负指数分布。（2） M/D/1排队系统。顾客到达间隔时间为负指数分布，服务时间为定长分布，只有一个服务员。（3） M/1排队系统。顾客到达间隔时间为负指数分布，服务时间为k阶爱尔兰分布，只有一个服务员。（4） M/1排队系统。顾客到达间隔时间为负指数分布，服务时间为k阶超指数时间分布，只有一个服务员。3 排队论在通信网中的应用3.1 排队论在电话通信网中的应用当系统中的顾客数等于窗口数时，新的顾客就会遭到拒绝，这种系统就M/M/m/n即时拒绝系统。电话通信网一般采用即使拒绝系统2。顾客到达时间间隔T服从参数为的负指数分布。一个顾客的服务时间服从参数为的负指数分布。对于M/M/1排队系统，排队强度为。可以推到得到，对于电话网通信系统，队长为k（即系统里面有k个顾客）的概率为其中：式中，是电话通信系统的流入话务量强度。这里是单位时间内的平均呼叫次数，而是平均每次呼叫的服务时间。是无量纲的，但通常使用爱尔兰作为它的单位，m为线束容量。当顾客到达系统时，若，则立即接受服务；若，就被拒绝而离去，因此顾客等待时间为0，平均队长N也变成平均处于忙状态的平均窗口数量。由此可以求的以下几个重要指标。（1） 平均队长N（2）顾客被拒绝的概率这是话务理论中著名的爱尔兰呼损公式。（3）系统效率即时拒绝系统的呼损率与流入话务量强度a及系统效率与线束容量m的关系如下：(1) 呼损率随着话务量强度a的增加而上升，当话务量强度一定时，增加m，可使呼损率下降。(2) 允许的呼损率越大，系统效率越高，这说明牺牲服务质量，即允许较大的呼损可以换取系统效率的提高。(3) m越大，系统效率越高，这就是所谓的大群化效应，即尽可能多地共用出线可以获得高效率。3.1.1 排队论在电话通信网中的应用实例分析 办公室有三条电话线可以打进，也就是说在任意时刻最多能打进接待三通话者来访，打进的电话是随机的，其时间服从上午九点至下午五点的均匀分布，每次电话的持续时间是均值为6分钟的随机变量，经理关心由于占线而可能打不进来的人数。他们当中有人稍后可能重拨电话，而其他人则可能放弃通话，一天中接通的电话平均数是70。 仿真这个办公室的电话系统并给出如下估计：（1） 无电话占线，有一条、两条占线和三条占线的时间百分比； （2） 没有打进电话的人所占的百分比。 问题的分析：这是一个多服务台混合制模型M/M/s/K，顾客的相继到达时间服从参数为的负指数分布（即顾客的到达过程为Poisson流），服务台的个数为s，每个服务台的服务时间相互独立，且服从参数为的负指数分布，系统的空间为K。在办公室三部电话系统的前提下，研究其工作情况，无电话占线、有一个、有两个、三个都占线所占的时间百分比，为保证顾客源不致过多的流失，能够接通更多的电话，比较研究是否应该新增加一台电话。 假设：顾客的相继到达时间服从参数为的负指数分布，服务时间服从参数的负指数分布，表示在时刻t，服务系统的状态为n（系统中顾客数为n）的概率，平稳状态队长N即系统中的顾客数其期望值，平稳状态排队长,指系统中排队等待服务的顾客数其期望值为，逗留时间指平稳状态顾客在系统中的停留时间，记它的期望值为，等待时间指平稳状态顾客在系统中排队等待的时间，期望值记作，表示当系统处于n时新来顾客的平均到达率，表示当系统处于n时，整个系统的平均服务率，s是系统中并行服务的台数，s为系统的服务强度。Little公式为：，顾客拨打这三部电话是等可能性的。 为求平稳分布，考虑系统处的任一状态n。假设记录了一段时间内系统进入状态n和离开状态n的次数，则因为“进入”和“离开”是交替发生的，所以这两个数要么相等要么相差1。但就这两件事件平均发生率来说，可以认为是相等的。即当系统运行相当时间而达到平衡状态后，对任一状态n来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数应该相等，这就是系统在统计平衡下的“流入=流出”原理3。根据这一原理，可得到任一状态下的平衡方程如下：0： 1： 2： n-1： n： 由上述平衡方程，可求得0： 1： 2： n： 记 n=1，2，则平稳状态的分布为： n=1，2，由概率分布的要求有由上面推导知本电话系统模型中有：于是其中由平稳分布，n=0,1,2,，K,可得平均排队长为：为求平均队长，由得到由系统的空间的有限性，必须考虑顾客的有效到达率。对多服务台系统有=再利用Little公式为：平均被占用的服务台数（也就是正在接受服务的顾客的平均数）为：因此，又有题中该办公室系统可看成M/M/3/3排队模型，其中平均到达率：= 0.146人/分钟；平均服务率：=人/分钟服务强度：=0.982于是可得空闲(无电话占线)的概率=0.381=38.1%有一条占线的概率 =0.9820.381=0.375=37.5%有两条占线的概率 =0.184=18.4%有三条占线率的概率 0.158=0.06=6.0%系统的顾客损失率为=0.06，即有6%的呼叫不能接通，即没有打进电话的人占6%。系统的相对通过能力Q=1-=0.94，即有94%的呼叫可以接通。系统的绝对通过能力A=Q=0.1460.94=0.137，即每分钟可接通0.137次（每小时8.23次）呼叫。被占用的中继线的平均数为：=0.982×0.94=0.923（条）通道利用率：=0.308=30.8% 结果分析：工作时间内，接通电话的总时间（三部电话）为：6×70=420（分钟），由于三部电话相互独立，打进的电话是随机的，其时间服从上午九点至下午五点的均匀分布则知三部电话的空闲率直观上看其和为：p=×3=3/8=0.375与模拟的结果0.381相差不大。通过巧妙的利用排队论的理论及概率学里边的函数分布规律（泊松分布、指数分布等）将一个看似离散随机的电话系统赋予数学的推导，得出一套基本可行方案，对实际问题的研究和解决提供参考依据。3.2 排队论在数据通信网中的应用目前各种数据通信网信息的交换都是以包为单位存储转发的，包可以称为分组。各分组到达网络节点（即交换机）进行存储转发的过程中，当多个分组要去往统一输出链路，那么就要进行排队，所以数据通信网就是一个大的排队系统。一个分组可以认为就是一个顾客，交换设备、信息传输网络就相当于服务机构，一条中继信道即为一个服务员（或服务窗口）4。服务到达率就是单位时间内到达交换节点的分组数量，服务员数目m指分组交换节点的输出信道数量。只是需要注意的是：在数据通信网中，习惯上用表示分组的平均长度，交换节点的一个输出信道容量为C。由此可以推导出，传送一个分组的平均时间，即分组的平均发送时间为，则每条输出信道发送分组的速率为（它对应着一个服务员的服务速率）。而对于有m条输出信道的交换节点（它相当于一个排队系统）来说，发送分组的速率（即系统的服务速率）为。4总结网络流量是个广泛使用的术语。网络的作用是传送各种业务流，业务流量的大小反映了人们对网络的需求和网络具有的传送能力。通信网络流量设计应根据业务流量预测值和服务指标要求确定交换设备和线路的容量，并对网内的流量进行合理分配，已达到节省网络资源的目的5。通过巧妙的利用排队论的理论及概率学里边的函数分布规律（泊松分布、指数分布等）将一个看似离散随机的网络流量设计赋予数学的推导，得出一套基本可行方案，对网络流量设计的实际问题的研究和解决提供参考依据。参考文献：1 毛京丽，李文海，现代通信网，北京邮电大学出版社，2007.6.2 唐宝民，江凌云，林建中，张颖，通信网基础，机械工业出版社，2004.3.3 赵国谦，通信网的性能分析，长春邮电学院学报，1990，vol.8，No.3.4 张柏生，任剑锋，基于排队论的网络通信系统的建模与分析，空军工程大学学报，2002,59-62.5 贾本，陆彦斌，国外科技新书评价，2006.7.