李瑞瑩,黨 煒
(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)用說明.
對有源網(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時的特例.
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ī)定的時間.
網(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點(diǎn)假設(shè):① 各端點(diǎn)、鏈路間故障相互獨(dú)立;②各端點(diǎn)、鏈路只有故障、正常兩種狀態(tài).
將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可靠度,算法如下:
以圖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)
下面按照第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)可靠度.
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.