第4课网内业务分析(1)

第四章第四章通信网内业务分析通信网内业务分析在前一章中，主要讨论了通信网的整体拓扑结构，站址的选择和流量分配等问题，其中假定流量是恒定的。实际应用中大多数通信网的流量是随机的，所以真正的网络性能分析必须从流量的随机性出发。这种分析的理论基础主要是排队论。因此，需要介绍近代排队论的基本知识，在此基础上，建立通信网中的业务分析模型，进而讨论分析方法。在分析和计算的基础上，讨论建网时的一些原则。昀后讨论通信网的多址接入问题。主要内容主要内容§4.1排队论基础§4.2业务模型与分析§4.3提高网络效率的一些措施§4.4多址接入系统排队论（QueuingTheory)，也称随机服务统理论，是运筹学的一个主要分支。1909年，丹麦哥本哈根的一名工程师A.K.Erlang发表开创性论文“概率论和电话通信理论”，标志排队论的诞生。直到今天，通信系统仍然是排队论的主要应用领域。二次世界大战期间，排队论日臻完善，战后，其应用更趋广泛。目前在计算机设计、通信网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。§4.1排队论基础排队是日常生活中常见的现象，有无形的、有形的排队，如打电话被占线、商店购物而售货员较少。虽然具体的问题各不相同，但却有一些共同的特点,例如都存在要求得到某种服务的人或物和提供这种服务的人或机构。排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。由要求服务的顾客和提供服务的服务员双方构成的系统通常称为排队系统。资源的有限性和需求的随机性是排队现象存在的基础。§4.1.1概述不同的“顾客”与“服务员”组成了各式各样的随机服务系统。顾客为了得到某种服务而来到系统，若不能立即得到服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统。研究这种系统需要将“顾客”与“服务员”的含义广义化。例如通信网中的信息流和信道、计算机中总线上的指令、数据与CPU等都可看成是“顾客”与“服务员”的关系。这种系统研究的复杂性在于顾客的到达和服务完毕的时间都是不确定的，绝大多数排队系统工作于随机状态。图1随机服务系统通常由图通常由图11表示的系统也称为表示的系统也称为随机聚散服随机聚散服务系统务系统。。““聚聚””表示顾客的到达，表示顾客的到达，““散散””表表示顾客的离去。示顾客的离去。一般的排队系统，都可由下面模型加以描述。排队系统的基本形式基本的排队系统如图2-6所示，其中一个服务台里只有一个服务员。图2单服务台排队系统图3单队列——S个服务台并联的排队系统图4S个队列——S个服务台的并联排队系统图5单队——多个服务台的串联排队系统图6多队——多服务台混联网络系统在日常生活中，面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费。如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论——排队论所要研究解决的问题。排队论解决的基本问题排队论解决的基本问题1.系统性能和形态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。2.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。3.昀优化问题：即包括昀优设计(静态优化)，昀优运营（动态优化）。一、排队系统的组成与特征一、排队系统的组成与特征排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。§4.1.24.1.2基本概念基本概念输入即为顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是平稳的（stationary）或说是对时间齐次的（Homogeneousintime），也可以是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。1.1.输入过程输入过程这是指服务台从队列中选取顾客进行服务的顺序。可以分为损失制、等待制、混合制3大类。(1)损失制（即时制）。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制或即时制。22..排队规则排队规则(2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：①先到先服务（FCFS）。按顾客到达的先后顺序对顾客进行服务，这是昀普遍的情形。②后到先服务（LCFS）。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。③随机服务（RAND）。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。④优先权服务（PR）。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。(3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限。当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求服务。如水库的库容、旅馆的床位等都是有限的。②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客自动离去，不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。③逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记c为系统中服务台的个数，则当K=c时，混合制即成为损失制；当K=∞时，混合制即成为等待制。33..服务机构服务机构1）服务机构可以是单服务员和多服务员服务。在多个服务员时，各服务员可以是并列的，或串列的，也可以是并串混合排列。这种排列形式与队列规则联合后可形成多种不同形式的排队服务机构，如前图2到6所示。2)服务方式分为单个顾客服务和成批顾客服务。3)服务时间分为确定型和随机型。4)服务时间的分布通常假定是平稳的。D.G.Kendall，1953提出了排队系统的分类法，采用[X/Y/Z]记号，适用于并列服务台，1971年一次关于排队论符号标准化会议上，对Kendall符号进行扩充：[X/Y/Z]:[d/e/f]。zzXX：顾客相继到达的间隔时间分布：顾客相继到达的间隔时间分布zzYY：服务时间的分布：服务时间的分布zzZZ：并列的服务台数：并列的服务台数zzd:d:排队系统的最大容量排队系统的最大容量zze:e:顾客源数量顾客源数量zzf:f:排队规则排队规则二、排队系统的描述符号与模型分类二、排队系统的描述符号与模型分类M：负指数分布；D：确定型分布(Deterministic)；Ek：K阶爱尔朗（Erlang）分布；GI：一般相互独立时间间隔分布；G：一般服务时间的随机分布；HR：R阶指数分布。间隔时间和服务时间的各种分布如[M/M/1][M/M/1]::[[∞∞//∞∞/FCFS]/FCFS]：表示顾客到达为泊松过程，服务时间为负指数分布，单个服务台，无限容量，无限顾客源，先到先服务的排队系统模型。排队模型举例•M/M/1问题称为初级问题或基本问题；•G/M/1和M/G/1问题称为中级问题；•G/G/1和G/G/m问题称为高级问题；此外还有Er/G/1，G/Er/1，Er/Ek/1等成批到达/离开问题。三、三、排队问题求解排队问题求解将一个实际问题作为排队问题求解时，首要判断它属于哪个模型，其中只有顾客到达的隔时间分布和服务时间的分布，需要根据实际量的数据来确定，其它因素都是在问题提出时定的。求解一般排队系统问题的目的：主要是通过研究排队系统运行的效率，估计服务质量，确定系统参数的昀优值，判断系统结构的合理性，以便实现对现有系统有效改进和对新建系统的优化设计等。排队问题求解的一般步骤：排队问题求解的一般步骤：1.确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。2.研究分析排队系统理论分布的概率特征。3.研究系统状态的概率。4.根据排队系统对应的理论模型，求用以判断系统运行优劣的基本数量指标的概率分布或特征参数。5.排队系统指标优化。包括优化设计与优化运营。排队系统状态：系统状态是指系统中顾客数。如果系统中有n个顾客，系统的状态是n，系统状态的可能取值为：•队长没有限制时，n=0,1,2,…;•队长限制在昀长N以内时，n=0,1,2,…,N;•在即时制系统中，服务台有C个时，n=0,1,2,…,C，此时，状态n又表示正在工作的服务台数。系统状态的概率系统状态的概率：：指系统处于某一状态下的概率，状态概率通常是随时刻t变化的，所以在时刻t，系统状态为n的概率，用Pn(t)表示，即在t时刻系统中有n个顾客的概率，也称瞬态概率。求解状态概率Pn(t)方法首先建立含Pn(t)的关系式，其中t是连续变量，n是离散变量，只取非负整数，所以Pn(t)的关系式一般为微分、差分方程，即关于t的微分方程，关于n的差分方程。其次通过求解微分差分方程，得到系统的瞬态解，由于一般求出瞬态解的确切值比较困难，即便求得，一般也很难利用。因此常常使用它的极限(如果存在的话)，即nttnp)(plim=∞→称为稳态(steadystate)解，或称统计平衡状态的解。当系统运行了无限长的时间以后，初始(t=0)状态的概率分布{Pn(0),n≥0}的影响已消失，系统的状态概率分布不再随时间变化，当然在大多数实际应用中，系统会很快趋于稳态，并不真的需要t→∞，但实际中达不到稳态的现象也存在。要注意的是求稳态概率Pn并不一定求t→∞的极限，只需求Pn’(t)=0。过渡状态稳定状态pnt排队系统状态变化示意图稳态的物理含义•系统队长：系统中的顾客数，其平均值记为Ls。•队列长：系统中排队等待服务的顾客数，其期望均）值为Lq。系统中的顾客数Ls=排队等待服务的顾客数Lq+正被服务的顾客数c•逗留时间：指一个顾客在系统中的停留时间，其平值为Ws。•等待时间：一个顾客在系统中排队等待的时间，其均值为Wq。逗留时间=等待时间+服务时间•列德尔(Little)公式：Ls=λWs,适用于任何排队系统。排队系统运行的基本数量指标•忙期：指从顾客到达空闲服务机构起，到服务机构再次为空闲止，这段时间长度。忙期和一个忙期中平均完成服务的顾客数都是衡量服务机构效率的指标，忙期关系到工作强度。•系统强度ρ：定义为顾客到达率λ与服务率μ之比ρ=λ/μ。Δ当ρ大于服务台数m时，系统变得不稳定；Δ当ρ小于服务台数m时，系统是稳定的。对于截止型系统，由于队长被人为地限制，即使ρm，系统仍能稳定地工作。系统效率η：即平均服务台占用率。设共有m个服务台，某时刻有r个服务台被占用，则占用率为：r/m，它是一个随机变量，其统计平均值即为系统效率：η=/m，对于单服务台系统η=忙期效率，η越大，服务资源的利用率越高。损失率：在即时制或队长有限制的系统中,由于拒绝顾客进入系统而带来的损失。r4.1.34.1.3到达间隔到达间隔和服务时间的分布和服务时间的分布一个排队系统的昀主要特征参数是顾客的到达间隔时间分布与服