现代通信网 第三章 通信网路设计基础课件

1、第三章 通信网路设计基础 3.1 通信网路结构设计基础 3.2 网路流量设计基础 3.3 可靠性理论基础 通信网是一个由多个系统、设备、部件组成的复杂而庞大的整体，要求设计人员应掌握网路理论基础和网路分析计算方法，主要包括： （1）网路结构设计必备的图论基本概念和网路结构优化基本知识。 （2）网路流量设计必备的排队论基础知识和一些网路性能指标的计算。 （3）通信网可靠性设计必备的可靠性数学基本知识，通信网可靠性的研究基本情况和基本概念。3.1 通信网路结构设计基础 通信网规划设计中第一层次的问题就是通信网的拓扑结构。通信网是由终端节点、交换节点和传输链路组成的，从数学模型来看，这就是一个图论的

2、问题。一、图论简介 图论是现代组合数学的一个分支，它研究人们在自然界和社会生活中遇到的包含某种二元关系的问题和系统，并把这种问题或系统抽象为点和线的集合，用点和线相互连接的图来表示。 如果边ek与点对（vi,vj）相对应，则称vi,vj是ek的端点，记为 ek=（vi,vj） 称点vi,vj是与边ek关联。 图可用几何图形来表示，但是一个图所对应的几何图形不是唯一的。 （2）有向图和无向图 如果图G=(V,E)的任一边ek都对应一个有序点对，则称图 G为有向图；如果ek对应的是无序点对（vi,vj），则称G为无向图。 （4）链路、路径、回路 若有图 G=(V,E)，其中k（=2）条边和与之关联

3、的点依次排成点和边的交替序列，则称该序列为链路；如果链路中不出现重复的边，则称为路径；如果路径的起点和终点重合，则称为回路。 （5）连通图与非连通图 若图G中任意两点之间至少存在一条路径，则称图G为连通图，否则称为非连通图。非连通图总可以分成几个分离的部分。 通信网络研究中一般只考虑连通图。 （6）图的连通性 定义与某点相关联的边数为点的度数，记为d(vi),若为有向图，d+(vi) 表示离开vi或从vi射出的边数； d-(vi)表示进入vi或射入vi的边数。图3.1 5阶完全图 b.正则图：所有点的度数均相等的连通图称为正则图。d(vi)=常数。 正则图的连通性最为均匀，它是取得一定连通性边

4、数最少的图。 正则图如图3.2所示。 c.子图：若图A的点集和边集分别为图G的点集和边集的子集，则称图A是G的子图。表示如下： 若 ，且 ，则称A是 G的真子图。 2.树 （1）树的定义与性质 一个无回路的连通图称为树。树中的边称为树枝。 树具有如下性质： 具有n个点的树共有n-1个树枝； 树中任意两点之间至存在一条路径； 树是连通的，但去掉任一条边则不连通。 树无回路，但增加一条边可得一回路。 除单点树外，树至少有两个端点度数为1。 （2）图的支撑树 若树 ，且A包含G的所有点，则称A是G的支撑树或生成树。 只有连通图才有支撑树，一个连通图至少有一棵支撑树。 3.图的矩阵表示 （1）关联矩阵

5、 关联矩阵是表达点与边关联的矩阵。可分为无向图和有向图两种关联矩阵。 给定图 G=（V，E），V=v1 ,v2 ,vn , E=e1 ,e2 ,em ， 用矩阵的行标号i表示图G的顶点下标，用列标号j表示G的边的下标，可构造一个nm 矩阵,既 M（G）=mij nm 其中 无向图 vi与ej关联vi与ej不关联v3v2v4v5v2v1v1v4v3e3e5e4e2e1e7e6e5e4e3e2e1e6图3.3 矩阵例题图(a) G1(b) G2 从M(G1)和M(G2)可知：每行中非零元素的个数等于该点的度数。 M(G1)的每一列元素之和为2。 M(G2)的每一列元素之和为0。 v1v2v3v4v

6、5 v1 v2 v3 v4 v5v1v2v3v4v1 v2 v3 v4 对无向图，邻接矩阵是对称的，即且对角线元素为0，每行或每列上1的个数则为该点的度数。 对有向图，对角线元素为 0，但不一定对称。 （3）权值矩阵 对具有n个点的简单图G，其权值矩阵为 其中 vi到vj有边vi与vj无边i=j 无向图的权值矩阵是对称的，对角元素为 0。有向图的权值矩阵不一定对称，但对角元素全为0。 二、路径选择 路径选择和路径优化是进行通信网路结构设计和选择路由时必须考虑的问题，即如何确定能够连接所有城市并使线路费用最小的网路结构；如何选择通信路由，怎样确定首选路由和迂回路由。 1.最小支撑树 连通图的支撑

7、树不止一个。若要在 n个顶点之间建立连通图，至少要有 n-1条边来连接这 n个顶点，在满足一定条件下的权值之和为最小的支撑树叫做最小支撑树。寻找最小支撑树是一个常见的优化问题，可分为两种情况：无限制条件和有限制条件。 （1）无限制条件 a.Kruskal方法：简称K方法，其步骤如下： K0：将连通图G中所有的边ei按权值非减次序排列。 K1：取权值最小的边作树枝，再按 K0的次序选边为树枝。 K3：直到n个点的图选出n-1条边结束。 例2： 要建设连接图 3.4所示的五个城镇的线路网，图上所标权值为两城镇之间的距离，要求用 K方法找出连接这五个城镇线路费用最小的网路结构图。3v5v4v3v2v

