[k]最短可靠路徑及其優(yōu)化問題

張震霄 管建民 邵方明

摘 ?要： [k]最短路徑在邊失效模型中，存在一個(gè)等長路徑的選擇問題，基于可靠性的選擇是有效的解決方案。 這里提出了一種[k]最短路徑限制下的可靠性模型來度量[k]最短路徑，進(jìn)一步把等長路徑的選擇問題轉(zhuǎn)化為一個(gè)可靠性優(yōu)化問題，即選擇使得可靠性最大的[k]最短路徑。最終通過設(shè)計(jì)近似算法有效地解決了優(yōu)化問題，實(shí)例證明了該算法的有效性。

關(guān)鍵詞： 網(wǎng)絡(luò)可靠性; [k]最短可靠路徑; 子網(wǎng)絡(luò); 路徑優(yōu)化; 優(yōu)化策略; 邊失效模型

中圖分類號： TN711?34 ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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 ?引 ?言

網(wǎng)絡(luò)可靠性已廣泛應(yīng)用于許多領(lǐng)域，如信息物理系統(tǒng)[1]、無線傳感器網(wǎng)絡(luò)[2?3]、空間通信網(wǎng)絡(luò)[4]。在二態(tài)網(wǎng)絡(luò)中，網(wǎng)絡(luò)的組件具有兩種狀態(tài)：失效、正常運(yùn)行。網(wǎng)絡(luò)可靠性是網(wǎng)絡(luò)魯棒性的重要指標(biāo)，可以視為幸存鏈路和節(jié)點(diǎn)生成運(yùn)行子網(wǎng)絡(luò)的概率。在經(jīng)典的可靠性度量中，源節(jié)點(diǎn)?目標(biāo)節(jié)點(diǎn)（[s?t]）可靠性描述了在一對節(jié)點(diǎn)之間至少存在一條可運(yùn)行路徑的概率。因此[s?t]可靠性可以作為二態(tài)網(wǎng)絡(luò)的一個(gè)衡量指標(biāo)?？煽啃杂?jì)算領(lǐng)域也取得了一些好的結(jié)果。文獻(xiàn)[5]提出了因子分解算法來計(jì)算[s?t]的可靠性，如式（1）所示：

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

式中：[G*e]是通過粘連邊[e]的兩個(gè)節(jié)點(diǎn)獲得的網(wǎng)絡(luò);[G-e]是通過刪除邊[e]獲得的網(wǎng)絡(luò);[p]是邊[e]正常運(yùn)行的概率。由于[s?t]可靠性的計(jì)算是NP難問題[6]，許多研究人員通過研究近似算法估計(jì)網(wǎng)絡(luò)可靠性[7?8]。

在網(wǎng)絡(luò)中，Dijkstra算法[9]解決了最短路徑問題，其在路徑導(dǎo)航系統(tǒng)和其他領(lǐng)域都有廣泛的應(yīng)用。作為最短路徑問題的推廣，[k]最短路徑問題，即對于給定的[k]，為每對[s?t]選擇[k]條最短路徑，已經(jīng)有相當(dāng)多的研究。例如，文獻(xiàn)[10]提出了一種在無線傳感器網(wǎng)絡(luò)中使用多條不同路徑進(jìn)行路由任務(wù)的方法。文獻(xiàn)[11]表明，[k]最短路徑路由可以在高性能計(jì)算集群和未來的大規(guī)模數(shù)據(jù)中心中提供更好的性能，因?yàn)樗浞掷昧司W(wǎng)絡(luò)容量。

[k]最短路徑算法也有很多研究工作。文獻(xiàn)[12]的算法是較著名的算法之一，它利用最短路徑算法考慮偏離路徑節(jié)點(diǎn)。該算法實(shí)現(xiàn)了[O（k*n*SP（n，m））]的復(fù)雜度，其中，[SP（n，m）]是所使用的最短路徑算法的復(fù)雜度[13]，[m，n]分別是網(wǎng)絡(luò)的邊和節(jié)點(diǎn)的數(shù)量。

