通信网理论基础第4章

的概率分布有：定长分布、指数分布、爱尔兰分布等。
21
一、基本概念
（一）排队系统的组成

（二）排队系统的三个基本参数 （三）排队系统分类的表示方法
22
（二）排队系统的三个基本参数
任何排队系统都有三个参量m 、λ、μ，称为排队模型三要素。 （1） m ：称为窗口数或服务员数目，表征系统的资源量。 它表示系统中有多少服务设备可同时向顾客提供服务。例如 机场供飞机起降的跑道数，通信系统中的线路数等。
16
(2) 服务规则
① 先到先服务(FCFS)或先入先出(FIFO)。顺序服务。 ② 后到先服务(LCFS)。如；计算机内的堆栈区域就是按此方
式工作的。
③ 优先制服务。对各类顾客分别事先赋予不同的优先级，优 先级愈高，愈提前被服务。 ④ 随机服务。即当窗口有空闲时，不按照排队序列而随意地 指定一个顾客去接受服务。例如，电话交换机接通呼叫的电




8

产生排队现象的根本原因：顾客需求的随机性和服务 设施的有限性是产生排队现象的根本原因。 应用的理论：概率论和随机过程理论。 研究的内容：研究随机服务系统内服务机构与顾客需 求之间的关系（供求关系），以便合理地设计和控制 随机服务系统，使之既能满足一定的服务质量要求又 能节省服务机构的费用。

27
一、基本概念
（一）排队系统的组成 （二）排队系统的三个基本参数

（三）排队系统分类的表示方法
28
（三）排队系统分类的表示方法
采用D．G．肯特尔（D．G．Kendall）提出的分类方法： X/Y/m (n, N)


X ：表示顾客到达时间间隔分布。
Y：表示服务时间分布。 m ：表示窗口或服务员数目（此处特指并列排队系统）。 n ：表示截止队长，省略这一项表示n→∞ ，即为非拒绝系 统。 N ：表示潜在顾客总数，对于无限潜在顾客源，即N→∞时， 可省去这一项。
绝系统。
14
延时拒绝系统： m<n的系统。此时容许一定数量的顾客排队 等待，当系统内顾客总数达到截止队长n时，新来的顾客就被 拒绝而离去。即当顾客到达系统时，系统中已有k个顾客（包 括正在被服务的顾客），若k < n，且m个窗口有空闲，就立
即接受服务，如果m个窗口均被占满，则允许顾客排队等待
服务；若k=n， m个窗口必均被占满，则遭到拒绝，即不容 许该顾客排队而离开系统。带有缓冲存储的数据通信，分组 交换等就属于这一类。
（2） λ ：顾客到达率或系统到达率，即单位时间内平均到
达系统的顾客数量。其单位为个/时间单位或份/时间单位，个、 份为一个信息单位。 对于电话系统→单位时间内发生的平均呼叫数 对于数据传输系统→单位时间内输入的平均信息量
23
λ的倒数称为平均到达时间间隔 T ，即
N (t ) lim t t
其中λ>0为常数，则t称服从参数为λ的指数分布，其分布 函数F (t)为：
1 e t F (t ) 0 t 0 t 0
其均值为 E ( t )
1

方值为
D( t )
1
2
35
二、有关的概率模型及最简单流 （一）排队系统常用的概率模型 （二）排队系统中几个常用的概念 （三）最简单流
e ( N Ls ) 0
k状态的系统到达率为：
k ( N k ) 0
25
（3）μ：服务员（或窗口）的服务速率，即单位时间内由一 个服务员（或窗口）进行服务所离开系统的平均顾客数。 m=1的单窗口系统，μ就是系统的服务速率。 m>1的多窗口系统，单位时间接受服务后离开系统的平 均顾客数为mμ（假设每个窗口的服务速率均为μ）。即 系统服务率为mμ。 μ的倒数1/μ就是单个窗口对顾客的平均服务时间 。


稳定性参数（排队强度）ρ：
1

/ m
26

ρ对系统稳定性的影响： 若ρ‹ 1 ，即λ‹ mμ时，说明平均到达系统的顾客数小于 平均离开系统的顾客数。这时系统是稳定的，可以采 取非拒绝方式和拒绝系统。 若ρ≥ 1 ，即λ≥ mμ时，说明平均到达系统的顾客数多于 平均离开系统的顾客数。采用拒绝方式，则可人为限 制系统内的顾客数量，保证系统的稳定性。
12
（3）顾客流的概率分布（或顾客到达的时间间隔分布）：所 谓顾客流，就是顾客在随机时刻一个（批）个（批）来到排 队系统的序列。相继到达的顾客（成批或单个）之间的时间 间隔的分布或到达顾客流的概率分布的是什么。如电话呼叫
流、列车到站流等等。
求解排队系统有关运行指标问题，首先要确定顾客流的概率 分布。即在一定的间隔时间内到达k (k = 1, 2, …)个顾客的概 率是多大，或相邻两个顾客到达的时间间隔分布是什么。顾 客流的概率分布一般有定长分布、二项分布、泊松流（最简
29

