通信网规划理论.pptx

《通信网规划理论.pptx》由会员分享，可在线阅读，更多相关《通信网规划理论.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1通信网规划理论通信网规划理论电信网规划的基础知识电信网规划的基础知识电信网规划的基础知识电信网规划的基础知识n n第一节 图论基础知识n n第二节 随机服务系统及其在电信中的应用n n第三节 业务预测的基本方法n n第四节 流量预测的基本方法n n第五节 电信网规划中的评价准则n n第六节 电信网规划中的财务经济评价指标及经济分析方法n n第七节 多目标方法及其应用n n第八节 智能算法及其应用2第1页/共34页电信网规划的过程：电信网规划的过程：3对业务量、发展动向、趋势和前景等进行预测对业务量、发展动向、趋势和前景等进行预测提出电信网发展规划提出电信网发展规划实施规划方案实施规划方

2、案规划评价规划评价规划调整规划调整优化方案优化方案确定规划目标确定规划目标第2页/共34页本章目的本章目的n n通过本章介绍的一些定量分析方法，掌握电信网规划的一般方法。为进一步的进行实际的规划工作奠定基础。n n本章的内容涉及：n n图论图论n n经济计量学经济计量学n n预测学预测学n n智能理论智能理论4第3页/共34页第一节第一节 图论基础知识图论基础知识n n主要应用领域：n n传输网络传输网络n n电路理论电路理论 n n编码理论编码理论 n n可靠性理论可靠性理论n n集成电路设计及计算机领域集成电路设计及计算机领域5第4页/共34页第一节第一节 图论基础知识图论基础知识n n网

3、络规划简介n n网络中各最短连接方法n n电信网中局、站间最短路的算法n n网络流及其算法n n电信网的可靠性6第5页/共34页71.1 网网 络络 规规 划划 简简 介介网络：电信网络、计算机网络、运输服务网络、能源和物质分派网络、人际关系网络等等。网网络规划就是研究如何有效地划就是研究如何有效地计划、管理和控划、管理和控制网制网络系系统，使之，使之发挥最大的社会和最大的社会和经济效益效益 第6页/共34页1.1 1.1 1.1 1.1 网网网网 络络络络 规规规规 划划划划 简简简简 介介介介n n网络规划与图网络规划与图n n网络规划问题的例子网络规划问题的例子n n图与网路分析图与网路

4、分析8第7页/共34页91.1 网网 络络 规规 划划 简简 介介 网络规划与图网络规划与图 网络：数学模型、数学结构网络：数学模型、数学结构-图图从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为（最）优化把这种问题称为（最）优化(Optimization)问题问题 运筹学（运筹学（Operations Research）广广义：管理科学（：管理科学（OR/MS)、系、系统科学科学/工程工程 狭狭义：最：最优化化连续优化：数学规划（线性规划、非线性规划等）连续优化：数学规划（线性规划、非线性规划等）离散优

5、化：组合优化（离散优化：组合优化（网络优化等）、整数规划等网络优化等）、整数规划等不确定规划：随机规划、模糊规划等不确定规划：随机规划、模糊规划等方法之一：研究方法之一：研究与（赋权）图有关的最优化问题与（赋权）图有关的最优化问题第8页/共34页101.1 网网 络络 规规 划划 简简 介介梁雄健、李鲁湘，梁雄健、李鲁湘，电信网规划电信网规划，人民邮电出版，人民邮电出版社社马永源、马力，马永源、马力，电信规划方法电信规划方法，北京邮电大学，北京邮电大学出版社出版社谢金星谢金星、邢文训，网络优化、邢文训，网络优化，清华大学出版，清华大学出版社，社，2000年年8月。月。Ahuja,R.K.,Ma

6、gnanti T.L.,Orlin J.B.Network Flows:Theory,Algorithms,and Applications.Prentice Hall,1993:Englewood Cliffs,New Jersey.内容：网内容：网络规划（划（优化）模型、算法及化）模型、算法及应用用参考书第9页/共34页11电信网管理问题是一个系统工程问题电信网管理问题是一个系统工程问题 任何一个通信管理措施的任何一个通信管理措施的实施，都会引起整个施，都会引起整个电信网信网络流量的重新分布！流量的重新分布！第10页/共34页改为单向通行改为单向通行第11页/共34页引起的流量变化引起的流

7、量变化第12页/共34页引起的速度变化引起的速度变化第13页/共34页通行能力流量流量时间分布早高峰早高峰 晚高峰晚高峰第14页/共34页16流流 量量 空空 间间 分分 布布 第15页/共34页1.1 1.1 网络规划简介网络规划简介网络规划问题的例子网络规划问题的例子第16页/共34页18网络规划问题的例子网络规划问题的例子 例例1.1 电电信信网网络络规规划划中中的的最最短短路路问问题题（SPP-Shortest Path Problem）从从甲甲电电信信局局到到乙乙电电信信局局要要建建设设一一条条通通信信线线路路，从从甲甲电电信信局局到到乙乙电电信信局局有有多多种种可可选选择择的的建建

