北邮-通信网规划理论 第二章--电信网规划(一).ppt

通信网规划理论 制作人 孙青华 第二章电信网规划的基础知识 3 第二章电信网规划的基础知识 第一节图论基础知识第二节随机服务系统及其在电信中的应用第三节业务预测的基本方法第四节流量预测的基本方法第五节电信网规划中的评价准则第六节电信网规划中的财务经济评价指标及经济分析方法第七节多目标方法及其应用第八节智能算法及其应用 4 电信网规划的过程 对业务量 发展动向 趋势和前景等进行预测 提出电信网发展规划 实施规划方案 规划评价 规划调整 优化方案 确定规划目标 5 本章目的 通过本章介绍的一些定量分析方法 掌握电信网规划的一般方法 为进一步的进行实际的规划工作奠定基础 本章的内容涉及 图论经济计量学预测学智能理论 6 第一节图论基础知识 主要应用领域 传输网络电路理论编码理论可靠性理论集成电路设计及计算机领域 7 第一节图论基础知识 网络规划简介网络中各最短连接方法电信网中局 站间最短路的算法网络流及其算法电信网的可靠性 8 2 1 1网络规划简介 网络 电信网络 计算机网络 运输服务网络 能源和物质分派网络 人际关系网络等等 网络规划就是研究如何有效地计划 管理和控制网络系统 使之发挥最大的社会和经济效益 9 2 1 1网络规划简介 网络规划与图网络规划问题的例子图与网路分析 10 2 1 1网络规划简介 网络规划与图 网络 数学模型 数学结构 图 从若干可能的安排或方案中寻求某种意义下的最优安排或方案 数学上把这种问题称为 最 优化 Optimization 问题 运筹学 OperationsResearch 广义 管理科学 OR MS 系统科学 工程狭义 最优化连续优化 数学规划 线性规划 非线性规划等 离散优化 组合优化 网络优化等 整数规划等不确定规划 随机规划 模糊规划等 方法之一 研究与 赋权 图有关的最优化问题 11 2 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 网路 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 最小生成树 多级辐射制的电信网络 管理的指标体系 家谱 分类学 组织结构等都是典型的树图 任两点之间有且只有一条路径的图称为树 tree 记为T树的性质 最少边的连通子图 树中必不存在回路任何树必存在次数为1的点具有n个节点的树T的边恰好为n 1条 反之 任何有n个节点 n 1条边的连通图必是一棵树 32 图的生成树 树T是连通图G的生成树 spanningtree 若T是G的子图且包含图G的所有的节点 如何找到一棵生成树深探法 depthfirstsearch 任选一点标记为0点开始搜索 选一条未标记的边走到下一点 该点标记为1 将走过的边标记 假设已标记到i点 总是从最新标记的点向下搜索 若从i点无法向下标记 即与i点相关联的边都已标记或相邻节点都已标记 则退回到i 1点继续搜索 直到所有点都被标记广探法 breadthfirstsearch 是一种有层级结构的搜索 一般得到的是树形图 33 最小生成树 最小部分树 例2 1 2通信网规划中通信线路的连接问题某一地区有若干个主要城市 现准备修建信息高速公路把这些城市连接起来 使得从其中任何一个城市都可以经信息高速公路直接或间接到达另一个城市 假定已经知道了任意两个城市之间修建信息高速公路的成本 那么应如何决定在哪些城市间修建信息高速公路 使得总