一種新的有源網(wǎng)絡(luò)可靠性參數(shù)及其算法

李瑞瑩，黨 煒

(1.北京航空航天大學(xué)可靠性與系統(tǒng)工程學(xué)院，北京100191;2.北京航空航天大學(xué)可靠性與環(huán)境工程技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100191;3.中國科學(xué)院空間應(yīng)用工程與技術(shù)中心，北京100094)

隨著科技的迅速發(fā)展，通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、交通網(wǎng)絡(luò)已經(jīng)成為人們生產(chǎn)、生活不可缺少的一部分.對網(wǎng)絡(luò)定量與定性特征的科學(xué)理解，已成為網(wǎng)絡(luò)時代科學(xué)研究中一個極其重要的挑戰(zhàn)性課題，甚至被稱為“網(wǎng)絡(luò)的新科學(xué)”［1］.網(wǎng)絡(luò)在建立起物質(zhì)、信息、能量傳遞橋梁的同時，也為故障傳播提供了條件.網(wǎng)絡(luò)可靠性水平對網(wǎng)絡(luò)能否正常運(yùn)轉(zhuǎn)起著至關(guān)重要的作用，一旦網(wǎng)絡(luò)故障，就可能造成重大甚至是災(zāi)難性的影響.因此，網(wǎng)絡(luò)可靠性成為了網(wǎng)絡(luò)定量理解中的重要問題.1955年，Lee在對電信交換網(wǎng)絡(luò)的研究過程中首次定義了連通可靠性，開啟了網(wǎng)絡(luò)可靠性的研究.根據(jù)網(wǎng)絡(luò)中有沒有固定的源點(diǎn)，網(wǎng)絡(luò)可分為無源網(wǎng)絡(luò)和有源網(wǎng)絡(luò).D.R.Shier［2］總結(jié)了有源網(wǎng)絡(luò)的3類網(wǎng)絡(luò)可靠性參數(shù)，包括Moore和Shannon提出的“ST可靠度”、“SAT可靠度”以及Moskowitz提出的“SKT可靠度”.這3類參數(shù)已成為有源網(wǎng)絡(luò)的經(jīng)典可靠性參數(shù)，數(shù)十年以來，研究者一直致力于這些參數(shù)的算法研究，如J.L.Cook和J.E.Ramirez-Marquez［3］提出了基于蒙特卡洛仿真的無線網(wǎng)絡(luò)ST可靠度算法;R.Mishra 和 S.K.Chaturvedi［4］提出了一種基于不交積的無冗余ST可靠度算法等等，文獻(xiàn)［5］對此進(jìn)行了詳細(xì)的綜述.然而，上述參數(shù)僅能描述源點(diǎn)到指定端點(diǎn)集中所有端點(diǎn)間的連通概率(即將故障判據(jù)為“與指定端點(diǎn)集中任意端點(diǎn)失去連通路徑”)，卻無法對指定端點(diǎn)集中部分端點(diǎn)的連通能力進(jìn)行度量.現(xiàn)實(shí)生活中，往往僅需要了解源點(diǎn)與部分端點(diǎn)間的連通能力是多少，而并不需要確切地知曉源點(diǎn)與具體哪些端點(diǎn)失去了連接.例如，移動通信需要實(shí)現(xiàn)90%用戶的接入能力，卻并不太關(guān)心這些用戶是誰;又如野戰(zhàn)通信網(wǎng)的故障判據(jù)［6］為網(wǎng)絡(luò)內(nèi)15%的端點(diǎn)傳輸中斷，該判據(jù)與傳輸中斷端點(diǎn)數(shù)量有關(guān)、與具體端點(diǎn)無關(guān).

文中在ST、SAT、SKT這3類有源網(wǎng)絡(luò)可靠性參數(shù)的基礎(chǔ)上，提出一個新的有源網(wǎng)絡(luò)可靠性參數(shù)——S(k/N)T可靠度，詳細(xì)說明該參數(shù)的度量范圍及與經(jīng)典參數(shù)的關(guān)系，并通過“組合連通集-尋找K樹-應(yīng)用容斥原理計算”的方法為該參數(shù)給出一種精確算法，最后用案例進(jìn)行應(yīng)用說明.

1 基本概念

1.1 經(jīng)典有源網(wǎng)絡(luò)可靠性參數(shù)

對有源網(wǎng)絡(luò)G(V，E)，其中V是網(wǎng)絡(luò)中的端點(diǎn)集，E是鏈路集.G(V，E)的經(jīng)典可靠性參數(shù)包括［2］:① ST 可靠度(source-to-terminal reliability):用于度量網(wǎng)絡(luò)中兩個端點(diǎn)s和t(s∈V，t∈V且s≠t)之間保持連通的概率;② SAT可靠度(source-to-all terminal reliability):用于度量網(wǎng)絡(luò)中源點(diǎn)s(s∈V)和網(wǎng)絡(luò)中其他所有端點(diǎn)之間保持連通的概率;③SKT可靠度(source-to-K-terminal reliability):用于描述網(wǎng)絡(luò)的源點(diǎn)s與指定端點(diǎn)集K(s∈V，s?K且K?V)中全部端點(diǎn)保持連通的概率.

