WO2010127527A1 - 在邻接节点间多边条件下实现k优路径算法的方法及装置 - Google Patents

Description

在邻接节点间多边条件下实现 K优路径算法的方法及装置

技术领域

本发明涉及通信领域， 特别涉及其中的路由技术。

背景技术

K优路径算法是一种解决在网络图拓朴中获得指定的源到目的节点的多 条路径问题的算法， 通过该算法可以在网络图拓朴中获得路径权重和由小到 大排序的 K条路径。 K优路径算法作为一种很实用的算法， 被广泛应用到交 通运输、 通信路由计算、 人工智能、 经济理论研究、 数学应用等领域， 具备 很高的应用价值， 并能够给使用者带来巨大的经济利益。 长期以来， 国内外 学术界对 K优路径算法都进行了广泛、 深入的研究， 旨在改善和提高算法的 效率， 尽可能的减少算法的时间与空间复杂度， 先后涌现了诸多的迥异 K优 路径算法。

近年来， 随着光传送网波长交换光网络（WSON )技术的迅猛发展， K 优路径算法正被越来越多地应用到解决路由波长分配 （RWA)算法的路由问 题中来。 由于 RWA本身具有非确定型多项式的特征， 其所包含的路由的 R 过程和波长分配的 WA过程要分为两步实现。 目前的 WSON传送网的 WA 波长分配过程， 往往不是全波长交换的， 由于面临传送节点有阻交叉约束的 限制， 需要在 R路由的计算过程中， 提供 K优条可替代路由， 以防止在选定 路由上 WA波长分配失败后， 提供可替换的路由以进行再次的 WA波长分配 过程。 在 RFC4655、 RFC4657中着重描述了路径计算单元（PCE )作为通用 多协议标记交换技术（ GMPLS )的路径计算单元的功能以及架构， 而满足邻 下需要具备的功能。

在以往的 K优路径算法文献中，研究人员往往都仅关注算法的执行效率， 研究的重点通常是怎样降低算法的时间和空间复杂度。 但对于如何在千差万 别的网络拓朴场景下实现 K优路径算法， 很少有文献做过深入细致的归纳与 总结。 在 WSON 的组网环境、 尤其是在多维可重构型光分插复用设备 ( ROADM ) 的拓朴应用中， 经常会有邻接节点间多条链路的场景出现。 不 幸的是， 目前已知的诸多 K优路径算法， 通常要求图拓朴具备一定的先决条 件：

1. 边的个数 m >= 节点的个数 n;

2. 边的权重 > 0, 且如果拓朴图是无向的， 要求边的双向权重相等；

3. 对图拓朴是有向、 还是无向的要求： 有些 K优路径算法明确要求仅 适用于有向图；

4. 任意两点间的路径不允许成环， 也就是路径中不包含重复节点； 5. K路径算法一般基于图拓朴的定义实现： 针对邻接节点间的边， 对于 无向图而言， 仅限于一条双向边； 而对于有向图而言， 仅限于正、 反方向至 多各一条边（或某个方向上有边， 而另一个方向的边不存在） ；

K优路径算法在上述的先决条件下实现时， 通常适用于 K优路径算法计 算的图拓朴场景如附图 1所示。

而现实应用中， 往往会遇到邻接节点间多边的情况， 如附图 2所示。 此 时， 通常的 K优路径算法无法将邻接节点间多出的其他边考虑到算法中来， 只能保留邻接节点间的一条边参与算法计算， 其他边做屏蔽处理， 不参与算 法计算， 这样算出的 "K优路径" 并不是拓朴中真正的 K优路径。

发明内容

本发明的主要目的是： 提供一种解决邻接节点间多边条件下的 K优路由 算法问题的方法及装置。

为此， 本发明提出了一种在邻接节点间多边条件下实现 K优路径算法的 方法： 记录原始的拓朴信息到拓朴结构中； 对原始的拓朴信息进行改造， 如 果两节点间有 n条原边， 除权重最短的那条原边以外， 在其余 n-1条原边上 分别增加假节点， 将原有的节点间的整条原边通过假节点分成两个子段； 每 一个子段形成为一条新边， 新边的权重通过拆分原边的权重得到； 根据新修 订的拓朴信息， 计算指定节点间的 K优路径； 依次对算出的 K优路径中的每 一条路径进行检查： 将每条路径中属于假节点、 新边的 hop跳跃， 还原成备 份拓朴结构中记录的原始的拓朴结构数据； 其中 n > 2。

上述方法中， 如果两节点间有 n条原边， 除权重最短的该条原边以外， 在其余 n-1 条原边上分别增加一个^^节点， 将原有的节点间的整条原边分成 两个子段； 所述新边的权重由原边权重均分得到。

