網絡端端可靠度的上下界計算研究

喬曉東，毛 志，鄧宏鐘

（國防科技大學 信息系統與管理學院，湖南 長沙 410073）

21 世紀以來，隨著信息技術的飛速發展，人類社會加快了網絡化進程。從Internet到www，從交通網絡到通信網絡，從電力網絡到物流網絡……可以說，我們被網絡包圍，幾乎所有的復雜系統都可以抽象成網絡模型，網絡已成為人們生產、生活中不可缺少的一部分。

隨著網絡技術的不斷發展與應用，對網絡的定量與定性特征的科學理解，已成為網絡時代科學研究中一個極其重要的挑戰性課題，甚至被稱為“網絡的新科學”[1]。其中網絡可靠性是對網絡定量理解的一個非常重要的參數[2]，網絡的可靠性也是保證系統正常運行的前提，因此很多先驅都投身研究網絡的可靠性問題。網絡就是有一些帶有連邊的節點組成。在網絡可靠性的研究中，人們常常用概率圖來表示網絡，圖的點和邊都分配給正常運行的概率。早期對網絡可靠性的算法研究主要為精確計算，算法包括狀態枚舉法、容斥原理法、不交積和法、因子分解法、隨機過程法等等，這些精確算法隨著網絡單元數量和復雜程度的增加，計算難度成指數增長。以狀態枚舉法為例，對于一個不考慮節點失效的含有M條邊的無向網絡來說，共有2M個狀態向量，計算量相當大，即使是計算機也難以在有意義的時間內完成計算，目前網絡可靠度的精確算法只適用于規模較小的網絡。可靠性度量參數的精確計算被Ball[3]等人證明為NP-hard問題后，研究人員開始了對近似算法的研究。近似算法主要包括定界法、蒙特卡洛法和圖形變換法[4]。所提出的這些近似算法大部分都是啟發式算法，而且無法預測計算結果的誤差大小，只有定界法避免了這個問題。定界法的主要思想就是通過數學的方法改變可靠性精確計算的代數結構，從而得到可靠性的邊界值。1972年Van Slyke和Frank[5]第一個用多項式計算網絡可靠性的上下界，1982年Ball和Provan[6]對算法進行了改進。研究者根據不同的思路提出了大量的算法來計算網絡可靠性的界，研究得比較好的界有Colboum界[7]（1988年）、Ball-Provan界[8]（2006年），2004年馮海林給出了基于網絡連通子網數與網絡割集以及斷集數的全端可靠性上下界評估法[9]，2006年Satitsatian和Kapur[10]通過尋找下界點的方法來計算多態網絡端端可靠性的下界。其中利用多項式計算網絡全端可靠性的關鍵是多項式中系數的計算，而且大部分系數的精確計算都比較困難[9]。

本文利用節點遍歷法求解網絡端端最小路，避開精確計算的不交化的復雜性，基于最小路集計算端端可靠度上界。引入端端不交最短路集的概念，來分析復雜網絡的可靠度，計算網絡端端可靠度的下界。兩個邊界算法簡單便捷，便于編程實現。最后結合實例，將計算結果與端端可靠度精確值進行比較分析，闡述本算法的有效性，并說明該算法的適用性。

1 問題描述與基本假設

1.1 基本定義

所謂一個網絡，它是由一些節點以及連接這些節點的邊組成。從數學的觀點看，網絡就是一個圖（但復雜網絡又與圖有本質區別）。為此我們給出圖的定義。

定義 1 稱數學結構 G={V（G），E（G），φG}[11]為一個圖，其中 V（G）是非空集合，φG是從集合 E（G）到 V（G）×V（G）的一個映射，則稱G是一個以V（G）為頂點集合，以E（G）為邊集合的（有向）圖。

圖中的節點是不帶圈的，即不存在從該節點流出又流入該節點的邊；圖中的邊不重復出現，即不存在同一條邊連接兩個以上的節點。