在邊二態(tài)網(wǎng)絡(luò)中，網(wǎng)絡(luò)中節(jié)點(diǎn)是正常運(yùn)行的，邊是失效或正常運(yùn)行的，將該網(wǎng)絡(luò)模型表示為[G（V，E，p）]，其中，[V]是邊集，[E]是點(diǎn)集，[p]是邊正常運(yùn)行的概率。假設(shè)網(wǎng)絡(luò)中的每個(gè)邊具有相同的獨(dú)立運(yùn)行概率[p]，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都是完美的，并且假設(shè)[s?t]存在[k]最短路徑。在傳統(tǒng)的[k]最短路徑算法中沒有考慮到可靠性問題，在本文中考慮了[k]最短路徑約束的[s?t]可靠性，并發(fā)現(xiàn)[k]最短路徑路由中也存在可靠性問題。通過使用可靠性模型優(yōu)化[k]最短路徑集，本文提出了[k]最短可靠路徑優(yōu)化問題。由于所提出的可靠性計(jì)算是NP難問題，本文還提出了[k]最短可靠路徑優(yōu)化問題的近似算法。最后，實(shí)驗(yàn)結(jié)果證明了該算法的有效性。

1 ?[k]最短路徑問題和可靠性

1.1 ?[k]最短路徑選擇問題

[k]最短路徑是對[s?t]選擇[k]條最短路徑，并且僅從路徑長度的角度選擇路徑。同時(shí)，在選擇[k]最短路徑的過程中，可能存在相等長度的路徑選擇問題。因此，有時(shí)候[k]最短路徑的選擇不是唯一的。

例如，在圖1a）中，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別為1，4且[k]=2，因?yàn)榇嬖?個(gè)長度相等的第2最短路徑，所以存在兩個(gè)2最短路徑集。圖1b）表示一個(gè)2最短路徑集[{A1=154，A12=1234}]，而圖1c）是另一個(gè)2最短路徑集[{A1=154，A22=1254}]。由圖1可以看出，在選擇[k]最短路徑的過程中存在等長路徑的選擇問題。接下來，當(dāng)路徑長度相等時(shí)，考慮哪個(gè)路徑集更好。

1.2 ?[k]最短可靠路徑

在[k]最短路徑中，不包含在[k]最短路徑集中的邊是無關(guān)邊。因此，只考慮包含[k]最短路徑的子網(wǎng)絡(luò)。子網(wǎng)絡(luò)[G12]和[G22]分別由[{A1，A12}]，[{A1，A22}]組成。參考文獻(xiàn)[14]中關(guān)于[s?t]可靠性的定義：

定義1：對于網(wǎng)絡(luò)[G]，[s?t]可靠性是在[s]和[t]之間至少存在一條路徑且其所有鏈路都可正常運(yùn)行的概率，記為[Rst（G）]。

對于兩個(gè)不同的子網(wǎng)絡(luò)[G12]和[G22]的[s?t]可靠性分別是[R14（G12）=p2+p3-p5]和[R14（G22）=][p2+p3-p4]。顯然，[R114（G12）≥R214（G22）]，子網(wǎng)絡(luò)的[s?t]可靠性是不同的，但是它們的路徑長度是相等的。因此，子網(wǎng)絡(luò)的可靠性可以作為[k]最短路徑的選擇度量，定義如下：

定義2：對于網(wǎng)絡(luò)[G]，[k]最短路徑組成的子網(wǎng)絡(luò)是指從[s]到[t]的[k]最短路徑集[{A1，A2，…，Ak}]組成的網(wǎng)絡(luò)，記為[Gk]。

定義3：對于網(wǎng)絡(luò)[G]，[k]最短路徑限制下的[s?t]可靠性是由[k]最短路徑組成的子網(wǎng)絡(luò)[Gk]的[s?t]可靠性，記為[Rskt（G）]。