同时， 本发明提出了一种在邻接节点间多边条件下实现 K优路径算法的 装置， 在邻接节点间多边条件下实现 K优路径算法时， 包括如下步骤： 记录 原始的拓朴信息到拓朴结构中备份； 对原始的拓朴信息进行改造， 如果两节 点间有 n条原边， 除权重最短的那条原边以外， 在其余 n-1条原边上分别增 加假节点， 将原有的节点间的整条原边通过假节点分成两个子段； 每一个子 段形成为一条新边， 新边的权重通过拆分原边的权重得到； 根据新修订的拓 朴信息， 计算指定节点间的 K优路径； 依次对算出的 K优路径中的每一条路 径进行检查： 将属于假节点、 新边的 hop跳跃， 还原成备份拓朴结构中记录 的原始的拓朴结构数据； 其中 n > 2。

上述的在邻接节点间多边条件下实现 K优路径算法的装置， 如果两节点 间有 n条原边， 除权重最短的那条原边以外， 在其余 n-1条原边上分别增加 一个^ ^节点， 将原有的节点间的整条原边分成两个新边。

本发明的方法及装置， 在邻接节点间多边条件下， 通过虚拟假节点和拆 分相关原边， 对图拓朴进行修正， 使各边都能够参与到 K优路径的算法计算 中， 而非简单作屏蔽处理， 这样， K优路径算法的结果准确可靠， 能够计算 出拓朴中真正的 K优路径。

附图概述

附图 1是通常适用于 K优路径算法的图拓朴场景举例；

附图 2是部接节点间多边的图拓朴场景举例；

附图 3 是本发明实施例中的修改后的邻接节点间多边的图拓朴场景举 例。 本发明的较佳实施方式

下面通过具体的实施例并结合附图对本发明作进一步详细的描述。

实施例一：

本例的在邻接节点间多边条件下实现 K优路径算法的方法， 所面临的图 拓朴和算法场景满足以下前提：

1. 本例的研究对象仅限于无向图；

2. 本例所针对的 K优路径算法， 要求本质上是通过迭代调用 Dijkstra算 法实现的；

3. 图拓朴所包含的边的个数 m>=节点的个数 n;

4. 图拓朴所包含的边的权重是整数， 且权重 w>0;

5.算得的任意两点间的路径不允许成环，也就是路径中不包含重复节点； 本例釆用以下解决步骤：

1. 记录附图 2中原始的拓朴信息到基于 K优算法的拓朴结构中（可以以 邻接表的形式记录） 并做备份； 原始的拓朴信息中存在的边， 本说明书中称 之为原边；

2. 如果两节点间有 n条原边， 那么除权重最短的那条以外， 在其余 n-1 条原边上分别增加一假节点，假节点的节点 ID取值范围， 不和原始节点的节 点 ID取值范围重合。 这样就将原有的节点间的整条原边分成了两个子段； 这 样每一个子段就成为一条新的边， 本说明书中称之为新边， 新边的权重可通 过拆分原来那条边的权重得到， 如附图 3所示；

3. 根据附图 3的拓朴信息， 计算指定节点间的 K优路径；

4. 依次对算出的 K优路径中的每一条路径进行检查： 凡是属于假节点、 新边的 hop跳， 都还原成基于 K优算法的拓朴结构中记录的原边； 例如， 对 于通过 K优路径算法依照附图 3得到的节点 3到节点 5的某一优路径 , 节点 3— 25—节点 L一 25—节点 7— 15—节点 K一 15—节点 5, 可依照附图 2对应 的基于 K优算法的拓朴结构，还原成节点 3— 50—节点 7— 30—节点 5的路径 信息； 实施例二：

本例的在邻接节点间多边条件下实现 K优路径算法的装置， 在邻接节点 间多边条件下实现 Κ优路径算法时， 所面临的图拓朴和算法场景满足以下前 提：

1. 本例的研究对象仅限于无向图；

2. 本例所针对的 Κ优路径算法， 要求本质上是通过迭代调用 Dijkstra算 法实现的；

3. 图拓朴所包含的边的个数 m>=节点的个数 n;

4. 图拓朴所包含的边的权重是整数， 且权重 w>0;

5.算得的任意两点间的路径不允许成环，也就是路径中不包含重复节点； 本例的装置， 在邻接节点间多边条件下实现 K优路径算法时， 釆用以下 解决步骤：

1. 记录附图 2中原始的拓朴信息到基于 K优算法的拓朴结构中（可以以 邻接表的形式记录） 并做备份； 原始的拓朴信息中存在的边， 本说明书中称 之为原边；

2. 如果两节点间有 n条原边， 那么除权重最短的那条以外， 在其余 n-1 条原边上分别增加一假节点，假节点的节点 ID取值范围， 不和原始节点的节 点 ID取值范围重合。 这样就将原有的节点间的整条原边分成了两个子段； 这 样每一个子段就成为一条新的边， 本说明书中称之为新边， 新边的权重可通 过拆分原来那条边的权重得到， 如附图 3所示；

3. 根据附图 3的拓朴信息， 计算指定节点间的 K优路径；

4. 依次对算出的 K优路径中的每一条路径进行检查： 凡是属于假节点、 新边的 hop跳， 都还原成基于 K优算法的拓朴结构中记录的原边； 例如， 对 于通过 K优路径算法依照附图 3得到的节点 3到节点 5的某一优路径 , 节点 3— 25—节点 L一 25—节点 7— 15—节点 K一 15—节点 5, 可依照附图 2对应 的基于 K优算法的拓朴结构，还原成节点 3— 50—节点 7— 30—节点 5的路径 信息；

