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