李瑞瑩 任武越

（北京航空航天大學(xué) 可靠性與系統(tǒng)工程學(xué)院，北京 100191）

基于啟發(fā)式算法的網(wǎng)絡(luò)可靠性分配方法

李瑞瑩 任武越

（北京航空航天大學(xué) 可靠性與系統(tǒng)工程學(xué)院，北京 100191）

由于網(wǎng)絡(luò)的結(jié)構(gòu)特殊性，已有的經(jīng)典可靠性分配方法難以直接應(yīng)用.在AGREE（Advisory Group on Reliability of Electronic Equipment）方法的基礎(chǔ)上，根據(jù)網(wǎng)絡(luò)可靠性與部件可靠性的函數(shù)關(guān)系確定網(wǎng)絡(luò)部件重要度，運(yùn)用啟發(fā)式算法逐步迭代實(shí)現(xiàn)了網(wǎng)絡(luò)k/N端可靠性分配，解決了無法對(duì)網(wǎng)絡(luò)應(yīng)用串聯(lián)模型開展可靠性分配的問題.以中國教育網(wǎng)（CERNET，China Education and Research Network）骨干網(wǎng)為案例，應(yīng)用該方法實(shí)現(xiàn)了75%網(wǎng)絡(luò)節(jié)點(diǎn)連通可靠性指標(biāo)的分配，并進(jìn)一步分析了迭代終止條件、網(wǎng)絡(luò)可靠性指標(biāo)要求等參數(shù)對(duì)分配結(jié)果的影響，通過繪制可靠性隨時(shí)間變化的曲線證明了分配結(jié)果能滿足網(wǎng)絡(luò)可靠性指標(biāo)要求，說明了該方法的正確性和適用性.

網(wǎng)絡(luò);可靠性;啟發(fā)式算法;二分搜索法

通過可靠性分配，可以把訂購方提出的系統(tǒng)可靠性指標(biāo)，自上而下，由大到小，從整體到局部，逐步分配到各分系統(tǒng)及設(shè)備.可靠性分配是系統(tǒng)論證、方案設(shè)計(jì)乃至工程研制階段的重要工作，用于確定分系統(tǒng)、設(shè)備可靠性指標(biāo).一般，系統(tǒng)可靠性分配方法主要包括等分配法、評(píng)分分配法、比例組合法、層次分析法、AGREE（Advisory Group on Reliability of Electronic Equipment）法（即:考慮重要度和復(fù)雜度的分配法）等［1］.對(duì)網(wǎng)絡(luò)而言，可靠性分配也是重要工作項(xiàng)目，根據(jù)網(wǎng)絡(luò)可靠性指標(biāo)來確定網(wǎng)絡(luò)部件可靠性指標(biāo)要求.然而，考慮到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的特殊性，簡(jiǎn)單地由串聯(lián)、并聯(lián)、旁聯(lián)、n中取r等模型組成的可靠性框圖并不能直接應(yīng)用于網(wǎng)絡(luò)可靠性建模，這也直接給網(wǎng)絡(luò)可靠性分配的實(shí)現(xiàn)帶來了困難.

