网络规划设计理论基础.pdf

通信网是由多个系统、设备、部件组成的复杂而庞大的整体，为了寻求一种既能够满足 各项性能指标要求又节省费用的设计方案，要求设计人员应掌握相当的网络理论基础知识和 网络分析的计算方法，如通信网所涉及的数学理论、优化算法、网络的分析方法与指标计算 方法等。 通信网的拓扑结构在通信网设计中是一个很重要的问题，它不但影响网络的造价和维护 费用，而且对网络的可靠性和网络的控制及规划起着重要的作用。所以，对网络拓扑结构的 研究是通信网规划和设计中第一层次的问题。通信网的结构是在不断发展的，但传统的网都 是转接式的，包括电路转接和信息转接，是由交换节点和传输线路构成的网络。从数学模型 来说，这是一个图论的问题。 通信网的可靠性是十分重要的。可靠性不高的通信网容易出现故障。因此，在通信网的 规划、设计和维护中，可靠性是一项重要的性能指标。 通过本章的学习，应掌握和理解图论在通信网规划和设计中的应用思想，熟悉最短路径、 最大流等常用计算方法，并熟悉通信网可靠性指标。 2.1 图论基础 2.1.1 图的概念 图论是离散数学的一部分，是现代应用数学的一个分支。离散数学以研究离散量的结构 和相互间的关系为主要目标，其研究对象一般是有限个或可 数个元素。图论则专门研究人们在自然界和社会生活中遇到 的包含某种二元关系的问题或系统。它把这种问题或系统抽 象为点和线的集合，用点和线相互连接的图来表示。图 2.1 就是这样一个图，通常称为点线图。图中的点和线可以代表 通信网中的交换节点和传输线路。图论就是研究点和线连接 关系的理论。近年来，随着计算机的广泛应用，图论得到迅 速发展。在通信网的规划、设计与优化中，图论可以用于确 定最佳网络结构，进行路由选择，分析网络的可靠性等。 图2.1 图的概念 1．图的定义 设有节点集 V = {v , v ,…,v }和边集 E = {e , e ,…,e }，当存在关系R ，使 V × V → E 成立 1 2 n 1 2 m 时，则说由节点集 V 和边集 E 组成图 G，记为 G = ( V, E) 。 关系R 可以说成对任意边 e ，有 V 中的一个节点对(v , v )与之对应。 图 G 中的 V 集可任 k i j 24 通信网理论与应用（第2 版） 意给定，而E 集只是代表 V 中的二元关系。对v ∈ V 和 v ∈ V，当且仅当v 对 v 存在某种关 i j i j 系时（如邻接关系）才有某一个 e ∈ E 。如果有一条边e 与节点对(v , v )相对应，则称 v , v k k i j i j 是 e 的端点，记为e = (v , v )，称点v , v 与边 e 关联，称 v 与 v 为相邻节点。若有两条边与 k k i j i j k i j 同一节点关联，则称这两条边为相邻边。 例 2.1 在图2.2 中，V={v , v , v , v } ，E = {e , e , e , e , e , e }。 1 2 3 4 1 2 3 4 5 6 其中 e = (v , v ) , e = (v , v ), e = (v , v ) 1 1 2 2 1 3