通信网理论分析

第2章通信网理论分析2.1排队论基础1.排队模型基本概念只有一个服务员的单服务员排队模型是最简单的排队模型。它由一个服务员和一个代表队列的方框组成，如图2.1所示。图中的λ是顾客到达率或称系统负荷，例如，在电话网中它表示单位时间内发生的呼叫次数（呼叫/秒）；在分组交换网中表示单位时间发生的分组信息数（分组/秒）。µ是顾客离去率或称系统服务率，它的单位与λ

相同。例如，在分组网中，µ

是由分组长度（bit）和链路传输速率（bit/s）所决定，其单位是分组/秒。例如，一条速率C

=

2

400bit/s的传输链路，在传输一个长度为1

000bit的分组时，其服务率µ=

2.4分组/秒。图2.1单服务员排队模型系统负荷与系统容量之比称为服务强度或链路利用率，即ρ=

λ

/µ，这是排队论中的一个重要的参数。对于单服务员排队模型，当ρ

趋近或超过1时，就会进入阻塞，时延迅速增大，到达的分组被阻塞。对于一般的排队系统，有一套A/B/C表示符号，A表示顾客到达的分布特性，B表示服务员的服务分布特性，C表示服务员的个数。有时采用A/B/C/K/M这样的符号，A、B、C的含义不变，K表示排队系统的容量，省略这一项表示K→∞；M表示潜在的顾客数，对于潜在顾客数M→∞时，也可省去此项。常见的几种排队系统模型符号表示如下。

M/M/1排队：表示泊松到达、指数服务特性、一个服务员的排队系统。这里符号M来自马尔可夫（Markov）过程，用来表示泊松过程或相应的指数分布。

M/M/m排队：表示泊松到达、指数服务分布特性、m个服务员的排队系统。

M/G/1排队：表示泊松到达、服务时间服从一般分布的单服务员排队系统。

M/D/1排队：表示泊松到达、服务时间为常数的单服务员排队系统。为了对泊松过程进行定义，在时间轴上取一个很小的时隙Dt，如图2.2所示。用下面3个表述来对泊松过程进行定义。①在时隙△t中有一个顾客到达的概率定义为λ△t

+o(△t)，o(△t)表示△t的更高阶项，当△t

→0时，它更快地趋于0；λ

是一比例常数，且λ△t

<<1。②在△t中没有顾客到达的概率是1−λ△t

+o(△t)。③到达是无记忆的，即在长度为△t的一个时隙内的顾客到达，与以前或以后的时隙中的到达无关。图2.2用于定义泊松过程的时隙图2.3泊松到达的时间间隔利用上述3点，我们可以求得在T间隔内有k个顾客到达的概率p(k)，由下式给出：

p(k)=(l

T)ke−l

T/k!（k

=

0，1，2，…）

（2.1）这就是熟知的泊松分布。其平均值E(k)和方差由下式给出:

（2.2）

（2.3）式中，l

为速率参数，它代表泊松到达的平均速率。图2.3所示为随机到达的示意图，相继到达之间的时间间隔为t，显然，t

是一个连续分布的正随机变量。对于泊松到达，可以证明t

服从指数分布，其概率密度函数f(t

)可由下式给出：

f(t)=le−lt（t

≥0）这一指数分布的平均值E(t

)为它的方差为：

=1/l2例如，某电话局忙时平均呼叫率为每小时1

000次，则平均来话间隔E(t

)

=

3.6s，平均来话间隔为10s的概率为0.94。2.

M/M/1，M/G/1，M/D/1排队模型1）．M/M/1排队模型

M/M/1排队模型是一个符合泊松到达、指数服务时间、按先进先出（FIFO）规则服务的单服务员排队模型。图2.4所示为M/M/1排队模型示意图，图中顾客到达率为l

。图2.4

M/M/1排队模型我们首先利用此模型来分析该系统的相关统计特性：系统中的平均顾客数E(n)、平均排队长度E(q)、顾客在系统中的平均逗留时间E(T)和平均等待时间E(w)等。假设，当系统中有n个顾客时，称此系统处于状态n，与此对应出现该状态的概率为Pn。由此，我们可以用图2.5表示M/M/1排队系统的状态转移关系。例如，图中“1”表示系统中有一个顾客，相应的出现概率为P1，依此类推。图2.5

M/M/1排队系统的状态图在系统状态图中，有顾客到达时，状态以l

速率向右转移一步；有顾客完成服务时状态以速率m

向左移动一步。在系统处于统计平衡状态下，可列出系统统计平衡方程：（2.4）平衡方程是通过稳态平衡原理来建立的，等式两边分别表示脱离状态n的速率与由状态n−1或n+1进入状态n的速率。在系统稳态平衡条件下，脱离n状态与进入n状态保持平衡，所有等式两边相等。根据此平衡方程，我们可以得到：在M/M/1排队系统的存储容量为无穷大时，可以利用概率归一性条件：求得：

于是，可以得到无限存储容量M/M/1排队的平衡状态概率：

