英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料

有界圈覆盖问题

综述：

我们考虑的是有界圈覆盖问题，此问题需要找到一个双连通图的最小圈覆盖，使得其中的任意圈所包含的边不超过预设值。对通信业务量采用多个自愈环提供路由功能时，在光纤通信的设计上，这个问题经常发生，即使当发生光纤断裂或他断网等情况时，也会出现此类问题。我们目前对此提出了一些相关问题，并且为这些问题开发出一套自适应算法来找到圈覆盖问题的近似最优解。我们将根据随机生成的问题来应用算法，求得实际结果并对其进行分析。

关键词：算法分析，连通图，启发式，网络通讯

1、简介

本文考虑的有界圈覆盖问题 (BCCP),是寻找一个最小花费的圈覆盖，使得这个双连通图的圈覆盖不包含超过规定编号的圈覆盖。这里所说的圈是指一个抽象出来的范围，它包括了原图内的点、边，相当于是对原图所做的分割。如果原连通图内的边拥有权重，那么这个圈覆盖的成本即是此圈覆盖内所有的边的权重之和。我们将在第三节对这个圈覆盖给出一个精确的定义，这里给出一个例子来简单说明，如下图：

图1，备注：边旁边的数字代表该边权重

由于边(1、4)和(2、3)在两个周期中都出现了,他俩需要计算2次，这使得总体的消费为130。

BCCP是一个棘手的问题。潜在的圈覆盖的数量会随着图内节点数量以及所允许的圈覆盖的大小而呈指数级增长。我们的解决方法就是基于第一次找到的一系列候选圈组成一个相对较好的覆盖。我们发现这个方法可以用来解决与BCCP类似的最优化算法，也能用来处理最优多项式时间算法。然后我们找到了一个求最小花费的一系列包含图边的候选人覆盖子集的方法。当然，如何去选择这些子集覆盖也是一个棘手的问题，不过，我们将在第10节介绍如何使用标准的整数规划来选择最优的候选圈子集。

2、BCCP和网络服务技术设计

电信网络的可靠性变得越来越重要,因为越来越多的组织在世界各地已经习惯于依赖它们。于是在设计网络时要考虑的一个重要因素是它的生存能力——也就是说,当出现一个或多个链接服务变慢或挂掉时，它能够继续提供站点之间的通信连接的事件,。

假设有一个I,j 节点的网络链接挂掉了，它所提供的服务可以路由重定向而恢复。这被称作为动态修复服务，他主要运用在网络中的逻辑层。换句话说,更改路由协议的消息通过其他路径到达目的地,但实际上网络本身的服务仍然不变。对于这种工作策略，网络上两个工作节点之间，必须存在至少两条相互之间无联系的独立路线。这种类型的网络拓扑称为2-connected design，它是一种具备高生存能力的网络基础设计。如果网络没有这个功能,那么当链接路径I,j 挂掉时，将会有至少一对,甚至更多的节点路径同时挂掉。

高存活性的网络设计通常采用环的形式来实现2-connected design拓扑结构。网络中的环结构是指由一组节点之间的路径所形成的一个闭环。为了利用环结构并优化消息重路由，动态恢复策略可以使用一个依赖于包含所有网络链接状态信息的数据库的控制系统。但这个策略太复杂了，很难实现。更重要的是，他可能需要花费很多时间来对网络的逻辑层进行故障检测并恢复服务(wu 1992)。自愈环（SHRs）通过使用专用硬件对故障进行简单的检测和重定向路由，他只需要简单的修改下通讯路径就可以在一定范围内在网络的物理层自动并快速的恢复故障链接。

有几种使用基本原理的自愈环（参见Shyur et al. 1994, Wu 1992），对于一组现有的通信网络链接环，使用第二个平行环对它进行备份。这个用作备份的冗余链接，被称为保护环。举例来说，一些自愈环使用线路开关机制，当工作环出现故障时，通过开关使所有的通信路径切换到保护环上，从而保证服务的正常运行。于是我们说，工作环通过自愈环的设计模式而被保护起来了。

鉴于不可使用现有的网络自愈环,我们认为提高生存能力的问题可以通过构造一组自愈环(环覆盖)解决。在原始网络之间，至少需要一条自愈环来复制节点i与节点j之间的链接路径来达到保护该链接的目的。这个问题的数据源需要包括每条直接链接节点i和节点j的自愈环的权重花费。这个成本包括所有的链接的采购成本和安装额外的纤维材料成本和网络节点的电缆终端设备成本。

