通信网理论基础-通信网结构.ppt

第四章 通信网结构 §4.1 图论基础 §4.2 最短径问题 4.2.1 最短主树（支撑树） 4.2.1 端间的最短径 §4.3 站址问题 4.3.1 单中点问题 4.3.2 k中点问题 4.3.3 设站问题 §4.2 最短径问题 最短径问题可以用于通信网的拓扑结构优化和通信路由选择。 内容涉及： 局间以及信道代价已知的情况下以最小的费用规划联结的网络 通信网络拓扑结构确定后，怎样选择局站间的最佳通信路由和备用路由，包括在转接次数等指标符合一定要求的处理方法，怎样选择站址和埋设管道的路由等 4.2.1 最短主树 联结图G本身不是树，则其主树可能不止一个，但是满足特定条件的主树至少存在一个。 寻找最短主树是一个常见的优化问题。 一、问题描述 已知联结图G有n个端，以及相应的端间距离 ，若vi和vj之间没有边存在，可以令距离为无穷大 ，目标是求最短主树，也即n-1条边的权和最小的联结子图。 二、最短主树的特征定理 若T*是G的最短主树，则下述论断等价： （１）Ｔ*是Ｇ的最短主树 （２）对T*的任一连枝e，e是由e所决定的基本圈中的最大权边。 （3）T*的任一树边e，e是由e决定的基本割集中的最小权边。 本定理可以用于最短主树的有哪些信誉好的足球投注网站。 三、无限制条件的最短主树 无限制条件的最短主树的求法 顺序取端的Prim算法 顺序取边的Kruskai算法 破圈法 Kruskal算法(K算法) 特点：顺序取边。 K算法所得的树也为最短支撑树。 K算法的复杂性： K算法的复杂性主要决定于对边的排序，设原图有m条边，共有m!种排法，相当于log2(m!)次比较，设原图有n个端，则最多可有n(n-1)/2条边，复杂性为：n2log2(n) 量级，也是多项式型。 K算法取得最短主树的证明 证明过程参考教材P117。 破圈法 基本思想 从联结图中寻找圈，然后在圈中删去权最大的边，最后剩下的无圈联结图为最短主树。 穷举法 穷举法 把图中所有支撑树都列举出来，再按条件筛选，选出符合条件的最短支撑树。这是一种最直观又最繁杂的方法。可以得到最佳解，但计算量往往很大。如n个端的全连通网，其支撑树数目为n(n-2)个，已属于非多项式的难题(NP Hard)。 穷举法只能用于端和边数较少的网络。 调整法 先选定适当的求最短支撑树的准则，如P算法和K算法，但在每一步中要判断是否满足限制条件，并进行调整，直至最后找出满足条件的支撑树。 这类方法的复杂性一般都是多项式型的，但不能保证取得最佳解，只能得到准最佳解，常用的方法有E-W算法(厄斯威廉算法，Esou-Willian算法)。它并不能保证最短性，但往往相差不会太大，而其计算要比穷举法简单得多。 D算法的适用条件 D算法可应用于有向图。 端点有权的处理策略。 如果边的权重有正有负，D算法不能应用于这种情形。 Bellman-Ford（BF）算法 复杂度为O(n3) §4.３ 站址问题 站址问题 4.3.1 单中心问题； 4.3.2 ｋ中心问题 4.3.3 建站问题 研究意义 上面第２节的内容主要是针对网内所有的端都是固定的情形。 实际通信网中，会增设新的端，交换站也是可以选择的 4.3.1 单中点问题 关于距离测度 根据不同的问题，距离测度可以有不同的形式： 欧式距离 平方距离 矩形线距离 用户数目随地理区域连续分布的情况 当用户的数目很大，用有限数n来计算很困难，可假设用户数是按概率密度 连续分布的，此时的代价可表示为： 求解上述各种距离下中点座标 欧式距离的情况，令一阶偏导数为零可求得最小值： 平方距离的情况 矩形线距离的情况 在距离线距离的情况，导数将出现不连续点，即： 当 是偶数，并且在上下和左右均可分割成相等的两部分时，可用上式来求中点，这时的解并不唯一，如下图所示： 当 是奇数，或虽为偶数，但不能均分时，则xq必与某些xi相同，yq也是这样，有时，中点可在一条线上的任一点，如下图所示：中点可为AB上的任一点。 有时也可能只有一个点可作为中心，如下图所示：只有A点是中点，这样选定的中点可使代价L取得极值，而且这极值必为极小。 用户点连续分布的情况 对于欧式距离：有 对于矩形线距离，有求解等式： 最佳服务区域问题 在用来连续分布的用户点来求解时，会遇到选择最佳服务区域问题。若所选的服务区域较小，建一个交换局的代价分摊到每一个用户的份额将增大。若所选的服务区域较大，远距离线路铺设费用将增大，也会使用户分担的份额增大。如何划分一个交换局的服务区域，才能使每个用户所分担费用最小，是一个有实际意义的问题。 不失一般性，可设x=0,y=0处建一个交换局，费用为C,