8、设设路路线线，应应选选择择种种建建设设方方案案，使使通通信信线线路路最最短短？第17页/共34页19网络规划问题的例网络规划问题的例子子 例例1.2 通信网规划中通信线路的连接问题通信网规划中通信线路的连接问题 某一地区有若干个主要城市，现准备修建信某一地区有若干个主要城市，现准备修建信息高速公路把这些城市连接起来，息高速公路把这些城市连接起来，使得从其使得从其中任何一个城市都可以经信息高速公路直接中任何一个城市都可以经信息高速公路直接或间接到达另一个城市或间接到达另一个城市.假定已经知道了任意假定已经知道了任意两个城市之间修建信息高速公路的成本，那两个城市之间修建信息高速公路的成本，那么应如

9、何决定在哪些城市间修建信息高速公么应如何决定在哪些城市间修建信息高速公路，使得总成本最小？路，使得总成本最小？第18页/共34页网络优化问题的例子网络优化问题的例子 例例1.3 路由方案路由方案(Transportation Problem)有有M个个信信息息源源，现现在在需需要要将将信信息息从从M个个信信息息源源发发送送到到N个个节节点点.假假定定M个个信信息息源源的的信信息息量量和和N节节点点接接收收的的信信息息量量已已知知，单单位位信信息息从从任任一一节节点点到到任任一一节节点点的的信信息息传传输输费费用用已已知知，那那么么如如何何安安排排路路由由方方案案可可以以使使总总传传输输成成本本

10、最最低低？第19页/共34页网络优化问题的例子网络优化问题的例子 例例1.5 中中国国邮邮递递员员问问题题(CPP-Chinese Postman Problem)一一条条信信息息将将走走遍遍网网络络中中的的所所有有结结点点,最最后后返返回回起起始始点点。请请设设计计一一条条最最短短的的信信息息回回路路(从从起起点点出出发发，经经过过网网络络中中的的每每一一条条线线路路至至少少一一次次，最最后后返返回回起起点点)？由由于于这这一一问问题题是是我我国国复复旦旦大大学学 管管梅梅谷谷教教授授1960年年首首先先提提出出的的，所所以以国国际上称之为中国邮递员问题际上称之为中国邮递员问题.第20页/共

11、34页网络规划问题的例子网络规划问题的例子 例例1.6 (TSP-Traveling Salesman Problem)一一条条信信息息将将走走遍遍网网络络中中的的所所有有结结点点,最最后后返返回回起起始始点点。请请设设计计一一条条最最短短的的信信息息回回路路(从从起起点点出出发发，经经过过网网络络中中的的每每一一节节点点恰恰好好一一次次，最最后后返返回回起起点点)？这这一一问问题题的的研研究究历历史史十十分分悠久，通常称之为旅行商问题悠久，通常称之为旅行商问题.第21页/共34页电信网规划问题的例子电信网规划问题的例子电信网规划问题的例子电信网规划问题的例子 网络优化网络优化：网络流网络流（

12、Network Flows)特点特点：（1）与图形有关，或易于用图形方式表示与图形有关，或易于用图形方式表示（2）优化问题：从若干可能的安排或方案中寻求某）优化问题：从若干可能的安排或方案中寻求某种意义下的最优安排或方案种意义下的最优安排或方案第22页/共34页1.1 1.1 网络规划简介网络规划简介图与网路分析第23页/共34页25图与网络图与网络 定义定义 从图论的观点看，网是由节点集从图论的观点看，网是由节点集V=v1,v2,vn和边链路的集和边链路的集L=l1,l2,lm组成，图表述网的模型组成，图表述网的模型称为图（称为图（Graph），记为），记为G(V,L)第24页/共34页图与