研究者對(duì)網(wǎng)絡(luò)可靠性分配開展了大量研究.文獻(xiàn)［2］通過容斥原理法建立網(wǎng)絡(luò)可靠性與部件可靠性的函數(shù)關(guān)系 Rs=f（R1，R2，…，Rn），根據(jù)Ii=?Rs/?Ri確定部件重要度，并進(jìn)一步根據(jù)最優(yōu)分配法實(shí)現(xiàn)網(wǎng)絡(luò)可靠性分配.文獻(xiàn)［3］對(duì)最優(yōu)分配問題進(jìn)行了詳細(xì)的總結(jié)，雖然最優(yōu)分配法在理論計(jì)算上表現(xiàn)出諸多優(yōu)勢(shì)，但該方法以費(fèi)用、重量等參數(shù)作為約束條件或優(yōu)化目標(biāo)，在系統(tǒng)設(shè)計(jì)早期相關(guān)的數(shù)據(jù)往往難以獲取，故而工程上應(yīng)用并不多.文獻(xiàn)［4］針對(duì)礦井通風(fēng)網(wǎng)絡(luò)研究了可靠性的比例組合分配法，然而，工程實(shí)踐中使用比例組合法的前提是要有相似系統(tǒng)，對(duì)網(wǎng)絡(luò)來說，其拓?fù)浣Y(jié)構(gòu)組成形式多樣，往往難于找到相似網(wǎng)絡(luò).文獻(xiàn)［5］針對(duì)C4ISR系統(tǒng)應(yīng)用了AGREE分配法，為了適應(yīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，通過頻率、交換速度、數(shù)據(jù)大小定義了部件的重要度，為基于AGREE法的網(wǎng)絡(luò)可靠性分配提供了新思路.然而，這里的重要度定義并沒有考慮網(wǎng)絡(luò)中大量存在的路徑冗余，其可靠性分配結(jié)果尚缺少對(duì)網(wǎng)絡(luò)連通能力的考量.

在眾多經(jīng)典的可靠性分配方法中，等分配法完全不考慮網(wǎng)絡(luò)結(jié)構(gòu)，實(shí)際工程上不可用;評(píng)分分配法主觀性強(qiáng)，極大程度上依賴于專家的智慧;比例組合法能否使用取決于是否存在相似網(wǎng)絡(luò)，這一前提條件過于苛刻;層次分析法的缺陷與專家評(píng)分法類似，只是采用數(shù)學(xué)驗(yàn)證手段，在一定程度上限制了評(píng)分人犯錯(cuò)誤的可能性;最優(yōu)分配法所需考慮因素較多，除可靠性外還需結(jié)合費(fèi)用、重量等信息，在這些信息未知的情況下無法應(yīng)用;AGREE法綜合考慮了部件故障對(duì)系統(tǒng)故障的影響（即部件重要度）以及部件設(shè)計(jì)的復(fù)雜度，是工程中大量使用的可靠性分配方法［6］，但其使用前提要求分系統(tǒng)是串聯(lián)結(jié)構(gòu)，顯然網(wǎng)絡(luò)對(duì)象無法滿足這一前提條件，這對(duì)AGREE分配法在網(wǎng)絡(luò)可靠性中的應(yīng)用造成了障礙.

為此，本文在AGREE方法的基礎(chǔ)上，根據(jù)網(wǎng)絡(luò)可靠性與部件可靠性的函數(shù)關(guān)系確定網(wǎng)絡(luò)部件重要度，運(yùn)用二分搜索法確定基于重要度和復(fù)雜度的部件可靠性分配結(jié)果，并通過啟發(fā)式算法逐步迭代實(shí)現(xiàn)網(wǎng)絡(luò)k/N端可靠性分配結(jié)果的收斂，可有效支持網(wǎng)絡(luò)系統(tǒng)開展可靠性分配工作.

1 基本參數(shù)

網(wǎng)絡(luò)可靠性是指網(wǎng)絡(luò)在規(guī)定條件下和規(guī)定時(shí)間內(nèi)，完成規(guī)定功能的能力.對(duì)網(wǎng)絡(luò)而言，最重要的就是網(wǎng)絡(luò)連通功能.連通可靠性［7］成為網(wǎng)絡(luò)的重要指標(biāo)，其表示網(wǎng)絡(luò)在規(guī)定條件下和規(guī)定時(shí)間內(nèi)的連通能力.

將網(wǎng)絡(luò)表示為G（V，E），其中V表示網(wǎng)絡(luò)的節(jié)點(diǎn)集合，E表示網(wǎng)絡(luò)的鏈路集合.考慮到所度量的節(jié)點(diǎn)范圍不同，常用的連通可靠性度量參數(shù)包括:k/N端可靠度、K端可靠度、全端可靠度和兩端可靠度.

其中，k/N 端可靠度［8］表示網(wǎng)絡(luò) G（V，E）在規(guī)定條件下和規(guī)定時(shí)間內(nèi)，節(jié)點(diǎn)子集N（含n個(gè)節(jié)點(diǎn)）中至少k個(gè)節(jié)點(diǎn)之間能連通的概率（其中，N?V;2≤k≤n）.k/N端可靠度可表示為

式中，Rk/N（t）是t時(shí)刻網(wǎng)絡(luò)G（V，E）的k/N端可靠度;ξk/N是節(jié)點(diǎn)子集N中能相互連通的節(jié)點(diǎn)個(gè)數(shù)少于k前的工作時(shí)間;t是網(wǎng)絡(luò)規(guī)定的時(shí)間.

特殊地，當(dāng)k=n時(shí)，k/N端可靠度就是K端可靠度，表示網(wǎng)絡(luò)中指定節(jié)點(diǎn)子集K中所有節(jié)點(diǎn)之間保持連通的概率;當(dāng)N=V，且k=n時(shí)，k/N端可靠度就是全端可靠度，表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間保持連通的能力;當(dāng)n=2時(shí)，k/N端可靠度就是兩端可靠度，表示網(wǎng)絡(luò)中兩個(gè)指定節(jié)點(diǎn)之間保持連通的能力.也就是說，K端可靠度、全端可靠度和兩端可靠度都是k/N端可靠度的特殊情況.

2 算法

2.1AGREE分配法

AGREE分配法根據(jù)各單元產(chǎn)品的重要程度、復(fù)雜程度進(jìn)行可靠性指標(biāo)分配的方法.AGREE方法僅適用于由若干串聯(lián)的分系統(tǒng)組成的系統(tǒng)，而分系統(tǒng)內(nèi)部可以由串聯(lián)、并聯(lián)、旁聯(lián)、n中取r等各類關(guān)系的部件組成.假設(shè)部件的壽命服從指數(shù)分布，具體的分配方法如下:

式中，ti為第i個(gè)部件的工作時(shí)間;Ci為第i個(gè)部件的復(fù)雜度:

其中，N為整個(gè)系統(tǒng)的基本構(gòu)成單元個(gè)數(shù);ni為第i個(gè)部件的基本構(gòu)成單元個(gè)數(shù).

ωi為第i個(gè)部件的重要度，反應(yīng)了第i個(gè)部件故障影響任務(wù)完成的程度:

其中，Ii表示由于第i個(gè)部件故障引起系統(tǒng)故障的次數(shù);Fi表示第i個(gè)部件故障的次數(shù).

2.2 AGREE分配法的改進(jìn)

AGREE分配法體現(xiàn)了可靠性分配的2個(gè)基本原則:①對(duì)復(fù)雜程度高的部件，分配較低的可靠性指標(biāo);②對(duì)重要度高的部件，分配較高的可靠性指標(biāo).

由于網(wǎng)絡(luò)一般無法表示為串聯(lián)結(jié)構(gòu)，故而無法直接使用式（2）實(shí)現(xiàn)可靠性分配.這里仍然假設(shè)網(wǎng)絡(luò)中各個(gè)部件的壽命均服從指數(shù)分布，為了體現(xiàn)AGREE分配法的2個(gè)基本原則，要求:

在網(wǎng)絡(luò)對(duì)象上實(shí)現(xiàn)基于式（5）的可靠性分配，需要解決兩個(gè)問題:一是如何確定網(wǎng)絡(luò)部件的重要度;二是如何得出部件的分配結(jié)果.

對(duì)問題一，由于式（4）表達(dá)的重要度計(jì)算公式是基于統(tǒng)計(jì)數(shù)據(jù)的，無法解析計(jì)算，這里運(yùn)用文獻(xiàn)［2］中使用的概率重要度:

上式反映了部件可靠度變化對(duì)系統(tǒng)可靠度的影響.

對(duì)問題二，由于Ri=exp（－λiti），部件可靠性分配結(jié)果和部件重要度在式（5）和式（6）中相互引用，這里應(yīng)用啟發(fā)式算法反復(fù)迭代計(jì)算，算法如下:

1）應(yīng)用狀態(tài)枚舉法、容斥原理、不交積和、因子分解等方法［9］確定網(wǎng)絡(luò)系統(tǒng)可靠性與部件可靠性的函數(shù)關(guān)系 Rs=f（R1，R2，…，Rn）;

2）令部件初始重要度相同ω1=ω2=…=ωm=1，根據(jù)部件所包含元件數(shù)量應(yīng)用式（3）確定部件復(fù)雜度Ci，并確定部件工作時(shí)間ti;

3）根據(jù)ai=Ci/（ωiti）計(jì)算出部件故障率系數(shù)ai，令部件故障率λi=aiX（其中，X為常數(shù)），即Ri=exp（－λiti）=exp（－aitiX），應(yīng)用二分搜索法［10］求解滿足式（7）的 X.

3 案例

下面以中國教育網(wǎng)（CERNET，China Education and Research Network）骨干網(wǎng)為例進(jìn)行可靠性分配，CERNET骨干網(wǎng)拓?fù)浣Y(jié)構(gòu)如圖1所示.