定義2 從指定節點s，經過一串邊序列可以到達節點t，則稱這個邊序列是從s到t的一條路。

定義3 從節點s到節點t的邊序列稱作一條最小路，若滿足：1）它是一條路；2）最小性，即從這個邊序列中除去任意一條邊后它將不再是從s到t的路。

定義4 沒有公共邊的端端最短路集稱為不交最短路集。

1.2 問題及基本假設

本文研究的問題是端端可靠性問題，也就是求解網絡源點s可以到達終點t的概率，本文重點對該概率的上下界進行計算。在定量計算網絡端端的可靠度時，還需做以下假設：

1）邊或系統只有兩種狀態：正常或者故障狀態；

2）節點的可靠度為1，即不考慮節點的故障；

3）每條邊之間的故障是相互獨立的，即任意一條邊的故障不會引起其他邊的故障。

2 基于最小路集的端端可靠度上界算法

上界算法的基本思路是利用節點遍歷法求出網絡端端的所有最小路集后，直接將所得到的最小路集做為端端的并聯單元，而每條最小路認為是所含各邊的一個串聯模型，這樣構成一個串并聯系統，利用這個模型計算網絡端端可靠度。由于計算過程中并沒有去除端端最小路集之間的冗余，也沒有對最小路集進行不交化處理，所以計算結果總大于精確值。

2.1 算法參數與符號說明

G—網絡的鄰接矩陣；

s—網絡源節點；

t—網絡匯節點；

E（i）—離開節點i的鏈路數，即從節點i出發，下一步可到達的節點數；

R（j，M）—路線矩陣，第j行各列元素表示從節點j出發，下一步可到達的節點的標號；

C（ j）—數組 R 第 j行元素的列號，R（ j，C（ j））記錄 j下一步到達的節點標號；

Path（v，m）—第m條路的節點序列中的第v個節點；

Um—第m條路中的節點數目；

F（K）—檢驗節點在前面是否走過以及是否到達輸出節點而設置的開關標志。

2.2 網絡端端可靠性上界算法

輸入：網絡圖的鄰接矩陣 G，源點 s，終點 t，網絡各邊的可靠度p；

輸出：網絡端端s-t可靠度的上界值Ru

Step 1初始化。

由網絡的鄰接矩陣計算得出路線矩陣R以及向量E，并對參數賦初值：n=length（G）；C=[C（1），…C（n）]，C（i）=1，i=1，…n；j=1，Path（1，1）=s，m=1，v=2；

其中Pathnum表示最小路集的條數，Rn表示第n條端端最小路的可靠度。

3 基于不交最短路集的端端可靠度下界算法

下界算法的基本思路是通過逐次刪除最短路的方法來求解網絡端端的所有不交最短路，直到網絡端端不連通為止。該算法求得的各條最短路不含有公共邊，故可以直接使用串并聯模型對其進行計算。由于算法在求解各不交最短路集的過程中，因為刪邊而減少了網絡端端路徑的數量，所以計算端端可靠度的值要小于精確值。

確定端端可靠性下界的算法如下：

輸入：網絡圖的鄰接矩陣 G，源點 s，終點 t，網絡各邊的可靠度p；

其中m表示不交最短路的條數，Rn表示第n條端端最短路的可靠度。

4 示例應用及分析

為了說明本算法，下面我們給出算例。

4.1 網絡邊的可靠性概率值恒定

圖1是由隨機網絡模型生成的含有5個節點、8條邊的隨機網絡。考慮圖1所示網絡系統從節點1到節點5的可靠度的問題，利用本文算法計算網絡端端1-5的可靠度上下界并與由BDD[12]算法計算的精確值進行比較分析。不考慮網絡節點的可靠性，對網絡邊的可靠度取p=0.01：0.01：1，比較結果如圖2所示。

圖1 ER網絡Fig.1 Random graph