由此可知，ST可靠度和SAT可靠度分別是SKT可靠度在k=v-1(k，v分別為端點(diǎn)子集K的端點(diǎn)數(shù)和網(wǎng)絡(luò)G(V，E)的端點(diǎn)總數(shù))和k=1時的特例.

1.2 新的有源網(wǎng)絡(luò)可靠性參數(shù)

S(k/N)T可靠度是為了考察有源網(wǎng)絡(luò)中指定端點(diǎn)集K中部分端點(diǎn)的連通能力而提出的，其定義如下:S(k/N)T可靠度指網(wǎng)絡(luò)G(V，E)在規(guī)定條件下和規(guī)定時間內(nèi)，某個指定端點(diǎn)s與端點(diǎn)子集N中至少k個端點(diǎn)之間能連通的概率，記作RS(k/N)T(t)，其中，N?V，s∈V且s?N.

特殊地，當(dāng)k=n時，S(k/N)T可靠度就是SKT可靠度;當(dāng)k=v-1時，S(k/N)T可靠度就是原來的SAT可靠度;當(dāng)n=1時，S(k/N)T可靠度就是ST可靠度.這也就是說，SKT可靠度、SAT可靠度和ST可靠度是S(k/N)T可靠度的特殊情況.新參數(shù)在有源網(wǎng)絡(luò)可靠性參數(shù)中的位置如圖1所示.

圖1 新參數(shù)與其他有源網(wǎng)絡(luò)可靠性參數(shù)的關(guān)系

S(k/N)T可靠度可表示為

式中:RS(k/N)T(t)是t時刻網(wǎng)絡(luò)G(V，E)的S(k/N)T可靠度;ξS(k/N)T是指定端點(diǎn)s與端點(diǎn)子集N中能相互連通的端點(diǎn)個數(shù)少于k前的工作時間;t是網(wǎng)絡(luò)規(guī)定的時間.

2 算法

網(wǎng)絡(luò)可靠性的算法包括2類:一類是精確算法，如狀態(tài)枚舉法、容斥原理法、不交積和法、因子分解法等［7］;另一類是近似算法，包括圖變換法［8］、定界法［9］等.

對于SKT可靠度，直接的計算方法是枚舉網(wǎng)絡(luò)中所有K樹(這里指能使源點(diǎn)s與指定端點(diǎn)集K連通的最小的鏈路和端點(diǎn)的集合)［10］，再對這些K樹進(jìn)行不交化運(yùn)算從而求出網(wǎng)絡(luò)的SKT可靠度.對于文中提出的S(k/N)T可靠度，可以枚舉出指定端點(diǎn)集N中k個端點(diǎn)的組合Ki，只要源點(diǎn)s與任意Ki連通，則S(k/N)T可靠性的連通條件就得到了滿足，由此將問題轉(zhuǎn)化為SKT可靠度求解問題.考慮到容斥原理法的簡潔性和計算效率，文中首先給出基于容斥原理的算法.

2.1 假設(shè)

算法的2點(diǎn)假設(shè):① 各端點(diǎn)、鏈路間故障相互獨(dú)立;②各端點(diǎn)、鏈路只有故障、正常兩種狀態(tài).

2.2 基于容斥原理的算法

將S(k/N)T可靠性的連通條件化解為若干個K樹隨后再應(yīng)用容斥原理便可計算出網(wǎng)絡(luò)的S(k/N)T可靠度.由此，基于容斥原理的算法步驟如下:

1)列舉從端點(diǎn)子集N中任意取k個端點(diǎn)的組合，若N中共有n個端點(diǎn)，則共有Ckn種組合，記作K1，K2，…，KCkn.將源點(diǎn)s與Ki結(jié)合起來，得到新的集合K'i=Ki+{s}.

該部分算法可表述如下:

Combine(G，N，k，s)

∥生成從指定端點(diǎn)集N中n個端點(diǎn)中選k個端點(diǎn)的所有組合，并與源點(diǎn)s組合在一起

∥輸入:指定端點(diǎn)集合N的端點(diǎn)個數(shù)n、需要選出的端點(diǎn)個數(shù)k

∥輸出:返回Ckn種端點(diǎn)組合K'i

fori←1 tokdo

K'［i］←i

K'［i+1］←n+1∥集合K與源點(diǎn)s合并

w riteK'

whileK'［1］＜n-k+1 do

∥遞歸算法，返回下一個組合

j←k

whileK'［j］＞ =n-k+jdo

