[k]最短可靠路径及其优化问题

张震霄 管建民 邵方明

摘  要： [k]最短路径在边失效模型中，存在一个等长路径的选择问题，基于可靠性的选择是有效的解决方案。 这里提出了一种[k]最短路径限制下的可靠性模型来度量[k]最短路径，进一步把等长路径的选择问题转化为一个可靠性优化问题，即选择使得可靠性最大的[k]最短路径。最终通过设计近似算法有效地解决了优化问题，实例证明了该算法的有效性。

关键词： 网络可靠性; [k]最短可靠路径; 子网络; 路径优化; 优化策略; 边失效模型

中图分类号： TN711?34                         文献标识码： A                          文章编号： 1004?373X（2020）23?0058?04

Abstract： In the edge failure model， it is required to select paths with equal length for the [k]?shortest paths. The reliability?based selection is an effective solution. In this paper， a reliability model under the constraint of [k]?shortest paths is proposed to measure the [k]?shortest paths， and convert the selection of paths with equal length to the optimization of the paths， that is， to choose the [k]?shortest paths with maximum reliability. In the end， an approximate algorithm is designed to realize the optimization effectively. The examples shows the effectiveness of the algorithm.

Keywords： network reliability; [k]?shortest reliable path; subnetwork; path optimization; optimization strategy; edge failure model

0  引  言

网络可靠性已广泛应用于许多领域，如信息物理系统[1]、无线传感器网络[2?3]、空间通信网络[4]。在二态网络中，网络的组件具有两种状态：失效、正常运行。网络可靠性是网络鲁棒性的重要指标，可以视为幸存链路和节点生成运行子网络的概率。在经典的可靠性度量中，源节点?目标节点（[s?t]）可靠性描述了在一对节点之间至少存在一条可运行路径的概率。因此[s?t]可靠性可以作为二态网络的一个衡量指标。可靠性计算领域也取得了一些好的结果。文献[5]提出了因子分解算法来计算[s?t]的可靠性，如式（1）所示：

[Rst（G）=pRst（G*e）+（1-p）Rst（G-e）] （1）

式中：[G*e]是通过粘连边[e]的两个节点获得的网络;[G-e]是通过删除边[e]获得的网络;[p]是边[e]正常运行的概率。由于[s?t]可靠性的计算是NP难问题[6]，许多研究人员通过研究近似算法估计网络可靠性[7?8]。

在网络中，Dijkstra算法[9]解决了最短路径问题，其在路径导航系统和其他领域都有广泛的应用。作为最短路径问题的推广，[k]最短路径问题，即对于给定的[k]，为每对[s?t]选择[k]条最短路径，已经有相当多的研究。例如，文献[10]提出了一种在无线传感器网络中使用多条不同路径进行路由任务的方法。文献[11]表明，[k]最短路径路由可以在高性能计算集群和未来的大规模数据中心中提供更好的性能，因为它充分利用了网络容量。

[k]最短路径算法也有很多研究工作。文献[12]的算法是较著名的算法之一，它利用最短路径算法考虑偏离路径节点。该算法实现了[O（k*n*SP（n，m））]的复杂度，其中，[SP（n，m）]是所使用的最短路径算法的复杂度[13]，[m，n]分别是网络的边和节点的数量。

在边二态网络中，网络中节点是正常运行的，边是失效或正常运行的，将该网络模型表示为[G（V，E，p）]，其中，[V]是边集，[E]是点集，[p]是边正常运行的概率。假设网络中的每个边具有相同的独立运行概率[p]，网络中的每个节点都是完美的，并且假设[s?t]存在[k]最短路径。在传统的[k]最短路径算法中没有考虑到可靠性问题，在本文中考虑了[k]最短路径约束的[s?t]可靠性，并发现[k]最短路径路由中也存在可靠性问题。通过使用可靠性模型优化[k]最短路径集，本文提出了[k]最短可靠路径优化问题。由于所提出的可靠性计算是NP难问题，本文还提出了[k]最短可靠路径优化问题的近似算法。最后，实验结果证明了该算法的有效性。

1  [k]最短路径问题和可靠性

1.1  [k]最短路径选择问题