表示不同输入过程（顾客流）和服务时间分布的符号 有：
Ｍ：泊松（Poisson）流（或指数分布）。两者都具有马尔
可夫随机过程性质。
Ｄ：定长分布。 EK：K阶爱尔兰（Erlang）分布。 ＧI：一般相互独立的随机分布。 Ｇ ：一般随机分布
30
一、基本概念 二、有关的概率模型及最简单流 三、生灭过程 四、排队系统的主要性能指标
话就是一例。通信网中一般是顺序服务，但有的也采用优先
制服务方式。
17
3.服务机构 服务机构包括以下三方面内容： (1)窗口或服务员数量 当m =1时，称为单窗口排队系统。 当m >1时，称为多窗口排队系统。 (2)服务方式及排队方式 服务方式：指在某一时刻接受服务的顾客数，即是单个顾客 接受服务（串列服务方式）还是成批顾客同时接受服务（并 列服务方式）。 串列服务方式：即m个窗口的串列排队系统。此时， m个窗 口的服务内容互不相同，每个窗口一次只能有一个顾客接受 服务，每个顾客要依次经过这个窗口接受全部的服务。
设随机变量X所有可能取的值为0，1，2，…， 而取各个值的概率为
Pk P { Χ k }
k
k!
e

k= 0，1，2 …
其中λ>0是常数，则称X服从参数为λ的泊松 分布。 其均值为
E( Χ )
方值为
D( Χ )
34
２．指数分布
一般地，若随机变量t取具有概率密度函数为
e t f (t ) 0 t0 t0
18
并列服务方式：即m个窗口的并列排队系统。此时， m个窗
口的服务内容相同，系统一次可以同时服务m个顾客。
排队方式：包括混合排队和分别排队两种方式。
混合排队：顾客排成一队。 分别排队：顾客排成m个队列。
19
服务方式与排队方式
20
（3）服务时间分布
服务时间和顾客到达时间一样，多数情况下是随机型的。为 此，要知道它的经验分布或概率分布。一般说来，服务时间

9
线路容量不够，将导致拥塞现象。

电路交换网→增加业务量损失（又称呼损）

分组交换网→增加信息延时。从经济条件考虑，线路容 量要有限制。信息到达网络节点时要排队等待处理，排 队时延与信息长度，信息到达时间，以及信息处理顺序 等有关。
10
（一）排队系统的组成
排队系统
顾客到达
排队 规则
服务 机构


4

经典（或古典）排队论：把相继到达“顾客”的到达时间 间隔和服务时间都相互独立的排队论内容称为经典（或古 典）排队论。经典排队论仍是新的排队论的基础，而且， 通信领域的许多问题可以用它来解决。 内容： 排队论基础 M / M / m（n）排队 通信业务量分析


多址接入系统业务分析


3

应用：
在通信、交通、港口泊位设计、机器维修、库存控制、计 算机设计等各个领域中排队论都获得了广泛应用。 通信系统仍然是排队论应用的主要领域，也是其发展的重 要推动力量。经过通信、计算机和应用数学三个领域的研 究学者的努力研究，排队论得到了迅速的发展。 在宽带综合业务数字网中，异步传送模式，统计复用，随 机多址接入中都涉及到许多排队论问题，而且正在研究解 决中，如ATM业务流的数学模型及其排队分析方法。
第4章 排队论基础
4．1 排队论基础 一、基本概念 二、有关的概率模型及最简单流 三、生灭过程 四、排队系统的主要性能指标
4．2 M/M/m (n) 排队
一、 M/M/1排队系统 二、 M/M/m (n) 排队
1

排队论： 是一个独立的数学分支，有时也把它归到运筹学中。 专门研究由于随机因素的影响而产生的拥挤现象(排队、 等待)的科学，也称为随机服务系统理论。
服务完毕离去排队系统的基本组成11（一）排队系统的组成
一个排队系统是由三个基本部分组成的：输入过程、排队规
则及服务机构。 1．输入过程
输入过程就是描述顾客按怎样的规律到达排队系统，包括以
下三方面： （1）顾客总体数：指顾客的来源（简称顾客源），可以是无 限的，也可以是有限的。根据情况电话呼叫次数有时认为是 有限的，有时认为是无限的。 （2）顾客到达方式：描述顾客是怎样来到系统的，是成批到 达（每批数量是随机的还是确定性的）还是单个到达。
5

一、基本概念 二、有关的概率模型及最简单流
三、生灭过程
四、排队系统的主要性能指标
6
一、基本概念
（一）排队系统的组成 （二）排队系统的三个基本参数
（三）排队系统分类的表示方法
7

排队：无形的排队——电话网，有形的排队——分组 交换。
顾客：要求服务的一方统称为顾客，如电话用户产生 的呼叫和待传送的分组信息。 服务机构：提供服务的一方统称为服务机构，如电话 交换设备、信息传输网路等。 服务员或服务窗口：把服务机构内的具体设施称服务 员或服务窗口，如中继线、信道等。 排队系统（随机服务系统）：由要求随机性服务的顾 客和服务机构两方面构成的系统称为排队系统（随机 服务系统）。