通信网络chapter3_0

1、第1章 通信网络概论及数学基础通信工程学院信息科学研究所通信工程学院信息科学研究所1.3 通信网络中的数学基础 p1.3.1 随机过程的基本概念随机过程的基本概念p1.3.2 Poisson过程过程p1.3.3 马尔可夫链马尔可夫链习 题 1.111.13-1.161.3 通信网络中的数学基础为了为了定量地描述定量地描述通信网络的运行过程、设计通信网络的运行过程、设计通信网络的体系结构和评估通信网络容量、通信网络的体系结构和评估通信网络容量、时延和服务质量等，我们需要了解网络中每时延和服务质量等，我们需要了解网络中每个链路、节点、交换机个链路、节点、交换机/路由器，用户终端等路由器，用户终端等

2、设备的设备的输入输出业务流输入输出业务流的的行为特征行为特征和和处理过处理过程程。AEFDCB A(t) C(t) D(t) B(t)描述这些行为特征和处理过程的基本数学基描述这些行为特征和处理过程的基本数学基础是础是随机过程随机过程和和排队论排队论，描述网络结构的基，描述网络结构的基本方法是本方法是图论图论。本节主要讨论常用的随机过。本节主要讨论常用的随机过程和图论基础，在第三章中将详细讨论排队程和图论基础，在第三章中将详细讨论排队论的基本内容。论的基本内容。1.3.1 随机过程的基本概念（1） 随机过程随机过程是用来描述在一个观察区间内某一实体是用来描述在一个观察区间内某一实体（壶口瀑布水

3、的流量、食堂中的人数壶口瀑布水的流量、食堂中的人数）的随机行为。）的随机行为。tttX(t)X(t)X(t)(1)(2)(n)例如例如: :在通信系统中的噪声就是一个典型的随机过程。在通信系统中的噪声就是一个典型的随机过程。( ( n台性能完全相同的通信接收机的输出如下图。台性能完全相同的通信接收机的输出如下图。) )1.3.1 随机过程的基本概念（2）随机过程是随机过程是随机变量随机变量概念在概念在时间域时间域上的延伸。直观地讲，上的延伸。直观地讲，随机过程是时间随机过程是时间t的的函数的集合函数的集合，在任一个观察时刻，在任一个观察时刻，随机过程的取值是一个随机变量。或者说，随机过程的取值

4、是一个随机变量。或者说，依赖于时间依赖于时间参数参数t的随机变量所构成的总体称为随机过程的随机变量所构成的总体称为随机过程。tttX(t)X(t)X(t)(1)(2)(n)t1X(t1)t2X(t2) 什么是随机变量？随机变量：某一变量以一定的概率取一确定的值，随机变量：某一变量以一定的概率取一确定的值，通常将这种变量称为随机变量。通常将这种变量称为随机变量。随机变量：定义在样本空间上的一个实值随机变量：定义在样本空间上的一个实值函数函数，或者说是样本空间到实数的一个映射。或者说是样本空间到实数的一个映射。1.3.1 随机过程的基本概念（2）随机过程具有二重性：随机过程具有二重性：（1 1）随