（2.5）式中，r

＜1是上式能够成立的必要条件。为使平衡得以存在，队列的到达率或负荷必须小于输出容量m

。如果在无限长排队模型中Pn这一条件不满足，队列就会随时间持续不断地增长，而永远达不到平衡点。图2.6所示为当r

=

0.5时状态概率的图形表示。图2.6

M/M/1状态概率（r

=

0.5）根据所得到的状态概率Pn，可以求得不同的排队统计特性。根据随机变量平均值的定义，排队系统中的平均顾客数（包括正在被服务的一个）可以表示为（2.6）由平均队长可以求得排队平均时延，这可以利用Little公式进行。Little公式是排队论中的一个重要公式，它说明了平均到达率l

、平均时延E(T)和平均队长E(n)三者之间的关系。

应用Little公式，M/M/1排队的平均时延E（T）可以表示为

式（2.7）的图形表示如图2.7所示，这一关系式对所有排队系统，包括具有优先级排队规则的系统都是适用的。（2.7）（2.8）图2.7

M/M/1排队的平均队长上面已经分析了E(n)和E(T)。在M/M/1排队中还有另外两个统计量，即平均等待时间E(w)和平均等待顾客数量E(q)，它们之间的关系为：（2.9）（2.10）这4个统计量可以归纳为与l

、m

的关系：（系统中平均队列长度）（顾客平均时间延迟）（平均等待顾客数）（顾客平均等待时间）可以将上述分析推广到存储容量为N的有限队列排队系统。这时与无限队列排队系统相比，平衡方程还是维持原状，所不同的是边界条件n

=

N。N对应的状态概率的归一性条件为（2.11）E(n)lm=-l我们可以求得

所以有限队列M/M/1排队的状态概率为排队系统全满的概率为

上述公式可用于计算分组的丢失率。（2.12）（2.13）（2.14）2）．M/G/1和M/D/1排队对于排队模型的到达过程和服务时间分布来说，它们是以马尔可夫无记忆特性为基础的这里将分析推广到另一种情况，即一般服务时间分布，因此，分组或呼叫可以有任意（但已知）长度或服务分布。然而，到达过程仍为泊松的，假定是单服务机且队列缓存器（等候室）是无限大的。根据Kendall标记法，这种排队称作M/G/1排队，其中G显然指一般（general）服务分布。可以证明平均队列长度E(n)和经过队列的平均时延E(T)分别由下列表达式确定。（2.15）（2.16）这些公式是以两个俄国数学家命名的，称为Pollaczek-Khinchine公式（帕拉恰克－辛钦公式）。参数r

仍由给出，为平均到达率（泊松），这两个表达式与M/M/1的相应结果（两式中括号前的项）看来是紧密相联系的。这是一个值得注意的结果：泊松到达和任意服务分布排队的平均队列占用量（和相应的时延）可由具有相同平均服务时间的指数服务分布排队的结果乘以一个校正因子得到。式（2.15）和式（2.16）括号中的校正因子与服务分布的方差s2和服务率平均值的平方1/m2之比有关。为平均服务时间。参量s为服务时间分布的方差。2回忆指数分布的方差为s2

=

1/m2，即平均值的平方。在式（2.15）和式（2.16）中，设s2

=

1/m2，则可得到以前推导的M/M/1排队的结果。当s2增大，s2

>

1/m2时，相应的平均队长和时延也随之增大。另一方面，当s2

<

1/m2时，平均队长和时延比M/M/1的结果小。作为一个特例，令所有顾客（分组或呼叫）都具有相同的服务长度1/m。这样，s2

=

0，则有：（2.17）

顾客服务时间固定不变的排队称作M/D/1排队，字母D表示确定的（det

erminIstic）服务时间。这是M/G/1排队的一个特例，它的排队长度和时延最小。如果r

不太大，可利用M/M/1的结果得到和。当，M/D/1的结果与M/M/1的结果相差50%。（2.18）

3

M/M/m排队到达率与离开率依赖于系统状态的排队系统如图11.19所示，其相应的稳态状态转移关系如图2.8所示。参数ln−1表示系统由状态（n−1）进入状态n的顾客到达率，Pn表示系统处于状态n的平衡概率，mn是在系统处于状态n条件下的顾客离去率。根据离开状态n的离去率等于进入状态n的到达率，可以得到系统的平衡方程：图2.8与状态相关的排队系统与状态相关的排队状态图解平衡方程，可以求得系统的平衡概率Pn：式中，P0为概率常数，可以利用概率归一性条件来求解。（2.19）

M/M/m排队是与状态相关的排队的一个例子。在一个分组交换网中，如果统计集中器或分组交换机有m条出局中继线，且输出队列的到达和离去均为指数统计特性，则该系统就是M/M/m排队系统，其排队模型如图2.9所示。在此系统中，如果只有一个分组要传输，它立即以服务率m受到任一中继线服务。如果有m个或更多的分组，则m条中继线都被占用。因此在系统中，可以得到：图2.9

