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

---

互联网布局优化的动态规划方法

摘 要

可靠性和成本是互联网络的两个重要性能指标。在布局设计阶段需要考虑这两个方面，以便在它们之间进行适当的权衡。本文介绍了使用动态规划进行互联网络布局优化的新方法。我们的主要目标是通过优化网络布局，来使在某些预定成本约束的条件下最大化给定网络的网络可靠性。由于上述问题是NP-hard问题，因此我们提出了一种基于动态规划的新方法来定位网络中节点和链路的最优位置。所提出的方法将通过示例来说明。我们还在文中给出了广泛的互联网络的实验结果，并发现所提出的方法被发现是有效的，并且适用于大型互联网络。

关键词：布局优化，动态编程，网络可靠性，互联网络。

1. 介绍

近年来在VLSI技术设计方面取得的巨大进步已经导致了强大的处理器的出现。互联网络在处理元件之间的通信中起着至关重要的作用。这种网络的设计和维护相当困难[1]。互联网络的性能主要通过确保即使出现某些故障也能够正常工作来判断[2]。换句话说，网络必须对生活中的必要应用程序具有较高可靠性。而具有高可靠性的网络的设计包含很多冗余部分，使得硬件配置增加了不必要的成本。因此，需要通过改变它们之间的节点和链路的布局来优化网络的布局，以便在一些预定的成本约束内获得更高的可靠性。由于在可靠性方面提高性能与成本密切相关，因此应该有可靠性成本折衷。这种折衷可以通过布局优化轻松实现。

网络结构，资源约束和可靠性改进方案的多样性使得优化模型的构建和分析中产生了一些主要问题，即可靠性优化问题和冗余分配问题[30]。可靠性优化问题的主要目标是通过最大限度地提高网络可靠性来节约网络中产生的成本。文献简述了许多启发式方法来解决这些问题。大多数这些方法基于人工神经网络（ANN）[4] [5]，遗传算法（GA）[6e9]，蚁群优化算法（ACO）[10]，Tabu搜索[11,12]，模拟退火法[13]和群优化算法[3]。在参考文献[3]中，Shi等人开发了一种通过最小化最大应力来最大化复合结构承载能力或强度的方法，在优化过程中采用了称为直接搜索模拟退火的随机全局搜索算法。Beltran等人[14]使用Tabu搜索方法来设计一个高度可靠的网络。他们的方法搜索一种目标是可靠性粗略替代的最小生成树（LCST）。参考文献[12]提出了设计可靠电信网络可通过考虑链路约束来取代网络可靠性的方法。参考文献[6]，Dengiz 等人开发了一种将网络可靠性优化视为20个问题进行测试的遗传基本算法。参考文献[7]提出了一种基于具有最小成本和一定可靠性约束的网络优化模型的遗传算法的进化算法。然而，它们的方法仅适用于尺寸非常小的网络模型。Walters等人[8]使用简单的遗传算法对管道网络进行结构优化，但他们没有考虑容量和可靠性。参考文献[9]中作者开发了一种考虑平均距离，直径和可靠性的遗传算法。而参考文献[5,15]中均采用人工神经网络来估计互联网络的网络可靠性。硬件状态下的冗余分配被认为是提高互联网络可靠性的重要选择。然而，随着冗余成本急剧增加，冗余分配问题就涉及到组件的同时选择以及可以共同满足所有设计约束以便优化一些目标函数的配置的系统级设计，即系统成本/可靠性。云等人在文献[16]提出了一种可以同时选择系统和模块并在子系统级别给出多级冗余的多重冗余分配问题（MMRAP）。参考文献[17]中王等人提出了可实现双目标（如可靠性最大化和成本最小化）的两个模糊随机冗余分配模型。参考文献[18]中作者提出了考虑多级可靠性配置的串联系统和串并联系统中的模块化的冗余分配优化方法。参考文献[19]中Gupta等人提出了具有组件间隔值可靠性的串联系统的约束冗余分配问题。主要解决的问题是通过惩罚函数技术的间隔系数的无约束整数规划，目的是在有限的资源限制下最大化系统可靠性。 Li等人在文献 [20]中提出了多状态串并联系统的异质冗余分配问题。他们使用通用生成函数（UGF）进行系统可靠性估计和采用遗传算法来优化系统结构。而参考文献[21]中Ding 等人也提出了使用模糊值用于性能速率和/或相应状态概率的多态系统，他们用模糊通用生成函数（FUGF）来扩展具有清晰集的生成函数。