圖1 CERNET骨干網(wǎng)拓?fù)浣Y(jié)構(gòu)

令CERNET的考察節(jié)點(diǎn)為全部8個(gè)骨干節(jié)點(diǎn)，即指定節(jié)點(diǎn)集N={北京，沈陽，西安，成都，武漢，南京，上海，廣州}，要求該網(wǎng)絡(luò)在運(yùn)行1 a時(shí)間以后75%骨干網(wǎng)節(jié)點(diǎn)的連通可靠度至少要達(dá)到0.99，即 R*6/N（365×24）≥0.99.下面采用本文的方法進(jìn)行可靠性分配，確定各節(jié)點(diǎn)可靠度指標(biāo)Ri.假設(shè)節(jié)點(diǎn)故障服從指數(shù)分布，鏈路絕對(duì)可靠.

首先運(yùn)用狀態(tài)空間枚舉法，確定網(wǎng)絡(luò)系統(tǒng)可靠性與部件可靠性的函數(shù)關(guān)系:

應(yīng)用2.2節(jié)提出的算法，迭代9次達(dá)到迭代終止條件ε=0.001.表1是逐次迭代得到的CERNET骨干網(wǎng)各節(jié)點(diǎn)可靠性分配結(jié)果，表中陰影表示與前次可靠度分配值之差超過ε=0.001的節(jié)點(diǎn).由此看出，隨著迭代過程分配結(jié)果逐漸趨于穩(wěn)定.最后一次迭代結(jié)果為CERNET可靠性分配結(jié)果，即要求各節(jié)點(diǎn)運(yùn)行1 a后的可靠度達(dá)到:

