直徑限定可靠性計(jì)算的冗余邊的檢測(cè)算法

熊祥軍， 邵方明， 張祖淵， 管建民

（1. 華東理工大學(xué)理學(xué)院，上海 200237；2. 長(zhǎng)春財(cái)經(jīng)學(xué)院數(shù)學(xué)系，長(zhǎng)春 130122）

經(jīng)典的二終端網(wǎng)絡(luò)可靠性是指源節(jié)點(diǎn)s 和終端節(jié)點(diǎn)t 之間存在至少一個(gè)操作路徑的概率，但是不考慮對(duì)st-路長(zhǎng)度的限制。通過(guò)限制所有st-路的長(zhǎng)度不超過(guò)給定正整數(shù)D，Petingi 等[1]最初將直徑限制引入網(wǎng)絡(luò)可靠性（DCR）。Cancela 等[2]研究了通信網(wǎng)絡(luò)的直徑限制可靠性模型，并提出了一種多項(xiàng)式時(shí)間算法，用于檢測(cè)和刪除冗余邊，以計(jì)算具有直徑限制的簡(jiǎn)單無(wú)向圖的二終端可靠性。在DCR 模型中，檢測(cè)冗余邊的必要條件尚未得到解決。此外，文獻(xiàn)[3]中做了進(jìn)一步的工作。文獻(xiàn)[4]中將s，K-直徑定義為源節(jié)點(diǎn)s 與K 中任意節(jié)點(diǎn)之間的最大距離，使用控制以提出一種簡(jiǎn)單的方法來(lái)計(jì)算s，K-直徑不大于給定值D 時(shí)的可靠性。然而，檢測(cè)冗余邊的必要條件仍然是一個(gè)懸而未決的問(wèn)題。

計(jì)算二終端可靠性的問(wèn)題是NP-難的問(wèn)題。因子分解算法[5]是評(píng)估可靠性的有效方法。通過(guò)使用這種算法，Cancela 等[2]研究了文獻(xiàn)[6]中網(wǎng)絡(luò)的結(jié)果，這些結(jié)果也用于本文。

多項(xiàng)式時(shí)間拓?fù)錃w約在直徑限制可靠性的計(jì)算中起重要作用，因?yàn)樵S多冗余邊能夠被刪除并且可靠性保持不變。然而，以往對(duì)冗余邊的研究并不全面。檢測(cè)冗余邊的必要條件是所謂的開(kāi)放問(wèn)題。在本文中，我們基于文獻(xiàn)[7]定義路徑長(zhǎng)度的新度量方法，將 st-路徑分類為實(shí)際路徑（RP），偽路徑（PP），組合路徑（CP），包含特定邊的最短 st-路徑（SPE）并明確指出通過(guò)測(cè)量PP、RP 和CP 可以得出SPE 的長(zhǎng)度。此外，我們提出了一種檢測(cè)隱藏冗余邊的算法，該算法的復(fù)雜度是多項(xiàng)式的(O(n4))。

1 系統(tǒng)模型和冗余邊問(wèn)題

1.1 系統(tǒng)模型

通信網(wǎng)絡(luò)可以通過(guò)概率圖G（V，E）在數(shù)學(xué)上建模，其中V 是節(jié)點(diǎn)集合，E 是邊的集合。每個(gè)節(jié)點(diǎn)v∈V 是完全可靠的，而每個(gè)邊e∈E 獨(dú)立地失效并且與操作概率pe（失效概率qe=1-pe）相關(guān)聯(lián)。圖1 示出了具有節(jié)點(diǎn)集 V={s，a，b，c，d，t}的通信網(wǎng)絡(luò) G，其中源節(jié)點(diǎn)和終端節(jié)點(diǎn)分別是 s、t，邊集 E={e1，e2，...，e11}。

圖 1 通訊網(wǎng)絡(luò)G (V, E)Fig. 1 Communication network G (V, E)

定義 1[1]：由 Rst(G)表示的st 可靠性是指源點(diǎn)s 和匯點(diǎn)t 之間至少存在一條連通路徑的概率。

文獻(xiàn)[5]提出了因子分解算法來(lái)計(jì)算st 可靠性，這被認(rèn)為是NP-難問(wèn)題?？煽啃杂?jì)算的因子定理：

1.2 直徑限制二終端可靠性

定義3：直徑限制下的二終端可靠性是指至少存在一條長(zhǎng)度小于D 的st 路徑，記為Rst(G, D)。

通過(guò)因子分解定理計(jì)算：

值得注意的是，收縮邊e 得到圖 G *e 的過(guò)程可能會(huì)使原來(lái)經(jīng)過(guò)邊e 的長(zhǎng)度為D+1 的路的長(zhǎng)度減少到D，從而導(dǎo)致計(jì)算Rst( G *e , D)時(shí)將多余的路徑計(jì)算在內(nèi)的情況。因此，我們?cè)O(shè)定固定邊e 的狀態(tài)為1 并保留邊e 在圖中的位置不變。

