通信网规划理论PPT课件

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