我们将原始的电信网络抽象成一个无向图，无向图的顶点代表原网络中的节点，边代表原网络节点中的直连路径。无向图中的边的成本，就对应为原网络节点之间建立直连路径的成本。这让我们将链接网络中的环覆盖和无向图中的圈覆盖一一对应起来。例如：假设有一个有两条自愈环的原始网络的环覆盖 G 如图一显示的那样。一条自愈环对应Cycle 1，另一条对应Cycle 2。请注意，这两个自愈环都使用了节点1，4和节点2,3之间的链接路径，这会造成成本的花销。与自愈环架构密切有关的同步光纤网络(SONET)标准限制一个环内的节点或者站点数量最大为16个(Kennington and Rahman 1998)。然而实际上，自愈环通常仅包括10或更少的节点（Wu 1992）。所以我们将 BCCP的圈覆盖所包含的节点极限也设置为10个。

这样，我们就可以将BCCP问题放在更大的电信网络生存能力的设计问题上。自愈环的通信流量也是有限制的，所以需要同等对待所有的生效和保护链接(Cosaresand Saniee 1994, Wu 1992)。环的能力在很大程度上取决于他所使用的增删改（add-drop-multiplexers ADM）的类型。ADMs 主要用于环上的节点用来发送或转发通信流量给其他节点、或从其他节点接收通信流量。此模型不对设备的效率进行考虑。

Slevinsky et al.(1993)提出了多环的设计问题，即找到一个网络的环覆盖，使得关于产能效率的目标函数最优。他们提出使用启发式贪心算法去寻找一个图最小花费的圈覆盖（没有圈容量的限制），圈覆盖的花费被定义为圈内边数与圈内边的最大权重的乘积。Kennington et al. (1999) 对上述圈覆盖问题的变体提出了一个基于优化的求解过程。Kennington 和Rahman (1998)改进了这种方法，使他适应于有最大16个节点限制和环的数量必须为28的倍数。

高存活性的电信网络的优化设计实际上是一个非常复杂的问题，无法使用一个简单的模型来解决。 Laguna (1994) and Cosares et al. (1995)在同步光纤网络（SONET）的设计过程中依次提出了不同的优化问题。例如Cosares 、Saniee (1994) 和Dellrsquo;Amico et al. (1999) 在双向对称环的逆时针和顺时针路径中考虑了对流量路径进行分区的问题。在一个双向环中，信息的传输是由工作环和保护环一同承担的，同时它的传输方向可能是任意的。SONET是一个基于电路的协议。因此，节点i和j之间被建立了一个等效的通信量，即从i到j和从j到i他们的花费是相同的。前面所描述的路线开关机制适用于单向环，所以节点i和j之间的通信量将耗费整个环的工作能力。双向环能更好的突破顺时针方向的工作环上的节点i和节点j之间的通讯限制，同样的对于相应的逆时针方向的也能突破。以上这些论文内所提出的并解决的问题与本文相比主要适用于要求不高的网络，我们在解决上述问题后，还将进行拓展讨论，例如对网络上的需求进行预测并决定需要建立何种程度的自愈环。

比较典型的是，类似BCCP和圈覆盖问题，Slevinsky et al. (1993), Ken-nington et al. (1998), and Kennington and Rahman (1998) 已经在整体网络规划的过程中被当做子问题解决了。举例来说，我们认为启发式BCCP方法可以用来寻找一系列较好的环去覆盖 Cosares et al. (1995)在 “Ring-Routing”问题中描述的 “共同权益集团”（community of interest CoI）。CoI是一组在地理位置上比较接近的网站节点，他们之间有大量的链接需求，因此比较适合设计成环结构。在这种情形下，应当对图的节点寻求圈覆盖，而不是对图的边寻求。然而，一个图的对边的圈覆盖能满足对他的点覆盖，也能轻易的满足在第6节中描述的BCCP问题对于节点覆盖版本问题的覆盖集公式。

网络规划者往往对网络场景进行分析。他们将对不同的需求模式进行成本估算，这些成本包括建立一个新的网络系统，以及对原有网络系统进行拓展升级所需要的设备成本。本质上，这项研究应当是短期的，且需要解决一系列的与之相关的问题。在这种背景下，BCCP需要被运算多次，他的运算速度将和启发式的运算速度同等重要，同时，他的运算过程的质量可能会更加重要。

3、符号和公式