M/M/m排队模型利用上述条件和式（11.27），可以得到平衡概率：

式中：（2.21）（2.20）

M/M/m排队的一个特殊情况是m为无穷大，这相当于在分组交换或电路交换的情况下，传输线或中继线的数量总是等于需要传输的分组和呼叫数，因而永远不会有阻塞的可能性，这时平衡状态概率为：P0=e−r与状态相关的排队的第2个例子是M/M/N/N系统，这是一个有N个服务员但没有等待室的排队系统，并当n

=

N时，将所有的到达阻塞掉。这一系统的排队模型如图2.10所示。这里ln

=

l，mn

=

nm，1≤n≤N。图2.10

M/M/N/N排队模型在这个系统中，ln

=

l，mn

=

nm，概率归一性条件为（2.22），把这些条件应用于式（11.16），可以求得：

这一公式就是求解电话系统阻塞概率的爱尔兰B公式。

当n

=

N时出现阻塞，因此阻塞概率PB为（2.23）2.2电路交换网分析1．呼损清除传统的电话交换网是电路交换网。一个由若干个交换节点和交换节点间的中继链路组成的电话交换网，如果在交换节点的全部出线都被占用的情况下仍有新的呼叫发生，交换节点向用户送忙音，表示将这个呼叫从交换系统中清除，这种现象称为呼损。对于交换节点来讲，如果呼叫到达是泊松过程，中继线群是全利用度线群，当系统发生呼叫阻塞时，该呼叫会被立即清除，则该系统达到统计平衡状态时，呼叫损失概率可以按爱尔兰B公式进行计算：

B(N，A)

=

（2.24）式中，B(N，A)表示流入话务量为A，中继线数为N时的呼损概率，式中用A代替式（11.22）中的ρ，即

A

=λ/µ

（2.25）

A表示系统的业务强度，对于电话网就是系统承受的电话负荷（话务量）。例如，电话网的平均来话率λ=

300次/时，每次通话平均时间2min（即1/µ

=

2min），则此电话网的流入话务量A

=

10Erl。话务量单位用Erl（爱尔兰，Erlang），是为了纪念丹麦话务理论家A.K.Erlang而命名的。话务量单位也可以用每小时百秒呼（ccs）来表示。Erl与ccs的关系是：Erl

=

36ccs。利用爱尔兰B公式可以在一定的中继线和流入话务量的情况下计算系统的呼损概率。举例如下：假定某电话局在上午9:00～10:15有500次呼叫发生，每次呼叫平均占用时间为200s，中继输出线有29条，求呼损概率。解：

平均来话率为

l

=

500/(75×60)

=

0.111

1次/秒平均占用时间为

1/m

=

200s流入话务量为

A

=

呼损概率为

B(29，22.2)

=

=

0.031

2

=

22.2Erl爱尔兰B公式是在求解阻塞概率或中继线数中常用的计算公式。话务量、中继线数和阻塞概率三者之间的关系已经制成相应图或表，以便查阅。图2.11及表11.3给出了在各种不同的中继线数的情况下，呼损概率与流入话务量之间的关系。在实际中，呼损概率用下列递推关系：（m=1，2，…，N）

（2.26）式中，初始值B(0，A)

=

1。由以上分析可知，在流入话务量之中，除大部分完成通话外，还有一部分被阻塞。完成通话部分话务量可以表示为

A‘

=

A[1−B(N，A)]（2.27）在上例中，容易算出完成话务量为

A'

=

22.2[1−0.0312]

=

21.5(Erl)

=

74%图2.11呼损清除系统的阻塞概率对于此交换系统，我们可以进一步求出出线的利用率：

η

=

2.3分组交换数据网分析在分组交换网中，分组信息在每一个节点被存储、转发而产生时延。交换节点的存储、转发功能可以用一个无限容量缓冲器的M/M/1排队模型来表示，如图2.12所示。为了分析分组信息时延，假定分组信息到达时，在缓冲器内已有n个分组在等待发送。因此，要发送的分组信息通过节点的时延由等待时间和服务时间两部分组成，即

T

=

等待时间+服务时间图2.12交换节点中的缓冲过程模型等待时间是分组信息在节点上等待链路空闲所消耗的时间，服务时间是分组在链路传输时间的总和。在分组网中，每个分组信息在链路上的服务时间即传输时间为

式中1/m'是分组信息的平均长度（比特/分组），Ci是链路i的容量或速率（bit/s）。为了计算在节点的的等待时间，我们仍保持单服务员排队系统的假设条件，于是可求得平均等待时间为（2.38）（2.29）式中li是链路i的分组到达率，单位为（分组/秒）。则分组通过节点和链路i的平均时延为（2.30）端—端平均时延图2.13所示为由多个节点组成的分组交换网。分析端－端的平均时延，需要考虑从源点到目的地所经过的路由上每段链路造成的时延影响。同时，由于路由中途经的节点处可能会有新的分组发生，因此，我们在计算从源点发生的分组在经过路由中各节点对时延的影响