13、网路的图与网路的基本概念基本概念图与网路n n节点(Vertex)n n物理实体、事物、概念物理实体、事物、概念n n一般一般用用 v vi i 表示表示n n边(Edge)n n节点间的连线，表示有节点间的连线，表示有关系关系n n一般一般用用 e eij ij 表示表示n n图(Graph)n n节点和边的集合节点和边的集合n n一般用一般用 G(G(VV,E E)表示表示n n点集点集 VV=v v1 1,v v2 2,v vn n n n边集边集E E=e eij ij 26网路网路(Network)边上具有表示上具有表示连接接强度度的的权值，如，如 wij又称又称加加权图(Weigh

14、ted graph)自自环平行平行边(parallel edges)第25页/共34页无向图与有向图无向图与有向图无向图与有向图无向图与有向图n n弧弧n n边边n n关关联边联边n n相相邻邻(adjacentadjacent)节节点点n n链链(link)(link)n n圈圈(loop)(loop)27相相邻边既没有自既没有自环也没有平行也没有平行边的的图称称为简单图(simple graph)在无向在无向图中，与中，与节点相关点相关联边的数目，称的数目，称为该节点的点的“次次”(degree)，记为 d；次数；次数为奇数的点称奇数的点称为奇点奇点(odd),次数次数为偶数的点称偶数的点

15、称为偶点偶点(even)；图中都是偶点的中都是偶点的图称称为偶偶图(even graph)第26页/共34页无向图与有向图无向图与有向图无向图与有向图无向图与有向图n n有向图中，由节点指向外的弧的数目称为正次数，记为有向图中，由节点指向外的弧的数目称为正次数，记为 d d+，指向该节点的弧的数目称为负次数，记为指向该节点的弧的数目称为负次数，记为 d d n n次数为次数为 0 0 的点称为的点称为孤立点孤立点(isolated vertexisolated vertex)，次数为，次数为 1 1 的点称为的点称为悬挂点悬挂点(pendant vertexpendant vertex)图中奇

16、点的个数总是偶数个图中奇点的个数总是偶数个n n走过图中所有边且每条边仅走一次的闭行走称为走过图中所有边且每条边仅走一次的闭行走称为欧拉欧拉回路回路偶图一定存在欧拉回路偶图一定存在欧拉回路(一笔画定理一笔画定理)n n无向图中，若任意两点间至少存在一条路径，则称为无向图中，若任意两点间至少存在一条路径，则称为连通图连通图(connected graphconnected graph)，否则为，否则为非连通图非连通图(discon-nected graphdiscon-nected graph)；非连通；非连通图中的每个图中的每个连通子图连通子图称为称为成分成分 (componentcompon

17、ent)28第27页/共34页1.2 网络中各端点的最短网络中各端点的最短连接方法连接方法 最小生成树算法第28页/共34页最小生成树最小生成树n n多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图30任两点之任两点之间有且只有一条路径的有且只有一条路径的图称称为树(tree)，记为T 树的性的性质：最少最少边的的连通子通子图，树中必不存在回路中必不存在回路任何任何树必存在次数必存在次数为 1 的点的点具有具有 n 个个节点的点的树 T 的的边恰好恰好为 n 1 条，反之，任何有条，反之，任何有n 个个节点，点，n 1 条条边的的连通通图必是一棵必是一棵树第29页/

18、共34页图的生成树图的生成树n n树 T 是连通图 G 的生成树(spanning tree)，若 T 是 G的子图且包含图 G 的所有的节点31如何找到一棵生成如何找到一棵生成树深探法深探法(depth first search)：任：任选一点一点标记为 0 点开始点开始搜索，搜索，选一条未一条未标记的的边走到下一点，走到下一点，该点点标记为 1，将走，将走过的的边标记；假；假设已已标记到到 i 点，点，总是从最新是从最新标记的点向下搜索，若从的点向下搜索，若从 i 点无法向下点无法向下标记，即与，即与 i 点相关点相关联的的边都已都已标记或相或相邻节点都已点都已标记，则退回退回到到 i 1

19、 点点继续搜索，直到所有点都被搜索，直到所有点都被标记广探法广探法(breadth first search)：是一种有：是一种有层级结构的搜构的搜索，一般得到的是索，一般得到的是树形形图第30页/共34页最小生成树（最小部分树）最小生成树（最小部分树）最小生成树（最小部分树）最小生成树（最小部分树）例例1.2 1.2 通信网规划中通信线路的连接问题通信网规划中通信线路的连接问题 某一地区有若干个主要城市，现准备修建信息高某一地区有若干个主要城市，现准备修建信息高速公路把这些城市连接起来，速公路把这些城市连接起来，使得从其中任何使得从其中任何一个城市都可以经信息高速公路直接或间接到一个城市都可

20、以经信息高速公路直接或间接到达另一个城市达另一个城市.假定已经知道了任意两个城市之假定已经知道了任意两个城市之间修建信息高速公路的成本，那么应如何决定间修建信息高速公路的成本，那么应如何决定在哪些城市间修建信息高速公路，使得总成本在哪些城市间修建信息高速公路，使得总成本最小？最小？n n显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法：32第31页/共34页n nKruskalKruskal 算法：算法：33将将图中所有中所有边按按权值从小到大排列从小到大排列选所剩最小的所剩最小的边加入加入边集集 T是否和前面加入是否和前面加入是否和前面加入是否和前面加入的边构成回路的边构成回路的边构成回路的边构成回路T T 中是否有中是否有中是否有中是否有 n n 1 1 条边条边条边条边将将边加入加入图中中NNT 是最小生成是最小生成树Y舍去舍去该边Y定理定理 指定指定图中中任一点任一点vi，如果，如果 vj 是距是距 vi 最近的相最近的相邻节点，点，则关关联边 eij 必在某个最小生必在某个最小生成成树中。中。推推论 将网路中将网路中的的节点划分点划分为两个两个不相交的集合不相交的集合V1和和V2，V2=V V1，则V1和和V2间权值最小最小的的边必定在某个最必定在某个最小生成小生成树中。中。第32页/共34页THE END第33页/共34页