李瑞瑩，黨 煒

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

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

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

1 基本概念

1.1 經典有源網絡可靠性參數

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

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

1.2 新的有源網絡可靠性參數

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

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

圖1 新參數與其他有源網絡可靠性參數的關系

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

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

2 算法

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

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

2.1 假設

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

2.2 基于容斥原理的算法

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

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

該部分算法可表述如下:

Combine(G，N，k，s)

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

∥輸入:指定端點集合N的端點個數n、需要選出的端點個數k

∥輸出:返回Ckn種端點組合K'i

fori←1 tokdo

K'［i］←i

K'［i+1］←n+1∥集合K與源點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'

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

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

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

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

∥K樹的枚舉算法

∥輸入:圖G(V，E，Φ)，端點組合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 ∥鏈路條數計數

else

A［a］［b］←0

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

j=0

forp←1 tokdo

E［p］←p

con=0 ∥連通個數計數

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為起始端點

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

Visited(v)←1con←con+1

for鄰接于v的每個端點wdo

ifVisited(w)=0

DFS(Ki'，E，w)

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

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

3 示例

3.1 示例說明

以圖2所示網絡拓撲結構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.將網絡中各端點可靠度記為Rvi(i=1，2，…，4)，鏈路可靠度記為Rej(j=1，2，…，5).令v4為源點，N={v1，v2，v3}，k=2，求解S(k/N)T可靠度

圖2 示例的網絡拓撲結構

3.2 基于容斥原理的計算

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

1)列舉從端點子集N={v1，v2，v3}中任意取2個端點的組合，即滿足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)根據圖G(V，E，Φ)，找出連接集合K'i中各端點的鏈路集Ei，得到子圖Gi如圖3所示.

圖3 子圖Gi

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

圖4 子圖Gi對應的K樹

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

若令網絡中各端點可靠度相同，為0.90，鏈路可靠度也相同，為0.99，根據式(3)，可得

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

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

4 結論

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

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

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

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］ 江逸楠，李瑞瑩，黃 寧，等.網絡可靠性評估方法綜述［J］.計算機科學，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］ 王 芳，侯朝楨.大型網絡的SKT可靠性的分散計算法［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］ 李曉明，黃振杰.圖中樹的數目:計算及其在網絡可靠性中的作用［M］.哈爾濱:哈爾濱工業(yè)大學出版社，1993:114.