[k]最短路径是对[s?t]选择[k]条最短路径，并且仅从路径长度的角度选择路径。同时，在选择[k]最短路径的过程中，可能存在相等长度的路径选择问题。因此，有时候[k]最短路径的选择不是唯一的。

例如，在图1a）中，源节点和目标节点分别为1，4且[k]=2，因为存在2个长度相等的第2最短路径，所以存在两个2最短路径集。图1b）表示一个2最短路径集[{A1=154，A12=1234}]，而图1c）是另一个2最短路径集[{A1=154，A22=1254}]。由图1可以看出，在选择[k]最短路径的过程中存在等长路径的选择问题。接下来，当路径长度相等时，考虑哪个路径集更好。

1.2  [k]最短可靠路径

在[k]最短路径中，不包含在[k]最短路径集中的边是无关边。因此，只考虑包含[k]最短路径的子网络。子网络[G12]和[G22]分别由[{A1，A12}]，[{A1，A22}]组成。参考文献[14]中关于[s?t]可靠性的定义：

定义1：对于网络[G]，[s?t]可靠性是在[s]和[t]之间至少存在一条路径且其所有链路都可正常运行的概率，记为[Rst（G）]。

对于两个不同的子网络[G12]和[G22]的[s?t]可靠性分别是[R14（G12）=p2+p3-p5]和[R14（G22）=][p2+p3-p4]。显然，[R114（G12）≥R214（G22）]，子网络的[s?t]可靠性是不同的，但是它们的路径长度是相等的。因此，子网络的可靠性可以作为[k]最短路径的选择度量，定义如下：

定义2：对于网络[G]，[k]最短路径组成的子网络是指从[s]到[t]的[k]最短路径集[{A1，A2，…，Ak}]组成的网络，记为[Gk]。

定义3：对于网络[G]，[k]最短路径限制下的[s?t]可靠性是由[k]最短路径组成的子网络[Gk]的[s?t]可靠性，记为[Rskt（G）]。

从上述定义显然可以得到：

[Rskt（G）=Rst（Gk）] （2）

由图1发现不同的[k]最短路径集可能得到不同的可靠性[Rskt（G）]，尽管它们的[k]最短路径的长度是相同的。定义1和定义3表明[Rskt（G）]是[Gk]中[s]和[t]之间至少有一条可正常运行路径的概率。为了在实现[k]最短路径下的[s?t]之间信息的可靠传输，考虑使得可靠性[Rskt（G）]最大的[k]最短路径的优化问题。在数学上该优化问题陈述如下：

优化问题：对于给定的[k]，[G（V，E，p）]中的节点[s]，[t]，找到使得[Rskt（G）]最大的[k]最短路径集合，表示为：

[R*=max Rskt（G）] （3）

定义4：对于给定的[k]，[G（V，E，p）]中的节点[s]，[t]，[k]最短可靠路径集是对应于[R*]的[k]最短路径集，记为[S*]。

传统的[k]最短路径问题主要集中在路径长度而不考虑可靠性。算法1直接使用文献[15]中的[k]最短路径算法和式（1）计算[Gk]的[s?t]可靠性。

算法1：计算[G（V，E，p）]的[Rskt]

输入：连通图[G=（V，E，p），s，t，k]

输出：图[G=（V，E，p）]的可靠性[Rskt]

步骤1：找到[s]到[t]的[k]最短路径。

步骤2：对于[k]最短路径组成的子网络[Gk]，计算[Rskt（G）=Rst（Gk）]。

2  优化问题算法

2.1  优化问题的精确算法

算法1没有考虑[k]最短可靠路径问题。优化问题的解决主要有两个过程：找到所有不同的子网络[Gk];计算可靠性[Rst（Gk）]。首先产生不同[k]最短路径集的原因是长度等于第[k]条最短路径的路径不是唯一的。因此，需要找到长度等于第[k]条最短路径的所有路径，其次对于第二个过程，可以使用因子分解算法（式（1））计算[Rst（Gk）]。详细步骤见算法2。

算法2：计算[G（V，E，p）]最大的[Rskt（Gk）]和[S*]的精确算法

输入：连通图[G=（V，E，p）]，[s]，[t]，[k]。