表1 CERNET骨干網(wǎng)節(jié)點(diǎn)可靠性分配迭代結(jié)果

歷次迭代過程中各節(jié)點(diǎn)的可靠度分配結(jié)果與最終分配結(jié)果的均方誤差隨著迭代次數(shù)的增多，逐漸減小，如圖2所示.這說明本文提出的基于啟發(fā)式的算法在案例應(yīng)用中具有良好的收斂性.

圖2 CERNET骨干網(wǎng)可靠性分配迭代過程的均方誤差

分配完成后，應(yīng)用 Rs=f（R1，R2，…，Rn）計(jì)算出網(wǎng)絡(luò)可靠度隨時(shí)間的變化關(guān)系如圖3所示.由于迭代過程中始終需要滿足R*s≤f（R1，R2，…，Rn），故而網(wǎng)絡(luò)在運(yùn)行1 a時(shí)間后75%骨干網(wǎng)節(jié)點(diǎn)的連通可靠度至少達(dá)到0.95的指標(biāo)要求必然可以達(dá)到.

迭代終止條件ε的選取對(duì)分配效率和分配精度有影響.ε越小，所需迭代次數(shù)越大，計(jì)算時(shí)間越長(zhǎng).當(dāng)ε小到某種程度時(shí)，迭代次數(shù)和計(jì)算時(shí)間會(huì)迅速增加，如表2所示.