整篇论文中，表示一副有个节点并且条边的图。每条边的权重或者说费用是。节点i与节点j之间的路径由一系列的相邻节点和他们之间不重复的边组成。符号Pij 表示节点i与j之间的一系列边路径。节点i和节点j之间的圈由其中依次相连的边组成。Cij 是指节点i和j之间的一个圈内的一系列边。 圈的权重或者说花费被定义为由他所有的边的权重的和与这个圈的大小。其中圈的大小是指|Cij| ，这个圈内边的数量。花费、权重以及路径的长短在定义上是相似的，节点i和j之间的最短路径这一术语通常来说是用来表示节点i和j之间的所有边的边长总和，见如下公式：

在某些情况下，我们将使用该术语来描述边的最小数量和路径的举例（例如： |Pij|）。我们将表明我们所谓的最短路径是对成本还是对边数进行统计(虽然一般来讲根据上下文可以很明确的看出来)。

如果圈C 包含了 边e ，我们就说 C 覆盖或者穿过了e 。图G 的一系列覆盖了所有边的圈被称作G 的圈覆盖。圈覆盖的花费是每个圈的花费的总和。首先，我们假设网络是2-连通的（例如：该图中不包含断边，不存在孤立的节点对）。

参数k 表示一个圈内的最大节点数。一条包含k条或者更少的边数被称为 k-path，也就是说 k-cycle 就是指这个圈所允许的最大尺寸为k 。图G的一个k-cycle cover 是指G的圈覆盖全部由k-cover 组成。每一条圈覆盖，至少包含每条边一次，但是每条已经被给出的边可以至少被一个圈使用。换句话说，一个覆盖里面可能会多次使用一些边。在有界圈覆盖问题中，可能会规定复用一组边的最低成本，这将导致在解决多重图（multi-graph）的问题时他的边可能被分割进多个k-cycle 。

我们使用决策变量来表示在创建自愈环是对链接e额外使用的次数。同时使用作为的一组备份。至此，有界圈覆盖问题（BCCP）正式被定义为如下形式：

问题名称：有界圈覆盖问题

实例：给出一个2-连通图G，每条边e，（eisin; E）的花费，和整数k。

最优化问题：目标函数： 条件：使得 可被分割为图G的一个k型圈覆盖（ kminus;cycle cover），或者表示这个问题无法被分割成k型圈覆盖（ kminus;cycle cover）。

我们可以考虑根据圈的大小去寻找满足目标函数的圈覆盖。这种情况等同于的情况或者是其他任何边的花费都相同的情况。我们首先考虑这种无权重类型的特殊情况，相对的，在这种情况下，节点的可靠程度就会变为最主要的问题。我们可以去寻找图G一系列包括节点的圈（不一定包括所有的边）。提出这个方向上的问题是出于对问题的完整性的考虑，但是我们主要的关注点，依旧还是针对于边的圈覆盖问题。图G的任何一个对于边的圈覆盖一定是能包括对于他节点的圈覆盖。因此，我们针对于BCCP问题所提出的对于边进行的覆盖算法一定能解决对于节点的覆盖问题。

4、BCCP问题的复杂度分析

4.1 寻找可行的有界圈覆盖

对已有的图G寻找一个最佳的k型圈覆盖（k-cycle cover）本就是一件比较困难的事情，但是如果仅仅是寻找一个可行解或者判断出他不存在可行解还是比较简单的。图G存在k型圈覆盖（k-cycle cover）的可行解的必要条件是他的每条边必须至少属于一个k型圈覆盖或者范围更低的覆盖。这意味着，在节点i与节点j之间（不包括节点i和节点j）最多存在k-1条路径。对于图 ，可以以j节点作为入口，使用广度优先算法找到路径。如果节点I 在广度优先搜索树中第一个被找到，那么我们就找到了节点i和j之间的一条k-1型路径。如果没有，那我们就说图G不存在一个包含边（i,j）的k型覆盖。广度优先搜索算法对于每一条边的搜索复杂度为O（m），因此，对于寻找一个可行的k型圈覆盖问题，他的时间复杂度为。

定义为图 中节点i与节点j之间最短路径的长度（与边的数量有关）。因此包含边 的圈的最短路径为 。为了使m型最短路径问题在BCCP中可行，我们定义最小圈长为 。通过使用斐波那契堆来实现Dijkstra算法，我们可以发现，每条路径 的时间复杂度为 (Fredman and Tarjan 1987)。因此求解 的复杂度为。

4.2 BCCP是一个NP-hard问题

目前

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[23749]，资料为PDF文档或Word文档，PDF文档可免费转换为Word