文档介绍：离散时间排队系统的分析与仿真
林稳安
(信息工程学院电子工程专业)
一、绪论

离散事件系统的性质与连续系统不同,这类系统的状态只在离散的时间点上发生变化,
而且这些离散的时间点是不确定的,因此离散事件系统的模型形式与连续系统也有很大的不
同。
首先考察一个简单的例子:
某商店只有一个收银台。在正常工作的时间内,如果没有顾客到收银台,则收银员空闲;
如果有顾客到达收银台,则收银员为顾客进行结账服务。如果顾客到收银台时,收银员正在
为其他顾客服务,则新来的顾客在一旁排队等候。显然,每个顾客到达收银台的时间是随机
的,而收银员为每个顾客进行结账服务的时间也是随机的,从而每个队列中的顾客等候的时
间也是随机的,这是一个典型的离散事件系统的例子。
进行系统仿真研究的目的之一是掌握系统的运动规律,即系统内部状态的变化律。对于
连续系统来说,其内部状态是随时间连续变化的,任意两个时间点上系统的内部状态都不相
同,因此必须确定每个时刻点上系统的内部状态,也就是应当解出系统的内部状态与时间的
函数关系。而对于离散事件系统来说,系统的内部状态变化是随机的,同一个内部状态可以
向多种状态转变,因此很难用函数形式来描述系统内部状态的变化,通常所关心的是系统内
部状态变化的统计规律。另一方向,系统的内部状态只在离散的随机时间点上发生变化,且
状态在一段时间内保持不变。因此在建立离散事件系统模型时只需考虑系统内部状态发生变
化的时间点以及产生这些状态变化的原因,而不用描述系统内部状态发生变化的过程。[1]
在离散事件系统建模过程中,适当地确定系统的状态变量是很重要的。用于进行仿真研
究的系统状态变量并不总是固定唯一的,它应当根据系统仿真研究的目的而确定。另外在建
模过程中,还必须清晰地描述系统状态变化的流程,包括到达并进人系统中实体的类型和数
目,使系统状态发生变化的事件类型、事件发生时间的分布规律等。[2]
2. 排队论基础
1918 年,Erlang 提出排队论,并将它用于电话系统,其实质就是研究服务台与顾客之
间的效率问题,希望服务台效率高,而顾客的等待时间又不长,他又称为随机服务理论。[3]
众所周知,一个电话系统的功能是按照用户(或顾客)需求在主叫用户与被叫用户之间
提供通信路由(或称通信信道,也称话路)。如果,在每一对电话用户之间提供一条固定的
通信路由时,由于其成本接近天文数字,而不可能办到。为了解决这个问题,必须建立和保
持通话的路由是“公用”的,即需要时选用,话毕时释放。这就隐含着这样一种可能性:由
于某一时刻恰好没有空闲的路由可选用,这个呼叫就不能建立.。亦即,不可能真正做到随
时都能“按需”实现任意双方用户之间的通信要求,存在着(系统的)“供”和(顾客的或
用户的)“需”之间的矛盾。
排队理论是应用概率论的一个分支,它有各种名称,如业务量(话务量)理论、排队论、
阻塞理论、大量业务(服务)理论以及随机服务系统的理论。其中,业务量(话务量)理论
通常应用于电话和通信业务量方面的理论,如同车辆交通流量理论。排队论通常用于描述更
加专门化的等待队列的数学理论。但是,某些系统最有用的或最感兴趣的模型是不容许形成
队列,所以,“排队论”的名称似乎不完全适宜,故称它为随机服务系统理论较确切一些。
从排队论的发展历史来看,它不但应用在电话业务量工程方面并已得到了很大的发展,
而且还广泛地应用在工程领域、运筹学以及计算机科学、计算机通信等诸方面。目前排队论
在计算机和现代电信网中的应用包括:计算机系统的性能分析、ATM 网络中的信源及其分
析、ATM 网络的阻塞控制、ATM 交换技术及其性能分析等等。
1
3. 泊松过程
在排队理论中,最常遇到的一种随机过程就是泊松(Poisson)过程。
Poisson 过程是一个重要过程,它满足如下假设条件:[4]
设有一小的时间间隔△t,则
(1) 在△t 内有一信息到达的概率为λ△t,且λ△t 它与前后时间间隔内到达的信息数无
关。这里,λ为平均的信息到达速率,是一个比例常数。
(2) 在△t 内无信息到达的概率是 1-λ△t,因为当△t 足够小时,多于一条信息到达的
概率忽略不计。
(3) 在各不相互重叠的时间间隔中,到达的信息数是相互独立的随机变量。
(4) 概率结构与时间位置无关。
根据以上性质,可以得到一个微分—差分方程,经过 Z 变换和解微分方程得
(λt)n e−λt
p (t) = ,t > 0, n = 0,1,2,.... (公式 1-1)
n n!
pn(t)为在是时间 t 内有 n