通信网规划理论.ppt

通信网规划理论,制作人：孙青华,第二章 电信网规划的基础知识,3,第二章 电信网规划的基础知识,第一节 图论基础知识 第二节 随机服务系统及其在电信中的应用 第三节 业务预测的基本方法 第四节 流量预测的基本方法 第五节 电信网规划中的评价准则 第六节 电信网规划中的财务经济评价指标及经济分析方法 第七节 多目标方法及其应用 第八节 智能算法及其应用,4,电信网规划的过程：,对业务量、发展动向、趋势和前景等进行预测,提出电信网发展规划,实施规划方案,规划评价,规划调整,优化方案,确定规划目标,5,本章目的,通过本章介绍的一些定量分析方法，掌握电信网规划的一般方法。为进一步的进行实际的规划工作奠定基础。 本章的内容涉及： 图论 经济计量学 预测学 智能理论,6,第一节 图论基础知识,主要应用领域： 传输网络 电路理论 编码理论 可靠性理论 集成电路设计及计算机领域,7,第一节 图论基础知识,网络规划简介 网络中各最短连接方法 电信网中局、站间最短路的算法 网络流及其算法 电信网的可靠性,8,2.1.1 网 络 规 划 简 介,网络：电信网络、计算机网络、运输服务网络、 能源和物质分派网络、人际关系网络等等。,网络规划就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益,9,2.1.1 网 络 规 划 简 介,网络规划与图 网络规划问题的例子 图与网路分析,10,2.1.1 网 络 规 划 简 介 网络规划与图,网络：数学模型、数学结构 - 图,从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为（最）优化 (Optimization) 问题,运筹学（Operations Research） 广义：管理科学（OR/MS)、系统科学/工程 狭义：最优化 连续优化：数学规划（线性规划、非线性规划等） 离散优化：组合优化（网络优化等）、整数规划等 不确定规划：随机规划、模糊规划等,方法之一：研究与（赋权）图有关的最优化问题,11,2.1.1 网 络 规 划 简 介,梁雄健、李鲁湘，电信网规划，人民邮电出版社 马永源、马力，电信规划方法，北京邮电大学出版社 谢金星 、邢文训，网络优化 ，清华大学出版社，2000年8月。 Ahuja, R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993: Englewood Cliffs, New Jersey.,内容：网络规划（优化）模型、算法及应用,参考书,12,电信网管理问题是一个系统工程问题,任何一个通信管理措施的实施，都会引起整个电信网络流量的重新分布！,改为单向通行,引起的流量变化,引起的速度变化,通行能力,流量,流量时间分布,早高峰 晚高峰,17,流 量 空 间 分 布,2.1.1 网络规划简介,网络规划问题的例子,19,网络规划问题的例子,例2.1.1 电信网络规划中的最短路问题（SPP-Shortest Path Problem） 从甲电信局到乙电信局要建设一条通信线路，从甲电信局到乙电信局有多种可选择的建设路线，应选择种建设方案，使通信线路最短？,20,网络规划问题的例子,例2.1.2 通信网规划中通信线路的连接问题 某一地区有若干个主要城市，现准备修建信息高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经信息高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建信息高速公路的成本，那么应如何决定在哪些城市间修建信息高速公路，使得总成本最小？,网络优化问题的例子,例2.1.3 路由方案(Transportation Problem) 有M个信息源，现在需要将信息从M个信息源发送到N个节点. 假定M个信息源的信息量和N节点接收的信息量已知，单位信息从任一节点到任一节点的信息传输费用已知，那么如何安排路由方案可以使总传输成本最低？,网络优化问题的例子,例2.1.5 中国邮递员问题(CPP-Chinese Postman Problem) 一条信息将走遍网络中的所有结点,最后返回起始点。请设计一条最短的信息回路(从起点出发，经过网络中的每一条线路至少一次，最后返回起点)？由于这一问题是我国复旦大学 管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.,网络规划问题的例子,例2.1.6 (TSP-Traveling Salesman Problem) 一条信息将走遍网络中的所有结点,最后返回起始点。请设计一条最短的信息回路(从起点出发，经过网络中的每一节点恰好一次，最后返回起点)？这一问题的研究历史十分悠久，通常称之为旅行商问题.,电信网规划问题的例子,网络优化：网络流（Network Flows),特点： （1）与图形有关，或易于用图形方式表示 （2）优化问题：从若干可能的安排或方案中寻求某种意义下的最优安排或方案,2.1.1 网络规划简介,图与网路分析,26,图与网络 定义,从图论的观点看，网是由节点集V=v1,v2,vn和边链路的集L=l1,l2,lm组成，图表述网的模型称为图（Graph），记为G(V,L),27,图与网路的基本概念,图与网路 节点 (Vertex) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 节点间的连线，表示有关系 一般用 eij 表示 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V=v1,v2, vn 边集E=eij ,网路 (Network) 边上具有表示连接强度的权值，如 wij 又称加权图(Weighted graph),自环,平行边(parallel edges),28,无向图与有向图,弧 边 关联边 相邻(adjacent)节点 链(link) 圈(loop),既没有自环也没有平行边的图称为简单图(simple graph) 在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为 d ；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(even graph),29,无向图与有向图,有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为 d 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant vertex) 图中奇点的个数总是偶数个 走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 偶图一定存在欧拉回路(一笔画定理) 无向图中，若任意两点间至少存在一条路径，则称为连通图(connected graph)，否则为非连通图( discon-nected graph)；非连通图中的每个连通子图称为成分 (component),2.1.2 网络中各端点的最短连接方法,最小生成树算法,31,最小生成树,多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图,任两点之间有且只有一条路径的图称为树(tree)，记为T 树的性质： 最少边的连通子图，树中必不存在回路 任何树必存在次数为 1 的点 具有 n 个节点的树 T 的边恰好为 n1 条，反之，任何有n 个节点， n1 条边的连通图必是一棵树,32,图的生成树,树 T 是连通图 G 的生成树(spanning tree)，若 T 是 G的子图且包含图 G 的所有的节点,如何找到一棵生成树 深探法(depth first search)：任选一点标记为 0 点开始搜索，选一条未标记的边走到下一点，该点标记为 1，将走过的边标记；假设已标记到 i 点，总是从最新标记的点向下搜索，若从 i 点无法向下标记，即与 i 点相关联的边都已标记或相邻节点都已标记，则退回到 i 1 点继续搜索，直到所有点都被标记 广探法(breadth first search)：是一种有层级结构的搜索，一般得到的是树形图,33,最小生成树（最小部分树）,例2.1.2 通信网规划中通信线路的连接问题 某一地区有若干个主要城市，现准备修建信息高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经信息高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建信息高速公路的成本，那么应如何决定在哪些城市间修建信息高速公路，使得总成