5、机性随机性：对任何单个样本值而言，它是一：对任何单个样本值而言，它是一随机变量。随机变量。（2 2）函数特性函数特性：在整个时域空间上，是一随机：在整个时域空间上，是一随机函数。函数。1.3.1 随机过程的基本概念（3）设设X(t)是一个随机过程，则可以从两个方面来描述是一个随机过程，则可以从两个方面来描述X(t)的特征：的特征：一是一是在任意时刻在任意时刻t1，随机变量随机变量X(t1)的统计特征的统计特征，如一维分布函，如一维分布函数，概率密度函数，均值和方差等。数，概率密度函数，均值和方差等。二是二是同一随机过程在不同时刻同一随机过程在不同时刻t1和和t2对应的随机变量对应的随机变量X(

6、t1)和和X(t2)的相关特性的相关特性，如多维联合分布函数、相关函数、协方差矩阵，如多维联合分布函数、相关函数、协方差矩阵等。等。tttX(t)X(t)X(t)(1)(2)(n)t1X(t1)t2X(t2) 1.3.1 随机过程的基本概念（4）随机过程随机过程X(t)的的一维分布函数一维分布函数，定义为，定义为 （1-1）式中式中P表示概率。表示概率。xtXPxFt)()(xxFxftt)()(如果如果Ft(x)对对x的微分存在，则的微分存在，则X(t)的的一维概率密度函一维概率密度函数数定义为定义为 （1-2） 1.3.1 随机过程的基本概念（5）通常一维分布函数不能完全描述随机过程的特征

7、，通常一维分布函数不能完全描述随机过程的特征，需要采用需要采用n维联合分布函数维联合分布函数。对于给定的。对于给定的n个时刻个时刻t1，t2， ，tn，随机变量，随机变量X(t1)，X(t2)，X(tn)的联合的联合分布函数为：分布函数为： （1-3） nnntttxtXxtXxtXPxxxFn)(,.,)(,)(,.,221121,.,21若若 则随机过程则随机过程X(t)的的均值函数均值函数为为 （1-4） ,)(xdFXt)()()(xxdFtXEtmtX确定性函数确定性函数1.3.1 随机过程的基本概念（6）若对任给的时刻若对任给的时刻t1和和t2，如下列函数，如下列函数 （1-5）存

8、在，则称存在，则称CX( (t1, ,t2) )为为X(t)的的协方差函数协方差函数；)()()()()(),(cov),(22112121tmtXtmtXEtXtXttCXXX)()()()(2tmtXEtXDtDXx （1-6）为为X(t)的的方差函数方差函数。1.3.1 随机过程的基本概念（7）若对任给的时间若对任给的时间t1和和t2， RX( (t1, ,t2)=)=E E X(t1) X(t2) 存存在，则在，则 RX( (t1, ,t2) )为为X(t)的的自相关函数自相关函数。协方差函数，自相关函数、均值函数有下列关系：协方差函数，自相关函数、均值函数有下列关系： （1-7） )

9、()(),(),(212121tmtmttRttCXXXX若对任给的时刻若对任给的时刻t1和和t2，如下列函数，如下列函数 （1-5）存在，则称存在，则称CX( (t1, ,t2) )为为X(t)的的协方差函数协方差函数；)()()()()(),(cov),(22112121tmtXtmtXEtXtXttCXXX1.3.1 随机过程的基本概念（8）下面介绍几类典型的随机过程：下面介绍几类典型的随机过程：1.独立随机过程独立随机过程2.马尔可夫马尔可夫(Markov)过程过程 3独立增量过程独立增量过程 4平隐随机过程平隐随机过程 5 Poisson过程过程 6 马尔可夫链马尔可夫链1.独立随机

10、过程 设有一个随机过程设有一个随机过程X(t) ，如果对任意给定的时刻，如果对任意给定的时刻t1，t2 ， ，tn ，随机变量，随机变量X(t1), X(t2), X(tn)是是相互独相互独立立的，也就是其的，也就是其n维分布函数可以表示为：维分布函数可以表示为： niitntttxFxxxFin121,.,)(),.,(21t1 t2 t3 tn-2 tn-1 tnX(t)t（1-8）则称则称X(t)是是独立随机过程独立随机过程。该过程的特点是。该过程的特点是任意一时任意一时刻的状态与其他任何时刻的状态无关刻的状态与其他任何时刻的状态无关。2.马尔可夫(Markov)过程(1) 设有设有X(

11、t)一个随机过程，如果对于一个任意的时间序一个随机过程，如果对于一个任意的时间序列：列： t1 t2 t0)所处的所处的状态与该过程在状态与该过程在t0时刻之前的状态无关。时刻之前的状态无关。式（式（1-9）右端的条件分布函数可以写成：）右端的条件分布函数可以写成： （1-10）该式称为马氏过程的该式称为马氏过程的转移概率转移概率。 ,) (|)() |(,ttxtXxtXPxxFtt)|(,.,|1,121.,1121nnttnnttttxxFxxxxFnnnn3独立增量过程 设设X(t2)- X(t1)= X(t1 ,t2)是随机过程是随机过程X(t)在时间间隔在时间间隔 t1 ,t2)上