從上述定義顯然可以得到：

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

由圖1發(fā)現(xiàn)不同的[k]最短路徑集可能得到不同的可靠性[Rskt（G）]，盡管它們的[k]最短路徑的長度是相同的。定義1和定義3表明[Rskt（G）]是[Gk]中[s]和[t]之間至少有一條可正常運(yùn)行路徑的概率。為了在實(shí)現(xiàn)[k]最短路徑下的[s?t]之間信息的可靠傳輸，考慮使得可靠性[Rskt（G）]最大的[k]最短路徑的優(yōu)化問題。在數(shù)學(xué)上該優(yōu)化問題陳述如下：

優(yōu)化問題：對于給定的[k]，[G（V，E，p）]中的節(jié)點(diǎn)[s]，[t]，找到使得[Rskt（G）]最大的[k]最短路徑集合，表示為：

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

定義4：對于給定的[k]，[G（V，E，p）]中的節(jié)點(diǎn)[s]，[t]，[k]最短可靠路徑集是對應(yīng)于[R*]的[k]最短路徑集，記為[S*]。

傳統(tǒng)的[k]最短路徑問題主要集中在路徑長度而不考慮可靠性。算法1直接使用文獻(xiàn)[15]中的[k]最短路徑算法和式（1）計(jì)算[Gk]的[s?t]可靠性。

算法1：計(jì)算[G（V，E，p）]的[Rskt]

輸入：連通圖[G=（V，E，p），s，t，k]

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

步驟1：找到[s]到[t]的[k]最短路徑。

步驟2：對于[k]最短路徑組成的子網(wǎng)絡(luò)[Gk]，計(jì)算[Rskt（G）=Rst（Gk）]。

2 ?優(yōu)化問題算法

2.1 ?優(yōu)化問題的精確算法

算法1沒有考慮[k]最短可靠路徑問題。優(yōu)化問題的解決主要有兩個(gè)過程：找到所有不同的子網(wǎng)絡(luò)[Gk];計(jì)算可靠性[Rst（Gk）]。首先產(chǎn)生不同[k]最短路徑集的原因是長度等于第[k]條最短路徑的路徑不是唯一的。因此，需要找到長度等于第[k]條最短路徑的所有路徑，其次對于第二個(gè)過程，可以使用因子分解算法（式（1））計(jì)算[Rst（Gk）]。詳細(xì)步驟見算法2。

