通信网规划理论PPT课件

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