参考文献[22]中作者讨论了在存在的常见原因故障的情况下最大化系统可靠性的冗余分配问题。Li等人在文献[23]提出了两个具有两个相互冲突目标（如系统可靠性最大化和总体系统成本最小化）的优化模型。他们称之为用于多状态加权的表决系统。参考文献[24]中讨论了分布式计算系统中的任务分配问题和可靠性优化问题。参考文献[25]中提出了使用遗传算法来解决选择冗余策略的串并联系统的优化问题。参考文献 [26]中Tian等提出了使用遗传算法的系统结构优化模式的编程方法。遗传算法还被用作通过最大化系统的服务可靠性来优化电网系统资源分配的工具[27]。文献研究表明，网络可靠性的价值下降但成本随着网络规模的增大而增加。因此，针对这类问题，最大的挑战是设计最合适的布局，以便在一些预定义的成本限制内实现最大的可靠性，我们可将其称为布局优化问题[3]。在本文中我们解决了布局优化问题，并提出了一种基于动态规划的新算法来解决这个问题。我们使用了动态规划的概念，因为与其对零件技术相反[28e30]，它总能够找到确切的解决方案。与启发式方法中的近似最优解相比，动态规划方法总能给出优化问题的确定性解决方案。这一点在本文中就得到了很好的体现。我们提出了一种新的算法来找到添加额外节点及其链接到现有互联网络的最佳位置，该算法将通过采取适当的示例来更好地理解来说明。因此，本文将对所提出的算法的融合及其重要发现进行详细说明。

本文的其余章节安排如下：第2节介绍了所提出的数学模型和算法支持的方法；第3节将说明我们提出的方法；第4节主要讨论所提出的各种网络布局优化方法的应用和所获得的结果；第5节则给出最后的结论。

2. 提出的方法

在本节中，我们将用动态规划概念来制定问题并描述拟议方法的细节，而优化问题通过算法解决。本文中使用的各种符号及说明如下2.1节所示。

2.1 符号说明

L：互联网络中编号的总数量（1~L）

N：互联网络中编号的节点总数 （L 1 ~ L N 1）.

G(N, L)：图G具有N个节点和L个链接数

Grsquo;(Nrsquo;, L#39;)：图G#39;具有N#39;个节点数和L#39;个链路数（添加n个节点和2n个链路数之后）

：优化前互联网络的初始成本

：连接节点i到节点j的链路的成本

：节点k的成本

：互联网络的最大允许成本

(i, j)：节点i和j之间的链接

X：{，，...，，...，}的链路拓扑结构

：指示G节点是否连接的决策变量——如果节点i，j相连则=1；否则=0 ()

：用于指示节点(i, N 1)之间是否存在链路的决策变量（ i = 1, 2, 3, hellip;, N ）().

R：互联网络的网络可靠性

R(X)：X的网络可靠性

：优化前互联网络的初始网络可靠性

：图G的u生成树

：节点的度

RM：G的可靠性矩阵

CM：G的成本矩阵

，：互联网络的链路可靠性和节点可靠性

：添加到互联网络进行优化的节点

：添加到互联网络进行优化的2N个链路的可靠性矩阵

：添加到互联网络中进行优化的N个节点的可靠性矩阵

：添加到互联网络进行优化的2N个链接数的成本矩阵

：添加到互联网络进行优化的N个节点的成本矩阵

2.2 问题陈述

在本小节中，我们制定了这个问题：假设节点的可靠性和成本以及给定互联网络的链路是已知的。若目标是获得最佳布局，则可能必须添加一组新的节点及其相关链接到现有网络。执行的同时，我们的主要目标是找到可以添加节点的最佳位置，以便最大限度地提高网络可靠性并同时满足一些成本约束。但是随着互联网络规模的扩大，选择适当位置的过程成为NP难题。为了克服上述困难，本文提出了一种解决这一优化问题的新方法。为此，我们遵循动态规划方法，将问题分解为子问题，每个子问题都被递归地解决。为每个可能的优化布局计算可靠性和成本，从而选择出最佳布局。

然而，在网络中添加节点和链路会增加硬件复杂性，这可能会降低互联网络的总体可靠性。在这种情况下，新节点必须连接到最佳位置，以便最小化总体可靠性的降低。换句话说，上述优化问题就是在定义的成本约束的条件内最大化互联网络的可靠性。

2.3. 模型建立

在本小节中，为了进一步分析，我们建立出所需的数学模型。互联网络的可靠性可以表示为：

其中，是初始生成树，

是图G的u生成树，

和分别是链路和节点的可靠性。

网络的总体成本是：

网络的总体成本可以计算为节点总成本和运营链路总成本的总和。如果= 1，即在（i，j）之间存在链接，则将链路视为操作链路。

我们提出了两个问题：即1个额外节点问题和n个节点问题。

1. 1个额外节点的配置问题：

将新节点添加到现有网络需要至少两个链路以确保节点级网络的最小连通性。 因此，现在的问题是找到添加新节点以及两条到现有的网络链接的适当位置。 在许多可能的可行位置中，只有部分位置能在满足网络的一些成本约束的情况下产生最大的可靠性，该部分位置则被认为是解决方案合集。

数学上可以表示为：

Max R(X)

s.t. Copt le; Cmax

则

其中，是选择节点（i，N 1）之间的链接的决策变量（i = 1,2,3，...，N）

B) n个额外节点的配置问题:

