直徑限定可靠性計算的冗余邊的檢測算法

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

（1. 華東理工大學理學院，上海 200237；2. 長春財經學院數學系，長春 130122）

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

計算二終端可靠性的問題是NP-難的問題。因子分解算法[5]是評估可靠性的有效方法。通過使用這種算法，Cancela 等[2]研究了文獻[6]中網絡的結果，這些結果也用于本文。

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

1 系統模型和冗余邊問題

1.1 系統模型

通信網絡可以通過概率圖G（V，E）在數學上建模，其中V 是節點集合，E 是邊的集合。每個節點v∈V 是完全可靠的，而每個邊e∈E 獨立地失效并且與操作概率pe（失效概率qe=1-pe）相關聯。圖1 示出了具有節點集 V={s，a，b，c，d，t}的通信網絡 G，其中源節點和終端節點分別是 s、t，邊集 E={e1，e2，...，e11}。

圖 1 通訊網絡G (V, E)Fig. 1 Communication network G (V, E)

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

文獻[5]提出了因子分解算法來計算st 可靠性，這被認為是NP-難問題?？煽啃杂嬎愕囊蜃佣ɡ恚?/p>

1.2 直徑限制二終端可靠性

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

通過因子分解定理計算：

值得注意的是，收縮邊e 得到圖 G *e 的過程可能會使原來經過邊e 的長度為D+1 的路的長度減少到D，從而導致計算Rst( G *e , D)時將多余的路徑計算在內的情況。因此，我們設定固定邊e 的狀態為1 并保留邊e 在圖中的位置不變。

1.3 冗余邊問題

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

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

與[2]中結果相比，命題1 可以被認為是路徑長度的新的度量方法，但它仍然不能完全找到冗余邊。比如在圖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 并非冗余邊。

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

圖 2 無法用命題1 判斷冗余邊的拓撲結構Fig. 2 Topology structure with irrelevant edges not identified by Proposition 1

2 檢測冗余邊的分析和算法

2.1 冗余邊的分析

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

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

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

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

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

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

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

在圖4 中，可以看到每個步驟都對上一步進行進一步度量。事實上，檢測所有冗余邊是基于SPE 的值，而不是SPE 本身。在我們的算法設計中，我們并沒有嘗試尋找SPE，而是使用SPE 的長度或其近似值。

以上分析側重于有向邊 (u, v)。對于邊（v，u），操作是相同的。不可否認，存在最短路徑不唯一的情況，實際上這并不會影響冗余邊的檢測，因為PP，RP 和CP 重復檢查兩個節點之間的最短路徑。更明確地，如果通過刪除Ck損壞了最短路徑之一，則度量將測量其他最短路徑。

表 1 路徑長度的度量標準Table 1 Metrics of path lengths

圖 4 從 PP 到 SPE 的長度Fig. 4 Length matric from PP to SPE

2.2 檢測冗余邊的算法

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

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

輸出：Rst(G, D)

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

步2：執行NRP 以獲得新網絡G0；

步3：在G0中隨機選擇邊e；

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

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

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

復雜性分析：文獻 [8]表明，對于 D=2，Rst(G,D)可以在多項式時間內確定，并且計算D, D≥3 的固定值的Rst(G, D)是NP-難問題。

3 實例分析

在本節中，我們將說明檢測冗余邊的不同拓撲，并顯示Petingi 算法與我們算法之間的比較。圖5 說明了 4 個圖：5（a）循環 C [6]; 5（b）Arpanet [6]; 5（c）歐洲光網絡[6]; 5（d）加齊大學網絡[6]。該算法被編碼為 MATLAB 程序，并在 PC（Intel Core i5; 2 450 M;2.5 GHz CPU）上實現。

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

表3 顯示了我們的算法和Petingi 算法之間冗余邊數和CPU 時間的比較，其中，IE1, T1分別為本文算 法 的 冗 余 邊 數 量 和 CPU 時 間；IE2，T2分 別 為Petingi 算法冗余邊數量和CPU 時間[2]?？偟膩碇v，Petingi 的算法和我們的算法都能有效地檢測不相關的邊緣。如果D 的值太小，則Peting 的算法更快，因為相關邊的數量很小。例如，由于網絡沒有長度為3,4 和5 的路徑，因此在D=2,3 的網絡中有20 個冗余邊（只有邊s1 和1t 是相關的）。但是，我們的算法的優點在D=4, 5, 6, 7 和8 時通過事實凸顯出來，結果見圖6。原因是我們的算法能夠在檢測冗余邊時清楚地找到PP，從而找到最內部冗余邊。因此，計算可靠性的相應CPU 時間進一步減少。最后，從s 到t 的最大距離是9，此時，我們的算法和Petingi 算法的CPU 時間接近。

圖 5 拓撲示意圖Fig. 5 Illustration of four topologies

表 2 數值結果（p=0.9）Table 2 Numerical results with p = 0.9

表 3 冗余邊的檢測及可靠性計算時間（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 結 論

我們在檢測直徑限制可靠性的冗余邊方面做了進一步的工作。提出的一些路徑長度度量來改進檢測隱藏的冗余邊的方法。實例分析結果表明所提出的算法能夠在多項式時間(O(n4))中識別更多冗余邊。