12、的增量，如果对于时间上的增量，如果对于时间t的任意的任意n个值个值0 0 t1 t2 tn ，增量增量X(t1 ,t2), X(t2 ,t3), X(tn-1 ,tn)是是相互独立相互独立的，则称的，则称X(t)为为独立增量过程独立增量过程。该过程的该过程的特点特点是：在任一时间间隔上是：在任一时间间隔上, ,随机过程状态随机过程状态的改变并不影响未来任一时间间隔上状态的改变。可的改变并不影响未来任一时间间隔上状态的改变。可以证明独立增量过程是一种特殊的以证明独立增量过程是一种特殊的马尔可夫过程马尔可夫过程。t1 t2 t3 tn-2 tn-1 tnX(t)tX(t1) X(t2) X(t3)

13、 X(tn-2) X(tn-1) X(tn)X(t1,t2) X(t2,t3) X(tn-2,tn-1) X(tn-1,tn)4平隐随机过程(1) 如果对于时间如果对于时间t的任意的任意n个值个值t1，t2 ， ，tn和任意实数和任意实数 ，随机过程随机过程X(t)的的n维分布函数满足关系式：维分布函数满足关系式： （1-11）则称则称X(t)为为平稳随机过程平稳随机过程或简称为平稳过程。或简称为平稳过程。),.,(),.,(21,.,21,.,2121ntttntttxxxFxxxFnn该过程的该过程的特点特点是随机过程的统计特性不随时间的平移而是随机过程的统计特性不随时间的平移而变化。变化

14、。t1 t2 t3 tn-2 tn-1 tnX(t)tt1+ + t2 + + t3 + + tn-2 + + tn-1 + + tn + + 按照上述定义的随机过程通常称为按照上述定义的随机过程通常称为严（狭义）平稳过程严（狭义）平稳过程。4平隐随机过程(2)(2tXE在实际应用中，我们更关心这样一类过程：其在实际应用中，我们更关心这样一类过程：其 （称为二阶矩过程），且满足下列条件：（称为二阶矩过程），且满足下列条件：1）均值均值为常量（与时间为常量（与时间t无关）；无关）；)(),(stRtsRXX2）对于任意时刻）对于任意时刻s和和t，其，其相关函数相关函数满足满足 ，即即相关函数仅与

15、时差相关函数仅与时差t-s有关有关，而与，而与s,t的取值无关；的取值无关；称这类过程为称这类过程为宽（广义）平稳过程宽（广义）平稳过程。在实际应用中所指。在实际应用中所指的随机过程通常是宽平稳过程。的随机过程通常是宽平稳过程。4平隐随机过程(3)当一个严平稳过程的一阶矩、二阶矩存在时，它当一个严平稳过程的一阶矩、二阶矩存在时，它一定是宽平稳过程；否则，结论不成立。一定是宽平稳过程；否则，结论不成立。一般的宽平稳过程不是严平稳过程，因为一般的宽平稳过程不是严平稳过程，因为“一阶矩一阶矩与时间无关与时间无关”是不能推出它的概率分布也与时间无是不能推出它的概率分布也与时间无关；同样，自相关函数只依

16、赖于时间差，也不能关；同样，自相关函数只依赖于时间差，也不能推出它的二维联合概率分布与采样时间有关。推出它的二维联合概率分布与采样时间有关。如果一个过程的所有的高阶矩或高阶相关函数完如果一个过程的所有的高阶矩或高阶相关函数完全由一阶矩、二阶矩决定，此时，宽平稳与严平全由一阶矩、二阶矩决定，此时，宽平稳与严平稳是等价的。到目前为止，我们了解到的具有此稳是等价的。到目前为止，我们了解到的具有此类特征的过程只有正态过程（高斯过程）类特征的过程只有正态过程（高斯过程）各态历经性(1) 为了说明各态历经性，在时间轴上定义下列两种平均：为了说明各态历经性，在时间轴上定义下列两种平均： （1-12） （1-

17、13）为随机过程的为随机过程的时间均值时间均值和和时间相关函数时间相关函数。TTTdttXTtX)(21lim)(TTTdttXtXTtXtX)()(21lim)()(-T 0 +Ttt各态历经性研究如何从过程的一次观察记录确定各态历经性研究如何从过程的一次观察记录确定其各种统计量的问题。其各种统计量的问题。各态历经性(2)若若X(t)是一个是一个平稳过程平稳过程，如果，如果 = EX(t) = mx依概率依概率1成立（即对所有样本都成立），则成立（即对所有样本都成立），则称随机过程称随机过程X(t)的的均值具有各态历经性均值具有各态历经性；如果如果 = EX(t) X(t+ ) = Rx (

18、 )依概依概率率1成立，则称过程成立，则称过程X(t)的的自相关函数具有各态自相关函数具有各态历经性；历经性；如果如果X(t)的均值和自相关函数都具有各态历经性，的均值和自相关函数都具有各态历经性，则称则称X(t)是（宽）各态历经过程是（宽）各态历经过程，或者说，或者说X(t)是各是各态历经的。态历经的。时域平均时域平均= =集总平均集总平均1.3.2 Poisson过程(1) 在日常生活中，如果我们观察顾客进入商店、银行或在日常生活中，如果我们观察顾客进入商店、银行或其它公共服务场所的过程，我们发现如果把一位顾客其它公共服务场所的过程，我们发现如果把一位顾客的到达看成一个的到达看成一个“随机

19、点随机点”，则这是一个源源不断出，则这是一个源源不断出现现随机点的过程随机点的过程。在这一过程中任一段时间内到达的。在这一过程中任一段时间内到达的顾客数也是随机的。顾客数也是随机的。这类描述到达顾客数及其特征的过程通常称为这类描述到达顾客数及其特征的过程通常称为计数过计数过程。程。如果我们考察一个交换局中如果我们考察一个交换局中电话呼叫到达电话呼叫到达（人们拨打电（人们拨打电话的行为中拿起电话并拨出对方号码的动作称为一次电话的行为中拿起电话并拨出对方号码的动作称为一次电话呼叫到达）的过程也具有类似的特征。话呼叫到达）的过程也具有类似的特征。1.3.2 Poisson过程(2)设一个随机过程为设

20、一个随机过程为A(t),t 0的的取值为非负整数取值为非负整数，如，如果该过程满足下列条件，则称该过程为到达率为果该过程满足下列条件，则称该过程为到达率为 的的Poisson(泊松泊松)过程过程。(1) A(t)是一个是一个计数过程计数过程，它表示在，它表示在0, t）区间内到达区间内到达的用户总数，的用户总数， A(0)=0, A(t)的的状态空间状态空间为为0,1,2,。如图如图1-12所示。任给两个时刻所示。任给两个时刻s和和t，且，且s d 1 1，并仅当，并仅当n n为为d d的整倍时有的整倍时有则状态则状态i i是有周期性的。是有周期性的。 非周期性如果马氏链中没有一个状态是有周期

21、性的，则称该马氏链为非周期的。本课程仅考虑本课程仅考虑非周期不可约非周期不可约的马氏链。的马氏链。1.3.3 马尔可夫链(12)对于马氏链，其对于马氏链，其状态的稳态概率状态的稳态概率定义为：如果有定义为：如果有 （1-27）则称概率分布则称概率分布 是马氏链的是马氏链的稳态分布稳态分布。0,.1 , 0iijijjPpp0|jpj01jjp对于概率分布有对于概率分布有 。稳态概率反映了系统达到稳态后，系统处于某一状态的稳态概率反映了系统达到稳态后，系统处于某一状态的可能性（概率）。可能性（概率）。1.3.3 马尔可夫链(13)稳态分布稳态分布可以表示为：可以表示为： （1-28）,.1 ,

22、0|lim0iiXjXPpnnj即过程从初始状态即过程从初始状态X0= i 出发，最终转移到状态出发，最终转移到状态Xn= j的的概率。显然与初始状态概率。显然与初始状态X0= i无关。无关。kjkpkj的次数次转移中访问状态前 lim稳态分布稳态分布也可以表示为：（以概率也可以表示为：（以概率1成立）成立） （1-29）因此因此pj表示该过程中访问状态表示该过程中访问状态j的时间比例或频率，且该的时间比例或频率，且该频率与初始状态无关。频率与初始状态无关。1.3.3 马尔可夫链(14)该式称为该式称为全局平衡方程全局平衡方程(Global balance equations)。它。它表示在稳

23、态情况下，从一个状态表示在稳态情况下，从一个状态j转移出去的频率转移出去的频率（式（式（1-30）左边）等于）左边）等于转移进入状态转移进入状态j的频率的频率（式（式（1-30）的右边）。该方程提供给我们一种典型的求解稳态概率的右边）。该方程提供给我们一种典型的求解稳态概率分布的方法。分布的方法。由于由于 ，则结合式（，则结合式（1-27）有）有 （1-30）01ijiP00., 1, 0iiijijijjPpPp1.3.3 马尔可夫链(15)例例1.2（续续）求随机游走过程的稳态概率。）求随机游走过程的稳态概率。),(0100021021000210210002102100010),(123

24、4512345pppppppppp0,.1 , 0iijijjPpp在例在例1.2中我们已知各种状态的转移概率矩阵，设状中我们已知各种状态的转移概率矩阵，设状态态a5,a4,a3,a2,a1的稳态概率为的稳态概率为p5, ,p4, ,p3, ,p2和和p1，则我，则我们根据式（们根据式（1-27）可得稳态概率的方程为：）可得稳态概率的方程为：0100021021000210210002102100010P1.3.3 马尔可夫链(16)例例1.2（续续）求随机游走过程的稳态概率。）求随机游走过程的稳态概率。由于由于 是稳态概率分布，则有是稳态概率分布，则有 （1-32）5., 2, 1|ipi5

25、11iip求解式求解式(1-31)和式和式(1-32)组成的方程组，得稳态概组成的方程组，得稳态概率分布为：率分布为： （1-33） )81,41,41,41,81(),(12345ppppp生灭（birth-death）过程(1) 在实际中，我们经常遇到这样一类特殊的马氏过程：在实际中，我们经常遇到这样一类特殊的马氏过程：仅有相邻状态的转移，而没有其它状态的转移（即如仅有相邻状态的转移，而没有其它状态的转移（即如果果 ，则，则 ），如图），如图1-15所示。这一所示。这一类过程通常称为类过程通常称为生灭（生灭（birth-death）过程）过程。 1| ji0ijP生灭（birth-deat

26、h）过程(2)它表示一个群体（动物、生物等）它表示一个群体（动物、生物等）总数为总数为n的特殊状态的特殊状态转移过程。该群体总数的转移过程。该群体总数的状态转移只有三种可能状态转移只有三种可能：或：或者者从从n增加一个增加一个（群体出生一个），或者（群体出生一个），或者从从n减少一个减少一个（死亡一个），或者群体的总数（死亡一个），或者群体的总数n保持不变保持不变。而其它所。而其它所有可能的转移相对前三种转移都是有可能的转移相对前三种转移都是高阶无穷小高阶无穷小，因而，因而可以忽略不计。该群体状态的转移概率取决于群体的可以忽略不计。该群体状态的转移概率取决于群体的总数总数n（状态）。（状态）。

27、令令 ，则应用式（，则应用式（1-30）可得：）可得： （1-35）., 1,., 1, 0nnS., 1, 0, 111,nPpPpnnnnnn00iiijijijPpPp它表示在稳态的情况下，从它表示在稳态的情况下，从状态状态n转移到状态转移到状态n+1的频的频率等于从状态率等于从状态n+1转移到状态转移到状态n的频率的频率，或在状态转移，或在状态转移图中设置一个虚拟的平面（图图中设置一个虚拟的平面（图1-15中的虚线），则进中的虚线），则进入该平面的频率等于退出该平面的频率，即该平面是入该平面的频率等于退出该平面的频率，即该平面是系统的一个稳定点。系统的一个稳定点。生灭（birth-de

28、ath）过程(3) 令状态空间为令状态空间为，0,1,1,Sn n00,0,1,jjiiijiip Pp Pj0 ,1ijPij当jjjjjjjjjjjjPpPpPpPp, 11, 111,1,1, 11, 111,jjjjjjjjjjjjPpPpPpPp1, 11)(jjjjjjPpPpjf令) 1()(jfjf则0)0(1, 000 , 11PpPpf而1, 11jjjjjjPpPpnnnnnnPpPp, 111,或详细平衡方程详细平衡方程生灭（birth-death）过程(4) 详细平衡方程详细平衡方程 local balance equationsnnnnnnPpPp, 111,nnnnnnPPpp, 11,100, 12, 11,1 ,01,2, 1pPPPPPPpnnnnnnnnnjjp1又0p求解稳态概率求解稳态概率0,jpj生灭（birth-death）过程(5)生灭（birth-death）过程(6)., 1, 0, 111,nPpPpnnnnnn上式可推广到一个更一般