《通信网技术基础 普通高等教育“十一五”国家级规划教材 教学课件 ppt 作者 唐宝民 江凌云 第11章 通信网理论分析》由会员分享，可在线阅读，更多相关《通信网技术基础 普通高等教育“十一五”国家级规划教材 教学课件 ppt 作者 唐宝民 江凌云 第11章 通信网理论分析（189页珍藏版）》请在金锄头文库上搜索。
1、第11章 通信网理论分析,11.1 图 论 基 础 11.2 最短路径算法 11.3 排队论基础 11.4 电路交换网分析 11.5 分组交换数据网分析 11.6 下一代网络性能分析 11.7 多址接入系统的分析 11.8 传输网性能分析,11.1 图 论 基 础,11.1.1 网络和图,1图的定义 设有端集：V = v1，v2，vn 边集：E = e1，e2，em 当边集E是端集V中两个元产生关系R时，,则V和E组成图G，即 G = V，E 由上述定义可知，图G中的V集可任意给定，而E集只是代表V集中两个元的关系。 当Vi对Vj有某种关系R，为邻接关系er时有：erE，每一个er所对应的两个
2、端Vi和Vj称为与er有关联的端，存在er的两个端称为邻接端。,根据端间关系的性质，可分为有向图和无向图，当Vi对Vj有某种关系等价于Vj对Vi有某种关系，就称该图为无向图，反之则称为有向图。 图是集合V及其关系集E的综合V，E，集合论中的许多概念都可以移植过来。,若图A的端集和边集分别是图G的端集和边集的子集，则图A是图G的子图，表示为 A G,若A,G 但AG，则称A是G的真子图；若A,G，,A，则必有A = G。,且G,2图的运算 设A，B为任意集合。 AB称为A与B的并集（union set），定义为 AB = x | xAxB 称为并运算。 AB称为A与B的交集（intersecti
3、on set），定义为 AB = x | xAxB 称为交运算。 AB称为A与B的差集（difference set），定义为 AB = x | xAxB 称为差运算。 A称为A的补集（complement set），定义为 A = UA = x xA 称为补运算，它是一元运算，是差运算的特例。,说明图的运算的示意图如图11.1所示。,图11.1 图的运算,（1）并图 设图Ga、Gb如图10.1（a）和（b）所示，Gc如图10.1（c）所示。 从图中看出，Gc中的端集和边集分别是Ga和Gb中的端集和边集的并，称图Gc是Ga和Gb的并图。 记为Gc = GaGb 对于边集和端集则有 Vc = V
4、aVb E = EaEb （2）交图 Gd如图10.1（d）所示，则Gd是Ga和Gb的交图，Gb是Ga和Gb的公共部分，同时有 Vd = VaVb Ed = EaEb,（3）差图 Ge如图10.1（e）所示，这是从Ga中去掉Ga和Gb的共有边和共有端，但保留未去掉的边关联的端。 Ge是Ga和Gb的差图。 记为Ge = GaGb （4）环和图 Gf如图10.1（f）所示，这是从GaGb中去掉Ga和Gb的共有边。 Gf是Ga和Gb的环和图。 记为Gf = Ga,Gb 一般来说存在GaGb = GaGaGb 若GaGb = f = 空图，则GaGb = Ga+Gb，称为它们的直和。 若Gb,Ga =
5、 GaGb，称为它们的直差。,11.1.2 图的矩阵表示,射出边,射入边,1图的关联阵表示 关联阵是表达图的端与边的关联性的矩阵。 若图含有m条边，n个端，则图的关联阵A0是行数为端数，列数为边数的nm阵， A0 = aijnm 对于无向图则有,对于有向图而言，则有,关联矩阵计算用书如图11.2所示，对于如图11.2所示的有向图，其关联矩阵可表示为：,图11.2 关联矩阵计算用图,从图的关联矩阵可以进一步来计算图的生成树的数量。 连通图的生成树的数量可以用以下公式来表示：,（11.1） 式中A是连通图的关联矩阵，AT是A阵的转置。,即此图有生成树21棵。 以上所讨论的图为有向图，对于无向图，可
6、以在图上任意加箭头，得到相应的有向图，这样就可求得无向图的生成树的数目。,以图11.2为例，关联阵A为式（11.1）所示，生成树数目可以由上式算得：,2图的邻接阵的表示 图也可以用端与端之间的关系矩阵，即邻接阵来表示，邻接阵的行和列都与图的端相对应。对于一个有几个端的图，邻接阵是一个nn的方阵，即,其中,对于图11.2所示的有向图，其邻接阵为,（11.2） 对于无向图，则有 cij = eij 因此，无向图的邻接阵是一个对称阵。,1树和生成树 树是图论中一个十分重要的概念，在网络的组播，路由选择中都有着广泛的应用，下面说明树的定义以及树的求法。 树定义为一个不包括环路的连通图，它具有以下性质。
7、 树是无环的连通图，当对于任何不同的节点i和j都有一个从i到j的路由时，图是连通图。 树是最小的连通图，即树中去掉任一边就成为非连通图，失去了连通性，所以是最小的连通图。 若树有m条边及n个端，则有 m = n1 这可用数学归纳法来证明。因此，树可定义为有n个端，n1条边的连通图。,树的例子如图11.3所示。,图11.3 树的例子,生成树是树中的重要一类，下面说明它们的定义。 设T是连通图G的子图。 T,G，若T含有G的所有端，则称T是G的生成树，也就是说生成树是覆盖连通图所有端的树。 只有连通图才有生成树，反之，有生成树的图必然是连通图。,对于图中的某一生成树而言，生成树上的边称为树枝，非树
8、枝的边称为连枝，生成树就是树枝集，连枝的边集称为连树集或树补。 在通信网的设计过程中，常涉及以下的问题：已给定一组固定的节点，在这些节点上找出一颗使全部链路的权值最小的生成树。这里的链路的权值，可以表示各种度量值，如费用、距离、带宽、时间延迟等。 在某些情况下，所求的树可能还受到某些约束条件的限制，如一个典型的约束就是：必须把节点连通而使它们承载的业务量不致造成链路过载。 求最小生成树的，需要借助于有效的算法，下面首先讨论求解具有最小权但不受任何约束的一颗树的算法，然后找出有约束条件的具有最小权的树。,2无约束的最小生成树,（1）普列姆（Prim）算法,Prim算法具体操作是：从图中任意一个顶
9、点开始，首先把这个顶点包括在MST里，然后在那些其一个端点已在MST里，另一个端点还不是MST里的边，找权最小的一条边，并把这条边和其不在MST里的那个端点包括进MST里。如此进行下去，每次往MST里加一个顶点和一条权最小的边，直到把所有的顶点都包括进MST里。 假设V是图中顶点的集合，E是图中边的集合，TE为最小生成树中的边的集合，则prim算法的步骤如下。, 初始化：U = u0，TE = e0 。此步骤设立一个只有节点u0的节点集U和一个空的边集TE作为最小生成树的初始状态 。 在所有uU，vVU的边(u，v)E中，找一条权最小的边（u0，v0），将此边加进集合TE中，并将此边的非U中顶
10、点加入U中。 如果U = V，则算法结束；否则重复步骤2。可以把本步骤看成循环终止条件。 该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集，V-U看作蓝点集，算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始，并逐渐生长直至U = V，即T包含了C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。,图11.4 PRIM算法用图,依P算法可顺序得,d23最小,d24最小,d21最小,d26最小,d45最小,其邻接阵为,树枝的总长度为,（2）克鲁斯格尔（Kruskal）算法,K算法每次选择n1条边，
11、所使用的准则是：从剩下的边中选择一条不会产生环路的具有最小权值的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K算法分e步，其中e是网络中边的数目。按权值递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 假设W = (V，E)是一个含有n个顶点的连通网， K算法的步骤如下。, 先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根节点，则它是一个含有n棵树的一个森林。 从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将
12、这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之，依此类推。 直至森林中只有一棵树，也即子图中含有n1条边为止。,仍用图11.4来说明此算法。此时,得到：,形成环路，删去这条边。,形成环路，删去这条边。,G7就是最小生成树，如图案11.4所示。,3有约束条件的最小生成树,图11.5 E-W算法用图,E-W算法用图如图11.5所示，图中v1是中心节点，其他2、3、4、5为端站，链路上的权值为dij(i，j=1，2，n)，各个端站的业务量为Fi(i = 2，3，n)，dij的值示于图11.5的边上，各个端站的业务量示于图11
13、.5的端的边上。 约束条件：要求任意一个端所到vj的链路数（边数）小于k，即转接次数小于k 1，边上的总业务量不大于M。 其中k是给定的整数，而M是给定的实数，本例中设k=3，M=50分组/秒，求符合约束条件的最小生成树。,根据公式eij = dij D1i,计算的eij的矩阵为, 矩阵中e34最小，取该边。经核对满足约束条件。 重新计算eij的矩阵得, 取,已有边。,相连后，总业务量 = 10 + 40 + 30 = 80，不符合约束条件。,，,，,，均不符合约束条件。,，满足约束条件，取该边。,，符合约束条件。,，符合约束条件。,，不符合约束条件。, 取, 取, 取, 取, 取,得如图11
14、.6的解。 业务量如图11.6所示，节点上的数字为该节点的业务量。 图11.7是无约束条件下的最小生成树，可以和有约束条件下的生成树加以比较，说明约束条件在求解过程中的影响。,图11.6 有约束条件下的最小生成树,图11.7 无约束条件下的最小生成树,11.2 最短路径算法,11.2.1 Bellman-Ford算法,Bellman-Ford算法（也叫做Ford-Fulkerson算法）是用以求解到固定点的最短路径算法。其原理是：如果某个节点在A和B之间的最短路径上，则该节点到A的路径必定是最短路径；同样，该节点到B的路径也必定是最短路径。,图11.8 Bellman-Ford算法用图,假定希
15、望求得图11.8中节点2到节点6（目的地）的最短路径，为了到达目的地，节点2的分组必须首先通过节点1、节点4或节点5中的某个节点。如果已经知道节点1、节点4、节点5到目的地（节点6）的最短路径分别是3、3、2，这样，如果节点2的分组首先通过节点1，则总距离（也可叫做总费用）就等于3+3 = 6；如果分组首先通过的是节点4，则总距离是1+3 = 4；如果分组首先通过的是节点5，则总距离是4+2 = 6。因此，从节点2到目的地的最短路径就是分组首先通过节点4时所得到的路径。,为了使这种想法形式化，首先固定目的地节点，并定义Dj是节点j到目的地的最小费用（或最短距离）的当前预测值；Cij是节点i到节
16、点j的线路费用。例如，在图11.8中，C12 = C21 = 2，C45 = 3，而从节点i到其自身的费用定义为0（即Cii = 0）。如果节点i到节点k之间没有直接相连的线路，则它们之间的线路费用定义为无穷大。例如，在图11.8中，C15 = C23 = 。根据这些定义，可以求得从节点2到目的地节点（节点6）的最小费用为 D2 =min C21 + D1，C24 + D4，C25 + D5 =min 3 + 3，1 + 3，4 + 2 = 4 因此，节点2到节点6的最小费用为4，且下一个访问的节点是节点4。,在计算节点2到节点6的最小费用时，假定已经知道了节点1、4、5分别到目的地的最小费用。而实际上，这些节点并没有执行同样的计算，它们到目的地的最小费用并不是已知的，因此，为了得到这些节点的最小费用，应用同样