类似于1个额外节点问题的描述，n个额外的节点问题可以定义为：

Max R(X)

s.t. Copt le; Cmax

则

其中，是决策变量。通过对变量，，，...，做出一系列决策，可得该问题的解决方案。关于变量的决策要赋予0或1中的哪一个，可以做出假设上的决策参照，，...，的顺序。在决定之后，可能有两种情况：（i）网络成本较低，可靠性不增加；（ii）成本更高，可靠性获得的增加。令m是可以找到n个额外节点的适当位置的决策的总数，则是问题的最优解。

由于最优性原则成立，最优解可以写成：

广义表达式可以导出为：

令为表示的有序集（1 le; i le; m）：

令 = {(1,0)}

因此，可以通过合并/清除和来计算。

如果包含了具有和属性的（，）和（，），则因为方程（6）对（，）可以舍弃。通过这种方式舍弃一个对象被定义为遵循优势规则的清除操作，其中优势规则规定必须清除主导元组。例如，在上述（，）控制了（，）的情况中，使得（，）必须被丢弃或清除。

我们可以通过作出决策的量来获得，其值可以是0或1。当= 0时，所得状态与每个相同。 当 = 1时，从中的每个状态获得结果状态。即= 0时执行清洗操作，反之执行合并操作。

通过每个决策将遵循两个值的原则，一组决策变量，，，...，的可能性总数为。 在最坏的情况下，如果没有结果被清除，则通过合并和来获得每个（i gt; 0）的值；所以有：

其中的值为中的对数。因此，计算所有所需的时间为。

因此，合并清除（，）是通过跟随清洗操作将和转化为或使保持同样的功能。

3. 例证

所提出的算法在以下算例中进行说明。如图，图1中互联网络有6个节点和9个链路，链路和节点根据提出的编码方案进行编号。其中网络的9个链路的编号是1到9，6个节点的编号从10到15。

将一个节点和两个节点分别添加到现有网络（图1）。给定互联网络的初始成本和网络可靠性分别计算为845和0.8227894。然后，将初始化为{（1，0）}。假设要添加到网络的新节点具有成本和可靠性，分别为50和0.9。类似地，要与上述节点一起添加到现有网络的两个链路具有成本{30,20}，并且这些链路的可靠性为0.9。通过检查节点的所有可能组合，可以找到网络中在给定成本约束内产生最大可靠性的最佳位置的搜索范围。通过选择随机的节点对来随机选择初始决策变量。接着，我们为每个计算和的值，并将其添加到搜索范围。之后计算先前的应比和大的。的下一个值可以通过和的合并清除操作来计算。继续该过程，直到获得满足成本约束的所有可能的有效组合。而后跟踪则是在矩阵中完成的，且其决策变量设置为1。我们的算法是采用图1的网络布局作为输入并输出了图2优化后的互联网络。结果生成的优化网络的成本为945，可靠性为0.7609。因此，我们提出的方法在预定义的成本约束内计算出了最佳可靠的网络布局。

4. 结果与讨论

互联网络的每个元素的成本可能彼此不同。然而，为了降低问题的复杂性，假设每个节点的成本相同。我们将所提出的算法在适用于各种样本互联网络的MATLAB 7.0平台上进行模拟。为了模拟我们设置以下参数：节点和链路的可靠性设置为0.9，链路的成本按照参考设置。参考文献[6]提出了一种在考虑成本和可靠性时解决网络可靠性的设计问题的启发式搜索算法。

与文献[31]的方法相比较

文献[31]在评估互联网络的可靠性的同时解决了网络布局变化的类似问题。而本文中很好地解释了添加节点和链接到现有互联网络的后果。并且已经确定了添加这些节点和链路的最佳位置和计算了最佳可能的网络可靠性值。

为了比较的目的，上述方

全文共6047字，剩余内容已隐藏，支付完成后下载完整资料

---

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