实施例三： 本例与实施例一的不同之处在于， 如果有的原边的权重是 1 , 则将拓朴 中所有原边的权重扩大 10倍， 并拆分到新边上， 计算后再按照上述步骤 4还 原。

实施例四：

本例与实施例一的不同之处在于， 如果 K优路径算法按照跳数最少的策 略实施， 那么可以将原拓朴中全部原边的权重暂定设为 10, 新边所拆分的权 重设为 5即可， 这样算出的路由就是按跳数最少策略得出的。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明， 不能认定本发明的具体实施只局限于这些说明。 对于本发明所属技术领域的 普通技术人员来说， 在不脱离本发明构思的前提下， 还可以做出若干简单推 演或替换， 都应当视为属于本发明的保护范围。 例如， 上述实施例中， 如果 有的原边的权重是 1 , 可以将拓朴中所有的原边的权重扩大任意偶数倍， 以 利于拆分给新边； 同理， 如果 K优路径算法按照跳数最少的策略实施， 全部 原边的权重暂定设为任意一个偶数， 新边所拆分的权重将该偶数一分为二即 可。

工业实用性 本发明的方法及装置， 在邻接节点间多边条件下， 通过虚拟假节点和拆 分相关原边， 对图拓朴进行修正， 使各边都能够参与到 K优路径的算法计算 中， 而非简单作屏蔽处理， 这样， K优路径算法的结果准确可靠， 能够计算 出拓朴中真正的 κ优路径。

Claims

权 利 要 求 书

1. 一种在邻接节点间多边条件下实现 K优路径算法的方法， 包括如下 步骤：

记录原始的拓朴信息到拓朴结构中；

如果两节点间有 n条原边， 在除权重最短的原边以外的 n-1条原边上分 别增加一假节点， 以将所述 n-1 条原边中的每一原边都分成两个子段， 每一 条所述子段形成为一条新边， 所述新边的权重通过拆分其所在的原边的权重 得到；

根据在所述 n-1条原边上增加假节点后的拓朴信息，计算指定节点间的 K 优路径； 以及

依次对算出的 K优路径中的每一条路径进行检查： 将每条路径中的属于 殳节点、 新边的 hop跳跃， 还原成所述拓朴结构中记录的原始的拓朴信息； 其中 n > 2。

2. 如权利要求 1所述的方法， 其中， 所述拆分为均分。

3. 如权利要求 1或 2所述的方法， 其中，

如果存在权重是 1的原边，

所述新边的权重通过拆分其所在原边的权重得到的所述步骤包括： 将所 述拓朴结构中记录的原始的拓朴信息中的邻接节点间除权重最短的原边外的 n-1条原边中的每一条原边的权重都放大偶数倍， 并拆分到新边上；

将每条路径中的属于假节点、 新边的 hop跳跃， 还原成所述拓朴结构中 记录的原始的拓朴信息的所述步骤中的所述还原根据所述 n-1 条原边放大前 的权重进行。

4. 如权利要求 1或 2所述的方法， 其中，

如果 K优路径算法按照跳数最少的策略实施，

所述新边的权重通过拆分其所在原边的权重得到的所述步骤包括： 将所 述拓朴结构中记录的原始的拓朴信息中的邻接节点间除权重最短的原边外的 n-1条原边中的每一条原边的权重设为同一偶数，新边的权重设为所述偶数的 二分之一；

将每条路径中的属于假节点、 新边的 hop跳跃， 还原成所述拓朴结构中 记录的原始的拓朴信息的所述步骤中的所述还原根据所述 n-1 条原边设为所 述偶数前的权重进行。

5. 如权利要求 1或 2所述的方法， 其中， 所述假节点的节点 ID取值范 围和所述节点的节点 ID取值范围相异。

6. 如权利要求 3所述的方法， 其中， 所述偶数倍为 10的整数倍。

7. 如权利要求 4所述的方法， 其中， 所述偶数为 10。

8. 一种在邻接节点间多边条件下实现 K优路径算法的装置， 其设置成： 记录原始的拓朴信息到拓朴结构中备份； 如果两节点间有 n条原边， 除权重 最短的那条原边以外， 在其余 n-1 条原边上分别增加^ ^节点， 将原有的节点 间的整条原边分成多个子段； 每一个子段形成为一条新边， 新边的权重通过 拆分原边的权重得到；根据新修订的拓朴信息，计算指定节点间的 K优路径； 依次对算出的 K优路径中的每一条路径进行检查：将属于假节点、新边的 hop 跳跃， 还原成备份拓朴结构中记录的原始的拓朴结构数据； 其中 n > 2。

9. 如权利要求 8所述的装置， 其中， 如果两节点间有 n条原边， 在除权 重最短的原边以外的 n-1条原边上分别增加一个^^节点，以将所述 n-1条原边 中的每一原边分成两个新边。