圖3 CERNET骨干網(wǎng)可靠度隨時(shí)間變化情況

表2 ε取值對(duì)迭代次數(shù)的影響

這里的計(jì)算時(shí)間是由MATLAB程序執(zhí)行得來的.同時(shí)，表2的結(jié)果還反映出，在本案例中迭代終止條件ε的選取對(duì)本文提出的啟發(fā)式算法的收斂性不產(chǎn)生影響.

當(dāng)網(wǎng)絡(luò)可靠性要求值不同時(shí)，各節(jié)點(diǎn)的分配結(jié)果不同，如圖4所示.由于北京節(jié)點(diǎn)的重要性，隨著網(wǎng)絡(luò)可靠性指標(biāo)要求的下降，北京節(jié)點(diǎn)可靠度分配結(jié)果的下降幅度遠(yuǎn)小于其他節(jié)點(diǎn).

圖4 CERNET骨干網(wǎng)可靠性指標(biāo)不同時(shí)的分配結(jié)果

4 結(jié)束語

可靠性分配是網(wǎng)絡(luò)系統(tǒng)論證和設(shè)計(jì)過程中的重要工作，然而目前工程常用的可靠性分配方法要么依賴于相似產(chǎn)品數(shù)據(jù)、依賴于專家經(jīng)驗(yàn);要么受到網(wǎng)絡(luò)結(jié)構(gòu)限制，并不能直接應(yīng)用到網(wǎng)絡(luò)中.本文以經(jīng)典的AGREE方法為基礎(chǔ)，研究了基于啟發(fā)式算法的網(wǎng)絡(luò)可靠性分配方法，根據(jù)網(wǎng)絡(luò)可靠性與部件可靠性的函數(shù)關(guān)系確定網(wǎng)絡(luò)部件重要度，運(yùn)用二分搜索法確定基于重要度和復(fù)雜度的部件分配結(jié)果，通過啟發(fā)式算法逐次逼近，可有效地解決網(wǎng)絡(luò)k/N端可靠性分配問題，算法同時(shí)考慮了部件重要性和復(fù)雜性，并且編寫了基于MATLAB的計(jì)算程序，兼顧了工程操作性.

本算法的適用條件為:①網(wǎng)絡(luò)部件壽命服從指數(shù)分布;②能夠獲得網(wǎng)絡(luò)系統(tǒng)可靠性與部件可靠性的函數(shù)關(guān)系式.

通過CERNET案例研究，實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)75%節(jié)點(diǎn)連通可靠性的分配.隨著迭代次數(shù)增多，均方誤差逐漸減小，表現(xiàn)出良好的收斂性.

本方法具有良好擴(kuò)充性.對(duì)于一些特殊情況，如要求網(wǎng)絡(luò)中某些部件沿用可靠度已知的老部件，本方法也可將這些部件作為已知條件，參與迭代計(jì)算.然而，網(wǎng)絡(luò)可靠性的解析計(jì)算已被證明為NP（Nondeterministic Polynomial）難問題［11］，對(duì)于大規(guī)模網(wǎng)絡(luò)往往不容易建立網(wǎng)絡(luò)可靠性與部件可靠性的函數(shù)關(guān)系，這導(dǎo)致根據(jù)式（6）計(jì)算部件重要度的使用受限，可以通過蒙特卡洛仿真統(tǒng)計(jì)部件重要度的方式實(shí)現(xiàn)，這也是下一步需要研究的問題.

（References）

［1］康銳，石榮德，李瑞瑩.型號(hào)可靠性維修性保障性技術(shù)規(guī)范:第2冊(cè)［M］.北京:國防工業(yè)出版社，2010:38－70

Kang Rui，Shi Rongde，Li Ruiying.Reliability，maintainability and supportability specifications for material:volumeⅡ［M］.Beijing:National Defense Industry Press，2010:38－70（in Chinese）

