规划 SD H 自愈环过程中的光缆路由策略

摘要:在规划SDH自愈环的过程中，环的光缆路由策略是一个比较复杂的问题。本文提出了一种基于TSP的改进算法，这种算法在考虑容量分配与否两种情况下，综合考虑了网络规划设计过程中可能出现的几种实际情况 ,对于规划 SDH 自岔环结构和设计生存性网络具有一定的参考价值。


1 引 言
    SDH技术是当今世界通信领域中的一个热点，被公认为是实现 B - - ISD N 的关键技术和理想的传输手段 。SDH自愈 环(self—healing ring)利 用了环形网固有的可靠性来提 高网络的生存性 ，在光缆完全被切断和节点故障的情况下仍然能够保持通信的完整性 ，周而在传输网中得到了广泛的应用。“九五期间各省市组建的省内干线网和本地网很多都采用
了 SDH 自愈环结构 。
    环的光缆路 由策略 (R ing F iber R outing Strat—egy )是 指 在 规 划 SD H 自愈 环 的过 程 中 ，当环中ADM 节 点的位置确 定以后 ，如何把这些节点用光缆物理地连接起来。光缆路由策略的根本目的就在于当环中节点位置等因素确定的情况下，选取适当的光缆路由将这些节点联接起来，使构成的自愈环结构最为经济，同时也比较合理。
    在实际的网络规划过程中，当环中的节点个数比较多 ，并且节点间链路有 一些具体的实际情况约束时 ，往往使 整个规划过程比较困难。另外 ，在复用段保护类型的自愈环结构中，经常需要把具有较大业务量的两 点连结在一起 ，以提高网络资源的利用效率 ，因此 ，节点间的容量分配对环的光缆路由策略也有较大的影响 。考虑到这些具体因素，在本文中提出了一种利用TSP (T raveling Salesm an P roblem )求解的 C A D 算法 ，能 比较有效的解决这类问题。
2 不考虑容量分配时环的光缆路由策略
    环的光缆路由策略从本质上讲可以纳入到求解TSP的范畴 。所谓 的TSP是这样的 ：一个旅行推销员从他所在的城市出发，到另外的 N一1个城 市推销，他应该如何选择路线 ，能既不重复又不遗漏地走完全部城镇 ，最后回到自己的城市 ，并且使整个过程距离最短。T SP 是图论 中一个非常著名的问题 ，它用 图论上的语 言描述就是在边带权图 G 一(v ，E )
中，寻找经过 每个节点一次且只有一次的权最小回路 ，称为 Hamilton回路。
    由此可见 ，可以考虑用求解TSP的方法来解决环的光缆路由策略问题 。在 TSP中，各个城市之间的距离矩阵就是图的邻接矩阵，求解 TSP也就相当于在距离矩 阵中找出 N 个元素，使它们既不同行又不同列 ，并且使 它们的和最小。在建设 SDH 自愈环的过程中，两个节点间链路的费用主要是光缆本身和敷设光缆的费用 ，这两项费用 与两点之间的距离基本上是线性关系，因而可以用节点间的光缆链路费用值作为邻接矩阵的权值 ，利用求解TSP 的方法来解决这个实际问题。
    但是 ，环的光缆路由策略作为一种工程规划设计中的实际问题，与传统的TSP 还是有不 少差别的，这些差别主要有以下几点；
    (1)当两点之间的光缆长度超过了一定的闻值时，就需要在线路中安装再生器 ，因而使两点间光缆链路费用不再比例于两点距离 。
    (2)由于各点之间的具体情况不同，敷设光缆的方式不同 任意两点间光缆敷设的费用与距离的比例关系也不完全相同。
    (3)有些节点之间由于某些具体原因不适合敷设光缆路线。
    (4)有些节点之间可能已经存在以前曾经敷设的光缆线路。
    为此 ，把传统的求解TSP方法作了一些改进，把工程规划设计中遇到的实际问题合理地纳入到TSP 的解法中去，以便可以直接利用求解 TSP 的方法来解决 环的光缆路由策略 问题 ，这些改进 主要包括以下几个方面 ：
    利用节点间的光缆链路费用值代替两点问的距离值作为邻接矩阵各元素的权值 。
    当两点间距离超过了阈值时 ，在两点问费用值上再加上再生器的费用 ，如果超过两倍的阚值，则加上再生器的费用 ，如此类推。如果自愈环采用四纤复用段倒换环 ，再生器的费用还要加倍。
    分别用系数表示因光缆敷设的方式不同、施工难度不同造成的费用差异，这两个参数由 设计人员根据具体情况给出。
    对于不适合敷设光缆的两点 ，它们之间的费用设为oo 。
    对于已经存在光缆线路的两点 ，它们之间的费用为0 。