j←j-1i←j

K'［i］←K'［i］+1

forj←i+1 tokdo

K'［j］←K'［j-1］+1

w riteK'

顯然，上述組合求解算法復(fù)雜度為O(n2).

2)根據(jù)圖G(V，E，Φ)中的鏈路集E，找出連接集合Ki中各端點(diǎn)的鏈路集Ei，二者共同構(gòu)成圖G(V，E，Φ)的子圖Gi(K'i，Ei，Φi).子圖Gi通過鄰接矩陣A和關(guān)聯(lián)矩陣M表示.

下面求解對于子圖Gi中的樹，也就是求解SKT可靠度過程中的K樹.由于“G是一棵樹”與“G是連通的，且其中鏈路數(shù)=端點(diǎn)數(shù)-1”等價［11］，可知圖Gi中樹的鏈路數(shù)為k.對這些鏈路集Ei求解k條鏈路的組合，再檢查這些鏈路的組合是否能滿足端點(diǎn)集K'i中任意兩個端點(diǎn)連通的條件，檢查時可采用深度優(yōu)先遍歷，如無法遍歷則去掉該鏈路組合.剩余的鏈路組合即是Gi的樹，分別記作{Gi1，Gi2，…，Gij}，將這些樹合并成{G1，G2，…，Gr}.

對每個K子圖Gi求解K樹的算法可表述如下:EnumerateKTree(G，K')

∥K樹的枚舉算法

∥輸入:圖G(V，E，Φ)，端點(diǎn)組合Ki'

∥輸出:K樹Gij

m=0

fora←1 ton+1 do

forb←1 toa-1 do

ifa∈Ki'andb∈Ki'

A［a］［b］←Φ ∥鄰接矩陣

If A［a］［b］≠0

m=m+1 ∥鏈路條數(shù)計數(shù)

else

A［a］［b］←0

∥求解從m條鏈路選取k條組合，并檢查是否滿足連通條件

j=0

forp←1 tokdo

E［p］←p

con=0 ∥連通個數(shù)計數(shù)

DFS(Ki'，E，v) ∥深度優(yōu)先遍歷

ifcon=k

j=j+1

Gij←E+Ki'

w riteGij

whileE［1］＜m-k+1 do

∥遞歸算法，返回下一個組合

q←k

whileE［q］＞ =m-k+qdo

q←q-1p←q

E［p］←E［p］+1

forq←p+1 tokdo

E［q］←E［q-1］+1con=0

DFS(Ki'，E，V)

ifcon=k

j=j+1

Gij←E+Ki'

w riteGij

DFS(Ki'，E，v) ∥v為起始端點(diǎn)

∥在Ki'與E組成的圖中，通過深度優(yōu)先遍歷，檢查任意兩個節(jié)點(diǎn)間是否存在鏈路

Visited(v)←1con←con+1

for鄰接于v的每個端點(diǎn)wdo

ifVisited(w)=0

DFS(Ki'，E，w)

顯然，上述組合求解算法復(fù)雜度也為O(n2).

3)采用容斥原理計算S(k/N)T可靠度，算法如下:

3 示例

3.1 示例說明

以圖2所示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G(V，E，Φ)為例計算S(k/N)T 可靠度.其中，V={v1，v2，v3，v4}，E={e1，e2，e3，e4，e5}，Φ(e1)=v1v2，Φ(e2)=v1v3，Φ(e3)=v2v3，Φ(e4)=v2v4，Φ(e5)=v3v4.將網(wǎng)絡(luò)中各端點(diǎn)可靠度記為Rvi(i=1，2，…，4)，鏈路可靠度記為Rej(j=1，2，…，5).令v4為源點(diǎn)，N={v1，v2，v3}，k=2，求解S(k/N)T可靠度

圖2 示例的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3.2 基于容斥原理的計算

下面按照第2節(jié)中基于容斥原理的網(wǎng)絡(luò)S(k/N)T可靠度計算方法進(jìn)行計算:

1)列舉從端點(diǎn)子集N={v1，v2，v3}中任意取2個端點(diǎn)的組合，即滿足S(k/N)T連通的各種組合，有C23=3 種，分別是K1={v1，v2}，K2={v1，v3}，K3={v2，v3}.令K'i=Ki+{v4}，即K'1={v1，v2，v4}，K'2={v1，v3，v4}，K'3={v2，v3，v4}.

2)根據(jù)圖G(V，E，Φ)，找出連接集合K'i中各端點(diǎn)的鏈路集Ei，得到子圖Gi如圖3所示.

圖3 子圖Gi

對子圖Gi求解K樹.對G1和G2，由于子圖鏈路數(shù)恰等于k=2，且鏈路集合E能保證端點(diǎn)集K'1和K'2中任意兩個端點(diǎn)間連通，故子圖G1和G2對應(yīng)的K樹如圖4a，4b所示.對于G3，通過鏈路組合和通性檢驗(yàn)可知，其對應(yīng)的K樹如圖4c所示.

圖4 子圖Gi對應(yīng)的K樹

3)采用容斥原理對S(k/N)T可靠度的計算如下:

若令網(wǎng)絡(luò)中各端點(diǎn)可靠度相同，為0.90，鏈路可靠度也相同，為0.99，根據(jù)式(3)，可得

圖5反映了端點(diǎn)和鏈路可靠度變化對本案例網(wǎng)絡(luò)S(k/N)T可靠度的影響.其中圖5a是鏈路可靠性不變的情況下，網(wǎng)絡(luò)S(k/N)T可靠度隨端點(diǎn)可靠度的變化;圖5b是端點(diǎn)可靠性不變的情況下，網(wǎng)絡(luò)S(k/N)T可靠度隨鏈路可靠度的變化.

由圖5可以看出，端點(diǎn)可靠度的變化對網(wǎng)絡(luò)S(k/N)T可靠度有較大的影響，從優(yōu)化網(wǎng)絡(luò)可靠性的角度應(yīng)優(yōu)先提高端點(diǎn)可靠度.

4 結(jié)論

1)針對現(xiàn)有的有源網(wǎng)絡(luò)可靠性參數(shù)無法度量源點(diǎn)與指定端點(diǎn)集中部分端點(diǎn)間連通概率的問題，提出了S(k/N)T可靠度這一新的有源網(wǎng)絡(luò)可靠度參數(shù).

2)基于容斥原理法給出了該參數(shù)的精確計算方法，通過轉(zhuǎn)化S(k/N)T可靠性的連通條件解決了S(k/N)T可靠度的計算問題.該算法適用于系統(tǒng)二態(tài)性、故障獨(dú)立性假設(shè)前提，同時考慮了端點(diǎn)故障和鏈路對網(wǎng)絡(luò)可靠性的影響.