1.3 冗余邊問(wèn)題

Petingi 等[3]提出檢測(cè)冗余邊的充分條件。

命題1：e=uv 是存在于圖G 某個(gè)st-路上的邊。如果 dG-e(s, u)+dG-e(v, t)≥D 和 dG-e(s, v)+dG-e(u, t)≥D，則邊e 是冗余邊。

與[2]中結(jié)果相比，命題1 可以被認(rèn)為是路徑長(zhǎng)度的新的度量方法，但它仍然不能完全找到冗余邊。比如在圖2 中，給定D=5，冗余邊e=bc。從命題1，dG-e(s, b)+dG-e(c, t)=4＜D 并 且 dG-e(s, c)+dG-e(b, t)=4＜D可知e=bc 并非冗余邊。

造成這種現(xiàn)象的原因是該度量?jī)H考慮路徑長(zhǎng)度，但忽略了從源點(diǎn)s 到點(diǎn)u 和點(diǎn)v 到匯點(diǎn)t（從s 到v 和u 到t）的路徑的具體信息以及路徑的組合是否包含給定邊uv。因此dG-e(s, u)+dG-e(v, t) 和 dG-e(s, v)+dG-e(u, t)的度量仍然需要進(jìn)一步改進(jìn)。

圖 2 無(wú)法用命題1 判斷冗余邊的拓?fù)浣Y(jié)構(gòu)Fig. 2 Topology structure with irrelevant edges not identified by Proposition 1

2 檢測(cè)冗余邊的分析和算法

2.1 冗余邊的分析

設(shè)定 P1, P2, …, Pm都為包含邊 e 的 st-路，

定理 1：如果 min1≤i≤m|Pi|＞D，則 e 為不相關(guān)邊。

顯 而 易 見(jiàn) ，min1≤i≤m|Pi|＞D 意 味 著 所 有 包 含 邊e 的st-路徑的長(zhǎng)度大于D，因此邊e 必然為冗余邊。反之，如果邊e 為冗余邊，則所有包含邊e 的st-路徑的長(zhǎng)度大于 D，例如，min1≤i≤m|Pi|＞D。

為了更有效地檢測(cè)冗余邊，我們考慮包含邊e（SPE）的最短 st-路徑[3]。如果找到 SPE，則肯定會(huì)完全檢測(cè)到所有冗余邊。但是，Petingi 等[3]證明找到SPE 的問(wèn)題是NP-難的。我們希望在多項(xiàng)式時(shí)間內(nèi)找到接近SPE 長(zhǎng)度的值，并使用該值與D 進(jìn)行比較以確定冗余邊。

對(duì)于節(jié)點(diǎn) x，y，Px,y表示從 x 到 y 的最短路徑之一。對(duì)于邊 e=uv，我們稱 Ps,u∪(u, v)∪Pv,t和 Ps,v∪(v, u)∪Pu,t分別為 u，v-path 和 v，u-path。為方便起見(jiàn)，我們只討論如何處理 u，v-paths 并對(duì) v，u-paths 進(jìn)行相同的操作。

推論1：包含邊uv 的最短路徑然必然是包含u，v-paths 和 v，u-paths 中最短的路徑。

圖 3 RP 和 CP 的示例Fig. 3 An example for RP and CP

在圖4 中，可以看到每個(gè)步驟都對(duì)上一步進(jìn)行進(jìn)一步度量。事實(shí)上，檢測(cè)所有冗余邊是基于SPE 的值，而不是SPE 本身。在我們的算法設(shè)計(jì)中，我們并沒(méi)有嘗試尋找SPE，而是使用SPE 的長(zhǎng)度或其近似值。

以上分析側(cè)重于有向邊 (u, v)。對(duì)于邊（v，u），操作是相同的。不可否認(rèn)，存在最短路徑不唯一的情況，實(shí)際上這并不會(huì)影響冗余邊的檢測(cè)，因?yàn)镻P，RP 和CP 重復(fù)檢查兩個(gè)節(jié)點(diǎn)之間的最短路徑。更明確地，如果通過(guò)刪除Ck損壞了最短路徑之一，則度量將測(cè)量其他最短路徑。

表 1 路徑長(zhǎng)度的度量標(biāo)準(zhǔn)Table 1 Metrics of path lengths

圖 4 從 PP 到 SPE 的長(zhǎng)度Fig. 4 Length matric from PP to SPE

2.2 檢測(cè)冗余邊的算法

將歸約過(guò)程整合到因子分解定理中，我們得到可靠性計(jì)算程序（RCP）：

輸入：G (V, E)，源點(diǎn) s，匯點(diǎn) t，p，直徑限制 D

輸出：Rst(G, D)

步1：如果G 直徑小于或等于D，執(zhí)行步3；否則執(zhí)行步2；

