现代通信网课件通信网络设计基础

第3章 通信网络设计基础第二讲本讲主要内容1.最短路径2.站址选择3.排队论基本概念 1.最短路径背景l建立多个城市之间的有线通信网络，如何确定能够连接所有城市并使得线路费用最小的网络结构？l在一定网络结构上，如何选择通信路由，怎样确定首选路由和迂回路由？l这些问题都归结到路径选择或者路径优化问题上来。1.1 最小支撑树寻找最小支撑树是一个优化问题，可以分为两种情况：无限制条件（无约束条件）和有限制条件（有约束条件）。这里重点介绍无限制条件的最小支撑树搜索方法。求无限制条件的最小支撑树的方法：K方法和P方法 求解最小支撑树的Kruskal 方法（K方法）例3-3求解最小支撑树的Prim 方法（P方法）求有限制条件的最小支撑树的方法 l在设计通信网的网络结构时，经常会提出一些特殊要求，如：两个交换中心通信时，转接的次数不能太多；某条线路上的话务量不能太大等等。这类问题可以归结为在限制条件下求最小支撑树。l求有约束条件的最小支撑树的方法简单来说是这样的：先按照上述K方法或者P方法求出无约束条件的最小支撑树，然后根据所给的约束条件对网络结构进行调整，使之既满足约束条件，又尽量接近最小支撑树。1.2 点间最短路径l在通信网的网络结构确定以后，任意两点之间的通信，首选路由是它们之间的最短路由，这是求两点间最短路径的问题。l两点间的最短路径问题有两种情况：（1）指定点到其他点的最短路径和（2）任意两点间的最短路径。指定点到其他点的最短路径 l求指定点到其他各点的最短路径，Dijkstra算法（简称D算法）是最有效的算法之一。D算法的具体步骤例3-5任意两点之间的最短路径算法 l求任意两点之间的最短路径，可以依次选择每个点为指定点，用D算法做n次运算，但这样做比较繁琐。下面介绍一种更为有效的算法Floyd算法，简称F算法。F算法的原理与D算法相同，只是使用矩阵形式进行运算，有利于在计算机中进行处理。例3-63.站址选择 l实际通信网中，可以设立新的交换局，或者在某些交换局之间设立汇接局或高等级的交换局，它的位置选择应能使得路径最短或者网的总费用最小。新交换局可以设立一个或者多个，在数学上是求单中位点或者多中位点的问题。3.1 单中位点l距离测度 单中位点位置的确定（矩形线测度）3.排队论基本概念 1.排队系统的概念（1）排队论与排队系统的概念l顾客要求服务的一方；l服务机构提供服务的一方l服务员服务机构内的具体设施排队现象产生的原因和排队论需要解决的问题l顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因。排队论就是利用概率论和随机过程的理论，研究随机服务系统内服务机构与顾客需求之间的关系，以便合理地设计和控制排队系统。l由于顾客到达的数目和要求提供服务的时间长短都是不确定的，这种要求随机服务的顾客和服务机构两个方面构成的系统称为随机服务系统或者排队系统。3.排队论基本概念（2）排队系统的一般表示任何一个排队系统都有以下过程：l顾客到达服务机构，若服务员有空闲便立刻得到服务，若服务员不空闲，则需要排队等待服务员有空闲时再接受服务，服务完后离开服务机构。图3-21 3.2 排队系统的基本参数3.2 排队系统的基本参数3.3 排队系统的三个特征3.3 排队系统的三个特征3.3 排队系统的三个特征3.3 排队系统的三个特征3.3 排队系统的三个特征综上所述，无论是顾客输入过程，还是服务过程，只要是最简单流，则所综上所述，无论是顾客输入过程，还是服务过程，只要是最简单流，则所对应的概率分布函数都为负指数分布，又称对应的概率分布函数都为负指数分布，又称M分布。分布。3.3 排队系统的三个特征3.4 排队系统的几个主要指标及李特尔（Little）定律 3.4 排队系统的几个主要指标及李特尔（Little）定律3.4 排队系统的几个主要指标及李特尔（Little）定律3.4 排队系统的几个主要指标及李特尔（Little）定律3.5 排队系统的分类3.5 排队系统的分类3.6 M/M/1排队系统 3.6 M/M/1排队系统3.6 M/M/1排队系统3.6 M/M/1排队系统3.7 M/M/m/n排队系统3.7 M/M/m/n排队系统3.8 排队论在通信网中的应用 3.8 排队论在通信网中的应用本次课内容回顾l最小支撑树求解的目的l最小支撑树及其求解方法K方法和P方法l最短路径求解的目的l点间最短路径求解方法：指定点到其他点的最短路径算法；任意两点之间的最短路径算法 l站址选择的目的l距离测度：欧氏距离、折线距离l单中位点求解的方法（折线距离测度）l排队论的意义l排队系统的3个基本参数l最简单流的概念l排队系统的主要指标