3 考虑容量分配时环的光缆路由策略
    在规划SDH自愈环的过程中，在很多情况下，节点间的容量分配也是一个需要考虑 的重要因素在复用段保护类型的自愈环结构中，在各个节点问容量分配一定的情 况下 ，环中节点的连接顺序对 网络容量的利用效率 有很大的影响。为 了合理有效地利用 网络资源 ，保 护投资，增加运营收入 ，需要在 网络规划阶段就把容量分配因素考虑在内。在复用段保护类型的自愈环结构中，从提高网络资源的利用 率的角度出发 ，应该尽可能地把那些具有较大容量需求的节点连结在一起 ，以使这些节点间的业务流量经过尽可能少的链路 。为了体现这种 实际情况 ，并且 能够把它纳入到以上所述的TSP算法 中去，增加了下面的改进 ：
    用参数R来表示 由于节点问容量分配的不同而对 网络规划所造成影响的 因子 ，节点 ， 间的容量分配为  ，如果两点间的光缆链路费用不为0 和oo ，则在两点的费用值中减去 R s 。
    通过上述的改进，可以把考虑容量分配的情况纳入到求解 TSP 的范畴中，R，具体值应根据网络实际情况确定。
4 算法描述与框图
    根据上面的讨论，得出了利用求解 T SP 制定环的光缆路由策略的基本 思路是首先根据 自愈环规划过程中的具体情况得出环节点 间的费用矩 阵(此矩阵为对称矩 阵)，然后利用 T SP 求解 ，所得结果即为自禽环经济合理的组成方案 。算法的具体步骤c 表示节点i， 之间敷设光缆线路所需的费用“ = J 时 C u = co )，D “表示节点 f，J 之间的光缆 线路 长度 ，c ，、c 分别表示 单位长度光缆 的费用和敷设单位长度光缆线路的基本费用 ，c 表示一套再生设备的费用，R ．、T 分别 表示 因为光缆敷设方 式不同和麓工难度不同所 引起的 费用差异 用参数 R 。来表示 由于节点间容量分配的不同而对网络规划所造成的影响因子，s。，表示节点f，J 间的容量分配。
5 实例分析
    下面来具体说 明算法的实现过程 。要把5个 A D M 节点用最经济的方案连成双纤复用段倒换环，图中的实线表示已经存在的光缆线 路，虚线表示两点间可以敷设光缆 ，其余各点问不适合敷设光缆 ，图中的数字表示链路的长度，规定安装再生设备的闻值为5O，为了简单起见，假设 c，、c 都为 1，也 、R 也都为 1，e 等于30 ，R 为 0．5，容量分配矩阵如图 3 所示 ，则通过 计算 ，可以得 出不考虑容量分配和考虑 容量分配两种情况下的费用矩 阵分别为 c 和C1  ：
6 小 结
在 目前应用SDH技术的传输网中，自愈环是应用最为广泛的一种拓扑结构 。因此 ，研究自愈环的规划设计技术 ，以便设计出更加经济有效的生存性拓扑结构 ．应该是很有意义的。在本文中提 出了一种利用TSP解决 环路的光缆路 由策略的方案 ，在是否考虑节点间容量分配两种情况下，根据实际约束条件对传统的TSP算法作了一些改进，因而可以把光缆的最优路由问题纳入到求解 T SP 的范畴中，通过框图和一个简单的实例，具体地描述了算法的实现过程。此算法可以用来解决环中节点个数较多 ，节点之间又有一些具体情况约束并且节 点间容量分配矩 阵已知情况下的光缆路由策略问题 ，对于合理规划 自愈环结构和有效地设计高生存性 网络拓扑具有一定的参考价值 。