步2：執(zhí)行NRP 以獲得新網(wǎng)絡(luò)G0；

步3：在G0中隨機(jī)選擇邊e；

步4：遞歸計(jì)算Rst(G*e, D)；

步5：遞歸計(jì)算Rst(G-e, D)；

步 6：Rst(G, D)=pRst(G*e, D)+qRst(G-e, D)。

復(fù)雜性分析：文獻(xiàn) [8]表明，對(duì)于 D=2，Rst(G,D)可以在多項(xiàng)式時(shí)間內(nèi)確定，并且計(jì)算D, D≥3 的固定值的Rst(G, D)是NP-難問(wèn)題。

3 實(shí)例分析

在本節(jié)中，我們將說(shuō)明檢測(cè)冗余邊的不同拓?fù)?，并顯示Petingi 算法與我們算法之間的比較。圖5 說(shuō)明了 4 個(gè)圖：5（a）循環(huán) C [6]; 5（b）Arpanet [6]; 5（c）歐洲光網(wǎng)絡(luò)[6]; 5（d）加齊大學(xué)網(wǎng)絡(luò)[6]。該算法被編碼為 MATLAB 程序，并在 PC（Intel Core i5; 2 450 M;2.5 GHz CPU）上實(shí)現(xiàn)。

表2 顯示了所提算法和Petingi 算法[2]之間冗余邊數(shù)和CPU 時(shí)間的比較，其中，*IE1, T1分別為本文算法的冗余邊數(shù)量和 CPU 時(shí)間；IE2, T2分別為Petingi 算法冗余邊數(shù)量和 CPU 時(shí)間[2]；T：未減少計(jì)算可靠性的CPU 時(shí)間。當(dāng)D=3 時(shí)，在圖5（a）中檢測(cè)到兩個(gè)冗余邊，并且CPU 時(shí)間節(jié)省0.007 6 s。當(dāng)D=5 時(shí)，我們?cè)趫D 5（b）中找到兩個(gè)冗余邊，CPU 時(shí)間節(jié)省4.439 s。在許多例中，通過(guò)使用我們的算法可以完全找到冗余邊。通常，冗余邊的數(shù)量與直徑限制 D 密切相關(guān)。例如，在圖 5（c）和表 2 中，D 越小，冗余邊越多，CPU 時(shí)間越少。當(dāng)D＜7 時(shí)，我們的算法檢測(cè)到的冗余邊比Petingi 算法更多。然而，當(dāng)D=7 時(shí)，Petingi 算法的冗余邊數(shù)與我們的相同，并且CPU 時(shí)間相近。

表3 顯示了我們的算法和Petingi 算法之間冗余邊數(shù)和CPU 時(shí)間的比較，其中，IE1, T1分別為本文算 法 的 冗 余 邊 數(shù) 量 和 CPU 時(shí) 間；IE2，T2分 別 為Petingi 算法冗余邊數(shù)量和CPU 時(shí)間[2]?？偟膩?lái)講，Petingi 的算法和我們的算法都能有效地檢測(cè)不相關(guān)的邊緣。如果D 的值太小，則Peting 的算法更快，因?yàn)橄嚓P(guān)邊的數(shù)量很小。例如，由于網(wǎng)絡(luò)沒(méi)有長(zhǎng)度為3,4 和5 的路徑，因此在D=2,3 的網(wǎng)絡(luò)中有20 個(gè)冗余邊（只有邊s1 和1t 是相關(guān)的）。但是，我們的算法的優(yōu)點(diǎn)在D=4, 5, 6, 7 和8 時(shí)通過(guò)事實(shí)凸顯出來(lái)，結(jié)果見(jiàn)圖6。原因是我們的算法能夠在檢測(cè)冗余邊時(shí)清楚地找到PP，從而找到最內(nèi)部冗余邊。因此，計(jì)算可靠性的相應(yīng)CPU 時(shí)間進(jìn)一步減少。最后，從s 到t 的最大距離是9，此時(shí)，我們的算法和Petingi 算法的CPU 時(shí)間接近。

圖 5 拓?fù)涫疽鈭DFig. 5 Illustration of four topologies

表 2 數(shù)值結(jié)果（p=0.9）Table 2 Numerical results with p = 0.9

表 3 冗余邊的檢測(cè)及可靠性計(jì)算時(shí)間（p=0.9）Table 3 Detection of irrelevant edges and computation of reliability for p = 0.9

圖 6 比較不同D 值的示意圖Fig. 6 An illustration for comparison of different values of D

4 結(jié) 論

我們?cè)跈z測(cè)直徑限制可靠性的冗余邊方面做了進(jìn)一步的工作。提出的一些路徑長(zhǎng)度度量來(lái)改進(jìn)檢測(cè)隱藏的冗余邊的方法。實(shí)例分析結(jié)果表明所提出的算法能夠在多項(xiàng)式時(shí)間(O(n4))中識(shí)別更多冗余邊。