输出：图[G=（V，E，p）]的可靠性[R*]， [k]最短可靠路径集[S*]。

步骤1：令[H=k+1]，[S=][?]。

步骤2：找到[H]最短路径，[S={A1，A2，…，AH-1}]。

步骤3：如果[AH-1

步骤4：对于每个[k]最短路径集[Si][∈][S]，[RisktG=Rst（Gik）]。

步骤5：[R*]=max [RisktG]，同时得到对应的[S*]。

算法2是解决优化问题的精确算法，步骤1～4是获得所有由[k]最短路径集组成的子网络，步骤5是计算对应的可靠性并返回最大的可靠性和[k]最短可靠路径集合。

算法2可以在图1中阐释，其中[s]=1，[t]=4，[k]=2，边正常运行的概率[p=]0.9。

步骤1：[H=]3，[S=][?]。

步骤2：找到3最短路径[{A1=154，A2=1234，A3=1254}]。

步骤3：[A2=A3]， 因此[H]=4，返回步骤2。

步驟2：找到4最短路径[A4=]16784。

步骤3：[A3

步骤4：对于2最短路径集，子网络[G12]和[G22]分别由{[A1]，[A2]}和{[A1]，[A3]}组成。[R1124（G）=R14（G12）=p2+p3-p5=]0.948 51，[R2124（G）=R14（G22）=p2+p3-p4=]0.882 90。

步骤5：[R*=]max [Riskt（G）]=0.948 51和对应的2最短可靠路径集[S*=]{[A1]，[A2]}。

算法2是优化问题的精确算法。算法1是不考虑不同子网络下的算法。算法1和算法2的相同部分是都计算了[s?t]可靠性[Rst（G）]。 然而，[Rst（G）]的计算是NP难问题[6]。因此有必要使用近似算法解决优化问题。

2.2  优化问题的近似算法

由于計算[s?t]可靠性是NP难问题，许多研究人员研究了近似算法来估计网络可靠性。文献[7]提出了一种蒙特卡罗模拟算法，用于估计二态网络的[s?t]网络可靠性。对于每个由[k]最短路径组成的子网络，使用Yeh算法而不是因子分解算法来估计[Rst（Gk）]。然后，用算法3解决优化问题。

算法3：计算[G（V，E，p）]最大的[Rskt（Gk）]和[S*]的近似算法

输入：连通图[G=（V，E，p）]，[s]，[t]，[k]。

输出：图[G=（V，E，p）]的可靠性[R*]，[k]最短可靠路径集[S*]。

步骤1：令[H=k+1]，[S=][?]。

步骤2：找到[H]最短路径，[S={A1，A2，…，AH-1}]。

步骤3：如果[AH-1

步骤4：对于每个[k]最短路径集[Si][∈][S]，通过Yeh算法得到[Rst（Gik）]，进而得到[RisktG=Rst（Gik）]。

步骤5：[R*]=max [RisktG]，得到对应的[S*]。

通过算法3重新计算图1，令[s]=1，[t]=4，[k]=2，边的概率为[p]=0.9。

步骤1：[H]=3，[S=][?]。

步骤2：找到3最短路径{[A1=154]，[A2=]1234，[A3=]1254}。

步骤3：[A2]=[A3]， 因此[H]=4，返回步骤2。

步骤2：找到4最短路径[A4]=16784。

步骤3：[A3]<[A4]，进行步骤4。

步骤4：对于2最短路径集，子网络[G12]和[G22]分别由{[A1]，[A2]}和{[A1]，[A3]}组成。通过Yeh算法，[R1124（G）=][R14（G12）]=0.955 8，[R2124（G）=R14]（[G22]）=0.896 4。

步骤5：[R*]=max [Riskt（G）]=0.955 8，对应的2最短可靠路径集[S*]={[A1]，[A2]}。

3  实验结果

在图2中，网络[G]，[s]=1，[t]=6且边的概率是[p]=0.9。在图3中，[G1]，[G2]，[G3]是[G]的三个子网络。

表1表示对应不同[k]的三种算法的CPU运行时间。当[k]很小时，算法1具有最短的CPU运行时间，但是随着[k]的增加，时间将更长。算法2具有最长的CPU运行时间，并且随着[k]的增加，时间将更长，因为[Rst（G）]的计算是NP难问题。虽然当[k]=6时算法3的CPU运行时间比算法1 长，但算法3的CPU运行时间随着[k]的增加没有太大变化。

表2展示了三种算法得到的子网络。[G2]，[G3]，[G]是算法2的子网络，并且具有最大的可靠性。算法1没有考虑可靠性问题，因此，当[k]=6，19时，子网络不是最可靠的子网络。算法3可实现与精确算法2相同的子网络。

表3显示了三种算法的[k]最短路径限制下的[s?t]可靠性。算法1和算法2实现了子网络的精确可靠性计算。算法3利用Yeh算法估计子网络的可靠性。当[k]=6，13，19时，算法3的错误率分别为0.06%，0.39%，0.14%。虽然算法3没有得到可靠的精确值，但误差并不大，运行时间较短且子网络在表2中与精确算法2相同。

4  结  论

[k]最短路径中存在如何选择等长路径的问题，可靠性可以度量等长路径和建立优化问题模型。本文提出了精确算法和近似算法来解决[k]最短可靠路径优化问题。最后通过实验近似算法有效地找到[k]最短可靠路径。该算法对于[k]最短路径的选择可以为高性能计算集群和未来的大规模数据中心提供更好的性能支持。

参考文献

[1] ZHANG Zuyuan， AN Wei， SHAO Fangming. Cascading fai?lures on reliability in cyber?physical system [J]. IEEE transactions on reliability， 2016， 65（4）： 1745?1754.

[2] AN Wei， SHAO Fangming， MENG Huajun. The coverage?control optimization in sensor network subject to sensing area [J]. Computers & mathematics with applications， 2009， 57（4）： 529?539.

[3] 诸震亚，邵方明.基于可靠性在结构健康监测系统中的备份点布控研究[J].现代电子技术，2019，42（4）：148?152.

[4] 李云飞.空间通信中的网络可靠性分析[J].现代电子技术，2012，35（23）：45?48.

[5] MOSKOWITZ F. The analysis of redundancy networks [J]. Transactions of the American institute of electrical engineers， Part I： communication and electronics， 1958， 77（5）： 627?632.

[6] SNOW A P. Network reliability： the concurrent challenges of innovation， competition， and complexity [J]. IEEE transactions on reliability， 2001， 50（1）： 38?40.

[7] YEH W?C， LIN Y?C， CHUNG Y?Y. Performance analysis of cellular automata Monte Carlo simulation for estimating network reliability [J]. Expert systems with applications， 2010， 37（5）： 3537?3544.

[8] CANCELA H， ROBLEDO F， RUBINO G. Monte Carlo estimation of diameter?constrained network reliability conditioned by pathsets and cutsets [J]. Computer communications， 2013， 36（6）： 611?620.

[9] DIJKSTRA E W. A note on two problems in connection with graphs [J]. Numerische mathematik， 1959， 1（1）： 269?271.

[10] HENAO?MAZO W， BRAVO?SANTOS ?. Finding diverse shortest paths for the routing task in wireless sensor networks [C]// The Seventh International Conference on Systems and Networks Communications. Lisbon： s.n.， 2012： 53?58.

[11] SINGLA A， HONG C?Y， POPA L S， et al. Jellyfish： networking data centers randomly [C]// Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2012： 1?17.

[12] YEN J Y. Finding the [k] shortest loopless paths in a network [J]. Management science， 1971， 17（11）： 712?716.

[13] SCANO G， HUGUET M?J， NGUEVEU S U. Adaptations of [k]?shortest path algorithms for transportation networks [C]// International Conference on Industrial Engineering & Systems Management. Seville， Spain： IEEE， 2015： 663?669.

[14] NIU Yifeng， SHAO Fangming. A practical bounding algorithm for computing two?terminal reliability based on decomposition technique [J]. Computers & mathematics with applications， 2011， 61（8）： 2241?2246.

[15] FENG G. Improving space efficiency with path length prediction for finding [k] shortest simple paths [J]. IEEE transactions on computers， 2014， 63（10）： 2459?2472.