算法2：計(jì)算[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：對于每個(gè)[k]最短路徑集[Si][∈][S]，[RisktG=Rst（Gik）]。

步驟5：[R*]=max [RisktG]，同時(shí)得到對應(yīng)的[S*]。

算法2是解決優(yōu)化問題的精確算法，步驟1～4是獲得所有由[k]最短路徑集組成的子網(wǎng)絡(luò)，步驟5是計(jì)算對應(yīng)的可靠性并返回最大的可靠性和[k]最短可靠路徑集合。

算法2可以在圖1中闡釋，其中[s]=1，[t]=4，[k]=2，邊正常運(yùn)行的概率[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最短路徑集，子網(wǎng)絡(luò)[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和對應(yīng)的2最短可靠路徑集[S*=]{[A1]，[A2]}。

算法2是優(yōu)化問題的精確算法。算法1是不考慮不同子網(wǎng)絡(luò)下的算法。算法1和算法2的相同部分是都計(jì)算了[s?t]可靠性[Rst（G）]。 然而，[Rst（G）]的計(jì)算是NP難問題[6]。因此有必要使用近似算法解決優(yōu)化問題。

2.2 ?優(yōu)化問題的近似算法

由于計(jì)算[s?t]可靠性是NP難問題，許多研究人員研究了近似算法來估計(jì)網(wǎng)絡(luò)可靠性。文獻(xiàn)[7]提出了一種蒙特卡羅模擬算法，用于估計(jì)二態(tài)網(wǎng)絡(luò)的[s?t]網(wǎng)絡(luò)可靠性。對于每個(gè)由[k]最短路徑組成的子網(wǎng)絡(luò)，使用Yeh算法而不是因子分解算法來估計(jì)[Rst（Gk）]。然后，用算法3解決優(yōu)化問題。

算法3：計(jì)算[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：對于每個(gè)[k]最短路徑集[Si][∈][S]，通過Yeh算法得到[Rst（Gik）]，進(jìn)而得到[RisktG=Rst（Gik）]。

步驟5：[R*]=max [RisktG]，得到對應(yīng)的[S*]。

通過算法3重新計(jì)算圖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]，進(jìn)行步驟4。

步驟4：對于2最短路徑集，子網(wǎng)絡(luò)[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，對應(yīng)的2最短可靠路徑集[S*]={[A1]，[A2]}。

3 ?實(shí)驗(yàn)結(jié)果

在圖2中，網(wǎng)絡(luò)[G]，[s]=1，[t]=6且邊的概率是[p]=0.9。在圖3中，[G1]，[G2]，[G3]是[G]的三個(gè)子網(wǎng)絡(luò)。

表1表示對應(yīng)不同[k]的三種算法的CPU運(yùn)行時(shí)間。當(dāng)[k]很小時(shí)，算法1具有最短的CPU運(yùn)行時(shí)間，但是隨著[k]的增加，時(shí)間將更長。算法2具有最長的CPU運(yùn)行時(shí)間，并且隨著[k]的增加，時(shí)間將更長，因?yàn)閇Rst（G）]的計(jì)算是NP難問題。雖然當(dāng)[k]=6時(shí)算法3的CPU運(yùn)行時(shí)間比算法1 長，但算法3的CPU運(yùn)行時(shí)間隨著[k]的增加沒有太大變化。

表2展示了三種算法得到的子網(wǎng)絡(luò)。[G2]，[G3]，[G]是算法2的子網(wǎng)絡(luò)，并且具有最大的可靠性。算法1沒有考慮可靠性問題，因此，當(dāng)[k]=6，19時(shí)，子網(wǎng)絡(luò)不是最可靠的子網(wǎng)絡(luò)。算法3可實(shí)現(xiàn)與精確算法2相同的子網(wǎng)絡(luò)。

表3顯示了三種算法的[k]最短路徑限制下的[s?t]可靠性。算法1和算法2實(shí)現(xiàn)了子網(wǎng)絡(luò)的精確可靠性計(jì)算。算法3利用Yeh算法估計(jì)子網(wǎng)絡(luò)的可靠性。當(dāng)[k]=6，13，19時(shí)，算法3的錯(cuò)誤率分別為0.06%，0.39%，0.14%。雖然算法3沒有得到可靠的精確值，但誤差并不大，運(yùn)行時(shí)間較短且子網(wǎng)絡(luò)在表2中與精確算法2相同。

4 ?結(jié) ?論

[k]最短路徑中存在如何選擇等長路徑的問題，可靠性可以度量等長路徑和建立優(yōu)化問題模型。本文提出了精確算法和近似算法來解決[k]最短可靠路徑優(yōu)化問題。最后通過實(shí)驗(yàn)近似算法有效地找到[k]最短可靠路徑。該算法對于[k]最短路徑的選擇可以為高性能計(jì)算集群和未來的大規(guī)模數(shù)據(jù)中心提供更好的性能支持。

參考文獻(xiàn)

[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] 諸震亞，邵方明.基于可靠性在結(jié)構(gòu)健康監(jiān)測系統(tǒng)中的備份點(diǎn)布控研究[J].現(xiàn)代電子技術(shù)，2019，42（4）：148?152.

[4] 李云飛.空間通信中的網(wǎng)絡(luò)可靠性分析[J].現(xiàn)代電子技術(shù)，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.