很顯然Ru≤R≤Rd，當且僅當網絡系統為特殊的串并聯系統時，不等式取等號。采用本文算法對大量網絡進行測試，發現網絡端端可靠度的精確值在通常情況下可以表示為R=（Ru+Rd）/2，圖3 為本算例節點 1～5 可靠度精確值 R 與（Ru+Rd）/2 的比較結果，本例計算顯示最大誤差為0.008 95，最小誤差為0。

4.2 網絡邊的可靠性概率值變化

圖2 精確值與上下界比較Fig.2 Comparison of exactness&&upper and lower bounds

圖3 精確值與上下界均值比較Fig.3 Comparison of exactness&&average of upper and lower bounds

現實中網絡部件的可靠度并不是一成不變的，而是隨著時間連續變化，也就是說任何元部件都有一定的壽命，且其可靠度隨著時間的推移逐漸下降。本文模型可以分析網絡端端可靠性隨時間的變化情況。不失一般性，假設野戰地域通信網的基本結構圖4的邊的可靠度概率服從負指數分布，Redge（i）=P（T）=λe-λT（T＞0），分析網絡端端 5～7 的可靠度隨時間的變化情況。

圖4 基本網絡結構Fig.4 Basic network framework

在λ=0.7時，網絡5～7端端可靠度的上下界隨時間的變化情況，如圖5所示。網絡端端可靠性的上下界也隨時間呈現負指數變化規律。

5 結束語

圖5 網絡端端可靠性隨時間的變化Fig.5 Change of network terminal to terminal reliability over time

本文基于最小路集和不交最短路集對網絡端端可靠性的上下界進行了計算研究，并對大量網絡進行了仿真實驗，發現網絡端端可靠度的精確值在通常情況下可以表示為R=（Ru+Rd）/2，通過實驗比較分析，得到了較好的效果，然而如何通過算法優化網絡端端可靠度上下界，使得上界值減小、下界值增大，使二者充分接近網絡端端可靠度的精確值以及如何基于路徑并考慮網絡部件容量限制以及網絡流約束精確計算網絡的可靠性，是下一步需要研究的工作。

[1]Duncan，Watts J.The“New”science of networks[J].Annual.Review of Sociology，2004（30）：243-270.

[2]Morgan D E，Taylor D J， Custeau G.A survey of methods for improving computer network reliability and availability[J].Computers and Mathematics with Applications，1977，11：42-50.

[3]Ball M O.Complexity of network reliability computations[J].Networks，1980，10（2）：153-165.

[4]李瑞瑩，康銳.網絡可靠性評價研究綜述[J].可靠性工程，2008：1-6.

LI Rui-ying，Kang rui.Review on evaluation of network reliability[J].Reliability Engineering，2008，1-6.

[5]Van.Slyke R M，Frank H.Network reliability analysis I[J].Networks，1972，（1）：279-290.

[6]Ball M，Provan J.S Bounds on the reliability polynomial for shellable independence systems[J].SIAM J.Alg.Disc.Meth，1982，（3）：166-181.

[7]Brecht T B，Colbourn C J.Lower bounds on two-terminal network reliability[J].Discrete Applied Mathematics，1988，21（3）：185-198.

[8]Ball M O，Provan J S.Calculating bounds on reachability and connectedness in stochastic networks[J].Networks，2006，13（2）：253-278.

[9]馮海林.網絡系統可靠性問題的研究 [D].西安：西安電子科技大學，2004.

[10]Satitsatian S，Kapur C K.An algorithm for lower reliability boundsofmultistatetwo-terminalnetworks[J].IEEE Transactions on Reliability， 2006， 55 （2）：199-206.

[11]殷劍宏，吳開亞.圖論及其算法研究[M].中國科學技術大學出版社，2003.

[12]武小悅，沙基昌.網絡系統可靠度的BDD算法[J].系統工程與電子技術，1999，21（7）：1-4.

WU Xiao-yue，SHA Ji-chang.A BDD algorithm for network reliability[J].Systems Engineering and Electronics，1999，21（7）：1-4.