848.510图3.4 五个城镇的地图 b.Prim方法：简称P方法，其步骤如下： P0：任取一点vi，作子图G1=vi,比较G1到G-G1中各边的权值dij，取最小的，把所连的点vj并入G1中，得G2=vi，vj。 P1：对已得到r-1个点的子图Gr-1，比较Gr-1中各点到G-Gr-1中各点所有边的权值，取最小的，把所连的点vjr并入G1中，得 Gr=vi，vj，vjr。 P2：若r0，当k=0时： 当系统进入稳定状态时，状态概率与时间无关，有：（3.17）（3.18） 由式（3.1）和（3.18）可得稳态方程： 令 ，可得：（3.19） 求得：（3.20） 排队系统

9、的系统方程可以用状态转移图来表示，见教材图3.23所示。 从状态转移图可知：在稳定状态下进某状态的概率等于离开改状态的概率，因此可以从状态图可以直接写出方程： 排队系统的指标如下： a.平均队长 （3.21） b.平均等待时间 顾客在系统内停留的平均时间 为平均等待时间与平均服务时间之和。（3.23）（3.22） c.系统效率 由于单窗口系统m=1，所以系统效率就是系统内有顾客的概率，即： 可知， 排队系统的指标均取决于排队强度 。三、 排队系统 对于该排队系统，每个窗口的服务率均为 ，服务时间和顾客到达时间间隔均为指数分布。 令系统内顾客数k作为系统的状态变量，此时系统的状态转移如教材图3.

10、25所示。 根据状态转移图可得系统稳态方程：（3.24） 由于 ，令 ，得：（3.25）（3.26）四、 排队系统 令式 和 中n=m，可得：（3.26）（3.26）（3.27） 式中 ，是电话系统的流入话务量强度。 是单位时间内的平均呼叫次数， 是平均每次呼叫的时间。 a.平均队长（3.28） b.顾客被拒绝的概率 这就是话务理论中爱尔兰呼损公式。（3.29） c.系统效率（3.30）3.3 可靠性理论基础一、可靠性数学概要 可靠性数学是可靠性理论的基础。一个产品的可靠性定义：该产品在给定条件下和规定时间内，完成规定功能的能力。产品丧失了这种能力，称为出现了故障。 可靠性研究的对象分为两大类

11、：可修复产品和不可修复产品。 1.不可修复系统的可靠性 不可修复系统的可靠性可以用可靠度、不可靠度、平均寿命来描述。 （1）单部件系统 a.可靠度 可靠度：产品在给定条件下和规定时间内完成规定功能的概率，用R(t)表示。 若用一非负随机变量x表示产品的寿命，则可靠度R(t)定义为： 即产品在0，t时间间隔内不失效的概率。 因此，为了得到可靠度，必须首先知道该产品的寿命分布函数。（3.31） 对于指数分布的寿命分布函数，可以表示为： 则可靠度：（3.32）（3.33） b.不可靠度 就是不可靠度。 c.产品的平均寿命 产品寿命x的密度函数为 （3.34） 则产品的寿命： （2）串联系统 负责系统

12、往往由多个器件、部件或子系统组成。常见的形式有串联、并联和混合等。（3.35） 设串联系统由n个部件组成，各部件相互独立，当n个部件有一个失效时，整个系统就失效。 设各个部件的寿命为 ，可靠度为 。该串联系统的寿命x是n个部件的寿命 中最小值。 （3.36） 可得：（3.37） 当 时，有： 串联系统的平均寿命： （3.39）（3.38） 当 时，有：（3.40） （3）并联系统 设并联系统由n个部件组成，各部件相互独立，当n个部件全部失效时，整个系统就失效。 设各个部件的寿命为 ，可靠度为 。该并联系统的寿命为： （3.41）（3.42）（3.43）当 时，有：（3.44） 2.可修复系统的

13、可靠性 可修复系统的可靠性可以用可用度A、不可用度 U=1A、平均故障间隔时间MTBF和平均故障修复时间MTTRL来表述。 可修复系统可用二值函数x(t)来表述： 则： 是系统在t时刻处于正常状态的概率，称为系统在t时刻的瞬时可用度。 若极限 存在 ，则称A为系统的稳态可用度。 （3.45） （1）单部件系统的可用度 用X表示部件的寿命，用Y表示部件出现故障后的修复时间，设X、Y服从指数分布： 、 分别为部件的失效率和修复率。 （3.46）（3.47） 若t=0时刻系统处于正常运行状态，则 若t=0时刻系统处于故障状态，则（3.48）（3.49） 当 时，可得系统的稳态可用度： 为MTBF，

14、为MTTR，故： （3.50） （2）串联系统的可用度 对于串联系统，只要一个部件失效，该串联系统就失效。 串联系统t时刻的瞬时可用度： （3.51） 则串联系统的可用度： 平均故障间隔时间：（3.52）（3.53）二、通信网的可靠性 1.通信网的可靠性定义 在人为或自然的破坏作用下，通信网在规定条件下和规定时间内的生存能力。 通信网的生存或规定功能应从连通性和性能指标两方面考虑。 2.通信网的连通性 通信网的连通性越好，可靠性就越高。图的连通性可以从两个指标进行讨论。 连通度 ：使图成为不连通图至少需去掉的节点数。 结合度 ：使图成为不连通图至少需去掉的边数。 对n个点、m条边的连通图，有： 称为网的抗毁性，或网的冗余度。 越大，网络的可靠性越高。 3.通信网的可靠性设计 要在满足给定的可靠性指标的条件下，寻找最经济的网络结构。 一般从构成网络部件的可靠性、网路的拓扑结构、路由选择方式等方面来进行考虑。 （1）网路部件的可靠性 提高通信网的可靠性首先应尽量