3)文中提出的基于容斥原理的算法尚存在計算復(fù)雜度大，不適用于大規(guī)模網(wǎng)絡(luò)應(yīng)用的問題.從已經(jīng)開展的網(wǎng)絡(luò)可靠性各類參數(shù)的精確算法研究可知，這一問題難以通過精確計算的方法解決.因此，對于大規(guī)模網(wǎng)絡(luò)的計算還需結(jié)合SKT可靠度的近似算法進(jìn)一步的研究.

References)

［1］ Watts D J.The ″new″science of networks［J］.Annual Review of Sociology，2004，30:243-270.

［2］ Shier D R.Network Reliability and Algebraic Structures［M］.Oxford:Clarendon Press，1991.

［3］ Cook JL，Ramirez-Marquez JE.Reliability for clusterbased Ad-hoc networks［C］∥Proceedings of Annual Reliability and Maintainability Symposium.Las Vegas:IEEE，2008，doi:10.1109/RAMS.2008.4925802.

［4］ Mishra R，Chaturvedi S K.A cutsets-based unified framework to evaluate network reliability measures［J］.IEEE Transactions on Reliability，2009，58(4):658-666.

［5］ 江逸楠，李瑞瑩，黃 寧，等.網(wǎng)絡(luò)可靠性評估方法綜述［J］.計算機(jī)科學(xué)，2012，39(5):9-13，18.Jiang Yinan，LiRuiying，Huang Ning，et al.Survey on network reliability evaluation methods［J］Computer Science，2012，39(5):9-13，18.(in Chinese)

［6］ 中國人民解放軍總裝備部.GJB 1909A:裝備可靠性維修性保障性要求論證［S］.2009.

［7］ Terruggia R.Reliability analysis of probabilistic networks［D］.University of Turin，2010:33-42.

［8］ Rebaiaia M L，Ait-Kadi D，Merlano A.A practical algorithm for network reliability evaluation based on the factoring theorem:a case study of a generic radiocommunication system［J］.Journal of Quality，2009，16(5):323-336.

［9］ Mohamed M H S，Yang Xiaozong，Liu Hongwei，et al.An efficient algorithm for reliability lower bound of distributed systems［J］.World Academy of Science，Engineering and Technology，2009，27:40-42.

［10］ 王 芳，侯朝楨.大型網(wǎng)絡(luò)的SKT可靠性的分散計算法［J］.計算機(jī)工程，2003，29(18):18-19，156.Wang Fang，Hou Chaozhen.Using decomposition method to calculate SKT reliability of large-scale network［J］.Computer Engineering，2003，29(18):18-19，156.(in Chinese)

［11］ 李曉明，黃振杰.圖中樹的數(shù)目:計算及其在網(wǎng)絡(luò)可靠性中的作用［M］.哈爾濱:哈爾濱工業(yè)大學(xué)出版社，1993:114.