［2］Adamantios Mettas.Reliability allocation and optimization for complex systems［C］//Proceedings Annual Reliability and Maintainability Symposium.Los Angeles，CA，USA:［s.n.］，2000:216－221

［3］Way Kuo，Rui Wan.Recent advances in optimal reliability allocation ［J］.IEEE Transactions on Systems，Man，and Cybernetics—Part A:Systems and Humans，2007，37（2）:143－156

［4］王洪德，馬云東.基于網(wǎng)絡(luò)模型的通風(fēng)系統(tǒng)可靠性分配方法研究［J］.煤，2003，12（3）:4－6

Wang Hongde，Ma Yundong.Study on reliability and it’s distribution technique of ventilation system based on network model［J］.Coal，2003，12（3）:4－6（in Chinese）

［5］郭浩.基于體系結(jié)構(gòu)的C4ISR系統(tǒng)可靠性建模及分配方法研究［D］.長(zhǎng)沙:國防科技大學(xué)信息系統(tǒng)與管理學(xué)院，2008

Guo Hao.Research on reliability modeling and allocation method of C4ISR system based on architecture［D］.Changsha:School of Information Managment and Systems，National University of Defense Technology，2008（in Chinese）

［6］Wang Yabin，Jia Xisheng，Zhao Jianmin，et al.Improvement of AGREE allocation method［C］//8th International Conference on Reliability，Maintainability and Safety.Chengdu，China:［s.n.］，2009:293－295

［7］Debany W H，Varshney P K，Hartmann C R P.Network reliability evaluation using probability expressions［J］.IEEE Transaction on Reliability，1986，35（2）:161－166

［8］Li Ruiying，Huang Ning，Kang Rui.A new parameter and its algorithm for network connection reliability:k/N-terminal reliability［C］//First International Conference on Future Information Networks.Beijing，China:［s.n.］，2009:259－262

［9］Douglas R Shier.Network reliability and algebraic structures［M］.Oxford:Clarendon Press，1991:8－17

［10］Jon Kleinberg，Eva Tardos.算法設(shè)計(jì)［M］.張立昂，屈婉玲譯.北京:清華大學(xué)出版社，2007

Jon Kleinberg，Eva Tardos.Algorithm design［M］.Translated by Zhang Li'ang，Qu Wanling.Beijing:Tsinghua University Press，2007（in Chinese）

［11］Michael O Ball.Complexity of network reliability computations［J］.Networks，1980，10（2）:153－165

Network reliability allocation method based on heuristic algorithm

Li Ruiying Ren Wuyue
（School of Reliability and Systems Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100191，China）

As network structure is difficult to be described with series and parallel models.Those traditional reliability allocation methods cannot be used by networks directly.A new method based on heuristic algorithm was advanced to solve the k/N terminal reliability allocation problem.Like advisory group on reliability of electronic equipment（AGREE）method，the new method also concerns about component importance and complexity.The component importance was calculated by taking partial derivatives of the function that relates component reliabilities to network reliability.The component complexity depends on the parts number which it owns.It solves the problem that the network reliability cannot be allocated by AGREE method with simple series models.This new method was applied to China education and research network（CERNET）backbone.Its reliability requirement，the connection probability among 75%of nodes，was allocated.It also discussed the affection to reliability allocation if some parameters，such as iteration termination value and network reliability requirements，shift.The curve of reliability over time verifies that the allocation results can meet reliability requirement of CERNET.The case study illustrates the applicability and correctness of this new allocation method.

networks;reliability;heuristic algorithms;binary search

TB 114.3

A

1001-5965（2012）02-0228-05

2010-10-29;< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2012-02-21 11:47;

CNKI:11-2625/V.20120221.1147.021

www.cnki.net/kcms/detail/11.2625.V.20120221.1147.021.html

北京市自然基金資助項(xiàng)目（4113074）

李瑞瑩（1982－），女，四川成都人，講師，liruiying@buaa.edu.cn.

（編 輯:婁 嘉）