網(wǎng)絡(luò)端端可靠度的上下界計算研究

喬曉東，毛 志，鄧宏鐘

（國防科技大學(xué) 信息系統(tǒng)與管理學(xué)院，湖南 長沙 410073）

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

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

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

1 問題描述與基本假設(shè)

1.1 基本定義

所謂一個網(wǎng)絡(luò)，它是由一些節(jié)點以及連接這些節(jié)點的邊組成。從數(shù)學(xué)的觀點看，網(wǎng)絡(luò)就是一個圖（但復(fù)雜網(wǎng)絡(luò)又與圖有本質(zhì)區(qū)別）。為此我們給出圖的定義。

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

圖中的節(jié)點是不帶圈的，即不存在從該節(jié)點流出又流入該節(jié)點的邊；圖中的邊不重復(fù)出現(xiàn)，即不存在同一條邊連接兩個以上的節(jié)點。

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

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

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

1.2 問題及基本假設(shè)

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

1）邊或系統(tǒng)只有兩種狀態(tài)：正?；蛘吖收蠣顟B(tài)；

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

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

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

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

2.1 算法參數(shù)與符號說明

G—網(wǎng)絡(luò)的鄰接矩陣；

s—網(wǎng)絡(luò)源節(jié)點；

t—網(wǎng)絡(luò)匯節(jié)點；

E（i）—離開節(jié)點i的鏈路數(shù)，即從節(jié)點i出發(fā)，下一步可到達的節(jié)點數(shù)；

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

C（ j）—數(shù)組 R 第 j行元素的列號，R（ j，C（ j））記錄 j下一步到達的節(jié)點標(biāo)號；

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

Um—第m條路中的節(jié)點數(shù)目；

F（K）—檢驗節(jié)點在前面是否走過以及是否到達輸出節(jié)點而設(shè)置的開關(guān)標(biāo)志。

2.2 網(wǎng)絡(luò)端端可靠性上界算法

輸入：網(wǎng)絡(luò)圖的鄰接矩陣 G，源點 s，終點 t，網(wǎng)絡(luò)各邊的可靠度p；

輸出：網(wǎng)絡(luò)端端s-t可靠度的上界值Ru

Step 1初始化。

由網(wǎng)絡(luò)的鄰接矩陣計算得出路線矩陣R以及向量E，并對參數(shù)賦初值：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表示最小路集的條數(shù)，Rn表示第n條端端最小路的可靠度。

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

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

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

輸入：網(wǎng)絡(luò)圖的鄰接矩陣 G，源點 s，終點 t，網(wǎng)絡(luò)各邊的可靠度p；

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

4 示例應(yīng)用及分析

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

4.1 網(wǎng)絡(luò)邊的可靠性概率值恒定

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

圖1 ER網(wǎng)絡(luò)Fig.1 Random graph

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

4.2 網(wǎng)絡(luò)邊的可靠性概率值變化

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

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

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

圖4 基本網(wǎng)絡(luò)結(jié)構(gòu)Fig.4 Basic network framework

在λ=0.7時，網(wǎng)絡(luò)5～7端端可靠度的上下界隨時間的變化情況，如圖5所示。網(wǎng)絡(luò)端端可靠性的上下界也隨時間呈現(xiàn)負指數(shù)變化規(guī)律。

5 結(jié)束語

圖5 網(wǎng)絡(luò)端端可靠性隨時間的變化Fig.5 Change of network terminal to terminal reliability over time

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

[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]李瑞瑩，康銳.網(wǎng)絡(luò)可靠性評價研究綜述[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，F(xiàn)rank 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]馮海林.網(wǎng)絡(luò)系統(tǒng)可靠性問題的研究 [D].西安：西安電子科技大學(xué)，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].中國科學(xué)技術(shù)大學(xué)出版社，2003.

[12]武小悅，沙基昌.網(wǎng)絡(luò)系統(tǒng)可靠度的BDD算法[J].系統(tǒng)工程與電子技術(shù)，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.