通信网理论基础第3章.ppt

第3章通信网设计基础 3 1图论结构设计基础3 2路由选择问题3 3站址选择问题3 4通信网的交换技术 3 1图论结构设计基础 通信网设计要求 满足各项性能指标要求节省费用要求设计人员应掌握相当的网络理论基础知识和网络分析的计算方法 如通信网所涉及的数学理论 优化算法 网的分析方法与指标计算方法等 通信网的拓扑结构在通信网设计中的作用 影响网的造价和维护费用对网络的可靠性和网络的控制及质量起着重要的作用对网络的拓扑结构的研究是通信网的规划和设计中第一层次的问题 通信网的结构传统的网都是转接式的 是由交换节点和传输线路构成从数学模型来说这是一个图论的问题 一 图的概念图论 是离散数学的一部分 是现代应用数学的一个分支 离散数学以研究离散量的结构和相互间的关系为主要目标 其研究对象一般是有限个或可数个元素 图论 图论专门研究人们在自然界和社会生活中遇到的包含某种二元关系的问题或系统 它把这种问题或系统抽象为点和线的集合 用点和线相互连接的图来表示 通常称为点线图 图论就是研究点和线连接关系的理论 通信网中 点 交换节点线 传输链路图论在通信网的设计中的应用 1 确定最佳网路结构 2 进行路由选择 3 分析网路的可靠性等 1 图的定义设有端点集V v1 v2 vn 和边集E e1 e2 em 当存在关系R 使V V E成立时 则说由端点集V和边集E组成图G 记为G V E 关系R 指对任一边ek 有V中的一个点对 vi vj 与之对应 此时 a 称vi vj是ek的端点 记为ek vi vj b 称点vi vj与边ek关联 且称vi与vj为相邻点 c 若有两条边与同一端点关联 则称这两条边为相邻边 对vi V vj V 当且仅当vi对vj存在某种关系时 如邻接关系 才有某一个ek E 或有两个或更多的ek E对应vi和vj 一个ek只能对应一点对 vi vj 一个图可以用几何图形来表示 但所对应的几何图形不是唯一的 图的几何图形 2 图的相关概念无向图 设图G V E 当vi对vj存在某种关系R等价于vj对vi存在某种关系R 则称G为无向图 即图G中的任意一条边ek都对应一个无序点对 vi vj 记为ek vi vj vj vi 一条边 有向图 设图G V E 当vi对vj存在某种关系R不等价于vj对vi存在关系R 则称G为有向图 即图G中的任意一条边都对应一个有序点对 vi vj 即ek vi vj vj vi 两条边 其边的方向为vi vj 无向图 有向图 空图 若图G中的端集V是空集 则不可能有边集E 这样的图称为空图 孤立点图 若图G中的边集E为空集 点集V不空 但各端间无关系 则称图G为孤立点图 有限图 若图G中的端集V和边集E为有限集时称图G为有限图 实际上我们通常所遇到的都是有限图 无限图 若图G中的端集V和边集E中有一个为无限集时称图G为无限图 有权图 设图G V E 如果对它的每一条边ek或每一个端点vi赋以一个实数pk 则称图G为有权图或加权图 pk称为权值 边和端的权值可以不止一个 可以是正值或负值 在实际问题中 代表不同的含义 二 图的连通性 一 相关概念1 自环 重边和度数自环 若与一个边er相关联的两个端是同一个端点 则称边er为自环 重边 在无向图中与同一对端点关联的两条或两条以上的边称为重边 在有向图中与同一对端点关联且方向相同的两条或两条以上的边称为重边 没有自环和重边的图称为简单图 在实际问题中 重边 一条边一条无向边 两条方向相反的有向边 自环示意图 端的度数 与某端相关联的边数可定义为该端的度数 记为d vi 若为有向图 d vi 表示离开或从端vi射出的边数 即端vi的出度 d vi 表示进入或射入端vi的边数 即端vi的入度 d vi d vi d vi 度数的两个性质 1 对于有n个端 m条边的图 必有 2 任何图中 度数为奇数的端的数目必为偶数 或零 即V1 奇度数端集 2 链 径和回路边序列 有限条边的一种串序排列称为边序列 边序列中的各条边是首尾相连的 在边序列中 可以有重复的边和重复的端 链 chain 没有重复边的边序列叫做链 但在链中可以有重复的端 链可分为开链和闭链 开链 起点和终点不是同一端的链 通常所说的链指的是开链 闭链 起点和终点重合的链 链的长度 链中边的数目称为链的长度 径 path 既无重复边 又无重复端的边序列叫做径 在一条径中 除了起点和终点的端的度数为1外 其他端的度数都是2 回路 circuit 起点和终点重合的径称为回路 或称为圈 回路是每个端点度数均为2的连通图 回路是最小闭链 对于有向图 可有相仿的定义 只是在链中 相邻二条边对共有端而言 前面的边必须是射出边 而后面的是射入边 二 图的连通性1 连通图 设图G V E 若图中任意两个点之间至少存在一条路径 则称图G为连通图 否则称G为非连通图 非连通图总可以分成几个部分 每一个部分都是原图的一个最大连通子图 这里最大是指若在最大连通子图上再加上原图的任意一个元素 一条边或一个端 都将使子图成为非连通图 2 环路 不重边的回路和回路的并称为环路 环路可以是连通的 也可以是非连通的 连通的环路 为一单一回路 即最小闭链 或有公共端 而无公共边的回路的并 即有重复端的闭链 非连通的环路 为无重复端的回路的并 即分离的回路的并 环路中每个端点的度数均为偶数 闭链和回路都是环路 连通的 但环路不一定是闭链和回路 当环路是非连通时 环路 1 2 3 4 1 3 1 2 2 4 等 1 4 3 4 不是环路 3 子图 真子图和生成子图从原来的图中适当地去掉一些边和端点后得到子图 设有图G V E 和G V E a 若V V E E 即G 的所有的端和边都属于图G 则称G 是G的子图 记为G G b 若V V E E 即子图G 不包含G的所有边 则称G 是G的真子图 记为G G c 若V V E E 即子图G 包含G的所有端 则称G 是G的生成子图 4 最大连通子图 若图G 是图G的一个连通子图 但再加上一个属于原图G的任何一个其他元素 图G就失去了连通性 成为非连通图 则图G 叫图G最大连通子图 最大连通子图并不是极大连通子图 三 几种特殊的图1 全连通图 任意两端间都有边的无向图称为全连通图 或称完全图 一个无重边和自环的全连通图 简单图 亦为正则图 的边数m和端数n之间有固定关系 全连通图是连通性最好的图 2 正则图 所有端的度数都相等的连通图称为正则图 即d vi 常数 i 1 2 n 正则图的连通性最均匀 也就是取得一定连通性的边数最少的图 无重边和自环的全连通图是正则图 其端的度数d vi n 1 其中n是图的端数 但正则图不一定是全连通图 全连通图 a d vi 2 b d vi 3 3 汉密尔顿图 Hamilton H图 当图中至少存在一个包含所有端的回路 这个图称为汉密尔顿图 简称H图 该回路称为汉密尔顿回路 一个汉密尔顿图可以有几个不同的汉密尔顿回路 汉密尔顿回路是 e1 e2 e3 e4 e5 H图 四 树 tree 1 定义a 树 tree 任意两端间有且只有一条径的连通图称为树 b 树枝 branch 树中的边称为树枝 c 树干 trunk 若树枝的两个端点都至少与两条边关联 则称该树枝为树干 d 树尖 若树枝的一个端点仅与此边关联 则称该树枝为树尖 e 树叶 leaf 度数为1的端点称为树叶 leaf f 有根树 若指定树中的一个点为根 则称该树为有根树 2 树的性质 树无回路 但增加一条边便可以得到一个回路 树是最小连通图 去掉树中的任一条边便不连通 若树有m条边 n个端 则有m n 1 即有n个端的树共有n 1条树枝 除了单点树外 任何一棵树中至少有两片树叶 2 图的生成树 支撑树 生成树的定义 设G是一个连通图 T是G的一个生成子图 且又是一棵树 则称T是G的一棵生成树 一个连通图至少有一棵生成树 树枝集 图G的生成树上的边组成树枝集 连枝 生成树之外的边称为连枝 连枝的边集称为连枝集或称为树补 具有n个端 m条边的连通图 生成树T有n 1条树枝和m n 1条连枝 图G的阶 连通图G的生成树T的树枝数称为图G的阶 记为 如果图G有n个端 则 G n 1 图G的空度 连枝集的连枝数称为图G的空度 记为 当G有m条边时 有 G G T m n 1m 表示生成树的大小 取决于G中的端点 1 表示生成树覆盖该图的程度 越小 覆盖度越高 0表示图G就是树 2 反映图G的连通程度 越大 连枝数越多 图的连通性越好 0表示图G有最低连通性 即最小连通图 3 生成树的求法 1 破圈法 拆除图中的所有回路并使其保持连通 就能得到G的一棵生成树 2 避圈法 设有n个点的连通图G a 在连通图中任选一条边 及其端点 b 选取第二 三 条边 使之不与已选的边形成回路 c 直到选取完n 1条边且不出现回路 结束 三 图的矩阵表示图的表示方法 1 几何图形 直观 2 矩阵表示 可以存入计算机 并进行数值计算和分析 二者在拓扑上是一致的 也就是满足图的抽象定义 图常用的三种矩阵 关联矩阵 邻接矩阵 权值矩阵 一 完全关联矩阵与基本关联矩阵完全关联矩阵 表示端与边的关联性的矩阵 图G V E 是一个含有n个端 m条边的图 它的完全关联矩阵是以图G的每一个端点为一行 以每一条边为一列所形成的n m矩阵 表示成 aij对于无向图而言 对于有向图而言 i 1 2 n j 1 2 m 举例 图的完全关联矩阵有如下性质 每行中非零元素的个数等于该行所对应端的度数 若某行向量为零向量 则该行所对应的端为孤立点端 对于无自环的图 若为无向图 各列向量元素之和为2 若为有向图 每列向量元素之和为零 对于连通图 完全关联矩阵的秩为n 1 对于非连通图 完全关联矩阵的秩小于n 1 2 基本关联矩阵基本关联矩阵 将完全关联矩阵去掉一行后所得到的矩阵为基本关联矩阵 在实际应用中 去掉的一行通常作为参考点 如电路设计中的接地点等 基本关联矩阵记为 二 邻接矩阵邻接矩阵是表示端与端之间的关系的矩阵 设图G有n个端 m条边 其邻接矩阵是一个n n的方阵 方阵中的每一行和每一列都与相应的端对应 记作 其中对于有向图 对于无向图 特点 1 对于无向简单图 邻接矩阵是一个对称阵 有cij cji 而对于有向图却不一定 2 当图中无自环时 C阵的对角线上的元素都为0 若有自环 则对角线上的元素为1 3 有向图中 C阵中的每行上1的个数为该行所对应的端的射出度数d vi 每列上的1的个数则为该列所对应的端的射入度数d vi 无向图中 每行或每列上1的个数则为该端的总度数 当某端所对应的行和列均为零时说明该端为孤立点端 举例 三 权值矩阵根据权值的含义 权值矩阵可以是实际问题中的距离矩阵 流量矩阵 费用矩阵等 设G为有权图 且是具有n个端的简单图 其权值矩阵为 特点 1 无向简单图的权值矩阵是对称的 对角线元素全为零 2 有向简单图的权值矩阵不一定对称 但对角线元素也全为零 举例 G1 G2 3 2路由选择 通信网设计 1 有线通信网络结构 连接所有的城市并使线路费用最小的网络结构 接通的任意性 经济合理性 求最小生成树 2 通信路由选择 确定首选路由和迂回路由等 接通的快速性 求最短径 路径选择或者说是路径优化 本节只涉及无向简单图的路径优化 一 最小生成树最小生成树 对于一个非树连通图G 可以找到G的若干个生成树 如果该图是有权图 各个生成树的树枝权值之和一般不相同 将其中权值之和为最小的那棵生成树称为最小生成树 最小生成树理论的应用 在通信网中确定连接n个城市并使费用最小的网络结构问题 实质上就是在有n个点的加权连通图中寻找最小生成树的问题 一 无约束条件的情况有两种方法 Kruskal方法 K方法 和Prim方法 P方法 1 Kruskal方法 K方法 Kruskal方法简称K方法 是顺序取边算法 是避圈法求生成树的推广 具体步骤为 1 将连通图G中的所有边ei按权值的非减次序排列 2 选取权值最小的边为树枝 再按 1 的次序依次选取不与已选树枝形成回路的边ei为树枝 如有几条这样的边权值相同则任选其中一条 3 对于有n个点的图直到n 1条树枝选出 结束 例 要建设连接如下图所示的七个城镇的线路网 任意两个城镇间的距离见表3 1 请用K方法找出线路费用最小的网络结构图 设线路费用与线路长度成正比 解 将各城镇间的距离按非减次序列成表3 2 表3 1各城镇间的距离 km 七个城市的地图 表3 2距离非减排列 km 网络总长度为38km 用K方法得到的一个最小费用的网络结构图 2 Prim方法 方法 Prim方法可简称为P方法 是一种顺序取端的算法 它的思路是 任意选择一个节点vi 将它与vj相连 同时使 vi vj 具有的权值最小 再从vi vj以外的其他各点中选取一点vk与vi或vj相连 同时使所连两点的边具有最小的权值 重复这一过程 直至将所有的点相连 就可得到连接n个节点的最小生成树 P方法可用矩阵实现 一般可借助于计算机编程来实现 二 有约束条件的最小生成树某些约束条件 1 某交换中心或某段线路上的业务量不能过大 2 任意两点间经过的转接次数不能过多等 不同的约束条件 算法也不同 一种常用的解决有约束条件的生成树的方法是穷举法 穷举法 先把图中的所有生成树穷举出来 再按条件筛选 最后选出最短的符合条件的生成树 例 1 任意两点间转接次数不能超过3 T1 392 假定C7的通信业务量负载对C3来说过大 则可将C7连到C6上 T2 403 如果C5与C7之间转接次数超过要求 可将C7连至C4上 T3 41 二 指定端到其他各端的最短路径在通信网的网络结构已被确定之后 就要进行路由选择顺序的安排 路由选择顺序 1 首选路由 最短路径 即图论中的端间最短径 可分为两种情况 a 指定端到其他各端的最短径 D算法b 任意两端间的最短径 F算法 2 迂回路由 次短径或可用径 求网中某指定端点到其他各端点的最短路径 通常认为Dijkstra算法是最有效的方法之一 将这一方法简称为D算法 一 D算法的具体实现D算法中用到的几个符号 Gp G Gp wj已知图G V E 将其端集V分为两组 置定端集Gp和未置定端集G Gp Gp 指定端vs到Gp内的所有端的最短路径已计算完 称Gp内的所有端为置定端 称Gp为置定端集 G Gp 指定端vs到G Gp内的端的路径长度是暂时的 随着算法的进行将不断调整 最终使其成为最短径 称G Gp内的所有端为未置定端 称G Gp为未置定端集 在计算过程中 以Gp中的端作为转接点 计算 vs vj 的径长 vj G Gp 若该次计算的径长小于上次的值 则更新径长 否则 径长不变 计算后取其中径长最短的端点 将其划归到Gp中 当 G Gp 最终成为空集 即G Gp时 求得vs到所有其他端的最短路径 wj vs表示与其他端点的距离 在Gp中 wi表示上一次划分到Gp中的端点vi到vs的最短路径 在 G Gp 中 wj表示从vs到vj vj G Gp 仅经过Gp中的端作为转接点 该次所求得的的最短路径的长度 如果vs与vj不直接相连 且无置定端作为转接点 则令wj D算法的步骤1 初始化a 端vs为指定端 对应的置定端集为Gp vs 此时的ws 0 b 其他端都为未置定端 组成未置定端集G Gp 未置定端的wj为暂设值 wj dij vj G Gp s与j直接相连 或wj vj G Gp s与j不直接相连 即wj 表示此次迭代s到j的最短距离的长度 2 计算G Gp中的wj在G Gp中找到一点vj 使vs到vj的距离最小 并将vj划归到Gp 然后 以该点作为此次的转接点 计算并修改 G Gp 中的wj 1 首先从与vs直连的vj中考虑 若 vj与vs直连则将vi划归到Gp中 即新的Gp vs vi 此时Gp的wi dsi 2 以vi为此次的转接点 计算并修改 G Gp 中的wj G Gp中的各个端的最短径可能经vi转接 或不转接 重新对 G Gp 中的wj值计算 取wj 上一次vs到vj的最短路径的暂定值wi 上一次得到的置定端vi的最短路径dij vi vj 的距离 3 选定所有wj 的最小值 并将所对应的vj划归到Gp中 得到新的Gp 重复过程 2 直到Gp G 则算法终止 否则 回到2 2 例3 6用D算法求下图中v1到其他各端的最短路径 解 计算过程及结果列于表3 3及表3 4中 最终路径图如图3 25所示 D算法例题图 表3 3 表3 4 v1到其他各点的最短路径和径长 图3 25v1到其他各点的最短路经 三 任意端之间的最短路径Floyd算法 又简称为F算法 它的解题思路与D算法相同 但使用矩阵形式进行运算 有利于在计算机中进行处理 F算法使用距离矩阵和路由矩阵进行计算 距离矩阵W 是一个n n矩阵 以图G的n个端点为行和列 记为 wij 表示图G中vi和vj两点之间的路径长路由矩阵R 是一个n n矩阵 以图G的n个端点为行和列 记为 rij 表示vi至vj经过的转接点 中间节点 F算法的思路 1 首先写出初始的W阵和R阵 2 接着按顺序将端集中的各个端点逐次作为中间节点 并计算任意两点间的径长 每次计算后 总是以小的径长更新前一次大的径长 若计算所得径长大于或等于上次径长 则不更新 以此不断更新W和R阵 直至所有的端点都计算完 即W中的数值收敛 F算法的具体步骤如下 1 写出图G的初始距离矩阵W0和路由矩阵R0 已知图G n个端点 边长为dij 2 依次将G中的各节点k作为中间节点 求wij的最短路径 k 1 2 n 当k为中间节点时 求第k次的更新矩阵 Wk 为当vk作为转接点时的最短路径长度矩阵 Rk 为当vk作为转接点时 任意两端间经过的转接点矩阵 3 如果k n则返回 2 若k n结束 从Wk和Rk中可以找到任意两端间的最短径和对应的路由 由D算法和F算法求得的最短径是最优解 的求解 步骤 1 当k为中间节点 即k不变 时 wikk 1为第k列列向量 i 1 2 n wkjk 1为第k行行向量 j 1 2 n 2 令i 1 取第k列列向量中的w1kk 1分别与第k行的行向量wkjk 1 j 1 2 n 中的各项相加 得w1kk 1 wkjk 1 j 1 2 n 该值再与第一行的行向量w1jk 1中对应的各项相比较 若前者小于后者 则Wk中的w1jk 1取前者值 即该w1jk 1值更新 否则 不变 3 i i 1 即顺序取第k列列向量中的各项 分别与第k行的行向量wkjk 1 j 1 2 n 中的各项相加 重复 2 的计算 比较 修改过程 直至i n 完成k作为中间节点时的W的修改过程 4 k k 1 k n重复 1 3 步骤 直至k n 算法过程结束 例7 6用F算法求下图中任意点之间的最短路径 解 计算结果如下 1 初始化距离矩阵W0和路由矩阵R0 2 依次以v1 v2 v7为中间节点修改W阵和R阵 结果如下 四 求K条最短路径1 次短径或可用径 当路由上有业务量溢出或发生故障时 需寻找迂回路由 迂回路由应依次选择次最短路径 第三条最短路径等 通常将这一系列可供选择的次短径称为可用径 2 业务量溢出或发生故障的两种情况a 发生在某段或某几段电路上 b 发生在某个或某几个交换节点上 3 可用径的分类A 边分离径 指与最短径无公共边但有公共端的可用径 b 端分离径 指除了起点和终点外与最短径无公共端的可用径 端分离径必是边分离径 边分离径适用于业务量溢出或故障发生在某段或某几段电路上的情况 端分离径适用于业务量溢出或故障发生在某个或某几个交换节点上的情况 4 边分离径和端分离径的求法a 边分离径的求法 在图G中 去掉最短路径中的所有边 用D方法在剩下的图中求出两端间的最短径 即为边分离次短径 依照此方法就可求出一系列边分离径 b 端分离径的求法 在图G中 去掉最短路径中的所有中间端 及其相关联的边 在剩下的图中求出两端间的最短径 即为端分离次短径 依照此方法就可求出一系列端分离径 当剩下的图中两点间不存在路径时 结束 P1 vs v2 vtP2 vs v3 v2 v4 vtP3 vs v5 v6 vt 边分离径 P1与P2 端分离径 P1与P3 P1 P2 P3 一 站址选择的基本概念局所设置 在通信网规划设计中 确定交换局的数目及其位置 局所设置包括 1 在一个用户区域内建一或几个交换中心 2 在若干个交换中心区域内 建一汇接中心 要求 达到各项性能指标且费用最小 就是选择一点 使其到其到其他各点的最短路径之和为最小 总费用也就达到了最小 局所设置的两种方案 1 在已有的几个站点中选择一个站点作为交换中心或汇接中心位置 2 另设新址 本小节主要讨论举例 某县有六个镇 镇之间的连线表示公路 该县要在某镇中或沿公路某处建一个电话交换中心 应如何选择交换中心的位置 方案 1 站址概念示意图 解 如果将交换中心设在某个镇 且各镇所需电路数相同 则该镇至其他各镇的最短距离总和应为最小 如在例7 6中 从最短路径矩阵W7中可算出某点至其他各点最短路径之和 可见 其中v7至其他各点最短路径之和最小 故v7适合作为交换中心的位置 这种情况就是方案 1 一 中位点中位点 从该点到其他各点有最小的网络总费用的点 设有n个用户点 各点的加权系数为pi i 1 2 n 中位点就是使费用为最小的点 其中 di 为各点与中位点之间的距离测度 pi 可代表该用户点的用户数 线路费用系数等 如果设中位点平面坐标为 x0 y0 第i个用户的坐标为 xi yi 则 二 距离测度di01 欧几里得距离 两点间的直线距离适用于无线通信系统 如广播系统的发射台位置 移动通信蜂窝小区基站位置的选择等 2 矩形线距离适用于城市中需要沿街道进行敷设线路的情况 三 单中位点与多中位点单中位点 当用户数比较少 分布范围不太广时 可以只设置一个交换中心 单中位点用来解决设置单一交换中心的问题 同